yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->4.4. Определение оптимального решения.

Исследование операций

4.4. Определение оптимального решения.

 

Рассмотрим на примере  графический метод определения оптимального решения ЗЛП – max. или  min. значения целевой функции.

 

Пример 4.4.

Найти такие неотрицательные значения переменных, которые удовлетворяют ограничениям

 

 

и оптимизируют функцию цели , т.е. обеспечивают ей максимальное или минимальное значения.

Вводим дополнительные переменные, чтобы преобразовать неравенства в равенства.

 

 

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

 

 

Строим многоугольник допустимых решений (рис. 4.8)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис.4.8

 

Введём в рассмотрение линии уровня функции цели. Линии уровня функции цели – линии, на которых функция цели имеет постоянное значение. В рассматриваемом случае уравнение линий уровня имеет вид . Это параллельные прямые, т.к. коэффициенты при переменных в уравнении не изменяются, а меняется только постоянная. Все они направлены перпендикулярно вектору нормали . Линии уровня обладают тем свойством, что в направлении вектора нормали их величина возрастает, а в противоположном направлении – убывает. Линия уровня, проходящая, через начало координат, будет иметь нулевое значение, проходящая через точку А(0;2) – max, проходящая через точку В(5;0,5) – min.

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

Отметим общие свойства решений ОЗЛП.

1.Оптимальное решение ОЗЛП, если оно существует, не может лежать внутри ОДР, а только на её границах.

2.Если границей ОДР для линии уровня функции цели является угловая точка, то функция цели принимает единственное оптимальное решение.

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

4.ОЗЛП может не иметь решений в следующих случаях:

1.Когда система ограничений несовместна. В этом случае не существует ОДР.

 

 

 

 

 

 

Рис. 4.9.

 

2.Если и существует ОДР, но она не ограничена.

 

 

 

 

 

 

 

Рис. 4.10.

 

 

 

11