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

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

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

; - целoе.

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

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

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

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

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

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

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

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

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

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

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

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

Ответ: .

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

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

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

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

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

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

Принимаем

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

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

Задача 2.

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

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

;

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

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

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

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

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

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

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

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

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

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

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

;

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

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

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

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

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

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

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

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

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

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

Ответ:

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

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