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

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

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.

Java'da optimizasyon problemi çözme

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

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.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");
    MPSolver, doğrusal programlama veya karma tam sayı programlama problemlerini çözmek için 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: 
    // Create a linear constraint, 0 <= x + y <= 2.
MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
ct.setCoefficient(x, 1);
ct.setCoefficient(y, 1);

System.out.println("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.
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ıp sonuçları gösterin. 
    solver.solve();
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.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();
    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");

    // 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());

    // Create a linear constraint, 0 <= x + y <= 2.
    MPConstraint ct = solver.makeConstraint(0.0, 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();

    solver.solve();

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

  private BasicExample() {}
}

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

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

  1. Yukarıdaki kodu kopyalayıp yeni 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 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

Programı çalıştırmadan yalnızca 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 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