Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Имеем задачу целочисленного программирования записанную в канонической форме:
(1)
при ограничениях:
(2)
(3) (4)
Здесь -исходные переменные задачи;
- дополнительные переменные задачи;
При решение необходимо иметь ввиду, что т.к. оптимальное решение определяется пересечением n гиперплоскостей, то таких гиперплоскостей существует не больше чем это необходимо(часть этих плоскостей могут быть ограничениями исходной задачи). Каждое текущее решение задачи можно представить в виде таблице неравенств:
… | |||||
f(X) | … | ||||
… | |||||
… | |||||
…….. | |||||
… |
Предполагается, что все в исходной таблице целыеà все дополнительные переменные также должны быть целыми неотрицательными числами. Можно показать, что если -выпуклый многогранник, -множество его целых точек, -выпуклая линейная оболочка множества , то является целочисленным многогранником. Непосредственно построение - сложная задача, является основной задачей методов отсечения.
Алгоритм состоит из следующих процедур:
1) Решается исходная задача линейного программирования (1)-(3) каким-либо методом
2) Получение оптимального решения ЗЛП(задача линейного программирования), если оно существует- проверить на условие целочисленности. Если условие выполняетсяà оптим. решение ЗЛП является одновременно оптимальным решением целочисленного ЗЛП (ЦЗЛП). Если условия (4) [x-целое] не выполняется хотя бы для одной переменной, то перейдем к следующему этапу
3) Строим специальное дополнительное ограничение, позволяющее отсечь часть области R; в котором содержится оптим. решение ЗЛП и не содержится допустимого ЦЗЛП.
Подобный процесс построения доп. ограничений повторим до тех пор пока:
а) не будет доказана неразрешимость ЦЗЛП
б) либо пока не получим целочисленное решение
Примечание: дополнительные ограничения должны быть линейны;
Таким образом, любое неравенство пригодное для этой цели(см. Примечание) и имеющее вид должно удовлетворять условиям правильного отсечения:
а) условию отсечения, т е оптимальному решению предыдущего ЗЛП не удовлетворяющего этому неравенству
б) любое допустимое решение ЦЗЛП удовлетворяет этому неравенству
Дата публикования: 2015-02-03; Прочитано: 280 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!