Содержание
- 2. Введение Рассмотрим следующую задачу линейного программирования (ЗЛП):
- 3. Приведем рассматриваемую ЗЛП к каноническому виду: или
- 4. Рассмотрим расширенную матрицу системы линейных уравнений: Матрица содержит единичную подматрицу порядка 3 и следовательно, определяет базисное
- 5. Так как элементы (n+1=6)-го столбца матрицы системы не являются неотрицательными, то она не является К-матрицей ЗЛП.
- 6. В чем отличие двойственного симплекс-метода от обычного?? При решении задачи симплекс-методом текущее базисное решение является допустимым,
- 7. КЗЛП имеет вид:
- 8. Р-матрица. Определение Р-матрицей КЗЛП (1) –(3) называется расширенная матрица системы линейных уравнений, равносильной системе (2), содержащую
- 9. Условие перехода от одной Р-матрицы ЗЛП к другой Пусть известна Р-матрица , определяющая псевдоплан Условия перехода
- 10. Теорема 1: Пусть и в строке матрицы есть хотя бы один отрицательный элемент. Тогда с помощью
- 11. Теорема 2: Пусть и в строке матрицы нет ни одного отрицательного элемента. Тогда множество планов Р
- 12. Теорема 3: При переходе от матрицы к матрице целевая функция изменяется в соответствии с формулой: откуда
- 13. Алгоритм Р-метода Будем считать, что известна исходная Р- матрица задачи линейного программирования, определяющая исходный псевдоплан: В
- 14. Рассмотрим алгоритм S-ой итерации метода последовательного уточнения оценок. В начале S-ой итерации имеем Р-матрицу задачи линейного
- 15. ШАГ 2. Если , то псевдоплан является оптимальным опорным планом, а есть оптимальное значение линейной формы
- 16. ШАГ 3. Если то задача линейного программирования не имеет решения (множество планов Р пусто), иначе переходим
- 17. ШАГ 5. Вычисляем компоненты вектора ШАГ 6. Производим один шаг метода Жордана-Гаусса с направляющим элементом .
- 18. Решим задачу, которую мы начали пешать в начале презентации. Результаты решения приведены в симплекс-таблице.
- 19. Решим следующую ЗЛП:
- 20. Приводим ЗЛП к каноническому виду
- 21. Т.К. расширенная матрица системы линейных уравнений является Р-матрицей. Следовательно, к решению данного ЗЛП применим Р-метод.
- 22. Решим задачу, которую мы начали решать в начале презентации. Результаты решения приведены в симплекс-таблице.
- 24. Скачать презентацию