Решение задач линейного программирования графическим методом

 

Решение задачи линейного программирования графическим методом производится по следующему алгоритму:

1. Интерпретируется система ограничений. Строится область допустимых решений.

2. Строится произвольная линия уровня.

Замечание: При решении ЗЛП графическим методом удобнее всего строить линию уровня при Z=0.

3. Выбирается направление перемещения линии уровня.

Замечание1: Направление перемещения линии уровня выбирается с учетом направления наибольшего изменения функции. Это направление определяется с помощью градиента:

grad Z = =(, )

Если решается задача на max, то выбирается направление вектора градиента (направление вектора ). В противном случае – направление антиградиента (вектора - ).

Замечание 2: С помощью вектора можно построить линию уровня. Она строится перпендикулярно градиенту, через точку (0,0).

4. Перемещается линия уровня, до тех пор, пока не найдено решение ЗЛП.

Замечание 1: При решении ЗЛП возможны следующие случаи:

Рис. 8 Рис. 9.

Рис. 10 Рис. 11

На рис. 8 показан случай, когда минимум и максимум целевой функции найдены и находятся соответственно в точках max и min. Во втором случае (рис. 9) минимум целевой функции существует. Однако область допустимых решений не ограничена сверху, следовательно, максимума у целевой функции нет. В третьем случае (рис. 10) нет ни минимума, ни максимума функции. На рис.11 ЗЛП имеет бесконечно много решений.

Пример1: Решить ЗЛП графическим методом. Найти:

при

Решение.

Найдем градиент: (2;-3).

Построим область допустимых значений. Для этого построим прямые, соответственные ограничениям:

1:	A	B		2:	A	B		3:	A	B
	-6

y

2

x

C

Решение находится, исходя из решения системы:

Тогда: = ; = и max Z= –

Ответ: Z= – в .

Пример 2. Решить ЗЛП графическим методом. Найти:

при

Решение.

Задачи, представленные в канонической форме можно решать графическим методом только в том случае, если разность между порядком и рангом системы ограничений равна 2. В данном случае: 5-3=2.

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

Так как все переменные неотрицательны, то можно составить систему неравенств:

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

Таким образом, ЗЛП имеет вид:

при

Найдем градиент: (1;1).

Построим область допустимых значений. Для этого построим прямые, соответственные ограничениям:

1:	A	B		2:	A	B		3:	A	B
								-5

 

y

x

Область допустимых решений не ограничена сверху. Значит, решений нет.

Ответ: Решений нет.