Элементы линейного программирования

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

;

при ограничениях

Величину принято называть целевой функцией.

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

;

Каждый студент решает свой вариант контрольного задания.

В соответствии с этим вариантом, все буквы, обозначенные в задании, приобретают вполне конкретные числовые значения, а знаки неравенств - вполне определенную направленность. Расшифровка конкретных данных по вариантам дается в приведенной таблице.

Так, например, в строке 40, согласно таблице, будем иметь: знаки неравенств (сверху вниз) и, наконец, правые части . Это значит, что задача линейного программирования примет вид

;

Эту задачу мы будем решать в качестве типовой.

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

Начинается решение с построения области допустимых решений (ОДР), т.е. таких значений неизвестных и , которые удовлетворяют всем заданным ограничениям. Каждое ограничение представляет собой прямую линию, разделяющую плоскость чертежа на две полуплоскости: «разрешенную» и «запрещенную». «Запрещенную» область условимся отмечать штриховкой.

Положение прямых линий задано условиями задачи и определяется уравнениями

При этом ориентация знаков неравенств «подсказывает», какую именно из образующих полуплоскостей следует штриховать. Построив на плоскости чертежа все названные линии и правильно сориентировавшись в том, какую из полуплоскостей следует штриховать (хотя бы путем подстановки в неравенства значения , мы сможем построить область допустимых решений ОДР. В нашем конкретном случае она примет следующий вид:

Внутри ОДР необходимо выделить точки с целочисленными координатами. Для всех этих точек рассчитывается величина и наносится на чертеж в соответствующих местах. Получается поле значений величины по ОДР. Таким образом, имеется возможность наглядно увидеть, в каком направлении растет величина и где достигается ее максимум и минимум. В данном примере максимум достигается в точке с координатами , в точке с координатами . При этом , а . Поле значений позволяет найти точки экстремума только приближенно, и процедура его построения громоздка. Более точный и быстрый метод решения задачи для случая с числом неизвестных дает графическое построение.

Рассмотрим выражение для целевой функции . Это есть уравнение прямой линии с параметром . Зададимся каким-нибудь промежуточным значением . Например, . Получим прямую, изображенную на чертеже пунктиром. Если эту прямую перемещать параллельно самой себе «вправо и вверх», то это будет сопровождаться возрастанием величины .

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

Для применения аналитического метода решения исходная задача должна быть приведена к так называемой канонической форме. Согласно ей, все неравенства-ограничения преобразуются в равенства путем подключения дополнительных неотрицательных переменных-неизвестных, называемых балансовыми. Для каждого неравенства необходима «своя» балансовая переменная. Причем для неравенства вида «» - балансовая переменная вводится со знаком минус, а для неравенства вида «» - со знаком плюс. (Ограничения в виде исходных равенств ввода балансовых переменных не требуют). Новые переменные вводятся и в выражение для с нулевыми коэффициентами, что не искажает существа исходной задачи. В итоге задача линейного программирования в канонической форме примет вид

Число неизвестных у нас возросло до 5, но теперь имеем не неравенства, а уравнения. Образовалась система линейных уравнений . Ее можно разрешить относительно любых трех неизвестных.

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

В итоге получается решение системы , называемое базисным решением. Каждому способу взятия базиса соответствует «свое» базисное решение. Необходимо их все перебрать.

Для пяти неизвестных и трех уравнений существует десять вариантов состава базиса: (123), (124), (134), (234), (125), (135), (235), (145), (245), (345).

Сначала необходимо для исходной системы найти какое-либо одно из базисных решений. Затем, используя свойство возможного «соседства» двух базисов, можно по цепочке последовательно найти все остальные базисные решения.

Первое из находимых базисных решений – так называемое дежурное базисное решение (ДБР). Определять его будем с помощью операций Жордана-Гаусса, последовательно продвигаясь «сверху вниз». Для определенности каждый раз в качестве ведущего элемента будем выбирать элемент, наибольший по абсолютной величине в рассматриваемой строке. (Последнее, впрочем, не обязательно – достаточно лишь, чтобы выбираемый элемент был отличен от нуля).

(5+1)

(5+1)

-1

(2)

-1

-3/2

-1/2

1/2

-1

(7/2)

1/2

-1

7/2

3/2

1/2

33/2

(5+1)

(5+1)

-3/7

-1/7

-3/7

-1/7

1/7

-2/7

1/7

-2/7

2/7

3/7

(1)

2/7

3/7

Таким образом, нами получена система, разрешенная относительно базиса (1,2,5) – именно эти столбцы содержали ведущие элементы, выбираемые в ходе преобразований. Система оказалась совместной и ее ранг , т.е. система в ее исходном виде не содержала «лишних» уравнений. Базисные переменные имеют номера 1,2 и 5, свободные –3 и 4. После их приравнивания нулю последняя система примет вид

И в целом дежурное базисное решение (ДБР) запишется в следующем компактом виде: .

Опираясь на ДБР, можно последовательно получить все остальные базисные решения. Для этого используется отношение «соседства» между двумя базисами. «Соседними» называются также два базиса, в составах которых имеется различие только на одну переменную. Для базиса (1,2,5) «соседними» будут следующие базисы:

Переход от одного базисного решения к соседнему осуществляется с помощью операции однократного замещения. Суть ее состоит в следующем.

- уясняется, какая именно переменная будет выводиться из базиса и какая – вводиться в новый базис;

- внизу расчетной таблицы под «выводимым» из базиса столбцом ставится точка и из нее ведется стрелка до «вводимого столбца»;

- внутри «выводимого» столбца отыскивается единственная единица и от нее, двигаясь горизонтально в направлении стрелки до вводимого столбца, приходим к необходимому ведущему элементу;

- по найденному ведущему элементу делается однократная итерация Жордана-Гаусса.

Продемонстрируем таким путем переходы ко всем соседним с ДБР базисным решениям:

(5+1)

(5+1)

-3/7

-1/7

1/2

3/2

47/2

1/7

-2/7

-1/2

-1/2

-13/2

(2/7)

3/7

3/2

7/2

105/2

(5+1)

(5+1)

-3/7

-1/7

-1/3

1/3

1/7

-2/7

1/3

2/3

2/7

(3/7)

2/3

7/3

(5+1)

(5+1)

(-3/7)

-1/7

-7/3

1/3

-7/3

1/7

-2/7

1/3

-1/3

4/3

2/7

3/7

2/3

1/3

47/3

(5+1)

(5+1)

-3/7

-1/7

-1

(1/7)

-2/7

-2

2/7

3/7

-2

(5+1)

(5+1)

-3/7

(-1/7)

-7

-7

1/7

-2/7

-2

-1

2/7

3/7

-1

(5+1)

(5+1)

-3/7

-1/7

-1/2

-1/2

1/2

1/7

(-2/7)

-7/2

-1/2

-7/2

2/7

3/7

3/2

1/2

33/2

Остальные три базисных решения можно определить опосредованно, через соседние для них и уже найденные базисные решения:

(5+1)

(5+1)

(1/2)

3/2

47/2

-1/2

-1/2

-13/2

3/2

7/2

105/2

-3

-1

-18

						(5+1)								(5+1)
								-3	-1					-4
	-3			-1		-18			-2					-1

						(5+1)								(5+1)
-3	-1					-4		-2
	-2					-1

Почему же нас так сильно привлекают именно базисные решения? Все дело в том, что математически доказан следующий факт: искомая точка и максимума, и минимума обязательно находится где-то среди базисных решений. Более того, она находится не среди базисных решений «вообще», а среди так называемых опорных решений. Опорными называются такие базисные решения, у которых все составляющие неотрицательные. Потому-то и необходимо найти все базисные решения, установить опорные каждого из них и уже для опорных решений вычислить значение , с целью нахождения среди них максимального и минимального. Именно это и будет проделано. Факт наличия опорности каждого базисного решения будем условно обозначать символом «1»; факт отсутствия опорности – символом «0». Все полученные результаты объединим в сводную таблицу.

Базисы	Базисные решения	Опор-ность		Примечание
	-13/2	47/2	105/2				-	-
								Максимум
			-18				-	-
								-
								-
	4/3		-7/3		47/3		-	-
								Минимум
	-1			-7			-	-
		1/2		-7/2	33/2		-	-
			-1	-4			-	-

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

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

Предположим, что наша система ограничений разрешима относительно базиса (1,2,5), что как раз соответствует точке минимума. Но нам о последнем факте неизвестно (других опорных решений как бы еще не нашли). Нам лишь известно, что решение по базису (1,2,5) является опорным. Система ограничений, разрешенная относительно наших базисных переменных, будет характеризоваться следующей расчетной таблицей:

						(5+1)
		-3/7	-1/7
		1/7	-2/7
		2/7	3/7

При переходе к обычной записи (с неизвестными) эта же система примет вид

Выразим базисные неизвестные через свободные неизвестные и подставим их в выражение для :

В точке опорного решения свободные переменные и . Видно, что постепенное наращивание любой из них от нуля будет приводить к увеличению линейной формы. «Круче» это будет выглядеть для переменной , ибо ее коэффициент по абсолютной величине превышает коэффициент при , т.е. .

Будем поэтому наращивать от нуля именно величину , оставляя пока . Тогда по мере «удаления» от исходного опорного решения выражения для и примут вид

(Требования неотрицательности этих величин очевидны для задач линейного программирования)

Очевидно, что величина будет при этом нарастать, что нам и нужно. Но до каких пор наращивать величину ? Ответ должны дать ограничения – неравенства в выражениях для базисных переменных. Видно, что первые два условия росту никак не мешают. А вот третье неравенство допускает рост только до значения .

(Сверх этого предела грозит стать отрицательной).

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

При достижении величиной значения этого наименьшего отношения соответствующая базисная переменная (у нас это будет переменная ) приобретает нулевое значение и переходит в разряд свободных, уступая свое место в базисе переменной , ставшей равной, как нами уже отмечалось, 35. На этом основании можно вычислить новые значения и для

.

Таким образом, мы пришли к новому опорному решению по базису (1,2,4) со свободными переменными и базисными значениями , и , Оно обеспечивает возрастание величины до уровня . Есть ли дальнейшие резервы для наращивания величины ? Снова выразим эту величину через свободные переменные и , выразив через них базисные переменные. Обратимся к ранее знакомому нам выражению:

.

Выразим с его помощью «бывшую» свободную неизвестную через «нынешние» свободные неизвестные и и подставим получившееся выражение в формулу для . Одновременно избавимся от неизвестной в выражениях для и . После преобразований получим:

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

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

.

Образуем в исходной расчетной матрице системы, разрешенной относительно базиса (1,2,5), еще одну дополнительную строку, которую в дальнейшем будем назвать разрешающей. Сделаем это по следующему правилу:

- на букву вообще не будем обращать внимание;

- на позициях, соответствующих базисным столбцам, разместим нули;

- на позициях, соответствующих свободным переменным, поместим коэффициенты с теми их знаками, как представлено в последней записи;

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

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

						(5+1)	(5+2)
		1/7	-2/7				-	(дополнительный столбец)
		-3/7	-1/7				-
		2/7	(3/7)
		-5/7	-11/7					(разрешающая строка)

Теперь дальнейшее увеличение величины обусловлено уже наличием отрицательных элементов разрешающей строки. Наибольший из них по абсолютной величине (-11/7) находится в четвертом столбце, который отмечается внизу дугой и будет впоследствии введен в базис. Если выделенный столбец содержит неположительные элементы, на их уровнях в дополнительном столбце ставятся прочерки. Там же, где элемент выделенного столбца строго положителен, вычисляется отношение правой части (столбца с условным номером (5+1)) к этому элементу. Результат записывается на этой строке в дополнительный, (5+2)-й столбец. Далее (если это необходимо) среди вычисленных отношений выбирается наименьшее. Оно определяет строку, на пересечении которой с выделенным столбцом находится искомый ведущий элемент. По этому ведущему элементу проводится итерация Жордана-Гаусса, которая охватывает также и разрешающую строку.

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

						(5+1)
		1/3		2/3
		-1/3		1/3
		2/3		7/3
		1/3		11/3

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

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

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

Обратимся снова к таблице исходного опорного решения по матрице для базиса (1,2,5).

Вот что дали бы указанные вычисления по небазисным столбцам – третьему, четвертому, пятому:

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

Конечно, элементы нижней строки получились те же, что и в прежних расчетах, и иначе быть не могло.

Теперь необходимо проделать «обратный ход» - от точки максимума к точке минимума. Снова условимся, что нам известно только одно базисное решение – по базису (1,2,4). Ранее мы выяснили, что оно опорное. Ему соответствует следующая расчетная матрица:

						(5+1)
		1/3		2/3
		-1/3		1/3
		2/3		7/3

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

Пристраиваем к расчетной матрице разрешающую строку.

						(5+1)	(5+2)
		1/3		2/3			33/2
		-1/3		1/3
		2/3		7/3
		1/3		11/3

Теперь нас интересуют уже положительные элементы разрешающей строки. Они таковые и по третьему и по пятому столбцам. Следовательно, резервы дальнейшего уменьшения линейной формы имеются. Надо выбрать соседний базис. Поэтому пристраиваем справа дополнительный (5+2)-й столбец. Наибольший по абсолютной величине элемент разрешающей строки находится в пятом столбце. Он и будет введен в базис (отмечается дугой). Все его элементы положительны. Вычисляются отношения элементов (5+1)-го столбца к элементам пятого столбца и записываются в (5+2)-й столбец. Наименьшее из получившихся отношений оказалось в третьей строке и равно 15.

Поэтому ведущий элемент, по которому будет осуществляться перерасчет, находится на пересечении третьей строки и пятого столбца и равен 7/3. Перерасчет по этому элементу дает

						(5+1)
		1/7	-2/7
		-3/7	-1/7
		2/7	3/7
		-5/7	-11/7

Все элементы нижней строки получились не положительными (по первому и пятому столбцам). Это значит, мы пришли в точку минимума, что и требовалось. Обратим внимание на то, что «спуск» произошел по тому же «маршруту» и за то же самое число шагов, что и «подъем». Такое бывает, но не всегда.