Программирования

Особые случаи решения задач линейного

Схема решения задачи графическим методом

1. Записывают уравнения граничных прямых.

2. Строят графики граничных прямых на плоскости.

3. Выделяют область решений для каждого ограничения задачи.

4. Строят область допустимых решений для системы ограничений.

5. Строят график линии уровня целевой функции и определяют направление ее наискорейшего возрастания.

6. Определяют точку экстремума целевой функции.

7. Вычисляют значение целевой функции в полученной точке.

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

1 З а д а ч а и м е е т е д и н с т в е н н о е р е ш е н и е.

Граница допустимой области представляет собой выпуклый многоугольник. Максимум целевой функции достигается в (·) D, минимум – в (·) А (рисунок 1.2).

Рисунок 1.2 – Задача имеет единственное решение

2 Задача имеет бесконечное множество решений

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

Рисунок 1.3 – Задача имеет бесконечное множество решений

3 Ц е л е в а я ф у н к ц и я н е о г р а н и ч е н а.

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

Рисунок 1.4 – Целевая функция не ограничена

4 С и с т е м а о г р а н и ч е н и й н е с о в м е с т н а

Не существует ни одной точки, удовлетворяющей всем ограничениям одновременно, т.е. область допустимых планов пуста. Решения не существует (рисунок 1.5).

Рисунок 1.5 – Система ограничений не совместна

Дата добавления: 2014-11-18