مدل های ریاضی مسائل برنامه ریزی خطی. مدل‌های ریاضی خطی گذار از محدودیت‌های یک مدل ریاضی خطی

مبنای حل مسائل اقتصادی مدل های ریاضی هستند.

مدل ریاضیمسئله مجموعه ای از روابط ریاضی است که ماهیت مسئله را توصیف می کند.

• انتخاب متغیر وظیفه
• تدوین یک سیستم محدودیت
• انتخاب تابع هدف

متغیرهای وظیفهمقادیر X1، X2، Xn نامیده می شوند که به طور کامل فرآیند اقتصادی را مشخص می کنند. معمولاً آنها به صورت بردار نوشته می شوند: X=(X 1 , X 2 ,...,X n).

سیستم محدودیت هاوظایف مجموعه ای از معادلات و نابرابری ها هستند که منابع محدود در مسئله مورد بررسی را توصیف می کنند.

تابع هدفوظیفه تابعی از متغیرهای وظیفه نامیده می‌شود که کیفیت کار را مشخص می‌کند و حداکثر آن را باید پیدا کرد.

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

این ورودی به معنای زیر است: حداکثر تابع هدف (1) و متغیرهای متناظر X=(X 1 , X 2 ,...,X n) را بیابید مشروط بر اینکه این متغیرها سیستم قیود (2) و غیر را برآورده کنند. -شرایط منفی (3) .

راه حل قابل قبول(طرح) یک مسئله برنامه ریزی خطی هر بردار n بعدی X=(X 1 , X 2 ,...,X n) است که سیستم محدودیت ها و شرایط غیر منفی را برآورده می کند.

مجموعه راه‌حل‌های عملی (طرح‌ها) مسئله شکل می‌گیرد طیف وسیعی از راه حل های عملی(ODR).

راه حل بهینه(طرح) یک مسئله برنامه‌ریزی خطی، راه‌حل (طرح) عملی مسئله است که در آن تابع هدف به حداکثر می‌رسد.

نمونه ای از تدوین مدل ریاضی

وظیفه استفاده از منابع (مواد اولیه)

وضعیت:برای ساخت n نوع محصول از m نوع منابع استفاده می شود. یک مدل ریاضی بسازید.

شناخته شده:

• b i (i = 1،2،3،...،m) ذخایر هر iمین نوع منبع است.
• a ij (i = 1,2,3,...,m؛ j=1,2,3,...,n) هزینه‌های هر iمین نوع منبع برای تولید حجم واحد است. j-امین نوع محصول؛
• c j (j = 1,2,3,...,n) سود حاصل از فروش یک واحد حجم از نوع j-ام محصول است.

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

راه حل:

ما یک بردار از متغیرهای X=(X 1 , X 2 ,...,X n) را معرفی می کنیم که در آن x j (j = 1,2,...,n) حجم تولید نوع j است. تولید - محصول.

هزینه های منبع iام برای تولید حجم معین x j از محصولات برابر با ij x j است، بنابراین محدودیت استفاده از منابع برای تولید انواع محصولات به شکل زیر است:
سود حاصل از فروش نوع j محصول برابر با c j x j است، بنابراین تابع هدف برابر است با:

پاسخ- مدل ریاضی به صورت زیر است:

شکل متعارف یک مسئله برنامه ریزی خطی

در حالت کلی، یک مسئله برنامه ریزی خطی به گونه ای نوشته می شود که هم معادلات و هم نابرابری ها قیود هستند و متغیرها می توانند غیرمنفی یا خودسرانه تغییر کنند.

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

می توان آن را به صورت مختصات، بردار و نماد ماتریسی نشان داد.

مسئله برنامه ریزی خطی متعارف در نماد مختصات به شکل زیر است:

مسئله برنامه نویسی خطی متعارف در نمادگذاری ماتریس به شکل زیر است:

• A ماتریس ضرایب سیستم معادلات است
• X یک ماتریس ستونی از متغیرهای وظیفه است
• Ao ماتریس-ستون قسمت های سمت راست سیستم محدودیت است

غالباً از مسائل برنامه ریزی خطی استفاده می شود که به آنها متقارن می گویند که در نمادهای ماتریسی به شکل زیر است:

کاهش یک مسئله برنامه ریزی خطی عمومی به شکل متعارف

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

یک نابرابری خطی a 1 x 1 +a 2 x 2 +...+a n x n ≤b را در نظر بگیرید و مقداری x n+1 را به سمت چپ آن اضافه کنید تا نابرابری به تساوی a 1 x 1 +a 2 x 2 + تبدیل شود. ...+a n x n +x n+1 =b. علاوه بر این، این مقدار x n+1 غیر منفی است.

بیایید همه چیز را با یک مثال در نظر بگیریم.

مشکل برنامه ریزی خطی را به شکل متعارف کاهش دهید:

راه حل:
بیایید به مسئله یافتن حداکثر تابع هدف برویم.
برای این کار، علائم ضرایب تابع هدف را تغییر می دهیم.
برای تبدیل نابرابری های دوم و سوم سیستم محدودیت به معادله، متغیرهای اضافی غیر منفی x 4 x 5 را معرفی می کنیم (این عمل با حرف D در مدل ریاضی مشخص شده است).
متغیر x 4 در سمت چپ نابرابری دوم با علامت "+" وارد می شود، زیرا نابرابری به شکل "≤" است.
متغیر x 5 در سمت چپ نابرابری سوم با علامت "-" وارد می شود، زیرا نابرابری به شکل "≥" است.
متغیرهای x 4 x 5 با یک ضریب وارد تابع هدف می شوند. برابر با صفر
مسئله را به صورت متعارف می نویسیم.

T10. بیان مسئله برنامه ریزی خطی

مدل ریاضییک مسئله اقتصادی مجموعه ای از روابط ریاضی است که فرآیند اقتصادی را توصیف می کند.

برای تدوین یک مدل ریاضی، لازم است:

1. متغیرهای وظیفه را انتخاب کنید.

2. یک سیستم محدودیت ها را تنظیم کنید.

3. تابع هدف را تنظیم کنید.

متغیرهای وظیفهمقادیر x 1 , x 2 ,…, x n نامیده می شوند که به طور کامل فرآیند اقتصادی را مشخص می کند. آنها معمولاً به عنوان یک بردار X \u003d (x 1، x 2، ...، x n) نوشته می شوند.

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

تابع هدف نامیده می شودتابع F(X) = f(x 1 , x 2 ,…, x n) از متغیرهای وظیفه که کیفیت کار را مشخص می کند و حداکثر آن را باید پیدا کرد.

مسئله عمومی برنامه ریزی ریاضیبه صورت زیر فرموله می شود: متغیرهای وظیفه x 1 , x 2 ,…, x n را پیدا کنید که حداکثر تابع هدف را ارائه می کند.

F (X) \u003d f (x 1، x 2، ...، x n) ® حداکثر (دقیقه) (2)

و سیستم قیود (1) را برآورده کند.

اگر تابع هدف (2) و سیستم محدودیت (1) خطی باشند، مسئله برنامه ریزی ریاضی نامیده می شود. مسئله برنامه ریزی خطی (LPP).

بردار X (مجموعه ای از متغیرهای وظیفه) نامیده می شود راه حل قابل قبول، یا طرح PLP، در صورتی که سیستم محدودیت ها (1) را برآورده کند. یک طرح X عملی که حداکثر تابع هدف را فراهم می کند نامیده می شود راه حل بهینه ZLP.

2. نمونه هایی از تدوین مدل های ریاضی مسائل اقتصادی

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

1.مشکل طرح تولید بهینه

برای تولید دو نوع محصول T 1 و T 2 از سه نوع منبع S 1 , S 2 , S 3 استفاده می شود. موجودی منابع، تعداد واحدهای منابع صرف شده برای ساخت یک واحد تولیدی و همچنین سود حاصل از فروش یک واحد تولیدی در جدول نشان داده شده است:

باید چنین طرحی برای تولید محصولاتی یافت که سود حاصل از فروش آن حداکثر باشد.

راه حل.

بیایید x 1، x 2 را نشان دهیم - تعداد واحدهای تولید، به ترتیب، T 1 و T 2، برنامه ریزی شده برای تولید. برای ساخت آنها، (x 1 + x 2) واحد از منبع S 1، (x 1 + 4x 2) واحد از منبع S 2، (x 1) واحد از منبع S 3 مورد نیاز است. مصرف منابع S 1 , S 2 , S 3 نباید از ذخایر آنها به ترتیب 8، 20 و 5 واحد بیشتر باشد.

سپس مدل اقتصادی-ریاضی مسئله را می توان به صورت زیر فرموله کرد:

یک طرح تولید X \u003d (x 1، x 2) پیدا کنید که سیستم محدودیت ها را برآورده کند:

و شرایط

که تحت آن تابع حداکثر مقدار را می گیرد.

مشکل را می توان به راحتی در مورد تولید n نوع محصول با استفاده از m نوع منابع تعمیم داد.

2.مشکل رژیم غذایی بهینه

دو نوع غذای K 1 و K 2 حاوی مواد مغذی S 1، S 2 و S 3 وجود دارد. محتوای تعداد واحدهای غذایی در 1 کیلوگرم از هر نوع خوراک، حداقل مواد مغذی مورد نیاز و همچنین هزینه 1 کیلوگرم خوراک در جدول نشان داده شده است:

لازم است یک جیره روزانه با حداقل هزینه تهیه شود که در آن محتوای هر نوع ماده غذایی کمتر از حد تعیین شده نباشد.

راه حل.

بیایید x 1، x 2 را نشان دهیم - مقدار خوراک K 1 و K 2 موجود در رژیم غذایی روزانه. سپس این رژیم شامل (3x 1 + x 2) واحد مواد مغذی S 1، (x 1 + 2 x 2) واحدهای ماده S 2، (x 1 + 6 x 2) واحد مواد مغذی S 3 خواهد بود. از آنجایی که محتوای مواد مغذی S 1، S 2 و S 3 در جیره باید به ترتیب 9، 8 و 12 واحد باشد، مدل اقتصادی-ریاضی مسئله را می توان به صورت زیر فرموله کرد:

یک رژیم غذایی روزانه X \u003d (x 1، x 2) بنویسید که سیستم محدودیت ها را برآورده کند:

و شرایط

که تحت آن تابع حداقل مقدار را می گیرد.

فرم های ضبط PLP

در LLP، لازم است حداکثر تابع هدف خطی را پیدا کنید:

با محدودیت:

و شرط عدم منفی

که در آن a ij , b i , c j ( , ) ثابت داده می شود.

ZLP به این صورت نوشته می شود عمومیفرم. اگر سیستم محدودیت فقط شامل نابرابری باشد، LLP در نمایش داده می شود استانداردفرم. متعارف (اصلی)شکل نماد ZLP زمانی است که سیستم محدودیت ها فقط دارای برابری باشد. بنابراین LLP های فوق به صورت استاندارد نوشته شده اند.

اشکال کلی، استاندارد و متعارف LLP معادل هستند به این معنا که هر یک از آنها با کمک تبدیل های ساده می توانند به شکل متفاوتی بازنویسی شوند. به این معنی که اگر راهی برای حل یکی از این مشکلات وجود داشته باشد، می توان برنامه بهینه برای هر یک از مشکلات را تعیین کرد.

برای حرکت از یک شکل نمادگذاری LLP به شکل دیگر، باید بتوان از محدودیت‌های نابرابری به محدودیت‌های برابری و بالعکس حرکت کرد.

یک قید نابرابری (£) را می توان با اضافه کردن یک متغیر غیر منفی اضافی به سمت چپ آن به یک قید برابری تبدیل کرد و یک محدودیت نابرابری (3) را می توان با کم کردن یک متغیر غیر منفی اضافی از آن به یک قید برابری تبدیل کرد. سمت چپ. تعداد متغیرهای غیر منفی اضافی معرفی شده برابر با تعداد محدودیت های نابرابری تبدیل شده است.

معرفی کرد متغیرهای اضافی تا حدی منطق اقتصادی دارند. بنابراین، اگر محدودیت های PLP اصلی منعکس کننده مصرف و در دسترس بودن منابع باشد، آنگاه مقدار متغیر اضافی PLP به شکل متعارف برابر با حجم منبع متناظر استفاده نشده است.

مثال 1. به شکل متعارف ZLP بنویسید:

با محدودیت:

راه حل.

تابع هدف بدون تغییر باقی می ماند:

سیستم نابرابری ها به سیستم برابری ها تبدیل می شود:

هنگام حل LLP با روش گرافیکی، انتقال از فرم متعارف به فرم استاندارد مورد نیاز است.

برای آوردن LLP به یک فرم استاندارد، استفاده کنید روش جردن-گاوسراه حل های SLAU برخلاف روش گاوس که در آن ماتریس توسعه‌یافته سیستم به شکل پله‌ای کاهش می‌یابد، در روش جردن-گاوس، یک ماتریس هویت به عنوان بخشی از ماتریس توسعه‌یافته تشکیل می‌شود. بنابراین، حرکت معکوس در اینجا لازم نیست.

برای تبدیل LLP متعارف اصلی به LLP استاندارد معادل:

الف) یک عنصر غیر صفر یک qp در ماتریس توسعه یافته سیستم محدودیت انتخاب شده است. این عنصر نامیده می شود سهل گیر، و q - i سطر و ستون p-امین به نام enable row و enable column.

ب) رشته حل بدون تغییر بازنویسی می شود و تمام عناصر ستون حل کننده به جز ستون حل، با صفر جایگزین می شوند. عناصر باقی مانده از ماتریس تقویت شده با استفاده از "قاعده مستطیل" تعیین می شوند:

چهار عنصر ماتریس منبسط شده را در نظر بگیرید: عنصر a ij که باید تبدیل شود، عنصر حل کننده a qp و عناصر a i p و a qj. برای یافتن عنصر a ij، از عنصر a ij نتیجه می‌گیریم که حاصل ضرب عناصر a i p و qj را که در رئوس مخالف مستطیل قرار دارند، بر عنصر تفکیک‌کننده a qp تفریق کنیم:

ج) مجهولات مجاز به طور همزمان از تابع هدف حذف می شوند. برای انجام این کار، ضرایب تابع هدف در ماتریس گسترش یافته در ردیف آخر نوشته می شود. محاسبات در نظر می گیرند که عنصر فعال در خط آخر نمی تواند انتخاب شود.

مثال 2. تغییر به فرم استاندارد:

راه حل.

با استفاده از روش جردن-گاوس، ما سیستم معادلات محدودیت LLP را به یک سیستم معادل از نابرابری ها می آوریم. بیایید عنصر سوم ردیف اول را به عنوان عنصر حل انتخاب کنیم:

عدد 9- بدست آمده در ستون آخر سطر آخر باید روی تابع هدف با علامت مخالف نوشته شود. در نتیجه تحولات، LLP شکل زیر را به خود می گیرد:

زیرا متغیرهای x 2 و x 3 غیر منفی هستند، سپس با کنار گذاشتن آنها، می‌توانیم ZLP را به شکل متقارن بنویسیم:

در شکل متعارف LLP، تابع هدف را می توان هم کمینه و هم حداکثر کرد. رفتن از یافتن حداکثر به یافتن حداقل یا برعکس، کافی است علائم ضرایب تابع هدف را تغییر دهید: F 1 = - F. مسئله حاصل و LLP اصلی دارای راه حل بهینه یکسان هستند و مقادیر توابع هدف در این راه حل فقط در این راه حل متفاوت است. امضا کردن.

خواص ZLP

1. مجموعه تمام راه حل های قابل قبول سیستم محدودیت های یک مسئله برنامه ریزی خطی محدب است.

مجموعه نقاط نامیده می شود محدب، در صورتی که شامل کل بخش متصل کننده هر دو نقطه از این مجموعه باشد.

طبق این تعریف، چند ضلعی در شکل 1a یک مجموعه محدب است، در حالی که چند ضلعی در شکل 1b چنین نیست، زیرا قطعه MN بین دو نقطه M و N آن به طور کامل به این چندضلعی تعلق ندارد.

مجموعه های محدب می توانند نه تنها چند ضلعی باشند. نمونه هایی از مجموعه های محدب عبارتند از دایره، بخش، قطعه، مکعب، هرم و غیره.

2. اگر LLP راه حل بهینه داشته باشد، تابع خطی حداکثر (حداقل) مقدار را در یکی از نقاط گوشه چندوجهی تصمیم می گیرد. اگر یک تابع خطی یک مقدار حداکثر (حداقل) را در بیش از یک نقطه گوشه بگیرد، آنگاه آن را در هر نقطه ای می گیرد که ترکیب خطی محدب این نقاط باشد.

نقطه X نامیده می شود ترکیب خطی محدبنقاط X 1 , X 2 ,…, X n در صورتی که شرایط زیر وجود داشته باشد:

X \u003d α 1 X 1 + α 2 X 2 + ... + α n X n،

αj ≥ 0، Σαj = 1.

واضح است که در حالت خاص برای n = 2 یک ترکیب خطی محدب از دو نقطه، قطعه ای است که آنها را به هم متصل می کند.

3. هر راه حل پایه مجاز سیستم محدودیت LLP متعارف مربوط به یک نقطه گوشه از چند وجهی محلول است، و بالعکس، به هر نقطه گوشه چند وجهی محلول، یک راه حل اساسی قابل قبول مربوط است.

از دو ویژگی آخر چنین برمی‌آید که اگر یک LLP راه‌حل بهینه داشته باشد، حداقل با یکی از راه‌حل‌های اساسی قابل قبول آن مطابقت دارد.

بنابراین، حداکثر تابع خطی LLP باید در میان تعداد محدودی از راه‌حل‌های پایه قابل قبول آن جستجو شود.

مفاهیم اولیه مدل سازی

در روند زندگی انسان، ایده هایی در مورد ویژگی های خاص اشیاء واقعی و تعاملات آنها ایجاد می شود. این بازنمایی ها توسط شخص به شکل توصیف اشیایی که زبان توصیف برای آنها استفاده می شود، شکل می گیرد. این می تواند یک توصیف شفاهی (مدل های کلامی)، یک طراحی، یک طراحی، یک نمودار، یک طرح و غیره باشد. همه موارد فوق در یک مفهوم خلاصه می شود. مدل،و فرآیند ساخت مدل مدل سازی

مدل سازیروشی جهانی برای مطالعه فرآیندها و پدیده های دنیای واقعی است. مدل سازی در مطالعه اشیایی که برای مشاهده و تحقیق مستقیم غیرقابل دسترس هستند از اهمیت ویژه ای برخوردار است. اینها به طور خاص شامل پدیده ها و فرآیندهای اجتماعی-اقتصادی است.

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

اقتصاد- این یک سیستم تولید اجتماعی است که تولید، توزیع، مبادله و مصرف واقعی کالاهای مادی لازم برای جامعه را انجام می دهد.

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

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

یک مسئله برنامه ریزی خطی از یک تابع هدف، یک سیستم از محدودیت ها و یک شرط برای غیر منفی بودن متغیرها تشکیل شده است.

اجازه دهید تابع nمتغیرها باید بزرگترین یا کوچکترین مقدار این تابع را پیدا کرد، مشروط بر اینکه آرگومان

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

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

حداکثر تابع را پیدا کنید

تحت محدودیت

تحت شرایط غیر منفی

اجازه دهید نماد را معرفی کنیم:

سهام من-ام نوع منبع؛

هزینه ها من- نوع منبع برای تولید j- نوع محصول؛

سود واحد j- نوع محصول

در نمادگذاری فشرده، مسئله برنامه ریزی خطی به شکل زیر است:

نماد فشرده نشان می دهد که مدل یک مسئله برنامه ریزی خطی کلی شامل پنج عنصر اصلی است:

متغیرهایی که ارزش آنها در فرآیند حل مسئله یافت می شود.

ضرایب فنی و اقتصادی برای متغیرهای موجود در محدودیت ها.

حجم سمت راست نابرابری ها که به آنها ثابت مسئله می گویند.

ضرایب متغیرهای تابع هدف که تخمین متغیر نامیده می شود.

شاخص متغیر؛

شاخص محدودیت

تابع هدف(تابع هدف) یک عبارت ریاضی است که می خواهید برای آن حداکثر، یعنی حداکثر یا حداقل مقدار را پیدا کنید.

متغیرهای x jانواع و روش‌های فعالیتی را که ابعاد آن ناشناخته است و باید در مسیر حل مشکل مشخص شود، تعیین کنید. معمولاً در وظایف کشاورزی، متغیرها به معنای اندازه مورد نظر شاخه های اقتصاد، انواع خوراک در جیره، برندهای تراکتور و ماشین آلات کشاورزی و ... است. یک محصول یا نوع دام ممکن است با بیش از یک متغیر با توجه به شرایط خاص بیان شود. به عنوان مثال، غلات کالا و علوفه; ذرت برای غلات، سیلو، علوفه سبز؛ علف های چند ساله برای یونجه، یونجه، علوفه سبز، پودر علف و دانه ها و غیره.

متغیرها می توانند خودسرانه تحت شرایط مسئله مورد بررسی تغییر کنند. متغیر , که ضرایب آن یک ستون واحد نامیده می شود پایه ای.متغیرهای پایه تشکیل می شوند اساس واحدسیستم های. متغیرهایی که در پایه واحد گنجانده نشده اند فراخوانی می شوند رایگان.

تعداد کل متغیرهای موجود در کار با توجه به ماهیت کار، شرایط خاص تولید، توانایی جمع آوری اطلاعات و غیره تعیین می شود.

متغیرها را می توان در واحدهای اندازه گیری مختلف بیان کرد: ha، q، kg، pcs، heads و غیره. از نظر ماهیت، متغیرها به اصلی، اضافی و کمکی تقسیم می شوند. متغیرهای اصلی شامل انواع فعالیت های مورد نظر است: بخش های اقتصاد، انواع خوراک، مارک های خودرو. متغیرهای اضافی به متغیرهایی گفته می شود که در فرآیند تبدیل نابرابری ها به معادله تشکیل می شوند. آنها می توانند به معنای بخشی از منابع کم استفاده باشند، مازاد بر سمت راست نابرابری (اگر این نابرابری از نوع "نه دیگر" باشد). متغیرهای کمکی به منظور تعیین مقادیر تخمینی منابع تولید به دست آمده، مقادیر تخمینی شاخص های کارایی اقتصادی تولید در کار گنجانده شده است.

متغیرهای اضافی و کمکی همیشه دارای ضرایب واحد (1+ یا -1) هستند.

ضرایب فنی و اقتصادی (a ij)با متغیرهایی در سیستم محدودیت ها، نرخ ورودی منابع تولید یا نرخ خروجی در واحد اندازه گیری متغیر را بیان می کنند.

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

نرخ‌های مصرف منابع اغلب از کتاب‌های مرجع تعیین می‌شوند؛ آنها باید با شرایط خاص مربوطه تنظیم شوند. فاکتورهای عملکرد محصول بر اساس بازده محصول برنامه ریزی شده و بهره وری دام محاسبه می شود.

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

محدودیت های سمت راست (b i)ثابت نامیده می شوند، یعنی. مقادیر ثابت اینها شامل حجم منابع تولید - زمین، نیروی کار، تجهیزات، کود، سرمایه گذاری و غیره است. منابع تولید باید با در نظر گرفتن وضعیت واقعی آنها تعیین شود و حتماً دوره برنامه ریزی در نظر گرفته شود. علاوه بر این، آن دسته از منابع تولیدی که استفاده از آنها در طول سال نابرابر است، نه تنها برای کل سال، بلکه برای دوره‌ها یا ماه‌های پرمشغله (منابع کار) نیز محاسبه می‌شود.

منابع تولید در واحدهای مختلفی تعریف می شود: زمین - بر حسب هکتار، منابع نیروی کار - بر حسب روز انسان یا ساعت کار، تجهیزات - به تعداد شیفت ماشین، شیفت یا تولید روزانه و غیره.

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

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

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

محدودیتیک عبارت ریاضی است که متغیرها را در قالب برابری ها و نابرابری ها مرتبط می کند. همه محدودیت ها شکل می گیرد سیستم محدودیت هاوظایف سیستم قیود در شکل ریاضی شرایط مسئله را مشخص می کند. کامل بودن انعکاس این شرایط به ترکیب محدودیت ها بستگی دارد. بنابراین، هنگام تعیین تعداد محدودیت ها، دو شرایط باید در نظر گرفته شود:

فقط آن شرایطی را که واقعاً امکانات تولید را محدود می کند در مسئله منعکس کند.

v محدودیت های زیاد، اندازه مسئله را افزایش می دهد و آن را غیرقابل حل می کند

محدودیت ها سه نوع هستند: مساوی (=)، نابرابری های نوع کمتر یا مساوی با (≤)، نابرابری های نوع بزرگتر یا مساوی با (≥). مثلا،

جایی که من = 1, 2, … , متر. ضرایب برای متغیرها مشخص می شود aij، جایی که شاخص من- شماره محدودیت، شاخص jتعداد متغیر است، اعضای آزاد (سمت راست محدودیت ها) نشان داده می شوند b i، فهرست مطالب من- شماره محدودیت

محدودیت های نوع اول را محدودیت های بالایی می نامند، زیرا سمت چپ نابرابری نمی تواند از مقدار معینی (ثابت) تجاوز کند. محدودیت های نوع سوم را محدودیت های پایین تر می نامند، زیرا سمت چپ نابرابری نمی تواند کمتر از مقدار معینی (ثابت) باشد.

از نظر معنا، تمام محدودیت ها را می توان به اساسی، اضافی و کمکی تقسیم کرد.

محدودیت های اصلی هستنداینها آنهایی هستند که با همه یا اکثر متغیرهای وظیفه همپوشانی دارند. به عنوان یک قاعده، با کمک آنها، شرایط اصلی کار منعکس می شود - برای زمین، نیروی کار، خوراک، مواد مغذی، فناوری و غیره.

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

محدودیت های کمکی،به عنوان یک قاعده، آنها معنای مستقلی ندارند و برای رسمی کردن شرایط فردی به مشکل وارد می شوند. اینها شامل محدودیت هایی است که رابطه ای متناسب بین متغیرهای فردی یا گروه های آنها ایجاد می کند.

ارزیابی متغیرها در تابع هدف (با ی) ضرایبی هستند که میزان درآمد یا هزینه کل در واحد اندازه گیری متغیر را بیان می کنند. ارزیابی متغیر، به عنوان یک قاعده، معیار پذیرفته شده بهینه بودن را بیان می کند. می توان آن را هم به صورت نقدی و هم به صورت نقدی ارائه کرد، یعنی. هزینه های هر واحد تولید (هزینه تولید).

شرط منفی نبودن متغیرها به صورت نوشته می شود

xj≥ 0، j = 1، 2، …، n.

در زندگی واقعی تولید، بر اساس شرایط کار، با توجه به این رکورد از مدل اقتصادی و ریاضی ساختاری (EMM)، فهرستی از متغیرها و محدودیت‌ها تهیه می‌شود، اطلاعات اولیه تهیه می‌شود، یک کار دقیق EMM ساخته می‌شود. که سپس به صورت ماتریس (جدول) نوشته می شود، وارد کامپیوتر می شود و طبق برنامه مربوطه، نتایج محاسبه و تجزیه و تحلیل می شود.i = 1, …, متر, (1.5)

j = 1, …, n. (1.6)

بردار ایکس = (ایکس 1 , ایکس 2 , …, ایکس n) اجزاء xjکه قیود (1.2) و (1.3) را برآورده کند [یا (1.5) و (1.6) در حداقل مسئله] نامیده می شود. راه حل قابل قبولیا طرح قابل قبولوظایف LP مجموعه تمام طرح های قابل قبول نامیده می شود بسیاری از برنامه های ممکن

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

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

قانون کاهش یک مسئله برنامه ریزی خطی به شکل متعارفشامل موارد زیر است:

1) اگر در مسئله اصلی نیاز به تعیین حداکثر یک تابع خطی است، باید علامت را تغییر دهید و به دنبال حداقل این تابع باشید.

2) اگر سمت راست محدودیت ها منفی باشد، این محدودیت باید در -1 ضرب شود.

3) اگر بین محدودیت ها نابرابری وجود داشته باشد، با معرفی متغیرهای اضافی متغیرهای غیرمنفی، آنها به برابری تبدیل می شوند. به عنوان مثال، متغیرهای اضافی Sjمحدودیت های نوع کمتر یا مساوی (£) با علامت مثبت وارد می شوند:

متغیرهای اضافی Sjمحدودیت های نوع بزرگتر یا مساوی (≥) با علامت منفی وارد می شوند:

برای حذف منفی بودن متغیرهای اضافی - Sjمتغیرهای مصنوعی را با علامت + معرفی کنید ام جیبا مقادیر بسیار بزرگ

سخنرانی 2

که در شکل متعارف

راه حل قابل قبول PLP(طرح قابل قبول).

راه حل بهینه LLP

ضرورت

مثال.

بیایید مشکل را در آن بنویسیم شکل متعارف

موقعیت های ویژه راه حل گرافیکی ZLP

مگر زمانی که وظیفه باشد تنها راه حل بهینهبرای و، می تواند باشد موقعیت های خاص:

1. وظیفه دارد تعداد بی نهایت راه حل بهینه - حداکثر تابع در بخش رسیده است ( بهینه جایگزین)- شکل 2؛

2. وظیفه قابل حل نیست به دلیل نامحدود بودن ODR، یا - شکل 3.

3. ODR - نقطه واحد آه، پس؛

4. وظیفه قابل حل نیست اگر ODR یک منطقه خالی داشته باشد.

آ

شکل 2 شکل 3

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

پارامتر کجاست برای هر مقدار از 0 تا 1، می توانید تمام نقاط بخش را بدست آورید که برای هر کدام از آنها تابع یک مقدار را می گیرد. از این رو نام - جایگزین بهینه.

مثال. حل گرافیکی مسئله برنامه ریزی خطی ( بهینه جایگزین):

سوالاتی برای خودکنترلی

1. مسئله برنامه ریزی خطی را به صورت کلی بنویسید.

2. مسئله برنامه ریزی خطی را به صورت متعارف و استاندارد بنویسید.

3. برای انتقال از شکل عمومی یا استاندارد یک مسئله برنامه ریزی خطی به حالت متعارف از چه تبدیلی می توان استفاده کرد؟

4. تعریفی از راه حل های امکان پذیر و بهینه برای مسئله برنامه ریزی خطی ارائه دهید.

5. کدام یک از راه حل ها "بهترین" برای مشکل کمینه سازی تابع اگر ?

6. کدام یک از راه حل ها "بهترین" برای مشکل به حداکثر رساندن تابع اگر ?

7. فرم استاندارد مدل ریاضی مسئله برنامه ریزی خطی را با دو متغیر بنویسید.

8-نحوه ساختن نیم صفحه ای که توسط نابرابری خطی با دو متغیر به دست می آید ?

9. حل سیستم نامساوی خطی با دو متغیر را چه می نامند؟ دامنه راه حل های امکان پذیر چنین سیستمی از نابرابری های خطی را روی صفحه بسازید که:

1) راه حل منحصر به فردی دارد.

2) مجموعه بی نهایت راه حل دارد.

3) راه حلی ندارد.

10. برای یک تابع خطی بنویسید گرادیان برداری، نوع خطوط سطح را نام ببرید. خطوط گرادیان و تراز چگونه نسبت به یکدیگر قرار دارند؟

11. یک الگوریتم برای یک روش گرافیکی برای حل یک LLP استاندارد با دو متغیر فرموله کنید.

12. چگونه مختصات و مقادیر راه حل را پیدا کنیم؟

13. مساحت راه حل های امکان پذیر، خطوط گرادیان و سطح را برای مسائل برنامه ریزی خطی بسازید که در آنها:

1) در یک نقطه به دست می آید، و - در بخش ODR.

2) در یک نقطه از ODS به دست می آید و .

14. یک تصویر هندسی از LLP ارائه دهید اگر:

1) دارای راه حل های بهینه منحصر به فرد برای و ;

2) دارای مجموعه ای از راه حل های بهینه برای .

سخنرانی 2

روش گرافیکی برای یافتن جواب بهینه

1. اشکال مدل های ریاضی خطی و تبدیل آنها

2. روش گرافیکی برای حل مسئله برنامه ریزی خطی

3. موقعیت های خاص راه حل گرافیکی LLP

4. حل گرافیکی مسائل اقتصادی برنامه ریزی خطی

اشکال مدل های ریاضی خطی و تبدیل آنها

یک مدل ریاضی یک مسئله برنامه ریزی خطی (LPP) را می توان به یکی از سه شکل نوشت.

که در شکل کلی مدل ریاضیبرای یافتن حداکثر یا حداقل تابع هدف مورد نیاز است. سیستم محدودیت شامل نابرابری ها و معادلات است. همه متغیرها نمی توانند غیر منفی باشند.

که در شکل متعارفمدل ریاضی باید حداکثر تابع هدف را پیدا کند. سیستم محدودیت فقط از معادلات تشکیل شده است. همه متغیرها غیر منفی هستند.

در شکل استاندارد یک مدل ریاضی، باید حداکثر یا حداقل یک تابع را پیدا کرد. همه محدودیت ها نابرابری هستند. همه متغیرها غیر منفی هستند.

حل سیستم قیودی که شرایط عدم منفی بودن متغیرها را برآورده می کند نامیده می شود. راه حل قابل قبول PLP(طرح قابل قبول).

مجموعه راه حل های امکان پذیر نامیده می شود حوزه راه حل های امکان پذیر LLP.

یک راه حل امکان پذیر، که در آن تابع هدف به یک مقدار شدید می رسد، نامیده می شود راه حل بهینه LLP

سه شکل LLP معادل هستند به این معنا که هر یک از آنها را می توان با کمک تبدیل های ریاضی به شکل متفاوتی کاهش داد.

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

انتقال به نماد متعارف ZLP.

مثال.

بیایید مشکل را در آن بنویسیم شکل متعارف، وارد کردن یک متغیر اضافی (موازنه) با علامت "+" در سمت چپ نابرابری اول سیستم محدودیت و یک متغیر اضافی با علامت "منهای" در سمت چپ نابرابری دوم.

معنای اقتصادی متغیرهای اضافی مختلف ممکن است یکسان نباشد: این بستگی به معنای اقتصادی محدودیت‌هایی دارد که این متغیرها در آن گنجانده شده‌اند.

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