Решение открытой транспортной задачи

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

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

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

     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)  транспортной задачи является оптимальным, то ему соответствует набор из 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_i1 +  x_i2 + ... +  x_in = a_i  в исходной задаче соответствует переменная U_i (i = 1, 2, ..., m), а каждому ограничению вида  x_1j + x_2j + 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 .

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

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

U_i + V_j = C_ij   ;     ( 5 )

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

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) придают нулевое значение. После этого остальные потенциалы определяются однозначно.

Пусть известен потенциал U_i; тогда из равенства ( 5 ) следует

V_j = C_ij - U_i .

Если  известен потенциал V_j ,  то из того же равенства имеем

U_i = C_ij - V_j .

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

Набором называется произвольная совокупность перевозок транспортной таблицы.

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

Циклом  называется цепь, крайние элементы которой находятся либо в одной строке, либо в одном столбце. 
 
 
 
 
 
 
 
 
 

       1.5.Критерий оптимальности  базисного решения транспортной задачи 

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

Полученные  при этом коэффициенты затрат свободных клеток равны оценкам этих клеток. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    1.6. Распределительный  метод решения  транспортной задачи 

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

    Пусть для транспортной задачи найдено начальное опорное решение и вычислено значение целевой функции на этом решении Z( ). По теореме для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Означив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину = , можно получить новое опорное решение Х₂.