Проверка на оптимальность

Чтобы осуществить проверку оптимальности, необходимо определить, является ли начальное распределение перевозок базисным, т.е. находится ли полученное решение в крайней точке допустимого множества. Представленное в таблице 4.4. распределение перевозок является допустимым решением, т.е. лежит внутри или на границе допустимого множества. Если распределение перевозок является базисным, каждому ограничению должна соответствовать одна базисная переменная. Задача для m торговых складов и n розничных магазинов (включая фиктивный) содержит (m + n - 1) независимых ограничений. Следовательно, базисное решение должно размещаться в (m + n - 1) клетках транспортной таблицы. Все (m + n- 1) переменные должны занимать независимые позиции. Однако на данной стадии нет необходимости проявлять беспокойство по поводу независимости переменных, поскольку в процессе проверки решения на оптимальность любые нарушения будут выявлены.

Если распределение перевозок включает (m + n - 1) независимую переменную, то к нему непосредственно молено применять методы проверки оптимальности. Если же число переменных меньше указанного количества, то критерий проверки оптимальности необходимо модифицировать так, как это будет показано и 4.6 Однако если число переменных превышает (m + n - 1), процедура распределения перевозок проведена некорректно. В этом случае должны существовать варианты такого перераспределения перевозок, которые при меньшей стоимости содержат требуемое число переменных.

Обратимся в данным примера 4.2 и проверим каждое из полученных распределений перевозок на базисность. В нашей таблице 3 строки и 4 столбца, следовательно, базисное решение должно содержать (3 + 4 - 1) = 6 заполненных клеток. Можно легко убедиться, что это верно для обоих методов распределения перевозок. Кроме того, переменные решения, полученные с помощью обоих методов, находятся в различных точках допустимого множества. Следовательно, процедуру проверки можно применять, не прибегая к каким-либо модификациям

Проверка исходного распределения перевозок производится для того, чтобы определить, является ли данный, вариант наиболее дешевым для транспортировки, и, если это не так, какие изменения следует внести в данное распределение. Ниже будут изложены два метода проверки решения на оптимальность. В методе ступенек рассчитываются значения стоимости неиспользованных клеток, или теневые издержки. Сама процедура довольно длительная и кропотливая, однако, понимание ее сущности не представляет затруднений. Метод МОДИ (модифицированных распределений) — это математический алгоритм, позволяющий получить те же значения теневых издержек, причем гораздо быстрее, однако, этот метод более сложен для понимания. В обоих методах в случае, если распределение перевозок является неоптимальным, для перехода к следующему базисному распределению используется ступенчатая процедура. Как только получено базисное решение, алгоритм позволяет осуществить переход от одной крайней точки допустимого множества к другой до тех пор, пока не будет достигнуто оптимальное решение.

Пример 4.3. Для иллюстрации применения данного алгоритма используем распределение перевозок, полученное методом минимальной стоимости. Данное распределение приводится в табл. 4.6.

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

Таблица 4.6. Начальное распределение, полученное методом минимальной стоимости
Торговый склад	Розничный магазин	Общее предложение
А	В	C	фиктивный
Р Q R
-	-
-		-	-
			-
Общая потребность

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

Какая из пустых клеток будет выбрана в начале процедуры, значения не имеет. Выберем клетку (Р,А). Добавим в нее одну единицу изделия. Теперь полученное распределение является несбалансированным. Розничный магазин А получает 4 единицы изделия, в то время как его потребность — 3. Торговый склад Р является поставщиком 10 изделий, тогда как максимальный объем его предложения равен 9. Необходимо произвести корректировку столбца А и строки Р. Для восстановления баланса в столбце А необходимо вычесть одно изделие из ступеньки (R,A). Эта мера корректирует столбец А, но нарушает баланс строки R, уменьшая соответствующее предложение с 8 до 7 единиц.

Можно осуществить перебалансировку строки Р вычитанием одного изделия либо из клетки (Р,С), либо из клетки (Р, фиктивный). Если мы выберем клетку (Р, фиктивный), то в фиктивном столбце нет больше заполненных клеток, которые можно было бы использовать в дальнейшей корректировке этого столбца, следовательно, данный выбор неприемлем. Корректировку можно осуществлять только помощью тех клеток, которые уже заполнены на настоящий момент. Поэтому мы должны выбрать клетку (Р,С). Из (Р,С) вычитаем одно изделие. Это корректирует баланс по строке Р, но нарушает его по столбцу С. На данном этапе проблема несбалансированности связана со строкой R и столбцом С. Их можно скорректировать одновременно, добавив одно изделие в (R,C). Схематично процесс заполнения пустой клетки (Р,А) и восстановления баланса распределения перевозок показан в табл. 4.7.

Денежный эффект от перемещения одного изделия в клетку (Р,А) рассчитывается следующим образом:

+ 1 × стоимость (Р,А) - 1 × стоимость (R,A) + 1 × стоимость (R,C) - 1 × стоимость (Р,С) = + (1 × 10) - (1 × 1) + (1 × 7) - (1 × 5) = +11 00 евро за 1 изделие.

Таблица 4.7. Проверка пустой клетки (Р,А) Изменение натурального объема, изделий
	А	С
Р	Клетка, подвергнутая проверке + 1	Заполненная клетка - 1
R	Заполненная клетка - 1	Заполненная клетка + 1

Использование клетки (Р,А) увеличило бы стоимость транспортировки на 11 00 евро за каждое изделие, перевозимое из Р в А. Значение теневой цены является положительным, следовательно, использование данной клетки нежелательно.

Мы возвращаемся к исходному распределению перевозок и проводим последовательную проверку остальных пустых клеток. Выберем клетку (R, фиктивный), а для иллюстрации натуральных и стоимостных изменений, связанных с перемещением одной единицы изделия в клетку (R, фиктивный), используем ступеньки (Р, фиктивный), (Р,С) и (R,C).

Таблица 4.8. Проверка пустой клетки (R, фиктивный) Изменение натурального объема - изделий
	С	Фиктивный
Р	Заполненная клетка + 1	Заполненная клетка - 1
R	Заполненная клетка -1	Клетка, подвергнутая проверке + 1

Таблица 4.9. Проверка пустой клетки (R, фиктивный)

Стоимостные изменения, 00 евро

	С	Фиктивный
Р	Заполненная клетка + 5	Заполненная клетка -0
R	Заполненная клетка -7	Клетка подвергнутая проверке + 0

Стоимостные изменения от дополнения одного изделия в клетку (R, фиктивный) составили: +0-0 + 5-7 = -200 евро за 1 изделие.

Размещение перевозок в клетке (R, фиктивный) дает возможность снизить издержки транспортировки, следовательно, начальное распределение перевозок оптимальным не является. Используя клетку (R, фиктивный) и указанный ступенчатый маршрут, можно найти более дешевое решение, позволяющее сэкономить 200 евро за каждую единицу изделия, помещаемую в данную клетку. Однако проверку пустых клеток необходимо завершить, поскольку могут существовать клетки, использование которых позволяет получить еще большую экономию.

Теперь построим ступенчатый путь для пустой клетки (Q, фиктивный). Необходимо учитывать, что для последующего осуществления балансировки движение можно осуществлять только через заполненные клетки. В этом случае цикл из четырех шагов построить уже невозможно. Нам приходится выбирать более сложный.маршрут. В клетку (Q, фиктивный) поместим одно изделие. Строка Q и фиктивный столбец содержат только по одной заполненной клетке. Предположим, что мы приняли решение двигаться из (Q, фиктивный) в (Q.B). Для того, чтобы сбалансировать, строку Q, из этой клетки вычтем одно изделие. Восстановить баланс для столбца В можно только с помощью клетки (R,B), следовательно, в нее необходимо добавить одно изделие. Балансировку строки R можно осуществить через клетки (R,A) и (R.C), но поскольку (R,A) — единственная заполненная клетка и столбце А; ее использовать нельзя. Если бы маршрут проходил через данную клетку, мы не могли бы сбалансировать столбец А. Объем перевозок в (R,C) уменьшается на одно изделие. Оставшаяся часть маршрута очевидна. Восстановление баланса в столбце С производится увеличением перевозок в (Р,С) на одну единицу, а баланс строки Р достигается вычитанием одного изделия из (Р, фиктивный). Последний шаг позволяет также сбалансировать фиктивный столбец и замкнуть цикл. Следует помнить, что построение замкнутого цикла внутри транспортной таблицы, который начинается и заканчивается в выбранной пустой точке, возможно только в случае, если исходное распределение перевозок является базисным. Натуральные и стоимостные изменения, соответствующие построенному циклу, показаны в табл. 4.10 и 4.11.

Чистый стоимостный эффект от размещения в пустой клетке (Q, фиктивный) составит:

+ 0 - 0 + 5 - 7 + 20 - 10 = +8 00 евро за изделие.

В случае заполнения данной пустой клетки общая стоимость транспортировки увеличится на 8 00 евро за 1 изделие. Поэтому мы не будем вводить рассмотренные изменения. Теневые цены для оставшихся пустых клеток рассчитываются аналогичным образом. В табл. 4.12 показано все множество значений теневых цен (они обведены в кружочки).

Таблица 4.10. Проверка пустой клетки (Q, фиктивный)

Таблица 4.11. Проверка пустой клетки (Q, фиктивный)

Таблица 4.12. Проверка начального распределения перевозок на оптимальность — метод ступенек

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

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

Для начала рассмотрим только заполненные клетки. Для этих клеток каждое значение единичной стоимости с,: разделяется на две компоненты — u_i для строк и v_j для столбцов. Например, единичная стоимость для клетки (R,B), лежащей на пересечении строки 3 и столбца 2, равна с₃₂ ⁼ 20 00 евро В ней можно выделить компоненту уз, соответствующую строке, и компоненту v₂, соответствующую столбцу, т.е. с₃₂ = 20 = u₃ + v₂.

Теневые цены для каждой пустой (небазисной) клетки можно найти из соотношения s_ij = с_ij-(u_i + v_j).

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

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

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

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

Торговый склад	Розничный магазин	Общее предложение
А	В	С	Фиктивный
Р Q R
-	-
-		-	-
			-
Общая потребность

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

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

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

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

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

С₂₂= 10 = U2 + 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,С);

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

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

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

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

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