Gomory طريقه. د integer پروګرامونو د ستونزو د حل لاره

د اقتصادي، پالن وزن ستونزو او آن د ژوند د انسان سره د integers اړوند متحولونه تړاو ستونزې نورو برخو مسایلو. لکه څنګه چې د خپل تحليل په پايله کې او د د افراطي ننګونو د تصور د حل د غوره لارو چارو د لټون. د دې بڼې دی پورته ځانګړنه یو integer ارزښت نیسي، او د کاري پخپله د رياضي په توګه integer پروګرامونو وبلل.

د سره متحول، یو integer ستونزو اصلي استعمال، ده د ګټورول. یو میتود دی چې هغه د یو integer کاروي خطي پروګرامونو، هم پري پړاو میتود په نامه.

Gomory ميتود د رياضي وروسته ونومول شو، لومړي ځل لپاره په 1957-1958 الګوریتم جوړ اوس هم په پراخه کچه له integer خطي پروګرامونو ستونزو د حل لپاره کارول. د integer پروګرامونو ستونزه ېک فورمه لاس رسی اجازه ورکوي او د دغه ميتود د ګټې په بشپړه توګه افشاء کړي.

ډېر Gomori میتود یوه خطي پروګرامونو تطبیق د مطلوبو ارزښتونو د موندلو دنده پیچلې کوي. integrality وروسته د يو اساسي شرط دی، نور هم د ستونزې د ټولو پارامترونو ده. مواردو کې شته دي چې په شتون باوري (integer) پلانونه ستونزه، چې په شتون موخه دنده پر منلو ټولګه محدوديتونو، پرېکړه اعظمي لاسته راځي. دا له امله دا دی چې د دا د نشتوالي نه بېلېدونکې حل دی. په ورته حالت پرته، د يو حاکميت په توګه، د يوه پرېکړه په بڼه دی مناسب ناقل.

د دې لپاره چې د ستونزو د حل شته دی چې د بيلابيلو شرايطو اضافي superimposition ترسره اړتيا د عددي الگوريتم توجیه.

د Gomory د میتود په کارولو سره، معمولا د محدود polyhedron د حل لارې تش په نامه ستونزه ډیر پلانونه په پام کې. په دې اساس، د ټولو نه بېلېدونکې پلان لپاره د کاري يو د محدودو ارزښت لري.

همدارنګه، د تضمین نه بېلېدونکې دنده وګڼي چې د ضريبونو ارزښتونو هم integers دي. د دغو شرايطو شدت سره سره، د کمزوری دوی یو څو اداره کړي.

Gomory میتود په اړینه ودانۍ محدوديتونو، چې د حل لارې چې nonintegral نه پرې لري. په دې صورت کې نه پرې پړاو نه integer د حل پلان شته.

د دې ستونزې د حل الګوریتم شامل مناسب انتخاب موندلو simplex طريقه، په پام کې نیولو د integrality د شرایطو پرته. که د مطلوبو پلان په ټولو برخو ته integers اړوند پریکړو لري، نو کولای شي فرض شي چې د integer پروګرام هدف دی ترلاسه کړي دي. ښايي چې د ستونزې insolubility موندل، نو موږ ثبوت چې د integer پروګرام ستونزه حل نه لري لري.

د شافعي، کله چې د مطلوبو د حل د برخو او اجزاو لرونکی د غیر integer شمیره. په دې حالت کې، یو نوی محدودیت زياته ده چې د ستونزې د ټولو خنډونو. د نوي محدوديتونه د ملکیتونو د يو شمير له خوا خصوصيات دي. د ټولو نه اول، دا بايد خطي وي، باید داچي د غیر integer مطلوبو پلان د موندل سیټ څخه وشړل شي. نه integer د حل لاره باید ورک شی نه، پرې.

کله چې د جوړولو محدودیتونه باید سره د لوړ کسر یو مطلوبو پلان جز غوره شي. دا د دې محدودیت به د موجوده simplex میز ته زياته شي.

موږ د دوديزې پایله simplex بدلون په کارولو سره د ستونزې د حل لاره پيدا کړي. موږ د یو integer مطلوبو پلان شتون د دې ستونزې د حل وګورئ، که د حالت د قناعت، نو ستونزه حل ده. که نتيجه سره د غیر integer د حل په شتون بيا تر لاسه شو، نو موږ د يو اضافي خنډ معرفي کړي، او د محاسبې د پروسې تکرار.

په درلودلو سره د iterations د محدودو شمیر ترسره کړل، موږ د ستونزې د integer پروګرام په مخ کې متوجه یو مطلوب پروګرام، او یا هم د ستونزې د insolubility ثابته کړي.