برنامه ریزی خطی در پایتون با استفاده از Scipy

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

در میان کتابخانه‌های پایتون در حوزه بهینه سازی خطی، چارچوب SciPy، بسته CVXOPT، کتابخانه PuLP و کتابخانه Pyomo از جمله معروف‌ترین راهکارهای پایتون در این حوزه محسوب می‌شوند که در این میان، SciPy.Optimize که زیرماژولی از SciPy است جایگاه ویژه‌ای دارد.

کلاس linprog برای برنامه ریزی خطی در پایتون

در این یادداشت، مروری ساده بر حل مسأله برنامه ریزی خطی در پایتون توسط کتابخانه scipy.optimize و تابع linprog انجام می‌دهیم. این مرور کوتاه، می‌تواند مقدمه‌ای برای حل مسائل بهینه سازی خطی باشد و بر اساس توانمندی و علاقمندی پژوهشگران قابل پیگیری و گسترش خواهد بود. کلاس و آرگومان‌های تابع موردنظر در اینجا تا حد زیادی به زبان متلب شبیه است. بنابراین افرادی که قبلا توابع بهینه‌سازی متلب به‌ویژه تابع linprog را در MATLAB دیده‌اند، شباهت زیادی بین این تابع (از نام آن گرفته تا آرگومان‌ها و چیدمان آنها) و تابع مورداستفاده در پایتون احساس خواهند کرد.

آرگومان‌ها و اجزای تابع linprog

فرمت استاندارد یک مسأله برنامه‌ریزی خطی در پایتون به شرح زیر است:

$$\begin{equation}
\begin{aligned}
& \underset{x}{\text{min}}
& & c^T x \\
& \text{s.t.} & & Ax \leq b \\
& & & A_{eq} \leq b_{eq} \\
& & & lb \leq x \leq ub
\end{aligned}
\end{equation} $$

در اینجا، \( c \) ضرایب تابع هدف را نشان می‌دهد. \( A \) و \( b \) به‌ترتیب نمایانگر ضرایب و مقادیر سمت راست در محدودیت‌های نامساوی بوده و \( A_{eq} \) و \( b_{eq} \) نیز به‌ترتیب نمایانگر ضرایب و مقادیر سمت راست در محدودیت‌های تساوی این مسأله برنامه‌ریزی خطی هستند. کران پایین و بالای متغیرهای تصمیم مسأله نیز با \( lb \) و \( ub \) مشخص شده‌اند. این فرمت منطبق با ساختار موردپذیرش scipy.optimize است. بنابراین برای حل هر مسأله برنامه ریاضی خطی، می‌توانیم مسأله را به ساختار فوق تبدیل کرده و سپس از حل‌کننده linprog برای آن استفاده کنیم:

linprog(c, A, b, Aeq, beq, bounds, method, callback, options, x0)

در کلاس scipy.optimize.linprog ضرایب تابع هدف (c) در قالب یک بردار یک بعدی تعریف می‌شود. طبیعی است که اگر تابع هدف از نوع حداکثرسازی (max) باشد، برای تبدیل آن به حداقل‌سازی (min) باید ضرایب را در یک منفی ضرب کنیم. ضرایب محدودیت‌های کوچکترمساوی (A) در قالب یک ماتریس که هر سطر نشان‌گر یک محدودیت و هر ستون آن نشانگر یکی از متغیرهای مسأله (به‌ترتیب نمایش در c) است تعریف می‌شود. مقادیر سمت راست محدودیت‌های کوچترمساوی (b) نیز یک بردار به طول تعداد این محدودیت‌ها است. قالب ضرایب محدودیت‌های مساوی (Aeq) و مقادیر سمت راست محدودیت‌های تساوی (beq) نیز همانند محدودیت‌های نامساوی  خواهد بود. مقادیر کران بالا و پایین متغیرهای تصمیم در قالب یک دنباله به فرمت (lb, ub) تعریف می‌شوند که در حالت پیش‌فرض به‌صورت (None و 0) هستند یعنی کران پایین همه متغیرها صفر و کران بالاهای همه بی‌نهایت است.

روش حل برنامه ریزی خطی توسط linprog به‌صورت پیش‌فرض روش نقطه درونی (‘interior-point’) است. با این حال، روش‌های سیمپلکس (‘simplex’) و سیمپلکس تجدیدنظرشده (‘revised simplex’) نیز دیگر روش‌های موجود این کلاس برای حل مسائل بهینه‌سازی خطی هستند. هریک از این روش‌ها را می‌توان با مقداردهی به آرگومان method فراخوانی کرد.

استفاده از linprog یک مثال برنامه ریزی خطی

یک مسأله برنامه‌ریزی خطی ساده را به صورت زیر در نظر بگیرید:

$$\begin{equation}
\begin{aligned}
& \underset{x}{\text{min}}
& & x_{1}-2x_{2} \\
& \text{s.t.} & & 3x_{1}+x_{2}\geq 3 \\
& & & x_{1}-x_{2}\leq 2 \\
& & & x_{1}+2x_{2} = 2 \\
& & & x_{1} \geq 1 \\
& & & x_{2} \geq 0 \\
\end{aligned}
\end{equation} $$

این مسأله یک تابع هدف از نوع بیشینه‌سازی، دو محدودیت نامساوی و یک محدودیت تساوی دارد. کران پایین و بالای متغیرهای تصمیم نیز مشخص شده‌اند. با تبدیل‌های لازم برای ایجاد فرم استاندارد linprog، مسأله را به‌فرم کمینه‌سازی (min) تبدیل کرده و محدودیت بزرگترمساوی را نیز به کوچکترمساوی تبدیل می‌کنیم. سپس می‌توان مسأله موردنظر را در فضای پایتون با تابع linprog به شکل زیر پیاده‌سازی کرد:

from scipy.optimize import linprog
c = [-1, 2]
A = [[-3, -1],[1, -1]]
b= [-3,2]
Aeq = [[1, 2]]
beq = [2]
x1_b=[1,None]
x2_b=[0,None]
opt = linprog(c, A_ub=A, b_ub=b, A_eq=Aeq, b_eq=beq, bounds=[x1_b, x2_b])

خروجی حاصل از اجرای فوق با استفاده از دستور print به صورت زیر خواهد بود:

>>> pritn(opt)
    con: array([-1.25659483e-11])
    fun: -1.9999999999957272
message: 'Optimization terminated successfully.'
    nit: 4
  slack: array([3.00000000e+00, 6.32827124e-14])
 status: 0
success: True
      x: array([2.00000000e+00, 4.20965904e-12])

در کلاس linprog به‌صورت پیش‌فرض از روش نقطه درونی استفاده می‌شود که ممکن است با خطای تقریب همراه باشد. در صورت نیاز می‌توان برای افزایش دقت روش حل را به سیمپلکس تجدیدنظرشده یا سیمپلکس عادی تغییر داد. پس از افزودن آرگومان method='revised simplex' برای حل با سیمپلکس تجدیدنظرشده، پاسخ نهایی به شکل زیر محاسبه می‌شود:

>>> opt = linprog(c, A_ub=A, b_ub=b, A_eq=Aeq, b_eq=beq, bounds=[x1_b, x2_b], method='revised simplex')
>>> print(opt)
     con: array([0.])
     fun: -2.0
 message: 'Optimization terminated successfully.'
     nit: 2
   slack: array([3., 0.])
  status: 0
 success: True
       x: array([2., 0.])

تحلیل خروجی حل مسأله

همان طور که در مثال فوق مشخص است، خروجی حاصل از اجرای linprog در هر مسأله برنامه ریزی خطی در پایتون شامل اجزای زیر خواهد بود:

• fun مقدار بهینه تابع هدف مسأله است.
• slack مقادیر متغیرهای کمکی یا لنگی مربوط به محدودیت‌های کوچکترمساوی را نمایش می‌دهد.
• con مقادیر متغیرهای مصنوعی یا باقی‌مانده محدودیت‌های تساوی را نشان می‌دهد.
• success زمانی که نقطه بهینه یافته شود، مقدار True را برمی‌گرداند.
• int نمایان‌گر وضعیت خروجی الگوریتم است و اعداد صحیح ۰ تا ۴ را نمایش وضعیت‌های زیر نشان می‌دهد:
  • مقدار 0 برای پایان موفقیت‌آمیز بهینه‌سازی
  • مقدار 1 برای توقف الگوریتم به دلیل رسیدن به حداکثر تعداد تکرار
  • مقدار 2 برای شرایط پاسخ نشدنی (منطقه موجه نشدنی)
  • مقدار 3 برای شرایط پاسخ نامحدود
  • مقدار 4 برای مواجهه الگوریتم با دشواری‌های عددی
• nit تعداد تکرارهای الگوریتم را نشان می‌دهد.
• message وضعیت خروجی الگوریتم را توصیف می‌کند.

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