Искусственное начальное решение

Идея использования искусственных переменных предполагает включение неотрицательных переменных в левую часть каждого из уравнений, в которых не содержится очевидных начальных базисных переменных (когда неравенство имеет знак ”³” или задано в виде равенства). Эти дополнительно вводимые переменные выполняют ту же роль, что и остаточные переменные. Но так как искусственные переменные не имеют отношения к поставленной задаче (отсюда их название - искусственные), то их введение допустимо только в том случае, если симплекс метод будет обеспечивать получение оптимального решения, в котором все искусственные переменные будут равны 0, то есть эти переменные следует использовать только для стартовой точки, причем итерационный метод оптимизации должен "вынуждать" эти переменные принимать нулевые значения в конечном оптимальном решении, обеспечивая допустимость оптимума. Разработаны два метода получения стартовой точки:

1) М - метод или метод больших штрафов.

2)  Двухэтапный метод.

 

Метод больших штрафов

Для построения требуемой схемы вычислений можно применить следующий прием: наложить штраф за использование искусственных переменных, равный сумме искусственных переменных, умноженный на очень большое число М (М>>1).

При поиске минимума штраф прибавляется к целевой функции.

,

при поиске максимума f вычитается из нее

.

Алгоритм метода:

1) Добавить искусственные переменные R_i в ограничения вида “=” и “ ”. Из ограничений “ ” предварительно следует вычесть избыточную переменную.

2) Выразить R_i из соответствующего ограничения через небазисные переменные и подставить в штраф.

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

Пример 2. 11.1:

В стандартной форме	В канонической форме
f0= 4x1 + x2 ® m in	f0= 4x1 + x2 ® m in
при ограничениях	При ограничениях
3х1 + х2 = 3                 (1)	3х1+ х2 = 3
4х1 + 3х ³ 6                  (2)	4х1 + 3х2-x3= 6
х1 + 2х2 4                   (3)	х1 + 2х2+x4= 4
х1, х2 ³ 0	х i ³ 0,                        i =1,2,...,4

В первом и втором уравнениях нет переменных, выполняющих роль остаточных. Поэтому введем в каждое из этих уравнений по одной искусственной переменной R₁ и R₂.

                                             3 ×х₁ + х₂+R₁ = 3

4 ×х₁ + 3 ×х₂ - x₃+R₂ =6

 

За использование R₁ и R₂ в состав целевой функции можно ввести штраф, приписывая переменным R ₁ и R₂ достаточно большой положительный коэффициент M (М>>1). При поиске mах f  этот штраф, равный

 

,

где е – число искусственных переменных,

вычитается из целевой функции, а при поиске min f прибавляется к целевой функции.

f = 4 × x₁ + x₂ + M × R₁ + M × R₂ ® min

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

3 ×х₁ + х₂+R₁ = 3                 R₁=3 – 3x₁ – x₂

4 ×х₁ + 3 ×х₂ - x₃+R₂= 6       R₂=6 – 4 x₁-3 x₂+ x₃

x₁+2 × x₂+x₄= 4                         

x₁, x₂, x₃, x₄, R₁, R₂ ³ 0

n = 6, m = 3,

n - m = 3 - число небазисных переменных.

Небазисные переменные х₁, х₂, х₃ равны нулю, тогда начальный базис R₁ = 3; R₂=6;, x₄ = 4.

Так как мы имеем дело с задачей минимизации f, то в оптимальном решении переменные R₁ и R₂, обратятся в нуль. Заметим, что все промежуточные итерации, предшествующие получению минимума, с точки зрения окончательного результата, не имеют значения.

Далее следует выразить переменные R₁ и R₂ из (1) и (2) уравнений через небазисные переменные и подставить в целевую функцию. Получим следующее выражение для целевой функции. 

f = 4 × x₁+ x ×₂+ M ×(3–3 × x₁– x₂)+ M ×(6–4 × x₁–3 × x₂+ x₃)

f = (4-7 M) × x₁+(1-4 M) × x₂+ Mx₃+9 M

В начальном базисе

  fур         (- 4 + 7M) ×x₁ + (-1 + 4M) ×x₂ – Mx₃= 9 ×M

 

результаты вычислений приведены в табл.38

Таблица 36

№ итер	Ба-зис	х1	х2	х3	х4	R 1	R 2	Знач	Отнош	Формула
№=0 х1 вв, R 1 искл	f ур	-4+7M	-1+1M	-M	0	0	0	9M
	R1	3	1	0	0	1	0	3	3:3=1
	R 2	4	3	-1	0	0	1	6	6:4=1,5
	x 4	1	2	0	1	0	0	4	4:1=4
№=1 х2 вв, R 2 искл.	f ур	0		- M	0		0	2 M +4		f ур = f ур +(4- M) × х1
	х1	1	1/3	0	0	1/3	0	1	1: 1/3=3	х1= R 1:3
	R 2	0	5/3	-1	0	-4/3	1	2	2: =1,2	R 2 = R 2 -4х1
	х4	0	5/3	0	1	-1/3	0	3	3: =1,8	х4=х4-х1
№=2 х3 вв.,   х4 искл	f ур	0	0	1/5	0	- M +8/5	- - M	18/5		f ур= f ур -(5 M + )х2
	х1	1	0	1/5	0	3/5	-1/5	3/5		х1=х1-1/3х2
	х2	0	1	-3/5	0	-4/5	3/5	6/5		х2= R 2:5/3
	х4	0	0	1	1	1	-1	1		х4=х4- х2
№=3 оптимум	f ур	0	0	0	-1/5	- M +7/5	- M	17/5		f ур = f ур -1/5х3
	х1	1	0	0	-1/5	2/5	0	2/5		х1=х1-1/5х3
	х2	0	1	0	3/5	-1/5	0	9/5		х2=х2+3/5х3
	х3	0	0	1	1	1	-1	1		х3=х4

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

х₁^*= 2/5; х₂*= 9/5; х₃^*= 1;

min f₀*= 17/5 (R₁*, R₂*, X₄* = 0), т.е. Х*(2/5; 9/5; 1; 0)

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

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

Двухэтапный метод

Недостаток M-метода связан с возможностью ошибок в вычислениях, обусловленной очень большой величиной коэффициента M. Например, если принять M=100000, тогда коэффициенты при х₁ и х₂ в f -уравнении начальной симплекс таблицы будут равны (-4 + 700000) и (-1 + 400000) соответственно. Из-за большой величины M вклад коэффициентов C₁= 4 и C₂= 1 при х₁ и х₂ оказывается ничтожно мал. Поэтому возникает опасность, что переменные х₁ и х₂ будут интерпретироваться как переменные, фигурирующие в целевой функции с нулевыми коэффициентами.

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

Этап 1. Искусственная переменная вводится для получения начального базиса. Записывается новая целевая функция f₁, предусматривающая минимизацию суммы искусственных переменных при исходных ограничениях, видоизмененных за счет введения искусственных переменных.

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

Если min f₁ ¹ 0, то исходная задача не имеет допустимых решений.

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

Пример 2. 11. 1: Рассмотрим предыдущий пример:

f₀= 4х₁ + х₂ ® min

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

                          3 ×х₁ + х₂+R₁=3 (1)      Þ      R₁=3 – 3 ×х₁ – х₂

4 ×х₁ + 3 ×х₂ -х₃+R₂= 6 (2)            Þ      R₂=6 – 4 × x₁-3 ×х₂+х₃

х₁+2 ×х₂+х₄=4           (3)

R₁, R₂ ³0                                          

x_i ³ 0 i=1, 2,..,4

R₁+ R₂=9-7 ×х₁-4 ×х₂+х₃

Этап 1. Решается задача f_1ур = R₁ + R₂ ® min.

Тогда целевая функция

f_1ур = 9 – 7х₁ – 4х₂ + х₃®min

при ограничениях исходной задачи

Составим исходную симплекс - таблицу, за начальный базис возьмем R₁, R₂, х₄, свободные переменные

х₁ = х₂ = х₃ = 0

f_1ур –                                 х₃+ 7х₁ + 4х₂ = 9

Таблица 37

№ итер	Базис	х1	х2	х3	х4	R 1	R 2	Знач	Отнош	Формула
№=0 х1 вв., R 1 искл.	f 1ур	7	4	-1	0	0	0	9
	R 1	3	1	0	0	1	0	3	3: 3=1
	R2	4	3	-1	0	0	1	6	6:4=3/2
	x 4	1	2	0	1	0	0	4	4:1=4
№=1 х2 вв., R 2 искл.	f 1ур	0	5/3	-1	0	-7/3	0	2		f 1ур = f 1ур -7х1
	х1	1	1/3	0	0	1/3	0	1	1:1/3=3	х1= R 1:3
	R2	0	5/3	-1	0	-4/3	1	2	2:5/3=6/5	R2=R2-4x1
	x4	0	5/3	0	1	-1/3	0	3	3:5/3=9/5	x4=x4-x1
№=2 оптим. решен. 1 этапа	f 1ур	0	0	0	0	-1	-1	0		f 1ур = f 1ур -5/3х1
	х1	1	0	1/5	0	3/5	-1/5	3/5		х1= х1-1/3 × x2
	x2	0	1	- 3 /5	0	-4/5	3/5	6/5		x2=R2:5/3
	x4	0	0	1	1	1	-1	1		x4=x4- 5/3 x 2

R₁^*=R₂^*= 0         х₁^*=3/5;  х₂^*=6/5;  х₃^*=0; x ₄ ^* =1; f _1ур ^* = 0

Получили допустимое базисное решение исходной системы ограничений, так как f _1ур ^* = 0 при R₁^*=R₂^*= 0.

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

х₁+ х₃=               Þ                       х₁= - х₃

х₂- х₃=                 Þ                       х₂= + х₃

х₃+х₄=1

 

Главная цель первого этапа обеспечить получение начального решения исходной системы ограничений. Теперь исходная задача содержит n = 4 переменных и m = 3 уравнения. Значит, число небазисных переменных n - m = 1. В полученном допустимом решении свободная переменная х₃= 0, базисная

х₁= ,  х₂=  ,  х₄= 1.

Выразим целевую функцию через свободную переменную х₃, подставив выражения для базисных переменных х₁ и х₂ через небазисную переменную х₃.

f ₀ = 4х₁ + х₂ = - х₃+ + х₃= - х₃ ® min

f _0ур                                                              х₃=

В результате будем иметь начальную симплекс - таблицу для 2–го этапа.

Таблица 38

№ итер.	Базис	х1	х2	х3	х4	Знач	Отнош	Формула
№=3 x 3 вв., х4 искл.	f 0ур	0	0	1/5	0	18/5
	х1	1	0	1/5	0	3/5	3/5:1/5=3
	х2	0	1	-3/5	0	6/5	не рассчит.
	х4	0	0	1	1	1	1:1=1
№=4 оптим. реше-ние	f 0ур	0	0	0	-1/5	17/5		f 0ур = f 0ур -1/5х3
	х1	1	0	0	-1/5	2/5		х1=х1-1/5х3
	х2	0	1	0	3/5	9/5		х2=х2+3/5 x 3
	х3	0	0	1	1	1		x 3 = x 4

 

Полученное решение оптимально, так как коэффициент при х₄<0, а решается задача min f₀

х₁^*= ,  х₂^*=  ,  х₃^*= 1, х₄^*=0

                             min f ₀ = 4х₁^* + х₂^* = 4  +  = .

Замечание:

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

2) На 2 этапе искусственные переменные отсутствуют только в том случае, если в конце 1 этапа они стали не базисными. Однако возможен случай, который при завершении 1 этапа искусственные переменные, имея нулевые значения, останутся базисными.

Пример 2. 11. 2:

Математическая модель

f ₀ =3 × х₁+2 × х₂+3 × х₃ ® min

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

                                             х₁+4 × х₂+х₃ ³ 7

                                                             2 × х₁+х₂+х₄ ³ 10

                                                             х _i ³ 0  i =1,..,4

В канонической форме

                          х₁+4 × х₂+х₃ - х₅+ R =7 Þ R =7 - х₁ - 4х₂ - х₃+х₅

2 × х₁+х₂+х₄ - х₆=10

х _i ³ 0 i =1, 2,..,6; R ³ 0

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

Первый этап:

f _1ур = R =7 - х₁ - 4 × х₂ - х₃+х₅ ® min

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

х₁+4 × х₂+х₃ - х₅+ R =7

2 × х₁+х₂+х₄ - х₆=10

                              f _1ур                          х₁ + 4 × х₂+х₃ - х₅=7

              Таблица 39

№ итер.	Базис	х1	х2	х3	х4	х5	х6	R	Знач	Отнош	Формула
N=0 x 2 вв, R искл.	f ур	1	4	1	0	-1	0	0	7
	R	1	4	1	0	-1	0	1	7	7:4=7/4
	х4	2	1	0	1	0	-1	0	10	10:1=10
N=1 оптимум	f ур	0	0	0	0	0	0	-1	0		f 1ур= f 1ур -4 x 3
	х2	1/4	1	1/4	0	-1/4	0	1/4	7/4		x 2 = R:4
	X 4	7/4	0	-1/4	1	1/4	-1	-1/4	3		x 4 =х4-х2

Второй этап:

Выразим базисную переменную х₂ через небазисные переменные. Из оптимальной симплекс–таблицы первого этапа:

х₁+х₂+ х₃ - х₅ =   Þ        х₂= - х₁ - х₃+ х₅

Подставим х₂ в f ₀:

f ₀ = 3х₁+2х₂+3х₃=3х₁+2( - х₁ - х₃+ х₅)+3 × х₃=3х₁+ - х₁ - х₃+ х₅+3 × х₃== х₁+ х₃+ х₅+ ® min

В целевую функцию f ₀ свободные переменные х_1, х₂, х₅ входят с положительными коэффициентами, поэтому их увеличение нецелесообразно, т.е. min f ₀ =   при плане Х*=(0; ; 0; 3; 0)

Двойственный симплекс-метод

Двойственный симплекс – метод широко используется:

1) при решении целочисленных задач ЛП;

2) если ограничение задачи в виде неравенств “³”. В этом случае в качестве начального выбирается базис в недопустимой области (базисные переменные отрицательные) и с помощью двойственного симплекс – метода осуществляется переход в ОДР.

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

Алгоритм метода:

1) Если все базисные переменные положительны, то далее используется симплекс – метод, иначе из базиса исключается переменная с наибольшим по модулю отрицательным значением.

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

3) Симплекс – таблица преобразовывается по известным правилам, переходим на пункт 1.

Пример 2. 11. 3.

f₀=2х₁+4х₂→maх

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

                          3х₁+4х₂+х₃=1700

2х₁+5х₂+х₄=1600

получили следующее оптимальное решение:

Таблица 40

№ итерации	Базис	х2	х2	х3	Х4	Значение
№=2 оптимум	f ур	0	0	2/7	4/7	1400
	х1	1	0	5/7	-4/7	300
	х2	0	1	-2/7	3/7	200

 

Спрос на изделие х₁ и х₂ упал. Недельная продажа изделий обоих видов ограничена 450 шт., то есть необходимо включать в модель дополнительное ограничение: х₁+х₂ £ 450. Это ограничение нарушается при оптимальном решении: х₁+х₂ = 500 >450.

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

х₁+ × х₃ - × х₄=300   Þ             х₁=300 - × х₃+ × х₄

х₂ - × х₃+ × х₄=200  Þ             х₂=200+ × х₃ - × х₄

Выражения для х₁ и х₂ подставляем в дополнительном ограничении, записанное в канонической форме:

х₁+х₂+х₅ = 450

300 - × х₃+ × х₄+200+ × х₃ - × х₄+ х₅=450

- × х₃ - × х₄ + х₅ = 450 - 500 = - 50

Добавляем к симплекс–таблице столбец х₅ и строку нового ограничения. Базисная переменная имеет недопустимое отрицательное значение х₅ =-50, так как х₃=х₄=0. Согласно двойственному симплекс – методу х₅ подлежит удалению из базиса, а вместо нее вводится в базис х₃. Свободная переменная, которая включается в базис вместо х₅, отыскивается по строке х₅ симплексной таблицы среди переменных с отрицательными коэффициентами.

Таблица 41

№ Итер.	базис	х1	х2	х3	х4	х5	Знач	Отнош	Формула
N=0 x 3 -вв, х5 -искл.	f ур	0	0	2/7	4/7	0	1400
	х1	1	0	5/7	-4/7	0	300
	х2	0	1	-2/7	3/7	0	200
	х5	0	0	-3/7	1/7	1	-50	-50:(-3/7)
N=1 Оптимум	f ур	0	0	0	2/3	2/3	4100/3		f ур = f ур - 2/7 × х3
	х1	1	0	0	-1/3	5/3	650/3		х1=х1 - 5/7 × х3
	х2	0	1	0	1/3	-2/3	700/3		х2=х2+2/7 × х3
	х3	0	0	1	-1/3	-7/3	350/3		х3=х5:(- 3/7)

 

Получили новое оптимальное решение, которое удовлетворяет введенному дополнительному ограничению х₁+х₂ £ 450:

m ах f = =1366,67 при плане Х*=(216,67;233,33).