Контрольна робота Завдання 1 Рішення задач лінійного програмування графічним методом Мета завдання: придбати практичні навички вирішення завдань лінійного програмування графічним методом.
Індивідуальне завдання Знайти максимум і мінімум лінійної форми графічним методом за вихідними даними завдання ЛП (таблиця 1).
Таблиця 1
Номер варіанта
| Цільова функція
| Обмеження задачі лінійного програмування
|
6
|
|
|
Рішення завдання Побудуємо область
L допустимих рішень. Замінимо в кожному
нерівності завдання
знак нерівності на знак рівності. Отримаємо рівняння прямих:
x 1 +4
x 2 = 8, 2 x 1 - x 2 = 4, x 1 + x 2 = 1, x 1 = 0, x 2 = 0. Область L визначається як загальна частина півплощини,
відповідних нерівностей обмежень (
малюнок 1).
Малюнок 1. Графічне рішення задачі ЛП
У цьому завданню вона становить багатокутник
ABCD. Для знаходження екстремуму
функції Z =- 2 x 1 +4 x 2 , Будуємо роздільну пряму, прирівнюючи лінійну форму нулю:
Z = 0. Будуємо градієнт цільової
функції C (2, 4).
Мінімальне значення функції в точці D (4,5; 0,7), а максимальне в точці
B. Аналіз виконання
завдання лінійного програмування В результаті
рішення задачі лінійного програмування були отримані мінімум і максимум аналізованої функції, внаслідок
того, що область обмежень представляє собою замкнутий багатокутник, якщо б фігура області обмежень була не замкнута, функція могла б не
мати одного або обох екстремумів в заданій області.
Завдання 2 Рішення задач ЛП симплексним методом з використанням симплекс-таблиць Мета завдання: закріпити теоретичні відомості і набути практичних навичок вирішення завдань ЛЗ
симплекс-методом.
Індивідуальне завдання Знайти максимум лінійної форми
Z = c 1 x 1 + c 2 x 2 за умов:
Дані представлені в
таблиці 2.
Номер варіанта
| A 11
| A 12
| A 21
| A 22
| A 31
| A 32
| B 1
| B 2
| B 3
| C 1
| C 2
|
6
| 4
| 1
| 3
| 6
| 8
| 7
| 43
| 74
| 76
| 7
| 4
|
Наведемо завдання ЛП до канонічного вигляду:
-Z '=-Z =-7x
1-4x 2 при обмеженнях
x
3, x
4, x
5 - додаткові
змінні.
У другому рівнянні додаткова мінлива введена з коефіцієнтом -1 і рівняння помножена на -1.
Постановка задачі у вигляді
матриці системи обмежень
Рішення задачі ЛП до складених симплекс-таблицями
Одиничні вектори
A 3, A 4, A 5 утворюють базис тривимірного простору
(m = 3). Вирішувати це завдання алгоритмом
симплекс-методу можна, оскільки змінні
x 3, x 4, x 5 входять з коефіцієнтом +1
відповідно в перше, друге і третє обмеження. Таким чином,
x 3, x 4, x 5 - базисні змінні, а інші небазисних. Вважаючи небазисних змінні в обмеженнях рівними нулю, отримаємо вихідне дозволене базисне рішення:
X 0 = (0,0,43, -74,76). Заповнюємо вихідну симплекс-таблицю (таблиця 2)
Таблиця 2. Нульова симплекс-таблиця
i
| Б x
| С б
| A 0
| - 7
| -4
| 0
| 0
| 0
| T
|
A 1
| A 2
| A 3
| A 4
| A 5
| |
1
| A 3
| 0
| 43
| 4
| 1
| 1
| 0
| 0
|
|
2
| A 4
| 0
| 74
| -3
| -6
| 0
| 1
| 0
|
3
| A 5
| 0
| 7 червня
| -8
| 7
| 0
| 0
| 1
|
4
| | | 0
| 7
| 4
| 0
| 0
| 0
|
Так як серед різниць є позитивні, то
X 0 не є оптимальним рішенням. Будуємо нове базисне рішення.
.
Виводимо з базису вектор
A 3, так як
.
Дозволяє елемент таблиці
x 12 виділимо колом, а дозволяє стовпець і рядок стрілками.
Таблиця 3. Перша симплекс-таблиця
i
| Б x
| C б
| A 0
| -7
| -4
| 0
| 0
| 0
| T
|
A 1
| A 2
| A 3
| A 4
| A 5
|
|
1
| A 1
| -7
|
| 1
|
|
| 0
| 0
|
2
| A 4
| 0
|
| 0
|
|
| 1
| 0
|
3
| A 5
| 0
| 162
| 0
| 9
| 2
| 0
| 1
|
4
| | |
| 0
|
|
| 0
| 0
|
Так як серед різниць є позитивні, то оптимальне рішення не отримано. Будуємо нове базисне рішення.
.
Виводимо з базису вектор
A 4, так як
.
Таблиця 4. Друга симплекс-таблиця
i
| Б x
| C б
| A 0
| -7
| - 4
| 0
| 0
| 0
| T
|
A 1
| A 2
| A 3
| A 4
| A 5
| |
1
| A 2
| - 4
| 43
| 4
| 1
| 4
| 0
| 0
|
2
| A 4
| 0
| 736
| 21
| 0
|
| 1
| 0
|
3
| A 5
| 0
| -225
| -36
| 0
| -34
| 0
| 1
|
4
| | |
| -9
| 0
|
| 0
| 0
|
Так як всі різниці в другій таблиці (таблиця 4) непозитивно:
, Т отримано оптимальне рішення:
min (- Z) = -225. Тоді
max (Z) =
- min (- Z) = 225
Аналіз оптимального плану.
Використання змінної x
1 недоцільно.
Завдання 3 Моделювання і рішення задач ЛП на ЕОМ Мета завдання: придбати практичні навички
моделювання задач ЛП і їх вирішення симплекс-методом з використанням прикладної програми SIMC.
Індивідуальне завдання Підприємство може працювати по 5-ти технологічним
процесам, причому кількість одиниць продукції, що випускається з різних ТП за од. часу
відповідно рівні 300, 260, 320, 400, 450 шт.
витрати виробничих факторів у гривнях при роботі з різних ТП протягом 1 од. часу і розташовуються
ресурси цих факторів у табл.5.
Знайти програму максимального випуску продукції.
Таблиця 5.
фактори
| Спосіб виробництва
| Ресурси, грн
|
| 1
| 2
| 3
| 4
| 5
|
Сировина
| 12
| 15
| 10
| 12
| 11
| 1300
|
Ел.енергія
| 0,2
| 0,1
| 0,2
| 0,25
| 0,3
| 30
|
Зарплата
| 3
| 4
| 5
| 4
| 2
| 400
|
Накладні витрати
| 6
| 5
| 4
| 6
| 4
| 800
|
Математична інтерпретація задачі
Вихідні
масиви, записані у вигляді, придатному для вирішення завдання по програмі SIMC
5
4
12.000 15.000 10.000 12.000 11.000 <1300.000
0.200 0.100 0.200 0.250 0.300 <30.000
3.000 4.000 5.000 4.000 2.000 <400.000
6.000 5.000 4.000 6.000 4.000 <800.000
300.000 260.000 320.000 400.000 450.000
Роздруківка ЕОМ у результаті прийняття рішень Ітерація N = 1 РІШЕННЯ ЗНАЙДЕНО!
ПОТОЧНА СИМПЛЕКС-ТАБЛИЦЯ ЗАДАЧА НЕ виродилися
Бx Cб Po 1 2 3 4 травня
6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000
7 0.000 30.000 0.200 0.100 0.200 0.250 0.300
8 0.000 400.000 3.000 4.000 5.000 4.000 2.000
9 0.000 800.000 6.000 5.000 4.000 6.000 4.000
0.000 300.000 260.000 320.000 400.000 450.000
КОД ПОМИЛКИ = 0
ОПТИМАЛЬНИЙ ЗНАЧЕННЯ БАЗИС-ВЕКТОРА І РІШЕННЯ
Оптимум ЦІЛЬОВОЇ ФУНКЦІЇ = 0.0000
Ітерація N = 1 ПРОДОВЖЕННЯ РІШЕННЯ ПОТОЧНА СИМПЛЕКС-ТАБЛИЦЯ ЗАДАЧА НЕ виродилися
Бx Cб Po 1 2 3 4 травня
6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000
7 0.000 30.000 0.200 0.100 0.200 0.250 0.300
8 0.000 400.000 3.000 4.000 5.000 4.000 2.000
9 0.000 800.000 6.000 5.000 4.000 6.000 4.000
0.000 -300.000 -260.000 -320.000 -400.000 -450.000
У БАЗИС ВВОДИТЬСЯ 5 стовпець
З базису Висновок 7 стовпець
Ітерація N = 2 ПРОДОВЖЕННЯ РІШЕННЯ ПОТОЧНА СИМПЛЕКС-ТАБЛИЦЯ ЗАДАЧА НЕ виродилися
Бx Cб Po 1 2 3 4 липня
6 0.000 200.000 4.667 11.333 2.667 2.833 -36.667
5 450.000 100.000 0.667 0.333 0.667 0.833 3.333
8 0.000 200.000 1.667 3.333 3.667 2.333 -6.667
9 0.000 400.000 3.333 3.667 1.333 2.667 -13.333
45000.000 -0.000 -110.000 -20.000 -25.000 1500.000
У БАЗИС ВВОДИТЬСЯ 2 Стовпець
З базису вивід 6 стовпець
Ітерація N = 3 ПРОДОВЖЕННЯ РІШЕННЯ ПОТОЧНА СИМПЛЕКС-ТАБЛИЦЯ ЗАДАЧА НЕ виродилися
Бx Cб Po 1 3 4 6 липня
2 260.000 17.647 0.412 0.235 0.250 0.088 -3.235
5 450.000 94.118 0.529 0.588 0.750 -0.029 4.412
8 0.000 141.176 0.294 2.882 1.500 -0.294 4.118
9 0.000 335.294 1.824 0.471 1.750 -0.324 -1.471
46941.176 45.294 5.882 2.500 9.706 1144.118
КОД ПОМИЛКИ = 0
ОПТИМАЛЬНИЙ ЗНАЧЕННЯ БАЗИС-ВЕКТОРА І РІШЕННЯ
X2 = 17.6471
X5 = 94.1176
Оптимум ЦІЛЬОВОЇ ФУНКЦІЇ = 46941.1765
РІШЕННЯ ЗНАЙДЕНО!
Оптимальний план.
Економічна інтерпретація оптимального рішення.
Відповідно до отриманого результату випуск продукції по 1,3 і 4 технологічним процесам недоцільний.
Завдання 4 Моделювання транспортних завдань та їх вирішення методом потенціалів Мета завдання: придбати практичні навички
моделювання і розв'язання
транспортної задачі ЛП методом потенціалів.
Індивідуальне завдання Скласти оптимальний розподіл трьох видів
механізмів на чотирьох ділянках робіт, що забезпечують мінімальну
собівартість виконання всієї
роботи. Кількість одиниць механізмів, потреби ділянок у
механізмах і
собівартість виконання одиниці роботи кожним
механізмом на
відповідній ділянці наведені в таблиці 6.
Таблиця 6. 06 варіант транспортної задачі
Вид механізму
| Собівартість виконання одиниці роботи механізму, гр.
| Кількість одиниць a i механізмів
|
B 1
| B 2
| B 3
| B 4
|
A 1
| 11
| 4
| 3
| 1
| 15
|
A 2
| 6
| 8
| 9
| 7
| 10
|
A 3
| 4
| 8
| 4
| 2
| 35
|
Потреби b j ділянок у механізмах
| 25
| 20
| 10
| 5
| |
Математичне формулювання транспортної задачі
Нехай
x ij - кількість одиниць роботи, виконаної механізмом виду
a i, на ділянці роботи
b j. Потрібно визначити план розподілу механізмів, здатний мінімізувати собівартість виконання всієї роботи:
при обмеженнях:
1)
; - Всі механізми повинні бути задіяні;
2)
; - Всі ділянки повинні бути завантажені;
3)
; - Кількість одиниць роботи не може бути негативним
Умова розв'язності задачі виконується:
25 +20 +10 +5 = 15 +10 +35; 60 = 60.
Вихідний опорний план, складений за методом північно-західного кута
Таблиця 7
I
| | a i
|
B 1
| B 2
| B 3
| B 4
|
A 1
| 11
| 4 15
| 3
| 1
| 15
|
A 2
| 6 5
| 8 5
| 9
| 7
| 10
|
A 3
| 4 20
| 8
| 4 10
| 2 5
| 5 Березня
|
b j
| 25
| 20
| 1 0
| 5
| |
Рішення транспортної задачі методом потенціалів Отже, видно що до числа зайнятих клітин слід ввести клітину (2,1).
Отримаємо новий покращений план - таблиця 8.
Таблиця 8
I
| | a i
|
B 1
| B 2
| B 3
| B 4
|
A 1
| 11
| 4 15
| 3
| 1
| 15
|
A 2
| 6 5
| 8 5
| 9
| 7
| 10
|
A 3
| 4 20
| 8
| 4 10
| 5 5
| 5 Березня
|
b j
| 25
| 20
| 1 0
| 5
| |
Введемо в число зайнятих клітину (1,4). Отримаємо новий покращений план - Таблиця 9.
Таблиця 9
I
| | a i
|
B 1
| B 2
| B 3
| B 4
|
A 1
| 11
| 4 10
| 3 5
| 1
| 15
|
A 2
| 6
| 8 10
| 9
| 7
| 10
|
A 3
| 4 25
| 8
| 4 5
| 2 5
| 5 Березня
|
b j
| 25
| 20
| 1 0
| 5
| |
Так як,
- То даний план є оптимальним і значення собівартості за даним планом.
x 12 = 15; x 21 = 5; x 22 = 5; x 31 = 20; x 33 = 10; x 34 = 5. Z = 15 * 4 +5 * 6 +5 * 8 +20 * 4 +10 * 4 +5 * 2 = 260. Аналіз оптимального плану
Даний оптимальний план показує, як потрібно розподілити механізми по ділянках для отримання мінімальної собівартості виконаної роботи.
Завдання 5 Рішення транспортної задачі на ЕОМ Мета завдання: придбати практичні навички вирішення транспортної задачі на ЕОМ з використанням прикладної програми TRAN2.
Індивідуальне завдання: Скласти оптимальний розподіл трьох видів механізмів на чотирьох ділянках робіт, що забезпечують мінімальну собівартість виконання всієї роботи. Кількість одиниць механізмів, потреби ділянок у механізмах і собівартість виконання одиниці роботи кожним механізмом на відповідній ділянці наведені в таблиці 6.
Таблиця 10. 06 варіант транспортної задачі
Вид механізму
| Собівартість виконання одиниці роботи механізму, гр.
| Кількість одиниць a i механізмів
|
B 1
| B 2
| B 3
| B 4
|
A 1
| 11
| 4
| 3
| 1
| 15
|
A 2
| 6
| 8
| 9
| 7
| 10
|
A 3
| 4
| 8
| 4
| 2
| 35
|
Потреби b j ділянок у механізмах
| 25
| 20
| 10
| 5
| |
Вихідні масиви для розв'язання транспортної задачі за програмою TRAN 2 Роздруківка з ЕОМ з результатом рішення Оптимальний план транспортної задачі x 12 = 15; x 21 = 5; x 22 = 5; x 31 = 20; x 33 = 10; x 34 = 5. Z = 15 * 4 +5 * 6 +5 * 8 +20 * 4 +10 * 4 +5 * 2 = 260. Аналіз результатів і висновки
Рішення транспортної задачі на ЕОМ
автоматизує роботу з обчислення рішень транспортних задач і на тестованому вхідному умова виходить за 3 ітерації, як і при ручному обчисленні.
Завдання 6 Рішення багатоетапних задач методом динамічного програмування Мета завдання: придбати практичні навички вирішення багатоетапних задач методом динамічного програмування.
Індивідуальне завдання. У таблиці 11 наведені значення
g i (x) можливого приросту продукції на чотирьох підприємствах залежно від виділеної на реконструкцію і
модернізацію виробництва суми
x. Розподілити між
підприємствами наявні 100 тис. гр., Щоб загальний приріст
f 4 (100) випуску продукції був максимальним. Для спрощення обчислень значення
x приймати кратними 20 тис. гр.