Doğrusal programlama - Linear programming

İki değişkenli ve altı eşitsizliği olan basit bir doğrusal programın resimli gösterimi. Uygun çözümler kümesi sarı renkle gösterilmiştir ve 2 boyutlu bir politop olan bir çokgen oluşturur . Doğrusal maliyet işlevi, kırmızı çizgi ve okla temsil edilir: Kırmızı çizgi, maliyet işlevinin bir düzey kümesidir ve ok, optimize ettiğimiz yönü gösterir.

Üç değişkenli bir problemin kapalı uygulanabilir bölgesi bir dışbükey çokyüzlüdür . Amaç fonksiyonunun sabit bir değerini veren yüzeyler düzlemlerdir (gösterilmemiştir). Doğrusal programlama problemi, çokyüzlü üzerinde, düzlem üzerinde olabilecek en yüksek değere sahip bir nokta bulmaktır.

Doğrusal programlama ( LP , doğrusal optimizasyon olarak da adlandırılır ), gereksinimleri doğrusal ilişkilerle temsil edilen bir matematiksel modelde en iyi sonucu (maksimum kar veya en düşük maliyet gibi) elde etmek için bir yöntemdir . Doğrusal programlama, matematiksel programlamanın özel bir durumudur ( matematiksel optimizasyon olarak da bilinir ).

Daha resmi, doğrusal programlama tekniğidir optimizasyon a doğrusal amaç fonksiyonu için, konunun lineer eşitlik ve doğrusal eşitsizlik kısıtları . Bu mümkün bölge a, dışbükey politop olarak tanımlanan bir dizi, kesişme sonlu sayıda bir yarım boşluk doğrusal, aşağıdaki eşitsizlikle tanımlanan her biri. Amaç fonksiyonu, bu çokyüzlü üzerinde tanımlanan gerçek değerli bir afin (doğrusal) fonksiyondur . Doğrusal bir programlama algoritması , politopta , böyle bir nokta varsa, bu fonksiyonun en küçük (veya en büyük) değere sahip olduğu bir nokta bulur .

Doğrusal programlar ifade edilebilir sorunlardır kanonik formu olarak

${\displaystyle {\begin{hizalanmış}&{\text{Bir vektör bulun}}&&\mathbf {x} \\&{\text{maksimize eden}}&&\mathbf {c} ^{T}\mathbf {x } \\&{\text{tabii}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{ve}}&&\mathbf {x} \geq \mathbf {0} .\ bitiş{hizalı}}}$

Burada x'in bileşenleri belirlenecek değişkenlerdir, c ve b'ye vektörler verilir ( c'nin katsayılarının matris çarpımını oluşturmak amacıyla tek sıralı bir matris olarak kullanıldığını belirtmekle birlikte ) ve A verilen bir matristir. . Değeri maksimize edilecek veya minimize edilecek ( bu durumda) fonksiyona amaç fonksiyonu denir . A x  ≤  b ve x ≥ 0 eşitsizlikleri , amaç fonksiyonunun optimize edileceği bir dışbükey politopu belirten kısıtlamalardır . Bu bağlamda, aynı boyutlara sahip olduklarında iki vektör karşılaştırılabilir . Birincideki her giriş, ikincideki karşılık gelen girişten küçük veya ona eşitse, o zaman birinci vektörün ikinci vektörden küçük veya ona eşit olduğu söylenebilir. ${\displaystyle \mathbf {c} ^{T}}$${\displaystyle \mathbf {x} \mapsto \mathbf {c} ^{T}\mathbf {x} }$

Doğrusal programlama çeşitli çalışma alanlarına uygulanabilir. Matematikte yaygın olarak kullanılır ve daha az ölçüde işletme, ekonomi ve bazı mühendislik problemlerinde kullanılır. Doğrusal programlama modellerini kullanan endüstriler arasında ulaşım, enerji, telekomünikasyon ve imalat bulunmaktadır. Planlama , yönlendirme , çizelgeleme , atama ve tasarımda çeşitli problem türlerinin modellenmesinde yararlı olduğu kanıtlanmıştır .

Tarih

Leonid Kantoroviç

John von Neumann

Tarih kadarıyla gibi en az geri doğrusal eşitsizlikler sisteminin çözülmesi sorunu Fourier 1827 yılında bunları çözmek için bir yöntem yayınlanan ve kime sonra yöntemi, Fourier-Motzkin eleme adlandırılır.

1939'da, Sovyet matematikçi ve ekonomist Leonid Kantorovich tarafından genel doğrusal programlama problemine eşdeğer bir doğrusal programlama formülasyonu verildi ve o da onu çözmek için bir yöntem önerdi. Dünya Savaşı sırasında ordunun maliyetlerini azaltmak ve düşmana verilen kayıpları artırmak için harcamaları ve getirileri planlamak için geliştirdiği bir yoldur . Kantorovich'in çalışması başlangıçta SSCB'de ihmal edildi . Hollandalı-Amerikalı ekonomist TC Koopmans , Kantorovich ile aşağı yukarı aynı zamanlarda, klasik ekonomik sorunları doğrusal programlar olarak formüle etti. Kantorovich ve Koopmans daha sonra 1975 Nobel ekonomi ödülünü paylaştılar . 1941'de Frank Lauren Hitchcock da taşıma problemlerini doğrusal programlar olarak formüle etti ve daha sonraki simpleks yöntemine çok benzer bir çözüm verdi . Hitchcock 1957'de öldü ve Nobel ödülü ölümünden sonra verilmedi.

1946–1947 yılları arasında George B. Dantzig , ABD Hava Kuvvetleri'ndeki planlama problemlerinde kullanılmak üzere bağımsız olarak genel doğrusal programlama formülasyonu geliştirdi. 1947'de Dantzig , çoğu durumda doğrusal programlama problemini ilk kez verimli bir şekilde ele alan simpleks yöntemini de icat etti . Dantzig , kendi simpleks yöntemini tartışmak için John von Neumann ile bir toplantı düzenlediğinde , Neumann oyun teorisinde üzerinde çalıştığı problemin eşdeğer olduğunu fark ederek hemen dualite teorisini tahmin etti . Dantzig, 5 Ocak 1948'de yayınlanmamış bir raporda "Lineer Eşitsizlikler Üzerine Bir Teorem" adlı resmi kanıt sağladı. Dantzig'in çalışması 1951'de halka açıldı. Savaş sonrası yıllarda, birçok endüstri bunu günlük planlarında uyguladı.

Dantzig'in orijinal örneği, 70 kişinin 70 işe en iyi atanmasını bulmaktı. En iyi atamayı seçmek için tüm permütasyonları test etmek için gereken hesaplama gücü çok büyük; olası konfigürasyonların sayısı , gözlemlenebilir evrendeki parçacıkların sayısını aşıyor . Ancak, problemi doğrusal bir program olarak kurarak ve simpleks algoritmasını uygulayarak optimum çözümü bulmak sadece bir dakika sürer . Doğrusal programlamanın arkasındaki teori, kontrol edilmesi gereken olası çözümlerin sayısını büyük ölçüde azaltır.

Lineer programlama probleminin ilk olarak 1979'da Leonid Khachiyan tarafından polinom zamanında çözülebilir olduğu gösterildi , ancak bu alanda daha büyük bir teorik ve pratik atılım, 1984'te Narendra Karmarkar'ın lineer programlama problemlerini çözmek için yeni bir iç nokta yöntemini tanıtmasıyla geldi .

kullanır

Doğrusal programlama, çeşitli nedenlerle yaygın olarak kullanılan bir optimizasyon alanıdır. Yöneylem araştırmasındaki birçok pratik problem, doğrusal programlama problemleri olarak ifade edilebilir. Şebeke akış problemleri ve çoklu mal akış problemleri gibi bazı özel lineer programlama durumları, çözümleri için özel algoritmalar üzerinde çok fazla araştırma üretecek kadar önemli kabul edilir. Diğer optimizasyon problemleri için bir dizi algoritma, LP problemlerini alt problemler olarak çözerek çalışır. Tarihsel olarak, doğrusal programlamadan gelen fikirler, dualite, ayrıştırma ve dışbükeyliğin önemi ve genellemeleri gibi optimizasyon teorisinin birçok merkezi kavramına ilham vermiştir . Benzer şekilde, doğrusal programlama, mikroekonominin erken oluşumunda yoğun bir şekilde kullanılmıştır ve şu anda planlama, üretim, ulaşım, teknoloji ve diğer konular gibi şirket yönetiminde kullanılmaktadır. Modern yönetim konuları sürekli değişse de, çoğu şirket sınırlı kaynaklarla kârlarını maksimize etmek ve maliyetleri minimuma indirmek ister. Google, YouTube videolarını dengelemek için doğrusal programlama kullanır. Bu nedenle birçok konu doğrusal programlama problemleri olarak nitelendirilebilir.

Standart biçim

Standart form , bir doğrusal programlama problemini tanımlamanın olağan ve en sezgisel şeklidir. Aşağıdaki üç bölümden oluşur:

• Bir doğrusal bir fonksiyonu maksimize edilmesi

Örneğin ${\displaystyle f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}}$

• Aşağıdaki formun problem kısıtlamaları

Örneğin

${\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{ 2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix}}}$

• Negatif olmayan değişkenler

Örneğin

${\displaystyle {\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix}}}$

Sorun genellikle matris biçiminde ifade edilir ve ardından şu hale gelir:

${\displaystyle \max\{\,\mathbf {c} ^{\mathrm {T} }\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}}$

Minimizasyon problemleri, alternatif formlar üzerindeki kısıtlamaları olan problemler ve negatif değişkenleri içeren problemler gibi diğer formlar her zaman standart formda eşdeğer bir probleme yeniden yazılabilir.

Örnek

Bir çiftçinin, ya buğday ya da arpa ya da ikisinin bir kombinasyonu ile ekilecek L km ² gibi bir çiftlik arazisi olduğunu varsayalım . Çiftçinin sınırlı miktarda gübresi, F kilogramı ve pestisit, P kilogramı vardır. Her kilometrekare buğday, F ₁ kilogram gübre ve P ₁ kilogram pestisit gerektirirken, her kilometrekare arpa F ₂ kilogram gübre ve P ₂ kilogram pestisit gerektirir. Buğdayın kilometrekare satış fiyatı S ₁ ve arpanın satış fiyatı S _{2 olsun} . Buğday ve arpa ekilen arazinin alanını sırasıyla x ₁ ve x _{2 ile gösterirsek} , x ₁ ve x ₂ için optimal değerler seçilerek kâr maksimize edilebilir . Bu problem standart formda aşağıdaki doğrusal programlama problemi ile ifade edilebilir:

Büyüt: ${\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}$		(geliri maksimize edin – gelir "hedef fonksiyondur")
Şunlara tabidir:	${\displaystyle x_{1}+x_{2}\leq L}$	(toplam alan sınırı)
	${\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F}$	(gübre limiti)
	${\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P}$	(pestisit limiti)
	${\displaystyle x_{1}\geq 0,x_{2}\geq 0}$	(negatif bir alan ekemez).

Matris formunda bu olur:

maksimize etmek ${\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}$

tabi ${\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{ 2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end {bmatrix}}\geq {\başlangıç{bmatrix}0\\0\end{bmatrix}}.}$

Artırılmış form (gevşek form)

Simpleks algoritmasının yaygın biçimini uygulamak için doğrusal programlama problemleri artırılmış bir forma dönüştürülebilir . Bu form, eşitsizlikleri kısıtlamalardaki eşitliklerle değiştirmek için negatif olmayan gevşek değişkenleri tanıtır . Problemler daha sonra aşağıdaki blok matris formunda yazılabilir :

Büyüt :${\görüntüleme stili z}$

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\ \mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}}$

${\displaystyle \mathbf {x} \geq 0,\mathbf {s} \geq 0}$

yeni tanıtılan gevşek değişkenler nerede , karar değişkenleri ve maksimize edilecek değişkendir. ${\displaystyle \mathbf {s} }$${\displaystyle \mathbf {x} }$${\görüntüleme stili z}$

Örnek

Yukarıdaki örnek, aşağıdaki genişletilmiş forma dönüştürülmüştür:

Büyüt: ${\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}$		(amaç fonksiyonu)
tabi:	${\displaystyle x_{1}+x_{2}+x_{3}=L}$	(artırılmış kısıtlama)
	${\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}+x_{4}=F}$	(artırılmış kısıtlama)
	${\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}+x_{5}=P}$	(artırılmış kısıtlama)
	${\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0.}$

burada bu örnekte kullanılmayan alanı, kullanılmayan gübre miktarını ve kullanılmayan pestisit miktarını temsil eden (negatif olmayan) gevşek değişkenlerdir. ${\displaystyle x_{3},x_{4},x_{5}}$

Matris formunda bu olur:

Büyüt :${\görüntüleme stili z}$

${\displaystyle {\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\ bitiş{bmatrix}}{\begin{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={ \begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{ 4}\\x_{5}\end{bmatrix}}\geq 0.}$

ikilik

İlkel problem olarak adlandırılan her doğrusal programlama problemi, birincil problemin optimal değerine bir üst sınır sağlayan ikili bir probleme dönüştürülebilir . Matris formunda, asal problemi şu şekilde ifade edebiliriz :

A x ≤ b , x ≥ 0'a tabi olarak c ^T x'i maksimize edin ;

karşılık gelen simetrik ikili problemle,

A ^T y ≥ c , y ≥ 0'a bağlı olarak b ^T y'yi en aza indirin .

Alternatif bir birincil formülasyon:

A x ≤ b'ye bağlı olarak c ^T x'i maksimize edin ;

karşılık gelen asimetrik ikili problemle,

A ^T y = c , y ≥ 0'a tabi olarak b ^T y'yi en aza indirin .

Dualite teorisi için temel olan iki fikir vardır. Birincisi, (simetrik ikili için) ikili doğrusal bir programın ikilisinin orijinal asli doğrusal program olmasıdır. Ek olarak, doğrusal bir program için her uygun çözüm, dualinin amaç fonksiyonunun optimal değerine bir sınır verir. Zayıf ikilik teoremi herhangi bir mümkün çözeltisi çifte amaç fonksiyon değeri herhangi bir uygun çözüme Primal amaç fonksiyon değerine eşit veya daha yüksek olmasını ifade eder. Güçlü ikilik ilkel optimal bir çözüm olup olmadığını teoremi durumları, bu X ^* , daha sonra çift de optimal bir çözüm vardır Y ^* ve C ^{, T} x ^* = b ^T y ^* .

Doğrusal bir program ayrıca sınırsız veya olanaksız olabilir. Dualite teorisi bize, eğer ilksel sınırsız ise, dualin zayıf dualite teoremi tarafından mümkün olmadığını söyler. Benzer şekilde, ikili sınırsız ise, o zaman asli mümkün olamaz. Bununla birlikte, hem dual hem de primalin olanaksız olması mümkündür. Ayrıntılar ve birkaç örnek için ikili doğrusal programa bakın .

Varyasyonlar

Kaplama/paketleme ikilikleri

Bir kapsayan LP , formun doğrusal bir programıdır:

Küçült: b ^T y ,

tabi: A ^T y ≥ c , y ≥ 0 ,

öyle ki A matrisi ve b ve c vektörleri negatif değildir.

Bir kaplama LP'sinin ikilisi , aşağıdaki formun doğrusal bir programı olan bir paketleme LP'sidir :

Maksimize Et: c ^T x ,

tabi: A x ≤ b , x ≥ 0 ,

öyle ki A matrisi ve b ve c vektörleri negatif değildir.

Örnekler

LP'lerin kapsanması ve paketlenmesi genellikle bir kombinatoryal problemin doğrusal programlama gevşemesi olarak ortaya çıkar ve yaklaşım algoritmalarının çalışmasında önemlidir . Örneğin, küme paketleme probleminin LP gevşemeleri , bağımsız küme problemi ve eşleştirme problemi , paketleme LP'leridir. Küme örtüsü probleminin LP gevşemeleri , tepe örtüsü problemi ve baskın küme problemi de LP'leri kapsar.

Bir grafiğin kesirli renklendirmesini bulmak , kaplama LP'sinin başka bir örneğidir. Bu durumda, grafiğin her köşesi için bir kısıtlama ve grafiğin her bağımsız kümesi için bir değişken vardır .

tamamlayıcı gevşeklik

Tamamlayıcı gevşeklik teoremi kullanılarak sadece primal için optimal bir çözüm bilindiğinde dual için optimal bir çözüm elde etmek mümkündür. Teorem şunları belirtir:

x  = ( x ₁ ,  x ₂ , ... ,  x _n )'nin ilkel olarak mümkün olduğunu ve y  = ( y ₁ ,  y ₂ , ... ,  y _m )'nin ikili olarak mümkün olduğunu varsayalım . ( w ₁ ,  w ₂ , ...,  w _m ) karşılık gelen asal bolluk değişkenlerini ve ( z ₁ ,  z ₂ , ... ,  z _n ) karşılık gelen ikili bolluk değişkenlerini göstersin. O zaman x ve y , ancak ve ancak şu durumlarda ilgili problemleri için optimaldir:

• x _j z _j  = 0, için j  = 1, 2, ... ,  n , ve
• w _ben y _ben  = 0, için i  = 1, 2, ... ,  m .

Dolayısıyla, asalın i -inci gevşek değişkeni sıfır değilse, o zaman ikilinin i -inci değişkeni sıfıra eşittir. Benzer şekilde, ikilinin j -inci gevşek değişkeni sıfır değilse, o zaman asalın j -inci değişkeni sıfıra eşittir.

Optimallik için bu gerekli koşul, oldukça basit bir ekonomik ilkeyi taşır. Standart formda (maksimize ederken), kısıtlanmış bir birincil kaynakta bolluk varsa (yani "artıklar" varsa), o kaynağın ek miktarlarının hiçbir değeri olmamalıdır. Benzer şekilde, ikili (gölge) fiyat negatif olmama kısıtlaması şartında gevşeklik varsa, yani fiyat sıfır değilse, o zaman kıt arzlar ("artık" yok) olmalıdır.

teori

Optimal çözümlerin varlığı

Geometrik olarak, doğrusal kısıtlamalar , bir dışbükey çokyüzlü olan uygun bölgeyi tanımlar . Bir doğrusal bir fonksiyonu a, dışbükey işlevi her ifade eder, yerel minimum a, genel minimum ; Benzer şekilde, bir doğrusal fonksiyonu olan içbükey işlev her ifade eder, lokal maksimum a, global maksimum .

İki nedenden dolayı optimal bir çözümün mevcut olması gerekmez. İlk olarak, eğer kısıtlamalar tutarsızsa, o zaman uygun bir çözüm yoktur: Örneğin, x  ≥ 2 ve x  ≤ 1 kısıtlamaları birlikte karşılanamaz; bu durumda LP'nin uygulanamaz olduğunu söylüyoruz . İkincisi, politop , amaç fonksiyonunun gradyanı yönünde sınırsız olduğunda (burada amaç fonksiyonunun gradyanı, amaç fonksiyonunun katsayılarının vektörüdür), o zaman hiçbir optimal değer elde edilmez, çünkü bunu yapmak her zaman mümkündür. amaç fonksiyonunun herhangi bir sonlu değerinden daha iyidir.

Çokyüzlülerin optimal köşeleri (ve ışınları)

Aksi takdirde, eğer uygun bir çözüm varsa ve kısıt kümesi sınırlandırılmışsa, optimum değere her zaman kısıt kümesinin sınırında, dışbükey fonksiyonlar için maksimum prensiple (alternatif olarak, içbükey fonksiyonlar için minimum prensiple ) ulaşılır. fonksiyonlar hem dışbükey hem de içbükeydir. Ancak, bazı problemlerin belirgin optimal çözümleri vardır; örneğin, bir doğrusal eşitsizlikler sistemine uygun bir çözüm bulma sorunu, amaç işlevinin sıfır işlevi olduğu bir doğrusal programlama sorunudur (yani, her yerde sıfır değerini alan sabit işlev). Bu fizibilite problemi için, amaç fonksiyonu için sıfır fonksiyonu ile, eğer iki farklı çözüm varsa, o zaman çözümlerin her dışbükey kombinasyonu bir çözümdür.

Politopun köşeleri aynı zamanda temel uygun çözümler olarak da adlandırılır . Bu isim seçiminin nedeni aşağıdaki gibidir. Let d değişkenlerin sayısını belirtir. O halde lineer eşitsizliklerin temel teoremi (uygulanabilir problemler için) , LP uygulanabilir bölgesinin her x ^* köşesi için , LP'den bir dizi d (veya daha az) eşitsizlik kısıtlaması olduğunu ima eder , öyle ki, bu d kısıtlamalarını şu şekilde ele aldığımızda eşitlikler, benzersiz çözüm x ^* . Böylece, LP çözümlerinin sürekliliği yerine tüm kısıtlamalar kümesinin (ayrık bir küme) belirli alt kümelerine bakarak bu köşeleri inceleyebiliriz. Bu ilke, doğrusal programları çözmek için tek yönlü algoritmanın temelini oluşturur .

algoritmalar

Doğrusal bir programlama probleminde, bir dizi doğrusal kısıtlama, bu değişkenler için olası değerlerin dışbükey bir uygulanabilir bölgesini üretir . İki değişkenli durumda bu bölge dışbükey basit çokgen şeklindedir .

Temel değişim algoritmaları

Dantzig'in Simpleks algoritması

Simpleks algoritması tarafından geliştirilen, George Dantzig 1947 yılında, çözer bir köşenin de uygun bir çözüm oluşturarak sorunları LP politop bir kadar amaç fonksiyonu değerleri olmayan azalan ile köşe noktalarına politop kenarlarında bir yol boyunca yürüyen sonra ve optimuma kesinlikle ulaşılır. Pek çok pratik problemde, " hızlanma " meydana gelir: birçok pivot, amaç fonksiyonunda herhangi bir artış olmadan yapılır. Nadir pratik problemlerde, tek yönlü algoritmanın olağan versiyonları aslında "döngü" yapabilir. Döngülerden kaçınmak için araştırmacılar yeni döner kurallar geliştirdiler.

Pratikte, simpleks algoritması oldukça verimlidir ve döngüye karşı belirli önlemler alınırsa global optimumu bulmayı garanti edebilir . Simpleks algoritmasının "rastgele" problemleri verimli bir şekilde, yani pratik problemler üzerindeki davranışına benzer şekilde, bir kübik sayıda adımda çözdüğü kanıtlanmıştır.

Bununla birlikte, simpleks algoritmasının en kötü durum davranışı zayıftır: Klee ve Minty, simpleks yönteminin problem boyutunda üstel birkaç adım attığı bir doğrusal programlama problemleri ailesi oluşturmuştur. Aslında, bir süredir doğrusal programlama probleminin polinom zamanında , yani karmaşıklık sınıfı P'de çözülebilir olup olmadığı bilinmiyordu .

çapraz algoritma

Dantzig'in tek yönlü algoritması gibi, çapraz çapraz algoritma da bazlar arasında dönen bir temel değişim algoritmasıdır. Bununla birlikte, çapraz geçiş algoritmasının fizibiliteyi sürdürmesi gerekmez, bunun yerine uygulanabilir bir temelden uygulanabilir olmayan bir temele dönebilir. Çapraz çapraz algoritma, doğrusal programlama için polinom zaman karmaşıklığına sahip değildir . Her iki algoritma da en kötü durumda Klee–Minty küpü olan D boyutundaki  (tehlikeli) bir küpün tüm 2 ^D köşelerini ziyaret eder .

İç nokta

Çokyüzlü bir kümede köşeler arasında kenarları geçerek optimal bir çözüm bulan simpleks algoritmasının aksine, iç nokta yöntemleri uygulanabilir bölgenin iç kısmından geçer.

Khachiyan'ı izleyen elipsoid algoritma

Bu, doğrusal programlama için şimdiye kadar bulunan ilk en kötü durumlu polinom zamanlı algoritmadır. n değişkenli ve L giriş bitlerinde kodlanabilen bir problemi çözmek için bu algoritma zamanında çalışır . Leonid Khachiyan , 1979 yılında elipsoid yönteminin tanıtılmasıyla uzun süredir devam eden bu karmaşıklık sorununu çözdü . Yakınsama analizinin (gerçek sayı) öncülleri vardır, özellikle Naum Z. Shor tarafından geliştirilen yinelemeli yöntemler ve Arkadi Nemirovski ve D. Yudin tarafından geliştirilen yaklaşım algoritmaları . ${\ Displaystyle O(n^{6}L)}$

Karmarkar'ın projektif algoritması

Khachiyan'ın algoritması, lineer programların polinom zamanlı çözülebilirliğini belirlemek için önemli bir öneme sahipti. Algoritma, hesaplamalı bir atılım değildi, çünkü simpleks yöntemi, özel olarak oluşturulmuş doğrusal program aileleri dışında tümü için daha verimlidir.

Bununla birlikte, Khachiyan'ın algoritması, doğrusal programlamada yeni araştırma hatlarına ilham verdi. 1984 yılında N. Karmarkar doğrusal programlama için projektif bir yöntem önerdi . Karmarkar'ın algoritması, Khachiyan'ın en kötü durum polinom sınırı (veren ) üzerinde geliştirildi. Karmarkar, algoritmasının pratik LP'de simpleks yönteminden çok daha hızlı olduğunu iddia etti; bu, iç nokta yöntemlerinde büyük ilgi uyandıran bir iddia. Karmarkar'ın keşfinden bu yana, birçok iç nokta yöntemi önerilmiş ve analiz edilmiştir. ${\ Displaystyle O(n^{3.5}L)}$

Vaidya'nın 87 algoritması

1987'de Vaidya, zamanda çalışan bir algoritma önerdi . ${\görüntüleme stili O(n^{3})}$

Vaidya'nın 89 algoritması

1989'da Vaidya, zamanda çalışan bir algoritma geliştirdi . Resmi olarak konuşursak, algoritma en kötü durumda aritmetik işlemleri alır , burada kısıtlama sayısı, değişken sayısı ve bit sayısıdır. ${\ Displaystyle O(n^{2.5})}$${\ Displaystyle O((n+d)^{1.5}nL)}$${\görüntüleme stili d}$${\görüntüleme stili n}$${\görüntüleme stili L}$

Girdi seyrekliği zaman algoritmaları

2015 yılında, Lee ve Sidford, sıfır olmayan öğelerin sayısını temsil eden zamanda çözülebileceğini ve en kötü durumda almaya devam ettiğini gösterdi. ${\displaystyle {\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)}$${\görüntüleme stili nnz(A)}$${\ Displaystyle O(n^{2.5}L)}$

Mevcut matris çarpma zaman algoritması

2019 yılında, Cohen, Lee ve Song için çalışma süresi geliştirilmiş zaman, üs olan matris çarpımı ve ikili üssüdür matris çarpımı . (kabaca) bir matrisi zaman içinde bir matrisle çarpabilecek en büyük sayı olarak tanımlanır . Lee, Song ve Zhang'ın bir takip çalışmasında, aynı sonucu farklı bir yöntemle yeniden üretiyorlar. Bu iki algoritma ne zaman ve ne zaman kalır . Nedeniyle Jiang, Song Weinstein ve Zhang için sonuç geliştirilmiş etmek . ${\displaystyle {\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)}$${\ Displaystyle \ omega }$${\görüntüleme stili \alfa }$${\görüntüleme stili \alfa }$${\görüntüleme stili n\kez n}$${\ Displaystyle n\times n^{\alpha }}$${\ Displaystyle O(n^{2})}$${\displaystyle {\tilde {O}}(n^{2+1/6}L)}$${\görüntüleme stili \omega =2}$${\görüntüleme stili \alfa =1}$${\displaystyle {\tilde {O}}(n^{2+1/6}L)}$${\displaystyle {\tilde {O}}(n^{2+1/18}L)}$

İç nokta yöntemleri ve simpleks algoritmalarının karşılaştırılması

Mevcut görüş, simpleks tabanlı yöntemlerin ve iç nokta yöntemlerinin iyi uygulamalarının etkinliklerinin, doğrusal programlamanın rutin uygulamaları için benzer olduğudur. Bununla birlikte, belirli LP problemleri türleri için, bir tür çözücü diğerinden daha iyi (bazen çok daha iyi) olabilir ve iç nokta yöntemleri ile simpleks tabanlı yöntemler tarafından üretilen çözümlerin yapısı, destekle önemli ölçüde farklı olabilir. aktif değişkenler kümesi, ikincisi için tipik olarak daha küçüktür.

Açık sorunlar ve son çalışmalar

Doğrusal programlama teorisinde, çözümü matematikte temel atılımları ve büyük ölçekli doğrusal programları çözme yeteneğimizde potansiyel olarak büyük ilerlemeleri temsil edecek olan birkaç açık problem vardır.

• LP, güçlü bir polinom-zaman algoritmasını kabul ediyor mu?
• LP, kesinlikle tamamlayıcı bir çözüm bulmak için güçlü bir polinom zamanlı algoritmayı kabul ediyor mu?
• LP, gerçek sayı (birim maliyet) hesaplama modelinde bir polinom zamanlı algoritmayı kabul ediyor mu?

Sorunların Bu yakından ilişkili seti aldığı atıflar Stephen Smale arasında olarak 18 büyük çözülmemiş sorunların 21. yüzyılın. Smale'nin sözleriyle, sorunun üçüncü versiyonu "doğrusal programlama teorisinin çözülmemiş ana problemidir." Elipsoid yöntemler ve iç nokta teknikleri gibi zayıf polinom zamanında doğrusal programlamayı çözmek için algoritmalar mevcut olsa da , kısıtlama sayısı ve değişken sayısında güçlü polinom zamanlı performansa izin veren hiçbir algoritma henüz bulunamadı. Bu tür algoritmaların geliştirilmesi, büyük teorik ilgi çekecek ve belki de büyük LP'lerin çözümünde pratik kazanımlara izin verecektir.

Hirsch varsayımı yakın zamanda daha yüksek boyutlar için reddedilmiş olsa da , hala aşağıdaki soruları açık bırakıyor.

• Polinom zamanlı tek yönlü değişkenlere yol açan pivot kurallar var mı?
• Tüm politopal grafikler polinomla sınırlı çapa sahip mi?

Bu sorular, performans analizi ve simpleks benzeri yöntemlerin geliştirilmesi ile ilgilidir. Simpleks algoritmasının üstel zamanlı teorik performansına rağmen pratikteki muazzam verimliliği, polinomda veya hatta güçlü polinom zamanında çalışan simpleks varyasyonlarının olabileceğini ima eder. Özellikle LP'nin güçlü polinom zamanında çözülüp çözülemeyeceğine karar verme yaklaşımı olarak, bu tür varyantların var olup olmadığını bilmek büyük pratik ve teorik öneme sahip olacaktır.

Simpleks algoritması ve varyantları, bir politopun kenarları boyunca tepe noktasından tepe noktasına hareket ederek doğrusal programlama problemlerini çözdükleri için bu şekilde adlandırılmış kenar takip algoritmaları ailesine girer. Bu, teorik performanslarının, LP politopu üzerindeki herhangi iki köşe arasındaki maksimum kenar sayısı ile sınırlı olduğu anlamına gelir. Sonuç olarak, politopal grafiklerin maksimum grafik-teorik çapını bilmek istiyoruz . Tüm politopların üstel çapa sahip olduğu kanıtlanmıştır. Hirsch varsayımının yakın zamanda çürütülmesi, herhangi bir politopun süperpolinom çapına sahip olup olmadığını kanıtlamanın ilk adımıdır. Eğer bu tür politoplar mevcutsa, polinom zamanında hiçbir kenar takip eden varyant çalışamaz. Politop çapı ile ilgili sorular bağımsız matematiksel ilgi alanına sahiptir.

Tek yönlü pivot yöntemleri, birincil (veya ikili) fizibiliteyi korur. Öte yandan, çapraz eksenli pivot yöntemleri (birincil veya ikili) fizibiliteyi korumaz - herhangi bir sırayla birincil uygulanabilir, ikili uygulanabilir veya ilk ve ikili mümkün olmayan temelleri ziyaret edebilirler. Bu türdeki pivot yöntemler 1970'lerden beri çalışılmaktadır. Esasen, bu yöntemler doğrusal programlama problemi altında düzenleme politopu üzerindeki en kısa pivot yolunu bulmaya çalışır . Politopal grafiklerin aksine, düzenleme politoplarının grafiklerinin küçük çapa sahip olduğu bilinmektedir, bu da genel politopların çapıyla ilgili soruları çözmeden güçlü polinom zamanlı çapraz eksen algoritması olasılığına izin verir.

Tamsayı bilinmeyenleri

Tüm bilinmeyen değişkenlerin tamsayı olması gerekiyorsa, problem tamsayılı programlama (IP) veya tamsayılı doğrusal programlama (ILP) problemi olarak adlandırılır. En kötü durumda verimli bir şekilde çözülebilen doğrusal programlamanın aksine, tamsayılı programlama problemleri birçok pratik durumda (sınırlı değişkenli olanlar) NP-zordur . 0–1 tamsayılı programlama veya ikili tamsayılı programlama (BIP), değişkenlerin (rastgele tamsayılar yerine) 0 veya 1 olması gereken tamsayılı programlamanın özel durumudur. Bu problem aynı zamanda NP-zor olarak sınıflandırılır ve aslında karar versiyonu Karp'ın 21 NP-tamamlanmış problemlerinden biriydi .

Bilinmeyen değişkenlerden yalnızca bazılarının tamsayı olması gerekiyorsa, soruna karma tamsayılı programlama (MIP) sorunu denir . Bunlar genellikle NP-zordur çünkü ILP programlarından bile daha geneldirler.

Bununla birlikte, etkin bir şekilde çözülebilen IP ve MIP problemlerinin bazı önemli alt sınıfları vardır, en önemlisi, kısıtlama matrisinin tamamen tek modüler olduğu ve kısıtlamaların sağ taraflarının tam sayılar olduğu veya - daha genel olarak - sistemin toplam ikili bütünlüğe sahip olduğu problemler. (TDI) özelliği.

Tamsayılı doğrusal programları çözmek için gelişmiş algoritmalar şunları içerir:

• kesme düzlemi yöntemi
• Şube ve bağlı
• Şube ve kesim
• Şube ve fiyat
• Eğer problemin ekstra bir yapısı varsa, gecikmeli kolon üretimi uygulamak mümkün olabilir .

Bu tür tamsayı programlama algoritmaları Padberg ve Beasley'de tartışılmıştır .

İntegral lineer programlar

Reel değişkenli bir lineer program, integral olan en az bir optimal çözüme sahipse integral olarak adlandırılır. Benzer şekilde, tüm sınırlı uygulanabilir amaç fonksiyonları c için lineer programın tamsayı koordinatları ile bir optimuma sahip olması durumunda , bir polihedronun integral olduğu söylenir . Edmonds ve Giles tarafından 1977'de gözlemlendiği gibi, her sınırlı uygulanabilir integral amaç fonksiyonu c için lineer programın optimal değeri bir tamsayıysa , polihedronun integral olduğu söylenebilir . ${\displaystyle P=\{x\mid Ax\geq 0\}}$${\displaystyle \{\max cx\mid x\in P\}}$${\görüntüleme stili x^{*}}$${\görüntüleme stili P}$${\displaystyle \{\max cx\mid x\in P\}}$

İntegral lineer programlar, bir problemin alternatif bir karakterizasyonunu sağladıklarından , kombinatoryal optimizasyonun çokyüzlü yönü açısından merkezi öneme sahiptir . Spesifik olarak, herhangi bir problem için, çözümlerin dışbükey gövdesi, bütünleşik bir çokyüzlüdür; eğer bu çokyüzlü güzel/kompakt bir açıklamaya sahipse, herhangi bir doğrusal amaç altında optimal uygulanabilir çözümü verimli bir şekilde bulabiliriz. Tersine, eğer bir doğrusal programlama gevşemesinin integral olduğunu kanıtlayabilirsek, bu, uygulanabilir (integral) çözümlerin dışbükey gövdesinin istenen açıklamasıdır.

Terminoloji literatürde tutarlı değildir, bu nedenle aşağıdaki iki kavramı ayırt etmeye özen gösterilmelidir,

• önceki bölümde açıklanan bir tamsayılı doğrusal programda, değişkenler tamsayı olmaya zorlanır ve bu problem genel olarak NP-zordur,
• Bu bölümde açıklanan bir integral lineer programda, değişkenler tamsayı olarak sınırlandırılmaz, bunun yerine sürekli problemin her zaman bir integral optimal değerine sahip olduğu ( c'nin integral olduğu varsayılarak) bir şekilde kanıtlanmıştır ve bu optimal değer verimli bir şekilde bulunabilir. tüm polinom boyutlu lineer programlar polinom zamanında çözülebilir.

Bir polihedronun integral olduğunu kanıtlamanın yaygın bir yolu, onun tamamen unimodüler olduğunu göstermektir . Tamsayı ayrıştırma özelliği ve toplam ikili bütünlük dahil olmak üzere başka genel yöntemler de vardır . Diğer iyi bilinen integral LP'ler, eşleşen politop, kafes çokyüzlüler, alt modüler akış çokyüzlüler ve iki genelleştirilmiş polimatroidlerin/ g- polimatroidlerin kesişimini içerir – örneğin bkz. Schrijver 2003.

Çözücüler ve komut dosyası (programlama) dilleri

İzin verilen lisanslar:

Copyleft (karşılıklı) lisanslar:

MINTO (Mixed Integer Optimizer, dal ve sınır algoritması kullanan bir tamsayı programlama çözücüsü) herkese açık kaynak koduna sahiptir ancak açık kaynak değildir.

Özel lisanslar:

Ayrıca bakınız

Notlar

Referanslar

daha fazla okuma

Dış bağlantılar

• LP Sorunlarını Formüle Etme Rehberi
• Matematiksel Programlama Sözlüğü
• Doğrusal Programlama SSS
• Optimizasyon Yazılımı için Kıyaslamalar