دانلود مقاله تحقیق در عملیات

برنامه‌ریزی خطی با بهینه‌سازی (ماکزیمم یا مینیمم) یک تابع خطی که از محدودیت‌های مساوی یا نامساوی یا ضمنی تشکیل شده است، سروکار دارد.

مساله برنامه‌ریزی خطی را ابتدا جرج.بی.دانتزیک در سال 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 در جدول زیر داده شده است: صاحب کارخانه می‌خواهد توازنی روی بار ماشین‌ها داشته باشد.

به این صورت که هیچ کدام از ماشین‌ها، «رنگ‌کاری و پرس» در روز نیم ساعت بیش از دیگر ماشین‌ها کار نکرده باشد.

فرض بر این است که کار انجام شده در ماشین پرس به طور یکنواخت به ماشین‌های دیگر برای رنگ‌کاری داده می‌شود.

هدف مدیر کارخانه در مدت 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, x2 ≥ 0 6.

یک مدیر تولید زمان‌بندی سه محصول روی چهار ماشین را برنامه‌ریزی می‌کند.

هر محصول می‌تواند با هر ماشین تولید شود.

هزینه تولید هر واحد (بر حسب دلار) چنین است: زمان لازم (بر حسب ساعت) برای تولید هر واحد محصول در هر ماشین در جدول زیر آمده است.

فرض کنید که 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) x1≥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 مجموعه‌ای از بردارهای می‌باشد، به طوری که: این مجموعه یک مجموعه مولد باشد.

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

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

همین‌طور پایین مثلثی گوییم اگر درایه‌های بالامثلثی قطر اصلی صفر باشد.

بالا مثلثی پایین مثلثی ماتریس‌های اندازه شده بلوکی عملیات سطری مقدماتی پله‌کانی: سطح iام را با سطر jام تعویض می‌کنیم.

سطر iام را در اسکالر λ ضرب می‌کنیم.

سطح 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) = rank (A|b)=n آنگاه دستگاه دارای جواب منحصر به فرد است.

ج) اگر rank(A) = rank (A/b) 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 (اندیس متغیرهای غیرپایه‌ای) سود متغیر غیرپایه‌ای تذکر: در مساله‌ی Lp فوق با جواب پایه‌ای شدنی که R مجموعه اندیس‌های ستون‌های غیرپایه‌ای باشد، برای بهتر نمودن مقدار تابع هدف کافی است اندیسی از R را پیدا کنیم به طوری که: در این صورت با افزایش متغیر xk «متغیر غیرپایه‌ای نظیر» از روند زیر به تکرار بعدی می‌رویم: بدیهی است اگر اندیس k با Zk-Ck>0 مولفه‌های بردار yk≤0 باشد.

برای مساله Lp با جواب پایه‌ای شدنی فرض کنید تکرار فعلی، بهینه باشد.

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

نکته: ماتریس پایه جدید در یک ستون با ماتریس قبلی اختلاف دارند.

شرط اینکه ماتریس یک ماتریس پایه جدید باشد این است که .

3-3 الگوریتم روش سیمپلکس گام اول: پایه شدنی B داده شده است.

گام دوم: قرار می‌دهیم: یک جواب پایه‌ای شدنی.

گام سوم: قرار می‌دهیم: گام چهارم: اگر آنگاه جواب پایه‌ای شدنی فعلی بهینه است و توقف کن.

در غیراینصورت قرار می‌دهیم: گام پنجم: قرار می‌دهیم اگر این مقدار پیدا نشده، یعنی (yik≤0) مساله Lp نامتناهی است و توقف کن.

تذکر: برای مساله Lp استاندارد با تابع هدف max کافیست گام چهارم را تغییر دهیم.

گام ششم: ماتریس پایه جدید را در B قرار بده و به گام اول ببر.

روش سیمپلکس در جدول.

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

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

فرم استاندارد چون متغیرهای سود همه صفر و یا منفی شدند، تکرار بهینه است.

CBT: ضرایب متغیرهای پایه در تابع هدف Ci: ضریب xiها در Z.

x1 مقدار x2 مقدار s1 مقدار s2 مقدار فرم استاندارد Z مقدار x1 مقدار x2 مقدار x3 مقدار فرم استاندارد Z مقدار x1 مقدار x2 مقدار فرم استاندارد Z مقدار x1 مقدار x2 مقدار x3 مقدار تذکر: برای حل مساله Lp با تابع هدف max، روش سیمپلکس دقیقاً مشابه مساله min است، با این تفاوت که معیار متغیر ورودی به صورت زیر تغییر می‌کند: 4-1 روش دو فازی فاز I: فاز II: هدف ما در این است که یک جواب پایه‌ای شدنی برای مساله اصلی پیدا کنیم و متغیرهای مصنوعی را حذف نماییم.

تحلیل روش دو فازی الف) اگر در پایان فاز I متغیرهای مصنوعی با مقدار صفر باشند، در این صورت دو حالت زیر را داریم: متغیرهای مصنوعی در پایان فاز I خارج پایه هستند.

«غیرپایه‌ای» در این صورت بدون هیچ مشکل وارد فاز II می‌شویم.

متغیرهای مصنوعی در پایان فاز I پایه‌ای هستند با مقدار صفر (جواب تباهیده داریم).

در این صورت قبل از اینکه وارد فاز II بشویم، باید متغیرهای مصنوعی با مقدار صفر را از پایه توسط متغیرهای غیرپایه‌ای غیرمصنوعی خارج کنیم.

اگر توانستیم این کار را انجام دهیم (تمام ----- صفر باشند)، قید را باید حذف کنیم.

ب) اگر در پایان فاز I متغیرهای مصنوعی با مقدار غیر صفر در پایه بهینه باشد، در این صورت مساله اصلی ناشدنی است.

زیرا: برهان خلف: فرض کنیم مساله اصلی شدنی باشد، یعنی: مثال: مساله Lp زیر را به روش فازی حل کنید.

فرم استاندارد فاز I: فاز دوم: فرم استاندارد فاز I فاز II فرم استاندارد مقدار سطر صفر در فاز I: فاز I: بنا به قسمت الف-2 تحلیل روش دوفازی قید R3 حذف می‌شود.

فرم استاندارد فاز I: متغیر مصنوعی در پایان فاز I با مقدار غیرصفر بهینه است.

یعنی Lp ناشدنی است.

فرم استاندارد فاز I: فاز II: فرم استاندارد فاز I: متغیر مصنوعی در پایان فاز I با مقدار غیرصفر بهینه است، یعنی Lp ناشدنی است.

4-2 روش M بزرگ M یک عدد خیلی بزرگ است که به سمت +∞ میل می‌کند، چون مساله ما min است، پس باید Xa از پایه حذف شود تا Z=min شود.

آنالیز روش M بزرگ حالت الف-1) اگر مساله P(M) (M بزرگ) دارای جواب بهینه (X*, X*a=0) باشد، «یعنی تمام متغیرهای مصنوعی در تکرار بهینه صفر باشند» در این صورت جواب، جواب بهینه مساله اصلی (Lp) است.

حالت الف-2) اگر مساله P(M) دارای جواب بهینه (X*, X*a≠0) باشد، «یعنی حداقل یکی از متیغیرهای مصنوعی در تکرار بهینه مخالف صفر باشد»، در این صورت مساله اصلی ناشدنی است.

حالت ب-1) اگر مساله P(M) نامتناهی باشد، به طوری که در تکرار مذکور حداقل یک متغیر مصنوعی مخالف صفر در پایه باشد، در این صورت مساله اصلی ناشدنی است.

حالت ب-2) اگر مساله P(M) نامتناهی باشد، به طوری که در تکرار مذکور تمام متغیرهای مصنوعی صفر باشد، در این صورت مساله اصلی نامتناهی است.

مثال: مساله Lp را به روش M بزرگ حل کنید.

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

پس Lp نامتناهی است.

فرم استاندارد فرم استاندارد x"2 وارد شونده است، ولی خارج شونده نداریم.

بنابراین P(M) بی‌کران (نامتناهی) است، چون R1=0.

بنابراین مساله اولیه نیز نامتناهی است.

4-3 دور در فرآیند سیمپلکس قاعده مند دوری «بلاند» جهت ممانعت از دور در یک سیمپلکس (Bland) در این روش ابتدا متغیرها را به دلخواه در یک دنباله مرتب می‌کنیم.

به این ترتیبکه از بین تمام متغیرهای غیرپایه‌ای وارد شونده متغیری که کوچکترین اندیس را دارد، به عنوان متغیر ورودی انتخاب می‌کنیم و به طریق مشابه از بین تمام متغیرهای کاندید خروجی که از آزمون مینیمم کسرها بدست می‌آید.

آن متغیری انتخاب می‌شود که کمترین اندیس را دارد.

مثال مساله Lp زیر را به روش قاعده بلاند حل کنید.

فرم استاندارد 5-1 تعریف دوگان در حالت متعارفی دوگان Dual مساله اولیه Primal مثال: دوگاه مساله‌های زیر را حساب کنید.

تعریف دوگان در حالت استاندارد تعریف دوگان در حالت متعارفی و استاندارد معادل هم است، یعنی با قبول کردن یکی، دیگری را می‌توان به راحتی اثبات کرد.

مثال: دوگاه مسائل زیر را حساب کنید.

قضیه 5-1: دوگان دوگان یک مساله، خودش می‌باشد.

اثبات: دوگان معادل () ترانهاد دوگان معادل ( ترانهاده روابط اولیه و دوگان مسائل زیر مفروضند: قضیه 5-2 (قضیه ضعیف دوگانی) اگر uo, xo به ترتیب جواب‌های شدنی مساله D, p باشند، در این صورت: اثبات: نتیجه 5-1: قضیه میزان اگر uo, xo جواب‌های شدنی مساله اولیه و دوگان باشند، به طوری که ، در این صورت uo, xo به ترتیب جواب‌های بهینه اولیه و دوگان هستند.

اثبات: برای هر شدنی داریم: (طبق قضیه ضعیف دوگانی) شدنی شدنی → جواب بهینه مساله اصلی xo شدنی شدنی → جواب بهینه مساله دوگان uo نتیجه 5-2: اگر یکی از مسائل اولیه یا دوگان نامتناهی باشد، آنگاه دیگری ناشدنی است.

اثبات: بدون از دست دادن کلیت مساله، فرض کنیم مساله اولیه نامتناهی باشد.

در این صورت ثابت می‌کنیم دوگان ناشدنی است.

فرض خلف: فرض کنیم دوگان شدنی باشد، یعنی uo جواب شدنی آن است.

در این صورت طبق قضیه ضعف دوگانی داریم: شدنی این با فرض نامتناهی بودن مساله اولیه در تناقض است.

بنابراین فرض خلف باطل و حکم برقرار است.

قضیه 5-3 (قضیه دوگانی): اگر یکی از مسائل اولیه یا دوگان دارای جواب بهینه باشد، در این صورت مساله دیگر نیز دارای جواب بهینه بوده و مقادیر تابع هدف آنها به ازای جواب بهینه برابر است.

اثبات: فرض کنیم مساله اولیه دارای جواب بهینه باشد: با استفاده از روش سیمپلکس مساله اولیه را حل می‌کنیم و به جواب بهینه می‌رسیم (در تعداد تکرار متناهی)، در این صورت اگر ماتریس B ماتریس پایه جواب بهینه باشد، در این صورت ثابت می‌کنیم: جواب بهینه مساله دوگان است.

از اینکه B ماتریس پایه تکرار بهینه است، داریم: و این یعنی یک جواب شدنی برای مساله اولیه دوگان می‌باشد.

مقدار تابع هدف دوگان: مقدار تابع مساله اولیه به ازای جواب بهینه که بنا به قضیه میزان، جواب بهینه مساله دوگان است.

قضیه 5-4: قضیه اساسی دوگانی با توجه به مسائل اولیه و دوگان، یکی از گزاره‌های زیر درست است: الف) هر دو مساله دارای جواب بهینه با مقدار تابع هدف برابر هستند.

(اگر یکی از مسائل اولیه یا دوگان شدنی و دارای جواب بهینه باشد، بنا به قضیه دوگانی دیگری نیز شدنی و دارای جواب بهینه است).

ب) یکی از مسائل نامتناهی است، در حالی که دیگری ناشدنی است.

(اگر یکی از مسائل اولیه یا دوگان نامتناهی باشد، بنا به نتیجه 5-2 دیگری نیز ناشدنی است).

ج) هر دو ناشدنی است.

(اگر یکی از مسائل اولیه یا دوگان ناشدنی باشد، بنابراین دیگری نیز ناشدنی یا نامتناهی می‌باشد و اگر ناشدنی باشد، حالت ج اتفاق می‌افتد).

قضیه 5-5: قضیه مکمل زائد اگر xo و uo جواب‌های شدنی مسائل اولیه دوگان باشند، در این صورت بهینه هستند اگر و فقط اگر: یکی از سه شرط فوق برقرار است.

اثبات: فرض کنید I برقرار باشد، در این صورت: با توجه به تغییر به نتیجه 5-1، جواب بهینه هستند.

اثبات عکس: فرض کنیم جواب بهینه مسائل اولیه و دوگان باشند، در این صورت بنا به قضیه 5-3 داریم: شدنی، بنابراین در دوگان صدق می‌کند: نتیجه 5-3: نتیجه قضیه مکمل زائد قضیه 5-6: قضیه کروش ـ کان تاکر «kkt» سیستم زیر مفروض است.

x* یک جواب بهینه برای مساله فوق می‌باشد.

اگر و تنها اگر: مثال 5-3: مساله زیر را با استفاده از قضیه مکمل زائد حل کنید.

نقطه A محل برخورد 1 و 4: جواب بهینه دوگان نقطه B محل برخورد 4 و 6: جایگذاری A* در قید دوگان: جواب بهینه برای مساله اولیه: نقطه A از برخورد 1و 3: نقطه B از برخورد 1 و5: جایگذاری A* در قید دوگان: جواب بهینه برای مساله اولیه: 5-2: سیمپلکس دوگان: فرض کنید تکرار اول در سیمپلکس دارای سطر صفر منفی و مقادیر سمت راستش نیز منفی باشد.

مساله (Min): RHs «XN» «XB» xm+1 … xk … xj … xn اگر خارج شونده داشته باشیم و وارد شونده نداشته باشیم، مساله اولیه ناشدنی در نتیجه مساله دوگان نامتناهی است.

الگوریتم سیمپلکس دوگان: گام 1: یک پایه B برای مساله اولیه پیدا می‌کنیم به طوری که «اگر مساله max بود، ».

گام 2: اگر یعنی به جواب بهینه مساله اولیه رسیده‌ایم و توقف کن.

در غیراینصورت: «که xr به عنوان متغیر خارج شونده انتخاب شده».

گام 3: اگر یعنی دوگان نامتناهی و مساله اولیه ناشدنی پس توقف کن.

در غیراینصورت: «که xk به عنوان وارد شونده» اگر مساله max بود، در اینصورت: گام 4: در yrk صعودگیری کنید و به گام 2 برگردید.

مثال 5-4: با سیمپلکس دوگان حل کنید.

فرم استاندارد فرم استاندارد تذکر: فرض کنید در حل یک مساله Lp از نوع minسازی به تکراری رسیدیم که مقادیر سطر صفر همگی کمتر مساوی صفر نبوده و مقادیر سمت راست همگی مثبت نباشد.

تکرار فوق نه اولیه شدنی و نه دوگان شدنی است.

در این صورت از روشزیر استفاده می‌کنیم: با افزودن محدودیتی به فرم فوق به مساله، تعداد محدودیت‌های مساله به m+1 تا می‌رسد که در این صورت جدول سیمپلکس به فرم زیر است: RHs «XN» «XB» xm+1 … xk … xnsn+1 اندیس k از این رابطه بدست می‌آید: در تکرار بعدی متغیر xk (دارای مثبت‌ترین سود) را وارد نموده و sn+1 را خارج می‌کنیم.

این کار باعث می‌شود که در تکرار بعدی سطر صفر سنتی شده و جدول برای سیمپلکس دوگان آماده است.

مراحل سیمپلکس را انجام داده و به یکی از سه حالت زیر می‌رسیم: حالت 1: خارج شونده داریم، ولی وارد شونده نداریم.

در اینصورت دوگان نامتناهی و مساله اولیه ناشدنی است.

حالت 2: به جواب بهینه برسیم با sn+1>0 در اینصورت جواب فوق برای مساله اولیه بهینه است.

حالت 3: به جواب بهینه برسیم با sn+1>0 در اینصورت: 3-1: اگر سود sn+1 صفر باشد، جواب فوق بهینه است.

3-2: در غیراینصورت سود منفی باشد، مساله اولیه نامتناهی و دوگان ناشدنی است.

مثال 5-5 مساله زیر را به روش سیمپلکس دوگان حل کنید.

فرم استاندارد فرم استاندارد مساله اول نامتناهی و دوگان ناشدنی است.

5-3: تحلیل حساسیت فرض کنید مساله زیر را حل کردید و به جواب بهینه رسیدید و در تکرار آخر متوجه شدید که یکی از ضرایب را اشتباه وارد کردید.

در این صورت داریم: 1.

ضرایب تابع هدف: الف) ضرایب تابع هدف برای متغیرهای غیرپایه‌ای غیرپایه‌ایj: تفاضل را بدست می‌آوریم و به مقدار سطر سود اضافه می‌کنیم.

اگر کماکان منفی بود، جواب فعلی، جواب بهینه است.

در غیراینصورت (مثبت باشد)، همان را به عنوان وارد شونده درنظر می‌گیریم و روند سیمپلکس مساله تغییریافته را حل می‌کنیم.

ب) ضرایب تابع هدف برای متغیرهای پایه‌ای: مثال 5-6: مساله Lp زیر مفروض است.

تکرار اول و بهینه آن داده شده است: الف) ضرایب x2 در تابع هدف از -1-2 تغییر یافته چون مساله max است و کماکان مثبت هستند، پس همین جواب بهینه برای مساله تغییر یافته است.

ب) ضریب x2 در تابع هدف از -12 تغییر یافته.

ج) ضریب x1 در تابع هدف از 14 تغییر یافته د) ضریب x1 در تابع هدف از 1-2 تغییر یافته ه‍( ضریب x2 در تابع هدف از -13 و ضریب x1 در تابع هدف از 1-2 تغییر یافته.

2.

تغییرات سمت راست b b' مقادیر سمت راست و Z تغییر می‌کند.

اگر همین تکرار بهینه است، در غیراینصورت اگر آن را سیمپلکس دوگان حل می‌کنیم.

مثال 5-7: مساله Lp زیر مفروض است که تکرار نهایی آن داده شده است.

با تحلیل حساسیت حالت‌های زیر را حل کنید.

الف) ب) بنابراین همان تکرار نهایی بهینه است با: ج) 3.

تغییرات ستون A الف) ستون‌های غیرپایه‌ای: ب) ستون‌های پایه‌ای: وقتی یک ستون پایه‌ای عوض می‌شود، کل جدول تغییر می‌کند.

سیمپلکس معمولی: به عنوان پاشنه انتخاب می‌شود:‌ روش M بزرگ :‌ سطر صفر یک متغیر مصنوعی اضافه نموده: سیملپکس دوگان سمت راست منفی به عنوان پاشنه انتخاب می‌شود: .

مثال 5-8 مساله Lp و تکرار بهینه آن داده شده است.

با استفاده از تحلیل حساسیت مسائل زیر را حل کنید.

الف) ب) الف) ب) الف) وارد شونده داریم، ولی خارج شونده نداریم.

بنابراین Lp نامتناهی است.

ب) الف) وارد شونده داریم، ولی خارج شونده نداریم.

ب) 4.

اضافه کردن یک قید ماتریس پایه جدید سودهای جدید با اضافه کردن یک قید، مقادیر سود تغییر نمی‌کند.

مقدار تابع هدف: مقادیر سمت راست: اگر *≥0 باشد، جواب فعلی بهینه است، در غیراینصورت اگر منفی باشد، روش سیمپلکس دوگاه را ادامه می‌دهیم.

مثال 5-9: 1.

مساله Lp و جواب بهینه آن داده شده است اگر قید اضافه کنیم، مساله را با تحلیل حساسیت حل کنید.

مساله برنامه‌ریزی خطی زیر و جدول آخر آن را درنظر بگیرید: الف) با استفاده از تحلیل حساسیت، جواب بهینه جدید را وقتی ضریب x2 در تابع هدف از 1 به 6 تغییر داده شده، پیدا کنید.

ب) فرض کنید ضریب x2 در اولین محدودیت از تغییر داده شود، با استفاده از تحلیل حساسیت جواب بهینه جدید را پیدا کنید.

ج) فرض کنید محدودیت به مساله اضافه شود با استفاده از تحلیل حساسیت جواب بهینه جدید را پیدا کنید.

5-4 برنامه‌ریزی پارامتری با درنظر گرفتن ضرایب تابع هدف و مقادیر سمت راست مساله Lp به صورت پارامتر خطی می‌توان یک مساله برنامه‌ریزی پارامتری ساخت، به طوری که: الف) مثال 5-10: مساله پارامتری زیر را حل کنید.

فرم استاندارد سودهای جدید: در شماره 1 به ازای ، s1 می‌تواند وارد شود: در شماره 2 به ازای ، s2 مثبت نمی‌شود، پس نمی‌تواند وارد شونده باشد.

اگر باشد، سطح صفر عوض می‌شود، مثل جدول زیر: چون ضریب λ منفی است، نمی‌تواند به عنوان ورودی انتخاب شود.