نمونه مسائل برنامه ریزی خطی
برنامه ریزی خطی
کاربرد برنامه ریزی خطی در فعالیت های کشاورزی روستاهای گیلان سهراب کرد رستمی 1مسعود گلدوست آذری 2 چكيده : چهلوشش درصد جمعیت استان گیلان در مناطق روستای زندگی می کنند که این آمار در بعضی از شهرستانهای استان گیلان همچون شفت، تالش و فومن به مرز 86 ، 72 و 70 درصد نیز می رسد، ولی با درنظر گرفتن نرخ بالای بیکاری در استان گیلان، مخصوصاً در مناطق روستایی که از مزیت های نسبی فراوانی نیز برخوردار هستند به نظرمی رسد که برای غلبه بروضعیت موجود ترویج فعالیت هایکارآفرینانه، این امکان را به وجود خواهد آورد که هر چه سریعتر جوامعروستایی در استان گیلان به توسعه و پیشرفت اقتصادی دست یابد. ولی كمبود درآمد عامل مهمي است كه اگر براي آن چاره‌اي انديشيده نشود اجازه نمي‌دهد طرح‌هاي توسعه روستايي به ثمر بنشيند و روستاها توسعه يافته و از حركت ساکنان آن به سمت شهرهاي بزرگ کاسته شود . كمبود درآمد روستاييان ناشي از چندين مساله است: 1 - افزايش جمعيت روستاييان (مقدار مطلق) 2 - بيكاري (كامل يا فصلي) 3 - بهره‌وري پايين افراد و منابع 4 - عدم‌جذابيت براي سرمايه‌گذاري 5 - ضعف فضاي كسب وكار 6 - محدودیت منابع و کوچک شدن قطعات زمینهای زراعی متعلق به یک فرد ، به همین علت بسیاری از کشاورزان در روستاهای گیلان وادار شدهاند که در راستای دستیابی به سطح درآمدی بالاتر با قطعیت زیاد، در کنار کشت زراعی خود به دنبال فعالیت های دیگری باشند . اقدامات دولت، از طریق اعطای تسهیلات اعتباری و غیره باعث گردیده که حوزه های مختلفی برای افراد خانواده در زمینه های مختلف از جمله کسب و کار خانگی[1] ، کسب و کارهای خانوادگی[2] و کسب و کار روستایی[3] به وجود آید،که محوریترین فعالیتها در روستا توجه به اشتغال در بخش کشاورزی است . اما کشاورزان گیلانی به دلیل منابع محدود در استفاده از پتانسلهای بخش کشاورزی در زیرشاخههای متعدد آن با در نظر گرفتن امکاناتی که دارند، با تصمیمگیری بهینه تخصیص منابع مواجهند . لذا توسعه و گسترش استفاده از برنامه ریزی خطی به طور عام و استفاده از مدل برنامهریزی خطی چند بخشی به طور خاص این امکان را برای روستائیان استان گیلان به وجود می آورد که بخشهای مختلف و نسبتاً مستقل یک واحد زراعی را مورد بحث و توجه قرار دهند، در این وضعیتی امکان تخصیص مشترک منابع تولیدی محدود کننده بین فعالیت های مختلف کشاورزی به صورت هم زمان مطرح میشود ، که با طراحی انواع برنامه ریزی های خطی در داخل واحد تولیدی و در بین کشاورزان منطقه، به جهت نوآوری در ارائه روشی جدید در فرآیند تولید،یافتن منابع جدید و به وجود آمدن یک تشکیلات منسجم تداعی کننده نظریات ...
روش جدید برای حل مسائل برنامه ریزی خطی (LP)
روش جدید برای حل مسائل برنامه ریزی خطی ... LP<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" /> يك روش جديد براي حل مسايل برنامه ريزي خطي كسري مسايل ماكزيمم سازي كسري خطي ، پژوهش و علاقه قابل ملاحظه اي را به خود اختصاص داده اند ، زيرا آنها در برنامه ريزي توليد ، برنامه ريزي مشاركتي ومالي ، برنامه ريزي بيمارستاني و مراقبت از سلامت مفيد مي با شند. چند روش براي حل اين مسأله در سال 1962 پيشنهاد شد.چارنز و كوپر روششان را كه تبديل اينبه يك برنامه خطي معادل بستگي داشت ، پيشنهاد دادند.روش ديگري كه روش تابع هدف -- ناميده مي شود توسط بيت ران و نوواييز در سال 1973 كشف شد ، كه در آن حل اين مسأله كسري خطي بوسيله حل يك دنباله از برنامه هاي خطي فقط با محاسبه مجدد جدول محلي تابع هدف صورت مي پذيرد.همچنين بعضي از جنبه هاي ارتباط دوگان و تحليل حساسيت در مسأله كسري خطي توسط بيت ران و مگنانت در سال 1976 به بحث گذاشته شد.ساي نيز در سال 1981 در مقاله اش يك مطاله مفيد در مورد شرط بهينگي در برنامه ريزي كسري ارايه كرد.2. تعاريف و نكات :مسأله مربوط زماني بوجود مي آيد كه يك تابع كسري خطي بايد روي يك چند وجهي-ماكزيمم شود.اين مسأله مي تواند به شكل رياضي به صورت زير فرمولبندي شود و بانشان داده مي شود: (LFP): كهC,d , bاسكالر هستند.متذكر مي شويم كه شرايط نامنفي در مجموعه محدوديت ها قرار مي گيرند.:امين سطر ماتريس jفرض مي شود كه مجموعه جواب شدني – يك مجموعه فشرده است يعني بسته وكراندار مي باشد. علاوه بر اينهرجا در --اين مسأله مي تواند به شكل زير فرمولبندي شود:دراينجاامين سطر ماتريس – است كه در تباهيدگي بايد مورد توجه قرار گيرد. iيك نقطه رأسي ازناحيه شدني – در بعضي از مجموعه هاي مستقل – خطي – قرارمي گيرد .در(2.2) ما فرض خواهيم كرد كه(*)پس يك شكل معادل براي (2.2) مي تواند به صورت زير فرمولبندي شود:(2.3)اگر ما تعريف كنيم:سپس (2.3 ) مي تواندبفرم زير نوشته شود:كه:در تعريف بالاي – مي توانيم بهبرسيم.با ضرب مجموعه محدوديت هاي اين مسأله دوگان بوسيله –كهما داريم:در اين مورد موقعي كهماتريس – از درايه ها ي نا منفي تعريف مي شود بطوريكه.اين ماتريس يك نقش مهم براي يافتن مقدار بهينه مسأله ماكزيمممقدار – روي بازه اعداد حقيقي كه بوسيلهتعريف مي شودبطور ساده نمايش بالا مي تواند به شكلنوشته شود.همچنين يك زير ماتريس – از ماتريس داده شده – كه درصدق مي كند براي تعيين مقدار دوگان مورد نياز براي حلبرنامه ريزي كسري (2.1) مهم خواهد بود.اين مقادير دوگان براي يك نقطه – كه يك جواب بهينه مسأله بالا (2.5) استبه خوبي در شرايط 2و3 كان-تاكر صدق مي كنند. ما بايد داشته باشيم :يا به طور ساده:در اينجا – ...
برنامه ريزي خطي (Lp)
برنامه ريزي خطي ... Lp<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" /> تعاریف برنامه ریزی خطیزهرا صابري،زهرا کاشفي 1- مقدمهدر رياضيات، مسائل برنامه ريزي خطي شامل بهينه سازي تابع هدفي خطي است که بايستي يکسري محدوديت در فرم هاي تساوي هاي خطي و نامساوي برقرار شوند. به طور خيلي غيررسمي برنامه ريزي خطي استفاده از مدل رياضي خطي براي بدست آوردن بهترين خروجي(به طور مثال حداکثر سود، حداقل کار) با توجه به شرط هاي داده شده (براي مثال فقط 30 ساعت کار در هفته، کار غير قانوني انجام ندادن و غيره) است. و به طور رسمي تر در يک چند سقفي (مانند چندضلعي يا چندوجهي) که تابعي با مقدار حقيقي بر روي آن تعريف شده است، هدف يافتن نقطه اي در اين چند سقفي است که تابع هدف بيشترين يا کمترين مقدار را دارا باشد. اين نقاط ممکن است موجود نباشد، اما اگر وجود داشته باشند جست و جو در ميان رئوس چند ضلعي يافتن حداقل يکي از آن ها را تضمين مي کند.برنامه ريزي خطي به صورت استاندارد مي توانند نمايش داده شوند:Maximize cTx Subject to Ax ≤ bx ≥ 0 X بيانگر بردار متغير ها مي باشد و همچنين c وb بردار ضرايب و A ماتريس ضرايب. عبارتي که بايد حداکثر يا حداقل شود تابع هدف نام دارد (در اين مورد cTx ).عبارت b Ax ≤ شرايطي هستند که يک چند وجهي محدب را نمايش مي دهند که تابع هدف روي آن بايد بهينه شود. برنامه ريزي خطي مي تواند در زمينه هاي مختلف مطالعه مورد استفاده قرار گيرد. برنامه ريزي خطي به طور عمده در موقعيت هاي تجاري و اقتصادي مورد استفاده قرار مي گيرد اما براي بعضي از مسائل مهندسي نيز مي تواند به کار برده شود. بعضي از صنعت ها که برنامه ريزي خطي را مورد استفاده قرار مي دهند عبارتند از حمل و نقل، انرژي، مخابرات و کارخانه ها و … . همچنين در مدل کردن مسائلي از قبيل برنامه ريزي، مسير يابي، زمانبندي، تخصيص و طراحي مفيد است.يک ارزيابي انجام شده از 500 شرکت بزرگ دنيا، نشان داد که 85% درصد آنها از برنامه ريزي خطي استفاده نموده اند.[1] 2-تاريخچه برنامه ريزي خطيمسئله حل يک سيستم نامساوي خطي به زمان فوريه[1] بر مي گردد. برنامه ريزي خطي به عنوان يک مدل رياضي به وجود آمد و در زمان جنگ جهاني دوم و پس از آن معلوم شد که طرح ريزي و هم آهنگي پروژه هاي مختلف و استفاده موثر از منابع کمياب يک ضرورت است. تيم SCOOP (محاسبات علمي برنامه هاي بهينه) نيروي هوايي ايالات متحده کار جدي خود را در ژوئن 1947 شروع کرد. ماحصل آن، ابداع روش سيمپلکس توسط جورج.بي.دانتزيک[2] در پايان تابستان 1947 بود. برنامه ريزي خطي به سرعت مورد توجه اقتصاد دانان، رياضي دانان، آماردانان، و موسسات دولتي قرار گرفت. در تابستان 1949 کنفرانسي ...
حل مسائل برنامه ریزی خطی با اکسل و WinQSB
نرم افزارهای زیادی برای حل مسائل برنامه ریزی خطی که در درس پژوهش عملیاتی مطرح می شود وجود دارد مانند نرم افزار WinQSB, MATLAB, MAPLE, LINDO و LINGO که هر کدام از این نرم افزارها خصوصیت خاصی دارند برای مثال در نرم افزار متلب حل ترسیمی این مسائل کمی دشوارتر از نرم افزاری مانند WINQSB است، و نیازمند کد نویسی است. در این جا روش حل این مسائل با نرم افزار معروف اکسل مد نظر است که در لینک زیر در قالب یک فایل PDF بصورت تصویری حل این گونه مسائل بطور کامل توضیح داده شده است با لینک مثال. همچنین نرم افزار WINQSB را که حجم کمی دارد می توانید دانلود کنید.برای دانلود روی گزینه دانلود کلیک کنید.دانلود فایل راهنمای حل مسائل برنامه ریزی خطی با کسلدانلود مثال بصورت فایل اکسلدانلود نرم افزار WINQSB
برنامه ریزی خطی و معرفی نرم افزارهای ان
۲-تاریخچه برنامه ریزی خطی مسئله حل یک سیستم نامساوی خطی به زمان فوریه[۱] بر می گردد. برنامه ریزی خطی به عنوان یک مدل ریاضی به وجود آمد و در زمان جنگ جهانی دوم و پس از آن معلوم شد که طرح ریزی و هم آهنگی پروژه های مختلف و استفاده موثر از منابع کمیاب یک ضرورت است. تیم SCOOP (محاسبات علمی برنامه های بهینه) نیروی هوایی ایالات متحده کار جدی خود را در ژوئن ۱۹۴۷ شروع کرد. ماحصل آن، ابداع روش سیمپلکس توسط جورج.بی.دانتزیک[۲] در پایان تابستان ۱۹۴۷ بود. برنامه ریزی خطی به سرعت مورد توجه اقتصاد دانان، ریاضی دانان، آماردانان، و موسسات دولتی قرار گرفت. در تابستان ۱۹۴۹ کنفرانسی در برنامه ریزی و برای برنامه ریزی مخارج و برگشت ها توسعه داده شد به طوری که با مسئولیت کمیته Cowles برای تحقیق در اقتصاد برگزار شد. مقالات ارائه شده در این کنفرانس اندکی بعد در سال ۱۹۵۱ به همت T.C.Koopmans در کتابی تحت عنوان تحلیل فعالیت تولید و تخصیص جمع آوری شد.[۲]. جان وان نیومن[۳] در همان سال تئوری دو گانگی را توسعه داد و لئونید خاشیان[۴] ریاضی دان روسی ار تکنیک های ساده در اقتصاد قبل از دانتزیک استفاده کرد و جایزه نوبل را در سال ۱۹۷۵ در اقتصاد برد. مثال اصلی دانتزیک یافتن بهترین تخصیص ۷۰ نفر به ۷۰ شغل بود و هنوز موفقیت او را نشان می دهد. برای محاسبه احتیاج به نمایش همه ی جایگشت ها برای انتخاب بهترین تخصیص بسیار وسیع و غیر ممکن است. او مشاهده کرد با استفاده از الگوریتم سیمپلکس یافتن بهترین جواب فقط چند لحظه طول می کشد و همچنین متوجه شد که جواب در گوشه چند ضلعی که به وسیله قید های مسأله تشکیل می شود وجود دارد. ۳-کاربرد ها برنامه ریزی خطی کاربرد های متعددی در ارتش، حکومت، صنعت و مهندسی شهر سازی یافته است همچنین اغلب به عنوان بخشی از طرح های محاسباتی، حل مسائل برنامه ریزی غیر خطی، برنامه های گسسته، مسائل ترکیباتی، مسائل کنترل بهینه و برنامه ریزی احتمالی به کار می رود.[۲] برنامه ریزی خطی زمینه مهمی در بهینه سازی برای چندین دلیل است: بسیاری از مسائل عملی در تحقیق عملیات به عنوان مسئله برنامه ریزی خطی می تواند بیان شود و همچنین تعدادی از الگوریتم های دیگر مسائل بهینه سازی به وسیله ی حل مسائل برنامه ریزی خطی، به عنوان زیر مسئله کار می کنند. به طور تاریخی ایده های برنامه ریزی خطی الهام بخش بسیاری از مفاهیم اولیه تئوری بهینه سازی مانند دوگانگی، تجزیه، اهمیت تحدب و تعمیم آن بوده است. برنامه ریزی خطی به طور عمده در اقتصاد کلان، مدیرت تجاری، حداکثر کردن درآمد یا حداقل کردن هزینه ی تولید به کار می رود. به عنوان مثال: مدیرت موجودی، مدیرت دارایی و سهام، تخصیص منابع ...
تصمیم گیری و برنامه ریزی
تصمیم گیری و برنامه ریزی تحقیق در عملیات برنامه ریزی جزئی اساسی از مدیریت در سازمان می باشد ، اما پیش از آن تصمیم گیری درباره چگونگی ترکیب و عملکرد و مشخص کردن اهداف پیش شرطی برای برنامه ریزی در سازمان می باشد . از این جهت یکی از مسائل مهمی که در سازمان باید مورد نوجه مدیران قرار گرفته و در آینده به عنوان یکی از روش های اصلی برای تصمیم گیری مدیران از آن استفاده شود مدل سازی ریاضی از طریق فنون تحقیق در عملیات (Operational Research ) است . این روش در واقع از طریق طراحی مدل های ریاضی که به سه صورت احتمالی ، قطعی و یا می باشد این امکان را برای مدیر فراهم می آورند تا با استفاده از این روش علاوه بر تصمیم گیری صحیح در زمان تصمیم گیری با توجه به محدودیت های منابع و با هدف حداکثر کردن سود یا حداقل کردن هزینه یکی از بهترین روش ها برای تخصیص آسان منابع در زمینه های نیروی انسانی و حمل و نقل را فراهم می آورد . را در هر زمان برای سازمان اتخاذ نماید . از ویژگی های این روش نگرش سیستمی به مسائل و بررسی چند رشته ای و بین رشته ای از طریق مدل های ریاضی است . همچنین با توجه به اینکه علم کامپیوتر امروز می تواند کمک موثری در سرعت و دقت تصمیمات مدیریتی ایجاد کند ، برخی کمپانی ها در این زمینه نرم افزار هایی را تولید کرده اند که از مهمترین آنها می توان به نرم افزار های Matlab , QSB , Lindo , Lingo ,DS , Tora , Gaps و ... اشاره نمود . در اینجا به برخی از مفاهیم و بنیان های ریاضی این فن جهت اشنایی بیشتر اشاره می نماییم . مفهوم برنامه ریزی خطی : رده ای یا دسته ای از مدل های برنامه ریزی ریاضی است که مربوط می شود به مناسب ترین ترکیب از منابع محدود به فعالیت های معلوم به منظور دست یابی به هدفی مطلوب . مانند ماکزیمم کردن سود یا مینیمم کردن هزینه .خصوصیت بارز برنامه ریزی خطی این است که در آنها برنامه معرف هدف برنامه ریزی یا محدودیت ها و یا و یا قید و منابع خطی بوده و متغیر ها نیز مجهول هستند . هر تصمیم گیرنده منابعی از قبیل سرمایه یا پول ، نیروی انسانی یا کار ، مواد خام اولیه یا منابع طبیعی ماشین آلات و تجهیزات و تکنولوژی اطلاعات و مدیریت در اختیار دارد کههمگی از لحاظ کمیت و کیفیت محدود می باشند . ویژگی های برنامه ریزی خطی : 1- مشخص بودن تابع هدف به صورت خطی 2- موجود بودن راه حل های مختلف در برنامه ریزی 3- مشخص بودن محدودیت های منابع به صورت معادلات یا نامعادلات خطی 4- موجود بودن روابط ریاضی بین متغیر ها 5- غیر منفی بودن متغیر ها مدل عمومی Max یا Min z = c1x1 + c2x2 + … + cjxj + … + cnxn تابع هدف به شرطی که : A11x1+a12x2…+a1jxj+…+ a1nxn =< ...