Транспортная задача с партийными перевозками(«с трейлерами»)

Требуемые знания: знакомство с методами линейного программирования, методы решения транспортной задачи(особенно метод потенциалов).

Год назад, на третьем курсе в качестве одной из лабораторных работ по курсу «Методы оптимизации» мне задали реализовать решение транспортной задачи, но с одним небольшим условием: перевозки происходят партиями. Это значит, что теперь, в отличие от классической постановки, оплачивается перевозка партии товаров (e.g. 10 штук), и, даже если Вам надо перевезти 11 штук, Вы заплатите за две партии(в один трейлер 11 штук не влезут). Казалось бы, мелкое дополнение, однако как теперь решать задачу, да хотя бы как её формализовать? Как студенту кафедры прикладной математики, мне было не привыкать, что великий google.ru чего-то не знает, но каково же было моё удивление, когда ни его старший брат — англоязычный google, ни тьма перебранных мной книг по теории оптимизации не смогли ответить на этот вопрос.

Сразу хочу сказать — на премию Филдса я со своим алгоритмом не претендую. Ничего сверхъестественного я не предлагаю, но тем, кто только приступает к решению такой задачи, могу немного подсобить.
Пусть C — платёжная матрица, a — вектор запасов груза, b — вектор потребности в грузе, k — количество товаров в партии. Будем рассматривать такую формализацию:

где X — матрица перевозок, т.е. оптимизируемый параметр, а ceil — округление вверх до ближайшего целого.
Дополнительно введём в рассмотрение:

Для начала решаем классическую транспортную задачу с F2->min. Полученное значение F2 является нижней границей для F1 на множестве допустимых значений. Запомним значение F2_save:=F2. Находим значение F1 при полученном решении X и запомним его F1_save=F1. Если F1_save==ceil(F2_save), то X — искомое решение, в противном случае идём далее.
F1 можно уменьшить лишь уменьшая базисные компоненты X до ближайших кратных k значений, поэтому будем строить(метод ветвей и границ) дерево решений задач с дополнительными ограничениями. Вершиной дерева является уже полученное решение. Каждый следующий ярус дерева строится следующим образом: для каждой базисной компоненты(xij), равной некоторому не кратному k значению(z), решаем классическую транспортную задачу F2->min с дополнительным ограничением xij=[z/k]*k ([x] — целая часть от x) (см. P.S.). Если для полученного решения ceil(F2)>=F1_save, то далее эту ветвь не рассматриваем. Если F1==ceil(F2_save), то полученное X — искомое решение, в противном случае идём далее. Если для полученного решения F1<F1_save, то F1_save:=F1. Таким образом получаем дерево решений, каждая ветвь которого завершается если на листе этой ветви ceil(F2)>=F1_save, или если все компоненты из базиса кратны k или если задача вообще не имела решение. План, соответствующий полученному после построения дерева F1_save, является оптимальным.

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

Автор: Pavel_Osipyants

Источник