Общие рекомендации к графическому решению задач лп

1. Графически могут решаться:

а) задачи, заданные в произвольной форме, содержащие не более

двух переменных;

б) задачи, заданные в канонической форме с числом свободных

переменных 

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

2. Основной формой для графического решения является 1-й тип

задач. Поэтому, если встречается 2-й или 3-й тип задач, то предварительно их модель должна быть приведена к 1-му типу, а именнно :

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

3. Решение задачи 1-го типа выполняется в два этапа.

Этап 1 -построение области допустимых решений.

Этап 2 - нахождение в допустимой области оптимального решения.

4. При построении области допустимых решений может встретиться

один из следующих трех случаев:

а) пустая область;

б) выпуклый многоугольник;

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

В случае а) задача не имеет решения из-за несовместимости системы ограничений в области допустимых решений.

В случае б) задача всегда имеет оптимальное решение.

В случае в) в зависимости от направления вектора В (вектор

коэффициентов целевой функции L ) задача может иметь или не иметь

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

5. Если оптимальное решение существует, то возможен один из

трех исходов:

а) оптимальное решение единственное и совпадает с одной из

вершин области;

б) оптимальные решения соответствуют всем точкам отрезка, соединяющего две вершины области;

в) оптимальные решения соответствуют всем точкам допустимого

луча, исходящего из вершины области.

Пример

Решить графически задачу ЛП, заданную в канонической форме:

Число уравнений задачи m = 3, число неизвестных n = 5 . Тогда

n - m = 2 и задача может быть сведена к задаче на плоскости относительно свободных переменных.

Возьмем в качестве базисных переменные

и выразим их через свободные (небазисные) переменные:

По условию (10) переменные могут принимать только неотрицательные значения, т.е. допустимой областью задачи ЛП (8)-(10) будет область, определяемая условиями (10)-(11),или

Чтобы получить задачу ЛП относительно свободных переменных

в целевую функцию (8).В результате получим

Задача (12), (13) эквивалентна задаче (8)-(10), поэтому решая графически задачу (12), (13), получим решение задачи (8)-(10).

Этап 1. Построение допустимой области.

Каждое из неравенств (12) определяет некоторую полуплоскость

Подставляя значения

в это неравенство, получим 0> - 2, значит, координаты (0,0) удовлетворяют первому неравенству (12) и область решений этого неравенства включает начало координат. Аналогично определяют полуплоскости остальных неравенств (12).

На рис. 7 прямые, соответствующие условию

Получим допустимую область M - выпуклый пятиугольник ОАBСД.

Этап 2. В допустимой области М находим оптимальное решение.

Строим прямую

и определяем направление возрастания функции

Перемещая прямую L параллельно самой себе в направлении вектора C

до тех пор, пока она будет сохранять общие точки с областью допустимых решений, найдем, что в крайнем возможном положении прямая L пройдет через точку В = x* . Этому положению прямой L соответствует значение L* (положение прямой L= L* показано пунктиром).

Для нахождения координат точки x* необходимо совместно решать

систему уравнений граничных прямых (4),(5), на которых лежит точка

x* :

В результате получим искомое оптимальное решение x*=(4,1) .

Подставляя значения  в целевую функцию и в

равенства (11), получим оптимальное значение целевой функции

L =4 - 1= 3 и оптимальное решение

Еще несколько примеров.

1. Допустимое и оптимальное решение существует

2. Пустая допустимая область

3. Неограниченная допустимая область

а) Оптимальное решение существует и единственное

b) целевая функция неограничена на допустимой области

Алгоритм решения ЗЛП графическим методом.

1) Записывают уравнения прямых, соответствующих ограничениям (3.3.4), и строят их на плоскости x₁ox_3.

2) Определяют области, в которых выполняются ограничения задачи. Для этого выбирают произвольную точку на плоскости х₁ох₂ и подставляют ее координаты в первую часть одного из неравенств. Если неравенство верно, то искомая полуплоскость находится с той же стороны от прямой, что и точка; в противном случае искомая полуплоскость лежит с противоположной стороны от прямой. Эти действия последовательно выполняются для всех неравенств (3.3.4).

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

4)  Определяют направление возрастания (убывания) целевой функции f. Это можно сделать двумя способами. Можно построить вектор-нормаль  , его направление показывает направление возрастания функции f, и противоположном направлении функция убывает. Можно просто построить две линии уровня функции f = K₁; f = K₂; (K₁, K₂ – произвольные константы, K₁  K₂), и по их расположению определить направление возрастания (убывания) функции.

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

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

Возможны следующие варианты областей допустимых решений (рис. 3.2):

 

Рис. 3.2. Варианты областей. а – область допустимых решений  – замкнутое множество (многоугольник); б – область допустимых решений – открытое множество; в – область допустимых решений – пустое множество (система ограничений (3.18) несовместна);  г – область допустимых решений состоит из единственной точки А

На рис. 3.2 показаны варианты пересечения линии уровня целевой функции с областью допустимых решений. Может быть единственное решение – точка В, бесконечно много решений – отрезок CD (рис. 3.2, а), максимальным (минимальным) значением целевой функции может быть бесконечность (рис. 3.2, б). Область ограничений несовместимо (допустимых решений нет, рис. 3.2, в). И может быть только одна допустимая точка (рис. 3.2, г)