Линейная  функция одинакова в обоих  случаях, изменяется только вид системы  ограничений. Открытая модель решается приведением к закрытой модели. В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель B_n+1, потребности которого  b_n+1 = . В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик A_m+1, запасы которого a_m+1 = .

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

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

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

1.4Составление опорного плана транспортной задачи.

     Методы составления опорного плана:

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

Пример. 

 

      Заполнение  таблицы начинается с ее северо-западного угла, т. е. клетки с неизвестным . Первая база может полностью удовлетворить потребность первого заказчика . Полагая , вписываем это значение в клетку и исключаем из рассмотрения первый столбец. На базе остается измененный запас . В оставшейся новой таблице с тремя строками и четырьмя столбцами ; северо-западным углом будет клетка для неизвестного . Первая база с запасом может полностью удовлетворить потребность второго заказчика . Полагаем , вписываем это значение в клетку и исключаем из рассмотрения второй столбец. На базе остается новый остаток (запас) . В оставшейся новой таблице с тремя строками и тремя столбцами северо-западным углом будет клетка для неизвестного . Теперь третий заказчик может принять весь запас с базы . Полагаем , вписываем это значение в клетку и исключаем из рассмотрения первую строку. У заказчика из осталась еще не удовлетворенной потребность .

      Теперь  переходим к заполнению клетки для  неизвестного и т.д.

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

      Общий объем перевозок в тонно-километрах для этого плана составит

 

. 

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

Пример. 

 

      В данном случае заполнение таблицы начинается с клетки для неизвестного , для которого мы имеем значение , наименьше из всех значений . Эта клетка находится на пересечении третьей строки и второго столбца, соответствующим третьей базе и второму заказчику . Третья база может полностью удовлетворить потребность второго заказчика . Полагая , вписываем это значение в клетку и исключаем из рассмотрения второй столбец. На базе остается изменённый запас . В оставшейся новой таблице с тремя строками и четырьмя столбцами клеткой с наименьшим значением клетка, где . Заполняем описанным выше способом эту клетку и аналогично заполняем следующие клетки. В результате оказываются заполненными (в приведенной последовательности) следующие клетки:  

.

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

 

. 

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

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

1.5 Методы решения транспортной задачи 

1.5.1 Метод потенциалов.

  При решении методом потенциалов необходимо:

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

 

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

 

1.5.1.1 Пример решения задачи методом потенциалов.

Дана  задача:

Вывозится продукция из 3 пунктов: A₁₌400, A₂₌970, A₃₌560;

Потребности в населенных пунктах: B₁₌540, B₂₌170, B₃₌980, B₄₌240;

Тарифы  из:  C_1,1=3,  C_1,2=5,  C_1,3=3,  C_1,4=5;

                                          C_2,1=3,   C_2,2=4,  C_2,3=5,  C_2,4=2;

                                                      C_3,1=3, C_3,2=2, C_3,3=4, C_3,4=2;

1) Опорный план. В данном примере мы строим опорный план методом наименьшей стоимости(см. стр.11):

 
 
 
 
 
 

Найдем целевую  функцию:

S₁ = 400*3 + 140*3 + 170*4 + 420*5 + 240*2 + 560*4 = 7120; 

2)Проведем ноль–преобразование таблицы тарифов(см. стр.7-8):

X₁+Y₁=-3; X₂=0; Y₁=-3;

X₂+Y₁=-3; X₁=2; Y₂=-4;

X₂+Y₂=-4; X₃=1; Y₃=-5;

X₂+Y₃=-5;  Y₄=-2;

X₂+Y₄=-2;  

X₃+Y₃=-4;   

3)Построим замкнутый контур:

 В клетках с перевозками находятся                                                                                           нулевые стоимости, но в остальных

 еще есть отрицательные стоимости т.е.

 проводим  еще раз ноль-преобразование.

И так до тех пор, пока не останется

отрицательных тарифов.

X₁+Y₃=-3             X₂=0; Y₁=-3;

X₂+Y₁=-3;            X₁=-2; Y₂=-4;

X₂+Y₂=-4;            X₃=1; Y₃=-5;

X₂+Y₃=-5; Y₄=-2;

X₂+Y₄=-2;  

X₃+Y₃=-4;  

 
 
 

X₁+Y₃=-3             X₂=0; Y₁=-3;

X₂+Y₁=-3;            X₁=-2; Y₂=-4;

X₂+Y₂=-4;            X₃=1; Y₃=-5;

X₂+Y₃=-5; Y₄=-2;

X₂+Y₄=-2;  

X₃+Y₃=-4;  

В итоге у  нас не осталось

отрицательных тарифов и 

все клетки с  перевозками обладают нулевыми тарифами, вывод это оптимальное решение. 

Находим целевую  функцию:

S₁ = 400*3 + 540*3 + 190*5 + 240*2 + 170*2 + 390*4 =6150; 

⁵1.5.2 Метод прямоугольников.

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

Прямоугольники  бывают трех типов:

1. обе диагонали не пустые;
2. одна диагональ полная, а вторая имеет одну нулевую перевозку;
3. одна диагональ полная, а другая пустая.

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

Прямоугольник у которого суммы тарифов по одной и по другой диагонали равны, называется нейтральным.

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