Симплексный метод решения ЗЛП

1. Симплексный метод решения ЗЛП

БПОУ ОО «Сибирский профессиональный колледж»
Симплексный метод
решения ЗЛП
Преподаватель:
Сатеева Д.С.
Омск -2021
Copyright © Wondershare Software

2. Содержание:

Содержание
:
Геометрическая интерпретация симплексного
метода
Симплексный метод
Критерии оптимальности целевой функции
Пример
Company Logo
Copyright © Wondershare Software

3.

Геометрическая интерпретация
симплексного метода
Основная теорема линейного программирования
утверждает, что если ЗЛП имеет оптимальное решение,
то оно соответствует хотя бы одной угловой точке
многогранника решений и совпадает, по крайней мере,
с одним из допустимых базисных решений системы
ограничений. Таким образом, путь решения любой ЗЛП
следующий: перебрать конечное число допустимых
базисных решений системы ограничений и выбрать среди
них то, на котором функция цели принимает оптимальное
решение. Геометрически это соответствует перебору
всех угловых точек многогранника решений. Такой
перебор в конце концов приведет к оптимальному
решению (если оно конечно существует)
Copyright © Wondershare Software

4.

Число перебираемых допустимых базисных решений
можно
сократить,
если
производить
перебор
не
беспорядочно, а с учетом изменений линейной функции, то
есть добиваясь того, чтобы каждое следующее решение было
«лучше» (или по крайней мере, «не хуже»), чем
предыдущее, по значениям линейной функции( увеличение
ее при отыскании максимума , уменьшение – при отыскании
минимума.
Поясним на примере:
Copyright © Wondershare Software

5.

6.

7.

8.

Критерии оптимальности решения
При решении ЗЛП симплексным методом необходимо
пользоваться критериями оптимальности целевой функции.
Критерий оптимальности решения при отыскании
максимума линейной функции: если в выражении
линейной функции через неосновные переменные
отсутствуют положительные коэффициенты при неосновных
переменных, то решение оптимально.
Критерий оптимальности решения при отыскании
минимума линейной функции: если в выражении
линейной функции через неосновные переменные
отсутствуют отрицательные коэффициенты при неосновных
переменных, то решение оптимально.
Copyright © Wondershare Software

9.

Разобрать решение задач из прилагаемого
текстового документа и решить задачу симплексным
методом:
F x1 2 x 2 max
x1 x 2 2,
5 x1 2 x 2 10,
5 x 2 x 5
2
1
Copyright © Wondershare Software

English Русский Правила