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

منتشر‌شده در: وبسایت درباره علم داده به تاریخ ۵ آپریل ۲۰۲۰
لینک منبع: Solving your first linear program in Python

شما ممکن است اصطلاح «برنامه‌ریزی خطی» را در جایی از علم داده یا تحقیق به کار برده باشید. من سعی خواهم کرد که توضیح دهم که چیست و چگونه می‌توان یک برنامه خطی را در پایتون پیاده‌سازی کرد.

چرا به برنامه‌ریزی خطی نیاز داریم؟

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

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

من شخصا برنامه‌های خطی را در بسیاری از کاربردها به‌کار برده‌ام.

• صنعت حمل و نقل: برای بهینه‌سازی مسیر که در آن انبارهای مختلف باید مورد بازدید قرار گیرند در حالی که هزینه‌های عملیاتی را به حداقل می‌رسانند.
• صنعت انرژی: مصرف برق برای یک خانواده با پنل خورشیدی را بهینه کنید، در حالی که الگوی بار را پیش‌بینی می‌کنید.
• مشکلات منطقی: حل مشکلات/معماها با استفاده از یک برنامه خطی که در آن همه محدودیت‌های منطقی باید به صورت موازی در نظر گرفته شوند (موضوع پست بعدی).

برنامه‌ریزی خطی چیست؟

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

گفتگوی فنی: یک برنامه خطی یک تابع هدف (یا تابع هزینه) را بهینه‌سازی می‌کند که در آن مجموعه‌ای از تعادل‌های خطی (و نابرابری‌ها) باید برآورده شوند.

من تمام این موارد را با یک مثال واقعی نشان خواهم داد.

مثال اجرایی

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

• وزن کل مواد اولیه دقیقا ۷۰۰ گرم بود.
• مقدار کره نصف مقدار شکر بود
• وزن آرد و تخم‌مرغ با هم حداکثر ۴۵۰ گرم بود.
• وزن تخم‌مرغ و کره به طور متوسط حداکثر ۳۰۰ گرم بود.
• وزن تخم‌مرغ و کره بیشتر از مجموع آرد و شکر بود.

آیا می توان مقادیر بهینه هر یک از موارد را از اطلاعات بالا بدست آورد؟

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

ما می‌توانیم هر یک از متغیرها را به صورت زیر تعریف کنیم:

• آرد: f
• تخم‌‌مرغ‌ها: e
• کره: b
• شکر: s

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

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

مثالی از یک تابع هزینه آگاه از سلامت می‌تواند به شرح زیر باشد:

• به حداقل رساندن مصرف کره و تخم‌مرغ

یا به عبارت دیگر

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

ما ماتریس‌های زیر را تعریف می‌کنیم

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

بنابراین مساله ما با استفاده از جبر خطی شکل می‌گیرد

توجه داشته باشید که ما از ترانهاده (سوپراسکریپت T) ماتریس c استفاده می‌کنیم تا بتوانیم آن را با ماتریس راه‌حل X ضرب کنیم.

حالا می‌توانیم کدنویسی این مساله را در پایتون آغاز کنیم.

چگونه برنامه خطی در پایتون بنویسیم

تنظیمات پایتون من

• Python 3.8.2
• SciPy 1.18.1
• Numpy 1.4.1
• Cvxopt 1.2.3 (اختیاری)

استفاده از سای‌پای

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

from scipy.optimize import linprog
import numpy as np
from cvxopt import matrix
from cvxopt import glpk

# The perfect cake recipe that I partially remember
# Equations to solve
# f + e + b + s = 700
# b -0.5s = 0
# f + e <= 450
# e + b <= 300
# -f + e + b -s <= 0

# X matrix
var_list = ['Flour', 'Eggs', 'Butter', 'Sugar']
# Inequality equations, LHS
A_ineq = [[1., 1., 0., 0.], [0., 1., 1., 0.], [-1., 1., -1., 1.]]

# Inequality equations, RHS
B_ineq = [450., 300.,0.]

# Equality equations, LHS
A_eq = [[1., 1., 1., 1.], [0., 0., 1., -0.5]]

# Equality equations, RHS
B_eq = [700., 0]

# Cost function
c = [0., 0., 1., 1.]  # construct a cost function

print('WITHOUT BOUNDS')
# pass these matrices to linprog, use the method 'interior-point'. '_ub' implies the upper-bound or
# inequality matrices and '_eq' imply the equality matrices
res_no_bounds = linprog(c, A_ub=A_ineq, b_ub=B_ineq, A_eq=A_eq, b_eq=B_eq, method='interior-point')
print(res_no_bounds)

که خروجی زیر را تولید می‌کند:

WITHOUT BOUNDS      
con: array([ 5.27055590e-08, -3.78719278e-11])      
fun: 249.99999998121916  
message: 'Optimization terminated successfully.'      
nit: 5    
slack: array([3.39247208e-08, 6.95661413e+01, 7.24656159e+01])   status: 0  
success: True        
x: array([302.8994746 , 147.10052537,  83.33333333, 166.66666665])

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

• آرد = ۳۰۲.۸۹ گرم
• تخم‌مرغ‌ها = ۱۴۷.۱۰ گرم
• کره = ۸۳.۳۳ گرم
• قند = ۱۶۶.۶۶ گرم

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

• توجه: اگر مقادیر بالا را به دست نیاوردید، ممکن است دلیل آن نسخه سای‌فایی باشد که استفاده کرده‌اید و یا روش پیش‌فرض استفاده‌شده برای اجرای برنامه خطی متفاوت باشد، یعنی  مثلا سیمپلکس در مقابل   نقطه درونی

استفاده از سای‌فای و اضافه کردن کرانه‌ها برای متغیرها

من می‌توانم با اضافه کردن برخی برآوردها برای متغیرهای خود مشکل را کمی دقیق‌تر کنم. برای مثال به یاد می‌آورم که آرد بیشتر از ۳۰۰ گرم نبود، و زمانی که ۱۰۰ گرم کره داشتم، توانستم کیک درست کنم. من حدس‌های معقولی برای بقیه متغیرها می‌زنم.

# these are the bounds that help the solver arrive at a solution 

f_b = [0., 300.]  # limits for flour
e_b = [0., 200.]  # limits for eggs
b_b = [0., 100.]  # limits for butter
s_b = [0., 200.]  # limits for sugar

res_bounds = linprog(c, A_ub=A_ineq, b_ub=B_ineq, A_eq=A_eq, b_eq=B_eq, bounds=(f_b, e_b, b_b, s_b),  method='interior-point')

print('\nWITH BOUNDS')
print(res_bounds)

که نتایج زیر را باز می‌گرداند

WITH BOUNDS      
con: array([ 4.53132998e-09, -3.25428573e-12])      
fun: 249.9999999983819  
message: 'Optimization terminated successfully.'      
nit: 6    
slack: array([2.91322522e-09, 5.30261661e+01, 3.93856656e+01])  
status: 0  
success: True        
x: array([286.35949946, 163.64050053,  83.33333333, 166.66666667])

خروجی اکنون نشان می‌دهد

• آرد = ۲۸۶.۳۵ گرم
• تخم = ۱۶۳.۶۴ گرم
• کره = ۸۳.۳۳ گرم
• قند = ۱۶۶.۶۶ گرم

توجه داشته باشید که اکنون مقدار منفرد کره و شکر بالاتر از قبل است. این کاملا قابل‌قبول است زیرا برنامه خطی در تلاش است تا به طور همزمان تمام شرایط کدگذاری شده ما را برآورده کند، از جمله مرزهای تحمیل‌شده جدید ما برای هر یک از مواد. کل آن هنوز ۷۰۰ گرم است، کره هنوز نیمی از شکر است، کره هنوز کم‌تر از ۱۰۰ گرم است (حدی که ما تحمیل کردیم) ، آرد + کره هنوز هم بیشتر یا مساوی تخم‌مرغ + شکر است و غیره. این زیبایی یک برنامه خطی است. هدف آن برآورده کردن هر شرطی است که از آن عبور می‌کند، بنابراین بهینه ترین راه‌حل را برمی‌گرداند.

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

# Write a parser for results
def result_parser(res, var_list):
    solve_status = res.success
    if solve_status is True:
        solution_list = res.x
        soln = {var_list[i]: np.round(solution_list[i]) for i in range(len(var_list))}
    else:
        soln = []
    return soln

با خروجی

Result (no bounds):  
{'Flour': 303.0, 'Eggs': 147.0, 'Butter': 83.0, 'Sugar': 167.0}
Result (with bounds):  
{'Flour': 286.0, 'Eggs': 164.0, 'Butter': 83.0, 'Sugar': 167.0}

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

در پایتون کتابخانه‌های زیادی وجود دارند ( cvxopt , pulp , cvxpy , ecos  و غیره) که اساسا با حل‌کننده‌های برنامه‌ریزی خطی خودشان می‌آیند یا به عنوان پوشش اطراف حل‌کننده‌های برنامه‌ریزی خطی دیگر عمل می‌کنند. بنابراین می توان بسته به مساله موجود ترکیب حل‌کننده-پوشش‌دهنده را انتخاب کرد.

در زیر همان مساله مشابه (ماتریس‌ها و معادلات) با استفاده از کتابخانه cvxopt و با یک حل‌کننده glpk پیاده‌سازی شده است. تفاوت اصلی در اینجا این است که باید معادلات را در چارچوب ماتریس خود cvxopt تعریف کرد. توجه داشته باشید که cvxopt نسبتا انعطاف‌پذیر است و به فرد این امکان را می‌دهد تا از تعدادی از حل‌کننده‌ها بسته به مساله استفاده کند. من هیچ حد و مرزی برای متغیرها در نظر نگرفتم.

# formulate problem in terms of GLPK/cvxopt
c, A_ineq, B_ineq, A_eq, B_eq = matrix(c), matrix(A_ineq).T, matrix(B_ineq), matrix(A_eq).T, matrix(B_eq)
# solve the problem
status, solution = glpk.ilp(c, A_ineq, B_ineq, A_eq, B_eq)
if status=='optimal':
    print('solution found')
    print(solution)
else: 
    print(status)

که خروجی زیر را تولید می‌کند

solution found 
[ 2.67e+02] 
[ 1.83e+02] 
[ 8.33e+01] 
[ 1.67e+02]

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

بعد چی؟

اخیرا از برنامه‌نویسی خطی برای حل یک مساله منطقی استفاده کردم که فکر می‌کردم شبیه به برنامه‌نویسی منطقی محدودیت همزمان است. به بیان ساده‌تر، این مشکلی بود که از من می‌خواست تا «منطق همزمان» را اجرا کنم. من در مقاله بعدی خود در مورد آخرین مشکلی بحث خواهم کرد که نیاز به فرمول‌بندی مساله خطی کمی پیچیده‌تری دارد که در آن باید متغیرهای دودویی را معرفی کنیم. این مساله به طور موثر مساله را به یک مساله خطی عدد صحیح مختلط یا MILP تبدیل می‌کند.

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