برنامه‌ريزي خطي

منظور از اثرات مستقيم، همان ضرايب عليت يا ضريب همبستگي جزئي هر صفت با عملكرد در صورت ثابت بودن صفات ديگر است. در جدول ۳ مجموع اثرات مستقيم و غيرمستقيم در هر يك از رديف‌هاي جدول برابر ضريب همبستگي صفت با عملكرد خواهد بود. در بين پنج صفت طول برگ پرچم، عرض برگ پرچم، طول پانيكول، پانيكول تا رسيدگي و تعداد دانه در پانيكول، بيشترين ضريب همبستگي بر روي عملكرد مربوط به تعداد دانه در پانيكول با ۹۰۶/۰ بود.

كمترين ضريب همبستگي بر روي عملكرد مربوط به طول برگ پرچم با ۴۳۴/۰ به خود اختصاص داده بود. بيشترين اثر مستقيم را بر روي عملكرد، تعداد دانه در پانيكول با ۷۲۴/۰ داشت. كمترين اثر مستقيم را بر روي عملكرد، عرض برگ پرچم با ۱۶۴/۰- داشت.

بيشترين اثر غيرمستقيم طول برگ پرچم از طريق تعداد دانه در پانيكول است و بين تعداد دانه در پانيكول با طول برگ پرچم ارتباط مثبتي وجود دارد، يعني با افزايش تعداد در پانيكول، طول برگ پرچم بيشتر و باعث شده كه عملكرد افزايش يابد. بيشترين اثر غيرمستقيم عرض برگ پرچم از طريق تعداد دانه در پانيكول بدست آمده است. لذا با افزايش تعداد دانه در پانيكول، عرض برگ پرچم بيشتر و در نهايت سبب افزايش عملكرد شد.
اين مورد با نتايج ضرايب همبستگي مطابقت دارد، چرا كه ضريب همبستگي صفات عرض برگ پرچم و تعداد دانه در پانيكول ۵۰۲/۰ است. بيشترين اثر غيرمستقيم طول پانيكول از طريق تعداد دانه در پانيكول بوده. بنابراين با افزايش تعداد دانه در پانيكول، طول پانيكول بيشتر و عملكرد بيشتر گرديد.

اين مورد نيز با نتايج ضرايب همبستگي مطابقت دارد، زيرا ضريب همبستگي صفات طول پانيكول و تعداد دانه در پانيكول ۶۱۱/۰ است. بيشترين اثر غيرمستقيم پانيكول تا رسيدن از طريق تعداد دانه در پانيكول بوده است، اما با افزايش تعداد دانه در پانيكول، پانيكول تا رسيدگي كمتر و نيز سبب كاهش عملكرد شد. اين مورد نيز همچون گذشته با نتايج ضرايب همبستگي مطابقت دارد، چرا كه ضريب همبستگي پانيكول تا رسيدگي و تعداد دانه در پانيكول ۴/۰- است. بيشترين اثر غيرمستقيم تعداد دانه در پانيكول، از طريق پانيكول تا رسيدگي بود.
تمرين
۱-۱ يك كارخانه خوراك دام براي گاو، گوسفند و طيور خود خوراك تهيه مي‌كند. اين خوراك با تركيب مواد اصلي زير تهيه مي‌شود: ذرت، سنگ آهك، دانه سويا و پودر ماهي. اين مواد شامل تركيبات مغذي زير است: ويتامين‌ها، پروتئين، كلسيم و چربي خام. ميزان اين تركيبات در هر كيلوگرم از مواد اصلي در جدول زير خلاصه مي‌شود:

مواد مغذي
مواد اصلي ويتامين‌ها پروتئين كلسيم چربي خاك
ذرت ۸ ۱۰ ۶ ۸
سنگ آهك ۶ ۵۴ ۱۰ ۶
دانه سويا ۱۰ ۱۲ ۶ ۶
پودر ماهي ۴ ۸ ۶ ۹

كارخانه براي توليد ۱۰، ۶ و ۸ تن (در واحد متريك) خوراك گاو، گوسفند و طيور قرارداد بسته است. به دليل كمبود، مقدار محدودي از مواد، يعني ۶ تن ذرت، ۱۰ تن سنگ آهك، ۴ تن دانه سويا و ۵ تن پودر ماهي موجود است. قيمت هر كيلوگرم از اين مواد به ترتيب ۲۰/۰، ۱۲/۰، ۲۴/۰ و ۱۲/۰ دلار است. حداقل و حداكثر واحدهاي تركيبي مواد مختلف مغذي در هر كيلوگرم خوراك گاو، گوسفند و طيور در جدول زير خلاصه شده است:

مواد مغذي
ويتامين‌ها پروتئين كلسيم چربي خاك
توليد حداقل حداكثر حداقل حداكثر حداقل حداكثر حداقل حداكثر
خوراك گاو ۶
۶
۷
۴ ۸

خوراك گوسفند ۶
۶
۶
۴ ۶

خوراك طيور ۴ ۶ ۶
۶
۴ ۶
اين مساله را طوري فرمول‌بندي كنيد كه كل هزينه مينيمم شود.

۱-۲ كاركنان فني يك بيمارستان تصميم دارند سيستم غذايي، كامپيوتري آن بيمارستان را توسعه دهند. ابتدا برنامه غذايي ناهار را بررسي مي‌كنند. برنامه غذايي ناهار به سه گروه اصلي تقسيم مي‌شود: سبزيجات، گوشت و دسر. در هر سفارش حداقل يك سرويس از هر گروه تقاضا مي‌شود. هزينه هر سرويس از اقلام پيشنهادي به علاوه تركيبات هيدروكربن‌ها، ويتامين‌ها، پروتئين‌ها و چربي در جدول زير خلاصه مي‌شود:

هيدروكربن‌ها ويتامين‌ها پروتئين‌ها چربي‌ها هزينه سرويس (دلار)
سبزيجات
نخود ۱ ۳ ۱ ۰ ۱۰/۰
نخود فرنگي ۱ ۵ ۲ ۰ ۱۲/۰
باميه ۱ ۵ ۱ ۰ ۱۳/۰
ذرت ۲ ۶ ۱ ۲ ۰۹/۰
ماكاروني ۴ ۲ ۱ ۱ ۱۰/۰

برنج ۵ ۱ ۱ ۱ ۰۷/۰
گوشت
مرغ ۲ ۱ ۳ ۱ ۷۰/۰
گوشت گاو ۳ ۸ ۵ ۲ ۲۰/۱
ماهي ۳ ۶ ۶ ۱ ۶۳/۰

دسر
پرتقال ۱ ۳ ۱ ۰ ۲۸/۰
سيب ۱ ۲ ۰ ۰ ۴۲/۰
پودينگ ۱ ۰ ۰ ۰ ۱۵/۰
ژله ۱ ۰ ۰ ۰ ۱۲/۰
فرض كنيد كه حداقل هيدروكربن‌ها، ويتامين‌ها، پروتئين‌ها و چربي‌هاي مورد نياز در هر وعده غذا به ترتيب ۵، ۱۰، ۱۰ و ۲ است.
الف) مساله برنام غذايي را به صورت برنامه‌ريزي خطي فرمول‌بندي كنيد.
ب) بسياري از جنبه‌هاي واقعي اين مدل ناديده گرفته شده است. اين جنبه‌ها شامل برنامه‌ريزي صبحانه، ناهار و شام با هم، برنامه‌ريزي هفتگي كه در آن انواع غذاها استفاده شود و برنامه غذايي ويژه بيماران، رژيم غذايي خاص، در مورد اينكه چگونه مي‌توانيم اين جنبه‌ها را در يك سيستم ويژه غذايي جامع تلفيق كنيم. به تفضيل بحث كنيد.

۱-۳ مساله تعيين مكان نصب يك ماشين جديد را در يك خط توليد شامل چهار ماشين درنظر بگيريد. اين ماشين‌ها در مختصات x1, x2 زير تعبيه شده‌اند:

فرض كنيد مختصات ماشين جديد است. مساله يافتن بهترين مكان نصب ماشين جديد را در هر يك از حالت‌هاي زير به صورت برنامه خطي فرمول‌بندي كنيد.
الف) مجموع تفاضل ماشين جديد از چهار ماشين مينيمم است، فاصله خياباني را بكار ببريد، مثلاً فاصله نقطه از ماشين اول |x1-3|+|x2| است.

ب) به علت وجود جريان‌هاي مختلف مابين ماشين جديد و ماشين‌هاي قبلي مساله را وقتي مجموع فواصل وزين مينيمم مي‌شود، تجديد فرمول كنيد، به طوري كه اوزان متناظر با چهار ماشين به ترتيب ۵، ۷، ۳ و ۱ باشد.
ج) براي جلوگيري از تراكم ماشين‌ها، فرض كنيد بخواهيم ماشين جديد در مربع نصب كنيم. قسمت‌هاي الف و ب را با اين محدوديت اضافه فرمول‌بندي كنيد.
د) فرض كنيد بخواهيم ماشين را طوري نصب كنيم كه فاصله آن از ماشين اول از ۲/۳ بيشتر نشود و مساله را با اين محدوديت اضافي فرمول‌بندي كنيد.
۱-۴ مساله پرتاب يك راكت به ارتفاع ثابت b در زمان مفروض T را كه كمترين مقدار سوخت را مصرف مي‌كند، درنظر بگيريد. فرض كنيد u(t) قدرت شتاب فرار راكت و y(t) ارتفاع آن در زمان t باشد. مساله را مي‌توان چنين فرمول‌بندي كرد:

كه در آن g نيروي شتاب ثقل و y مشتق دوم ارتفاع y است. مساله را به شكل گسسته بنويسيد و آن را به صورت يك برنامه خطي فرمول‌بندي كنيد. به ويژه مساله را در T=10 و g=32 و b=15 فرمول‌بندي كنيد (راهنمايي: انتگرال با مجموع سره و مشتقات را با معادلات تفاضلي عوض كنيد. تغيير متغير |uj|=xj را اعمال كنيد و توجه كنيد كه xi≥-uj, xi≥uj ).

۱-۵ شركتي مي‌خواهد براي دو فقره از توليداتش با توجه به تقاضاهاي فصلي براي مدت ۱۲ ماه برنامه‌ريزي كند. تقاضاي ماهيانه فقره يك صد هزار واحد در طول ماه‌هاي اكتبر، نوامبر و دسامبر، ده هزار واحد در طول ماه‌هاي ژانويه، فوريه، مارس و آوريل. سي‌ هزار واحد در طول ماه‌هاي باقيمانده. تقاضاي فقره ۲ در طول ماه‌هاي اكتبر تا فوريه ۵۰۰۰۰ واحد و ۱۵۰۰۰ واحد در طول ماه‌هاي باقيمانده است. فرض كنيد كه هزينه توليد فقرخ ۱ و ۲، به ترتيب ۵ و ۸ دلار است،

به شرطي كه آنها قبل از ماه ژوئن توليد شده باشند. بعد از ماه ژوئن، به علت اصلاح سيستم توليد، هزينه دو فقره به ۵/۴ و ۷ دلار كاهش مي‌يابد. تعداد كل اقلام توليدي فقره ۱ و ۲ هر ماه در فاصله زماني بين ماه‌هاي ژانويه ـ سپتامبر حداكثر ۱۲۰۰۰۰ و بين ماه‌هاي اكتبر ـ دسامبر حداكثر ۱۵۰۰۰۰ است. علاوه بر اين، هر واحد از فقره ۱ دو فوت مكعب و هر واحد فقره ۲ چهار فوت مكعب از فضاي انبار را اشغال مي‌كند. فرض كنيد كه ماكزيمم فضاي انبار كه به اين دو فقره مي‌توان اختصاص داد، ۱۵۰۰۰۰ فوت مكعب است و هزينه نگهداري هر فوت مكعب در طول ماه ۱/۰ دلار است. مساله زمانبندي توليد را طوري فرمول‌بندي كنيد كه كل هزينه و انبارداري مينيمم شود.

۱-۶ يك كارخانه نساجي پنج نوع پارچه توليد مي‌كند. تقاضا (بر حسب هزار يارد) در طول سه ماه سال براي اين نوع پارچه به ترتيب ۱۶، ۴۸، ۲۱ و ۸۲ است. اين پنج نوع پارچه پس از بافت و دسته‌بندي در بازار هر يارد به ترتيب به قيمت ۹/۰، ۸/۰، ۸/۰، ۲/۱ و ۶/۰ دلار فروخته مي‌شود. علاوه بر توليد و بسته‌بندي در خود كارخانه، پارچه‌ها از خارج كارخانه نيز خريداري مي‌شود و قبل از فروش در خود كارخانه بسته‌بندي مي‌شود. اگر پارچه‌هاي بسته‌بندي نشده از خارج كارخانه خريداري شوند، هزينه پنج نوع پارچه هر يارد ۸/۰، ۷/۰، ۷۵/۰، ۹/۰ و ۷/۰ دلار است. اگر در خود كارخانه توليد شود، هر يارد به ترتيب ۶/۰، ۵/۰، ۶/۰، ۷/۰ و ۳/۰ دلار هزينه برمي‌دارد. دو نوع دستگاه در كارخانه وجود دارد كه مي‌توانند پارچه توليد كند. يعني ۱۰ دستگاه Dobbie و ۸۰ دستگاه عادي. ميزان توليد هر دستگاه Dobbie در ساعت براي پنج پارچه به ترتيب ۶/۴، ۶/۴، ۲/۵، ۸/۳ و ۲/۴ يارد است. دستگاه عادي به همان ميزان دستگاه Dobbie توليد دارد،

فقط پارچه‌اي نوع ۳، ۴ و ۵ را مي‌تواند توليد كند. با فرض اينكه كارخانه هفت روز هفته و هر روز هم ۲۴ ساعت كار مي‌كند، مساله برنامه‌ريزي بهينه براي برآورد تقاضاي بازار براي سه ماه در سال را به صورت خطي فرمول‌بندي كنيد. آيا فرمول‌بندي شما يك مساله حمل و نقل است؟ اگر نه، مساله را به صورت يك مساله حمل و نقل دوباره فرمول‌بندي كنيد.

۱-۷ شخصي ۲۲۰۰ دلار را مي‌خواهد در پنج سال آينده سرمايه‌گذاري كند. در شروع هر سال او مي‌تواند پولش را براي يك دوره يك ساله يا دو ساله به حساب بگذارد. بانك ۸ درصد سود به ازاي هر سال سپرده و ۱۷ درصد (در كل) براي دو سال سپرده مي‌پردازد. به علاوه، شركتي براي سه سال سود تضميني پيشنهاد مي‌كند كه شروع آن در شروع سال دوم است. اين تضمين شامل ۲۷ درصد (در كل) است و اگر اين شخص موجودي‌اش را هر سال سرمايه‌گذاري كند، يك برنامه خطي ارائه دهيد تا به او نشان دهد چگونه بايد سرمايه‌گذاري كند تا در سال پنجم پول نقدش ماكزيمم گردد.

۱-۸ يك كارخانه فولادسازي تيرآهن به شكل I را در چهار اندازه كوچك، متوسط، بزرگ و خيلي بزرگ توليد مي‌كند. هر يك از ماشين‌هاي B, A و C مي‌تواند اين تيرآهن‌ها را توليد كند. طول تيرآهن‌هاي توليدي توسط ماشين‌ها در هر ساعت چنين خلاصه مي‌شود:
تيرآهن ماشين
A B C
كوچك ۳۰۰ ۶۰۰ ۸۰۰
متوسط ۲۵۰ ۴۰۰ ۷۰۰
بزرگ ۲۰۰ ۳۵۰ ۶۰۰
خيلي بزرگ ۱۰۰ ۲۰۰ ۳۰۰

با فرض اينكه از هر ماشين تا ۵۰ ساعت در هفته مي‌توان استفاده كرد و نيز هزينه هر ساعت كار اين ماشين‌ها، به ترتيب ۳۰، ۵۰ و ۸۰ دلار است. علاوه بر اين با فرض اينكه ۱۰۰۰۰، ۸۰۰۰، ۶۰۰۰ و ۶۰۰۰ فوت از اندازه‌هاي مختلف تير I در هر هفته لازم است. مساله زمان‌بندي ماشين را به صورت برنامه‌ريزي خطي فرمول‌بندي كند.

۱-۹ يك شركت دو نوع پنير توليد مي‌كند: پنير سوئيسي و پنير تند. شركت ۶۰ كارگر مجرب دارد و مي‌خواهد تعداد نيروي كار خود را به ۹۰ كارگر در طول ۸ هفته آينده افزايش دهد. هر كارگر مجرب مي‌تواند سه كارگر تازه استخدام جديد را در يك دوره ۲ هفته‌اي آموزش دهد كه در طول اين مدت كارگران آموزش دهنده چيزي توليد نمي‌كنند. توليد ۱۰ پوند پنير سوئيسي يك ساعت و توليد ۶ پوند پنير تند نيز يك ساعت وقت مي‌گيرد. يك هفته كاري چهل ساعت است. تقاضاي هفتگي (بر حسب ۱۰۰۰ پوند) چنين خلاصه مي‌شود:

نوع پنير هفته
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸
پنير سوئيسي ۱۲ ۱۲ ۱۲ ۱۶ ۱۶ ۲۰ ۲۰ ۲۰
پنير تند ۸ ۸ ۱۰ ۱۰ ۱۲ ۱۲ ۱۲ ۱۲
فرض كنيد هر كارگر كارآموز همان حقوق كارگر مجرب را دريافت كند. علاوه بر اين، فرض كنيد تاريخ مصرف پنيرها يك هفته باشد. شركت چگونه بايد دستمزد بپردازد و نيروهاي جديد را آموزش دهد تا هزينه دستمزدها كمترين شود؟ مساله را به صورت برنامه خطي فرمول‌بندي كند.

۱-۱۰ يك ميله فولادي به طول ۳۶ اينچ داريم و با كمك يك دستگاه برش مي‌خواهيم قطر آن را از ۱۴ اينچ به ۱۲ اينچ برسانيم. x1 سرعت دوراني (دور در دقيقه)، x2 سرعت عمقي (اينچ در دقيقه) و x3 سرعت طولي‌ (اينچ در دقيقه) كميت‌هاي موردنظر هستند كه بايد مشخص شوند. مدت زمان برش با رابطه داده مي‌شود. تراكم و فشار كنارز وارد بر دستگاه برش به ترتيب با رابطه ۳۰×۱+۴۰۰۰×۲ و ۴۰×۱+۶۰۰۰×۲+۶۰۰۰×۳ پوند بر اينچ مربع است. درجه حرارت تيغه برش بر حسب فارنهايت (x2+x3)150+x15/0+200 است. ماكزيمم تراكم، فشار كناري و درجه حرارت مجاز به ترتيب ۱۵۰۰۰۰ و ۱۰۰۰۰۰ هر اينچ مربع و ۸۰۰ درجه فارنهايت است

. مي‌خواهيم سرعت (كه بايد در فاصله ۶۰۰ تا ۸۰۰ دور در هر دقيقه باشد)، عمق برش و طول برشرا تعيين كنيم، به طوري كه زمان برش مينيمم شود. براي بكارگيري يك مدل خطي تقريب زير ارائه مي‌شود. چون مينيمم است، اگر و فقط اگر x2x3 ماكزيمم باشد، تابع هدف با ماكزيمم مينيمم x2 و x3 جايگزين مي‌كنيم. مساله را به صورت يك مدل خطي فرمول‌بندي كنيد و درستي تقريب بكار رفته در تابع هدف را بررسي كنيد.

۱-۱۱ پالايشگاهي مي‌تواند دو نوع نفت خريداري كند: نفت خام سفيد و نفت خام سنگين. هزينه هر بشكه به ترتيب ۱۱ و ۹ دلار است. محصول گازوئيل، نفت سفيد و سوخهت هواپيماي توليدي از هر بشكه مطابق جدول زير است:
گازوئيل نفت سفيد سوخت هواپيما
نفت خام سفيد ۴/۰ ۲/۰ ۳۵/۰
نفت خام سنگين ۳۲/۰ ۴/۰ ۲/۰

قابل توجه است كه در هنگام فرآيند پالايش به ترتيب ۵ و ۸ درصد آنها هدر مي‌رود. پالايشگاه براي تحويل ۱ ميليون بشكه گازوئيل، ۴۰۰۰۰۰ بشكه نفت سفيد و ۲۵۰۰۰۰ بشكه سوخت هواپيما قراردادي امضا كرده است. مساله يافتن تعداد بشكه‌هاي دو نوع نفت خاك را براي برآوردن تقاضا و مينيمم‌سازي كل هزينه به صورت يك مدل خطي فرمول‌بندي كنيد.
۱-۱۲ شركتي مونتاژ محصولي را برعهده دارد كه شامل قاب، ميله فلزي و بلبرينگ است. شركت ميله فلزي و قاب را خود توليد مي‌كند، اما بلبرينگ را از توليد كننده ديگري خريداري مي‌كند. هر ميله فلزي بايد مراحل ماشين‌ سندان، ماشين تراش و ماشين تيزكن را بگذارند.

اين مراحل به ترتيب ۵/۰، ۲/۰ و ۳/۰ ساعت براي هر ميله فلزي وقت‌ مي‌گيرد. هر قاب ۸/۰ ساعت در ماشين سندان، ۱/۰ ساعت در ماشين تيزكن، ۲۰ ماشين سندان، ۳ ماشين سوراخ‌كن و ۶ آسياب دارد. با فرض اينكه هر ماشين ماكزيمم ۲۴۰۰ ساعت در هر سال كار مي‌كند، مساله يافتن ماكزيمم تعداد مولفه‌هاي محصول توليدي مونتاژ را به صورت يك مدل خطي فرمول‌بندي كنيد .

۱-۱۳ يك شركت توليد كننده تلويزيون تصميم دارد تلويزيون‌هاي سياه و سفيد رنگي توليد كند. ارزيابي بازار نشان مي‌دهد كه حداكثر مي‌توان ۱۰۰۰ تلويزيون رنگي و ۴۰۰۰ تلويزيون سياه و سفيد در ماه فروش داشت. ماكزيمم تعداد نفر ـ‌ ساعت موجود در هر ماه ۵۰۰۰۰ است. يك تلويزيون رنگي ۲۰ نفر ـ ساعت و يك تلويزيون سياه و سفيد ۱۵ نفر ـ ساعت وقت مي‌گيرد. سود حاصل از تلويزيون‌هاي رنگي و سياه و سفيد به ترتيب ۶۰ و ۳۰ دلار است. مي‌خواهيم تعداد تلويزيون‌هايي را پيدا كنيم كه شركت بايد از هر نوع توليد كند تا سود آن ماكزيمم شود. مساله را فرمول‌بندي كنيد.