§ 2. Некоторые обобщения

2.1. Описанный в предыдущем параграфе метод Балинского для приближенного решения транспортной задачи с фиксированными доплатами допускает распространение и на более широкие классы задач. Рассмотрим прежде всего распределительную задачу с фиксированными доплатами, описанную в п. 1.3 § 1 гл. 3. Напомним, что эта задача заключается в минимизации

при условиях

Здесь разрывные функции

Путем нахождения верхних границ для переменных и введения дополнительных целочисленных переменных

эта задача сводится к следующей целочисленной задаче. Минимизировать

при условиях (2.2), (2.3), (2.7) и

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

Схема этого метода принципиально не отличается от схемы метода Балинского (п. 1.3 предыдущего параграфа). Именно, заменим прежде всего условие (2.7) целочисленной задачи условием неотрицательности у. Тогда для получающейся частично целочисленной задачи имеет место

Теорема 2.1. Пусть оптимальный план задачи (2.8), (2.2), (2.3), (2.9), (2.10). Тогда

Доказательство этой теоремы не отличается от доказательства теоремы 1.1 предыдущего параграфа.

Так как достаточно ограничиться рассмотрением оптимальных планов, то доказанная теорема позволяет нам выразить из через

Подставляя это выражение в (2.8) и (2.9), мы приходим к задаче минимизации

при условиях (2.2), (2.3) и

Оптимальный план этой задачи естественным образом порождает приближенный план исходной задачи (2.1) — (2.4).

Задача (2.12), (2.2), (2.3), (2.13); оставаясь полностью целочисленной, имеет уже меньшие размеры (при сведении ее к общей задаче целочисленного программирования получаем переменных и ограничений).

К сожалению, описанная в предыдущем параграфе модификация метода Балинского уже не может быть непосредственно перенесена на распределительную задачу с фиксированными доплатами.

2.2. Идею метода Балинского можно использовать также для приближенного решения общей задачи линейного программирования с фиксированными доплатами в целевой функции. Эта задача (см. § 5 гл. 2) заключается в минимизации

при условиях

где

Ограничение целочисленности на здесь не накладывается; все

Если для всех переменных заданы или найдены верхние границы

то путем введения вспомогательных целочисленных переменных

эта задача сводится к следующей частично целочисленной задаче.

Минимизировать

при условиях (2.15), (2.16), (2.19) и

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

при условиях (2.15) и (2.16). Ее оптимальный план будет естественным образом порождать приближенный план исходной задачи (2.14) — (2.16).

2.3. Недавно в работе Купера и Дрибса [60] был предложен более подробно разработанный эвристический метод решения задачи Авторы вообще не используют сведения этой задачи к частично

целочисленной, рассматривая ее в слегка видоизмененной форме.

Минимизировать

при условиях (2.15), (2.16), где

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

Прежде всего, целевая функция (2.23) представляется в виде двух слагаемых:

и

так что

Далее рассматривается задача линейного программирования: минимизировать при условиях (2.15), (2.16).

Процесс разбивается на несколько этапов. На I этапе задача (2.24), (2.15), (2.16) решается методом последовательного улучшения плана. Рассматривается ее оптимальный план и для вошедших в базис векторов пересчитываются коэффициенты целевой функции:

По этим пересчитанным коэффициентам вычисляются новые значения оценок фигурирующих в методе последовательного улучшения плана [45]. Как известно,

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

где вектор пересчитанных согласно (2.27) коэффициентов.

В исходном оптимальном плане как известно, при всех Далее все пересчитываемые согласно (2.27) разности также делают неположительными (путем обычных элементарных преобразований: замены базисных векторов для тех для которых окажется

Результатом I этапа является некоторый план, в определенном смысле наилучший по значениям На

II этапе базисный вектор с наибольшей доплатой выводится из базиса. Если ввести в базис можно несколько векторов, то берется тот из них, для которого величина минимальна (здесь значение переменной которое она приняла бы при введении в базис).

На III этапе к таблице предыдущего этапа применяется другое правило замещения. Вектор из базиса выводится по обычному критерию; вводится в базис вектор с наименьшей (среди небазисных векторов) доплатой

Далее повторяется видоизмененный II этап (из базиса выводится вектор с максимальным где среднее значение базисных переменных), затем снова

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

Проведенная авторами серия вычислительных экспериментов позволяет довольно высоко оценить эффективность этого алгоритма. Было решено несколько сотен задач сравнительно небольших размеров (от 5X10 до 15x30). При этом оптимальные планы были получены в среднем в 95% всех случаев. В остальных случаях процентные отклонения от оптимума были невелики, причем при росте размеров задачи не наблюдалось увеличения этих отклонений. Среднее время решения на машине IBM-7072 для задач 5X10 составило 20 сек., для задач 15X30 — около 15 мин.