مقاله مسائل برنامه ریزی خطی با word دارای 111 صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد مقاله مسائل برنامه ریزی خطی با word  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

این پروژه توسط مرکز مرکز پروژه های دانشجویی آماده و تنظیم شده است

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی مقاله مسائل برنامه ریزی خطی با word،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از متن مقاله مسائل برنامه ریزی خطی با word :

به نام خداوند متعال
تحقیق در عملیات 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+6xC150

:محدودیت‌ها
محدودیت مربوط به ماده خام 4xA+4xB+5xC200
محدودیت xA+xB+xC0

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

مرتب کردن: اول تابع هدف و بعد قیدها
7xA+3xB+6xC0
S.T. 4xA+4xB+5xC0
xA, xB, xC0
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
متغیرهای تصمیم xij0
J=1,2,3,…,6 i=1,2
xij: طول کاغذ iام با استفاده از برش jام؛
S1: کاغذی که عرض آن 5dm و مازاد بر نیاز؛
S2: کاغذی که عرض آن 7dm و مازاد بر نیاز؛
S3: کاغذی که عرض آن 9dm و مازاد بر نیاز؛
فرموله کردن مساله:
2xu+4×21+2×22+2×23+2×24-S1=10000
x12+x22+x24+x25-S2=30000
x13+x23+x25+x26-S3=20000
تابع هدف «مینیمم ضایعات»
Min Z: 3×12+ x13+ 3×22+ x23+ x24+ 4×25+ 2×26+5S1+7S2+9S3
مرتب کردن:
Min Z: 3×12+ x13+ 3×22+ x23+ x24+ 4×25+ 2×26+5S1+7S2+9S3
2×11+ 4×21+ 2×22+ 2×23+ x24-S1=10000
S.T. x12+ x22+ x24+ x25-S2=30000
x13+ x23+ x25+ x26-S3=20000

xij0, 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+ x13400
x21+ x22+ x23600
x31+ x32+ x33300

قید مربوط به آب موجود
3×11+ 2×12+x13600
3×21+ 2×22+ x23800
3×31+ 2×32+ x33375
قید مربوط به حداکثر کشت
x11+ x21+ x31600
x12+ x22+ x32500
x13+ x23+ x33325

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

متغیرهای تصمیم:
xA0 A تعداد محصول نوع
xB0 B تعداد محصول نوع
xC0 C تعداد محصول نوع
محدودیت مربوط به پرس:
3xA+5xB 8/60=480
محدودیت مربوط به رنگ‌کاری:
(20xA+15xB)/5 480 4xA+3xB 480
محدودیت مربوط به کار نکردن بیش از نیم ساعت:
|(3xA+5xB)-(4xA+3xB)| 30 |-xA+2xB|30
-xA+2xB30
-xA+2xB-30 *(-) xA-2xB30
xA و xB وابسته به xC = min{xA,xB} xCxA xC-xA0
xCxB 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: 60×1 + 30×2
20×1+15×250000
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: 4×11+ 4×12+ 5×13 +7×14+ 5×23+ 6×24 +12×31+ 10×32+ 8×33+ 11×34
محدودیت زمانی هر ماشین:
03×11+ 02×21+ 08×311500
025×12+ 03×22 +06×321200
02×13+ 02×23+ 06×331500
02×14+ 025×24+ 05×342000
محدودیت تولید هر محصول
x11+ x12+x13+x14=4000
x21+ x22 +x23 +x24=5000
x31 +x32 +x33 +x34=3000
xij0
i=1, 2, 3, j=1, 2, 3, 4
1-3 حل هندسی مساله‌ها
مثال: مساله برنامه‌ریزی خطی زیر را به روش هندسی «ترسیمی» حل کنید.
Max Z: 3×1+5×2
1) x14
2) 2×212
S.T: 3) 3×1+2×218
4) x¬10
5) x20
Z=3i+5j (/2) 3/2i+5/2j

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

x1=0 C=|0, 6 ZC=30
نقطه A جواب است.
مثال: مساله برنامه‌ریزی خطی زیر را به روش هندسی حل کنید.
Max Z: 2×1+3×2
1) x1+x22
S.T 2) 4×1+6×29
3) x1, 4) x20

نقطه A از برخورد 2 و 3:
4×1+6×2=9
x1=0 x2=3/2 A|0, 3/2 ZA=9/2
نقطه B از برخورد 1 و 2
x1+x2=2 x1=3/2
4×1+6×2=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-1b0 باشد. جواب فوق را یک جواب پایه‌ای شدنی گوییم.
حال اگر یکی از مولفه‌های 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 مولفه‌های بردار yk0 باشد.

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

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

به جواب بهینه دگرین رسیده‌ایم.
نکته:

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

گام پنجم: قرار می‌دهیم اگر این مقدار پیدا نشده، یعنی (yik0) مساله 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