Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»


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


1)    ограниченный выпуклый многоугольник (рис. 2.1, а);


2)    неограниченный выпуклый многоугольник (рис. 2.1, б);


3)    пустая область. В этом случае задача не имеет решения из-за несовместимости системы ограничений в области допустимых решений (рис. 2.1, в).


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


а)    б)    в)



представляет собой линию уровня, которую можно перемещать в направлении градиента


grad f = ^—;    I = |с1; с2 } при поиске максимума или антиградиента — grad f при поиске ми-


I 0x1 0x2 I


нимума до пересечения с крайней точкой (множеством точек) многоугольника ограничений. Координаты любой крайней точки есть оптимальное решение задачи линейного программирования. На втором этапе графического решения могут быть получены следующие результаты:


1)    оптимальное решение единственное и совпадает с одной из вершин допустимой области (рис. 2. 2, а);


2)    оптимальное решение неединственное, имеется бесконечное множество решений. Оптимальные решения соответствуют всем точкам отрезка, соединяющего две вершины допустимой области (рис. 2.2, б);


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

Рис. 2.2


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

Скачать в pdf «Экстремальные модели менеджмента и экономики»