Наиболее простым и наглядным методом линейного программирования (ЛП) является графический метод. Он применяется для решения задач ЛП с двумя переменными.
Графический метод решения ЗЛП состоит из следующих этапов:
1. Сначала строится многоугольная область допустимых решений (ОДР), соответствующая ограничениям.
2. Далее строится вектор–градиент линейной формы в какой-нибудь точке х0, принадлежащей допустимой области . Координаты вектора можно пропорционально увеличивать или уменьшать, при этом направление вектора не изменяется.
3. Строится прямая , перпендикулярная вектору-градиенту, и передвигается в направлении этого вектора в случае максимизации до тех пор, пока не покинет пределов многоугольной области. В случае минимизации целевой функции, прямую передвигают в направлении противоположном вектору-градиенту. Предельная точка (или точки) области при этом движении и является точкой максимума (минимума) . Если прямая при своем движении не покидает допустимой области, то соответствующий максимум или минимум не существует.
|
|
4. Находятся координаты предельной точки. Для нахождения ее координат достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение , найденное в получаемой точке, является максимальным (минимальным).
Пример.
Решить графическим методом следующую ЗЛП:
f(х1,х2) = (2х1+3х2) → max
х1+3х2 £ 300
х1+х2 £ 150
х1,2 ³ 0
Прямые ограничения означают, что область решений будет лежать в первой четверти Декартовой системы координат.
Этап 1. Определим множество решений первого неравенства. Оно состоит из решения уравнения и строгого неравенства. Решением уравнения служат точки прямой х1+3х2 =300. Построим прямую по двум точкам (0;100) и (300;0).
Множество решений строгого неравенства – одна из полуплоскостей, на которую делит плоскость построенная прямая. Какая из них является искомой, можно выяснить при помощи одной контрольной точки. Если в произвольно взятой точке, не принадлежащей прямой, неравенство выполняется, то оно выполняется и во всех точках той полуплоскости, которой принадлежит контрольная точка, и не выполняется во всех точках другой полуплоскости. В качестве контрольной точки удобно брать начало координат. Подставим значение координат (0;0) в неравенство, получим 0<300, т.е. оно выполняется. Следовательно, областью решения неравенства служит нижняя полуплоскость.
Аналогичным образом построим ОДР второго неравенства.
х1+х2 = 150 Точки (0;150) и (150;0).
х1+х2 < 150, при х1 = х2 = 0 неравенство 0 < 150 выполняется, область решения – нижняя полуплоскость.
|
|
Заштрихуем общую область для всех неравенств, обозначим вершины многоугольника латинскими буквами А, В, С.
Этап 2. Для определения направления движения к оптимуму построим вектор-градиент, соединив его вершину ∆(100;150) с началом координат О (0;0).
Этап 3. Построим прямую (линию уровня), перпендикулярную вектору-градиенту.
Будем передвигать линию уровня до ее пересечения с точкой В. Далее она выходит из ОДР. Следовательно, именно в этой точке достигается максимум целевой функции.
Этап 4. Координаты точки В найдем, решив систему из двух уравнений:
х1+3х2 = 300
х1+х2 = 150
х1 = 75 х2 = 75
Координаты точки А (0;100) и точки С (150,0).
Т.к. координаты точки В равны х1 = 75 и х2 = 75, то максимум ЦФ равен 375.
|
|
|