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

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

В данном случае исходная таблица имеет вид:
[table]
[row][col]Завод[/col][col]Комбинат 1[/col][col]Комбинат 2[/col][col]Комбинат 3[/col][col]Производство[/col][/row]
[row][col]1[/col][col]10[/col][col]15[/col][col]25[/col][col]55[/col][/row]
[row][col]2[/col][col]20[/col][col gray]5[/col][col]30[/col][col gray]30[/col][/row]
[row][col]3[/col][col]12[/col][col]10[/col][col]20[/col][col]25[/col][/row]
[row][col]Потребность[/col][col]50[/col][col gray]25[/col][col]35[/col][col]110[/col][/row]
[/table]
Наименьшая стоимость перевозки в таблице равна 5. Выберем клетку 2:2 с данной стоимостью. Потребность равна 25, производство равно 30, поэтому перевозка будет равна min(25,30)=25. Потребность комбината 2 стала равна 0 (25-25), производство завода 2 стало равно 5 (30-25), поэтому исключаем из дальнейшего рассмотрения второй столбец (соответствующий комбинату 2):
[table]
[row][col]Завод[/col][col]Комбинат 1[/col][col silver]Комбинат 2[/col][col]Комбинат 3[/col][col]Производство[/col][/row]
[row][col]1[/col][col gray]10[/col][col silver]15[/col][col]25[/col][col gray]55[/col][/row]
[row][col]2[/col][col]20[/col][col lime]5*25[/col][col]30[/col][col]5[/col][/row]
[row][col]3[/col][col]12[/col][col silver]10[/col][col]20[/col][col]25[/col][/row]
[row][col]Потребность[/col][col gray]50[/col][col silver]0[/col][col]35[/col][col]85[/col][/row]
[/table]
В оставшейся части таблицы наименьшая стоимость перевозки равна 10. Выберем клетку 1:1 с данной стоимостью. Потребность равна 50, производство равно 55, поэтому перевозка будет равна min(50,55)=50. Потребность комбината 1 стала равна 0 (50-50), производство завода 1 стало равно 5 (55-50), поэтому исключаем из дальнейшего рассмотрения первый столбец (соответствующий комбинату 1):
[table]
[row][col]Завод[/col][col silver]Комбинат 1[/col][col silver]Комбинат 2[/col][col]Комбинат 3[/col][col]Производство[/col][/row]
[row][col]1[/col][col lime]10*50[/col][col silver]15[/col][col]25[/col][col]5[/col][/row]
[row][col]2[/col][col silver]20[/col][col lime]5*25[/col][col]30[/col][col]5[/col][/row]
[row][col]3[/col][col silver]12[/col][col silver]10[/col][col gray]20[/col][col gray]25[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col silver]0[/col][col gray]35[/col][col]35[/col][/row]
[/table]
Наименьшая стоимость 20, клетка 3:3, перевозка min(35,25)=25, исключаем строку 3:
[table]
[row][col]Завод[/col][col silver]Комбинат 1[/col][col silver]Комбинат 2[/col][col]Комбинат 3[/col][col]Производство[/col][/row]
[row][col]1[/col][col lime]10*50[/col][col silver]15[/col][col gray]25[/col][col gray]5[/col][/row]
[row][col]2[/col][col silver]20[/col][col lime]5*25[/col][col]30[/col][col]5[/col][/row]
[row][col silver]3[/col][col silver]12[/col][col silver]10[/col][col lime]20*25[/col][col silver]0[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col silver]0[/col][col gray]10[/col][col]10[/col][/row]
[/table]
Наименьшая стоимость 25, клетка 1:3, перевозка min(10,5)=5, исключаем строку 1:
[table]
[row][col]Завод[/col][col silver]Комбинат 1[/col][col silver]Комбинат 2[/col][col]Комбинат 3[/col][col]Производство[/col][/row]
[row][col silver]1[/col][col lime]10*50[/col][col silver]15[/col][col lime]25*5[/col][col silver]0[/col][/row]
[row][col]2[/col][col silver]20[/col][col lime]5*25[/col][col]30[/col][col]5[/col][/row]
[row][col silver]3[/col][col silver]12[/col][col silver]10[/col][col lime]20*25[/col][col silver]0[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col silver]0[/col][col]5[/col][col]5[/col][/row]
[/table]
Осталась клетка 2:3, перевозка 5, исключаем строку 2 и столбец 3:
[table]
[row][col]Завод[/col][col silver]Комбинат 1[/col][col silver]Комбинат 2[/col][col silver]Комбинат 3[/col][col]Производство[/col][/row]
[row][col silver]1[/col][col lime]10*50[/col][col silver]15[/col][col lime]25*5[/col][col silver]0[/col][/row]
[row][col silver]2[/col][col silver]20[/col][col lime]5*25[/col][col lime]30*5[/col][col silver]0[/col][/row]
[row][col silver]3[/col][col silver]12[/col][col silver]10[/col][col lime]20*25[/col][col silver]0[/col][/row]
[row][col]Потребность[/col][col silver]0[/col][col silver]0[/col][col silver]0[/col][col]0[/col][/row]
[/table]
Все строки и столбцы исключены (то есть оставшиеся потребности и производства равны нулю), следовательно, опорное решение построено верно. Вычислим общую стоимость поставок:
10[$183$]50 + 5[$183$]25 + 25[$183$]5 + 30[$183$]5 + 20[$183$]25 = 1400.

Теперь используем метод потенциалов для оптимизации опорного решения. Этот метод работает следующим образом:
всем производителям 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]Производство[/col][/row]
[row][col]1[/col][col lime]10*50[/col][col]15[/col][col lime]25*5[/col][col]55[/col][/row]
[row][col]2[/col][col]20[/col][col lime]5*25[/col][col lime]30*5[/col][col]30[/col][/row]
[row][col]3[/col][col]12[/col][col]10[/col][col lime]20*25[/col][col]25[/col][/row]
[row][col]Потребность[/col][col]50[/col][col]25[/col][col]35[/col][col]110[/col][/row]
[/table]
Вычислим потенциалы:
u[sub]1[/sub]=0;
c[sub]11[/sub]=u[sub]1[/sub]+v[sub]2[/sub]=10 [$8658$] v[sub]1[/sub]=10-0=10;
c[sub]13[/sub]=u[sub]1[/sub]+v[sub]3[/sub]=25 [$8658$] v[sub]3[/sub]=25-0=25;
c[sub]23[/sub]=u[sub]2[/sub]+v[sub]3[/sub]=30 [$8658$] u[sub]2[/sub]=30-25=5;
c[sub]22[/sub]=u[sub]2[/sub]+v[sub]2[/sub]=5 [$8658$] v[sub]2[/sub]=5-5=0;
c[sub]33[/sub]=u[sub]3[/sub]+v[sub]3[/sub]=20 [$8658$] u[sub]3[/sub]=20-25=-5;
и добавим их в таблицу:
[table]
[row][col]Завод[/col][col]Комбинат 1[/col][col]Комбинат 2[/col][col]Комбинат 3[/col][col]Производство[/col][col]U[/col][/row]
[row][col]1[/col][col lime]10*50[/col][col]15[/col][col lime]25*5[/col][col]55[/col][col]0[/col][/row]
[row][col]2[/col][col]20[/col][col lime]5*25[/col][col lime]30*5[/col][col]30[/col][col]5[/col][/row]
[row][col]3[/col][col]12[/col][col]10[/col][col lime]20*25[/col][col]25[/col][col]-5[/col][/row]
[row][col]Потребность[/col][col]50[/col][col]25[/col][col]35[/col][col]110[/col][/row]
[row][col]V[/col][col]10[/col][col]0[/col][col]25[/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])=15-(0+0)=15;
[$916$][sub]13[/sub]=0;
[$916$][sub]21[/sub]=c[sub]13[/sub]-(u[sub]2[/sub]+v[sub]1[/sub])=20-(10+5)=5;
[$916$][sub]22[/sub]=[$916$][sub]23[/sub]=0;
[$916$][sub]31[/sub]=c[sub]31[/sub]-(u[sub]3[/sub]+v[sub]1[/sub])=12-(10-5)=7;
[$916$][sub]32[/sub]=c[sub]31[/sub]-(u[sub]3[/sub]+v[sub]2[/sub])=10-(0-5)=15.
Поскольку отрицательных оценок нет, опорное решение является оптимальным.