Python İçin VEYA Araçlarını Kullanmaya Başlama

Aşağıdaki bölümlerde Python için OR-Araçları'nı kullanmaya başlayabilirsiniz:

Optimizasyon problemi nedir?

Optimizasyonun amacı, bir sorun için mümkün olan çok sayıda çözüm arasından en iyi çözümü bulmaktır. (Bazen uygun bir çözüm bulmaktan memnun olursunuz; VEYA araçları bunu da yapabilir.)

Tipik bir optimizasyon problemi aşağıda verilmiştir. Bir nakliye şirketinin, kamyon filosu kullanarak müşterilerine paketleri teslim ettiğini varsayalım. Şirket her gün paketleri kamyonlara atamalı ve ardından her kamyonun paketlerini teslim edeceği rotayı seçmelidir. Olası her paket ve rota ataması, kamyonların toplam seyahat mesafesine ve diğer muhtemelen başka faktörlere bağlı olarak belirli bir maliyete sahiptir. Sorun, en az maliyeti olan paket ve rota atamalarını seçmektir.

Tüm optimizasyon problemlerinde olduğu gibi bu sorunda da aşağıdaki unsurlar bulunur:

  • Hedef: Optimize etmek istediğiniz miktar. Yukarıdaki örnekte amaç maliyeti en aza indirmektir. Optimizasyon problemi oluşturmak için olası herhangi bir çözüm için hedefin değerini hesaplayan bir fonksiyon tanımlamanız gerekir. Buna hedef işlev denir. Yukarıdaki örnekte amaç işlevi, paket ve rota atamalarının toplam maliyetini hesaplar.

    Optimum çözüm, hedef fonksiyonu değerinin en iyi olduğu çözümdür. ("En iyi", maksimum veya minimum olabilir.)

  • Kısıtlamalar: Sorunun belirli gereksinimlerine bağlı olarak olası çözüm grubu üzerindeki kısıtlamalar. Örneğin kargo şirketi belirli bir ağırlığın üzerindeki paketleri kamyonlara atayamazsa bu durum çözümlere bir kısıtlama getirir.

    Uygulanabilir çözüm, mutlaka optimum olmasa da, sorun için verilen tüm kısıtlamaları karşılayan bir çözümdür.

Bir optimizasyon sorununu çözmenin ilk adımı, hedefi ve kısıtlamaları belirlemektir.

Python'da optimizasyon problemleri çözme

Daha sonra, bir optimizasyon sorunu örneği vererek Python'da bu problemin nasıl oluşturulup çözüleceğini göstereceğiz.

Doğrusal optimizasyon örneği

En eski ve en yaygın kullanılan optimizasyon alanlarından biri, hedef fonksiyonu ve kısıtlamaların doğrusal ifadeler olarak yazılabileceği doğrusal optimizasyon veya doğrusal programlamadır. Aşağıda, bu tür bir problemin basit bir örneği verilmiştir.

3x + y değerini aşağıdaki kısıtlamalara tabi olarak en üst düzeye çıkarın:

  1. 0 ≤ x ≤ 1
  2. 0 ≤ y ≤ 2
  3. x + y ≤ 2

Bu örnekteki hedef fonksiyon 3x + y'dir. Hem amaç fonksiyonu hem de kısıtlar doğrusal ifadelerle verilir. Bu da doğrusal bir problemdir.

Sorunu çözmeye yönelik ana adımlar

Her dilde sorun oluşturma ve çözme temel adımları aynıdır:

  1. Gerekli kitaplıkları içe aktarın,
  2. Çözücüyü tanımlayın.
  3. Değişkenleri oluşturun,
  4. Kısıtlamaları tanımlayın,
  5. Hedef fonksiyonunu tanımlama,
  6. Çözücüyü çağırın ve
  7. Sonuçları görüntüleyin.

Python programı

Bu bölümde, sorunu kuran ve çözen bir Python programı açıklanmaktadır.

İzleyeceğiniz adımlar aşağıda açıklanmıştır:

  • Gerekli kitaplıkları içe aktarın. 
    from ortools.linear_solver import pywraplp
  • Çözücüyü tanımlayın. 
    # Create the linear solver with the GLOP backend.
solver = pywraplp.Solver.CreateSolver("GLOP")
if not solver:
    return
    pywraplp, temel C++ çözücü için bir Python sarmalayıcıdır. "GLOP" bağımsız değişkeni, VEYA araçları doğrusal çözücü olan GLOP'yi belirtir.
  • Değişkenleri oluşturun. 
    # Create the variables x and y.
x = solver.NumVar(0, 1, "x")
y = solver.NumVar(0, 2, "y")

print("Number of variables =", solver.NumVariables())
  • Kısıtlamaları tanımlayın. İlk iki kısıtlama, 0 ≤ x ≤ 1 ve 0 ≤ y ≤ 2, değişkenlerin tanımlarına göre zaten belirlenmiştir. Aşağıdaki kod x + y ≤ 2 kısıtlamasını tanımlar: 
    # Create a linear constraint, 0 <= x + y <= 2.
ct = solver.Constraint(0, 2, "ct")
ct.SetCoefficient(x, 1)
ct.SetCoefficient(y, 1)

print("Number of constraints =", solver.NumConstraints())
    SetCoefficient yöntemi, kısıtlamanın ifadesindeki x ve y katsayılarını belirler.
  • Hedef işlevini tanımlama. 
    # Create the objective function, 3 * x + y.
objective = solver.Objective()
objective.SetCoefficient(x, 3)
objective.SetCoefficient(y, 1)
objective.SetMaximization()
    SetMaximization yöntemi, bunun bir maksimizasyon problemi olduğunu belirtir.
  • Çözücüyü çağırıp sonuçları gösterin. 
    print(f"Solving with {solver.SolverVersion()}")
solver.Solve()
print("Solution:")
print("Objective value =", objective.Value())
print("x =", x.solution_value())
print("y =", y.solution_value())

Programı tamamlayın

Programın tamamı aşağıda gösterilmektedir.

from ortools.linear_solver import pywraplp


def main():
    # Create the linear solver with the GLOP backend.
    solver = pywraplp.Solver.CreateSolver("GLOP")
    if not solver:
        return

    # Create the variables x and y.
    x = solver.NumVar(0, 1, "x")
    y = solver.NumVar(0, 2, "y")

    print("Number of variables =", solver.NumVariables())

    # Create a linear constraint, 0 <= x + y <= 2.
    ct = solver.Constraint(0, 2, "ct")
    ct.SetCoefficient(x, 1)
    ct.SetCoefficient(y, 1)

    print("Number of constraints =", solver.NumConstraints())

    # Create the objective function, 3 * x + y.
    objective = solver.Objective()
    objective.SetCoefficient(x, 3)
    objective.SetCoefficient(y, 1)
    objective.SetMaximization()

    print(f"Solving with {solver.SolverVersion()}")
    solver.Solve()

    print("Solution:")
    print("Objective value =", objective.Value())
    print("x =", x.solution_value())
    print("y =", y.solution_value())


if __name__ == "__main__":
    main()

Programı yürütme

Yukarıdaki programı aşağıdaki şekilde yürütebilirsiniz:

  1. Yukarıdaki kodu kopyalayıp yeni dosyaya yapıştırın ve program.py adıyla kaydedin.
  2. Bir komut penceresi açın ve program.py dosyasını kaydettiğiniz dizine geçin. Komut istemine şunu yazın: 
    python relative/path/to/program.py
    Burada relative/path/to/, programı kaydettiğiniz dizine giden yoldur.

Program, hedef işlevini en üst düzeye çıkaran x ve y değerlerini döndürür:

Solution:
x =  1.0
y =  1.0

Diğer Python örnekleri

Çeşitli optimizasyon sorunlarının nasıl çözüleceğini gösteren daha fazla Python örneği için Örnekler bölümüne bakın.

Çözmek istediğiniz problemin türünü belirleme

Dünyada birçok farklı türde optimizasyon problemi vardır. Her sorun türü için optimum çözümü bulmak üzere farklı yaklaşımlar ve algoritmalar vardır.

Bir optimizasyon problemini çözmek için program yazmaya başlamadan önce, ne tür bir sorunla karşılaştığınızı belirlemeniz ve ardından uygun bir çözücü (en uygun çözümü bulmaya yönelik bir algoritma) seçmeniz gerekir.

Aşağıda, VEYA araçlarının çözdüğü sorun türlerine kısa bir genel bakışın yanı sıra bu kılavuzda her bir sorun türünün nasıl çözüleceğini açıklayan bölümlere yönlendiren bağlantılar bulunmaktadır.

Doğrusal optimizasyon

Önceki bölümde öğrendiğiniz gibi, doğrusal optimizasyon problemi, hedef işlevi ve kısıtlamaların değişkenlerdeki doğrusal ifadeler olduğu bir problemdir.

Bu tür sorunlar için VEYA Araçları'ndaki birincil çözücü, doğrusal optimizasyon çözücüdür. Bu çözücü, aslında üçüncü taraf kitaplıklar da dahil olmak üzere doğrusal ve karma tamsayı optimizasyonu için birçok farklı kitaplık için sarmalayıcıdır.

Doğrusal optimizasyon hakkında daha fazla bilgi

Karma tam sayı optimizasyonu

Karışık tam sayı optimizasyon problemi, değişkenlerin bazılarının veya tümünün tam sayı olmasını gerektiren bir problemdir. Örneğin, bir çalışan grubunun bir dizi göreve atanması gereken atama problemi verilebilir. Her çalışan ve görev için, belirli bir çalışan verilen göreve atanmışsa değeri 1, aksi halde 0 olan bir değişken tanımlarsınız. Bu durumda, değişkenler yalnızca 0 veya 1 değerlerini alabilir.

Karma tam sayı optimizasyonu hakkında daha fazla bilgi

Kısıtlama optimizasyonu

Kısıt optimizasyonu veya kısıt programlama (CP), sorunun rastgele kısıtlamalara göre modellendiği çok büyük bir çözüm grubundan uygun çözümleri tanımlar. CP, optimizasyon yerine (ideal çözüm bulma) uygulanabilirliğe (uygun çözüm bulma) dayanır ve amaç işlevi yerine kısıtlamalara ve değişkenlere odaklanır. Ancak CP, optimizasyon problemlerini çözmek için basitçe tüm uygun çözümler için hedef fonksiyonunun değerlerini karşılaştırarak kullanılabilir.

Kısıtlama optimizasyonu hakkında daha fazla bilgi

Ödev

Atama problemleri, her aracıyı belirli bir göreve atamanın sabit bir maliyeti olduğu bir görev grubuna bir aracı grubu (örneğin, çalışanlar veya makineler) atamayı içerir. Sorun, toplam maliyeti en düşük olan ödevi bulmaktır. Atama sorunları aslında ağ akışı sorunlarının özel bir durumudur.

Atama hakkında daha fazla bilgi

Paketleme

Kutu paketleme farklı boyutlardaki bir nesne grubunun farklı kapasitelere sahip kaplara paketlenmesi sorunudur. Amaç, container'ların kapasitesine bağlı olarak mümkün olduğunca çok nesneyi paketlemektir. Bunun özel bir örneği, içinde yalnızca bir container'ın bulunduğu Sırtma sorunudur.

Kutu paketleme hakkında daha fazla bilgi

Scheduling (Zaman planlama)

Zaman çizelgesi sorunları, bir dizi görevi belirli zamanlarda gerçekleştirmek için kaynaklar atamayı içerir. Önemli bir örnek, birden fazla işin birkaç makinede işlendiği iş atölyesi sorunudur. Her iş, belirli bir sırada gerçekleştirilmesi ve her görevin belirli bir makinede işlenmesi gereken bir görev dizisinden oluşur. Sorun, tüm işlerin mümkün olduğunca kısa bir zaman aralığı içinde tamamlanması için bir zaman çizelgesi atamaktır.

Planlama hakkında daha fazla bilgi

Yönlendirme

Yönlendirme problemleri, araç filolarının yönlendirilmiş bir grafikle tanımlanmış bir ağı geçmeleri için en uygun rotaları bulmayı içerir. Optimizasyon sorunu nedir? bölümünde açıklanan, teslimat kamyonlarına paket atama sorunu, yönlendirme sorunlarına bir örnektir. Diğer bir sorun da seyahat eden satış görevlisi sorunu.

Yönlendirme hakkında daha fazla bilgi

Ağ akışları

Birçok optimizasyon problemi, düğümler ve arasında yönlendirilmiş yaylardan oluşan yönlendirilmiş bir grafikle temsil edilebilir. Örneğin, ürünlerin bir demiryolu ağı üzerinden gönderildiği ulaşım sorunları, yayların demiryolu hatları ve düğümlerin dağıtım merkezi olduğu bir grafikle gösterilebilir.

Maksimum akış probleminde her bir yay, üzerinden aktarılabilecek bir maksimum kapasiteye sahiptir. Sorun, taşınan toplam miktarın mümkün olduğunca büyük olacağı şekilde her bir yay boyunca gönderilecek mal miktarının atanmasıdır.

Ağ akışları hakkında daha fazla bilgi