فصل اول
(مقدمه و تعاریف)

مقدمه
برنامه ریزی خطی(LP) ابزاری برای حل مسائل بهینه سازی است.
در سال 1947، جورج دانتزیگ یک روش کارا به نام الگوریتم سیمپلکس برای حل مسائل برنامه ریزی خطی (که LP نیز نامیده می شود)توسعه داد.با توسعه الگوریتم سیمپلکس،LP برای مسائل بهینه سازی گوناگونی مانند بانکداری،آموزش،فعالیت های جنگی،نفت و حمل و نقل کامیون ها استفاده شده است.در یک ارزیابی انجام شده از 500 شرکت بزرگ دنیا،85% آنها از برنامه ریزی خطی استفاده کرده اند.
به طور کلی می توان گفت در یک مسئله برنامه ریزی ریاضی که تصمیم گیرنده مایل است به منظور بیشینه یا کمینه کردن تابع هدفی تصمیم گیرد می تواند از برنامه ریزی خطی استفاده کند که این مسئله برای مدیران بسیار حائز اهمیت است.





















چکیده

برنامه ریزی خطی یکی از مسائل مهم و پرکاربرد در ریاضیات ، مدیریت و... است که اکثرا دانشجویان کارشناسی در مهندسی صنایع ، تحقیق در عملیات ، روش های مقداری ، رشته های مرتبط با مدیریت و بازرگانی و ... با آن سر و کار دارند .
از آنجایی که برنامه ریزی خطی مسئله ای مهم است در این مقاله به توضیح این مقوله می پردازیم و بعضی از کاربردهای آن را با مثال بیان می کنیم و نرم افزارهای مفیدی را در این زمینه برای بهره مندی بیشتر معرفی می کنیم .
در واقع هدف من در این مقاله معرفی بیشتر برنامه ریزی خطی همراه با مثال برای درک بهتر این موضوع و نیز بیان بعضی از کاربرد های آن در زندگی است.










تاریخچه
مسئلهٔ حل مجموعه‌ای ازنامعادلات خطی از زمان فوربه مطرح بوده‌است. برنامه‌ریزی خطی (LP) به عنوان یک مدل ریاضی در زمان جنگ جهانی دوم شکل گرفت تا خرج‌ها و بازگشت‌های مالی را طوری سامان بخشد که به کاهش هزینه‌های ارتش و افزایش خسارات دشمن بینجامد. این طرح تا سال1947 سری باقی ماند. پس از جنگ، بسیاری از صنایع به استفاده‌ از آن پرداختند. پایه‌گذاران این حوزه جورج دانتزیگ منتشرکنندهٔ روش سیمپلکس در سال1947 ،جان نیومن مطرح‌کننده نظریه دو گانگی در همان سال، و لئونید کانتروویچ ریاضیدان روس که از تکنیک‌های مشابهی پیش از دانتزینگ استفاده کرد ونوبل سال 1957 را برد هستند. نخستین بار در سال 1979 لئونید خاچیان نشان داد که مسئله‌ برنامه‌ریزی خطی در مرتبه زمانی چند جمله ای قابل حل است. اما پیشرفت اساسی‌تر زمانی حاصل شد که نراندرا کارمارکار یک روش نقطه داخلی جدید برای حل این مسائل معرفی کرد. مثال دانتزینگ برای منتصب کردن هفتاد نفر به هفتاد شغل متمایز کارآمدی برنامه‌ریزی خطی را به نمایش می‌گذارد. توان محاسباتی لازم برای آزمودن همهٔ جایگشت های ممکن این مسئله بسیار بالاست. این تعداد از تعداد ذرات موجود در عالم بیشتر است، با این حال، پیدا کردن پاسخ بهینه با تبدیل مسئله به یک مسئله برنامه‌ریزی خطی و حل آن با روش سیمپلکس تنها لحظاتی طول می‌کشد.



تعاریف
در این فصل مطالب لازم که در بقیه مقاله مورد نیاز است را به طور خلاصه وار بیان می کنیم.مباحثی که تحت پوشش این فصل قرار می گیرند برای مطالب بعدی مقاله در زمینه برنامه ریزی خطی مورد استفاده خواهند گرفت.
مجموعه محدب:مجموعه نقاط s یک مجموعه محدب را تشکیل می دهند اگر پاره خطی که هر دو نقطه از s را به هم وصل می کند تماما در s باشد.



تابع هدف:در هر مسئله برنامه ریزی خطی تابعی که باید بیشینه یا کمینه شود را تابع هدف گوییم.
نامعادلات خطی:به ازای هر تابع خطی ) ( fو هر عدد b،نامعادلات ذیل خطی هستند:
و

ضریب تابع هدف:ضریب یک متغیر در تابع هدف ضریب تابع هدف متغیر نامیده می شود.
ضریب تکنولوژی:ضریب متغیرهای تصمیم در محدودیت ها، ضریب تکنولوژی نام دارد چون اغلب منعکس کننده تکنولوژی مورد استفاده برای تولید محصولات مختلف هستند.
محدودیت فعال:محدودیتی فعال است که سمت چپ و راست آن محدودیت به ازای مقادیر بهینه متغیرهای تصمیم،برابر باشند.
محدودیت غیر فعال: محدودیتی غیر فعال است که سمت چپ و راست آن محدودیت به ازای مقادیر بهینه متغیرهای تصمیم،برابر نباشند.
سمت راست محدودیت:عدد سمت راست هرمحدودیت سمت راست محدودیت (rhs) نامیده می شود معمولا rhs مربوط به یک محدودیت،میزان منابع در دسترس را نشان می دهد.
آزاد در علامت:اگر یک متغیر بتواند یک مقدار مثبت یا منفی یا صفر فرض شود می گوییم متغیر آزاد در علامت که به اختصار به آن urs می گوییم.
جواب:کلیه مقادیری که متغیر های تصمیم اختیار می کند به تنهایی یک جواب محسوب می شود.
جواب موجه : جوابی است که در تمام محدودیت ها صدق می کند.
جواب غیر موجه :کلیه مقادیری که خارج از منطقه موجه قرار دارند.
جواب بهینه :جوابی است که به ازای آن مقدار تابع هدف مطلوب ترین و بهینه ترین وضعیت خود را داراست. ( برای تابع هدف ماکسیمم ، جواب هایی که تابع را حد اکثر و برای مینیمم ، حداقل کنند)به عبارتی دیگر هر یک از جواب های بهینه مشخص می کند که از هر متغیر تصمیم چه تعداد (مقدار ) تخصیص یابد تا تابع هدف ماکسیمم یا مینیمم شود.
جواب های بهینه اصلی ترین هدف تشکیل مدل برنامه ریزی خطی است.
جواب های بهینه مدل برنامه ریزی خطی ، ممکن است انواع مختلفی داشته باشند که به شرح ذیل بیان می گردد....
الف : جواب بهینه چند گانه داشته باشد:
ممکن است بیش از یک جواب موجه مقدار تابع هدف را مطلوب ترین نماید که در این صورت همه ی آنها جواب بهینه خواهند بود
ب : فاقد جواب بهینه باشد :
در این حالت مدل،جواب بهینه ندارد و این در واقعیت امکان پذیر نیست ، در چنین صورتی باید مجددا مسئله را فرموله و حل نماییم.
ج: ناحیه جواب ، بی کران باشد:
چنانچه با این حالت مواجه شویم باید بر مشاهده و تعریف مدل بازنگری کنیم که قطعا اشتباهی رخ داده و باید رفع شود .
منطقه موجه :ناحیه ای از جواب های موجه است که در همه محدودیت ها صادق است.
تابع خطی:تابع بر حسب یک تابع خطی است اگر و فقط اگر برای بعضی مجموعه های ثابت رابطه ذیل برقرار باشد:


برنامه‌ریزی خطی: یا همان بهینه‌سازی خطی، روشی در ریاضیات است که به پیدا کردن مقدار کمینه یا بیشینه از یک تابع خطی روی یک چند ضلعی محدب می‌پردازد. این چندضلعی محدب در حقیقت نمایش نموداری تعدادی محدودیت از نوع نامعادله روی متغیر های تابع است. به بیان ساده‌تر به وسیله برنامه‌سازی خطی می‌توان بهترین نتیجه (مثلاً بیشترین سود یا کمترین هزینه) را در شرایط خاص و با محدودیت‌های خاص به دست آورد.
محل اصلی استفاده برنامه‌ریزی خطی در اقتصاد است، اما در مهندسی نیز کاربردهای فراوانی دارد. می‌توان گفت حدود یک‌چهارم کل محاسبات علمی که بر روی رایانه انجام گرفته‌است، به برنامه‌ریزی خطی و مشتقات آن مربوط می‌شود.















فصل دوم
(کلیات)

برای توضیح برنامه ریزی خطی،مبحث را با یک مثال آغاز می کنیم.
شرکت منبت کاری گیاپتو دو نوع اسباب بازی چوبی می سازد:
سرباز و قطار.یک سرباز 27 دلار فروش می رود و 10 دلار ماده خام مصرف می کند.ساخت هر سرباز منجر به هزینه متغیر نیروی انسانی و سربار 14 دلار می شود.یک قطار 21 دلار فروش می رود و 9 دلار ماده خام مصرف می کند.ساخت هر قطار،منجر به هزینه متغیر نیروی انسانی و سربار 10 دلار می شود.ساخت قطارها و سربازهای چوبی دو نوع مهارت نیاز دارد:نجاری و پرداخت،یک سرباز به 2ساعت نیروی انسانی برای پرداخت و1 ساعت نیروی انسانی برای نجاری نیاز دارد.یک قطار به 1 ساعت نیروی انسانی برای پرداخت و 1 ساعت نیروی انسانی برای نجاری نیاز دارد.هر هفته،گیاپتو می تواند مدت 100 ساعت برای پرداخت و 80 ساعت برای نجاری صرف کند.تقاضای هفتگی برای قطار ها محدودیتی ندارد اما تقاضای هفتگی برای سرباز ها حداکثر برابر 40 است.
گیاپتو می خواهد سود(درآمد منهای هزینه)هفتگی را بیشینه کند،یک مدل ریاضی می سازیم که بیانگر وضعیت گیاپتو بوده و بتوان از آن برای بیشینه کردن سود هفتگی استفاده کرد.
در ابتدا مشخصه هایی را که در همه مسائل برنامه ریزی خطی مشترک است،معرفی می کنیم. متغیر های تصمیم:در هر مدل برنامه ریزی خطی،متغیر های تصمیم باید به طور کامل بیانگر تصمیم گرفته شده،باشند.به طور واضح،گیاپتو باید تصمیم بگیرد که در هر هفته چند سرباز و قطار ساخته شود.با این تفکر متغیر های تصمیم را به صورت ذیل تعریف می کنیم:
:تعداد سرباز های تولید شده در هر هفته
:تعداد قطار های تولید شده در هر هفته
تابع هدف:در مسئله گیاپتو می دانیم که هزینه های ثابت(مانند اجاره و بیمه) به مقادیر وابسته نیست.بنابراین گیاپتو می تواند روی بیشینه سازی
(سایر هزینه های متغیر)-(هزینه خرید مواد اولیه)-(درآمدهای هفتگی)
تمرکز کند.
درآمد و هزینه های هفتگی گیاپتو بر حسب متغیر های تصمیم قابل بیان است.
برای این شرکت مطلوب نیست بیش از تعداد سربازی که خریداری می شود،تولید کند بنابر این فرض می کنیم که همه اسباب بازی های تولید شده،به فروش می رسد،پس داریم:
درآمد هفتگی قطارها+درآمد هفتگی سربازها =درآمدهای هفتگی
(هفته/تعداد قطارها)(قطار/دلار)+(هفته/تعداد سربازها)(سرباز/دلار)=
همچنین عبارات ذیل برقرارند:
= هزینه های هفتگی مواد خام
= سایر هزینه های هفتگی متغیر
پس گیاپتو می خواهدعبارت ذیل را بیشینه کند:

بیشینه کردن را می توان به طریق دیگر نیز بررسی نمود:

سهم قطار در سود هفتگی+هزینه های غیر ثابت هفتگی-سهم سرباز در سود هفتگی=درآمد هفتگی
(هفته/تعداد قطارها)(قطار/سهم سود)+(هفته/تعدادسربازها)(سرباز/سهم سود)=
همچنین داریم:
سرباز/سهم سود
قطار/سهم سود
پس مانند قبل بدست می آوریم:

هزینه های غیر ثابت هفتگی-درآمدهای هفتگی
بنابراین هدف گیاپتو انتخاب به نحوی است که و بیشینه گردد.
متغیر z را برای نمایش تابع هدف هر LP به کار می گیریم . تابع هدف گیاپتو عبارت است از :
بیشینه کردن
ضریب تابع هدف:ضریب در تابع هدف برابر 3 و ضریب در تابع هدف برابر 2 است . در این مثال ( و بسیاری از مسائل ) ضریب تابع هدف برای هر متغیر ، همان مشارکت (سهم) متغیر در سود شرکت است .
محدودیت ها : با افزایش تابع هدف گیاپتو نیز بزرگتر می شود .به عبارت دیگر ، اگر گیاپتو برای انتخاب هر مقدار آزاد بود ، می توانست با انتخاب مقادیر بسیار بزرگ ،به سود مطلوب بسیار بزرگی دست یابد .متأسفانه ،مقادیر محدود هستند و سه محدودیت ذیل وجود دارد :
محدودیت 1: در هر هفته ، نباید بیش از 100 ساعت وقت برای پرداخت صرف شود .
محدودیت 2: در هر هفته ، نباید بیش از 80 ساعت وقت برای نجاری صرف شود .
محدودیت 3: به دلیل تقاضای محدود ، حداکثر تولید سرباز در هر هفته ، نباید از 40 بیشتر شود .
میزان مواد خام موجود ، بی نهایت فرض شده است؛ بنابراین ،محدودیتی به وجود نمی آورد .
قدم بعد در فرموله کردن یک مدل ریاضی برای مسئله گیاپتو این است که محدودیت های 1 تا 3 ، بر حسب بیان شوند .
برای بیان محدودیت 1 بر حسب ، توجه کنید که رابطه ذیل برقرار است ؛
+ (هفته/تعداد سربازها)(سرباز/ساعات پرداخت) = هفته / کل ساعات پرداخت
(هفته/تعداد قطارها)(قطار/ساعات پرداخت )
(1)
اکنون محدودیت 1 را می توان به صورت ذیل بیان کرد ،
(2)
توجه داشته باشید که واحد کدام از اجزای رابطه (2) ، تعداد ساعات پرداخت در هفته است . برای اینکه یک محدودیت قابل توجیه باشد ،همه اجزای آن باید دارای واحد یکسان باشند . در غیر این صورت ، سیب با پرتقال جمع شده است و این محدودیت معنی دار نخواهد بود .
برای بیان محدودیت 2 بر حسب ، توجه کنید که داریم:
+ (هفته/تعداد سربازها)(سرباز/ساعات نجاری) = هفته/کل ساعات نجاری
(هفته/تعداد قطارها)(قطار/ساعات نجاری)

پس محدودیت 2 را می توان به صورت ذیل بیان کرد ،
(3)

دوباره توجه داشته باشید که واحد هرکدام از اجزای رابطه (3) ، یکسان هستند (مانند تعداد ساعات نجاری در هفته ).
سرانجام ، با بیان این واقعیت که حداکثر 40 سرباز در هفته خریداری می شود ، تولید سربازها باید به حداکثر 40 سرباز محدود شود .
این محدودیت به صورت ذیل بیان می گردد ؛
(4)
در مسئله گیاپتو ، به وضوح روابط برقرارند. در مسائل دیگر ممکن است بعضی از متغیرها urs باشند . برای مثال ، اگر نشان دهنده توازن نقدینگی در یک شرکت باشد ، می تواند منفی باشد و این در صورتی است که بدهکاری های شرکت بیش از پول در دسترس آن باشد ؛ در این مورد ، مناسب است که در دسته urs باشد.
با ترکیب محدودیت های علامت و ، تابع هدف (1) و محدودیت های (2) تا (4) ، مدل بهینه سازی ذیل نتیجه می شود :
(1) ( تابع هدف )
s.t. با توجه به
(2) (محدودیت پرداخت)
(3)( محدودیت نجاری)
(4)(محدودیت تقاضا برای سربازان)
(5)(محدودیت علامت)
(6)( محدودیت علامت)
با توجه به(s.t.) به این معنی است که مقادیر متغیرهای تصمیم باید همه محدودیت ها و همچنین محدودیت های علامت را شامل شود.
پس با توجه به این مطالب برایمان ثابت شد که مسئله گیاپتو یک مسئله برنامه ریزی خطی است زیرا هم تابع هدف گیاپتو یک تابع خطی از است و هم محدودیت های گیاپتو نامعادلات خطی هستند.
هم اکنون به ادامه حل مسئله توجه کنید:
در این مسئله نقطه در ناحیه موجه قرار دارد.
توجه داشته باشید که و محدودیت های(2) تا (4) و محدودیت های علامت (4) و (5) را شامل می شود ؛
محدودیت (2) ، را شامل می شود ،چون برقرار است .
محدودیت (3) ، را شامل می شود ،چون برقرار است .
محدودیت (4) ، را شامل می شود ، چون برقرار است .
محدودیت (5) ، را شامل می شود ، چون برقرار است .
محدودیت (6) ، را شامل می شود ، چون برقرار است .
از سوی دیگر نقطه در ناحیه موجه قرار ندارد زیرا روابط(2)،(4)،(5)و(6) را شامل می شود اما رابطه (3) را نقض می کند(چون 15+70 کوچکتر یا مساوی 80 نیست.)پس این نقطه یک نقطه ی غیر موجه است و به عنوان مثال دیگر می توان نقطه غیر موجه را در نظر گرفت که چون محدودیت علامت(6) را نقض می کند غیر موجه است.
در این مسئله مجموعه طرح های امکان پذیر که باید برای یافتن طرح تولید بهینه در نظر گرفته شود ر واقع همان ناحیه موجه است که در این سوال فقط یک نقطه در ناحیه موجه است که آن نقطه،نقطه ی است زیرا مقدار تابع هدف برای این جواب به صورت زیر است:

پس وقتی جواب بهینه مسئله گیاپتو است که هیچ نقطه دیگری در ناحیه موجه با مقدار تابع هدفی بیش از 180 وجود نداشته باشد.
گیاپتو با ساخت 20 سرباز و 60 قطار در هر هفته می تواند سود خود را بیشینه کند که در این صورت سود هفتگی برابر 180 دلار منهای هزینه های ثابت هفتگی می شود برای مثال اگر تنها هزینه ثابت گیاپتو،هفته ای 100دلار برای اجاره باشد،سود هفتگی او به دلار برابر 80=100-180 خواهد بود.
حل ترسیمی مسائل برنامه ریزی خطی با دو متغیر
هر LP با تنها دو متغیر ، به صورت ترسیمی قابل حل است .متغیرها را با و محورهای مختصات را نیز به صورت محور مشخص می کنیم . فرض کنید می خواهیم نموداری ترسیم کنیم که مجموعه نقاط آن ، رابطه ذیل را شامل شود ،
(7)
همان مجموعه نقاط ،این رابطه را نیز شامل می شود ،

نامعادله اخیر به صورت ذیل قابل بازنویسی است ،
(
روی نمودار (به شکل 1 مراجعه کنید) وقتی به طرف پایین حرکت می کنیم ، کاهش می یابد و مجموعه نقاطی که (7)و( را شامل می شود در زیر یا دقیقا روی خط قرار می گیرند . این مجموعه نقاط در شکل صفحه بعد با سایه تیره تر نمایش داده شده است . توجه داشته باشید که همه خطوط ، و یکسان هستند .به طور مشابه ، مجموعه نقاطی که را شامل می شود در بالای خط قرار می گیرند که این نقاط در شکل صفحه بعد با سایه روشن تر نشان داده شده اند.




نکته قابل ذکر این است که :
یک محدودیت به شکل نامعادله خطی یا را در نظر بگیرید.در حالت کلی می توان نشان داد که در دو بعد،مجموعه نقاطی نامعادله را در بر می گیرد که شامل نقاطی روی خط به اضافه کلیه نقاط یک سمت خط است.
یک راه ساده برای تشخیص آن سمت خط که نامعادله های یا را شامل شود،وجود دارد:
یک نقطه P که خط را شامل نمی شود ،انتخاب کنید.بررسی کنید که آیا P نامعادله را شامل می شود . در این صورت همه نقاط یک سمت خط که P در آن واقع شده است نیز نامعادله را شامل می شود . اگر P نامعادله را شامل نشود ، آنگاه همه نقاط سمت دیگر خط که P را در برنمی گیرد ،نامعادله را شامل می شود . برای مثال ،جهت تصمیم گیری در مورد معادله ، توجه کنید که (0و0) در این نامعادله صدق نمی کند .از آنجا که (0و0) در زیر خط واقع شده است ، کلیه نقاطی که را شامل شود ، در بالای خط قرار دارند .این موضوع با شکل 1 تطابق دارد .
یافتن ناحیه موجه
حال چگونگی حل مسئله گیاپتو را به صورت ترسیمی تشریح می کنیم . برای شروع ، باید بر روی نمودار ، ناحیه موجه مسئله گیاپتو را مشخص می کنیم .ناحیه موجه این مسئله ، مجموعه نقاط است که نامعادلات ذیل را شامل می شود ؛
(2) (محدودیت ها )
(3)
(4)
(5) ( محدودیت های علامت )
(6)
برای اینکه نقطه در ناحیه موجه واقع شود ، باید در همه نامعادلات (2) تا (6) صدق کند . توجه داشته باشید نقاطی که در (5)و(6) صدق می کنند ، فقط در ربع اول صفحه واقع می شوند . این امر در شکل 2 به وسیله پیکان هایی نمایش یافته است که به طرف راست محور و بالای محور اشاره می کنند . بنابراین ، هر نقطه ای که خارج از ربع اول باشد، نمی تواند در ناحیه موجه واقع شود ، یعنی ناحیه موجه ، مجموعه نقاطی از ربع اول است که در روابط (2) تا (4) صدق کنند .




روش تعیین مجموعه نقاط صادق در نامعادله خطی ، نقاطی را مشخص می کند که در (2) تا (4) صدق کنند . در شکل (2) می بینیم که نامعادله (2) با همه نقاط زیر خط AB یا منطبق بر آن ( خط AB ، است ) شامل می شود . نامعادله (3) با همه نقاط زیر خط CD یا منطبق بر آن ( خط CD ، است) شامل می شود . سرانجام ، نامعادله (4) با همه نقاط زیر خط EF یا منطبق بر آن ( خط EF ، است) شامل می شود . (سمتی از خط که یک نامعادله را شامل می شود ، در شکل 2 به وسیله پیکان هایی نشان داده شده است .)
طبق شکل 2 ، مجموعه نقاط ربع اول که (2)،(3)و(4) را شامل شود با پنج ضلعی DGFEH احاطه شده است . هر نقطه روی این چند ضلعی یا داخل آن ،در ناحیه موجه قرار دارد . هر نقطه دیگر ، حداقل یکی از نامعادلات (2) تا (6) را شامل نمی شود . برای مثال ، نقطه (30و40) غیر موجه است چون (2) را نقض می کند .
یک راه ساده برای یافتن ناحیه موجه ، تعیین مجموعه نقاط غیرموجه است . توجه کنید که در شکل 2 ، همه نقاط بالای خط AB غیرموجه هستند ، زیرا (2) را نقض می کنند . به طور مشابه ، همه نقاط بالای خط CD غیرموجه هستند ،زیرا (3) را نقض می کنند. همچنین، همه نقاط بالای خط EF غیرموجه هستند ،زیرا (4) را نقض می کنند .پس از حذف این نقاط ، ناحیه موجه ( DGFEH ) حاصل می شود .
یافتن جواب بهینه
با داشتن ناحیه موجه مسئله گیاپتو، اکنون جواب بهینه را جستجو می کنیم . جواب بهینه ، نقطه ای در ناحیه موجه است که در آن تابع هدف دارای بزرگترین مقدار خواهد بود . برای یافتن جواب بهینه ، به رسم خطی نیاز است که همه نقاط آن دارای مقادیر یکسان Z باشند . در یک مسئله بیشینه سازی ، چنین خطی یک خط هم سود ( در یک مسئله کمینه سازی ، خط هم هزینه ) نامیده می شود . برای رسم یک خط هم سود ،نقطه ای در ناحیه موجه را انتخاب کرده و Z آن را محاسبه کنید .فرض کنید (0و2) انتخاب شود . به ازای (0و2) ، مقدار محاسبه می شود . بنابراین (0و2) روی خط هم سود قرار می گیرد. با نوشتن معادله به صورت ، می بینیم که این خط هم سود دارای شیب است (خط هم سود ). از آنجا که همه خطوط هم سود به شکل مقدار ثابت هستند ، همه آنها دارای شیب یکسان هستند . این موضوع بدین معنی است که اگر یک خط هم سود رسم کنیم ، می توانیم همه خطوط هم سود را با حرکت به موازات خط هم سود رسم شده ، پیدا کنیم .
اکنون واضح است که چگونه می توان جواب بهینه یک LP با دو متغیر را پیدا کرد. بعد از اینکه یک خط هم سود رسم کردید ، سایر خطوط هم سود را با حرکت به موازات آن در جهت افزایش z ( در یک مسئله بیشینه سازی ) ، تولید کنید . بعد از رسیدن به یک نقطه، خطوط هم سود اشتراکی با ناحیه موجه نخواهند داشت . آخرین اشتراک خط هم سود ( محل تماس) با ناحیه موجه، بزرگترین مقدارz را در ناحیه موجه خواهد داشت که جواب بهینه LP خواهد بود . در این مسئله تابع هدف با حرکت در جهت افزایش و ، افزایش می یابد. بنابراین، با حرکت به موارات خط در جهت شمال شرقی ، به خطوط هم سود دیگری می رسیم . در شکل 2 می بینیم خط هم سودی که از G عبور می کند ،آخرین خط هم سودی است که با ناحیه موجه اشتراک دارد . بنابراین ، G نقطه ای از ناحیه موجه با بزرگترین مقدار z و جواب مسئله گیاپتو است . توجه داشته باشید نقطه G تنها جایی است که خطوط و اشتراک دارند . با حل این دو معادله به طور همزمان ، می بینیم که جواب بهینه مسئله گیاپتو است . مقدار بهینه z با جایگزینی مقادیر و در تابع هدف به دست می آید . بنابراین ، مقدار بهینه z برابر است.













جواب های بهینه چندگانه
گاهی اوقات مسائل جواب های بیشماری دارند برای نمونه:
یک شرکت اتومبیل سازی،سواری و کامیون تولید می کند.هر وسیله نقلیه باید به کارگاه نقاشی و مونتاژ بدنه برود.اگر کارگاه نقاشی کاملا به نقاشی کامیون بپردازد در روز می تواند 40 کامیون را نقاشی کند و اگر کاملا به نقاشی سواری بپردازد،در روز می تواند 60 سواری را نقاشی کند.اگر کارگاه بدنه کاملا به مونتاژ کامیون بپردازد در روز می تواند 50 کامیون را مونتاژ کند و اگر کاملا به مونتاژ سواری بپردازد در روز می تواند 50 سواری مونتاژ کند.سود هر کامیون معادل 300 دلار و سود هر سواری معادل 200 دلار است.
برنامه ریزی خطی را به کار می گیریم و مشخص می کنیم برنامه تولید روزانه چه باشد تا سود شرکت بیشینه گردد.
جواب:شرکت باید مشخص کند که روزانه چند سواری و کامیون تولید شود.این مطلب به تعریف متغیرهای تصمیم ذیل منجر می گردد:
:تعداد کامین های تولید شده در روز
:تعداد سواری های تولید شده در روز
سود روزانه شرکت(بر حسب دلار)برابر است بنابراین می توان تابع هدف شرکت را به صورت ذیل نوشت:
(1)
دو محدودیت شرکت به صورت ذیل هستند،
محدودیت 1:کسری از روز(به صورت عددی کوچکتر یا مساوی 1)که طی آن،کارگاه نقاشی مشغول است.
محدودیت 2: کسری از روز(به صورت عددی کوچکتر یا مساوی 1)که طی آن،کارگاه بدنه مشغول است.
پس روابط ذیل برقرار هستند:
کسری از روز که کارگاه نقاشی روی کامیون ها کار می کند
(کامیون/کسری از روز)(روز/کامیون ها)
کسری از روز که کارگاه نقاشی روی سواری ها کار می کند
کسری از روز که کارگاه بدنه روی کامیون ها کار می کند
کسری از روز که کارگاه بدنه روی سواری ها کار می کند
بنابراین محدودیت 1 به صورت ذیل قابل بیان است:
(2) (محدودیت کارگاه نقاشی)
و محدودیت 2 نیز به صورت ذیل قابل بیان است:
(3) (محدودیت کارگاه بدنه)
از آنجا که باید و نیز برقرار باشند،LP مربوطه به صورت زیر است:
(1)
s.t.
(2)
(3)

ناحیه موجه این مسئله در شکل 2 سایه زده شده و با AEDF محصور شده است.
برای یافتن خط هم سود،خطی را که از نقطه ی عبور می کند،رسم می کنیم .از آنجا که مقدار z به ازای این نقطه برابر است،خط هم سود به صورت به دست می آید.با بررسی خطوط موازی این خط هم سود در جهت افزایشZ(شمال شرقی)،می توان آخرین نقطه ناحیه موجه که با خط هم سود اشتراک دارد جستجو کرد که پاره خط AE است،این بدین معناست که هر نقطه روی پاره خط AE،بهینه است.می توان از هر نقطه روی پاره خط AE برای مشخص کردن مقدار بهینه Z استفاده کرد.
برای مثال،نقطه A با مختصات ،دارای مقدار تابع هدف برابر است.
به طور خلاصه برنامه ریزی خطی مربوط به این شرکت،بی نهایت جواب بهینه دارد پس یعنی:
این مدل دارای چند جواب یا جواب بهینه چند گانه است .مطلب فوق این حقیقت را مشخص می کند که یک خط هم سود در ناحیه موجه ،با پاره خط منطبق بر محدودیت فعال (در اینجا AE ) کاملاَ اشتراک دارد .






از این مثال به نظر می رسد ( و می توان نشان داد که درست است ) که اگر دو نقطه ( در اینجا Aو E ) بهینه باشند ، آنگاه هر نقطه روی پاره خط واصل آنها نیز بهینه خواهد بود .اگر بهینه چندگانه وجود داشته باشد ، تصمیم گیرنده می تواند ضابطه دیگری را به کار گیرد و از بین جواب های بهینه یکی را انتخاب کند .
مدیران شرکت ممکن است نقطه A را ترجیح دهند ، زیرا برای شرکت تولید یک نوع محصول (کامیون ها ) ساده تر است ( درحالی که هنوز سود بیشینه باشد ) .
















الگوریتم سیمپلکس
در فصل قبل دیدیم که چگونه مسائل برنامه ریزی خطی دو متغیره،به صورت ترسیمی حل می شوند .اما در مسائل واقعی متغیر های زیادی وجود دارند،بنابراین روشی مورد نیاز است که LP با بیش از دو متغیر را حل کرد.
در این فصل بیشتر در مورد الگوریتم سیمپلکس بحث می شود که برای حل هر LP بزرگی استفاده می شود.در بسیاری از کاربرد های صنعتی،الگوریتم سیمپلکس برای حل LP هایی با هزاران محدودیت و متغیر استفاده می شود در واقع در این فصل توضیح می دهیم که چگونه الگوریتم سیمپلکس را می توان برای یافتن جواب بهینه LP ها به کار گرفت.
چگونه یک LP را به شکل استاندارد تبدیل کنیم؟
دیدیم که LP می تواند محدودیت هایی به شکل معادله یا نا معادله داشته باشد، همچنین می تواند متغیر های غیر منفی داشته باشد و می تواند متغیر های نا محدود در علامت) (ursنیز داشته باشد.قبل از اینکه الگوریتم سیمپلکس برای حل LP استفاده شود،LP باید به مسئله معادلی تبدیل شود که در آن همه ی محدودیت ها به شکل معادله هستند و همه متغیرها غیر منفی هستند.این شکل LP را شکل استاندارد گویند.
برای تبدیل یک LP به شکل استاندارد،هر محدودیت نامعادله باید با یک محدودیت معادله جایگزین شود.این رویه را برای مثال ذیل استفاده می کنیم:
مثال:لیترلیمی تد ،دو نوع کمربند،مدل لوکس و مدل معمولی می سازد.هر نوع کمربند به یک یارد مربع چرم نیاز دارد.هر کمربند معمولی به یک ساعت نیروی انسانی ماهر و هر کمربند لوکس به دو ساعت نیروی انسانی ماهر نیاز دارد .
هر هفته 40 یارد مربع چرم و 60 ساعت نیروی انسانی ماهر موجود است . هر کمربند معمولی ، 3 دلار و هر کمربند لوکس ، 4 دلار سود دارد .
اگر تعریف کنیم :
: تعداد کمربندهای لوکس که در هفته تولید می شود .
: تعداد کمربندهای معمولی که در هفته تولید می شود .
LP مناسب بدین صورت خواهد بود ،
(LP1)
(1) (محدودیت چرم ) S.T.
(2) (محدودیت نیروی انسانی )

چگونه می توانیم محدودیت های (1) و (2) را به تساوی تبدیل کنیم ؟
برای هر محدودیت به شکل ، متغیر کمبود ( متغیر کمبود امین محدودیت ) را تعریف می کنیم که مقدار منبع استفاده نشده در محدودیت است . از آنجا که یارد مربع چرم استفاده می شود و 40 یارد مربع چرم موجود است ، را این گونه تعریف می کنیم ،
یا
به طور مشابه ، را این گونه تعریف می کنیم ،
یا
مشاهده کنید که نقطه ( ) ، امین محدودیت را شامل می شود ، اگر و فقط اگر باشد . برای مثال ، ، (1) را شامل می شود ، زیرا برقرار است .
(1) با نقطه (15،20 ) برقرار می شود ، زیرا یارد مربع چرم استفاده نمی شود . به طور مشابه ، نقطه (15،20 ) ، (2) را شامل می شود ، زیرا ساعت نیروی انسانی ، بدون استفاده می ماند .سرانجام ، توجه کنید که نقطه در رابطه (2) صدق نمی کند ، زیرا مشخص می کند که (25،25 ) بیشتر از نیروی انسانی موجود استفاده می کند .
به طور خلاصه ، برای تبدیل (1) به یک محدودیت تساوی ، (1) را با (یا ) و جایگزین می کنیم . برای تبدیل (2) به یک محدودیت تساوی ، (2) را با ( یا ) و جایگزین می کنیم . LP1 به صورت ذیل تبدیل می شود ؛

(LP1' ) S.t.


توجه کنید که LP1' ، به شکل استاندارد است . به طور خلاصه ، اگر محدودیت ام یک LP ، یک محدودیت باشد ، با افزوذن یک متغیر کمبود به محدودیت ام و افزودن محدودیت علامت ، آن را به معادله تبدیل می کنیم .









تحلیل حساسیت : یک راهکار کاربردی
در این فصل ، روی تأثیر تغییرات پارامترها بر روی جواب بهینه ، بحث می کنیم .این موضوع ، تحلیل حساسیت نامیده می شود .
یک مقدمه ترسیمی برای تحلیل حساسیت
تحلیل حساسیت : با بررسی اثرات تغییر پارامترهای یک LP بر جواب بهینه ، مرتبط است .
مسئله گیاپتو را از فصل 2 مجدداَ در نظر بگیرید :


(محدودیت پرداخت) s.t.
( محدودیت نجاری)
(محدودیت تقاضا)

به طوری که
: تعداد سربازان تولید شده در هفته ،
: تعداد واگن های تولید شده در هفته
جواب بهینه این مسئله ؛ ( که در واقع همان نقطه B در شکل مسئله بود ) است .
حال می بینیم که تغییرات ضرایب در تابع هدف مسئله یا سمت راست محدودیت ها ، چگونه بر جواب بهینه تأثیر می گذارد .



تحلیل ترسیمی تأ ثیر حاصل از تغییر یک ضریب در تابع هدف
اگر مشارکت در سود یک سرباز به حد کافی افزایش پیدا کند ، منطقی به نظر می رسد که بهتر است گیاپتو ، سربازان بیشتری تولید کند .
به طور مشابه ، اگر مشارکت در سود یک سرباز به حدّ کافی ، کاهش پیدا کند ، برای گیاپتو بهتر خواهد بود که فقط واگن تولید کند .
حال نشان می دهیم که چگونه مقدار مشارکت در سودی را بیابیم که پایه بهینه فعلی را بهینه نگه دارد .
را میزان مشارکت در سود هر سرباز بگیرید . برای چه مقادیری از ، پایه فعلی بهینه می ماند ؟
در حال حاظر ، و هر خط هم سود به شکل ، مقدار ثابت است یا مقدارثابت
و هر خط هم سود دارای شیب است . در شکل صفحه بعد می بینیم که اگر تغییر داده شود و باعث شود که خط هم سود ، شیب کندتری نسبت به محدودیت نجاری داشته باشد ، جواب بهینه از جواب بهینه فعلی ( نقطه B ) به یک جواب بهینه جدید (A) می رسد . اگر سود هر سرباز باشد، شیب هر خط هم سود ، خواهد بود . از آنجا که ، شیب محدودیت نجاری ، است ، خطوط هم سود در صورتی شیب کندتری نسبت به محدودیت نجاری خواهند داشت که یا باشد و بهینگی جواب پایه فعلی دیگر دوامی نخواهد داشت . جواب بهینه جدید ، (80و0 ) یعنی نقطه A در شکل صفحه بعد خواهد بود .
اگر خطوط هم سود ، شیب تندتری نسبت به محدودیت پرداخت داشته باشند ، جواب بهینه از نقطه B به نقطه C ، تغییر خواهد کرد . شیب محدودیت پرداخت ، -2 است . اگر باشد یا شود ، پایه فعلی دیگر بهینه نخواهد بود و نقطه C ، (20و40 ) ، بهینه خواهد بود. به طور خلاصه نشان داده ایم که ( اگر پارامترهای دیگر هم بدون تغییر بماند ) پایه فعلی برای بهینه خواهد ماند و گیاپتو هنوز باید 20 سرباز و 60 واگن تولید کند . البته ، حتی اگر باشد ، سود گیاپتو تغییر خواهد کرد . برای نمونه ، اگر ، سود گیاپتو دلار می شود و دیگر 180 دلار نیست .
تحلیل ترسیمی تأثیر حاصل از تغییر در سمت راست بر روی جواب بهینه
تحلیل ترسیمی را همچنین می توان برای تعیین اثر تغییرات در سمت راست محدودیت ها و بهینگی پایه فعلی استفاده کرد. را تعداد ساعات پرداخت در دسترس فرض می کنیم،فعلأ است.


برای چه مقادیری از پایه فعلی بهینه می ماند؟
در شکل (2) می بینیم که تغییر در ،محدودیت پرداخت را به موازات محل فعلیش تغییر می دهد.جواب بهینه فعلی (نقطه B در شکل 2)جایی است که محدودیت های پرداخت و نجاری، فعال هستند.اگر مقدار را عوض کنیم آنگاه نقطه ای که در آن محدودیت های نجاری و پرداخت فعال هستند،موجه می مانند.جواب بهینه هنوز هم در جایی خواهد بود که محدودیت های نجاری وپرداخت اشتراک دارند.
در شکل (2) می بینیم که اگر باشد،نقطه ای که در آن محدودیت های پرداخت و نجاری هر دو فعال هستند،زیر نقطه D واقع می شود.توجه داشته باشید که در نقطه D، ساعت پرداخت،مورد استفاده است.در این ناحیه، و محدودیت تقاضا برای سربازان را شامل نشده است،بنابراین برای پایه فعلی دیگر بهینه نخواهد بود.به طور مشابه اگر باشد،محدودیت های نجاری پرداخت در یک نقطه غیر موجه که ،فعال خواهند بود و پایه فعلی دیگر بهینه نخواهد بود.توجه داشته باشید که در نقطه A ، ساعت پرداخت استفاده شده است،بنابراین (اگر همه ی پارامترهای دیگر بدون تغییر باقی بمانند)،پایه فعلی در صورتی بهینه خواهد بود که باشد.
همچنین توجه داشته باشید که برای ،گرچه پایه فعلی بهینه می ماند،مقادیر متغیرهای تصمیم و مقدار تابع هدف تغییر خواهد کرد ،برای مثال:اگر باشد،جواب بهینه از نقطه B به نقطه دیگری روی پاره خط AB می رود.به طور مشابه اگر باشد،جواب بهینه از نقطه B به نقطه دیگری روی پاره خطBD می رود.
تا زمانی که پایه فعلی بهینه بماند،یک روش معمول برای تعیین چگونگی تغییر متغیرهای تصمیم در زمان تغییر پارامترهای سمت راست،وجود دارد.برای نمایش این ایده، را تعداد ساعات پرداخت بگیرید.
اگر را به تغییر دهید،می دانید پایه فعلی برای بهینه می ماند. توجه داشته باشید،همان طور که تغییر می کند (به صورتی که برقرار باشد)،جواب بهینه LP هنوز نقطه ای است که در آن محدودیت های ساعات نجاری و ساعات پرداخت،فعال هستند،بنابراین اگر باشد،می توان مقادیر جدید متغیرهای تصمیم را با حل دستگاه ذیل به دست آورد:

این نتیجه می دهد. و . بنابراین یک افزایش در تعداد ساعات پرداخت،باعث افزایش در تعداد سربازان تولید شده و کاهش در تعداد واگن های تولید شده است.
اگر (تعداد ساعات نجاری)برابر باشد می توان نشان داد که پایه فعلی برای بهینه می ماند. اگر مقادیر را تغییر دهیم( نگه داشته شود)جواب بهینه LP هنوز نقطه ای است که محل تلاقی محدودیت های پرداخت و نجاری باشد،بنابراین اگر باشد،جواب بهینه LP حل دستگاه ذیل می باشد:

این نتیجه می دهد که و که یعنی افزایش در تعداد ساعات نجاری در دست،باعث کاهش تعداد سربازان تولید شده و افزایش تعداد واگن های تولیدی می شود.
فرض کنید ،تقاضا برای سربازها به تغییر کند .آنگاه می توان نشان داد که پایه فعلی برای بهینه می ماند.برای در این بازه،جواب بهینه LP،هنوز در جایی خواهد بود که محدودیت های نجاری و پرداخت،فعال هستند،بنابراین جواب بهینه برابر با حل دستگاه ذیل خواهد بود:


البته این نتیجه می دهد و است که یک واقعیت مهم است.یک محدودیت با کمبودهای مثبت (یا افزایش مثبت)در جواب بهینه یک LP را در نظر بگیرید:
اگر طرف راست این محدودیت را در بازه ای که پایه فعلی،بهینه بماند،تغییر دهیم،جواب بهینه LP بدون تغییر خواهد ماند.] 1 [
اهمیت تحلیل حساسیت
تحلیل حساسیت به چند دلیل مهم است:
در بسیاری از کاربردها،ممکن است مقادیر پارامترهای یک LP تغییر کند.اگر یک پارامتر عوض شود،معمولأ حل مجدد مسئله با وجود تحلیل حساسیت ضرورت نمی یابد،برای مثال:
اگر مشارکت در سود یک سرباز به 3.5 دلار افزایش یابد،مجبور نخواهیم بود که مسئله گیاپتو را دوباره حل کنیم،زیرا جواب فعلی بهینه می ماند،البته حل کردن مجدد مسئله گیاپتو کار زیادی نمی خواهد اما حل دوباره یک LP با هزاران متغیر و محدودیت،خسته کننده است ،در واقع دانش تحلیل حساسیت معمولا تحلیل گر را قادر می سازد تا از روی حل مسئله اصلی،چگونگی اثر تغییر پارامترها در جواب بهینه را مشخص کند.
به خاطر آورید که ممکن است در مورد مقادیر پارامترهای یک LP مطمئن نباشیم،برای مثال:
ممکن است تقاضای هفتگی برای سربازان را با قطعیت ندانیم.
با روش ترسیمی می توان نشان داد که اگر تقاضای هفتگی سربازان حداقل 20 باشد،جواب بهینه مسئله گیاپتو هنوز است، بنابراین اگر گیاپتو برای تقاضای سرباز مطمئن نباشد،کمپانی تقریبأ می تواند مطمئن باشد که تولید 20 سرباز و 60 واگن هنوز بهینه است.







 


فصل سوم
(کاربرد ها و معرفی نرم افزار)

کاربردها
برنامه ريزي خطي کاربرد هاي متعددي در ارتش، حکومت، صنعت و مهندسي شهر سازي يافته است همچنين اغلب به عنوان بخشي از طرح هاي محاسباتي، حل مسائل برنامه ريزي غير خطي، برنامه هاي گسسته، مسائل ترکيباتي، مسائل کنترل بهينه و برنامه ريزي احتمالي به کار مي رود. برنامه ريزي خطي زمينه مهمي در بهينه سازي است: بسياري از مسائل عملي در تحقيق عمليات به عنوان مسئله برنامه ريزي خطي مي تواند بيان شود و همچنين تعدادي از الگوريتم هاي ديگر مسائل بهينه سازي به وسيله ي حل مسائل برنامه ريزي خطي، به عنوان زير مسئله کار مي کنند. به طور تاريخي ايده هاي برنامه ريزي خطي الهام بخش بسياري از مفاهيم اوليه تئوري بهينه سازي مانند دوگانگي، تجزيه، اهميت تحدب و تعميم آن بوده است.
برنامه ريزي خطي به طور عمده در اقتصاد کلان، مديرت تجاري، حداکثر کردن درآمد يا حداقل کردن هزينه ي توليد به کار مي رود. به عنوان مثال: مديرت موجودي، مديرت دارايي و سهام، تخصيص منابع انساني و منابع غيرانساني، برنامه ريزي سفرهاي تبليغاتي.
در بسياري شرکت ها و موسسات دولتي با به کارگيري موفقيت آميز برنامه ريزي خطي، ميليون ها دلار صرفه جويي کرده اند. در زير به بيان چند مورد از اين موفقيت ها اشاره مي کنيم:
با استفاده از برنامه ريزي خطي و برنامه ريزي عدد صحيح ، روشي براي زمان بندي گشت افسران پليس در سان فرانسيسکو، توسط تيلور و هاکس لي (1989) طراحي گرديد. با اين روش سالانه 11 ميليون دلار صرفه جويي حاصل شد، زمان پاسخ گويي به درخواست ها نيز حدود 3 ميليون دلار در سال افزايش يافت.
با استفاده از برنامه ريزي پويا، چائو و ديگران (1989) در حدود 79پست برق و بيش از 125 ميليون دلار در خريد موجودي و هزينه هاي کمبود صرفه جويي کردند.
با استفاده از برنامه ريزي عدد صحيح، واسکو و ديگران (1989) در طراحي تأسيسات قالب شمش به فولاد بتلهم کمک کردند. برنامه ريزي عدد صحيح باعث شد که در هزينه هاي عملياتي سالانه، 8 ميليون دلار صرفه جويي گردد.
با استفاده از مدل هاي شبکه پاول و ديگران (1988) يک مدل جهت تخصيص بار براي رانندگان کاميون در شرکت خطوط آمريکاي شمالي توسعه دادند. استفاده از اين مدل باعث ارائه خدمات بهتر به مشتريان و کاهش حدود 5/2 ميليارد دلار هزينه ساليانه شده است.
سوليوان و سکرست از برنامه ريزي خطي استفاده کردند تا در مورد چگونگي فرايند کره گيري از دوغ، شير خام، کشک شيرين و خامه براي پنير خامه اي، پنير بسته بندي، خامه ترش و خامه کشک تصميم گيري شود.استفاده از مدل، سود کره گيري را سالانه 48000 دلار افزايش داده است. ]3[











استفاده از نرم افزارهای لیندو و لینگو در مسائل برنامه ریزی خطی
لیندو چیست؟
LINDO از حروف ابتدایی عبارت linear interactive and discrete optimizer به معنای بهینه ساز گسسته خطی و در ارتباط دو طرفه با کاربر اخذ گردیده است.
از این بسته نرم افزاری در حل مسائل برنامه ریزی خطی،عدد صحیح و درجه دو استفاده می شود.
این بسته نرم افزاری می تواند در زمینه های مختلفی از قبیل برنامه ریزی تولید،زمان بندی،تخصیص بودجه و سایر فعالیت های صنعتی که به مسائل بهینه سازی مربوط است ،مورد استفاده قرار می گیرد.
در ابتدا لیندو در دهه 80 به وجود آمد و سپس به صورت نرم افزار شئ گرا با امکاناتی مناسب،تحت محیط ویندوز درآمد.
در واقع در لیندو از الگوریتم سیمپلکس برای حل مسائل برنامه ریزی خطی استفاده می شود.
لینگو چیست؟
لینگو یک بسته نرم افزاری با امکان برقراری ارتباط دو طرفه با کاربر است و از آن می توان در حل مسائل خطی،عدد صحیح و غیر خطی استفاده کرد.
استفاده از این نرم افزار وضعیت مشابهی مانند لیندو دارد اما از انعطاف بیشتری در بیان مدل برخوردار است.
برخلاف لیندو، لینگو امکان استفاده از پرانتزها و متغیرها را در سمت راست معادله فراهم می آورد،بنابراین محدودیت ها را می توان به صورت اولیه،بدون نیاز به تبدیل آن به ساختار استاندارد(آوردن مقادیر ثابت به سمت راست)نوشت.همچنین لینگو قابلیت تولید مدل های بزرگ با سطرهای نسبتأ کم در داده های ورودی را داراست.
لینگو دارای یک کتابخانه بزرگ از توابع ریاضی،آماری و احتمالی بوده و قدرت بالای آن در خواندن اطلاعات از فایل های خارجی و نرم افزارهای صفحه گسترده است.

نیازهای سخت افزاری
برای استفاده مناسب از این دو نرم افزار،حداقل وجود سخت افزارهای زیر لازم است:
• یک کامپیوتر شخصی حداقل با یک پردازشگر 80386
• 4 مگا بایت RAM
• 2 مگا بایت فضای خالی بر روی دیسک سخت برای هر یک از بسته های نرم افزاری و داشتن فضای اضافی برای فایل های مربوط به داده ها

علاوه بر حداقل نیازهای سخت افزاری مذکور،یک کمک پردازشگر ریاضی،حافظه اضافی و پردازشگر سریع تر می تواند باعث بهبود قابل توجه در کارایی نرم افزار گردد.










تحقیقات جاری
موارد زير از جمله مواردي است که تحقيقات بر روی آنها ادامه دارد:
* پيدا نمودن الگوريتمي چند جمله اي قوي زماني کاراتر جهت حل مسائل برنامه ريزي خطي
* تعيين مسائلي که زمان اجراي مطابق الگوريتمهاي چند جمله اي قوي دارند ( حالات خاص)
اينها مسائلي هستند که توسط استفان اسميت در بين 18 مسئله بزرگ حل نشده ي قرن 21 عنوان شده اند.در نوشته هاي اسميل اولين مسائل مسئله هاي تئوري برنامه ريزي خطي هستند.هر چند الگوريتم هايي براي حل مسائل برنامه ريزي خطي براي چند جمله اي با درجه بالا وجود دارد مانند روش بيضوي و نقطه دروني، ولي هيچ الگوريتمي براي چند جمله اي با درجه پائين يافت نشده است. توسعه ي الگوريتم هايي مانند اينها ميتواند کمکي به تئوري و همچنين تمريني براي حل مسائل برنامه ريزي خطي بزرگ تري باشد.
آيا با روش سطري کردن مي توان سيمپلکسي براي چند جمله اي ها به وجود آورد؟
اين سوالات وابسته به انجام آناليز و گسترش روش هايي مانند سيمپلکس است.








 
فصل چهارم
(نتیجه گیری)

نتیجه گیری :
با توجه به تحقیقاتی که در این زمینه انجام دادم به نتایج زیر دست پیدا کردم :
برنامه ریزی خطی یکی از مباحث بسیار مهم در علوم اقتصادی و ریاضیات و مدیریت و غیره بوده که باعث بهبود کارها و صرفه جویی در وقت و هزینه شده است . به عنوان مثال این روش باعث میلیون ها دلار صرفه جویی در مباحث مربوط به علم اقتصاد شده است .
همچنین این روش دغدغه های ذهنی بسیاری از مدیران در مواردی چون میزان تولید، سود ، درآمد و غیره را نیز برطرف نموده است .
امید است که با مطالعات بیشتر ، مسائل نهان در این زمینه حل شود و با استفاده از آن در جهت بهبود زندگی بشر گام برداریم .



















واژه نامه
A
چکیده – خلاصه

تایید است.