НОВОСТИ [Из песочницы] Кластерный метод решения транспортной задачи

[Alvaros]

Оптимизация в бизнесе в подавляющем числе случаев связана с применением метода линейного программирования. Метод достаточно понятен. Кроме того, имеется теорема существования и единственности решения.

Однако на практике все обстоит не совсем просто.

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

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

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

Вторая проблема — ограничение переменной снизу (x>h>0). Любая реализация метода линейного программирования всегда обеспечит не нулевое значение x. Если x будет в точности равно h, то это означает, что значение переменной x по сути должно быть нулевым. На практике такие «фиктивные» объемы (эксцесс метода) разбрасывают по «содержательным» переменным. Следствие такой практики — эрозия понятия оптимального решения, что особенно важно, если такое решение одно из многих в цепочке решений.

Третья проблема — управленческая. Метод линейного программирования дает только один результат. А как посмотреть близкие результаты к оптимальному? Например, в полученном решении рейтинг поставщика плохой. Как понять, есть ли близкие решения, но для надежных поставщиков.

Транспортная задача


Пример соответствует транспортной задаче линейного программирования.
Имеется 5 перевозчиков (задача ставилась для перевозки угля), у которых действует двух тарифный расчет. Границы тарифов и сами тарифы можно менять (они заданы параметрически).

Перевозки задаются как точка-точка (по принятой методике при перевозке угля) и объем.
Общий вид интерфейса.

Область задания перевозок.

Кластерный метод решения


Вместо одной задачи линейного программирования решается кластер задач, количество которых соответствует всем возможным сочетаниям тарифов. В приведенной выше перевозке их 127 (второе значение в верхнем левом прямоугольнике).

Оптимальные решения выбираются из совокупности оставшихся корректных задач. Каждая задача дает оптимальное решение для конкретного сочетания тарифов. Выведенные выше решения составляют некоторый диапазон максимумов.

Чем хорош кластерный метод:

• появляется понимание устойчивости решения.
• нет «фиктивных» объемов по переменным, ограниченным снизу, так как будет существовать другое сочетание, где такое условие отсутствует (так как такая переменная отсутствует).
• можно вводить субъективные условия (рейтинги, предпочтения) в рамках применения стандартного метода линейного программирования.

При большем количестве перевозок имеем следующую картину (фрагмент).

В верхнем левом углу в прямоугольнике над решениями (выделено оранжевым) указаны другие величины, чем ранее: 127 — сочетаний (как и раньше, что связано со структурой тарифных сеток), 26 — соответствует количеству оставшихся корректных задач, которые решаются. Под названием фирмы-перевозчика красным указан используемый тариф, а столбцы перевозок соответствуют перечню маршрутов (подчеркнуто оранжевым).

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