[Бизнес-модели, Математика] Кластерный метод решения транспортной задачи
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Оптимизация в бизнесе в подавляющем числе случаев связана с применением метода линейного программирования. Метод достаточно понятен. Кроме того, имеется теорема существования и единственности решения.
Однако на практике все обстоит не совсем просто.
Первая проблема — это нелинейность реальных условий. Для того, чтобы метод линейного программирования можно было применить, они должны быть линеаризованы. Имеются способы правдоподобного задания нелинейности через линейные уравнения и неравенства за счет введения новых переменных, задания весовых коэффициентов и т.п. При решении производственных задач в этом случае необходимо оперировать большим количеством переменных и соответственно уравнений (неравенств).
В теории решения экстремальных задач имеется теорема об устойчивости решения задач линейного программирования. Согласно ей решение устойчиво только при условии выпуклости области определения задачи. При большом количестве переменных и неравенств установить, выпукла ли область определения задачи, не представляется возможным. При этом вероятность не выпуклости велика.
В случае если задача не устойчива, то в зависимости от начальной точки обхода вершин будет получаться разный результат.
Вторая проблема — ограничение переменной снизу (x>h>0). Любая реализация метода линейного программирования всегда обеспечит не нулевое значение x. Если x будет в точности равно h, то это означает, что значение переменной x по сути должно быть нулевым. На практике такие «фиктивные» объемы (эксцесс метода) разбрасывают по «содержательным» переменным. Следствие такой практики — эрозия понятия оптимального решения, что особенно важно, если такое решение одно из многих в цепочке решений.
Третья проблема — управленческая. Метод линейного программирования дает только один результат. А как посмотреть близкие результаты к оптимальному? Например, в полученном решении рейтинг поставщика плохой. Как понять, есть ли близкие решения, но для надежных поставщиков.
Транспортная задача
Пример соответствует транспортной задаче линейного программирования.
Имеется 5 перевозчиков (задача ставилась для перевозки угля), у которых действует двух тарифный расчет. Границы тарифов и сами тарифы можно менять (они заданы параметрически).
Перевозки задаются как точка-точка (по принятой методике при перевозке угля) и объем.
Общий вид интерфейса.
Область задания перевозок.
Кластерный метод решения
Вместо одной задачи линейного программирования решается кластер задач, количество которых соответствует всем возможным сочетаниям тарифов. В приведенной выше перевозке их 127 (второе значение в верхнем левом прямоугольнике).
Оптимальные решения выбираются из совокупности оставшихся корректных задач. Каждая задача дает оптимальное решение для конкретного сочетания тарифов. Выведенные выше решения составляют некоторый диапазон максимумов.
Чем хорош кластерный метод:
- появляется понимание устойчивости решения.
- нет «фиктивных» объемов по переменным, ограниченным снизу, так как будет существовать другое сочетание, где такое условие отсутствует (так как такая переменная отсутствует).
- можно вводить субъективные условия (рейтинги, предпочтения) в рамках применения стандартного метода линейного программирования.
При большем количестве перевозок имеем следующую картину (фрагмент).
В верхнем левом углу в прямоугольнике над решениями (выделено оранжевым) указаны другие величины, чем ранее: 127 — сочетаний (как и раньше, что связано со структурой тарифных сеток), 26 — соответствует количеству оставшихся корректных задач, которые решаются. Под названием фирмы-перевозчика красным указан используемый тариф, а столбцы перевозок соответствуют перечню маршрутов (подчеркнуто оранжевым).
Важно отметить, что применяемый метод позволяет понять полученный результат, оценить аналогичные решения и использовать свой профессиональный опыт при выборе альтернатив, учитывая тонкости ведения конкретного бизнеса.
===========
Источник:
habr.com
===========
Похожие новости:
- [Математика, Научно-популярное] Бенуа Мандельброт на TED: «Фракталы и искусство изломов» (перевод)
- [Карьера в IT-индустрии, Математика, Научно-популярное, Физика] Нефтянка для инженеров, программистов, математиков и широких масс трудящихся, часть 4
- [Анализ и проектирование систем] UML. Взгляд со стороны или «Как UML удерживает аналитиков в прошлом». Часть 1
- [Биотехнологии, Мозг, Научно-популярное, Читальный зал] Предсказание будущего: нейрокомпьютерная модель распознавания речи
- [Habr, Бизнес-модели, Брендинг, Медийная реклама, Управление проектами] Как выбрать нишу для создания своего курса или онлайн школы?
- [*nix, C, История IT, Математика] Утерянная диссертация Денниса Ритчи (перевод)
- [Алгоритмы, Киберспорт, Математика, Программирование] Технологические соревнования Радиофест-2020
- [C#, Open source, Биотехнологии, Клиентская оптимизация, Научно-популярное] Играем в Бога, причиняем непрошеную помощь науке и немножечко Сингулярности
- [Big Data, Математика, Машинное обучение] Алгоритм MADDPG OpenAI (перевод)
- [Бизнес-модели, Исследования и прогнозы в IT, Карьера в IT-индустрии, Хакатоны] «Хакатоны можно использовать для найма»: опыт организатора 35 хакатонов
Теги для поиска: #_biznesmodeli (Бизнес-модели), #_matematika (Математика), #_transportnaja_zadacha (транспортная задача), #_linejnoe_programmirovanie (линейное программирование), #_modelirovanie (моделирование), #_biznesmodeli (
Бизнес-модели
), #_matematika (
Математика
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 20:36
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
 Оптимизация в бизнесе в подавляющем числе случаев связана с применением метода линейного программирования. Метод достаточно понятен. Кроме того, имеется теорема существования и единственности решения. Однако на практике все обстоит не совсем просто. Первая проблема — это нелинейность реальных условий. Для того, чтобы метод линейного программирования можно было применить, они должны быть линеаризованы. Имеются способы правдоподобного задания нелинейности через линейные уравнения и неравенства за счет введения новых переменных, задания весовых коэффициентов и т.п. При решении производственных задач в этом случае необходимо оперировать большим количеством переменных и соответственно уравнений (неравенств). В теории решения экстремальных задач имеется теорема об устойчивости решения задач линейного программирования. Согласно ей решение устойчиво только при условии выпуклости области определения задачи. При большом количестве переменных и неравенств установить, выпукла ли область определения задачи, не представляется возможным. При этом вероятность не выпуклости велика. В случае если задача не устойчива, то в зависимости от начальной точки обхода вершин будет получаться разный результат. Вторая проблема — ограничение переменной снизу (x>h>0). Любая реализация метода линейного программирования всегда обеспечит не нулевое значение x. Если x будет в точности равно h, то это означает, что значение переменной x по сути должно быть нулевым. На практике такие «фиктивные» объемы (эксцесс метода) разбрасывают по «содержательным» переменным. Следствие такой практики — эрозия понятия оптимального решения, что особенно важно, если такое решение одно из многих в цепочке решений. Третья проблема — управленческая. Метод линейного программирования дает только один результат. А как посмотреть близкие результаты к оптимальному? Например, в полученном решении рейтинг поставщика плохой. Как понять, есть ли близкие решения, но для надежных поставщиков. Транспортная задача Пример соответствует транспортной задаче линейного программирования. Имеется 5 перевозчиков (задача ставилась для перевозки угля), у которых действует двух тарифный расчет. Границы тарифов и сами тарифы можно менять (они заданы параметрически).  Перевозки задаются как точка-точка (по принятой методике при перевозке угля) и объем. Общий вид интерфейса.  Область задания перевозок.  Кластерный метод решения Вместо одной задачи линейного программирования решается кластер задач, количество которых соответствует всем возможным сочетаниям тарифов. В приведенной выше перевозке их 127 (второе значение в верхнем левом прямоугольнике).  Оптимальные решения выбираются из совокупности оставшихся корректных задач. Каждая задача дает оптимальное решение для конкретного сочетания тарифов. Выведенные выше решения составляют некоторый диапазон максимумов. Чем хорош кластерный метод:
При большем количестве перевозок имеем следующую картину (фрагмент).  В верхнем левом углу в прямоугольнике над решениями (выделено оранжевым) указаны другие величины, чем ранее: 127 — сочетаний (как и раньше, что связано со структурой тарифных сеток), 26 — соответствует количеству оставшихся корректных задач, которые решаются. Под названием фирмы-перевозчика красным указан используемый тариф, а столбцы перевозок соответствуют перечню маршрутов (подчеркнуто оранжевым). Важно отметить, что применяемый метод позволяет понять полученный результат, оценить аналогичные решения и использовать свой профессиональный опыт при выборе альтернатив, учитывая тонкости ведения конкретного бизнеса. =========== Источник: habr.com =========== Похожие новости:
Бизнес-модели ), #_matematika ( Математика ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 20:36
Часовой пояс: UTC + 5