Методы решения задач линейного программирования

Симплекс-метод

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

1. Для перехода от задачи максимизации к задаче минимизации целевую функцию необходимо умножить на –1.

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

x_j = u_j- w_j u_j, w_j ³ 0.

3. Переход к ограничениям с неотрицательными правыми частями осуществляется умножением левой и правой частей ограничений с отрицательными правыми частями на –1. При этом знаки соответствующих неравенств меняются на противоположные.

4. Переход от ограничений-неравенств к ограничениям-равенствам производится путем введения дополнительных неотрицательных переменных. При этом если знак неравенства £, дополнительная переменная прибавляется к левой части ограничения, а если ³, то вычитается. Таким образом, ограничение-неравенство

a_i1x₁ + a_i2x₂ +…+ a_inx_n £ b_i

преобразуется в ограничение-равенство

a_i1x₁ + a_i2x₂ +…+ a_inx_n + x_n+1 = b_i (x_n+1 ³ 0),

где x_n+1 – дополнительная переменная, x_n+1³0.

Ограничение-неравенство:

a_i1x₁ + a_i2x₂ +…+ a_inx_n ³ b_i

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

a_i1x₁ + a_i2x₂ +…+ a_inx_n - x_n+1 = b_i (x_n+1 ³ 0)

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

Рассмотрим ЗЛП в канонической форме:

Вектор X = (x_1,…, x_n), удовлетворяющий системе ограничений ЗЛП, называется допустимым решением или планом.

План, X^*=(x₁^*,…,x_n^*), при котором целевая функция принимает оптимальное значение, называется оптимальным.

Перепишем ЗЛП в векторной форме.

где A₁,…,A_n – m-мерные вектор-столбцы, составленные из коэффициентов при переменных в системе ограничений:

.

B – вектор-столбец свободных членов системы ограничений:

.

План X = (x_1,…, x_n) называется опорным планом ЗЛП, если система векторов А_j, входящих в разложение с положительными коэффи-циентами x_j , линейно независима. Так как векторы А_j являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может быть больше, чем m.

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

Векторная форма данной задачи имеет вид:

где

Переменные, которые входят только в одно уравнение системы ограничений с коэффициентом равным 1, называют базисными переменными (в рассматриваемом примере это переменные x₁… x_m). Остальные переменные называются свободными. Тогда, приравнивая базисные переменные соответствующим правым частям ограничений, а свободные переменные нулю, получим опорный план X = (b₁, b₂,…, b_m,0 ,…,0), определяемый системой единичных векторов, А₁,…, А_m , которые образуют базис m-мерного пространства.

Для удобства расчетов в симплексном методе все данные по задаче аносят в симплекс-таблицу:

Таблица 5

xd	сd	B	с1	c2	…	cn
X1	x2	…	xn
xd1	cd1	b1	A11	a12	…	a1n
xd2	cd2	b2	A21	a22	…	a2n
…	…	…	…	…	…	…
xdm	cdm	bm	Am1	am2	…	amn
F		D1	D2	…	Dn

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

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

Основные шаги симплекс – метода:

1. Определение начального опорного плана.

2. Составление симплекс-таблицы.

3. Вычисление оценок .

4. Анализ оценок.

4.1. Если , то получено оптимальное решение.

4.2. Если существует хотя бы одна оценка D_j > 0 , для которой , то целевая функция не ограничена снизу на множестве допустимых решений (ЗЛП не имеет решения).

4.3. Из всех оценок D_j > 0 выбирается максимальная:

Переменная x_k, которой соответствует максимальная оценка, стано-

вится на текущей итерации базисной, а k-й столбец объявляется

ведущим столбцом.

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

.

S-я строка объявляется ведущей строкой. Элемент, находящийся в симп-

лекс-таблице на пересечении s-й строки и k-го столбца a_sk, называется ведущим элементом.

6. Пересчет элементов симплекс-таблицы.При этом элементы ведущей строки a_s1,…, a_sn, b_s делятся на ведущий элемент a_sk. Пересчет остальных элементов осуществляется по правилу прямоугольника.

	k-й столбец		j-й столбец
s-я строка	ask		аsj
i-я строка	aik		аij

Пусть a_sk – ведущий элемент. Элемент a_ij– пересчитывается следующим образом:

.

7. Переход к шагу 3

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

Пример

x₁-x₂-3x₃®min

2x₁-x₂+x₃ £ 1

4x₁-2x₂+x₃ ³ -2

3x₁+x₃ £ 5

x₁, x₂, x₃ ³ 0

Приведем к каноническому виду

x₁-x₂-3x₃®min

2x₁-x₂+x₃+x₄ = 1

-4x₁+2x₂-x₃+x₅ = 2

3x₁+ x₃+x₆ = 5

x₁, x₂, x₃ ³ 0

Составим “симплекс-таблицу”:

xб	Сб	b		-1	-3
x1	x2	x3	x4	x5	x6
x4				-1
x5			-4		-1
x6
	-1
x3	-3			-1
x5			-2
x6						-1
-3	-7			-3
x3	-3
x2	-1		-2
x6						-2	-1
-15				-7	-4
x3	-3
x2	-1	11/3				-1/3	1/3	2/3
x1		1/3				-2/3	-1/3	1/3
-46/3				-19/3	-11/3	-1/3

Оптимальное решение:

x₁=1/3; x₂=11/3; x₃=4; x₄=0; x₅=0; x₆=0.

Метод искусственного базиса

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

Пусть в данной задаче среди векторов

нет единичных.

В данном случае к каждому i-му уравнению системы ограничений добавляется неотрицательная переменная x_n+i , называемая искусственной переменной. Так как введение искусственных переменных, в отличие от дополнительных, меняет множество решений задачи, то они вводятся также и в выражение для целевой функции с очень большим коэффициентом M > 0 (тогда в процессе решения задачи минимизации искусственные переменные будут стремиться к нулю). В результате получается задача, называемая расширенной по отношению к исходной:

;

;

.

В результате может быть указан первоначальный опорный план. Искусственные переменные приравниваются к правым частям (x_n+i=b_i), остальные – нулю ( ). Тогда целевая функция примет вид:

,

а оценки D_j в данном случае будут складываться из двух частей, одна из которых зависит от М, а другая не зависит:

.

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

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

1) либо все искусственные переменные не будут исключены из базиса;

2) либо не все искусственные переменные будут исключены, но (m + 2)-я

строка не содержит больше положительных элементов.

В первом случае полученное базисное решение соответствует некоторому опорному плану исходной задачи, (m+2)-я строка таблицы вычеркивается и решение задачи продолжают обычным симплексными методом. Во втором случае, если элемент, стоящий в (m + 2)-й строке столбца B положителен, задача не имеет решения, если он равен нулю, то базис содержит по крайней мере один из векторов искусственного базиса.

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

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

Таким образом алгоритм метода включает следующие шаги:

1. Составляется расширенная задача

2. Находится опорный план решения задачи

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

4). Нахождение оптимального плана исходной задачи с использованием симплекс-метода.

Пример:

xб	Сб	b	-2		-6	-1			M
x1	x2	x3	x4	x5	x6	x7
x4	-1				-2
x5
x7	M			-1				-1
-24		-4
		-1				-1
x4	-1							-1
x5			-1
x3	-6		1/2	-1/2				-1/2
-64	-4
x4	-1		5/2				1/2
x6			-1/2				1/2
x3	-6	11/2	1/4	1/2			1/4
-68	-2	-8			-2

Ответ: x^*=(0; 0; 11/2; 35; 0; 1).

Двойственность в линейном программировании

Каждой ЗЛП можно поставить в соответствие двойственную в соответствии с следующими правилами:

1) если целевая функция F исходной задачи стремится к минимуму, то целевая функция Ф двойственной задачи – к максимуму и наоборот;

2) число переменных двойственной задачи равно числу ограничений исходной, число ограничений двойственной задачи равно числу переменных исходной. Каждому i-му ограничению исходной задачи соответствует переменная y_i двойственной задачи (двойственная переменная), а каждой j-й переменной исходной задачи соответствует j-е ограничение исходной задачи;

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

4) матрица коэффициентов при двойственных переменных в системе ограничений двойственной задачи является транспонированной матрицей коэффициентов при переменных в ограничениях исходной задачи;

5) для удобства построения двойственных задач рекомендуется в исходной задаче ограничения-неравенства записывать со знаком “£ ” при максимизации и со знаком “ ³” при минимизации;

6) каждому i-му ограничению – неравенству исходной задачи соответствует в двойственной задаче условие неотрицательности (y_i³0), а ограничению -равенству - переменная y_i произвольного знака;

7) неотрицательной переменной исходной задачи x_j³0 соответствует в двойственной задаче j-е ограничение – неравенство, а произвольной переменной x_j - равенство. При этом если двойственная задача подлежит минимизации, неравенство записывается со знаком “ ³”, а если двойственная задача подлежит максимизации – со знаком “£ ”.

Рассмотренные правила построения двойственных задач иллюстрируются табл. 8.

Таблица 8

Соотношение двойственности является взаимным, то есть задача двойственная по отношению к двойственной совпадает с исходной.

Пример 5. Построить двойственную задачу к задаче определения производственного плана, приведенной в примере 1: определить, сколько продукции каждого вида x_j необходимо изготовить, чтобы при заданной прибыли от реализации единицы продукции c_j и заданных размерах имеющихся ресурсов b_i максимизировать общую прибыль.

Математическая модель задачи из примера 1 формулировалась следую-щим образом:

F=7x₁+3x₂+6x₃+12x₄®max;

3x₁+x₂+2x₃+4x₄ £440;

x₁+8x₂+6x₃+2x₄ £200;

x₁+4x₂+7x₃+2x₄ £320;

x_j ³0, j= .

Введя три двойственные переменные y₁ , y₂ , y₃ , в соответствии с приве-денными выше правилами построим двойственную задачу:

Ф=440у₁+200y₂+320у₃®min;

3y₁+y₂+y₃ ³7;

y₁+8y₂+4y₃ ³3;

2y₁+6y₂+7y₃³6;

4y₁+2y₂+2y₃ ³12;

y_i ³0, j= .

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

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

Исходная задача: сколько и какой продукции х_j (j=1, n) необходимо произвести, чтобы при заданной прибыли от выпуска единицы каждого вида продукции C_j и размерах имеющихся ресурсов b_i максимизировать общую прибыль

C _j -прибыль от единицы продукции j-го вида, х _j - количество единиц продукции j-го вида, max - доход (прибыль)

, где

a_ij - затраты i-го ресурса на производство единицы продукции j-го вида, x_j - количество единиц продукции j-го вида, b_i - запас i-го ресурса,

-общие затраты i-го ресурса на производство всей продукции.

Двойственная задача

где, b_i - запас i-го ресурса; y_i - стоимость единицы i-го ресурса; min - общая стоимость всех ресурсов.

а_i - затраты i-го ресурса на производство продукции j-го вида; y_j - стоимость единицы i-го ресурса; C_j - прибыль от продукции j-го вида;

-цена всех ресурсов, идущих на изготовление продукции j-го вида.

Двойственная задача: Какова должна быть стоимость единицы каждого из ресурсов y_j i= 1,m , чтобы при заданных количествах ресурсов b_iи заданных величинах дохода C_jот производства каждого вида продукции минимизировать общую стоимость ресурсов?

Переменные y_jназываются учетными, неявными, фиктивными, теневыми ценами.

Пара взаимодвойственных задач, в которых все ограничения записываются в виде неравенств, причем при максимизации знаки всех неравенств £, а при минимизации ³, называется симметричной. Приведенная выше пара задач симметрична.