ГЛАВА 16. ДЕТЕРМИНИРОВАННЫЕ МЕТОДЫ

В этой главе излагаются некоторые приближенные методы для решения одного частного класса дискретных задач (задачи с фиксированными доплатами). Специфика этого класса задач позволяет разработать ряд приемов, приводящих к вполне приемлемым на практике планам. В § 1 эти приемы излагаются применительно к транспортной задаче с фиксированными доплатами. В § 2 указаны возможности их распространения на более общие случаи.

§ 1. Приближенные методы для транспортной задачи с фиксированными доплатами

1.1. Напомним, что транспортная задача с фиксированными доплатами, называемая также неоднородной транспортной задачей (см. § 5 гл. 2), заключается в минимизации

при обычных условиях транспортного типа

Фигурирующие в (1.1) функции равны

Здесь все Разумеется, если все то задача превращается в обычную транспортную.

1.2. Обсудим прежде всего некоторые прямолинейные подходы к этой задаче, подсказываемые «транспортным» характером ее ограничений. Легко установить следующие простые теоремы, впервые доказанные Данцигом еще в 1954 г. в неопубликованном отчете корпорации РЭНД (см. [106]).

Теорема 1.1. Если в транспортной задаче с фиксированными доплатами все и соответствующая ей обычная транспортная задача (без доплат) с матрицей не вырождена, то оптимальные планы для задач с доплатами и без доплат совпадают.

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

Теорема 2.1. Если в задаче с доплатами различны, то ее оптимальный план следует искать среди опорных планов соответствующей ей транспортной задачи (без доплат) с матрицей С.

Это утверждение станет особенно ясным, если учесть, что целевая функция (1.1), будучи суммой вогнутых функций (рис. 16.1.1, а), сама является вогнутой, и следовательно, ее экстремумы будут достигаться в крайних точках многогранного выпуклого множества (см. [92]). Но поскольку речь идет о минимизации вогнутой функции, любой стандартный метод (например,

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

Попытаемся воспользоваться транспортностью ограничений (1.2)-(1.4) и извлечь некоторую информацию из решения соответствующей транспортной задачи с матрицей С.

Рис. 16.1.1а.

Рис. 16.1.1б.

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

Элементарный алгоритм для искусственного создания вырожденности в транспортной задаче был предложен в [106]. Он основан на том известном факте, что транспортная задача является вырожденной тогда и только тогда, когда существуют такие подмножества индексов:

что

Указанный алгоритм состоит в следующем.

1. Найти .

2. Задавшись некоторым сравнить Если положить вычеркнуть строку и столбец и перейти к шагу 1. Если перейти к шагу 3.

3. Положить

4. Если этот минимум есть авычеркнуть из матрицы строку и положить Если минимум есть вычеркнуть столбец и положить

5. Повторить шаги 1—4 над суженной матрицей, пока все не станут нулями.

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

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

1.3. Сведение транспортной задачи с фиксированными доплатами к целочисленной было продемонстрировано

в § 5 гл. 2. Напомним здесь соответствующую формулировку.

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

при условиях (1.2), (1.3), (1.4) и

где

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

Поэтому естественно пытаться использовать здесь специфику задачи в ином направлении — в направлении создания специализированных приближенных методов. Простой приближенный метод был предложен в 1961 г. Балинским [49]. Идея этого метода основана на рассмотрении задачи с отброшенным условием целочисленности (1.7). Она дается следующей простой теоремой.

Теорема 3.1. Пусть оптимальный план задачи (1.6), (1.2) -(1.4), (1.8). Тогда

Доказательство. Если то в силу (1.8) и т. е. (1.10) выполняется. Пусть но вместо (1.10) мы имеем неравенство Тогда можно уменьшить до тех пор, пока не будет выполняться (1.10). Ограничения задачи при этом нарушаться не

будут, а значение линейной формы (1.6) уменьшится. Следовательно, план не является оптимальным; это противоречие и доказывает теорему.

Из этой теоремы следует, что при поиске оптимального плана задачи (1.6), (1.2) - (1.4), (1.8) без учета требования целочисленности можно выразить из через

и прийти тем самым к задаче минимизации линейной формы

при условиях (1.2) — (1.4). Таким образом, транспортная задача с фиксированными доплатами аппроксимирована обычной транспортной задачей (1.11), (1.2) -(1.4), машинное решение которой освоено достаточно хорошо и никаких трудностей уже не представляет.

По оптимальному плану задачи (1.11), (1.2) — (1.4) естественным образом выписывается приближенный план задачи с фиксированными доплатами:

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

Идея этого метода станет еще более прозрачной, если обратиться к геометрической интерпретации

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

откуда сразу находим коэффициенты линейной функции

Рис. 16.1.1в.

Таким образом, однородная транспортная задача с коэффициентами линейной формы (1.13) и есть задача (1.11), (1.2) — (1.4).

1.4. Остановимся теперь на одной модификации метода Балинского, позволяющей во многих случаях улучшить получаемый с его помощью приближенный план (см. [11], [13], [14]). Идея этого подхода заключается в следующем. В любом оптимальном плане аппроксимирующей транспортной задачи с матрицей всегда найдется по крайней мере два таких что По тем парам для которых затраты в задачах и (1.11), (1.2) -(1.4) совпадают и равны Для остальных же пар

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

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

Это реализуется следующим образом. В качестве первого приближения к оптимальному плану задачи (1.1) — (1.4) составляется и решается транспортная задача с целевой функцией (1.11) (т. е. осуществляется метод Балинского). В оптимальном плане этой задачи отмечаются те для которых т. е. или Такие строки и столбцы назовем висячими рядами. Затем производится поочередное вычеркивание висячих рядов и пересчет соответствующих (аналогичные операции производятся в известном методе минимального элемента, о котором мы упоминали в п. 1.2). Именно, если вычеркиваем строку и полагаем если же вычеркиваем столбец и полагаем Для остальных берем После этого находим

вычисляем

и решаем транспортную задачу (меньших размеров!) с исходными данными

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

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

На каждом цикле в окончательный план переносятся те которые оказались в висячих рядах.

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

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

1.5. Опишем более подробно намеченный выше приближенный метод. Как уже указывалось, в нем по данной задаче с фиксированными доплатами строится последовательность транспортных задач, причем задача совпадает с задачей (1.11),

Задача 0. Дано множество пунктов производства с объемами производства и множество пунктов потребления с объемами потребления (Здесь Требуется минимизировать

где

при условиях

Пусть оптимальный план задачи 0. Как известно, для него существует система потенциалов, т. е. таких чисел что для всех для тех при которых

Найдем множества висячих строк и столбцов:

Как известно, хотя бы одно из этих множеств не пусто. Рассмотрим него найдется такой индекс что Найдем

Аналогично для любого найдется для которого Найдем

Определим

Обозначим

Плану задачи соответствует в задаче значение целевой функции (1.1), равное

Вычислим, кроме того,

Задача 1. Дано множество пунктов производства с объемами производства где

Дано множество пунктов потребления с объемами производства где

Требуется минимизировать

где

при условиях

Пусть оптимальный план задачи 1. Вычислим

Если то переходим к задаче 2, используя план Если переходим к задаче 2, используя план

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

Вычислим

Если находим множества висячих рядов

Для каждого находим

а для каждого

Вычисляем

Обозначим

Вычислим

и переходим к задаче

Задача Дано множество пунктов производства с объемами производства

Дано множество пунктов потребления с объемами потребления

Требуется минимизировать

где

при условиях

Напомним, что описанный переход к задаче выполняется в случае Если же то переход к задаче осуществляется на основе плана

В качестве приближенного плана задачи принимается план где

1.6. Машинное опробование описанного сейчас алгоритма пока не проводилось. Ручной счет для задач небольших размеров показал, что этот алгоритм может дать снижение суммарных затрат против значения, по лучаемого по методу Балинского, порядка 3—5%.

Как основной вариант метода Балинского, так и описанная здесь его модификация первоначально предназначались для решения сбалансированных задач, задач, в которых

Между тем для многих прикладных задач такого типа (в особенности для задач размещения — см. § 2 гл. 3) характерна значительная несбалансированность (открытость):

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