referat-web.com Бесплатно скачать - рефераты, курсовые, контрольные. Большая база работ.
Симплексный метод
Задача 1.
Решить задачу линейного программирования симплексным методом.
Вариант 3.
Найти наибольшее значение функции f(X) = - x1 - x2 + 2x3 при ограничениях
2x1 + x2 + x3 £ 2
x1 - x2 + x3 £ 1,
xj ³ 0, j = 1, 2, 3.
Решение.
Приведем задачу к каноническому виду, вводя дополнительные неотрицательные переменные x4,5 ³ 0.
f(X) = - x1 - x2 + 2x3 ® max
2x1 + x2 + x3 + x4 = 2
x1 - x2 + x3 + x5 = 1,
xj ³ 0, j = 1, 2, 3, 4, 5.
Каноническая задача имеет необходимое число единичных столбцов, т. е. обладает очевидным начальным опорным решением.
Очевидное начальное опорное решение (0; 0; 0; 2; 1).
Решение осуществляется симплекс-методом с естественным базисом. Расчеты оформим в симплекс-таблицах
| Номер симплекс-таблицы | Базис | Cj Ci | B | -1 | -1 | 2 | 0 | 0 | Q |
A1 | A2 | A3 | A4 | A5 | |||||
| 0 | A4 | 0 | 2 | 2 | 1 | 1 | 1 | 0 | 2:1 = 1 |
A5 | 0 | 1 | 1 | -1 | 1 | 0 | 1 | 1:1 = 1 | |
j | - | 0 | 1 | 1 | -2 | 0 | 0 | ||
| 1 | A4 | 0 | 1 | 1 | 2 | 0 | 1 | -1 | 1:2 = 1/2 |
A3 | 2 | 1 | 1 | -1 | 1 | 0 | 1 | ||
j | - | 2 | 3 | -1 | 0 | 0 | 2 | ||
| 2 | A2 | -1 | 1/2 | 1/2 | 1 | 0 | 1/2 | -1/2 | |
A3 | 2 | 3/2 | 3/2 | 0 | 1 | 1/2 | 1/2 | ||
j | - | 5/2 | 7/2 | 0 | 0 | 1/2 | 3/2 |