--- title: "Линейно програмиране" source: "https://systems-analysis.info/int/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%D0%B5" wiki: "systems-analysis.info/int" article: "Линейно_програмиране" language: "bg" categories: - "Category:Bulgarian" - "Category:Mathematical modeling" - "Category:Operations research" revision_id: 8691 wiki_created_at: 2026-09-07T01:21:13Z wiki_modified_at: 2026-09-07T01:21:13Z downloaded_at: 2026-09-07T23:26:50Z --- # Линейно програмиране **Линейното програмиране** е дял на математическото програмиране и широко използван метод на изследването на операциите, посветен на разработването на теория и методи за решаване на задачи за намиране на екстремум (максимум или минимум) на линейна функция при наличие на линейни ограничения. ЛП е един от най-мощните и често прилагани инструменти за решаване на задачи по оптимизация в икономиката, управлението, планирането, логистиката и други области. ## Предмет и предназначение **Основната задача на линейното програмиране** е да се намери най-добрият (оптималният) начин за разпределение на ограничени ресурси с цел постигане на определена цел, когато и целта, и ограниченията върху използването на ресурсите могат да бъдат изразени чрез линейни зависимости. - Линейното програмиране позволява решаването на такива практически задачи като: - Оптимално планиране на производството. - Оптимизация на транспортните потоци (транспортна задача). - Оптимално разпределение на инвестициите. - Оптимално рязане на материали. Задача за назначенията. ## Математическа постановка на задачата по ЛП Стандартната задача на линейното програмиране се формулира по следния начин: Необходимо е да се намерят стойностите на променливите на решението, които максимизират или минимизират линейната целева функция. При това върху променливите на решението се налагат ограничения под формата на система от линейни равенства и/или линейни неравенства. По правило се добавя условие за неотрицателност на променливите на решението (техните стойности трябва да бъдат по-големи или равни на нула), което често се диктува от физическия или икономическия смисъл на задачата. Математически това означава работа с линейни функции и системи от линейни уравнения/неравенства. ## Основни понятия на ЛП - Променливи на решението (Управляеми променливи): Величини, чиито стойности трябва да бъдат определени в процеса на решаване на задачата (например обеми на производство на различни продукти, количество ресурси, насочвани към различни цели). - Целева функция: Линейна функция на променливите на решението, чиято стойност трябва да се максимизира или минимизира. Тя количествено изразява целта на задачата (например обща печалба, съвкупни разходи). - Ограничения: Система от линейни равенства и/или неравенства, на които трябва да отговарят променливите на решението. Ограниченията отразяват лимитите на ресурсите, технологичните изисквания, плановите задания и други условия на задачата. - Област на допустимите решения (ОДР): Множеството от всички набори от стойности на променливите на решението, които удовлетворяват всички ограничения на задачата. Геометрически в многомерното пространство ОДР представлява изпъкнал многостен (полиедър), евентуално неограничен или празен. - Допустимо решение: Всеки набор от стойности на променливите, принадлежащ на ОДР. - Оптимално решение: Допустимо решение, при което целевата функция достига своята екстремална (максимална или минимална) стойност. Ако оптималното решение съществува, то винаги се намира на границата на ОДР, поне в един от върховете на изпъкналия многостен на ОДР (основна теорема на ЛП). ## Методи за решаване на задачи по ЛП Съществуват няколко основни метода за решаване на задачи по линейно програмиране: - Графичен метод: Прилага се за задачи с две променливи на решението. Позволява нагледно да се изобрази ОДР и целевата функция в равнина и да се намери оптималното решение чрез анализ на върховете на ОДР или чрез преместване на нивовата линия на целевата функция. - Симплекс метод: Универсален итерационен алгоритъм, разработен от Джордж Данциг. Методът последователно преминава от един връх на ОДР към съседен, подобрявайки стойността на целевата функция на всяка стъпка, докато не бъде намерено оптималното решение. Той е класическият и най-известен метод за решаване на задачи по ЛП. - Методи на вътрешната точка: Алтернативен клас алгоритми, появили се по-късно от симплекс метода. Те се движат към оптималното решение вътре в ОДР, а не по нейните граници. Тези методи са особено ефективни при решаване на задачи по ЛП с много голяма размерност. ## Двойственост в линейното програмиране На всяка задача по линейно програмиране (наречена права) може да се съпостави друга задача по ЛП, наречена двойствена. Правата и двойствената задача са тясно свързани помежду си: Решението на едната задача дава информация за решението на другата. Оптималните стойности на целевите функции и в двете задачи съвпадат (ако съществуват). Променливите на двойствената задача имат важна икономическа интерпретация — те съответстват на сенчестите цени (или двойствените оценки) на ресурсите, показвайки с колко ще се промени оптималната стойност на целевата функция на правата задача при малка промяна на ограничението върху съответния ресурс. ## Приложение на ЛП Линейното програмиране намира широко приложение в: - Икономиката и бизнеса (планиране на производството, логистика, финанси, маркетинг). - Промишлеността (оптимизация на технологичните процеси, управление на запасите, рязане на материали). - Транспорта (оптимизация на маршрутите, разписанията). Селското стопанство (оптимизация на посевните площи, фуражните дажби). - Енергетиката (оптимизация на натоварването на генериращите мощности). ## Литература - *Данциг Дж.* Линейное программирование, его применения и обобщения. — М.: Прогресс, 1966. - *Юдин Д. Б., Гольштейн Е. Г.* Линейное программирование (теория, методы и приложения). — М.: Наука, 1969. - *Taha, Hamdy A.* Operations Research: An Introduction. — Pearson. (10th ed., 2017) - *Hillier, Frederick S.; Lieberman, Gerald J.* Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021) ## Вижте също - Изследване на операциите - Оптимизация - Целева функция - Ограничения - Област на допустимите решения - Оптимално решение