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

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

Главная

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

Задача:

Рацион для питания животных на ферме состоит из двух видов кормов 1 и 2.
Один килограмм корма 1 стоит 80 р. и содержит 1 ед. жиров, 3 ед. белков,
1 ед. углеводов, 2 ед. нитратов. Один килограмм корма 2 стоит 10 р. и
содержит 3 ед. жиров, 1 ед. белков, 8 ед. углеводов, 4 ед. нитратов.
Составить наиболее дешевый рацион питания при условии, что:
Жиров .....……. не менее 6 ед.
Белков .....….... не менее 9 ед.
Углеводов ..…. не менее 8 ед.

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

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

Система ограничений:
x1+3*x2>=6
3*x1+x2>=9
x1+8*x2>=8
2*x1+4*x2<=16

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

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

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

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

Система ограничений:
x1+3*x2>=6
3*x1+x2>=9
x1+8*x2>=8
2*x1+4*x2<=16

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

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

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

Система ограничений:
-1*x1-3*x2+x3=-6
-3*x1-1*x2+x4=-9
-1*x1-8*x2+x5=-8
2*x1+4*x2+x6=16

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

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

Вектора:

P0	P1(x1)	P2(x2)	P3(x3)	P4(x4)	P5(x5)	P6(x6)
-6	-1	-3	1	0	0	0
-9	-3	-1	0	1	0	0
-8	-1	-8	0	0	1	0
16	2	4	0	0	0	1

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

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

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

Таблица №1

№	Base	CBase	P0	P1	P2	P3	P4	P5	P6
№	Base	CBase	P0	80	10	0	0	0	0
1	P3	0	-6	-1	-3	1	0	0	0
2	P4	0	-9	-3	-1	0	1	0	0
3	P5	0	-8	-1	-8	0	0	1	0
4	P6	0	16	2	4	0	0	0	1
S min =			0	-80	-10	0	0	0	0

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

№	Base	CBase	P0	P1	P2	P3	P4	P5	P6
№	Base	CBase	P0	80	10	0	0	0	0
1	P1	80	6	1	3	-1	0	0	0
2	P4	0	9	0	8	-3	1	0	0
3	P5	0	-2	0	-5	-1	0	1	0
4	P6	0	4	0	-2	2	0	0	1
S min =			480	0	230	-80	0	0	0

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

№	Base	CBase	P0	P1	P2	P3	P4	P5	P6
№	Base	CBase	P0	80	10	0	0	0	0
1	P1	80	4,8	1	0	-1,6	0	0,6	0
2	P4	0	5,8	0	0	-4,6	1	1,6	0
3	P2	10	0,4	0	1	0,2	0	-0,2	0
4	P6	0	4,8	0	0	2,4	0	-0,4	1
S min =			388	0	0	-126	0	46	0

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

№	Base	CBase	P0	P1	P2	P3	P4	P5	P6
№	Base	CBase	P0	80	10	0	0	0	0
1	P1	80	2,625	1	0	0,125	-0,375	0	0
2	P5	0	3,625	0	0	-2,875	0,625	1	0
3	P2	10	1,125	0	1	-0,375	0,125	0	0
4	P6	0	6,25	0	0	1,25	0,25	0	1
S min =			221,25	0	0	6,25	-28,75	0	0

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

№	Base	CBase	P0	P1	P2	P3	P4	P5	P6
№	Base	CBase	P0	80	10	0	0	0	0
1	P1	80	2	1	0	0	-0,4	0	-0,1
2	P5	0	18	0	0	0	1,2	1	2,3
3	P2	10	3	0	1	0	0,2	0	0,3
4	P3	0	5	0	0	1	0,2	0	0,8
S min =			190	0	0	0	-30	0	-5

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

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

x1	x2	x3	x4	x5	x6
2	3	5	0	18	0

Целевая функция:
S min = 80*2+10*3
И в результате:
S min = 190;
Задача решена.

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

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

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

Назад Вверх