Online User روش سیمپلکس تجدید نظر شده یا Revised Simplex Method (مقدمه) - مدیریت صنعتی Industrial Management

مدیریت صنعتی Industrial Management

مدیریت صنعتی - تحقیق در عملیات - مدیریت تولید - ...

روش سیمپلکس تجدید نظر شده یا Revised Simplex Method (مقدمه)
نویسنده : محسن رحیمی - ساعت ٧:٢۳ ‎ق.ظ روز ۱۳٩٤/۱٢/٢٥
 

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

برای مطالعه متن کامل مقاله روی "ادامه مطلب" کلیک کنید.

(500 کلمه)

مطلب مرتبط بعدی: منتشر نشده است.

مطلب مرتبط قبلی: ویژگی بهینگی یک جواب گوشه ای موجه


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

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

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

$$ \max {Z=\mathbf{c.x}}$$

$$\mathbb{subject\,to:}$$

$$\mathbf{A.x}\le\mathbf{b}\quad\text{and}\quad\mathbf{x}\ge\mathbf{0}$$

که در آن $\mathbf{c}$ یک بردار سطری با تعریف زیر است:

$$\mathbf{c}=\begin{bmatrix}c_1&c_2&\cdots&c_n\\\end{bmatrix}$$

$\mathbf{x,b}$ و $\mathbf{0}$ نیز بردارهای ستونی به شکل زیر هستند:

 $$\mathbf{x}=\begin{bmatrix}x_1\\x_2\\\vdots\\x_n\\\end{bmatrix}\quad\mathbf{b}=\begin{bmatrix}b_1\\b_2\\\vdots\\b_n\\\end{bmatrix}\quad\mathbf{0}=\begin{bmatrix}0\\0\\\vdots\\0\\\end{bmatrix}$$

$\mathbf{A}$ نیز ماتریسی است به صورت زیر:

$$\mathbf{A}=\begin{bmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\\vdots&\vdots&\ddots&\vdots\\a_{m1}&a_{m2}&\cdots&a_{mn}\\\end{bmatrix}$$

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

$$\mathbf{x_s}=\begin{bmatrix}x_{n+1}\\x_{n+2}\\\vdots\\x_{n+m}\\\end{bmatrix}$$

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

$$\begin{bmatrix}\mathbf{A}&\mathbf{I}\\\end{bmatrix}\begin{bmatrix}\mathbf{x}\\\mathbf{x_s}\\\end{bmatrix}=\mathbf{b}\quad{and}\quad\begin{bmatrix}\mathbf{x}\\\mathbf{x_s}\\\end{bmatrix}\ge\mathbf{0}$$

که در آن $\mathbf{I}$ یک ماتریس یکه ${m}\times{m}$ است و بردار صفر $\mathbf{0}$ نیز دارای ${n+m}$ عنصر می باشد.

در مطلب مرتبط بعدی به روش حل در سیمپلکس تجدید نظرشده خواهیم پرداخت.

 

مطلب مرتبط بعدی: منتشر نشده است.

مطلب مرتبط قبلی: ویژگی بهینگی یک جواب گوشه ای موجه