Заняття 2 Рішення задачі лінійного програмування симплекс-методом.

Мета заняття – придбати практичні навички рішення задач лінійного програмування симплекс-методом, використовуючи симплекс-таблицю.

Завдання. Вирішити симплекс-методом задачу лінійного програмування, використовуючи симплекс-таблиці. Знайти додаткові значення змінних які спрямовують в максимум лінійну форму (2.2) при умовах (2.1).

(2.1)

(2.2)

Вказівки до виконання

За своїм варіантом в табл. 2.1 знайти значення постійних величин виражень (2.1) та (2.2), де і – остання, j – предостання цифра номеру залікової книжки.

Таблиця 2.1 - Значення постійних величин

Виконання завдання здійснюється у такій послідовності:

1. Записати систему обмежень для невідомих у канонічному вигляді.

Введемо додаткові змінні до кожної нерівності системи для того, щоб записати їх у вигляді рівнянь.

Якщо кожне обмеження має змінну, яка входить до лівої частини рівняння з коефіцієнтом 1, а до всіх інших обмежень – з коефіцієнтом 0, то ця система обмежень представлена у переважному виді. Для нашої задачи система обмежень має переважний вигляд відносно змінних .

2. Скласти опорний план.

Якщо усі змінні, крім переважних прирівняти до 0, то переважні змінні будуть дорівнювати правим частинам рівнянь системи обмежень . Згідно з теоремою о структурі координат базисного рішення отримане рішення ( план ) буде опорним.

– базисне рішення,

– базисні змінні,

– вільні змінні.

3. Симплекс – таблиця.

Записати усі дані до симплекс – таблиці, основна частина якої складається з коефіцієнтів при основних змінних усіх рівнянь і одиничної матриці.

Симплекс-метод складається з математичних кроків, при яких від початкового опорного плану ми рухаємось до знаходження такого рішення, при якому функція цілі отримає своє максимальне значення, – знаходимо оптимальний план.

4. Кроки метода:

а) Оцінки змінних.

До симплекс-таблиці нижче додають рядок ( індексний рядок ), в яку записують оцінки змінних, обчислені за формулами:

, де – коефіцієнти при базисних змінних у функції цілі;

– вектор вільних членів у системі обмежень.

дає значення функції цілі для наданого плану .

; − оцінки вільних змінних, де

− вектор коефіцієнтів при цій змінній у системі обмежень;

– коефіцієнт при цій змінній у запису функції цілі.

Оцінки базисних змінних завжди дорівнюють 0.

Отриманий план дає функції цілі максимальне значення , якщо усі оцінки вільних змінних невід'ємні.

Тобто вести обчислення у симплекс-методі потрібно до тих пір, доки усі оцінки вільних змінних не стануть ≥ 0.

б) Розв'язуючий стовпчик та рядок.

Після того, як знайдені із значень обираємо найменше, відповідний стовпчик називають розв'язуючим.

Щоб отримати розв'язуючий рядок треба елементи стовпчика правих частин поділити на додатні елементи розв'зуючого стовпчика та серед отриманих часток обираємо найменшу:

.

Це число буде відповідати деякому рядку , цей рядок називають розв’язуючим.

При рішенні задачі на max Z , якщо у розв'язуючому стовпчику нема жодного додатного елемента, то функція цілі Z необмежена зверху та немає max значення.

Змінну , яка відповідає розв'язуючому стовпчику треба ввести до складу базисних змінних, а змінну виводять із базису. Таким чином, не змінив нульові значення інших вільних змінних, потрібно збільшити функцію Z за рахунок зменшення значення .

в) Друга симплекс-таблиця.

Для нових базисних змінних будують нову симплекс-таблицю, аналогічну першій. Щоб її заповнити, елементи розв'язуючого рядка ділять на розв'язуючий елемент, та результат записують у відповідний рядок, у тій клітинці, де стояв розв'язуючий елемент, тепер буде 1. Інші елементи розв'язуючого стовпчика будуть дорівнювати 0, так як − базисна.

Щоб знайти інші елементи нової симплекс-таблиці застосовують правило прямокутника:

в початковій таблиці виділяють прямокутник, вершинами якого є потрібні для обчислення елементи;

діагональ,яка містить розв’язуючий та шуканий елементи називають головною, а іншу – побічною;

від добутку елементів головної діагоналі віднімають добуток кутових елементів побічної діагоналі та отримане число ділять на розв’язуючий елемент.

г) Отримавши нову симплекс-таблицю з нею поступають відповідно описаному методу.

Обчислення роблять до тих пір, доки усі не стануть ≥0.

За даними останньої симплекс-таблиці визначити значення змінних, які забезпечують оптимальне розв'язання.

Контрольні запитання

1. Як будується симплекс-таблиця?.

2. Як визначаються ключовий стовпець, рядок і число?

3. Як визначаються числа головного рядку?

4. Правила визначення похідних чисел.

6. Ознака оптимального рішення.

7. Що визначають в результаті рішення числа в стовпці вільних членів і число в клітинці індексного рядку стовпця вільних членів?

ЛІТЕРАТУРА [1, 3, 5]