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

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

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