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

Aşağıdaki bölümlerde Python için VEYA Araçları'nı kullanmaya başlamanıza yardımcı olacak bilgiler verilmiştir:

• Optimizasyon sorunu nedir?
• Python'da optimizasyon problemlerini çözme
• Diğer Python örnekleri
• Çözmek istediğiniz sorunun türünü belirleme

Optimizasyon sorunu nedir?

Optimizasyonun amacı, bir sorun için birçok olası çözüm arasından en iyi çözümü bulmaktır. (Bazen uygun bir çözüm bulmak sizi tatmin eder; VEYA araçları bunu da yapabilir.)

Tipik bir optimizasyon problemi aşağıda açıklanmıştır. Bir nakliye şirketinin, kamyon filosu kullanarak paketleri müşterilerine teslim ettiğini varsayalım. Şirketin her gün paketleri kamyonlara ataması ve ardından her kamyonun paketlerini teslim edeceği bir rota seçmesi gerekir. Paket ve rotalar için her olası atamanın, kamyonların toplam seyahat mesafesine ve diğer muhtemel faktörlere bağlı olarak bir maliyeti vardır. Sorun, en düşük maliyetli paket ve rota atamalarını seçmektir.

Tüm optimizasyon problemlerinde olduğu gibi bu sorun da aşağıdaki öğeleri içerir:

• 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 nesne işlevi 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 bir değer olabilir.)

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

  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 problemlerini çözme

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

Doğrusal optimizasyon örneği

En eski ve en çok 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 programlama) alanıdır. Aşağıda, bu tür bir soruna ilişkin basit bir örnek verilmiştir.

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

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

Bu örnekteki amaç fonksiyonu 3x + y'dir. Hem amaç fonksiyonu hem de kısıtlar doğrusal ifadelerle verilir. Bu nedenle, problem doğrusaldır.

Sorunun çözümündeki 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ımlayın,
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ı ayrıntılı bir şekilde açıklanmaktadır.

Not: Python programının tamamı ve koşulmasına ilişkin adımlar bölümün sonunda verilmiştir.

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

• Gerekli kitaplıkları içe aktarın.

  from ortools.init.python import init
  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:
      print("Could not create solver GLOP")
      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_var = solver.NumVar(0, 1, "x")
  y_var = 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:

  infinity = solver.infinity()
  # Create a linear constraint, x + y <= 2.
  constraint = solver.Constraint(-infinity, 2, "ct")
  constraint.SetCoefficient(x_var, 1)
  constraint.SetCoefficient(y_var, 1)
  
  print("Number of constraints =", solver.NumConstraints())

  SetCoefficient yöntemi, kısıtlama 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_var, 3)
  objective.SetCoefficient(y_var, 1)
  objective.SetMaximization()

  SetMaximization yöntemi, bunun bir maksimizasyon problemi olduğunu bildirir.
• Çözücüyü çağırın ve sonuçları görüntüleyin.

  print(f"Solving with {solver.SolverVersion()}")
  result_status = solver.Solve()
  print(f"Status: {result_status}")
  if result_status != pywraplp.Solver.OPTIMAL:
      print("The problem does not have an optimal solution!")
      if result_status == pywraplp.Solver.FEASIBLE:
          print("A potentially suboptimal solution was found")
      else:
          print("The solver could not solve the problem.")
          return
  
  print("Solution:")
  print("Objective value =", objective.Value())
  print("x =", x_var.solution_value())
  print("y =", y_var.solution_value())

Programı tamamlayın

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

from ortools.init.python import init
from ortools.linear_solver import pywraplp


def main():
    print("Google OR-Tools version:", init.OrToolsVersion.version_string())

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

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

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

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

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

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

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

    print(f"Status: {result_status}")
    if result_status != pywraplp.Solver.OPTIMAL:
        print("The problem does not have an optimal solution!")
        if result_status == pywraplp.Solver.FEASIBLE:
            print("A potentially suboptimal solution was found")
        else:
            print("The solver could not solve the problem.")
            return

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

    print("Advanced usage:")
    print(f"Problem solved in {solver.wall_time():d} milliseconds")
    print(f"Problem solved in {solver.iterations():d} iterations")


if __name__ == "__main__":
    init.CppBridge.init_logging("basic_example.py")
    cpp_flags = init.CppFlags()
    cpp_flags.stderrthreshold = True
    cpp_flags.log_prefix = False
    init.CppBridge.set_flags(cpp_flags)
    main()

Programın çalıştırılması

Yukarıdaki programı şu şekilde yürütebilirsiniz:

1. Yukarıdaki kodu kopyalayıp yeni bir dosyaya yapıştırın ve program.py olarak kaydedin.
2. Bir komut penceresi açın ve program.py dosyasını kaydettiğiniz dizine geçin. Komut istemine şu komutu girin:

   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 problem türünü belirleme

Dünyada birçok farklı türde optimizasyon sorunu vardır. Her sorun türü için en uygun çözümü bulmaya yönelik farklı yaklaşımlar ve algoritmalar vardır.

Bir optimizasyon problemini çözmek üzere program yazmaya başlamadan önce, ne tür bir sorunla uğraş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ılavuzdaki, her bir sorun türünün nasıl çözüleceğini açıklayan bölümlerin bağlantıları yer almaktadır.

• Doğrusal optimizasyon
• Kısıtlama optimizasyonu
• Karma tam sayı optimizasyonu
• Devretme
• Planlama
• Paketleme
• Yönlendirme
• Ağ akışları

Doğrusal optimizasyon

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

Bu tür sorunlar için OR 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 birkaç farklı kitaplığın sarmalayıcısı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. Her çalışan ve görev için, belirtilen çalışan belirli bir 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ıtlama optimizasyonu veya kısıt programlama (CP), sorunun rastgele kısıtlamalara göre modellenebileceği çok büyük bir aday grubu içinden uygulanabilir çözümleri tanımlar. CP, optimizasyon (en iyi çözüm bulma) yerine fizibiliteyi (uygun bir çözüm bulma) temel alır ve amaç işlevi yerine kısıtlar ve değişkenlere odaklanır. Bununla birlikte CP, optimizasyon problemlerini çözmek için kullanılabilir. Tüm uygulanabilir çö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, bir aracı grubunun (ör. çalışanlar veya makineler) bir görev kümesine atanmasını içerir. Bu durumda, her bir aracıyı belirli bir göreve atamanın sabit bir maliyeti vardır. Problem, 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 dizi nesneyi farklı kapasitelere sahip kapsayıcılara paketleme sorunudur. Amaç, container'ların kapasitesine bağlı olarak mümkün olduğunca çok nesneyi paketlemektir. Bunun özel bir durumu, yalnızca bir container'ın bulunduğu Sırt çantası sorunudur.

Kutu paketleme hakkında daha fazla bilgi

Scheduling (Zaman planlama)

Zaman çizelgesi problemleri, bir dizi görevi belirli zamanlarda gerçekleştirmek için kaynaklar atamayı içerir. Önemli bir örnek olarak, birden fazla işin birkaç makinede işlendiği iş atölyesi sorunu verilebilir. 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ını sağlayacak bir zaman çizelgesi atamaktır.

Planlama hakkında daha fazla bilgi

Yönlendirme

Rota sorunları, bir araç filosunun bir ağı geçmek için yönlendirilmiş bir grafikle tanımlanan en iyi 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. Bir diğeri de seyahat eden satış görevlisi sorunu.

Yönlendirme hakkında daha fazla bilgi

Ağ akışları

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

Maksimum akış probleminde, her bir yay boyunca aktarılabilecek bir maksimum kapasitesi vardır. 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ı atamaktır.

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