Для связи в whatsapp +905441085890

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

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

Рассмотрим следующую задачу линейного программирования: максимизировать

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

при условии

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

Заметим, что Целочисленное линейное программирование — слабые переменные, а Целочисленное линейное программирование — исходные переменные задачи (2.5). Если наряду с ограничениями (2.5) потребовать, чтобы все Целочисленное линейное программирование были целыми, то задача будет называться задачей целочисленного программирования. Существует большое число задач, особенно комбинаторных, которые можно сформулировать как задачи целочисленного программирования.

Ограничения (2.5) определяют выпуклую область Целочисленное линейное программирование в Целочисленное линейное программирование-мерном пространстве, как показано на рис. 2.6. Узлы целочисленной решетки на рис. 2.6 изображены точками. Такие точки, расположенные внутри области Целочисленное линейное программирование, являются допустимыми решениями задачи целочисленного программирования. Оптимальные решения задачи линейного программирования всегда располагаются на границе области решений. В данном случае граничные точки не являются даже допустимыми решениями, поскольку ни одна из них не целочисленна.

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

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

Действительно, если к задаче линейного программирования, определяющей допустимую область Целочисленное линейное программирование, добавить ограничение типа Целочисленное линейное программирование, как показано на рис. 2.6, то для вновь полученной задачи Целочисленное линейное программирование будет областью допустимых решений. Такая область обладает двумя важными свойствами: 1) содержит все допустимые целочисленные точки исходной задачи линейного программирования (поскольку является выпуклой оболочкой этих точек); 2) все крайние точки новой области — целочисленны. Поэтому любое базисное оптимальное решение модифицированной задачи линейного программирования имеет своими компонентами целые числа и является оптимальным решением исходной задачи целочисленного программирования.

Как только будут введены дополнительные ограничения, можно решать модифицированную задачу линейного программирования любым обычным методом, и полученное базисное оптимальное решение автоматически будет целочисленным. Представленный ниже целочисленный алгоритм обладает следующими свойствами: 1) все дополнительные ограничения сохраняют допустимые точки исходной целочисленной задачи; 2) за конечное число шагов создается достаточное число дополнительных ограничений для того, чтобы оптимальное решение модифицированной задачи было целочисленным; 3) дополнительные ограничения (гиперплоскости) проходят по крайней мере через одну целочисленную точку, хотя и не обязательно находящуюся внутри выпуклой оболочки; 4) каждое новое ограничение сокращает область допустимых решений исходной задачи целочисленного программирования.

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

Задачу целочисленного программирования также можно записать в виде табл. 2.14.

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

Обычно в ограничения задачи (2.5) включают тривиальные соотношения

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

Причины представления переменных в виде

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

чисто исторические, но это стало практикой в целочисленном программировании. Будем использовать

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

для обозначения Целочисленное линейное программирование-го столбца те кущей таблицы и

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

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

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

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

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

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

Каждый раз после проведения итерации симплекс-метода происходит изменение множества небазисных переменных. Изменяется и таблица. Будем использовать Целочисленное линейное программирование для обозначения Целочисленное линейное программирование-таблицы. Изложим сам алгоритм.

Шаг 1. Решить задачу целочисленного программирования как задачу линейного программирования с помощью прямого или двойственного симплекс-метода. Если получено оптимальное решение задачи линейного программирования, то

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

Шаг 2. Если Целочисленное линейное программирование — все целые, то задача решена и решение получено без использования дополнительных ограничений. В противном случае пусть Целочисленное линейное программирование — первая нецелочисленная компонента в Целочисленное линейное программирование. Тогда Целочисленное линейное программирование-я строка называется производящей. Записать внизу таблицы уравнение, используя данные производящей строки:

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

где

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

ближайшее к числу целое.

Переменную 5 называют слабой переменной Гомори, а уравнение (2.6) — отсечением Гомори. Проделать шаг (двойственного) симплекс-метода, использовав в качестве ведущей строки отсечение Гомори (2.6). При этом таблица останется двойственно допустимой. Повторять до тех пор, пока все Целочисленное линейное программирование не станут целыми неотрицательными. Если Целочисленное линейное программирование на некотором шаге остается отрицательным, следующий шаг (двойственного) симплекс-метода производится без введения отсечения Гомори. (Если Целочисленное линейное программирование становится отрицательным, нулевую строку не выбирают в качестве производящей. Если Целочисленное линейное программирование становится нецелым, следует выбрать нулевую строку в качестве производящей.)

В приведенном ниже числовом примере все дополнительные ограничения сохраняются на протяжении вычислений.

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

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

Пример:

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

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

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

при условиях

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

Вводя слабые переменные Целочисленное линейное программирование получаем:

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

Решаем задачу линейного программирования (ведущий элемент отмечен):

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

Получено оптимальное решение задачи линейного программирования:

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

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

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

Отсюда находим оптимальное целочисленное решение:

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

Выразив Целочисленное линейное программирование через исходные небазисные переменные Целочисленное линейное программированиеЦелочисленное линейное программирование и Целочисленное линейное программирование, получим неравенство Целочисленное линейное программирование целыми коэффициентами:

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

или Целочисленное линейное программирование Чтобы получить матрицу, полностью целочисленную, просто продолжим введение отсечений:

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

Эта теория взята со страницы лекций по предмету «математическое программирование»:

Предмет математическое программирование

Возможно эти страницы вам будут полезны:

Задача о перевозках с перегрузкой в математическом программировании
Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям
Постановка задачи об оптимальном раскрое материалов (о минимизации отходов)
Задача о наилучшем использовании посевной площади