روش سیمپلکس (Simplex) | به زبان ساده

الگوریتم سیمپلکس (Simplex Algorithm) روشی برای به دست آوردن جواب بهینه یک تابع هدف خطی با دستگاهی از قیود است. این الگوریتم با یک رأس پایه از ناحیه شدنی (Feasible Region) شروع می‌شود و برای رئوس مجاور ادامه پیدا می‌کند. روش سیمپلکس تا رسیدن به جواب بهینه ادامه می‌یابد. ناحیه‌ای که به قیود سیستم محدود می‌شود، ناحیه شدنی (Feasible Region) نامیده می‌شود. این ناحیه، مقادیر ممکن متغیرهایی را نشان می‌دهد که در همه قیود صدق می‌کنند. برای آنکه برنامه‌ریزی خطی قابل اعمال باشد، ناحیه شدنی باید یک چندبر یا چندسقفی محدب (Convex Polytope) باشد (در حالت دوبعدی، یک چندضلعی محدب و در حالت سه‌بعدی، یک چندوجهی محدب و…). برای آشنایی بیشتر با ناحیه شدنی، به آموزش «برنامه‌ریزی خطی در متلب» مراجعه کنید.

روش سیمپلکس مراحل و قواعد زیادی دارد. قبل از بیان الگوریتم کلی روش سیمپلکس، با یک مثال این مراحل و قواعد را بررسی می‌کنیم.

مثال ساده روش سیمپلکس

دستگاه قیود زیر را در نظر بگیرید:

$$ \large \begin {cases} \begin {aligned} 2 x + 3 y & \le 9 0 \\ 3 x + 2 y & \le 1 2 0 \\ x & \ge 0 \\ y & \ge 0, \end{aligned} \end{cases} $$

فیلم آموزش الگوریتم سیمپلکس Simplex در فرادرس

کلیک کنید

می‌خواهیم تابع هدف زیر را با توجه به این قیود بیشینه کنیم:

$$ \large f (x , y ) = 7 x + 5 y  $$

حل: روش سیمپلکس با تبدیل قیود و توابع هدف به یک دستگاه معادلات آغاز می‌شود. این کار را می‌توان با معرفی متغیرهای جدیدی به نام «متغیر لَنگی» یا «متغیر کمکی» یا «متغیر کمبود» (Slack Variables)‌ انجام داد. متغیرهای کمکی اختلاف یا اسلک مثبت بین سمت چپ یک نامعادله و سمت راست آن را نشان می‌دهند.

بنابراین، نامعادله

$$ \large 2 x + 3 y \le 90 $$

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

$$ \large 2 x + 3 y + s _ 1 = 90 . $$

به طور مشابه، نامعادله

$$ \large 3 x + 2 y \le 120 $$

با تساوی زیر معادل است:

$$ \large 3 x + 2 y + s_ 2 = 120. $$

علاوه بر متغیرهای کمکی، متغیر $$ z $$‌ را نیز تعریف می‌کنیم که مقدار تابع هدف را نشان می‌دهد. در نتیجه، می‌توان نوشت:

$$ \large z - 7 x - 5 y = 0 . $$

 معادلات بالا منجر به دستگاه معادلات زیر خواهد شد:

$$ \large
\begin {cases} \begin {array}{cccccccccccc} z & - & 7x & - & 5y & & & & & = & 0 && (0) \\ & & 2x & + & 3y & + & s_1 & & & = & 90 && (1) \\ & & 3x & + & 2y & & & + & s_2 & = & 120. && (2) \end{array} \end{cases} $$

دستگاه معادلات بالا را به فرم ماتریس افزوده می‌نویسیم:

$$ \large \left [ \begin {array} {ccccc|c} 1 & -7 & -5 & 0 & 0 & 0 \\ 0 & 2 & 3 & 1 & 0 & 90 \\ 0 & 3 & 2 & 0 & 1 & 120 \end{array}\right]. \qquad \begin {array}{c} (0) \\ (1) \\ (2) \end{array} $$

این ماتریس نشان می‌دهد که همه متغیرهای این دستگاه (شامل $$s_1$$، $$s _ 2$$ و $$z$$) بزرگ‌تر از یا مساوی با صفر هستند. ضرایب متغیرهای $$ s _1 $$ و $$s _ 2$$ در سطر $$(0)$$، صفر است. این متغیرها متغیرهای اساسی (Basic Variables) نامیده می‌شوند. متغیرهای $$ x $$ و $$y $$ ضرایب غیرصفری در سطر $$(0)$$ دارند و متغیرهای غیراساسی (Non-basic Variables) نامیده می‌شوند. در هر لحظه از الگوریتم، جواب اساسی با صفر قرار دادن متغیرهای غیراساسی به دست می‌آید. بنابراین، اکنون جواب اساسی به صورت زیر است:

$$ \large x = 0 , \quad y = 0 , \quad s _ 1 = 9 0 , \quad s _ 2 = 1 2 0 , \quad z = 0 . $$

به تأثیر افزایش مقادیر متغیرهای غیراساسی روی متغیر $$z $$ توجه کنید. افزایش هر یک از متغیرهای $$ x $$ و $$y$$ سبب افزایش $$z $$ خواهد شد، زیرا ضرایب $$ x $$ و $$ y$$ در سطر $$(0)$$ منفی است. در نتیجه، این جواب بهینه نیست.

تکرار روش سیمپلکس شامل تبادل متغیرهای اساسی و متغیرهای غیراساسی با استفاده از عملیاتی سطری مقدماتی ماتریسی است. در هر مرحله از فرایند، یک متغیر غیراساسی در سطر $$(0)$$ حذف می‌شود و یک متغیر اساسی دیگر جای آن را به عنوان متغیر غیراساسی می‌گیرد. این سطر، «لولا» (Pivot) نامیده می‌شود.

فرض کنید $$ x $$ از سطر $$ ( 0 ) $$ حذف شده باشد. این کار را ‌می‌توان توسط سطر $$(1)$$ یا $$(2)$$ انجام داد.

حالت ۱: حذف $$x $$ در سطر $$(0)$$ توسط سطر $$(1)$$:

$$ \large \left [ \begin {array}{ccccc|c} 1 & 0 & \frac{11}{2} & \frac{7}{2} & 0 & 315 \\ 0 & 2 & 3 & 1 & 0 & 90 \\ 0 & 3 & 2 & 0 & 1 & 120 \end{array} \right ] . \qquad \begin {array} { c } ( 0 ) \vphantom { \frac { 1 } { 2 } } \\ (1) \\ (2) \end {array} $$

در این لولا، متغیر $$ x$$ به عنوان یک متغیر اساسی وارد می‌شود و متغیر $$ s _ 1 $$ خارج می‌شود تا یک متغیر غیراساسی شود. اکنون $$ x $$ را از سطر $$(2)$$ حذف می‌کنیم:

$$ \large \left [ \begin {array} {ccccc|c} 1 & 0 & \frac{11}{2} & \frac { 7 } { 2 } & 0 & 315 \\ 0 & 2 & 3 & 1 & 0 & 90 \\ 0 & 0 & - \frac { 5 } { 2} & - \frac { 3 } { 2 } & 1 & -15 \end {array}\right]. \qquad \begin{array}{c} (0)\vphantom{\frac{1}{2}} \\ (1) \\ (2)\vphantom{\frac{1}{2}} \end{array} $$

که منجر به جواب اساسی زیر خواهد شد:

$$ \large x=45, \quad y=0, \quad s_1=0, \quad s_2=-15, \quad z=315. $$

این جواب نشدنی است، زیرا منجر به منفی شدن یکی از متغیرها شده است.

حالت ۲: حذف $$x $$ در سطر $$(0)$$ توسط سطر $$(2)$$

$$ \large \left [ \begin {array} {ccccc|c} 1 & 0 & - \frac { 1 } { 3 } & 0 & \frac { 7 } { 3 } & 2 8 0 \\ 0 & 2 & 3 & 1 & 0 & 90 \\ 0 & 3 & 2 & 0 & 1 & 120 \end{array}\right ] . \qquad \begin {array} { c } ( 0 ) \vphantom { \frac { 1 } { 2 } } \\ (1) \\ (2) \end {array} $$

در این لولا، متغیر $$ x $$ به عنوان یک متغیر اساسی وارد شده و متغیر $$ s _ 2 $$ به یک متغیر غیراساسی تبدیل شده و خارج می‌شود. اکنون $$ x $$ را از سطر $$(1)$$ حذف می‌کنیم:

$$ \large \left [ \begin {array} { ccccc|c} 1 & 0 & - \frac { 1 } {3 } & 0 & \frac { 7 } { 3 } & 2 8 0 \\ 0 & 0 & \frac { 5 } { 3 } & 1 & - \frac { 2 } { 3 } & 1 0 \\ 0 & 3 & 2 & 0 & 1 & 120 \end {array} \right ] . \qquad \begin {array} { c } ( 0 ) \vphantom { \frac { 1 } { 2 } } \\ ( 1 ) \vphantom { \frac { 1 } { 2 } } \\ (2) \end {array} $$

در نتیجه، جواب اساسی زیر را خواهیم داشت:

$$ \large x = 4 0 , \quad y = 0 , \quad s _ 1 = 1 0 , \quad s _ 2 = 0 , \quad z = 2 8 0 . $$

این جواب قابل قبول است، اما بهینه نیست؛ زیرا یک ضریب منفی در سطر $$(0)$$ وجود دارد. این بدین معنی است که با افزایش $$y$$ می‌توان $$z $$ را زیاد کرد. یک لولای دیگر برای یافتن جواب بهینه لازم است.

خوشبختانه می‌توان با مشاهده نسبت درایه ستون سمت راست ماتریس افزوده به ضریب متغیر ورودی، مشاهده کرد که کدام لولا منجر به یک جواب شدنی خواهد شد. متغیر $$y $$ را به عنوان متغیر ورودی در نظر گرفته و نسبت‌ها را محاسبه می‌کنیم:

$$ \large \left[\begin{array}{ccccc|c} 1 & 0 & -\frac{1}{3} & 0 & \frac{7}{3} & 280 \\ 0 & 0 & \color{#D61F06} { \frac{5} {3} }& 1 & -\frac{2}{3} & {\color{#D61F06}{10}} \\ 0 & 3 & {\color{#3D99F6}2} & 0 & 1 & {\color{#3D99F6}{120}} \end{array}\right]. \qquad \begin{array}{c} (0)\vphantom{\frac{1}{2}} \\ (1)\vphantom{\frac{1}{2}} \\ (2) \end{array} $$

برای متغیر وارد شده $$ y$$، نسبت برای سطر $$(1)$$ برابر با $$ 10 ÷\frac{5}{3} = 6 $$ و برای سطر $$(2)$$ برابر با $$ \frac {120}{2} = 60 $$ است. انتخاب سطری که نسبت را کمینه می‌کند، تضمین خواهد کرد که لولا منجر به یک جواب شدنی شود. بنابراین، سطر $$(1)$$ را باید به عنوان سطر لولا انتخاب کرد.

با حذف $$y$$ در سطر $$ (0)$$ با استفاده از سطر $$(1)$$، داریم:

$$ \large \left [ \begin {array} {ccccc|c} 1 & 0 & 0 & \frac { 1 } { 5 } & \frac { 1 1 } { 5 } & 2 8 2 \\ 0 & 0 & \frac { 5 } { 3 } & 1 & - \frac { 2 } { 3 } & 10 \\ 0 & 3 & 2 & 0 & 1 & 120 \end {array} \right]. \qquad \begin {array} { c } (0) \vphantom { \frac { 1 } { 2 } } \\ ( 1 ) \vphantom { \frac { 1 } {2 } } \\ (2) \end{array} $$

حذف $$y$$ در سطر $$(2)$$ نیز به صورت زیر است:

$$ \large \left [ \begin {array} {ccccc|c} 1 & 0 & 0 & \frac {1 } { 5 } & \frac { 1 1 } { 5 } & 2 8 2 \\ 0 & 0 & \frac { 5 } { 3 } & 1 & - \frac { 2 } { 3 } & 10 \\ 0 & 3 & 0 & -\frac { 6 } { 5} & \frac { 9 } { 5 } & 1 0 8 \end {array} \right ] . \qquad \begin {array}{c} ( 0 ) \vphantom { \frac { 1 } { 2 } } \\ ( 1 ) \vphantom { \frac { 1 } { 2 } } \\ ( 2 ) \vphantom { \frac { 1 } { 2 } } \end {array} $$

در نتیجه، جواب اساسی زیر را خواهیم داشت:

$$ \large x = 3 6 , \quad y = 6 , \quad s _ 1 = 0 , \quad s _ 2 = 0 , \quad z = 2 8 2 . $$

این جواب باید بهینه باشد، زیرا هر افزایش در متغیرهای غیراساسی $$ s _ 1 $$ و $$ s _2 $$ سبب کاهش در $$ z $$ خواهد شد. بنابراین، مقدار بیشینه تابع هدف برابر است با:

$$ \large f (36,6) = 282 . $$

روش سیمپلکس برای بیشینه‌سازی

این نسخه از روش سیمپلکس برای یک مسئله بیشینه‌سازی با همه قیود (جز برای قیود نامنفی) مقادیر بیشینه را به دست خواهد داد. فرم ماتریسی الزامات به صورت زیر است:

$$ \large
\begin {array} {ll} \text {Maximize:} & \textbf {c} ^ \text {T} \cdot \textbf {x} \\ \text {Subject to:} & \textbf {A} \textbf {x} \le \textbf {b} , \ \ x _ i \ge 0, \end {array} $$

که در آن، $$ \textbf {c} $$ برداری شامل ضرایب تابع هدف، $$\textbf{x}$$ یک بردار شامل متغیرهای مسئله، $$ \textbf{A}$$ یک ماتریس شامل ضرایب قیود و $$ \textbf{b}$$ یک بردار شامل مقادیر بیشینه این قیود است. برای استفاده از روش سیمپلکس برای بهینه‌سازی، گام‌های زیر را انجام دهید.

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

روش سیمپلکس برای کمینه‌سازی

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

$$ \large \begin {array} {ll} \text {Minimize:} & \textbf {c} ^ \text {T} \cdot \textbf {x} \\ \text {Subject to:} & \textbf {A} \textbf {x} \ge \textbf {b} \, \quad x _ i \ge 0 \end {array} $$

که در آن، $$ \textbf{c}$$ برداری شامل ضرایب تابع هدف، $$ \textbf{x}$$ برداری شامل متغیرهای مسئله، $$ \textbf{A}$$ یک ماتریس شامل ضرایب قیود و $$ \textbf{b}$$ یک بردار شامل مقادیر کمینه این قیود است. برای پیاده‌سازی این الگوریتم، به صورت زیر عمل می‌کنیم.

• ضرایب قیود و تابع هدف را در ماتریس افزوده قرار دهید. ضرایب تابع هدف باید به سطر زیرین بروند.
• ماتریس را ترانهاده کنید.
• این ماتریس جدید، دوگان مسئله بیشینه‌سازی است. دستگاه جدید قیود و تابع هدف را بنویسید. این مسئله متغیرهای متفاوتی نسبت به مسئله اصلی دارد.
• از روش سیمپلکس برای بیشینه‌سازی استفاده کنید تا مقدار بیشینه را به دست آورید. مقدار بیشینه همان مقدار کمینه مسئله اصلی است. ضرایب متغیرهای کمکی سطر $$(0)$$ متناظر با مقادیر متغیرهای مسئله اصلی هستند.

مثال دوگان روش سیمپلکس

دستگاه قیود زیر را در نظر بگیرید:

$$ \large \begin {cases} \begin {aligned} 4 x + 3 y + 5 z & \ge 6 5 \\ x + 3 y + 2 z & \ge 3 8 \\ 2 x + 3 y +4 z &\ge 5 2 \\ x , y , z & \ge 0 , \end {aligned} \end{cases} $$

فیلم آموزش الگوریتم سیمپلکس Simplex در فرادرس

کلیک کنید

تابعی که می‌خواهیم آن را کمینه کنیم به صورت زیر است:

$$ \large f ( x , y , z ) = 1 2 x + 3 y + 1 0 z . $$

این مسئله را می‌توان به فرم دیگر بیشینه‌سازی بالا نشان داد، اما مسئله‌ای در یافتن جواب اساسی اول اتفاق می‌افتد: برابر قرار دادن متغیرهای $$ x $$، $$ y $$ و $$ z $$ با $$0$$ منجر به یک جواب نشدنی با متغیرهای کمکی می‌شود که مقدار آن‌ها منفی است. روش سیمپلکس باید با جواب شدنی آغاز شود، بنابراین، مفید نخواهد بود. روش M بزرگ راه‌حلی برای این مشکل ارائه می‌دهد، اما روش بسیار ساده‌تری برای این مسئله وجود دارد.

یک دوگان برای این مسئله، را می‌توان با ترانهادن ضرایب نوشت. برای این کار باید ضرایب قیود را در یک ماتریس افزوده قرار داد. همچنین باید ضرایب تابع هدف را در سطر زیرین، با یک $$0$$ در قسمت راست قرار داد:

$$ \large \left [ \begin {array} {ccc|c} \color{#20A900}4 & \color{#D61F06}3 & \color{#3D99F6}5 & \color{#EC7300}{65} \\ \color{#20A900}1 & \color{#D61F06}3 & \color{#3D99F6}2 & \color{#EC7300}{38} \\ \color{#20A900}2 & \color{#D61F06}3 & \color{#3D99F6}4 & \color{#EC7300}{52} \\ \hline \color{#20A900}{12} & \color{#D61F06}3 & \color{#3D99F6}{10} & \color{#EC7300}0 \end{array}\right]. $$

حاصل ترانهادن درایه‌های ماتریس به شکل زیر است:

$$ \large
\left [ \begin {array} {ccc|c} \color {#20A900}4 & \color {#20A900}1 & \color{#20A900}2 & \color{#20A900}{12} \\ \color {#D61F06}3 & \color{#D61F06}3 & \color{#D61F06}3 & \color {#D61F06}3 \\ \color{#3D99F6}5 & \color{#3D99F6}2 & \color {#3D99F6}4 & \color{#3D99F6}{10} \\ \hline \color{#EC7300}{65} & \color {#EC7300}{38} & \color{#EC7300}{52} & \color{#EC7300}0 \end {array} \right ] . $$

توجه کنید که ممکن است به تقسیم سطر دوم بر ۳ وسوسه شوید، اما باید دقت کرد که این کار موجب بر هم خوردن تقارنی خواهد شد که برای بازگشتن به مسئله اصلی لازم است.

اکنون دستگاهی از قیود و تابع هدف داریم که باید بیشینه شود. قیود به صورت زیر هستند:

$$ \large \begin {cases} \begin {aligned} 4 u + v + 2 w & \le 12 \\ 3 u + 3 v + 3 w & \le 3 \\ 2 u + 3 v + 4 w & \le 52 \\ u , v , w & \ge 0 , \end {aligned} \end{cases} $$

و باید تابع هدف زیر را بیشینه کنند:

$$ \large g ( u , v , w ) = 6 5 u + 3 8 v + 5 2 w . $$

اکنون می‌توانیم از روش سیمپلکس برای پیدا کردن جواب بهینه استفاده کنیم:

$$ \large \left [ \begin {array} {ccccccc|c} 1 & - 6 5 & - 3 8 & - 5 2 & 0 & 0 & 0 & 0 \\ 0 & 4 & 1 & 2 & 1 & 0 & 0 & 12 \\ 0 & 3 & 3 & 3 & 0 & 1 & 0 & 3 \\ 0 & 2 & 3 & 4 & 0 & 0 & 1 & 52 \end {array} \right ] . \qquad \begin {array} { c } ( 0 ) \\ ( 1 ) \\ ( 2 ) \\ ( 3 ) \end {array} $$

$$u$$ را در سطر $$(2)$$ وارد می‌کنیم:

$$ \large \left [ \begin {array}{ccccccc|c} 1 & 0 & 27 & 13 & 0 & \frac{65}{3} & 0 & 65 \\ 0 & 0 & -3 & -2 & 1 & -4 & 0 & 8 \\ 0 & 1 & 1 & 1 & 0 & \frac { 1 } { 3 } & 0 & 1 \\ 0 & 0 & 1 & 2 & 0 & -2 & 1 & 50 \end {array} \right ] . \qquad \begin {array} {c} ( 0 ) \vphantom { \frac { 1 } { 2 } } \\ ( 1 ) \\ ( 2 ) \vphantom { \frac { 1 } { 2 } } \\ (3) \end {array} $$

تمام ضرایب در سطر $$(0)$$ مثبت هستند، بنابراین این جواب بهینه است. مقدار بیشینه در قسمت بالای سمت راست (یعنی $$ 65 $$)، برابر با مقدار کمینه برای مسئله اصلی است. البته متغیرهای $$ u $$، $$v$$ و $$ w $$ برابر با متغیرهای مسئله اصلی نیستند. خوشبختانه، مقادیر متغیرهایی که مسئله اصلی را کمینه می‌کنند، متناظر با ضرایب متغیرهای کمکی در سطر $$(0)$$ هستند.

$$\large  \left [ \begin {array} {ccccccc|c} 1 & 0 & 27 & 13 & \color {#D61F06} 0 & \color{#D61F06} { \frac { 6 5 } { 3 } } & \color {#D61F06} 0 & 65 \\ 0 & 0 & - 3 & -2 & 1 & -4 & 0 & 8 \\ 0 & 1 & 1 & 1 & 0 & \frac { 1 } { 3 } & 0 & 1 \\ 0 & 0 & 1 & 2 & 0 & - 2 & 1 & 50 \end {array}\right ] . \qquad \begin {array} { c } ( 0 ) \vphantom { \frac { 1 } { 2 } } \\ (1) \\ (2) \vphantom{ \frac { 1 } { 2 } } \\ ( 3 ) \end {array} $$

بنابراین، مقادیر مسئله اصلی که تابع هدف را کمینه می‌کنند، به صورت زیر است:

$$ \large x = 0 , \quad y = \frac { 6 5 } { 3 } , \quad z = 0 . \ _ \square $$

حالت‌های خاص روش سیمپلکس

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

فیلم آموزش تحقیق در عملیات ۱ – مرور و تست کنکور ارشد و دکتری در فرادرس

کلیک کنید

مثالی از عدم کارایی روش سیمپلکس

دستگاه قیود زیر را در نظر بگیرید:

$$ \large \begin {cases} \begin {aligned} 2 x + 3 y & \ge 1 0 \\ 3 x + y &\ge 8 \\ x & \ge 0 \\ y & \ge 0 , \end {aligned} \end {cases} $$

می‌خواهیم تابع هدف زیر را کمینه کنیم:

$$ \large f ( x , y ) = 5 x + 10 y . $$

نشان دهید این کار را نمی‌توان با روش سیمپلکس معمولی انجام داد.

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

$$ \large \left [ \begin {array} {ccccc|c} -1 & 5 & 10 & 0 & 0 & 0 \\ 0 & 2 & 3 & -1 & 0 & 10 \\ 0 & 3 & 1 & 0 & -1 & 8 \\ \end {array} \right ] . \qquad \begin {array} {c} (0) \\ (1) \\ (2) \end {array} $$

این ماتریس اولیه جواب نشدنی $$ s _ 1 = - 1 0$$ و $$ s_ 2 = - 8 $$ را نشان می‌دهد. اگر جواب اساسی اولیه نشدنی باشد، روش سیمپلکس نتیجه بامعنی نخواهد داشت.

گاهی اوقات می‌توان مسئله را با دوگان آن حل کرد، اما نه برای وقتی که مسئله شامل ترکیبی از قیود کمینه و بیشینه باشد.

مثالی از عدم کارایی دوگان روش سیمپلکس

دستگاه قیود زیر را در نظر بگیرید.

$$ \large \begin {cases} \begin {aligned} - x + 5 y & \le 2 5 \\ 6 x + 5 y & \le 6 0 \\ x + y & \ge 2 \\ x & \ge 0 \\ y & \ge 0 , \end {aligned} \end {cases} $$

می‌خواهیم تابع زیر کمینه شود:

$$ \large f (x,y) = x - 10 y . $$

نشان دهید این کار را نمی‌توان با استفاده از روش سیمپلکس معمولی یا روش دوگان انجام داد.

پاسخ: این مسئله را به فرم یک ماتریس سیمپلکس می‌نویسیم و می‌بینیم که یک جواب اساسی اولیه نشدنی دارد:

$$ \large \left [ \begin {array} {cccccc|c} -1 & 1 & -10 & 0 & 0 & 0 & 0 \\ 0 & -1 & 5 & 1 & 0 & 0 & 25 \\ 0 & 6 & 5 & 0 & 1 & 0 & 60 \\ 0 & 1 & 1 & 0 & 0 & -1 & 2 \\ \end {array} \right ] \qquad \begin{array}{c} ( 0 ) \\ ( 1 ) \\ ( 2 ) \\ ( 3 ) \end {array} $$

$$ \large \begin {array} {ccc} s _ 1 = 25 , & s _ 2 = 60 , & s _ 3 = - 2 . \end {array} $$

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

$$ \large \left [ \begin {array} {cccccc|c} 1 & -25 & -60 & 2 & 0 & 0 & 0\\ 0 & 1 & -6 & 1 & 1 & 0 & 1 \\ 0 & - 5 & - 5 & 1 & 0 & 1 & - 10 \end {array} \right ] \qquad \begin {array} {c} ( 0 ) \\ ( 1 ) \\ ( 2 ) \end {array} $$

$$ \large \begin {array} {cc} s _ 1 = 1 , & s _ 2 = - 1 0 . \ _ \square \end {array} $$

وقتی  یک جواب اساسی اولیه نشدنی است، می‌توان از روش M بزرگ استفاده کرد. ایده پشت این روش، معرفی متغیرهای مصنوعی یا ساختگی (Artificial Variables) برای جابه‌جایی جواب به ناحیه شدنی است. برخلاف متغیرهای کمکی، باید مقدار این متغیرهای ساختگی در جواب نهایی صفر باشد.

روش M بزرگ

• این روش برای هر مسئله برنامه‌ریزی خطی که با فرم‌های قبل سازگار نیست، مطابقت دارد. همچنین، برای مسائلی که شامل محدودیت‌هایی  به صورت تساوی هستند، مناسب است.
• متغیرهای کمکی و متغیر $$z$$ را مانند روش سیمپلکس پایه تعیین کرده و یک ماتریس سیمپلکس را ایجاد کنید. برای هر متغیر کمکی که دارای مقدار منفی در جواب اساسی اولیه است، یک متغیر ساختگی مجزا را به آن محدودیت اضافه کنید. همچنین یک متغیر ساختگی مشخص را به هر قید تساوی اضافه کنید. متغیرهای ساختگی با ضریب $$1$$ در هر سطر محدودیت شروع می‌شوند. در سطر تابع هدف، هر متغیر مصنوعی با ضریب یکسان $$M$$ شروع می شود. $$M$$ یک مقدار ثابت مثبت دلخواه را نشان می‌دهد.

فیلم آموزش تحقیق در عملیات – برنامه ریزی خطی در فرادرس

کلیک کنید

• اگر مسئله کمینه‌سازی باشد، آنگاه ضرایب سطر تابع هدف قرینه می‌شوند و هرف بیشینه کردن $$ - z $$ خواهد بود.
• با لولاها و با استفاده از یک متغیر کمکی منفی به عنوان یک متغیر خروجی و یک متغیر ساختگی به عنوان متغیر ورودی، جواب را به ناحیه شدنی جابه‌جا کنید.
• وقتی جواب اساسی در ناحیه شدنی قرار گرفت، مانند روش سیمپلکس کار را ادامه دهید.
• وقتی در حال اجرای روش سیمپلکس هستید، باید مطمئن باشید که عناصر سمت راست ماتریس مثبت هستند. اگر یک عنصر در سمت راست مثبت نباشد، آن سطر را در $$-1$$ ضرب کنید تا مثبت شود. اگر یک عنصر در سمت راست ماتریس $$0$$ باشد، آنگاه مطمئن شوید ضریب متغیر اساسی در آن سطر مثبت است.
• متغیر وارد شونده را با مشاهده ضریب در سطر $$(0)$$ انتخاب کنید که از همه منفی‌تر است. سطرهای لولا را با انتخاب سطری که نسبت عنصر سمت راست ماتریس افزوده را به ضریب متغیر وارد شونده کمینه می‌کند، انتخاب کنید. این نسبت باید نامنفی بوده و ضریب متغیر وارد شونده در سطر لولا باید مثبت باشد.
• یک جواب بهینه نمی‌تواند شامل هرگونه متغیر ساختگی باشد. اگر سطر $$(0)$$ ماتریس شامل ضرایب نامنفی نباشد، و جواب شامل یک متغیر ساختگی باشد، آنگاه مسئله جواب نخواهد داشت.

مثال اول روش M بزرگ

دستگاه قیود زیر را در نظر بگیرید.

$$ \large \begin {cases} \begin {aligned} - x + 5 y & \le 2 5 \\ 6 x + 5 y & \le 6 0 \\ x + y & \ge 2 \\ x & \ge 0 \\ y & \ge 0 , \end {aligned} \end {cases} $$

می‌خواهیم تابع زیر را کمینه کنیم:

$$ \large f ( x , y ) = x - 10 y . $$

با توجه به مثال قبل، می‌دانیم که قید سوم منجر به جواب نشدنی $$ s _ 3 = - 2 $$ می‌شود. برای جبران این موضوع، متغیر ساختگی $$ a_ 1 $$ را معرفی می‌کنیم. در تابع هدف، این متغیر دارای ضریب $$M$$ خواهد بود. $$M$$ یک مقدار ثابت بزرگ دلخواه است. قیود و تابع هدف جدید به صورت زیر خواهند بود:‌

$$ \large
\begin {cases} \begin {array} {ccccccccccccccc} -z & + & x & - & 10y & & & & & & & + & Ma_1 & = & 0 \\ & - & x & + & 5y & + & s_1 & & & & & & & = & 25 \\ & & 6x & + & 5y & & & + & s_2 & & & & & = & 60 \\ & & x & + & y & & & & & - & s_3 & + & a_1 & = & 2. \end {array} \end {cases} \qquad \begin {array} {c} ( 0 ) \\ ( 1 ) \\ ( 2 ) \\ ( 3 ) \end {array} $$

و به فرم ماتریسی، داریم:

$$ \large \left [ \begin {array} {ccccccc|c} -1 & 1 & -10 & 0 & 0 & 0 & M & 0 \\ 0 & -1 & 5 & 1 & 0 & 0 & 0 & 25 \\ 0 & 6 & 5 & 0 & 1 & 0 & 0 & 60 \\ 0 & 1 & 1 & 0 & 0 & -1 & 1 & 2 \end {array} \right ] . \qquad \begin {array} {c} ( 0 ) \\ ( 1 ) \\ ( 2 ) \\ ( 3 ) \end {array} $$

هدف نخست در روش M بزرگ، جابه‌جایی مسئله به ناحیه شدنی است. جواب اساسی کنونی دارای $$ s _ 3 = - 2 $$ است. این متغیر، متغیر خروجی خواهد بود و متغیر ساختگی $$ a _ 1 $$، متغیر ورودی است:

$$ \large \left [ \begin{array} {ccccccc|c} - 1 & 1 - M & - 10 - M & 0 & 0 & M & 0 & -2M \\ 0 & -1 & 5 & 1 & 0 & 0 & 0 & 25 \\ 0 & 6 & 5 & 0 & 1 & 0 & 0 & 60 \\ 0 & 1 & 1 & 0 & 0 & -1 & 1 & 2 \\ \end {array} \right ] . \qquad \begin {array} {c} (0) \\ (1) \\ (2) \\ (3) \end{array} $$

اکنون جواب در ناحیه شدنی است و تمام متغیرهای اساسی مثبت هستند:

$$ \large s _ 1 = 2 5 , \quad s _ 2 = 6 0 , \quad a _ 1 = 2 . $$

واضح است که این جواب صحیح نیست، زیرا شامل یک متغیر ساختگی غیرصفر است. علاوه بر این، ضرایب منفی در سطر $$(0)$$ وجود دارد. اکنون می‌توان از روش M بزرگ مانند سیمپلکس استفاده کرد. هدف جدید، آوردن متغیرهای با ضرایب منفی به سطر $$(0)$$ است. از آنجا که $$y$$ منفی‌ترین ضریب در سطر $$(0)$$ است، ابتدا این متغیر وارد خواهد شد. سطری که نسبت درایه ستون سمت راست و ضریب را کمینه می‌کند، $$(3)$$ است، بنابراین، $$y$$ به این سطر وارد خواهد شد:

$$ \large \left [ \begin {array} {ccccccc|c} - 1 & 1 1 & 0 & 0 & 0 & -10 & 10 + M & 2 0 \\ 0 & -6 & 0 & 1 & 0 & 5 & -5 & 15 \\ 0 & 1 & 0 & 0 & 1 & 5 & -5 & 50 \\ 0 & 1 & 1 & 0 & 0 & -1 & 1 & 2 \\ \end {array} \right ] \qquad \begin {array} {c} ( 0 ) \\ ( 1 ) \\ ( 2 ) \\ ( 3 ) \end {array} $$

$$ \large y = 2 , \quad s _ 1 = 1 5 , \quad s _ 2 = 5 0 . $$

این جواب، دیگر شامل متغیر ساختگی نیست، اما هنوز هم بهینه نیست، زیرا ضریب سطر $$(0)$$ منفی است. $$ s _ 3 $$ باید متغیر بعدی برای ورود باشد. حداقل نسبت مثبت برای این متغیر در سطر $$(1)$$ است:

$$ \large \left [ \begin {array} {ccccccc|c} - 1 & - 1 & 0 & 2 & 0 & 0 & M & 5 0 \\ 0 & - 6 & 0 & 1 & 0 & 5 & -5 & 15 \\ 0 & 7 & 0 & - 1 & 1 & 0 & 0 & 35 \\ 0 & -1 & 5 & 1 & 0 & 0 & 0 & 25 \\ \end {array} \right ] \qquad \begin {array} {c} ( 0 ) \\ ( 1 ) \\ ( 2 ) \\ ( 3 ) \end {array} $$

$$ \large y = 5 , \quad s _ 2 = 3 5 , \quad s _ 3 = 3 . $$

اکنون $$ x $$ باید متغیر ورودی باشد و تنها سطر با نسبت مثبت $$(2)$$ است:

$$ \large \left [ \begin {array} {ccccccc|c} - 1 & 0 & 0 & \frac { 1 5 } { 7 } & \frac { 1 } { 7 } & 0 & M & 5 5 \\ 0 & 0 & 0 & \frac { 1 } { 7 } & \frac { 6 } { 7 } & 5 & - 5 & 4 5 \\ 0 & 7 & 0 & - 1 & 1 & 0 & 0 & 3 5 \\ 0 & 0 & 5 & \frac { 6 } { 7 } & \frac {1}{7} & 0 & 0 & 30 \\ \end {array} \right ] . \qquad \begin {array} {c} ( 0 ) \vphantom { \frac { 1 } { 7 } } \\ ( 1 ) \vphantom { \frac { 1 } { 7 } } \\ ( 2 ) \\ ( 3 ) \vphantom { \frac { 1 } { 7 } } \end {array} $$

واضح است که جواب بهینه برابر خواهد بود با:

$$ \large x = 5 , y = 6 , s _ 3 = 9 \implies f ( 5 , 6 ) = - 5 5.\ _\square $$

مثال دوم روش M بزرگ

شرکتی در حال برنامه‌ریزی برای تنظیم ساعت کاری هفته آینده کاگرانش است. در خط مونتاژ، بهروز ۵ واحد در ساعت مونتاژ می‌کند و هنگامی که در خط بسته‌بندی است، ۱۰ واحد در ساعت بسته‌بندی می‌کند. فردین فقط روی خط مونتاژ کار می‌کند و ۴ واحد در ساعت مونتاژ می‌کند. دستمزد بهروز ۱۲ دلار در ساعت و دستمزد فردین ۹ دلار است. شرکت تا پایان هفته باید حداقل ۲۰۰ واحد مونتاژ شده و بسته‌بندی شده را تحویل دهد و می‌تواند حداکثر ۴۰ ساعت به هر کدام اختصاص دهد. این شرکت برای به حداقل رساندن دستمزد کارگران چگونه باید برنامه‌ریزی کند؟

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

فرض کنید $$ m _ b $$ و $$ m _ f $$، به ترتیب،‌ تعداد ساعت‌هایی باشند که بهروز و فردین در خط مونتاژ‌ کار می‌کنند. همچنین، $$ p _ b $$ تعداد ساعت‌هایی است که بهروز در خط بسته‌بندی کار می‌کند. هرکدام از این دو نفر، حداکثر می‌توانند ۴۰ ساعت کار کنند. بنابراین، قیود زیر را خواهیم داشت:

$$ \large \begin {aligned} m _ b + p _ b & \le 40 \\ m _ f & \le 4 0 . \end {aligned} $$

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

$$ \large 5 m _ b + 4 m _ f = 1 0 p _ b . $$

تعداد واحدهای مونتاژ شده و باید حداقل ۲۰۰ باشد. این موضوع را می‌توان با قیود زیر نوشت:

$$ \large \begin {aligned} 1 0 p _ b & \ge 2 0 0 \\ p _ b & \ge 2 0 . \end {aligned} $$

در نتیجه، دستگاه قیود زیر را خواهیم داشت:

$$ \large \begin {cases} \begin {array} {ccccccc} m _ b & & & + & p _ b & \le & 40 \\ & & m_f & & & \le & 40 \\ & & & & p_b & \ge & 20 \\ 5m_d & + & 4m_f & - & 10p_d & = & 0 \\ m_b, & & m_f, & & p_b& \ge & 0. \end {array} \end {cases} $$

تابع هدف به صورت زیر است:

$$ \large f ( m _ b , m _ f , p _ b ) = 1 2 m _ d + 9 m _ f + 1 2 p _ d . $$

دستگاه قیود و تابع هدف را به یک ماتریس سیمپلکس تبدیل می‌کنیم:

$$ \large \left [ \begin {array} {ccccccc|c} - 1 & 1 2 & 9 & 1 2 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 40 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 40 \\ 0 & 0 & 0 & 1 & 0 & 0 & -1 & 20 \\ 0 & 5 & 4 & -10 & 0 & 0 & 0 & 0 \\ \end {array} \right ] . \qquad \begin {array} { c } ( 0 ) \\ ( 1 ) \\ ( 2 ) \\ ( 3 ) \\ ( 4 ) \end {array} $$

جواب اساسی کنونی نشدنی است:

$$ \large m _ b = 0 , \quad m _ f = 0 , \quad p _ b = 0 , \quad s _ 1 = 4 0 , \quad s _ 2 = 4 0 , \quad s _ 3 = - 2 0 . $$

از آنجا که $$ s _ 3 $$ یک مقدار نشدنی دارد، سطری که شامل آن است، به یک متغیر ساختگی نیاز دارد. قید تساوی نیز به یک متغیر ساختگی نیاز دارد. این متغیرهای ساختگی دارای ضریب $$M$$ در سطر $$(0)$$ هستند:

$$ \large \left [ \begin {array} {ccccccccc|c} - 1 & 12 & 9 & 12 & 0 & 0 & 0 & M & M & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 40 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 40 \\ 0 & 0 & 0 & 1 & 0 & 0 & -1 & 1 & 0 & 20 \\ 0 & 5 & 4 & -10 & 0 & 0 & 0 & 0 & 1 & 0 \end {array} \right ] . \qquad \begin {array} { c } ( 0 ) \\ ( 1 ) \\ ( 2 ) \\ ( 3 ) \\ ( 4 ) \end {array} $$

برای جابه‌جا کردن جواب به ناحیه شدنی، $$ s _ 3 $$ متغیر خارج شونده و $$ a _ 1 $$ متغیر وارد شونده خواهد بود. لولا را می‌توان در سطر $$(3)$$ انجام داد:

$$ \large \left[\begin{array}{ccccccccc|c} -1 & 12 & 9 & 12-M & 0 & 0 & M & 0 & M & -20M \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 40 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 40 \\ 0 & 0 & 0 & 1 & 0 & 0 & -1 & 1 & 0 & 20 \\ 0 & 5 & 4 & -10 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right]. \qquad \begin{array}{c} (0) \\ (1) \\ (2) \\ (3) \\ (4) \end{array} $$

متغیر ساختگی دیگر نیز باید به جواب اساسی جابه‌جا شود.

$$ \large \left[\begin{array}{ccccccccc|c} -1 & 12-5M & 9-4M & 12+9M & 0 & 0 & M & 0 & 0 & -20M \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 40 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 40 \\ 0 & 0 & 0 & 1 & 0 & 0 & -1 & 1 & 0 & 20 \\ 0 & 5 & 4 & -10 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right]. \qquad \begin{array}{c} (0) \\ (1) \\ (2) \\ (3) \\ (4) \end{array} $$

اکنون الگوریتم را مانند روش سیمپلکس ساده اجرا می‌کنیم. هدف، حذف ضرایب منفی سطر $$(0)$$ است. از آنجا که $$M$$ هر مقدار ثابت مثبت بزرگ دلخواهی می‌تواند باشد، $$ 12 - 5 M $$ منفی‌ترین ضریب در سطر $$(0)$$ است. بنابراین، $$ m _ b $$ متغیر وارد شونده خواهد بود. انتخاب سطر لولا نسبت به روش سیمپلکس ساده چالش بیشتری دارد.

مشاهده می‌کنیم که هر مقدار در سمت راست سطرهای قیود به جز مقدار سطر $$(4)$$ مثبت است. در این سطر، سمت راست $$0$$ است و متغیر اساسی آن، $$ a _ 2 $$، دارای یک ضریب مثبت است. دو مورد زیر مهم هستند:

• مقادیر سمت راست سطرهای قیود مثبت هستند، یا
• اگر مقدار سمت راست $$ 0 $$ باشد، آنگاه ضریب متغیر اساسی در آن سطر مثبت است.

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

بنابراین، حداقل نسبت برای متغیر وارد شونده $$ \frac {0}{5 } $$ از سطر $$(4)$$ است. این سطر، سطر لولا خواهد بود:

$$ \large \left[\begin{array}{ccccccccc|c} -1 & 0 & -\frac{3}{5} & 36-M & 0 & 0 & M & 0 & M-\frac{12}{5} & -20M \\ 0 & 0 & -4 & 15 & 5 & 0 & 0 & 0 & -1 & 200 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 40 \\ 0 & 0 & 0 & 1 & 0 & 0 & -1 & 1 & 0 & 20 \\ 0 & 5 & 4 & -10 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right]. \qquad \begin{array}{c} (0) \\ (1) \\ (2) \\ (3) \\ (4) \end{array} $$

اکنون، $$ 36 - M $$ منفی‌ترین ضریب در سطر $$(0)$$ است. بنابراین، $$p_ b $$ متغیر وارد شونده خواهد بود. سطر $$(4)$$ دوباره به عنوان سطر لولا انتخاب نخواهد شد، زیرا یک ضریب منفی برای این متغیر دارد. سطری که نسبت را کمینه می‌کند، $$ \frac { 200 } { 15 } $$ سطر $$(1 ) $$ است:

$$ \large \left[\begin{array}{ccccccccc|c} -1 & 0 & 9-\frac{4}{15}M & 0 & \frac{1}{3}M-12 & 0 & M & 0 & \frac{14}{15}M & -\frac{20}{3}M-480 \\ 0 & 0 & -4 & 15 & 5 & 0 & 0 & 0 & -1 & 200 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 40 \\ 0 & 0 & 4 & 0 & -5 & 0 & -15 & 15 & 1 & 100 \\ 0 & 15 & 4 & 0 & 10 & 0 & 0 & 0 & 1 & 400 \end{array}\right]. \qquad \begin{array}{c} (0) \\ (1) \\ (2) \\ (3) \\ (4) \end{array} $$

حال، $$ 9 - \frac {4}{15} $$ منفی‌ترین ضریب در سطر $$ ( 0 ) $$ است. $$ m _ f $$ متغیر وارد شونده و نسبت کمینه‌کننده $$ \frac { 100 } { 4 } $$ در سطر $$ (3)$$ خواهد بود:

$$ \large \left[\begin{array}{ccccccccc|c} -1 & 0 & 0 & 0 & -\frac{3}{4} & 0 & \frac{135}{4} & M-\frac{135}{4} & M-\frac{9}{4} & -705 \\ 0 & 0 & 0 & 1 & 0 & 0 & -1 & 1 & 0 & 20 \\ 0 & 0 & 0 & 0 & 5 & 4 & 15 & -15 & -1 & 60 \\ 0 & 0 & 4 & 0 & -5 & 0 & -15 & 15 & 1 & 100 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & -1 & 0 & 20 \end{array}\right]. \qquad \begin{array}{c} (0) \\ (1) \\ (2) \\ (3) \\ (4) \end{array} $$

اکنون $$ -\frac 34 $$ منفی‌ترین ضریب در سطر $$(0)$$ است. $$ s _ 1 $$ متغیر وارد شونده و نسبت کمینه‌ساز $$ \frac {60}{5}$$ در سطر $$(2)$$ است:‌

$$ \large \left[\begin{array}{ccccccccc|c} -1 & 0 & 0 & 0 & 0 & \frac{3}{5} & 36 & M-36 & M-\frac{12}{5} & -696 \\ 0 & 0 & 0 & 1 & 0 & 0 & -1 & 1 & 0 & 20 \\ 0 & 0 & 0 & 0 & 5 & 4 & 15 & -15 & -1 & 60 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 40 \\ 0 & 5 & 0 & 0 & 0 & -4 & -10 & 10 & 1 & 40 \end{array}\right]. \qquad \begin{array}{c} (0) \\ (1) \\ (2) \\ (3) \\ (4) \end{array} $$

با مثبت بودن همه ضرایب در سطر $$(0)$$ و نبود متغیر ساختگی در جواب، جواب بهینه است و به صورت زیر خواهد بود:

$$ \large m_b=8, \quad m_f=40, \quad p_b=20, \quad z=696. $$

بنابراین، شرکت باید از بهروز به مدت ۸ ساعت در خط مونتاژ و ۲۰ ساعت در خط بسته‌بندی استفاده کند. همچنین، فردین باید ۴۰ ساعت در خط مونتاژ کار کند. این منجر به ۹۶۹ دلار برای یک هفته می‌شود.

روش سیمپلکس در متلب

برای پیاده‌سازی روش سیمپلکس در متلب، می‌توانید از برنامه زیر استفاده کنید.

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

کلیک کنید

1function tab = nma_simplex(A,b,c,debug)
2%function [A,b,c]=nma_simplex(A,b,c)
3%This function implments the simplex matrix algorithm.
4%It accepts A_eq and b_eq and c as defined in standard
5%documentation and generates all the simplex tableaus, and
6%returns the final tableau which the user can read from it the
7%minimum value of the objective function and the optimal x vector
8%directly.                                                                                          
9                                                                                              
10%
11%It runs both phase one and phase two automatically.
12%
13%The input is
14%
15%A: This is the Ax=b matrix. This is for simplex standard
16%   form only. The caller must convert all inequalites to
17%   equalities first by using slack and suprluse variables. This
18%   is what is called the Aeq matrix in Matlab documenation.
19%   This function does not support Ax<b form. A has to be in
20%   standard form
21%
22%b: Vector. This is the right hand side of Ax=b.
23%
24%c: Vector. This is from minimize  J(x) = c'x. As defined in
25%   standard Matlab documentations.
26%
27%debug: flag. Set to true to see lots of internal steps.
28%
29%Returns:
30%
31%This function returns the final tableau. It has the form
32%
33%  [ A | b  ]
34%  [ c | J  ]
35%
36% Version 5/12/2016
37% by Nasser M. Abbasi
38% Free for use.
39 
40validate_input(A,b,c);
41 
42[A,b] = make_phase_one(A,b,debug);
43tab   = simplex(A,b,c,debug,'phase two');
44end
45%==========================
46function [A,b] = make_phase_one(A,b,debug)
47[m,n]              = size(A);
48tab                = zeros(m+1,n+m+1);
49tab(1:m,1:n)       = A;
50tab(end,n+1:end-1) = 1;
51tab(1:m,end)       = b(:);
52tab(1:m,n+1:n+m)   = eye(m);
53 
54if debug
55    fprintf('>>>>Current tableau [phase one]\n');
56    disp(tab);
57end
58                                                                                              
59                                                                                              
60 
61for i = 1:m %now make all entries in bottom row zero
62    tab(end,:) = tab(end,:)-tab(i,:);
63end
64 
65tab = simplex(tab(1:m,1:n+m),tab(1:m,end),tab(end,1:n+m),...
66                                                 debug,'phase one');
67%if tab(end,end) ~=0
68%   error('artificial J(x) is not zero at end of phase one.');
69%end
70 
71A = tab(1:m,1:n);
72b = tab(1:m,end);
73 
74end
75%=================================
76function tab = simplex(A,b,c,debug,phase_name)
77[m,n]        = size(A);
78tab          = zeros(m+1,n+1);
79tab(1:m,1:n) = A;
80tab(m+1,1:n) = c(:);
81tab(1:m,end) = b(:);
82 
83keep_running = true;
84while keep_running
85    if debug
86         fprintf('***********************\n');
87         fprintf('Current tableau [%s] \n',phase_name);
88         disp(tab);
89    end
90 
91    if any(tab(end,1:n)<0)%check if there is negative cost coeff.
92         [~,J] = min(tab(end,1:n)); %yes, find the most negative
93         % now check if corresponding column is unbounded
94         if all(tab(1:m,J)<=0)
95           error('problem unbounded. All entries <= 0 in column %d',J);
96         %do row operations to make all entries in the column 0
97         %except pivot
98         else
99             pivot_row = 0;
100             min_found = inf;
101             for i = 1:m
102                  if tab(i,J)>0
103                      tmp = tab(i,end)/tab(i,J);
104                      if tmp < min_found
105                          min_found = tmp;
106                          pivot_row = i;
107                      end
108                                                                                              
109                                                                                              
110                  end
111             end
112             if debug
113                  fprintf('pivot row is %d\n',pivot_row);
114             end
115             %normalize
116             tab(pivot_row,:) = tab(pivot_row,:)/tab(pivot_row,J);
117             %now make all entries in J column zero.
118             for i=1:m+1
119                  if i ~= pivot_row
120                      tab(i,:)=tab(i,:)-sign(tab(i,J))*...
121                                    abs(tab(i,J))*tab(pivot_row,:);
122                  end
123             end
124         end
125         if debug  %print current basic feasible solution
126             fprintf('current basic feasible solution is\n');
127             disp(get_current_x());
128         end
129    else
130         keep_running=false;
131    end
132end
133 
134    %internal function, finds current basis vector
135    function current_x = get_current_x()
136         current_x = zeros(n,1);
137         for j=1:n
138             if length(find(tab(:,j)==0))==m
139                  idx= tab(:,j)==1;
140                  current_x(j)=tab(idx,end);
141             end
142         end
143    end
144end
145%==========================
146function validate_input(A,b,c)
147if ~ismatrix(A)
148    error('A must be matrix');
149end
150 
151if ~isvector(b)
152    error('b must be vector');
153end
154if ~isvector(c)
155    error('c must be vector');
156end
157 
158                                                                                              
159                                                                                              
160[m,n]=size(A);
161if rank(A) <m
162    error('Rank A must be equal to number of rows in A');
163end
164 
165if length(b) ~= m
166    error('b must have same size as number of rows of A');
167end
168if length(c) ~= n
169    error('c must have same size as number of columns of A');
170end
171end

در برنامه بالا، تابع هدف به صورت زیر تعریف شده است:

$$ \large \min _x J(x) = c^T x $$

قیود نیز به شکل زیر هستند:

$$ \large \begin{align*} Ax &= b\\ x & \geq 0 \end{align*} $$

برای مثال، فرض کنید می‌خواهیم $$2 x_1 + 3 x_2 $$ را با توجه به قیود زیر کمینه کنیم:

$$ \large \begin{align*} 4 x_1+2 x_2 &\geq 12\\ x_1+4 x_2 &\geq 6 \\ x_i \geq 0 \end{align*} $$

قیود را به فرم استاندارد برنامه می‌نویسیم:

$$ \large \begin{align*} 4 x_1+2 x_2 -x_3 &= 12\\ x_1+4 x_2 -x_4 &=6 \end{align*} $$

که در آن، $$ x _ i \ge 0 $$ است.

بنابراین:

$$ \large \begin{align*} A =& \begin{pmatrix} 4&2&-1&0\\ 1&4&0&-1 \end{pmatrix} \end{align*} $$

و

$$ \large \begin{align*} b =& \begin{pmatrix} 12\\ 6 \end{pmatrix} \end{align*} $$

و

$$ \large c^T = \begin{pmatrix} 2&3&0&0 \end{pmatrix} $$

برای حل مسئله با متلب، از nma_simplex استفاده می‌کنیم:

1A=[4,2,-1,0;
2  1,4,0,-1];
3b=[12,6];
4c=[2,3,0,0];
5nma_simplex(A,b,c,true);

که نتیجه اجرای آن به صورت زیر خواهد بود:

>>>>Current tableau [phase one]
4 2 -1 0 1 0 12
1 4 0 -1 0 1 6
0 0 0 0 1 1 0

***********************
Current tableau [phase one]
4 2 -1 0 1 0 12
1 4 0 -1 0 1 6
-5 -6 1 1 0 0 0

pivot row is 2
current basic feasible solution is
0
1.5000
0
0
9.0000
0

***********************
Current tableau [phase one]
3.5000 0 -1.0000 0.5000 1.0000 -0.5000 9.0000
0.2500 1.0000 0 -0.2500 0 0.2500 1.5000
-3.5000 0 1.0000 -0.5000 0 1.5000 9.0000

pivot row is 1
current basic feasible solution is
2.5714
0.8571
0
0
0
0

***********************
Current tableau [phase one]
1.0000 0 -0.2857 0.1429 0.2857 -0.1429 2.5714
0 1.0000 0.0714 -0.2857 -0.0714 0.2857 0.8571
0 0 0 0 1.0000 1.0000 18.0000

***********************
Current tableau [phase two]
1.0000 0 -0.2857 0.1429 2.5714
0 1.0000 0.0714 -0.2857 0.8571
2.0000 3.0000 0 0 0

می‌بینیم که جواب $$x_1=2.5714 $$ و $$x_2=0.8671 $$ است. مقدار بهینه تابع هدف نیز به شکل زیر خواهد بود:

$$\large \begin{align*} J(x)&=2(2.5714)+3(0.8671) \\ &=7.7441 \end{align*} $$

با استفاده از نرم‌افزار اکسل نیز می‌توان مسائل را به روش سیمپلکس به آسانی حل کرد. برای آشنایی با پیاده‌سازی روش سیمپلکس در اکسل، پیشنهاد می‌کنیم مطلب «سیمپلکس در اکسل — راهنمای کاربردی» را مطالعه کنید.