Линейното програмиране е набор от техники за рационален анализ и решаване на проблеми, който има за цел да помогне на вземащите решения по въпроси, включващи голям брой променливи.

ctica

Името на линейното програмиране не идва от създаването на компютърни програми, а от военен термин, програмиране, което означава „да се правят планове или предложения за време за обучение, логистика или разполагане на бойни единици“.

Въпреки че изглежда, че линейното програмиране е използвано от Г. Мондж през 1776 г., Л. В. Канторович се счита за един от неговите създатели. Той го представи в книгата си „Математически методи за организация и производство“ (1939) и го разработи в своята работа „За пренасянето на масите“ (1942). Канторович получи Нобелова награда за икономика през 1975 г. за приноса си към проблема с оптималното разпределение на човешките ресурси.

Изследванията на операциите като цяло и по-специално линейното програмиране получиха голям тласък благодарение на компютрите. Един от най-важните моменти беше появата на симплекс метода. Този метод, разработен от Г. Б. Данциг през 1947 г., се състои в използването на алгоритъм за оптимизиране на стойността на целевата функция, като се вземат предвид ограниченията. Започвайки от един от върховете на осъществимата област, например връх А, и прилагайки свойството: ако целевата функция не вземе максималната си стойност при връх А, тогава има ръб, който започва от връх А и по който целевата функция се увеличава. стигнете до друг връх.

Процедурата е итеративна, тъй като подобрява резултатите от целевата функция на всеки етап до достигане на търсеното решение. Това е във връх, от който не започва ребро, по което се увеличава целевата функция.

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


Съдържанието на тази учебна единица е под лиценз Creative Commons, освен ако не е посочено друго.