ИсследованиеОпераций
.pdf1)z = 2x1 − x2 +3x3 −2x4 + x5 (max)
− x1 + x2 + x3 |
|
=1, |
|||||||
|
x1 − x2 |
|
+ x4 |
|
=1, |
||||
|
|
|
|||||||
|
x |
1 |
+ x |
2 |
|
+ x |
5 |
= 2, |
|
|
|
|
|
|
|
|
|||
x |
|
≥ 0, j |
= |
|
|
|
|
||
j |
1,5. |
|
|
||||||
|
|
|
|
|
|
|
|
|
3)z = 2x1 +3x2 − x4 (max),
2x |
1 |
− x |
2 |
|
|
−2x |
4 |
+ x |
5 |
=16, |
||
|
|
|
|
|
|
|
|
|||||
3x1 +2x2 + x3 −3x4 |
|
=18, |
||||||||||
− x |
+3x |
2 |
|
+4x |
4 |
|
+ x |
= 24, |
||||
|
|
1 |
|
|
|
|
|
|
6 |
|
||
x |
|
≥0, j |
= |
|
. |
|
|
|
|
|
||
j |
1,6 |
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
5)z = 3x1 +2x3 −6 x6 (max),
2x |
+ x |
|
−3x |
|
|
|
|
+6 x |
=18, |
||||||
−3x1 |
|
2 |
+2x |
|
3 |
+ x |
4 |
|
−2x6 |
= 24, |
|||||
|
|
1 |
|
|
|
|
|
|
3 |
|
|
6 |
|
||
|
|
x |
|
+3x |
3 |
|
+ x |
5 |
−4x |
= 36, |
|||||
|
|
1 |
|
|
|
|
|
|
|
|
6 |
|
|||
x |
|
≥0, j = |
|
. |
|
|
|
|
|
|
|
||||
j |
1,6 |
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7)z = x1 + x2 + x3 (min),
x1 |
|
|
− x4 |
|
|
−2x6 = 5, |
||||
|
|
x |
2 |
+2x |
4 |
−3x |
5 |
+ x |
= 3, |
|
|
|
|
|
|
|
6 |
|
|||
|
|
|
|
x3 +2x4 −5x5 +6 x6 |
= 5, |
|||||
|
|
|
|
|||||||
x |
|
≥0, j = |
|
. |
|
|
|
|||
j |
1,6 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
9)z = x1 +3x2 −5x4 (max),
2x1 +4x2 + x3 +2x4 |
|
|
= 28, |
||||||||
−3x |
+5x |
2 |
|
−3x |
4 |
+ x |
5 |
= 30, |
|||
|
|
1 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
+8x4 |
+ x6 = 32, |
|||
4x1 −2x2 |
|
|
|
||||||||
x |
|
≥0, j = |
|
|
|
|
|
|
|
||
j |
1,6. |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
11)z = x1 − 2x2 + 3x3 − x4 (max),
2x |
− x |
+ 2x |
−3x |
≤ 5, |
|||
|
1 |
2 |
3 |
4 |
|
||
|
x1 |
+ 2x2 − x3 |
+ x4 ≤ 3, |
||||
|
|||||||
|
|
|
|
|
|
|
|
x ≥0, j = 1,4.
j
51
2)z = 3x1 −2x2 (min),
|
2x |
1 |
+ x |
2 |
≤14, |
|
||
|
|
|
|
|
|
|
||
−3x1 +2x2 ≤ 9, |
|
|||||||
|
3x |
+4x |
2 |
≤ 27 |
, |
|||
|
|
1 |
|
|
|
|
|
|
x |
1,2 |
≥0. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4)z = 2x1 +3x2 (max),
−3x |
+2x |
|
≤6, |
|||
|
|
1 |
|
|
2 |
|
|
x1 −4x2 ≤ 2, |
|||||
|
x |
1 |
− x |
2 |
≤ 5, |
|
|
|
|
|
|||
x |
1,2 |
≥0. |
|
|
|
|
|
|
|
|
|
|
6)z = 4x1 +2x2 (max),
− x1 +2x2 ≤6, |
||||
|
x1 |
+ x2 |
≤ 9, |
|
|
||||
|
3x1 |
− x2 |
≤ 15, |
|
|
||||
x |
1,2 |
≥ 0. |
|
|
|
|
|
|
8)z = x1 + x2 (max),
5x1 −2x2 ≤7, |
||||
− x |
+ x |
2 |
≤ 5, |
|
|
1 |
|
|
|
|
x |
+ x |
2 |
≤6, |
|
1 |
|
|
|
x |
≥0. |
|
||
|
1,2 |
|
|
|
10)z = x1 + x2 (max),
2x1 +11x2 |
≤ 38, |
||
|
x1 |
+ x2 |
≤7, |
|
|||
|
|
−5x2 |
≤ 5, |
4x1 |
|||
x |
1,2 |
≥ 0. |
|
|
|
|
12)z = 3x2 − x4 (max),
x |
− 2x |
+ x |
= 8, |
||
|
1 |
2 |
|
4 |
|
|
|
x2 + x3 −3x4 =6, |
|||
|
|
||||
|
|
|
|
|
|
|
≥0, j = 1,4. |
|
|
||
x j |
|
|
|||
|
|
|
|
|
|
13)z = 2x1 − x2 +3x3 −2x4 + x5 (max)
− x1 + x2 + x3 |
|
|
=1, |
|||||||
|
x |
− x |
2 |
|
+ x |
4 |
|
=1, |
||
|
|
1 |
|
|
|
|
|
|
||
|
x |
+ x |
2 |
|
|
+ x |
5 |
= 2, |
||
|
|
1 |
|
|
|
|
|
|
||
x |
|
≥0, j |
= |
|
. |
|
|
|
||
j |
1,5 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
15)z = 8x2 +7 x4 + x6 (max),
x1 − 2x2 |
|
− 3x4 |
|
− 2x6 = 12, |
|||||||||
|
|
4x |
2 |
+ x |
3 |
− 4x |
4 |
|
− 3x |
= 12, |
|||
|
|
|
|
|
|
|
|
|
6 |
|
|||
|
|
5x |
2 |
|
|
+ 5x |
4 |
+ x |
5 |
+ x |
= 25, |
||
|
|
|
|
|
|
|
|
6 |
|
||||
x |
|
|
|
|
|
|
|
|
|||||
j |
≥ 0, j = |
1,6 |
. |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
17)z = 3x1 +2x5 −5x6 (max),
2x1 + x2 |
|
|
−3x5 +5x6 = 34, |
|||||||||
|
4x1 |
+ x3 |
|
+2x5 −4x6 = 28, |
||||||||
|
|
|||||||||||
−3x |
1 |
+ x |
4 |
−3x |
5 |
+6 x |
6 |
= 24, |
||||
|
|
|
|
|
|
|
|
|
||||
x |
|
≥ 0, j = |
|
|
|
|
|
|
||||
j |
1,6. |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
19)z = −2x2 + x4 + 3x5 (max),
x |
− 2x |
|
+ 3x |
+ x = 8, |
||
|
1 |
2 |
4 |
5 |
||
|
|
x2 |
+ x3 + x4 − 2x5 =6, |
|||
|
|
|||||
|
|
|
|
|
|
|
x ≥0, j = 1,5.
j
14)z = x1 −2x2 (max),
−3x1 +2x2 ≤ 6, |
||||
|
x1 |
−4x2 |
≤ 2, |
|
|
||||
|
x1 |
− x2 |
≤ 5, |
|
|
||||
x |
1,2 |
≥ 0. |
|
|
|
|
|
|
16)z = 2x1 − x2 +3x3 + x4 (max),
2x1 + x2 −3x3 |
|
|
=10, |
||||||
|
|
x1 |
+ x3 + x4 |
|
=7, |
||||
|
|
|
|||||||
−3x |
1 |
−2x |
3 |
+ x |
5 |
= 4, |
|||
|
|
|
|
|
|
|
|||
x |
|
≥ 0, j = |
|
|
|
|
|
||
j |
1,5. |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
18)z = 8x1 + 2x2 (max),
|
x |
−4x |
≤ 4, |
|
|
1 |
|
2 |
|
−4x1 + x2 ≤ 4, |
||||
|
x |
|
+ x |
≤6, |
|
1 |
|
2 |
|
|
x |
|
≥0. |
|
|
1,2 |
|
|
20)z = 3x1 + x2 (max),
− x |
+ 2x |
+ x |
|
= 4, |
|
|
1 |
2 |
3 |
|
|
|
x1 |
− x2 |
|
+ x4 = 3, |
|
|
|
||||
|
|
|
|
|
|
x ≥0, j = 1,4.
j
7. Методи штучного базису
Основна ідея методів штучного базису полягає у побудові та розв'язуванні симплекс-методом допоміжної канонічної задачі, по розв'язку якої можна або відновити допустимий чи оптимальний розв'язок вихідної задачі, або встановити її нерозв'язність.
У всіх методах штучного базису система обмежень задачі ЛП змінюється шляхом введення у рівняння-обмеження нових невідомих змінних (їх називають штучними) таким чином, щоб змінена система мала канонічний вигляд. З цією системою обмежень розв'язують симплексметодом допоміжну лінійну задачу ЛП (вже канонічну) зі спеціальним чином побудованою цільовою функцією.
52
В залежності від вигляду цільової функції допоміжної задачі або одержують початковий базисний розв'язок вихідної задачі ЛП, або її оптимальний розв'язок, або з'ясовують, що вона недопустима.
7.1Метод штучного базису у найпростішій формі
Унайпростішій формі метод штучного базису допомагає з'ясувати чи є допустимою вихідна задача, та знайти її початковий опорний план, якщо вона допустима.
Нехай вихідна задача зведена до вигляду
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L = ∑c j x j → max , |
|
|
|
|
|
|
|
(7.1) |
|||||||
|
|
j=1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= a10 , |
|
|
|||
|
a11x1 +... + a1r xr + xr +1 |
|
|
|
||||||||||||
|
a21x1 +... + a2r xr |
+ xr +2 |
= a20 , |
|
|
|||||||||||
|
............................................................... |
|
|
|||||||||||||
|
|
|
|
|
+ akr xr |
|
+ xn |
= ak0 , |
|
(7.2) |
||||||
|
ak1x1 +... |
|
|
|
|
|||||||||||
|
a |
x |
+ +... a |
|
x |
|
= a |
k +1,0 |
, |
|
||||||
|
|
k +1,1 1 |
|
|
|
|
|
k +1,r r |
|
|
|
|
|
|||
|
............................................................... |
|
|
|||||||||||||
|
|
x + |
|
|
+ a |
|
x |
|
|
= a |
|
|
, |
|
|
|
|
a |
|
|
|
|
|
m0 |
|
|
|||||||
|
|
m1 1 |
|
|
|
|
mr r |
|
|
|
|
|
|
|||
|
x j |
≥ 0, j = |
|
, |
|
|
|
|
|
|
|
|
(7.3) |
|||
|
1, n |
|
|
|
|
|
|
|
|
|||||||
|
ai0 ≥ 0,i = |
|
. |
|
|
|
|
|
|
|
|
(7.4) |
||||
|
1, m |
|
|
|
|
|
|
|
|
|||||||
Припустимо, що rangA = m , що загальності не обмежить. |
||||||||||||||||
Очевидно, |
що змінні |
xr+1 ,..., xn |
можна вважати базисними, оскільки |
|||||||||||||
відповідні їм вектори умов одиничні: |
|
|
|
|
|
|
|
|||||||||
|
Ar +1 = e1,..., An = ek . |
|
|
|
|
|
|
|
|
|||||||
Внаслідок того, |
що |
rangA = m , |
довільний базис системи векторів |
|||||||||||||
{A1, A2 ,..., An} |
повинен складатися з m векторів, однак |
k < m . |
||||||||||||||
Додамо у ліву частину кожного з рівнянь системи (7.2), починаючи з |
||||||||||||||||
k +1 -го, відповідні штучні змінні: |
y1 ≥ 0 |
– в |
(k +1) -е, |
y2 ≥ 0 – в (k + 2) -е, і |
||||||||||||
т.д., ym−k ≥ 0 |
– в m -е рівняння. Отримаємо таку канонічну лінійну систему |
|||||||||||||||
обмежень |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
53 |
|
|
|
|
|
|
|
|
|
+ + a1r xr + xr +1 |
|
|
|
= a10 , |
|
|
|
|
|||||||||
a11x1 |
|
|
|
|
|
|
|
||||||||||||
a21x1 +... + a2r xr |
+ xr +2 |
|
|
|
= a20 , |
|
|
|
|
||||||||||
............................................................... |
|
|
|
|
|
|
|
|
|||||||||||
|
|
+ + akr xr |
+ xn |
|
|
|
= ak0 , |
|
|
|
(7.5) |
||||||||
ak1x1 |
|
|
|
|
|
|
|||||||||||||
a |
|
x + +... a |
x |
+ y |
|
|
= a |
k +1,0 |
, |
|
|
|
|||||||
|
k +1,1 1 |
|
k +1,r r |
|
1 |
|
|
|
|
|
|
|
|
||||||
............................................................... |
|
|
|
|
|
|
|
|
|||||||||||
|
x |
+ + a |
|
x |
|
+ y |
|
|
= a |
|
|
, |
|
|
|
|
|||
a |
mr |
|
m |
−k |
m0 |
|
|
|
|
||||||||||
|
m1 1 |
|
|
|
|
r |
|
|
|
|
|
|
|
|
|||||
x j |
≥ 0, j = |
|
, |
|
|
|
|
|
|
|
|
|
|
|
(7.6) |
||||
1, n |
|
|
|
|
|
|
|
|
|
|
|
||||||||
ai0 ≥ 0,i = |
|
. |
|
|
|
|
|
|
|
|
|
|
|
(7.7) |
|||||
1, m |
|
|
|
|
|
|
|
|
|
|
|
||||||||
Система (7.5)−(7.7) має опорний план |
~0 |
= (0,...,0, a |
,...,a |
|
T |
||||||||||||||
x |
m0 |
) , якому |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
123 |
10 |
|
|
відповідає одиничний базис {Ar+1 , Ar+2 ,..., An , An+1 ,..., An+mr −k }.
Допоміжна задача у найпростішому випадку полягає у мінімізації суми штучних змінних або максимізації суми штучних змінних зі знаком “мінус”, тобто
~ |
m−k |
|
L∂( x) = − ∑yi → max , |
(7.8) |
|
|
i=1 |
|
за виконання умов (7.5)−(7.7).
Вкажемо на ту особливість задачі (7.8), (7.5)−(7.7), що вона завжди має оптимальний розв'язок, оскільки вона допустима і її цільова функція обмежена зверху
|
|
|
|
~ |
|
|
m−k |
|
|
|
|
|
|
|
|
|
|
|
|
L∂ ( x) |
= − ∑yi ≤ 0 . |
|
|
|
|
|
|
|
(7.9) |
||
|
|
|
|
|
|
|
i=1 |
|
|
|
|
|
|
|
|
Теорема 7.1 (про розв'язок допоміжної задачі у методі штучного базису). |
|||||||||||||||
Нехай: |
Задача |
(7.8), |
|
(7.5)−(7.7) |
розв'язана |
симплекс-методом і |
|||||||||
~* |
|
|
|||||||||||||
* |
* |
* |
* |
T |
– її оптимальний розв'язок. |
|
|||||||||
x |
= (x1 |
,..., xn |
, y1 ,..., ym−k ) |
|
|
|
|||||||||
Тоді: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1) якщо серед чисел y1* ,..., ym* −k |
є відмінні від нуля, то вихідна |
||||||||||||
задача (7.1)−(7.4) не має допустимих розв'язків; |
|
|
|
||||||||||||
~* |
|
2) якщо y1* = y2* =... = ym* −k =0 |
|
і серед векторів базису розв'язку |
|||||||||||
немає штучних, |
|
то вектор |
x |
* |
|
* |
* |
* |
T |
є опорним планом |
|||||
x |
|
|
= (x1 |
, x2 ,..., xn ) |
|
задачі (7.1)−(7.4);
54
3) якщо y1* = y2* =... = ym* −k =0 і серед векторів базису розв'язку
~* |
є l штучних, то вектор |
x |
* |
* |
* |
* |
T |
є допустимим |
x |
|
= (x1 |
, x2 |
,..., xn ) |
|
виродженим розв'язком задачі (7.1)−(7.4), для якого існує базис, що складається лише із векторів системи {A1, A2 ,..., An} який можна
отримати шляхом l однократних замін штучних векторів у базисі.
7.1.1. Приклади. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Приклад 1. Розв'язати задачу ЛП: |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
L = x1 +4x2 + x3 → max, |
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
x |
1 |
|
− x |
2 |
+ x |
3 |
= 3, |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
2x1 −5x |
2 − x3 = 0, |
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
≥ 0, j |
=1,3. |
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
x j |
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Розв'язування. Задача |
має стандартну форму. |
Матриця |
A коефіцієнтів |
||||||||||||||||||||||
|
|
|
|
|
A = [A1 |
|
|
|
|
|
1 |
−1 |
1 |
|
|
|
|
|
|
||||||
системи обмежень |
, A2 |
|
|
|
|
|
|
не має жодного одиничного |
|||||||||||||||||
, A3 ]= |
|
−5 |
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
−1 |
|
|
|
|
|
|
|||
стовпця, |
тому вводимо повний штучний базис. З цією метою доповнюємо A |
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
0 |
|
|
|
двома штучними базисними векторами A4 |
|
|
, |
A5 |
|
|
; отримаємо таку |
||||||||||||||||||
= |
|
= |
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
1 |
|
|
|
матрицю |
|
коефіцієнтів |
|
|
|
системи |
|
обмежень |
допоміжної |
задачі |
|||||||||||||||
1 |
−1 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
−5 |
−1 |
0 |
. Записуємо допоміжну задачу: |
|
|
|
|
|
||||||||||||||||
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
L∂ = −y1 − y2 → max, |
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
x1 − x2 + x3 + y1 |
|
= 3, |
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
2x |
−5x |
− x |
|
+ y |
2 |
=0, |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
1 |
|
|
|
2 |
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
≥0, j = 1,3, |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
x j |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
y , y |
2 |
≥0 |
−штучнізмінні. |
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ця задача має канонічну форму, тому розв’язуємо її розглянутим вище симплекс-алгоритмом. Результати обчислень заносимо до симплекстаблиці (див. таблицю 7).
|
|
|
|
|
Пояснення |
до |
змісту таблиці. |
Нульовий |
крок: |
~0 |
|
T |
, |
||||||
|
|
|
|
|
x |
= (0,0,0,3,0) |
|||||||||||||
B |
0 |
=[ A4 , A5 ] , |
~0 |
) = |
0 |
, |
0 |
|
0 |
|
0 |
|
0 |
= 6 |
, |
||||
|
L∂ ( x |
(cб , α0 ) = −3 |
∆1 |
= (cб,α0 ) −c1 |
= −3 , ∆2 |
= (cб,α2 ) −c2 |
|||||||||||||
∆0 |
= (c |
б |
, |
α0 ) |
−c |
=0 , |
∆0 |
= ∆0 = 0 . |
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
3 |
3 |
4 |
5 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
55 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблиця 7. |
|
№ |
cб |
xб |
|
|
A0 |
0 |
|
|
0 |
|
0 |
–1 |
|
–1 |
θ |
||
кр. |
|
|
x1 |
|
|
x2 |
|
x3 |
y1 |
|
y2 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
–1 |
y1 |
|
|
3 |
1 |
|
|
-1 |
|
1 |
1 |
|
0 |
3 1 |
||
0 |
–1 |
← y2 |
|
|
0 |
2 |
|
|
-5 |
|
-1 |
0 |
|
1 |
0 2 |
||
|
∆ j |
L∂ |
|
|
-3 |
−3 ↑ |
|
|
6 |
|
0 |
0 |
|
0 |
|
||
|
-1 |
← y1 |
|
|
3 |
0 |
|
|
3 2 |
3 2 |
1 |
|
|
|
|||
1 |
0 |
x1 |
|
|
0 |
1 |
|
|
−5 2 |
−1 2 |
0 |
|
|
|
|||
|
∆ j |
L∂ |
|
|
-3 |
0 |
|
|
−3 2 ↑ |
−3 2 |
0 |
|
|
|
|||
|
0 |
x2 |
|
|
2 |
0 |
|
|
1 |
|
1 |
|
|
|
|
||
2 |
0 |
x1 |
|
|
5 |
1 |
|
|
0 |
|
2 |
|
|
|
|
||
|
∆ j |
L∂ |
|
|
0 |
0 |
|
|
0 |
|
0 |
|
|
|
|
||
|
∆0 = −3 |
< 0 , тому |
A вводиться в базис. |
A – ведучий стовпчик для |
|||||||||||||
|
1 |
|
|
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|
симплекс-перетворення. |
|
|
= 0 , |
тому |
|
|
A5 |
виводиться з |
базису. |
Другий |
|||||||
|
θ0 = min(θ1 ,θ2 ) =θ2 |
|
|
||||||||||||||
рядок є ведучим для симплекс-перетворення. |
|
|
|
|
|
||||||||||||
|
Після симплекс-перетворення кроку 0 |
стовпчик |
A5 |
відкинутий, |
|||||||||||||
оскільки штучна змінна y2 |
вже не є базисною. |
|
~1 |
|
|
|
|||||||||||
|
Перший крок: |
~1 |
= (0,0,0,3,0) |
T |
, |
B |
1 |
=[ A4 |
, A1] , |
|
1 |
1 |
|||||
|
x |
|
|
|
L∂ ( x |
) = (cб , α0 ) = −3 , |
|||||||||||
∆12 = (c1б,α12 ) −c2 = −3 2 |
|
|
∆13 |
= (cб1 , α31 ) − c3 |
= −3 2 . |
При |
симплекс- |
||||||||||
перетворенні кроку 1 |
в базис вводиться вектор |
A3 , |
з базису виводиться |
||||||||||||||
вектор |
A4 . |
|
~* |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Отже, вектор |
|
|
|
T |
є оптимальним розв'язком допоміжної |
|||||||||||
|
x |
= (5,2,0,0,0) |
|||||||||||||||
задачі. Серед векторів його базису немає штучних. Тому обведена жирною |
56
лінією частина таблиці кроку 2 містить коефіцієнти канонічної форми вихідної задачі, яка визначає її початковий опорний план x0 = (5,2,0)T .
Заносимо знайдену канонічну форму вихідної задачі у симплекстаблицю (див. таблицю 8) і розв'язуємо вихідну задачу.
|
|
|
|
|
|
|
|
|
|
|
|
Таблиця 8. |
№ |
cб |
xб |
A0 |
0 |
|
0 |
0 |
|
θ |
|
Пояснення |
|
кр. |
x1 |
|
x2 |
x3 |
|
|||||||
|
|
|
|
|
|
|
||||||
0 |
4 |
x2 |
2 |
0 |
|
1 |
1 |
|
|
|
x0 = (5,2,0)T , |
|
1 |
x1 |
5 |
1 |
|
0 |
2 |
|
|
|
L( x0 ) = (cб,α0 ) =13, |
||
|
|
|
|
|
||||||||
|
∆ j |
L |
13 |
0 |
|
0 |
5 |
|
|
|
∆1 = ∆2 = 0, |
|
|
|
|
|
∆3 = (cб,α3 ) −c3 = 5 > 0. |
||||||||
|
|
|
|
|
|
|
|
|
|
|
||
|
Всі |
симплекс-різниці |
∆ j ≥ 0 , |
j = |
|
. Тому |
опорний план x0 є |
|||||
|
1,3 |
оптимальним розв'язком вихідної задачі. Йому відповідає оптимальне
значення цільової функції L( x0 ) = 13 . |
|
|
|
|
|
|
|||||||||||||||
Приклад 2. Розв'язати задачу лінійного програмування. |
|
||||||||||||||||||||
|
L = −x1 + 2x2 − 3x3 |
→ max, |
|
|
|
||||||||||||||||
|
− 2x |
1 |
+ x |
2 |
|
+ 3x |
3 |
= 2, |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
2x1 |
+ 3x2 + 4x3 = 1, |
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x j ≥ 0, j = 1,3. |
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Розв'язування. Задача |
має |
стандартну |
форму. |
Доповнюємо |
матрицю |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
−2 |
1 |
|
3 |
|
|
|
||
коефіцієнтів |
A = [ A1 |
, A2 , A3 ] = |
|
|
|
|
|
|
двома |
штучними |
векторами |
||||||||||
|
|
2 |
3 |
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|||
A4 = (1, 0)T , |
A5 = (0, 1)T |
|
та записуємо допоміжну канонічну задачу: |
|
|||||||||||||||||
|
L∂ = −y1 − y2 → max, |
|
|
|
|
|
|
||||||||||||||
|
− 2x |
|
+ x |
|
+ 3x |
|
+ y |
|
= 2, |
|
|
|
|||||||||
|
|
1 |
|
2 |
3 |
|
1 |
|
|
|
|
|
|
||||||||
|
|
+ 3x2 + 4x3 |
|
|
+ y2 = 1, |
|
|
|
|||||||||||||
|
2x1 |
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0, |
j = 1,3, |
yi ≥ |
0,i = 1,2 −штучнізмінні, |
|
|||||||||||||||
|
x j ≥ |
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
яку розв'язуємо симплекс методом (див. таблицю 9). |
x |
= (0,0,0,2,1) |
|
, |
Пояснення до змісту таблиці. На нульовому кроці |
T |
|||
|
~(0 ) |
|
|
Lд ( x(0 ) ) = −3, ∆4 = ∆5 =0 ∆1 =0 , ∆2 = (cб ,α2 ) −c2 = −4 , ∆3 =(cб ,α3 ) −c3 = −7 <0 . 57
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблиця 9. |
|||||
№ |
|
cб |
|
|
xб |
|
|
|
A0 |
|
|
0 |
|
|
|
|
0 |
|
|
0 |
–1 |
|
–1 |
|
θ |
|
|||||||||
кр. |
|
|
|
|
|
|
|
|
x1 |
|
|
|
|
x2 |
|
|
x3 |
y1 |
|
y2 |
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
0 |
|
–1 |
|
|
y1 |
|
|
|
|
2 |
|
|
|
–2 |
|
|
|
1 |
|
|
3 |
1 |
|
|
0 |
|
|
2 3 |
|
||||||
|
|
|
|
y2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
–1 |
|
|
|
|
|
|
1 |
|
|
|
2 |
|
|
|
|
3 |
|
|
4 |
0 |
|
|
1 |
|
|
14 |
|
||||||
|
|
|
|
|
← |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
∆j |
|
|
L∂ |
|
|
|
–3 |
|
|
0 |
|
|
|
|
–4 |
|
−7 ↑ |
0 |
|
|
0 |
|
|
|
|
|
|||||||
|
|
–1 |
|
|
y |
1 |
|
|
|
5 |
4 |
|
|
−7 |
2 |
|
|
|
− 5 |
4 |
|
0 |
1 |
|
|
|
|
|
|
|
|
||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
14 |
|
|
1 2 |
|
|
|
3 4 |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
0 |
|
|
x 3 |
|
|
|
|
|
|
|
|
|
1 |
0 |
|
|
|
|
|
|
|
|
|||||||||||
|
|
∆ j |
|
|
L∂ |
|
|
|
− 5 |
4 |
|
|
7 |
2 |
|
|
|
5 |
4 |
|
0 |
0 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
На першому кроці |
~( |
1) |
= (0,0, |
14 , 5 4 ,0) |
T |
~(1) |
) = −5 4 , |
|
∆3 |
= ∆4 |
=0 , |
||||||||||||||||||||||
|
|
x |
|
|
, Lд( x |
|
|||||||||||||||||||||||||||||
∆1 = |
7 |
2 ,∆2 = |
5 |
4 . |
Всі |
|
|
оцінки |
|
∆ j |
>0 , |
тому |
|
вектор |
~(1) |
= (0,0, |
1 |
4 , |
5 |
4 ,0) |
T |
є |
|||||||||||||
|
|
|
|
|
|
x |
|
|
|
||||||||||||||||||||||||||
оптимальним розв'язком допоміжної задачі. |
|
у цьому розв'язку відмінне від |
|||||||||||||||||||||||||||||||||
|
|
Оскільки значення штучної змінної y1 |
|||||||||||||||||||||||||||||||||
нуля: y1(1) = 5 4 ≠ 0 , то вихідна задача допустимих розв'язків немає. |
|
|
|
|
|
||||||||||||||||||||||||||||||
Приклад 3. Розв'язати задачу ЛП. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
L = x1 + 2x2 → max, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
x |
|
+ 2x |
|
≤ 4, − x |
− x |
2 |
≤ −4, |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
1 |
|
|
2 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
− x1 + x2 ≤ 4, |
|
x1, x2 ≥0. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
Розв'язування. Задача має загальну форму. Зводимо її до стандартної |
|||||||||||||||||||||||||||||||||||
форми |
|
|
L = x1 +2x2 |
→ max, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
x1 +2x2 + x3 |
|
|
|
|
|
|
= 4, |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
+ x4 |
|
|
|
|
= 4, |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
− x1 + x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
− x |
1 |
− x |
2 |
|
|
|
|
− x |
5 |
= −4, |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
x |
j |
|
≥ 0, j =1,5. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Матриця коефіцієнтів при невідомих |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
58
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
1 |
0 |
0 |
|
||
|
A = |
[ A , A , A , A , A ] = |
|
−1 1 0 1 |
0 |
|
|
|||||||||||
|
|
|
|
|||||||||||||||
|
|
|
1 |
2 |
3 |
|
4 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
0 |
−1 |
|
||
має два |
одиничних |
вектори: |
A3 = (1, 0, 0)T , |
A4 = (0, 1, 0)T . Доповнюємо |
||||||||||||||
матрицю вектором |
|
A6 = (0, 0, 1)T . Відповідну йому штучну змінну позначимо |
||||||||||||||||
через x6 ≥ 0 . Отримаємо таку матрицю |
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
|
1 |
0 |
0 |
0 |
|
|
[ A , A , A , A , A , A ] = |
|
−1 |
1 |
|
0 1 0 0 |
|
|||||||||||
|
|
|
. |
|||||||||||||||
|
|
1 |
2 |
3 |
4 |
|
5 |
6 |
|
1 |
1 |
|
0 0 −1 1 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Як система векторів-умов |
Aj , |
|
j = |
|
, |
вона має одиничний базис |
||||||||||||
|
1,6 |
|||||||||||||||||
[ A3 , A4 , A6 ] , |
в якому |
A6 |
– штучний базисний вектор. Записуємо допоміжну |
|||||||||||||||
канонічну задачу |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lд = −x6 → max, |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
x1 + 2x2 + x3 |
|
|
|
= 4, |
|
|
|
|
|
|
|
||||||
|
− x + x |
2 |
+ x |
|
|
= 4, |
|
|
|
|
|
|
|
|||||
|
|
|
1 |
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
+ x |
|
|
|
|
− x |
+ x |
= 4, |
|
|
|
|
|
|
|
|
|
1 |
2 |
|
|
|
|
5 |
6 |
|
|
|
|
|
|
|
|
|
|
|
x |
|
≥0, j = |
|
|
−штучназмінна, |
|
|
|
|
||||||||
|
j |
1,6 |
; x |
|
|
|
|
|
||||||||||
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
яку розв’язуємо симплекс-методом (див. таблицю 10).
Пояснення до змісту таблиці. |
|
|
|
|
~(1) |
= (4,0,0,8,0,0) |
T |
, |
|||||||
На першому кроці x |
|
||||||||||||||
|
|
|
|
|
|
|
~(1) |
|
|
|
|
|
|
|
|
і всі оцінки |
∆ j |
|
≥ 0 , |
j =1,6 , |
− оптимальний |
розв'язок допоміжної |
|||||||||
|
тому x |
||||||||||||||
задачі. Відповідний йому базис B1 =[ A |
, A |
, A ] містить штучний вектор A . |
|
||||||||||||
|
|
|
|
|
|
|
|
1 |
|
4 |
6 |
|
6 |
|
|
Вибираємо перший не штучний вектор, який має ненульову третю |
|||||||||||||||
компоненту |
A2 = (2; 3; −1)T і виконуємо крок повного виключення з ведучим |
||||||||||||||
елементом |
α32 = −1 . |
При цьому штучний вектор A6 |
виводиться з базису. |
||||||||||||
Новий базис B |
1 |
=[ A1 |
, A4 , A2 ] |
розв'язку |
|
~(1) |
не містить штучних векторів. |
|
|
||||||
|
|
x |
|
|
|||||||||||
Отже, |
|
вектор |
~(1) |
= (4,0,0,8,0,0) |
T |
є початковим опорним планом |
|||||||||
|
x |
|
вихідної стандартної задачі. Коефіцієнти канонічної форми системи обмежень вихідної задачі, яка визначає цей опорний план, містяться у виділеній жирною лінією частині таблиці кроку 2.
59
|
|
|
|
|
|
|
|
|
Таблиця 10. |
||
№ |
cб |
xб |
A0 |
0 |
0 |
0 |
0 |
0 |
–1 |
θ |
|
кр |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|||||
|
|
|
|
||||||||
|
0 |
← x3 |
4 |
1 |
2 |
1 |
0 |
0 |
0 |
4 |
|
0 |
0 |
x4 |
4 |
–1 |
1 |
0 |
1 |
0 |
0 |
|
|
|
–1 |
x6 |
4 |
1 |
1 |
0 |
0 |
–1 |
1 |
4 |
|
|
∆ j |
Lд |
–4 |
–1 ↑ |
–1 |
0 |
0 |
1 |
0 |
|
|
|
0 |
x1 |
4 |
1 |
2 |
1 |
0 |
0 |
0 |
|
|
1 |
0 |
x4 |
8 |
0 |
3 |
1 |
1 |
0 |
0 |
|
|
|
–1 |
x6 |
0 |
0 |
–1 |
–1 |
0 |
–1 |
1 |
|
|
|
∆ j |
Lд |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
|
|
|
0 |
x1 |
4 |
1 |
0 |
–1 |
0 |
–2 |
|
|
|
2 |
0 |
x4 |
8 |
0 |
0 |
–2 |
1 |
–3 |
|
|
|
|
0 |
x2 |
0 |
0 |
1 |
1 |
0 |
1 |
|
|
|
|
∆ j |
Lд |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
Записуємо цю канонічну форму у симплекс-таблицю (див. таблицю |
||||||||||
11) та розв'язуємо вихідну задачу. |
|
|
|
|
Таблиця 11. |
||||||
|
|
|
|
|
|
|
|
|
|||
№ |
cб |
xб |
A0 |
0 |
0 |
0 |
0 |
0 |
|
θ |
|
кр |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
||||
|
|
|
|
|
|||||||
|
1 |
x1 |
4 |
1 |
0 |
–1 |
0 |
–2 |
|
||
|
0 |
x4 |
8 |
0 |
0 |
–2 |
1 |
–3 |
|
||
|
2 |
x2 |
0 |
0 |
1 |
1 |
0 |
1 |
|
|
|
|
∆ j |
L |
4 |
0 |
0 |
1 |
0 |
0 |
|
|
~1 |
Всі елементи |
∆ -рядка невід'ємні, тому початковий опорний план |
||||
= (4,0,0,8,0) |
T |
є і |
оптимальним розв'язком стандартної |
задачі. Її |
||
x |
|
|||||
|
|
|
|
~1 |
) = 4 . |
|
оптимальне значення рівне L( x |
|
|||||
|
Якщо повернутись до вихідної загальної задачі, то її оптимальним |
|||||
розв'язком та оптимальним значенням будуть відповідно вектор |
x* = (4,0)T |
|||||
та число Lmax = 4 . |
|
|
|
|||
|
|
|
|
|
60 |
|