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

Графический метод можно использовать для решения задачи НП, которая содержит две переменных х1 и х2, например задачи следующего вида:
Z = f(x1, x2) → min (max);
gi(x1, x2) bi, .

Чтобы найти ее оптимальное решение, нужно выполнить следующие действия:

  1. Найти ОДР, определяемую ограничениями задачи. Если окажется, что эта область пуста, то это означает, что задача не имеет решения.
  2. Построить семейство линий уровня целевой функции f(х1, х2) = C при различных значениях числового параметра С.
  3. При решении задачи на минимум определить направление убывания, а для задачи на максимум — направление возрастания линий уровня ЦФ.
  4. Найти точку ОДР, через которую проходит линия уровня с наименьшим в задаче на минимум (соответственно, наибольшим в задачи на максимум) значением параметра С. Эта точка будет оптимальным решением. Если ЦФ не ограничена снизу в задаче на минимум (сверху — в задаче на максимум), то это означает, что задача не имеет оптимального решения.
  5. Найти координаты точки оптимума и определить в ней значение ЦФ.

Отметим, что в отличие от задачи ЛП точка оптимума в задаче НП не обязательно находится на границе ОДР. Ею также может быть внутренняя точка этого множества.

Пример.

см. также Решение задачи безусловной оптимизации, Решение классической задачи условной оптимизации.

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

загрузка...