Универзитет у Приштини
Економски факултет
Косовска Митровица
СЕМИНАРСКИ РАД
Предмет:
Операциона истраживања
ТЕМА:
Линеарно програмирање - дуални проблем
Ментор:
Студент:
Др Радица Бојичић
Слађан Дејановић
бр.индекса 52/13
Косовска Митровица, 2015.
Операциона истраживања
Линеарно програмирање -
Дуални проблем
САДРЖАЈ
УВОД
..........................................................................................................................................3
1. ЛИНЕАРНО ПРОГРАМИРАЊЕ
..................................................................................4
2.
ОПШТИ ОБЛИК ПРОБЛЕМА ЛП И ЊЕГОВА СВОЈСТВА
........................................6
2.1. Својства општег задатка ЛП..........................................................................................6
3
.
ДУАЛНИ ПРОБЛЕМ
...........................................................................................................7
3.2. Геометријска интерпретација проблема ЛП...............................................................13
ЗАКЉУЧАК
............................................................................................................................17
ЛИТЕРАТУРА
.........................................................................................................................18
2
Операциона истраживања
Линеарно програмирање -
Дуални проблем
1. ЛИНЕАРНО ПРОГРАМИРАЊЕ
Линеарно програмирање спада у једну од најзначајнијих и у пракси
највише примењиваних метода операционих истраживања чији развој многи
сврставају међу најважнија научна достигнућа средине двадесетог века. Први
примери оваквог моделирања изложени су у радовима Кванторовича и
Нојмана, док је главни развој линеарног програмирања уследио после другог
светског рата када су Нојман, Данцинг, Кун и други поставили теоријске
основе линеарног и нелинеарног програмирања. Овај модел се до сада
показао врло делотворним у моделирању, анализи и решавању читавог низа
најразличитијих практичних проблема у привредним, економским,
техничким, пословним, војним и другим системима.
Линеарно програмирање служи за моделирање проблема тзв. условне
оптимизације у којима треба наћи оптимално решење, тј.оно решење за које
се постиже најбоља вредност неког циља на скупу свих могућих
алтернативних решења проблема, при чему свако решење из овог скупа
задовољава задате услове (ограничења). Придев „линеарно“ означава да се и
циљ и ограничења у линеарном програмирању моделима формализују
помоћу линеарних функција, линеарних једначина и неједначина, док се
термин
„програмирање“
овде употребљава као синоним за планирање.
Један од разлога распрострањене примене модела линеарног
програмирања у пракси је (осим његове једноставности) и постојање
ефикасних процедура за њихово решавање које са успехом могу да реше и
проблеме великих димензија. Међу њима је најпознатија
Симплекс
1
метода
(Данцинг, 1947), док су теоријски резултати до којих се дошло осамдесетих
година двадесетог века довели до развоја читавог низа такозваних
унутрашњих метода за проблеме линеарног програмирања које су и даље
предмет интензивних изучавања. Упоредно су развијани и одговарајући
комерцијални рационални пакети који имплементирају ове методе. Симплекс
метод представља један универзални алгоритам који се може применити за
решавање разних облика задатака линеарног програмирања без обзира на
број променљивих параметара који учествују у математичком моделу.
Другим речима, синплекс методом се конструише неко почетно решење, па
1
С.Крчевинац, М. Чангаловић, В. Ковачевић-Вујчић, М. Мартић, М. Вујошевић, „Операциона
истраживања“, Факултет организационих наука, Београд, 2004, стр. 27.
4
Операциона истраживања
Линеарно програмирање -
Дуални проблем
тек када имамо то решење тестирамо да ли је оптимално или није. Уколико се
као резултат појави решење које није оптимално, онда нам симплекс метод
даје упуство како да побољшањем тога решења дођемо до оптималног
решења.
Међутим, у самом математичком моделу постоји одређена функција
која се зове
функција критеријума или функција циља
у ознаци
F
. Ако
функција на пример, изражава доходак, тада је треба максимизирати, у
супротном је треба минимизирати. У сваком случају, ради се о њеној
оптималној вредности што означавамо са
(opt)
F
при чему,
(opt) F значи F
max
или
F
min
што зависи од конкретне ситуације.
Међутим, у неким методама задатака линеарног програмирања
потребно је прећи са ограничења у виду неједначина на ограничења у виду
линеарних једначина, при чему се уводе такозване
допунске променљиве
х
n+1
> 0,..., х
n+m
> 0
са циљем да би се систем линеарних неједначина превео у
систем линеарних једначина.
При томе треба пронаћи:
(opt) F = c
1
x
1
+...+ c
n
x
n
+ 0х
n+1
+…+ 0х
n+m
[1.5]
где под оптималним решењем за функцију подразумевамо да треба одредити
њену највећу односно најмању вредност зависно од тога како је формулисан
услов задатака модела линеарног програмирања.
Дакле, са математичког аспекта основни проблем линеарног
програмирања је проналажење коначне вредности условног екстремума,
максимум или минимум, линеарне функције више променљивих, тако да
одабрана односно оптимална комбинација вредности тих променљивих
задовољава скуп свих услова који су задати системом линеарних једначина
или неједначина уз додатне услове да променљиве имају само ненегативне
вредности.
5
