Начальное распределение перевозок, полученное методом минимальной стоимости

с₁₃=5= u₁ + v_з для заполненной клетки (Р,С);

c₁₄=0= u₁ + v₄ для заполненной клетки (Р, фиктивный):

c₃₃=7=u₃+v₃ для заполненной клетки (R.C);

c₃₁=1=u₃+v₁ для заполненной клетки (R,A);

c₃₂=20=u₃ + v₂ для заполненной клетки (R,B);

c₂₂=10= u₂ + v₂ для заполненной клетки (Q,B).

Какой-либо из компонент присваивается некоторое значение, по которому из соответствующих уравнений рассчитываются значения остальных компонент. Положим u₁ = 0. Из этого следует, что v₃= 5, v₄ = 0, u₃ = 2, v₁ = - 1, v₂ = 18 и u₂ = - 8. Теперь, пользуясь соотношением

s_ij=c_ij-(u_i+v_j)

мы можем найти значения теневых цен, соответствующих незаполненным клеткам.

Подставив найденные значения компонент u_i и v_j получим следующие теневые цены:

s₁₁ =10 - (0 - (- 1)) = +11 для пустой клетки (Р,А);

s₁₂ =20 - (0 +18) = + 2 для пустой клетки (Р,В);

s₂₁ = 2 -(-8- 1) =+11 для пустой клетки (Q, A);

s₂₃ = 8 - (-8 + 5) =+11 для пустой клетки (Q, C);

s₂₄ = 0 - (-8 + 0) = + 8 для пустой клетки (Q, фиктивный);

s₃₄ = 0 - (2 + 0) = - 2 для пустой клетки (R, фиктивный).

Эти значения заносятся в транспортную таблицу так, как это показано в табл. 2.14.

Таблица 2.14.

Применение метода моди для проверки на оптимальность начального распределения перевозок

Теневые цены совпадают с теми значениями, которые были найдены методом ступенек и представлены в табл. 2.12. Маршрут (R, фиктивный) имеет отрицательную теневую цену - 2 ф. ст., следовательно, полученное решение является неоптимальным. Необходимо осуществить перераспределение перевозимых изделий с использованием указанной клетки и соответствующего ей ступенчатого цикла, что позволит снизить стоимость транспортировки.

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

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

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

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

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

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

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

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

Таблица 2.15.