Идея использования искусственных переменных предполагает включение неотрицательных переменных в левую часть каждого из уравнений, в которых не содержится очевидных начальных базисных переменных (когда неравенство имеет знак ”³” или задано в виде равенства). Эти дополнительно вводимые переменные выполняют ту же роль, что и остаточные переменные. Но так как искусственные переменные не имеют отношения к поставленной задаче (отсюда их название - искусственные), то их введение допустимо только в том случае, если симплекс метод будет обеспечивать получение оптимального решения, в котором все искусственные переменные будут равны 0, то есть эти переменные следует использовать только для стартовой точки, причем итерационный метод оптимизации должен "вынуждать" эти переменные принимать нулевые значения в конечном оптимальном решении, обеспечивая допустимость оптимума. Разработаны два метода получения стартовой точки:
1) М - метод или метод больших штрафов.
2) Двухэтапный метод.
Метод больших штрафов
Для построения требуемой схемы вычислений можно применить следующий прием: наложить штраф за использование искусственных переменных, равный сумме искусственных переменных, умноженный на очень большое число М (М>>1).
При поиске минимума штраф прибавляется к целевой функции.
,
при поиске максимума f вычитается из нее
.
Алгоритм метода:
1) Добавить искусственные переменные Ri в ограничения вида “=” и “ 
”. Из ограничений “ ” предварительно следует вычесть избыточную переменную.
2) Выразить Ri из соответствующего ограничения через небазисные переменные и подставить в штраф.
3) Решить задачу симплекс-методом. Если в оптимальной симплекс–таблице искусственные переменные остались в базисе и не равны нулю, то это означает, что исходная задача не имеет решения.
|
|
Пример 2. 11.1:
| В стандартной форме | В канонической форме |
| f0= 4x1 + x2® min | f0= 4x1 + x2® min |
| при ограничениях | При ограничениях |
 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 |
В первом и втором уравнениях нет переменных, выполняющих роль остаточных. Поэтому введем в каждое из этих уравнений по одной искусственной переменной R1 и R2.
3×х1 + х2+R1 = 3
4×х1 + 3×х2 - x3+R2 =6
За использование R1 и R2 в состав целевой функции можно ввести штраф, приписывая переменным R 1 и R2 достаточно большой положительный коэффициент M (М>>1). При поиске mах f этот штраф, равный
,
где е – число искусственных переменных,
вычитается из целевой функции, а при поиске min f прибавляется к целевой функции.
f = 4×x1 + x2 + M×R1 + M×R2® min
при ограничениях
3×х1 + х2+R1 = 3 R1=3 – 3x1 – x2
4×х1 + 3×х2 - x3+R2= 6 R2=6 – 4x1-3x2+x3
x1+2×x2+x4= 4
x1, x2, x3, x4, R1, R2³0
n = 6, m = 3,
n - m = 3 - число небазисных переменных.
Небазисные переменные х1, х2, х3 равны нулю, тогда начальный базис R1 = 3; R2=6;, x4 = 4.
Так как мы имеем дело с задачей минимизации f, то в оптимальном решении переменные R1 и R2, обратятся в нуль. Заметим, что все промежуточные итерации, предшествующие получению минимума, с точки зрения окончательного результата, не имеют значения.
Далее следует выразить переменные R1 и R2 из (1) и (2) уравнений через небазисные переменные и подставить в целевую функцию. Получим следующее выражение для целевой функции.
|
|
f = 4×x1+x×2+M×(3–3×x1–x2)+M×(6–4×x1–3×x2+x3)
f = (4-7M)×x1+(1-4M)×x2+Mx3+9M
В начальном базисе
fур (- 4 + 7M)×x1 + (-1 + 4M)×x2 – Mx3= 9×M
результаты вычислений приведены в табл.38
Таблица 36
| № итер | Ба-зис | х1 | х2 | х3 | х4 | R1 | R2 | Знач | Отнош | Формула |
| №=0 х1 вв, R1 искл | fур | -4+7M | -1+1M | -M | 0 | 0 | 0 | 9M | ||
| R1 | 3 | 1 | 0 | 0 | 1 | 0 | 3 | 3:3=1 | ||
| R2 | 4 | 3 | -1 | 0 | 0 | 1 | 6 | 6:4=1,5 | ||
| x4 | 1 | 2 | 0 | 1 | 0 | 0 | 4 | 4:1=4 | ||
| №=1 х2 вв, R2 искл. | fур | 0 | 
| -M | 0 | 
| 0 | 2M+4 | fур=fур+(4-M)×х1 | |
| х1 | 1 | 1/3 | 0 | 0 | 1/3 | 0 | 1 | 1: 1/3=3 | х1=R1:3 | |
| R2 | 0 | 5/3 | -1 | 0 | -4/3 | 1 | 2 | 2:  =1,2
| R2=R2-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ур-(5M+  )х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=R2: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 |
Оптимальное решение:
х1*= 2/5; х2*= 9/5; х3*= 1;
min f0*= 17/5 (R1*, R2*, X4* = 0), т.е. Х*(2/5; 9/5; 1; 0)
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.
Если задача не имеет допустимого решения, то в полученном оптимальном решении, по крайней мере, одна искусственная переменная останется в базисе и будет отлична от нуля.
Двухэтапный метод
Недостаток M-метода связан с возможностью ошибок в вычислениях, обусловленной очень большой величиной коэффициента M. Например, если принять M=100000, тогда коэффициенты при х1 и х2 в f -уравнении начальной симплекс таблицы будут равны (-4 + 700000) и (-1 + 400000) соответственно. Из-за большой величины M вклад коэффициентов C1= 4 и C2= 1 при х1 и х2 оказывается ничтожно мал. Поэтому возникает опасность, что переменные х1 и х2 будут интерпретироваться как переменные, фигурирующие в целевой функции с нулевыми коэффициентами.
|
|
Двухэтапный метод позволяет избежать этих затруднений. В нем так же вводятся искусственные переменные, но без коэффициента M. Решение задачи расчленяется на два этапа.
Этап 1. Искусственная переменная вводится для получения начального базиса. Записывается новая целевая функция f1, предусматривающая минимизацию суммы искусственных переменных при исходных ограничениях, видоизмененных за счет введения искусственных переменных.
Если минимальное значение новой целевой функции равно нулю, (то есть искусственные переменные равны нулю), то исходная задача имеет допустимое решение. Переходят тогда к этапу 2.
Если min f1¹ 0, то исходная задача не имеет допустимых решений.
Этап 2. Оптимальное базисное решение, полученное на этапе1, используется в качестве начального базиса исходной задачи.
Пример 2. 11. 1: Рассмотрим предыдущий пример:
f0= 4х1 + х2 ® min
при ограничениях:
3×х1 + х2+R1=3 (1) Þ R1=3 – 3×х1 – х2
4×х1 + 3×х2 -х3+R2= 6 (2) Þ R2=6 – 4×x1-3×х2+х3
х1+2×х2+х4=4 (3)
R1, R2³0
xi³ 0 i=1, 2,..,4
R1+R2=9-7×х1-4×х2+х3
Этап 1. Решается задача f1ур = R1 + R2® min.
Тогда целевая функция
f1ур = 9 – 7х1 – 4х2 + х3®min
при ограничениях исходной задачи
Составим исходную симплекс - таблицу, за начальный базис возьмем R1, R2, х4, свободные переменные
х1 = х2 = х3 = 0
f1ур – х3+ 7х1 + 4х2 = 9
Таблица 37
| № итер | Базис | х1 | х2 | х3 | х4 | R1 | R2 | Знач | Отнош | Формула |
| №=0 х1 вв., R1 искл. | f1ур | 7 | 4 | -1 | 0 | 0 | 0 | 9 | ||
| R1 | 3 | 1 | 0 | 0 | 1 | 0 | 3 | 3:3=1 | ||
| R2 | 4 | 3 | -1 | 0 | 0 | 1 | 6 | 6:4=3/2 | ||
| x4 | 1 | 2 | 0 | 1 | 0 | 0 | 4 | 4:1=4 | ||
| №=1 х2 вв., R2 искл. | f1ур | 0 | 5/3 | -1 | 0 | -7/3 | 0 | 2 | f1ур=f1ур-7х1 | |
| х1 | 1 | 1/3 | 0 | 0 | 1/3 | 0 | 1 | 1:1/3=3 | х1=R1: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 этапа | f1ур | 0 | 0 | 0 | 0 | -1 | -1 | 0 | f1ур=f1ур-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/3x2 |
R1*=R2*= 0 х1*=3/5; х2*=6/5; х3*=0; x4*=1; f1ур *= 0
Получили допустимое базисное решение исходной системы ограничений, так как f1ур *= 0 при R1*=R2*= 0.
Этап 2. Искусственные переменные уже выполнили свою функцию, так что во всех последующих вычислениях они не должны фигурировать. Запишем из оптимальной симплекс таблицы уравнения ограничения:
х1+ 
х3= 
Þ х1= 
- 
х3
х2- 
х3= 
Þ х2= 
+ х3
х3+х4=1
Главная цель первого этапа обеспечить получение начального решения исходной системы ограничений. Теперь исходная задача содержит n = 4 переменных и m = 3 уравнения. Значит, число небазисных переменных n - m = 1. В полученном допустимом решении свободная переменная х3= 0, базисная
х1= , х2= , х4= 1.
Выразим целевую функцию через свободную переменную х3, подставив выражения для базисных переменных х1 и х2 через небазисную переменную х3.
f0 = 4х1 + х2 = 
- 
х3+ 
+ 
х3= 
- 
х3® min
f0ур х3=
В результате будем иметь начальную симплекс - таблицу для 2–го этапа.
Таблица 38
| № итер. | Базис | х1 | х2 | х3 | х4 | Знач | Отнош | Формула |
| №=3 x3 вв., х4 искл. | f0ур | 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 оптим. реше-ние | f0ур | 0 | 0 | 0 | -1/5 | 17/5 | f0ур=f0ур-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/5x3 | ||
| х3 | 0 | 0 | 1 | 1 | 1 | x3=x4 |
Полученное решение оптимально, так как коэффициент при х4<0, а решается задача min f0
х1*= 
, х2*= , х3*= 1, х4*=0
min f0 = 4х1* + х2* = 4 
+ = 
.
Замечание:
1) Количество необходимых итераций в М – методе и двухэтапном методе всегда одинаково (в нашем случае 3 итерации), а между симплекс-таблицами, которые получаются при использовании этих методов, имеется взаимнооднозначное соотношение.
2) На 2 этапе искусственные переменные отсутствуют только в том случае, если в конце 1 этапа они стали не базисными. Однако возможен случай, который при завершении 1 этапа искусственные переменные, имея нулевые значения, останутся базисными.
Пример 2. 11. 2:
Математическая модель
f0=3×х1+2×х2+3×х3®min
при ограничениях:
х1+4×х2+х3 ³ 7
2×х1+х2+х4 ³ 10
хi ³ 0 i=1,..,4
В канонической форме
х1+4×х2+х3-х5+R=7 Þ R =7-х1-4х2-х3+х5
2×х1+х2+х4-х6=10
хi³ 0 i=1, 2,..,6; R³ 0
В качестве базисных переменных возьмем R и х4, которые входят лишь в одно ограничение.
Первый этап:
f1ур =R=7-х1-4×х2-х3+х5®min
при ограничениях:
х1+4×х2+х3-х5+R=7
2×х1+х2+х4-х6=10
f1ур х1 + 4×х2+х3 -х5=7
Таблица 39
| № итер. | Базис | х1 | х2 | х3 | х4 | х5 | х6 | R | Знач | Отнош | Формула |
| N=0 x2 вв, 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 | f1ур=f1ур-4x3 | |
| х2 | 1/4 | 1 | 1/4 | 0 | -1/4 | 0 | 1/4 | 7/4 | x2=R:4 | ||
| X4 | 7/4 | 0 | -1/4 | 1 | 1/4 | -1 | -1/4 | 3 | x4=х4-х2 |
Второй этап:
Выразим базисную переменную х2 через небазисные переменные. Из оптимальной симплекс–таблицы первого этапа:
х1+х2+ х3- 
х5 = 
Þ х2= 
- х1- 
х3+ х5
Подставим х2 в f0:
f0 = 3х1+2х2+3х3=3х1+2( - х1- х3+ х5)+3×х3=3х1+ 
- 
х1- х3+ 
х5+3×х3== 
х1+ х3+ 
х5+ ® min
В целевую функцию f0 свободные переменные х1, х2, х5 входят с положительными коэффициентами, поэтому их увеличение нецелесообразно, т.е. min f0 = 
при плане Х*=(0; 
; 0; 3; 0)