
منتشرشده در: وبسایت درباره علم داده به تاریخ ۵ آپریل ۲۰۲۰
لینک منبع: Solving your first linear program in Python
شما ممکن است اصطلاح «برنامهریزی خطی» را در جایی از علم داده یا تحقیق به کار برده باشید. من سعی خواهم کرد که توضیح دهم که چیست و چگونه میتوان یک برنامه خطی را در پایتون پیادهسازی کرد.
یک برنامه خطی یک راهحل بهینه برای یک مساله پیدا میکند که در آن متغیرها در معرض روابط خطی متعددی هستند. علاوه بر این، مساله میتواند مستلزم آن باشد که یک شرط خاص را به حداکثر رسانده یا به حداقل برساند، برای مثال هزینه یک محصول را به حداقل برساند یا سود را به حداکثر برساند.
مثال مورد بحث اغلب برنامههای خطی، مثال فروشنده دورهگرد است. با شروع از زادگاهش، یک فروشنده باید تمام شهرهای یک منطقه را سفر کند اما به منظور به حداقل رساندن هزینههای سفر باید کوتاهترین مسیر ممکن را انتخاب کند که از هر شهر میگذرد و در زادگاهش به پایان میرسد. به طور کلی بهترین مسیر ممکن مسیری است که تنها یکبار از هر شهر میگذرد در نتیجه شبیه یک حلقه بسته است (شروع و پایان در شهر زادگاه).
من شخصا برنامههای خطی را در بسیاری از کاربردها بهکار بردهام.
صحبت خودمونی: به ریاضیات دبیرستان، معادلات خطی و حل معادلات خطی همزمان فکر کنید. اساسا ایده همین است، اما یک شرط اضافی روی متغیرهایی که باید به حداقل یا حداکثر رسانده شوند به آن اضافه کنید.
گفتگوی فنی: یک برنامه خطی یک تابع هدف (یا تابع هزینه) را بهینهسازی میکند که در آن مجموعهای از تعادلهای خطی (و نابرابریها) باید برآورده شوند.
من تمام این موارد را با یک مثال واقعی نشان خواهم داد.
من باید کیکی با چهار ماده اولیه شامل آرد، تخممرغ، کره و شکر درست کنم. با این حال، من فقط قسمتهایی از دستورالعمل را همانطور که در زیر ذکر میشود به یاد دارم.
آیا می توان مقادیر بهینه هر یک از موارد را از اطلاعات بالا بدست آورد؟
پاسخ مثبت است. این همان چیزی است که یک برنامه خطی برای انجام آن طراحی شدهاست.
ما میتوانیم هر یک از متغیرها را به صورت زیر تعریف کنیم:
سپس میتوانیم هر یک از شرایط را به شکل زیر بنویسیم:

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

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

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

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

توجه داشته باشید که ما از ترانهاده (سوپراسکریپت T) ماتریس c استفاده میکنیم تا بتوانیم آن را با ماتریس راهحل X ضرب کنیم.
حالا میتوانیم کدنویسی این مساله را در پایتون آغاز کنیم.
تنظیمات پایتون من
استفاده از سایپای
سایپای در پایتون قابلیتهای برنامهنویسی خطی پایه را ارایه میدهد. برای اجرای برنامه بالا با استفاده از سایپای، باید همه ماتریسها را براساس آن تعریف کنیم. در زیر یک مثال عملی از معادلات بالا آورده شدهاست که من با استفاده از بهینهسازی کتابخانه سایپای انجام دادم.
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 تبدیل میکند.
این متن با استفاده از ربات ترجمه مقالات دیتاساینس ترجمه شده و به صورت محدود مورد بازبینی انسانی قرار گرفته است.در نتیجه میتواند دارای برخی اشکالات ترجمه باشد.