З економічної точки зору, лінійне програмування - чи не найважливіший математичний прогрес 20 століття.
Якщо ви запитаєте щось на кшталт: Який винахід Другої світової війни дозволяє збалансувати раціон для тварин ... Можливо, вам спадають на думку сцени з бойових серіалів чи з фільму зі списку Шіндлера. І тоді ви заплутаєтесь. Але в 1947 році Джордж Б. Данциг пропонує математичну модель для оптимізації навчання, матеріально-технічного постачання та переміщення військ у ВПС США. Заміна використання суб’єктивних емпіричних правил лінійними нерівностями та цільовою функцією.
Потім розробити метод рішення: симплексний алгоритм.
Джордж Б. Данциг
Поговоримо про математику
Проблема лінійного програмування - це проблема оптимізації, де: Вона призначена для максимізації або мінімізації (наприклад, мінімальна вартість або максимальна вигода).
Ми будемо називати математичний вираз нашої задачі цільовою функцією. (функція витрат або функція прибутковості, наприклад).
Ми будемо називати обмеження наших параметрів (наприклад, не більше одного разу, не більше ніж). Кожне з обмежень буде лінійним рівнянням або лінійною нерівністю у змінних рішення.
Ми будемо називати Реалістичний регіон областю, де всі лінії, складені обмеженнями, створюють цифру, яка їх виконує, і ми знайдемо можливу відповідь у кожному їх перетині, визначаючи мінімум або максимум.
На даний момент важко зрозуміти, що таке симплекс і як він працює, але давайте розглянемо першу проблему дієти, поставлену математиком Штіглером:
"Проблема дієти" Штіглера
Пошук найнижчої вартості харчової суміші, яка відповідає дев’яти основним харчовим потребам людини середньої ваги.
Зменшити витрати на постачання військ.
хв. x1 + x2 (Знайдіть мінімальну вартість при поєднанні х кількостей їжі за їх одиничною вартістю)
2x1 + x2 = 3 (мінімальна потреба в білку)
x1 + 2x2 = 3 (мінімальна потреба у вуглеводах)
x1 = 0 (мінімальна кількість картоплі в раціоні)
x2 = 0 (мінімальна кількість квасолі в раціоні)
У своїй спробі її вирішити Стіглер отримує одну з перших формулювань лінійного програмування: із 77 змінними та 9 обмеженнями. Знайдіть рішення евристичними методами: $ 39,93 у 1939 році.
Кілька років потому Ладерман у 1947 р. Використовував симплекс для пошуку оптимального рішення - це перший масштабний розрахунок, який вимагав 120 людських днів, використовуючи 10 ручних настільних калькуляторів з 39,69 доларів США лише 24 ctv. дешевше, ніж стиглер.
Звичайно, розвиток комп'ютерних технологій робить цей досвід просто анекдотичним. Але основна ідея та ж. Тепер давайте розглянемо приклад, коли лінійне програмування стає важливим .
Приклад:
Збалансований корм для курки (1–21 день) за мінімальних витрат
Зростання курчат залежить від повноцінного раціону, який відповідає харчовим потребам. Цей приклад розробляє просте збалансування двох продуктів з енергетичними обмеженнями, білка та метіоніну.
Візьміть до уваги, що метод персонового квадрата не може запропонувати рішення з кількома вимогами, а також не забезпечує мінімальної реакції на основі вартості.
У таблиці 1 наведені мінімальні харчові потреби курчат-бройлерів (від 1 до 21 дня) .
Для отримання збалансованого раціону буде використана кукурудза та соя. У таблиці 2 наведено поживний склад цих двох речовин, а в таблиці 3 - ціна за кг. кожен .
А тепер давайте змоделюємо проблему, сказавши, що: x, y - Kg. їжі, яка, звичайно, повинна бути більше 0 (може бути, що лише одна з них відповідає вимогам, які ми шукаємо).