Лінійне програмування - це набір методів раціонального аналізу та вирішення проблем, який спрямований на допомогу особам, що приймають рішення з питань, що включають велику кількість змінних.
Назва лінійного програмування походить не від створення комп'ютерних програм, а від військового терміна, програмування, що означає `` складати плани чи пропозиції щодо часу для підготовки, матеріально-технічного забезпечення або розгортання бойових підрозділів ''.
Хоча, схоже, лінійне програмування було використано Г. Монжем у 1776 р., Л. В. Канторович вважається одним із його творців. Він представив його у своїй книзі "Математичні методи організації та виробництва" (1939) та розвинув у своїй праці "Про передачу мас" (1942). Канторович отримав Нобелівську премію з економіки в 1975 році за внесок у проблему оптимального розподілу людських ресурсів.
Дослідження операцій в цілому та, зокрема, лінійне програмування отримали значний поштовх завдяки комп’ютерам. Одним з найважливіших моментів стала поява симплексного методу. Цей метод, розроблений Г. Б. Данцигом у 1947 р., Полягає у використанні алгоритму для оптимізації значення цільової функції з урахуванням обмежень. Починаючи з однієї з вершин можливої області, наприклад вершини A, і застосовуючи властивість: якщо цільова функція не приймає свого максимального значення у вершині A, то існує ребро, яке починається з вершини A і вздовж якого цільова функція зростає. ви досягаєте іншої вершини.
Процедура є повторюваною, оскільки покращує результати цільової функції на кожному етапі до досягнення шуканого рішення. Це у вершини, з якої не починається жодне ребро, по якому збільшується цільова функція.
Незважаючи на те, що протягом цього блоку вирішуються лише двовимірні задачі лінійного програмування, цей тип аналізу використовується у випадках, коли задіяні сотні або навіть тисячі змінних.
Зміст цього навчального блоку підпадає під ліцензію Creative Commons, якщо не вказано інше.