Gomory метод. Решението на број проблеми програмирање

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

Главна употреба на проблеми со променлива, цел број, е оптимизација. Метода кој користи број линеарно програмирање, исто така, се нарекува метод на cut-off.

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

метод Gomori примени на линеарно програмирање голема мера го отежнува задачата за наоѓање на оптимални вредности. По интегралност е основен услов, дополнително сите параметри на проблемот. Има случаи кога проблемот со тоа што ќе важи (цел број) планови, присуството во целта функција на ограничувањата за допуштена сет, одлуката збор за постигнување на максимум. Ова се должи на недостаток на тоа е составен решенија. Без исти услови, како по правило, во форма на одлука е соодветно вектор.

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

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

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

метод Gomory суштина вклучува ограничувања зграда, која го намали решенија кои не се nonintegral. Во овој случај, не постои намалување на-оф не цел број решенија план.

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

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

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

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

Ја врши конечен број на повторувања, ние се постигне оптимално програма на проблемот поставени пред број програмирање, или се докаже нерастворливост на проблемот.