در آموزش‌های قبلی مجله فرادرس، با روش سیمپلکس و همچنین، سیمپلکس دوگان آشنا شدیم. در این آموزش، «روش سیمپلکس تجدید نظر شده» (Revised Simplex Method) را معرفی خواهیم کرد.

روش سیمپلکس تجدید نظر شده

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

  • سطر ارزیابی خالص $$ \Delta _ j $$ برای تعیین متغیر غیرپایه که وارد پایه می‌شود.
  • ستون لولا
  • متغیرهای پایه فعلی و مقادیر آن‌ها (ستون $$ X_ B $$) برای تعیین حداقل مقدار نسبت مثبت و سپس مشخص کردن متغیر پایه برای خروج از پایه.

اطلاعات بالا مستقیماً‌ از معادلات اصلی با استفاده از وارون ماتریس پایه فعلی در هر تکرار به دست می‌آید.

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

  • فرم استاندارد اول: در این فرم، فرض می‌شود که یک ماتریس یکه پس از تعیینِ فقط متغییرهای کمکی به دست می‌آید.
  • فرم استاندارد دوم: اگر متغیرهای مصنوعی یا ساختگی برای یک ماتریس یکه لازم باشند، آنگاه از روش دو فازی سیمپلکس معمولی استفاده می‌شود، به گونه‌ای که با متغیرهای ساختگی کمی متفاوت‌تر برخورد کند.

مراحل روش سیمپلکس تجدید نظر شده به فرم استاندارد

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

$$ \large \operatorname {Max}\;\;\;\;\; Z = 2 x _ { 1 } + x _ { 2 }
\\ \large
\operatorname {Subject to}\;\;\;\
\begin{array}{l}
3 x_{1}+4 x_{2} \leq 6 \\
6 x_{1}+x_{2} \leq 3 \\
\text { } x_{1}, x_{2} \geq 0
\end{array} $$

مسئله را به فرم زیر می‌نویسیم:

$$ \large \operatorname {Max} \;\;\;\;\;\;\; Z = 2 x _ { 1 } + x _ { 2 } + 0 s _ { 1 } + 0 s _ { 2 }
\\ \large
\operatorname {Subject to} \;\;\;\;\;\;
\begin{array}{l}
3 x_{1}+4 x_{2}+s_{1}=6 \\
6 x_{1}+x_{2}+s_{2}=3 \\
\text { } x_{1}, x_{2}, s_{1}, s_{2} \geq 0
\end{array} $$

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

  • مطمئن می‌شویم که برای هر $$ i $$، نامساوی $$ b _ i \ge 0 $$ برقرار باشد.
  • تابع هدف باید بیشینه‌ساز باشد.
  • از متغیرهای کمکی نامنفی برای تبدیل نامساوی‌ها به تساوی استفاده می‌کنیم.

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

$$ \large \begin {array} { l }
Z – 2 x _ { 1 } – x _ { 2 } + 0 s _ { 1 } + 0 s _ { 2 } = 0 \\
3 x _ { 1 } + 4 x _ { 2 } + s _ { 1 } + 0 s _ { 2 } = 6 \\
6 x _ { 1 } + x _ { 2 } + 0 s _ { 1 } + s _ { 2 } = 3 \\
x _ { 1 , } x _ { 2 } , s _ { 1 } , s _ { 2 } \geq 0
\end {array} $$

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

$$ \large \left [ \begin {array} {ccccc}
1 & -2 & -1 & 0 & 0 \\
0 & 3 & 4 & 1 & 0 \\
0 & 6 & 1 & 0 & 1
\end {array} \right ] \left [ \begin {array} { l }
z \\
x _ { 1 } \\
x _ { 2 } \\
s _ { 1 } \\
s _ { 2 }
\end {array} \right ] = \left [ \begin {array} { c }
0 \\
6 \\
3
\end {array} \right ] $$

بردار ستونی متناظر با $$ Z $$ معمولاً با $$ e _ 1 $$ مشخص می‌شود. ماتریس $$ B_ 1 $$ نیز به شکل $$ { B } _ { 1 } = \left [ \beta _ { 0 } ^ { ( 1 ) } , \beta _ { 1 } ^ { ( 1 ) } , \beta _ { 2 } ^ { ( 1 ) } \ldots \beta _ { \mathrm { n } } ^ { ( 1 ) } \right ] $$ است. بنابراین، ستون‌های $$ \beta _ { 0 } ^ { ( 1 ) } $$، $$\beta _ { 1 } ^ { ( 1 ) } $$ و $$\beta _ { 2 } ^ { ( 1 ) } $$ پایه‌های ماتریس $$ B_ 1 $$ هستند.

سیمپلکس تجدید نظر شده

گام ۳: $$ \Delta _ j $$ برای $$ a _ 1 ^ {(1)}$$ و $$ a _ 2 ^ { (1)}$$ را محاسبه می‌کنیم.

$$\Delta _ 1 $$: اولین سطر $$ B_ 1 ^ {-1} \times a _ 1 ^ { ( 1 )} = 1 \times – 2 + 0 \times 3 + 0 \times 6 = – 2 $$

$$\Delta _ 2 $$: اولین سطر $$ B_ 1 ^ {-1} \times a _ 2 ^ { ( 1 )} = 1 \times – 1 + 0 \times 4 + 0 \times 1 = – 1 $$

گام ۴: آزمون بهینه بودن را اعمال می‌کنیم.

هر دو $$ \Delta _ 1 $$ و $$ \Delta _ 2 $$ منفی هستند. بنابراین، منفی‌ترین مقدار را پیدا می‌کنیم و و بردار وارد شونده را تعیین می‌کنیم. منفی‌ترین مقدار $$ \Delta _ 1 = – 2 $$ است. این مشخص می‌کند که $$ a _ 1 ^ {(1)} ( x _ 1 ) $$ بردار وارد شونده است.

گام ۵: بردار ستونی $$ X _ k $$ را محاسبه می‌کنیم:

$$ \large X_ k = B_ 1 ^ {-1} \times a _ 1 ^ {(1)} $$

$$ \large \left [ \begin {array} { c c c }
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end {array} \right ] \times \left [ \begin {array} { c }
– 2 \\
3 \\
6
\end {array} \right ] = \left [ \begin {array} { c }
– 2 \\
3 \\
6
\end {array} \right ] $$

گام ۶: بردار خارج شونده را تعیین می‌کنیم. قرار نیست برای سطر $$ Z $$ این کار را انجام دهیم.

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

گام ۷: جواب بهبودیافته را تعیین می‌کنیم.

ستون $$ e _ 1 $$ هرگز تغییر نخواهد کرد و $$ x _ 1 $$ وارد شونده است، بنابراین، آن را بیرون از مرز مستطیل قرار می‌دهیم.

سیمپلکس تجدیدنظر شده

عنصر لولا را به $$ 1 $$ تبدیل می‌کنیم و عناصر ستون مربوطه را صفر می‌کنیم.

سیمپلکس تجدیدنظر شده

جدول را برای تکرار دوم تشکیل می‌دهیم.

جدول سیمپلکس اصلاح شده

مقادیر زیر را داریم:

$$ \large \begin {array} { l }
\Delta _ { 4 } = 1 \times 0 + 0 \times 0 + 1 / 3 \times 1 = 1 / 3 \\
\Delta _ { 2 } = 1 \times – 1 + 0 \times 4 + 1 / 3 \times 1 = – 2 / 3
\end {array} $$

می‌بینیم که $$\Delta _ 2 $$ منفی‌تر است، بنابراین، $$ a _ 2 ^ {(1)}$$ بردار وارد شونده است.

اکنون بردار ستونی را محاسبه می‌کنیم:

$$ \large \left [ \begin {array} {ccc}
1 & 0 & 1 / 3 \\
0 & 1 & – 1 / 2 \\
0 & 0 & 1 / 6
\end {array} \right ] \times \left [ \begin {array} { c }
– 1 \\
4 \\
1
\end {array} \right ] = \left [ \begin {array} { c }
– 2 / 3 \\
7 / 2 \\
1 / 6
\end {array} \right ] $$

حال، بردار خارج شونده را تعیین می‌کنیم.

بردار خارج شونده سیمپلکس

در نهایت، جواب بهبودیافته را مشخص می‌کنیم.

جواب بهینه سیمپلکس

روش سیمپلکس تجدید نظر شده

اکنون $$\Delta _ 3 $$ و $$ \Delta _ 4 $$ را محاسبه می‌کنیم:

$$ \large \begin {array} { l }
\Delta _ { 4 } = 1 \times 0 + 4 / 2 1 \times 0 + 5 / 2 1 \times 1 = 5 / 2 1 \\
\Delta _ { 3 } = 1 \times 0 + 4 / 2 1 \times 1 + 5 / 2 1 \times 0 = 4 / 2 1
\end {array} $$

$$ \Delta _ 4 $$ و $$ \Delta _ 3 $$ مثبت هستند. بنابراین، جواب بهینه $$ \text {Max} \; Z = 13 / 7 $$، $$x _ 1 = 2 / 7 $$ و $$ x _ 2 = 9 / 7 $$ است.

مثالی از روش سیمپلکس تجدید نظر شده

می‌خواهیم مسئله زیر را حل کنیم:

$$ \large \operatorname {Max} Z = x _ { 1 } + 2 x _ { 2 } \\ \large \text {Subject to} \;\;\;
\begin {array} { l }
x _ { 1 } + x _ { 2 } \leq 3 \\
x _ { 1 } + 2 x _ { 2 } \leq 5 \\
3 x _ { 1 } + x _ { 2 } \leq 6 \\
x _ { 1 } , x _ { 2 } \geq 0
\end {array} $$

حل: مسئله را به فرم زیر می‌نویسیم:

$$ \large \operatorname {Max} \;\;\; Z = x _ { 1 } + 2 x _ { 2 } + 0 s _ { 1 } + 0 s _ { 2 } + 0 s _ { 3 }
\\ \large \text {Subject to} \;\;\;\;
\begin {array} { l }
x _ { 1 } + x _ { 2 } + s _ { 1 } = 3 \\
x _ { 1 } + 2 x _ { 2 } + s _ { 2 } = 5 \\
3 x _ { 1 } + x _ { 2 } + s _ { 3 } = 6 \\
\text { } x _ { 1 } , x _ { 2 } , s _ { 1 } , s _ { 2 } , s _ { 3 } \geq 0
\end {array} $$

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

$$ \large \begin {array} { l }
Z – x _ { 1 } – 2 { x } _ { 2 } – 0 { s } _ { 1 } – 0 { s } _ { 2 } – 0 { s } _ { 3 } = 0 \\
{ x } _ { 1 } + { x } _ { 2 } + { s } _ { 1 } + 0 { s } _ { 2 } + 0 { s } _ { 3 } = 3 \\
{ x } _ { 1 } + 2 { x } _ { 2 } + 0 { s } _ { 1 } + { s } _ { 2 } + 0 { s } _ { 3 } = 5 \\
3 { x } _ { 1 } + { x } _ { 2 } + 0 { s } _ { 1 } + 0 { s } _ { 2 } + { s } _ { 3 } = 6 \\
{ x } _ { 1 } , { x } _ { 2 } , { s } _ { 1 } , { s } _ { 2 } , { s } _ { 3 } \geq 0
\end {array} $$

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

فرم ماتریسی جدول سیمپلکس

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

جدول سیمپلکس

محاسبه $$ \Delta _ j $$ برای $$ a_ 1 ^ {(1)}$$ و $$ a _ 2 ^ { ( 1 ) }  $$ به صورت زیر است:

$$ \Delta _ 1 $$: اولین سطر $$ { B } _ { 1 } ^ { – 1 } \times { a } _ { 1 } ^ { ( 1 ) } = 1 \times – 1 + 0 \times 1+0\times 1+0\times 3=-1 $$.

$$ \Delta _ 2 $$: اولین سطر $$ { B } _ { 1 } ^ { – 1 } \times { a } _ { 2 } ^ { ( 1 ) } = 1 \times – 2 + 0 \times 1 + 0 \times 2 + 0 \times 1 = – 2 $$

می‌بینیم که $$ \Delta _ 2 = – 2 $$ منفی‌تر است. بنابراین، $$ a _ 2 ^ { ( 1 ) } (x_ 2 ) $$ بردار وارد شونده است.

بردار ستونی $$ X _ k $$ را محاسبه می‌کنیم:

$$ \large X _ k = B _ 1 ^ { – 1 } \times a _ 2 ^ { (  1 ) } $$

$$ \large \left [ \begin {array} { c c c c }
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end {array} \right ] \times \left [ \begin {array} { c }
– 2 \\
1 \\
2 \\
1
\end {array} \right ] = \left [ \begin {array} { c }
– 2 \\
1 \\
2 \\
1
\end {array} \right ] $$

اکنون جواب بهبودیافته را مشخص می‌کنیم.

جواب بهبودیافته

روش سیمپلکس تجدید نظر شده

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

روش سیمپلکس تجدید نظر شده

مقادیر $$ \Delta _ 1 $$ و $$ \Delta _ 4 $$ به صورت زیر محاسبه می‌شوند:

$$ \large \begin {array} { l }
\Delta _ { 1 } = 1 \times – 1 + 0 \times 1 + 1 \times 1 + 0 \times 3 = 0 \\
\Delta _ { 4 } = 1 \times 0 + 0 \times 0 + 1 \times 1 + 0 \times 0 = 1
\end {array} $$

می‌بینیم که $$ \Delta _ 1 $$ و $$ \Delta _ 4 $$ مثبت هستند. بنابراین، جواب بهینه $$ \text{Max}\; Z = 5 $$، $$ x _ 1 = 0 $$ و $$ x_ 2 = 5 / 2 $$ خواهد بود.

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

برای آشنایی بهتر با روش سیمپلکس، پیشنهاد می‌کنیم دوره ویدیویی «آموزش الگوریتم سیمپلکس (Simplex)» را مشاهده کنید. در این آموزش که مدت زمان آن ۱ ساعت و ۲۸ دقیقه است، ابتدا مقدمه‌ای درباره روش سیمپلکس ارائه شده و پس از آن درباره شرایط حل مسئله سیمپلکس بحث شده است. سایر سرفصل‌های این دوره ویدیویی عبارتند از: گام‌های الگوریتم سیمپلکس، استانداردسازی مسئله، تشکیل جدول اولیه، انتخاب متغیر وارد شونده و بررسی شرایط ورود، انتخاب متغیر خارج شونده و بررسی تست مینیمم، انجام عملیات لولایی و رفتن به نقطه جدید، برسی شرایط توقف، بررسی حالات خاص، جواب بهینه نامتناهی، تباهیدگی، جواب بهینه چندگانه، جواب بهینه منحصر به فرد و بررسی روابط جدول سیمپلکس. همچنین، در پایان این آموزش، مثال جامعی حل شده است.

آموزش روش سیمپلکس

اگر این مطلب برای شما مفید بوده است، آموزش‌ها و مطالب زیر نیز به شما پیشنهاد می‌شوند:

سید سراج حمیدی (+)

«سید سراج حمیدی» دانش‌آموخته مهندسی برق است. او مدتی در زمینه انرژی‌های تجدیدپذیر فعالیت کرده، و در حال حاضر، آموزش‌های مهندسی برق و ریاضیات مجله فرادرس را می‌نویسد.

بر اساس رای 2 نفر

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *