تالار فرهنگی هنری جی تاک
 




Register
Welcome
آخرین مطالب ارسالی در جی تاک
 
پاسخ
قدیمی 28th June 2009   #1

Tinamo مرد

كاربر سایت

 Tinamo آواتار ها

تاریخ عضویت: May 2009
نـــام واقعــی: سروش طیبی
محل سکونت: تهران
نوشته ها: 813
تشکر ها: 274
از این کاربر 923 بار در 529 ارسال تشکر شده است.
مایه تیله: 1,000

 

برنامه ریزی خطی

۱- مقدمه

در ریاضیات، مسائل برنامه ریزی خطی شامل بهینه سازی تابع هدفی خطی است که بایستی یکسری محدودیت در فرم های تساوی های خطی و نامساوی برقرار شوند. به طور خیلی غیررسمی برنامه ریزی خطی استفاده از مدل ریاضی خطی برای بدست آوردن بهترین خروجی(به طور مثال حداکثر سود، حداقل کار) با توجه به شرط های داده شده (برای مثال فقط ۳۰ ساعت کار در هفته، کار غیر قانونی انجام ندادن و غیره) است.

و به طور رسمی تر در یک چند سقفی (مانند چندضلعی یا چندوجهی) که تابعی با مقدار حقیقی بر روی آن تعریف شده است، هدف یافتن نقطه ای در این چند سقفی است که تابع هدف بیشترین یا کمترین مقدار را دارا باشد. این نقاط ممکن است موجود نباشد، اما اگر وجود داشته باشند جست و جو در میان رئوس چند ضلعی یافتن حداقل یکی از آن ها را تضمین می کند.


برنامه ریزی خطی به صورت استاندارد می توانند نمایش داده شوند:

Maximize cTx

Subject to Ax ≤ b

x ≥ ۰

X بیانگر بردار متغیر ها می باشد و همچنین c وb بردار ضرایب و A ماتریس ضرایب. عبارتی که باید حداکثر یا حداقل شود تابع هدف نام دارد (در این مورد cTx ).عبارت b Ax ≤ شرایطی هستند که یک چند وجهی محدب را نمایش می دهند که تابع هدف روی آن باید بهینه شود.

برنامه ریزی خطی می تواند در زمینه های مختلف مطالعه مورد استفاده قرار گیرد. برنامه ریزی خطی به طور عمده در موقعیت های تجاری و اقتصادی مورد استفاده قرار می گیرد اما برای بعضی از مسائل مهندسی نیز می تواند به کار برده شود. بعضی از صنعت ها که برنامه ریزی خطی را مورد استفاده قرار می دهند عبارتند از حمل و نقل، انرژی، مخابرات و کارخانه ها و … . همچنین در مدل کردن مسائلی از قبیل برنامه ریزی، مسیر یابی، زمانبندی، تخصیص و طراحی مفید است.یک ارزیابی انجام شده از ۵۰۰ شرکت بزرگ دنیا، نشان داد که ۸۵% درصد آنها از برنامه ریزی خطی استفاده نموده اند.[۱]



۲-تاریخچه برنامه ریزی خطی

مسئله حل یک سیستم نامساوی خطی به زمان فوریه[۱] بر می گردد. برنامه ریزی خطی به عنوان یک مدل ریاضی به وجود آمد و در زمان جنگ جهانی دوم و پس از آن معلوم شد که طرح ریزی و هم آهنگی پروژه های مختلف و استفاده موثر از منابع کمیاب یک ضرورت است. تیم SCOOP (محاسبات علمی برنامه های بهینه) نیروی هوایی ایالات متحده کار جدی خود را در ژوئن ۱۹۴۷ شروع کرد. ماحصل آن، ابداع روش سیمپلکس توسط جورج.بی.دانتزیک[۲] در پایان تابستان ۱۹۴۷ بود. برنامه ریزی خطی به سرعت مورد توجه اقتصاد دانان، ریاضی دانان، آماردانان، و موسسات دولتی قرار گرفت. در تابستان ۱۹۴۹ کنفرانسی در برنامه ریزی و برای برنامه ریزی مخارج و برگشت ها توسعه داده شد به طوری که با مسئولیت کمیته Cowles برای تحقیق در اقتصاد برگزار شد. مقالات ارائه شده در این کنفرانس اندکی بعد در سال ۱۹۵۱ به همت T.C.Koopmans در کتابی تحت عنوان تحلیل فعالیت تولید و تخصیص جمع آوری شد.[۲]. جان وان نیومن[۳] در همان سال تئوری دو گانگی را توسعه داد و لئونید خاشیان[۴] ریاضی دان روسی ار تکنیک های ساده در اقتصاد قبل از دانتزیک استفاده کرد و جایزه نوبل را در سال ۱۹۷۵ در اقتصاد برد.

مثال اصلی دانتزیک یافتن بهترین تخصیص ۷۰ نفر به ۷۰ شغل بود و هنوز موفقیت او را نشان می دهد. برای محاسبه احتیاج به نمایش همه ی جایگشت ها برای انتخاب بهترین تخصیص بسیار وسیع و غیر ممکن است. او مشاهده کرد با استفاده از الگوریتم سیمپلکس یافتن بهترین جواب فقط چند لحظه طول می کشد و همچنین متوجه شد که جواب در گوشه چند ضلعی که به وسیله قید های مسأله تشکیل می شود وجود دارد.



۳-کاربرد ها

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

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

در بسیاری شرکت ها و موسسات دولتی با به کارگیری موفقیت آمیز برنامه ریزی خطی، میلیون ها دلار صرفه جویی کرده اند. در زیر به بیان چند مورد از این موفقیت ها اشاره می کنیم:

با استفاده از برنامه ریزی خطی و برنامه ریزی عدد صحیح ، روشی برای زمان بندی گشت افسران پلیس در سان فرانسیسکو، توسط تیلور و هاکس لی (۱۹۸۹) طراحی گردید. با این روش سالانه ۱۱ میلیون دلار صرفه جویی حاصل شد، زمان پاسخ گویی به درخواست ها نیز حدود ۳ میلیون دلار در سال افزایش یافت.

با استفاده از برنامه ریزی پویا، چائو و دیگران (۱۹۸۹) در حدود ۷۹پست برق و بیش از ۱۲۵ میلیون دلار در خرید موجودی و هزینه های کمبود صرفه جویی کردند.

با استفاده از برنامه ریزی عدد صحیح، واسکو و دیگران (۱۹۸۹) در طراحی تأسیسات قالب شمش به فولاد بتلهم کمک کردند. برنامه ریزی عدد صحیح باعث شد که در هزینه های عملیاتی سالانه، ۸ میلیون دلار صرفه جویی گردد.

با استفاده از مدل های شبکه پاول و دیگران (۱۹۸۸) یک مدل جهت تخصیص بار برای رانندگان کامیون در شرکت خطوط آمریکای شمالی توسعه دادند. استفاده از این مدل باعث ارائه خدمات بهتر به مشتریان و کاهش حدود ۵/۲ میلیارد دلار هزینه سالیانه شده است.

سولیوان و سکرست از برنامه ریزی خطی استفاده کردند تا در مورد چگونگی فرایند کره گیری از دوغ، شیر خام، کشک شیرین و خامه برای پنیر خامه ای، پنیر بسته بندی، خامه ترش و خامه کشک تصمیم گیری شود.استفاده از مدل، سود کره گیری را سالانه ۴۸۰۰۰ دلار افزایش داده است.

یک سواری یا کامیون قبل از جایگزینی چند سال می تواند در یک کارخانه مورد استفاده قرار گیرد؟ نفت فیلیپس از مدل های جایگزینی تجهیزات برای پاسخ به این سؤال، استفاده کرد. این مدل های جایگزینی تجهیزات، طبق برآورد انجام شده، باعث صرفه جویی سالانه ۹۰۰۰۰ دلار برای فیلیپس شده اند.


۴- تحقیقات جاری

موارد زیر از جمله مواردی است که تحقیقات بر روی آنها ادامه دارد:

پیدا نمودن الگوریتمی چند جمله ای زمانی کاراتر جهت حل مسائل برنامه ریزی خطی
پیدا نمودن الگوریتمی چند جمله ای قوی زمانی کاراتر جهت حل مسائل برنامه ریزی خطی
تعیین مسائلی که زمان اجرای مطابق الگوریتمهای چند جمله ای قوی دارند( حالات خاص)
اینها مسائلی هستند که توسط استفان اسمیت در بین ۱۸ مسئله یزرگ حل نشده ی قرن ۲۱ عنوان شده اند.در نوشته های اسمیل اولین مسائل مسئله های تئوری برنامه ریزی خطی هستند.هر چند الگوریتم هایی برای حل مسائل برنامه ریزی خطی برای چند جمله ای با درجه یالا وجود دارد مانند روش بیضوی و نقطه درونی. ولی هیچ الگوریتمی برای چند جمله ای با درجه پائین یافت نشده است. توسعه ی الگوریتم هایی مانند اینها میتواند کمکی به تئوری و همچنین تمرینی برای حل مسائل برنامه ریزی خطی بزرگ تری باشد.

آیا با روش سطری کردن می توان سیمپلکسی برای چند جمله ای ها به وجود آورد؟

این سوالات وابسته به انجام آنالیز و گسترش روش هایی مانند سیمپلکس است.



منابع

۱- واین ال وینستون، “برنامه ریزی خطی”، ۱۳۸۰، نشر ترمه
۲- مختار اس. بازارا، جان جی. جارویس، حنیف دی. شرالی، ” برنامه ریزی خطی” ۱۳۷۸، نشر کتاب دانشگاهی
۳-http://en.wikipedia.org/wiki/Linear_programming




--------------------------------------------------------------------------------
[۱] Fourier

[2] George B. Dantzig

[3] John von Neumann

[4] Leonid Kantorovich


اینم یه مثال
يك شركت هواپيمايي يك هواپيما با 160 صندلي در اختيار دارد و مي خواهد آنرا در مسير فرضي تهران-دوشنبه بكار بياندازد. اين شركت مي خواهد سه نوع بليط كلاس عالي-كلاس متوسط-كلاس اكونومي (يا دو نوع اول) بفروشد. قيمت بليط ها بترتيب 560 دلار-460 دلار-360 دلار خواهد بود. در حال حاضر كه تمامي بليط ها يكسان فروش مي رود ضريب اشغال صندلي 62 درصد است يعني در هر پرواز بطور متوسط 103 صندلي را بفروش مي رساند. تركيبي از اختصاص صندلي كه بتواند حد اكثر درآمد (فروش بليط) را براي اين شركت ميسر سازد را معين كنيد. نحوه حل مسپله و توضيحات ضروري نيز مد نظر مي باشد. قبلا تشكر مي كنم
هزينه در هر حال فرقي نمي كند.


این جوابش
x1 تعداد صندلي فروخته شده نوع 1
x2 تعداد صندلي فروخته شده نوع 2
x3 تعداد صندلي فروخته شده نوع 3
تابع هدف به صورت زير است:
560x1+460x2+360x3 max
st
x1+x2+x3<=160
x1/(x1+x2+x3)<=0.62
x2/(x1+x2+x3)<=0.62
x3/(x1+x2+x3)<=0.62

----------------------------------------------------------------------------------------------------------------------

برنامه نویسی وب
09127163972
09360901792

Tinamo آفلاين است  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiTweet this Post!
پاسخ با نقل قول
4 کاربر مقابل از Tinamo عزیز به خاطر این پست مفید تشکر کرده اند .
قدیمی 17th June 2010   #2

nastarane man زن

کاربر سايت

 nastarane man آواتار ها

تاریخ عضویت: Jun 2009
نـــام واقعــی: نسترن
محل سکونت: تهران
نوشته ها: 21
تشکر ها: 84
از این کاربر 116 بار در 57 ارسال تشکر شده است.
مایه تیله: 1,000

 

من ميتونم يه منبع خوب معرفي كنم واسه بهتر فهميدن اين مبحث.
كتاب پ‍‍ژوهش عملياتي 1و2
نوشته دكتر خاتمي فيروزآبادي.
تو اين كتاب مفصلا در مورد برنامه ريزي خطي بحث شده.

----------------------------------------------------------------------------------------------------------------------

بی تو من در همه شهر غریبم...

nastarane man آفلاين است  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiTweet this Post!
پاسخ با نقل قول
3 کاربر مقابل از nastarane man عزیز به خاطر این پست مفید تشکر کرده اند .
قدیمی 7th May 2011   #3

NiKtA20 زن

کاربر سایت

 NiKtA20 آواتار ها

تاریخ عضویت: May 2011
نوشته ها: 1
تشکر ها: 0
از این کاربر 2 بار در 1 ارسال تشکر شده است.
مایه تیله: 1,000

 

سلام
دوستان من دنبال چندتا مدل ساخته شده میگردم،،، یعنی چندتا مسئله که پارامترهاو تابع هدف و محدودیت هاش مشخص شده باشه،،، و مدلش هم باشه...
( البته تو کتابای مرتبط حلش نباشه، یعنی نمیخوام مثال کتاب باشه، مثلا خودم حلش کردم)
خیلی خیلی لازم دارم و مهمه واسم،،، خواهشا اگه میتونید کمکم کنید
مرسی

NiKtA20 آفلاين است  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiTweet this Post!
پاسخ با نقل قول
2 کاربر مقابل از NiKtA20 عزیز به خاطر این پست مفید تشکر کرده اند .
قدیمی 12th November 2011   #4

vlady زن

کاربر سایت

 vlady آواتار ها

تاریخ عضویت: Nov 2011
نوشته ها: 1
تشکر ها: 0
از این کاربر 0 بار در 0 ارسال تشکر شده است.
مایه تیله: 1,000

 

salam mamnoon tozihatetoon b dard manam khord faghat mesale najaro age darin lotfan niaz daram lotfaaaaaaaaaaaaaaaaaaan

vlady آفلاين است  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiTweet this Post!
پاسخ با نقل قول
 
پاسخ

برچسب ها
برنامه, خطی, ریزی


کاربران در حال دیدن موضوع: 1 نفر (0 عضو و 1 مهمان)
 
ابزارهای موضوع جستجو در موضوع
جستجو در موضوع:

جستجوی پیشرفته

مجوز های ارسال و ویرایش
شما نمیتوانید موضوع جدیدی ارسال کنید
شما امکان ارسال پاسخ را ندارید
شما نمیتوانید فایل پیوست در پست خود ضمیمه کنید
شما نمیتوانید پست های خود را ویرایش کنید

BB code is فعال
شکلک ها فعال است
کد [IMG] فعال است
کد HTML غیر فعال است
Trackbacks are فعال
Pingbacks are فعال
Refbacks are فعال

سیستم بانکی Policy
Posting New Thread: 20 مایه تیله
Posting New Reply: 5 مایه تیله


تبلیغات در جی تاک

 
***تبلیغات متنی در جی تاک***
ثبت هاستینگ و دامنه * *هاست ایرانی ، میزبانی ملی *پنل ارسال sms *دانلود رایگان مقاله *دانلود رایگان کتاب دانشگاهی