Содержание к диссертации
Введение
ГЛАВА I. Метод последовательного уменьшения размеиюсти задачи бинарного программирования 21
1.1. Обзор некоторых подходов к уменьшению размерности задачи ЦЛП 21
1.2. Уменьшение количества переменных и ограничений в задаче бинарного программирования 26
1.3. Описание алгоритма последовательного уменьшения размерности задачи бинарной оптимизации 33
1.4. О вычислительной реализации алгоритма ПУРЗ 41
1.5. Некоторые результаты вычислительных экспериментов 56
ГЛАВА II. Метод построения нижней оценки оптимального значения целевой функции задачи бинарного программирования 59
2.1. Методы приближенного решения и методы, ориентированные на построение допустимого решения 59
2.2. Методы типа последовательного назначения для приближенного решения задачи бинарного программирова ния с неотрицательными коэффициентами 69
2.3. Алгоритмы улучшения приближенных решений задачи бинарного программирования с неотрицательными коэффициентами 82
2.4. Обобщение методов типа последовательного назначе ния для приближенного решения некоторых классов задач 91
2.5. Пакет прикладных программ РАНЕЦ-І для приближенно го решения задачи бинарного программирования с не отрицательными коэффициентами 103
2.6. Вычислительные эксперименты 106
ГЛАВА III. Методо построения верхней оценки оптимального значения целевой функции задачи бинарного программирования 112
3.1. Некоторые подходы к вычислению верхней оценки оптимального значения целевой функции задачи бинарного программирования 112
3.2. Метод обхода вершин многогранника ограничений задачи бинарной оптимизации 121
3.3. Вычислительные аспекты алгоритма ОБХОД 129
3.4. Результаты вычислительных экспериментов 139
Заключение 142
Литература
- Уменьшение количества переменных и ограничений в задаче бинарного программирования
- О вычислительной реализации алгоритма ПУРЗ
- Методы типа последовательного назначения для приближенного решения задачи бинарного программирова ния с неотрицательными коэффициентами
- Метод обхода вершин многогранника ограничений задачи бинарной оптимизации
Введение к работе
При решении таких важнейших проблем экономического развития страны, как повышение эффективности производства на основе комплексного внедрения достижений научно-технического прогресса, интенсификация производства, рациональное использование трудовых, материальных и финансовых ресурсов в народном хозяйстве, все больше применяются математические методы оптимизации. Наряду с такой объективной необходимостью, все возрастающее использование экономико-математического моделирования и математических методов оптимизации основывается также, с одной стороны, на значительном развитии теории и вычислительных методов математического программирования, и с другой стороны, на огромном количестве АСУ различного уровня, функционирующих на базе мощной современной вычислительной техники и развивающихся, в первую очередь, за счет внедрения новых оптимизационных задач.
Одним из быстроразвивающихся разделов математического программирования является дискретное программирование, задачи которого выражаются в виде отыскания экстремума некоторой функции на некотором дискретном множестве. К задачам дискретной оптимизации сводятся многие оптимизационные задачи, имеющие важное народнохозяйственное значение. Это - задачи планирования работ, организации производства, размещения и реконструкции предприятий и др. [43, 54, 83,86,89] . За последние годы в связи с интенсивным развитием АСУ, теории и технологии вычислительных сетей в терминах дискретного программирования сформулированы многие задачи, возникающие при проектировании АСУ, вычислительных сетей и систем ЭВМ, а также при обработке данных в вычислительных центрах и системах [95,71,84].
Большинство из перечисленных практических задач выражается
5
в виде следующей задачи целочисленного линейного программирова
ния (ВДП): ^
Максимизировать f"(X) = -> С X: (I)
и, & * * при ограничениях &00- 2 &д *j «^ , 6=i,...,"t, (2)
0 4Х;<о!., І <.«,*, (3)
)(j - целые, ^=1,...,11/. (4) При ol.= I задача ЦЛП (I) - (4) называется задачей бинарного
программирования (бинарной оптимизации) или булева программирования, подчеркивая тем самым, что переменные задачи могут принимать лишь только два альтернативные целочисленные значения 0 и I.
Постоянное внимание многих исследователей к задаче бинарного программирования не случайно, так как она имеет важное методологическое и практическое значение:
к ней сводится всякая линейная задача дискретной оптимизации, множество допустимых решений которой ограничено [54,49] ;
большинство из многих принципиальных трудностей, возникающих при ее решении являются характерными и для других задач дискретной оптимизации в более общей постановке;
обычно не возникают трудности при распространении предложенного для ее решения метода на общую задачу ЦДЛ.
Поэтому эта задача является естественной моделью для выработки общих подходов к решению задач дискретной оптимизации.
С ростом количества переменных и ограничений эффективность методов решения задач ЦЛП резко падает. Поэтому в настоящее время наряду., с разработкой и исследованием новых методов решения и различных приемов повышения эффективности этих методов весьма актуальной является разработка и исследование различных подходов, связанных с предварительным уменьшением размерности задачи. В связи с этим настоящая диссертиционная работа посвящена исследо-
ванию различных подходов к уменьшению размерности задачи бинарного программирования с использованием двусторонних оценок оптимума целевой функции.
Сложность решения задач ЦЛП неоднократно была подтверждена как теоретически, так и экспериментально [52,89]. В частности, исследование задачи ЦЛП с позиций сильно развивающейся в последние годы теории сложности вычислений: показало, что эта задача принадлежит к классу NP - полных задач [36,129].
Последнее фактически означает, что все без исключения известные методы решения задачи ЩП имеют экспоненциальную оценку зависимости трудоемкости решения от ее размерности и что всякая другая комбинаторная задача, имеющая только экспоненциальные алгоритмы решения, может быть полиноминально сведена к задаче ЦШ1.
Как видно, трудность решения задач ЦЛП основана не столько на некачественности методов и малой производительности современных ЭВМ, сколько в принципиальной сложности самих задач.
Экспоненциальная оценка трудоемкости методов решения задачи ЦЛП, являясь оценкой по наихудшему случаю, ни в коей мере не означает, что всякое применение этих методов к решению конкретных задач ЦЛП будет требовать очень большие вычислительные затраты. Имеется немало сообщений об удачном применении мощных пакетов программ к решению задач с сотнями и даже тысячами целочисленных переменных [Юб, 51]. Интересно отметить, что исправно служащий в течение долгого времени исследователям и практикам и считающийся достаточно эффективным симплекс - метод решения задачи линейного программирования (ЛП) тоже имеет экспоненциальную оценку трудоемкости.
Исторически первым методом решения задачи ЦЛП является метод отсечения, геометрически прозрачная идея которого впервые была
предложена Данцигом [l07] и вкратце заключается в следующем: предлагается вначале пренебречь условием целочисленности переменных и вместо задачи ЦЛП (I) - (4) решить задачу ЛП (I) - (3). Если решение задачи ЛП не является целочисленным, то к системе ограничений (2) - (3) добавляется новое ограничение, которому полученное решение задачи ЛП не удовлетворяет, а любое допустимое (целочисленное) решение задачи (I) - (4) заведомо удовлетворяет.
Далее решается очередная задача ЛП, система ограничений которой содержит на одно неравенство больше и т.д. до получения задачи ЛП с целочисленным оптимальным решением.
Впервые идею Данцига удалось удовлетворительно реализовать Гомори [Пб]. Ему принадлежат алгоритмы полностью и частично целочисленного линейного программирования, подробное изложение которых можно найти в [54,110,91,I34J. Эти, ставшие уже классическими, алгоритмы дали начало целому ряду работ, в которых рассматривались различные способы построения отсечений [146,97,147, ИЗ, 103,92,112] и делались попытки их сравнения [ЗЗ].
Вычислительная практика (в основном, только по методам Гомори) показала невысокую эффективность методов отсечения [54].
Несмотря на это, алгоритмы отсечений могут быть успешно использованы, если их применять не как метод точного решения, а как вспомогательный аппарат для анализа задачи. Они также могут быть использованы в схемах различных методов решения задачи ЦЛП для увеличения эффективности этих методов и получения новых гибридных методов [ 88,119,27,138,106J . Такая методология применения отсечений систематически используется и в настоящей работе.
Большое количество методов решения задачи ЦЛП относится к комбинаторным методам. Основная идея всех комбинаторных методов состоит в использовании конечности множества решений и замене
8 полного их перебора сокращенным перебором. Последнее достигается отсеиванием неперспективных подмножеств решений, заведомо несо-держащих оптимальных решений.
Одним из первых наиболее общих методов комбинаторного типа, примененного для решения задачи ЦЛП,был метод динамического программирования [22] . Метод может быть применен к задаче ЦЛП с небольшим числом ограничений. Наиболее хорошо разработаны и исследованы различные схемы применения метода динамического программирования к задаче о ранце [23,П0] (задаче бинарного программирования только с одним ограничением вида (2)).
Метод динамического программирования для решения задач дискретной оптимизации является частным случаем более универсального и гибкого метода последовательного анализа вариантов, предложенного В.С.Михалевичем, Н.З.Шором [64І и развитого в последующих работах [65,66,68,69 ] . В основе схемы последовательного анализа вариантов лежит теоретико-множественный подход к задаче поиска решений. Алгоритмы, реализующие эту схему, используют различные идеи перебора и анализа вариантов, позволяющие отсеивать множества неоптимальных решений задачи без их полного просмотра. Многие исследования по методу последовательного анализа вариантов нашли широкое применение и развитие в созданной в Институте кибернетики АН УССР программной системе ДИСПРО для решения задач дискретного программирования [ 67J.
Мощным средством решения широкого круга задач дискретной оптимизации является метод построения последовательности планов, разработанный и развитый Емеличевым В.А. и его учениками[40,41,43,73І. Сущность этого метода состоит в замене исходной задачи более простой, вспомогательной задачей, для которой удается находить не только оптимальное решение, но и следующие за ним решения
9 в порядке ухудшения новой целевой функции. Последовательное построение таких решений продолжается до выполнения критерия оптимальности. Важной особенностью метода построения последовательности планов является то, что схема метода позволяет в ходе процесса оценивать оптимум целевой функции исходной задачи с двух сторон, одновременно генерируя приближенное решение.
Из комбинаторных методов, предназначенных для решения специальных задач целочисленного программирования, следует выделить оригинальный метод последовательных расчетов [93], который предназначен для нахождения максимума функции Иод), определенной на всех подмножествах заданного конечного множества Я* . При этом предполагается, что функция удовлетворяет следующему аналогу условия выпуклости. Для любого OJH , 60Д в Л
На основе метода последовательных расчетов разработан ап-проксимационно-комбинаторный метод [90J, успешно применяющийся для решения ряда прикладных задач.
На сегодняшний день по всеобщему признанию наиболее мощным и перспективным методом решения задач дискретной оптимизации является метод ветвей и границ. Первой публикацией по данному методу была работа [123] в I960 г., в которой предлагалась схема метода ветвей и границ применительно к задаче ЩП. Однако значительный интерес специалистов этот метод вызвал лишь после появления известной работы Литла, Мурти и др. [124], где детально описывалось применение метода ветвей и границ к задаче о коммивояжере, а также сообщалось о машинной реализации и успешном решении, задач с количеством до 40 городов.
Под методом ветвей и границ обычно понимается метод последовательного разбиения множества допустимых решений на подмножества, имеющий древовидную структуру поиска решения и использующий
10 -в процессе поиска результаты решения оценочных (релаксиро-ванных) задач на подмножествах. Детальное описание формальной схемы метода ветвей и границ содержится, например, в [52,54,ПО:, III] . Эта схема содержит четыре основных элемента:
Выбор подзадачи для ветвления.
Выбор способа ветвления. , і 3. Выбор метода построения оценочных подзадач.
4. Выбор метода решения оценочных подзадач.
Как видно, каждый из перечисленных элементов представляет вычислителю определенную свободу выбора, что является весьма характерным и ценным свойством метода ветвей и границ.
Эффективность алгоритма существенным образом зависит от способа реализации указанных выше основных элементов (см.,например, [52]).
Высокая вычислительная эффективность метода ветвей и границ подтверждена многочисленными эксперементами и решением большого количества прикладных задач. Почти все наиболее мощные коммерческие пакеты программ по решению задачи ЩШ (ЛП АСУ, МІР/370,АРЕХ Ш и ІУ и др.) реализованы на базе метода ветвей и границ.
В последнее время значительное развитие и применение получили приближенные методы дискретной оптимизации. Объективные причины, стимулировавшие появление приближенных методов и краткий обзор основных направлений их развития, приведены в первой части 2.1 настоящей работы.
При проверке вычислительной эффективности новых точных и приближенных методов, при сравнении различных методов между собой становится необходимым иметь возможность сгенерировать серии случайных задач ЩШ, исходные данные которых в случае необходимости можно было бы получать повторно. К сожалению, публикации о формировании тестовых задач немногочисленны. При проведении вычисли-
тельных эксперементов, результаты которых изложены в работе, для генерации тестовых задач в основном использовались генераторы тестовых задач из [77] и формулы вычисления случайных коэффициентов ЦЛП из [l7]. Отметим интересную работу [l04] , где изложены предварительные результаты попытки создать генератор тестовых задач бинарного программирования с заданными значениями параметров, определяющих, по мнению авторов, сложность решения этих задач.
В [20] предложен новый подход к проблеме построения тестовых задач дискретного программирования, основанный на использовании аппарата функции Лагранжа. Основная идея этого подхода заключается в следующем. Если заданы коэффициенты ограничений - ОС-и целевой функции - с-, то каждому неотрицательному вектор - мно-жителю Лагранжа соответствует функция Лагранжа. Максимум последней функции по прямым неизвестным при условии их_целочисленности определяет некоторый вектор X, который является оптимальным решением задачи (I) - (4), если правые части положить равными
fry *
6L = zL &u X^, іН-^.Зта задача и принимается за тестовую. Опыт решения больших прикладных задач ЦЛП показывает наличие многих избыточностей в формулировке этих задач, которые не всегда могут быть замечены постановщиком задачи - как правило не являющегося специалистом по математическому программированию. Поэтому не удивительно, что успехи, достигнутые при применении коммерческих программ для решения прикладных задач, обычно связаны с предварительным анализом задач и видоизменением модели (с возможным участием пользователя)[106,109,128,131] . Многие из приемов предварительного анализа довольно прозрачны, вычислительно не трудоемки и обычно не требуют вычисления различных оценок с применением аппарата ЛП.' С другой стороны имеет смысл применить различные критерии для уменьшения размерности задачи с вычислением .
12 оценок и привлечением аппарата ЛП. (Одна такая схема уменьшения
размерности задачи бинарного программирования описана и исследуется в гл.I настоящей работы). Такой вторичный анализ требует больших вычислительных усилий, чем предварительный анализ, но дает лучшие результаты по сокращению размерности задачи.
С учетом всего вышеизложенного, по нашему мнению, в настояв щее время наиболее перспективным можно считать следующую общую схему системы решения задачи ЦШ1:
Этап I
Препроцессирование задачи (Предварительный анализ и видоизменение модели)
Этап 2
Вторичный анализ (Применение более сильных критериев для уменьшения размерности задачи)
Сохранение информации для восстановления исходной задачи
Этап 3
Применение мощного пакета программ на базе метода ветвей и границ (с использованием улучшенных оценок, эвристик для выбора ветвления, анализа на уровне подзадач, уточнением приоритетов в диалоговом режи ме и т.д.)
Выдача результатов в терминах исходной задачи.
Объединение результатов, полученных на первых двух этапах и на этапе 3
ІЗ В связи с этим целью исследования в настоящей диссертационной работе является:
построить общую схему алгоритма, предназначенного для последовательного уменьшения размерности задачи бинарного программирования с использованием верхних и нижних оценок оптимума;
сформулировать в общем виде алгоритмы типа последовательного назначения для приближенного решения задачи бинарного программирования, изучить основные свойства и исследовать возможные способы повьшения качества этих алгоритмов. Разработать эффективные методы построения нижних оценок оптимума (в задачах на максимум) на базе сформулированных общих алгоритмов;
построить эффективный алгоритм для получения верхних оценок оптимума, лучших, чем оптимум соответствующей (релаксированной) задачи ЛП;
реализовать все основные предложенные алгоритмы в виде комплексов программ и провести вычислительные эксперименты.
Диссертация состоит из трех глав, заключения, списка использованной литературы и приложений.
Первая глава посвящена изложению предлагаемой схемы алгоритма последовательного уменьшения размерности задачи бинарного программирования и исследованию этого алгоритма.
В І.І дан краткий обзор основных способов уменьшения размерности задачи ЦЛП и ЛП. При этом методы, применимые к задачам ЩШ разделяются на две группы: I) относительно простые способы предварительного анализа и переформулирования задачи (видоизменение модели), не требующие вычисления различных оценок с применением ЛП и 2) методы уменьшения размерности задачи более сложного характера, использующие значения оценок, вычисленных с помощью аппарата ЛП.
В 1.2 сформулированы два основных критерия, применяемые для установления оптимальных значений части переменных и устранения избыточных ограничений, в следующих обозначениях. Пусть x*=(X-t ,..\»X»J- оптимальное решение задачи (1)-(4) ( otj = І, j»l,tti)
и F*= m*) ;
F - нижняя оценка Г , причем 3 х , F = F С х) и
X - допустимое решение; F ()(;; = cL) - верхняя оценка оптимума задачи, полученной из ис-ходной добавлением условия Х^ = ь , где оС=0 или 1;
Критерий I. Если
F(Xj=oO < , С*)
то Xt-i-oC , где i = 0 или 1, ^{^.-)^1-
Критерий 2. Если
то ограничение Ук (X) ^ Ък - избыточно, здесь ке{^„.;)и}.
Предложены две различные схемы алгоритма уменьшения размерности, включающие в себя последовательную проверку выполнения условий (*) и () Доказана теорема, показывающая целесообразность применения сначала критерия I, а затем - критерия 2.
В 1.3 приведено пошаговое описание основного алгоритма уменьшения размерности задачи бинарного программирования (алгоритм ПУРЗ). Предложены некоторые уточнения процесса проверки условия (х) при использовании аппарата ЛП для вычисления F(X:=oC).
Описаны детали алгоритма: последовательность выполнения основных процедур, обоснованность повторного применения, критерий останова, добавление правильных отсечений, возможность получения приближенного решения и др.
Детальному описанию схемы вычислительной реализации всех основных процедурных частей алгоритма ПУРЗ посвящен следующий 1.4.
15 Ь этом разделе приводятся отдельные алгоритмы, реализующие процедуры: получение симплекс-таблицы, соответствующей допустимому зешению х (исходя из этой таблицы, затем вычисляется оптималь-юе решение релаксированной задачи -X ); проверка условия (к) уія дробных координат к ; проверка условия (к) для целочислен-шх координат к ; повторная проверка условия (к) в случаях улуч-іения нижней оценки f ; удаление избыточных ограничений (с соот-ютствующим изменением симплекс-таблицы).
В отличие от известных вычислительных алгоритмов, связанных \ применением критерия I, где проверка условия (к) для каждой пе-геменной сводится к решению отдельной задачи ЛП, в алгоритме ПУРЗ юе вычисления проводятся систематическим использованием текущей іптимальной симплекс-таблицы, без привлечения данных исходной за-іачи. Трудности, возникающие при построении наиболее рациональных ;хем реализации отдельных этапов алгоритма ПУРЗ, удается преодо-[еть, используя аппарат симплекс-метода и теории двойственности П.
Результаты вычислительных экспериментов, проведенных с алгорит-[ом ПУРЗ, изложены в 1.5.
Эффективность алгоритма ПУРЗ в значительной степени зависит т качества периодически вычисляемых верхних и нижних оценок -f CX: = oL) и , от их близости к своим, соответственно, нижним верхним пределам. Вопросам вычисления эффективных нижних и верх-их оценок посвящены, соответственно, главы 2 и 3.
Основным способом порождения качественных нижних оценок оп-имума целевой функции задачи бинарного программирования в главе избрано приближенное решение этой задачи.
В первой части 2.1 рассмотрены основные типы методов приб-иженного решения. В конце раздела предлагается алгоритм решения
задачи бинарной оптимизации, основанный на применении эквивалентных гиперсфер, начальные этапы которого могут быть использованы для получения допустимых решений задачи бинарной оптимизации. Алгоритм запрограммирован - приведены результаты вычислительного эксперимента.
В 2.2 с единой точки зрения описаны общие алгоритмы метода последовательного назначения единиц (алгоритм ПОСНЕД) и двойственного двухэтапного метода последовательного назначения нулей (алгоритм ПОСНУЛ), имеющих эвристический характер и предназначенных для построения приближенного решения задачи бинарного программирования с неотрицательными коэффициентами- многомерной задачи о ранце. Оценена трудоемкость этих алгоритмов, выявлены некоторые их свойства. Предложен новый алгоритм - П0СНУЛІ - последовательного назначения нулей, вычислена его трудоемкость. Сравнены трудоемкости алгоритмов ПОСНЕД и ПОСНУЛ (на примере конкретных их вариантов) в зависимости от количества единиц в построенных приближенных решениях.
2.3 посвящен описанию различных подходов, направленных на улучшение имеющегося приближенного решения. Основной принцип следующий: получить серию приближенных решений неоднократным применением одного и того же алгоритма к незначительно измененной исходной задаче.
В 2.4 алгоритмы ПОСНЕД и ПОСНУЛ обобщены на случай многомерной задачи о ранце с ограниченными переменными и на случай задачи с ограничениями группового выбора. Также описаны способы обобщения и применения к этим задачам тех подходов, которые были рассмотрены в 2.3.
Три конкретные реализации алгоритма ПОСНЕД и алгоритм ПОСНУЛЬ-а также два метода улучшения допустимого решения реализованы в сое-
I?
таве ІЇЇШ РАНЕЦ-І для приближенного решения многомерной задачи о ранце. О назначении и структуре этого пакета сообщается в 2.5.
Результаты обширного вычислительного эксперемента, проведенного, в основном, с использованием ППП РАНЕЦ-І, нашли свое отражение в 2.6.
Как уже было отмечено, третья глава посвящена вопросу построения верхних оценок оптимального значения целевой функции задачи бинарного программирования.
В 3.1 приведен обзор некоторых результатов, имеющихся в целочисленном линейном программировании, которые могут быть использованы для получения верхних оценок оптимума, в т.ч. лучших, чем решение релаксированной задачи. В конце раздела сформулированы два новых результата, один из которых связан с уменьшением коэффициентов линейного неравенства с переменными 0 и I (что приводит к усилению этого неравенства), а второй - с вычислением верхних оценок оптимума, строго лучших, чем оптимум непрерывной релаксации, посредством решения некоторого конечного числа задач ЛП.
В первой части 3.2 пояснена идея метода обхода вершин многогранника ограничений (МО) задачи бинарного программирования,заключающейся в целенаправленном просмотре части вершин МО, начиная с вершины X , двигаясь по вершинам в направлении убывания -Р(х) и останавливаясь при достижении первой же целочисленной вершины -оптимального решения X . Далее описан основной алгоритм метода -алгоритм ОБХОД и доказана теорема о правильности алгоритма и конечности поиска. Как основное приложение изложено получение верхней оценки оптимума с применением аппарата алгоритма ОБХОД. Рассмотрены другие возможные применения этого алгоритма.
Решению всех задач, связанных с вычислительной реализацией отдельных шагов алгоритма ОБХОД, посвящен 3.3. Здесь в виде отдельных детальных алгоритмов изложены основные процедуры алгоритма ОБХОД.
Результаты вычислительного эксперимента с алгоритмом ОБХОД приводятся в 3.4. Вычисления проводились по генерируемым тестовым задачам как по решению задач, так и по вычислению верхних оценок оптимума.
В заключении кратко изложены основные результаты исследования.
В приложения к работе включены: описание языка изложения алгоритмов, систематически используемого в работе; описание комплексов программ, реализующих алгоритмы ПУРЗ и ОБХОД; акты и справки о внедрении и использовании программ.
Теоретической основой исследований по теме диссертации явились современные достижения в области теории математического программирования, в частности, в дискретном программировании. В работе использован аппарат линейной алгебры, теории двойственности ЛП, многих современных точных и приближенных методов решения задачи ЦЛП, применены методы построения и анализа комбинаторных вычислительных алгоритмов, геометрическая интерпретация как самих задач ЛП и ЦЛП, так и методов их решения.
Все разработанные алгоритмы написаны на специальном алголопо-добном языке изложения алгоритмов, описание которого приводится в приложении I. Для большинства из этих алгоритмов обоснована их правильность и приведен анализ их вычислительной трудоемкости. Программная реализация алгоритмов произведена с использованием методов нисходящего проектирования структурных программ и методов создания пакетов прикладных программ. Эффективность большинства построенных алгоритмов различного назначения исследуется путем решения на ЭВМ серии тестовых задач и анализа результатов вычислений.
Описанные в диссертации алгоритмы и составленные на их осно-
ве программы нашли разнообразные приложения.
Программа решения задачи квадратичного программирования (КП) практической версией метода Била, которая входит составной частью в комплекс программ для решения задачи бинарного программирования с применением эквивалентных гиперсфер( 2.1), принята в ГосШ СССР (Программа № П003856).
Пакет прикладных программ РАНЕЦ-I ( 2.5), предназначенный для приближенного решения многомерной задачи о ранце принят в ГосШІ (Программа № 007833).
Программы, составленные автором на основе разработанных в диссертации алгоритмов точного и приближенного решения задачи ЦЛП, внедрены и используются в течении нескольких лет в следующих организациях:
В РИВЦ Минздрава Азерб.ССР для решения задачи "Расчет индивидуализированной инфузионной терапии" в АСУ Центром реанимации в Республиканской клинической больнице;
На Бакинском заводе бытовых кондиционеров для решения различных оптимизационных задач;
В КИВЦ ВПО "Каспморнефтегазпром" для решения задач: "Определение максимального отбора нефти с месторождения и распределения дебитов скважин с учетом обводненности продукции при заданной суммарной закачке воды" и "Определение минимальной закачки воды и распределение дебитов по нагнетательным эксплуатационным скважинам при заданном планируемом объеме добычи нефти";
- В тресте Геокчаймелиоводстрой для оптимального выбора перечня
строительных работ на очередной плановый период при наличии ог
раниченных материальных и трудовых ресурсов. Годовой экономичес
кий эффект от внедрения составил 27 тыс.рублей.
Применение результатов подтверждено соответствующими актами и справками.
Основное содержание диссертационной работы освещено в работах [з,5,6,7,8,9,10,II,12,19] .
Результаты, нашедшие отражение в диссертации, докладывались на конференции молодых ученых Института кибернетики АН Азерб.ССР (Баку, 1979г.), на УІ и УП Всесоюзных симпозиумах по системам программного обеспечения решения задач оптимального планирования (Пу-щино, 1980г.; Нарва-Йыэссу, 1982г.), на Всесоюзной школе-семинаре по математическим методам оптимизации и их приложениям в больших экономических и технических системах (Баку, 1980г.), на У совместных расширенных заседаниях научно-исследовательских семинаров Южного научного центра АН УССР и Кишиневского ТУ по дискретной математике, графам, гиперграфам и алгебраическим системам (Одесса, 1981г), на I Республиканской конференции молодых ученых по прикладной математике и кибернетике (Баку, 1981г.), на ІУ Республиканской конференции молодых ученых по математике и механике (Баку, 1982г.),а также в течение ряда лет на различных семинарах в Институте кибернетики АН Азерб.ССР.
Уменьшение количества переменных и ограничений в задаче бинарного программирования
Тогда БЛ= упоос Л)0 й)г является верхней оценкой оптимума задачи (I.I.4), причем вг4 \ . В [I27J приводятся некоторые другие способы вычисления верхних оценок, сравнимых по величине с й,. Там же описана процедура уменьшения числа переменных с использованием значений верхних оценок внутри схемы алгоритма уменьшения из [l20].
В последнее время предложен [24,25,98] новый перспективный подход к точному и быстрому решению почти всех задач ЦШ1 одного относительно широкого, но частного класса задач с большим числом бинарных переменных и малым числом ограничений с натуральными коэффициентами. При этом предполагается, что разброс значений коэффициентов и правых частей ограничен.
Ощутимый выигрыш в объеме вычислений в этих подходах по сравнению с ранее известными методами достигается за счет использования идеи выделения ядра задачи и области устойчивости. При приня тых допущениях относительно задачи, методы аналитической теории чисел позволяют ([24]) почти всегда отделить несущественные составляющие решения задачи от составляющих, которые могут оказаться существенными и войти в ядро задачи. Несущественные переменные принимают одни и те же значения как на оптимальном решении задачи, так и в окрестности оптимума и эти их значения обычно устанавливаются применением описанных выше способов.
В предлагаются геометрически прозрачные способы выявления избыточных ограничений и установления оптимальных значений части переменных задачи БП с использованием эквивалентных гиперсфер.
В предложены критерии избыточности линейных ограничений -неравенств. В основе получения этих критериев лежит использование оценочной задачи, двойственной по отношению к одномерной задаче о ранце и идей гиперсферического программирования [ 16,105] .
Некоторые способы выявления избыточных ограничений и переменных, которые в оптимальном решении принимают нулевое значение, предложены в работе [133 ] . При этом основным инструментом является анализ отдельных строк таблицы Таккера, в ходе решения задачи методом отсечения.
Уменьшение количества переменных и ограничений в задаче бинарного программирования I. Рассмотрим задачу целочисленного линейного программирования Максимизировать 21 \ 1 Н при ограничениях O0-g суи« «t, UfHV-.,4 І (І#2Л) X-. - целые
Для решения этой задачи имеется ряд методов, наиболее эффективными из которых являются различные модификации метода ветвей и границ [52] , в том числе методы неявного перебора [54] . Однако даже этими методами практическое решение задачи с іь и т. порядка 50-100 может затребовать огромных вычислительных затрат. Методы решения задачи (І.2.І) наиболее болезненно реагируют на рост числа переменных. Во всех случаях увеличение количества ограничений также приводит к росту требуемого объема вычислений. Поэтому понижение размерности задачи (1.2,1) как перед ее решением конкретным методом, так и в процессе решения может существенно уменьшить вычислительные затраты. Примем следующие обозначения: Ху - значение неизвестного X, в оптимальном решении задачи (1.2.I); Г - оптимальное значение целевой функции задачи (І.2.І); F - нижняя оценка для т , а X - такое допустимое решение задачи (1.2 Д), что F-Z C-; . ; F (X- = oi ) F(.Xj=c ) соответственно, оптимальное значение целевой функции задачи (І.2Д) и оценка сверху для него при дополнительном условии Х-= , где об = 0 или I; о )={x(x4,...,)cJljuCx) 6; LeM, x.=0Vl, je/V}; ={x g K leMNUJ OVi, /єA/}; (1.2.2) к={х (х) к, = оуі, /еЛ/}. (I-2-3) В настоящей работе для установления оптимальных значений неизвестных задачи (I.2.I) будем пользоваться следующим достаточным условием, которое, следуя [18] , приведем в виде теоремы.
О вычислительной реализации алгоритма ПУРЗ
В результате работы алгоритма ГЕНТАБ вырабатывается симплекс-таблица, базис которого является допустимым и соответствует решению X
Доказательство: Для доказательства достаточно заметить, что, как известно [38,94] , каждое симплекс-преобразование (симплекс-итерация) переводит один базис в другой и, что в результате рабо-ты алгоритма все единичные координаты решения X окажутся в базисе с тем же значением, а нулевые - вне базиса. С другой стороны, т.к. решение X допустимо для задачи (I.2.I), то можно указать такие значения дополнительных переменных, что вместе с этими переменными координаты решения X будут составлять допустимое решение задачи (I.4.I). Именно эти значения и принимают дополнительные переменные по завершении работы алгоритма ГЕНТАБ. Таким образом, результирующая симплекс-таблица допустима и значения переменных х- , і = 1, и-, в этой таблице совпадают со значениями координат решения .
Полученная в результате работы алгоритма ГЕНТАБ симплекс-таблица является прямо-допустимой [94] и поэтому выбрав ее базис в качестве начальной, можно вычислить решение задачи ЛП I.4.I X обычным симплекс-методом.
Проверка условия 1.2.4 для дробных координат Xх Отметим, что перед каждым очередным выполнением шага 4 в алгоритме ПУРЗ мы имеем оптимальную симплекс-таблицу, соответствующую текущему решению X . Обозначим эту таблицу через Пусть очередной проверяемой дробной координатой на шаге 4 является X . Для вычисления верхней оценки гЫд= ) di-0 или I, предлагается алгоритм ФИКСДРОБ, сущность которого заключается в следующем: посредством одной двойственной симплекс-итерации перейти к такому базису, где X =о и исходя из этого базиса, двойственным симплекс-методом получить оптимальную симплекс-таблицу, сохраняя Х об .
АЛГОРИТМ ФИКСДРОБ (Фиксирование ДРОБной координаты Х " для проверки условия (1.2.4)). Входные данные: симплекс-таблица Ю с элементами a.. , i= itm J ,ni , д, - номер проверяемой переменной, конкретное значение о , обвили I, при котором следует фиксировать х . Выходом является значение верхней оценки ЛЯг=о0 для текущей остаточной задачи и соответствующая оптимальная симплекс-таблица .
Установить номера строк симплекс-таблицы Ю , соответствующие базисным переменным Х И X. Обозначим номера этих строк через 14 и 13 соответственно. Шаг 2.[оН?] Ц d= U&t stt (замена значений lj и і друг на друга). Шаг 3. [Предварительное устранение строки с номером iz переставленном некоторых строк таблицы 2)] 4. Set шгц - ггц-і. Шаг 5. Выбрать строку с номером ц в качестве ведущей в двойственном симплекс-методе и найти номер ведущего столбца - к : Шаг б. Провести двойственное симплекс-преобразование таблицы 2)с ведущим элементом а-,. . Шаг 7. [ Устранение столбца с номером L перемещением последнего столбца F і. - і to угц Oo шаг 7.1 ? . Шаг 7.1. Sei cL, - . Шаг 8. $гі уц - кц- {. [Решение задачи лп] Применить двойственный симплекс-метод решения задачи ЛП, выбрав в качестве начальной текущую двойственно-допустимую таблицу 2)\ STOP Заметим, что в алгоритме ФИКСДРОБ на шаге 3 предположено, что і ФЩ-і . Если окажется, что і щ-і , то перед выполнением шага 3 необходимо произвести замену значения на значение 4 : h Если на шаге 5 окажется, что cL. 0 для всех 1-1 или выявится неограниченность двойственной задачи на шаге 9, то это означает отсутствие допустимых решений соответствующей прямой задачи
Методы типа последовательного назначения для приближенного решения задачи бинарного программирова ния с неотрицательными коэффициентами
Затем выбирается следующая переменная для назначения единицы и т.д. В тех случаях, когда назначение выбранной переменной значения единица приводит к нарушению каких-то ограничений задачи (2.2.1), этой переменной назначается значение, равное нулю. В обоих случаях соответствующая переменная устраняется из дальнейшего рассмотрения, число переменных уменьшается на единицу, а в случае назначения единицы пересчитываются и правые стороны ограничений - -fy , i At . Процесс повторяется до просмотра всех П/ переменных. Приведем в общем виде алгоритм метода последовательного назначения единиц.
Алгоритм поснед (Последовательное Назначение Единиц). Построение допустимого решения задачи (2.2.1). На входе задаются п, ,m- , матрица 11&ЦЦ , & , С- (ієМ,ієГО, а выходом является множество Jv , содержащее номера единичных координат построенного допустимого решения. Шаг І. { Инициализация множеств ] Set N - { множество номеров переменных j ; М " {множество номеров ограничений ; Шаг 2. Выбрать индекс Le N очередной переменной, которой следует назначить значение единицы. Шаг 3. [Проверка допустимости и пересчет 6L а.. Ыииъ set J, - J4 U {} }; амА, с VL(LM set 4 -4- 4і Шаг 4. [Уменьшить число переменных Ц N = 0 theft STOP (все переменные просмотрены, построение допустимого решения завершено) в&в- сиЯо шаг Zjl% Нетрудно видеть, что в процессе работы алгоритма ПОСНЕД будут последовательно просмотрены все к, переменных задачи (2.2.1) и в результате будет получено допустимое решение посредством множест ва номеров переменных, которые принимают в этом решении значение единицы.
Определение 2.2.1. Будем говорить, что допустимое решение задачи (2.2.1) обладает свойством недополняемости, если в результате замены любой нулевой координаты на единицу допустимость этого решения нарушается.
Проверка, проводимая на шаге 3 алгоритма ПОСНВД, гарантирует, что построенное решение будет обладать свойством недополняемости.
Сформулируем указанные свойства алгоритма ПОСНЕЩ в виде следующих утверждений: Утверждение 2.2.1. Пусть - множество, полученное на выходе алгоритма ПОСНВД. Тогда решение X = ( Х ,...,3 ), где х. = і , если je Д, и х. = 0 , если je [,, , является допустимым для задачи (2.2.1). Утверждение 2.2.2. Пусть СҐ0=1\/\С . Тогда для Уке Т0 , зим , такое, что _, сЬд. + &к
Выясним порядок максимально потребных арифметических и логических операций, а также операций присваивания для выполнения алгоритма ПОСНЕД. Предположим, что выполнение шага 2 требует 0( ( , к,))операций. Тогда для выполнения шага 2 в течение работы алгоритма потребуется 0( ( , ,))== ОСкі/УСПЧН)) операций. В ходе работы алгоритма шаги 3 и 4 также выполняются Уь раз. Всего на шаге 3 для выполнения проверок . & будет проведено сравнений, а для выполнения Ь ъ -СЬ-- самое большее Уп(п-1) вычитаний и столько же присваиваний (т.к. / / уь-1 ). Операция добавления в множество ( одного нового элемента ( J, Я 17 {\Л ) программно может быть реализована выполнением одной операции присваивания. Всего таких присваиваний может быть выполнено не более к,-і раз. Аналогично, выполнение шага 4 потребует всего к операций присваивания и \ъ операций сравнения.
Таким образом, получаем следующее выражение для оценки макси мально потребного количества операций при выполнении алгоритма ПОСВД: л , п ч n, N Л , . N +(w/-i) +с2к = 0(K. (VYU, VU)) -Ь 3vn,kb -Лпь- і. (2.2.3) Как видно, трудоемкость алгоритма ПОСНЕД в основном зависит от значения величины (W h/). Для различных конкретных реализаций алгоритма ПОСНЕД [ 17,2,125,139] 0(и, У(пг,к,)) = ОСтЛъ2).
Другим способом построения допустимого решения задачи (2.2.1) является метод последовательного назначения нулей. Отправной точкой в этом случае является заведомо недопустимое решение X =(1,...) 1) (см.условие 4) в (2.2.2)). Этот метод состоит из двух этапов. На первом этапе определенным способом последовательно выбираются координаты решения х , которым назначаются значения, равные нулю. Это продолжается до получения первого допустимого ре z шения - X . На втором этапе к задаче, получившейся из исходной задачи (2.2.1) фиксированием единичных компонент решения х при значении, равном I, применяется метод последовательного назначения единиц. Объединением результатов первого и второго этапов получается окончательное допустимое решение.Приведем общую схему алгоритма,
Метод обхода вершин многогранника ограничений задачи бинарной оптимизации
В [31,62,72] предложены методы построения верхней оценки оптимума задачи (I.2.I), которые фактически являются приближенным методами решения задачи ЛП и существенно используют специфику задачи CI.2.I).
Возможность использования правильных отсечений для улучшения верхней оценки была уже нами рассмотрена в гл.1 настоящей работы. Идея усиления оценок с использованием алгоритма отсечения "внутри" метода ветвей и границ ("гибридная" схема) была одновременно и независимо Ссм.[5і] ) опубликована в [88] и [119], причем в последней также освещена первая вычислительная реализация.
Налее мы рассмотрим некоторые результаты, применимые для вычисления улучшенных верхних оценок. Использование функции Лагранжа
Как известно, для задачи математического программирования fr = ггиуь { fa) I g(X) l7 хбХ]. (3.1.4) функция Лагранжа имеет следующий вид: L(X,A) jW + ACo-JOO). Задача ІГИ П/ГПА L(X,A) эквивалентна задаче (3.1.4) для лю-бых і (х) и о (к) . Изменение порядка уплп. и мая приводит к двойственной задаче Кг = УУЮУХ [ У(\) \Х 0], У(А)-Кгшг{Цх,Х)кХ}. (3.1.5)
При этом всегда выполняется условие. Для задач выпуклого (в т.ч. линейного) программирования при определенных условиях регулярности имеем Ь Уг . Для невыпуклых (в т.ч. дискретных) задач может оказаться &
В дискретном программировании двойственная задача (3.1.5) может быть использована для получения нижних оценок (а в задачах на максимум - верхних оценок) в различных методах переборного типа [58,59,138] .
Однако при большом числе переменных и ограничений задачи ЦЛП использование такого подхода становится трудоемким в части пересчета обобщенных множителей Лагранжа при многократном вычислении оценок.
Использование методов двойственного характера I. Как уже указывалось, метод построения последовательности планов (решений), рассмотренный в [40,41,43] , может быть использован для получения верхней оценки оптимума целевой функции для задачи дискретного программирования в следующей постановке: найти такой элемент р конечного множества Р , на котором достигается максимум функции Г(Х) , определенной на этом множестве F(p ) = таж FCx). (3.1.6) Метод построения последовательности планов применим к решению этой задачи, если 1) можно найти конечное расширение R. множества Р , R P и функцию Ь((Х) , определенную на R- и являющейся мажорантой функции FCx) , т.е. й(х) Г(Ю для xeR. ; 2) можно построить алгоритм У , который на к-м шаге (к= 1, ,-0 находит элемент ZK.(L , обладающий свойством Q(2 J= YYum (AC ), ЮІ,где =R, RK= RK-Л И U=.2,3,...).
Критерий оптимальности формулируется следующим образом: если существует такое натуральное число к , что Рк = {г0 ,... «} ПР 0 (3.1.7) Х: Р. то ьк - оптимальное решение задачи (3.1.6).
Сущность метода Y построения последовательности планов сое 115 тоит в следующем: на к -ом шаге с помощью алгоритма У находится элемент ZK , а также множество Рк . Если Рк = 0 , то переходим к (К+І) - му шагу. Если Рк # , то проверяем, выполняется ли условие (3.1.7). Если да, то процесс завершается и рк - оптимальный план задачи. Если нет, то переходим к следующему шагу. Теорема [43]. Пусть на К. -м шаге работы метода У Рк а условие (3.1.7) не выполняется. Тогда fCpK) f(p ) 0.().
Теорема подтверждает возможность использования метода построения последовательности планов для вычисления верхних оценок задачи дискретного программирования на максимум.
Другой метод двойственного характера, идейно близкий методу построения последовательности планов, предложен в работе [ i] . Схему метода опишем применительно к задаче Ш.
По заданной задаче Ш строится задача с одним ограничением, множество допустимых решений которой содержит Ъ - множество допустимых решений заданной задачи (І.2.І). Если оптимальное решение построенной задачи принадлежит множеству Я) , то оно также является оптимальным решением исходной задачи. В противном случае строится новая задача с одним ограничением, множество допустимых решений которой также содержит множество 2) » но не содержит оптимального решения предыдущей задачи с одним ограничением. Если оптимальное решение новой построенной задачи принадлежит множеству ), то оно является оптимальным решением исходной задачи. Иначе - строится следующая задача с одним ограничением аналогично последней и т.д. Множество допустимых решений каждой новой задачи с одним ограничением содержит множество Ъ и при выполнении определенных условий, не содержит оптимального решения ранее построенных задач с одним ограничением.
