Gomory Method. Der Léisung vun ganz programméiere Problemer

Gewiicht Problemer vun wirtschaftlechen, Planung a souguer Problemer aus anere Beräicher vum mënschleche Liewen Problemer mat Verännerlechen verbonne zu integers dinn. Als Resultat vun hirer Analyse an der Sich no de beschte Manéiere d'Notioun vun extremen Erausfuerderungen ze Adress. Seng Fonctiounen ass heivun Fonktioun eng ganz Wäert hëlt, an d'Aufgab selwer ass Mathematik als ganz programméiere preservéiert.

D'Haaptrei Gebrauch vu Problemer mat ofwiesselnd, eng ganz, ass den akeef. Eng Method déi eng ganz benotzt Linearschrëft programméiere, och d'Zentral-ugefaangen Method genannt.

Gomory Method war no der Mathematiker genannt, éischt an 1957-1958 Algorithmus entwéckelt ass nach benotzt dicht ganz linear programméiere Problemer ze léisen. Kanonesche Form vun der ganz programméiere Problem erlaabt zougänglech a voll d'Virdeeler vun dëser Method präiszeginn.

Gomori Method fir eng linear programméiere applizéiert complicates immens der Aufgab de optimal Wäerter vun fannen. No integrality ass eng fundamental Noutwendegkeete, weider all Parameteren vum Problem. Et gëtt Fäll, wou de Problem vun valabel mussen (ganz) Pläng, d'Präsenz an der objektiv Funktioun vun Restriktiounen op der zoulässeg virbereet, d'Decisioun ze Maximum erreechen kënnt. Dat ass wéinst der opgepasst et integral Léisungen ass. Ouni déi selwecht Konditiounen, als Regel, an der Form vun enger Decisioun ass passenden Vecteure.

Fir berechtegen der z'identifizéieren algorithms fir erauszefannen Problemer do e brauchen zousätzlech ze droen eraus ass superimposition vu verschiddene Konditiounen.

Mat der Method vun Gomory, betruecht normalerweis vill Pläng fir de sougenannte Problem vun limitéiert polyhedron Léisungen. Op dëser Basis, huet de Set vun all integral plangen engem Haapt Wäert fir d'Aufgab.

Och, fir Garantie integral Funktioun beweis dass d'Wäerter vum Ech sinn och integers. Trotz der Gravitéit vun deene Konditiounen, verwalten de Rescht si e puer.

Gomory bezitt Fong Gebai Restriktiounen, déi Léisungen Géigewier datt net nonintegral sinn. An dësem Fall ass et keen Géigewier-ugefaangen kee ganz Léisungen plangen.

D'Algorithmus fir d'Léise implizéiert gëeegent Optiounen fannen Simplex Method, ouni Kont ausgebild d'Konditiounen vun integrality. Wann all Deeler vun der optimal plangen Décisiounen ze integers Zesummenhang ass, kann et ugeholl ginn, datt d'ganz programméiere Zil erreecht ass. Vläicht dat ass insolubility vun de Problem fonnt, sou hu mir Beweis dass der ganz programméiere Problem keng Léisung huet.

Der Variant, wann d'Komponente vun der optimal Léisung Net-ganz Zuel ass. An dësem Fall ass eng nei Restriktioun fir all Contrainten vum Problem dobäi. Déi nei Restriktiounen sinn duerch eng Rei vun Eegeschaften charakteriséiert. Éischt vun all, soll et linear ginn, sollen aus dem fonnt Formatioun vun Net-ganz optimal plangen Géigewier ugefaangen ginn. Weder ganz Léisung soll net verluer, Géigewier ugefaangen ginn.

Wann Gebai Restriktiounen soll mat der héchster Ëmwandlung Komponent vun engem optimal plangen gewielt ginn. Et ass dëst begrenzten Dauer fir déi bestehend Simplex Dësch dobäi ginn.

Mir fannen d'Léisung vum Problem doraus konventionell Simplex Transformatioun benotzt. Mir kucken d'Léisung vum Problem iwwert d'Existenz vun enger ganz optimal plangen, wann d'Konditioun zefridden ass, dann ass de Problem geléist. Wann d'Resultat erëm mat der Präsenz vun Net-ganz Léisungen kritt huet, da Aféieren mir eng zousätzlech Beschränkung, an der Berechnung Prozess widderhuelen.

Allerdéngs war d'Haapt Zuel vun Ben duerchgefouert, mir eng optimal Programm vun de Problem virun ganz programméiere, oder beweisen der insolubility vum Problem zougemaach erreechen.