От икономическа гледна точка линейното програмиране е може би най-важният математически напредък на 20 век.

програмиране

Ако попитате нещо като: Кое изобретение от Втората световна война позволява балансиране на диетата с животни ... Възможно е сцените от битката в телевизионния сериал или от филма на списъка на Шиндлър да минат през ума ви. И тогава се обърквате. Но през 1947 г. Джордж Б. Данциг предлага математически модел за оптимизиране на обучението, снабдяването с логистика и движението на войските във ВВС на САЩ. Замяна на използването на субективни емпирични правила с линейни неравенства и целева функция.

След това разработете метод за решение: Симплексният алгоритъм.

Джордж Б. Данциг

Нека поговорим за математиката

Проблемът с линейното програмиране е проблем с оптимизацията, при който: Той е предназначен да максимизира или минимизира (Минимални разходи или максимална полза например.).

Ще наречем математическия израз на нашия проблем целевата функция. (функция на разходите или функция на рентабилността например).

Ще извикаме ограниченията на нашите параметри (например не повече от, само веднъж, не повече от). Всяко от ограниченията ще бъде линейно уравнение или линейно неравенство в променливите на решението.

Ще извикаме изпълним регион в област, където всички линии, съставени от ограниченията, създават фигура, която ги изпълнява и ще намерим възможен отговор във всяко пресичане на тях, определяйки минимума или максимума.

В този момент е трудно да се разбере какво представлява симплексът и как работи, но нека разгледаме първия проблем с диетата, поставен от математика Стиглер:

„Проблемът с диетата“ на Stigler

Намиране на най-евтиния хранителен микс, който отговаря на девет основни хранителни нужди на човек със средно тегло.

Намалете разходите за снабдяване с войски.

мин. x1 + x2 (Намерете минималните разходи при комбиниране на х количества храна според единичната им цена)

2x1 + x2 = 3 (минимално изискване за протеин)

x1 + 2x2 = 3 (минимално изискване за въглехидрати)

x1 = 0 (минимално количество картофи в диетата)

x2 = 0 (Минимално количество боб в диетата)

В опита си да го реши, Stigler получава една от първите формулировки на линейното програмиране: със 77 променливи и 9 ограничения. Намерете решение чрез евристични методи: 39,93 долара през 1939 г.

Няколко години по-късно Ладерман през 1947 г. използва симплекса, за да намери оптималното решение, като е първото мащабно изчисление, което изисква 120 човекодни, използвайки 10 ръчни настолни калкулатора с 39,69 долара само 24 ctvs. по-евтин от stigler.

Разбира се, напредъкът в изчисленията прави тези преживявания просто анекдотични. Но основната идея е същата.А сега нека разгледаме един пример, когато линейното програмиране става важно .

Пример:

Балансиран фураж за пилета (1- 21 дни) при минимални разходи

Растежът на пилетата зависи от солидна диета, която отговаря на хранителните изисквания на същия.Този пример разработва просто балансиране на две храни с енергийни ограничения, протеини и метионин.

Вземете под внимание, че методът на квадратен квадрат не може да осигури решение с повече от едно изискване и не осигурява минимален отговор въз основа на разходите.

Таблица 1 показва минималните хранителни нужди на пилета-бройлери (от 1 до 21 дни) .

За да се получи балансирана дажба, ще се използват царевица и соя.Таблица 2 показва хранителния състав на тези два входа.А таблица 3 представя цената за кг. всеки .

Сега нека моделираме проблема, като кажем, че: x, y са Kg. на храната, която, разбира се, трябва да е по-голяма от 0 (Възможно е само една от тях да отговаря на изискванията, които търсим).