Пример отыскания минимума линейной функции

Пример. Решить симплексным методом задачу Z=18y₁+16y₂+5y₃+21y₄®min при ограничениях:

Решение. Введем дополнительные неотрицательные переменные y₅, y₆ со знаком “-”, т.к. неравенства имеют вид ”³”:

Запишем систему в векторной форме:

(3) А₁y₁ + А₂y₂ + А₃y₃ + А₄y₄ - A₅ y₅- A₆ y₆ =A₀,

где

В качестве базисных удобно взять переменные y₃ , y₄, т.к. коэффициенты при них положительны, а разделив 1-ое уравнение на коэффициент 3 при y₄, получим систему единичных векторов А₃, А₄:

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

1 шаг. Базисные переменные: y₃ , y₄.

Свободные переменные: y₁, y₂, y₅, y₆.

Выразим базисные переменные через свободные:

Y₁=(0;0;3;2/3;0;0) – первоначальный опорный план. Выразим линейную функцию через свободные переменные:

Z=18y₁+16y₂+5y₃+21y₄=18y₁+16y₂+5(3-3y₁- y₂+ y₆)+21(2/3-1/3y₁- 2/3y₂+ 1/3y₅)=29-4y₁- 3y₂+ 7y₅+ 5y_6.

Z₁=Z(Y₁)=29 – это значение не является оптимальным, т.к. функцию Z можно уменьшить за счет перевода в базисные любой из свободных переменных y₁, y₂, имеющих в выражении для Z отрицательные коэффициенты. Т.к. y₁ имеет больший по абсолютной величине коэффициент, то начнем с этой переменной. Определим наибольшее возможное значение для y₁ (при этом y₂, y₅, y₆ раны 0 как свободные переменные).

Откуда

Для нее наибольшее возможное значение: y₁=min{3/3;2/1}=1, т.е. первое уравнение является разрешающим, y₃ становится свободной переменной.

2 шаг. Базисные переменные: y₁ , y₄.

Свободные переменные: y₂, y₃, y₅, y₆.

Выразим базисные переменные через свободные, подставив в уравнение для y₄ вместо y₁ его представление через свободные:

Z=25 –5/3y₂+4/3y₃+ 7y₅+ 11/3y_6.

При базисном решении Y₂=(1;0;0;1/3;0;0) получаем Z₂=Z(Y₂)=29 – это значение не является оптимальным, т.к. функцию Z можно уменьшить за счет перевода в базисные переменной y₂, имеющей в выражении для Z отрицательный коэффициент. Определим наибольшее возможное значение для y₂ (при этом y₃, y₅, y₆ раны 0 как свободные переменные).

Откуда

Для нее наибольшее возможное значение: y₂=min{3;3/5}=3/5, т.е. 2-ое уравнение является разрешающим, y₄ становится свободной переменной.

3 шаг. Базисные переменные: y₁ , y₂.

Свободные переменные: y₃, y₄, y₅, y₆.

Выразим базисные переменные через свободные, подставив в уравнение для y₁ вместо y₂ его представление через свободные:

Z=24+y₃+3y₄+ 6y₅+ 4y_6. Базисное решение Y₃=(4/5;3/5;0;0;0;0) оптимальное, т.к. в выражении для Z нет переменных с отрицательными коэффициентами. Получаем Z_min=Z(Y₃)=24.

Симплексные таблицы

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

Рассмотрим следующую ЗЛП.

Найти максимум целевой функции Z=С₀+ ® max

при ограничениях где x_j ³ 0 (j=1,2,…,n), b_i ³ 0 (i=1,2,…m; m£n).

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

(1)

Целевую функцию записываем как разность: Z-C₁x₁ ­- C₂x₂ -_×××-C_nx_n=C₀. (2)

причем x₁ ³ 0, x₂ ³ 0, ... , x_n ³ 0. При этом учитываем, что b_i ³ 0, i=1,2,…,m.

2. Найти первоначальный опорный план с базисом из единичных векторов.

Возможны следующие случаи:

а) Если предварительно ограничения ЗЛП можно преобразовать к виду АX£A₀ при А₀³0, то после перехода к каноническому виду система ограничений всегда содержит единичную матрицу из коэффициентов при дополнительных переменных, т.е. коэффициенты при них образуют единичный базис.

б) Если система ограничений задачи явно не содержит единичные векторы, то, используя метод Жордана – Гаусса, можно привести систему ограничений задачи к равносильной разрешенной относительно некоторого базиса системе уравнений, сохраняя при этом правые части неотрицательными.

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

Пользуясь терминами линейных векторных пространств, при выборе базисных переменных руководствуются следующими соображениями: линейно независимые единичные век­торы n-мерного пространства A_i (1£i£m£n) образуют базис этого простран­ства. Поэтому за базисные переменные выбираем x_i, стоящие при этих векторах, остальные переменные – свободные.

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

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

Предположим, для определенности, что система ограничений задачи содержит т единичных векторов, которыми являются первые т векторов, и, следовательно, базисные переменные - это x₁,x₂,...,x_m, т.е. система ограничений имеет вид:

(3)

причем x₁ ³ 0, x₂ ³ 0, ... , x_n ³ 0. При этом учитываем, что b_i ³ 0, i=1,2,…,m.

Переменные x₁,x₂,...,x_m, соответствующие единичным векторам, называются базисными, а весь набор {x₁,x₂,...,x_m} - базисом; остальные переменные называются небазисными или свободными.

Выражаем целевую функцию Z через свободные переменные x_m+1,..., x_n, подставляя в Z вместо базисных переменных их выражения через свободные из (3), и получаем:

Z =C₀ + C_m+1x_m+1 + ... + C_nx_n. (4)

Полученную расширенную систему заносим в первую симплексную таблицу.

Базис	Свобод.	переменные	Оценочное
	член А0	x1	x2	…	xm	xm+1	…	xn	отношение
x1	b1			…		a1,m+1	…	a1n
…	…	…	…	…	…	…	…	…
xk	bk	…	…	…	…	ak,m+1	…	a1n
…	…	…	…	…	…	…	…	…
xm	bm			…		am,m+1	…	amn
Z	C0			…		-Cm+1	…	-Cn

Последняя строка таблицы, в которой приведено уравнение для линейной функции, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком: Z-C_m+1x _m+1 ­– C _m+2x _m+2 -_×××-C_nx_n=C₀.

В 1-ом столбце записываем базисные переменные (базис), в 1-ой строке – все переменные (отмечая при этом базисные), во 2-ом столбце – свободные члены расширенной системы b₁, b₂,…,b_m. Последний столбец подготовлен для оценочных отношений, необходимых при расчете наибольшего возможного значения переменной. В рабочую часть таблицы занесены коэффициенты а_ij при переменных из расширенной системы.

Т.к. все величины х_i (i=1,2,…,n) должны быть неотрицательны, то наименьшие возможные значения свободных переменных - это значения, равные нулю. Положим все свободные переменные равными нулю: x_m+1 = 0, ... , x_n = 0

и найдем из системы (3) значения базисных переменных:

x₁ = b₁, x₂ = b₂, ... , x_m = b_m.

Получим первоначальное базисное решение (опорный план) системы, отвечающие базису x₁,x₂,...,x_m:

X₁ = (b₁, b₂,..., b_m,0, ... , 0).

Оно будет допустимым, а т.к. векторы, соответствующие базисным переменным, линейно независимы, то и опорным. Т. е. получим первоначальный опорный план. Геометрически данный план соответствует первоначальной угловой точке.

Подставим в максимизируемую целевую функцию Z из (4) значения свободных переменных. Т.к. x_m+1 = 0, ... , x_n = 0, то Z₁ = C₀.

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

Если все коэффициенты C¢_m+1,...,C¢_n целевой функции отрицательны (в последней строке таблицы - положительные, т.к. записаны с противоположным знаком), то, увеличивая какие-то из переменных x_m+1,..., x_n сверх нуля, мы не можем увеличить L; значит, найденное нами базисное решение X=(b₁,b₂,..., b_m,0,...,0) оптимально.

3. Проверяем выполнения критерия оптимальности.

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

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

Т.о., если выполнены критерии оптимальности, то найденное базисное решение является оптимальным, достигнут max (min) Z=c₀ (в левом нижнем углу таблицы), базисные переменные принимают значения b_i (второй столбец), свободные переменные равны 0, т.е. получаем оптимальное базисное решение.

4. Если критерий оптимальности не выполнен, т.е. среди коэффициентов C_m+1,..., C_n имеются отрицательные, то увеличивая те из переменных x_m+1, ... , x_n, коэффициенты при которых отрицательны, мы можем улучшить решение, т.е. увеличить Z.

Для определенности в такой ситуации будем выбирать переменную, имеющую наибольший коэффициент. Т.о., наибольший по модулю отрицательный коэффициент C_i<0 (для max) или наибольший по модулю положительный коэффициент C_i>0 (для min) в последней строке определяет разрешающий столбец.

Пусть, например, это будет коэффициент C_m+1 в формуле (4) при x_m+1, т.е. m+1 столбец. Значит есть смысл увеличивать x_m+1, т.е. перейти от данного опорного решения к другому, где переменная x_m+1 ¹ 0, а вместо нее равна 0 какая-то другая. При таком переходе геометрически произойдет переход к соседней вершине многоугольника, где значение линейной функции лучше.

Однако увеличивать x_m+1 надо осторожно, так чтобы не стали отрицательными другие переменные x₁,x₂,...,x_m, которые можно было бы выразить через свободные переменные. Поэтому, для выбора базисной переменной, переводимой в свободные, составляем оценочные отношения для каждой строки.

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

Т. о. оценочные отношения определяются по следующим правилам:

1)µ, если b_i и a_i,m+1 имеют разные знаки;

2) µ, если b_i =0 и a_i,m+1 <0;

3) µ, если a_i,m+1 =0;

4) 0, если b_i =0 и a_i,m+1 >0;

5) , если b_i и a_i,m+1 имеют одинаковые знаки.

Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из полученных во всех уравнениях границ. Поэтому выберем ту из переменных x₁,x₂,...,x_m, которая раньше всех обратится в нуль при увеличении x_m+1, т.е. ту, для которой величина меньше всего.

Для этого определяем . Если конечного минимума нет, то задача не имеет конечного оптимума (Z_max =µ или Z_min =-µ). Если минимум конечен, то выбираем строку k, на которой он достигается (любую, если их несколько), и называем разрешающей строкой.

Выделяем, например, с помощью стрелок разрешающие строку и столбец таблицы 1, на пересечении которых находится разрешающий элемент a_k,m+1.

5. Переход от базиса x₁, ...,x_k-1,x_k,x_k+1, ...,x_m к новому базису x₁, ..., x_k-1,x_k+1, ...,x_m+1, путем исключения из старого базиса x_к и ввдением вместо него x_m+1.

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

Переход к новой таблице осуществляем по правилам:

а) в левом столбце записываем новый базис: вместо базисной переменной x_к - переменную x_m+1;

б) делим все числа выделенной строки на a_k,m+1 с таким расчетом, чтобы на месте a_k,m+1 появилась единица. Полученную таким образом строку пишем на месте прежней;

в) к каждой из остальных строк таблицы прибавляем вновь полученную строку, умноженную на такое число a_i,m+1 (i=1,2,…,k-1,k+1,…,m) с противоположным знаком, чтобы во всех клетках разрешающего столбца m+1, т.е. в строках x₁, ..., x_k-1,x_k+1, ...,x_m, кроме клетки (к,m+1), появился 0. Это соответствует исключению x_m+1 из остальных уравнений системы. Или по-другому, все остальные элементы (i=1,2,…,k-1,k+1,…,m; j=1,2,…,m,m+2,…,n) вычисляем по правилу прямоугольника: для вычисления элементов (к–1)-ой строки

_{] ]}

- - - - - - - - _{- - -}

- - - - - - - - _{- - -}

_{] ]}

Преобразованные таким образом строки пишем на месте прежних.

Базис	Свобод.	переменные	Оценочное
	Член А0	x1	x2	…	xk	…	xm+1	…	xn	отношение
x1	b’1			…	a’1,k	…		…	a’1n
x2	b’2			…	a’2k	…		…	a’2n
…	…	…	…	…	…	…	…	…	…
xm+1	b’k			…	a’k,k	…		…	a’kn
…	…	…	…	…	…	…	…	…	…
xm	b’m			…	a’m,k	…		…	a’mn
Z	C’0			…	-C’k	…		…	-C’n

В результате получаем новую таблицу II, а также новое опорное решение. Первое опорное решение мы получили, положив равными нулю все прежние свободные переменные x_m+1, ... , x_n; второе мы получим, если обратим в нуль все новые свободные переменные x_k, x_m+2 ,..., x_n.

Далее переходим к пункту 3 алгоритма (но уже в новом базисе).

Итак, если дана таблица I и указан разрешающий элемент a_ij , то переход к таблице II происходит автоматически. Весь процесс решения задачи сводится к последовательному составлению таблиц: I, II, III, ... - до тех пор, пока не будет получено оптимальное решение (признаком этого будет служить положительность всех коэффициентов целевой функции Z в последней строки таблицы для max или отрицательность всех элементов для min). Или же будет обнаружено, что max (min) Z = ¥ (признаком этого будет служить наличие для всех строк бесконечных оценочных отношений при выборе разрешающей строки). В этот момент процесс решения задачи закончится.

Пример 1. Найти максимум целевой функции Z=2x₁+3x₂®max

при ограничениях (1) x₁³0, x₂³0.

Расширенная система имеет вид:

Линейную функцию представим в виде Z-2x₁-3x₂=0.

Этим данным соответствует таблица 1, в которой переменные x₃, x₄, x₅, x₆ базисные. Последняя строка заполняется коэффициентами линейной функции с противоположным знаком (см.п.2 алгоритма).

Базис	Свобод.	пе	ре	ме	нн	ые		Оценочное
	член А0	x1	X2	х3	x4	x5	x6	Отношение
х3								18/3
х4
X5
х6								µ
Z		-2	-3

В соответствии с п.3 алгоритма проверяем критерий оптимальности. В последней строке имеем отрицательные числа; выбираем наибольший по модулю (-3), 2-ой столбец разрешающий, переменная х₂ перейдет в базисные ( помечаем его стрелкой). В соответствии с п.4 алгоритма находим оценочные отношения и х₂=min{18/3;16;5;µ}=5. Третья строка является разрешающей (помечаем ее горизонтальной стрелкой). Разрешающим элементом является единица, стоящая на пересечении строки для x₅ и столбца для x₂.

C этого момента начинается переход к таблице 2 по правилам п.5 алгоритма.

А) Новый базис состоит из x₃, x₄, x₂, x₆ (удаляем из старого базиса x₅ и вводим x₂).

Б) Прежде всего, делим выделенную строку таблицы 1 на такое число а₃₂=1, чтобы на месте разрешающего элемента появилась единица, и полученную таким образом строку пишем на месте прежней. В нашем случае сразу стоит 1.

В) К каждой из остальных строк прибавляем вновь полученную, умноженную на такое число, чтобы в клетках столбца x₂ появились нули, и пишем преобразованные строки на месте прежних. Например:

и т.д.

Переход к таблице 2 завершает первый шаг нашего процесса.

Таблица 2.

Базис	Свобод.	пе	ре	ме	нн	ые		Оценочное
	член А0	x1	x2	х3	x4	x5	x6	Отношение
х3						-3
х4						-1		11/2
x2								µ
х6
Z		-2

Критерий оптимальности вновь не выполнен. Теперь 1-вый столбец разрешающий, х₁ – переходит в базисные, х₁=min{3/1;11/2;µ;7}=3. 1-ая строка разрешающая, элемент а₁₁=1 находится на пересечении строки для x₁ и столбца для x₁. Делаем следующий шаг - переходим к таблице 3.

Таблица 3.

Базис	Свобод.	пе	ре	ме	Нн	ые		Оценочное
	член А0	x1	x2	х3	x4	x5	x6	Отношение
х1						-3		µ
х4				-2				5/5
x2								5/1
х6				-3				12/9
Z						-3

Критерий оптимальности вновь не выполнен. Теперь 5-ый столбец разрешающий, х₅ – переходит в базисные, х₄=min{µ;5/5;5/1;12/9;}=1. 2-ая строка разрешающая, элемент а₂₅=5 разрешающий. Переходим к таблице 4.

Таблица 4.

Базис	Свобод.	пе	ре	ме	нн	ые		Оценочное
	член А0	x1	x2	х3	x4	x5	x6	Отношение
х1				-1/5	3/5
х5				-2/5	1/5
x2				2/5	-1/5
х6				3/5	-9/5
Z				4/5	3/5

Критерий оптимальности выполнен. Значит Z_max=24, оптимальное базисное решение x₁=6, x₂=4, x₃=0, x₄=0, x₅=1; x₆=3.