Егоров, Казаков Мет. по лин. програм

21

Рис. 1.5.

Целевая функция геометрически представляется (рис. 1.6) прямой, соответствующей произвольно выбранному значению z . Выбирая последовательно увеличивающиеся значе-

ния z (направление увеличения обозначено стрелкой и определяется вектором N , коорди-

натами которого являются коэффициенты целевой функции), можно найти оптимальное ре-

				4		10			1		1
шение x	( x ,	x )			;			( 1		; 3		).
2	1	2	3			3			3		3

Рис. 1.6.

Для получения оптимального решения рассматриваемой задачи линейного программи-

рования достаточно решить систему уравнений 1 и 2 , т.к. искомая опорная точка является пересечением прямых, соответствующих этим ограничениям:

22

2 x1				x2		6 ,					x2 6 2 x1	x1 2 6 2 x1 8
	x1	2 x2				8;
		x			4	, x			10		.
			1				2
				3						3

▲

Обобщая рассмотренный пример, может быть доказана

основная теорема линейного программирования. Линейная целевая функция задачи ли-

нейного программирования достигает своего экстремального (максимального или мини-

мального) значения в угловой точке многогранника решений. Если линейная целевая функция принимает экстремальное значение более чем в одной угловой точке, то она достигает то-

го же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.

Пусть задача линейного программирования задана в двумерном пространстве, т.е. огра-

ничения содержат две переменные:

z c1 x1				c2 x2				min			(1.1)
при ограничениях
a1 1 x1				a1 2 x2				b1 ,
a	2 1	x	1	a	2 2	x	2	b	2	,	(1.2)
...........................
				am 2 x2 bm ,
am 1		x1
		x1 0 ,				x2 0 .					(1.3)

Допустим, что система (1.2) при условии (1.3) совместна и ее многоугольник решений ограничен. Каждое из неравенств (1.2) и (1.3), как отмечалось выше, определяет полуплоскость с граничной прямой: ai 1 x1 ai 2 x2 bi i 1,2,...,m , x1 0 , x2 0 . Ли-

нейная целевая функция (1.1) при фиксированных значениях z является уравнением прямой линии: c1 x1 c2 x2 const . Построим многоугольник решений системы ограничений

(1.2) и график линейной целевой функции (1.1) при z 0 (рис. 1.7).

Тогда поставленной задаче линейного программирования можно дать следующую ин-

терпретацию:	найти точку многоугольника решений, в которой прямая
c1 x1 c2 x2	const - опорная и функция z при этом достигает минимума.

23

Рис. 1.7.

Значения z c1 x1 c2 x2 возрастают в направлении вектора N c1 ,c2 , поэтому

прямую z 0 передвигаем параллельно самой себе в направлении вектора N .

Из рис. 1.7 следует, что прямая z дважды становится опорной по отношению к много-

угольнику решений (в точках A и C ), причем минимальное значение принимает в точке A .

Координаты точки A x1 , x2 находятся решением системы уравнений прямых AB и AE .

Если многоугольник решений представляет собой неограниченную многоугольную об-

ласть, то возможны два случая.

1. Прямая c1 x1 c2 x2 const , передвигаясь в направлении вектора N (максимиза-

ция) или противоположно ему (минимизация), постоянно пересекает многоугольник реше-

ний и ни в какой точке не является опорной к нему. В этом случае линейная целевая функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 1.8).

Рис. 1.8.

24

2. Прямая, передвигаясь, все же становится опорной относительно многоугольника ре-

шений (рис. 1.9, рис. 1.10, рис. 1.11). Тогда в зависимости от вида области линейная целевая функция может быть ограниченной сверху и неограниченной снизу (рис. 1.9), ограниченной снизу и неограниченной сверху (рис. 1.10), либо ограниченной как снизу, так и сверху (рис.

1.11).

Рис. 1.9.

Рис. 1.10.

Рис. 1.11.

25

На выявленной закономерности основывается общий метод решения задачи линейного программирования: для поиска оптимального решения достаточно последовательно рассмат-

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

нию определенного числа уравнений из ограничений задачи линейного программирования.

▼

Пример

На некотором предприятии, выпускающем изделия двух типов, производственная мощ-

ность цеха сборки составляет 100 изделий первого или 300 изделий второго типа в сутки.

Если x1 - количество выпускаемых в сутки изделий первого типа, x2 - второго, то вся про-

дукция цеха в пересчете на изделия второго типа составляет 3 x1 x2 штук в сутки.

Отдел технического контроля в состоянии проверить не более 150 изделий (любого ти-

па) в сутки.

Требуется при этих условиях описать все возможные планы выпуска продукции в сутки,

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

том выбрать план, обеспечивающий предприятию наибольшую прибыль.

Решение

Искомые планы должны удовлетворять следующим условиям:

3 x1 x2				300 ,
	x1		x2	150 ,
	x	1	0 , x		2	0.

Область решений этой системы линейных неравенств будет множеством всех возмож-

ных планов выпуска продукции в сутки.

Построим на плоскости область решений первого неравенства из рассмотренной выше системы линейных неравенств:

3x1 x2 300.

Сначала определяются точки, в которых уравнение пересекает оси координат:

3x1 x2 300,

x1 0, x2 300; x2 0, x1 100.

Затем через них проводится прямая.

26

Чтобы определить полуплоскость, соответствующую неравенству, подставим в него точ-

ку 0;0 .

Если неравенство

3x1 x2 300

выполняется, значит, оно задает ту полуплоскость, в которой находится точка 0;0 . Если не выполняется, значит – другую полуплоскость.

3 0 0 300 - выполняется.

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

	№ п/п	Уравнения		x1	x2
	1	3 x1 x2	300	0	300
				100	0
	2	x1 x2	150	0	150
				150	0

27

Докажем, что одна из угловых точек области решений рассматриваемой системы линей-

ных неравенств будет соответствовать плану выпуска продукции в сутки, обеспечивающему предприятию максимальную прибыль.

Пусть известно, что изделие первого типа стоит вдвое дороже, чем изделие второго типа.

Тогда продажа произведенных за сутки изделий принесет прибыль (целевая функция):

2 x1 x2 c.

Изобразим эту прямую для разных значений числа c .

2 x1	x2		225
2 x1	x	2	200
2 x1 x2		100

С ростом числа c рассматриваемая прямая параллельно смещается “вверх” (по стрелке).

Следовательно, своего наибольшего значения число c (прибыль) достигнет в угловой точке с координатами 75;75 :

2 x1 x2 2 75 75 225 c.

28

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

▲

Вопросы для самопроверки

Что представляет собой математическая модель, необходимая для решения задачи ли-

нейного программирования?

Чем геометрически представляется целевая функция задачи линейного программирова-

ния?

Как геометрически находится оптимальное решение задачи линейного программирова-

ния?

Как аналитически рассчитывается значение оптимального решения задачи линейного программирования?

В чем состоит основная теорема линейного программирования?

Как можно интерпретировать формальную суть задачи линейного программирования?

В чем заключается общий метод решения задачи линейного программирования?

Задания для самостоятельной работы

▼

Пример

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

2 x1 x2 m a x

	при ограничениях
1	x1		x2		2 ,
2	x1		x2		6 ,
3	2 x1	5 x2 2 5 ,
4	x1	0 , x2		0 .

В ответе указать:

1)оптимальное решение x 2 ( x1 , x2 ) ;

2)оптимальное значение целевой функции z .

29

Решение

Строим прямые, соответствующие уравнениям:

1	x1		x2		2 ,
2	x1		x2		6 ,
3	2 x1 5 x2 2 5 ,
4	x1	0 , x2		0 .

Определим пересечение полуплоскостей, соответствующих ограничениям:

1	x1		x2		2 ,
2	x1		x2		6 ,
3	2 x1	5 x2 2 5 ,
4	x1	0 , x2		0 .

Построим прямую, соответствующую целевой функции и проходящую через точки

А 2;0 и Б 4;2 :

30

z A 2 x1 x2 4 , zБ 2 x1 x2 6 .

Судя по направлению увеличения целевой функции z , опорная точка Б является оптимальной.

Координаты точки Б , являющиеся решением задачи, могут быть найдены решением си-

стемы линейных уравнений (1) и (2), т.к. эта точка находится на пересечении соответствую-

щих прямых:

		x1	x2 2 ,
	1

2

x1

x2

6.

Складывая уравнения системы, получим:

2 x1 8,	x1 4.
Подставляя найденное значение x1				4 в любое из этих уравнений, найдем:
4 x2 2,		x2 2,	или 4 x2 6,		x2	2.
Ответ:
1) оптимальное решение x				( x , x		) ( 4 , 2 );
			2	1	2

2) оптимальное значение целевой функции z 2 x1 x2 6 .

▲

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

В ответе указать:

1) оптимальное решение x 2 ( x1 , x2 ) ;

3) оптимальное значение целевой функции z .