تحقیق در مورد برنامه نویسی خطی

بخشی از مقاله

برنامه نویسی خطی

کاربردها
دیدگاه اساسی دارای کاربردهای مهم در زیر برنامه نویسی خطی است. یکی از این کاربردها شامل روش ساده سازی تجدید نظر شما می باشد. همانطور که در بخش قبلی (جدول 8-5) شرح داده شد. این روش از برای محاسبه خود فراتر می رود.
کاربرد دیگر شامل تفسیر قیمت های سایه که در بخش 7-4 شرح داده شده میس باشد. دیدگاه پایه نشان میدهد که (مقدار z برای راه حل بهینه) زیر است.
بنابراین برای مثال:

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

آوردن یک راه حل بهینه (و نیز s,y) برای الگوی اصلی به کار برده می شود و سپس این تغییرات صورت می گیرد. اگر توالی مشابه عملکردهای جبری برای جدول اوسید بازبینی شده به کار رود. تغییرات حاصل در جدول نهایی چه خواهد بود. چون s,y تغییر نمی کند دیدگاه پایه پاسخ را نشان می دهد. برای مثال تغییر از تا را که در شکل 4.8 آمده است برای مسئله شرکت ویندوز گلاس در نظر بگیرید. حل کردن برای راه حل بهینه جدید الزامی نیست. چون مقادیر متغیرهای پایه در جدول نهایی (ط) با دیدگاه پایه آشکار می شود.

یک روش ساده تر برای انجام این محاسبه وجود دارد ، چون تنها تغییر در مولفه ثانیویه صورت می گیرد. که از طریق ضرب کردن در ستون ثانویه s صورت می گیرد. تغییر در b را می توان به شکل زیر محاسبه کرد.

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

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

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

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

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

مسئله:
نمادهای قرار گرفته در سمت چپ مسئله ها (یا بخشی از آنها دارای معانی زیر می باشد).
D مثال بازنمایی بیان شده در بالا می تواند مفید باشد.
I شما می توانید برخی از کارهای خود را با استفاده از روش های کنش متقابل فوق الذکر برای روش ساده سازی اصلی بررسی کنید.
نماد در شماره مسئله نشان می دهد که حداقل یک پاسخ نسبی در پشت کتاب داده می شود.
1-1-5 مسئله زیر را درنظر بگیرید.
حداکثر در معرض و
(a) این مسئله را بصورت گرافیکی حل کنید. راه حلهای CPF را با خط کشیدن با آنها روی نمودار شناسایی کنید
B همه مجموعه های 2 معادله نعریف شده برای این مسئله شناسایی کنید. برای هر مجموعه راه حل مربوط به راه حل نقطه مقطه گوشه را معین کنید و سپس آن را به عنوان یک راه حل CPF یا راه حل نقطه – گوشه طبقه بندی کنید.
C متغیرهای نمونه را به منظور نوشتن محدودهای عملکردی در شکل افزوده معرفی کنید. از این متغیرها برای شناسایی راه حلهای پایرای کم با هر راه حل نقطه – گوشه یافت شده ر بخش b متناسب است ، استفاده کنید.

D روش زیررا برای هر مجموعه از دو معادله تعریف شده شناسایی کنید.
مجموعه معادلات از بخش c بعد از حذف این دو متغیر غیر پایه را نشان دهد سپس از مجموعه آخر معادلات برای حل دو متغیر باقی مانده (متغیر پایه) استفاده کنید. راه حل پایه حاص را برای راه حل پایه متناسب بدست آمده در بخش c مقایسه کنید.

E بدون اجرای روش شاده سازی از بازنمایی هندسی آن برای شناسایی مسیر (توالی راه حلهای CPF) استفاده کنید. این روش برای رسیدن به راه حل بهینه استفاده می شود. برای هر یک از ین راه حل های CPF تصمیم گیرهای زیر را که برای محاسبه بعدی انجام شده شناسایی کنید.
از کدام معادله تعریف شده حذف و کدامیک اضافه می شود.

2- کدام متغیر نمایشگر حذف می شود (متغیر پایه ورودی) و کدامیک اضافه می شود (متغیر پایه باقی مانده)
2-1-5 مسئله -1-5 را برای الگوی 5-1-3 تکرار کنید.
3-1-5 مسئله زیر را در نظر بگیرید.

حداکثر در قبال و
A این مسئله را بصورت گرافیکی حل کنید. راه حل های CPF را با خط کشیده دور انها روی نمودار شناسایی کنید.
b جدولی را توسعه دهید که هر یک لز راه حلهای CPF و معادلات تعریف کننده متناسب ، راه حل EF و متغیرهای غیر پایه را ارائه می دهد. z را برای هر یک از این راه حلها محاسبه کنید و از این اطلاعات برای شناسایی راه حل بخهینه استفاده کنید.
C جدول متناسب برای راه حلهای نقطه ، گوشه را توسعه دهید و مجموعه های معادلات تعریف کننده و متغیرهای غیر پایه را که راه حلی را به دست نمی دهد ، شناسایی نمایید.

4-1-5 مسئله زیر را در نظر بگیرید.
حداکثر در قبال و پس از اینکه متغیرها معرفی شدند و سپس یک روش کامل شیوه ساده سازی اجرا شد. جدول ساده سازی یزر بدست می آید.
A راه حل CPF بدست آمده در رابطه یک را شناسایی کنید.

b معادلات مرزی محدود که این راه حل CPF را تعریف می کند ، شناسایی کند.
5-1-5 مسئله برنامه نویسی خطی سه متغیر نشان داده شده در شکل 2-5 را در نظر بگیرید.
حداکثر در قبال و

a این مسئله را بصورت گرافیکی حل کنید.
b جدولی را توسعه دهید که هر یک از راه حل های CPT و معادلات تعریف کننده متناسب ، راه حلها bF و متغیرهای غیر پایه را ارائه می دهد.
8-1-5 الگو را در مسئله 3-6-6 در نظر بگیرید.

a 10 مجموعه از معادلات تعریف کننده برای این مسئله را شناسایی کنید. برای هر یک راه حل نقطه – گوشه متناسب را بدست آورید. و آن را بعنوان یک راه حل CPF یا یک راه حل نقطه- گوشه طبقه بندی کنید.

b برای هر راه حل نقطه – گوشه راه حل پایه متناسب و مجموعه متغیرهای غیر پایه را ارائه دهید.
9-1-5 الگو را در مسئله 4-3 در نظر بگیرید. 15 مجموعه از معادلات را برای این مجموعه شناسایی کنید. برای هر یک راه حل نقطه- گوشه متناسب را بدست آورده و آن را بعنوان یک راه حل CPF و یک راه حل نقطه – گوشه طبقه بندی کنید .

b برای هر راه حل نقطه گوشه راه حل پایه متناسب و مجموعه متغیرهای اصلی ارائه دهید.
10-1-5 هر یک عبارت زیر تحت جریانات خاص صحیح می باشد. در هر مورد نشان دهید که چه موقع این عبارات صحیح نبوده و چرا.
a بهترین راح حل CPF یک راه حل بهینه است.
b یک راه حل بهینه یک راه حل CPT است.

c یک راه حل CPT در صورتی راه حل بهینه است که هیچکدام از راه حل های CPT مجاوز بهتر نباشد. (که بر اساس مقدار تابع مورد هدف اندازه گیری می شود).
11-1-5 شکل اصلی یک مسئله برنامه نویسی خطی با n متغیر (هر یک دارای محدوده غیر منفی) و m محدوده عملکردی در نظر بگیرید.
هر یک از عبارات زیر را به شکل درست یا غلط نشان داده و سپس پاسخ خود را با توجه به مرجع برای موضع مورد نظر توجیح کنید.
a اگر راه حل بهینه باشد باید یک راه حل CPF بدست آورید.

b تعداد راه حل های حداقل
c اگر یک راه حل CPS دارای راه حل های مجاور CPF باشد که بهتر باشند (که با z اندازه گیری می شود)، یکی از این راه حل های CPF مجاور بایت یک راه حل بهینه باشد.

12-1-5 هر یک از عبارت زیر را که درباره مساول برنامه نویسی خطی است ، بصورت درشت یا غلط ، نشانه گذاری کنید و سپس پاسخ خود را توجیه نمایید.
a) گر یک راه حل ، بهینه باشد و سی و یک راه حل CPF نباشد ، راه حلهای بهینه گوناگونی وجود داشت.
b) اگر مقدار تابع مورد هدف دو دو نقطه مختلف برابر باشد ، همه نقاط در بخش خطی متصل کننده امکان پذیر بوده و z دارای مقادیر مشابه در همه آن نقاط خواهد بود.

c) اگر شعله دارای 8 متغیر باشد ، راه حل شبیه سازی هر مجموعه از مرز محدوده 8 ، یک راه حل CPF خواهد بود.
13-1-5 شکل محاسبه شده مسائل برنامه نویسی خطی را که دارای راه حل های امکان پذیر و یک نقطه منطقه نحدود می باشند، در نظر بگیرید. هر یک از عبارات زیر را به صورت درست یا غلط علامت گذاری کرده و پاسخ خود را با مراجعه به عبارات ویژه ، توجیه کنید.
a) حداقل یک راه حل بهینه وجود دارد.
b) یک راه حل بهینه باید یک راه حل BF باشد

c) تعداد راه حل های BF محدود هستند.
14-1-5 الگوی مسئه 10-6-4 را دوباره در نظر بگیرید. اکنون شما اطلاعاتی را در اختیار داریکه در آن متغیرهای پایه در راه حل بهینه x3,x2 هستند. از این اطلاعات برای شناسایی یک سیستم از معادلات فردی سه محدوده استفاده کنید که راه حل شبیه سازی شده آنها باید یک راه حل بهینه باشد. سپس این سیستم معادلات را برای بدست آوردن این راه حل ، حل نمایید.

15-1-5 مسئله 3.7-4 را در نظر بگیرید. اکنون از اطلاعات ارائه شده و تئوری و روش برای شناسایی یک سیستم با 3 معادله مرزی محدود (x3,x2,x1,) که در آن شبیه سازس باید راه حل بهینه بدون بکارگیری روش ساده سازی باشد، استفاده کنید. این سیستم معادلات را برای یافتن راه حل بهینه حل کنید.
16-1-5 مسئله 8-30 40 را در نظر بگیرید. با اطلاعات ارائه شده و تئوری روش ساده سازی ، محدوده های مسئله را به منظور شناسایی یم سیستم دارای معادلات راه حل بهینه مرز محدوداً که شبیه سازی آن باید راه حل بهینه باشد ، تجربه و تحصیل کنید. سپس سیستم را برای بدست آوردن این راه حل ، حل کنید.

17-1-5 مسئله زیر را در نظر بگیرید.
حداکثر در قبال
فرض کنید x5,x4 متغیرهای خاص برای محدوده پایه مربوطه می باشند. این دو متغیر را بعنوان متغیرهای پایه برای راه حل BF اولیه در نظر بگیرید. بدین ترتیب اطلاعاتی را در اختیار دارید که طبق آن روش ساده سازی برای بدست آوردنراه حل بهینه در دو محاسبه جریان می یابد.
1) در محاسبه متغیر پایه ورودی x3 می باشد و متغیر باقی مانده x4 است.

2) در محاسبه متغیر پایه ورودی x2 و متغیر باقی مانده پایه x5 می باشد.
a) یک طراحی سه بعدی از منطقه مربوط به این مسئله را در نظر بگیرید و --- دنبال شده با روش ساده سازی را نشان دهید.
b) تغییر هندسی در این باره را که چرا روش سازی این مسیر را دنبال می کند ارائه دهید.

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

e) برای هر راه حل CPF بئدست آمده در بخش d ، راه حل BF متناسب و مجموعه متغیرهای غیر پایه آن را ارائه دهید.
شرح دهید که چگونه این متغیرهای غیر پایه معادلات تعریف کننده بدست آمده در بخش (d) را شناسایی می کند.
18-1-5 مسئله زیر را در نظر بگیرید:

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

2- در روش دوم ، متغیر پایه ورودی x1 و متغیر پایه کانده x4 است.
ساختار مسئه 117-5 را برای این راه حل دنبال کنید.
19-1-5 با در نظر گرفتن شکل 2-5 ، شرح دهید که چرا ویژگی 1b برای راه حل های CPF برای عین مسئله در صورتی برقرار می شود که تابع مورد حذف زیر در آن جود داشته باشد.

a) حداکثر 3=a
b) حداکثر Z=-x1+2x3
20-1-5 مسئله برنامه نویس خطی سه تفسیری نشان داده شده در شکل 2-5 را در نظر بگیرید.
a) بر حسب تعاریف هندسی شرح دهید که چرا مجموعه راه حل های توجیه کننده هر --- مجزا ، یک مجموعه همگرا می باشد که در ضمیمه 2 شرح داده شده است.

b) از نتیجه گیری های بخش a برای شرح این موضوع که چرا منطقه کامل (مجموعه راه حل هایی که بطور همزمان هر محدوده ای را توجیه می کند) یک مجموعه همگرا هستند.
21-1-5 فرض کنید که مسئله برنامه نویسی خطی سه در شکل 2-5 دارای تابع مورد هدف زیر می باشد.
حداکثر بدون بکارگیری محاسبات جبری روش ساده سازی ، فقط منطق هندسی را بررسی تعیین و شرح سیری که می توان در شکل
2-5 برای منطقه ای در راه حل بهینه دنبال کرد به کار ببرید.

22-1-5 مسئله برنامه نویسی خطی سه متغیری نشان وارد شده در شکل 2-5 را در نظر بگیرید.
a) جدولی مثل جدول 4-5 بسازید و در آن هر متغیر نمایشگر را برای هر معادله ضرری محدوده منطقه ای نمایش دهید.
b) برای راه حل CPF (2.4.3) و سه راه حل CPF مجاور آن (4.2.4) ، (0.4.2) و (2.3.0) جدولی مثل جدول 5-5 بسازید که نمایشگر معادلات تعریف کننده متناسب ، راه حل BF و متغیرهای غیره پیه باشه.