ДРУГИЙ ЕТАП ДВОХЕТАПНОГО СИМЛЕКС-МЕТОДУ - Рішення оптимізаційної задачі лінійного програмування

Отже, як видно з Таблиці 4, всі штучні змінні вийшли з базису, штучна цільова функція обнулилася - значить, перший етап двохетапного симплекс-метода закінчений, знайдено початкове допустиме рішення: (Х1,X2,X3,X4,X5,X6) = (0,0,0,0,0,0), цільова функція Е=0. Тепер переходимо до реалізації другого етапу: викреслюємо з таблиці рядок штучної цільової функції і стовпці штучних змінних; над новою таблицею виконуємо звичайні процедури симплекс-метода, а саме: провідний стовпець визначається також, як і для першого етапу двохетапного симплекс-метода, єдина відмінність полягає в тому, що максимальний по модулю негативний коефіцієнт знаходимо по Е-рядку цільової функції. Розрахунок ведемо до тих пір, поки в Е-рядку не залишиться негативних коефіцієнтів:

БП

X1

X2

X3

X4

X5

X6

X7

X8

БР

E

0

0

-5

0

0

-5

0

0

0

X7

1

1

1

0

0

0

1

0

8

X8

-0,33

-0,33

1

0

0

2

0

1

8

X4

0,33

0

-0,33

1

0

-0,33

0

0

0

X5

0

0,33

-0,67

0

1

-0,67

0

0

0

Таблиця 5. Симплекс-таблиця №4.

Наше початкове допустиме рішення не є оптимальним, оскільки в Е-рядку містяться негативні коефіцієнти. Визначимо по Е-рядку нову змінну для включення в базис. Це змінна X3, оскільки -5 - максимальне по модулю негативне число (коефіцієнт Е-рядка при змінній X6 також рівний -5, тому вибрали будь-яку з цих змінних, наприклад X3). Стовпець X3 стає таким, що веде. По мінімальному сімплексному відношенню ( 8/1=8; 8/1=8) для виключення з базису вибираємо змінну Х7 (сімплексне відношення при змінній X8 також рівне 8, тому вибрали будь-яку з цих змінних). Провідний елемент рівний 1. Після проведених пересчетов отримуємо нову симплекс-таблицю:

БП

X1

X2

X3

X4

X5

X6

X7

X8

БР

E

5

5

0

0

0

-5

5

0

40

X3

1

1

1

0

0

0

1

0

8

X8

-1,33

-1,33

0

0

0

2

-1

1

0

X4

0,67

0,33

0

1

0

-0,33

0,33

0

2,67

X5

0,67

1

0

0

1

-0,67

0,67

0

5,33

Таблиця 6. Симплекс-таблиця №5.

Отже, як видно з таблиці, деякі з шуканих змінних, а саме Х3, Х4 і Х5, почали рости, що привело і до зростання значення цільової функції - з нульового значення вона прийняла значення 40. Це можна пояснити тим, що з точки початкового допустимого рішення ми перейшли до сусідньої кутової точки області допустимих рішень, причому в цій сусідній крапці зростання цільової функції максимальне. Проте в Е-рядку є ще негативний коефіцієнт, тому продовжимо розрахунки.

Визначимо по Е-рядку нову змінну для включення в базис. Це змінна X6, оскільки -5 - максимальне по модулю негативне число. Стовпець X6 стає таким, що веде. По мінімальному сімплексному відношенню ( 0/2=0) для виключення з базису вибираємо змінну Х8. Отримуємо нову симплекс-таблицю:

БП

X1

X2

X3

X4

X5

X6

X7

X8

БР

E

1,67

1,67

0

0

0

0

2,5

2,5

40

X3

1

1

1

0

0

0

1

0

8

X6

-0,67

-0,67

0

0

0

1

-0,5

0,5

0

X4

0,44

0,11

0

1

0

0

0,17

0,17

2,67

X5

0,22

0,55

0

0

1

0

0,33

0,33

5,33

Таблиця 7. Симплекс-таблиця №6.

Оскільки всі коефіцієнти E-рядка таблиці 7 позитивних, то оптимальне рішення знайдене. Оптимальний план полягає в тому, щоб токарний верстат працював над деталями типу 3 8 годин за зміну, тобто всю робочу зміну, і не працював над деталями типу 1 і 2 взагалі. Верстат-автомат повинен працювати за зміну 2,67 години над деталями типу 1 і 5,33 години над деталями типу 2 і не повинен працювати над деталями типу 3. При цьому за зміну випускатиметься максимально можлива кількість комплектів деталей, а саме 40 комплектів. Жоден з верстатів не простоюватиме.

Похожие статьи




ДРУГИЙ ЕТАП ДВОХЕТАПНОГО СИМЛЕКС-МЕТОДУ - Рішення оптимізаційної задачі лінійного програмування

Предыдущая | Следующая