Розрахунок максимуму і мінімуму цільової функції графоаналітичним методом
Значення індексного рядка невід'ємні, отже отримуємо оптимальне рішення:,; .
Відповідь: максимальний прибуток від реалізації виготовленої продукції, що дорівнює 160/3 од. забезпечує випуск тільки продукції другого типу в кількості 80/9 одиниць.
Завдання № 2
Дана задача нелінійного програмування. Знайти максимум і мінімум цільової функції графоаналітичним методом. Скласти функцію Лагранжа і показати, що в точках екстремуму виконуються достатні умови мінімуму (максимуму).
Оскільки остання цифра шифру дорівнює 8, то А = 2; В = 5.
Оскільки передостання цифра шифру дорівнює 1, то слід вибрати завдання № 1.
1) Накреслимо область, яку задає система нерівностей.
Ця область - трикутник АВС з координатами вершин: А (0; 2); В (4; 6) і С (16/3; 14/3).
Рівні цільової функції є окружності з центром в точці (2; 5). Квадрати радіусів будуть значеннями цільової функції. Тоді по малюнку видно, що мінімальне значення цільової функції досягається в точці Н, максимальне - або в точці А, або в точці С.
Значення цільової функції в точці А:;
Значення цільової функції в точці С:;
Значить, найбільше значення функції досягається в точці А (0; 2) і дорівнює 13.
Знайдемо координати точки М.
Для цього розглянемо систему:
Пряма є дотичною до кола, якщо рівняння має єдине рішення. Квадратне рівняння має єдине рішення, якщо дискримінант дорівнює 0.
тоді; ; - мінімальне значення функції.
2) Складемо функцію Лагранжа для знаходження мінімального рішення:
Достатні умови екстремуму:
Система має рішення при, тобто достатні умови екстремуму виконуються.
Складемо функцію Лагранжа для знаходження максимального рішення:
Достатні умови екстремуму:
Система також має рішення, тобто достатні умови екстремуму виконуються.
Відповідь: мінімум цільової функції досягається при; ; максимум цільової функції досягається при; .
Завдання № 3
Двом підприємствам виділяються кошти в кількості d одиниць. При виділенні першому підприємству на рік x одиниць засобів воно забезпечує дохід k1x одиниць, а при виділенні другого підприємству y одиниць засобів, воно забезпечує дохід k1y одиниць. Залишок коштів на кінець року для першого підприємства дорівнює nx. а для другого my. Як розподілити всі кошти протягом 4-х років, щоб загальний дохід був найбільшим? Завдання вирішити методом динамічного програмування.
Весь період тривалістю 4 роки розбиваємо на 4 етапи, кожен з яких дорівнює одному року. Пронумеруємо етапи починаючи з першого року. Нехай Хk і Yk - кошти, виділені відповідно підприємствам А і В на k - тому етапі. Тоді сума Хk + Yk = аk є загальною кількістю коштів, що використовуються на k - тому етапі і що залишилися від попереднього етапу k - 1. на першому етапі використовуються всі виділені кошти і а1 = 2200 од. дохід, який буде отриманий на k - тому етапі, при виділенні Хk і Yk одиниць складе 6Хk + 1Yk. нехай максимальний дохід, отриманий на останніх етапах починаючи з k - того етапу становить fk (аk) од. запишемо функціональне рівняння Беллмана, що виражає принцип оптимальності: яке б не було початковий стан і початкове рішення наступне рішення повинно бути оптимальним по відношенню до стану, що отримується в результаті початкового стану:
Для кожного етапу потрібно вибрати значення Хk. а значення Yk = аk- хk. З урахуванням цього знайдемо дохід на k - тому етапі:
Функціональне рівняння Беллмана матиме вигляд:
Розглянемо всі етапи, починаючи з останнього.
(Тому що максимум лінійної функції досягається в кінці відрізка [0; а4] при х4 = а4);
(Тому що максимум лінійної функції досягається в кінці відрізка [0; а3] при х3 = а3)
(Тому що максимум лінійної функції досягається в кінці відрізка [0; А2] при х2 = А2)
(Тому що максимум лінійної функції досягається в кінці відрізка [0; а1] при х1 = а1). y1 = а1 - х1 = 0.
Таким чином, максимальний дохід за 4-е року складе
Відповідь: кошти буде вкладено тільки в підприємство А сумарний дохід за 4 роки складе 16473,6 од.
Завдання № 4
Визначити - оптимальний параметричний ряд виробів для задоволення заданого попиту, а саме число типів виробів N, значення параметрів (k = 1,2, ..., 5) виробів, при яких сумарні витрати мінімальні, безліч видів виробів, що обслуговуються виробом кожного обраного K-го типу -, кількість виробів кожного виду, необхідних для задоволення попиту і мінімальні витрати на вироби кожного K-го виду:
Побудувати повне дерево рішень, і показати які його гілки відсікаються при використанні методу гілок і меж, і як наслідок скорочується обсяг обчислень в порівнянні з методом повного