Математическая экономика

обходимо и достаточно, чтобы ранг матрицы системы А был равен рангу расширенной матрицы этой системы Ap , где

a11		… a1n				a11		… a1n b1
					;
A =						Ap =				.
am1			amn			am1			amn bm

Напомним, что ранг матрицы – это наибольший порядок отличных от нуля миноров данной матрицы. Это означает, что если ранг матрицы равен r , то в матрице имеется хотя бы один отличный от нуля минор порядка r , но всякий минор порядка большего чем r равен нулю. При этом ранг матрицы равен наибольшему числу линейно независимых строк (или столбцов) матрицы. Ясно, что r не превышает наименьшего из значений n

и m.

В дальнейшем будем считать, что указанное выше условие совместности системы (2.2) выполнено и ранг матрицы A = AP обозначать r .

Для совместной системы возможны два случая.

1. Ранг системы равен числу неизвестных, т.е. r = m. Тогда система

(2.2) имеет единственное решение x = xo . Если все компоненты xio этого

решения неотрицательны, то ОДР состоит из одной точки xo . Она и является решением рассматриваемой КЗЛП. Этот случай интереса не представляет.

2. В случае, когда r < n , система (2.2) имеет бесконечное множество решений. Его образуют наборы значений переменных ( x1,..., xn ), в которых (n – r) переменных, называемых свободными, принимают любые значения, а остальные r переменных, называемых базисными, определяются в виде линейной комбинации соответствующих значений свободных переменных.

В указанном бесконечном множестве решений системы (2.2) нужно выделить образующее ОДР подмножество тех решений, в которых все переменные неотрицательны. Если оно не окажется пустым, то в нем и следует искать решение x , при котором целевая функция (2.1) принимает наименьшее значение.

Учитывая изложенное, будем далее рассматривать только КЗЛП, в которых число r линейно независимых уравнений-ограничений меньше числа n переменных xi .

31

§2.2. Графическое решение задач ЛП

Втех случаях, когда в поставленной задаче n = r +1 или n = r + 2, ее

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

Пример. Найти значения переменных x1,..., x5 , при которых целевая

	функция
	y = x1 + x2 + x3 + 4x4			(2.17)
	принимает наименьшее значение и выполняются условия:
	− x1 + 2x2 + x4 = 2;	x2 + x5	= 6;	(2.18)
	− x2 + x3 + x4 = 4;	xi ≥ 0 (i =	1,...,5).

Решение. Данная задача является КЗЛП, в ней n = 5, r = 3 . Так как n – r = 2, то две переменные нужно выбрать в качестве свободных, а остальные выразить через них. В данном случае удобно взять в качестве свободных переменных x2 и x4 , тогда остальные переменные непосредствен-

но выражаются через них из системы уравнений (2.18):

				x1 = −2 + 2x2 + x4;			x3 = 4 + x2 − x4;	x5 = 6 − x2.		(2.19)
							Рассмотрим плоскость с ко-
		12	х4				ординатами x2 , x4 (рис. 2.1). На
						D	ней можно наглядно интерпрети-
10							ровать условия-ограничения зада-
8							чи.
6						С=50	Условию		x4 ≥ 0	соответст-
4			С				вует множество точек верхней по-
				ОДР			луплоскости,	а	x2 ≥ 0	– правой
2			В
							полуплоскости;		обоим	условиям
							соответствует 1-й квадрант этой
0			А	2 4	6	Е	х2 плоскости. Отметим его штрихов-
						8	кой на рис. 2.1.
				С=Сmin			Рассмотрим теперь условие
							x1 ≥ 0 . Используя первое уравне-
				Рис. 2.1			ние из системы (2.19), получаем:
							−2 +2x2 + x4 ≥0		или x4 ≥2 −2x2.
		Равенству x4 = 2 − 2x2 соответствует прямая, проходящая через точ-
ки ( x2 = 0 ,				x4 = 2 )	и ( x4 = 0 , x2 =1). Неравенству x4 ≥ 2 − 2x2					соответст-

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

32

Аналогично рассматриваем остальные условия:

x3 ≥ 0;	4 + x2 − x4 ≥ 0; x4 ≤ 4 + x2 ;
x5 ≥ 0;	6 − x2 ≥ 0;	x2 ≤ 6.

Таким образом, каждому неравенству xi ≥ 0 на плоскости x2 0x4 соответствует множество точек некоторой полуплоскости. По условиям задачи должны выполняться все неравенства xi ≥ 0 , i = 1, 2,…, 5. Значит, на плоскости нужно выделить те точки (если они существуют), которые принадлежат всем полученным полуплоскостям. В рассматриваемом случае множество таких точек ограничено многоугольником АВСDЕ (см. рис. 2.1).

В каждой точке, принадлежащей границе или внутренней области АВСDЕ, свободные переменные x2 и x4 , а также определяемые соотношениями (2.19) базисные переменные x1, x3, x5 удовлетворяют всем условиям – ограничениям данной КЗЛП и, следовательно, они образуют область допустимых решений (ОДР) (см. рис. 2.1).

Для решения поставленной задачи теперь нужно в полученной ОДР отыскать такую точку, в которой целевая функция принимает наименьшее значение. Для этого подставим выражения (2.19) в ЦФ (2.17). В результате получаем

y = (−2 + 2x2 + x4 ) + x2 + (4 + x2 − x4 ) + 4x4 = 2 + 4x2 + 4x4 .

Рассмотрим множество точек ( x2 , x4 ), для которых целевая функция принимает одно и то же значение y = C. Геометрическое место таких точек образует линию равного уровня ЦФ. Найдем уравнение этой линии:

C = 2 + 4x2 + 4x4 или x4 = C 4− 2 − x2.

Оно показывает, что линии равного уровня ЦФ в рассматриваемом случае представляют собой прямые. Такая линия для С = 50 пунктиром изображена на рис. 2.1. При различных значениях С наклон прямых не меняется, причем уменьшению С соответствует смещение этих прямых вниз.

Отыскание в ОДР точки, в которой целевая функция принимает наименьшее значение, сводится к перемещению прямой y = C без изменения наклона в сторону убывания y (в рассматриваемом случае – вниз) до тех пор, пока эта прямая не достигнет крайней точки (в данном случае такой является точка А (см. рис. 2.1)). Координаты этой точки соответствуют ис-

33

комым значениям свободных переменных: x20 =1; x40 = 0 . Используя их в выражениях (2.19), получим искомые значения остальных (базисных) переменных: x10 = 0; x30 = 5 ; x50 = 5 .

Геометрическое истолкование рассмотренной задачи ЛП подсказывает следующие основные свойства решений КЗЛП общего вида (строгое доказательство этих свойств см., например, в [3, 15, 26]).

1. Решение КЗЛП, если оно существует, всегда будет на границе ОДР, представляющей собой выпуклый многогранник в (n – r)-мерном пространстве свободных переменных. Это решение обычно получается в одной из вершин ОДР, тогда оно единственное. При этом по крайней мере n – r переменных равны нулю. В вырожденном случае вершине ОДР может соответствовать более чем n – r переменных, равных нулю. Такой случай иллюстрируется рис. 2.2 (т. А).

2. Искомое оптимальное решение КЗЛП может оказаться не единственным. Такой случай показан на рис. 2.3. Здесь прямая, соответствующая y = C = const, параллельна грани АВ. При этом каждая точка грани АВ будет давать одно и то же значение ЦФ, являющееся наименьшим возможным значением для данной задачи.

А

х2

х2

х5=0

А

х4=0

В

х6 = 0

ОДР

ОДР

K

х7=0

х1

х1

0

0

х3=0

L

Рис. 2.3

Рис. 2.2

3. КЗЛП может не иметь решения в двух случаях:

а) когда ОДР – пустое множество (получающаяся система неравенств оказывается противоречивой (рис. 2.4, а);

б) ОДР не ограничена и оказывается возможным неограниченное уменьшение целевой функции (рис. 2.4, б).

34

х2

х2

х1	у=С	х1
0		0
		1
а)		б)

Рис. 2.4

Рассмотренные свойства решений ЗЛП лежат в основе алгебраического подхода к решению задач ЛП, реализуемого в так называемом сим- плекс-методе.

§ 2.3. Алгебраическое решение задач ЛП. Сущность симплекс-метода

Рассмотрим некоторую задачу ЛП вида (2.6). Например, x1,..., x5 , при которых функция

y = 63 + x1 + 2x2 + 2x3 + 4x4 + x5

принимает наименьшее значение и выполняются условия:

x1 + 4x2 + 4x4	= 24;	x1	+ x3 + x 5=9;
2x1 +3x2 + x3	+ 4x4 = 28;	xi	≥ 0.

найти

(2.20)

(2.21)

Выше было установлено, что решение такой задачи получается в одной из вершин ОДР. Кроме того, отмечалось, что любой вершине ОДР соответствует комбинация переменных x1,..., xn , в которой ( n − r ) переменных равны нулю, а остальные переменные неотрицательны. Такая комбинация называется опорным решением или опорным планом. Найдем одну из таких комбинаций для рассматриваемой задачи. В ней n = 5 , r = 3 , поэтому выбираем n −r = 2 переменных, например, x1 и x2 в качестве свободных, а остальные выражаем через них из системы (2.21). Для этого x4

выражаем из 1-го уравнения: x4 = 6 − 14 x1 − x2 , полученное соотношение

подставляем во 2-е уравнение и получаем x3 = 4 − x1 + x2 . Используя этот результат, из последнего уравнения системы (2.21) находим x5 = 5 − x2 .

35

Подставив выражения для x3, x4 , x5 :

	x	3	= 4 − x	+ x	2	; x	4	= 6 −	1	x − x	2	;	x	5	= 5 − x	2	(2.22)
									4
			1							1
	в (2.20), получаем					y =100 − 2x1 − x2 .											(2.23)

Положим, что в (2.22) свободные переменные равны нулю, в результате найдем следующую комбинацию значений переменных:

x1 = 0; x2 = 0; x3 = 4; x4 = 6; x5 = 5.

(2.24)

Поскольку в ней n − r переменных равны нулю, а остальные неотрицательны, то (2.24) является опорным решением рассматриваемой КЗЛП. Возникает вопрос – является ли оно оптимальным решением. Анализируя выражение для целевой функции (2.23), видим, что соответствующее решению (2.24) значение этой функции y =100 не является наименьшим

возможным значением, так как заменяя x1 = 0 или x2 = 0 некоторыми по-

ложительными величинами, можно уменьшить это значение.

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

тается свободной (она будет по-прежнему равной нулю).

Возникает вопрос – какую переменную из x3, x4 , x5 перевести в свободные и насколько можно увеличить переменную x1. Так как при увеличении x1 ЦФ пропорционально x1 уменьшается, то желательно было бы придать x1 как можно большее значение. Но изменение x1 приводит к из-

менению базисных переменных в соответствии с (2.22). Получаемые из (2.22) соотношения

	x	3	= 4	− x	;	x	4	= 6 −	1	x ;	x	5	= 5	(2.25)
									4
				1						1

показывают, что при чрезмерном увеличении x1 переменные х3 и х4 мо-

гут принять недопустимые отрицательные значения. Анализируя (2.25), видим, что предельно допустимое увеличение x1 , при котором x3 умень-

шается до нуля, равно x1 = 4 /1 = 4 , аналогично для x4 получаем	«крити-
ческое» значение x1 = 6 /(1/ 4) = 24.
Увеличивая x1 от 0 до 4, находим вместо (2.24) новое опорное реше-
ние:
x1 = 4; x2 = 0; x4 = 5; x3 = 0; x5 = 5,	(2.26)
при этом y =100 − 2 + 4 = 92.

36

Найдем соотношения, связывающие отличные от нуля переменные x1 , x4 , x5 с переменными x2 и x3 , получившими нулевые значения. Для этого выразим из 1-го уравнения системы (2.22) x1 и полученное соотношение подставим в остальные уравнения (2.22) и ЦФ (2.23). В результате получим:

x1 = 4 + x2 − x3;							x5 =5 − x2;		(2.27)
x	=5 −	5 x		+	1 x ;		y =92 −3x	+ 2x .
4		4	2		4	3	2	3

Анализируя (2.27), видим, что возможно дополнительное уменьшение ЦФ за счет увеличения x2 , так как коэффициент при x2 является отрицательным. Рассматривая соотношения, входящие в (2.27), устанавливаем, что увеличение x2 «неопасно» для x1 , так как переменная x1 увеличивается, а для x4 и x5 «опасно», так как коэффициенты при x2 в уравнениях для x4 и x5 отрицательны. Определяя отношения свободных членов к коэффициентам при x2 в этих уравнениях, находим допустимое увеличение пере-

менной x2 :
по x	4	: xдоп =5/(5/ 4) = 4; по x		: xдоп =5/1 =5.	(2.28)
		2	5	2
Принимая наименьшее из этих значений, увеличиваем x2					от 0 до 4.
В результате вместо опорного решения (2.26) получаем:
x1 =8; x2 = 4;			x3 = 0; x4 = 0; x5 =1.		(2.29)

Выразим из 2-го уравнения системы (2.27) переменную x2 , ставшую ненулевой, и полученное соотношение подставим в остальные уравнения этой системы:

x	= 4 − 4 x		+ 1 x ;		x	=8 − 4 x		− 4 x			;	x		=1+	4 x		−	1 x		,	(2.30)
2	5	4	5	3	1	5	3		5	4		5			5	4		5	3
а также в целевую функцию						y =80 +		7 x		+	12 x		4	.
								5	3		5
Выражение для ЦФ показывает,									что значение функции y = 80, полу-

чаемое для опорного решения (2.29), является наименьшим, так как коэффициенты при x2 и x4 положительны, и увеличение этих переменных привело бы к увеличению y. Таким образом, опорное решение (2.29) является искомым решением рассматриваемой КЗЛП.

37

Отметим, что в рассматриваемой задаче n − r = 2, поэтому решение этой задачи можно наглядно интерпретировать на плоскости подобно тому, как это было изложено в § 2.2. Такая геометрическая интерпретация представлена на рис. 2.5.

Первому выбранному по существу наугад опорному решению (2.24) на рис. 2.5 соответствует вершина А1 в многоугольнике А1А2А3А4А5, являющемся ОДР и построенном по уравнениям (2.22) и условиям xi ≥ 0.

	х2				Найденному	затем решению
6		А4	х5=0		(2.26) соответствует	вершина А , яв-
						2
А5			А3		ляющаяся точкой пересечения прямых
4	ОДР			х4=0	x2 = 0 и x3 = 0 . Полученное вслед за
2 А1
		А2	х3=0		ним решение (2.29) оказалось иско-
0	2	4	6 8 10х1		мым. Ему соответствует вершина А3.
	у=С				Это же решение получается в резуль-
		Рис. 2.5			тате перемещения линии равных зна-
					чений ЦФ (пунктирная прямая на рис.

2.5). Таким образом, начав с вершины

А1, выбранной наугад в ОДР, мы в соответствии с рассмотренным алгоритмом последовательно переходили от вершины к вершине в ОДР, все время уменьшая значения ЦФ и приближаясь к ее наименьшему значению.

Рассмотренная для наглядности на конкретном примере методика решения КЗЛП применима к задачам любой размерности и сводится к выполнению следующих операций:

1. Разбиваем список переменных x1,..., xn на m = n − r свободных переменных, например, x1, x2 ,..., xm и r базисных – соответственно xm+1, xm+2 ,..., xn . Пользуясь методом исключения, выражаем выбранные

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

xi =βi −(αi1x1 + αi2x2 +... + αis xs +... + αimxm ),

(2.31)

где i = m +1,...,n . Пользуясь этими соотношениями, ЦФ тоже выражаем через свободные переменные:

y = γ0 − (γ1x1 + γ2 x2 +... + γs xs +... + γm xm ).

(2.32)

Примечание. Вслед за [6] будем при записи выражений базисных переменных и целевой функции через свободные переменные пользоваться формой (2.31) и (2.32), в которой свободные переменные объединены в скобки, перед которыми вынесен знак “минус”.

38

Предположим, что все свободные члены βi неотрицательны.

2. Анализируем выражение для ЦФ (2.32) и выясняем, имеется ли среди коэффициентов γ1,..., γm при свободных переменных хотя бы один

неотрицательный (с учетом знака “минус” за скобкой). Если таких коэффициентов нет, то решение

x1 = x2 =... = xs =...xm = 0; xi =βi для i = m +1,...,n

(2.33)

является искомым решением данной КЗЛП.

В противном случае опорное решение (2.32) оптимальным не является, и нужно перейти к следующей операции.

3. Выбираем одну из переменных, например, xs с неотрицательным коэффициентом γs . Если таких коэффициентов несколько, можно выби-

рать, например, переменную с наибольшим по модулю коэффициентом. 4. Среди коэффициентов αis при этой переменной xs выбираем по-

ложительные коэффициенты (опять же с учетом знака «минус» за скобками), для каждого из них находим отношение βi / αik и выделяем ту пере-

менную, например xk , для которой это отношение оказалось наименьшим.

5. Из уравнения для выделенной базисной переменной, входящего в систему (2.31) xk =βk −(αk1x1 +... + αks xs +... + αkmxm ) , выражаем выделенную свободную переменную

x

s

=

βk

−(

αk1 x +... +

1

x

k

+... +

αkm x

) .

(2.34)

α

α

ks

α

1

ks

α

m

ks

ks

6. Подставляем (2.34)

в каждое из остальных уравнений системы

(2.31) и в выражение для ЦФ (2.32); после приведения подобных членов получаем выражения:

αis

αis

αis

xi =

βi −βk

−

αi1 −αk1

x1

+

αi2 −αk2

x2

+

αks

αks

αks

(2.35)

αis

αis

+... +

xk +

... +

αim −αkm

xm ;

αks

αks

γs

γs

γs

yi

= γ0 −βk

− γ1

−αk1

x1

+ γ2

−αk2

x2

+

αks

αks

αks

(2.36)

γs

γs

+... + −

xk

+... +

γm −αkm

xm .

αks

αks

39

Уравнения (2.35) и (2.36) по виду аналогичны (2.31) и (2.32). Однако в списке свободных и базисных переменных, фигурирующих в этих уравнениях, переменные xk и xs поменялись местами.

7. С полученными уравнениями (2.35) и (2.36) переходим к шагу 2. Перечисленные операции, входящие в алгебраическое решение КЗЛП (симплекс-метод), можно выполнять с помощью так называемой симплекс-таблицы. Одна из возможных форм ее записи представлена

табл. 2.1 [6].

Т а б л и ц а

2.1

β

x

…

x

s

…

x

β α

x

β

1

…

…

m

m+1

α

m+1,1

α

m+1,s

α

m+1,m

β

/α

m+1

m+1

m+1,s

αm+1,s

αm+1,s

αm+1,s

αm+1,s

−βk αks

−αk1 αks

−

αks

−αkm αks

... ...

...

...

...

... ...

...

xk βk

βk

αk1

αk1

…

αks

… αkm

αkm

βk

αk,s

1

... ...

αks

...

αks

...

...

αks

... ...

αks

...

x

β

n

α

n1

…

α

ns

…

α

nm

β

n

n

αns

αns

αns

αns

αk,s

−βk

−αk1

−

−αkm

y

γ

αks

γ

αks

…

αks

…

γ

αks

0

m

γs

1

γs

γs

αns

−βk

−αk1

−

−αkm

αks

αks

αks

αks

Другие формы ее записи и соответствующие правила ее преобразования представлены в [1, 3, 14, 32].

В клетки этой таблицы (в левый верхний угол) записываются соответствующие коэффициенты из системы ограничений-равенств и выражения для ЦФ, записанные в форме (2.31) и (2.32).

Выполнение операций № 2 и 3 сводится к анализу коэффициентов при переменных в строке для ЦФ. Если все они отрицательны, то данная таблица соответствует оптимальному решению. При этом оптимальные значения свободных переменных равны нулю, а базисные – соответст-

40