2.2 Решение частично целочисленной задачи

Максимизировать целевую функцию вида:

При ограничениях:

;- целoе.

a) Метод Гомори для частично целочисленных задач.

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

Таблица 2.2.1
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8
x5	5	0	0	0	-5	1	0	-2	1
x1	9/2	1	0	0	-1	0	-1/2	0	0
x2	7/4	0	1	0	-2	0	1/4	-1	1/2
x3	5/4	0	0	1	-1	0	-1/4	0	1/2
Y	-16	0	0	0	5	0	1	1	1

Значения целевой функции и переменных:

Значение переменной не удовлетворяет требованиям целочисленности.

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

Вводим дополнительную свободную переменную:

Выражаем новое ограничение в форме Куна-Таккера:

Решаем новую расширенную задачу линейного программирования:

Таблица 2.2.2
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	5	0	0	0	-5	1	0	-2	1	0
x1	9/2	1	0	0	-1	0	-1/2	0	0	0
x2	7/4	0	1	0	-2	0	1/4	-1	1/2	0
x3	5/4	0	0	1	-1	0	-1/4	0	1/2	0
x9	-1/2	0	0	0	-1	0	-1/2	0	0	1
Y	-16	0	0	0	5	0	1	1	1	0

Таблица 2.2.3
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	5	0	0	0	-5	1	0	-2	1	0
x1	5	1	0	0	0	0	0	0	0	-1
x2	3/2	0	1	0	-5/2	0	0	-1	1/2	½
x3	3/2	0	0	1	-1/2	0	0	0	1/2	-1/2
x6	1	0	0	0	2	0	1	0	0	-2
Y	-17	0	0	0	3	0	0	1	1	2

Полученное оптимальное решение удовлетворяет поставленным ограничением и требованию целочисленности переменной .

Ответ: .

б) Метод ветвей и границ.

Проанализировав ограничения определим границы следующим образом:

Т.к. о целевой функции ничего не известно, примем .

Решаем Задачу 1 – исходную задачу линейного программирования. Ее решение приведено в пункте 1.3. Последняя симплексная таблица имеет вид:

Таблица 2.2.4
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8
x5	5	0	0	0	-5	1	0	-2	1
x1	9/2	1	0	0	-1	0	-1/2	0	0
x2	7/4	0	1	0	-2	0	1/4	-1	1/2
x3	5/4	0	0	1	-1	0	-1/4	0	1/2
Y	-16	0	0	0	5	0	1	1	1

Значения целевой функции и переменных:

Принимаем

Полученное решение не удовлетворяет требованиям целочисленности для переменной .

Поэтому составляем относительно первой задачи две новых порожденных задачи:

Задача 2.

Максимизировать целевую функцию вида:

При ограничениях:

;

- новое ограничение.

Преобразуем новую систему ограничений Задачи 2, введя свободные переменные и приведя их к форме Куна-Таккера:

Воспользуемся симплекс методом и решим Задачу 2.

Таблица 2.2.5
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	-3	-1	-2	0	0	1	0	0	0	0
x6	-9	-2	0	0	2	0	1	0	0	0
x7	-5	-1	-1	1	2	0	0	1	0	0
x8	-2	-1	0	2	-1	0	0	0	1	0
x9	3	1	0	0	0	0	0	0	0	1
Y	0	4	1	-3	2	0	0	0	0	0

Таблица 2.2.6
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	3/2	0	-2	0	-1	1	-1/2	0	0	0
x1	9/2	1	0	0	-1	0	-1/2	0	0	0
x7	-1/2	0	-1	1	1	0	-1/2	1	0	0
x8	5/2	0	0	2	-2	0	-1/2	0	1	0
x9	-1/2	0	0	0	1	0	1/2	0	0	1
Y	-18	0	1	-3	6	0	2	0	0	0

Таблица 2.2.6
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	5/2	0	0	-2	-3	1	1/2	-2	0	0
x1	9/2	1	0	0	-1	0	-1/2	0	0	0
x2	½	0	1	-1	-1	0	1/2	-1	0	0
x8	5/2	0	0	2	-2	0	-1/2	0	1	0
x9	-1/2	0	0	0	1	0	1/2	0	0	1
Y	-37/2	0	0	-2	7	0	3/2	1	0	0

Допустимого решения Задачи 2 не существует.

Поэтому примем

Выбираем и решаем Задачу 3.

Максимизировать целевую функцию вида:

При ограничениях:

;

- новое ограничение.

Преобразуем новую систему ограничений Задачи 3, введя свободные переменные и приведя их к форме Куна-Таккера:

Воспользуемся симплекс методом и решим Задачу 2.

Таблица 2.2.7
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x5	-3	-1	-2	0	0	1	0	0	0	0	0
x6	-9	-2	0	0	2	0	1	0	0	0	0
x7	-5	-1	-1	1	2	0	0	1	0	0	0
x8	-2	-1	0	2	-1	0	0	0	1	0	0
x9	-5	-1	0	0	0	0	0	0	0	1	0
x10	6	1	0	0	0	0	0	0	0	0	1
Y	0	4	1	-3	2	0	0	0	0	0	0

Таблица 2.2.8
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x5	3/2	0	-2	0	-1	1	-1/2	0	0	0	0
x1	9/2	1	0	0	-1	0	-1/2	0	0	0	0
x7	-1/2	0	-1	1	1	0	-1/2	1	0	0	0
x8	5/2	0	0	2	-2	0	-1/2	0	1	0	0
x9	-1/2	0	0	0	-1	0	-1/2	0	0	1	0
x10	3/2	0	0	0	1	0	1/2	0	0	0	1
Y	-18	0	1	-3	6	0	2	0	0	0	0

Таблица 2.2.8
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x5	5/2	0	0	-2	-3	1	1/2	-2	0	0	0
x1	9/2	1	0	0	-1	0	-1/2	0	0	0	0
x2	1/2	0	1	-1	-1	0	1/2	-1	0	0	0
x8	5/2	0	0	2	-2	0	-1/2	0	1	0	0
x9	-1/2	0	0	0	-1	0	-1/2	0	0	1	0
x10	3/2	0	0	0	1	0	1/2	0	0	0	1
Y	-37/2	0	0	-2	7	0	3/2	1	0	0	0

Таблица 2.2.9
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x5	2	0	0	-2	-4	1	0	-2	0	1	0
x1	5	1	0	0	0	0	0	0	0	-1	0
x2	0	0	1	-1	-2	0	0	-1	0	1	0
x8	3	0	0	2	-1	0	0	0	1	-1	0
x6	1	0	0	0	2	0	1	0	0	-2	0
x10	1	0	0	0	0	0	0	0	0	1	1
Y	-20	0	0	-2	4	0	0	1	0	3	0

Таблица 2.2.10
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x5	5	0	0	0	-5	1	0	-2	1	0	0
x1	5	1	0	0	0	0	0	0	0	-1	0
x2	3/2	0	1	0	-5/2	0	0	-1	1/2	1/2	0
x3	3/2	0	0	1	-1/2	0	0	0	1/2	-1/2	0
x6	1	0	0	0	2	0	1	0	0	-2	0
x10	1	0	0	0	0	0	0	0	0	1	1
Y	-17	0	0	0	3	0	0	1	1	2	0

Полученное оптимальное решение удовлетворяет поставленным ограничением и требованию целочисленности переменной . Поэтому принимаем

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

Ответ:

Рис 2.2.1 Блок схема решения.

На основе полученных результатов решения задачи методом Гомори и методом ветвей и границ, можно сделать вывод о том, метод Гомори менее трудоемок. Однако, стоит учесть простоту решаемой задачи, в которой требование целочисленности наложено всего на одну переменную из трех. Метод Гомори в данном случае позволяет получить оптимальное решение с использованием всего одного уравнения отсекающей плоскости и решением одной расширенной задачи. Используя метод ветвей и границ, приходится решать уже две порожденных задачи, т.е. использование этого метода в данном случае менее эффективно. Таким образом можно сделать вывод о том, что метод ветвей и границ вообще мало эффективен для решения простых задач, где не требуется получение всех локальных оптимумов. В таких случаях разумнее воспользоваться методом Гомори для частично целочисленных задач.