книги / Математические методы принятия решений

3)дополнительные ограничения (гиперплоскости) проходят по крайней мере через одну целочисленную точку, хотя и не обязатель­ но находящуюся внутри выпуклой оболочки;

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

Заметим, что оптимальное решение исходной задачи может быть получено прежде, чем допустимая область будет сокраще­ на до области O EF G H . Оптимальное целочисленное решение определяется пересечением п гиперплоскостей, что обеспечивается процедурой отсечения; некоторые гиперплоскости могут соответ­ ствовать ограничениям исходной задачи.

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

Обычно в ограничения задачи (2.9) включают тривиальные соотношения Xj = —(—Xj), j = 1,2, ... , п. Запись переменных в ви­

чать j -й столбец текущей таблицы и через ay , i = 0 ,1 , ... , п + тп, j = 0 ,1 , ... , п, — элемент г-й строки и j-ro столбца таблицы. Пред­ полагается, что все a,ij в исходной таблице целые. Следовательно, все слабые переменные х п+\ , ..., хп+гп должны быть также неот­ рицательными целыми числами.

Сначала задачу целочисленного программирования рассматри­ вают как задачу ЛП и решают ее с помощью прямого или двой­ ственного симплекс-метода. Используя двойственный симплексметод (см. § 2.5), в первую очередь получают переменную, которую исключают из базиса. Она определяется наибольшим по модулю

отрицательным элементом столбца сводных членов, поэтому не на­ до решать вспомогательную задачу ЛП. Чтобы определить пере­ менную, вводимую в базис, рассматривают отношение элементов строки для целевой функции и соответствующих отрицательных элементов разрешающей строки. Наименьшее по значению отно­ шение (в задаче максимизации) определяет переменную, вводи­ мую в базис. Операция замещения проводится методом Жордана. В конце алгоритма получаем а,о ^ 0, г = 1,2,..., п + т, и aoj^O , j = 1,2,..., п. Если Oio^O целые для всех г, то найдено опти­ мальное решение целочисленной задачи. В этом случае решение получается сразу, без использования ограничений целочисленности. Если элементы а*о ^ 0, но они не все целые, то к ограничениям (2.9) добавляют еще одно. Новое ограничение записывают внизу табли­ цы так, чтобы задача перестала быть прямо допустимой, т. е. а»о < 0 для г = п + т + 1. Затем используют двойственный симплекс-ме­ тод, чтобы получить все що ^ 0. Если що являются нецелыми, в таблицу добавляют новые ограничения до тех пор, пока все йго^О, i = 1,2, ... , п + т, станут целыми и по-прежнему неотри­ цательными.

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

Каждый раз после проведения итерации симплекс-метода про­ исходит изменение множества небазисных переменных. Изменяется и таблица.

Приведем алгоритм решения задачи целочисленного програм­ мирования.

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

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

Х 2 + 2 Хз ~ 2 Х 4 = 2 ‘

Дополнительное ограничение (2.10) в данном случае будет иметь следующий вид:

/ 0 ) ® 2 + / ( у ) * 3 + / ( - у ) * 4 ^ / ( у )

Переменную s называют слабой переменной Гоморщ а уравне­ ние (2.10) —отсечением Гомори. Выполнить одну итерацию (двой­ ственного) симплекс-метода, используя в качестве ведущей строки

отсечение Гомори (2.10). При этом таблица останется двойственно допустимой. Повторять шаг 2 до тех пор, пока все ÛÎO, г = 1,2,...

..., п + т, не станут целыми неотрицательными. Если що на неко­ тором шаге остаются отрицательными, следующий шаг (двойствен­ ного) симплекс-метода производится без введения отсечения Гомо­ ри. (Если элемент ооо становится отрицательным, нулевую строку не выбирают в качестве производящей. Если а<ю становится неце­ лым, следует выбрать нулевую строку в качестве производящей.)

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

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

Приведем пример, иллюстрирующий изложенный алгоритм. Пример. Рассмотрим задачу целочисленного программирова­

ния: максимизировать функцию

/(ж) = Лх\ + 5X2 + жз

при условиях

Зж] + 2жг < 10,

Ж1 + 4 Ж 2 ^ И ,

ЗЖ1+ ЗЖ2 + Жз ^ 13,

жь жг, жз ^ 0 (целые).

Вводя слабые переменные хц, xs, Хб, получаем значения, запи­ санные в табл. 2.18.

Решая задачу линейного программирования (ведущий элемент отмечен), получаем новые значения, записанные в табл. 2.19-2.21.

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

целочисленное решение (табл. 2.22).

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

2, Х2 —2, Ж3 —1, fm a x ix ) —19.

Таблица 2.23

Введение отсечения з2

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

3

где уij определеняются из следующих соотношений:

Таблица 2.24

Полностью целочисленная матрица

1) для Xjy которые могут принимать целочисленные значения, имеем

2) для Xj, которые могут принимать только целочисленные зна­ чения, имеем

Напомним, что /(а у ) = ay —[ay]; здесь [ay] — ближайшее к ayцелое.

§ 2.9. Задача о назначениях (проблема выбора)

Рассмотрим задачу о распределении механизмов (работников) для выполнения п конкретных действий (заданий) таким образом, чтобы каждый механизм выполнял только одно действие и чтобы при заданной производительности каждого механизма на каждом задании суммарный эффект был максимальным.

Обозначим через су, г, j = 1,2, ... ,п , производительность г-го механизма на j - й работе. Тогда данная задача, известная под на­ званием задачи о назначениях, будет заключаться в таком выборе

Обозначим, как рекомендовалось выше, через Xÿ переменную, равную единице, если механизм А{ назначен на работу B j, и рав­ ную нулю, если механизм Ai не назначен на работу Bj. Тогда сум­ марная производительность механизмов описывается функцией

/ ( х ) = Х\\ + 2х \2 + 3X13 + 2X21 + 4X22 + £23 + З х з 1 + Х32 + 5хзз

при условиях-ограничениях

Хп +Х12 +Х13 = 1, Я21 +Х22 +Х23 = 1,

£ 3 1 + а ^ 3 2 + S 3 3 = 1,

Х п + Х 2 1 + Х 3 1 = 1 ,

Х12 +Х22 +^32 = 1, Х13 + Х23 + Хзз = 1.

Необходимо найти максимум функции / ( х ) при этих ограниче­ ниях.

Запишем условия задачи в виде табл. 2.25, в которой проведем выделение базисных переменных.

Таблица 2.25

Исходная таблица

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

не получено.

Используя метод исключения Жордана (разрешающий элемент —1 отмечен), получим значения, записанные в табл. 2.27.