3.1: Додатки для максимізації
- Page ID
- 67227
У цьому розділі ви навчитеся:
- Розпізнати типову форму задачі лінійного програмування
- Сформулювати задачі лінійного програмування максимізації
- Регіони доцільності графіків для задач лінійного програмування максимізації
- Визначити оптимальні рішення для максимізації задач лінійного програмування.
Проблеми застосування в бізнесі, економіці, соціальних та біологічних науках часто просять нас приймати рішення на основі певних умов. Умови або обмеження часто набувають форми нерівностей. У цьому розділі ми почнемо формулювати, аналізувати і вирішувати подібні завдання, на простому рівні, щоб зрозуміти безліч складових такої проблеми.
Типова задача лінійного програмування полягає у знаходженні екстремального значення лінійної функції з урахуванням певних обмежень. Ми або намагаємося максимізувати або мінімізувати значення цієї лінійної функції, наприклад, максимізувати прибуток або дохід, або мінімізувати витрати. Ось чому ці проблеми лінійного програмування класифікуються як проблеми максимізації або мінімізації, або просто проблеми оптимізації. Функція, яку ми намагаємося оптимізувати, називається об'єктивною функцією, а умови, які повинні бути виконані, називаються обмеженнями.
Типовим прикладом є максимізація прибутку від виробництва декількох продуктів, з урахуванням обмежень на матеріали або ресурси, необхідні для виробництва цих предметів; проблема вимагає від нас визначення кількості кожного виробленого товару. Інший тип проблеми включає планування; нам потрібно визначити, скільки часу приділяти кожному з декількох видів діяльності, щоб максимізувати дохід від (або мінімізувати вартість) цих видів діяльності, за умови обмеження часу та інших ресурсів, доступних для кожної діяльності.
У цьому розділі ми будемо працювати з проблемами, які задіяні тільки дві змінні, а отже, можуть бути вирішені графіком. У наступному розділі ми вивчимо алгоритм чисельного пошуку рішення. Це надасть нам інструмент для вирішення проблем з більш ніж двома змінними. У той час, маючи трохи більше знань про лінійне програмування, ми також вивчимо багато способів використання цих методів в бізнесі та широкому спектрі інших галузей.
Починаємо з вирішення проблеми максимізації.
Нікі має дві роботи за сумісництвом, роботу I та роботу II. Вона ніколи не хоче працювати більше, ніж загалом 12 годин на тиждень. Вона визначила, що на кожну годину, яку вона працює в Іові І, їй потрібно 2 години часу на підготовку, а на кожну годину, яку вона працює на Іові, їй потрібна одна година часу на підготовку, і вона не може витратити більше 16 годин на підготовку.
Якщо Ніккі заробляє 40 доларів на годину на роботі I, і 30 доларів на годину на роботі II, скільки годин вона повинна працювати на тиждень на кожній роботі, щоб максимізувати свій дохід?
Рішення
Ми починаємо з вибору наших змінних.
- Нехай\(x\) = Кількість годин на тиждень Нікі працюватиме на роботі I.
- Нехай\(y\) = Кількість годин на тиждень Нікі буде працювати на Job II.
Тепер пишемо об'єктивну функцію. Оскільки Нікі отримує 40 доларів на годину на роботі I та 30 доларів на годину на роботі II, її загальний дохід I дається наступним рівнянням.
\[I = 40x + 30y \nonumber \]
Наше наступне завдання - знайти обмеження. Друге речення в проблемі говорить: «Вона ніколи не хоче працювати більше, ніж загалом 12 годин на тиждень». Це означає наступне обмеження:
\[x + y \leq 12 \nonumber \]
Третє речення говорить: «На кожну годину, яку вона працює в Іові I, їй потрібно 2 години часу на підготовку, і на кожну годину, яку вона працює в Іові II, їй потрібна одна година часу на підготовку, і вона не може витратити більше 16 годин на підготовку». Наступний переклад.
\[2x + y \leq 16 \nonumber \]
Той факт, що\(x\) і ніколи не\(y\) може бути негативним, представлений наступними двома обмеженнями:
\[x \geq 0 \text{, and } y \geq 0 \nonumber. \nonumber \]
Ну, хороша новина! Ми сформулювали проблему. Ми повторюємо його як
\ begin {масив} {ll}
\ textbf {Максимізувати} &\ математика {I} =40\ математика {x} +30\ mathrm {y}\
\ textbf {За умови:} &\ mathrm {x} +\ mathrm {y}\ leq 12\\
& 2\ mathrm {x} +\ mathrm {y}\ leq 16\\
&\ математика {x}\ geq 0;\ mathrm {y}\ geq 0
\ кінець {масив}
Для того, щоб вирішити задачу, ми графуємо обмеження і затінюємо область, яка задовольняє всі обмеження нерівності.
Будь-який відповідний метод може бути використаний для побудови графіків ліній для обмежень. Однак часто найпростішим методом є графік лінії шляхом побудови графіка x-перехоплення і y-перехоплення.
Лінія для обмеження розділить площину на дві області, одна з яких задовольняє нерівності частини обмеження. Тестова точка використовується для визначення того, яку частину площини затінювати, щоб задовольнити нерівність. Будь-яка точка на площині, яка не знаходиться на лінії, може бути використана як контрольна точка.
- Якщо контрольна точка задовольняє нерівність, то область площини, яка задовольняє нерівність, - це область, яка містить контрольну точку.
- Якщо контрольна точка не задовольняє нерівності, то область, яка задовольняє нерівність, лежить на протилежному боці прямої від контрольної точки.
На графіку нижче, після того, як лінії, що представляють обмеження, були побудовані за допомогою відповідного методу з глави 1, точка (0,0) була використана як контрольна точка, щоб визначити, що
- (0,0) задовольняє обмеженню,\(x + y \leq 12\) оскільки\(0 + 0 < 12\)
- (0,0) задовольняє обмеженню,\(2x + y \leq 16\) оскільки\(2(0) + 0 < 16\)
Тому в цьому прикладі ми затінюємо область, яка знаходиться нижче і ліворуч від обох ліній обмеження, але також над віссю x і праворуч від осі y, щоб додатково задовольнити обмеження\(x \geq 0\) і\(y \geq 0\).
Затінена область, де виконуються всі умови, називається регіоном доцільності або полігоном доцільності.
Фундаментальна теорема лінійного програмування стверджує, що максимальне (або мінімальне) значення цільової функції завжди має місце у вершині області доцільності.
Тому ми виділимо всі вершини (кутові точки) області техніко-економічного обґрунтування. Ми називаємо ці точки критичними точками. Вони перераховані як (0, 0), (0, 12), (4, 8), (8, 0). Щоб максимізувати дохід Нікі, ми підставимо ці пункти в об'єктивну функцію, щоб побачити, яка точка дає нам найвищий дохід на тиждень. Ми перерахуємо результати нижче.
| Критичні точки | Дохід |
|---|---|
| (0, 0) | 40 (0) + 30 (0) = 0 |
| (0, 12) | 40 (0) + 30 (12) = 360 доларів |
| (4, 8) | 40 (4) + 30 (8) = 400 доларів |
| (8, 0) | 40 (8) + 30 (0) = 320 доларів |
Ясно, що точка (4, 8) дає найбільший прибуток: 400 доларів.
Тому ми робимо висновок, що Нікі повинен працювати 4 години на Іові і 8 годин на роботі II.
Фабрика випускає два види гаджетів, звичайні і преміальні. Кожен гаджет вимагає використання двох операцій, складання та оздоблення, а для кожної операції є не більше 12 годин. Звичайний гаджет вимагає 1 години збірки і 2 години обробки, в той час як преміум-гаджету потрібно 2 години збірки і 1 година обробки. Через інші обмеження компанія може робити не більше 7 гаджетів в день. Якщо за кожен звичайний гаджет реалізується прибуток в розмірі 20 доларів і 30 доларів за преміальний гаджет, скільки з кожного потрібно виготовити, щоб отримати максимальний прибуток?
Рішення
Вибираємо наші змінні.
- Нехай\(x\) = Кількість звичайних гаджетів, що випускаються щодня.
- and\(y\) = Кількість преміальних гаджетів, що випускаються щодня.
Об'єктивною функцією є
\[P = 20x + 30y \nonumber \]
Тепер пишемо обмеження. Четверте речення говорить про те, що компанія може робити не більше 7 гаджетів в день. Це перекладається як
\[x + y \leq 7 \nonumber \]
Так як штатний гаджет вимагає однієї години збірки, а преміум гаджет вимагає двох годин збірки, а для цієї операції є максимум 12 годин, отримуємо
\[x + 2y \leq 12 \nonumber \]
Аналогічно, звичайний гаджет вимагає двох годин обробки, а преміум гаджет - одну годину. Знову ж таки, є максимум 12 годин, доступних для обробки. Це дає нам наступне обмеження.
\[2x + y \leq 12 \nonumber \]
Той факт, що\(x\) і ніколи не\(y\) може бути негативним, представлений наступними двома обмеженнями:
\[x \geq 0 \text{, and } y \geq 0 \nonumber. \nonumber \]
Ми сформулювали проблему наступним чином:
\ [\ begin {масив} {ll}
\ textbf {Максимізувати} &\ математика {P} =20\ математика {x} +30\ mathrm {y}
\\ textbf {За умови:} &\ mathrm {x} +\ mathrm {y}\ leq 7\\
&\ mathrm {x} +2\ mathrm {y}\ q 12\\
& 2\ матрм {x} +\ матрм {y}\ до 12\\
&\ математика {x}\ geq 0;\ mathrm {y}\ geq 0
\ кінець {масив}\ номер\]
Для того, щоб вирішити проблему, ми далі графуємо обмеження та область техніко-економічного обґрунтування.
Знову ж таки, ми затінювали область техніко-економічного обґрунтування, де всі обмеження задовольняються.
Оскільки крайнє значення цільової функції завжди має місце в вершині області техніко-економічного обґрунтування, ми виділяємо всі критичні точки. Вони перераховані як (0, 0), (0, 6), (2, 5), (5, 2) і (6, 0). Щоб максимізувати прибуток, ми підставимо ці точки в об'єктивну функцію, щоб побачити, яка точка дає нам максимальний прибуток щодня. Результати наведені нижче.
| Критична точка | Дохід |
|---|---|
| (0, 0) | 20 (0) + 30 (0) = 0 |
(0, 6) |
20 (0) + 30 (6) = 180 доларів |
(2, 5) |
20 (2) + 30 (5) = 190 доларів |
(5, 2) |
20 (5) + 30 (2) = 160 доларів |
| (6,0) | 20 (6) + 30 (0) = 120 доларів |
Точка (2, 5) дає найбільший прибуток, а той прибуток становить 190 доларів.
Тому робимо висновок, що ми повинні виробляти 2 звичайних гаджета і 5 преміальних гаджетів щодня, щоб отримати максимальний прибуток в 190 доларів.
Поки що ми зосередилися на «стандартних проблемах максимізації», в яких
- Мета функції полягає в тому, щоб бути максимальним
- Всі обмеження мають форму\(ax + by \leq c\)
- Всі змінні обмежені невід'ємним (\(x ≥ 0\),\(y ≥ 0\))
Далі ми розглянемо приклад, де це не так. Наша наступна проблема, як кажуть, має «змішані обмеження», оскільки деякі обмеження нерівності мають форму,\(ax + by ≤ c\) а деякі - форми\(ax + by ≥ c\). Ненегативні обмеження все ще є важливою вимогою в будь-якій лінійній програмі.
Вирішіть наступну проблему максимізації графічно.
\ [\ begin {масив} {ll}
\ textbf {Максимізувати} &\ mathrm {P} =10\ mathrm {x} +15
\ mathrm {y}\\ textbf {За умови:} &\ mathrm {x} +\ mathrm {y}\ geq 1\\
&\ mathrm {x} 6\\
& 2\ матрм {x} +\ mathrm {y}\ leq 6\\
&\ математика {x}\ geq 0;\ mathrm {y}\ geq 0
\ кінець {масив}\ номер\]
Рішення
Графік наведено нижче.
П'ять критичних точок перераховані на наведеному вище малюнку. Читач повинен зауважити, що перше обмеження\(x + y ≥ 1\) вимагає, щоб область доцільності була обмежена нижче лінією\(x + y =1\); контрольна точка (0,0) не задовольняє\(x + y ≥ 1\), тому ми затінюємо область на протилежній стороні лінії від тестової точки (0,0).
| Критична точка | Дохід |
|---|---|
| (1, 0) | 10 (1) + 15 (0) = $10 |
| (3, 0) | 10 (3) + 15 (0) = $30 |
| (2, 2) | 10 (2) + 15 (2) = 50 доларів |
| (0, 3) | 10 (0) + 15 (3) = 45 доларів |
| (0,1) | 10 (0) + 15 (1) = $15 |
Зрозуміло, що точка (2, 2) максимізує цільову функцію до максимального значення 50.
Важливо зауважити, що якщо точка (0,0) лежить на лінії для обмеження, то (0,0) не може бути використана як контрольна точка. Нам потрібно буде вибрати будь-яку іншу точку, яку ми хочемо, яка не лежить на лінії, щоб використовувати як контрольну точку в цій ситуації.
Нарешті, ми вирішимо важливе питання. Чи можна визначити точку, яка дає максимальне значення без обчислення значення в кожній критичній точці?
Відповідь - так.
Наприклад\(\PageIndex{2}\), ми підставили точки (0, 0), (0, 6), (2, 5), (5, 2) і (6, 0), і (6\(P = 20x + 30y\), 0), і отримали значення $0, $180, $190, $160, $120 відповідно.
Іноді це не найефективніший спосіб пошуку оптимального рішення. Замість цього ми могли б знайти оптимальне значення, також графікуючи цільову функцію.
Щоб визначити найбільшу\(P\), графуємо\(P = 20x + 30y\) для будь-якого\(P\) значення на наш вибір. Скажімо, вибираємо\(P = 60\). Графуємо\(20x + 30y = 60\).
Тепер рухаємо лінію паралельно собі, тобто зберігаючи однаковий ухил в усі часи. Так як ми рухаємо лінію паралельно собі, нахил тримаємо колишнім, і єдине, що змінюється - це П. У міру відходу від початку значення Р збільшується. Найбільша можлива величина Р реалізується при дотику лінії до останньої кутової точки області техніко-економічного обґрунтування.
На малюнку нижче показані рухи лінії, а оптимальне рішення досягається в точці (2, 5). У задачах максимізації, коли лінія відсувається від початку, ця оптимальна точка є найвіддаленішою критичною точкою.
Підсумовуємо:
Задачі лінійного програмування максимізації
- Напишіть об'єктивну функцію.
- Напишіть обмеження.
- Для стандартних задач лінійного програмування максимізації обмеження мають вигляд:\(ax + by ≤ c\)
- Оскільки змінні невід'ємні, включаємо обмеження:\(x ≥ 0\);\(y ≥ 0\).
- Графік обмежень.
- Затіньте область доцільності.
- Знайдіть кутові точки.
- Визначте кутову точку, яка дає максимальне значення.
- Це робиться шляхом знаходження значення цільової функції в кожній кутовій точці.
- Це також можна зробити, перемістивши лінію, пов'язану з цільовою функцією.