Tiykarǵi bólim pútin sanlı programmalastırıw máselesiniń qoyılıwı, túrleri hám geometriyalıq talqını 4

Pútin sanlı programmalastırıw máselesin sheshiwdiń Gomori usılı

Pútin sanlı programmalastırıw máselesi sızıqlı programmalastırıw máselesinen qosımsha (1) yamasa (10 ) kórinistegi shártler menen parıq etedi. Bul shártlerdiń qatnasıwı pútin sanlı programmalastırıw máselesin sheshiw procesin qıyınlastıradı. Nátiyjede sızıqlı programmalastırıw máselesin sheshiw ushın qollanılatuǵın usıllardı pútin sanlı programmalastırıw máselelerine qóllaw múmkin bolmay qaladı.

Pútin sanlı programmalastırıw máselelerdi sheshiw ushın onıń qásiyetlerin itibarǵa alıwshı usıllar jaratılǵan bolıp, olardan amerika alımı R. Gomori jaratqan usıl optimal sheshimdi beretuǵın eń anıq usıl esaplanadı. R. Gomori tolıq pútin sanlı hám bólek pútin sanlı programmalastırıw máselelerdi sheshiw usılın jaratqan. tómende onıń tek tolıq Pútin sanlı programmalastırıw máselelerdi sheshiw ushın mólsherleńen 1-algoritmı menen tanısamız.
Bul usıldıń ideyası tómendeginen ibarat. Berilgen pútin sanlı programmalastırıw máselesinde belgisizlerdiń pútin bolıwlıq shártige itibar bermesten, olardıń ápiwayı sızıqlı programmalastırıw máselesi retinde simpleks usılınan paydalanıp sheshemiz. Eger sheshim pútin sanlardan ibarat bolsa, ol pútin sanlı programmalastırıw máselesiniń de sheshimi boladı. Keri jaǵdayda belgisizlerdiń pútin bolıwlıq shártini itibarǵa alıwshı hám «kesiwshi teńleme» dep atalıwshı qosımsha teńleme dúziledi. Bul teńleme tiykarǵı teńlemeler sistemasına qosıp jazıladı hám bazis sheshim almastırıladı. Onıń ushın belgisizdi kesetuǵın teńlemeden ajratıladı jáne onıń ma`nisin basqa teńlemelerge qoyıp shıǵıladı. Bunday jumıslar máseleniń Pútin sanlı sheshimi tawılǵansha yamasa onıń joqlıǵı anıqlanǵansha tákirarlanadı. Hár bir basqıshda dúzilgen qosımsha teńleme kesetuǵın teńleme dep atalıwına sebep bul teńleme járdeminde berilgen (1) - (4 ) máseleniń jobalarınan shólkemlesken qabarıq kompleksiniń bólshek sanlı jobaların óz ishine alǵan bólegin kesip beredi. Kesiw procesi K kompleksiniń tek pútin sanlı jobaların óz ishine alǵan bólegi K' tapilguncha yamasa bunday bólim joqlıǵı anıqlańuncha tákirarlanadı. Bunıń geometriyalıq suwretin tómendegi formada (2-sızılma) ańlatıw múmkin.
Bu shaklda K qabarıq toplam OABCD kópmuyesh arqalı anıqlanadı. Bu kópmuyeshniń muyesh noqatlari kesiwshi teńlemeler járdemi menen kesip barıw nátijesinde OMLEN qabarıq kópmuyesh payda boladı, onıń shetki noqarlarınıń koordinatalari pútin sanlardan ibarat boladı.

2-sızılma
Kesetuǵın teńlemeler tómendegishe dúziledi:

1. 
   Shama menen oylayıq, (1) - (4 ) máseledegi belgisizlerdiń pútin bolıwlıq shártini tastap jiberiwden payda bolǵan másele sheshilgen jáne onıń optimal sheshimi bolsın. Aqırǵı simpleks kestedegi basis vektorlar lardan ibarat deylik. Bul halda bul simpleks kestesiniń kórinisi tómendegishe boladı.
   

Eger barlıq lar pútin sanlar bolsa, tabılǵan sheshim pútin sanlı programmalastırıw máselesiniń sheshimi boladı.

2. 
   Shama menen oylayıq, bázi birleri bólshek sanlardan ibarat bolsın hám de bázi birleri de bólshek sanlar bolsın (keri jaǵdayda másele pútin sanlı sheshimge iye bolmaydı ). hám larniń pútin bólimlerin uyqas túrde hám menen belgileymiz. Ol halda bul sanlardıń bólshek bólimleri hám lar tómendegishe anıqlanadı :
   

Shama menen oylayıq, bázibir bolsın. Ol halda matritsaniń teńlikti qánaatlantıratuǵın qatarı ushın kesetuǵın teńleme dúziledi. Onıń ushın aldın

Teńsizlik dúziledi, keyininen onı (-1) ga kópeytirip, qosımsha ózgeriwshi kirgiziw nátiyjesinde tómendegi teńleme payda etinadi.

Bunday dúzilgen teńleme kesetuǵın teńleme dep ataladı.

3. 
   Kesetuǵın teńlemeni simpleks kestesiniń qatarına jaylastıramız. Bul teńleme degi ózgeriwshige uyqas keliwshi vektor bazis vektor boladı.
   

Bazisdan vektor shıǵarılıp, onıń ornına

Shártni qánaatlantıratuǵın vektor kiritiledi hám ápiwayı simpleks usıldaǵı formulalar járdeminde simpleks keste almastırıladı. Eger payda bolǵan simpleks kestedegi barlıq ar Pútin sanlı (yaǵnıy hámme ) bolsa, tabılǵan sheshim berilgen Pútin sanlı programmalastırıw máselesiniń sheshimi boladı. Keri jaǵdayda joqarıdaǵı 2-3 punktlerde etilgen islerdi taǵı tákirarlaymız, ulıwma bul jumıslar berilgen máselelerdiń Pútin sanlı sheshimi tapilguncha yamasa máselelerdiń Pútin sanlı sheshimi joqlıǵı anıqlańuncha tákirarlanadı. Eger s hártni qánaatlantıratuǵın k- qatardaǵı barlıq lar Pútin sanlı (sonday eken barlıq ) bolsa, ol halda berilgen másele Pútin sanlı sheshimge iye bolmaydı.

3.