Условия разрешимости задачи и единственности решения

Таким образом, если область допустимых планов непустая и ограниченная, то для каждой из задач — на максимум целевой функции или на минимум целевой функции, существует оптимальный план.

Если же область неограничена, то дело обстоит по-иному. В этом случае одна из задач (на максимум или на минимум целевой функции) или обе эти задачи могут оказаться неразрешимыми.

Полученные результаты можно сформулировать следующим образом.

Область допустимых планов задачи либо пуста, либо непуста. Если она пуста, то задача неразрешима, поскольку она не имеет даже допустимых планов.

Если область непуста, то она либо ограничена, либо неограниченна. Если область ограничена, то задача имеет решение.

Если же область неограниченна, то задача может иметь решение, а может не иметь его. Все зависит в этом случае от того, ограничена ли область в нужном направлении - в том направлении, в котором необходимо смещать линию уровня целевой функции до ее крайнего положения.

Мы рассмотрели геометрический смысл задачи с двумя переменными. Для задач с тремя переменными можно провести аналогичное рассуждение. Вместо полуплоскостей с граничной прямой нужно будет рассматривать полупространства с граничными плоскостями. Вместо многоугольной области на плоскости - многогранную область в пространстве. Вместе линии уровня на плоскости - плоскость уровня в пространстве. Представление ситуации будет менее наглядным.

Для задач с большим числом переменных наглядность и вовсе будет утрачена. Графический метод решения для таких задач оказывается непригодным. Необходимо использовать уже другие, не геометрические, а аналитические, расчетные методы.

Такие методы существуют. Наиболее известным среди них является так называемый симплекс-метод. Этот метод позволяет решить любую задачу линейного программирования (либо доказать ее неразрешимость). Он лежит в основе разнообразных алгоритмов расчета оптимального плана. Известны многочисленные компьютерные реализации таких алгоритмов. Один из удобных вариантов встроен в Excel. Для проведения соответствующих расчетов следует обратиться в Excel к программе «Поиск решения».

Геометрический подход, изученный нами для задачи с двумя переменными, позволяет не только решать такие задачи, но и глубже понять ход решения задачи с большим числом переменных, в тех ситуациях, когда непосредственная геометрическая наглядность оказывается утраченной.

ПРИМЕР ГРАФИЧЕСКОГО РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Дата добавления: 2015-04-24