 |
 |
 |
 |
|
 |
 |
79
далеко в вычислительные и математические тонкости, которыми буквально изобилуют алгоритмы дис-
кретного программирования. Заметим также, что достаточно эффективный и широко применяемый
подход к решению целочисленных задач основан на сведении их к задачам транспортного типа. Это
объясняется тем, что если в условиях транспортной задачи значения запасов (а
i
) и потребностей (b
j
)
являются целочисленными, то целочисленным будет и оптимальный план.
4.2. МЕТОД ГОМОРИ
4.2.1. Основные идеи и принципы*. Данный метод, который также носит название метода
отсекающих плоскостей, предназначен для решения ЦЗЛП в канонической форме (4.2)-(4.3). Кратко
представим его основные идеи.
* Впервые был предложен Р.Гомори в 1957-1958 гг.
Отправной точкой для решения задачи (4.2)-(4.3) является решение ее непрерывного аналога, т. е.
КЗЛП без учета условий целочисленности. Если получаемый в результате оптимальный план х*
содержит только целые компоненты, то мы автоматически получаем и соответствующее решение
ЦЗЛП. В противном случае к системе ограничений задачи должно быть добавлено такое ограничение,
для которого:
найденный нецелочисленный оптимальный план х* не удовлетворяет вновь добавляемому
ограничению;
любой допустимый целочисленный план непрерывной задачи (4.2)-(4.3) удовлетворяет вновь
добавляемому ограничению.
Такое ограничение называют правильным отсечением. В первой геометрической интерпретации
правильному отсечению соответствует гиперплоскость, отсекающая от выпуклого многогранного
множества допустимых планов D некоторый многогранник, не содержащий целочисленных планов.
Добавив сформированное отсекающее ограничение к уже существующим, мы получаем новую
оптимизационную задачу, после чего вычислительный процесс итеративно повторяется.
Теперь необходимо несколько более подробно остановиться на принципах формирования
отсекающих ограничений. Воспользуемся системой обозначений, применявшихся при изложении
вычислительных методов линейного программирования. Пусть
?
(q)
— оптимальный базис, полученный
на последней итерации решения нецелочисленной ЗЛП. Если обозначить через
?
i,j
и
?
i
коэффициенты
матрицы задачи и вектора ограничений в текущем базисе (A(?
(q)
) и b(?
(q)
))
то i-ое уравнение в системе ограничений задачи примет вид:
Так как план x(?
(q)
) является базисным, то в каждом уравнении все коэффициенты
?
i,j
,
соответствующие базисным столбцам (j?N(?
(q)
)), равны нулю за исключением некоторого
?
i,ji
=1, на
основе чего из (4.18) получаем:
Если представить каждый коэффициент
?
i,j
в виде суммы целой и дробной частей
?
i,j
=[?
i,j
]+{?
i,j
}, то
получим