ЛИНЕАРНО ПРОГРАМИРАЊЕ: ЧЕМУ СЛУЖИ, МОДЕЛИ, ОГРАНИЧЕЊА, АПЛИКАЦИЈЕ - МАТХС - 2025

Линеарно програмирање представља математички метод који се користи за оптимизацију (максимизујете или минимизирају према потреби) функције чији варијабилни параметри су ограничене, док док функција и ограничења линеарно зависне варијабле.

Опћенито, функција за оптимизацију моделира практичну ситуацију, попут профита произвођача чији су улози, радна снага или стројеви ограничени.

Слика 1. Линеарно програмирање се широко користи за оптимизацију профита. Извор: Пикселс.

Један од најједноставнијих случајева је линеарна функција коју треба максимизирати, што зависи само од две променљиве, назване променљиве одлуке. Може бити у облику:

З = к ₁ к + к ₂ и

Са константом к ₁ и к ₂ . Ова функција је позната као објективна функција. Наравно, постоје ситуације које за проучавање заслужују више од две варијабле, које су сложеније:

З = к ₁ к ₁ + к ₂ к ₂ + к ₃ к ₃ +….

А ограничења су такође математички моделирана системом једначина или неједнакости, једнако линеарним у к и и.

Скуп решења у овом систему назива се изведивим решењима или изведивим тачкама. А међу изведивим тачкама постоји бар једна, која оптимизује циљну функцију.

Линеарно програмирање самостално су развили амерички физичар и математичар Георге Дантзиг (1914-2005) и руски математичар и економиста Леонид Канторовицх (1912-1986), убрзо након Другог светског рата.

Метода решавања проблема позната као симплекс метода је деца Дантзиг-а, који је радио за ваздухопловне снаге САД, Беркелеи Университи и Универзитет Станфорд.

Слика 2. Математичари Георге Дантзиг (лево) и Леонид Канторовицх (десно). Извор: Ф. Запата.

Модели линеарног програмирања

Елементи потребни за успостављање линеарног модела програмирања, погодног за практичну ситуацију су:

-Објективна функција

- Променљиве прецизности

-Ограничења

У циљној функцији дефинишете шта желите да постигнете. На пример, претпоставимо да желите да повећате профит од производње одређених производа. Тада се успоставља функција „добит“, у складу са ценом по којој се производи продају.

Математички гледано, ова се функција може изразити скраћено помоћу нотације сажимања:

З = ∑к _и к _и

У овој једначини, к _и су коефицијенти, а к _и су варијабле одлуке.

Променљиве одлуке су елементи система чија је контрола имала, а њихове вредности су реални позитивни бројеви. У предложеном примеру, променљиве одлуке су количина сваког производа који се производи како би се добио максималан профит.

Коначно, имамо ограничења, која су линеарне једначине или неједнакости у погледу варијабли одлуке. Они описују ограничења проблема која су позната и могу бити, на пример, количине сировина доступних у производњи.

Врсте ограничења

Можете имати број М ограничења, почевши од ј = 1 до ј = М. Математички су ограничења три врсте:

1. А _ј = ∑ а _иј . к _и
2. Б _ј ≥ ∑ б _иј . к _и
3. Ц _ј ≤ ∑ ц _иј . к _и

Прво ограничење је типа линеарне једначине и значи да се мора поштовати вредност А _ј , која је позната.

Две преостале рестрикције су линеарне неједнакости, а то значи да се познате вредности Б _ј и Ц _ј могу поштовати или премашити, када је симбол који се појављује ≥ (већи или једнак) или поштован или не премашен, ако је симбол ≤ (мање или једнако).

Пример модела

Поље примене су веома разнолике, у распону од пословне администрације до исхране, али да бисмо разумели методу, у наставку је предложен једноставан модел практичне ситуације са две варијабле.

Локална сластичарница позната је по два специјалитета: црни шумски колач и жртвени колач.

У својој припреми потребна су им јаја и шећер. За црну шуму потребно вам је 9 јаја и 500 г шећера, док је за жртвеник потребно 8 јаја и 800 г шећера. Одговарајуће продајне цене су 8 и 10 УСД.

Проблем је: колико колача сваке врсте мора пекара направити да повећа свој профит, знајући да има 10 килограма шећера и 144 јаја?

Променљиве одлуке

Променљиве варијабле су "к" и "и", које узимају стварне вредности:

-к: број црних шумских колача

-и: колачи са жртвеном врстом.

Ограничења

Ограничења су дата чињеницом да је број колача позитивна количина и да постоје ограничене количине сировина за њихову припрему.

Стога, у математичком облику, ова ограничења имају облик:

1. к ≥ 0
2. и ≥0
3. 9к + 8и ≤ 144
4. 0,5 к + 0,8и ≤ 10

Ограничења 1 и 2 представљају услов ненегативности претходно изложене, а све подигнуте неједнакости линеарне су. У ограничењима 3 и 4 су вредности које не смеју да буду прекорачене: 144 јаја и 10 кг шећера.

Објективна функција

Коначно, циљна функција је добит добијена од производње „к“ количине црних шумских колача плус „и“ количине жртвоваца. Гради се множењем цене са количином направљених колача и додавањем за сваку врсту. То је линеарна функција коју ћемо назвати Г (к, и):

Г = 8к + 10и

Методе решења

Различите методологије решења укључују графичке методе, алгоритам симплекса и интерну тачку.

- Графичка или геометријска метода

Када имате проблем са две променљиве као онај из претходног одељка, ограничења одређују полигоналну област у ки равнини, која се назива изводљива област или регион одрживости.

Слика 3. Изводљива регија у којој се налази рјешење проблема оптимизације. Извор: Викимедиа Цоммонс.

Овај регион је конструисан користећи рестрикцијске линије, које су линије добијене из неједнакости ограничења, радећи само са знаком једнакости.

У случају пекаре која жели да оптимизира добит, ограничења су:

1. к = 0
2. и = 0
3. 9к + 8и = 144
4. 0,5 к + 0,8и = 10

Све тачке у региону затворене овим линијама могућа су решења, па их има бесконачно много. Осим у случају када се испостави да је изведива регија празна, у том случају постављени проблем нема решења.

Срећом, за проблем са пецивом изведива регија није празна, имамо је у наставку.

Слика 4. Изводљиво подручје проблема са пецивом. Линија са добитком 0 прелази порекло. Извор: Ф. Запата са Геогебром.

Оптимално решење, ако постоји, налази се уз помоћ циљне функције. На пример, када покушавамо да пронађемо максималан профит Г, имамо следећу линију, која се назива изо профитна линија:

Г = к ₁ к + к ₂ и → и = -к ₁ к / к ₂ + Г / к ₂

Овом линијом добијамо све парове (к, и) који пружају добијени добитак Г, па постоји породица линија према вредности Г, али све с истим нагибом -к ₁ / к ₂ , тако да су паралелне линије.

Оптимално решење

Сада се може показати да је оптимално решење линеарног проблема увек екстремна тачка или тачка изводљиве регије. Тако:

Ако линија најближа извору има читав сегмент заједнички са изводљивом регијом, онда се каже да постоје бесконачна решења. До овог случаја долази ако је нагиб линије за изузеће профита једнак било којој другој линији која ограничава регију.

За наше пециво, кандидати врхови су А, Б и Ц.

- Дантзиг-ова једноставна метода

Графичка или геометријска метода је применљива за две променљиве. Међутим, сложеније је када постоје три променљиве и немогуће их је користити за већи број променљивих.

Када се баве проблемима са више од две променљиве, користи се симплекс метода која се састоји од низа алгоритама за оптимизацију циљних функција. За израчун се често користе матрице и једноставна аритметика.

Симплек метода започиње одабиром изведивог решења и провером да ли је оптимално. Ако јесте, проблем смо већ решили, али ако није, настављамо ка решењу ближем оптимизацији. Ако решење постоји, алгоритам га проналази у неколико покушаја.

Апликације

Линеарно и нелинеарно програмирање примењују се у многим пољима за доношење најбољих одлука у смислу смањења трошкова и повећања профита, који нису увек новчани, јер се могу мерити временом, на пример, ако желите да минимизирате потребно време извршити низ операција.

Ево неких поља:

-У маркетингу се користи за проналажење најбоље комбинације медија (друштвене мреже, телевизија, штампа и други) за рекламирање одређеног производа.

-За додјељивање адекватних задатака особљу компаније или фабрике или распоредом истих.

- У избору најхрањивије хране и по најнижим трошковима у сточној и перадарској индустрији.

Решене вежбе

- Вежба 1

Графички решите модел линеарног програмирања подигнут у претходним одељцима.

Решење

Неопходно је графиковати скуп вредности који су одређени системом ограничења наведених у проблему:

1. к ≥ 0
2. и ≥0
3. 9к + 8и ≤ 144
4. 0,5 к + 0,8и ≤ 10

Подручје дато неједнакостима 1 и 2 одговара првом квадранту картезијанске равни. Што се тиче неједнакости 3 и 4, започет ћемо проналажењем рестриктивних линија:

9к + 8и = 144

0,5 к + 0,8и = 10 → 5к + 8и = 100

Изводљива регија је четвороножац чији су врхови тачке А, Б, Ц и Д.

Минимална добит је 0, дакле линија 8к + 10и = 0 је доња граница, а линије за изузеће профита имају нагиб -8/10 = - 0.8.

Ова вредност се разликује од падина осталих рестриктивних линија и пошто је изведива регија ограничена, јединствено решење постоји.

Слика 5. Графичко решење вежбе 1, које приказује изводљиву област и тачку решења Ц у једној од врхова поменутог региона. Извор: Ф. Запата.

Ово решење одговара линији нагиба -0.8 која пролази кроз било коју од тачака А, Б или Ц, чије су координате:

А (11; 5.625)

Б (0; 12.5)

Ц (16, 0)

Оптимално решење

Израчунавамо вредност Г за сваку од ових тачака:

- (11; 5.625): Г _А = 8 к 11 + 10 к 5.625 = 144.25

- (0; 12.5): Г _Б = 8 к 0 + 10 к 12.5 = 125

- (16, 0): Г _Ц = 8 к 16 + 10 к 0 = 128

Највећи профит остварује производња 11 црних шумских колача и 5.625 колача са жртвинама. Ово се решење слаже са оним које је пронађено у софтверу.

- Вежба 2

Провјерите резултат претходне вјежбе помоћу Солвер функције доступне у већини прорачунских таблица као што су Екцел или ЛибреОффице Цалц, које укључују алгоритам Симплек-а за оптимизацију у линеарном програмирању.

Решење

Слика 6. Детаљ решења из вежбе 1 кроз табелу Либре Оффице Цалц. Извор: Ф. Запата.

Слика 7. Детаљ решења из вежбе 1 кроз табелу Либре Оффице Цалц. Извор: Ф. Запата.

Референце

1. Сјајно. Линеарног програмирања. Опораван од: бриљант.орг.
2. Еппен, Г. 2000. Оперативно истраживање у административној науци. 5. Едитион. Прентице Халл.
3. Хаеусслер, Е. 1992. Математика за менаџмент и економију. 2нд. Едитион. Групо Едит Ибероамерицана.
4. Хиру.еус. Линеарног програмирања. Опоравак од: хиру.еус.
5. Википедиа. Линеарног програмирања. Опоравак од: ес. википедиа.орг.