 |
 |
 |
 |
|
 |
 |
42
В результате имеем:
Как видно из таблицы Т
(1)
, в столбце b(?
(1)
) содержатся отрицательные элементы b1(?
(1)
) = - 1/3<0), то
есть базис
?
(1)
={
a
5
,
a
1
,
a
3
} не является оптимальным, но в то же время легко убедиться, что он
обладает свойствами сопряженного базиса. Отрицательный элемент в b(?
(1)
) является единственным,
поэтому номер столбца, выводимого из базиса, определяется однозначно —
r =
1 и N1(?
(1)
)=5. Далее
рассматриваем строку a1(?
(1)
) = (0, -1/6, 0, -1/6, 1). В ней имеются отрицательные элементы. Вычисляем
?2 =42:(-(-1/6))=252, ?
4
=38:(-(-1/6))=228. ?2> ?
4
, следовательно, номер столбца, вводимого в базис — l =
4. Осуществляем преобразование и получаем симплекс-таблицу T
(2)
.
Поскольку b(?
(2)
)
>0, то достигнутый базис N(?
(2)
)
=
{4,1,3} является оптимальным. Из Т
(2)
можно
выписать оптимальный план х* =
(6, 0, 32/3, 2, 0) и соответствующее ему значение целевой функции
f(x*)= 444.
КЛЮЧЕВЫЕ ПОНЯТИЯ
Общая задача линейного программирования (ОЗЛП).
Каноническая задача линейного программирования (КЗЛП).
Допустимый план.
Оптимальный план.
Первая геометрическая интерпретация ЗЛП.
Базисное решение ЗЛП.
Вторая геометрическая интерпретация ЗЛП.
Вырожденный и невырожденный план ЗЛП.
Симплекс-метод — метод последовательного улучшения плана.
Критерий оптимальности допустимого базисного плана.
Метод минимизации невязок.
Модифицированный симплекс-метод — вычислительная
схема, связанная с преобразованием
обратных матриц.
Двойственная задача линейного программирования.
Симметричность отношения двойственности.
Теоремы двойственности.
Экономическая интерпретация двойственных оценок.
Параметрическая устойчивость решения ЗЛП.
Двойственный симплекс-метод — метод последовательного уточнения оценок.
Сопряженный (двойственно допустимый) базис.