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

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