PuLP ile Doğrusal Optimizasyon 1
Bu yazımda python’da optimizasyon problemlerini modellemeye ve çözmeye yarayan PuLP kütüphanesinin genel kullanımından bahsedeceğim. 2 farklı optimizasyon problemi için de açık form ve kapalı formda PuLP ile problemi pythonda modellemeyi ve çözmeyi göstereceğim.
PuLP doğrusal optimizasyon problemlerini modellemeye yarayan bir python kütüphanesidir. Modelleri çözmek için varsayılan çözücü olarak CBC çözücüsünü kullanır. Ayrıca, CPLEX, COIN-OR, GUROBI ve XPRESS gibi ticari optimizasyon çözücülerini de kolayca çağırabilir. Bunların yanı sıra PuLP, MPS ve LP dosyaları oluşturmada da kullanılabilir.
Kurulum
pip aracılığıyla pip install pulp komutuyla kurulabilir. conda ile kurmak içinse conda install -c conda-forge pulp komutu kullanılabilir.
PuLP Metodları ve Fonksiyonları
Model Oluşturma
PuLP’ta yeni bir problem objesini LpProblem() fonksiyonuyla tanımlarız.
Örnek: Amaç fonksiyonu minimizasyon olan Problem1'i aşağıdaki ifadeyle tanımlayabiliriz:
model = LpProblem("Problem1", LpMinimize)Karar Değişkeni Tanımlama
PuLP’ta yeni değişkenler LpVariable() fonksiyonuyla tanımlanır. 0 ile 3 arasında reel değerler alan bir x değişkenini
x = LpVariable("x", 0, 3)ifadesiyle modele ekleyebiliriz.
Kısıt Oluşturma
Karar değişkenlerinden kısıtlar oluşturup modele eklemek içinse modelDeğişkeni += operatörü kullanılır.
model += x + y <= 2Amaç Fonksiyonu Oluşturma
Karar değişkenlerinden oluşturulan bir ifade, sağ taraf (rhs) içermiyorsa, modelin amaç fonksiyonu olur.
model += -4 * x + yModeli Çözme
Optimizasyon modelini varsayılan çözücü ile çözmek için solve() metodu kullanılır.
status = prob.solve()Çözümün Durumunu ve Değerlerini gösterme:
Problem çözümünün durumunu (optimal, infeasible) LpStatus[status] komutuyla görebiliriz.
LpStatus[status]
> 'Optimal'Karar değişkenlerinin aldığı değeriyse value() fonksiyonu veya karar değişkeninin .varValue niteliği ile görebiliriz.
1. Açık form modelleme örneği
A ürününün bir asortisi 6 parça, B ürününün bir asortisiyse 5 parça ürün içeriyor. Sevkiyat kısıtı gereği bir seferde 60 adetten fazla ürün mağazaya gönderilemiyor. Mağazada, A ürününün bir asortisi 10 birim alan, B ürününün bir asortisiyse 20 birim alan kaplıyor. Mağazada bu ürünler için ayrılan toplam sergileme alanı kapasitesiyse 150 birim. Bunların yanı sıra A ürününden depoda toplam 6 asorti var. A ürününün bir asortisi 5 tl, B ürününün bir asortisiyse 4.5 tl kar getiriyorsa, en yüksek karı veren asorti karışımını bulunuz.
Model:
Karar Değişkenleri:
Python Uygulaması:
from pulp import *# Problemi tanimlama
model = LpProblem("XYZ_Kar_En_İyileştirme", LpMaximize)# Karar degiskenleri
A = LpVariable('A', lowBound=0, upBound=None, cat='Integer')
B = LpVariable('B', lowBound=0, upBound=None, cat='Integer')# Amac Fonksiyonu
model += 5 * A + 4.5 * B# Kisitlar
model += 6 * A + 5 * A <= 60
model += 10 * A + 20 * B <= 150
model += A <= 6# Modeli Cozdurme
status = model.solve()print(LpStatus[status])
>Optimal#Cozum vektoru
print('A urununden gonderilecek asorti sayisi: {}'.format(A.varValue))
>A urununden gonderilecek asorti sayisi: 5.0print('B urununden gonderilecek asorti sayisi: {}'.format(B.varValue))
>B urununden gonderilecek asorti sayisi: 5.0
Dictionary Veri Yapısı
Dictionary, birçok dilde bulunan associative array’lerin python dilindeki ismidir. Dictionary, verileri depolamak ve erişmek için kullanılan bir veri yapısıdır. Üyelik kontrolündeki hızı yaklaşık olarak O(1) olduğu için, bu amaçla kullanılan en hızlı veri yapısıdır. PuLP kütüphanesinde, belirli kümeler üzerinde birçok karar değişkeni tanımlamak gerekli olduğunda, dictonary ve list comprehension yapıları birlikte kullanılabilir. PuLP, birden çok değişkeni tek seferde tanımlamak istediğimizde dictionary yapısını kullanıyor.
PuLP ile modellemede sık kullanılan iki örnekse
- Tek anahtarla (key) mağazaların taleplerini döndürme
- tuple’ın anahtar olarak kullanıldığı ve o karar değişkeni seçmede kullanılabilecek python ifadeleri aşağıdaki gibidir:
# key:value ikilileri
d = {'T100': 1800, 'T101':1200, 'T102':1100, 'T103':1000}display(d['T103'])
>1000# key olarak tuple kullanımı
x = {('K','0'):'XK0', ('K','1'):'XK1', ('K','2'):'XK2', ('K','3'):'XK3', ('I','0'):'XI0', ('I','1'):'XI1', ('I','2'):'XI2', ('I','3'):'XI3'}display(x[('K','0')])
>'XK0'
Liste Oluşturma (List Comprehension) Yapısı
List comprehension, python’da liste, tuple gibi bir iterable’ın elemanlarına belli bir operasyonu veya şartı uygulayarak liste oluşturmanın hızlı ve kısa bir yoludur. List comprehension kullanarak PuLP’ta amaç fonksiyonu ve kısıtlarımızı belli kümeler için kolayca oluşturabiliriz.
List comprehension’ın pulp ile modellemede işe yarayacağı durumlar için:
- 1'den 5'e kadar tam sayıların karesinden liste oluşturma
- Bir dictionary’den değerleri alıp, bir liste oluşturan
iki farklı örneği aşağıdaki gibidir:
print([i ** 2 for i in [1,2,3,4,5]])
> [1, 4, 9, 16, 25]print([d[i] for i in ['T100', 'T101', 'T102', 'T103']])
> [1800, 1200, 1100, 1000]
2.Ulaştırma problemi / Transportation Problem
Ulaştırma Problemi, birçok şirketin karşılaştığı ve bir ürünün, belli üretim/depolama noktalarından belli tüketim/talep noktalarına en uygun biçimde gönderilmesini ele alan temel bir optimizasyon problemidir. Problemin çözümünde tedarik ve talep kısıtlarının da sağlanıyor olması gereklidir.
Örnek:
L şirketi önümüzdeki ay, 2 bölge deposundan, 4 mağazasına yaptığı dağıtım için en ekonomik çözümü aramaktadır. Bölge depoları Konya ve İstanbulda yer almaktır. Bölge depolarından mağazalarına bir birim ürün gönderme maliyetleri tablo 1'deki gibidir:
Mağazaların talepleriyse tablo2'de verilmiştir,
L şirketi için mağazaların taleplerini karşılayan en ucuz çözümü bulunuz.
Model:
python uygulaması:
# model parametreleri
stores = ['T100', 'T101', 'T102', 'T103']
store_demand = [1800, 1200, 1100, 1000]
demand = dict(zip(stores, store_demand))costs = {('Konya', 'T100'): 232,
('Konya', 'T101'): 230,
('Konya', 'T102'): 212,
('Konya', 'T103'): 280,
('Istanbul', 'T100'): 211,
('Istanbul', 'T101'): 240,
('Istanbul', 'T102'): 232,
('Istanbul', 'T103'): 300}warehouse = ['Istanbul', 'Konya']# karar degiskenleri
XK0 = LpVariable('XK0', lowBound=0, cat='Integer')
XK1 = LpVariable('XK1', lowBound=0, cat='Integer')
XK2 = LpVariable('XK2', lowBound=0, cat='Integer')
XK3 = LpVariable('XK3', lowBound=0, cat='Integer')
XI0 = LpVariable('XI0', lowBound=0, cat='Integer')
XI1 = LpVariable('XI1', lowBound=0, cat='Integer')
XI2 = LpVariable('XI2', lowBound=0, cat='Integer')
XI3 = LpVariable('XI3', lowBound=0, cat='Integer')x = {('Konya', 'T100'): XK0,
('Konya', 'T101'): XK1,
('Konya', 'T102'): XK2,
('Konya', 'T103'): XK3,
('Istanbul', 'T100'): XI0,
('Istanbul', 'T101'): XI1,
('Istanbul', 'T102'): XI2,
('Istanbul', 'T103'): XI3}# Modeli Tanımlama
model2 = LpProblem("Minimize Transportation Costs", LpMinimize)# Hedef Fonksiyonu
model2 += lpSum([costs[(w, s)] * x[(w, s)] for s in stores for w in warehouse])# Kısıtlar, her magaza icin talep karsilanmali
for s in stores:
model2 += lpSum([x[(w, s)] for w in warehouse]) == demand[s]# modeli cozdurme
print(model2.solve())
> 1# en iyi cozumdeki sonuclar
print("Send from Istanbul to T100 {} of products".format(XI0.varValue))
> Send from Istanbul to T100 1800.0 of products# Hedef fonksiyonunun optimal degeri
print("Optimal Total Cost {} TL".format(value(model2.objective)))
> Optimal Total Cost 1169000.0 TL
3. LpVariable.dicts kullanımı ve Çözüm Vektörü
Modelde, belli kümeler üzerinde karar değişkenlerini kapalı formda tanımlamak için LpVariable.dicts metodunu kullanabiliriz. Çözüm vektörüne ulaşmak içinse model.variables() metodunu çağırıp, karar değişkenlerinin optimal çözümdeki değerlerine ulaşabiliriz.
# model parametreleri
warehouse = ['Istanbul', 'Konya']
stores = ['T100', 'T101', 'T102', 'T103']
store_demand = [1800, 1200, 1100, 1000]demand = dict(zip(stores, store_demand))costs = {('Konya', 'T100'): 232,
('Konya', 'T101'): 230,
('Konya', 'T102'): 212,
('Konya', 'T103'): 280,
('Istanbul', 'T100'): 211,
('Istanbul', 'T101'): 240,
('Istanbul', 'T102'): 232,
('Istanbul', 'T103'): 300}# karar degiskenleri
index = [(w, s) for w in warehouse for s in stores]
x = LpVariable.dicts('num_of_shipments', index, lowBound=0, cat='Integer')# Modeli Tanımlama
model3 = LpProblem("Minimize Transportation Costs", LpMinimize)# Hedef Fonksiyonu
model3 += lpSum([costs[(w, s)] * x[(w, s)] for s in stores for w in warehouse])# Kısıtlar, her magaza icin talep karsilanmali
for s in stores:
model2 += lpSum([x[(w, s)] for w in warehouse]) == demand[s]# # modeli cozdurme
model3.solve()
> 1# Çözümün Durumu
print(LpStatus[model3.status])
> Optimal# Çözüm Vektörü
for v in model3.variables():
print(v.name, "=", v.varValue)> num_of_shipments_('Istanbul',_'T100') = 0.0
> num_of_shipments_('Istanbul',_'T101') = 0.0
> num_of_shipments_('Istanbul',_'T102') = 0.0
> num_of_shipments_('Istanbul',_'T103') = 0.0
> num_of_shipments_('Konya',_'T100') = 0.0
> num_of_shipments_('Konya',_'T101') = 0.0
> num_of_shipments_('Konya',_'T102') = 0.0
> num_of_shipments_('Konya',_'T103') = 0.0
Kullanılan kodları https://github.com/orkunberk/pulp adresinden klonlayabilirsiniz.
Bu yazı dizisine başlamam için bana hem fikir hem de ilham veren Şükrü İmre ve Sabri Suyunu’ya en içten teşekkürlerimi sunuyorum.