Гомори метод. Решење целочисленних програмских проблема

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

Главни употребе проблема са променљиве, цео број, је оптимизација. Поступак који користи интегер линеарног програмирања, такође назива метод цут-офф.

Гомори метод је назван по математичар, прво развијен у 1957-1958 алгоритму и даље у широкој употреби за решавање целе линеарно програмирање проблеме. Канонског облика проблема интегер програмирање омогућава доступним и потпуно откривају предности овог метода.

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

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

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

Исто тако, за гарантни интегралну функцију претпоставити да су вредности коефицијената су цели бројеви. Упркос озбиљности ових услова, слабији они управљају неколико.

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

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

Варијанте, када су компоненте оптимално решење садржи нон-интегер нумбер. У том случају, нова ограничење се додаје свим ограничењима проблема. Нове рестрикције се одликују великом броју особина. Пре свега, требало би да буде линеаран, треба одсечен од нашао скупа не цео број оптималан план. Ни цео решење не би требало да се изгуби, одсечен.

Приликом израде ограничења треба да буду изабрани компоненту оптималне плана са највећим фракције. То је ово ограничење ће бити додат на постојећи симплекс табеле.

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

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