Идея методов отсечения

Методы отсечения (методы отсекающих плоскостей) разработаны для решения задач целочисленного программирования.

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

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

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

· полученное нецелочисленное решение ему не удовлетворяет и, следовательно должно быть отброшено

· все целочисленные точки допустимого множества исходной задачи ему удовлетворяет. Такое ограничение называется правильным отсечением. Полученную задачу называют расширенной непрерывной задачей линейного программирования.

2)затем решается расширенная задача линейного программирования и опять проверяется решение на «целочисленность». Если решение целочисленное, то оно является решением исходной задачи. В противном случае вводим новое правильное отсечение (ограничение) и т.д. пока решение не будет целочисленным.

Пусть L – исходная целочисленная задача линейного программирования,

– ее решение.

– расширенная непрерывная задача и ее решение

– исходная задача с отброшенным требованием целочисленности.

Алгоритм решения целочисленной задачи линейного программирования методом отсечений:

1)Находится решение -задачи линейного программирования .

Если решение целочисленное, то вычисления завершаются. Если нет, то полагается k=1 и осуществляется переход к пункту 2.

2)Определяется k-тое правильное отсечение, составляется задача

3)Находится решение задачи . Если решение целочисленное, то вычисления завершаются. Если нет, то полагается k=k+1 и переход к пункту 2. Решением исходной задачи равно решению расширенной непрерывной задачи .

Если задача не имеет допустимого решения, то исходная задача L не имеет допустимого целочисленного решения.

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

(5.3)

Если (1-й алгоритм Гомори), то задача называется полностью целочисленной задачей.

Если (2-й алгоритм Гомори), то задача называется частично целочисленной задачей.