ЛАБОРАТОРНА РОБОТА
Симплекс-метод
Теоретичні відомості:
Симплекс-метод (СМ) безпосередньо застосовується до розв'язування канонічної задачі лінійного програмування (КЗЛП) i здійснює цілеспрямоване перебирання допустимих базисних розв'язкiв (ДБР) (вершин допустимого многогранника розв'язкiв ЗЛП, що визначається обмеженнями ), до множини яких належить оптимальний розв'язок, якщо він існує; або визначає, що ЗЛП не має оптимального розв'язку.
ЗЛП — канонічна, якщо її обмеження мають канонічну форму: xi + ai,m+1 xm+1 + ... + ainxn = ai0, ai0?0, i=1,...,m, тобто, матриця умов A=||aij||, i=1,...,m, j=1,...,n, містить в собі одиничну пiдматрицю розміру mЧm i вектор обмежень A0=(a10,...,am0)т — невід'ємний.
КЗЛП елементарно визначає такі основні в лінійному програмуванні конструкції:*
деякий ДБР — x(0)=(a10,...,am0,0,...,0);*
його базис — m-вимiрнi одиничні вектори (1,0,...,0)т, (0,1,...,0)т,..., (0,...,0,1)т;*
його базисну матрицю B — одиничну матрицю розміру mЧm;*
базисні змінні — x1,...,xm.
Стандартна ЗЛП зводиться в загальному випадку до канонічної ЗЛП додаванням штучних невід'ємних змінних до лівих частин обмежень i введенням цих же змінних з досить великим коефіцієнтом М>0 до цільової функції (М-метод). М-задача має вигляд: L(x) = c1x1 + ... + cnxn + M(y1 + ... + ym) > min, a11x1 + . . . + a1n xn + y1 = a10, . . . . . . . . . . . . . . . . . . . . . . . . . . . . , am1x1 + . . . + amnxn + ym = am0, xj?0, j=1,...,n, yi?0, i=1,...,m, ai0?0, i=1,...,m. Ознака оптимальності: Якщо на деякому кроцi СМ симплекс-рiзницi ДБР x* невід'ємні, то x* — оптимальний розв'язок КЗЛП. Умови відсутності розв'язку:
1) 1.ЗЛП не має оптимального розв'язку, якщо на якому-небудь кроцi хоча б один вектор умов Aj з від'ємною оцінкою Д j не має додатних компонент;
2) 2.ЗЛП не має розв'язкiв, якщо хоча б одна штучна змінна додатна у випадку, коли виконується ознака оптимальності.
Постановка задачі(Варіант 1):
В задачі, що пропонується нижче, всі змінні невід'ємні, розв’язати їх за допомогою симплекс-методу.
x1+ x2 +x3 > max
x1 – x4 - 2x6 =< 5
x2 + 2x4 – 3x5 + x6 =< 3
x3 + 2x4 - 5x5 + 6x6 =<5
Розв’язання задачі :
y1=5-(0x1+0x2+0x3-x4+0x5-2x6)
y2=3-(0x1+x2+0x3+2x4-3x5+x6)
y3=5-(0x1+0x2+x3+2x4-5x5+6x6)
z=0-(x1+x2+x3) |
Вільний член | X1 | X2 | X3 | X4 | X5 | X6
Z | 0
-5 | 1
-1 | 1
0 | 1
0 | 0
1 | 0
0 | 0
2
Y1 | 5
5 | 1
1 | 0
0 | 0
0 | -1
-1 | 0
0 | -2
-2
Y2 | 3
0 | 0
0 | 1
0 | 0
0 | 2
0 | -3
0 | 1
0
Y3 | 5
0 | 0
0 | 0
0 | 1
0 | 2
0 | -5
0 | 6
0
Вільний член | Y1 | X2 | X3 | X4 | X5 | X6
Z | -5
-6 | -1
0 | 1
-2 | 1
0 | 1
-4 | 0
6 | 2
-2
X1 | 5
6 | 1
0 | 0
2 | 0
0 | -1
4 | 0
-6 | -2
2
Y2 | 3
3 | 0
0 | 1
1 | 0
0 | 2
2 | -3
- 3 | 1
1
Y3 | 5
-18 | 0
0 | 0
-6 | 1
0 | 2
-12 | -5
18 | 6
-6
Вільний член | Y1 | X2 | X3 | X4 | X5 | Y2
Z | -11
6 | -1
0 | -1
36/13 | 1
-6/13 | -3
60/13 | 6
-6/13 | -2
36/13
X1 | 11
-6 | 1
0 | 2
-36/13 | 0
6/13 | 3
-60/13 | -6
6/13 | 2
-36/13
X6 | 3
-3 | 0
0 | 1
-18/13 | 0
3/13 | 2
-30/13 | -3
3/13 | 1
-18/13
Y3 | -13
-1 | 0
0 | -6
-6/13 | 1
1/13 | -10
- 10/13 | 13
1/13 | -6
-6/13
Вільний член | Y1 | X2 | X3 | X4 | Х9 | Y2
Z | -5
| -1
| 23/13
| 7/13
| 21/13
| -6/13
| 10/13
X1 | 5
| 1
| -10/13
| 6/13
| -21/13
| 6/13
| -10/13
X6 | 0 |
0 | -5/13 | -3/13 | 56/13 | 3/13 | 31/13
Х5 | -1 |
0 | 6/31 | 1/13 | -10/13 | 1/13 | -6/13
Висновок:
При розв’язку даного завдання, приходимо до висновку, що задача не має оптимального розв’язку
