Суть метода искусственного базиса

В случаях, когда сразу не выделяются базисные переменные (а они сразу выделяются только после приведения к каноническому виду задачи, в которой имеются только неравенства типа «≤» при неотрицательных правых частях) можно применять так называемый метод искусственного базиса, который является по сути разновидностью симплекс-метода.

Пусть задача приведена к каноническому виду (1.6), в котором в некоторых уравнениях, скажем в i1-м, i2-м, …, is-м, явно не выделяются базисные переменные. Добавим в эти уравнения искусственные переменныеxm+1, xm+2, …, xm+s, а в целевую функцию - слагаемые ±Mxm+1, ±Mxm+2, …, ±Mxm+s, где M>>1 (M - достаточно большое положительное число) причём «±» - это «+», если решается задача на min, и «±» - это «-», если решается задача на max. Получается новая задача, которая называется дополнительной или вспомогательной.

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

c1x1+c2x2+…+cnxn+Mxn+m+1+Mxn+m+2+…+Mxn+2m®min

Суть метода искусственного базиса - student2.ru

Аналогично, если задача (2.1) решается на max и придётся вводить искусственные переменные во все ограничения, то получаем следующую вспомогательную задачу:

c1x1+c2x2+…+cnxn-Mxn+1-Mxn +2-…-Mxn+m®max

Суть метода искусственного базиса - student2.ru (5.1)

5.1.1. Если ( Суть метода искусственного базиса - student2.ru , Суть метода искусственного базиса - student2.ru , …, Суть метода искусственного базиса - student2.ru , Суть метода искусственного базиса - student2.ru , …, Суть метода искусственного базиса - student2.ru ) оптимальное решение вспомогательной задачи, где Суть метода искусственного базиса - student2.ru , …, Суть метода искусственного базиса - student2.ru - значения искусственных переменных, Суть метода искусственного базиса - student2.ru , Суть метода искусственного базиса - student2.ru , …, Суть метода искусственного базиса - student2.ru - значения переменных в исходной задаче в канонической форме, то Суть метода искусственного базиса - student2.ru =…= Суть метода искусственного базиса - student2.ru =0 и ( Суть метода искусственного базиса - student2.ru , Суть метода искусственного базиса - student2.ru , …, Суть метода искусственного базиса - student2.ru ) - оптимальное решение исходной задачи. При этом значения целевой функции исходной и вспомогательной задач совпадают.

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

1. Привести задачу к каноническому виду.

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

3. Решить вспомогательную задачу, и если ( Суть метода искусственного базиса - student2.ru , Суть метода искусственного базиса - student2.ru , …, Суть метода искусственного базиса - student2.ru , Суть метода искусственного базиса - student2.ru , …, Суть метода искусственного базиса - student2.ru ) - оптимальное решение вспомогательной задачи, где x1, x2, …, xm - основные и дополнительные переменные (из задачи в каноническом виде), xm+1, xm+2, …, xm+s - искусственные переменные то ( Суть метода искусственного базиса - student2.ru , Суть метода искусственного базиса - student2.ru , …, Суть метода искусственного базиса - student2.ru ) - решение задачи в каноническом виде. Оптимальное значение целевой функции вспомогательной задачи равно оптимальному значению исходной задачи.

При этом к вспомогательной задаче применяется обычный симплекс-метод с некоторыми своими особенностями:

1. Так как целевая функция вспомогательной задачи имеет слагаемые с коэффициентами ±M, то оценки Dk имеют вид Суть метода искусственного базиса - student2.ru ± Суть метода искусственного базиса - student2.ru M, причём M - достаточно большое число. Поэтому при Суть метода искусственного базиса - student2.ru ≠0 знак Dk фактически определяется знаком при Суть метода искусственного базиса - student2.ru . В связи с этим в симплекс-таблице на начальном этапе (пока в базис входят искусственные переменные) вместо одной строки Dk записывают две строки Суть метода искусственного базиса - student2.ru и Суть метода искусственного базиса - student2.ru , и при применении критерия оптимальности ориентируются только на строку Суть метода искусственного базиса - student2.ru .

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

3. После того, как все искусственные переменные будут выведены из базиса, коэффициенты Dk при M будут равны нулю, в таблице остаётся только строка Суть метода искусственного базиса - student2.ru =Dk.

Пример. Решить пример из предыдущего параграфа методом искусственного базиса.

Решение. Напоминаем задачу:

-3x1+x2+2x3 ® max(min)

Суть метода искусственного базиса - student2.ru

1. Приведём задачу к каноническому виду:

-3x1+x2+2x3 ® max(min)

Суть метода искусственного базиса - student2.ru

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

Суть метода искусственного базиса - student2.ru

В целевую функцию они войдут с коэффициентами M или -M в зависимости от того, решается задача на min или на max.

Решим задачу на максимум. Тогда вспомогательная задача - следующая:

-3x1+x2+2x3-Mx6-Mx7 ® max

Суть метода искусственного базиса - student2.ru

3. Решаем полученную вспомогательную задачу с применением симплекс-таблиц:

Базис Сб Своб. чл. -3 -M -M q2 q3    
x1 x2 x3 x4 x5 x6 x7    
x6 -M -1 min
x4 -    
x7 -M -1    
Суть метода искусственного базиса - student2.ru -1 -2    
Суть метода искусственного базиса - student2.ru -8 -2 -3    

Здесь D2=-2M-1, D3=-3M-2. Коэффициенты при M записаны в строке Суть метода искусственного базиса - student2.ru . Имеем, что D2<0 и D3<0, то есть для переменных x2 и x3 нарушается критерий оптимальности. Поэтому в базис будем вводить x2 или x3. Какую именно из этих переменных, и вместо какой из искусственных (вместо x6 или вместо x7), определяем с помощью столбцов q2 и q3. На пересечении столбца q2 и строк Суть метода искусственного базиса - student2.ru и Суть метода искусственного базиса - student2.ru числа соответственно 2 и 4 означают, что в случае включения в базис x2 значение функции возрастёт на -q2D2=4M+2, а в случае включения в базис x3 значение функции возрастёт на -q3D3=3M+2<-q2D2. Поэтому в базис включаем x2 (что обеспечивает большее возрастание функции и в конечном итоге ускоряет процесс решения задачи). Так как min Суть метода искусственного базиса - student2.ru =2 достигается в строке x6, то из базиса исключаем x6. Строим новую симплекс-таблицу, в который уже столбец с искусственной переменной x6 отсутствует (вычеркнут), так как искусственная переменная x6 из дальнейшего процесса исключается. В новой таблице коэффициент при x2 в первой строке (которая теперь соответствует новой базисной переменной x2) равен 1, а во второй равен нулю. Поэтому первые две строки в новую таблицу переписываем из старой. Для того, чтобы в строке x7 при x2 получить 0, из строки x7 в старой таблице вычитаем новую первую. Получаем следующую, очередную, таблицу:

Базис Сб Своб. чл. -3 -M -M q1    
x1 x2 x3 x4 x5 x6 x7    
x2 -1   -  
x4      
x7 -M -1 -1   min
Суть метода искусственного базиса - student2.ru        
Суть метода искусственного базиса - student2.ru -4 -2        

Так как Dk<0 только для одного значения k=1, а именно, D1=-2M+2<0 (напоминаем, что M - достаточно большое число, так что -2M<2 и D1<0), то ищем только отношения q1. Минимум этих отношений достигается в строке x7: min Суть метода искусственного базиса - student2.ru =2. Поэтому искусственная переменная исключается из базиса, а вместо неё в базис включается x1.

Искусственные переменные теперь исключены из базиса. Поэтому дальше работаем с обычной симплекс-таблицей, в которой новая третья строка (соответствующая переменной x1) получается делением старой третьей строки на 2. Затем эту новую третью прибавляем к старой первой и вычитаем из старой второй. В результате в новой таблице в столбце x1 появятся соответственно 0, 0 и 1:

Базис Сб Своб. чл. -3
x1 x2 x3 x4 x5
x2 3/2 -1/2
x4 3/2 1/2
x7 -3 -1/2 -1/2
Dk -2

В полученной таблице Dk³0 для всех k=1, 2, …, 5, то есть критерий оптимальности выполнен. Поэтому X0=(2; 4; 0) является оптимальным решением, при котором значение целевой функции равно -2 (x4 в окончательном ответе не учитывается, так как она является дополнительной переменной, и не входит в первоначальную задачу).

Решим задачу на минимум (min). Тогда вспомогательная задача - следующая:

-3x1+x2+2x3-Mx6-Mx7 ® max

Суть метода искусственного базиса - student2.ru

Как и выше, решаем полученную вспомогательную задачу с применением симплекс-таблицы:

Базис Сб Своб. чл. -3 M M q2 q3    
x1 x2 x3 x4 x5 x6 x7    
x6 M -1 min
x4 -    
x7 M -1    
Суть метода искусственного базиса - student2.ru -1 -2    
Суть метода искусственного базиса - student2.ru -1    

Критерий оптимальности нарушается для переменных x2 и x3: D2=2M-1>0, D3=3M-2>0. Так как -q2D2=-4M+2 по абсолютной величине превосходит -q3D3=-3M+2, то в базис включаем x2. При этом min Суть метода искусственного базиса - student2.ru =2 достигается в строке x6, и из базиса исключаем x6. Переход к новой таблице аналогичен переходу при решении задачи на max:

Базис Сб Своб. чл. -3 -M -M q1    
x1 x2 x3 x4 x5 x6 x7    
x2 -1   -  
x4      
x7 -M -1 -1   min
Суть метода искусственного базиса - student2.ru        
Суть метода искусственного базиса - student2.ru -1 -1        

Теперь D1>0. Поэтому переход к новой таблице аналогичен соответствующему переходу при решении задачи на max: в базис вводится x1 вместо x7:

Базис Сб Своб. чл. -3 q3 q5
x1 x2 x3 x4 x5
x2 3/2 -1/2 8/3 -
x4 3/2 1/2 4/3
x7 -3 -1/2 -1/2 - -
Dk -2 -4/3 -4

Имеем D3=1>0 и D5=1>0. Так как |-q5D5|=|-q3D3|, то вводим в базис x5 (вместо x4): сначала умножаем 2-ю строку на 2, а затем новую вторую строку, умноженную на ½, прибавляем к первой и третьей (фактически вторую старую прибавляем к первой и третьей):

Базис Сб Своб. чл. -3
x1 x2 x3 x4 x5
x2
x4
x7 -3
Dk -6 -2 -2

В полученной таблице Dk£0 для всех k=1, 2, …, 5, то есть критерий оптимальности выполнен. Поэтому X0=(4; 6; 0) является оптимальным решением, при котором значение целевой функции равно -6.

Ответ: Fmin=-6, минимум достигается в точке X2=(4; 6; 0);

Fmax=-2, максимум достигается в точке X1=(2; 4; 0).

5.2. Упражнение. Решить соответствующие задачи линейного программирования из Упражнения 1.3 методом искусственного базиса.

Теория двойственности

Наши рекомендации