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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ОДЕССКИЙ НАЦИОНАЛЬНЫЙ МОРСКОЙ УНИВЕРСИТЕТ

Кафедра «Информационные технологии»

 

 

 

 

 

 

 

 

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

 

 

Расчётно - графическое задание №1

 

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

 

Вариант № 20

 

 

 

 

 

 

 

Выполнила:

ст. КСФ V курса

    специалист

Тодосюк А.В

Проверил:

доц. Ширшков А.К.

асс. Личикаки Н.К.

 

 

 

 

 

 

 

 

 

Одесса

2014

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

 

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

 

 

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

 

 

 

Решение

 

 

Рассмотрим графический метод отсекающих плоскостей. Решим задачу ЦЧП – задача №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 ОДР является 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") = 30y.e, оптимальное решение – целочисленно.Отсекающие точки(3;3) (4;1)

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