Tam sayılı programlama çalışma alanı
Küçük bir tam sayılı doğrusal programı kesin dal-sınır yöntemiyle çözün ve aramanın tüm düğümlerini görün. En iyi noktanın en iyi olduğu yalnızca arama ağacının tamamı incelendiğinde kanıtlanmış olarak bildirilir.
Programlar 4.000 karakter ve 40 satır, 8 değişken ve iki veya daha fazla değişken içeren 8 kısıtla sınırlıdır; düğüm sınırı 1 ile 5.000 arasındadır ve arama 3.000.000 kesin aritmetik adımından sonra da durur. Tüm hesaplamalar cihazınızda arka plan işçisinde en fazla 15 saniyede yapılır. JSON raporunu ve düğümlerin CSV dosyasını indirebilirsiniz. İlk satıra maximize veya minimize ile amaç fonksiyonunu yazın. Ardından her satıra bir kısıt girin. En fazla 4.000 karakter. Çalıştırmadan önce ayarları gözden geçirin.
Sonucunuz
Tam sayılı programlama çalışma alanı
- Amaç fonksiyonunu ilk satıra yazın; örneğin maximize 5x + 4y.
- Her satıra bir kısıt yazın; x, y >= 0 gibi sınırlar ve integer x veya binary z gibi isteğe bağlı satırlar ekleyin.
- Düğüm sınırını belirleyip aramayı çalıştırın.
- Durumu, mevcut en iyi çözümü, en iyi sınırı ve aralarındaki farkı inceleyin; ardından JSON raporunu veya düğümlerin CSV dosyasını indirin.
Bilmeniz gerekenler
Programlar 4.000 karakter ve 40 satır, 8 değişken ve iki veya daha fazla değişken içeren 8 kısıtla sınırlıdır; düğüm sınırı 1 ile 5.000 arasındadır ve arama 3.000.000 kesin aritmetik adımından sonra da durur. Tüm hesaplamalar cihazınızda arka plan işçisinde en fazla 15 saniyede yapılır. JSON raporunu ve düğümlerin CSV dosyasını indirebilirsiniz.
Dal-sınır yöntemi
Her düğüm doğrusal gevşetmeyi simpleks yöntemiyle kesin olarak çözer. Kesirli değerli bir tam sayı değişkeni x <= taban ve x >= tavan biçiminde iki dala ayrılır. Gevşetmesi olanaksız olan veya bulunan en iyi tam sayı noktasından daha iyi olamayacak düğümler elenir. Yöntem: Wolsey, Integer Programming, 2. baskı, 7. bölüm (2020).
Kanıtlanmış olmanın anlamı
Her düğüm çözüldüğünde veya kesin bir sınırla elendiğinde mevcut en iyi çözümün optimum olduğu ya da problemin olanaksız olduğu kanıtlanır. Arama önce düğüm sınırına veya adım bütçesine ulaşırsa mevcut çözüm yalnızca o ana kadar bulunan en iyi noktadır; rapor en iyi sınırı ve ikisi arasındaki farkı verir.
Girdi kuralları
Değişkenler varsayılan olarak tam sayıdır. integer x, y ile tam sayı olarak listelediklerinizin dışındaki değişkenler bu durumda sürekli kabul edilir. Tek değişkenli kısıtlar sınırlara dönüşür. Sınırsız bir gevşetme aramayı durdurur; çünkü tam sayılı program sınırsız veya olanaksız olabilir.