Metodo de Homori. Solvanta entjerajn programproblemojn

La amaso de problemoj de ekonomia naturo, planado de problemoj kaj eĉ la solvo de demandoj de aliaj sferoj de homa vivo-aktiveco konektas kun variabloj, kiuj rilatas al tutaj nombroj. Kiel rezulto de ilia analizo kaj serĉado de optimumaj metodoj de solvo, aperis la koncepto de ekstrema problemo. Ĝiaj trajtoj estas la supra funkcio por preni entjera valoro, kaj la problemo mem estas traktita en matematiko kiel entjera programado.

La ĉefa direkto de uzado de taskoj kun variabloj, kiuj havas entjerajn valorojn, estas optimumigo. Al metodo kiun uzas entjera lineara programado, ankaŭ nomita la tranĉo-off metodo.

La metodo de Homori ricevis sian nomon per la nomo de matematikisto, kiu unue disvolvis en algoritmo en 1957-1958, kiu ankoraŭ estas vaste uzita por solvi entjerajn programajn problemojn. La kanona formo de la interna problemo de programado ebligas plene malkovri la avantaĝojn de ĉi tiu metodo.

La metodo Gomori por lineara programado signife komplikas la problemon trovi optimumajn valorojn. Post ĉio, entjero estas la ĉefa kondiĉo, krom ĉiuj parametroj de la problemo. Ekzistas kazoj, kiam la problemo de havanta validan (entjero) planojn, la ĉeesto en la objektiva funkcio de limigoj sur la konsentebla aro, la decido venas al atingi maksimuman. Ĉi tio estas pro la foresto de entjeraj solvoj. Sen ĉi tiu sama kondiĉo, kiel regulo, taŭga vektoro estas en formo de solvo.

Por certigi nombrajn algoritojn en solvado de problemoj, necesas superimponi diversajn kromajn kondiĉojn.

Uzante la Gomori-metodon, la aro de problemprogramoj kutime konsideras limigitan nomitan polipapon de solvoj. Pro tio sekvas, ke la aro de ĉiuj integraj planoj por la problemo en demando havas finian valoron.

Ankaŭ, por certigi la entutecon de funkcio, ĝi supozas, ke la koeficientaj valoroj ankaŭ estas (entjeroj, entjeras). Malgraŭ la severeco de tiaj kondiĉoj, ili povas esti senditaj al iom.

La metodo de Homori fakte implikas la konstruon de limigoj, kiuj detranĉas decidojn, kiuj ne estas entjeraj. En ĉi tiu kazo, ne estas trankvilo de iu ajn solvo al la entjera valora plano.

La algoritmo por solvi la problemon implikas trovi taŭgan ebloj simplex metodo, sen konsideri la kondiĉojn de integralidad. Se en ĉiuj komponantoj de la optimuma plano ekzistas solvoj rilataj al entjeroj, tiam ni povas supozi ke la celo de entjera programado estas atingita. Eblas, ke malkaŝebleco de la problemo malkaŝiĝos, do ni pruvas, ke la entjera problemo de programado ne havas solvon.

Varianto estas ebla kiam estas ne-entjeraj nombroj en la komponantoj de la optimuma solvo. En ĉi tiu kazo, nova limigo aldoniĝas al ĉiuj limigoj de la tasko. Nova limigo estas karakterizita de la ĉeesto de kelkaj propraĵoj. Unue, ĝi devas esti lineara, ĝi devas forpreni la ne-entjera planon de la optimuma aro trovita. Neniu sola entjera solvo devus esti perdita, forigita.

Kiam vi konstruas la limigon, vi devas elekti la komponanton de la optimuma plano kun la plej granda frakcia parto. Ĝi estas ĉi tiu limigo, kiu estos aldonita al la ekzistanta simplax-tablo.

Ni trovas la solvon de la akirita problemo uzanta ordinarajn simplajn transformojn. Ni kontrolas la solvon de la problemo por la ĉeesto de entjera optimuma plano, se la kondiĉo estas kontentigita, tiam la problemo solvas. Se denove la rezulto estis akirita per la ĉeesto de ne-entjeraj solvoj, tiam ni enmetos aldonan limigon, kaj ni ripetas la procezon de kalkuloj.

Farante finitan numeron de ripetoj, ni akiras optimuman planon por la problemo antaŭ la entjera programado, aŭ pruvas la nesolvigeblecon de la problemo.