Презентация на тему "Варианты ОДР"

Графический метод. Варианты ОДР.

Вопрос 1. Постановка задачи линейного программирования

• (1)
• 2)
• 3)

Вопрос 2. Графический метод решения задачи линейного программирования с двумя переменными.

• Графический метод используется для решения задач с двумя переменными следующего вида:

Алгоритм графического метода решения задач линейного программирования с двумя переменными:

• 1) Построить область допустимых решений.
• 2) Если область допустимых решений является пустым множеством, то задача не имеет решения вследствие несовместности системы ограничений.
• 3) Если область допустимых решений является непустым множеством, построить вектор-градиент целевой функции.

• 4) Произвольную линию уровня, имеющую общие точки с ОДР, перемещаем параллельно самой себе до опорной прямой в направлении вектора-градиента (при решении задачи на максимум) или в противоположном направлении (при решении задачи на минимум).
• 5) Если при перемещении линии уровня по ОДР в направлении, соответствующем приближению к экстремуму целевой функции, линия уровня уходит в бесконечность, то задача не имеет решения вследствие неограниченности целевой функции.

• 6) Если ЗЛП имеет оптимальное решение, то для его нахождения решить совместно уравнения прямых, ограничивающих ОДР и имеющих общие точки с соответствующей опорной прямой. Если целевая функция задачи достигает экстремума в двух вершинах ОДР, то она достигает экстремума также в любой точке, лежащей на отрезке, соединяющем эти две вершины. Задача имеет бесконечное множество оптимальных решений.
• 7) Вычислить значение целевой функции на оптимальном решении.

При решении задач линейного программирования графическим методом возможны следующие случаи:

В этом случае целевая функция достигает своего максимального значения в любой точке отрезка [A;B]; и записывается в виде выпуклой комбинации

Задача линейного программирования не имеет оптимального решения , так как целевая функция не ограничена сверху, если требуется найти максимум целевой функции (или снизу, если требуется найти минимум).

Задача линейного программирования не имеет решения, так как система ограничений противоречива, то есть ОДЗ – пустое множество.

Если ОДЗ состоит из одной точки, то в этой точке целевая функция принимает свое максимальное или минимальное значение