Karma Tamsayılı Programlama: Hesaplamalı Karar Vermeye Yönelik Bir Kılavuz

Yöneylem araştırması, optimal kararlar vermek için bilgisayarları kullanma bilimi, yazılımın birçok alanında kullanılmış ve uygulanmıştır. Birkaç örnek vermek gerekirse, lojistik şirketleri bunu A noktasından B noktasına gitmek için en uygun rotayı belirlemek için, enerji şirketleri bunu enerji üretim çizelgelerini belirlemek için ve imalat şirketleri fabrikaları için en uygun personel modellerini bulmak için kullanıyor.

Bugün, varsayımsal bir problemin üzerinden geçerek yöneylem araştırmasının gücünü keşfedeceğiz. Spesifik olarak, varsayımsal bir fabrika için en uygun personel düzenini belirlemek için karma tamsayılı programlamayı (MIP) kullanacağız.

Yöneylem Araştırması Algoritmaları

Örnek problemimize dalmadan önce, yöneylem araştırmasındaki bazı temel kavramları gözden geçirmek ve bugün kullanacağımız bazı araçları anlamak faydalı olacaktır.

Doğrusal Programlama Algoritmaları

Doğrusal programlama, amaç ve kısıtlamaların bir doğrusal denklem sistemi olarak ifade edildiği bir matematiksel modelde en iyi sonucu belirlemek için kullanılan bir yöneylem araştırması tekniğidir. Örnek bir doğrusal programlama modeli şöyle görünebilir:

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

Çok basit örneğimizde, a = 2 ve b = 3 olmak üzere optimal sonucun 5 olduğunu görebiliriz. Bu oldukça önemsiz bir örnek olsa da, muhtemelen binlerce değişken ve yüzlerce kısıtlama kullanan bir doğrusal programlama modeli hayal edebilirsiniz. .

İyi bir örnek, sözde kodda aşağıdaki gibi bir şeyle karşılaşabileceğiniz bir yatırım portföyü sorunu olabilir:

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

Elle veya deneme yanılma yoluyla çözülmesi oldukça karmaşık ve zor olurdu. Yöneylem araştırması yazılımı, bu sorunları hızlı bir şekilde çözmek için çeşitli algoritmalar kullanacaktır. Altta yatan algoritmalarla ilgileniyorsanız, burada simpleks yöntemini ve burada iç nokta yöntemini öğrenmenizi öneririm.

Tamsayılı Programlama Algoritmaları

Tamsayılı programlama, değişkenlerin bir kısmının veya tamamının tamsayı değerleri olması için ek bir pay ile doğrusal programlama gibidir. Bu ilk başta büyük bir gelişme gibi görünmese de, yalnızca doğrusal programlama kullanarak çözülmemiş olabilecek birçok sorunu çözmemize olanak tanır.

Böyle bir problem, bize atanmış değerlere ve ağırlıklara sahip bir dizi eşyanın verildiği ve sırt çantamıza sığdırabileceğimiz en yüksek değerli eşya kombinasyonunu bulmamızın istendiği sırt çantası problemidir. Doğrusal bir programlama modeli bunu çözemez çünkü sırt çantanıza bir eşya koyup koyamayacağınız fikrini ifade etmenin bir yolu yoktur, ancak bir eşyanın bir kısmını sırt çantanıza koyamazsınız - her değişken süreklidir. değişken!

Örnek bir sırt çantası sorunu aşağıdaki parametrelere sahip olabilir:

Ve MIP modeli şöyle görünecek:

 Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

Bu durumda optimal çözüm a=0, b=1, c=0, d=1'dir ve toplam öğenin değeri 17'dir.

Bugün çözeceğimiz problem aynı zamanda tamsayılı programlama gerektirecektir, çünkü bir fabrikadaki bir çalışan bir vardiya için programlanabilir veya planlanamaz—basitlik adına, bir çalışanı bu fabrikada bir vardiyanın 2/3'ü için programlayamazsınız.

Tamsayılı programlamayı mümkün kılmak için çeşitli matematiksel algoritmalar kullanılır. Altta yatan algoritmalarla ilgileniyorsanız, burada kesme düzlemleri algoritmasını ve dal-sınır algoritmasını incelemenizi öneririm.

Örnek Problem: Zamanlama

Sorun Açıklaması

Bugün, bir fabrikaya personel alma sorununu inceleyeceğiz. Fabrika yönetimi olarak işçilik maliyetlerini en aza indirmek isteyeceğiz, ancak üretim talebini karşılamak için her vardiya için yeterli kapsamı sağlamak istiyoruz.

Aşağıdaki personel talepleriyle beş vardiyamız olduğunu varsayalım:

Ve, aşağıdaki işçilerimiz olduğunu varsayalım:

Sorunu basit tutmak için, bir an için mevcudiyet ve maliyetin tek endişe olduğunu varsayalım.

Araçlarımız

Bugünün sorunu için, CBC adlı bir açık kaynak dal-kesme yazılımı parçası kullanacağız. Python için popüler bir yöneylem araştırması modelleme kitaplığı olan PuLP kullanarak bu yazılımla arayüz oluşturacağız. Bununla ilgili bilgileri burada bulabilirsiniz.

PuLP, MIP modellerini çok Pythonic bir tarzda oluşturmamızı sağlar ve mevcut Python koduyla güzel bir şekilde bütünleşir. En popüler veri işleme ve analiz araçlarından bazıları Python'da yazıldığından ve çoğu ticari yöneylem araştırma sistemi optimizasyondan önce ve sonra kapsamlı veri işleme gerektirdiğinden bu çok kullanışlıdır.

PuLP'nin sadeliğini ve zarafetini göstermek için, daha önce PuLP'de çözülen sırt çantası problemi:

 import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack a = pl.LpVariable("a", 0, 1, pl.LpInteger) b = pl.LpVariable("b", 0, 1, pl.LpInteger) c = pl.LpVariable("c", 0, 1, pl.LpInteger) d = pl.LpVariable("d", 0, 1, pl.LpInteger) # define the problem prob = pl.LpProblem("knapsack", pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print("a", pl.value(a)) print("b", pl.value(b)) print("c", pl.value(c)) print("d", pl.value(d))

Bunu çalıştırın ve çıktıyı almalısınız:

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

Şimdi zamanlama problemimize gelelim!

Çözümümüzü Kodlamak

Çözümümüzün kodlaması oldukça basittir. İlk olarak, verilerimizi tanımlamak isteyeceğiz:

 import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } }

Ardından, modeli tanımlamak isteyeceğiz:

 # define the model: we want to minimize the cost prob = pl.LpProblem("scheduling", pl.LpMinimize) # some model variables cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

Ve şimdi sadece çözmesini ve sonuçları yazdırmasını istiyoruz!

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))

Kodu çalıştırdıktan sonra aşağıdaki çıktıları görmelisiniz:

 Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

Zorluğu Biraz Arttırın: Ek Kısıtlamalar

Önceki model ilginç ve kullanışlı olsa da, karma tamsayılı programlamanın gücünü tam olarak göstermiyor. Her vardiya için en ucuz x işçiyi bulmak için kolayca bir for döngüsü yazabiliriz, burada x bir vardiya için gereken işçi sayısıdır. Zorunlu bir şekilde çözülmesi zor olan bir sorunu çözmek için MIP'nin nasıl kullanılabileceğini göstermek için, birkaç ekstra kısıtlama eklersek ne olacağını inceleyelim.

Ek Kısıtlamalar

Yeni çalışma düzenlemeleri nedeniyle hiçbir işçinin 2 vardiyadan fazla görevlendirilemeyeceğini varsayalım. Artan işi hesaba katmak için, her vardiya için vardiya başına 40 $ oranında 10 Dothraki işçisi tedarik edecek olan Dothraki Personel Grubu'nun yardımını aldık.

Ek olarak, fabrikamızın dışında devam eden bazı kişiler arası çatışmalar nedeniyle Cersei ve Jaime'nin Daenerys veya Jon ile birlikte herhangi bir vardiyada çalışamadıklarını varsayalım. Ek olarak, Jaime ve Cersei birlikte herhangi bir vardiyada çalışamazlar. Son olarak, özellikle karmaşık kişiler arası ilişkilere sahip olan Arya, Jaime, Cersei veya Melisandre ile aynı vardiyada çalışamaz.

Bu iki yeni kısıtlamanın ve kaynağın eklenmesi, sorunu hiçbir şekilde zorunlu yollarla çözülemez hale getirmez, ancak bir işçiyi belirli bir vardiyaya planlamanın fırsat maliyetlerini hesaba katmak zorunda kalacağından çözümü daha da zorlaştırır.

Çözüm

Ancak karma tamsayılı programlama ile çok daha kolaydır. Sadece kodumuzu şu şekilde değiştirmemiz gerekiyor:

Yasak listesini ve bazı kısıtlamaları tanımlayın:

 ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Yasaklama ve maksimum kaydırma kısıtlamalarını uygulamak için değişkenleri doldurun:

 for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

Dothraki değişkenlerini ekleyin:

 for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

Ayrıca, hesaplama kaydırma ve yasaklama gereksinimleri için biraz değiştirilmiş bir döngüye ihtiyacımız olacak:

 # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

Ve son olarak, sonuçları yazdırmak için:

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var[1][0] for var in vars if var[0].varValue == 1], "dothrakis": dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

Ve gitmek için iyi olmalıyız. Kodu çalıştırın ve çıktıyı aşağıdaki gibi görmelisiniz:

 Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0

Ve işte orada, yasaklı işçi listesine saygı duyan, iş düzenlemelerini takip eden ve Dothraki işçileri akıllıca kullanan bir sonuç var.

Çözüm

Bugün, daha iyi kararlar almak için karma tamsayılı programlamayı kullanmayı keşfettik. Yöneylem araştırmasında kullanılan temel algoritmaları ve teknikleri tartıştık ve gerçek dünyada karma tamsayılı programlamanın nasıl kullanıldığını temsil eden örnek bir soruna baktık.

Umarım bu makale, yöneylem araştırması hakkında daha fazla bilgi edinmenize ilham vermiş ve bu teknolojinin projelerinize nasıl uygulanabileceği hakkında düşünmenizi sağlamıştır. Optimizasyon algoritmaları ve yöneylem araştırmasının heyecan verici dünyası söz konusu olduğunda, buzdağının yalnızca görünen yüzünü gerçekten gördük.

Bu yazı ile ilgili tüm kodları GitHub'da bulabilirsiniz. Daha fazla tartışmak isterseniz, yorumlarınızı aşağıda paylaşın!