Лабораторне заняття №6

 

Тема заняття: Розв’язання задач лінійного програмування методом штучного базису.

Мета: сформувати вміння та навички розв’язування задач лінійного програмування методом штучного базису.

Методичні рекомендації: Вивчити лекцію №3 та ознайомиться з наступною літературою [1 с. 39-52], [2 c. 33-74], [3 с. 32-78].

Постановка завдання:

Теоретичні рекомендації вирішення задач ЛП зі штучним базисом наведені до лабораторної роботи 4, тому розглянемо вирішення задачі на прикладі.

Розв’язати приклад 1 із додатковою умовою: продукція С має виготовлятися в кількості не менш як 9 одиниць.

Розв’язування. Математичну модель сформульованої задачі запишемо так:

Застосовуючи для розв’язування поставленої задачі симплекс-метод, спочатку записуємо систему обмежень у канонічній формі, а далі — у векторній:

Зауважимо, що нерівність типу «≥» у рівняння перетворюємо введенням у ліву частину обмеження додаткової змінної зі знаком «–».

Векторна форма запису:

Серед записаних векторів є лише два одиничні — та , а базис у тривимірному просторі має складатися з трьох одиничних векторів. Ще один одиничний вектор можна дістати, увівши в третє обмеження з коефіцієнтом +1 штучну змінну х ₈, якій відповідатиме одиничний вектор .

Тепер можемо розглянути розширену задачу лінійного програмування:

На відміну від додаткових змінних штучна змінна х ₈ має в цільовій функції Z коефіцієнт + М (для задачі на min) або – М (для задачі на max), де М — досить велике додатне число.

У розширеній задачі базисними змінними є х ₅, х ₆, х ₈, а решта змінних вільні. Початковий опорний план задачі:

Складемо першу симплексну таблицю задачі:

Базис	С баз	План				–5				– М	θ
х 1	х 2	х 3	х 4	х 5	х 6	х 7	х 8
х 5											112,5
х 6
←х 8	– М								–1
Zj – Cj ≥ 0		–8	–10
–9 М			– М				М

Розраховуючи оцінки першого опорного плану, дістаємо
Z ₀ = 0 – 9 M, Z ₁ – C ₁ = –8, Z ₂ – C ₂ = –10, Z ₃ – C ₃ = 0 – М і т. д.
Як бачимо, значення оцінок складаються з двох частин, одна з яких містить М, а інша — просто число. Тому для зручності розбиваємо оцінковий рядок на два. У перший оцінковий рядок записуємо просто число, а в другий — число з коефіцієнтом М.

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

Подальше розв’язування задачі наведене у вигляді таблиці:

Базис	С баз	План				–5				– М	θ
х 1	х 2	х 3	х 4	х 5	х 6	х 7	х 8
← х 5										–4
х 6										–1	185,5
х 3									–1		—
Zj – Cj ≥ 0		–8	–10
								М
х 2			2/3			2/3	1/3		4/3	–4/3
← х 6			5/3			2/3	–2/3		–5/3	5/3
х 3									–1		—
Zj – Cj ≥ 0		–4/3			35/3	10/3		40/3	–40/3
								М
х 2						2/5	3/5	–2/5		–2
х 1						2/5	–2/5	3/5	–1
х 3									–1
Zj – Cj ≥ 0					61/5	14/5	4/5		–12
								М

Оптимальним планом задачі є вектор

Х ^* = (57; 100; 9; 0; 0; 0; 0),

Отже, оптимальним є виробництво 57 одиниць продукції А, 100 одиниць продукції В і 9 одиниць продукції С. Тоді прибуток буде найбільшим і становитиме 1456 дол.

Задача 1.

Розв’язати задачу лінійного програмування методом штучного базису:

1.1. ; 1.2. ;

 

 

1.3. ; 1.4. ;

ДОДАТКОВІ ЗАВДАННЯ:

№1: Розв’язати задачу лінійного програмування методом штучного базису:

1.1. ; 1.2. ;