Линейно програмиране, техника на математическо моделиране, при която линейна функция се увеличава или минимизира, когато е подложена на различни ограничения. Тази техника е полезна за насочване на количествени решения в бизнес планирането, в индустриалния инженеринг и - в по-малка степен - в социалните и физическите науки.
оптимизация: Линейно програмиране
Макар и широко използвана сега за решаване на ежедневни проблеми с решения, линейното програмиране е сравнително непознато преди 1947 г. Няма работа с никакво значение
Решението на проблем с линейното програмиране се свежда до намиране на оптималната стойност (най-голямата или най-малката, в зависимост от проблема) на линейния израз (наречена обективна функция)
при спазване на набор от ограничения, изразени като неравенства:
А, b и c са константи, определени от капацитета, нуждите, разходите, печалбите и други изисквания и ограничения на проблема. Основното предположение при прилагането на този метод е, че различните връзки между търсенето и наличността са линейни; тоест никой от x i не е издигнат до мощност, различна от 1. За да се получи решение на този проблем, е необходимо да се намери решението на системата от линейни неравенства (тоест, множеството от n стойности на променливите x i, които едновременно удовлетворяват всички неравенства). След това обективната функция се оценява чрез заместване на стойностите на x i в уравнението, което определя f.
Приложенията на метода на линейно програмиране за първи път бяха опитани сериозно в края на 30-те години на миналия век от съветския математик Леонид Канторович и от американския икономист Васили Леонтиеф, съответно в областта на производствените графици и на икономиката, но тяхната работа беше игнорирана от десетилетия. По време на Втората световна война линейното програмиране се използва широко за справяне с транспортирането, планирането и разпределението на ресурсите, подложени на определени ограничения, като разходи и наличност. Тези приложения направиха много за установяването на приемливостта на този метод, който придоби допълнителен тласък през 1947 г. с въвеждането на симплексния метод на американския математик Джордж Данциг, което значително опрости решението на задачите на линейното програмиране.
Въпреки това, тъй като се опитваха все по-сложни проблеми, включващи повече променливи, броят на необходимите операции се разшири експоненциално и надхвърли изчислителния капацитет дори на най-мощните компютри. Тогава, през 1979 г., руският математик Леонид Хачиян открива алгоритъм за многочленно време - в който броят на изчислителните стъпки нараства като сила на броя на променливите, а не експоненциално - като по този начин позволява разрешаването на досега недостъпни проблеми. Алгоритъмът на Хачиян обаче (наречен елипсоиден метод) беше по-бавен от симплексния метод, когато практически се прилагаше. През 1984 г. индийският математик Нарендра Кармакар открива друг алгоритъм на полиномично време, методът на вътрешната точка, който се оказва конкурентен на симплексния метод.
