logo
Економічна кібернетика

5. Рішення симплекс-методом, використовуючи перетворення Йордана-Гаусса.

Шляхом введення нових змінних yi (i=1,5) переходимо до канонічної форми у наступному вигляді:

Y1=-x1-3x2+x3+2x4+20≥0

Y2=-x1-x2+5≥0

Y3=-x1+x2+3≥0

Y4=-2x3-x4+4≥0

Y5=x3-x4+4≥0

xi≥0 (i=1,4)

yj≥0 (j=1,5)

x1+3x2-x3-2x4+y1=20

x1+x2+y2=5

x1-x2+y3=3

2x3+x4+y4=4

-x3+x4+y5=2

xi≥0 (i=1,4)

yj≥0 (j=1,5)

Складемо повну симплекс-таблицю, яка відповідає даній задачі.

X1

X2

X3

X4

Y1

Y2

Y3

Y4

Y5

F

1

Y1

1

3

-1

-2

1

0

0

0

0

0

20

Y2

1

1

0

0

0

1

0

0

0

0

5

Y3

1

-1

0

0

0

0

1

0

0

0

3

Y4

0

0

2

1

0

0

0

1

0

0

4

Y5

0

0

-1

1

0

0

0

0

1

0

2

F

-2

-3

2

1

0

0

0

0

0

1

0

Так як у Fрядку є від’ємні елементи, обираємо найбільший по модулю від’ємний елемент (-3) - отже 2 стовпець буде розрахунковим. Для визначення розрахункового рядка знайдемо найменше невід’ємне відношення вільних членів до елементів розрахункового (2-го) стовпця.

Min={20/3;5/1}=5/[1]

Розрахунковим рядком є 2 рядок: R22=a22=1

Для переходу до нового базису над повною симплекс-таблицею з вибраним розрахунковим елементом зробимо перетворення Йордана-Гаусса. Елементи розрахункового рядка ділимо на розрахунковий елемент. У розрахунковому стовпці всі елементи нулі і тільки замість розрахункового елемента ставимо одиницю. Всі інші елементи шукаємо за правилом прямокутника.

Наприклад елемент а11=а11-a12*а21/а22=1-1*3/1=-2

Ця операція робиться до тих пір, поки у F рядку всі елементи не будуть додатніми.

X1

X2

X3

X4

Y1

Y2

Y3

Y4

Y5

F

1

Y1

-2

0

-1

-2

1

-3

0

0

0

0

5

X2

1

1

0

0

0

1

0

0

0

0

5

Y3

2

0

0

0

0

1

1

0

0

0

8

Y4

0

0

2

1

0

0

0

1

0

0

4

Y5

0

0

-1

1

0

0

0

0

1

0

2

F

1

0

2

1

0

3

0

0

0

1

15

Відповідь: x2=5, Fmax=15.

Перевірка : F=2x1+3x2-2x3-x4=3*5=15