Содержание
- 2. Симплекс-метод с естественным базисом Симплекс –метод основан на переходе от одного опорного плана к другому, при
- 3. В этом случае каноническая задача линейного программирования должна содержать единичную подматрицу порядка m Тогда очевиден первоначальный
- 4. Рассмотрим задачу, для которой это возможно. Пусть требуется найти максимальное значение функции при условиях Здесь -заданные
- 5. Перепишем ЗЛП в векторной форме: найти максимум функции при условиях Здесь
- 6. Так как , то по определению опорного плана , где последние компоненты вектора равны нулю, является
- 7. План, при котором целевая функция ЗЛП принимает свое максимальное (минимальное ) значение , называется оптимальным Этот
- 8. Признак оптимальности. 1)Опорный план ЗЛП является оптимальным, если для любого .
- 9. 2)Если для некоторого j=k и среди чисел нет положительных, т.е. , то целевая функция ЗЛП не
- 10. 3)Если же для некоторого k выполняется условие , но среди чисел есть положительные, т.е. не все
- 11. Симплекс-таблица
- 12. Симплекс-таблица В столбце Сб записывают коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и
- 13. Здесь , т.е. Значение После заполнения таблицы исходный опорный план проверяют на оптимальность. Для этого просматривают
- 14. 1) Все Тогда составленный план оптимален. 2) для некоторого j и все соответствующие этому j .
- 15. Этот переход осуществляется исключением из базиса какого-нибудь из векторов и включением в него другого. В базис
- 16. Из базиса выводится вектор , который дает наименьшее положительное оценочное отношение для всех , т.е. минимум
- 17. Строка называется разрешающей строкой, элементы этой строки в новой симплекс-таблице вычисляются по методу Жордана-Гаусса, т.е. по
- 18. Элементы i-й строки –по формулам
- 19. Значение нового опорного плана считают по формулам Значение целевой функции при переходе от одного опорного плана
- 20. Процесс решения продолжаем до получения оптимального плана либо до установления неограниченности ЦФ. Если среди оценок оптимального
- 21. Алгоритм применения симплекс-метода 1)Находят опорный план. 2)Составляют симплекс-таблицу. 3)Выясняют, имеется ли хотя бы одна отрицательная оценка.
- 22. 4)Находят направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом , а
- 23. Пример. Решить симплекс-методом ЗЛП
- 24. Решение. Приведем задачу к каноническому виду, введя новые переменные В целевую функцию эти переменные войдут с
- 25. Из коэффициентов при неизвестных и свободных членов составим векторы Единичные векторы образуют единичную подматрицу и составляют
- 26. Составим симплекс-таблицу и проверим план на оптимальность. В нашем примере Для заполнения последней строки таблицы сразу
- 27. Составим теперь нулевую симплексную таблицу
- 28. Таблица 0.
- 29. Определяем разрешающий элемент симплексной таблицы. Т.к. имеется 2 отрицательные оценки, то выбираем ту, что дает максимальную
- 30. Разрешающим элементом является . Значение целевой функции в следующей симплекс-таблице будет равно:
- 31. Элементы направляющей строки в новой таблице вычисляем, деля эту строку на ведущий элемент(в том числе и
- 32. Можно рассчитывать элементы строк методом Жордана-Гаусса, домножая 1-ю строку на (-0,5) и прибавляя ее ко 2-й,
- 33. Элементы 2-ой строки получаем по методу Жордана-Гаусса (или по формулам треугольника)
- 34. Аналогично рассчитываем элементы 3-й строки. Значения нового опорного плана рассчитываем по формулам: После чего заполняем таблицу
- 35. Таблица 1.
- 36. Проверим план на оптимальность. Вычислим симплекс-разности.
- 37. В первом столбце матрицы имеется отрицательная оценка. План не оптимален, но его можно улучшить , включив
- 38. Выводится из базиса вектор , которому соответствует минимальное оценочное отношение 70. Переходим к следующему опорному плану.
- 39. Таблица 2
- 41. Скачать презентацию