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

Java için VEYA Araçları'nı kullanmaya başlamanızı sağlayacak bölümler şunlardır:

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.

Java'da optimizasyon problemlerini çözme

Ardından, bir optimizasyon problemi örneği vererek bu problemin Java’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.

Java programı<

Bu bölümde, sorunu kuran ve çözen bir Java programı anlatılmıştır.

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

  • Gerekli kitaplıkları içe aktarın. 
    import com.google.ortools.Loader;
import com.google.ortools.init.OrToolsVersion;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
  • Çözücüyü tanımlayın. 
    // Create the linear solver with the GLOP backend.
MPSolver solver = MPSolver.createSolver("GLOP");
if (solver == null) {
  System.out.println("Could not create solver GLOP");
  return;
}
    MPSolver, doğrusal programlama veya karma tamsayı programlama problemlerini çözmek için kullanılan bir sarmalayıcıdır.
  • Değişkenleri oluşturun. 
    // Create the variables x and y.
MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
MPVariable y = solver.makeNumVar(0.0, 2.0, "y");

System.out.println("Number of variables = " + solver.numVariables());
  • Kısıtlamaları tanımlayın. İlk iki kısıtlama (0 &leq; x ≤ 1 ve 0 &leq; y ≤ 2) değişkenlerin tanımlarına göre zaten belirlenmiştir. Aşağıdaki kod x + y &leq; 2 kısıtlamasını tanımlar: 
    double infinity = Double.POSITIVE_INFINITY;
// Create a linear constraint, x + y <= 2.
MPConstraint ct = solver.makeConstraint(-infinity, 2.0, "ct");
ct.setCoefficient(x, 1);
ct.setCoefficient(y, 1);

System.out.println("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.
MPObjective objective = solver.objective();
objective.setCoefficient(x, 3);
objective.setCoefficient(y, 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. 
    System.out.println("Solving with " + solver.solverVersion());
final MPSolver.ResultStatus resultStatus = solver.solve();
System.out.println("Status: " + resultStatus);
if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
  System.out.println("The problem does not have an optimal solution!");
  if (resultStatus == MPSolver.ResultStatus.FEASIBLE) {
    System.out.println("A potentially suboptimal solution was found");
  } else {
    System.out.println("The solver could not solve the problem.");
    return;
  }
}

System.out.println("Solution:");
System.out.println("Objective value = " + objective.value());
System.out.println("x = " + x.solutionValue());
System.out.println("y = " + y.solutionValue());

Programı tamamlayın

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

package com.google.ortools.linearsolver.samples;

import com.google.ortools.Loader;
import com.google.ortools.init.OrToolsVersion;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Minimal Linear Programming example to showcase calling the solver. */
public final class BasicExample {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();

    System.out.println("Google OR-Tools version: " + OrToolsVersion.getVersionString());

    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");
    if (solver == null) {
      System.out.println("Could not create solver GLOP");
      return;
    }

    // Create the variables x and y.
    MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
    MPVariable y = solver.makeNumVar(0.0, 2.0, "y");

    System.out.println("Number of variables = " + solver.numVariables());

    double infinity = Double.POSITIVE_INFINITY;
    // Create a linear constraint, x + y <= 2.
    MPConstraint ct = solver.makeConstraint(-infinity, 2.0, "ct");
    ct.setCoefficient(x, 1);
    ct.setCoefficient(y, 1);

    System.out.println("Number of constraints = " + solver.numConstraints());

    // Create the objective function, 3 * x + y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 3);
    objective.setCoefficient(y, 1);
    objective.setMaximization();

    System.out.println("Solving with " + solver.solverVersion());
    final MPSolver.ResultStatus resultStatus = solver.solve();

    System.out.println("Status: " + resultStatus);
    if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
      System.out.println("The problem does not have an optimal solution!");
      if (resultStatus == MPSolver.ResultStatus.FEASIBLE) {
        System.out.println("A potentially suboptimal solution was found");
      } else {
        System.out.println("The solver could not solve the problem.");
        return;
      }
    }

    System.out.println("Solution:");
    System.out.println("Objective value = " + objective.value());
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());

    System.out.println("Advanced usage:");
    System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
    System.out.println("Problem solved in " + solver.iterations() + " iterations");
  }

  private BasicExample() {}
}

Java programını çalıştırma

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

  1. Yukarıdaki kodu kopyalayıp yeni bir dosyaya yapıştırın ve my_program.java olarak kaydedin.
  2. OR-Tools'u yüklediğiniz dizinin en üst düzeyinde bir komut penceresi açın ve şunu girin: 
    make run SOURCE=relative/path/to/my_program.java
    Burada relative/path/to/, programı kaydettiğiniz dizinin yoludur.

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

Programı çalıştırmadan derlemek için şunu girin:

make build SOURCE=relative/path/to/my_program.java

Diğer Java örnekleri

Çeşitli optimizasyon sorunlarının nasıl çözüleceğini gösteren daha fazla Java ö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

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