Усули Gomory. Дар ҳалли мушкилоти барномасозӣ бутуни

мушкилоти Вазн иқтисодӣ, банақшагирӣ ва ҳатто масоили аз дигар соҳаҳои аз мушкилоти зиндагии инсон вобаста ба тағйирёбандаҳои марбут ба integers. Дар натиҷаи таҳлили худ ва ба ҷустуҷӯи роҳҳои беҳтарини ҳалли мафҳуми мушкилоти шадид. хусусиятҳои он аст, ки хусусияти боло мегирад Аҳамияти пурраи, ва вазифаи худи математика ҳамчун барномасозии бутуни он мебошад.

Истифодаи асосии мушкилоти тағйирёбанда, бутунро, ки беҳсозии аст. Методи, ки истифода мебарад бутуни барномасозии хаттӣ, инчунин усули набуред,-истироҳат номида мешавад.

Усули Gomory пас аз математик номи шуд, аввал дар 1957-1958 алгоритми тањия ҳанӯз ба таври васеъ истифода бурда мешавад барои ҳалли масъалаҳои барномасозӣ адресатсияи бутуни. Шакли каноникӣ масъала барномасозии бутуни имкон медиҳад, дастрас ва пурра ошкор намудани афзалиятҳои ин усул.

Усули Gomori бурда ба барномањои хатиро хеле вазифаи ёфтани арзишҳои оптималии мушкил. Баъд аз integrality талаботи асосӣ, минбаъд тамоми параметрҳои масъала аст. Мавридҳое, вақте ки мушкилоти бо доштани эътибор (бутуни) нақшаҳои, ҳузури дар вазифаи мақсади маҳдуд оид ба маҷмӯи қобили қабул аст, қарор меояд, барои расидан ба ҳадди. Ин аст сабаби набудани он ҳалли људонопазири аст. Бе шароити ҳамин, чун қоида, дар шакли қарори вектори мувофиқ аст.

Барои сафед кардани алгоритмҳои ададӣ барои ҳалли масъалаҳои зарур аст, ки ба гузаронидани superimposition иловагии шароити гуногун вуҷуд дорад.

Истифодаи усули Gomory, одатан нақшаҳои зиёде барои мушкилоти ном ҳалли polyhedron маҳдуд дида бароем. Дар ин замина, маҷмӯи тамоми нақшаи ҷудонашавандаи дорои арзиши ниҳоӣ барои иҷро кардани супориш.

Инчунин, барои кафолати функсияи интегралии дар њолате, ки ба арзишҳои аз коэффитсиентҳои низ integers мебошанд. Сарфи назар аз вазнинии ин шароит ба заифтар онҳо идора чанд.

Усули Gomory моҳиятан мегирад маҳдудиятҳои бино, ки ҳалли, ки nonintegral нест, бурида. Дар ин ҳолат, ки ҳеҷ набуред-истироҳат нест, ҳалли бутуни нақшаи нест.

Дар алгоритми ҳалли масъала дар бар мегирад дарёфти имконоти муносиб усули содак, бе назардошти шароити integrality. Агар ҳамаи компонентҳои нақшаи муносиби дорои қарорҳо вобаста ба integers, онро метавон тахмин кард, ки ҳадафи барномасозии бутуни аст, ба даст. Шояд ки он insolubility масъала ёфта, то мо исбот мекунад, ки масъалаи барномасозии бутуни дорад, ҳалли.

Варианти, вақте ҷузъҳои аз ҳалли муносиби дорои рақами бутуни ғайридавлатӣ. Дар ин ҳолат, як маҳдудияти нав аст, ки ба ҳамаи маҳдудиятҳо аз мушкилоти, илова шуда. Дар маҳдудиятҳои нав аз ҷониби як қатор объектҳои хос аст. Пеш аз ҳама, бояд хаттӣ бошад, бояд аз маҷмӯи пайдо наќшаи оптималии ғайридавлатӣ бутуни бурида. На ҳалли бутуни бояд гум карда намешавад, бурида хоҳи шуд.

Вақте ки маҳдудиятҳо эҷоди бояд интихоб шавад, ҷузъи нақшаи муносиби бо баландтарин њиссаи. Ин аст, ин маҳдудият мешавад ба мизи содак мавҷуда, илова шуда.

Мо пайдо кардани ҳалли мушкили дар натиҷаи истифодаи дигаргунсозии содак анъанавӣ. Мо тафтиш ҳалли проблема дар бораи мавҷудияти нақшаи муносиби бутуни, агар ҳолати қонеъ аст, пас масъала ҳал мешавад. Агар дар натиҷаи аз нав бо ҳузури ҳалли ғайридавлатӣ бутуни гирифта шуда буд, он гоҳ мо маҳдудияти иловагӣ ҷорӣ ва такрор раванди ҳисоб мекунад.

Бо як қатор маҳдуди iterations гузаронида, ки мо ба даст барномаи оптималии масъала муҳиме, ки дар назди барномарезии бутуни, ё исбот insolubility масъала.