ПРОБЛЕМ ЗА ЛИНЕЙНО ПРОГРАМИРАНЕ (PPL)
Математика
ДРУГИ ДОКУМЕНТИ
ПРОБЛЕМ ЗА ЛИНЕЙНО ПРОГРАМИРАНЕ (PPL)
Основни форми на PPL, решения, класификация; икономическо тълкуване на ЗОП.
Проблемът на математическо програмиране представлява определянето на оптимума (максимум или минимум) на векторна променлива функция, която изпълнява 11511s1820l условия за подкуп (ограничения, връзки), като неравенства или уравнения, както и условия за не-отрицателност на променливите на функцията. Ако всички функции, които се намесват при формулирането на задачата за математическо програмиране, са линейни, тогава проблемът се извиква проблемът с линейното програмиране (PPL); иначе се нарича проблем с нелинейното програмиране.
Стандартна форма - е тази, която съдържа ограничения на типа уравнение.
- оптимално z =
-ограничения на равенството:
- условия на неотрицателност:
Стандартната матрична форма може да бъде изразена по следния начин:
където
- е наречен обективна функция ( функция икономически)
се извиква пространството R n на вектора X, съответно C - пространство за дейност
векторът се нарича ресурсен вектор
се нарича пространството R m ресурсно пространство.
Канонични форми
който проверява системата от ограничения се нарича решението на проблема (възможно решение);
- извиква се решение на ограниченията, което проверява условията на неотрицателност времеви график или допустимо решение;
- извиква се програмата, за която се изпълнява исканият край на функцията оптимална програма.
Нека проблемът с линейното програмиране е в стандартна форма.
Възможно е ограниченията на неравенството да бъдат въведени под формата на ограничения на равенството чрез добавяне (или изваждане) в един от термините на неравенството термин, наречен променлива ecart или компенсационна променлива.
Обозначаваме колоните вектори на матрицата A,; тогава системата от ограничения може да бъде написана:
Нека B е основа в пространството. Забележка за един от векторите на основа В. Или базовият разтвор съответства на основа Б. Извиква се основа Б, която води до програма допустима основа; ако не е програма, казваме, че B е възможен.
Модели на линейно програмиране, срещани в икономическата практика
Сред най-често срещаните икономически проблеми, моделирани с помощта на линейно програмиране, представяме следното:
а) проблемът с планирането на производството
Предприятието произвежда в асортимент и разполага с m ресурси. Необходимо е да се организира производството, ако са известни количеството налични ресурси, специфичните консумации и унитарните ползи.
Организацията на производството идентифицираме при създаването на модела PPL с производствения план.
И двете: количеството налични ресурси на Ri
aij - количеството ресурси Ri, необходимо за консумация за асортимента Sj
cj - ползата, донесена от асортимента Sj.
Обозначаваме xj - броят на асортиментите от тип Sj. Тогава производственият план се представя от вектора на колоната
Така че PPL може да се заяви, както следва:
За да определите координатите му при условията:
получаване на максимална полза
б) проблемът с храненето
Диетата трябва да съдържа хранителни вещества в количествата, открити в храната
Нека aij - количествата вещества, съдържащи се в храната Aj,
cij-единични разходи за храна Aj.
Определете количествата xj храна, необходими за осигуряване на необходимото ниво на вещества, така че общите разходи за диетата да бъдат минимални.
Математическият модел на задачата: така
в) Проблем с транспорта
Същият продукт трябва да бъде преразпределен от m-производствени центрове (доставчик) до n-търговски центрове (бенефициент), наличността на доставчика е, потребността на бенефициера Bj е bj, единичната цена от доставчика до бенефициера Bj е cij. Организирането на транспорта означава да се определят количествата продукти, които да бъдат транспортирани от всеки доставчик до всеки бенефициент, така че общите разходи за транспорт да бъдат минимални.
Отбелязваме xij - количеството, което се транспортира от доставчика до бенефициента Bj.
Като се има предвид, че общият размер на разположение на доставчиците е равен на сумата, необходима на бенефициентите, проблемът става балансиран и моделът на линейно програмиране е:
мин
г) Проблемът със смесването
Продуктът се получава от сместа от n-суровини Mj, като единицата суровини Mj съдържа aij единици вещество. Продуктът трябва да съдържа поне dh, единици вещество и най-много dk, единици вещество, единичната цена на суровините Mj е cj .
Определете xj количествата суровини Mj, които трябва да бъдат част от продукта, така че разходите му да бъдат минимални. Математическият модел на задачата, формулирана като PPL, е:
,
,