Здравствуйте, alenchik2545!

1. Метод северо-западного угла состоит в следующем:
перебираем ячейки таблицы, начиная с левой верхней ("северо-западной");
для очередной ячейки определяем максимально возможную отгрузку как минимум из величины потребности соответствующего потребителя и запаса соответствующего поставщика;
уменьшаем потребность и запас на величину отгрузки;
если потребность стала равна нулю, то исключаем соответствующий столбец (потребителя) из дальнейшего рассмотрения;
аналогично, если запас стал равен нулю, то исключаем соответствующую строку (поставщика);
повторяем для оставшейся части таблицы, пока не дойдём до правой нижней ячейки.

В данном случае исходная таблица имеет вид:
[table]
[row][col]Номер[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запасы[/col][/row]
[row][col]1[/col][col gray][/col][col][/col][col][/col][col][/col][col gray]140[/col][/row]
[row][col]2[/col][col][/col][col][/col][col][/col][col][/col][col]210[/col][/row]
[row][col]3[/col][col][/col][col][/col][col][/col][col][/col][col]190[/col][/row]
[row][col]4[/col][col][/col][col][/col][col][/col][col][/col][col]160[/col][/row]
[row][col]Потребность[/col][col gray]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row]
[/table]
(стоимости перевозки не указываем, так как при построении опорного плана они не учитываются). Начинаем с левой верхней ячейки (строка 1, столбец 1). Потребность равна 190, запас равен 140, поэтому отгрузка равна min(190,140)=140. Потребность потребителя 1 стала равна 50 (190-140), запас поставщика 1 стал равен 0 (140-140), поэтому исключаем из дальнейшего рассмотрения первую строку (соответствующую поставщику 1):
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col lime]140[/col][col silver][/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col]2[/col][col gray][/col][col][/col][col][/col][col][/col][col gray]210[/col][/row]
[row][col]3[/col][col][/col][col][/col][col][/col][col][/col][col]190[/col][/row]
[row][col]4[/col][col][/col][col][/col][col][/col][col][/col][col]160[/col][/row]
[row][col]Потребность[/col][col gray]50[/col][col]220[/col][col]160[/col][col]130[/col][col]560[/col][/row]
[/table]
В оставшейся части таблицы левая верхняя ячейка находится на пересечении строки 2 (запас 210) и столбца 1 (потребность 50). Отгрузка равна min(50,210)=50, оставшаяся потребность 1 равна 0, оставшийся запас 2 равен 160, исключаем столбец 1:
[table]
[row][col]Поставщики[/col][col silver]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col lime]140[/col][col silver][/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col]2[/col][col lime]50[/col][col gray][/col][col][/col][col][/col][col gray]160[/col][/row]
[row][col]3[/col][col silver][/col][col][/col][col][/col][col][/col][col]190[/col][/row]
[row][col]4[/col][col silver][/col][col][/col][col][/col][col][/col][col]160[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col gray]220[/col][col]160[/col][col]130[/col][col]510[/col][/row]
[/table]
Ячейка 2:2, отгрузка min(220,160)=160, исключаем строку 2:
[table]
[row][col]Поставщики[/col][col silver]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col lime]140[/col][col silver][/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]50[/col][col lime]160[/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col]3[/col][col silver][/col][col gray][/col][col][/col][col][/col][col gray]190[/col][/row]
[row][col]4[/col][col silver][/col][col][/col][col][/col][col][/col][col]160[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col gray]60[/col][col]160[/col][col]130[/col][col]350[/col][/row]
[/table]
Ячейка 3:2, отгрузка min(60,190)=60, исключаем столбец 2:
[table]
[row][col]Поставщики[/col][col silver]1[/col][col silver]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col lime]140[/col][col silver][/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]50[/col][col lime]160[/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col]3[/col][col silver][/col][col lime]60[/col][col gray][/col][col][/col][col gray]130[/col][/row]
[row][col]4[/col][col silver][/col][col silver][/col][col][/col][col][/col][col]160[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col silver]0[/col][col gray]160[/col][col]130[/col][col]290[/col][/row]
[/table]
Ячейка 3:3, отгрузка min(160,130)=130, исключаем строку 3:
[table]
[row][col]Поставщики[/col][col silver]1[/col][col silver]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col lime]140[/col][col silver][/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]50[/col][col lime]160[/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col silver]3[/col][col silver][/col][col lime]60[/col][col lime]130[/col][col silver][/col][col silver]0[/col][/row]
[row][col]4[/col][col silver][/col][col silver][/col][col gray][/col][col][/col][col gray]160[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col silver]0[/col][col gray]30[/col][col]130[/col][col]160[/col][/row]
[/table]
Ячейка 4:3, отгрузка min(30,130)=30, исключаем столбец 3:
[table]
[row][col]Поставщики[/col][col silver]1[/col][col silver]2[/col][col silver]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col lime]140[/col][col silver][/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]50[/col][col lime]160[/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col silver]3[/col][col silver][/col][col lime]60[/col][col lime]130[/col][col silver][/col][col silver]0[/col][/row]
[row][col]4[/col][col silver][/col][col silver][/col][col lime]30[/col][col gray][/col][col gray]130[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col silver]0[/col][col silver]0[/col][col gray]130[/col][col]130[/col][/row]
[/table]
Ячейка 4:4, отгрузка min(130,130)=130, исключаем строку 4 и столбец 4:
[table]
[row][col]Поставщики[/col][col silver]1[/col][col silver]2[/col][col silver]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col lime]140[/col][col silver][/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]50[/col][col lime]160[/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col silver]3[/col][col silver][/col][col lime]60[/col][col lime]130[/col][col silver][/col][col silver]0[/col][/row]
[row][col silver]4[/col][col silver][/col][col silver][/col][col lime]30[/col][col lime]130[/col][col silver]0[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col silver]0[/col][col silver]0[/col][col silver]0[/col][col]0[/col][/row]
[/table]
Все строки и столбцы исключены (то есть оставшиеся потребности и запасы равны нулю), следовательно, опорный план построен верно. Добавим в таблицу значения стоимости перевозок:
[table]
[row][col]Поставщики[/col][col silver]1[/col][col silver]2[/col][col silver]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col lime]4*140[/col][col silver][/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]2*50[/col][col lime]4*160[/col][col silver][/col][col silver][/col][col silver]0[/col][/row]
[row][col silver]3[/col][col silver][/col][col lime]2*60[/col][col lime]1*130[/col][col silver][/col][col silver]0[/col][/row]
[row][col silver]4[/col][col silver][/col][col silver][/col][col lime]2*30[/col][col lime]4*130[/col][col silver]0[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col silver]0[/col][col silver]0[/col][col silver]0[/col][col]0[/col][/row]
[/table]
и вычислим общую стоимость перевозок:
4[$183$]140 + 2[$183$]50 + 4[$183$]160 + 2[$183$]60 + 1[$183$]130 + 2[$183$]30 + 4[$183$]130 = 2130.

2. Метод двойного предпочтения состоит в следующем:
в каждом столбце и в каждой строке отмечаем ячейку с наименьшей стоимостью перевозки (очевидно, что некоторые ячейки могут быть отмечены дважды, если они минимальны по стоимости, как в строке, так и в столбце);
выбираем ячейку таблицы с наибольшим числом отметок и наименьшей стоимостью перевозки (если таких несколько, выбираем любую);
определяем максимально возможную отгрузку как минимум из величины потребности соответствующего потребителя и запаса соответствующего поставщика;
уменьшаем потребность и запас на величину отгрузки;
если потребность стала равна нулю, то исключаем соответствующий столбец (потребителя) из дальнейшего рассмотрения;
аналогично, если запас стал равен нулю, то исключаем соответствующую строку (поставщика);
повторяем для оставшейся части таблицы, пока не будут распределены все запасы и удовлетворены все потребности.
В данном случае исходная таблица имеет вид:
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4[/col][col]1[/col][col]2[/col][col]2[/col][col]140[/col][/row]
[row][col]2[/col][col]2[/col][col]4[/col][col]3[/col][col]1[/col][col]210[/col][/row]
[row][col]3[/col][col]4[/col][col]2[/col][col]1[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col]2[/col][col]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row]
[/table]
Отметим ячейки c наименьшей в строке стоимостью перевозки:
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4[/col][col]1*[/col][col]2[/col][col]2[/col][col]140[/col][/row]
[row][col]2[/col][col]2[/col][col]4[/col][col]3[/col][col]1*[/col][col]210[/col][/row]
[row][col]3[/col][col]4[/col][col]2[/col][col]1*[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col]2*[/col][col]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row]
[/table]
Отметим ячейки c наименьшей в столбце стоимостью перевозки:
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4[/col][col]1**[/col][col]2[/col][col]2[/col][col]140[/col][/row]
[row][col]2[/col][col]2*[/col][col]4[/col][col]3[/col][col]1**[/col][col]210[/col][/row]
[row][col]3[/col][col]4[/col][col]2[/col][col]1**[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col]2*[/col][col]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row]
[/table]
Получилось пять отмеченных ячеек, из которых три отмечены дважды и имеют одну и ту же стоимость перевозки (1).
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4[/col][col gray]1**[/col][col]2[/col][col]2[/col][col gray]140[/col][/row]
[row][col]2[/col][col]2*[/col][col]4[/col][col]3[/col][col]1**[/col][col]210[/col][/row]
[row][col]3[/col][col]4[/col][col]2[/col][col]1**[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col]2*[/col][col]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col gray]220[/col][col]160[/col][col]130[/col][col]700[/col][/row]
[/table]
Выберем одну из отмеченных ячеек, например, 1:2. Потребность равна 220, запас равен 140, поэтому отгрузка будет равна min(220,140)=140. Потребность потребителя 2 стала равна 80 (220-140), запас поставщика 1 стал равен 0 (140-140), поэтому исключаем из дальнейшего рассмотрения первую строку (соответствующую поставщику 1):
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col]2[/col][col]2*[/col][col]4[/col][col]3[/col][col gray]1**[/col][col gray]210[/col][/row]
[row][col]3[/col][col]4[/col][col]2[/col][col]1**[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col]2*[/col][col]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]80[/col][col]160[/col][col gray]130[/col][col]560[/col][/row]
[/table]
В оставшейся части таблицы снова выберем одну из дважды отмеченных ячеек, например, 2:4. Потребность равна 130, запас равен 210, поэтому отгрузка будет равна min(130,210)=130. Потребность потребителя 4 стала равна 0 (130-130), запас поставщика 2 стал равен 80 (210-130), поэтому исключаем из дальнейшего рассмотрения четвёртый столбец (соответствующую потребителю 4):
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col]2[/col][col]2*[/col][col]4[/col][col]3[/col][col lime]1*130[/col][col]80[/col][/row]
[row][col]3[/col][col]4[/col][col]2[/col][col gray]1**[/col][col silver]5[/col][col gray]190[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col]2*[/col][col silver]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]80[/col][col gray]160[/col][col silver]0[/col][col]430[/col][/row]
[/table]
В оставшейся части таблицы для единственной дважды отмеченной ячейки 3:3 отгрузка будет равна min(160,190)=160, исключаем столбец 3:
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col silver]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col]2[/col][col gray]2*[/col][col]4[/col][col silver]3[/col][col lime]1*130[/col][col gray]80[/col][/row]
[row][col]3[/col][col]4[/col][col]2[/col][col lime]1*160[/col][col silver]5[/col][col]30[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col silver]2*[/col][col silver]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col gray]190[/col][col]80[/col][col silver]0[/col][col silver]0[/col][col]270[/col][/row]
[/table]
Отмеченная ячейка 2:1, отгрузка min(190,80)=80, исключаем строку 2:
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col silver]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]2*80[/col][col silver]4[/col][col silver]3[/col][col lime]1*130[/col][col silver]0[/col][/row]
[row][col]3[/col][col]4[/col][col gray]2[/col][col lime]1*160[/col][col silver]5[/col][col gray]30[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col silver]2*[/col][col silver]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]110[/col][col gray]80[/col][col silver]0[/col][col silver]0[/col][col]190[/col][/row]
[/table]
В оставшейся части таблицы больше нет отмеченных ячеек, поэтому выбираем среди неотмеченных ячейку с наименьшей стоимостью - 3:2. Отгрузка равна min(80,30)=30, исключаем строку 3:
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col silver]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]2*80[/col][col silver]4[/col][col silver]3[/col][col lime]1*130[/col][col silver]0[/col][/row]
[row][col silver]3[/col][col silver]4[/col][col lime]2*30[/col][col lime]1*160[/col][col silver]5[/col][col silver]0[/col][/row]
[row][col]4[/col][col gray]3[/col][col]4[/col][col silver]2*[/col][col silver]4[/col][col gray]160[/col][/row]
[row][col]Потребность[/col][col gray]110[/col][col]50[/col][col silver]0[/col][col silver]0[/col][col]160[/col][/row]
[/table]
Ячейка 4:1, отгрузка min(110,160)=110, исключаем столбец 1:
[table]
[row][col]Поставщики[/col][col silver]1[/col][col]2[/col][col silver]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]2*80[/col][col silver]4[/col][col silver]3[/col][col lime]1*130[/col][col silver]0[/col][/row]
[row][col silver]3[/col][col silver]4[/col][col lime]2*30[/col][col lime]1*160[/col][col silver]5[/col][col silver]0[/col][/row]
[row][col]4[/col][col lime]3*110[/col][col gray]4[/col][col silver]2*[/col][col silver]4[/col][col gray]50[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col gray]50[/col][col silver]0[/col][col silver]0[/col][col]50[/col][/row]
[/table]
Ячейка 4:2, отгрузка min(5,50)=50, исключаем строку 4 и столбец 2:
[table]
[row][col]Поставщики[/col][col silver]1[/col][col]2[/col][col silver]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]2*80[/col][col silver]4[/col][col silver]3[/col][col lime]1*130[/col][col silver]0[/col][/row]
[row][col silver]3[/col][col silver]4[/col][col lime]2*30[/col][col lime]1*160[/col][col silver]5[/col][col silver]0[/col][/row]
[row][col]4[/col][col lime]3*110[/col][col lime]4*50[/col][col silver]2*[/col][col silver]4[/col][col silver]0[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col silver]0[/col][col silver]0[/col][col silver]0[/col][col]0[/col][/row]
[/table]
Все строки и столбцы исключены (то есть оставшиеся потребности и запасы равны нулю), следовательно, опорный план построен верно. Вычислим общую стоимость перевозок:
1[$183$]140 + 2[$183$]80 + 1[$183$]130 + 2[$183$]30 + 1[$183$]160 + 3[$183$]110 + 4[$183$]50 = 1180.
Полученное опорное решение намного лучше, чем в первом случае (метод северо-западного угла вообще редко даёт хорошее решение, так как не учитывает стоимость перевозки).

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

В данном случае исходная таблица имеет вид:
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4[/col][col gray]1[/col][col]2[/col][col]2[/col][col gray]140[/col][/row]
[row][col]2[/col][col]2[/col][col]4[/col][col]3[/col][col]1[/col][col]210[/col][/row]
[row][col]3[/col][col]4[/col][col]2[/col][col]1[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col]2[/col][col]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col gray]220[/col][col]160[/col][col]130[/col][col]700[/col][/row]
[/table]
Наименьшая стоимость перевозки в таблице равна 1. Выберем одну из клеток с данной стоимостью, например, 1:2. Потребность равна 220, запас равен 140, поэтому отгрузка будет равна min(220,140)=140. Потребность потребителя 2 стала равна 80 (220-140), запас поставщика 1 стал равен 0 (140-140), поэтому исключаем из дальнейшего рассмотрения первую строку (соответствующую поставщику 1):
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col]2[/col][col]2[/col][col]4[/col][col]3[/col][col gray]1[/col][col gray]210[/col][/row]
[row][col]3[/col][col]4[/col][col]2[/col][col]1[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col]2[/col][col]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]80[/col][col]160[/col][col gray]130[/col][col]560[/col][/row]
[/table]
В оставшейся части таблицы наименьшая стоимость перевозки равна 1. Выберем одну из клеток с данной стоимостью, например, 2:4. Потребность равна 130, запас равен 210, поэтому отгрузка будет равна min(130,210)=130. Потребность потребителя 4 стала равна 0 (130-130), запас поставщика 2 стал равен 80 (210-130), поэтому исключаем из дальнейшего рассмотрения четвёртый столбец (соответствующий потребителю 4):
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col]2[/col][col]2[/col][col]4[/col][col]3[/col][col lime]1*130[/col][col]80[/col][/row]
[row][col]3[/col][col]4[/col][col]2[/col][col gray]1[/col][col silver]5[/col][col gray]190[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col]2[/col][col silver]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]80[/col][col gray]160[/col][col silver]0[/col][col]430[/col][/row]
[/table]
Наименьшая стоимость 1, ячейка 3:3, отгрузка min(160,190)=160, исключаем столбец 3:
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col silver]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col]2[/col][col gray]2[/col][col]4[/col][col silver]3[/col][col lime]1*130[/col][col gray]80[/col][/row]
[row][col]3[/col][col]4[/col][col]2[/col][col lime]1*160[/col][col silver]5[/col][col]30[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col silver]2[/col][col silver]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col gray]190[/col][col]80[/col][col silver]0[/col][col silver]0[/col][col]270[/col][/row]
[/table]
Наименьшая стоимость 2, ячейка 2:1, отгрузка min(190,80)=80, исключаем строку 2:
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col silver]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]2*80[/col][col silver]4[/col][col silver]3[/col][col lime]1*130[/col][col silver]0[/col][/row]
[row][col]3[/col][col]4[/col][col gray]2[/col][col lime]1*160[/col][col silver]5[/col][col gray]30[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col silver]2[/col][col silver]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]110[/col][col gray]80[/col][col silver]0[/col][col silver]0[/col][col]190[/col][/row]
[/table]
Наименьшая стоимость 2, ячейка 3:2, отгрузка min(80,30)=30, исключаем строку 3:
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col silver]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]2*80[/col][col silver]4[/col][col silver]3[/col][col lime]1*130[/col][col silver]0[/col][/row]
[row][col silver]3[/col][col silver]4[/col][col lime]2*30[/col][col lime]1*160[/col][col silver]5[/col][col silver]0[/col][/row]
[row][col]4[/col][col gray]3[/col][col]4[/col][col silver]2[/col][col silver]4[/col][col gray]160[/col][/row]
[row][col]Потребность[/col][col gray]110[/col][col]50[/col][col silver]0[/col][col silver]0[/col][col]160[/col][/row]
[/table]
Наименьшая стоимость 3, ячейка 4:1, отгрузка min(110,160)=110, исключаем столбец 1:
[table]
[row][col]Поставщики[/col][col silver]1[/col][col]2[/col][col silver]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]2*80[/col][col silver]4[/col][col silver]3[/col][col lime]1*130[/col][col silver]0[/col][/row]
[row][col silver]3[/col][col silver]4[/col][col lime]2*30[/col][col lime]1*160[/col][col silver]5[/col][col silver]0[/col][/row]
[row][col]4[/col][col lime]3*110[/col][col gray]4[/col][col silver]2[/col][col silver]4[/col][col gray]50[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col gray]50[/col][col silver]0[/col][col silver]0[/col][col]50[/col][/row]
[/table]
Осталась ячейка 4:2, отгрузка min(50,50)=50, исключаем строку 4 и столбец 2:
[table]
[row][col]Поставщики[/col][col silver]1[/col][col silver]2[/col][col silver]3[/col][col silver]4[/col][col]Запас[/col][/row]
[row][col silver]1[/col][col silver]4[/col][col lime]1*140[/col][col silver]2[/col][col silver]2[/col][col silver]0[/col][/row]
[row][col silver]2[/col][col lime]2*80[/col][col silver]4[/col][col silver]3[/col][col lime]1*130[/col][col silver]0[/col][/row]
[row][col silver]3[/col][col silver]4[/col][col lime]2*30[/col][col lime]1*160[/col][col silver]5[/col][col silver]0[/col][/row]
[row][col silver]4[/col][col lime]3*110[/col][col lime]4*50[/col][col silver]2[/col][col silver]4[/col][col silver]0[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col silver]0[/col][col silver]0[/col][col silver]0[/col][col]0[/col][/row]
[/table]
Все строки и столбцы исключены (то есть оставшиеся потребности и запасы равны нулю), следовательно, опорный план построен верно. Вычислим общую стоимость перевозок:
1[$183$]140 + 2[$183$]80 + 1[$183$]130 + 2[$183$]30 + 1[$183$]160 + 3[$183$]110 + 4[$183$]50 = 1180.
Данное опорное решение совпадает с полученным методом двойного предпочтения (такое бывает часто).

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

Воспользуемся методом потенциалов для оптимизации решения, полученного методом северо-западного угла:
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col lime]4*140[/col][col]1[/col][col]2[/col][col]2[/col][col]140[/col][/row]
[row][col]2[/col][col lime]2*50[/col][col lime]4*160[/col][col]3[/col][col]1[/col][col]210[/col][/row]
[row][col]3[/col][col]4[/col][col lime]2*60[/col][col lime]1*130[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col lime]2*30[/col][col lime]4*130[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row][/table]
Вычислим потенциалы:
u[sub]1[/sub]=0;
c[sub]11[/sub]=u[sub]1[/sub]+v[sub]1[/sub]=4 [$8658$] v[sub]1[/sub]=4-0=4;
c[sub]21[/sub]=u[sub]2[/sub]+v[sub]1[/sub]=2 [$8658$] u[sub]2[/sub]=2-4=-2;
c[sub]22[/sub]=u[sub]2[/sub]+v[sub]2[/sub]=4 [$8658$] v[sub]2[/sub]=4-(-2)=6;
c[sub]32[/sub]=u[sub]3[/sub]+v[sub]2[/sub]=2 [$8658$] u[sub]3[/sub]=2-6=-4;
c[sub]33[/sub]=u[sub]3[/sub]+v[sub]3[/sub]=1 [$8658$] v[sub]3[/sub]=1-(-4)=5;
c[sub]43[/sub]=u[sub]4[/sub]+v[sub]3[/sub]=2 [$8658$] u[sub]4[/sub]=2-5=-3;
c[sub]44[/sub]=u[sub]4[/sub]+v[sub]4[/sub]=4 [$8658$] v[sub]4[/sub]=4-(-3)=7
и добавим их в таблицу:
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][col]U[/col][/row]
[row][col]1[/col][col lime]4*140[/col][col]1[/col][col]2[/col][col]2[/col][col]140[/col][col]0[/col][/row]
[row][col]2[/col][col lime]2*50[/col][col lime]4*160[/col][col]3[/col][col]1[/col][col]210[/col][col]-2[/col][/row]
[row][col]3[/col][col]4[/col][col lime]2*60[/col][col lime]1*130[/col][col]5[/col][col]190[/col][col]-4[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col lime]2*30[/col][col lime]4*130[/col][col]160[/col][col]-3[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][col][/col][/row]
[row][col]V[/col][col]4[/col][col]6[/col][col]5[/col][col]7[/col][col][/col][col][/col][/row][/table]
Найдём оценки поставок:
[$916$][sub]11[/sub]=0;
[$916$][sub]12[/sub]=c[sub]12[/sub]-(u[sub]1[/sub]+v[sub]2[/sub])=1-(0+6)=-5;
[$916$][sub]13[/sub]=c[sub]13[/sub]-(u[sub]1[/sub]+v[sub]3[/sub])=2-(0+5)=-3;
[$916$][sub]14[/sub]=c[sub]14[/sub]-(u[sub]1[/sub]+v[sub]4[/sub])=2-(0+7)=-5;
[$916$][sub]21[/sub]=[$916$][sub]22[/sub]=0;
[$916$][sub]23[/sub]=c[sub]23[/sub]-(u[sub]2[/sub]+v[sub]3[/sub])=3-(-2+5)=0;
[$916$][sub]24[/sub]=c[sub]24[/sub]-(u[sub]2[/sub]+v[sub]4[/sub])=1-(-2+7)=-4;
[$916$][sub]31[/sub]=c[sub]31[/sub]-(u[sub]3[/sub]+v[sub]1[/sub])=4-(-4+4)=4;
[$916$][sub]32[/sub]=[$916$][sub]33[/sub]=0;
[$916$][sub]34[/sub]=c[sub]34[/sub]-(u[sub]3[/sub]+v[sub]4[/sub])=5-(-4+7)=2;
[$916$][sub]41[/sub]=c[sub]41[/sub]-(u[sub]4[/sub]+v[sub]1[/sub])=3-(-3+4)=2;
[$916$][sub]42[/sub]=c[sub]42[/sub]-(u[sub]4[/sub]+v[sub]2[/sub])=4-(-3+6)=1;
[$916$][sub]43[/sub]=[$916$][sub]44[/sub]=0;
и добавим их в таблицу (для ячеек, не входящих в опорное решение):
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col lime]4*140[/col][col]1/-5[/col][col]2/-3[/col][col]2/-5[/col][col]140[/col][/row]
[row][col]2[/col][col lime]2*50[/col][col lime]4*160[/col][col]3/0[/col][col]1/-4[/col][col]210[/col][/row]
[row][col]3[/col][col]4/4[/col][col lime]2*60[/col][col lime]1*130[/col][col]5/2[/col][col]190[/col][/row]
[row][col]4[/col][col]3/2[/col][col]4/1[/col][col lime]2*30[/col][col lime]4*130[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row][/table]
Ячейка 1:2 содержит наименьшую оценку, равную -5 (ячейка 1:4 также подошла бы). Вместе с ячейками 2:2, 2:1 и 1:1 она образует замкнутый цикл, в котором ячейки 1:2 и 2:1 - "положительные", а 2:2 и 1:1 - "отрицательные":
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col gray]4*140[/col][col silver]1/-5[/col][col]2/-3[/col][col]2/-5[/col][col]140[/col][/row]
[row][col]2[/col][col silver]2*50[/col][col gray]4*160[/col][col]3/0[/col][col]1/-4[/col][col]210[/col][/row]
[row][col]3[/col][col]4/4[/col][col lime]2*60[/col][col lime]1*130[/col][col]5/2[/col][col]190[/col][/row]
[row][col]4[/col][col]3/2[/col][col]4/1[/col][col lime]2*30[/col][col lime]4*130[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row][/table]
Среди "отрицательных" ячеек наименьшее значение поставки достигается в 1:1 (140). Уменьшаем на 140 объём поставок для ячеек 2:2 и 1:1, увеличиваем на 140 объём поставок для ячеек 1:2 и 2:1. Получаем новое опорное решение:
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]2[/col][col]140[/col][/row]
[row][col]2[/col][col lime]2*190[/col][col lime]4*20[/col][col]3[/col][col]1[/col][col]210[/col][/row]
[row][col]3[/col][col]4[/col][col lime]2*60[/col][col lime]1*130[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col lime]2*30[/col][col lime]4*130[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row][/table]
и вычисляем новую стоимость перевозок:
1[$183$]140 + 2[$183$]190 + 4[$183$]20 + 2[$183$]60 + 1[$183$]130 + 2[$183$]30 + 4[$183$]130 = 1430.
Можно заметить, что по сравнению с исходным опорным решением стоимость изменилась на величину -700 = -5·140, равную произведению оценки выбранной ячейки (-5) на величину изменения объёмов поставок для ячеек цикла (140).
Вычислим потенциалы:
u[sub]1[/sub]=0;
c[sub]12[/sub]=u[sub]1[/sub]+v[sub]2[/sub]=1 [$8658$] v[sub]2[/sub]=1-0=1;
c[sub]22[/sub]=u[sub]2[/sub]+v[sub]2[/sub]=4 [$8658$] u[sub]2[/sub]=4-1=3;
c[sub]21[/sub]=u[sub]2[/sub]+v[sub]1[/sub]=2 [$8658$] v[sub]1[/sub]=2-3=-1;
c[sub]32[/sub]=u[sub]3[/sub]+v[sub]2[/sub]=2 [$8658$] u[sub]3[/sub]=2-1=1;
c[sub]33[/sub]=u[sub]3[/sub]+v[sub]3[/sub]=1 [$8658$] v[sub]3[/sub]=1-1=0;
c[sub]43[/sub]=u[sub]4[/sub]+v[sub]3[/sub]=2 [$8658$] u[sub]4[/sub]=2-0=2;
c[sub]44[/sub]=u[sub]4[/sub]+v[sub]4[/sub]=4 [$8658$] v[sub]4[/sub]=4-2=2
и добавим их в таблицу:
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][col]U[/col][/row]
[row][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]2[/col][col]140[/col][col]0[/col][/row]
[row][col]2[/col][col lime]2*190[/col][col lime]4*20[/col][col]3[/col][col]1[/col][col]210[/col][col]3[/col][/row]
[row][col]3[/col][col]4[/col][col lime]2*60[/col][col lime]1*130[/col][col]5[/col][col]190[/col][col]1[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col lime]2*30[/col][col lime]4*130[/col][col]160[/col][col]2[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][col][/col][/row]
[row][col]V[/col][col]-1[/col][col]1[/col][col]0[/col][col]2[/col][col][/col][col][/col][/row][/table]
Найдём оценки поставок:
[$916$][sub]11[/sub]=c[sub]11[/sub]-(u[sub]1[/sub]+v[sub]1[/sub])=4-(0-1)=5;
[$916$][sub]12[/sub]=0;
[$916$][sub]13[/sub]=c[sub]13[/sub]-(u[sub]1[/sub]+v[sub]3[/sub])=2-(0+0)=2;
[$916$][sub]14[/sub]=c[sub]14[/sub]-(u[sub]1[/sub]+v[sub]4[/sub])=2-(0+2)=0;
[$916$][sub]21[/sub]=[$916$][sub]22[/sub]=0;
[$916$][sub]23[/sub]=c[sub]23[/sub]-(u[sub]2[/sub]+v[sub]3[/sub])=3-(3+0)=0;
[$916$][sub]24[/sub]=c[sub]24[/sub]-(u[sub]2[/sub]+v[sub]4[/sub])=1-(3+2)=-4;
[$916$][sub]31[/sub]=c[sub]31[/sub]-(u[sub]3[/sub]+v[sub]1[/sub])=4-(1-1)=4;
[$916$][sub]32[/sub]=[$916$][sub]33[/sub]=0;
[$916$][sub]34[/sub]=c[sub]34[/sub]-(u[sub]3[/sub]+v[sub]4[/sub])=5-(1+2)=2;
[$916$][sub]41[/sub]=c[sub]41[/sub]-(u[sub]4[/sub]+v[sub]1[/sub])=3-(2-1)=2;
[$916$][sub]42[/sub]=c[sub]42[/sub]-(u[sub]4[/sub]+v[sub]2[/sub])=4-(2+1)=1;
[$916$][sub]43[/sub]=[$916$][sub]44[/sub]=0
и добавим их в таблицу (для ячеек, не входящих в опорное решение):
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4/5[/col][col lime]1*140[/col][col]2/2[/col][col]2/0[/col][col]140[/col][/row]
[row][col]2[/col][col lime]2*190[/col][col lime]4*20[/col][col]3/0[/col][col]1/-4[/col][col]210[/col][/row]
[row][col]3[/col][col]4/4[/col][col lime]2*60[/col][col lime]1*130[/col][col]5/2[/col][col]190[/col][/row]
[row][col]4[/col][col]3/2[/col][col]4/1[/col][col lime]2*30[/col][col lime]4*130[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row][/table]
В новой таблице только ячейка 2:4 содержит отрицательную оценку (-4). Вместе с ячейками 4:4, 4:3, 3:3, 3:2 и 2:2 она образует замкнутый цикл, в котором ячейки 2:4, 4:3 и 3:2 - "положительные", а 4:4, 3:3 и 2:2 - "отрицательные":
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4/5[/col][col lime]1*140[/col][col]2/2[/col][col]2/0[/col][col]140[/col][/row]
[row][col]2[/col][col lime]2*190[/col][col gray]4*20[/col][col]3/0[/col][col silver]1/-4[/col][col]210[/col][/row]
[row][col]3[/col][col]4/4[/col][col silver]2*60[/col][col gray]1*130[/col][col]5/2[/col][col]190[/col][/row]
[row][col]4[/col][col]3/2[/col][col]4/1[/col][col silver]2*30[/col][col gray]4*130[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row][/table]
Среди "отрицательных" ячеек наименьшее значение поставки достигается в 2:2 (20). Уменьшаем на 20 объём поставок для ячеек 4:4, 3:3 и 2:2, увеличиваем на 20 объём поставок для ячеек 2:4, 4:3 и 3:2. Получаем новое опорное решение:
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]2[/col][col]140[/col][/row]
[row][col]2[/col][col lime]2*190[/col][col]4[/col][col]3[/col][col lime]1*20[/col][col]210[/col][/row]
[row][col]3[/col][col]4[/col][col lime]2*80[/col][col lime]1*110[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col lime]2*50[/col][col lime]4*110[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row][/table]
и вычисляем новую стоимость перевозок:
1[$183$]140 + 2[$183$]190 + 1[$183$]20 + 2[$183$]80 + 1[$183$]110 + 2[$183$]50 + 4[$183$]110 = 1350.
либо как
1430 - 4[$183$]20 = 1350.
Для нового решения вычислим потенциалы:
u[sub]1[/sub]=0;
c[sub]12[/sub]=u[sub]1[/sub]+v[sub]2[/sub]=1 [$8658$] v[sub]2[/sub]=1-0=1;
c[sub]32[/sub]=u[sub]3[/sub]+v[sub]2[/sub]=2 [$8658$] u[sub]3[/sub]=2-1=1;
c[sub]33[/sub]=u[sub]3[/sub]+v[sub]3[/sub]=1 [$8658$] v[sub]3[/sub]=1-1=0;
c[sub]43[/sub]=u[sub]4[/sub]+v[sub]3[/sub]=2 [$8658$] u[sub]4[/sub]=2-0=2;
c[sub]44[/sub]=u[sub]4[/sub]+v[sub]4[/sub]=4 [$8658$] v[sub]4[/sub]=4-2=2;
c[sub]24[/sub]=u[sub]2[/sub]+v[sub]4[/sub]=4 [$8658$] u[sub]2[/sub]=1-2=-1;
c[sub]21[/sub]=u[sub]2[/sub]+v[sub]1[/sub]=2 [$8658$] v[sub]1[/sub]=2-(-1)=3
и добавим их в таблицу:
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][col]U[/col][/row]
[row][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]2[/col][col]140[/col][col]0[/col][/row]
[row][col]2[/col][col lime]2*190[/col][col]4[/col][col]3[/col][col lime]1*20[/col][col]210[/col][col]-1[/col][/row]
[row][col]3[/col][col]4[/col][col lime]2*80[/col][col lime]1*110[/col][col]5[/col][col]190[/col][col]1[/col][/row]
[row][col]4[/col][col]3[/col][col]4[/col][col lime]2*50[/col][col lime]4*110[/col][col]160[/col][col]2[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][col][/col][/row]
[row][col]V[/col][col]3[/col][col]1[/col][col]0[/col][col]2[/col][col][/col][col][/col][/row][/table]
Найдём оценки поставок:
[$916$][sub]11[/sub]=c[sub]11[/sub]-(u[sub]1[/sub]+v[sub]1[/sub])=4-(0+3)=1;
[$916$][sub]12[/sub]=0;
[$916$][sub]13[/sub]=c[sub]13[/sub]-(u[sub]1[/sub]+v[sub]3[/sub])=2-(0+0)=2;
[$916$][sub]14[/sub]=c[sub]14[/sub]-(u[sub]1[/sub]+v[sub]4[/sub])=2-(0+2)=0;
[$916$][sub]21[/sub]=0;
[$916$][sub]22[/sub]=c[sub]22[/sub]-(u[sub]2[/sub]+v[sub]2[/sub])=4-(-1+1)=4;
[$916$][sub]23[/sub]=c[sub]23[/sub]-(u[sub]2[/sub]+v[sub]3[/sub])=3-(-1+0)=4;
[$916$][sub]24[/sub]=0;
[$916$][sub]31[/sub]=c[sub]31[/sub]-(u[sub]3[/sub]+v[sub]1[/sub])=4-(1+3)=0;
[$916$][sub]32[/sub]=[$916$][sub]33[/sub]=0;
[$916$][sub]34[/sub]=c[sub]34[/sub]-(u[sub]3[/sub]+v[sub]4[/sub])=5-(1+2)=2;
[$916$][sub]41[/sub]=c[sub]41[/sub]-(u[sub]4[/sub]+v[sub]1[/sub])=3-(2+3)=-2;
[$916$][sub]42[/sub]=c[sub]42[/sub]-(u[sub]4[/sub]+v[sub]2[/sub])=4-(2+1)=1;
[$916$][sub]43[/sub]=[$916$][sub]44[/sub]=0;
и добавим их в таблицу (для ячеек, не входящих в опорное решение):
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4/1[/col][col lime]1*140[/col][col]2/2[/col][col]2/0[/col][col]140[/col][/row]
[row][col]2[/col][col lime]2*190[/col][col]4/4[/col][col]3/4[/col][col lime]1*20[/col][col]210[/col][/row]
[row][col]3[/col][col]4/0[/col][col lime]2*80[/col][col lime]1*110[/col][col]5/2[/col][col]190[/col][/row]
[row][col]4[/col][col]3/-2[/col][col]4/1[/col][col lime]2*50[/col][col lime]4*110[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row][/table]
В новой таблице только ячейка 4:1 содержит отрицательную оценку (-2). Вместе с ячейками 2:1, 2:4 и 4:4 она образует замкнутый цикл, в котором ячейки 4:1 и 2:4 - "положительные", а 2:1 и 4:4 - "отрицательные":
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]2[/col][col]140[/col][/row]
[row][col]2[/col][col gray]2*190[/col][col]4[/col][col]3[/col][col silver]1*20[/col][col]210[/col][/row]
[row][col]3[/col][col]4[/col][col lime]2*80[/col][col lime]1*110[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col silver]3[/col][col]4[/col][col lime]2*50[/col][col gray]4*110[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row][/table]
Среди "отрицательных" ячеек наименьшее значение поставки достигается в 4:4 (110). Уменьшаем на 110 объём поставок для ячеек 2:1 и 4:4, увеличиваем на 110 объём поставок для ячеек 4:1 и 2:4. Получаем новое опорное решение:
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]2[/col][col]140[/col][/row]
[row][col]2[/col][col lime]2*80[/col][col]4[/col][col]3[/col][col lime]1*130[/col][col]210[/col][/row]
[row][col]3[/col][col]4[/col][col lime]2*80[/col][col lime]1*110[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col lime]3*110[/col][col]4[/col][col lime]2*50[/col][col]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row][/table]
и вычисляем новую стоимость перевозок:
1[$183$]140 + 2[$183$]80 + 1[$183$]130 + 2[$183$]80 + 1[$183$]110 + 3[$183$]110 + 2[$183$]50 = 1130.
либо как
1350 - 2[$183$]110 = 1130.
Для нового решения вычислим потенциалы:
u[sub]1[/sub]=0;
c[sub]12[/sub]=u[sub]1[/sub]+v[sub]2[/sub]=1 [$8658$] v[sub]2[/sub]=1-0=1;
c[sub]32[/sub]=u[sub]3[/sub]+v[sub]2[/sub]=2 [$8658$] u[sub]3[/sub]=2-1=1;
c[sub]33[/sub]=u[sub]3[/sub]+v[sub]3[/sub]=1 [$8658$] v[sub]3[/sub]=1-1=0;
c[sub]43[/sub]=u[sub]4[/sub]+v[sub]3[/sub]=2 [$8658$] u[sub]4[/sub]=2-0=2;
c[sub]41[/sub]=u[sub]4[/sub]+v[sub]1[/sub]=3 [$8658$] v[sub]1[/sub]=3-2=1;
c[sub]21[/sub]=u[sub]2[/sub]+v[sub]1[/sub]=2 [$8658$] u[sub]2[/sub]=2-1=1;
c[sub]24[/sub]=u[sub]2[/sub]+v[sub]4[/sub]=1 [$8658$] v[sub]4[/sub]=1-1=0
и добавим их в таблицу:
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][col]U[/col][/row]
[row][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]2[/col][col]140[/col][col]0[/col][/row]
[row][col]2[/col][col lime]2*80[/col][col]4[/col][col]3[/col][col lime]1*130[/col][col]210[/col][col]1[/col][/row]
[row][col]3[/col][col]4[/col][col lime]2*80[/col][col lime]1*110[/col][col]5[/col][col]190[/col][col]1[/col][/row]
[row][col]4[/col][col lime]3*110[/col][col]4[/col][col lime]2*50[/col][col]4[/col][col]160[/col][col]2[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][col][/col][/row]
[row][col]V[/col][col]1[/col][col]1[/col][col]0[/col][col]0[/col][col][/col][col][/col][/row][/table]
Найдём оценки поставок:
[$916$][sub]11[/sub]=c[sub]11[/sub]-(u[sub]1[/sub]+v[sub]1[/sub])=4-(0+1)=3;
[$916$][sub]12[/sub]=0;
[$916$][sub]13[/sub]=c[sub]13[/sub]-(u[sub]1[/sub]+v[sub]3[/sub])=2-(0+0)=2;
[$916$][sub]14[/sub]=c[sub]14[/sub]-(u[sub]1[/sub]+v[sub]4[/sub])=2-(0+0)=2;
[$916$][sub]21[/sub]=0;
[$916$][sub]22[/sub]=c[sub]22[/sub]-(u[sub]2[/sub]+v[sub]2[/sub])=4-(1+1)=2;
[$916$][sub]23[/sub]=c[sub]23[/sub]-(u[sub]2[/sub]+v[sub]3[/sub])=3-(1+0)=2;
[$916$][sub]24[/sub]=0;
[$916$][sub]31[/sub]=c[sub]31[/sub]-(u[sub]3[/sub]+v[sub]1[/sub])=4-(1+1)=2;
[$916$][sub]32[/sub]=[$916$][sub]33[/sub]=0;
[$916$][sub]34[/sub]=c[sub]34[/sub]-(u[sub]3[/sub]+v[sub]4[/sub])=5-(1+0)=4;
[$916$][sub]41[/sub]=0;
[$916$][sub]42[/sub]=c[sub]42[/sub]-(u[sub]4[/sub]+v[sub]2[/sub])=4-(2+1)=1;
[$916$][sub]43[/sub]=0;
[$916$][sub]44[/sub]=c[sub]44[/sub]-(u[sub]4[/sub]+v[sub]4[/sub])=4-(2+0)=2.
Отрицательных оценок нет, следовательно, последнее решение со стоимостью 1130 является оптимальным.

5. Используем также метод потенциалов для оптимизации опорного решения, полученного методом двойного предпочтения и методом минимальной стоимости:
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]2[/col][col]140[/col][/row]
[row][col]2[/col][col lime]2*80[/col][col]4[/col][col]3[/col][col lime]1*130[/col][col]210[/col][/row]
[row][col]3[/col][col]4[/col][col lime]2*30[/col][col lime]1*160[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col lime]3*110[/col][col lime]4*50[/col][col]2[/col][col]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row][/table]
Вычислим потенциалы:
u[sub]1[/sub]=0;
c[sub]12[/sub]=u[sub]1[/sub]+v[sub]2[/sub]=1 [$8658$] v[sub]2[/sub]=1-0=1;
c[sub]32[/sub]=u[sub]3[/sub]+v[sub]2[/sub]=2 [$8658$] u[sub]3[/sub]=2-1=1;
c[sub]33[/sub]=u[sub]3[/sub]+v[sub]3[/sub]=1 [$8658$] v[sub]3[/sub]=1-1=0;
c[sub]42[/sub]=u[sub]4[/sub]+v[sub]2[/sub]=4 [$8658$] u[sub]4[/sub]=4-1=3;
c[sub]41[/sub]=u[sub]4[/sub]+v[sub]1[/sub]=3 [$8658$] v[sub]1[/sub]=3-3=0;
c[sub]21[/sub]=u[sub]2[/sub]+v[sub]1[/sub]=2 [$8658$] u[sub]2[/sub]=2-0=2;
c[sub]24[/sub]=u[sub]2[/sub]+v[sub]4[/sub]=1 [$8658$] v[sub]4[/sub]=1-2=-1
и добавим их в таблицу:
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][col]U[/col][/row]
[row][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]2[/col][col]140[/col][col]0[/col][/row]
[row][col]2[/col][col lime]2*80[/col][col]4[/col][col]3[/col][col lime]1*130[/col][col]210[/col][col]2[/col][/row]
[row][col]3[/col][col]4[/col][col lime]2*30[/col][col lime]1*160[/col][col]5[/col][col]190[/col][col]1[/col][/row]
[row][col]4[/col][col lime]3*110[/col][col lime]4*50[/col][col]2[/col][col]4[/col][col]160[/col][col]3[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][col][/col][/row]
[row][col]V[/col][col]0[/col][col]1[/col][col]0[/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])=4-(0+0)=4;
[$916$][sub]12[/sub]=0;
[$916$][sub]13[/sub]=c[sub]13[/sub]-(u[sub]1[/sub]+v[sub]3[/sub])=2-(0+0)=2;
[$916$][sub]14[/sub]=c[sub]14[/sub]-(u[sub]1[/sub]+v[sub]4[/sub])=2-(0-1)=3;
[$916$][sub]21[/sub]=0;
[$916$][sub]22[/sub]=c[sub]22[/sub]-(u[sub]2[/sub]+v[sub]2[/sub])=4-(2+1)=1;
[$916$][sub]23[/sub]=c[sub]23[/sub]-(u[sub]2[/sub]+v[sub]3[/sub])=3-(2+0)=1;
[$916$][sub]24[/sub]=0;
[$916$][sub]31[/sub]=c[sub]31[/sub]-(u[sub]3[/sub]+v[sub]1[/sub])=4-(1+0)=3;
[$916$][sub]32[/sub]=[$916$][sub]33[/sub]=0;
[$916$][sub]34[/sub]=c[sub]34[/sub]-(u[sub]3[/sub]+v[sub]4[/sub])=5-(1-1)=3;
[$916$][sub]41[/sub]=[$916$][sub]42[/sub]=0;
[$916$][sub]43[/sub]=c[sub]43[/sub]-(u[sub]4[/sub]+v[sub]2[/sub])=2-(3+0)=-1;
[$916$][sub]44[/sub]=c[sub]44[/sub]-(u[sub]4[/sub]+v[sub]4[/sub])=4-(3-1)=2.
и добавим их в таблицу (для ячеек, не входящих в опорное решение):
[table][row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4/4[/col][col lime]1*140[/col][col]2/2[/col][col]2/3[/col][col]140[/col][/row]
[row][col]2[/col][col lime]2*80[/col][col]4/1[/col][col]3/1[/col][col lime]1*130[/col][col]210[/col][/row]
[row][col]3[/col][col]4/3[/col][col lime]2*30[/col][col lime]1*160[/col][col]5/3[/col][col]190[/col][/row]
[row][col]4[/col][col lime]3*110[/col][col lime]4*50[/col][col]2/-1[/col][col]4/2[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row][/table]
В новой таблице только ячейка 4:3 содержит отрицательную оценку (-1). Вместе с ячейками 4:2, 3:2 и 3:3 она образует замкнутый цикл, в котором ячейки 4:3 и 3:2 - "положительные", а 4:2 и 3:3 - "отрицательные":
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]2[/col][col]140[/col][/row]
[row][col]2[/col][col lime]2*80[/col][col]4[/col][col]3[/col][col lime]1*130[/col][col]210[/col][/row]
[row][col]3[/col][col]4[/col][col silver]2*30[/col][col gray]1*160[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col lime]3*110[/col][col gray]4*50[/col][col silver]2[/col][col]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row]
[/table]
Среди "отрицательных" ячеек наименьшее значение поставки достигается в 4:2 (50). Уменьшаем на 50 объём поставок для ячеек 3:2 и 4:3, увеличиваем на 50 объём поставок для ячеек 4:2 и 3:3. Получаем новое опорное решение:
[table]
[row][col]Поставщики[/col][col]1[/col][col]2[/col][col]3[/col][col]4[/col][col]Запас[/col][/row]
[row][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]2[/col][col]140[/col][/row]
[row][col]2[/col][col lime]2*80[/col][col]4[/col][col]3[/col][col lime]1*130[/col][col]210[/col][/row]
[row][col]3[/col][col]4[/col][col lime]2*80[/col][col lime]1*110[/col][col]5[/col][col]190[/col][/row]
[row][col]4[/col][col lime]3*110[/col][col]4[/col][col lime]2*50[/col][col]4[/col][col]160[/col][/row]
[row][col]Потребность[/col][col]190[/col][col]220[/col][col]160[/col][col]130[/col][col]700[/col][/row]
[/table]
и вычисляем новую стоимость перевозок:
1[$183$]140 + 2[$183$]80 + 1[$183$]130 + 2[$183$]80 + 1[$183$]110 + 3[$183$]110 + 2[$183$]50 = 1130.
либо как
1180 - 1[$183$]50 = 1130.
Решение совпадает с полученным ранее. Поскольку в данном случае исходное опорное решение было более оптимальным, оптимизация потребовала всего одного шага (вместо трёх).