Имеются три пункта поставки однородного груза

Представим исходные данные в виде распределительной таблицы транспортной задачи.
Пункты отправления Пункты назначения Запасы
В1
В2
В3 В4
В5
А1
24 50 55 27 16 200
А2
50 47 23 17 21 350
А3 35 59 55 27 41 300
Потребности 270 130 190 150 110 ai=bj=850
Так как ai=bj=850 модель транспортной задачи закрытая.
1 этап. Составим начальное опорное решение, используя
1) метод северо-западного угла
Пункты отправления Пункты назначения Запасы
В1
В2
В3 В4
В5
А1
24
200 50
- 55
- 27
- 16
- 200
А2
50
70 47
130 23
150 17
- 21
- 350
А3 35
- 59
- 55
40 27
150 41
110 300
Потребности 270 130 190 150 110
Проверим правильность построения опорного плана: число заполненных клеток должно быть равно n+m-1=3+5-1=7. В расчетной таблице занято 7 клеток. Получим первое опорное решение, затраты при котором равны:
Z(x)=200*24+70*50+130*47+150*23+40*55+150*27+110*41=28 620
2) метод наилучшего элемента матрицы удельных затрат
Пункты отправления Пункты назначения Запасы
В1
В2
В3 В4
В5
А1
24
90 50
- 55
- 27
- 16
110 200
А2
50
- 47
10 23
190 17
150 21
- 350
А3 35
180 59
120 55
- 27
- 41
- 300
Потребности 270 130 190 150 110
Проверим правильность построения опорного плана: число заполненных клеток должно быть равно n+m-1=3+5-1=7. В расчетной таблице занято 7 клеток . Получим первое опорное решение, затраты при котором равны:
Z(x1)=24*90+16*110+47*10+23*190+17*150+35*180+59*120=24 690.
В качестве начального опорного решения будем использовать план, сформированный методом наилучшего элемента матриц удельных затрат, так как он дал меньшее значение затрат на перевозки, чем методом северо-западного угла.
Для проверки оптимальности опорного решения необходимо найти потенциалы. По признаку оптимальности в каждой занятой опорным решением клетке таблицы транспортной задачи сумма потенциалов равна стоимости (ui+vj=cij при xij>0). Записываем систему уравнений для нахождения потенциалов и решаем ее.
u1+v2=24u1+v5=16u2+v2=47u2+v3=23u2+v4=17u3+v1=35u3+v2=59
Система состоит из 7 уравнений и имеет 8 переменных. Система неопределенная. Одному из потенциалов задаем значение произвольно. Пусть, например u2=0. Остальные потенциалы находятся однозначно
u2=0v2=47-u2=47-0=47v3=23-u2=23-0=23v4=17-u2=17-0=17u3=59-v2=59-47=12v1=35-u3=35-12=23u1=24-v1=24-23=1v5=16-u1=16-1=15
Значения потенциалов записываем в таблицу рядом с запасами или запросами соответствующих поставщиков и потребителей
X1
v1=23 v2=47 v3=23 v4=17 v5=15
bj
ai
270 130 190 150 110
u1=1 200 24
90 50
- 55
- 27
- 16
110
u2=0 350 50
- 47
10 + 23
190 17
150 - 21
-
u3=12 300 35
180 59
120 - 55
- 27
2 + 41
-
Проверим выполнение условия оптимальности для свободных клеток таблицы