فهرست بستن

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

بسیاری از مسائل صنعت و مهندسی در عمل به برنامه‌ریزی بهینه با تابع هزینه قابل بیان به شکل خطی تحت قیود تساوی و ناتساوی ختم می‌شود. ابزارهای بسیاری برای حل این نوع مسائل طراحی شده است که بطور رایگان در دسترس عموم قرار دارد؛ مثل GNU Linear Programming Kit یا GLTK. با این حال این ابزارها بعنوان ورودی از مدل مجتمع ماتریسی استفاده می کنند. کتابخانه PuLP در پایتون واسط بین کاربر و حل کننده‌های برنامه‌ریزی خطی می‌باشد تا کاربر در گیر ساخت مدل ماتریسی که اغلب زمان بر و پر خطا است نباشد.

بسم الله الرحمن الرحیم

مثل اکثر آموزش‌های دیگر این آموزش نیز با یک مثال خیلی ساده شروع می‌شود. ابتدا با هم شرح مسئله را می‌بینیم و بعد از آن نحوه مدل کردن آن در پایتون با استفاده از PuLP.

قبل از هر چیز توابع و کلاس‌های مورد نیاز را از کتابخانه PuLP فراخوانی می‌نماییم:

from pulp import LpProblem, LpMaximize, LpVariable, \
                 GLPK, LpStatus, value

فرض کنیم صاحب یک قنادی هستیم و می‌خواهیم دو محصول نان باگل و کیک مافین را تولید نماییم. مواد اولیه محدودی در اختیار ماست و قیمت هر یک از این محصولات متفاوت است. برای داشتن بیشترین سود از هر کدام چه تعداد باید تولید کنیم؟! فرض کنیم برای تولید هر نان باگل به ۵ واحد آرد، دو واحد تخم مرغ و یک واحد شکر نیاز داریم. همچنین برای تولید کیک مافین به ۴ واحد آرد، چهار واحد تخم مرغ و دو واحد شکر نیاز داریم. سود حاصل از فروش هر واحد نان باگل برابر ۱۰ واحد و سود حاصل از تولید هر واحد کیک مافین ۱۲ واحد سود حاصل قنادی می‌شود.

حالا که مسئله توضیح داده شد، ببینیم با استفاده از کتابخانه PuLP چگونه می‌توانیم مسئله را مدل سازی نماییم. ابتدا مسئله را با نام مشخص و نوع مشخص ایجاد می‌نماییم. در این مثال هدف ما ماکزیمم کردن سود است. با استفاده از LpProblem خواهیم داشت:

# Problem
myLpProblem = LpProblem("My Problem", LpMaximize)

متغیرهای مسئله ما هم تعداد نان باگل و کیک مافین تولیدی می‌باشد. آنها را هم با LpVariable تعریف می‌نماییم:

# Variables
bagel = LpVariable("Bagel", lowBound=0, cat='Integer')
muffin = LpVariable("Muffin", lowBound=0, cat='Integer')

همانطور که مشهود است، متغیرها از نوع عدد صحیح و محدوده پایین آنها برابر صفر تعریف شده اند اگر می‌خواستیم پیوسته باشند بجای Integer از Continuous استفاده می‌کردیم که وابسته به مسئله است. بعد از تعریف متغیرها نوبت به اضافه کردن قیود مسئله می‌رسد. در این مسئله قیدها میزان کل موجودی آرد، تخم مرغ و شکر است که به ترتیب برابر ۵۰، ۳۰ و ۲۰ است. با در نظر گرفتن میزان تولید از هر کدام از دو محصول نباید میزان استفاده از این مواد اولیه ماکزیمم مقدار را نقض نماید و از آن بیشتر شود. برای مدل کردن این قیود بصورت زیر عمل می‌نماییم:

# Constrains
myLpProblem += 5 * bagel + 4 * muffin <= 50
myLpProblem += 2 * bagel + 4 * muffin <= 30
myLpProblem += 1 * bagel + 2 * muffin <= 20

همان طور که مشهود است قید با توجه به مسئله بصورت شرطی نوشته شده و به مسئله یعنی myLpProblem اضافه می‌شود. بعد از اتمام اضافه کردن قیود می‌توانیم تابع هدف را اضافه کنیم که میزان سود با توجه به تولیدات است. کد زیر این کار را برای ما انجام می‌دهد:

# Objective function
myLpProblem += 12 * muffin + 10 * bagel

برای حل مسئله از تابع solve داخل myLpProblem استفاده می کنیم. حل کننده مورد استفاده در این مثال همانطور که گفته شد، GLPK است و ما نمی خواهیم پیامهای حین حل برای ما نمایش داده شوند:

# solve the problem
status = myLpProblem.solve(GLPK(msg=1))

در نهایت خروجی‌های مورد نیاز چاپ می‌شوند:

print("Condition:", LpStatus[status])
print("Muffin production:", muffin.varValue)
print("Bagel production:", bagel.varValue)

print("Revenue:", value(myLpProblem.objective))

که به شکل زیر خواهد بود:

Condition: Optimal
Muffin production: 5
Bagel production: 5
Revenue: 110

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

An Integer Linear Programming and Game Theory Based Optimization for Demand-side Management in Smart Grid

که از لینک زیر قابل خریداری می‌باشد:

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

1 Comment

دیدگاهتان را بنویسید

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