2. Лекции Практические и лабораторные занятия
жүктеу/скачать 0,77 Mb.
|
Рис.1. Построение ОДЗЧтобы графически определить, по какую сторону от граничной прямой располагается полуплоскость, содержащая Неравенства x10, x20, также соответствуют полуплоскостям, одна из которых расположена справа от оси ординат, а другая - над осью абсцисс (рис. 1). Выделив полуплоскости, содержащие решения, удовлетворяющие неравенствам, входящим в рассматриваемую систему, мы определим область, в которой находятся решения, удовлетворяющие всем ограничениям, входящим в рассматриваемую систему неравенств. Именно эта область и есть область допустимых решений задачи. В общем случае область допустимых решений систем неравенств (1) и (2) может быть: пустой, что означает несовместимость систем неравенств: одной точкой: выпуклым многоугольником: неограниченной выпуклой многоугольной областью: Х2 Рассмотренные примеры позволяют сделать следующий вывод: область допустимых решений системы неравенств может быть пустой, одной точкой, выпуклым многоугольником или неограниченной выпуклой многоугольной областью. На втором этапе формируется графическое изображение целевой функции. Уравнение: c1 x1+c2x2 =L при фиксированном значении L определяет прямую, а при изменении L — семейство параллельных прямых с параметром L. Вектор C=(c1, c2), перпендикулярный ко всем этим прямым, показывает направление возрастания параметра L. Так, на рис. 2 показаны прямые, соответствующие уравнению 2x1+3x2=L при L=-3, 0, 3, 9. Рис.2. Графическое изображение целевой функции Для всех точек, лежащих на одной из этих прямых, функция F принимает одно определенное значение, равное соответствующему значению L. Поэтому рассматриваемые прямые называются линиями уровня для параметра L. Важное свойство линий уровня в том, что при их параллельном смещении в одном направлении уровень (значение L) только возрастает, а при смещении в другом — только убывает. Построим, для рассмотренного выше примера линии уровня и определим направление их возрастания. Чтобы построить вектор С=(с1,с2), можно использовать следующий прием: по оси X1 откладывается значение первой компоненты вектора с1=2, а по оси Х2 — значение второй компоненты с2=3. По найденным координатам строим прямоугольник и находим направление возрастания вектора С. Затем перпендикулярно вектору С строим линии уровня. Построив на одном рисунке (рис. 3) область допустимых решений, вектор С, и перпендикулярную ему одну из линий уровня, можно путем ее параллельного перемещения в направлении, указанном вектором С (или в противоположном), определить точку в области допустимых значений, которая доставляет максимум или минимум целевой функции. На рис. 3 видно, что в крайнем положении линия уровня проходит через (.) В. При дальнейшем ее перемещении она уже не будет иметь общих точек с областью допустимых решений. Таким образом, искомое оптимальное решение, которое графически соответствует координатам (.)В, можно найти путем совместного решения системы двух уравнений, соответствующих граничным прямым АВ иВД. Если при тех же исходных данных требовалось бы достичь минимума функции F, то, очевидно, линию уровня пришлось бы перемещать в направлении, противоположном вектору С. В этом случае оптимальное решение, соответствующее минимуму функции F, определялось бы координатами точки (.) 0. Рис. 3. Определение оптимального решения графическим методом В зависимости от вида области допустимых решений и положения линий уровня возможны следующие случаи: ЗЛП имеет единственное решение ЗЛП имеет альтернативный оптимум ЗЛП имеет минимум и не имеет максимума ЗЛП не имеет решения жүктеу/скачать 0,77 Mb. Достарыңызбен бөлісу:
|