3172
.pdfЗадачи для самостоятельного решения
Решить графическим методом следующие задачи:
4.2.1. 4x1 |
2x2 |
max |
||
2x1 |
3x2 |
18, |
|
|
x1 |
3x2 |
9, |
|
|
2x1 |
x2 |
|
10, |
|
x1 |
0, x2 |
|
0. |
|
4.2.3. x1 |
2x2 |
|
min |
|
x1 |
x2 |
1, |
|
|
x1 |
x2 |
|
2, |
|
x1 |
2x2 |
|
0, |
|
x1 |
0, x2 |
|
0. |
|
4.2.5. x1 |
3x2 |
|
max |
|
x1 |
x2 |
1, |
|
|
2x1 |
x2 |
|
2, |
|
x1 |
x2 |
|
0, |
|
x1 |
0, x2 |
|
0. |
|
4.2.2. 2x1 |
4x2 |
max |
|||
|
3x1 |
|
2x2 |
11, |
|
|
2x1 |
2x2 |
2, |
||
|
x1 |
3x2 |
0, |
|
|
|
x1 |
0, x2 |
0. |
||
4.2.4. 2x1 |
4x2 |
max |
|||
|
x1 |
x2 |
3, |
|
|
|
x1 |
2x2 |
12, |
||
|
3x1 |
|
x2 |
15, |
|
|
x1 |
0, x2 0. |
|||
4.2.6. x1 |
|
x2 |
max |
||
x1 |
2x2 |
10, |
|
||
x1 |
2x2 |
2, |
|
||
2x1 |
x2 |
10, |
|
||
x1 |
0, x2 |
0. |
|
4.2.7. x1 |
x2 |
max(min) |
4.2.8. |
2x1 |
3x2 |
max |
2x1 |
4x2 |
16, |
2x1 |
x2 |
10, |
|
4x1 2x2 8, |
2x1 3x2 6, |
|
||||
x1 |
3x2 |
9, |
2x1 |
4x2 |
8, |
|
x1 |
0, x2 |
0. |
x1 |
0, x2 |
0. |
|
4.2.9. x1 |
x2 |
max |
4.2.10. |
x1 |
2x2 |
max |
93
x1 |
2x2 |
14, |
4x1 |
2x2 |
12, |
5x1 3x2 |
15, |
x1 |
3x2 |
6, |
|
4x1 |
6x2 |
24, |
2x1 |
4x2 |
16, |
x1 |
0, x2 |
0. |
x1 |
0, x2 |
0. |
4.3. Алгоритм симплексного метода
Рассмотрим задачу линейного программирования, записанную в канонической форме:
|
|
|
|
|
z(x) |
cT x |
max |
(4.3.1) |
|
|
|
|
|
Ax |
b, (b |
0) |
(4.3.2) |
|
|
|
|
|
x |
0 , |
|
(4.3.3) |
где cT |
(c1 ,..., cn ) , x T (x1 ,..., x n ) , |
bT (b1 ,..., b m ) , A (aij ) , |
||||||
|
|
|
|
|
|
|
||
i 1, m , |
j 1, n |
|
|
|
||||
|
|
План ЗЛП x |
(x1, x 2 ,..., x n ) |
называется опорным планом |
(базисной точкой), если векторы-столбцы матрицы А: Ai1 ,..., Aik ,
k n , соответствующие его ненулевым координатам, линейно независимы.
Симплекс-метод решения ЗЛП (1)-(3) представляет собой итерационную процедуру последовательного перехода от одного базисного решения к другому с меньшим (большим) значением целевой функции до получения оптимального решения. Следует отметить, однако, что на начальном этапе решения обязательно наличие исходной базисной точки.
Известно, что число положительных координат базисной точки не может быть более, чем ранг матрицы r(А)= m. Если базисная точка содержит ровно т положительных координат, то она называется невырожденной, в противном случае - вырожденной. Задача называется невырожденной, если допустимое множество не имеет вырожденных базисных точек.
Перебор базисных точек осуществляется с помощью преобразований Жордана-Гаусса.
Пусть имеется исходная базисная точка допустимого множества ЗЛП xBT (xi ,i I; xj 0, j J ) . Координаты xi ,i I
94
будем в дальнейшем называть базисными, xj 0, j J -
небазисными. Соответственно множество I - множеством базисных (зависимых) индексов, J -множеством небазисных
(свободных) индексов. В случае невырожденной задачи каждой базисной точке соответствует известный базис, состоящий из
векторов Ai ,i I . Обозначим его через В. Заметим далее, что
каждая итерация метода Жордана-Гаусса соответствует переходу от одной базисной точки к другой при замене одной базисной (зависимой) переменной на одну небазисную (свободную). При этом выбору подлежит номер небазисной переменной k и жестко
определяется номер базисной переменной l ( alk 0 ). Координаты новой базисной точки вычисляются следующим образом:
H |
|
|
|
|
x l |
|
|
|
x l |
|
|
|
|
|
|
|
|
||||||||
x B |
(x i |
|
|
|
|
a ik , i I; x k |
|
|
|
; x j |
0, j J, j k). (4.3.4) |
|
|
a lk |
a lk |
||||||||||
|
|
|
|
|
|
|
Таким образом, получается алгоритм, позволяющий перебрать все базисные точки ЗЛП. Однако возникает естественное желание исключить из рассмотрения точки, обеспечивающие «худшее» значение целевой функции, нежели уже известные. С целью такой «фильтрации», вычислим значение целевой функции в
точке xBH , представленной в виде (4.3.4).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Обозначим |
|
|
xl |
|
min |
xi |
. Тогда |
|
|
|
|
|
|
|
|
|
|||||||
|
alk |
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
aik 0 |
aik |
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
z(x BH ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
(xi |
|
|
|
|
aik )ci |
|
ck |
ci xi |
( |
ciaik |
|
ck ). (4.3.5) |
|
||||||||||
|
i I |
|
|
|
|
|
|
|
|
|
|
i I |
|
|
|
i |
I |
|
|
|
|
||
Обозначим |
|
|
|
k |
|
ci aik ck |
(в |
матричной |
|
форме |
|||||||||||||
|
|
|
|
|
|
|
|
|
i |
I |
|
|
|
|
|
|
|
|
|
|
|
|
|
k cBT B 1 Ak |
ck , |
cB |
- вектор коэффициентов целевой функции |
||||||||||||||||||||
при базисных переменных). В таком случае |
z(xH ) z(x ) |
k |
. |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B |
|
B |
|
|
Отсюда |
видно, |
|
|
что |
если |
|
|
выбрано |
k такое, |
что |
k |
0 , |
то на |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
следующей итерации будет получена точка с большим значением
целевой функции (т.к. |
0 ). |
Если |
|
k |
0 , то произойдет |
уменьшение целевой функции, |
при |
k |
0 |
значение целевой |
|
|
|
|
|
|
95
функции не изменится. Если |
k |
0 , но все |
aik |
0 , то, выбирая |
любое положительное число |
в |
качестве |
, |
будем получать |
допустимую, но не базисную точку. (см. (4.3.4)). Значение целевой функции в этой точке изменяется в соответствии с формулой (4.3.5), откуда видно, что если выбирать как угодно большим, то значение функции цели будет как угодно увеличиваться. Следовательно, в таком случае можно сделать вывод о неограниченности целевой функции на допустимом множестве.
|
Теорема. |
Если |
|
некоторой |
|
|
базисной |
|
|
|
точке |
xB |
||||||||||||||
соответствует |
ситуация, |
при |
которой |
|
все |
|
k |
|
0 , |
то |
такая |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
точка является оптимальной в задаче (4.3.1 – 4.3.3). |
|
|
|
|
|
|
|
|||||||||||||||||||
|
Все вышесказанное позволяет сконструировать алгоритм |
|||||||||||||||||||||||||
базового симплекс метода. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Алгоритм базового симплекс метода |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
Задана исходная базисная точка x B : xTB |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
1. |
|
|
(xi ,i |
I; x j |
0, j |
J). |
||||||||||||||||||||
|
Вычислить оценки по формуле |
j |
|
|
ci aij |
c j |
, |
j J . |
|
|||||||||||||||||
|
|
|
|
|
|
|
|
i |
I |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
2. |
Проверить, если все |
j |
|
0 , |
то перейти к п.8. |
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3. |
Проверить, если k J : |
k |
0 |
и все aik |
|
|
|
0 , то перейти к п.10. |
||||||||||||||||||
4. |
Выбрать k : k |
0 (>0, если задача на min) и вектор Ak |
имеет |
|||||||||||||||||||||||
|
хотя бы одну строго положительную координату (выбор такого |
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
номера k произволен, например, max |
|
j |
|
|
|
|
|
k |
). |
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
k |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
5. |
Вычислить параметр |
|
по формуле |
|
|
|
|
xl |
|
min |
xi |
|
|
|
||||||||||||
|
|
|
|
alk |
aik |
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
aik |
0 |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6.Осуществить переход к новой базисной точке с помощью преобразований Жордана-Гаусса с направляющим элементом alk .
7.Изменить исходную информацию:
|
|
xH |
|
|
|
|
xl |
|
a ,i I; x |
|
xl |
|
; x |
|
|
||
x |
B |
(x |
j |
0, j J , j k) . |
|||||||||||||
|
|
|
|
|
|||||||||||||
|
B |
|
i |
|
|
|
|
ik |
k |
alk |
|
||||||
|
|
|
|
|
|
alk |
|
|
|
||||||||
I |
|
I \ ({l} {k}) ; J |
J \ ({l} {k}) |
|
|
Перейти к п.1.
96
8. |
Если существует номер s |
J : s 0 , то выписать ответ: xB - |
|
оптимальная точка, в задаче имеется бесчисленное множество |
|
|
решений. |
|
9. |
Если для всех j J : j |
0 , то выписать ответ: xB - |
единственное решение задачи.
10.Выписать ответ: задача решений не имеет из-за неограниченности целевой функции на допустимом множестве:
|
sup z(x) |
. |
|
|||
|
Пример 1. Решить задачу |
|||||
|
x2 |
3x3 |
2x5 |
min |
||
x1 |
3x2 |
x3 |
2x5 |
7, |
||
|
2x2 |
4x3 x4 |
|
12, |
||
|
4x2 |
3x3 |
8x5 |
x6 10, |
||
xi |
0, i |
|
|
|
|
|
1,6. |
|
|
Решение задачи удобно оформлять в виде таблицы. В первом столбце помещаются текущие базисные переменные, во втором - их коэффициенты в целевой функции, в третьем - координаты текущей
базисной точки. Далее переписываем элементы матрицы
помещая над каждым столбцом коэффициент соответствующей переменной в целевой функции. Последний столбец предназначается для определения значения . В отдельной строке вычисляются
оценки векторов Aj . В ячейке, находящейся на пересечении
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
оценочной |
строки |
и |
столбца |
x , |
помещаем |
значение |
целевой |
|||||||||||
функции в текущей базисной точке. |
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B |
CB |
|
|
|
|
0 |
|
1 |
|
-3 |
|
0 |
|
2 |
0 |
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
A1 |
|
A2 |
|
|
A3 |
|
A4 |
|
A5 |
A6 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
x1 |
0 |
7 |
|
|
1 |
|
3 |
|
-1 |
|
0 |
|
2 |
0 |
|
- |
||
x4 |
0 |
12 |
|
0 |
|
-2 |
|
4 |
|
1 |
|
0 |
0 |
|
3 |
|||
x6 |
0 |
10 |
|
0 |
|
-4 |
|
3 |
|
0 |
|
8 |
1 |
|
10/3 |
|||
j |
|
0 |
|
|
0 |
|
-1 |
|
3 |
|
0 |
|
-2 |
0 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
97
|
Поскольку на первой итерации |
3 |
0 , в базис вводится вектор A3 . |
|||||||||||||||||||||||||
|
|
min{ |
12 |
|
, |
10 |
} 3 , |
т.е. в |
качестве направляющего |
элемента |
||||||||||||||||||
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
4 |
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
выбирается a23 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B |
CB |
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
|
-3 |
|
|
0 |
|
2 |
|
0 |
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
A1 |
A2 |
|
A3 |
|
|
A4 |
|
A5 |
|
A6 |
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
x1 |
0 |
|
10 |
|
|
1 |
5/2 |
|
0 |
|
|
0 |
|
2 |
|
0 |
|
|
4 |
||||||||
|
x3 |
-3 |
|
3 |
|
|
|
|
|
|
0 |
-1/2 |
|
1 |
|
|
1/4 |
|
0 |
|
0 |
|
|
- |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
x6 |
0 |
|
1 |
|
|
|
|
|
|
0 |
-5/2 |
|
0 |
|
|
-3/4 |
|
8 |
|
1 |
|
|
- |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
j |
|
|
-9 |
|
|
|
0 |
1/2 |
|
0 |
|
|
-3/4 |
|
-2 |
|
0 |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
2 |
0 , то есть в базис вводится вектор A2 . |
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
4 , т.е. в качестве направляющего элемента выбирается a12 . |
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
B |
CB |
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
-3 |
|
0 |
2 |
0 |
|
|
|
|||||
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
A1 |
A2 |
|
A3 |
|
|
A4 |
|
A5 |
|
A6 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
x2 |
1 |
|
|
|
|
|
4 |
|
|
2/5 |
1 |
0 |
|
0 |
4/5 |
0 |
|
- |
|
||||||||
|
x3 |
-3 |
|
|
|
|
|
5 |
|
|
|
1/5 |
0 |
1 |
|
1/4 |
2/5 |
0 |
|
- |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
x6 |
0 |
|
|
|
|
|
11 |
|
|
1 |
0 |
0 |
|
-3/4 |
10 |
1 |
|
- |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
j |
|
|
|
|
|
|
-11 |
|
|
-1/5 |
0 |
0 |
|
-3/4 |
-12/5 |
0 |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
Все |
|
j |
0 , |
|
|
то |
есть |
|
получена |
|
оптимальная |
|
точка |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
x* |
(0,4,5,0,0,11) . Поскольку на небазисных векторах |
j |
0 , то |
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
решение в задаче единственно.
98
Пример 2. Решить задачу
|
|
2x1 |
|
|
x2 |
|
x3 |
3x4 |
2x5 |
|
x6 |
max |
|
|
|
|||||
|
|
x1 |
|
|
x2 |
|
x3 |
x4 |
|
|
|
1, |
|
|
|
|||||
|
|
x1 |
|
|
x2 |
|
|
|
|
|
|
|
x5 |
1, |
|
|
|
|||
|
|
x1 |
|
3x2 |
|
x3 |
|
|
|
|
|
x6 |
2, |
|
|
|
||||
|
|
xi |
0, i |
1,6. |
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
B |
|
CB |
|
|
|
|
|
2 |
|
|
-1 |
|
1 |
|
3 |
-2 |
1 |
|
||
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
A1 |
|
A2 |
|
A3 |
|
A4 |
A5 |
A6 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
x4 |
|
3 |
|
1 |
|
|
-1 |
|
|
1 |
|
-1 |
|
1 |
0 |
0 |
- |
|||
x5 |
|
-2 |
|
1 |
|
|
1 |
|
|
-1 |
|
0 |
|
0 |
1 |
0 |
1 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
x6 |
|
1 |
|
2 |
|
|
1 |
|
|
-3 |
|
1 |
|
0 |
0 |
1 |
2 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
j |
|
3 |
|
|
-6 |
|
|
3 |
|
-3 |
|
0 |
0 |
0 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
x4 |
|
3 |
|
2 |
|
|
0 |
|
|
0 |
|
-1 |
|
1 |
1 |
0 |
|
|||
x1 |
|
2 |
|
1 |
|
|
|
1 |
|
|
-1 |
|
0 |
|
0 |
1 |
0 |
|
||
x6 |
|
1 |
|
1 |
|
|
|
0 |
|
|
-2 |
|
1 |
|
0 |
-1 |
1 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
j |
|
9 |
|
|
0 |
|
|
-3 |
|
-3 |
|
0 |
6 |
0 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
На второй итерации получаем, что оценка 2 0 , но в столбце A2 |
нет положительных элементов. Это означает, что целевая функция не ограничена на допустимом множестве, т.е sup z(x)
Задачи для самостоятельного решения
Решить симплекс - методом: |
|
|
4.3.1 x1 + x2 + x3 |
min, |
|
x1 |
– x4 |
– 2 x6 = 5, |
x2 |
+ 2 x4 – 3 x5 + x6 = 3, |
x3 + 2 x4 – 5 x5 + 6 x6 = 5;
99
4.3.2 2 x1 + x2 – x3 – x4 min, x1 + x2 + 2 x3 – x4 = 2,
2x1 + x2 – 3 x3 + x4 = 6, x1 + x2 + x3 + x4 = 7;
4.3.3 |
x1 – 2x2 + 3x3 min, |
4.3.4 |
2x1 |
– 3x2 |
max, |
||||
|
2x1 + 3x2 |
+ 4x3 = 1, |
|
|
5x1 |
+ 2x2 |
10, |
||
|
–2x1 + x2 + 3x3 = 2; |
|
|
x1 |
+ 3x2 |
12; |
|||
4.3.5 |
6 x1 |
+ 4 x2 |
min, |
|
4.3.6 |
2 x1 – 4 x2 |
min, |
||
|
2 x1 + |
x2 |
3, |
|
|
8 x1 – 5 x2 |
16, |
||
|
x1 – x2 |
1; |
|
|
x1 + 3 x2 |
2, |
|||
4.3.7 |
7 x1 |
+ 5 x2 |
max, |
|
4.3.8 |
3 x1 + 2 x2 |
max, |
||
|
7 x1 + 5 x2 |
7, |
|
|
4 x1 + 2 x2 |
12, |
|||
|
7 x1 – 5 x2 |
35, |
|
|
x1 + 2 x2 |
10, |
|||
|
x1 – x2 |
0; |
|
|
2 x1 + 2 x2 = 6; |
||||
4.3.9 |
4 x1 |
+ 5 x2 |
+ 9 x3 + 11 x4 |
max, |
|
|
|
||
|
x1 + x2 + x3 + |
x4 |
15, |
|
|
|
|||
|
7 x1 + 5 x2 |
+ 3 x3 + |
2 x4 |
80, |
|
|
|
||
|
3 x1 + 5 x2 |
+ 10 x3 + 15 x4 |
60; |
|
|
|
4.3.10 |
2 x1 |
+ x2 |
– |
x3 – x4 |
min, |
|
x1 + x2 + 2 x3 – x4 = 2, |
||||
|
2 x1 + x2 – 3 x3 + x4 = 6, |
||||
|
x1 + x2 + x3 + x4 = 7; |
||||
4.3.11 |
4x1 |
+ x2 |
– 2x3 – x4 |
– x5 min, |
|
|
|
|
|
x3 – x4 + x5 = 1, |
|
|
|
x2 |
|
+ 2x4 |
– x5 = 1, |
|
x1 |
+ 2x2 |
|
+ 2x5 = 4; |
100
4.3.12 x1 |
+ 2 x2 |
+ 3 x3 – x4 |
max, |
|
x1 |
+ 2 x2 |
+ 3 x3 |
= 15, |
|
2 x1 |
+ |
x2 |
– 3 x3 |
= 20, |
x1 |
+ |
2 x2 |
+ x4 = 10. |
4.4. Метод искусственного базиса решения произвольной задачи линейного программирования
В общем случае ограничения ЗЛП могут не содержать единичной матрицы и использование базового симплексного метода будет невозможно из-за отсутствия исходного базиса.
Для решения таких задач предназначен метод искусственного базиса (модифицированный симплекс метод).
По условию исходной задачи (4.3.1)-(4.3.3) (см. 4.3) составляется вспомогательная задача следующего вида:
n |
|
m |
|
|
|
c j x j |
M |
zi |
max |
J 1 |
|
i |
1 |
|
Ax |
Ez |
b |
(b |
0), |
x |
0, z |
0, |
|
|
где z - искусственные переменные, введенные в условие задачи с целью обеспечения исходной базисной точки, а M - некоторое большое положительное число. Задача такого вида иногда называется М-задачей.
Очевидно, что введение слагаемых с положительными zi
уменьшает значение целевой функции. Введение числа M в целевую функцию производит как бы еѐ “штрафование” за выбор точки с
положительными координатами zi . Тогда в оптимальной точке при достаточно большом M все значения zi будут равны нулю. Однако
это возможно только в случае, если в исходной задаче допустимое множество не пусто. Имеет место следующая теорема.
Теорема 2. Если исходная задача имеет решение, то существует такое число М°, что при всех М>М° вспомогательная М-
задача тоже имеет решение, и в любом ее решении |
x* |
точка z*=0, |
|
z* |
|||
|
|
101
а х* будет решением исходной задачи.
Следствие 1. Если при решении произвольной задачи линейного программирования методом исскуственного базиса будет
получена такая оптимальная точка, что z* допустимое множество пусто.
Из теоремы следует, что решение можно осуществлять, фиксируя некоторое большое число M, однако обычно поступают иначе: число M не фиксируется, а оставляется в задаче в качестве параметра, который позволяет осуществлять непрерывное двухэтапное решение задачи. Нa первом этапе алгоритма осуществляется максимизация второй группы слагаемых
|
|
m |
|
0 |
M |
zi |
max , а после достижения максимума непрерывно |
|
i |
1 |
|
переходят к оптимизации исходной целевой функции, либо делают вывод о неразрешимости исходной задачи. До тех пор, пока
переменные |
zi |
0 , т.е. |
являются базисными, |
и значение целевой |
||||
функции, |
и |
оценки |
j |
можно |
представить в |
виде |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
j M j , j |
1,n . Следовательно, если |
вводить в базис |
такой |
|||||
вектор Aj , что соответствующее значение |
j |
0 , то это приведет к |
увеличению значения 0 . Максимальное значение будет получено,
когда, все |
j |
будут неотрицательными. |
Очевидно, что при этом |
|||
|
|
|
|
|
|
|
возможны |
две ситуации: |
0 |
0 и |
0 |
0 . Рассмотрим оба эти |
|
|
|
|
|
|
||
случая. |
|
|
|
|
|
|
1. Оптимальное значение |
0 |
0 . Наличие такой ситуации на одной |
||||
|
|
|
|
|
|
из итераций означает, что допустимое множество исходной задачи пусто, т.к. оптимальная точка имеет координаты zi 0 .
2. Оптимальное значение |
0 |
0 |
. Такой вариант возможен в двух |
|
|
|
ситуациях:
а) все искусственные переменные выведены из базиса и равны нулю. В этом случае получена базисная точка исходной задачи и продолжается оптимизация исходной целевой функции по базовому алгоритму симплексного метода;
б) искусственные переменные zi не выведены из базиса, но их
102