Теневая цена пустой клетки

472 Ч. 4. Моделирование в бизнесе

Это решение является неоптимальным, так как клетке (R, фиктивный) соот­ветствует отрицательная теневая цена, равная -2 ф. ст. Стоимость транспортиров­ки в 101 ф. ст. можно уменьшить, если ввести эту клетку и соответствующий ступенчатый цикл в распределение перевозок, что позволит достичь экономии стоимости в 2 ф. ст. на 1 изделие.

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

Для начала рассмотрим только заполненные клетки. Для этих клеток каждое значение единичной стоимости c_t: разделяется на две компоненты — и; для строк и Vj для столбцов. Например, единичная стоимость для клетки (R,B), лежащей на пересечении строки 3 и столбца 2, равна С32 ⁼ 20 ф. ст. В ней можно выделить компоненту 113, соответствующую строке, и компоненту V2, соответствующую столбцу, т.е.

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

Теневые цены для каждой пустой (небаэисной) клетки можно найти из соотно­шения

^sij ^{= c}ij^_<^ui ^{+ v}j>-

Эта теневая цена отражает дополнительную стоимость транспортировки единицы изделия.из пункта i в пункт j. Если все теневые цены положительны или равны нулю, т.е. s,. 2 0, то полученное решение является оптимальным. В этом случае перемещение единицы изделия в пустую клетку, которой соответствует положи­тельная теневая цена, только увеличит общую стоимость транспортировки. Если же соответствующая теневая цена имеет нулевое значение, то общая стоимость транс­портировки не изменится.

О Пример 13.4. Обратимся вновь к начальному распределению перевозок, по­лученному методом минимальной стоимости. Проведем проверку данного распре­деления на оптимальность с помощью метода МОДИ. Ниже воспроизведено начальное распределение перевозок (см. табл. 13.13).

Расчет компонент для строк и; и компонент для столбцов V: производится с помощью заполненных клеток. Заполненные клетки (Р,С), (Р, фиктивный), (Q,B), (R,A), (R,B) и (R,C) приводят к системе из шести уравнений. Эти шесть уравнений содержат семь переменных, поэтому система имеет не одно решение. Поскольку множество значений переменных является совместимым, фактические значения, присваиваемые компонентам, не играют никакой роли.