Задач лінійного програмування

Продукція чотирьох видів А, В, С і D проходить послідовну обробку на двох верстатах. Тривалість обробки одиниці продукції кожного виду наведена в табл. 2.8.Таблиця 2.8

Верстат	Тривалість обробки одиниці продукції
А	В	С	D

Витрати на виробництво одиниці продукції кожного виду визначають як величини, прямо пропорційні до часу використання верстатів (у машино-годинах). Вартість однієї машино-години становить 10 грн для верстата 1 і 15 грн — для верстата 2. Тривалість використання верстатів обмежена: для верстата 1 вона становить 450 машино-годин, а для верстата 2 — 380 машино-годин.

Ціна одиниці продукції видів А, В, С і D дорівнює відповідно 73, 70, 55 та 45 грн.

Визначити оптимальний план виробництва продукції всіх чотирьох видів, який максимізує загальний прибуток.

Побудова економіко-математичної моделі. Нехай х_j — план виробництва продукції j-го виду, де j може набувати значень від 1 до 4.

Умовами задачі будуть обмеження на тривалість використання верстатів для виробництва продукції всіх видів:

для верстата 1 (маш.год.);

для верстата 2 (маш.-год.).

Цільовою функцією задачі є загальний прибуток від реалізації готової продукції, який розраховується як різниця між ціною та собівартістю виготовлення продукції кожного виду:

Отже, математична модель цієї задачі має такий вигляд:

за умов:

Розв’язання. Розв’яжемо задачу симплекс-методом згідно з розглянутим алгоритмом.

1. Запишемо систему обмежень задачі в канонічному вигляді. Для цього перейдемо від обмежень-нерівностей до строгих рівнянь, увівши до лівої частини обмежень додаткові змінні х₅ та х₆:

Ці додаткові змінні за економічним змістом означають недовикористаний для виробництва продукції час роботи верстатів 1 та 2. У цільовій функції Z додаткові змінні мають коефіцієнти, які дорівнюють нулю:

Канонічну систему обмежень задачі запишемо у векторній формі:

де

Оскільки вектори та одиничні та лінійно незалежні, то саме з них складається початковий базис у зазначеній системі векторів. Змінні задачі х₅ та х₆, що відповідають одиничним базисним векторам, називають базисними, а решту — вільними змінними задачі лінійного програмування. Прирівнюючи вільні змінні до нуля, з кожного обмеження задачі дістаємо значення базисних змінних:

Згідно з визначеними векторна форма запису системи обмежень цієї задачі матиме вигляд:

Оскільки додатні коефіцієнти х5 та х6 відповідають лінійно незалежним векторам, то за означенням

є опорним планом задачі і для цього початкового плану

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

Базис	С_баз	План				– 5
х₁	х₂	х₃	х₄	х₅	х₆
х₅
х₆
Z_j – с_j ≥ 0		–8	–10

Елементи останнього рядка симплекс-таблиці є оцінками Δj, за допомогою яких опорний план перевіряють на оптимальність. Їх визначають так:

;

У стовпчику «План» оцінкового рядка записують значення цільової функції Z, якого вона набуває для визначеного опорного плану:

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

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

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

Для введення до нового базису вибираємо змінну х₂, оскільки їй відповідає найбільша за абсолютною величиною оцінка з-поміж тих, які не задовольняють умову оптимальності (|–10|>|–8|).

Щоб визначити змінну, яка підлягає виключенню з поточного базису, для всіх додатних елементів стовпчика «х₂» знаходимо відношення і вибираємо найменше значення. Згідно з даними симплексної таблиці маємо, що , і тому з базису виключаємо змінну х₅, а число а₁₂ = 3 — розв’язувальний елемент. Дальший перехід до нового опорного плану задачі полягає в побудові наступної симплексної таблиці, елементи якої розраховують за методом Жордана—Гаусса.

Друга симплексна таблиця має такий вигляд:

Базис	С_баз	План				– 5
х₁	х₂	х₃	х₄	х₅	х₆
х₂			2/3		4/3	2/3	1/3
х₆			5/3		-5/3	2/3	–2/3
Z_j – с_j ≥ 0		-4/3		40/3	35/3	10/3

У цій таблиці спочатку заповнюють два перших стовпчики «Базис» і «Сбаз», а решту елементів нової таблиці розраховують за розглянутими нижче правилами:

1. Кожний елемент розв’язувального (напрямного) рядка необхідно поділити на розв’язувальний елемент і отримані числа записати у відповідний рядок нової симплексної таблиці.

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

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

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

Усі інші елементи наступної симплексної таблиці розраховують за правилом прямокутника.

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

1 — розв’язувальний елемент (число 1);

2 — число, що стоїть на місці елемента нової симплексної таблиці, який ми маємо розрахувати;

3 та 4 — елементи, що розміщуються в двох інших протилежних вершинах умовного прямокутника.

Необхідний елемент нової симплекс-таблиці визначають за такою формулою:

Наприклад, визначимо елемент , який розміщується в новій таблиці в другому рядку стовпчика «х₄». Складемо умовний прямокутник:

Тоді . Це значення записуємо в стовпчик «х₄» у другому рядку другої симплексної таблиці.

Аналогічно розраховують усі елементи нової симплексної таблиці, у тому числі й елементи стовпчика «План» та оцінкового рядка. Наявність двох способів зображення визначення оцінок опорного плану (за правилом прямокутника та за відповідною формулою) дає змогу контролювати правильність арифметичних обчислень на кожному кроці симплекс-методу.

Після заповнення нового оцінкового рядка перевіряємо виконання умови оптимальності Z_j – с_j ≥ 0 для другого опорного плану. Цей план також неоптимальний, оскільки . Використовуючи процедуру симплекс-методу, визначаємо третій опорний план задачі, який наведено у вигляді таблиці:

Базис	С_баз	План				– 5
х₁	х₂	х₃	х₄	х₅	х₆
х₂						2/5	3/5	–2/5
х₁					–1	2/5	–2/5	3/5
Z_j – с_j ≥ 0					61/5	14/5	4/5

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

або

Х* = (48; 118; 0; 0; 0; 0);

Отже, план виробництва продукції, що передбачає випуск 48 одиниць продукції А та 118 одиниць продукції В, є оптимальним. Він уможливлює отримання найбільшого прибутку за заданих умов (1564 грн). При цьому час роботи верстатів використовується повністю (х₅ = х₆ = 0).

Наведені вище три симплексні таблиці можна об’єднати в одну та послідовно записувати в ній всі ітерації.

Задача 2.13.

(Метод штучного базису).

Продукція фабрики випускається у вигляді паперових рулонів стандартної ширини — 2 м. За спеціальним замовленням споживачів фабрика постачає також рулони інших розмірів, розрізуючи стандартні.

Замовлення	Потрібна ширина рулона, м	Кількість замовлених рулонів
	0,8
	1,0
	1,2

Типові замовлення на рулони нестандартних розмірів наведено в табл. 2.9.

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

Розв’язання. Аби виконати спеціальні замовлення, які надійшли, розглянемо п’ять можливих варіантів розрізування стандартних рулонів, що можуть використовуватися в різних комбінаціях. Варіанти розкрою наведено в табл. 2.10.

МОЖЛИВІ ВАРІАНТИ РОЗРІЗУВАННЯ СТАНДАРТНИХ РУЛОНІВ ПАПЕРУ

Потрібна ширина рулона, м	Кількість нестандартних рулонів за варіантами

0,8
1,0
1,2
Обсяг відходів, м	0,4	0,2	0,8

Нехай x_j — кількість стандартних рулонів паперу, які буде розрізано j-способом, .

Обмеження задачі пов’язані з обов’язковою вимогою повного забезпечення необхідної кількості нестандартних рулонів за спеціальними замовленнями. Якщо брати до уваги всі подані в таблиці способи розкрою, то дістанемо такі умови (обмеження) даної задачі:

1. Щодо кількості рулонів шириною 0,8 м:

2х₁ + х₂ + х₃ = 150.

2. Щодо кількості рулонів шириною 1 м:

х₃ + 2х₄ = 200.

3. Стосовно кількості рулонів шириною 1,2 м:

х₂ + х₅ = 300.

Цільова функція задачі — це мінімальні загальні втрати паперу під час розрізування стандартних рулонів на рулони нестандартної ширини. Математично вона має такий вигляд:

Математична модель задачі загалом записується так:

за умов:

Для розв’язування цієї задачі застосуємо алгоритм симплекс-методу. Оскільки задачу сформульовано в канонічній формі, запишемо її відразу у векторній формі:

де

У системі векторів маємо лише один одиничний вектор . Тому в перше та друге обмеження введемо штучні змінні х₆ та х₇. Розширена задача матиме вигляд:

за умов:

Процес розв’язання задачі симплекс-методом подано у вигляді таблиці:

Базис	С_баз	План	0,4		0,2		0,8	М	M
х₁	х₂	х₃	х₄	х₅	х₆	х₇
х₆	M
х₇	M
х₅	0,8
Z_j – с_j ³ 0		–0,4	0,8	–0,2
	350 M	2 M	M	2 M	2 M
х₆	M
х₄					1/2
х₅	0,8
Z_j – с_j ³ 0		–0,4	0,8	–0,2
	150 M	2 M	M	M
х₁	0,4			1/2	1/2
х₄					1/2
х₅	0,8
Z_j – с_j ³ 0
х₂
х₄					1/2
х₅	0,8		–2		–1
Z_j – с_j ³ 0		–2		–1

Згідно з останньою симплексною таблицею запишемо оптимальний план задачі:

Х* = (0; 150; 0; 100; 150),

min Z = 120.

Визначений оптимальний план передбачає: щоб у повному обсязі виконати спеціальні замовлення, які надходять на паперову фабрику, необхідно розрізати 150 стандартних рулонів другим способом, 100 рулонів — четвертим і 150 — п’ятим. За такого оптимального варіанта розкрою обсяг відходів паперу буде найменшим і становитиме 120 м.

⇐ Предыдущая 1 234 5 6 7 Следующая ⇒