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

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 6 1 0 0 0
P1 P2 P3 P4 P5
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 6 1 0 0 0
P1 P2 P3 P4 P5
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 6 1 0 0 0
P1 P2 P3 P4 P5
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 6 1 0 0 0 0
P1 P2 P3 P4 P5 P6
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 6 1 0 0 0 0
P1 P2 P3 P4 P5 P6
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. Двойственная задача

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

© 2011 Семён Гирич,
Система Orphus: Выделите текст с ошибкой и нажмите [Ctrl] + [Enter]
Назад    Вверх