2

Липецкий государственный технический университет

Кафедра автоматизированных систем управления

ЛАБОРАТОРНАЯ РАБОТА №6

по Теории принятия решений

Целочисленное линейное программирование (ЗЦЛП)

Студент

Ключанских А.С

^подпись, дата

^фамилия, инициалы

Группа

АС-10

Принял

доцент

Корнеев А.М.

^ученая степень, звание

^подпись, дата

^фамилия, инициалы

Липецк 2013

1. Задание

Найти оптимальное целочисленное решение.

1. Исходными данными взять результаты, посчитанные симплекс-методом.

2. Найти решение ЗЦЛП:

2.1 методом Гомори;

2.2 методом ветвей и границ.

2. Решение

Двойственный симплекс.

Целевая функция имеет вид: .

А область ограничений задачи в стандартной форме имеет вид:

Найденное оптимальное решение в предыдущих практических работах:

.

Симплекс-таблица, полученная в практической работе №3 имеет вид:

Базис	B
	6	1	0	0	0	-1/7	1/7
	3	0	0	1	0	-9/14	1/7
	2	0	0	0	1	-8/7	1/7
	7	0	1	0	0	1/2	0
	100	0	0	0	0	30/7	5/7

1) Введем дополнительное ограничение:

Уравнение прямой имеет вид:

Ограничение имеет вид:

Представим в канонической форме:

Выразим :

Выразим : .

Формируем новую строку симплекс таблицы:

Базис	B
	6	1	0	0	0	- 1/7	1/7	0
	3	0	0	1	0	- 9/14	1/7	0
	2	0	0	0	1	-1 1/7	1/7	0
	7	0	1	0	0	1/2	0	0
	-15	0	0	0	0	2 5/28	- 13/14	1
	100	0	0	0	0	4 2/7	5/7	0

Проверим полученный базисный план на оптимальность по условию оптимальности: В симплекс-таблице в столбце базисных переменных есть отрицательные элементы, значит данное базисное решение не оптимально.

Выбираем переменную, которая выводится из базиса. Находим строку, у которой самый большой по модулю отрицательный элемент .

Ведущая строка: .

Выбираем переменную, которая вводится в базис. Для элементов ведущей строки, которые меньше 0, находим .

Ведущий столбец: .

Перестроим симплекс-таблицу по правилам обычного симплекс-метода:

Базис	B
	3 9/13	1	0	0	0	5/26	0	2/13
	9/13	0	0	1	0	- 4/13	0	2/13
	- 4/13	0	0	0	1	- 21/26	0	2/13
	7	0	1	0	0	1/2	0	0
	16 2/13	0	0	0	0	-2 9/26	1	-1 1/13
	88 6/13	0	0	0	0	5 25/26	0	10/13

Проверим полученный базисный план на оптимальность по условию оптимальности: В симплекс-таблице в столбце базисных переменных есть отрицательные элементы, значит данное базисное решение не оптимально.

Выбираем переменную, которая выводится из базиса. Находим строку, у которой самый большой по модулю отрицательный элемент .

Ведущая строка: .

Выбираем переменную, которая вводится в базис. Для элементов ведущей строки, которые меньше 0, находим .

Ведущий столбец: .

Перестроим симплекс-таблицу по правилам обычного симплекс-метода:

Базис	B
	3 13/21	1	0	0	5/21	0	0	4/21
	17/21	0	0	1	- 8/21	0	0	2/21
	8/21	0	0	0	-1 5/21	1	0	- 4/21
	6 17/21	0	1	0	13/21	0	0	2/21
	17 1/21	0	0	0	-2 19/21	0	1	-1 11/21
	86 4/21	0	0	0	7 8/21	0	0	1 19/21

Значение целевой функции ухудшилось по сравнению с исходным оптимальным решением, следовательно, дополнительное ограничение АКТИВНОЕ.