.Net için VEYA araçlarını kullanmaya başlayın

Aşağıdaki bölümler, .Net için VEYA Araçları'nı kullanmaya başlamanızı sağlayacaktı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.

.Net'te optimizasyon problemlerini çözme

Daha sonra, bir optimizasyon sorunu örneği vererek bu sorunun .Net'te 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.

.Net programı

Bu bölümde, sorunu kuran ve çözen bir .Net programı ele alınmaktadır.

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

  • Gerekli kitaplıkları içe aktarın. 
    using System;
using Google.OrTools.Init;
using Google.OrTools.LinearSolver;
  • Çözücüyü tanımlayın. 
    // Create the linear solver with the GLOP backend.
Solver solver = Solver.CreateSolver("GLOP");
if (solver is null)
{
    Console.WriteLine("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.
Variable x = solver.MakeNumVar(0.0, 1.0, "x");
Variable y = solver.MakeNumVar(0.0, 2.0, "y");

Console.WriteLine("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, x + y <= 2.
Constraint constraint = solver.MakeConstraint(double.NegativeInfinity, 2.0, "constraint");
constraint.SetCoefficient(x, 1);
constraint.SetCoefficient(y, 1);

Console.WriteLine("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 objective = solver.Objective();
objective.SetCoefficient(x, 3);
objective.SetCoefficient(y, 1);
objective.SetMaximization();
    setMaximization yöntemi, bunu bir maksimizasyon problemi olarak tanımlar. (Temel C++ yöntemi SetMaximization şeklindedir.
  • Çözücüyü çağırın ve sonuçları görüntüleyin. 
    Console.WriteLine("Solving with " + solver.SolverVersion());
Solver.ResultStatus resultStatus = solver.Solve();
Console.WriteLine("Status: " + resultStatus);
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
    Console.WriteLine("The problem does not have an optimal solution!");
    if (resultStatus == Solver.ResultStatus.FEASIBLE)
    {
        Console.WriteLine("A potentially suboptimal solution was found");
    }
    else
    {
        Console.WriteLine("The solver could not solve the problem.");
        return;
    }
}

Console.WriteLine("Solution:");
Console.WriteLine("Objective value = " + solver.Objective().Value());
Console.WriteLine("x = " + x.SolutionValue());
Console.WriteLine("y = " + y.SolutionValue());

Programı tamamlayın

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

using System;
using Google.OrTools.Init;
using Google.OrTools.LinearSolver;

public class BasicExample
{
    static void Main()
    {
        Console.WriteLine("Google.OrTools version: " + OrToolsVersion.VersionString());

        // Create the linear solver with the GLOP backend.
        Solver solver = Solver.CreateSolver("GLOP");
        if (solver is null)
        {
            Console.WriteLine("Could not create solver GLOP");
            return;
        }

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

        Console.WriteLine("Number of variables = " + solver.NumVariables());

        // Create a linear constraint, x + y <= 2.
        Constraint constraint = solver.MakeConstraint(double.NegativeInfinity, 2.0, "constraint");
        constraint.SetCoefficient(x, 1);
        constraint.SetCoefficient(y, 1);

        Console.WriteLine("Number of constraints = " + solver.NumConstraints());

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

        Console.WriteLine("Solving with " + solver.SolverVersion());
        Solver.ResultStatus resultStatus = solver.Solve();

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

        Console.WriteLine("Solution:");
        Console.WriteLine("Objective value = " + solver.Objective().Value());
        Console.WriteLine("x = " + x.SolutionValue());
        Console.WriteLine("y = " + y.SolutionValue());

        Console.WriteLine("Advanced usage:");
        Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds");
        Console.WriteLine("Problem solved in " + solver.Iterations() + " iterations");
    }
}

.Net 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 BasicExample.cs olarak kaydedin. oluşturduğunuz dizinin examples/dotnet alt dizininde görürsünüz.
  2. Aynı dizinde yeni bir dosya (BasicExample.csproj) oluşturun ve şu kodu ekleyin: 
    <Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <LangVersion>7.3</LangVersion>
    <TargetFramework>netcoreapp3.1</TargetFramework>
    <EnableDefaultItems>false</EnableDefaultItems>
    <!-- see https://github.com/dotnet/docs/issues/12237 -->
    <RollForward>LatestMajor</RollForward>
    <RestoreSources>../../../temp_dotnet/packages;$(RestoreSources);https://api.nuget.org/v3/index.json</RestoreSources>
    <AssemblyName>Google.OrTools.BasicExample</AssemblyName>
    <IsPackable>true</IsPackable>
  </PropertyGroup>

  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
    <DebugType>full</DebugType>
    <Optimize>true</Optimize>
    <GenerateTailCalls>true</GenerateTailCalls>
  </PropertyGroup>

  <ItemGroup>
    <Compile Include="BasicExample.cs" />
    <PackageReference Include="Google.OrTools" Version="9.1.*" />
  </ItemGroup>
</Project>
  3. OR-Tools'u yüklediğiniz dizinin en üst düzeyinde bir komut penceresi açın ve şu komutu girin: 
    make run SOURCE=examples/dotnet/BasicExample.cs

.Net programlarını examples/dotnet/ dizininden farklı bir dizinde kaydedip çalıştırmak mümkündür ancak bu işlem biraz daha zordur: csproj dosyasının yukarıda gösterilen satırını değiştirerek packages dizinine gidebileceğiniz

../../../packages;$(RestoreSources);https://api.nuget.org/v3/index.json
yolunu değiştirmeniz gerekir.

En kolay çözüm, .Net programlarınızı examples/dotnet/ dizinine yerleştirmektir.

Program, hedef fonksiyonunu 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/SimpleProgram.cs

Programda değişiklik yaparsanız, programı yukarıda gösterildiği gibi yeniden derlemeniz gerekir.

Diğer .Net örnekleri

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