Лекция 2. Графический метод решения ЗЛП

Графический метод решения ЗЛП

Если число неизвестных равно 2, то ее можно решить графическим методом. Найти решение Найти решение х=(х₁,х₂)

Макс(мин)Z=C₁X₁+C₂X₂ (1)

Sum(A_ijX_j)<=b_i (2)

X₁,X₂>=0

Каждое из неравенств 2 определяет на координатной плоскости полуплоскость, а система неравенств 2 и 3 в случае ее совместимости – пересечение плоскостей. Это будет выпуклое множество, которое может быть представлено как:

1.Выпуклый многоугольник.

2.Выпуклая неограниченная многоугольная область.

3.Отрезок.

4.Луч.

5.Одна точка.

6.Пустое множество.

Геометрическая интерпретация целевой функции:

Z=C₁X₁+C₂X₂ (1)

При фиксированных значениях Z=Z₀ определяет линию. При изменении Z получим семейство параллельных прямых, называемых линиями уровня. Вектор С=(С₁ , С₂) перпендикулярен каждой из линий уровня. Вектор С показывает направления наибольшего возрастания(убывания) целевой функции.

Если построить на одном рисунке область допустимых решений вектор С и одну из линий уровня, например Z=0, то задача сводится к определению области допустимых решений точки направления вектора С, через которую проходит линия уровня Z макс(мин), соответствующая наибольшему(меньшему) значению функции Z. Если задача рерзрешима могкт представиться следующие случаи:

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

2.Задача имеет бесконечное множество решений(альтернативный оптимум).

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

Х₁

Х₂

Max(min)Z=2X₁+3X₂

X2

1 3

X1

Проверяем каждую вершину.

Zmin()=2*(4/9)+3*(8/9)=32/9

Zmax=2*2+3*4=16

Поиск по сайту: