- •Линейное программирование постановка задачи
- •Основные понятия линейного программирования (лп)
- •Графический метод решения простейших задач лп
- •Метод последовательного улучшения решения задачи лп (симплекс-метод)
- •Симплекс-таблица № 1
- •Симплекс-таблица № 3
- •Задача об оптимальном планировании производства
- •Симплекс-таблица № 3
- •Симплекс-таблица № 1
- •Симплекс-таблица № 2
- •Пара взаимно двойственных задач лп. Основные теоремы теории двойственных задач и их применение к решению задач лп
- •Транспортная задача
Симплекс-таблица № 1
30 40
1
2
0 3 12 4 = 300
0 4 4 4 = 120
0 5 3 12 = 252
– 30 – 40 = 0
Полагая
свободные переменные
,
,
получим первое опорное решение
,
,
т.е. если предприятие не выпускает
продукцию
,
то остатки сырья равны его запасам
и прибыль предприятия
.
План не оптимальный, т.к.
строка
содержит отрицательные оценки
.
По схеме 1 выбираем разрешающий столбец (второй), разрешающую строку (третью) и проводим один шаг жордановых преобразований по схеме 2. Получим:
Симплекс-таблица № 2
30 0
1 5
0 3 11 –1/3 = 216
0
4
3 –1/3
= 36
40 2 1/4 1/12 = 21
–20 10/3 = 840
Опорный
план, соответствующий симплекс-таблице
№ 2,
,
,
т.е. если предприятие не будет производить
продукцию вида
и изготовит 21 единицу продукции вида
,
то прибыль составит
денежных единиц, при этом останутся
неизрасходованными 216
единиц сырья
и 36
единиц сырья
,
сырьё
будет израсходовано полностью
.
Полученный опорный план не является оптимальным, поэтому проводим ещё одно жорданово преобразование.
Симплекс-таблица № 3
0 0
4 5
0 3 – 11/3 8/9 = 186
30 1 1/3 –1/9 = 12
40 2 – 1/12 1/9 = 18
20/3 10/9 = 1080
Опорный
план, соответствующий симплекс-таблице
№ 3,
,
,
является оптимальным, т.к.
строка не содержит отрица-
тельных оценок.
Вывод:
если предприятие изготовит
единиц продукции
и
единиц продукции
,
то прибыль его будет максимальной –
денежных единиц, при этом запасы сырья
и
будут полностью исчерпаны
),
остаток сырья
составит 186
единиц
.
