Содержание
- 2. Теорема 2 Если исходная задача решается на максимум, то в – неотрицательные, оптимальное решение исходной задачи.
- 3. Теорема 3 Если опорный план ЗЛП не вырожден и такое, что в k-ом столбце системы ограничений
- 4. Структура симплекс таблицы
- 5. Методы контроля: 1. Z-оценки при базисных переменных равны нулю 2. Значения правой части всегда неотрицательны 3.
- 6. Пример: Составим симплекс-таблицу:
- 8. Скачать презентацию
Теорема 2 Если исходная задача решается на максимум, то в
Теорема 2 Если исходная задача решается на максимум, то в
оптимальное решение исходной задачи.
то такое опорное решение является оптимальным.
Теорема 1 Пусть исходная задача решается на минимум, тогда если для некоторого опорного решения все z-оценки
получаем
случае, когда все
неположительные,
Теорема 3 Если опорный план ЗЛП не вырожден и
такое, что
Теорема 3 Если опорный план ЗЛП не вырожден и
такое, что
k-ом столбце системы ограничений есть хотя бы
одно положительное число, т.е. не все
, то существует
, что
, где x – исходное
Теорема 4 Если опорное решение ЗЛП не вырождено и
и в k-ом
столбце системы ограничений нет ни одного положительного числа, т.е. все
, то целевая функция
не ограничена на ОДР.
такое опорное решение
опорное.
Структура симплекс таблицы
Структура симплекс таблицы
Методы контроля:
1. Z-оценки при базисных переменных равны нулю
2. Значения правой
Методы контроля:
1. Z-оценки при базисных переменных равны нулю
2. Значения правой
3. Значение целевой функции на каждом шаге не ухудшается.
Зацикливание
Зацикливание может возникать при наличии вырожденного опорного решения. Выражается в том, что значение целевой функции на следующем шаге не меняется.
Пример:
Составим симплекс-таблицу:
Пример:
Составим симплекс-таблицу: