несбалансированна. Введем фиктивную строку с нулевыми перевозками и запасом продукции = 10. Составим начальную таблицу.

Пункты потребления Bj
Запасы продукции
Пункты отправления Ai
B1
B2
B3
B4

A1

8
1
2 160

7

A2

4
5
9
8 140
A3

9
2
3
6 170
A4

0
0
0
0 10
Потребность продукции 120 50 200 110

Найдем опорное решение методом северо-западного угла

Пункты потребления Bj
Запасы продукции
Пункты отправления Ai
B1
B2
B3
B4

A1
120 40
8
1
2 160

7

A2

4 10
5 130
9
8 140
A3

9
2 70
3 100
6 170
A4

0
0
0 10
0 10
Потребность продукции 120 50 200 110
Опорный план XСЗУ, найденный методом северно-западного угла
XСЗУ=12040000101300007010000010
Соответствующая ЦФ (общие затраты на перевозку):
LXСЗУ=120*7+40*8+10*5+130*9+70*3+100*6+0*10=3190

Найдем опорное решение минимального элемента

Пункты потребления Bj
Запасы продукции
Пункты отправления Ai
B1
B2
B3
B4

A1

8 160
1
2 160

7

A2
120
4
5
9 20
8 140
A3

9 50
2 40
3 80
6 170
A4

0
0
0 10
0 10
Потребность продукции 120 50 200 110
Опорный план XМЭ, найденный методом северно-западного угла
XМЭ=0016001200020050408000010
Соответствующая ЦФ (общие затраты на перевозку):
LXМЭ=160*1+120*4+20*8+50*2+40*3+80*6+10*0=1500

Найдем опорное решение методом Фогеля

Пункты потребления Bj
Запасы продукции
Пункты отправления Ai
B1
B2
B3
B4

A1

8 50
1 110
2 160

7

A2
120
4 20
5
9
8 140
A3

9 20
2 150
3
6 170
A4

0 10
0
0
0 10
Потребность продукции 120 50 200 110
1й шаг: определим разницу между двумя минимальными тарифами по строкам:
строка 1 – 2-1=1;
строка 2 – 5-4=1;
строка 3 – 3-2=1
по столбцам:
столбец 1 – 7-4=3;
столбец 2 – 5-2=3;
столбец 3 – 3-1=2;
столбец 4 – 6-2=4;
Наиболее предпочтителен столбец 4, найдем в этом столбце минимальную цену (2), вписываем в эту ячейку максимальный объем: x14=110
2й шаг: по строкам:
строка 1 – 7-1=6;
строка 2 – 5-4=1;
строка 3 – 3-2=1
по столбцам:
столбец 1 – 7-4=3;
столбец 2 – 5-2=3;
столбец 3 – 3-1=2;
Наиболее предпочтительна строка 1, найдем в этой строке минимальную цену (1), вписываем в эту ячейку максимальный объем: x13=50
3й шаг: по строкам:
строка 2 – 5-4=1;
строка 3 – 3-2=1
по столбцам:
столбец 1 – 9-4=5;
столбец 2 – 5-2=3;
столбец 3 – 9-3=6;
Наиболее предпочтителен столбец 3, найдем в этом столбце минимальную цену (3), вписываем в эту ячейку максимальный объем: x33=150
4й шаг: по строкам:
строка 2 – 5-4=1;
строка 3 – 9-2=7
по столбцам:
столбец 1 – 9-4=5;
столбец 2 – 5-2=3;
Наиболее предпочтительна строка 3, найдем в этой строке минимальную цену (2), вписываем в эту ячейку максимальный объем: x32=20
5й шаг: по строкам:
строка 2 – 5-4=1;
по столбцам:
столбец 1 – 4;
столбец 2 – 5;
Наиболее предпочтителен столбец 1, вписываем в эту ячейку максимальный объем: x21=120
Оставшийся объем — x22=20, x42=10
Опорный план XФ, найденный методом Фогеля
XФ=00501101202000020150001000
Соответствующая ЦФ (общие затраты на перевозку):
LXФ=50*1+110*2+120*4+20*5+20*2+150*3+10*0=1340
Решим задачу методом потенциалов.
Воспользуемся опорным планом, найденным методом Фогеля.
Каждой строке поставим в соответствие число ui, а каждому столбцу vj, таким образом, что ui+vj=cij на ненулевых решениях. Получим систему уравнения:
u1+ v3=1u1+ v4=2u2+ v1=4u2+ v2=5u3+ v2=2u4+ v2=0
Найдем решение этой системы. Положим, что u1=0, тогда v3=1, v4=2. Пусть v2=0, тогда u2=5, v1=-1, u3=2, u4=0
Проверим оптимальность решения по критерию: ui+vj≤cij
u1+v1=-1≤7, u1+v2=0≤8,u1+v3=1≤1,u1+v4=2≤2
u2+v1=4≤4, u2+v2=5≤5,u2+v3=6≤9,u2+v4=7≤8
u3+v1=-1≤9, u3+v2=2≤2,u3+v3=3≤3,u3+v4=4≤6
u4+v1=-1≤0, u4+v2=0≤0,u4+v3=1≥0,u4+v4=2≥0
Получили, что план не является оптимальным (критерий не выполняется на элементах(4,3) и (4,4))
Перебросим груз с элемента (4,2), на неоптимальный (4,4), тогда надо перекинуть груз из во 2й столбец. Уменьшаем элемент (3,3) на 10, а элемент (3,2) увеличиваем на 10. Теперь надо увеличить груз в 3м столбце. Уменьшаем элемент (1,4) на 10, а элемент (1,3) увеличиваем на 10.
Получили новый опорный план:

Пункты потребления Bj
Запасы продукции
Пункты отправления Ai
B1
B2
B3
B4

A1

8 60
1 10
2 160

7

A2
120
4 20
5
9
8 140
A3

9 30
2 140
3
6 170
A4

0
0
0 10
0 10
Потребность продукции 120 50 200 110
Составим систему уравнения:
u1+ v3=1u1+ v4=2u2+ v1=4u2+ v2=5u3+ v2=2u4+ v4=0
Найдем решение этой системы. Положим, что u1=0,
тогда v3=1, v4=2→u4=-2, u3=2, →v2=0→u2=5→v1=-1.
Проверим оптимальность решения по критерию: ui+vj≤cij
u1+v1=-1≤7, u1+v2=0≤8,u1+v3=1≤1,u1+v4=2≤2
u2+v1=4≤4, u2+v2=5≤5,u2+v3=6≤9,u2+v4=7≤8
u3+v1=-1≤9, u3+v2=2≤2,u3+v3=3≤3,u3+v4=4≤6
u4+v1=-3≤0, u4+v2=-2≤0,u4+v3=-1≤0,u4+v4=0≤0
Получили, что план является оптимальным.
XОПТ=00601001202000030140000010
Соответствующая ЦФ (общие затраты на перевозку):
LXОПТ=60*1+100*2+120*4+20*5+30*2+140*3+10*0=1320
Решили задачу, в случае, когда фиктивные тарифы нулевые.
Для случая, когда фиктивные тарифы ненулевые и больше максимального из реальных тарифов, оптимальный план не изменится.
Анализ методов нахождения опорных планов.
При нахождении опорного плана наиболее эффективным оказался метод Фогеля, поскольку он позволяет наиболее эффективно распределить ресурсы на начальном этапе (рассматриваем заполнение ячеек анализируя стоимости строк и столбцов).
Метод минимальных элементов дает хороший оптимальный план, но он учитывает только минимальные затраты в конкретной ячейке и не рассматривает совокупность строки-столбцы.
Метод северно-западного угла является самым простым методом и в то же время самым неэффективным, поскольку мы заполняем ячейки в направлении вниз и вправо и не смотрим на оставшиеся незаполненные ячейки.

несбалансированна Введем фиктивную строку с нулевыми перевозками и запасом продукции = 10