3.6. Пример(1) решения задачи ЛП методом симплекс-таблиц

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

Главная

3.6. Пример(1) решения задачи ЛП методом симплекс-таблиц

Задача:

Определить оптимальный план выпуска машин М1, М2, М3, исходя из максимальной прибыли и ограниченности фонда времени цехов мех. завода. Прибыль от реализации первой машины:
М1 = 4 тыс. руб.
М2 = 5 тыс. руб.
М3 = 6 тыс. руб.
Заготовительный цех может проработать в год не более 2000 часов, мех. цех не более 1770 часов и сборочный не более 1660 часов. На изготовление машин М1, М2, М3 уходит времени по цехам: заготовительный - 4, 5 и 6 соответственно; мех. цех - 8, 6 и 4; сборочный - 6, 4 и 5 часов

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

Целевая функция:
S max = 4*x1+5*x2+6*x3

Система ограничений:
4*x1+5*x2+6*x3<=2000
8*x1+6*x2+4*x3<=1770
6*x1+4*x2+5*x3<=1600

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

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

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

Целевая функция:
S max = 4*x1+5*x2+6*x3

Система ограничений:
4*x1+5*x2+6*x3<=2000
8*x1+6*x2+4*x3<=1770
6*x1+4*x2+5*x3<=1600

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

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

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

Система ограничений:
4*x1+5*x2+6*x3+x4=2000
8*x1+6*x2+4*x3+x5=1770
6*x1+4*x2+5*x3+x6=1600

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

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

Вектора:

P0	P1(x1)	P2(x2)	P3(x3)	P4(x4)	P5(x5)	P6(x6)
2000	4	5	6	1	0	0
1770	8	6	4	0	1	0
1600	6	4	5	0	0	1

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

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

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

Таблица №1

№	Base	CBase	P0	P1	P2	P3	P4	P5	P6
№	Base	CBase	P0	4	5	6	0	0	0
1	P4	0	2000	4	5	6	1	0	0
2	P5	0	1770	8	6	4	0	1	0
3	P6	0	1600	6	4	5	0	0	1
S max =			0	-4	-5	-6	0	0	0

Замещаемый базисный вектор: P6 (3-я строка)
Новый базисный вектор: P3 (3-й столбец)
Заменяем базисный вектор P6 на P3.
Таблица №2

№	Base	CBase	P0	P1	P2	P3	P4	P5	P6
№	Base	CBase	P0	4	5	6	0	0	0
1	P4	0	80	-3,2	0,2	0	1	0	-1,2
2	P5	0	490	3,2	2,8	0	0	1	-0,8
3	P3	6	320	1,2	0,8	1	0	0	0,2
S max =			1920	3,2	-0,2	0	0	0	1,2

Замещаемый базисный вектор: P5 (2-я строка)
Новый базисный вектор: P2 (2-й столбец)
Заменяем базисный вектор P5 на P2.
Таблица №3

№	Base	CBase	P0	P1	P2	P3	P4	P5	P6
№	Base	CBase	P0	4	5	6	0	0	0
1	P4	0	45	-3,4286	0	0	1	-0,0714	-1,1429
2	P2	5	175	1,1429	1	0	0	0,3571	-0,2857
3	P3	6	180	0,2857	0	1	0	-0,2857	0,4286
S max =			1955	3,4286	0	0	0	0,0714	1,1429

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

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

x1	x2	x3	x4	x5	x6
0	175	180	45	0	0

Целевая функция:
S max = 4*0+5*175+6*180
И в результате:
S max = 1955;
Задача решена.

Далее: 3.7. Пример(2) решения задачи ЛП методом симплекс-таблиц

Далее: 4. Целочисленное линейное программирование - метод отсечений Гомори

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

Назад Вверх