Какие методы решения задач целочисленного программирования

3.3. Целочисленное программирование

3.3.1. Особенности задач целочисленного программирования

Математическая формулировка задач целочисленного программирования аналогична задачам нелинейного программирования:

Однако специфика задач целочисленного программирования заключается в том, что переменные x_j и функции F(х), φ_i(x) могут принимать только дискретные значения. Специальными преобразованиями в подавляющем большинстве случаев можно свести эти дискретные значения к целочисленным.

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

Если все функции F(х), φ_i(x) в задаче (3.10) линейные, то имеет место линейная задача целочисленного программирования. Методы решения таких задач получили наибольшее распространение. Очевидно, что могут встречаться задачи с целочисленными переменными x_j и функциями F(х), φ_i(x) и целочисленными переменными и непрерывными функциями (рис. 3.6). Как правило, именно этот последний случай рассматривается в большинстве руководств. Кроме того, встречаются задачи частично и полностью целочисленные в зависимости от того, часть или все переменные x_j принимают целочисленные значения. Как уже отмечалось, допустимые дискретные значения, входящие во множество, могут быть даже нецелочисленными. В частности, это множество может быть бесконечным, конечным или даже состоящим всего из двух значений: 0 и 1. В этом случае имеет место целочисленное программирование с булевыми переменными, методы которого в значительной мере перекрываются логическим синтезом конечных автоматов.

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

Рис. 3.6. Классификация задач целочисленного программирования

Со значительными оговорками все методы решения задач целочисленного программирования можно разделить на четыре группы (рис. 3.7):

– другие методы, которые нельзя отнести ни к одной из трех первых групп.

Рис. 3.7. Классификация методов решения задач целочисленного программирования

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

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

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

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

Пример. Требуется найти решение следующей задачи целочисленного программирования:

При целочисленности переменных максимум z_опт = 13/5 достигается в точке х_1опт = 3, х_2опт = 2, в то время как при исключении этого требования z_опт = 3 в точке х_1опт = 10/7, х_2опт = 19/7. Округление результата до целых не дает оптимума исходной задачи, как это видно из рис. 3.8. Заметим, что условие целочисленности z при снятии этого требования к переменным х₁ и х₂ определяет оптимум при других значениях х₁ и х₂.

Рис. 3.8. К особенностям задач целочисленного программирования

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

Будем считать, что переменная x_j0 может принимать только одно из заданного множества значений

Введем дополнительные булевы переменные у₁, y₂, . y_p и запишем условие дискретности для x_j0 в виде:

_j0 = k_j0 1 у₁, k j0 ₂y₂, . y_p;

Последнее соотношение требует, чтобы только одна переменная у_v была отлична от нуля. Нетрудно убедиться, что формулы (3.11) обеспечивают дискретность переменной x_j0. Таким образом, путем введения булевых переменных у_v можно всегда свести нецелочисленную дискретную задачу математического программирования к целочисленной. Как видно, соотношения (3.11) представляют собой p-кратную логическую альтернативу:

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

Введем дополнительную булеву переменную y_j0, которую не будем включать в функцию цели, а заменим рассмотренные соотношения следующими:

Очевидно, что соотношения (3.11а) и (3.11б) эквивалентны. Действительно, когда y_j0 = 1, то (3.11б) сводится к x_j0  0 и x_j0 ≤ a; когда y_j0 = 0, то x_j0  b и x_j0 ≤ k_j0. Таким образом, многосвязность области допустимых значений легко учитывается введением дополнительных булевых переменных. Этот метод без труда распространяется на случай многих переменных.

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

Пример. Рассмотрим процедуру сведения задачи невыпуклого программирования к целочисленному программированию. Пусть область допустимых значений задана системой неравенств:

Соответствующая область представлена на рис. 3.9. Первая и вторая пара неравенств образуют выпуклые подобласти x₁, x₂ с учетом неотрицательности переменных с верхними границами x_1макс, x_2макс, соответственно. Введение булевой переменной у приводит к дополнительным неравенствам:

Здесь каждое условие относится ко всем неравенствам соответствующей области.

Рис.3.9. Невыпуклая область, состоящая из выпуклых многогранников

Нетрудно убедиться, что аналогичный способ применим в случае числа переменных, большего двух.

Источник

13.3. Методы решения задачи целочисленного линейного программирования

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

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

Теорема 13.3. Пусть D – многогранник, – множество его целых точек, – выпуклая линейная оболочка множества . Тогда: 1) R – целочисленный многогранник; 2) ; 3) множество опорных планов многогранника R содержится в многограннике , т.е. .

Доказательство. Докажем, что R – целочисленный многогранник. По условию теоремы D – многогранник, т.е. ограниченное множество, поэтому – конечное множество и – выпуклая линейная оболочка конечного множества точек. Следовательно, R тоже многогранник, причем , т.е. многогранник R целочисленный. Обозначим его через . Докажем, что совпадает с . Из определения выпуклой линейной оболочки следует, что .

Покажем, что справедливо также и противоположное неравенство – включение, т.е. . Пусть . Поскольку , . Следовательно, . Но так как произвольный элемент из принадлежит , очевидна справедливость того, что . Из и следует, что .

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

Следствие. Пусть – оптимальный опорный план задачи (R, F). Тогда также является оптимальным планом задачи .

Покажем, что – единственный целочисленный многогранник, для которого множество его целочисленных точек совпадает с .

Теорема 13.4. Пусть D – многогранник, L – целочисленный многогранник и

. (13.8)

Тогда .

Доказательство. Из равенств (13.5) непосредственно следует, что . Покажем, что .

Из целочисленности многогранника L имеем, что . С учетом равенств (13.5) получим . Отсюда , т.е. .

Теорема 13.3 и следствие из нее показывают принципиальную возможность точной линейной аппроксимации целочисленной задачи линейного программирования с помощью задачи линейного программирования ; однако они не дают алгоритма для определения . Кроме того, построение выпуклой линейной оболочки – не менее сложная задача, и в настоящее время неизвестны эффективные алгоритмы ее решения. В 1954 г. Дж. Данциг, С. Джонсон и Д. Фалкерсон высказали идею о том, что построение для задачи можно осуществить поэтапно и решать полученные при этом задачи.

Введем понятие правильного отсечения. Пусть – некоторая задача целочисленного линейного программирования и опорный оптимальный план соответствующей задачи линейного программирования (D, F) не удовлетворяет условию целочисленности

(13.9)

называется правильным отсечением, если оно удовлетворяет условиям:

1) отсечения: не удовлетворяет неравенству (13.9), т.е. ;

2) правильности: любое допустимое решение задачи удовлетворяет неравенству (13.9), т.е. .

Изложим теперь идею метода.

1. Задача решается путем не двухэтапного, а многоэтапного процесса, причем:

а) на r-м этапе решается вспомогательная задача линейного программирования , . Здесь ;

б) множество целых точек – одно и то же для всех многогранников: .

Следовательно, если оптимальный план задачи удовлетворяет условию целочисленности, то он оказывается также и оптимальным планом исходной задачи , и процесс решения задачи завершается;

в) если не удовлетворяет условию целочисленности, то не является планом задачи , т.е. .

2. Переход от r-го этапа к (r + 1)-му этапу, т.е. от задачи к задаче , в случае нецелочисленности осуществляется с помощью правильного отсечения , добавление которого к линейным условиям задачи превращает многогранник в многогранник . Построение дополнительных ограничений и решение возникающей при этом задачи продолжается до тех пор, пока не получится целочисленное решение или не убедимся в неразрешимости задачи. Однако при этом возникают вопросы: как строить ограничения задачи и обеспечить конечность процесса? Ответ на этот вопрос был впервые получен Р. Гомори, который предложил алгоритм решения полностью и частично целочисленных задач.

Источник