Содержание
- 2. Среди универсальных методов решения задач линейного программирования наиболее распространен симплексный метод (или симплекс-метод), разработанный американским ученым
- 3. Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения метода Жордана-Гаусса
- 4. СИМПЛЕКС-МЕТОД ОСНОВАН НА СЛЕДУЮЩИХ СВОЙСТВАХ ЗЛП: Множество всех планов задачи линейного программирования выпукло. Не существует локального
- 5. СИМПЛЕКСНЫМ МЕТОДОМ называется метод последовательного улучшения плана. Название метода возникло от слова «симплекс», что значит «простейший»
- 6. (1) (2) КАНОНИЧЕСКАЯ ФОРМУЛА ЗЛП
- 7. ИДЕЯ МЕТОДА: найти вначале любую угловую точку многогранника решений, т.е. найти x0 опорное решение системы ограничений
- 8. СУЩНОСТЬ МЕТОДА: Пусть известно первое опорное решение системы ограничений, в ней выделены базисные неизвестные x1, x2,
- 9. - опорное решение. Чтобы перейти к новому опорному решению, надо сменить базис. Какой из векторов ввести
- 10. Умножим первое уравнение системы (1) на c1 , второе – на c2 т.д., m-тое уравнение -
- 11. Обозначим, ; ( j = m + 1, m + 2, …, n) тогда кратко или
- 12. КАК ЗАВИСИТ L ОТ ОЦЕНОЧНОГО КОЭФФИЦИЕНТА ∆J? Если все ∆j > 0, то L увеличить нельзя,
- 13. Пусть вводится в базис, тогда из (1) Получаем (5) и помним, что теперь xj ≠ 0,
- 14. КАКАЯ ИЗ БАЗИСНЫХ НЕИЗВЕСТНЫХ x1, x2, …, xm МОЖЕТ ПЕРЕЙТИ В ЧИСЛО СВОБОДНЫХ НЕИЗВЕСТНЫХ, Т.Е. ОБРАТИТСЯ
- 15. 2. Предположим, что существует aij Но если в столбце несколько положительных элементов, то при таком выборе
- 16. КРИТЕРИЙ ОПТИМАЛЬНОСТИ Если для найденного опорного решения найдется хотя бы одна отрицательная оценка ∆j 0, то
- 17. ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ МЕТОД СИМПЛЕКСНЫХ ТАБЛИЦ
- 18. Пусть дана ЗЛП с системой ограничений, состоящей из m линейных неравенств и n неизвестных: Целевая функция
- 19. ЗАДАЧА КАНОНИЧЕСКОЙ ФОРМЫ: (7)
- 20. Для решения задачи целесообразно использовать метод симплекс-таблиц. СОСТАВИМ ЕЁ ТРАФАРЕТ: Таблица 1.
- 21. В первом столбце таблицы (Cб) - коэффициенты целевой функции при базисных переменных. Во втором столбце (Хб)
- 22. В индексной строке записываем оценки: Наибольшая по модулю отрицательная оценка определяет разрешающий столбец. Разрешающую строку определяем
- 23. План не оптимален. Переходим к новой симплекс-таблице, используя метод Жордана-Гаусса: Элементы разрешающей строки в новой таблице
- 24. Приведём к каноническому виду: В качестве примера решим симплекс-таблицей ВЛП
- 25. Составим симплекс таблицу Таблица 2. Разрешающему столбцу соответствует наименьшая оценка = -4. Разрешающую строку найдем по
- 26. Переходим к новой симплекс-таблице по формуле Жордана-Гаусса. Разрешающему столбцу соответствует наименьшая оценка = -1/3. Разрешающую строку
- 28. Скачать презентацию