4.3. Пример решения ЦЗЛП с применением метода Гомори

Мастерская программиста Гирича Семёна Николаевича
Решение задач линейного программирования

Главная

4.3. Пример решения ЦЗЛП с применением метода Гомори

Задача:

Вариант №4
Задача №4: Найти оптимальное решение задачи целочисленного линейного программирования.
Zmin=6*x1 +x2; при ограничениях:
3*x1 - x2>=9;
2*x1+3*x2=<50;
- x1+4*x2>=18;
x1,x2>=0; x1,x2: целые числа.

Математическая модель задачи:

Целевая функция:
S min = 6*x1+1*x2

Система ограничений:
3*x1-1*x2>=9
2*x1+3*x2<=50
-1*x1+4*x2>=18

x1,x2 >=0; - условие неотрицательности переменных.

Решение задачи с использованием метода симплекс-таблиц.

Математическая модель задачи:

Целевая функция:
S min = 6*x1+1*x2

Система ограничений:
3*x1-1*x2>=9
2*x1+3*x2<=50
-1*x1+4*x2>=18

x1,x2, >=0; - условие неотрицательности переменных.

Система неравенств приведена к каноническому виду:

Целевая функция:
S min = 6*x1+1*x2+0*x3+0*x4+0*x5

Система ограничений:
-3*x1+x2+x3=-9
2*x1+3*x2+x4=50
x1-4*x2+x5=-18

Векторный анализ системы ограничений:

Расширенная целевая функция:
S min = 6*x1+1*x2+0*x3+0*x4+0*x5

Вектора:

P0	P1(x1)	P2(x2)	P3(x3)	P4(x4)	P5(x5)
-9	-3	1	1	0	0
50	2	3	0	1	0
-18	1	-4	0	0	1

Базис:
Базисный вектор №1: P3(x3)
Базисный вектор №2: P4(x4)
Базисный вектор №3: P5(x5)

Расширенная целевая функция:
S min = 6*x1+1*x2+0*x3+0*x4+0*x5

Заполним первую таблицу:

Таблица №1

№	Base	CBase	P0	P1	P2	P3	P4	P5
№	Base	CBase	P0	6	1	0	0	0
1	P3	0	-9	-3	1	1	0	0
2	P4	0	50	2	3	0	1	0
3	P5	0	-18	1	-4	0	0	1
S min =			0	-6	-1	0	0	0

Невозможно выбрать столбец замещения, так как нет положительных dj!
Выберем столбец таким образом. Чтобы избавиться от недопустимого решения, т.е. от отрицательных значений в столбце свободных членов (Р0).
Замещаемый базисный вектор: P3 (1-я строка)
Новый базисный вектор: P1 (1-й столбец)
Заменяем базисный вектор P3 на P1.
Таблица №2

№	Base	CBase	P0	P1	P2	P3	P4	P5
№	Base	CBase	P0	6	1	0	0	0
1	P1	6	3	1	-0,3333	-0,3333	0	0
2	P4	0	44	0	3,6667	0,6667	1	0
3	P5	0	-21	0	-3,6667	0,3333	0	1
S min =			18	0	-3	-2	0	0

Невозможно выбрать столбец замещения, так как нет положительных dj!
Выберем столбец таким образом. Чтобы избавиться от недопустимого решения, т.е. от отрицательных значений в столбце свободных членов (Р0).
Замещаемый базисный вектор: P5 (3-я строка)
Новый базисный вектор: P2 (2-й столбец)
Заменяем базисный вектор P5 на P2.
Таблица №3

№	Base	CBase	P0	P1	P2	P3	P4	P5
№	Base	CBase	P0	6	1	0	0	0
1	P1	6	4,9091	1	0	-0,3636	0	-0,0909
2	P4	0	23	0	0	1	1	1
3	P2	1	5,7273	0	1	-0,0909	0	-0,2727
S min =			35,1818	0	0	-2,2727	0	-0,8182

Решение не целочисленное. Применим метод Гомори: выберем в таблице строку, в которой целая часть дробного свободного члена (P0) принимает наибольшее значение.
Макс. целая часть дробного свободного члена при базисном векторе P2 (3-я строка). Составим уравнение ограничения и добавим в таблицу новый базисный вектор по новому уравнению и новой переменной.
Добавляем базисный вектор: P6 (6-й столбец)

Таблица №4

№	Base	CBase	P0	P1	P2	P3	P4	P5	P6
№	Base	CBase	P0	6	1	0	0	0	0
1	P1	6	4,9091	1	0	-0,3636	0	-0,0909	0
2	P4	0	23	0	0	1	1	1	0
3	P2	1	5,7273	0	1	-0,0909	0	-0,2727	0
4	P6	0	-0,7273	0	0	-0,9091	0	-0,7273	1
S min =			35,1818	0	0	-2,2727	0	-0,8182	0

Невозможно выбрать столбец замещения, так как нет положительных dj!
Выберем столбец таким образом. Чтобы избавиться от недопустимого решения, т.е. от отрицательных значений в столбце свободных членов (Р0).
Замещаемый базисный вектор: P6 (4-я строка)
Новый базисный вектор: P5 (5-й столбец)
Заменяем базисный вектор P6 на P5.
Таблица №5

№	Base	CBase	P0	P1	P2	P3	P4	P5	P6
№	Base	CBase	P0	6	1	0	0	0	0
1	P1	6	5	1	0	-0,25	0	0	-0,125
2	P4	0	22	0	0	-0,25	1	0	1,375
3	P2	1	6	0	1	0,25	0	0	-0,375
4	P5	0	1	0	0	1,25	0	1	-1,375
S min =			36	0	0	-1,25	0	0	-1,125

Невозможно выбрать столбец замещения, так как нет положительных dj!
Получено оптимальное решение!

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

x1	x2	x3	x4	x5	p6
5	6	0	22	1	0

Целевая функция:
S min = 6*5+1*6
И в результате:
S min = 36;
Задача решена.

Далее: 5. Двойственная задача

Вернуться в Начало

Назад Вверх