مقاله کامل تحقيق در عمليات

به نام خداوند متعال
تحقيق در عمليات 1
مقدمه
برنامه‌ريزي خطي با بهينه‌سازي (ماكزيمم يا مينيمم) يك تابع خطي كه از محدوديت‌هاي مساوي يا نامساوي يا ضمني تشكيل شده است، سروكار دارد. مساله برنامه‌ريزي خطي را ابتدا جرج.بي.دانتزيك در سال 1947 ابداع كرد. اگرچه ال.دي.كانترويچ مساله‌اي از اين نوع كه با سازمان‌دهي و برنامه‌ريزي ارتباط پيدا مي‌كرد را در سال 1939 فرمول‌بندي كرده بود، ولي كار او تا سال 1959 ناشناخته باقي ماند. بنابراين مبتكر اصلي برنامه‌ريزي خطي به طور كلي جرج دانتزيك معرفي شد.
در سال 1949 جرج.بي.دانتزيك «روش سيمپلكس» را براي حل برنامه‌ريزي خطي به چاپ رساند. از آن زمان به بعد افراد زيادي به روش‌هاي بسيار متعددي از جمله بسط و توسعه نظري، ديدگاه محاسباتي و بكارگيري كاربردهاي جديد آن، در اين حوزه وارد شدند. روش سيمپلكس به دلايل:
توانايي مدل‌بندي مسائل مهم و پيچيده مديريتي؛
توانمندي حل مسائل در مدت زمان معقول در برنامه‌ريزي خطي كاربردهاي وسيعي دارد.
مدل‌بندي و مثال‌هاي برنامه‌ريزي خطي
به طول كلي مراحل مهمي كه يك تيم تحقيق در عمليات بايستي طي نمايد، عبارتند از:
تعريف مساله
ساختن مدل
حل مدل
معتبر بودن مدل
اجراي نتيجه‌ نهايي «اتخاذ تصميم»
مهمترين نوع از انواع مدل‌هاي تحقيق در عمليات، مدل رياضي مي‌باشد. در نوشتن اين نوع مدل‌ها، فرض بر اين است كه متغيرها كميت‌پذيرند. بنابراين علائم رياضي را جهت نمايش متغيرها بكار مي‌رود كه بوسيله توابع رياضي به هم مربوط مي‌شود و مدل به وسيله الگوريتم مناسبي حل مي‌شود.
ساختار مدل رياضي
متغيرهاي تصميم
محدوديت‌ها «قيدها»
تابع هدف
انواع مدل‌هاي رياضي كه در «R» (تحقيق در عمليات) استفاده مي‌شود:
مدل برنامه‌ريزي خطي
مدل برنامه‌ريزي پويا
مدل صف
مدل كنترل موجودي‌ها
مدل شبيه‌سازي
برنامه‌ريزي خطي يك مدل رياضي براي تحقيق در عمليات است.
مساله
1. يك كارخانه مي‌خواهد برنامه‌اي براي توليد وسايل آشپزخانه داشته باشد. براي ساختن اين وسايل كارخانه به داده خام و نيروي انساني نيازمند است و مي‌خواهد سه نوع كالا از نوع A, B و C توليد كند. اطلاعات داده شده در جدول زير در اختيار كارخانه مي‌باشد. حداكثر در روز مي‌توان 200 كيلوگرم ماده خام تهيه نموده و حداكثر نيروي انساني موجود 150 نفر ساعت در روز مي‌باشد. مديريت كارخانه مي‌خواهد طوري تصميم بگيرد كه بيشترين سود را داشته باشد. مساله را به صورت برنامه‌ريزي خطي فرموله كنيد.
Max Z=4xA+2xB+3xC: تابع هدف «ماكزيمم سود»
مرتب كردن: اول تابع هدف و بعد قيدها
7xA+3xB+6xC≤0
S.T. 4xA+4xB+5xC≤0
xA, xB, xC≥0
2. يك كارخانه كاغذسازي سه سفارش براي تهيه توپ‌هاي كاغذي «مشابه توپ پارچه» كه طول و عرض آنها در جدول زير داده شده است، دريافت مي‌كند. در اين كارخانه توپ‌هاي كاغذي در دو عرض استاندارد 10 دسي‌متر و 20 دسي‌متر توليد مي‌شود كه بايد به اندازه‌هايي كه در سفارش‌ها مشخص شده، بريده شوند. براي طول توپ‌هاي استاندارد محدوديتي نيست، زيرا از لحاظ علمي، توپ‌هاي با طول محدود مي‌توانند به هم وصل شوند و توپ‌هاي موردنظر را بوجود آورند. به فرم برنامه‌ريزي خطي فرموله كنيد.
حل: هدف عبارت است از تعيين آن طرح برش كه ضمن كمينه ساختن ضايعات برش تقاضاي موردنظر را برآورده سازد.
x12: كاغذ اول برش 2
x21: كاغذ دوم برش 1
متغيرهاي تصميم xij≥0
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
xij≥0, i=1.2, j=1, 2, …, 6
3. كشاورزان يك منطقه زراعي تصميم دارند كه عمليات كاشت، داشت و برداشت را به شكل تعاوني انجام دهند تا از قابليت‌هاي ديگر و امكانات دولتي استفاده كنند و توليد جمعي را افزايش دهند. اين منطقه از سه مزرعه تشكيل شده است. دو عامل زمين و آب امكانات كاشت اين مزارع را محدود مي‌كند كه اطلاعات مربوط به آب و زمين قابل كشت در جدول زير آمده است:
محصولات مناسب كشت در اين منطقه زراعي عبارت است از:
چغندرقند، پنبه و ذرت. ميزان عملكرد در هكتار و آب مورد نياز اين سه محصول با يكديگر متفاوتند. به علاوه براي رسيدن به تركيب مناسب از سه محصول كاشت هم محصول نمي‌توانند از يك مقدار مشخص بيشتر باشد. اين اطلاعات در جدول زير آمده است:
كشاورزان توافق كردند كه نسبت زمين كاشته شده به زمين موجود براي هر سه مزرعه مساوي باشد، اما محدوديتي در مورد تركيب كشت محصولات در هر يك از سه مزرعه وجود ندارد. اكنون مي‌خواهيم با توجه به محدوديت‌هاي فوق، ميزان سود جمعي را ماكزيمم كنيم. مساله را به فرم برنامه‌ريزي خطي فرموله كنيد.
حل:
xij: زمين كاشته شده از محصول iام در مزرعه jام.
تابع هدف:
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
قيد مربوط به آب موجود
3×11+ 2×12+x13≤600
3×21+ 2×22+ x23≤800
3×31+ 2×32+ 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: 60×1 + 30×2
20×1+15×2≤50000
x1 ≤ 1000
x2 ≤ 4000
x1, x2 ≥ 0
6. يك مدير توليد زمان‌بندي سه محصول روي چهار ماشين را برنامه‌ريزي مي‌كند. هر محصول مي‌تواند با هر ماشين توليد شود. هزينه توليد هر واحد (بر حسب دلار) چنين است:
زمان لازم (بر حسب ساعت) براي توليد هر واحد محصول در هر ماشين در جدول زير آمده است.
فرض كنيد كه 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
محدوديت زماني هر ماشين:
0.3×11+ 0.2×21+ 0.8×31≤1500
0.25×12+ 0.3×22 +0.6×32≤1200
0.2×13+ 0.2×23+ 0.6×33≤1500
0.2×14+ 0.25×24+ 0.5×34≤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: 3×1+5×2
1) x1≤4
2) 2×2≤12
S.T: 3) 3×1+2×2≤18
4) x1≥0
5) x2≥0
(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+x2≤2
S.T 2) 4×1+6×2≤9
3) x1, 4) x2≥0
نقطه 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 گويند اگر:

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

فایل : 110 صفحه

فرمت : Word