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

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

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	0			4	0			0	4
	0	4			0	3			0	4

						y
			2
		1
						0									x
								C
		3

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

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

Ответ: Z= –в.

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

при

Решение.

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

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

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

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

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

при

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

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

1:	A	B		2:	A	B		3:	A	B
	7	0			2	0			-5	0
	0	2			0	6			0	4

						y
		1
						0									x
									2

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

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