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

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

چگونه می توان آن ها را تقویت نمود؟
چه ارزش افزوده ای برای مشتریان ایجاد کرده است؟
چرا کارمندان باصلاحیت در این چشمه ها مشغول اند؟
چرا کارمندان جذب کار در این چشمه ها می شوند و چه کارهایی در جهت جذب آنها باید انجام شود؟
چگونه می توان با ذینعفان ارتباط برقرار کرد و پیام این کار چیست؟
بیان برنامه ریزی خطی و به طور خاص مدل سازی مسئله امتزاج
مقدمه:
در ریاضیات، مسائل برنامه ریزی خطی شامل بهینه سازی تابع هدفی خطی است که بایستی یکسری محدودیت در فرم های تساوی های خطی و نامساوی برقرار شوند. به طور خیلی غیررسمی برنامه ریزی خطی استفاده از مدل ریاضی خطی برای بدست آوردن بهترین خروجی(به طور مثال حداکثر سود، حداقل کار) با توجه به شرط های داده شده (برای مثال فقط 30 ساعت کار در هفته، کار غیر قانونی انجام ندادن و غیره) است. و به طور رسمی تر در یک چند سقفی (مانند چندضلعی یا چندوجهی) که تابعی با مقدار حقیقی بر روی آن تعریف شده است، هدف یافتن نقطه ای در این چند سقفی است که تابع هدف بیشترین یا کمترین مقدار را دارا باشد. این نقاط ممکن است موجود نباشد، اما اگر وجود داشته باشند جست و جو در میان رئوس چند ضلعی یافتن حداقل یکی از آن ها را تضمین می کند.
برنامه ریزی خطی به صورت استاندارد می توانند نمایش داده شوند:
Maximize cTx
Subject to Ax ≤ b
x ≥ 0
X بیانگر بردار متغیر ها می باشد و همچنین c وb بردار ضرایب و A ماتریس ضرایب. عبارتی که باید حداکثر یا حداقل شود تابع هدف نام دارد (در این مورد cTx). عبارتAx ≤ b شرایطی هستند که یک چند وجهی محدب را نمایش می دهند که تابع هدف روی آن باید بهینه شود. برنامه ریزی خطی می تواند در زمینه های مختلف مطالعه مورد استفاده قرار گیرد. برنامه ریزی خطی به طور عمده در موقعیت های تجاری و اقتصادی مورد استفاده قرار می گیرد اما برای بعضی از مسائل مهندسی نیز می تواند به کار برده شود. بعضی از صنعت ها که برنامه ریزی خطی را مورد استفاده قرار می دهند عبارتند از حمل و نقل، انرژی، مخابرات و کارخانه ها و … . همچنین در مدل کردن مسائلی از قبیل برنامه ریزی، مسیر یابی، زمانبندی، تخصیص و طراحی مفید است.
تاریخچه برنامه ریزی خطی:
برنامه ریزی خطی به عنوان یک مدل ریاضی به وجود آمد و در زمان جنگ جهانی دوم و پس از آن معلوم شد که طرح ریزی و هم آهنگی پروژه های مختلف و استفاده موثر از منابع کمیاب یک ضرورت است. تیم SCOOP (محاسبات علمی برنامه های بهینه) نیروی هوایی ایالات متحده کار جدی خود را در ژوئن 1947 شروع کرد. ماحصل آن، ابداع روش سیمپلکس توسط جورج.بی.دانتزیک در پایان تابستان 1947 بود. برنامه ریزی خطی به سرعت مورد توجه اقتصاد دانان، ریاضی دانان، آماردانان، و موسسات دولتی قرار گرفت. در تابستان 1949 کنفرانسی در برنامه ریزی و برای برنامه ریزی مخارج و برگشت ها توسعه داده شد به طوری که با مسئولیت کمیته Cowles برای تحقیق در اقتصاد برگزار شد. مقالات ارائه شده در این کنفرانس اندکی بعد در سال 1951 به همت T.C.Koopmans در کتابی تحت عنوان تحلیل فعالیت تولید و تخصیص جمع آوری شد.. جان وان نیومن در همان سال تئوری دو گانگی را توسعه داد و لئونید خاشیان ریاضی دان روسی ار تکنیک های ساده در اقتصاد قبل از دانتزیک استفاده کرد و جایزه نوبل را در سال 1975 در اقتصاد برد.
مثال اصلی دانتزیک یافتن بهترین تخصیص 70 نفر به 70 شغل بود و هنوز موفقیت او را نشان می دهد. برای محاسبه احتیاج به نمایش همه ی جایگشت ها برای انتخاب بهترین تخصیص بسیار وسیع و غیر ممکن است. او مشاهده کرد با استفاده از الگوریتم سیمپلکس یافتن بهترین جواب فقط چند لحظه طول می کشد و همچنین متوجه شد که جواب در گوشه چند ضلعی که به وسیله قید های مسأله تشکیل می شود وجود دارد. یکی از مسائلی که غالبا در برنامه ریزی خطی پیش می آید مسئله امتزاج است. این نوع مسائل وقتی مطرح می شوند که چندین ماده خام باید برای تولید یک محصول با هم مخلوط شوند. هرکدام از این مواد خام شامل عناصر یا موادی هستند که باید به میزان معین در محصول نهایی موجود باشند. مثلا یک نوع دارو را می توان از ترکیب چهارماده اولیه خام تولید نمود. در ساختمان هر ماده خام 6 عنصر وجود دارد. داروی فوق باید به گونه ای ساخته شود که درصد خاصی از هر عنصر در آن وجود داشته باشد. هزینه مواد خام مشخص است. واضح است که مقادیر مختلفی از مواد خام را می توان مخلوط نمود بطوریکه محدودیت درصد هر عنصر نیز رعایت شود. حال سوال این است که چه میزان از هر ماده خام اولیه باید باهم ترکیب شوند تا محصول نهایی به گونه ای تولید شود که هم محدودیت فوق رعایت شود و هم اینکه هزینه مواد اولیه مینیمم گردد .
فرموله کردن مدل مساله امتزاج
برای فرموله کردن مسایل امتزاج به صورت یک مدل برنامه ریزی خطی ، فرض می کنیم که n ماده ی اولیه و m عنصر برای محصول نهایی موجود باشد . متغیر های تصمیم، تابع هدف و محدودیتهای مساله به صورت زیر می باشند:
xi: نسبت ماده خام جی در ترکیب نهایی هر واحد محصول
cj: قیمت هر واحد از ماده خام نوع جی
aij: نسبت عنصر ای ام که در ماده خام جی ام وجود دارد
bi: نسبت مشخصه اس ام در محصول
ej: نسبت نا خالصی ماده خام jام( نسبتی از ماده خام نوع j که در ترکیب محصول نهایی وجود ندارد)

Share