Жолобов Ввведение в Математическое 2008
.pdfПример 1.11(продолжение)
Исходная табл. 1 уже является лексикографически допустимой, поэтому остается лишь следовать алгоритму лексикографического сим- плекс-метода при определении выводимого из базиса вектора, чтобы избежать зацикливания. В табл. 1 альтернатива отсутствует – единственный вектор, который может быть выведен из базиса – это вектор A1:
|
Баз |
|
Cбаз |
|
A0 |
0 |
|
0 |
|
0 |
|
0 |
300 |
80 |
-1219 |
|
-1 |
|||||||||||||
|
|
|
|
A1 |
|
|
A2 |
|
|
A3 |
|
A4 |
|
A5 |
|
|
A6 |
|
|
A7 |
A8 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
A2 |
0 |
0 |
0 |
|
1 |
|
0 |
|
|
0 |
|
-8 |
|
|
|
-2 |
|
|
30 |
|
|
1/2 |
|||||||
|
A1 |
|
0 |
|
0 |
|
1 |
|
|
0 |
|
|
0 |
|
|
0 |
|
19/2 |
5/2 |
|
|
-38 |
|
-2/3 |
||||||
|
A3 |
0 |
1 |
0 |
|
0 |
|
1 |
|
|
0 |
|
40 |
|
|
|
-3 |
|
|
90 |
|
|
1 |
|||||||
|
A4 |
0 |
1 |
0 |
|
0 |
|
0 |
|
|
1 |
|
0 |
|
|
|
0 |
|
|
|
0 |
|
|
1 |
||||||
|
Tабл. 1 |
|
|
0 |
0 |
|
0 |
|
0 |
|
|
0 |
|
-300 |
-80 |
|
1219 |
|
1 |
|||||||||||
|
A2 |
0 |
0 |
16/19 |
|
1 |
|
0 |
|
|
0 |
|
0 |
|
|
|
2/19 |
-2 |
|
|
-7/114 |
|||||||||
|
A5 |
|
300 |
|
0 |
|
2/19 |
|
|
0 |
|
|
0 |
|
|
0 |
|
1 |
|
|
|
5/19 |
|
-4 |
|
|
-4/57 |
|||
|
A3 |
0 |
1 |
-80/19 |
0 |
|
1 |
|
|
0 |
|
0 |
|
|
|
-257/19 |
250 |
|
217/57 |
|||||||||||
|
A4 |
0 |
1 |
0 |
|
0 |
|
0 |
|
|
1 |
|
0 |
|
|
|
0 |
|
|
|
0 |
|
|
1 |
||||||
|
Табл.2 |
0 |
600/19 |
0 |
|
0 |
|
|
0 |
|
0 |
|
|
|
-20/19 |
19 |
|
|
-1143/57 |
|||||||||||
|
|
Однако, в табл. 2 появляются две альтернативы: |
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x10 |
|
|
x20 |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
0 |
min |
xk 0 |
|
|
|
|
0. |
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
x2s |
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
xks |
0 |
xks |
|
x1s |
|
|
|
|
|
|
|
|
||||||||
|
|
Рассмотрим столбец A1 вместо столбца A0: |
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
xk1 |
|
|
|
|
|
16 |
19 |
|
|
2 |
19 |
} 2 |
x21 |
|
|||||||
|
|
|
|
|
|
min |
min{ |
|
|
; |
|
. |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
5 |
|
|
|
5 |
|
|
x2s |
|
|||
|
|
|
|
|
|
|
xks 0 |
xks |
|
|
|
|
|
|
19 |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
19 |
|
|
|
|
|
|
|
|
Выведем из базиса вектор A5. В этой таблице проиллюстрировано решение, принимаемое с помощью лексикографического правила, отличающееся от решения, принимаемого с использованием обычного сим- плекс-метода. Продолжим решение задачи.
61
|
Баз |
|
Cбаз |
|
A0 |
0 |
0 |
0 |
0 |
300 |
80 |
-1219 |
-1 |
|||||||
|
|
|
|
A1 |
|
A2 |
|
A3 |
|
A4 |
|
A5 |
|
A6 |
|
A7 |
A8 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
A2 |
0 |
0 |
4/5 |
1 |
0 |
0 |
-2/5 |
0 |
-2/5 |
-1/30 |
|||||||||
|
A6 |
80 |
0 |
2/5 |
0 |
0 |
0 |
19/5 |
1 |
-76/5 |
-4/15 |
|||||||||
|
A3 |
0 |
1 |
6/5 |
0 |
1 |
0 |
257/5 |
0 |
222/5 |
1/5 |
|||||||||
|
A4 |
|
0 |
|
1 |
|
0 |
|
0 |
|
0 |
|
1 |
|
0 |
|
0 |
|
0 |
1 |
|
Табл.3 |
|
|
0 |
32 |
0 |
0 |
0 |
4 |
0 |
3 |
-61/3 |
||||||||
|
A2 |
0 |
1/30 |
4/5 |
1 |
0 |
1/30 |
-2/5 |
0 |
-2/5 |
-7/114 |
|||||||||
|
A6 |
80 |
4/15 |
2/5 |
0 |
0 |
4/15 |
19/5 |
1 |
-76/5 |
-4/57 |
|||||||||
|
A3 |
0 |
4/5 |
6/5 |
0 |
1 |
-1/5 |
257/5 |
0 |
222/5 |
217/57 |
|||||||||
|
A8 |
-1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|||||||||
|
Табл.4 |
|
|
61/3 |
32 |
0 |
0 |
61/3 |
4 |
0 |
3 |
0 |
Втабл. 4 получено оптимальное решение.
1.2.13.Метод вспомогательной задачи
Втом случае, когда система ограничений задачи не содержит полного набора единичных векторов, который можно было бы принять в качестве базиса исходного опорного решения, прибегают к методу искусственного базиса.
Основная идея этого метода –использование симплекс-метода для отыскания опорного решения и вычисления коэффициентов разложения всех векторов задачи по базису найденного решения.
Для этого в задачу вводятся искусственные переменные, векторы коэффициентов при которых называются искусственными векторами.
Целевая функция строится таким образом, чтобы в процессе решения задачи симплекс-методом при переходе от одного опорного решения к другому искусственные векторы, входящие в базис, заменялись векторами основной задачи – основными векторами.
Взависимости от конкретного способа построения ЦФ, в результате решения новой задачи формируется допустимое или оптимальное решение исходной задачи или устанавливается факт неразрешимости последней.
Наиболее популярными способами реализации метода искусственного базиса являются два метода: метод вспомогательной задачи ("двухэтапный метод") и метод М-задачи ("метод больших штрафов"). Рассмотрим сначала первый метод.
62
Пусть дана задача ЛП: |
|
|
||
c1x1 |
+ c2x2 |
+ ...+cnxn max |
|
|
a11x1 |
+ a12x2 + ...+a1nxn = a1 |
|
||
a21x1 |
+ a22x2 |
+ ...+a2nxn = a2 |
(1.52) |
|
............................................ |
||||
|
am1x1 + am2x2+ ...+amnxn= am xj 0, j=1,2,...,n,
в которой все свободные члены неотрицательны (ai 0, i=1,2,...,m).
Вспомогательная задача имеет вид: |
|
|
|
|||
-xn+1 - xn+2 - |
...-xn+m max, |
|
|
|||
a11x1 |
+ a12x2 |
+ ... |
+a1nxn+ xn+1 |
= a |
|
|
a21x1 |
+ a22x2 |
+ ... |
+a2nxn |
+ xn+2 |
= a2 |
(1.53) |
.............................................. |
|
|||||
|
|
|||||
am1x1 |
+ am2x2 |
+ ... |
+amnxn |
+ xn+m = am |
|
xj 0, j=1,2,...,n+m.
В этой задаче переменные xn+1, xn+2,...,xn+m – искусственные. Им соответствует полный набор единичных (искусственных) векторов.
Задача (1.53) имеет очевидное опорное решение: x' = (0,0,...,0,a1,a2,...,am),
в котором первые n нулей – значения основных переменных
x1,x2,...,xn, а базисные переменные xn+1, xn+2,...,xn+m (искусственные) имеют значения a1, a2, ..., am соответственно.
Это решение имеет единичный базис:
B=(An+1,An+2,...,An+m)=E,
следовательно, можно заполнить первую симплекс-таблицу и решить задачу симплекс-методом.
Задача (1.53) всегда имеет оптимальное решение, так как ее ЦФ ограничена сверху на допустимом множестве - не может принять значение большее нуля.
Пусть получено оптимальное решение вспомогательной зада-
чи:
x* ( x1* , x2* ,..., xn* , xn* 1 , xn* 2 ,..., xn* m ) |
(1.54) |
В зависимости от того, входят ли искусственные векторы в базис оптимального решения (1.54) и какие при этом значения имеют искусственные переменные, относительно исходной задачи (1.52) можно сделать различные выводы.
63
Случай 1. Среди чисел xn* 1 , xn* 2 ,..., xn* m есть отличные от нуля. В
этом случае исходная задача не имеет допустимых решений. Действительно, предположим от противного, что исходная
задача имеет допустимое решение x'=(x'1,x'2,...,x'n).
Тогда очевидно, что вектор x"=(x'1,x'2,...,x'n,0,0,...,0),
в котором все искусственные переменные имеют нулевое значение, является допустимым решением вспомогательной задачи (1.53). На этом решении ее ЦФ принимает нулевое значение - большее, чем на оптимальном решении (1.54), так как среди чисел xn* 1 ,xn* 2 ,...,xn* m есть строго положительные.
Полученное противоречие доказывает неправомерность предположения о допустимости исходной задачи.
Пример 1.12. Дана задача линейного программирования:
|
|
|
2x1 - 15x2 max |
|
|
|
|||||
|
|
|
x1 +4x2 |
= 2 |
|
|
|
|
|
||
|
|
|
3x1 - 8x2 = 7 |
|
|
|
|
||||
|
|
|
x1 ,x2 |
0. |
|
|
|
|
|||
Вспомогательная задача имеет вид: |
|
|
|
||||||||
|
|
|
-x3 - x4 |
max |
|
|
|
||||
|
|
|
x1 +4x2 |
+ x3 |
= 2 |
|
|
|
|||
|
|
|
3x1 - 8x2 + |
x4= 7 |
|
|
|
||||
|
|
|
x1 ,x2 |
0. |
|
|
|
|
|||
Ниже представлено решение вспомогательной задачи: |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Баз |
Cбаз |
A0 |
|
|
0 |
|
0 |
-1 |
-1 |
|
|
|
A1 |
|
A2 |
A3 |
A4 |
|
||||
|
A3 |
-1 |
2 |
|
|
1 |
|
4 |
1 |
0 |
|
|
A4 |
-1 |
7 |
|
|
3 |
|
-8 |
0 |
1 |
|
|
Tабл.1 |
-9 |
|
-4 |
|
4 |
0 |
0 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
Баз |
Cбаз |
A0 |
|
|
0 |
|
0 |
-1 |
-1 |
|
|
|
A1 |
|
A2 |
A3 |
A4 |
|
||||
|
A1 |
0 |
2 |
|
|
1 |
|
4 |
1 |
0 |
|
|
A4 |
-1 |
1 |
|
|
0 |
|
-20 |
-3 |
1 |
|
|
Tабл.2 |
-1 |
|
|
0 |
|
20 |
4 |
0 |
|
Ввиду того, что искусственная переменная x4 в оптимальном решении вспомогательной задачи отлична от нуля, исходная задача не имеет допустимых решений.
64
Случай 2. В оптимальном решении вспомогательной задачи все искусственные переменные имеют нулевое значение. В этом случае существенным фактором является вхождение искусственных переменных в базис оптимального решения вспомогательной задачи.
Случай 2a. В оптимальном базисе нет искусственных векторов. В этом случае получено опорное решение исходной задачи и известно разложение всех векторов задачи по базису опорного решения.
Для решения исходной задачи достаточно:
в полученной симплекс-таблице отбросить столбцы, связанные с искусственными переменными;
восстановить коэффициенты целевой функции исходной задачи;
пересчитать значение ЦФ и оценки всех свободных векторов.
Пример 1.13
Дана задача линейного программирования: |
|
|
|
|
|||||||||||
|
|
|
|
x1 |
+ 4x2 + x3 |
max |
|
|
|||||||
|
|
|
|
x1 |
- x2 |
+ x3 |
=3 |
|
|
|
|
||||
|
|
|
|
2x1 - 5x2 - x3 = 0 |
|
|
|
|
|||||||
|
|
|
|
x1 |
,x2 , x3 0. |
|
|
|
|
|
|
||||
Вспомогательная задача имеет вид: |
|
|
|
|
|||||||||||
|
|
|
|
-x4 |
- x5 |
max |
|
|
|
|
|||||
|
|
|
|
x1 |
- x2 |
+ x3 |
+ x4 |
=3 |
|
|
|||||
|
|
|
|
2x1 - 5x2 - x3 |
|
+ x5 |
= 0 |
|
|
||||||
|
|
|
|
xj |
0, (j=1 5). |
|
|
|
|
||||||
|
Ниже представлено решение вспомогательной задачи: |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
0 |
|
0 |
|
|
-1 |
-1 |
|
Баз |
Cбаз |
A0 |
A1 |
|
|
A2 |
|
A3 |
|
|
A4 |
A5 |
||
|
|
|
|
|
|
|
|
|
-1 |
|
|
|
|
|
|
|
A4 |
-1 |
3 |
|
1 |
|
|
|
1 |
|
|
1 |
0 |
||
|
A5 |
-1 |
0 |
|
2 |
|
|
|
-5 |
|
-1 |
|
|
0 |
1 |
|
Tабл. 1 |
-3 |
-3 |
|
|
6 |
|
0 |
|
|
0 |
0 |
|||
|
|
|
|
|
|
|
|
|
3/2 |
|
|
|
|
|
|
|
A4 |
-1 |
3 |
|
0 |
|
|
|
3/2 |
|
|
1 |
-1/2 |
||
|
A1 |
0 |
0 |
|
1 |
|
|
|
-5/2 |
|
-1/2 |
|
0 |
1/2 |
|
|
Табл.2 |
-3 |
|
0 |
|
|
|
-3/2 |
|
-3/2 |
|
0 |
3/2 |
||
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
A2 |
0 |
2 |
|
0 |
|
|
|
1 |
|
|
2/3 |
-1/3 |
||
|
A1 |
0 |
5 |
|
1 |
|
|
|
0 |
|
2 |
|
|
5/3 |
-1/3 |
|
Табл.3 |
0 |
|
0 |
|
|
|
0 |
|
0 |
|
|
1 |
1 |
Cледует отметить, что во второй симплекс-таблице столбец A0
не изменился – новое опорное решение совпадает со старым. Не изменилось и значение целевой функции. Это связано с тем, что исходное
опорное решение вспомогательной задачи – вырожденное.
65
Оптимальное решение вспомогательной задачи:
xвсп. =(5,2,0,0,0).
В базисе нет искусственных векторов, следовательно, получено опорное решение исходной задачи x. =(5,2,0), базис которого составляют векторы A2 , A1.
Теперь, отбросив столбцы, связанные с искусственными векторами, восстановив коэффициенты целевой функции, пересчитав значение целевой функции и оценки свободных векторов, сформируем сим- плекс-таблицу для решения исходной задачи симплекс-методом.
Баз |
Cбаз |
A0 |
1 |
4 |
1 |
A1 |
A2 |
A3 |
|||
|
|
|
|
|
|
A2 |
4 |
2 |
0 |
1 |
1 |
A1 |
1 |
5 |
1 |
0 |
2 |
Табл.3 |
13 |
0 |
0 |
5 |
Оценки всех векторов не отрицательные. Следовательно, в этой таблице записано оптимальное решение исходной задачи:
xопт=(5,2,0); Zопт=13.
Случай 2b. В оптимальный базис вспомогательной задачи входят искусственные векторы.
Рассмотрим симплекс-таблицу, соответствующую оптимальному решению вспомогательной задачи в случае 2b.
Баз |
Сбаз |
А0 |
|
0 |
0 |
... |
0 |
|
-1 |
... |
-1 |
||
|
|
|
|
|
А1 |
|
А2 |
|
Аn |
|
Аn+1 |
|
Аn+m |
A |
0 |
х10 |
|
х11 |
|
х12 |
|
х1n |
|
х1,n+1 |
|
х1,n+m |
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
... |
... |
... |
|
|
... |
... |
... |
... |
|
... |
... |
... |
|
A |
0 |
хl0 |
|
хll |
|
хl2 |
|
хln |
|
хl,n+1 |
... |
хl,n+m |
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
l |
|
|
|
|
|
|
|
|
|
|
|
|
|
A |
-1 |
0 |
|
|
|
|
|
|
|
|
хl+1,n+1 |
... |
хl+1,n+m |
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
l 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
... |
... |
... |
|
|
|
|
{xrs} |
|
|
... |
... |
... |
|
A |
-1 |
0 |
|
|
|
|
|
|
|
|
хm,n+1 |
... |
хm,n+m |
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
m |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Z' |
|
|
|
|
|
|
|
|
|
... |
|
|
|
|
|
1 |
|
2 |
|
n |
|
n+1 |
n+m |
Здесь для определенности принято, что первые l базисные векторы – основные (векторы исходной задачи): Ai1 , Ai2 ,..., Ail .
Векторы Ail 1 , Ail 2 ,..., Aim – искусственные. 66
Важно знать, существуют ли среди коэффициентов разложения основных векторов при искусственных базисных векторах отличные от нуля. Область этих коэффициентов выделена двойной рамкой.
Случай 2b1. Все xrs = 0 ( r |
|
|
; s |
|
), т.е. все коэффици- |
l 1, |
m |
1, n |
енты в отмеченной области имеют нулевое значение.
В этом случае любой вектор исходной задачи Аj ( j 1, n ) линейно выражается через основные векторы Ai1 , Ai2 ,..., Ail , входя-
щие в базис оптимального решения вспомогательной задачи:
Аj =x1j Ai1 + x2j Ai2 +...+ xlj Ail .
Таким образом, систему векторов ( Ai1 , Ai2 ,..., Ail ) можно при-
нять в качестве базиса опорного решения исходной задачи. В этом опорном решении базисные переменные xi1 , xi2 ,..., xil имеют значе-
ния x1j, x2j,..., xlj , соответственно, а свободные (остальные) – нулевое значение.
Отбросив строки и столбцы, связанные с искусственными переменными, можно перейти к решению основной задачи. Для этого нужно:
восстановить коэффициенты целевой функции;
пересчитать значение целевой функции;
вычислить оценки свободных векторов.
Всоответствующей симплекс-таблице будет l строк – меньше, чем количество ограничений исходной задачи. Это говорит о том, что в исходной задаче имеется m-l ограничений-уравнений, которые линейно выражаются через остальные уравнения, т.е. ранг матрицы системы ограничений равен l.
67
Пример 1.14
Дана задача линейного программирования:
4x1 + 5x2 + 3x3 - 7x4 max x1 + 2x3 + x4 =10
x2 + x3 - 2x4 = 2 4x2 +4x3 - 8x4 = 8 x1 ,x2 , x3,x4 0.
Вспомогательная задача имеет вид:
-x5 |
- x6 max |
|
x1 |
+ 2x3 + x4 |
=10 |
x2 + x3 - 2x4 +x5 |
= 2 |
|
4x2 |
+4x3 - 8x4 |
+x6= 8 |
x1 ,x2 , x3,x4 0
|
|
|
xj 0, (j=1 6). |
|
|
|
|
||
Ниже представлено решение вспомогательной задачи: |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
Баз |
Cбаз |
A0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
|||
|
|
|
|
|
|
|
|
|
|
|
A1 |
0 |
10 |
1 |
0 |
2 |
1 |
0 |
0 |
|
A5 |
-1 |
2 |
0 |
1 |
1 |
-2 |
1 |
0 |
|
A6 |
-1 |
8 |
0 |
4 |
4 |
-8 |
0 |
1 |
|
Tабл.1 |
-10 |
0 |
-5 |
-5 |
10 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
A1 |
0 |
10 |
1 |
0 |
2 |
1 |
0 |
0 |
|
A2 |
0 |
2 |
0 |
1 |
1 |
-2 |
1 |
0 |
|
A6 |
-1 |
0 |
0 |
0 |
0 |
0 |
-4 |
1 |
|
Tабл.2 |
0 |
0 |
0 |
0 |
0 |
5 |
0 |
Как видно из таблицы, коэффициенты разложения всех основных векторов при искусственном базисном векторе А6 имеют нулевое значение. Следовательно, можно переходить к решению исходной задачи, восстановив коэффициенты целевой функции, подсчитав ее значение и вычислив оценки свободных векторов А3 и А4 .
Решение основной задачи представлено ниже.
Баз |
Cбаз |
A0 |
4 |
5 |
3 |
-7 |
A1 |
A2 |
A3 |
A4 |
|||
|
|
|
|
|
|
|
A1 |
4 |
10 |
1 |
0 |
2 |
1 |
A2 |
5 |
2 |
0 |
1 |
1 |
-2 |
Tабл.1 |
50 |
0 |
0 |
10 |
1 |
Оптимальное решение исходной задачи: xопт=(10, 2, 0, 0); Zопт=50.
68
Случай 2b2. xrs 0 ( r |
|
|
; s |
|
), т.е. среди коэффициен- |
l 1, |
m |
1, n |
тов в области, выделенной в оптимальной симплекс-таблице вспомогательной задачи, имеются отличные от нуля.
В этом случае получено допустимое решение исходной задачи, однако для того чтобы продолжить решение, необходимо знать,
какие основные векторы в дополнение к векторам Ai1 , Ai2 ,..., Ail со-
ставляют базис найденного решения.
Для того чтобы получить опорное решение исходной задачи, найти базис этого решения и коэффициенты разложения основных векторов по найденному базису, используется следующий прием.
Пусть xrs 0 |
( r |
|
|
; s |
|
). Тогда основной вектор As |
l 1, |
m |
1, n |
принудительно вводится в базис вместо искусственного вектора Air и по обычным правилам пересчитывается симплекс-таблица.
Ввиду того, что xr0=0 (оптимальное решение вспомогательной задачи – вырожденное), столбец A0 не изменится.
Аналогичная процедура повторяется до тех пор, пока не возникнет одна из двух рассмотренных ранее ситуаций: 2a или 2b1. И в том, и в другом случае будет получено опорное решение исходной задачи и базис этого решения, состоящий только из основных векторов.
Пример 1.15
Дана задача линейного программирования:
-2x1 + x2 |
+ 6x3 - 4x4 max, |
||
x1 |
+ x2 |
+ x3 |
= 4 |
x2 |
-(1/3) x3 |
+ x4 |
= 2 |
-x1 +2x2 |
- x3 |
+3x4 = 2 |
x1 ,x2 , x3,x4 0.
Вспомогательная задача имеет вид:
-x5 |
- x6 -x7 |
max |
||
x1 |
+ x2 |
+ x3 |
+x5 |
|
x2 |
-(1/3) x3 |
+ x4 |
+x6 |
|
-x1 |
+2x2 |
- x3 |
+3x4 |
= 4
= 2
+x7 = 2
xj 0, (j=1 7).
Ниже представлено решение вспомогательной задачи:
69
Баз |
Cбаз |
A0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
||||
A5 |
-1 |
4 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
|
A6 |
-1 |
2 |
0 |
1 |
-1/3 |
1 |
0 |
1 |
0 |
|
A7 |
-1 |
2 |
-1 |
2 |
-1 |
3 |
0 |
0 |
1 |
|
Tабл.1 |
|
-8 |
0 |
-4 |
1/3 |
-4 |
0 |
0 |
0 |
|
A5 |
|
|
|
|
|
|
|
|
|
|
-1 |
3 |
3/2 |
0 |
3/2 |
-3/2 |
1 |
0 |
-1/2 |
||
A6 |
-1 |
1 |
1/2 |
0 |
1/6 |
-1/2 |
0 |
1 |
-1/2 |
|
A2 |
0 |
1 |
-1/2 |
1 |
-1/2 |
3/2 |
0 |
0 |
1/2 |
|
Табл.2 |
|
-4 |
-2 |
0 |
-5/3 |
2 |
0 |
0 |
2 |
|
A1 |
|
|
|
|
|
|
|
|
|
|
0 |
2 |
1 |
0 |
1 |
-1 |
2/3 |
0 |
-1/3 |
||
A6 |
-1 |
0 |
0 |
0 |
-1/3 |
0 |
-1/3 |
1 |
-1/3 |
|
A2 |
0 |
2 |
0 |
1 |
0 |
1 |
1/3 |
0 |
1/3 |
|
Табл.3 |
|
|
0 |
0 |
0 |
1/3 |
0 |
4/3 |
0 |
4/3 |
Коэффициент разложения основного вектора А3 по базису оптимального решения вспомогательной задачи при искусственном векторе А6 отличен от нуля (х23 = -1/3). Следовательно, вектор А6 нужно
вывести из базиса, а основной вектор А3 – ввести в базис. В результате
будет получена симплекс-таблица, в которой все базисные векторы – основные:
Баз |
Cбаз |
A 0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
|
A 1 |
A 2 |
A 3 |
A 4 |
A 5 |
A 6 |
A 7 |
||||
A1 |
0 |
2 |
1 |
0 |
0 |
-1 |
-1/3 |
3 |
-4/3 |
|
A3 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
-3 |
1 |
|
A2 |
0 |
2 |
0 |
1 |
0 |
1 |
1/3 |
0 |
1/3 |
|
Табл.4 |
|
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
Теперь можно приступить к решению основной задачи (как в случае 2а). Для этого:
восстанавливаются коэффициенты ЦФ;
вычисляется значение ЦФ на полученном опорном решении;
вычисляются оценки свободных векторов (в данном случае это единственный вектор А4 ).
Врезультате формируется следующая симплекс-таблица:
Баз |
Cбаз |
A 0 |
-2 |
1 |
6 |
-4 |
A 1 |
A 2 |
A 3 |
A 4 |
|||
A1 |
-2 |
2 |
1 |
0 |
0 |
-1 |
A3 |
6 |
0 |
0 |
0 |
1 |
0 |
A2 |
1 |
2 |
0 |
1 |
0 |
1 |
Tабл. 5 |
|
-2 |
0 |
0 |
0 |
7 |
70