- •Технологическая карта (план) занятия № 10
- •Содержание урока:
- •1. Организационный момент проверка посещаемости
- •Методы решения злп
- •1.2 Табличный симплекс - метод
- •1.3 Метод искусственного базиса
- •1.4 Модифицированный симплекс - метод
- •Описание Симплекс-метода
- •Порядок работы с симплекс таблицей
- •Пример 1 Задача об использовании сырья
- •Пример 2.
- •Пример 3
- •Пример 4 Задача об использовании ресурсов
- •Пример 5
- •Задачи на закрепление:
Пример 5
f(x) = 5 х1 + 3 х2 + 4 х3 – х4 ® max
х1 + 3 x2 + 2 х3 + 2 х4 <= 3,
2 х1 + 2 x2 + х3 + х4 <= 3,
хi ³ 0, i = 1,…,4.
Решение: Решим данную задачу методом искусственного базиса, для этого в ограничения задачи добавим искусственные переменные х5, х6:и возьмем их в качестве базисных.
х1 + 3 x2 + 2 х3 + 2 х4 + х5 = 3,
2 х1 + 2 x2 + х3 + х4 + х6 = 3,
Составим вспомогательную функцию: Z = х5 + х6 min, выразим ее через небазисные переменные: Z = 6 – 3 х1 – 5 x2 – 3 х3 – 3 х4. Строим симплексную таблицу и решаем задачу:
базис |
значение |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
Z(x) |
6 |
3 |
5 |
3 |
3 |
0 |
0 |
f(x) |
0 |
-5 |
-3 |
-4 |
1 |
0 |
0 |
х5 |
3 |
1 |
3 |
2 |
2 |
1 |
0 |
х6 |
3 |
2 |
2 |
1 |
1 |
0 |
1 |
базис |
значение |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
Z(x) |
1 |
4/3 |
0 |
-1/3 |
-1/3 |
-5/3 |
0 |
f(x) |
3 |
-4 |
0 |
-2 |
3 |
1 |
0 |
х2 |
1 |
1/3 |
1 |
2/3 |
2/3 |
1/3 |
0 |
х6 |
1 |
4/3 |
0 |
-1/3 |
-1/3 |
-2/3 |
1 |
базис |
значение |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
Z(x) |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
f(x) |
6 |
0 |
0 |
-3 |
2 |
-1 |
3 |
х2 |
3/4 |
0 |
1 |
3/4 |
3/4 |
1/2 |
-1/4 |
х1 |
3/4 |
1 |
0 |
-1/4 |
-1/4 |
-1/2 |
3/4 |
Искусственные переменные исключены из базиса, т. е. найдено начальное допустимое базисное решение и вспомогательная целевая функция Zmin = 0.
Вычеркнем строку для Z, столбики, соответствующие искусственным переменным и решим исходную задачу:
базис |
значение |
х1 |
х2 |
х3 |
х4 |
f(x) |
6 |
0 |
0 |
-3 |
2 |
х2 |
3/4 |
0 |
1 |
3/4 |
3/4 |
х1 |
3/4 |
1 |
0 |
-1/4 |
-1/4 |
базис |
значение |
х1 |
х2 |
х3 |
х4 |
f(x) |
9 |
0 |
4 |
0 |
5 |
х3 |
1 |
0 |
1/3 |
0 |
0 |
х1 |
1 |
1 |
4/3 |
1 |
1 |
Максимум функции f(x) найден: x* = (1, 0, 1, 0) – точка максимума, а значение целевой функции f(x*) = 9.