Soru Doğrusal programlama nedir? [kapalı]


Wikipedia'yi okudum makaleama benim anlayışımın ötesinde görünüyor. Optimizasyon için olduğunu söylüyor, ama şeyleri optimize etmek için başka herhangi bir yöntemden nasıl farklıdır?

Beni lineer programlamaya yönlendiren bir cevap, daha az yeni başlayanlar için erişilebilir malzemeye dalmaya başlayabilmem için en faydalı olacaktı.


18
2017-07-26 16:42


Menşei


Çok basitçe söylemek gerekirse, probleminizi bir dizi doğrusal denklem olarak yeniden yazmak ve sonra bu denklemleri çözmektir. - FrustratedWithFormsDesigner
Bu çok saçma. Bu soru hiç konu dışı değil. - Greg Kuperberg
Yeniden açılmaya oy vermek, konu dışı değil. - BlueRaja - Danny Pflughoeft
LP algoritmaları veya kodu ile ilgili bir tartışma kesinlikle konu üzerinde olacaktır. Süper Kullanıcı üzerinde bir LP sistemi tartışması konu olacaktır. Bir yaklaşım olarak LP'nin tartışması konu dışıdır, çünkü program dışı disiplinlerde aynı derecede konu (veya daha fazlası) olacaktır. - David Thornley
@David: Yayınlanan her cevap algoritmalar ve yazılım geliştirme ile ilgilidir. Soru, LP paketleri ile ilgili olmasa bile, süper paketler.com, LP paketleri genellikle API'ler olarak ve son kullanıcı yazılımı olarak kullanılmadığından anlam ifade etmiyordu. Aksiyomlar ve varsayımlardan ziyade, konu üzerinde neyin deneyim ve sağduyuyla olduğuna karar vermek daha iyi olmaz mı? - Greg Kuperberg


Cevaplar:


Şimdiye kadar verilen cevaplar doğrusal programlamanın cebirsel bir tanımını ve operasyonel bir tanımı vermiştir. Ama aynı zamanda geometrik bir tanım var. bir politop bir poligonun (iki boyutta) veya bir polihedronun (üç boyutlu) bir n-boyutlu genellemesidir. bir dışbükey polytope aynı zamanda bir dışbükey set olan bir polytope. Tanım olarak, doğrusal programlama, bir dışbükey polytope üzerinde bir lineer işlevi en üst düzeye çıkarmak veya en aza indirmek istediğiniz bir optimizasyon problemidir.

Örneğin: Kırmızı kum ve mavi kumların bazı kombinasyonlarını satın almak istediğinizi varsayalım. Ayrıca düşünün:

  1. Her iki türden de negatif bir miktar satın alamazsınız.
  2. Depoda sadece 300 lira kırmızı kum ve 400 lira mavi kum var.
  3. Ayrıca cipinizin ağırlık limiti 500 liradır.

Bu kısıtlamalarla ne kadar satın alabileceğinizi uçakta çizerseniz, bu bir dışbükey pentagondur. Ardından, optimize etmek istediğiniz her şeyi (örneğin, kumdaki toplam altın miktarı), bir optimumun (sadece optimum olanı değil), polytope'un köşe noktalarından birinde olduğunu bilirsiniz. Aslında, çok daha güçlü bir sonuç var: Yüksek boyutlarda bile, bu tür doğrusal programlama problemleri polinom zamanında, kısıtlamaların sayısına veya poltopeun varsayılan yanlarına çözülebilir. Her kısıtlamanın bir tarafa karşılık gelmediğini unutmayın. Kısıtlama bir eşitlik ise, polytope boyutunu azaltabilir. Ya da kısıtlama bir eşitsizlik ise, diğer tüm kısıtlamaların zaten ima ettiği bir taraf oluşturmayabilir.

Doğrusal programlama olan birçok pratik optimizasyon problemi vardır. İlk örneklerden biri "diyet problemi" idi: Bir çeşit yiyecek türünden bir menü verildiğinde, mümkün olan en ucuz dengeli diyet nedir? Doğrusal bir programlama problemidir, çünkü maliyet doğrusaldır ve tüm kısıtlamalar (vitaminler, kaloriler, negatif miktarda yiyecek alamayacağınız varsayımı, vb.) Doğrusaldır.

Ancak, doğrusal programlama teorik bir sebepten daha önemlidir. Optimizasyon veya herhangi bir başka amaç için en güçlü polinom zaman algoritmalarından biridir. Bu nedenle, diğer optimizasyon problemlerini çözmenin bir alternatifi ve bunları tam olarak çözmek için bir altprogram olarak çok önemlidir.

Evet, iki genelleme, dışbükey programlama ve tamsayı programlamadır. Bazı kalifikasyonlar ile, konveks programlama, doğrusal (maksimize edilecek şey) çizgisinin doğrusal olması koşuluyla, doğrusal programlamanın yanı sıra çalışabilir. Doğrusal programlamanın iyi bir algoritmaya sahip olmasının ana sebebi, düz kenarların değil, dışbükeyliğin ortaya çıkmasıdır.

Tam tersi programlama ise genellikle zor. Örneğin, örnek problemde kumun, toplu halde değil, sabit boyutlu torbalarda satın almanız gerektiğini varsayalım; o zaman tamsayı programlama. NP-zor olabileceği bir teorem var. Pratikte ne kadar zor olursa doğrusal programlamaya ne kadar yakın olduğuna bağlıdır. Doğrusal programın tüm köşeleri mucizevi bir şekilde tamsayı noktaları olan tamsayılı programlama problemlerinin bazı ünlü örnekleri vardır. Ardından doğrusal programı çözebilir ve çözümün bütünleşik olacağı söylenebilir. Böyle bir sorunun bir örneği, evlenme problemi, n erkek ve kadınların evlenmeleri ile toplam mutluluğu en üst düzeye çıkarmasıdır. (Ya da, n şehirlere n şehirler, n iş başvurusunda bulunanlar, n bilgisayarlardan n yazıcıya, vb.)


13
2017-07-26 19:43





Doğrusal programlama, 'matematiksel optimizasyon' olarak da adlandırılan 'matematiksel programlama' konusudur. Doğrusal programlar, genel matematik programlarından farklı olarak, tüm kısıtlama fonksiyonlarında Doğrusal Program (LP) için ve objektif fonksiyon değişkenlerine göre doğrusaldır.

Başlamak için iyi bir yer olurdu İşte Dantzig'in orijinal çalışmasını istiyorsanız ya da bir ders kitabı almak istiyorsanız, bu bir. Kendi kaynaklarınızı aramak istiyorsanız, Simpleks metodu- bu programları çözmek için çok yaygın bir teknik ya da daha az yaygın fakat kesinlikle polinom zamanı Elipsoid yöntemi. Her şeyi okumamış olmama rağmen, hızlıca bakmak da önerdi bu PDF, başlamak için iyi bir yer olabilir. Sonunda okuduğunuz şey, dualiteyi (ve özellikle de Farkas 'lemmaÇoğu LP çözücüsünde merkezi bir fikir olduğu için.

En doğal uzantılar ya Tamsayı programlardır (LP'lere benzer, ancak tüm değişkenler tamsayı değerleri almalıdır - yani, kesirli bileşenler içermez) veya Konveks programlama (belki daha genel bir uzantı). İyi bir dışbükey optimizasyon ders kitabı PDF formatındadır. İşte.


6
2017-07-26 16:56





Herkesin dediği gibi, Doğrusal Programlama, terimlerin lineer olduğu optimizasyon problemlerini çözmenin bir yoludur.

LP'nin çözdüğü problem türlerini anlamaya yardımcı olabilir.

Doğrusal Programlama'yı kullandığım bir örnek, bir restoran programı oluşturuyor. Bir restoranda yetenek setleriniz var:

  • Aşçılar
  • Sunucular
  • Bulaşık Makineleri
  • Sunucular
  • bussers
  • yönetici vb

Ve her birinde bir veya daha fazla beceri kümesine sahip çalışanlarınız var. Her çalışanın özel bir mevcudiyeti de vardır. Örneğin, Bob Pazar sabahları çalışamaz çünkü yerel bir kilisede papaz. Çalışanlar da ilişkili bir maliyete sahiptir. Suzy $ 5.15 / saat iken Bob, 10.50 $ / saat olabilir. Son olarak Çalışanların minimum garanti süresi olabilir. Bob 15 yıldır bir çalışan olduğundan, patron her zaman en az 35 saat alacağını söylüyor.

Restoranın talepleri vardır. Örneğin, 3 vardiyası vardır: Sabah, Öğleden Sonra ve Gece ve bu vardiyaların her biri bir dizi personel gereksinimine sahiptir: 1 aşçıya, 1 sunucuya, sabah 1 yöneticiye, 3 aşçıya, 2 sunucuya, 2 ana bilgisayara, 2 Öğleden sonraları yöneticiler ve 4 aşçı, 4 sunucu, 3 host, 2 yönetici, akşam 2 bussers. Her vardiyada bir süre olacak ve süreyi çalışanın saatlik ücretiyle çarparak her vardiyanın maliyetini hesaplayabilirsiniz.

Son olarak eyalet ve federal yasalarımız ve bazı temel “iş” kurallarımız var: Hiçbir çalışan fazla mesai yapmadan 8 saatten fazla çalışamaz. Hiçbir çalışan 2 saatten daha kısa bir süre için planlanamaz (çünkü 2 saatlik vardiya için 30 dakikalık bir işe gidip gelmek için emer), çalışanlar iki örtüşen vardiya çalışamaz, vb.

Şimdi tüm bu gereksinimler göz önüne alındığında, bana tüm gereksinimleri karşılayan bir program verin ve en düşük işçilik maliyetini yaratın.

Bu, doğrusal programlama optimizasyon probleminin bir örneğidir.

Bir doğrusal program tipik olarak aşağıdakilerden oluşur:

Bir nesnel işlev, değişkenler, değişken sınırlar ve kısıtlamalar.

Maliyetimizi en aza indirmek istediğimizden beri, objektif fonksiyonumuz çalışanların çalıştığı vardiyaları ve ilgili maliyetleri (vardiya süresi * ücret) içerecektir.

Bu durumda değişkenler, her bir çalışanın çalışabileceği vardiyalardır.

Bu değişkenlerdeki sınırlar 0 ile 1 arasında bir tamsayıdır, çünkü bir çalışan vardiyada çalışıyor (1), ya da çalışan vardiyada (0) çalışmıyor. Bu arada, tüm değişkenler tamsayılar (kesirli değerler değil) ve tüm değerler 0 veya 1 olduğundan, bu, İkili Tamsayı Programı veya BIP olarak adlandırılan özel bir programdır.

Kısıtlamalar, yukarıdaki gerekliliklere dayalı eşitlik / eşitsizlik kısıtlarıdır.

Örneğin, eğer Bob ve Suzy sabahları aşçı olarak çalışabilirlerse, o zaman Bob_Morning_Cook1_Shift + Suzy_Morning_Cook1_Shift = 1, ile Bob_Morning_Cook_Shift = {0,1} ve Suzy_Morning_Cook_Shift = {0,1} Yukarıda belirtilen sınırlar nedeniyle. Bu üç bilgi parçası, ilk sabah aşçısı olarak sadece en az bir çalışanın atanabileceğini belirtmektedir.

Böylece, sorununuzu modelleyen tüm kısıtlamaları tanımladıktan sonra, sorunu çözmeye başlayabilirsiniz. Bir çözüm bulunabilirse (ve kısıtlamalara bağlı olarak problemin mümkün olmadığı durumlarda), size en düşük haftalık işgücü maliyetini üreten çalışan atamaları verilecektir.


4
2017-07-26 17:24





Doğrusal programlama, doğrusal kısıtlamaları ve doğrusal bir amaç işlevini içeren bir optimizasyon tekniğidir. Kısıtlamalar, problem alanını sınırlamak için yazılırken, objektif işlev, kısıtlamaları karşılayan minimize etmeye (veya muhtemelen maksimize etmeye) çalıştığınız bir şeydir. simpleks algoritması Bu tipik olarak, kısıtlamaları tatmin eden hedef fonksiyonun minimum (veya maksimum) değerini bulmak için kısıtlama kesişiminin kenarları boyunca yürümektedir.

Bir LP problemi kurarken, kısıtlamaların objektif fonksiyonu doğru bir şekilde bağladığından emin olmak önemlidir. Olası bir çözümle sonuçlanmayan kısıtlamaları tanımlamak mümkündür (örneğin x> 1 ve -x> 1). Bu kısıtlanmış bir şey. Bir problemi daha az kısıtlamak da mümkündür (örneğin, x <1 gibi min.


2
2017-07-26 16:56



Eminim ki bu soru şu anda kapalıdır diye sormak anlamsızdır, ama beni modifiye eden kişi nedenini açıklayacak kadar nazik olur mu? Teşekkürler. - andand


Bir büyük fark (ya da en azından ayırt edici özelliği) doğrusal programlama, kısıtlamaların modellenmesidir. doğrusal denklemler, yani hepsi formda c_1 x_1 + c_2 x_2.... Wikipedia makalesinin standart form bölümü, bunun oldukça iyi bir genel görünümünü verir.

Bir başka fark / özellik, doğrusal programlamanın ONE fonksiyonunu en üst düzeye çıkarmak (ya da en aza indirmek) için uğraşmasıdır - çok amaçlı optimizasyonu etkin bir şekilde yapamazsınız.


1
2017-07-26 16:48



Bir fonksiyonun maksimizasyonu norm değil midir? - Mathias
@Mathias - belki de bu norm, ancak mevcut olan tek optimizasyon türü değil. - awshepard
Aslında aklında ne olduğunu duymakla ilgilenirdim! Bir optimizasyon problemi matematiksel olarak bazı fonksiyonların en aza indirgenmesidir ve aynı değişkenin iki fonksiyonunu bir arada tutamayacağınız için, genellikle bu fonksiyonların tek bir fonksiyonunu en aza indirirsiniz (bunların ağırlıklı bir kombinasyonu gibi). - Mathias
@Mathias - wikipedia, bir fonksiyonun en aza indirgenmesi / maksimizasyonu olan optimizasyonun "en basit hali" ni ifade eder ve daha sonra çok amaçlı optimizasyon sayfasına bağlantı sağlar. Belki de beni şaşırtmak / tartışmamız, bir profesörün bir kez çok yönlü bir optimizasyon problemi olarak sırt çantası problemine gönderme yapmasıdır (ağırlığı en aza indirgemek, değeri maksimize etmek); Geriye doğru bakıldığında, gerçekten sadece sırtlığın sadece belirli bir miktar tutacağı kısıtlamaya tabi olan değeri en üst düzeye çıkarır. - awshepard
@Mathias (devamı) - Çok amaçlı optimizasyon sayfası aynı zamanda fonksiyonların bir araya getirilmesi yaklaşımına da atıfta bulunur, ancak ağırlığın seçimi açısından öznel olduğunu belirtmektedir ... Açıkçası biraz daha fazla okumaya ihtiyacım var. Bu konuda ... .... - awshepard