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

Постановка задачи

Составить содержательную постановку для заданной оптимизационной задачи целочисленного программирования (управляющие переменные, ограничения, целевая функция):

• 1. Вычислить оптимальное целочисленное решение графическим методом отсекающих гиперплоскостей (решение без учета целочисленности, решение с учетом целочисленности, решение с учетом целочисленности).
• 2. Факторы эффективности оптимального целочисленного решения.

Решение

Рассмотрим графический метод отсекающих плоскостей. Решим задачу ЦЧП — задача № 1:

ОДР (Областью допустимых решений) задачи ЦЧП являются узловые точки координатной сетки ограниченные системой ограничений.

Построим диаграмму области допустимых решений ОДР1 задачи № 1, рисунок 1:

Рис 1. Задача ЦЧП, задача № 1

Строим область допустимых решений:

Табл. 1.

Допустимыми решениями задачи ЦЧП являются целочисленные узлы координатной сетки, ограниченные условиями (1−3). Вершина B (целевая функция достигает своего максимума) имеет не дробные координаты, которые являются допустимыми решениями целочисленной задачи.

Шаг 1. Решим ослабленную задачу ЦЧП, т. е. без условия целочисленности переменных, задача № 2:

Для задачи № 2 построим диаграмму ОДР2 и вычислим оптимальное решение. Изобразим на рисунке 2.

Рис 2. Задача № 2

ОДР задачи № 2 является выпуклый треугольник ABC. Оптимальное решение — координаты вершины В (2,5; 4,5) и значение целевой функции F (В) = 37 у.е. Полученное оптимальное решение оказалось нецелочисленным, обе переменные — дробные.

Шаг 2. Введем в систему ограничений задачи № 2 ПДО № 1 для переменной., получим задачу 3:

Для задачи № 3 построим диаграмму ОДР3 и вычислим оптимальное решение, рис 3:

Рис. 3.

Для задачи № 3 ОДР является ABґС, оптимальным решением — координаты вершины Вґ(2; 3), значение целевой функции у.

Шаг 3. Введем в систему ограничений задачи № 3 ПДО № 2 для переменной, получим задачу № 4.

Для задачи № 4 построим диаграмму ОДР4 и вычислим оптимальное решение, рис 4.

оптимизационный целочисленный отсекающий графический.

Рис 4. Задача № 4

Отсекающие точки (3;3) и (4;1).

Для задачи № 4 ОДР является A, B" C, оптимальное решение — координаты вершины B" (3;3) — целые, значение целевой функции F (B") = 30 y. e, оптимальное решение — целочисленно. Отсекающие точки (3;3) (4;1).

Следовательно, вычислено оптимальное целочисленное решение (), обеспечивающее max целевой функции исходной задачи ЦЧП. Задача ЦЧП решена.