Поиск оптимального решения

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

1. Если транспортная таблица содержит более одной пустой клетки с отрицательным значением теневой цены, то выбирается та из них, которой соответствует наибольшее значение по абсолютной величине.

2. Построение для этой клетки ступенчатого цикла аналогично описанному выше.

3. Выявление клеток, количество перевозок в которых необходимо сократить, и определение величины этих сокращений таким образом, чтобы ни одно из значений перевозок не оказалось отрицательным. Максимальное количество изделий, соответствующее выбранной клетке, определяется минимумом из этих значений. Перераспределение производится только для клеток, входящих в построенный цикл.

4. Нет никаких гарантий, что в полученном распределении нельзя предпринять никаких улучшений. Поэтому новое решение необходимо проверить на оптимальность с использованием метода МОДИ. Утверждать, что найденная стоимость транспортировки является минимальной, можно только в том случае, если все теневые цены положительны или равны нулю.

Продолжение примера 4.4. Единственной клеткой с отрицательным значением теневой цены, равным - 2 00 евро, является клетка (R, фиктивный). В эту клетку желательно разместить максимально возможное количество изделий.

Ниже приведен ступенчатый цикл для клетки (R, фиктивный), которая имеет значение теневой цены, равное -2 00 евро, а также исходное распределение перевозок и единичные издержки.

Таблица 4.15. Ступенчатый цикл для (R, фиктивный)

Знак "+" означает увеличение количества перевозимых изделий в данной клетке; знак "-" — уменьшение соответствующего количества изделий.

Клетки со знаком "—" — это клетки (R, фиктивный) и (R,C), объем перевозок в которых равен 7 и 4 изделиям соответственно. Минимальным значением для клеток, отмеченных знаком "-", является 4, что означает, что внутри цикла можно осуществлять перемещение четырех изделий, добавляя их в клетки со знаком "+" и вычитая из клеток со знаком "-". Общая экономия стоимости транспортировки составит в данном случае (2 х 4) = 8 00 евро Изменения, внесенные в транспортную таблицу, отражены в табл. 13.16.

Таблица 4.16 Перераспределение перевозок

Данное решение по-прежнему является базисным, так как число заполненных клеток равно 6. Проверим данное решение иа оптимальность с использованием метода МОДИ. Обратившись к заполненным клеткам (Р,С), (Р. фиктивный), (Q,B), (R,A), (R,B) и (R, фиктивный), получим:

с₁₃= 5 ⁼ u₁ + v₃ Положим u₁ = 0, тогда v₃ = 5;

с₁₄= 0 = u₁ + v₄v₄ = 0;

с₃₄= 0 = u₃ + v₄u₃ = 0;

с₃₁= 1 = u₃ +v₁ v₁ = 1;

с₃₂= 20 = u₃ + v₂ v₂ = 20;

с₂₂= 10 = u₂ + v₂u₂ = -10.

Таким образом, теневые цены соответствующие пустым клеткам, будут равны:

s_ij = c_ij-(u_i + v_j);

s₁₁ = 10 - (0+ 1) = +9;

s₁₂ = 20 - (0 +20) = 0;

s₂₁ = 2 - (-10+ 1) = +11;

s₂₃ = 8 - (-10 + 5) = +13;

s₂₄ = 0 - (-10 + 0) = +10;

s₃₃ = 7 - (0 + 5) = + 2.

Поскольку ни одно из значений теневых цен не отрицательно, полученное решение является оптимальным.

Минимальная стоимость равна: 101 + (4 х (- 2)) = 93 00 евро

Таблица 4.17. Проверка распределения перевозок на оптимальность с использованием метода МОДИ