Здравствуйте, Посетитель - 399202!

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

В данном случае исходная таблица имеет вид:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col gray][/col][col][/col][col][/col][col][/col][col gray]120[/col][/row]
[row][col]A2[/col][col][/col][col][/col][col][/col][col][/col][col]140[/col][/row]
[row][col]A3[/col][col][/col][col][/col][col][/col][col][/col][col]230[/col][/row]
[row][col]A4[/col][col][/col][col][/col][col][/col][col][/col][col]200[/col][/row]
[row][col]Потребность[/col][col gray]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
(стоимости перевозки не указываем, так как при построении опорного плана они не учитываются). Начинаем с левой верхней ячейки (строка A1, столбец B1). Потребность равна 160, запас равен 120, поэтому отгрузка равна min(160,120)=120. Потребность потребителя B1 стала равна 40 (160-120), запас поставщика A1 стал равен 0 (120-120), поэтому исключаем из дальнейшего рассмотрения первую строку (соответствующую поставщику A1):
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col lime]120[/col][col silver][/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col]A2[/col][col gray][/col][col][/col][col][/col][col][/col][col gray]140[/col][/row]
[row][col]A3[/col][col][/col][col][/col][col][/col][col][/col][col]230[/col][/row]
[row][col]A4[/col][col][/col][col][/col][col][/col][col][/col][col]200[/col][/row]
[row][col]Потребность[/col][col gray]40[/col][col]180[/col][col]200[/col][col]150[/col][col]570[/col][/row]
[/table]
В оставшейся части таблицы левая верхняя ячейка находится на пересечении строки A2 (запас 140) и столбца B1 (потребность 40). Отгрузка равна min(40,140)=40, оставшаяся потребность B1 равна 0, оставшийся запас A2 равен 100, исключаем столбец B1:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col lime]120[/col][col silver][/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col]A2[/col][col lime]40[/col][col gray][/col][col][/col][col][/col][col gray]100[/col][/row]
[row][col]A3[/col][col silver][/col][col][/col][col][/col][col][/col][col]230[/col][/row]
[row][col]A4[/col][col silver][/col][col][/col][col][/col][col][/col][col]200[/col][/row]
[row][col]Потребность[/col][col]0[/col][col gray]180[/col][col]200[/col][col]150[/col][col]530[/col][/row]
[/table]
Ячейка A2:B2, отгрузка min(180,100)=100, исключаем строку A2:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col lime]120[/col][col silver][/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]40[/col][col lime]100[/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col]A3[/col][col silver][/col][col gray][/col][col][/col][col][/col][col gray]230[/col][/row]
[row][col]A4[/col][col silver][/col][col][/col][col][/col][col][/col][col]200[/col][/row]
[row][col]Потребность[/col][col]0[/col][col gray]80[/col][col]200[/col][col]150[/col][col]430[/col][/row]
[/table]
Ячейка A3:B2, отгрузка min(80,230)=80, исключаем столбец B2:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col silver]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col lime]120[/col][col silver][/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]40[/col][col lime]100[/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col]A3[/col][col silver][/col][col lime]80[/col][col gray][/col][col][/col][col gray]150[/col][/row]
[row][col]A4[/col][col silver][/col][col silver][/col][col][/col][col][/col][col]200[/col][/row]
[row][col]Потребность[/col][col]0[/col][col]0[/col][col gray]200[/col][col]150[/col][col]350[/col][/row]
[/table]
Ячейка A3:B3, отгрузка min(200,150)=150, исключаем строку A3:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col silver]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col lime]120[/col][col silver][/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]40[/col][col lime]100[/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col silver]A3[/col][col silver][/col][col lime]80[/col][col lime]150[/col][col silver][/col][col]0[/col][/row]
[row][col]A4[/col][col silver][/col][col silver][/col][col gray][/col][col][/col][col gray]200[/col][/row]
[row][col]Потребность[/col][col]0[/col][col]0[/col][col gray]50[/col][col]150[/col][col]200[/col][/row]
[/table]
Ячейка A4:B3, отгрузка min(50,200)=50, исключаем столбец B3:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col silver]B2[/col][col silver]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col lime]120[/col][col silver][/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]40[/col][col lime]100[/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col silver]A3[/col][col silver][/col][col lime]80[/col][col lime]150[/col][col silver][/col][col]0[/col][/row]
[row][col]A4[/col][col silver][/col][col silver][/col][col lime]50[/col][col gray][/col][col gray]150[/col][/row]
[row][col]Потребность[/col][col]0[/col][col]0[/col][col]0[/col][col gray]150[/col][col]150[/col][/row]
[/table]
Ячейка A4:B4, отгрузка min(150,150)=150, исключаем строку A4 и столбец B4:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col silver]B2[/col][col silver]B3[/col][col silver]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col lime]120[/col][col silver][/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]40[/col][col lime]100[/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col silver]A3[/col][col silver][/col][col lime]80[/col][col lime]150[/col][col silver][/col][col]0[/col][/row]
[row][col silver]A4[/col][col silver][/col][col silver][/col][col lime]50[/col][col lime]150[/col][col]0[/col][/row]
[row][col]Потребность[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]
Все строки и столбцы исключены (то есть оставшиеся потребности и запасы равны нулю), следовательно, опорный план построен верно. Добавим в таблицу значения стоимости перевозок:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col silver]B2[/col][col silver]B3[/col][col silver]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col lime]2*120[/col][col silver][/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]1*40[/col][col lime]4*100[/col][col silver][/col][col silver][/col][col]0[/col][/row]
[row][col silver]A3[/col][col silver][/col][col lime]2*80[/col][col lime]4*150[/col][col silver][/col][col]0[/col][/row]
[row][col silver]A4[/col][col silver][/col][col silver][/col][col lime]2*50[/col][col lime]1*150[/col][col]0[/col][/row]
[row][col]Потребность[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][col][/col][/row]
[/table]
и вычислим общую стоимость перевозок:
2[$183$]120 + 1[$183$]40 + 4[$183$]100 + 2[$183$]80 + 4[$183$]150 + 2[$183$]50 + 1[$183$]150 = 1690.

2. Метод двойного предпочтения состоит в следующем:
в каждом столбце и в каждой строке отмечаем ячейку с наименьшей стоимостью перевозки (очевидно, что некоторые ячейки могут быть отмечены дважды, если они минимальны по стоимости, как в строке, так и в столбце);
выбираем ячейку таблицы с наибольшим числом отметок и наименьшей стоимостью перевозки (если таких несколько, выбираем любую);
определяем максимально возможную отгрузку как минимум из величины потребности соответствующего потребителя и запаса соответствующего поставщика;
уменьшаем потребность и запас на величину отгрузки;
если потребность стала равна нулю, то исключаем соответствующий столбец (потребителя) из дальнейшего рассмотрения;
аналогично, если запас стал равен нулю, то исключаем соответствующую строку (поставщика);
повторяем для оставшейся части таблицы, пока не будут распределены все запасы и удовлетворены все потребности.
В данном случае исходная таблица имеет вид:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col]2[/col][col]1[/col][col]3[/col][col]2[/col][col]120[/col][/row]
[row][col]A2[/col][col]1[/col][col]4[/col][col]1[/col][col]2[/col][col]140[/col][/row]
[row][col]A3[/col][col]1[/col][col]2[/col][col]4[/col][col]5[/col][col]230[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col]2[/col][col]1[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
Отметим ячейки c наименьшей в строке стоимостью перевозки:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col]2[/col][col]1*[/col][col]3[/col][col]2[/col][col]120[/col][/row]
[row][col]A2[/col][col]1*[/col][col]4[/col][col]1*[/col][col]2[/col][col]140[/col][/row]
[row][col]A3[/col][col]1*[/col][col]2[/col][col]4[/col][col]5[/col][col]230[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col]2[/col][col]1*[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
Отметим ячейки c наименьшей в столбце стоимостью перевозки:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col]2[/col][col]1**[/col][col]3[/col][col]2[/col][col]120[/col][/row]
[row][col]A2[/col][col]1**[/col][col]4[/col][col]1**[/col][col]2[/col][col]140[/col][/row]
[row][col]A3[/col][col]1**[/col][col]2[/col][col]4[/col][col]5[/col][col]230[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col]2[/col][col]1**[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
Получилось пять отмеченных ячеек, причём все отмечены дважды и имеют одну и ту же стоимость перевозки (1).
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col]2[/col][col gray]1**[/col][col]3[/col][col]2[/col][col gray]120[/col][/row]
[row][col]A2[/col][col]1**[/col][col]4[/col][col]1**[/col][col]2[/col][col]140[/col][/row]
[row][col]A3[/col][col]1**[/col][col]2[/col][col]4[/col][col]5[/col][col]230[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col]2[/col][col]1**[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col gray]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
Выберем одну из отмеченных ячеек, например, A1:B2. Потребность равна 180, запас равен 120, поэтому отгрузка будет равна min(180,120)=120. Потребность потребителя B2 стала равна 60 (180-120), запас поставщика A1 стал равен 0 (120-120), поэтому исключаем из дальнейшего рассмотрения первую строку (соответствующую поставщику A1):
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col]A2[/col][col gray]1**[/col][col]4[/col][col]1**[/col][col]2[/col][col gray]140[/col][/row]
[row][col]A3[/col][col]1**[/col][col]2[/col][col]4[/col][col]5[/col][col]230[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col]2[/col][col]1**[/col][col]200[/col][/row]
[row][col]Потребность[/col][col gray]160[/col][col]60[/col][col]200[/col][col]150[/col][col]570[/col][/row]
[/table]
В оставшейся части таблицы снова выберем одну из отмеченных ячеек, например, A2:B1. Потребность равна 160, запас равен 140, поэтому отгрузка будет равна min(160,140)=140. Потребность потребителя B1 стала равна 20 (160-140), запас поставщика A2 стал равен 0 (140-140), поэтому исключаем из дальнейшего рассмотрения вторую строку (соответствующую поставщику A2):
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]1*140[/col][col silver]4[/col][col silver]1**[/col][col silver]2[/col][col]0[/col][/row]
[row][col]A3[/col][col gray]1**[/col][col]2[/col][col]4[/col][col]5[/col][col gray]230[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col]2[/col][col]1**[/col][col]200[/col][/row]
[row][col]Потребность[/col][col gray]20[/col][col]60[/col][col]200[/col][col]150[/col][col]430[/col][/row]
[/table]
Дважды отмеченная ячейка A3:B1, отгрузка min(20,230)=20, исключаем столбец B1:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]1*140[/col][col silver]4[/col][col silver]1**[/col][col silver]2[/col][col]0[/col][/row]
[row][col]A3[/col][col lime]1*20[/col][col]2[/col][col]4[/col][col]5[/col][col]210[/col][/row]
[row][col]A4[/col][col silver]3[/col][col]4[/col][col]2[/col][col gray]1**[/col][col gray]200[/col][/row]
[row][col]Потребность[/col][col]0[/col][col]60[/col][col]200[/col][col gray]150[/col][col]410[/col][/row]
[/table]
Дважды отмеченная ячейка A4:B4, отгрузка min(150,200)=150, исключаем столбец B4:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col]B2[/col][col]B3[/col][col silver]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]1*140[/col][col silver]4[/col][col silver]1**[/col][col silver]2[/col][col]0[/col][/row]
[row][col]A3[/col][col lime]1*20[/col][col gray]2[/col][col]4[/col][col silver]5[/col][col gray]210[/col][/row]
[row][col]A4[/col][col silver]3[/col][col]4[/col][col]2[/col][col lime]1*150[/col][col]50[/col][/row]
[row][col]Потребность[/col][col]0[/col][col gray]60[/col][col]200[/col][col]0[/col][col]260[/col][/row]
[/table]
В оставшейся части таблицы больше нет отмеченных ячеек, поэтому выбираем среди неотмеченных ячейку с наименьшей стоимостью, например, A3:B2. Отгрузка равна min(60,210)=60, исключаем столбец B2:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col silver]B2[/col][col]B3[/col][col silver]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]1*140[/col][col silver]4[/col][col silver]1**[/col][col silver]2[/col][col]0[/col][/row]
[row][col]A3[/col][col lime]1*20[/col][col lime]2*60[/col][col]4[/col][col silver]5[/col][col]150[/col][/row]
[row][col]A4[/col][col silver]3[/col][col silver]4[/col][col gray]2[/col][col lime]1*150[/col][col gray]50[/col][/row]
[row][col]Потребность[/col][col]0[/col][col]0[/col][col gray]200[/col][col]0[/col][col]200[/col][/row]
[/table]
Ячейка A4:B3, отгрузка min(200,50)=50, исключаем строку A4:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col silver]B2[/col][col]B3[/col][col silver]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]1*140[/col][col silver]4[/col][col silver]1**[/col][col silver]2[/col][col]0[/col][/row]
[row][col]A3[/col][col lime]1*20[/col][col lime]2*60[/col][col gray]4[/col][col silver]5[/col][col gray]150[/col][/row]
[row][col silver]A4[/col][col silver]3[/col][col silver]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]0[/col][/row]
[row][col]Потребность[/col][col]0[/col][col]0[/col][col gray]150[/col][col]0[/col][col]150[/col][/row]
[/table]
Ячейка A3:B3, отгрузка min(150,150)=150, исключаем строку A3 и столбец B3:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col silver]B2[/col][col silver]B3[/col][col silver]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]1*140[/col][col silver]4[/col][col silver]1**[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A3[/col][col lime]1*20[/col][col lime]2*60[/col][col lime]4*150[/col][col silver]5[/col][col]0[/col][/row]
[row][col silver]A4[/col][col silver]3[/col][col silver]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]0[/col][/row]
[row][col]Потребность[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]
Все строки и столбцы исключены (то есть оставшиеся потребности и запасы равны нулю), следовательно, опорный план построен верно. Вычислим общую стоимость перевозок:
1[$183$]120 + 1[$183$]140 + 1[$183$]20 + 2[$183$]60 + 4[$183$]150 + 2[$183$]50 + 1[$183$]150 = 1250.

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

В данном случае исходная таблица имеет вид:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col]2[/col][col gray]1[/col][col]3[/col][col]2[/col][col gray]120[/col][/row]
[row][col]A2[/col][col]1[/col][col]4[/col][col]1[/col][col]2[/col][col]140[/col][/row]
[row][col]A3[/col][col]1[/col][col]2[/col][col]4[/col][col]5[/col][col]230[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col]2[/col][col]1[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col gray]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
Наименьшая стоимость перевозки в таблице равна 1. Выберем одну из клеток с данной стоимостью, например, A1:B2. Потребность равна 180, запас равен 120, поэтому отгрузка будет равна min(180,120)=120. Потребность потребителя B2 стала равна 60 (180-120), запас поставщика A1 стал равен 0 (120-120), поэтому исключаем из дальнейшего рассмотрения первую строку (соответствующую поставщику A1):
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col]A2[/col][col gray]1[/col][col]4[/col][col]1[/col][col]2[/col][col gray]140[/col][/row]
[row][col]A3[/col][col]1[/col][col]2[/col][col]4[/col][col]5[/col][col]230[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col]2[/col][col]1[/col][col]200[/col][/row]
[row][col]Потребность[/col][col gray]160[/col][col]60[/col][col]200[/col][col]150[/col][col]570[/col][/row]
[/table]
В оставшейся части таблицы наименьшая стоимость перевозки равна 1. Выберем одну из клеток с данной стоимостью, например, A2:B1. Потребность равна 160, запас равен 140, поэтому отгрузка будет равна min(160,140)=140. Потребность потребителя B1 стала равна 20 (160-140), запас поставщика A2 стал равен 0 (140-140), поэтому исключаем из дальнейшего рассмотрения вторую строку (соответствующую поставщику A2):
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]1*140[/col][col silver]4[/col][col silver]1[/col][col silver]2[/col][col]0[/col][/row]
[row][col]A3[/col][col gray]1[/col][col]2[/col][col]4[/col][col]5[/col][col gray]230[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col]2[/col][col]1[/col][col]200[/col][/row]
[row][col]Потребность[/col][col gray]20[/col][col]60[/col][col]200[/col][col]150[/col][col]430[/col][/row]
[/table]
Наименьшая стоимость 1, ячейка A3:B1, отгрузка min(20,230)=20, исключаем столбец B1:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]1*140[/col][col silver]4[/col][col silver]1[/col][col silver]2[/col][col]0[/col][/row]
[row][col]A3[/col][col lime]1*20[/col][col]2[/col][col]4[/col][col]5[/col][col]210[/col][/row]
[row][col]A4[/col][col silver]3[/col][col]4[/col][col]2[/col][col gray]1[/col][col gray]200[/col][/row]
[row][col]Потребность[/col][col]0[/col][col]60[/col][col]200[/col][col gray]150[/col][col]410[/col][/row]
[/table]
Наименьшая стоимость 1, ячейка A4:B4, отгрузка min(150,200)=150, исключаем столбец B4:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col]B2[/col][col]B3[/col][col silver]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]1*140[/col][col silver]4[/col][col silver]1[/col][col silver]2[/col][col]0[/col][/row]
[row][col]A3[/col][col lime]1*20[/col][col gray]2[/col][col]4[/col][col silver]5[/col][col gray]210[/col][/row]
[row][col]A4[/col][col silver]3[/col][col]4[/col][col]2[/col][col lime]1*150[/col][col]50[/col][/row]
[row][col]Потребность[/col][col]0[/col][col gray]60[/col][col]200[/col][col]0[/col][col]260[/col][/row]
[/table]
Наименьшая стоимость 2, ячейка A3:B2, отгрузка min(60,210)=60, исключаем столбец B2:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col silver]B2[/col][col]B3[/col][col silver]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]1*140[/col][col silver]4[/col][col silver]1[/col][col silver]2[/col][col]0[/col][/row]
[row][col]A3[/col][col lime]1*20[/col][col lime]2*60[/col][col]4[/col][col silver]5[/col][col]150[/col][/row]
[row][col]A4[/col][col silver]3[/col][col silver]4[/col][col gray]2[/col][col lime]1*150[/col][col gray]50[/col][/row]
[row][col]Потребность[/col][col]0[/col][col]0[/col][col gray]200[/col][col]0[/col][col]200[/col][/row]
[/table]
Наименьшая стоимость 2, ячейка A4:B3, отгрузка min(200,50)=50, исключаем строку A4:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col silver]B2[/col][col]B3[/col][col silver]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]1*140[/col][col silver]4[/col][col silver]1[/col][col silver]2[/col][col]0[/col][/row]
[row][col]A3[/col][col lime]1*20[/col][col lime]2*60[/col][col gray]4[/col][col silver]5[/col][col gray]150[/col][/row]
[row][col silver]A4[/col][col silver]3[/col][col silver]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]0[/col][/row]
[row][col]Потребность[/col][col]0[/col][col]0[/col][col gray]150[/col][col]0[/col][col]150[/col][/row]
[/table]
Наименьшая стоимость 4, ячейка A3:B3, отгрузка min(150,150)=150, исключаем столбец B3 и строку A3:
[table]
[row][col]Поставщики[/col][col silver]B1[/col][col silver]B2[/col][col silver]B3[/col][col silver]B4[/col][col]Запас[/col][/row]
[row][col silver]A1[/col][col silver]2[/col][col lime]1*120[/col][col silver]3[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A2[/col][col lime]1*140[/col][col silver]4[/col][col silver]1[/col][col silver]2[/col][col]0[/col][/row]
[row][col silver]A3[/col][col lime]1*20[/col][col lime]2*60[/col][col lime]4*150[/col][col silver]5[/col][col]0[/col][/row]
[row][col silver]A4[/col][col silver]3[/col][col silver]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]0[/col][/row]
[row][col]Потребность[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]
Все строки и столбцы исключены (то есть оставшиеся потребности и запасы равны нулю), следовательно, опорный план построен верно. Вычислим общую стоимость перевозок:
1[$183$]120 + 1[$183$]140 + 1[$183$]20 + 2[$183$]60 + 4[$183$]150 + 2[$183$]50 + 1[$183$]150 = 1250.
Данное опорное решение совпадает с полученным методом двойного предпочтения.

4. Метод потенциалов используется для оптимизации уже имеющегося опорного решения. Он выглядит следующим образом:
всем поставщикам A[sub]i[/sub] и потребителям B[sub]j[/sub] ставим в соответствие некоторые значения 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]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col]1[/col][col]3[/col][col]2[/col][col]120[/col][/row]
[row][col]A2[/col][col lime]1*40[/col][col lime]4*100[/col][col]1[/col][col]2[/col][col]140[/col][/row]
[row][col]A3[/col][col]1[/col][col lime]2*80[/col][col lime]4*150[/col][col]5[/col][col]230[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
Вычислим потенциалы:
u[sub]1[/sub]=0;
c[sub]11[/sub]=u[sub]1[/sub]+v[sub]1[/sub]=2 [$8658$] v[sub]1[/sub]=2-0=2;
c[sub]21[/sub]=u[sub]2[/sub]+v[sub]1[/sub]=1 [$8658$] u[sub]2[/sub]=1-2=-1;
c[sub]22[/sub]=u[sub]2[/sub]+v[sub]2[/sub]=4 [$8658$] v[sub]2[/sub]=4-(-1)=5;
c[sub]32[/sub]=u[sub]3[/sub]+v[sub]2[/sub]=2 [$8658$] u[sub]3[/sub]=2-5=-3;
c[sub]33[/sub]=u[sub]3[/sub]+v[sub]3[/sub]=4 [$8658$] v[sub]3[/sub]=4-(-3)=7;
c[sub]43[/sub]=u[sub]4[/sub]+v[sub]3[/sub]=2 [$8658$] u[sub]4[/sub]=2-7=-5;
c[sub]44[/sub]=u[sub]4[/sub]+v[sub]4[/sub]=1 [$8658$] v[sub]4[/sub]=1-(-5)=6.
и добавим их в таблицу:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][col]U[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col]1[/col][col]3[/col][col]2[/col][col]120[/col][col]0[/col][/row]
[row][col]A2[/col][col lime]1*40[/col][col lime]4*100[/col][col]1[/col][col]2[/col][col]140[/col][col]-1[/col][/row]
[row][col]A3[/col][col]1[/col][col lime]2*80[/col][col lime]4*150[/col][col]5[/col][col]230[/col][col]-3[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][col]-5[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][col][/col][/row]
[row][col]V[/col][col]2[/col][col]5[/col][col]7[/col][col]6[/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+5)=-4;
[$916$][sub]13[/sub]=c[sub]13[/sub]-(u[sub]1[/sub]+v[sub]3[/sub])=3-(0+7)=-4;
[$916$][sub]14[/sub]=c[sub]14[/sub]-(u[sub]1[/sub]+v[sub]4[/sub])=2-(0+6)=-4;
[$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])=1-(-1+7)=-5;
[$916$][sub]24[/sub]=c[sub]24[/sub]-(u[sub]2[/sub]+v[sub]4[/sub])=2-(-1+6)=-3;
[$916$][sub]31[/sub]=c[sub]31[/sub]-(u[sub]3[/sub]+v[sub]1[/sub])=1-(-3+2)=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-(-3+6)=2;
[$916$][sub]41[/sub]=c[sub]41[/sub]-(u[sub]4[/sub]+v[sub]1[/sub])=3-(-5+2)=6;
[$916$][sub]42[/sub]=c[sub]42[/sub]-(u[sub]4[/sub]+v[sub]2[/sub])=4-(-5+5)=4;
[$916$][sub]43[/sub]=[$916$][sub]44[/sub]=0;
и добавим их в таблицу (для ячеек, не входящих в опорное решение):
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col]1/-4[/col][col]3/-4[/col][col]2/-4[/col][col]120[/col][/row]
[row][col]A2[/col][col lime]1*40[/col][col lime]4*100[/col][col]1/-5[/col][col]2/-3[/col][col]140[/col][/row]
[row][col]A3[/col][col]1/2[/col][col lime]2*80[/col][col lime]4*150[/col][col]5/2[/col][col]230[/col][/row]
[row][col]A4[/col][col]3/6[/col][col]4/4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
Ячейка A2:B3 содержит наименьшую оценку (-5). Вместе с ячейками A3:B3, A3:B2 и A2:B2 она образует замкнутый цикл, в котором ячейки A2:B3 и A3:B2 - "положительные", а A3:B3 и A2:B2 - "отрицательные":
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col]1/-4[/col][col]3/-4[/col][col]2/-4[/col][col]120[/col][/row]
[row][col]A2[/col][col lime]1*40[/col][col gray]4*100[/col][col silver]1/-5[/col][col]2/-3[/col][col]140[/col][/row]
[row][col]A3[/col][col]1/2[/col][col silver]2*80[/col][col gray]4*150[/col][col]5/2[/col][col]230[/col][/row]
[row][col]A4[/col][col]3/6[/col][col]4/4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
Среди "отрицательных" ячеек наименьшее значение поставки достигается в A2:B2 (100). Уменьшаем на 100 объём поставок для ячеек A3:B3 и A2:B2, увеличиваем на 100 объём поставок для ячеек A2:B3 и A3:B2. Получаем новое опорное решение:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col]1[/col][col]3[/col][col]2[/col][col]120[/col][/row]
[row][col]A2[/col][col lime]1*40[/col][col]4[/col][col lime]1*100[/col][col]2[/col][col]140[/col][/row]
[row][col]A3[/col][col]1[/col][col lime]2*180[/col][col lime]4*50[/col][col]5[/col][col]230[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
и вычисляем новую стоимость перевозок:
2[$183$]120 + 1[$183$]40 + 1[$183$]100 + 2[$183$]180 + 4[$183$]50 + 2[$183$]50 + 1[$183$]150 = 1190.
Можно заметить, что по сравнению с исходным опорным решением стоимость изменилась на величину -500 = -5[$183$]100, равную произведению оценки выбранной ячейки (-5) на величину изменения объёмов поставок для ячеек цикла (100).
Вычислим потенциалы:
u[sub]1[/sub]=0;
c[sub]11[/sub]=u[sub]1[/sub]+v[sub]1[/sub]=2 [$8658$] v[sub]1[/sub]=2-0=2;
c[sub]21[/sub]=u[sub]2[/sub]+v[sub]1[/sub]=1 [$8658$] u[sub]2[/sub]=1-2=-1;
c[sub]23[/sub]=u[sub]2[/sub]+v[sub]3[/sub]=1 [$8658$] v[sub]3[/sub]=1-(-1)=2;
c[sub]33[/sub]=u[sub]3[/sub]+v[sub]3[/sub]=4 [$8658$] u[sub]3[/sub]=4-2=2;
c[sub]32[/sub]=u[sub]3[/sub]+v[sub]2[/sub]=2 [$8658$] v[sub]2[/sub]=2-2=0;
c[sub]43[/sub]=u[sub]4[/sub]+v[sub]3[/sub]=2 [$8658$] u[sub]4[/sub]=2-2=0;
c[sub]44[/sub]=u[sub]4[/sub]+v[sub]4[/sub]=1 [$8658$] v[sub]4[/sub]=1-0=1.
и добавим их в таблицу:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][col]U[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col]1[/col][col]3[/col][col]2[/col][col]120[/col][col]0[/col][/row]
[row][col]A2[/col][col lime]1*40[/col][col]4[/col][col lime]1*100[/col][col]2[/col][col]140[/col][col]-1[/col][/row]
[row][col]A3[/col][col]1[/col][col lime]2*180[/col][col lime]4*50[/col][col]5[/col][col]230[/col][col]2[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][col]0[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][col][/col][/row]
[row][col]V[/col][col]2[/col][col]0[/col][col]2[/col][col]1[/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+0)=1;
[$916$][sub]13[/sub]=c[sub]13[/sub]-(u[sub]1[/sub]+v[sub]3[/sub])=3-(0+2)=1;
[$916$][sub]14[/sub]=c[sub]14[/sub]-(u[sub]1[/sub]+v[sub]4[/sub])=2-(0+1)=1;
[$916$][sub]21[/sub]=0;
[$916$][sub]22[/sub]=c[sub]22[/sub]-(u[sub]2[/sub]+v[sub]2[/sub])=4-(-1+0)=5;
[$916$][sub]23[/sub]=0;
[$916$][sub]24[/sub]=c[sub]24[/sub]-(u[sub]2[/sub]+v[sub]4[/sub])=2-(-1+1)=2;
[$916$][sub]31[/sub]=c[sub]31[/sub]-(u[sub]3[/sub]+v[sub]1[/sub])=1-(2+2)=-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-(2+1)=2;
[$916$][sub]41[/sub]=c[sub]41[/sub]-(u[sub]4[/sub]+v[sub]1[/sub])=3-(0+2)=1;
[$916$][sub]42[/sub]=c[sub]42[/sub]-(u[sub]4[/sub]+v[sub]2[/sub])=4-(0+0)=4;
[$916$][sub]43[/sub]=[$916$][sub]44[/sub]=0;
и добавим их в таблицу (для ячеек, не входящих в опорное решение):
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col]1/1[/col][col]3/1[/col][col]2/1[/col][col]120[/col][/row]
[row][col]A2[/col][col lime]1*40[/col][col]4/5[/col][col lime]1*100[/col][col]2/2[/col][col]140[/col][/row]
[row][col]A3[/col][col]1/-3[/col][col lime]2*180[/col][col lime]4*50[/col][col]5/2[/col][col]230[/col][/row]
[row][col]A4[/col][col]3/1[/col][col]4/4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
В новой таблице только ячейка A3:B1 содержит отрицательную оценку (-3). Вместе с ячейками A3:B3, A2:B3 и A2:B1 она образует замкнутый цикл, в котором ячейки A3:B1 и A2:B3 - "положительные", а A3:B3 и A2:B1 - "отрицательные":
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col]1/1[/col][col]3/1[/col][col]2/1[/col][col]120[/col][/row]
[row][col]A2[/col][col gray]1*40[/col][col]4/5[/col][col silver]1*100[/col][col]2/2[/col][col]140[/col][/row]
[row][col]A3[/col][col silver]1/-3[/col][col lime]2*180[/col][col gray]4*50[/col][col]5/2[/col][col]230[/col][/row]
[row][col]A4[/col][col]3/1[/col][col]4/4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
Среди "отрицательных" ячеек наименьшее значение поставки достигается в A2:B1 (40). Уменьшаем на 40 объём поставок для ячеек A3:B3 и A2:B1, увеличиваем на 40 объём поставок для ячеек A3:B1 и A2:B3. Получаем новое опорное решение:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col]1[/col][col]3[/col][col]2[/col][col]120[/col][/row]
[row][col]A2[/col][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]140[/col][/row]
[row][col]A3[/col][col lime]1*40[/col][col lime]2*180[/col][col lime]4*10[/col][col]5[/col][col]230[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
и вычисляем новую стоимость перевозок:
2[$183$]120 + 1[$183$]140 + 1[$183$]40 + 2[$183$]180 + 4[$183$]10 + 2[$183$]50 + 1[$183$]150 = 1070,
либо как
1190 - 3[$183$]40 = 1070.
Для нового решения вычислим потенциалы:
u[sub]1[/sub]=0;
c[sub]11[/sub]=u[sub]1[/sub]+v[sub]1[/sub]=2 [$8658$] v[sub]1[/sub]=2-0=2;
c[sub]31[/sub]=u[sub]3[/sub]+v[sub]1[/sub]=1 [$8658$] u[sub]3[/sub]=1-2=-1;
c[sub]32[/sub]=u[sub]3[/sub]+v[sub]2[/sub]=2 [$8658$] v[sub]2[/sub]=2-(-1)=3;
c[sub]33[/sub]=u[sub]3[/sub]+v[sub]3[/sub]=4 [$8658$] v[sub]3[/sub]=4-(-1)=5;
c[sub]23[/sub]=u[sub]2[/sub]+v[sub]3[/sub]=1 [$8658$] u[sub]2[/sub]=1-5=-4;
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]=1 [$8658$] v[sub]4[/sub]=1-(-3)=4.
и добавим их в таблицу:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][col]U[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col]1[/col][col]3[/col][col]2[/col][col]120[/col][col]0[/col][/row]
[row][col]A2[/col][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]140[/col][col]-4[/col][/row]
[row][col]A3[/col][col lime]1*40[/col][col lime]2*180[/col][col lime]4*10[/col][col]5[/col][col]230[/col][col]-1[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][col]-3[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][col][/col][/row]
[row][col]V[/col][col]2[/col][col]3[/col][col]5[/col][col]4[/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+3)=-2;
[$916$][sub]13[/sub]=c[sub]13[/sub]-(u[sub]1[/sub]+v[sub]3[/sub])=3-(0+5)=-2;
[$916$][sub]14[/sub]=c[sub]14[/sub]-(u[sub]1[/sub]+v[sub]4[/sub])=2-(0+4)=-2;
[$916$][sub]21[/sub]=c[sub]21[/sub]-(u[sub]2[/sub]+v[sub]1[/sub])=1-(-4+2)=3;
[$916$][sub]22[/sub]=c[sub]22[/sub]-(u[sub]2[/sub]+v[sub]2[/sub])=4-(-4+3)=5;
[$916$][sub]23[/sub]=0;
[$916$][sub]24[/sub]=c[sub]24[/sub]-(u[sub]2[/sub]+v[sub]4[/sub])=2-(-4+4)=2;
[$916$][sub]31[/sub]=[$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+4)=2;
[$916$][sub]41[/sub]=c[sub]41[/sub]-(u[sub]4[/sub]+v[sub]1[/sub])=3-(-3+5)=1;
[$916$][sub]42[/sub]=c[sub]42[/sub]-(u[sub]4[/sub]+v[sub]2[/sub])=4-(-3+4)=3;
[$916$][sub]43[/sub]=[$916$][sub]44[/sub]=0;
и добавим их в таблицу (для ячеек, не входящих в опорное решение):
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col lime]2*120[/col][col]1/-2[/col][col]3/-2[/col][col]2/-2[/col][col]120[/col][/row]
[row][col]A2[/col][col]1/3[/col][col]4/5[/col][col lime]1*140[/col][col]2/2[/col][col]140[/col][/row]
[row][col]A3[/col][col lime]1*40[/col][col lime]2*180[/col][col lime]4*10[/col][col]5/2[/col][col]230[/col][/row]
[row][col]A4[/col][col]3/4[/col][col]4/4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
Наименьшую оценку -2 содержат ячейки A1:B2, A1:B3 и A1:B4. Выберем одну из них, например A1:B2. Вместе с ячейками A3:B2, A3:B1 и A1:B1 она образует замкнутый цикл, в котором ячейки A1:B2 и A3:B1 - "положительные", а A3:B2 и A1:B1 - "отрицательные":
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col gray]2*120[/col][col silver]1/-2[/col][col]3/-2[/col][col]2/-2[/col][col]120[/col][/row]
[row][col]A2[/col][col]1/3[/col][col]4/5[/col][col lime]1*140[/col][col]2/2[/col][col]140[/col][/row]
[row][col]A3[/col][col silver]1*40[/col][col gray]2*180[/col][col lime]4*10[/col][col]5/2[/col][col]230[/col][/row]
[row][col]A4[/col][col]3/4[/col][col]4/4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
Среди "отрицательных" ячеек наименьшее значение поставки достигается в A1:B1 (120). Уменьшаем на 120 объём поставок для ячеек A3:B2 и A1:B1, увеличиваем на 40 объём поставок для ячеек A1:B2 и A3:B1. Получаем новое опорное решение:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col]2[/col][col lime]1*120[/col][col]3[/col][col]2[/col][col]120[/col][/row]
[row][col]A2[/col][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]140[/col][/row]
[row][col]A3[/col][col lime]1*160[/col][col lime]2*60[/col][col lime]4*10[/col][col]5[/col][col]230[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
и вычисляем новую стоимость перевозок:
1[$183$]120 + 1[$183$]140 + 1[$183$]160 + 2[$183$]60 + 4[$183$]10 + 2[$183$]50 + 1[$183$]150 = 830,
либо как
1070 - 2[$183$]120 = 830.
Для нового решения вычислим потенциалы:
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]31[/sub]=u[sub]3[/sub]+v[sub]1[/sub]=1 [$8658$] v[sub]1[/sub]=1-1=0;
c[sub]33[/sub]=u[sub]3[/sub]+v[sub]3[/sub]=4 [$8658$] v[sub]3[/sub]=4-1=3;
c[sub]23[/sub]=u[sub]2[/sub]+v[sub]3[/sub]=1 [$8658$] u[sub]2[/sub]=1-3=-2;
c[sub]43[/sub]=u[sub]4[/sub]+v[sub]3[/sub]=2 [$8658$] u[sub]4[/sub]=2-3=-1;
c[sub]44[/sub]=u[sub]4[/sub]+v[sub]4[/sub]=1 [$8658$] v[sub]4[/sub]=1-(-1)=2.
и добавим их в таблицу:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][col]U[/col][/row]
[row][col]A1[/col][col]2[/col][col lime]1*120[/col][col]3[/col][col]2[/col][col]120[/col][col]0[/col][/row]
[row][col]A2[/col][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]140[/col][col]-2[/col][/row]
[row][col]A3[/col][col lime]1*160[/col][col lime]2*60[/col][col lime]4*10[/col][col]5[/col][col]230[/col][col]1[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][col]-1[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][col][/col][/row]
[row][col]V[/col][col]0[/col][col]1[/col][col]3[/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])=2-(0+0)=2;
[$916$][sub]12[/sub]=0;
[$916$][sub]13[/sub]=c[sub]13[/sub]-(u[sub]1[/sub]+v[sub]3[/sub])=3-(0+3)=0;
[$916$][sub]14[/sub]=c[sub]14[/sub]-(u[sub]1[/sub]+v[sub]4[/sub])=2-(0+2)=0;
[$916$][sub]21[/sub]=c[sub]21[/sub]-(u[sub]2[/sub]+v[sub]1[/sub])=1-(-2+0)=3;
[$916$][sub]22[/sub]=c[sub]22[/sub]-(u[sub]2[/sub]+v[sub]2[/sub])=4-(-2+1)=5;
[$916$][sub]23[/sub]=0;
[$916$][sub]24[/sub]=c[sub]24[/sub]-(u[sub]2[/sub]+v[sub]4[/sub])=2-(-2+2)=2;
[$916$][sub]31[/sub]=[$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-(-1+0)=4;
[$916$][sub]42[/sub]=c[sub]42[/sub]-(u[sub]4[/sub]+v[sub]2[/sub])=4-(-1+1)=4;
[$916$][sub]43[/sub]=[$916$][sub]44[/sub]=0.
Отрицательных оценок нет, следовательно, последнее решение со стоимостью 830 является оптимальным.

5. Используем также метод потенциалов для оптимизации опорного решения, полученного методом двойного предпочтения и методом минимальной стоимости:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col]2[/col][col lime]1*120[/col][col]3[/col][col]2[/col][col]120[/col][/row]
[row][col]A2[/col][col lime]1*140[/col][col]4[/col][col]1[/col][col]2[/col][col]140[/col][/row]
[row][col]A3[/col][col lime]1*20[/col][col lime]2*60[/col][col lime]4*150[/col][col]5[/col][col]220[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/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]31[/sub]=u[sub]3[/sub]+v[sub]1[/sub]=1 [$8658$] v[sub]1[/sub]=1-1=0;
c[sub]21[/sub]=u[sub]2[/sub]+v[sub]1[/sub]=1 [$8658$] u[sub]2[/sub]=1-0=1;
c[sub]33[/sub]=u[sub]3[/sub]+v[sub]3[/sub]=4 [$8658$] v[sub]3[/sub]=4-1=3;
c[sub]43[/sub]=u[sub]4[/sub]+v[sub]3[/sub]=2 [$8658$] u[sub]4[/sub]=2-3=-1;
c[sub]44[/sub]=u[sub]4[/sub]+v[sub]4[/sub]=1 [$8658$] v[sub]4[/sub]=1-(-1)=2.
и добавим их в таблицу:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][col]U[/col][/row]
[row][col]A1[/col][col]2[/col][col lime]1*120[/col][col]3[/col][col]2[/col][col]120[/col][col]0[/col][/row]
[row][col]A2[/col][col lime]1*140[/col][col]4[/col][col]1[/col][col]2[/col][col]140[/col][col]1[/col][/row]
[row][col]A3[/col][col lime]1*20[/col][col lime]2*60[/col][col lime]4*150[/col][col]5[/col][col]220[/col][col]1[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][col]-1[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][col][/col][/row]
[row][col]V[/col][col]0[/col][col]1[/col][col]3[/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])=2-(0+0)=2;
[$916$][sub]12[/sub]=0;
[$916$][sub]13[/sub]=c[sub]13[/sub]-(u[sub]1[/sub]+v[sub]3[/sub])=3-(0+3)=0;
[$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)=2;
[$916$][sub]23[/sub]=c[sub]23[/sub]-(u[sub]2[/sub]+v[sub]3[/sub])=1-(1+3)=-3;
[$916$][sub]24[/sub]=c[sub]24[/sub]-(u[sub]2[/sub]+v[sub]4[/sub])=2-(1+2)=-1;
[$916$][sub]31[/sub]=[$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-(-1+0)=4;
[$916$][sub]42[/sub]=c[sub]42[/sub]-(u[sub]4[/sub]+v[sub]2[/sub])=4-(-1+1)=4;
[$916$][sub]43[/sub]=[$916$][sub]44[/sub]=0.
и добавим их в таблицу (для ячеек, не входящих в опорное решение):
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col]2/2[/col][col lime]1*120[/col][col]3/0[/col][col]2/0[/col][col]120[/col][/row]
[row][col]A2[/col][col lime]1*140[/col][col]4/2[/col][col]1/-3[/col][col]2/-1[/col][col]140[/col][/row]
[row][col]A3[/col][col lime]1*20[/col][col lime]2*60[/col][col lime]4*150[/col][col]5/2[/col][col]220[/col][/row]
[row][col]A4[/col][col]3/4[/col][col]4/4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
Ячейка A2:B3 содержит наименьшую оценку (-3). Вместе с ячейками A3:B3, A3:B1 и A2:B1 она образует замкнутый цикл, в котором ячейки A2:B3 и A3:B1 - "положительные", а A3:B3 и A2:B1 - "отрицательные":
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col]2/2[/col][col lime]1*120[/col][col]3/0[/col][col]2/0[/col][col]120[/col][/row]
[row][col]A2[/col][col gray]1*140[/col][col]4/2[/col][col silver]1/-3[/col][col]2/-1[/col][col]140[/col][/row]
[row][col]A3[/col][col silver]1*20[/col][col lime]2*60[/col][col gray]4*150[/col][col]5/2[/col][col]220[/col][/row]
[row][col]A4[/col][col]3/4[/col][col]4/4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
Среди "отрицательных" ячеек наименьшее значение поставки достигается в A2:B1 (140). Уменьшаем на 140 объём поставок для ячеек A3:B3 и A2:B1, увеличиваем на 140 объём поставок для ячеек A2:B3 и A3:B1. Получаем новое опорное решение:
[table]
[row][col]Поставщики[/col][col]B1[/col][col]B2[/col][col]B3[/col][col]B4[/col][col]Запас[/col][/row]
[row][col]A1[/col][col]2[/col][col lime]1*120[/col][col]3[/col][col]2[/col][col]120[/col][/row]
[row][col]A2[/col][col]1[/col][col]4[/col][col lime]1*140[/col][col]2[/col][col]140[/col][/row]
[row][col]A3[/col][col lime]1*160[/col][col lime]2*60[/col][col lime]4*10[/col][col]5[/col][col]220[/col][/row]
[row][col]A4[/col][col]3[/col][col]4[/col][col lime]2*50[/col][col lime]1*150[/col][col]200[/col][/row]
[row][col]Потребность[/col][col]160[/col][col]180[/col][col]200[/col][col]150[/col][col]690[/col][/row]
[/table]
и вычисляем новую стоимость перевозок:
1[$183$]120 + 1[$183$]140 + 1[$183$]160 + 2[$183$]60 + 4[$183$]10 + 2[$183$]50 + 1[$183$]150 = 830,
либо как
1250 - 3[$183$]140 = 830.
Решение совпадает с полученным ранее. Поскольку в данном случае исходное опорное решение было более оптимальным, оптимизация потребовала всего одного шага (вместо трёх).