Новое оптимальное решение

Пример:

На 3-х складах имеется мука в количестве т., которая должна быть доставлена хлебозаводам в количестве (30, 80, 60, 110) т.

Стоимость перевозки одной тонны муки задана матрицей

Решение:

					ui
1 60
2 130					-1
3 90
vj

D12=u1 + v2 – c12= 0 + 12 – 8 = 4 >0

D13=u1 + v3 – c13= 0 + 3 – 15 = -12 <0

D21=u2 + v1 – c21= -1 + 6 – 9 = - 4 <0

D22=u2 + v2 – c22= -1 + 12 – 15 = -4 <0

D33=u3 + v3 – c33= 0 + 3 – 7 = -4 >0

D34=u3 + v4 – c34= 0 + 4 – 10 = - 6 >0

D12= 4 >0 => решение не оптимально

					ui
1 60
2 130					-1
3 90
vj

D11=u1 + v2 – c11= 0 + 2 – 6 = -4 <0

D13=u1 + v3 – c13= 0 + 3 – 15 = -12 <0

D21=u2 + v1 – c21= -1 + 2 – 9 = - 8 <0

D22=u2 + v2 – c22= -1 + 8 – 15 = -8 <0

D33=u3 + v3 – c33= 4 + 3 – 7 = 0

D34=u3 + v4 – c34= 4 + 4 – 10 = - 2 <0

Т.к. D33=0 то существует альтернативный оптимум

Перераспределим груз, относящийся к клетке (3,3)

					ui
1 60
2 130					-1
3 90
vj

Найдём элементы:

§6 Вырожденность в Транспортных Задачах

Задачи, имеют вырожденное решение, если число занятых клеток . Для возможного его исключения целесообразно поменять местами поставщиков и потребителей или ввести в свободную клетку с минимальным тарифом нулевую поставку, помещая её так, чтобы ……

Дата добавления: 2014-01-04