دانلود مقاله مسائل برنامه ریزی خطی

بخشی از مقاله

به نام خداوند متعال
تحقيق در عمليات 1
مقدمه
برنامه‌ريزي خطي با بهينه‌سازي (ماكزيمم يا مينيمم) يك تابع خطي كه از محدوديت‌هاي مساوي يا نامساوي يا ضمني تشكيل شده است، سروكار دارد. مساله برنامه‌ريزي خطي را ابتدا جرج.بي.دانتزيك در سال 1947 ابداع كرد. اگرچه ال.دي.كانترويچ مساله‌اي از اين نوع كه با سازمان‌دهي و برنامه‌ريزي ارتباط پيدا مي‌كرد را در سال 1939 فرمول‌بندي كرده بود، ولي كار او تا سال 1959 ناشناخته باقي ماند. بنابراين مبتكر اصلي برنامه‌ريزي خطي به طور كلي جرج دانتزيك معرفي شد.

در سال 1949 جرج.بي.دانتزيك «روش سيمپلكس» را براي حل برنامه‌ريزي خطي به چاپ رساند. از آن زمان به بعد افراد زيادي به روش‌هاي بسيار متعددي از جمله بسط و توسعه نظري، ديدگاه محاسباتي و بكارگيري كاربردهاي جديد آن، در اين حوزه وارد شدند. روش سيمپلكس به دلايل:
1. توانايي مدل‌بندي مسائل مهم و پيچيده مديريتي؛
2. توانمندي حل مسائل در مدت زمان معقول در برنامه‌ريزي خطي كاربردهاي وسيعي دارد.

مدل‌بندي و مثال‌هاي برنامه‌ريزي خطي
به طول كلي مراحل مهمي كه يك تيم تحقيق در عمليات بايستي طي نمايد، عبارتند از:
1. تعريف مساله

2. ساختن مدل
3. حل مدل
4. معتبر بودن مدل
5. اجراي نتيجه‌ نهايي «اتخاذ تصميم»
مهمترين نوع از انواع مدل‌هاي تحقيق در عمليات، مدل رياضي مي‌باشد. در نوشتن اين نوع مدل‌ها، فرض بر اين است كه متغيرها كميت‌پذيرند. بنابراين علائم رياضي را جهت نمايش متغيرها بكار مي‌رود كه بوسيله توابع رياضي به هم مربوط مي‌شود و مدل به وسيله الگوريتم مناسبي حل مي‌شود.
ساختار مدل رياضي

1. متغيرهاي تصميم
2. محدوديت‌ها «قيدها»
3. تابع هدف
انواع مدل‌هاي رياضي كه در «R» (تحقيق در عمليات) استفاده مي‌شود:
1. مدل برنامه‌ريزي خطي
2. مدل برنامه‌ريزي پويا
3. مدل صف
4. مدل كنترل موجودي‌ها
5. مدل شبيه‌سازي
برنامه‌ريزي خطي يك مدل رياضي براي تحقيق در عمليات است.
مساله
1. يك كارخانه مي‌خواهد برنامه‌اي براي توليد وسايل آشپزخانه داشته باشد. براي ساختن اين وسايل كارخانه به داده خام و نيروي انساني نيازمند است و مي‌خواهد سه نوع كالا از نوع A, B و C توليد كند. اطلاعات داده شده در جدول زير در اختيار كارخانه مي‌باشد. حداكثر در روز مي‌توان 200 كيلوگرم ماده خام تهيه نموده و حداكثر نيروي انساني موجود 150 نفر ساعت در روز مي‌باشد. مديريت كارخانه مي‌خواهد طوري تصميم بگيرد كه بيشترين سود را داشته باشد. مساله را به صورت برنامه‌ريزي خطي فرموله كنيد.
C B A
6 3 7 كارگر «نفر ساعت»
5 4 4 ماده خام «كيلوگرم»
3 2 4 سود حاصل از فروش «دلار»

تعداد واحدهاي كالاي نوع A xC

:متغيرهاي تصميم
تعداد واحدهاي كالاي نوع B xB
تعداد واحدهاي كالاي نوع C xA

محدوديت مربوطبه نيروي انساني 7xA+3xB+6xC≤150

:محدوديت‌ها
محدوديت مربوط به ماده خام 4xA+4xB+5xC≤200
محدوديت xA+xB+xC≥0

Max Z=4xA+2xB+3xC: تابع هدف «ماكزيمم سود»

مرتب كردن: اول تابع هدف و بعد قيدها
7xA+3xB+6xC≤0
S.T. 4xA+4xB+5xC≤0
xA, xB, xC≥0
2. يك كارخانه كاغذسازي سه سفارش براي تهيه توپ‌هاي كاغذي «مشابه توپ پارچه» كه طول و عرض آنها در جدول زير داده شده است، دريافت مي‌كند. در اين كارخانه توپ‌هاي كاغذي در دو عرض استاندارد 10 دسي‌متر و 20 دسي‌متر توليد مي‌شود كه بايد به اندازه‌هايي كه در سفارش‌ها مشخص شده، بريده شوند. براي طول توپ‌هاي استاندارد محدوديتي نيست، زيرا از لحاظ علمي، توپ‌هاي با طول محدود مي‌توانند به هم وصل شوند و توپ‌هاي موردنظر را بوجود آورند. به فرم برنامه‌ريزي خطي فرموله كنيد.
طول (دسي‌متر) عرض (دسي‌متر) شماره سفارش
10000 5 1
30000 7 2
20000 9 3
حل: هدف عبارت است از تعيين آن طرح برش كه ضمن كمينه ساختن ضايعات برش تقاضاي موردنظر را برآورده سازد.
20dm 10dm
x26 x25 x24 x23 x22 x21 x13 x12 x11 عرض سفارش
0 0 1 2 2 4 0 0 2 5
0 1 2 0 1 0 0 1 0 7
2 1 0 1 0 0 1 0 0 9
2 4 1 1 3 0 1 3 0 عرض ضايعات

x12: كاغذ اول برش 2
x21: كاغذ دوم برش 1
متغيرهاي تصميم xij≥0
J=1,2,3,…,6 i=1,2
xij: طول كاغذ iام با استفاده از برش jام؛
S1: كاغذي كه عرض آن 5dm و مازاد بر نياز؛
S2: كاغذي كه عرض آن 7dm و مازاد بر نياز؛
S3: كاغذي كه عرض آن 9dm و مازاد بر نياز؛
فرموله كردن مساله:
2xu+4x21+2x22+2x23+2x24-S1=10000
x12+x22+x24+x25-S2=30000
x13+x23+x25+x26-S3=20000
تابع هدف «مينيمم ضايعات»
Min Z: 3x12+ x13+ 3x22+ x23+ x24+ 4x25+ 2x26+5S1+7S2+9S3
مرتب كردن:
Min Z: 3x12+ x13+ 3x22+ x23+ x24+ 4x25+ 2x26+5S1+7S2+9S3
2x11+ 4x21+ 2x22+ 2x23+ x24-S1=10000
S.T. x12+ x22+ x24+ x25-S2=30000
x13+ x23+ x25+ x26-S3=20000

xij≥0, i=1.2, j=1, 2, …, 6
3. كشاورزان يك منطقه زراعي تصميم دارند كه عمليات كاشت، داشت و برداشت را به شكل تعاوني انجام دهند تا از قابليت‌هاي ديگر و امكانات دولتي استفاده كنند و توليد جمعي را افزايش دهند. اين منطقه از سه مزرعه تشكيل شده است. دو عامل زمين و آب امكانات كاشت اين مزارع را محدود مي‌كند كه اطلاعات مربوط به آب و زمين قابل كشت در جدول زير آمده است:
آب موجود (هزار مترمكعب) زمين قابل كشت (هكتار) مزرعه
600 400 1
800 600 2
375 300 3

محصولات مناسب كشت در اين منطقه زراعي عبارت است از:
چغندرقند، پنبه و ذرت. ميزان عملكرد در هكتار و آب مورد نياز اين سه محصول با يكديگر متفاوتند. به علاوه براي رسيدن به تركيب مناسب از سه محصول كاشت هم محصول نمي‌توانند از يك مقدار مشخص بيشتر باشد. اين اطلاعات در جدول زير آمده است:
سود حاصل از فروش (هكتاري) مصرف آب در هكتار (هزارمترمربع) حداكثر كشت (هكتار) محصول
400 3 600 چغندرقند
3 2 500 پنبه
100 1 325 ذرت
كشاورزان توافق كردند كه نسبت زمين كاشته شده به زمين موجود براي هر سه مزرعه مساوي باشد، اما محدوديتي در مورد تركيب كشت محصولات در هر يك از سه مزرعه وجود ندارد. اكنون مي‌خواهيم با توجه به محدوديت‌هاي فوق، ميزان سود جمعي را ماكزيمم كنيم. مساله را به فرم برنامه‌ريزي خطي فرموله كنيد.
حل:
xij: زمين كاشته شده از محصول iام در مزرعه jام.
ذرت پنبه چغندرقند زمين
x13 x12 x11 1

x23 x22 x21 2
x33 x32 x31 3
تابع هدف:
Max Z: 400(x11+ x12+x13) + 300 (x21+ x22+ x23) + 100 (x31+ x32+ x33)
قيد مربوط به زمين قابل كشت:

x11+ x12+ x13≤400
x21+ x22+ x23≤600
x31+ x32+ x33≤300

قيد مربوط به آب موجود
3x11+ 2x12+x13≤600
3x21+ 2x22+ x23≤800
3x31+ 2x32+ x33≤375
قيد مربوط به حداكثر كشت
x11+ x21+ x31≤600
x12+ x22+ x32≤500
x13+ x23+ x33≤325

قيد مربوط به توافق تساوي
(x11+ x12+x13)/400=(x11+ x21+ x31)/600
(x11+ x12+x13)/400=(x31+ x32+ x33)/300
(x21+ x22+ x23)/600=(x31+ x32+ x33)/300
xij ≥ 0
4. يك كارخانه توليدي 5 ماشين رنگ‌كاري و يك ماشين پرس دارد كه اين ماشين‌ها براي ساختن دو نوع محصول A و B بكار برده مي‌شوند.

با تركيب يك واحد از A و يك واحد از B يك محصول جديد بدست مي‌آيد كه محصول نهايي C نام دارد. بهره‌دهي «راندمان» هر كدام از ماشين‌ها براي محصول A و B در جدول زير داده شده است:
رنگ كاري (دقيقه) پرس (دقيقه) محصول
20 3 A
15 5 B

صاحب كارخانه مي‌خواهد توازني روي بار ماشين‌ها داشته باشد. به اين صورت كه هيچ كدام از ماشين‌ها، «رنگ‌كاري و پرس» در روز نيم ساعت بيش از ديگر ماشين‌ها كار نكرده باشد. فرض بر اين است كه كار انجام شده در ماشين پرس به طور يكنواخت به ماشين‌هاي ديگر براي رنگ‌كاري داده مي‌شود. هدف مدير كارخانه در مدت 8 ساعت كار روزانه، ماكزيمم كردن محصولات C مي‌باشد. مساله را به صورت برنامه‌ريزي خطي فرموله كنيد.
حل:

متغيرهاي تصميم:
xA≥0 A تعداد محصول نوع
xB≥0 B تعداد محصول نوع
xC≥0 C تعداد محصول نوع
محدوديت مربوط به پرس:
3xA+5xB ≤ 8/60=480
محدوديت مربوط به رنگ‌كاري:
(20xA+15xB)/5 ≤ 480  4xA+3xB ≤ 480
محدوديت مربوط به كار نكردن بيش از نيم ساعت:
|(3xA+5xB)-(4xA+3xB)| ≤ 30  |-xA+2xB|≤30
 -xA+2xB≤30
-xA+2xB≥-30 *(-) xA-2xB≤30
xA و xB وابسته به xC = min{xA,xB}  xC≤xA  xC-xA≤0
xC≤xB  xC-xB ≤0
مرتب كردن:
تابع هدف : Max Z = xC
S.T:
3xA+5xB ≤ 480
4xA+3xB ≤ 480
-xA+2xB ≤ 30

xA-2xB ≤ 30
xC-5xA ≤ 0
xC-xA ≤ 0
xA,xB,xC ≥ 0
5. يك شركت توليد كننده تلويزيون تصميم دارد تلويزيون سياه و سفيد و رنگي توليد كند. ارزيابي بازار نشان مي‌دهد كه حداكثر مي‌توان 1000 تلويزيون رنگي و 4000 تلويزيون سياه و سفيد در ماه فروش داشت. ماكزيمم تعداد نفر ـ ساعت موجود در هر ماه 50000 است. يك تلويزيون رنگي 20 نفر ـ ساعت و يك تلويزيون سياه و سفيد 15 نفر ـ‌ ساعت وقت مي‌گيرد. سود حاصل از تلويزيون رنگي و سياه سفيد به ترتيب 60 و 30 دلار است. مي‌خواهيم تعداد تلويزيون‌هايي را پيدا كنيم كه شركت بايد از هر نوع توليد كند تا سود آن ماكزيمم شود. مساله را فرمول‌بندي كنيد.
حل: xi: تعداد تلويزيون‌هاي نوع iام كه بايد توليد شوند.
x1: تعداد تلويزيون‌هاي رنگي x2: تعداد تلويزيون‌هاي سياه و سفيد

مرتب كردن مساله
Max Z: 60x1 + 30x2
20x1+15x2≤50000
x1 ≤ 1000
x2 ≤ 4000
x1, x¬2 ≥ 0
6. يك مدير توليد زمان‌بندي سه محصول روي چهار ماشين را برنامه‌ريزي مي‌كند. هر محصول مي‌تواند با هر ماشين توليد شود. هزينه توليد هر واحد (بر حسب دلار) چنين است:
4 3 2 1 ماشين
محصول
7 5 4 4 1
6 5 7 6 2
11 8 10 12 3
زمان لازم (بر حسب ساعت) براي توليد هر واحد محصول در هر ماشين در جدول زير آمده است.
4 3 2 1 ماشين
محصول
2/0 2/0 25/0 3/0 1

25/0 2/0 3/0 2/0 2
5/0 6/0 6/0 8/0 3
فرض كنيد كه 4000، 5000 و 3000 واحد از محصولات مورد نياز است و نيز ماشين ـ ساعت موجود به ترتيب 1500، 1200، 1500 و 2000 باشد. مساله را به صورت يك برنامه خطي فرمول‌بندي كنيد.
حل:
xij: تعداد محصول iام كه توسط ماشين jام بايد توليد گردد.
Min Z: 4x11+ 4x12+ 5x13 +7x14+ 5x23+ 6x24 +12x31+ 10x32+ 8x33+ 11x34
محدوديت زماني هر ماشين:
0.3x11+ 0.2x21+ 0.8x31≤1500
0.25x12+ 0.3x22 +0.6x32≤1200
0.2x13+ 0.2x23+ 0.6x33≤1500
0.2x14+ 0.25x24+ 0.5x34≤2000
محدوديت توليد هر محصول
x11+ x12+x13+x14=4000
x21+ x22 +x23 +x24=5000
x31 +x32 +x33 +x34=3000
xij≥0
i=1, 2, 3, j=1, 2, 3, 4
1-3 حل هندسي مساله‌ها
مثال: مساله برنامه‌ريزي خطي زير را به روش هندسي «ترسيمي» حل كنيد.
Max Z: 3x1+5x2
1) x1≤4
2) 2x2≤12
S.T: 3) 3x1+2x2≤18
4) x¬1≥0
5) x2≥0
Z=3i+5j (/2) 3/2i+5/2j

نقطه A از برخورد 2 و 3:
x2=6
3x1+2x2=18, → x1=2 A=|2, 6 ZA=36
نقطه B از برخورد 1 و 3:
x1=4
3x1+2x2=18, → x2=3 B=|4, 3 ZB=27
نقطه C از برخورد 2 و 4:
x2=6

x1=0 C=|0, 6 ZC=30
نقطه A جواب است.
مثال: مساله برنامه‌ريزي خطي زير را به روش هندسي حل كنيد.
Max Z: 2x1+3x2
1) x1+x2≤2
S.T 2) 4x1+6x2≤9
3) x1, 4) x2≥0

نقطه A از برخورد 2 و 3:
4x1+6x2=9
x1=0 → x2=3/2 A|0, 3/2 ZA=9/2
نقطه B از برخورد 1 و 2
x1+x2=2 → x1=3/2
4x1+6x2=9 → x2=1/2 B|3/2, 1/2 ZB=9/2
نقاط A و B هر دو جواب هستند.

2-1 فضاي اقليدسي

تركيبات خطي
برداي را تركيب خطي از بردارهاي a1, a2, …, ak گوييم هرگاه

به علاوه اين تركيب را به تركيب آنين گويند. اگر علاوه بر موارد بالا داشته باشيم:

زيرفضاي خطي
مجموعه را يك زيرفضاي خطي En گويند اگر:

و همينطور را يك فضاي آنين En گويند اگر:

استقلال خطي بردارها
بردارهاي را مستقل خطي گوييم اگر:

به علاوه بردارها وابسته خطي هستند اگر مستقل نباشند. يعني:

مجموعه مواد
مجموعه كه يك مجموعه مواد براي En را بتوان تركيب خطي از اعضاي مجموعه مولد نوشت.
مثال:

وابسته خطي‌اند:

پايه براي En:
يك پايه براي En مجموعه‌اي از بردارهاي مي‌باشد، به طوري كه:
1. اين مجموعه يك مجموعه مولد باشد.

2. اين مجموعه مستقل خطي باشد.
n = بعد فضاي En 
{تعداد اعضاي پايه}= بعد يك فضا
2-2 ماتريس‌ها
ماتريس An*n را يك ماتريس بالا مثلثي گوييم اگر درايه‌هاي پايين قطر اصلي صفر باشد. همين‌طور پايين مثلثي گوييم اگر درايه‌هاي بالامثلثي قطر اصلي صفر باشد.
بالا مثلثي
پايين مثلثي
ماتريس‌هاي اندازه شده بلوكي

عمليات سطري مقدماتي پله‌كاني:
1. سطح iام را با سطر jام تعويض مي‌كنيم.
2. سطر iام را در اسكالر λ ضرب مي‌كنيم.
3. سطح iام را با سطح iام به علاوه λ سطح jام تعويض مي‌كنيم.
مثال:
دستگاه زير را حل كنيد.

ماتريس معكوس
زماني ماتريس معكوس دارد كه:

مثال
معكوس ماتريس زير را بدست آوريد.

تعريف: ماتريس Am*n مفروض است:
الف) رتبه سطري ماتريس A، تعداد سطرهاي مستقل خطي A مي‌باشد.
ب) رتبه ستوني ماتريس A، تعداد ستون‌هاي مستقل خطي A مي‌باشد.
ج) رتبه ستوني ماتريس A = رتبه سطري ماتريس A = رتبه ماتريس A
Rank A ≤ min{m,n}
ماتريس Am*n را رتبه كامل گويند اگر:
Rank A = min{m,n}
تذك‍ر: دستگاه Am*n=b مفروض است:
الف) اگر rank(A) < rank(A|b) آنگاه دستگا جواب ندارد.
ب) اگر rank(A) = rank (A|b)=n آنگاه دستگاه داراي جواب منحصر به فرد است.
ج) اگر rank(A) = rank (A/b)<n آنگاه دستگاه داراي بي‌نهايت جواب است.
2-3 مجموعه محدب

مجموعه X در En را يك مجموعه محدب گويند اگر به ازاي هر دو نقطه x2, x1 در X به آنگاه به ازاي داشته باشيم:

كه در آن تركيب را يك تركيب محدب گوييم و آن را محدب اكيد مي‌ناميم اگر: .از نظر مهندسي هر نقطه به صورت يك نقطه از پاره خطي است كه x1 را به x2 در En وصل مي‌كند.

مثال:
نشان دهيد مجموعه‌هاي زير محدب هستند.

پس S محدب است.
تعريف نطقه راسي يا گوشه‌اي: يك نقطه x در مجموعه محدب X نقطه راسي گفته مي‌شود. اگر x را نتوان به صورت محدب درآورد، دو نقطه متمايز در X بنويسيم.
X نقطه راسي است اگر:

3-2 جواب‌هاي شدني پايه
سيستم مفروض است كه در آن Rank(A)=rank(A|b)=m. بعد از تغيير ترتيب ستون‌هاي ماتريس A در صورت لزوم فرض كنيد Am*n[B,N] كه در آن Bm*n يك ماتريس معكوس‌پذير باشد. در اين صورت يك جواب دستگاه AX=b است، زيرا:

كه‌ آن را يك جواب پايه‌اي براي دستگاه گوييم. Bm*m را ماتريس پايه و Nm*(n-m) را ماتريس غيرپايه دستگاه گوييم. اگر XB=B-1b≥0 باشد. جواب فوق را يك جواب پايه‌اي شدني گوييم.
حال اگر يكي از مولفه‌هاي XB=B-1b دقيقاً صفر باشد، آن را يك جواب پايه‌اي شدني ----- گوييم.
مثال:

مجموعه محدب زير مفروض است. جواب‌هاي (نقاط) پايه‌اي شدني آن را بدست آوريد.
(ماتريس 4×2 است. بايد دنبال ماتريس 2×2 معكوس‌پذير بگرديم. چون دو تا سطر داريم و دنبال 2 تا ستون مي‌گرديم).


مساله مفروض است، به طوري كه:
rank(A)=rank(A|b)=m.
جواب شدني:
نقطه X را يك جواب شدني براي Lp گوييم اگر در محدوديت‌هاي مساله صدق كند. يعني:

مجموعه نقاط شدني مساله Lp را با S نمايش داده و اگر باشد، آنگاه مساله را شدني گوييم.
جواب بهينه:
جواب شدني X* را يك جواب بهينه براي Lp گوييم اگر:

تعريف:
مساله Lp نامتناهي است، اگر:

تعريف:
مساله Lp را ناشدني گوييم اگر ناحيه جواب آن تهي باشد.

مساله Lp داراي جواب بهينه دگرين است اگر حداقل داراي 2 جواب بهينه باشد.
قضيه
در مساله Lp، اگر جواب شدني وجود داشته باشد، در اين صورت حتماً يك جواب پايه‌اي شدني وجود دارد.
قضيه:
مجموعه نقاط راسي با مجموعه نقاط پايه‌اي شدني متناظر است. اگر مساله Lp شدني باشد، آنگاه مجموعه نقاط راسي (مجموعه نقاط پايه‌اي شدني) ناتهي است.
قضيه:
به ازاي هر نقطه راسي يك جواب پايه‌اي شدني وجود دارد، ولي نه لزوماً منحصر به فرد.
حل مساله Lp:

يعني سطرهاي مستقل خطي باشند.

CBT: ضريب متغيرهاي مربوط به XB
CNT: ضريب متغيرهاي مربوط به XN

(انديس متغيرهاي غيرپايه‌اي)
سود متغير غيرپايه‌اي
تذكر:
1. در مساله‌ي Lp فوق با جواب پايه‌اي شدني كه R مجموعه انديس‌هاي ستون‌هاي غيرپايه‌اي باشد، براي بهتر نمودن مقدار تابع هدف كافي است انديسي از R را پيدا كنيم به طوري كه:

در اين صورت با افزايش متغير xk «متغير غيرپايه‌اي نظير» از روند زير به تكرار بعدي مي‌رويم:

بديهي است اگر انديس k با Zk-Ck>0 مولفه‌هاي بردار yk≤0 باشد.

2. براي مساله Lp با جواب پايه‌اي شدني فرض كنيد تكرار فعلي، بهينه باشد. يعني:

اما اگر انديسي مثل يافت شود يا موجود باشد، به طوري كه Zk-Ck=0 در اين صورت ---- يعني:

به جواب بهينه دگرين رسيده‌ايم.
نكته:

ماتريس پايه جديد در يك ستون با ماتريس قبلي اختلاف دارند.
شرط اينكه ماتريس يك ماتريس پايه جديد باشد اين است كه .
3-3 الگوريتم روش سيمپلكس
گام اول: پايه شدني B داده شده است.
گام دوم: قرار مي‌دهيم: يك جواب پايه‌اي شدني.
گام سوم: قرار مي‌دهيم:
گام چهارم: اگر آنگاه جواب پايه‌اي شدني فعلي بهينه است و توقف كن. در غيراينصورت قرار مي‌دهيم:

گام پنجم: قرار مي‌دهيم اگر اين مقدار پيدا نشده، يعني (yik≤0) مساله Lp نامتناهي است و توقف كن.
تذكر: براي مساله Lp استاندارد با تابع هدف max كافيست گام چهارم را تغيير دهيم.
گام ششم: ماتريس پايه جديد را در B قرار بده و به گام اول ببر.
روش سيمپلكس در جدول.

Z XB XN RHS
1 -CBT -CNT 0
0 B N b

Z xB1… xBr … xBm xj …………xk RHS
1 0 0 0 Zj-Cj Zk-Ck CBTB-1b
0 1 0 0

0 1 0

0 0 1 y1j y1k

yrj yrk

ymj ymk b1

br

bm

پاشنه حتماً بايد يك باشد و بالا و پايين آن حتماً صفر باشد.

مثال:
مساله Lp زير را به روش سيمپلكس حل كنيد.

فرم استاندارد

RHs x1 x2 s1 s2 Z
0 0 0 3 1 1
6

1 2 3 1 0
-1 1 0 1 0
-3 4 0 0 -3 1
3
1 5 0 1 -3
-1 1 0 1 0
-27/5 0 -4 -4/5 -3/5 1
3/5
8/5 1 0 1/5 -3/5
0 1 1/5 2/5 0
چون متغيرهاي سود همه صفر و يا منفي شدند، تكرار بهينه است.
CBT: ضرايب متغيرهاي پايه در تابع هدف
Ci: ضريب xiها در Z.
x1 مقدار
x2 مقدار
s1 مقدار
s2 مقدار

فرم استاندارد

RHs x1 x2 x3 s1 s2 s3 Z
0 -1 -1 4 0 0 0 1
9
2
4 1 1 2 1 0 0
1 1 -1 0 1 0
-1 1 1 0 0 1 0
-16 3 -5 0 0 0 -4 1
1
6
4 3 -1 0 1 0 -2
0 2 0 0 1 0

-1 1 1 0 0 1 0
-17 0 -4 0 -1 0 -2 1
1/3
6
13/3 1 -1/3 0 1/3 0 -2/3
0 2 0 0 1 0
0 2/3 1 1/3 0 1/3 1

Z مقدار
x1 مقدار
x2 مقدار
x3 مقدار

فرم استاندارد

RHs x1 x2 s1 s2 s3 Z
0 -5 -4 0 0 0 1
6
4
15 1 2 1 0 0
-2 1 0 1 0
5 3 0 0 1 0
15 0 -1 0 0 1 1
3
10
3 0 7/5 1 0 -1/5
0 11/5 0 1 2/5
1 3/5 0 0 1/5 0
12/7 0 0 5/7 0 6/7 1
15/7

37/7
12/7 0 1 5/7 0 -1/7
0 0 -11/7 1 5/7
1 0 -3/7 0 2/7 0

Z مقدار
x1 مقدار
x2 مقدار

فرم استاندارد

RHs x1 x2 x3 s1 s2 s3 Z
0 -1 2 -1 0 0 0 1
12
6
9 1 2 1 1 0 0
2 1 -1 0 1 0
-1 3 0 0 0 1 0
3 0 5/2 -3/2 0 1/2 0 1
9
3
12 0 3/2 3/2 1 -1/2 0
1 1/2 -1/2 0 1/2 0
0 7/2 -1/2 0 1/2 1 0
12 0 4 0 1 0 0 1
6
6
15 0 1 1 2/3 -1/3 0
1 1 0 1/3 1/3 0
0 4 0 1/3 1/3 1 0

Z مقدار
x1 مقدار
x2 مقدار
x3 مقدار
تذكر: براي حل مساله Lp با تابع هدف max، روش سيمپلكس دقيقاً مشابه مساله min است، با اين تفاوت كه معيار متغير ورودي به صورت زير تغيير مي‌كند:

4-1 روش دو فازي

فاز I:

فاز II:

هدف ما در اين است كه يك جواب پايه‌اي شدني براي مساله اصلي پيدا كنيم و متغيرهاي مصنوعي را حذف نماييم.
تحليل روش دو فازي
الف) اگر در پايان فاز I متغيرهاي مصنوعي با مقدار صفر باشند، در اين صورت دو حالت زير را داريم:
1. متغيرهاي مصنوعي در پايان فاز I خارج پايه هستند. «غيرپايه‌اي» در اين صورت بدون هيچ مشكل وارد فاز II مي‌شويم.
2. متغيرهاي مصنوعي در پايان فاز I پايه‌اي هستند با مقدار صفر (جواب تباهيده داريم). در اين صورت قبل از اينكه وارد فاز II بشويم، بايد متغيرهاي مصنوعي با مقدار صفر را از پايه توسط متغيرهاي غيرپايه‌اي غيرمصنوعي خارج كنيم. اگر توانستيم اين كار را انجام دهيم (تمام ----- صفر باشند)، قيد را بايد حذف كنيم.
ب) اگر در پايان فاز I متغيرهاي مصنوعي با مقدار غير صفر در پايه بهينه باشد، در اين صورت مساله اصلي ناشدني است. زيرا:
برهان خلف: فرض كنيم مساله اصلي شدني باشد، يعني:

مثال:
مساله Lp زير را به روش فازي حل كنيد.

فرم استاندارد

فاز I:

RHs x1 x2 s1 s2 s3 R1 R2 Z
3 1 2 -1 -1 0 0 0 1
2
1
3 1 1 -1 0 0 1 0
-1 1 0 -1 0 0 1
0 1 0 0 1 0 0 0

1 2 0 -1 1 0 0 -2 1
1
1
2 2 0 -1 1 0 1 -1
-1 1 0 -1 0 0 1
1 0 0 1 1 0 -1 0
0 0 0 0 0 0 -1 -1 1
1/2
3/2
3/2 1 0 -1/2 1/2 0 1/2 -1/2
0 1 -1/2 -1/2 0 1/2 1/2
0 0 1/2 1/2 1 -1/2 -1/2 0

فاز دوم:

RHs x1 x2 s1 s2 s3 R1 R2 Z
-5/2 0 0 1/2 3/2 0 1
1/2
3/2
3/2 1 0 -1/2 1/2 0 1/2 -1/2
0 1 -1/2 -1/2 0 1/2 1/2
0 0 1/2 1/2 1 -1/2 -1/2 0
-4 -3 0 2 0 0 1
1
2
1 2 0 -1 1 0 1 -1
1 1 -1 0 0 1 0

-1 0 1 0 1 -1 0 0
-6 -1 0 0 0 -2 1
2
3
1 1 0 0 1 1 0 -1
0 1 0 0 1 0 0
-1 0 1 0 1 -1 0 0