در این مقاله می خواهم در خصوص مفهوم استواری در تحقیق در عملیات توضیح دهم. مخاطب این مقاله دانشجویان کارشناسی هستند که یا درس تحقیق در عملیات 1 و برنامه ریزی خطی را گذرانده اند یا در ترم جاری آنرا اخذ کرده اند.

بنابراین قرار نیست مطالب خیلی فنی و ریاضی را مورد بحث قرار دهیم. هدف از این مقاله آشنا نمودن شما با مفهوم و چرایی استواری است.

برای سادگی، کار را از یک مثال شروع می کنیم.

فرض کنید یک کارخانه داروسازی قصد دارد دو نوع داروی جدید را تولید نماید. این دو نوع دارو را با D1 و D2 نشان می دهیم. ماده موثر در هر دو دارو ماده A می باشد که از دو نوع ماده اولیه R1 و R2 قابل حصول است.

اطلاعات مربوط به دو داروی D1 و D2 در جدول 1 داده شده است.

جدول 1: اطلاعات دو نوع داروی D1 و D2

D2 (کیلوگرم)	D1 (کیلوگرم)
6900	6200	قیمت فروش (واحد پول بر کیلوگرم)
0.6	0.5	مقدار ماده موثر A (گرم در هر کیلوگرم)
100	90	نیروی انسانی (ساعت بر کیلوگرم)
50	40	تجهیزات مورد نیاز (ساعت بر کیلوگرم)
800	700	هزینه عملیاتی (واحد پول بر کیلوگرم)

در جدول 2 اطلاعات مربوط به مواد اولیه داده شده است .

جدول 2: اطلاعات مواد اولیه R1 و R2

مقدار ماده موثر A (گرم بر کیلوگرم)	قیمت خرید (واحد پول بر کیلوگرم)
0.01	100	R1
0.02	199	R2

و بالاخره جدول 3 منابع در دسترس سیستم تولید را نمایش می دهد.

جدول 3: منابع در دسترس

ظرفیت انبار (کیلوگرم)	تجهیزات (ساعت)	نیروی انسانی (ساعت)	بودجه (واحد پول)
1000	800	2000	100000

می توان به کمک یک مدل برنامه ریزی خطی مقادیر بهینه تولید دو نوع داروی D1 و D2 را با هدف حداکثر نمودن سود کارخانه به دست آورد.

نوتاسیون های مورد استفاده در مدل برنامه ریزی خطی در جدول 4 ارائه شده اند.

جدول 4: نوتاسیون های مدل برنامه ریزی خطی

D1	مقدار تولید شده از داروی D1 (کیلوگرم)
D2	مقدار تولید شده از داروی D2 (کیلوگرم)
R1	مقدار خریداری شده از R1 (کیلوگرم)
R2	مقدار خریداری شده از R2 (کیلوگرم)

مدل برنامه ریزی خطی به صورت زیر خواهد بود: (مدل 1)

[math]{max}\qquad{Z=6200D1+6900D2-100R1-199R2-700D1-800D2}[/math]

[math]{St:}[/math]

[math]{0.01R1+0.02R2}\geq{0.5D1+0.6D2}\qquad{(Balance}\quad{of}\quad{A)}[/math]

[math]{R1+R2}\leq{1000}\qquad{(Storage)}[/math]

[math]{90D1+100D2}\leq{2000}\qquad{(ManPower)}[/math]

[math]{40D1+50D2}\leq{800}\qquad{(Equipment)}[/math]

[math]{100R1+199R2+700D1+800D2}\leq{100000}\qquad{(Budget)}[/math]

[math]{R1,R2,D1,D2}\geq{0}[/math]

با حل مدل فوق جواب های بهینه عبارت خواهند بود از:

[math]{Z}^{*}={9251.1}[/math]

[math]{R1}^{*}={0}[/math]

[math]{R2}^{*}={440.529}[/math]

[math]{D1}^{*}={17.62}[/math]

[math]{D2}^{*}={0}[/math]

جواب فوق بهینه است، یعنی در میان مجموعه حل های قابل قبول، بیشترین مقدار ممکنه برای تابع هدف را به دست می دهد. کل حل بهینه را با بردار *X نمایش خواهیم داد.

حال یکی از این حل های قابل قبول را انتخاب می کنیم. مثلا حل زیر را:

[math]{Z}^{“}={8294.5}[/math]

[math]{R1}^{“}={877.73}[/math]

[math]{R2}^{“}={0}[/math]

[math]{D1}^{“}={17.467}[/math]

[math]{D2}^{“}={0}[/math]

از علامت (“) روی متغیرها برای نشان دادن حل قابل قبول استفاده می کنیم. کل حل قابل قبول را با “X نشان خواهیم داد. همانگونه که ملاحظه می گردد مقدار تابع هدف برای بردار حل “X کمتر از این مقدار برای بردار حل *X می باشد که امری است طبیعی.

در صورت مساله می بینیم که مقدار ماده موثر A در هر کیلوگرم از ماده اولیه R1 برابر با 0.01 گرم و در هر کیلوگرم از ماده اولیه R2 برابر با 0.02 گرم داده شده است. در دنیای واقعی معمولا این میزان از دقت کمتر دست یافتنی است و مقدار ماده موثر A (برحسب گرم) در هر کیلوگرم از دو نوع ماده اولیه به صورت غیر قطعی و در قالب یک بازه عددی با تلرانس مشخص تعریف می گردد. در اینجا نیز فرض کنید برای میزان ماده موثر A برحسب گرم در هر کیلوگرم از R1 یک تلرانس 0.5 درصدی و برای R2 یک تلرانس 2 درصدی تعریف شده باشد. پس در حقیقت مقدار واقعی A در R1 و R2 برابر خواهد بود با:

[math]{R1}\longmapsto{0.01}\pm{0.5}\%\longmapsto{[0.00995,0.01005]}[/math]

[math]{R2}\longmapsto{0.02}\pm{2}\%\longmapsto{[0.00196,0.00204]}[/math]

منظور از مثلا بازه بین 0.00995 و 0.01005 بدین معناست که مقدار ماده موثر A در هر کیلوگرم از ماده اولیه R1 می تواند حداقل 0.00995 گرم و حداکثر 0.01005 گرم باشد. مقدار دقیق آنرا نمی دانیم، ولی حدود آن دانسته شده است. به این موضوع، عدم قطعیت گفته می شود.

حال فرض کنید در یک زمان خاص، در ماده اولیه R1 مقدار ماده موثر A در حداقل آن یعنی 0.00995 گرم و در ماده اولیه R2 هم در حداقل یعنی 0.00196 گرم باشد. با توجه به بازه مجاز تعریف شده برای هر دو نوع ماده اولیه این امر کاملا شدنی است. در این صورت مدل برنامه ریزی خطی که در بالا داشتیم به شکل زیر تبدیل خواهد شد: (مدل 2)

[math]{max}\qquad{Z=6200D1+6900D2-100R1-199R2-700D1-800D2}[/math]

[math]{St:}[/math]

[math]{0.00995R1+0.0196R2}\geq{0.5D1+0.6D2}\qquad{(Balance}\quad{of}\quad{A)}[/math]

[math]{R1+R2}\leq{1000}\qquad{(Storage)}[/math]

[math]{90D1+100D2}\leq{2000}\qquad{(ManPower)}[/math]

[math]{40D1+50D2}\leq{800}\qquad{(Equipment)}[/math]

[math]{100R1+199R2+700D1+800D2}\leq{100000}\qquad{(Budget)}[/math]

[math]{R1,R2,D1,D2}\geq{0}[/math]

حال نکته جالب در خصوص این مدل این است که دیگر حل بهینه ای که برای مدل (1) به دست آورده بودیم در مدل (2) صدق نخواهد کرد. به بیان دیگر مدل (2) برای حل بهینه مدل (1) نشدنی می گردد. محدودیت اول را در نظر بگیرید:

[math]{0.00995}\times{0}+{0.0196}\times{440.529}\ngeq{0.5}\times{17.62}+{0.6}\times{0}[/math]

می توانیم از زاویه دیگری هم به موضوع نگاه کنیم. در این مساله از همان ابتدا مقدار ماده موثر A در مواد اولیه R1 و R2 غیر قطعی بوده است، این غیر قطعی بودن هم در قالب یک توزیع یکنواخت مابین حد پایین و حد بالای بازه داده شده قرار می گیرد. منظور از توزیع یکنواخت این است که احتمال آنکه ماده موثر A هر مقداری مابین حد پایین و حد بالا را اختیار نماید، برابر است. از اول هم این موضوع را می دانستیم ولی برای آنکه مدل برنامه ریزی خطی (1) یک مدل قطعی و معمولی شود، عدد میانگین بازه را که یک مقدار قطعی است، به عنوان نماینده بازه انتخاب کردیم. معمولا این کاری است که در موارد متعددی انجام می شود.

اما اتفاقی که افتاده این است که اگر بدترین حالت رخ دهد و مقدار ماده موثر A در هر دو ماده اولیه R1 و R2 در کمترین حد خود در بازه قرار گیرد، مدل (2) با جواب های بهینه ای که برحسب میانگین بازه از مدل (1) به دست آورده بودیم نشدنی می گردد.

حال جواب هایی را در نظر بگیرید که به عنوان حل شدنی (و نه بهینه) از مدل (1) محاسبه کرده بودیم. یعنی همان ها که با “R نشان دادیم. اگر همین جواب ها را در محدودیت مربوط به حد پایین محدودیت مربوط به ماده موثر A در مدل (2) قرار دهیم خواهیم داشت:

[math]{0.00995}\times{877.73}+{0.0196}\times{0}\geq{0.5}\times{17.467}+{0.6}\times{0}[/math]

یادآوری می شود که برای این حل قابل قبول مقدار تابع هدف یعنی سود کارخانه، برابر با 8294.5 واحد پول می باشد.

حال اگر کارخانه اصرار داشته باشد که همان الگوی حل بهینه را ادامه دهد چه اتفاقی خواهد افتاد؟

در این صورت مقادیر ذیل همان مقادیر طرح بهینه باقی خواهند ماند:

[math]{R1}^{*}={0}[/math]

[math]{R2}^{*}={440.529}[/math]

[math]{D2}^{*}={0}[/math]

ولی برای آنکه مدل (1) شدنی باقی بماند بایستی مقدار *D1 کاهش پیدا کند. ضریب این کاهش 98 درصد خواهد بود. یعنی داریم:

[math]{D1}^{*}\times{0.98}={17.2676}[/math]

این اصرار بر حفظ طرح بهینه باعث می گردد تا سود کارخانه به مقدار 7294.39 واحد پول کاهش یابد. یعنی 21 درصد کاهش در سود بهینه به دست آمده از مدل (1) که برابر با 9251.1 واحد پول بود. این مقدار را با 8294.5 واحد پول سود ناشی از حل شدنی خودمان مقایسه کنید. حل شدنی خودمان که ادعایی در خصوص بهینگی هم نداشت هم قابل قبول بودن مدل را به هم نمی زند و هم سود بالاتری عاید کارخانه می کند!

می گویند این حل استوارتر از حل بهینه ای است که قبلا به دست آورده ایم

حل استوار حلی است که مصونیت بیشتری در قبال عدم قطعیت ها و تغییرات در پارامترهای مدل داشته باشد. حال سئوال این است که چگونه باید حل یا حل های استوار را برای یک مدل به دست آورد؟ در این مقاله تمرکز خود را روی مدلهای برنامه ریزی خطی میگذاریم.

لازم به ذکر است که در اینجا قصد ورود به موضوعات تخصصی برنامه ریزی استوار را ندارم و نمی خواهم در خصوص تکنیک های گوناگون استوارسازی بحث کنم. علاقمندان می توانند به منابع تخصصی در این حوزه مراجعه نمایند.

یک مدل برنامه ریزی خطی را در نظر بگیرید (مدل 3):

[math]{min}\qquad{Z}={C}^{T}{X}+{d}[/math]

[math]{St:}[/math]

[math]{AX}\leq{b}[/math]

[math]{X}\geq{0}[/math]

فرض می کنیم ماتریس ضرایب A ، بردار سمت راست b ،بردار ضرایب تابع هدف C و پارامتر d همگی غیر قطعی باشند به گونه ای که بتوانیم آنها را در قالب مقادیر بازه ای بیان کنیم.

بازه های عدم قطعیت را به صورت زیر نشان می دهیم:

[math]{A}\in{[A}_{0}{-}\Delta{A,}\quad{A}_{0}{+}\Delta{A]}=\alpha[/math]

[math]{b}\in{[b}_{0}{-}\Delta{b,}\quad{b}_{0}{+}\Delta{b]}=\beta[/math]

[math]{C}\in{[C}_{0}{-}\Delta{C,}\quad{C}_{0}{+}\Delta{C]}=\gamma[/math]

[math]{d}\in{[d}_{0}{-}\Delta{d,}\quad{d}_{0}{+}\Delta{d]}=\delta[/math]

می توانید اینگونه فرض کنید که مدل اولیه برنامه ریزی خطی را بر مبنای میانگین بازه ها ساخته ایم. یعنی در مدل اولیه از A₀, b₀, C₀, d₀ استفاده کرده ایم. اگر بخواهیم مقادیر بازه ای را در مدل برنامه ریزی خطی به کار گیریم، خواهیم داشت (مدل 4):

[math]{min}\lbrace{C}^{T}{X}+{d}\quad{|}\quad{AX}\leq{b,}\quad{X}\geq{0}\rbrace[/math]

[math]{A}\in\alpha[/math]

[math]{b}\in\beta[/math]

[math]{C}\in\gamma[/math]

[math]{d}\in\delta[/math]

چون کار کردن با مقادیر بازه ای در یک مدل ریاضی کار ساده ای نمی باشد، می توانیم بازه ها را با یک ترفند ریاضی به شکل مناسب جهت مدل خودمان تبدیل نماییم.

[math]{A}\in\alpha\qquad\Leftrightarrow\qquad{A}={A}_{0}+{t}_\alpha\Delta{A,}\quad{t}_\alpha\in{[-1,+1]}[/math]

[math]{b}\in\beta\qquad\Leftrightarrow\qquad{b}={b}_{0}+{t}_\beta\Delta{b,}\quad{t}_\beta\in{[-1,+1]}[/math]

[math]{C}\in\gamma\qquad\Leftrightarrow\qquad{C}={C}_{0}+{t}_\gamma\Delta{C,}\quad{t}_\gamma\in{[-1,+1]}[/math]

[math]{d}\in\delta\qquad\Leftrightarrow\qquad{d}={d}_{0}+{t}_\delta\Delta{d,}\quad{t}_\delta\in{[-1,+1]}[/math]

در اینجا با تغییر متغیر t در بازه بین منفی یک و مثبت یک، عملا همان رفتار بازه ای بودن می تواند شبیه سازی شود.

تابع هدف مدل (3) یک تابع هدف min سازی می باشد. برای حفظ حداکثر محافظه کاری و استوار سازی در مدل می توانیم به دنبال آن حل X باشیم که حداکثر تابع هدف مدل (3) را حداقل نماید. لذا مدل به صورت زیر تبدیل خواهد گردید (مدل 5):

[math]{min}\qquad{max}\lbrace{C}^{T}{X}+{d}|\quad{C}\in\gamma\quad{and}\quad{d}\in\delta\rbrace[/math]

[math]{St:}[/math]

[math]{AX}\leq{b}\qquad\forall{A}\in\alpha\quad{and}\quad{b}\in\beta[/math]

[math]{X}\geq{0}[/math]

مدل نهایی را می توانیم به صورت زیر بنویسیم (مدل 6):

[math]{min}\qquad{Y}[/math]

[math]{Y}\geq{(C}_{0}+{t}_\gamma\Delta{C)}^{T}{X}+{(d}_{0}+{t}_\delta\Delta{d)}\qquad\forall{t}_\gamma\in{[-1,+1]}\quad{and}\quad\forall{t}_\delta\in{[-1,+1]}[/math]

[math]{(A}_{0}+{t}_\alpha\Delta{A)}{X}\leq{b}_{0}+{t}_\beta\Delta{b}\qquad\forall{t}_\alpha\in{[-1,+1]}\quad{and}\quad{t}_\beta\in{[-1,+1]}[/math]

[math]{X}\geq{0}[/math]

مدل (6) یک مدل برنامه ریزی خطی است و می تواند یک حل استوار را به دست دهد.

همانگونه که قبلا هم بحث شد، هدف از این مقاله ورود به مباحث تخصصی بهینه سازی استوار نیست. هدف صرفا بیان مفهوم استواری حل و مدل می باشد.

برای مطالب بیشتر و تخصصی می توانید به کتاب ها و مقالات در حوزه بهینه سازی استوار مراجعه نمایید.