Материал: УП - Методы оптимальных решений

Решение:

Исходное опорное решение получим, например, по методу «минимального элемента» (табл. 34). Получен опорный вырожденный план, так как число занятых клеток должно быть m + n – 1 = 3 + 5 – 1 = 7, а у нас это число равно 6. В одну из свободных клеток помещаем 0, и считаем ее занятой. Поместим число 0, например, в клетку (1; 2) с наименьшим тарифом. План будет опорным, так как из занятых клеток не образуется циклов.

Таблица 34

2. Для определения потенциалов составляем уравнение из заполненных клеток:

Замечание. Потенциалы можно считать и непосредственно по табл. 33, используя только заполненные клетки. Определим оценки свободных клеток:

S₁₁ = 7 – (0 + 7) = 0, S₁₃ = 5 – (0 + 6) = –1 < 0,

S₁₄ = 4 – (0 + 2) = 2 > 0, S₂₃ = 3 – (– 1 + 6) = – 2 < 0,

S₂₅ = 7 – (– 1 + 2) = 6 > 0, S₃₂ = 5 – (– 4 + 3) = 6 > 0,

S₃₄ = 6 – (– 4 + 2) = 8 > 0, S₃₅ = 4 – (– 4 + 2) = 6 > 0.

Перспективными являются клетки (1; 3) и (2; 3) с оценками S₁₃ = – 1 и S₂₃ = – 2, наиболее потенциальной является клетка (2; 3), так как – 2 < – 1. Строим для клетки (2; 3) цикл непосредственно в таблице. В цикл войдут клетки (2; 3), (2; 1), (3; 1), (3; 3).

Наименьшее количество груза, стоящее в вершинах цикла с отрица­тельным знаком λ = min (10; 90) = 10. В результате смещения λ по циклу получим новый план (табл. 35).

Таблица 35

Для нового плана определяем новые потенциалы, используя только заполненные клетки и новые оценки свободных клеток:

S₁₁ = 7 – (5 + 0) = 2 > 0;

S₁₃ = 5 – (4 + 0) = 1 > 0; S₁₄ = 4 – 2 = 2 > 0; S₂₅ = 7 – 1 = 6 > 0;

S₃₂ = 5 – 1 = 4 > 0; S₃₄ = 6 – 0 = 6 > 0; S₃₅ = 4 – 0 = 4 > 0.

Оценки всех свободных клеток неотрицательны, значит план оптимальный. Так как все оценки S > 0, то он единственный.

Запишем оптимальный план:

Х^* = , т. е. со склада А₁ надо поставить 40 т овощей в магазин В₅, со склада А₂ – 80 т в магазин В₂, 10 т в магазин В₃, 60 т в магазин В₄ и со склада А₃ 20 т в магазин В₁, 80 т. в магазин В₃. При этом издержки перевозок:

min Z = Z(x^*) = 2 · 40 + 2 · 80 + 3 · 10 + 1 · 60 + 3 · 20 + 2 · 80 = = 520 тыс. руб.

6.5. Решение транспортной задачи с открытой моделью

_{Решение транспортной задачи рассмотрим для случая, когда:}

.

Пример 28. В трех хранилищах А₁, А₂, А₃ имеется соответственно 70, 80, 50 т. топлива. Требуется спланировать перевозку топлива четырем потребителям В₁, В₂, В₃, В_4, спрос которых равен 50, 70, 40 и 40 т. так, чтобы затраты на транспортировку были минимальны. Стоимость перевозки 1 т указана в табл. 36.

Таблица 36

Решение.

Поскольку запасы топлива в хранилищах больше спроса потребителей, вводим фиктивного потребителя В₅, спрос которого:

а затраты на перевозку для фиктивного потребителя с_i5 = 0 ( ).

П

Таблица 37

	В1	В2	В3	В4	В5	аi	Ui
А1						70	0
А2						90	1
А3						50	-1
bj	50	70	40	40	10	210 = 210
Vj	3	2	2	6	0

Исходный опорный план получим по методу минимального элемента.

Проверяем m + n – 1 = 3 + 5 – 1 = 7 = 7 выполняется. Определяем потен­циалы занятых клеток и находим оценки свободных клеток:

S₁₁ = 5 – 3 = 2 > 0; S₁₃ = 3 – 2=1 > 0; S₁₄= 6 – 6 = 0;

S₂₃ = 5 – 3 = 2 > 0; S₂₅ = 0 – 1 = –1 < 0; S₃₂ = 4 – 1 = 3 > 0;

S₃₄ = 5 – 5 = 0; S₃₅ =0 + 1 = 1 > 0;

Только одна оценка S₂₅ < 0; поэтому план перевозки можно улучшить за счет этой клетки (2; 5).

Выделяем для нее цикл: λ = min (10; 10) = 10.

После смещения по циклу 10 т груза получаем новый план перевозок (табл. 38):

Таблица 38