برنامه مزدوج (ثانویه ، دوگان ،  همزاد ، همتا ) در برنامه ریزی خطی

Duality Programming

 

یکی از مسائل مهمی که در برنامه ریزی خطی باید به آن توجه نمود رابطه ی مستقیم سود آوری و مصرف منابع می باشد . در مدل برنامه ریزی ثانویه پس از تعیین متغیر های تصمیم و محدودیت ها (منابع ) هزینه های مربوط به منابع در تولید معین می شود . در مدل برنامه ریزی مزدوج یک مسئله عبارت از یک برنامه خطی است به منظور یافتن ارزش هایی (قیمت سایه ای ) برای ارزیابی منابع مورد استفاده می باشد . این ارزش ها به نحوی باید تعیین که مجموع ارزش نسبت داده شده به هزینه استفاده از منابع ( یا هزینه تولید ) مینیمم گردد . برنامه مزدوج یک مسئله وسیله ای است جهت ارزشیابی منابع مورد استفاده برای تولید ( یا مصرف) در مقابل راه حل های دیگردر به کارگیری آن منابع . در اینجا برای روشن تر شدن مفهوم قیمت سایه ای به تعریف آن می پردازیم .

قیمت های سایه : در هر مسئله به تعداد محدودیت های موجود در آن مساله بستگی دارد . قیمت سایه هر محدودیت نشان دهنده میزان بهبود مقدار بهینه تابع هدف به ازای افزایش عدد سمت راست آن محدودیت به میزان یک واحد ، به شرطی که سایر پارامتر های مدل بدون تغییر باقی بمانند می باشد .

 

قیمت های سایه منعکس کننده ارزشاقتصادی هر واحد از منبع است و نرخ تغییرات مقدار تابع هدف را به ازای افزایش یک واحد منبع را نشان می دهد . توان ارزش آفرینی یک منبع برای هر واحد از منبع را ((قیمت سایه)) آن منبع گویند .

 مراحل برنامه نویسی مدل ثانویه از مدل اولیه

1- در حالت کلی اگر تابع هدف مسئله اولیه ماکزیمم (Max) باشد (فرم استاندارد ) ابتدا باید تمامی محدودیت های نامعادیله آن به صورت حداکثر)  (( کوچکتر مساوی ) باشد و اگر تابع هدف مسئله اولیه مینیمم باشد کلیه محدودیت های نامعادله ی آن به صورت حداقل (≤) بزرگتر مساوی می باشد .

 

2- در مدل اولیه به تعداد متغیر های تصمیم همان تعداد محدودیت در برنامه ثانویه خواهیم داشت .

 

3- به تعداد محدودیت های موجود در برنامه اولیه همان تعداد متغیر مزدوج (Yi) در برنامه ثانویه وجود دارد .

 

4- اگر مدل اولیه ماکزیمم باشد مدل ثانویه مینیمم خواهد بود .

 

5- مقادیر سمت راست مدل اولیه پس از ترنسپوزه یا برگردان در مقادیر (Yi) ضرب شده و ضرایب سطر تابع هدف مسئله ثانویه را تشکیل می دهد .

 

6- ضرایب هر محدودیت برای متغیر (Xj) در مقادیر (Yi) ضرب شده و به بیان ساده تر ضرایب هر محدودیت به صورت ترنسپوزه در (Yi)ضرب می شود و محدودیت های مدل ثانویه را تشکیل می دهد .در این محدودیت ها جهت نامعادلات مانند بند یک نوشته می شود .

 

7- مقادیر سمت راست محدودیت های ثانویه از ترنسپوزه ضرایب سطر تابع هدف مدل اولیه یعنی Cj ها بدست می اید .

 

8- چون (Yi) ها دارای ارزش می باشند و یا نهایتاٌ صفرند از این رو در مدل ثانویه Yi≥0 می باشد .

 

 مثال: مدل ثانویه را از مدل اولیه بنویسید .