ЧАСТЬ IV. ПРИБЛИЖЕННЫЕ МЕТОДЫ

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

Приближенные методы дискретного программирования могут конструироваться двумя принципиально разными путями. Первый из них связан с использованием идеи случайного поиска; такие методы описываются в гл. 15. В наиболее чистом виде идея случайного поиска воплощена в методе, предложенном Пятецким-Шапиро, Волконским, Левиной и Поманским [25]. Этот метод приведен в § 1. Идея сочетания случайного поиска с локальной оптимизацией была выдвинута Рейтером и Шерманом [119]; их работа излагается в § 2.

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

ГЛАВА 15. МЕТОДЫ СЛУЧАЙНОГО ПОИСКА

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

§ 1. Случайный поиск

1.1. В статье Пятецкого-Шапиро, Волконского, Левиной и Поманского [25] был предложен итеративный метод для решения задачи линейного программирования с булевыми переменными. Как отмечают авторы, этот метод навеян идеями теории игр автоматов [2].

Задача ставится обычным образом:

Максимизировать

при условиях

Все коэффициенты предполагаются неотрицательными.

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

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

Опишем метод итераций для решения системы Начальный набор выбирается

произвольным образом. Пусть на шаге процесса получен набор Вычисляем величины

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

где Это приводит к новому вектору для которого проводится следующая итерация. Когда все А обращаются в 0, процесс окончен, решение системы найдено.

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

1.4. При численном экспериментировании с описанным методом было сосчитано, в частности, несколько примеров, в которых приближенные решения можно сравнить с точными. Так, в примере размером 3X17 при точном значении максимума, равном 14,91, значение было достигнуто за 14 итераций, значение за 166 итераций. В примере при точном значении максимума, равном 20, значение было достигнуто за 253 итерации, значение за 2317

итераций (тип машины и машинное время не указаны). В этих расчетах величина в (1.6) бралась равной 1/2.

1.5. В работе Пятецкого-Шапиро, Волконского, Казакевича и Левиной [24] намечено одно усовершенствование описанного метода, позволяющее расширить возможности его применения на реальные прикладные задачи больших размеров. Оно основано на следующих простых соображениях. При решении реальных задач целесообразно искать не один определенный план, а серию близких к оптимальному планов, один из которых будет выбран при окончательном анализе задачи. Далее большую задачу можно разбить (более или менее произвольным образом) на несколько подзадач и для каждой из них найти серии близких к оптимуму планов. Затем рассматриваются всевозможные комбинации полученных планов и с помощью полного перебора среди них находятся наилучшие для задачи в целом. Кроме того, для упрощения решения системы неравенств (1.2) — (1.4) целесообразно иногда прежде всего искать решения «огрубленной» системы, т.е. требовать выполнения (1.2), скажем, с точностью а (1.4) — с точностью Дальнейший анализ проводится уже над сериями «огрубленных» планов.