Gomory mbinu. ufumbuzi wa matatizo integer programu

matatizo ya uzito wa kiuchumi, mipango na hata masuala ya kutoka nyanja nyingine ya matatizo ya maisha ya binadamu yanayohusiana na vigezo kuhusiana na integers. Kutokana na uchambuzi wao na kutafuta njia bora ya kukabiliana na dhana ya changamoto uliokithiri. makala yake ni kipengele juu inachukua thamani integer, na kazi yenyewe inachukuliwa hisabati kama programu namba kamili.

matumizi kuu ya matatizo ya kutofautiana, integer, ni optimization. Mbinu ambayo inatumia integer programu linear, ambayo pia hujulikana njia ya kukata-off.

Mbinu Gomory ilikuwa jina baada ya mwanahisabati, kwanza maendeleo katika 1957-1958 algorithm bado sana kutumika kutatua matatizo integer programu mstari. aina kanuni la tatizo programu integer inaruhusu kupatikana na kikamilifu kufichua faida za njia hii.

Gomori Mbinu kutumika kwa programu linear complicates sana kazi ya kutafuta maadili mojawapo. Baada integrality ni sharti la msingi, zaidi kila vigezo ya tatizo. Kuna maeneo wakati tatizo kwa kuwa na (integer) mipango halali, kuwepo kwa kazi lengo la vikwazo juu ya kuweka juzu, uamuzi suala la kufikia kiwango cha juu. Hii ni kutokana na ukosefu wa hivyo ni muhimu ufumbuzi. Bila ya hali hiyo, kama sheria, katika hali ya uamuzi ni sahihi vector.

Kuhalalisha mipangilio namba kwa ajili ya kutatua matatizo ya kuna haja ya kufanya kupachika ziada ya hali tofauti.

Kwa kutumia njia ya Gomory, kwa kawaida kuzingatia mipango mingi kwa kile kinachoitwa tatizo la ufumbuzi mdogo polihedroni. Kwa msingi huu, seti ya mpango wote muhimu ina thamani finite kwa ajili ya kazi.

Pia, kwa udhamini kazi muhimu kudhani kwamba thamani za coefficients pia integers. Pamoja na ukali wa masharti haya, kuwa wao kusimamia chache.

Gomory njia kimsingi inahusisha kujenga vikwazo, ambayo kupunguza ufumbuzi ambayo si nonintegral. Katika hali hii, hakuna kukata-off hakuna integer ufumbuzi mpango.

algorithm kwa ajili ya kutatua tatizo inahusisha kutafuta njia zinazofaa simplex mbinu, bila kuzingatia hali ya integrality. Kama sehemu zote za mpango mojawapo ina maamuzi kuhusiana na nambari halisi, inaweza kuwa kudhani kuwa programu integer lengo ni mafanikio. Labda ambayo hupatikana insolubility ya tatizo, hivyo tuna ushahidi kuwa tatizo programu integer haina ufumbuzi.

lahaja, wakati sehemu ya suluhisho mojawapo lina zisizo integer idadi. Katika hali hii, kizuizi mpya aliongeza kwa vikwazo wote wa tatizo. vikwazo mpya na sifa ya idadi ya mali. Kwanza kabisa, ni lazima linear, lazima kukatwa kutoka kupatikana seti ya mashirika yasiyo ya integer mojawapo mpango. Wala integer ufumbuzi haipaswi kupotea, kukatwa.

Wakati wa kujenga vikwazo unapaswa kuchaguliwa sehemu ya mpango bora na sehemu ya juu. Ni kiwango cha juu hii itakuwa aliongeza kwa sasa simplex meza.

Sisi kupata ufumbuzi wa tatizo na kusababisha kutumia ya kawaida simplex mabadiliko. Sisi kuangalia ufumbuzi wa tatizo kwenye kuwepo kwa integer mojawapo mpango, kama hali ni kuridhika, basi tatizo ni kutatuliwa. Kama matokeo ni kupatikana tena kwa uwepo wa ufumbuzi zisizo integer, basi sisi kuanzisha kikwazo ziada, na kurudia hesabu mchakato.

Baada kufanyika finite idadi ya iterations, sisi kufikia mpango mojawapo ya tatizo vinavyotokana mbele ya programu integer, au kuthibitisha insolubility ya tatizo.