بخشی از پاورپوینت
اسلاید 1 :
مدلسازي صفر و يك
اسلاید 2 :
اهداف آموزشي
آشنايي با مفهوم مدلسازي صفر و يك
آشنايي با كاربرد متغيرهاي صفر و يك در برنامه ريزي خطي
كسب مهارت در كاربرد متغيرهاي صفر و يك براي متغيرهاي تصميم و محدوديت هاي مساله برنامه ريزي خطي
اسلاید 3 :
برنامه ريزي عدد صحيح Integer Programming
برنامه ريزي عدد صحيح محض
برنامه ريزي عدد صحيح مختلط
برنامه ريزي صفر و يك
اسلاید 4 :
وضعيت بله/نه مستلزم بکار گيري متغير 0 – 1 است.
1 به معناي بله و 0 به معناي خير است.
مثال:
اگر x نشان دهنده مقدار توليد محصول a باشد.
cy >= x
1 يا 0 = y و 0 <=x
محصول a توليد نمي شود يا در صورت توليد حداکثر به c واحد توليد مي شود.
متغير هاي 0 – 1 از نوع بله / نه
اسلاید 5 :
X =< Cy
X => By
X => 0 , Y=0 يا1
حال محدوديت زير چه تصميمي را بيان مي کند؟
X = Qy
X => 0 , Y=0 يا1
جواب:
:توليد محصول A مساوي با Q يا عدم توليد اين محصول
عدم توليد محصول A و يا توليد A حداکثر معادل C واحد وحداقل B واحد
اسلاید 6 :
متغير هاي 0 – 1 از نوع اين و آن
حالت 1 - انتخاب يک مقدار از ميان n مقدار ممکن براي متغير تصميم
حالت 2 - انتخاب يک محدوديت از دو محدوديت
حالت 3 - انتخاب k محدوديت از n محدوديت
اسلاید 7 :
انتخاب يك مقدار از بين n مقدار ممكن براي متغير تصميم
X= a1y1 + a2y2 + … + anyn
به شرطي که:
Y1 + y2+ …+yn = 1
Yi = 0 يا 1 , (i = 1,2,3,…,n)
محدوديت دوم موجب مي شود که فقط يکي از متغير هاي yi داراي مقدار 1 شده بقيه 0 شوند .
در اين صورت ضريب آن متغيري که مقدارش 1 شده است در محدوديت اول و مقدار غير 0 ، x را نشان مي دهد.
حالت 1
اسلاید 8 :
انتخاب يك محدوديت از بين دو محدوديت
دو محدوديت زير مفروض است:
5x1 + 2x2 =< 24
3x1 + 4x2 =< 21
براي انتخاب يکي از دو محدوديت فوق، از M که مقداري بزرگ و مثبت است استفاده مي کنيم
5x1 + 2x2 =< 24 + My1
3x1 + 4x2 =< 21 + My2
y1 + y 2 = 1
x1 , x2 => 0
y1 , y2 = 0 or 1
اگر 1 = y1 باشد چه اتفاقي خواهد افتاد.؟
حالت 2
اسلاید 9 :
انتخاب k محدوديت از n محدوديت
N محدوديت داريم
Σ a1j xj =< b1
↓
Σ aij xj =< bi
↓
Σ anj xj =< bn
حالت 3
اسلاید 10 :
Σ a1j xj =< b1 + My1
↓
Σ aij xj =< bi + Myi
↓
Σ anj xj =< bn + Myn
Y1+ y2 + …+ym=N-K
Y1+Y2+…+YN=0 OR 1
X1,X2,…,XN>=0
اسلاید 11 :
مثال:
شخصي به منظور حداکثر کردن سود ناشي از سرمايه گذاري خود تا سقف يک ميليون ريال قصد دارد سه پروژه را مورد بررسي قرار مي دهد. سود ناشي از سرمايه گذاري سالانه براي هر پروژه به ترتيب زير است:
پروژه 1: 14% در سال
پروژه2 : 10% در سال
پروژه 3 : 16% در سال
سياست سرمايه ، انتخاب دو شيوه از سه شيوه مختلف سرمايه گذاري است . مساله را به نحوي فرموله کنيد که سود حداکثر شود.
شيوه 1 : 75% مجموع سرمايه گذاري>=ميزان سرمايه گذاري در پروژه 3 + ميزان سرمايه گذاري در پروژه 2
شيوه 2 : 50% مجموع سرمايه گذاري >= ميزان سرمايه گذاري در پروژه 3
شيوه 3 : مجموع 12.5 % مجموع سرمايه گذاري>= ميزان سرمايه گذاري در پروژه 2
اسلاید 12 :
حل مساله :
اگر X1,X2,X3 ، ميزان سرمايه گذاري فرد در هر کدام از سه پروژه باشد .
MAX Z =0.14 X1+ 0.10X2+0.16X3
X2+X3<= 0.75 + MY1
X3 <=0.5+MY2
X2 <= 0.125 + MY3
X1+X2+X3 <=1
مجموعه سرمايه :
1 = X1+X2+X3
انتخاب دو محدوديت از سه محدوديت :
Y1,Y2,Y3 = 0 OR 1
X1,X2,X3 >=0
اسلاید 13 :
تبيين مدلسازي عدد صحيح در قالب مثال
بودجه بندي سرمايه اي
تخصيص بودجه اي ثابت ميان چند پروژه مختلف به منظور به حداکثر رساندن ارزش فعلي خالص درآمدهاي ناشي از اجراي پروژه .
پروژه مورد نظر : XJ
ارزش فعلي خالص مخارج انجام شده براي پروژه J در زمان T : CTJ
ارزش فعلي در آمدهاي هر پروژه : Bj
ارزش فعلي بودجه اي که در دوره t سرمايه گذاري مي شود : Ct
اسلاید 14 :
مدل مساله
Max z = Σ bj xj
Σ cTj xj <= ct ( t= 1,…t)
xj = 0 or 1
اسلاید 15 :
مثال :
شرکتي بررسي 4 پروژه مختلف براي سرمايه گذاري در سه سال آينده را در دستورکار خود دارد . اطلاعات مربوط به اين پروژه ها در جدول زير منعکس شده است . به منظور حداکثر کردن در آمد ناشي از پروژه ها چه ترکيبي از پروژه ها را بايد انتخاب نمايد ؟
اسلاید 16 :
حل مساله :
Max z= 80x1+100x2+150x3+120x4
10 x1+15x2+20x3+12x4<=35
12 x1+18x2+22x3+14x4<=35
14 x1+20x2+24x3+16x4<=35
x1,x2,x3,x4 = 0 or 1
اسلاید 17 :
مساله کوله پشتي
هدف از اين مساله ، حمل n نوع کالا با وزن هاي a1,a2,…,an و ارزش c1, c2,…,c3 با وسيله اي به ظرفيت c
Max z = c1x1 +c2x2+…+cnxn
a1x1+a2x2+…+anxn <=c
xj=0 or 1 ( j=1,2,…,n)
در مدل فوق xj تصميم گيري در مورد حمل يا عدم حمل محموله j ام را به عهده دارد . Xj=1 به معني حمل محموله j ام و xj=0 به مفهوم عدم حمل آن محموله است.
اسلاید 18 :
مثال:
به صاحب يک کشتي حمل کالا با ظرفيت حداکثر 12 تن ،پيشنهادحمل کالاهايي با وزن و در آمد متفاوت زير پيشنهاد شده است. با توجه به ظرفيت اين کشتي کدام يک از اين محموله ها بايد براي حمل انتخاب گردد تا در آمد کل ناشي از حمل اين کالاها حداکثر گردد.
اسلاید 19 :
راه حل
در صورتي که xj انتخاب يا عدم انتخاب محموله براي حمل را نشان دهد:
MAX z = 6x1+3x2+2x3+x4+9x5+5x6+8x7+4x8
x1+2x2+3x3+4x4+6x5+5x6+3x7+9x8 <= 12
xj=0 يا 1 j= 1,…,8
اگر هدف بردن حداقل يکي از دو محموله 1و4 باشد؟
اگر هدف بردن حداکثر يکي از دو محموله 2و5 باشد؟
x1+x4=>1
x2+x5=<1
اسلاید 20 :
مساله با هزينه ثابت
فرض کنيد امکان توليد محصول A توسط n ماشين مختلف وجود داشته باشد هر ماشين i ،(n و.و2و1=i)داراي يک هزينه ثابت راه اندازي به ميزان fi باشد.البته اين هزينه وقتي عينيت مي يابد که ماشين i براي توليد مقدارxi واحد که 0 <=xi است مورد استفاده قرار مي گيرد. هزينه متغيرcixi متناسب با توليد xi و براي هر ماشين i در صورت توليد قابل پرداخت است. محدوديت ظرفيت ماشين i براي هر ماشين در طول پريود زماني توليد با bi نشان داده مي شود.مساله تعيين مقدار توليد xi توليد شده بوسيله هر ماشين در هر پريود ، به گونه اي که مجموع هزينه توليد را حداقل کرده و تقاضاي توليد محصول A را به ميزان D واحد ارضا نمايد،مي باشد.مدل عمومي اين مساله به شکل زير است:
Min z = Σ cixi+ Σfiyi
Σ xi => D Xi =
