Gomory પદ્ધતિ. પૂર્ણાંક પ્રોગ્રામિંગ સમસ્યાઓ ઉકેલ

આર્થિક આયોજન વજન સમસ્યાઓ અને પૂર્ણાંકો સંબંધિત વેરિયેબલ્સ સાથે સંકળાયેલ માનવ જીવન સમસ્યાઓ અન્ય ગોળા પણ મુદ્દાઓ. અને તેમના વિશ્લેષણમાં પરિણામે ભારે પડકારો ખ્યાલ સંબોધવા માટે શ્રેષ્ઠ રીતો માટે શોધ તરીકે. તેના લક્ષણો ઉપર લક્ષણ પૂર્ણાંક કિંમત લે છે, અને કાર્ય પોતે ગણવામાં આવે છે પૂર્ણાંક પ્રોગ્રામિંગ કારણ કે ગણિત.

ચલ, પૂર્ણાંક સાથે સમસ્યાઓ મુખ્ય ઉપયોગો, ઓપ્ટિમાઇઝેશન છે. એક પદ્ધતિ પૂર્ણાંક ઉપયોગ કરે છે રેખીય પ્રોગ્રામિંગ, પણ કપાઇ પદ્ધતિ કહેવાય છે.

Gomory પદ્ધતિ ગણિતશાસ્ત્રી પછી નામ આપવામાં આવ્યું હતું, પ્રથમ 1957-1958 અલ્ગોરિધમનો વિકસાવવામાં પણ મોટાપાયે પૂર્ણાંક રેખીય પ્રોગ્રામિંગ સમસ્યાઓ ઉકેલવા માટે વપરાય છે. પૂર્ણાંક પ્રોગ્રામિંગ સમસ્યા કેનોનિકલ ફોર્મ સુલભ પરવાનગી આપે છે અને સંપૂર્ણપણે આ પદ્ધતિ ફાયદા પ્રગટ.

Gomori પદ્ધતિ રેખીય પ્રોગ્રામિંગ પર લાગુ મોટા પ્રમાણમાં શ્રેષ્ઠ કિંમતો શોધવાની કાર્ય જટિલ બનાવે છે. integrality પછી મૂળભૂત જરૂરિયાત છે, જે વધુ સમસ્યા બધા પરિમાણો છે. એવા કિસ્સાઓ છે જ્યારે માન્ય (પૂર્ણાંક) યોજનાઓનો હોવાના સમસ્યા હાજરી ઉદ્દેશ કાર્ય સ્વીકાર્ય સેટ પર પ્રતિબંધના નિર્ણય મહત્તમ પ્રાપ્ત કરવા માટે આવે છે. આ કારણે છે તે અભાવ અભિન્ન ઉકેલો છે. સમાન શરતો વિના, એક નિયમ તરીકે, એક નિર્ણય સ્વરૂપમાં યોગ્ય વાહક છે.

સમસ્યાઓનું નિરાકરણ વિવિધ શરતો વધારાના આવરણ હાથ ધરવા માટે જરૂર છે માટે સંખ્યાત્મક એલ્ગોરિધમ્સ justify કરો.

Gomory પદ્ધતિ મદદથી, સામાન્ય રીતે મર્યાદિત બહુફલક ઉપાયોના કહેવાતા સમસ્યા માટે ઘણા યોજના વિચારો. આ આધાર પર, બધા અભિન્ન યોજના સેટ કાર્ય માટે મર્યાદિત મૂલ્ય ધરાવે છે.

ઉપરાંત, વોરંટી અભિન્ન કાર્ય માટે ધારે છે કે સહગુણાંકો મૂલ્યો પણ પૂર્ણાંકો હોય છે. આ શરતો ગંભીરતા હોવા છતાં, નબળા તેઓ થોડા મેનેજ કરો.

Gomory પદ્ધતિ અનિવાર્યપણે મકાન બંધનો છે, કે જે ઉકેલો કે nonintegral નથી કાપી સમાવેશ થાય છે. આ કિસ્સામાં, ત્યાં કોઈ કપાઇ કોઈ પૂર્ણાંક ઉકેલો યોજના છે.

સમસ્યા ઉકેલવા માટેની અલ્ગોરિધમનો યોગ્ય વિકલ્પો શોધવામાં સમાવેશ થાય છે સિમ્પ્લેક્સ પદ્ધતિ, ધ્યાનમાં integrality શરતો લેતી વગર. શ્રેષ્ઠ યોજના બધા ઘટકો પૂર્ણાંકો સંબંધિત નિર્ણયો હોય, તો તેને ધારી શકાય કે પૂર્ણાંક પ્રોગ્રામિંગ ધ્યેય પ્રાપ્ત થાય છે. કદાચ કે સમસ્યા એ ખુલાસો કરવાની અશક્યતા જોવા મળે છે, તેથી અમે સાબિતી પૂર્ણાંક પ્રોગ્રામિંગ સમસ્યા કોઈ ઉકેલ છે કે છે.

ચલ, જ્યારે શ્રેષ્ઠ ઉકેલ ઘટકો બિન-પૂર્ણાંક સંખ્યા છે. આ કિસ્સામાં, એક નવો પ્રતિબંધ સમસ્યા તમામ મર્યાદાઓ ઉમેરવામાં આવે છે. નવા નિયંત્રણો સંખ્યાબંધ ગુણધર્મો લાક્ષણિકતા છે. સૌ પ્રથમ, તે રેખીય હોવી જોઈએ, બિન-પૂર્ણાંક શ્રેષ્ઠ યોજના મળી સેટ પરથી કાપી હોવી જોઈએ. બેમાંથી પૂર્ણાંક ઉકેલ ગુમાવી ન કરવી જોઈએ, કાપી નાખ્યો.

મકાન બંધનો સૌથી વધુ અપૂર્ણાંક સાથે શ્રેષ્ઠ યોજના ઘટક પસંદ થયેલ હોવું જોઈએ છે. તે આ મર્યાદા વર્તમાન સિમ્પ્લેક્સ ટેબલ ઉમેરવામાં આવશે.

અમે પરંપરાગત સિમ્પ્લેક્સ રૂપાંતર મદદથી પરિણામે સમસ્યા ઉકેલ શોધી શકો છો. અમે પૂર્ણાંક શ્રેષ્ઠ યોજના અસ્તિત્વ પર સમસ્યા ઉકેલ તપાસો, જો શરત સંતુષ્ટ છે, તો પછી સમસ્યા ઉકેલી છે. જો પરિણામ બિન-પૂર્ણાંક ઉકેલો હાજરી સાથે ફરીથી મેળવી હતી, તો પછી અમે વધારાના અવરોધ રજૂ, અને ગણતરી પ્રક્રિયા પુનરાવર્તન કરો.

એવું હાથ ધરવામાં iterations મર્યાદિત નંબર, અમે પૂર્ણાંક પ્રોગ્રામિંગ સામે પૂછતા સમસ્યા શ્રેષ્ઠ કાર્યક્રમ હાંસલ, અથવા સમસ્યા ઉકેલ કરવાની અશક્યતા સાબિત.