Рішення оптимізаційних задач управління методом лінійного програмування
Раніше я описав, як приймати рішення з урахуванням обмежуючих факторів . Мета таких рішень - визначити асортимент продукції (виробничий план), максимально збільшує прибуток компанії. Рішення полягало в тому, щоб розподілити ресурси між продуктами згідно маржинальної прибутку, отриманої на одиницю обмежених ресурсів, при дотриманні будь-яких інших обмежень, таких як максимальний або мінімальний попит на окремі види продукції. [1]
Якщо обмежуючий фактор один (наприклад, дефіцитний верстат), рішення може бути знайдено з застосуванням простих формул (див. Посилання на початку статті). Якщо ж обмежуючих факторів кілька, застосовується метод лінійного програмування.
Лінійне програмування - це назва, дана комбінації інструментів використовуваних в науці про управління. Цей метод вирішує проблему розподілу обмежених ресурсів між конкуруючими видами діяльності з тим, щоб максимізувати або мінімізувати деякі чисельні величини, такі як маржинальний прибуток або витрати. У бізнесі він може використовуватися в таких областях як планування виробництва для максимального збільшення прибутку, підбір комплектуючих для мінімізації витрат, вибір портфеля інвестицій для максимізації прибутковості, оптимізація перевезень товарів з метою скорочення відстаней, розподіл персоналу з метою максимально збільшити ефективність роботи і складання графіка робіт в цілях економії часу.
Завантажити замітку в форматі Word , Малюнки в форматі Excel
Лінійне програмування передбачає побудову математичної моделі даної задачі. Після чого рішення може бути знайдено графічно (розглянуто нижче), з використанням Excel (буде розглянуто окремо) або спеціалізованих комп'ютерних програм. [2]
Мабуть, побудова математичної моделі - найбільш складна частина лінійного програмування, що вимагає перекладу даної задачі в систему змінних величин, рівнянь і нерівностей - процес, в кінцевому підсумку залежить від навичок, досвіду, здібностей і інтуїції укладача моделі.
Розглянемо приклад побудови математичної моделі лінійного програмування
Микола Кузнєцов управляє невеликою механічним заводом. Наступного місяця він планує виготовляти два продукти (А і В), за якими питома маржинальний прибуток оцінюється в 2500 і 3500 руб., Відповідно.
Виготовлення обох продуктів вимагає витрат на машинну обробку, сировину і праця (рис. 1). На виготовлення кожної одиниці продукту А відводиться 3 години машинної обробки, 16 одиниць сировини і 6 одиниць праці. Відповідні вимоги до одиниці продукту В складають 10, 4 і 6. Микола прогнозує, що в наступному місяці він може надати 330 годин машинної обробки, 400 одиниць сировини і 240 одиниць праці. Технологія виробничого процесу така, що не менше 12 одиниць продукту В необхідно виготовляти в кожен конкретний місяць.
Мал. 1. Використання і надання ресурсів
Микола хоче побудувати модель з тим, щоб визначити кількість одиниць продуктів А і В, які він повідомлений виробляти в наступному місяці для максимізації маржинального прибутку.
Лінійна модель може бути побудована в чотири етапи.
Етап 1. Визначення змінних
Існує цільова змінна (позначимо її Z), яку необхідно оптимізувати, тобто максимізувати або мінімізувати (наприклад, прибуток, виручка або витрати). Микола прагне максимізувати маржинальний прибуток, отже, цільова змінна:
Z = сумарна маржинальний прибуток (в рублях), отримана в наступному місяці в результаті виробництва продуктів А і В.
Існує ряд невідомих шуканих змінних (позначимо їх х1, х2, х3 та ін.), Чиї значення необхідно визначити для отримання оптимальної величини цільової функції, яка, в нашому випадку є сумарною маржинальної прибутком. Ця маржинальний прибуток залежить від кількості вироблених продуктів А і В. Значення цих величин необхідно розрахувати, і тому вони представляють собою шукані змінні в моделі. Отже, позначимо:
х1 = кількість одиниць продукту А, вироблених в наступному місяці.
х2 = кількість одиниць продукту В, вироблених в наступному місяці.
Дуже важливо чітко визначити всі змінні величини; особливу увагу приділіть одиницях виміру і періоду часу, до якого відносяться змінні.
Етап. 2. Побудова цільової функції
Цільова функція - це лінійне рівняння, яке повинно бути або максимізувало або мінімізовано. Воно містить цільову змінну, виражену за допомогою шуканих змінних, тобто Z виражену через х1, х2 ... у вигляді лінійного рівняння.
У нашому прикладі кожен виготовлений продукт А приносить 2500 руб. маржинальної прибутку, а при виготовленні х1 одиниць продукту А, маржинальний прибуток складе 2500 * х1. Аналогічно маржинальний прибуток від виготовлення х2 одиниць продукту В складе 3500 * х2. Таким чином, сумарна маржинальний прибуток, отриманий в наступному місяці за рахунок виробництва х1 одиниць продукту А і х2 одиниць продукту В, тобто, цільова змінна Z складе:
Z = 2500 * х1 + 3500 * х2
Микола прагне максимізувати цей показник. Таким чином, цільова функція в нашій моделі:
Максимізувати Z = 2500 * х1 + 3500 * х2
Етап. 3. Визначення обмежень
Обмеження - це система лінійних рівнянь і / або нерівностей, які обмежують величини шуканих змінних. Вони математично відображають доступність ресурсів, технологічні чинники, умови маркетингу і інші вимоги. Обмеження можуть бути трьох видів: «менше або дорівнює», «більше або дорівнює», «строго одно».
У нашому прикладі для виробництва продуктів А і В необхідно час машинної обробки, сировину і праця, і доступність цих ресурсів обмежена. Обсяги виробництва цих двох продуктів (тобто значення х1 іх2) будуть, таким чином, обмежені тим, що кількість ресурсів, необхідних у виробничому процесі, не може перевищувати наявне. Розглянемо ситуацію з часом машинної обробки. Виготовлення кожної одиниці продукту А вимагає трьох годин машинної обробки, і якщо виготовлено х1, одиниць, то буде витрачено З * х1, годин цього ресурсу. Виготовлення кожної одиниці продукту В вимагає 10 годин і, отже, якщо вироблено х2 продуктів, то буде потрібно 10 * х2 годин. Таким чином, загальний обсяг машинного часу, необхідного для виробництва х1 одиниць продукту А і х2 одиниць продукту В, становить 3 * х1 + 10 * х2. Це загальне значення машинного часу не може перевищувати 330 годин. Математично це записується в такий спосіб:
3 * х1 + 10 * х2 ≤ 330
Аналогічні міркування застосовуються до сировини і праці, що дозволяє записати ще два обмеження:
16 * х1 + 4 * х2 ≤ 400
6 * х1 + 6 * х2 ≤ 240
Нарешті слід зазначити, що існує умова, згідно з яким має бути виготовлено не менше 12 одиниць продукту В:
х2 ≥ 12
Етап 4. Запис умов невід'ємності
Шукані змінні не можуть бути негативними числами, що необхідно записати у вигляді нерівностей х1 ≥ 0 і х2 ≥ 0. У нашому прикладі Другою умовою є надлишковим, так як вище було визначено, що х2 не може бути менше 12.
Повна модель лінійного програмування для виробничої завдання Миколи може бути записана у вигляді:
Максимізувати: Z = 2500 * х1 + 3500 * х2
За умови, що: 3 * х1 + 10 * х2 ≤ 330
16 * х1 + 4 * х2 ≤ 400
6 * х1 + 6 * х2 ≤ 240
х2 ≥ 12
х1 ≥ 0
Розглянемо графічний метод розв'язання задачі лінійного програмування.
Цей метод підходить тільки для задач з двома шуканими змінними. Модель, побудована вище, буде використана для демонстрації методу.
Осі на графіку є дві шукані змінні (рис. 2). Не має значення, яку змінну відкласти уздовж, який осі. Важливо вибрати масштаб, який в кінцевому підсумку дозволить побудувати наочну діаграму. Оскільки обидві змінні повинні бути невід'ємними, малюється тільки I-й квадрант.
Мал. 2. Осі графіка лінійного програмування
Розглянемо, наприклад, перше обмеження: 3 * х1 + 10 * х2 ≤ 330. Це нерівність описує область, що лежить нижче прямої: 3 * х1 + 10 * х2 = 330. Ця пряма перетинає вісь х1 при значенні х2 = 0, тобто рівняння виглядає так: 3 * х1 + 10 * 0 = 330, а його рішення: х1 = 330/3 = 110
Аналогічно обчислюємо точки перетину з осями х1 і х2 для всіх умов-обмежень:
Область допустимих значень Кордон допустимих значень Перетин з віссю х1 Перетин з віссю х2 3 * х1 + 10 * х2 ≤ 330 3 * х1 + 10 * х2 = 330 х1 = 110; х2 = 0 х1 = 0; х2 = 33 16 * х1 + 4 * х2 ≤ 400 16 * х1 + 4 * х2 = 400 х1 = 25; х2 = 0 х1 = 0; х2 = 100 6 * х1 + 6 * х2 ≤ 240 6 * х1 + 6 * х2 = 240 х1 = 40; х2 = 0 х1 = 0; х2 = 40 х2 ≥ 12 х 2 = 12 не перетинає; йде паралельно осі х1 х1 = 0; х2 = 12
Графічно перше обмеження відображено на рис. 3.
Мал. 3. Побудова області допустимих рішень для першого обмеження
Будь-яка точка в межах виділеного трикутника або на його кордонах слід пов'язати з цим обмеження. Такі точки називаються припустимими, а точки за межами трикутника називаються неприпустимими.
Аналогічно відображаємо на графіку інші обмеження (рис. 4). Значення х1 і х2 на або всередині заштрихованої області ABCDE будуть відповідати всім обмеженням моделі. Така область називається областю допустимих рішень.
Мал. 4. Область допустимих рішень для моделі в цілому
Тепер в області допустимих рішень необхідно визначити значення х1 і х2, які максимізують Z. Для цього в рівнянні цільової функції:
Z = 2500 * х1 + 3500 * х2
розділимо (або помножимо) коефіцієнти перед х1 і х2 на одне і теж число, так щоб отримані значення потрапили в діапазон, який відображається на графіку; в нашому випадку такий діапазон - від 0 до 120; тому коефіцієнти можна розділити на 100 (або 50):
Z = 25х1 + 35х2
потім призначимо Z значення дорівнює добутку коефіцієнтів перед х1 і х2 (25 * 35 = 875):
875 = 25х1 + 35х2
і, нарешті, знайдемо точки перетину прямої з осями х1 і х2:
Рівняння цільової функції Перетин з віссю х1 Перетин з віссю х2 875 = 25х1 + 35х2 х1 = 35; х2 = 0 х1 = 0; х2 = 25
Нанесемо це цільове рівняння на графік аналогічно обмеженням (рис. 5):
Мал. 5. Нанесення цільової функції (чорна пунктирна лінія) на область допустимих рішень
Значення Z постійно на всьому протязі лінії цільової функції. Щоб знайти значення х1 і х2, які максимізують Z, потрібно паралельно переносити лінію цільової функції до такої точки в межах області допустимих рішень, яка розташована на максимальному видаленні від вихідної лінії цільової функції вгору і вправо, тобто до точки С (рис. 6) .
Мал. 6. Лінія цільової функції досягла максимуму в межах області допустимих рішень (в точці С)
Можна зробити висновок, що оптимальне рішення буде знаходитися в одній з крайніх точок області прийняття рішення. В який саме, буде залежати від кута нахилу цільової функції і від того, яке завдання ми вирішуємо: максимізації або мінімізації. Таким чином, не обов'язково креслити цільову функцію - все, що необхідно, це визначити значення х1 і х2 в кожної з крайніх точок шляхом зчитування з діаграми або шляхом вирішення відповідної пари рівнянь. Знайдені значення х1 і х2 потім підставляються в цільову функцію для розрахунку відповідної величини Z. Оптимальним рішенням є те, при якому отримана максимальна величина Z при вирішенні завдання максимізації, і мінімальна - при вирішенні задачі мінімізації.
Визначимо, наприклад значення х1 і х2 в точці С. Зауважимо, що точка С знаходиться на перетині ліній: 3х1 + 10х2 = 330 і 6х1 + 6х2 = 240. Рішення цієї системи рівнянь дає: х1 = 10, х2 = 30. Результати розрахунку для всіх вершин області припустимих рішень наведені в таблиці:
Точка Значення х1 Значення х2 Z = 2500х1 + 3500х2 А 22 12 97 000 В 20 20 120 000 З 10 30 130 000 D 0 33 115 500 E 0 12 42 000
Таким чином, Микола Ковалем повинен запланувати на наступний місяць виробництво 10 виробів А і 30 виробів В, що дозволить йому отримати маржинальний прибуток в розмірі 130 тис. Руб.
Коротко суть графічного методу розв'язання задач лінійного програмування можна викласти наступним чином:
- Накресліть на графіку дві осі, що представляють собою два параметра рішення; намалюйте тільки I-й квадрант.
- Визначте координати точок перетину всіх граничних умов з осями, підставляючи в рівняння граничних умов по черзі значення х1 = 0 і х2 = 0.
- Нанести лінії обмежень моделі на графік.
- Визначте на графіку область (звану допустимої областю прийняття рішення), яка відповідає всім обмеженням. Якщо така область відсутня, значить, модель не має рішення.
- Визначте значення шуканих змінних в крайніх точках області прийняття рішення, і в кожному випадку розрахуйте відповідне значення цільової змінної Z.
- Для задач максимізації рішення - точка, в якій Z максимально, для задач мінімізації, рішення - точка, в якій Z мінімально.
[1] Ця замітка написана за матеріалами CIMA .
[2] Див., Наприклад, тут .
