Решение открытой транспортной задачи (стр. 2 из 5)

Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.

Найти минимальное значение линейной функции

при ограничениях

, i = 1, 2, ..., m, (случай а)

, j = 1, 2, ..., n;

, i = 1, 2, ..., m, (случай б)

, j = 1, 2, ..., n,

x_ij³ 0 (i = 1, 2, ..., m; j = 1, 2, ..., n).

Открытая модель решается приведением к закрытой модели.

В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель B_n₊₁, потребности которого b_n₊₁ =

. В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик A_m₊₁, запасы которого a_m₊₁ =
.

Стоимость перевозки единицы груза как фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.

После преобразований задача принимает вид закрытой модели и решается обычном способом. При равных стоимостях перевозки единицы груза от поставщиков к фиктивному потребителю затраты на перевозку груза реальным потребителям минимальны, а фиктивному потребителю будет направлен груз от наименее выгодных поставщиков. То же самое получаем и в отношении фиктивного поставщика.

Прежде чем решать какую-нибудь транспортную задачу, необходимо сначала проверить, к какой модели она принадлежит, и только после этого составить таблицу для ее решения.

1.3. Методы составления начального опорного плана

Как и для других задач линейного программирования, итерационный процесс по отысканию оптимального плана транспортной задачи начинается с опорного плана .

Рассмотрим систему ограничений ( 2 ) и ( 3 ) транспортной задачи. Она содержит m´n неизвестных и m+n уравнений,

Связанных соотношением (4). Если сложить почленно уравнения отдельно подсистемы ( 2 ) и отдельно подсистемы ( 3 ), то получим два одинаковых уравнения . В таблице такое сложение равнозначно соответственно почленному сложению столбцов и почленно сложению строк .

Наличие в системе ограничений двух одинаковых уравнений говорит о ее линейной зависимости. Если одно из этих уравнений отбросить, то в общем случае система ограничений должна содержать m+n-1 линейно независимых уравнений, с

ледовательно, невырожденный опорный план транспортной задачи содержит m+n-1 положительных компонент или перевозок.

Таким образом, если каким-либо способом получен невырожденный опорный план транспортной задачи, то в матрице

( X_ij ) (i = 1, 2, ..., m; j = 1, 2, ... , n) значений его компонент (таблицы 2) положительными являются только

M+n-1, а остальные равны нулю.

Если условие транспортной задачи и ее опорный план записаны в виде таблицы, то клетки, в которых находятся отличные от нуля перевозки, называются занятыми, а остальные - незанятыми.

Занятые клетки соответствует неизвестным, и для невырожденного опорного плана их количество равно

M+n-1. Если ограничения транспортной задачи записаны в виде ( 2 ) и (3) то, как известно, базисным неизвестным, включенным в опорный план, соответствует система линейно независимых векторов.

Всякий план транспортной задачи, содержащий более

M+n-1 занятых клеток, не являются опорным, так как ему соответствует линейно зависимая система векторов. При таком плане в таблице всегда можно построить замкнутый цикл, с помощью которого уменьшают число занятых клеток до m+n-1.

Циклом называется набор клеток вида ( i₁ j₁ )( i₁ j₂ )*( j₂ i₂ )( j₁ i_m ), в котором две и только две соседние клетки расположены в одном столбце или одной строке таблицы, причем последняя клетка находится в той же строке или столбце, что и первая.

Если к занятым клеткам, определяющим опорный невырожденный план, следовательно, и ацикличный, присоединить какую-либо незанятую клетку, то план становится не опорным, появляется единственный цикл, все вершины которого, за исключением одной, лежат в занятых клетках.

Существует несколько простых схем построения первоначального опорного плана транспортной задачи.

При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Поэтому рассмотренный метод используется при вычислениях с помощью ЭВМ.

При

использовании метода минимальной стоимости запасы поставщиков перераспределяются потребителям по минимальным стоимостям , а в методе двойного предпочтения перераспределения предпочтительно производятся через те клетки ,чьи стоимости минимальны как для поставщиков , так и для потребителей .

Стоимости планов, полученных методами минимальной стоимости и двойного предпочтения меньше стоимости плана, полученного методом северно-западного угла, значит они ближе к оптимальному.

Между собой методы минимальной стоимости и двойного предпочтения равноценны, их легко программировать. Полученные планы доводят до оптимального методом потенциалов.

1.4. Понятие потенциала и цикла

Если план X* = (x*_ij) транспортной _oзадачи является оптимальным, то ему соответствует набор из m + n чисел U_i* и V_j* , удовлетворяющих условиям

U_i* + V_j* = C_ij для x_ij* > 0

U_i* + V_j* £ C_ij для x_ij* = 0

(i = 1, 2, 3, ..., m ; j = 1, 2, 3, ..., n) .

Числа U_i* и V_j* называются потенциалами соответственно поставщиков и потребителей.

Доказательство. Транспортную задачу минимизации линейной функции Z =

при ограничениях

x_i1 + x_i2+ ... + x_in= a_i, i = 1, 2, ... , m,

x_1j + x_2j + ... + x_mj= b_j, j = 1, 2, ... , n,

x_ij ? 0 (i = 1, 2, ... , m; j = 1, 2, ... , n)

можно рассматривать как двойственную некоторой исходной задачи линейного программирования, условия которой получаются по общей схеме, если каждому ограничению вида x_i₁ + x_i₂ + ... + x_in = a_i в исходной задаче соответствует переменная U_i (i = 1, 2, ..., m), а каждому ограничению вида x₁_j + x₂_j + x_mj = b_j - переменная V_j (j = 1, 2, ..., n), а именно: максимизировать линейную функцию f =

при ограничениях U_i + V_j £ C_ij

(i = 1, 2, ..., m; j = 1, 2, ..., n).

План X* является оптимальным планом двойственной задачи, поэтому план Y* = ( U_i*, V_j* ) является планом исходной задачи и на основании теоремы двойственности

max f = min Z

или

где x_ij* ³ 0_.

На основании теоремы о двойственной задаче, получаем что ограничения исходной задачи, соответствующие положительным компонентам оптимального плана двойственной задачи, удовлетворяются как строгие равенства, а соответствующие компонентам, равным нулю, ¾ как неравенства, т. е.

U_i* + V_j* = C_ij для x_ij* > 0 ,

Ui* + V_j* £ C_ij для x_ij* = 0 .

Из доказанной теоремы следует: для того чтобы первоначальный опорный план был оптимальным, необходимо выполнение следующих условий:

a) для каждой занятой клетки сумма потенциалов должна быть равна стоимости единицы перевозок, стоящей в этой клетке:

U_i+ V_j= C_ij ; ( 5 )

b) для каждой незанятой клетки сумма потенциалов должна быть меньше или равна стоимости единицы перевозки, стоящей в этой клетке :

U_i + V_j £ C_ij . ( 6 )

Если хотя бы одна незанятая клетка не удовлетворяет условию ( 6 ), то опорный план является неоптимальным и его можно улучшить, вводя в базис вектор, соответствующий клетке, для которой нарушается условие оптимальности,(т. е. в клетку надо переместить некоторое количество единиц груза).

Таким образом, для проверки на оптимальность необходимо сначала построить систему потенциалов.

Для построения системы потенциалов используем условие

U_i + V_j = C_ij

где C_ij¾ стоимость перевозки единицы груза занятой клетки в i-ой строке и j-м столбце .

Систему потенциалов можно построить только для невырожденного опорного плана. Такой план содержит m+n-1 линейно независимых уравнений вида (5) с

n+m неизвестными. Уравнений на одно меньше, чем неизвестных, поэтому система является неопределенной и одному неизвестному (обычно U_i) придают нулевое значение. После этого остальные потенциалы определяются однозначно.