Gomory ọna. Awọn ojutu ti odidi siseto isoro

Àdánù isoro ti aje, igbogun ati paapa awon oran lati miiran agbegbe ti awọn eniyan aye isoro ni nkan ṣe pẹlu oniyipada jẹmọ si odidi. Bi awọn kan abajade ti won onínọmbà ati awọn àwárí fun awọn ti o dara ju ona lati koju awọn iro ti awọn iwọn italaya. Awọn oniwe-ẹya ara ẹrọ ni awọn loke ẹya-ara gba ohun odidi iye, ati awọn iṣẹ-ṣiṣe ara ti wa ni mathimatiki bi odidi siseto.

Awọn ifilelẹ ti awọn ipawo ti awọn iṣoro pẹlu ayelujara, ohun odidi, ni o dara ju. A ọna ti nlo ohun odidi PCM siseto, tun npe ni ge-pipa ọna.

Gomory ọna ti a npè ni lẹhin ti awọn mathimatiki, akọkọ ni idagbasoke ni 1957-1958 alugoridimu ti wa ni ṣi o gbajumo ni lilo lati yanju odidi PCM siseto isoro. Awọn oṣuwọn ilana fọọmu ti odidi siseto isoro faye gba wiwọle ati ni kikun afihan awọn anfani ti yi ọna.

Gomori ọna loo si a PCM siseto gidigidi complicates awọn iṣẹ-ṣiṣe ti wiwa awọn ti aipe iye. Lẹhin ti integrality ni a yeke ibeere, siwaju gbogbo sile ti awọn isoro. Nibẹ ni o wa igba nigbati awọn isoro nipa nini wulo (odidi) eto, niwaju ninu awọn ohun iṣẹ ti awọn ihamọ lori gbawole ṣeto, awọn ipinnu ba de si iyọrisi pọju. Eleyi jẹ nitori awọn aini ti o jẹ je solusan. Lai kanna ipo, bi ofin, ni awọn fọọmu ti a ipinnu jẹ yẹ fekito.

Lati da awọn ìtúwò aligoridimu fun lohun isoro ti o wa ni a nilo lati gbe jade afikun superimposition ti o yatọ si awọn ipo.

Lilo awọn ọna ti Gomory, maa ro ọpọlọpọ awọn eto fun awọn ti ki-ti a npe isoro ti lopin polyhedron solusan. Lori yi igba, awọn ti ṣeto ti gbogbo je ètò ni o ni a adópin iye fun awọn iṣẹ-ṣiṣe.

Bakannaa, fun atilẹyin ọja je iṣẹ ro pe awọn iye ti awọn olùsọdipúpọ ni o wa tun odidi. Pelu awọn idibajẹ ti awọn wọnyi ipo, awọn peronial ti nwọn ṣakoso awọn kan diẹ.

Gomory ọna pataki je ile ihamọ, eyi ti ge solusan ti o ba wa ni ko nonintegral. Ni idi eyi, nibẹ ni ko si ge-pipa ti ko si odidi solusan ètò.

Awọn alugoridimu fun lohun awọn isoro je wiwa ti o dara awọn aṣayan rọrun ọna, lai mu sinu iroyin awọn ipo ni integrality. Ti o ba ti gbogbo irinše ti awọn ti aipe ètò ni ipinu jẹmọ si odidi, o le wa ni pe ti awọn odidi siseto ìlépa ti waye. Boya ti o ti wa ni ri insolubility ti awọn isoro, ki a ni ẹri ti awọn odidi siseto isoro ti ko ni ojutu.

Awọn iyatọ, nigbati awọn irinše ti awọn ti aipe ojutu ni ti kii-odidi nọmba. Ni idi eyi, a titun ihamọ wa ni afikun si gbogbo awọn inira ti awọn isoro. Awọn titun awọn ihamọ wa ni characterized nipasẹ nọmba kan ti-ini. Akọkọ ti gbogbo, o yẹ ki o wa PCM, o yẹ ki o wa ni ge ni pipa lati ri ṣeto ti kii-odidi ti aipe ètò. Bẹni odidi ojutu yẹ ki o ko le ti sọnu, ke kuro.

Nigba ti ile ihamọ yẹ ki o wa ni yàn ẹyaapakankan fun ohun ti aipe ètò pẹlu awọn ga ida. O ti wa ni yi aropin yoo wa ni afikun si awọn ti wa tẹlẹ rọrun tabili.

A ri awọn ojutu ti awọn Abajade isoro lilo mora rọrun transformation. A ṣayẹwo awọn ojutu ti awọn isoro lori awọn aye ti ẹya odidi ti aipe ètò, ti o ba ti majemu ti wa ni ooto, ki o si awọn isoro ti wa ni re. Ti o ba ti awọn esi ti a gba lẹẹkansi pẹlu niwaju ti kii-odidi solusan, ki o si a agbekale ohun afikun opin, ati ki o tun awọn isiro ilana.

Lehin ti gbe jade nọmbà adópin kan ti iterations, a se aseyori ohun ti aipe eto ti awọn isoro farahan ni iwaju ti odidi siseto, tabi fi idi insolubility ti awọn isoro.