دانلود با لینک مستقیم و پر سرعت .
لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 146
بخش اول
1-1 برنامه ریزی خطی
1-1-1مقدمه
هر مسئله برنامه ریزی خطی یک برنامة ریاضی است که در آن تابع هدف ،تابعی خطی برحسب متغیرهای مجهول است و قیود آن مرکب از معادلات و نامعادلات خطی است . صورت دقیق قیود ممکن است از مسئله ای به مسئله دیگر تفاوت کند ،ولی همانطور که در زیر نشان داده می شود هر مسئله برنامه ریزی خطی را می توان به صورت استاندارد درآورد:
مینیمم سازی
با قیود
(1-1-1)
و
که در آن ها و ها ،اعداد حقیقی ثابتی هستند و هامتغیرهایی حقیقی اند که باید تعیین شوند. در صورت لزوم ،هر معادله را در 1- ضرب کرده, تا برای هر i شود .
صورت استاندارد فوق را می توان به شکل فشردة برداری زیر نوشت:
مینیمم سازی
(2-1-1) با قیود
در اینجا x برداری ستونی و n بعدی،برداری سطری و n بعدی و A ماتریسیوb برداری m بعدی و ستونی است . نامعادلة برداری به مفهوم آن است که تمامی مؤلفه های x نا منفی است .
مثال(1-1-1 )(متغیرهای کمبود). مسئله زیر را ملاحظه کنید .
مینیمم سازی
با قیود
و
در این مورد کلیة قیود به صورت نامعادلات خطی است پس مسئله را می توان به صورت زیر درآورد.
مینیمم سازی
با قیود
و
و
متغیرهای جدید نامنفی که نامعادلات را به معادلات تبدیل می کنند ،موسوم به متغیرهای کمبودند. حال مسئله دارایm+n مجهول و است و به صورت استاندارد در آمده است. ماتریس ضرایب مجهولات قیود و به صورت است (یعنی می توان این ماتریس را به دو ماتریس Aو I افراز کرد که n ستون اول، ماتریس اصلی A وm ستون بعدی ،ماتریس یکه باشد).
مثال (2-1-1)(متغیرهای مازاد) . اگر جهت نامعادلات مثال 1-1-1 عوض شوند ،به طوری که یک نامعادله نوعاً به صورتباشد ،بدیهی است که این هم ارز است با
که در آن .متغیرهایی مانند که به این نحو اضافه می شوند تا نا معادله به معادله بدل گردد، موسوم به متغیرهای مازاد هستند.
اگر مجهولات محدودیت غیر منفی داشته باشند ،در این صورت روشن است که هر مجموعه از نامعادلات خطی را می توان با ضرب کردن در 1- و افزودن متغیرهای کمبود و مازاد به صورت استاندارد تبدیل کرد.
2-1-1جوابهای پایه ای (اساسی)
دستگاه معادلات زیر را در نظر می گیریم:
(3-1-1) Ax=b
که در آن x برداری n بعدی و b بردار n بعدی وA ماتریساست .فرض می کنیم از n ستونA ،m ستون انتخاب کنیم که مستقل خطی باشد(در صورتی چنین mستونی وجود دارند که مرتبه ماتریس A، m باشد). برای سادگی نماد گذاری فرض می کنیم m ستون اول Aانتخاب شده باشند. در این صورت، mستون انتخابی، یک ماتریس را تشکیل می دهد که آن را با B نشان می دهیم. ماتریس B نامنفرد است. بنابراین از دستگاه معادلات زیر می توانرا محاسبه کرد و جواب منحصر به فردی بدست آورد:
(4-1-1)
با قرار دادن (یعنی با مساوی قرار دادن m مؤلفه اول x با مؤلفه های و صفر قرار دادن بقیه مؤلفه ها)، جواب Ax=b را بدست میآوریم. این جواب ما را به تعریف زیر هدایت می کند.
تعریف(1-1-1):
دستگاهی متشکل از m معادله n مجهولی به صورت(3-1-1) مفروض است. فرض می کنیم Bزیر ماتریس و نامنفردی باشد که از ستونهایA تشکیل شده است. حال اگر همة n-m مؤلفه x که متناظر با ستونهای B نیستند برابر صفر باشند، جواب دستگاه معادلات باقی مانده، موسوم به جواب پایه ای یا اساسی دستگاه (3-1-1) نسبت به پایه B است. مؤلفه هایی از x را که متناظر با ستونهای B اند، متغیرهای پایه ای یا اساسی می نامند.
در تعریف فوق B را به عنوان پایه در نظر می گیریم زیرا Bمشتمل بر m ستون مستقل خطی است که می توان آن را پایه ای از فضای در نظر گرفت. جواب پایه ای متناظر است با عبارتی برای بردار b به صورت ترکیبی خطی از این بردارهای خطی.
در حالت کلی، البته ممکن است دستگاه (3-1-1) فاقد جوابهای پایه ای باشند. ولی برای اجتناب از حالات پیش پا افتاده و مشکلات غیر ضروری می توان مفروضاتی برای ساختار ماتریس A در نظر گرفت.
اولاً اغلب فرض می کنیم n>m یعنی تعداد متغیرهای بیشتر از تعداد قیود تساوی است.
ثانیاً اغلب فرض می کنیم سطرهای ماتریس A مستقل خطی هستند، به عبارت دیگر m معادله مربوط به قیود مستقل خطی اند. وابستگی خطی بین سطرهای ماتریس A متناظر است با یکی از این دو حالت:
ناسازگاری معادلات قیود و در نتیجه جواب نداشتن(4-1-1) یا وجود برخی معادلات اضافی در آن که باید حذف شوند. در تشریح این مبحث، فرض زیر را به طور صریح اتخاذ می کنیم مگر آنکه خلاف آن را قید کنیم.
3-1-1 فرض رتبه کامل
ماتریسA، و m
بر اساس فرض فوق دستگاه (3-1-1) همواره دارای جواب است و در حقیقت، حداقل دارای یک جواب پایه ای است.
ضرورت ندارد که متغیرهای پایه ای در یک جواب پایه ای همگی غیر صفر باشند. این مطالب با تعریف زیر تأکید می شود.
تعریف(2-1-1):
اگر یک یا چند متغیر پایه ای در یک جواب پایه ای دارای مقدار صفر باشد، در این صورت آن را جواب پایه ای تباهیده می نامند.
