Требуемые знания: знание методов линейного программирования, методов решения транспортной задачи (особенно потенциального метода).
Год назад, третьего 
Разумеется, в качестве одной из лабораторных работ по курсу «Методы оптимизации» мне было предложено реализовать решение транспортной задачи, но с одним небольшим условием: транспортировка происходит партиями.
Это означает, что теперь, в отличие от классической постановки, вы платите за перевозку партии товара (например, 10 штук), и даже если вам нужно перевезти 11 штук, вы платите за две партии товара (11 штук в одну не поместятся).
трейлер).
Казалось бы, незначительное дополнение, но как теперь решить задачу и хотя бы как ее формализовать? Будучи студентом кафедры прикладной математики, мне был не чужд тот факт, что великий google.ru чего-то не знал, но каково же было мое удивление, когда ни его старший брат, англоязычный Google, ни множество книг по Теория оптимизации, с которой я разобрался, смогла ответить на этот вопрос.
Сразу хочу сказать, что я не претендую на премию Филдса со своим алгоритмом.
Ничего сверхъестественного не предлагаю, но для тех, кто только начинает решать такую задачу, могу немного помочь.
Позволять С - платежная матрица, а — вектор грузовых запасов, б – вектор спроса на грузы, k – количество товаров в партии.
Мы рассмотрим следующую формализацию: 
Где Икс — транспортная матрица, т.е.
оптимизируемый параметр, а ячейка округляется до ближайшего целого числа.
Дополнительно вводим во внимание: 
Сначала мы решаем классическую транспортную задачу с F2-> min. Полученное значение F2 является нижней границей F1 на множестве допустимых значений.
Запомним значение F2_save:=F2. Найдите значение F1 для полученного решения Икс и запомните это F1_save=F1. Если F1_save==ceil(F2_save), то Икс - искомое решение, иначе идем дальше.
F1 можно уменьшить только за счет уменьшения базисных компонентов Икс до ближайших кратных значений k, поэтому будем строить (методом ветвей и границ) дерево решений задач с дополнительными ограничениями.
Вершиной дерева является уже полученное решение.
Каждый следующий ярус дерева строится следующим образом: для каждой базовой компоненты (xij), равной некоторому значению (z), не кратному k, решается классическая транспортная задача F2-> min с дополнительным ограничением xij=[z /k]*k ([x] — целая часть x) (см.
P.S.).
Если для полученного решения F1 =F1_save, то не продолжаем эту ветку.
Если F1==ceil(F2_save), то результирующий Икс - искомое решение, иначе идем дальше.
Таким образом, мы получаем дерево решений, каждая ветвь которого заканчивается, если на листе этой ветви ceil(F2)> =F1_save, или если все компоненты из базиса кратны k, или если задача не имела решения при все.
Оптимальным является план, соответствующий полученному после построения дерева F1_save. P.S. Добавляя ограничение, нет необходимости решать задачу заново.
Можно, например, перебрать все возможные убывающие циклы F1 и выбрать среди них оптимальный.
Либо воспользоваться методами двойственного симплекс-метода.
Пример Давайте рассмотрим алгоритм на очень простом примере.
Пусть k=3, C={{2,2},{4,5}}, a={2,3}, b={2,3}.
Итак, вершина дерева — это решение такой транспортной задачи с целевой функцией F2: 0) X={{0,2},{2,1}}, F2(X)~=5,67, F1(X)=2+4+5=11. F2_save:=5.67, F1_save:=11 потому что ячейка(5.67)<11 we go further - we build the next tier of the tree: 1.1) к задаче, решенной в узле 0, добавляем условие x12==0 и решаем ее еще раз.
X={{2,0},{0,3}}, F2(X)~=6,35, F1(X)=2+5=7. потому что Ф1 =F1_save (7> =7), то эту ветку не продолжаем поскольку F1> ceil(F2_save) мы идем дальше (возможно, есть лучшее решение), ветка не продолжается, но уровень еще не закончен.
1.2) к задаче, решенной в узле 0, добавляем условие x21==0 и решаем ее еще раз.
X={{2,0},{0,3}}, F2(X)~=6,35, F1(X)=2+5=7. поскольку F1==F1_save(7==7), то F1_save не меняется поскольку ceil(F2)> =F1_save (7> =7), то эту ветку не продолжаем поскольку F1> ceil(F2_save) мы идем дальше (возможно, есть лучшее решение), ветка не продолжается, но уровень еще не закончен.
1.3) к задаче, решенной в узле 0, добавляем условие x22==0 и решаем ее еще раз.
Эта проблема не имеет решения => и мы не продолжаем эту ветку.
Базовых компонентов больше не осталось (уровень завершен) и продолжать ветки нет необходимости (бессмысленно, лучшего решения мы не получим), а значит дерево построено.
F1_save==7 — наша минимальная стоимость.
Соответствующий им план (он же ответ) X={{2.0},{0.3}} Теги: #Алгоритмы #методы оптимизации #транспортная задача #исследование операций #кибернетика #программирование #алгоритмы #математика
-
Варианты Веб-Дизайна Для Вашего Бизнеса
19 Oct, 24 -
Самые Лучшие Стратегии В Социальных Сетях
19 Oct, 24
