Лінійне програмування в Excel

Оптимізаційні моделі використовуються, щоб знайти відповіді на запитання на кшталт:

• як скласти розклад для співробітників колл-центру, щоб воно відповідало їх відпускними запитам, збалансував переробки і виключало цілодобові чергування?
• які можливості буріння нафтових свердловин використовувати для отримання максимального доходу, тримаючи при цьому під контролем всі ризики?
• коли слід робити нові замовлення в Китаї і як їх доставляти, щоб мінімізувати вартість і відповідати очікуваному попиту?

Мал. 1. Бюджетне обмеження робить область допустимих значень трикутної

Завантажити замітку в форматі Word або pdf , Приклади в форматі Excel

Метою оптимізації завжди є «максимізація» або «мінімізація». Найпоширеніша і зрозуміла форма математичної оптимізації - це лінійне програмування, секретна розробка радянських інженерів кінця 1930-х років, що стала популярною в ході Другої світової війни. До речі, слово «програмування» в даному словосполученні є пережитком військової термінології того часу і не має нічого спільного з комп'ютерним програмуванням. [1]

Почнемо з улюбленого прикладу економістів - гармат і масла. Йде 1941-й рік, ви - господар французької молочної ферми. Днем ви доїте корів і робите вершкове масло, вночі - збираєте автомати. Ваша мета - максимальний прибуток, щоб якомога довше виробляти автомати. Від посередника з Опору ви отримуєте за кожен автомат по 195 грошових одиниць (щоб не напружувати Excel неіснуючими франками, припустимо, що це долари). За кожну бочку олії на ринку вам платять по $ 150.

Умови та обмеження. Собівартість однієї бочки масла - $ 100, а одного автомата - $ 150. Місячний бюджет на виробництво - $ 1800. Ви зберігаєте продукцію в 21-кубометровом підвалі. Автомат займає ½ м3, бочка масла 1½ м3. Скільки автоматів і бочок олії вам потрібно продати за місяць, щоб отримати максимальний прибуток?

Лінійна програма визначається як набір рішень, необхідний для оптимізації об'єкта в світлі деяких умов, де і об'єкт, і умови лінійні. Ви можете додавати, віднімати, множити на константи, але не можете застосовувати для вирішення нелінійні функції, наприклад, множення змінних (не можна автомати помножити на масло), зведення в квадрат або логічні цикли, такі як ЯКЩО.

Уявімо області допустимих значень графічно. По-перше, кількість гармат і бочок олії повинно бути невід'ємним. По-друге, максимально можна зробити $ 1800 / $ 150 = 12 автоматів або $ 1800 / $ 100 = 18 бочок олії (рис. 1). Загальна назва цього трикутника - політопа - фігура з плоскими сторонами (наприклад, діамант). По-третє, підвал може вмістити не більше 21 / (½) = 42 автоматів або 21 / (1½) = 14 бочок олії (рис. 2).

Мал. 2. Обмежений обсяг підвалу відрізає шматок області допустимих значень

Щоб знайти ідеальне співвідношення автоматів і бочок введемо в задачу поняття лінії рівня функції. Така лінія в оптимізаційної моделі включає значення, що приносять однаковий прибуток. Лінію рівня можна задати рівнянням:

(195 - 150) * Nавтоматов + (150 - 100) * Nбочек масла = С,

де С - константа.

Наприклад, при С = 450, лінія буде проходити через координати (0; 10) і (9; 0). Графічно ідея максимізації прибутку реалізується переміщенням лінії рівня паралельно самій собі в напрямку збільшення значень по осях Х і Y (рис. 3). Цікаво, що для політопа оптимум завжди лежить в одній з вершин (або єдиного рішення не існує зовсім). На цій властивості заснований алгоритм симплексного методу. Рішення завдання в Excel починають зі створення області моделі (рис. 4). Формула цільової функції в комірці В1 = СУММПРОИЗВ (C4: D4; C10: D10).

Мал. 3. Лінія рівня і функція для оптимізації прибутку: а) якесь довільне початкове положення; б) лінія рівня в оптимальному положенні

Мал. 4. Дані про автомати і маслі, поміщені в Excel

У вас все готово, щоб натиснути кнопку ДАНІ -> Пошук рішення. (Якщо ви не бачите цієї кнопки, встановіть надбудову Пошук рішення; см. Джон Форман. Багато цифр: Аналіз великих даних за допомогою Excel , Глава 1). У вікні Параметри пошуку рішення задайте виділені опції і натисніть Знайти рішення.

Мал. 5. Вікно Пошук рішення

Excel оновить лист і внесе на нього результати розрахунку (рис. 6).

Мал. 6. Оптимізована таблиця автоматів і бочок олії

Що станеться, якщо додати нелінійність? Припустимо ваш посередник пропонує $ 500, якщо число автоматів в місяць буде більш 5. Просто додайте функцію ЯКЩО в клітинку з прибутком (В1). Тепер цільова функція виглядає так: = СУММПРОИЗВ (C4: D4; C10: D10) + ЯКЩО (C4> 5; 500; 0). Тиснемо Пошук рішення. Невдача, Excel повідомляє про помилку - умови лінійності не виконані (рис. 7).

Мал. 7. Excel не дає вам використовувати логічні оператори в лінійному алгоритмі

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

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

На жаль, з еволюційним алгоритмом все ж виникають деякі проблеми:

• Час роботи істотно більше, ніж при симплекс-методі
• Немає ніякої гарантії, що він знайде оптимальне рішення. Все, що в його силах - це контроль кращого рішення в популяції, поки не закінчиться час, або популяція не зміниться в достатній мірі для продовження, або ви примусово не зупините «Пошук рішення» натисканням кнопки ESC.
• Еволюційний пошук рішення працює досить повільно. А якщо області допустимих значень складні, він часто лається, не знайшовши навіть місця, з якого почати.
• Якщо ви хочете змусити еволюційний алгоритм добре працювати в Excel, вам доведеться визначити жорсткі межі для кожної змінної рішення. Навіть якщо ваше рішення більш-менш необмежену, вам все ж потрібні обмеження.

Беручи до уваги останній пункт, для вирішення завдання з автоматами і маслом вам потрібно додати обмеження, згідно з яким обидва рішення не повинні бути більше 25 (рис. 8). Встановивши основні параметри моделі, клікніть на кнопку Параметри. Пропрацювавши близько хвилини, еволюційний алгоритм видав очікуване рішення - 6 автоматів і 9 бочок олії. Оскільки без бонусу оптимально зробити лише три автомати, а бонус виплачується при виробництві більш 5 автоматів, очевидно, що оптимальним буде вибір 6 автоматів.

Мал. 8. Налаштування еволюційного «Пошуку рішення»

Розглянемо тепер більш складний приклад. Ви працюєте в компанії, яка виробляє апельсиновий сік, змішуючи натуральні соки різних сортів (рис. 9). Щоб ваш сік відповідав найвишуканішим вимогам:

• ставлення за шкалою Брікс / кислотність має залишатися в межах 11,5-12,5;
• рівень кислотності повинен залишатися між 0,75-1%;
• рівень терпкого смаку повинен бути 4 або нижче;
• колір повинен перебувати в рамках 4,5-5,5.

Шеф повідомив вам, що на січень і лютий він очікує попиту на рівні 600 000 галонів соку в місяць, а в березні - 700 000 галонів. І ще, є договір зі штатом Флорида, що надає податкові пільги за умови, що компанія купує не менше 40% соку кожен місяць у фермерів, які вирощують сорт Valencia. Договір слід дотриматися.

Мал. 9. Список характеристик для виробництва свіжого апельсинового соку (щоб збільшити зображення, клікніть на ньому правою кнопкою миші, а потім Відкрити зображення в новій вкладці)

Створіть оптимизационную модель (рис. 10). Формули можна вивчити на відповідному аркуші, прикладеного Excel-файлу. Натисніть Пошук рішення, і введіть параметри (рис. 11). Натисніть Знайти рішення.

Мал. 10. Налаштовуємо таблицю змішування

Мал. 11. Заповнена вікно Пошук рішення для задачі змішування

Запустивши Пошук рішення, ви знаходите оптимальну вартість закупівель - $ 1,23 млн. (Рис. 12). Зверніть увагу, що замовлення флоридской Valencia проходить по нижній межі умови. Очевидно, ця угода - не найкращий варіант, але доводиться змиритися. Другий за популярністю сорт - це Verna з Мексики, яка страшенно дешева, але рівно настільки ж жахлива.

Мал. 12. Рішення оптимізаційної задачі по змішуванню апельсинового соку

Ви уявляєте результати розрахунку шефу, але він залишається незадоволений, і говорить про те, що не хоче виходити за бюджет $ 1,17 млн. Ви повертаєтеся до комп'ютера і починаєте розуміти, що вартість перестала бути цільовою функцією. Тепер ця умова! А яка мета? Ви можете знизити вартість закупівель тільки пом'якшивши вимоги до якості. Ви вирішуєте сформулювати їх у термінах процентного скорочення, і робите нову модель (рис. 13).

Мал. 13. Модель зі зниженим якістю

Зверніть увагу, що в осередках В26: 29 і F26: F29 тепер не константи, а формули. Ваша нова мета - мінімізація відсотка зниження якості в осередках G26: G29. Точніше, ви б хотіли мінімізувати максимальне з значень в осередках G26: G29. Однак, якщо в осередок D2 помістити формулу = МАКС (G26: G29), модель не буде працювати. Нагадую, функція МАКС не є лінійної. Тут доступна маленька хитрість - можна внести додаткову умову в модель: $ G $ 26: $ G $ 29 <= $ D $ 2 (рис. 14), а осередок D2 залишити порожній. Тобто, осередок D2 буде оптимізуватися не завдяки наявності в ній формули, а послідовними циклами, що запускаються цим додатковою умовою.

Мал. 14. Параметри Пошуку рішення в моделі зі зниженим якістю

Натисніть Знайти рішення. Симплексний алгоритм буде намагатися наблизити D2 до 0 як цільову функцію моделі, в той час як обмеження за смаком і кольором будуть намагатися збільшити її наскільки можливо, щоб отримати придатну для роботи суміш. Де ж зупиниться значення D2? Найменше з можливих значень - максимальний відсоток з чотирьох знижених в діапазоні G26: G29. Ми бачимо (рис. 15, осередки С26: Е29), що зниження витрат на 5% зажадало вийти за обмеження якості за всіма чотирма параметрами.

Мал. 15. Рішення оптимізаційної задачі з скороченням витрат на 5%

Ви представили дані шефу, який побачив, що скорочення витрат на 5% не варто зниження якості соку, тому він погодив ваш перший варіант. Але, коли ви принесли його в відділ постачання, співробітники обурилися. Як можна було так роздрібнити поставки !? Постачальники наполягають, щоб ви укрупнили партії: не більше 4 постачальників щомісяця! І ви сідаєте за нову модель. На жаль, використовувати функції ЯКЩО або РАХУНОК ви не можете, так як хочете залишитися в рамках лінійної моделі. Тому вам знову доводиться вдатися до хитрощів (рис. 16). Ви додаєте в модель область С33: Е43, яку визначаєте, як бінарну (значення в ній можуть бути тільки 0 або 1), і залишаєте її порожній. А також область F33: H43, де кожна клітинка дорівнює добутку значення з областей С33: Е43 на G5: G15. У параметри Пошук рішення (рис. 17) ви додаєте ще одну умову $ З $ 15: $ Е $ 15 <= $ F $ 33: $ H $ 43 і ще одну область змінних - $ C $ 33: $ E $ 43.

Як в цьому випадку буде працювати оптимізаційний алгоритм? Коли він стартує все значення в областях С5: Е15, С33: Е43 і F33: H43 дорівнюють нулю. Припустимо, що алгоритм намагається в клітинку С7 помістити значення 240. Чи спрацює умова С7 <= F35, яке призведе до збільшення значення в F35, яке, в свою чергу, визначається формулою F35 = C35 * $ G7. Оскільки G7 - константа, а С35 - бінарна змінна, останньої присвоюється значення 1. Умова С7 <= F35 виконано, тому що, 240 <= 1200. Таким чином ви моделюєте незручні умови «якщо ... то»: «якщо замовлення зроблено, то бінарна змінна включається ».

Мал. 16. Додавання індикаторів в модель

Мал. 17. Установка значень для умови «не більше 4 постачальників»

Натисніть Знайти рішення. Ви помітите, що рішення задачі вимагає більше часу з-за додавання бінарних змінних. Якщо з якоїсь причини Пошук рішення занадто затягнув свій пошук, ви завжди можете натиснути ESC і побачити найкраще з знайдених рішень на даний момент.

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

Інженери повідомили, що на виробництві з'явилися нові «сніжателі кислотності». Дана технологія здатна нейтралізувати 20% кислоти в соку, що протікає через прилад. Це не тільки знижує відсоток кислоти, але і підвищує індекс Брікс / кислотність на 25%. Але для «сніжателя» потрібна енергія і витратні матеріали вартістю $ 20 за 1000 галонів соку. Чи не весь сік, який надходить від постачальників, потрібно проганяти через цей процес, проте, якщо поставка по якомусь замовлення проганяється через ионообменник, то повинен бути оброблений весь її обсяг. Побудуйте модель за участю іонообмінника для зниження вартості.

Проблема з новим правилом полягає в тому, що природний спосіб його моделювання - нелінійний, що призведе до використання повільного алгоритму оптимізації. Але, як і в попередньому прикладі, можна ввести бінарну змінну в області С25: Е35, яка б «включалася» при необхідності знизити кислотність партії (рис. 18). Оскільки, не можна використовувати твір «індикатор зниження кислотності (бінарний) * обсяг партії», ви створюєте область С37: Е47, яка вам знадобляться для зрівнювання обсягів, що підлягають зниженню кислотності, без прямої участі в формулах самих цих обсягів. Отже, області С25: Е35 і С37: Е47 не містять формул. В області G25: I35 використовуються формули = С25: Е35 * G5: G15 (це обмеження партії загальним доступним об'ємом соку), а в області К25: М35 = Е5: E15-GG5: 15 * (1-Е25: E35). Ця умова запрацює тільки якщо партія підлягає зниженню кислотності.

Мал. 18. Область індикаторів в моделі зі «сніжателем кислотності»

Також в моделі зі «сніжателем кислотності» були змінені формули в осередках С16: Е16 (тепер вони враховують витрати на зниження кислотності за формулою «індикатор (бінарний) * обсяг партії * $ 20) і в осередках С50: Е51 (тепер вони враховують підвищення коефіцієнта Брікс / кислотність на 25% і зниження кислотності на 20% для оброблених партій). В параметрах Пошуку рішення з'явилися нові змінні і додаткові умова (рис. 19). На жаль, натиснувши кнопку Знайти рішення, ви дізнаєтеся, що надбудова Пошук рішення не може впоратися із завданням (рис. 20). Модель стали занадто складною.

Мал. 19. Параметри Пошуку рішення в моделі зі «сніжателем кислотності»

Мал. 20. Пошук рішення не справляється із завданням

Вам потрібно завантажити і встановити OpenSolver (як це зробити див. Джон Форман. Багато цифр: Аналіз великих даних за допомогою Excel , Глава 1). OpenSolver «підхопить» установки, введені тільки що в вікні Пошук рішення. Тому просто натисніть кнопку Solver. Отримане рішення - $ 1 235 927 більше ніж на $ 100 000 краще за попередній мінімум - $ 1 338 913.

До сих пір ми вважали, що поставляється, має точно зазначені параметри. Резонно припустити, що ці параметри схильні до варіації, яка характеризується середньоквадратичним відхиленням (рис. 21; докладніше див. Визначення середнього значення, варіації і форми розподілу. описові статистики ). Найвідоміше і широко використовується розподіл випадкової величини - це нормальний розподіл, інакше зване «колоколообразной кривої». Скажімо, у випадку з соком з Єгипту середнє значення відносини Брікс / кислотність буде 13, а середньоквадратичне відхилення (також званої стандартним відхиленням) - 0,9 (рис. 21). В даному прикладі 13 - це центр розподілу ймовірності, 68% замовлень будуть в межах ± 0,9 від 13, а 95% будуть в межах ± 1,8 від 13.

Мал. 21. У параметри соків додано стандартне відхилення

Ваша мета - запропонувати план змішування вартістю менше $ 1,25 мільйона, який найкращим чином відповідає очікуванням щодо якості в світлі варіабельності поставок.

Ми використовуємо середнє і середньоквадратичне відхилення характеристик, щоб застосувати імітаційне моделювання за методом Монте-Карло (якщо ви чуєте це назва вперше, рекомендую Використання методу Монте-Карло для розрахунку ризику ). У цьому методі замість включення параметрів розподілу (середнього значення і середньоквадратичного відхилення) в модель безпосередньо, створюється велика кількість сценаріїв, заснованих на цих самих параметрах розподілу.

Сценарій - це один з можливих відповідей на питання: «Якщо це - розподілу, засновані на статистиці, на що ж буде схожий конкретне замовлення?» Кожен сценарій включає сорок параметрів десяти сортів соку (рис. 22). Щоб отримати один такий параметр, скористайтеся функцією НОРМ.ОБР (докладніше про функції див. Нормальний розподіл ). Наприклад, в комірці В33 ставлення Брікс / кислотність для сорту Hamlin визначається формулою = НОРМ.ОБР (СЛЧИС (); H5; N5). Введіть аналогічні формули в область В33: СW76, згенерувавши 100 сценаріїв. Пошук рішення не зможе працювати з цими формулами, так як вони нелінійні, тому скопіюйте їх в буфер і вставте, але вже, як значення.

Мал. 22. Фрагмент згенерованих сценаріїв характеристик соків

Далі для кожного сценарію визначаємо 4 параметра по кожному місяцю (рис. 23).

Мал. 23. Розрахунок характеристик для кожного сценарію

Мета мінімізувати значення в комірці D2. Тобто, знайти рішення, яке найменше знижує кордону якості для 100 сценаріїв. Як і в прикладах на рис. 13-15, в комірці D2 немає формули. Оптимізація виконується завданням параметрів у вікні Пошук рішення. Все, що потрібно - це помістити в усі сценарії кордону якості, а не просто очікувані значення характеристик. Таким чином, в відношення Брікс / кислотність ви додаєте умови B78: CW80> = B26 і = <F26, потім робите те ж саме з кислотністю, в'язкої складової смаку і кольором (рис. 24). Натисніть Знайти рішення. Рішення знайдеться досить швидко. Якщо ви генерували випадкові значення самі, а не використовували ті, що знаходяться в файлі для завантаження, ваше рішення може відрізнятися. Для моєї сотні сценаріїв найкращим показником, який мені вдалося отримати, є зміна якості на 133%.

Мал. 24. Налаштування Пошуку рішення для моделі з варіабельністю характеристик

Якщо ви хочете розширити свої знання в області лінійного програмування, рекомендую книгу The AIMMS optimization modeling book . Не пропустіть два розділи про трюки і підказки - вони воістину геніальні.

[1] Написано за матеріалами книги Джона Формана Багато цифр: Аналіз великих даних за допомогою Excel . - М .: Паблішер, 2016. - С. 129-186. Щодо секретності розробки та Другої світової - це, схоже, особиста думка автора книги. Див. Вікіпедію . - Прим. Багузіна.