pizhurin_a_a_pizhurin_a_a_modelirovanie_i_optimizaciya_proce

51

	х,+ 2 х 2 - Зх3 - 5		= 0;	(3.44)
	х г	Зх2 + 1 х3	=
	дг,>0;	х2 >0;	*3 > 0 .	(3.45)

Выберем в системе уравнений (3.44) переменную хг в качестве свободной и выразим через нее базисные переменные х\ и Х 2 . Вычитая второе уравнение из первого,

получим 5 х 2 - 10*з - 5 = 0, откуда х2 = 1 + 2х3 . Подставив найденное выражение для

Х 2 в первое уравнение, получим х j= 3 - х3.

Из последних двух уравнений можно получить любое число решений исходной системы (3.44), задавая произвольные значения переменной хз. Легко проверить, что ограничениям (3.45) среди них будут удовлетворять только те решения, для которых

0 < х3 < 3. Они и будут допустимыми решениями данной ОЗЛП.

К основной задаче линейного программирования можно свести ЗЛП

общего вида (3.20) -	(3.22) следующим образом. Введем дополнительные
переменныеу\, у 2	равные левым частям ограничений (3.21):

У\ = Ь^ ЬПХ\ + Ь \2Х2 + -- + ЬЫХп> У2 = Ъ2+ Ьпх х+Ъ22х2 + ... + Ь2пхп;

(3.46)

Из неравенств (3.21) следует, что все дополнительные переменные должны быть неотрицательны: у . > 0; j = 1 , 2 , . т . Таким образом, задача

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

W= с0 + схх j+ с2х2 +... + спхп -» min; y l= b l+ b uxl + b l2x2 +... + buxn;

(3.47)

ym=bm+bm\X\+bm2X2+--+bm

xt > 0 , z = l,..., n\

у} > 0 , 7 = 1,...,m,

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

Система (3.46) с (п + т) неизвестными, входящая в эту задачу, име­ ет очень удобный вид. Будем считать, что все ее уравнения линейно неза­ висимы. Тогда она имеет ранг г, равный числу уравнений т. При этом т

базисных переменных у\, У2,--, Утуже выражены через п свободных пере­ менных *i, Х2, . . Хп.

Основной задаче линейного программирования разумно давать геометрическую интерпретацию в пространстве свободных переменных хи хп. При п = 2 рассмотрим плоскость с координатами хи х2. Вследст­ вие требования неотрицательности переменных у . > 0 , область допусти­

мых решений в этом случае ограничена прямыми, описываемыми уравне­ ниями:

У у—Ь1+ £>цХ]+ Ь12-^2 = ^>

У2 = Ь 2 + Ь

Ь 22%2 = ^ »

У » = Ьт + Ь т1х \+ Ь *1х г = 0 >

х^= 0; х2 =0.

ОДР, если она существует, представляет собой выпуклый много­ угольник (рис. 3.3, г, соответствующий случаю т = 3). Он называется мно­ гоугольником допустимых решений. Оптимальное решение достигается в одной из вершин этого многоугольника. Поскольку на каждой из ограни­ чивающих прямых одна из переменных yj или х( обращается в нуль, можно утверждать, что в любой вершине многоугольника допустимых решений, а значит, и в вершине, соответствующей оптимальному решению, по край­ ней мере две переменные обращаются в ноль.

При п = 3 следует уже рассматривать трехмерное пространство сво­

бодных	переменных х\9 х2,	х3.	ОДР	в нем	ограничена плоскостями
yj - b j	+ bjXx х+ bj2x2 + bJ3x3 =	0 , j	= 1,	2 ,..., m,	а также координатными

плоскостями xi = 0; *2 = 0; X3 = 0. Она представляет собой выпуклый мно­ гогранник, в одной из вершин которого находится оптимальное решение. Вершина многогранника образуется пересечением не менее чем трех плос­ костей, на каждой из которых одна из переменных обращается в нуль. По­ этому в каждой из вершин, в том числе и в точке оптимума, обращается в нуль не менее трех переменных.

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

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

1. Область допустимых решений ОЗЛП, если она существует, все­ гда образует выпуклое множество. Выпуклым называется множество, об­ ладающее следующим свойством: если любые две точки принадлежат это­

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

2. Оптимальное решение, если оно существует, всегда достигается на границе ОДР, а именно, в одной из вершин многогранника допустимых решений. Допустимое решение, находящееся в одной из вершин этого многогранника, называется опорным решением, а сама вершина - опор­

ной точкой.

3.В опорной точке не менее чем п переменных обращаются в нуль. Здесь п - число свободных переменных ОЗЛП.

4.Для отыскания оптимального решения можно перебрать все опорные решения, отыскивая среди них то, в котором целевая функция достигает экстремума.

3.4. Симплекс-метод решения задачи линейного программирования

3.4.1. Алгоритм замены переменных

Основным методом решения ЗЛП является так называемый сим­ плекс-метод. Он состоит в отыскании опорного решения ЗЛП и в после­ дующем переборе опорных точек до достижения оптимального решения. При этом на каждом шаге перебора опорное решение улучшается по срав­ нению с предыдущим шагом.

Рассмотрим процедуру симплекс-метода для задачи линейного про­ граммирования, сведенной к ОЗЛП и имеющей вид (3.47). При этом т уравнений системы (3.46), входящей в ее состав, будем считать линейно независимыми.

Введем обозначения: а и = - Ь п; а 12= - 6 12,.-*; атп= ~Ьтп> с учетом которых система (3.46) примет так называемую стандартную форму

у , = Ъ Г (апх х+ а пх2 +... + а Хпхп)\

Уг = Ь2 - ( а2)Х1+ а 22Х2+-~ + а2пХг,У’

(3.48)

У т = Ьт ~ (am,*>+ °m2X2 + •••+ а тпХп)• У

Составим стандартную таблицу коэффициентов этой системы (табл.

3.2).

В алгоритм симплекс-метода входит многократно повторяющаяся процедура переразрешения системы (3.48) относительно новых базисных переменных. В ходе этой процедуры требуется вывести какую-либо пере­ менную Xj, j = 1, 2 ,..., л, из числа свободных и перевести ее в базисные, а взамен ввести в число свободных какую-либо базисную переменную y h

i = 1, 2,..., т. Такую замену обозначим

у г По результатам этой про­

цедуры осуществляется переход к новой опорной точке.

				Т а б л и ц а 3.2
Базисная	Свободный			Свободные переменные
переменная
	член (СЧ)				x„
(БП)			*2	Xj
У\	bi	«п	ап	a\j	a\n
У2	ь2	<321	ап	<*2j	аы
У/	ь,	Д/1	ап	ay	ain
Ут	ът	®т\	ami	amj	amn

Пусть требуется произвести замену *. <-> у .. Элемент ау стандарт­

ной табл. 3.2 называется разрешающим. Строка и графа, на пересечении которых стоит разрешающий элемент, также называются разрешающими.

Изложим алгоритм замены переменных [7]. Он состоит в следую­ щем преобразовании стандартной табл. 3.2:

1) в таблице выделяют (обводят) разрешающий элемент ау. Вычис­ ляют его обратную величину X= 1/ау и записывают ее в нижней части той

же ячейки, в которой находится разрешающий элемент; 2 ) все элементы разрешающей строки, кроме самого ау, умножают

на Я. Результаты записывают в нижних частях соответствующих ячеек;

3)все элементы разрешающей графы, кроме* ^самого ау, умножают на (- X). Результаты записывают в нижних частях соответствующих ячеек;

4)подчеркивают в разрешающей строке все верхние числа - преж­ ние элементы, а в разрешающей графе - все нижние числа - новые элемен­ ты, - за исключением X;

5)для каждого из элементов, не принадлежащих ни к разрешающей строке, ни к разрешающей графе, записывают в нижней части соответст­ вующей ячейки произведения подчеркнутых чисел, стоящих в той же строке и той же графе, что и данный элемент;

6 ) переписывают таблицу, заменив Xj на y t и обратно, элементы раз­

решающей строки и разрешающей графы на числа, стоящие в нижних час­ тях соответствующих ячеек; каждый из остальных элементов - на сумму чисел, стоящих в верхней и нижней частях той же ячейки.

55

Например, дана система уравнений

	у х= 2 х х+ х 2 + х3 +1;^
	у 2 = х г х2 ~2 х3; >
	у 3= х }+Зх2 +4.
Требуется произвести замену переменных х3 <-> у 2, то есть вывести
переменную	из числа свободных и перевести ее в базисные, а взамен

внести в число свободных переменную^- Перепишем исходную систему в стандартной форме (3.48):

	у 1= 1 - ( - 2 х - х 2 - х 3У> I
	У2 = 0 -(-* ,+ * 2	+2л:3);	У
	у 3 = 4 - ( - х - З х 2).		)
Составим стандартную таблицу (табл. 3.3).
				Т а б л и ц а 3.3
БП	с ч	Свободные переменные
		*1		*3
			*2
	1	- 2	- 1	- 1
У2	0	-1	1	©
Уз	4	- 1	- 3	0

Разрешающим элементом является элемент на пересечении строки у 2 и графы х3. Это число 2. Величина, обратная разрешающему элементу,

равна X= 1/2.

Т а б л и ц а 3.4

				Т а б л и ц а 3.5
БП	СЧ		Свободные переменные
			*2	У2
У\	1	-5/2	-1/2	1/2
*3	0	-1/2	1/2	1/2
Уз	4	-1	- 3	0

Все элементы табл. 3.3 перепишем в верхние части соответствую­ щих клеток вспомогательной табл. 3.4. В этой же таблице будем записы­ вать и результаты промежуточных вычислений. Число Я запишем в нижней части той же ячейки, в которой находится разрешающий элемент. Нижние части остальных ячеек табл. 3.4 заполняются согласно пп. 2...5 приведен­ ного выше алгоритма. Перепишем табл. 3.4, заменив *3 на у 2 и обратно

(табл. 3.5), вычислив ее элементы в соответствии с п. 6.

Таким образом, исходная система уравнений разрешена относи­ тельно переменных у х, *3, у ъ и приобрела следующий вид:

у 1= 1 -(-2 ,5 * j - 0,5*2 + 0,5у 2)= 1 + 2 , 5 * 0,5*2 - 0,5у 2;

	*3 = 0 - ( - 0 ,5 * ^ 0,5*2 + 0,5^2)= 0,5* j- 0,5*2			►
	у 3 = 4 - ( - * 1-3 * 2)=4 + *1+3*2.
				Т а б л и ц а 3.6
БП	СЧ		Свободные переменные
			х2...	Хп
У1	bi	а и	012 . . .	din
У2	ъ2	а2\		&2п
Ут	Ьщ	Qm\	йт2 . . .	&тп
W	Со	7i	72 ...	7п
Помимо уравнений-ограничений в ОЗЛП имеется еще целевая
функция (3.41). После замены Xj		y i ее также надо выразить через новые

свободные переменные *1, *2,..., *у-1, у» Xj +1,..., хп. Это делается точно так же, как и при преобразовании произвольной строки стандартной таблицы. Функция W приводится к стандартной форме:

w = сй-(У\х\ + Чгх2 + --- + Чпхп\

(3-49)

где yi = - си J2 = - с2\..., уп= - сп. Числа с0, 71, 72,- • Y#*записываются в ка­ честве элементов добавочной строки стандартной таблицы (табл. 3.6) и

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

3.4.2. Отыскание опорного решения ОЗЛП

Первый этап решения ОЗЛП симплекс-методом состоит в получе­ нии опорного решения задачи. На втором этапе отыскивается ее оптималь­ ное решение.

Изложим алгоритм отыскания опорного решения ОЗЛП в предпо­ ложении, что ограничения задачи записаны в стандартной форме (3.48), а коэффициенты этой системы и целевой функции сведены в стандартную табл. 3.6.

1. Если в системе (3.48) все свободные члены b\,b2,...,bmнеотрица­ тельны, то опорное решение уже получено и имеет вид х\ = х2 - ... = х„ = 0; У\ = Ь\\у2 = Ь2\...,ут= Ът. Иными словами, для получения опорного реше­ ния, в случае, если все Ь. > 0, следует в системе (3.48) принять все свобод­

ные переменныех],х2,...ухправными нулю и получить из нее значения ба­ зисных переменных уъУг^-чУт* которые станут равны соответствующим свободным членам Ь\, Ь2,..., Ът.

2.Пусть в одном из уравнений системы (3.48) свободный член от­ рицателен. Если все элементы a}J соответствующей строки неотрицатель­ ны, то система (3.48) несовместна с условиями неотрицательности варьи­ руемых переменных и, следовательно, ОЗЛП не имеет решений.

3.Пусть в уравнении с отрицательным свободным членом есть от­ рицательный элемент ау. Тогда графа стандартной таблицы, в которой он находится, выбирается в качестве разрешающей. Если в рассматриваемой строке отрицательных элементов несколько, то можно взять любой из них.

4.Рассмотрим все элементы данной графы, не считая строки W, имеющие одинаковый знак со своим свободным членом. Элемент, для ко­ торого отношение к нему свободного члена минимально, выбирается в ка­ честве разрешающего. Обратимся к алгоритму замены переменных.

5.В соответствии с изложенными выше правилами осуществляется обмен переменными, которым соответствует выбранный разрешающий элемент.

6.Полученное решение исследуется согласно пп. 1 и 2. Если оно не является опорным и не доказана несовместность системы ограничений, то процедура обмена переменных повторяется до тех пор, пока не будет най­ дено опорное решение или не доказана несовместность системы.

3.4.3. Алгоритм отыскания оптимального решения ОЗЛП

После того как опорное решение ОЗЛП найдено, приступают к оты­ сканию ее оптимального решения в следующей последовательности:

58

1) рассматривается стандартная симплексная таблица, соответст­ вующая найденному опорному решению (см. табл. 3.6). Если все свобод­ ные члены в ней, не считая строки W, неотрицательны, а в строке W, не считая свободного члена, нет ни одного положительного элемента, то оп­ тимальное решение достигнуто и имеет вид х\ = х2 - ... = хп = 0; у\ = Ъ\\

У2 = Ь2 ; ... , у т = Ьт;

2)если в строке W есть один или несколько положительных эле­ ментов, не считая свободного члена, а в каждой из соответствующих им граф нет ни одного положительного элемента, то оптимального решения не существует. Целевая функция в этом случае не ограничена снизу;

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

4)вновь обращаются в п. 1, и при необходимости процедура повто­

ряется.

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

Дана задача линейного программирования:

W’= -2 х } - Зх2 - 1х3 —> шах;

6 - х j —Злг2 —4х3 > 0;

- 4 + 2jCj + 5х2 + 8*3 > 0;

хх >0; х2 > 0 ; х3 > 0.

Перейдем к минимизируемой целевой функции W\ изменив знаки всех коэф­ фициентов исходной целевой функции W' на противоположные, и к ограничениям в виде равенств, введя дополнительные переменные:

fV = 2х1 + Зх2 + 7х3 -> min;

у ] = 6 - х 1 - 3 х 2 - 4*з;

у2 - - 4 + 2jfj + 5х2 + 8*з;

JCj, х2, х3, у {, у 2 - неотрицательны.

В результате исходная задача сведена к 03ЯП. Запишем ее в стандартной фор­ ме: целевую функцию в виде (3.49), а нетривиальные ограничения в виде (3.48):

W = 0-(-2jCj - З х 2 - 1 х3);

(3.50)

Составим стандартную таблицу вида табл. 3.6 из коэффициентов целевой функции (3.50) и системы ограничений (3.51) (табл. 3.7).

					Т а б л и ц а 3.7
	БП	с ч		Свободные переменные
			*i	*2	*3
	У\	6	1	3	4
	У2	- 4	©	- 5	- 8
	W	0	- 2	- 3	- 7

Найдем опорное решение согласно приведенному выше алгоритму:

1)поскольку в системе уравнений (3.51) есть отрицательный свободный член Ъ2 ~ - 4, опорное решение еще не получено;

2)в строке у 2 (см. табл. 3.7) с отрицательным свободным членом есть отрица­

тельные коэффициенты atJ, поэтому опорное решение ОЗЛП существует;

3) среди отрицательных коэффициентов а{. строки у 2 выберем элемент

а21 = -2 . Соответствующую ему графу х1 возьмем в качестве разрешающей;

4)рассмотрим все элементы данной графы, не считая графы W. Оба элемента 1

и- 2 имеют один и тот же знак, что и свободный член, однако отношение свободного члена к своему элементу минимально для коэффициента - 2 : - 4 /(- 2) < 6/1. Поэтому

элемент - 2 в строке у 2 выбран в качестве разрешающего;

5) производится обмен переменными х] <-» у 2 (промежуточная табл. 3.8). В

верхние части ее клеток переписаны коэффициенты из табл. 3.7, в нижние - результаты промежуточных вычислений согласно алгоритму замены переменных. В окончатель­ ном виде результат замены переменных представлен в табл. 3.9. Вновь обратимся к п. 1 алгоритма отыскания опорного решения ОЗЛП. В полученном решении все свободные члены, относящиеся к ограничениям, неотрицательны. Поэтому опорное решение по­ лучено и имеет вид у 2 - х2 - *3 = 0; у х - 4; х, = 2. Значение целевой функции для это­

го решения равно 4.

					Т а б л и ц а 3.8
	БП	с ч		*2	*3
	У\	6	1	3	4
		- 2	ш	-5/2	- 4
	У7	Е З	©	Е З	Е З
		2		5/2	4
			-1/2
	W	0	- 2	- 3	- 7
		4	Е З ’	5	8

60

					Т а б л и ц а 3.9
	БП	с ч	У2	*2	*3
	Ух	4	1/2	1/2	0
				©
	х х	2	-1/2		4
	W	4	- 1	2	1

Переходим к отысканию оптимального решения задачи:

1)согласно п. 1 алгоритма оптимальное решение еще не получено, так как в строке W есть положительные элементы, не считая свободного члена (см. табл. 3.9);

2)в столбцах х2 и х3, соответствующих положительным элементам строки W,

есть положительные элементы, поэтому оптимальное решение существует;

3)выполняется обмен свободной и базисной переменными. Из двух столбцов

х2 и х3, среди которых можно выбирать разрешающий элемент, возьмем столбец х2.

Для элемента 5/2 этого столбца отношение к нему свободного члена мини­ мально: 2/(512) < 4/(1/2), в связи с чем он выбирается в качестве разрешающего. Поэто­ му обмениваются переменные х 1 и х2 (табл. ЗЛО с промежуточными вычислениями).

				Т а б л и ц а	3.10
БП	СЧ	У2	*2	*3
У\	4	1/2	1/2	0
	-2/5	1/10	1-1/51	-4/5
лх \	4/5	|-1/2|	©	Ш
		-1/5		8/5
			Ш
W	4	-1	2	1
	-8/5	2/5	|-4/5|	-16/5
				Т а б л и ц а	3.11
БП	СЧ	У2	*1	*3
У\	18/5	3/5	-1/5	-4/5
х2	4/5	-1/5	2/5	8/5
W	12/5	-3/5	-4/5	-11/5
В табл. 3.11	представлен окончательный результат. В этой таблице оба свобод­

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

достигнуто и имеет вид у\ = х \ - х] = 0; jv* = 18/5; х\ = 4/5. Значение целевой функ­ ции W для этого решения равно 12/5, а значение исходной (максимизируемой) целевой функции W' равно - 12/5.