1. Транспортная модель будет иметь следующий вид: требуется составить план перевозок x = (x[sub]11[/sub], x[sub]12[/sub],..., x[sub]15[/sub], x[sub]21[/sub],..., x[sub]25[/sub], x[sub]31[/sub],..., x[sub]35[/sub]), удовлетворяющий условиям


и минимизирующий целевую функцию


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

2. Метод наименьших стоимостей состоит в следующем:
выбираем перевозку с наименьшей стоимостью (если таких несколько, выбираем любую);
определяем максимально возможную отгрузку как минимум из величины потребности соответствующего потребителя и запаса соответствующего поставщика;
уменьшаем потребность и запас на величину отгрузки;
если потребность стала равна нулю, то исключаем соответствующего потребителя из дальнейшего рассмотрения;
аналогично, если запас стал равен нулю, то исключаем соответствующего поставщика;
повторяем для оставшихся потребителей и поставщиков, пока не будут распределены все запасы и удовлетворены все потребности.
Метод удобно реализовать в виде таблицы, которая в данном случае будет иметь следующий вид:
[table]
[row][col]28[/col][col]12[/col][col]7[/col][col]18[/col][col]7[/col][col]280[/col][/row]
[row][col]35[/col][col]14[/col][col]12[/col][col]15[/col][col]3[/col][col]300[/col][/row]
[row][col]30[/col][col]16[/col][col]11[/col][col]25[/col][col]15[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][/row]
[/table]Здесь правый столбец содержит запасы, нижняя строка - потребности, нижняя правая клетка - общий баланс, остальные клетки - стоимость перевозок. Наименьшая стоимость перевозки в таблице равна 3 (клетка 2:5). Потребность равна 180, запас - 300, поэтому отгрузка будет равна min(180,300)=180.
[table]
[row][col]28[/col][col]12[/col][col]7[/col][col]18[/col][col]7[/col][col]280[/col][/row]
[row][col]35[/col][col]14[/col][col]12[/col][col]15[/col][col gray]3[/col][col gray]300[/col][/row]
[row][col]30[/col][col]16[/col][col]11[/col][col]25[/col][col]15[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col gray]180[/col][col]800[/col][/row]
[/table]Потребность потребителя 5 стала равна 180-180=0, запас поставщика 2 стал равен 300-180=120, поэтому исключаем из дальнейшего рассмотрения пятый столбец (соответствующую потребителю 5).
[table]
[row][col]28[/col][col]12[/col][col]7[/col][col]18[/col][col silver]7[/col][col]280[/col][/row]
[row][col]35[/col][col]14[/col][col]12[/col][col]15[/col][col lime]3*180[/col][col]120[/col][/row]
[row][col]30[/col][col]16[/col][col]11[/col][col]25[/col][col silver]15[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col silver]0[/col][col]620[/col][/row]
[/table]В оставшейся части таблицы наименьшая стоимость перевозки будет равна 7 (клетка 1:3). Потребность равна 190, запас - 280, поэтому отгрузка будет равна min(190,280)=190.
[table]
[row][col]28[/col][col]12[/col][col gray]7[/col][col]18[/col][col silver]7[/col][col gray]280[/col][/row]
[row][col]35[/col][col]14[/col][col]12[/col][col]15[/col][col lime]3*180[/col][col]120[/col][/row]
[row][col]30[/col][col]16[/col][col]11[/col][col]25[/col][col silver]15[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col gray]190[/col][col]140[/col][col silver]0[/col][col]620[/col][/row]
[/table]Потребность потребителя 3 стала равна 190-190=0, запас поставщика 1 стал равен 280-190=90, поэтому исключаем из дальнейшего рассмотрения третий столбец.
[table]
[row][col]28[/col][col]12[/col][col lime]7*190[/col][col]18[/col][col silver]7[/col][col gray]90[/col][/row]
[row][col]35[/col][col]14[/col][col silver]12[/col][col]15[/col][col lime]3*180[/col][col]120[/col][/row]
[row][col]30[/col][col]16[/col][col silver]11[/col][col]25[/col][col silver]15[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col silver]0[/col][col]140[/col][col silver]0[/col][col]430[/col][/row]
[/table]Дальше действуем аналогично: клетка 1:2 (стоимость 12) с отгрузкой min(120,90)=90 и исключением первого поставщика
[table]
[row][col silver]28[/col][col lime]12*90[/col][col lime]7*190[/col][col silver]18[/col][col silver]7[/col][col silver]0[/col][/row]
[row][col]35[/col][col]14[/col][col silver]12[/col][col]15[/col][col lime]3*180[/col][col]120[/col][/row]
[row][col]30[/col][col]16[/col][col silver]11[/col][col]25[/col][col silver]15[/col][col]220[/col][/row]
[row][col]170[/col][col]30[/col][col silver]0[/col][col]140[/col][col silver]0[/col][col]340[/col][/row]
[/table]клетка 2:2 (стоимость 14) с отгрузкой min(30,120)=30 и исключением второго потребителя
[table]
[row][col silver]28[/col][col lime]12*90[/col][col lime]7*190[/col][col silver]18[/col][col silver]7[/col][col silver]0[/col][/row]
[row][col]35[/col][col lime]14*30[/col][col silver]12[/col][col]15[/col][col lime]3*180[/col][col]90[/col][/row]
[row][col]30[/col][col silver]16[/col][col silver]11[/col][col]25[/col][col silver]15[/col][col]220[/col][/row]
[row][col]170[/col][col silver]0[/col][col silver]0[/col][col]140[/col][col silver]0[/col][col]310[/col][/row]
[/table]клетка 2:4 (стоимость 15) с отгрузкой min(140,90)=90 и исключением второго поставщика
[table]
[row][col silver]28[/col][col lime]12*90[/col][col lime]7*190[/col][col silver]18[/col][col silver]7[/col][col silver]0[/col][/row]
[row][col silver]35[/col][col lime]14*30[/col][col silver]12[/col][col lime]15*90[/col][col lime]3*180[/col][col silver]0[/col][/row]
[row][col]30[/col][col silver]16[/col][col silver]11[/col][col]25[/col][col silver]15[/col][col]220[/col][/row]
[row][col]170[/col][col silver]0[/col][col silver]0[/col][col]50[/col][col silver]0[/col][col]220[/col][/row]
[/table]для единственного оставшегося поставщика 3 отгрузки выбираются однозначно
[table]
[row][col silver]28[/col][col lime]12*90[/col][col lime]7*190[/col][col silver]18[/col][col silver]7[/col][col silver]0[/col][/row]
[row][col silver]35[/col][col lime]14*30[/col][col silver]12[/col][col lime]15*90[/col][col lime]3*180[/col][col silver]0[/col][/row]
[row][col lime]30*170[/col][col silver]16[/col][col silver]11[/col][col lime]25*50[/col][col silver]15[/col][col silver]0[/col][/row]
[row][col silver]0[/col][col silver]0[/col][col silver]0[/col][col silver]0[/col][col silver]0[/col][col silver]0[/col][/row]
[/table]Все строки и столбцы исключены (то есть оставшиеся потребности и запасы равны нулю), следовательно, опорный план построен верно. Вычислим общую стоимость перевозок:


3. Метод потенциалов для оптимизации опорного решения выглядит следующим образом:
всем поставщикам i и потребителям j ставим в соответствие некоторые значения u[sub]i[/sub] и v[sub]j[/sub], называемые потенциалами. Один из потенциалов задаём (например, u[sub]1[/sub]=0), остальные определяем исходя из того, что для стоимости c[sub]ij[/sub] поставки, входящей в опорное решение, должно выполняться равенство c[sub]ij[/sub]=u[sub]i[/sub]+v[sub]j[/sub];
находим для всех поставок оценки по формуле ?[sub]ij[/sub]=c[sub]ij[/sub]-(u[sub]i[/sub]+v[sub]j[/sub]). Для поставок, входящих в опорное решение, они будут нулевые, для остальных могут отличаться от нуля;
если нет отрицательных оценок, то текущее решение является оптимальным, и оптимизация заканчивается;
в противном случае выбираем ячейку с наименьшей оценкой (то есть с максимальной по абсолютной величине отрицательной оценкой;
начиная с выбранной ячейки, строим в таблице замкнутый цикл, содержащий ячейки опорного решения;
обходим ячейки цикла в произвольном порядке, помечая их по очереди как "положительные" и "отрицательные" (выбранная ячейка с наименьшей оценкой помечается как "положительная");
находим минимальное значение величины поставки для всех "отрицательных" ячеек;
уменьшаем на эту величину объёмы поставок для всех "отрицательных" ячеек цикла и увеличиваем - для всех "положительных";
получаем новое опорное решение, для которого повторяем всё сначала.

Используем метод потенциалов для оптимизации полученного опорного решения:
[table]
[row][col]28[/col][col lime]12*90[/col][col lime]7*190[/col][col]18[/col][col]7[/col][col]280[/col][/row]
[row][col]35[/col][col lime]14*30[/col][col]12[/col][col lime]15*90[/col][col lime]3*180[/col][col]300[/col][/row]
[row][col lime]30*170[/col][col]16[/col][col]11[/col][col lime]25*50[/col][col]15[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][/row]
[/table]Вычислим потенциалы:
u[sub]1[/sub]=0;
c[sub]12[/sub]=u[sub]1[/sub]+v[sub]2[/sub]=12 [$8658$] v[sub]2[/sub]=12-0=12;
c[sub]13[/sub]=u[sub]1[/sub]+v[sub]3[/sub]=7 [$8658$] v[sub]4[/sub]=7-0=7;
c[sub]22[/sub]=u[sub]2[/sub]+v[sub]2[/sub]=14 [$8658$] u[sub]2[/sub]=14-12=2;
c[sub]24[/sub]=u[sub]2[/sub]+v[sub]4[/sub]=15 [$8658$] v[sub]4[/sub]=15-2=13;
c[sub]25[/sub]=u[sub]2[/sub]+v[sub]5[/sub]=3 [$8658$] v[sub]5[/sub]=3-2=1;
c[sub]34[/sub]=u[sub]3[/sub]+v[sub]4[/sub]=25 [$8658$] u[sub]3[/sub]=25-13=12;
c[sub]31[/sub]=u[sub]3[/sub]+v[sub]1[/sub]=30 [$8658$] v[sub]1[/sub]=30-12=18
добавим их в таблицу:
[table]
[row][col]28[/col][col lime]12*90[/col][col lime]7*190[/col][col]18[/col][col]7[/col][col]280[/col][col]0[/col][/row]
[row][col]35[/col][col lime]14*30[/col][col]12[/col][col lime]15*90[/col][col lime]3*180[/col][col]300[/col][col]2[/col][/row]
[row][col lime]30*170[/col][col]16[/col][col]11[/col][col lime]25*50[/col][col]15[/col][col]220[/col][col]12[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][col][/col][/row]
[row][col]18[/col][col]12[/col][col]7[/col][col]13[/col][col]1[/col][col][/col][col][/col][/row]
[/table]найдём оценки поставок:
[$916$][sub]11[/sub]=c[sub]11[/sub]-(u[sub]1[/sub]+v[sub]1[/sub])=28-(0+18)=10;
[$916$][sub]14[/sub]=c[sub]14[/sub]-(u[sub]1[/sub]+v[sub]4[/sub])=18-(0+13)=5;
[$916$][sub]15[/sub]=c[sub]15[/sub]-(u[sub]1[/sub]+v[sub]5[/sub])=7-(0+1)=7;
[$916$][sub]21[/sub]=c[sub]21[/sub]-(u[sub]2[/sub]+v[sub]1[/sub])=35-(2+18)=15;
[$916$][sub]23[/sub]=c[sub]23[/sub]-(u[sub]2[/sub]+v[sub]3[/sub])=12-(2+7)=3;
[$916$][sub]32[/sub]=c[sub]32[/sub]-(u[sub]3[/sub]+v[sub]2[/sub])=16-(12+12)=-8;
[$916$][sub]33[/sub]=c[sub]33[/sub]-(u[sub]3[/sub]+v[sub]3[/sub])=11-(12+7)=-8;
[$916$][sub]35[/sub]=c[sub]35[/sub]-(u[sub]3[/sub]+v[sub]5[/sub])=15-(12+1)=2
(остальные равны 0) и добавим их в таблицу (для ячеек, не входящих в опорное решение):
[table]
[row][col]28/10[/col][col lime]12*90[/col][col lime]7*190[/col][col]18/5[/col][col]7/7[/col][col]280[/col][/row]
[row][col]35/15[/col][col lime]14*30[/col][col]12/3[/col][col lime]15*90[/col][col lime]3*180[/col][col]300[/col][/row]
[row][col lime]30*170[/col][col]16/-8[/col][col]11/-8[/col][col lime]25*50[/col][col]15/2[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][/row]
[/table](значения потенциалов больше не требуются). Отрицательную оценку (-8) содержат две ячейки - 3:2 и 3:3. Выберем любую, например 3:2. Вместе с ячейками 2:2, 2:4 и 3:4 она образует замкнутый цикл, в котором ячейки 3:2 и 2:4 - "положительные", а 2:2 и 3:4 - "отрицательные":
[table]
[row][col]28/10[/col][col lime]12*90[/col][col lime]7*190[/col][col]18/5[/col][col]7/7[/col][col]280[/col][/row]
[row][col]35/15[/col][col gray]14*30[/col][col]12/3[/col][col lightgray]15*90[/col][col lime]3*180[/col][col]300[/col][/row]
[row][col lime]30*170[/col][col lightgray]16/-8[/col][col]11/-8[/col][col gray]25*50[/col][col]15/2[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][/row]
[/table]Среди "отрицательных" ячеек наименьшее значение поставки достигается в 2:2 (30). Уменьшаем на 30 объём поставок для ячеек 2:2 и 3:4, увеличиваем на 30 объём поставок для ячеек 3:2 и 2:4. Получаем новое опорное решение:
[table]
[row][col]28[/col][col lime]12*90[/col][col lime]7*190[/col][col]18[/col][col]7[/col][col]280[/col][/row]
[row][col]35[/col][col]14[/col][col]12[/col][col lime]15*120[/col][col lime]3*180[/col][col]300[/col][/row]
[row][col lime]30*170[/col][col lime]16*30[/col][col]11[/col][col lime]25*20[/col][col]15[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][/row]
[/table]и вычисляем новую стоимость перевозок:

Можно заметить, что по сравнению с исходным опорным решением стоимость изменилась на величину -240 = -8·30, равную произведению оценки выбранной ячейки (-8) на величину изменения объёмов поставок для ячеек цикла (30).
Вычислим потенциалы:
u[sub]1[/sub]=0;
c[sub]12[/sub]=u[sub]1[/sub]+v[sub]2[/sub]=12 [$8658$] v[sub]2[/sub]=12-0=12;
c[sub]13[/sub]=u[sub]1[/sub]+v[sub]3[/sub]=7 [$8658$] v[sub]3[/sub]=7-0=7;
c[sub]32[/sub]=u[sub]3[/sub]+v[sub]2[/sub]=16 [$8658$] u[sub]3[/sub]=16-12=4;
c[sub]31[/sub]=u[sub]3[/sub]+v[sub]1[/sub]=30 [$8658$] v[sub]1[/sub]=30-4=26;
c[sub]34[/sub]=u[sub]3[/sub]+v[sub]4[/sub]=25 [$8658$] v[sub]4[/sub]=25-4=21;
c[sub]24[/sub]=u[sub]2[/sub]+v[sub]4[/sub]=15 [$8658$] u[sub]2[/sub]=15-21=-6;
c[sub]25[/sub]=u[sub]2[/sub]+v[sub]5[/sub]=3 [$8658$] v[sub]5[/sub]=3-(-6)=9
добавим их в таблицу
[table]
[row][col]28[/col][col lime]12*90[/col][col lime]7*190[/col][col]18[/col][col]7[/col][col]280[/col][col]0[/col][/row]
[row][col]35[/col][col]14[/col][col]12[/col][col lime]15*120[/col][col lime]3*180[/col][col]300[/col][col]-6[/col][/row]
[row][col lime]30*170[/col][col lime]16*30[/col][col]11[/col][col lime]25*20[/col][col]15[/col][col]220[/col][col]4[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][col][/col][/row]
[row][col]26[/col][col]12[/col][col]7[/col][col]21[/col][col]9[/col][col][/col][col][/col][/row]
[/table]найдём ненулевые оценки поставок:
[$916$][sub]11[/sub]=c[sub]11[/sub]-(u[sub]1[/sub]+v[sub]1[/sub])=28-(0+26)=2;
[$916$][sub]14[/sub]=c[sub]14[/sub]-(u[sub]1[/sub]+v[sub]4[/sub])=18-(0+9)=9;
[$916$][sub]15[/sub]=c[sub]15[/sub]-(u[sub]1[/sub]+v[sub]5[/sub])=7-(0+9)=-2;
[$916$][sub]21[/sub]=c[sub]21[/sub]-(u[sub]2[/sub]+v[sub]1[/sub])=35-(-6+26)=15;
[$916$][sub]22[/sub]=c[sub]22[/sub]-(u[sub]2[/sub]+v[sub]2[/sub])=14-(-6+12)=8;
[$916$][sub]23[/sub]=c[sub]23[/sub]-(u[sub]2[/sub]+v[sub]3[/sub])=12-(-6+7)=11;
[$916$][sub]33[/sub]=c[sub]33[/sub]-(u[sub]3[/sub]+v[sub]3[/sub])=11-(4+7)=0;
[$916$][sub]35[/sub]=c[sub]35[/sub]-(u[sub]3[/sub]+v[sub]5[/sub])=15-(4+9)=2
и добавим их в таблицу:
[table]
[row][col]28/2[/col][col lime]12*90[/col][col lime]7*190[/col][col]18/9[/col][col]7/-2[/col][col]280[/col][/row]
[row][col]35/15[/col][col]14/8[/col][col]12/11[/col][col lime]15*120[/col][col lime]3*180[/col][col]300[/col][/row]
[row][col lime]30*170[/col][col lime]16*30[/col][col]11/0[/col][col lime]25*20[/col][col]15/2[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][/row]
[/table]Отрицательную оценку (-2) содержит ячеёка 1:5. Вместе с ячейками 1:2, 3:2, 3:4, 2:4 и 2:5 она образует замкнутый цикл, в котором ячейки 1:5, 3:2 и 2:4 - "положительные", а 1:2, 3:4 и 2:5 - "отрицательные":
[table]
[row][col]28/2[/col][col gray]12*90[/col][col lime]7*190[/col][col]18/9[/col][col lightgray]7/-2[/col][col]280[/col][/row]
[row][col]35/15[/col][col]14/8[/col][col]12/11[/col][col lightgray]15*120[/col][col gray]3*180[/col][col]300[/col][/row]
[row][col lime]30*170[/col][col lightgray]16*30[/col][col]11/0[/col][col gray]25*20[/col][col]15/2[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][/row]
[/table]Среди "отрицательных" ячеек наименьшее значение поставки (20) достигается в 3:4. Уменьшаем на 20 объём поставок для ячеек 1:2, 3:4 и 2:5, увеличиваем на 20 объём поставок для ячеек 1:5, 3:2 и 2:4. Получаем новое опорное решение:
[table]
[row][col]28[/col][col lime]12*70[/col][col lime]7*190[/col][col]18[/col][col lime]7*20[/col][col]280[/col][/row]
[row][col]35[/col][col]14[/col][col]12[/col][col lime]15*140[/col][col lime]3*160[/col][col]300[/col][/row]
[row][col lime]30*170[/col][col lime]16*50[/col][col]11[/col][col]25[/col][col]15[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][/row]
[/table]и вычисляем новую стоимость перевозок:

либо как

Для нового решения вычислим потенциалы:
u[sub]1[/sub]=0;
c[sub]12[/sub]=u[sub]1[/sub]+v[sub]2[/sub]=12 [$8658$] v[sub]2[/sub]=12-0=12;
c[sub]13[/sub]=u[sub]1[/sub]+v[sub]3[/sub]=7 [$8658$] v[sub]3[/sub]=7-0=7;
c[sub]15[/sub]=u[sub]1[/sub]+v[sub]5[/sub]=7 [$8658$] v[sub]5[/sub]=7-0=7;
c[sub]25[/sub]=u[sub]2[/sub]+v[sub]5[/sub]=3 [$8658$] u[sub]2[/sub]=3-7=-4;
c[sub]24[/sub]=u[sub]2[/sub]+v[sub]4[/sub]=15 [$8658$] v[sub]4[/sub]=15-(-4)=19;
c[sub]32[/sub]=u[sub]3[/sub]+v[sub]2[/sub]=16 [$8658$] u[sub]3[/sub]=16-12=4;
c[sub]31[/sub]=u[sub]3[/sub]+v[sub]1[/sub]=30 [$8658$] v[sub]1[/sub]=30-4=26;
добавим их в таблицу
[table]
[row][col]28[/col][col lime]12*70[/col][col lime]7*190[/col][col]18[/col][col lime]7*20[/col][col]280[/col][col]0[/col][/row]
[row][col]35[/col][col]14[/col][col]12[/col][col lime]15*140[/col][col lime]3*160[/col][col]300[/col][col]-4[/col][/row]
[row][col lime]30*170[/col][col lime]16*50[/col][col]11[/col][col]25[/col][col]15[/col][col]220[/col][col]4[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][col][/col][/row]
[row][col]26[/col][col]12[/col][col]7[/col][col]19[/col][col]7[/col][col][/col][col][/col][/row]
[/table]найдём ненулевые оценки поставок:
[$916$][sub]11[/sub]=c[sub]11[/sub]-(u[sub]1[/sub]+v[sub]1[/sub])=28-(0+26)=2;
[$916$][sub]14[/sub]=c[sub]14[/sub]-(u[sub]1[/sub]+v[sub]4[/sub])=18-(0+19)=-1;
[$916$][sub]21[/sub]=c[sub]21[/sub]-(u[sub]2[/sub]+v[sub]1[/sub])=35-(-4+26)=13;
[$916$][sub]22[/sub]=c[sub]22[/sub]-(u[sub]2[/sub]+v[sub]2[/sub])=14-(-4+12)=6;
[$916$][sub]23[/sub]=c[sub]23[/sub]-(u[sub]2[/sub]+v[sub]3[/sub])=12-(-4+7)=9;
[$916$][sub]33[/sub]=c[sub]33[/sub]-(u[sub]3[/sub]+v[sub]3[/sub])=11-(4+7)=0;
[$916$][sub]34[/sub]=c[sub]34[/sub]-(u[sub]3[/sub]+v[sub]4[/sub])=25-(4+19)=2;
[$916$][sub]35[/sub]=c[sub]35[/sub]-(u[sub]3[/sub]+v[sub]5[/sub])=15-(4+9)=2
и добавим их в таблицу:
[table]
[row][col]28/2[/col][col lime]12*70[/col][col lime]7*190[/col][col]18/-1[/col][col lime]7*20[/col][col]280[/col][/row]
[row][col]35/13[/col][col]14/6[/col][col]12/9[/col][col lime]15*140[/col][col lime]3*160[/col][col]300[/col][/row]
[row][col lime]30*170[/col][col lime]16*50[/col][col]11/0[/col][col]25/2[/col][col]15/2[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][/row]
[/table]Отрицательную оценку (-1) содержит ячеёка 1:4. Вместе с ячейками 2:4, 2:5 и 3:5 она образует замкнутый цикл, в котором ячейки 1:4 и 2:5 - "положительные", а 2:4 и 1:5 - "отрицательные":
[table]
[row][col]28/2[/col][col lime]12*70[/col][col lime]7*190[/col][col lightgray]18/-1[/col][col gray]7*20[/col][col]280[/col][/row]
[row][col]35/13[/col][col]14/6[/col][col]12/9[/col][col gray]15*140[/col][col lightgray]3*160[/col][col]300[/col][/row]
[row][col lime]30*170[/col][col lime]16*50[/col][col]11/0[/col][col]25/2[/col][col]15/2[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][/row]
[/table]Среди "отрицательных" ячеек наименьшее значение поставки (20) достигается в 1:5. Уменьшаем на 20 объём поставок для ячеек 1:5 и 2:4, увеличиваем на 20 объём поставок для ячеек 1:4 и 2:5. Получаем новое опорное решение:
[table]
[row][col]28[/col][col lime]12*70[/col][col lime]7*190[/col][col lime]18*20[/col][col]7[/col][col]280[/col][/row]
[row][col]35[/col][col]14[/col][col]12[/col][col lime]15*120[/col][col lime]3*180[/col][col]300[/col][/row]
[row][col lime]30*170[/col][col lime]16*50[/col][col]11[/col][col]25[/col][col]15[/col][col]220[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][/row]
[/table]и вычисляем новую стоимость перевозок:

либо как

Для нового решения вычислим потенциалы:
u[sub]1[/sub]=0;
c[sub]12[/sub]=u[sub]1[/sub]+v[sub]2[/sub]=12 [$8658$] v[sub]2[/sub]=12-0=12;
c[sub]13[/sub]=u[sub]1[/sub]+v[sub]3[/sub]=7 [$8658$] v[sub]3[/sub]=7-0=7;
c[sub]14[/sub]=u[sub]1[/sub]+v[sub]4[/sub]=18 [$8658$] v[sub]4[/sub]=18-0=18;
c[sub]24[/sub]=u[sub]2[/sub]+v[sub]4[/sub]=15 [$8658$] u[sub]2[/sub]=15-18=-3;
c[sub]25[/sub]=u[sub]2[/sub]+v[sub]5[/sub]=3 [$8658$] v[sub]5[/sub]=3-(-3)=6;
c[sub]32[/sub]=u[sub]3[/sub]+v[sub]2[/sub]=16 [$8658$] u[sub]3[/sub]=16-12=4;
c[sub]31[/sub]=u[sub]3[/sub]+v[sub]1[/sub]=30 [$8658$] v[sub]1[/sub]=30-4=26;
добавим их в таблицу
[table]
[row][col]28[/col][col lime]12*70[/col][col lime]7*190[/col][col lime]18*20[/col][col]7[/col][col]280[/col][col]0[/col][/row]
[row][col]35[/col][col]14[/col][col]12[/col][col lime]15*120[/col][col lime]3*180[/col][col]300[/col][col]-3[/col][/row]
[row][col lime]30*170[/col][col lime]16*50[/col][col]11[/col][col]25[/col][col]15[/col][col]220[/col][col]4[/col][/row]
[row][col]170[/col][col]120[/col][col]190[/col][col]140[/col][col]180[/col][col]800[/col][col][/col][/row]
[row][col]26[/col][col]12[/col][col]7[/col][col]18[/col][col]6[/col][col][/col][col][/col][/row]
[/table]найдём ненулевые оценки поставок:
[$916$][sub]11[/sub]=c[sub]11[/sub]-(u[sub]1[/sub]+v[sub]1[/sub])=28-(0+26)=2;
[$916$][sub]15[/sub]=c[sub]15[/sub]-(u[sub]1[/sub]+v[sub]5[/sub])=7-(0+5)=2;
[$916$][sub]21[/sub]=c[sub]21[/sub]-(u[sub]2[/sub]+v[sub]1[/sub])=35-(-3+26)=12;
[$916$][sub]22[/sub]=c[sub]22[/sub]-(u[sub]2[/sub]+v[sub]2[/sub])=14-(-3+12)=5;
[$916$][sub]23[/sub]=c[sub]23[/sub]-(u[sub]2[/sub]+v[sub]3[/sub])=12-(-3+7)=8;
[$916$][sub]33[/sub]=c[sub]33[/sub]-(u[sub]3[/sub]+v[sub]3[/sub])=11-(4+7)=0;
[$916$][sub]34[/sub]=c[sub]34[/sub]-(u[sub]3[/sub]+v[sub]4[/sub])=25-(4+18)=3;
[$916$][sub]35[/sub]=c[sub]35[/sub]-(u[sub]3[/sub]+v[sub]5[/sub])=15-(4+6)=5.
Отрицательных оценок нет, следовательно, последнее решение со стоимостью 10770 является оптимальным. Соответствующий план перевозок можно записать как