Doğrusal programlama matematiği

Doğrusal programlama, çeşitli kısıtlamalara maruz kaldığında lineer bir fonksiyonun maksimize edildiği veya minimize edildiği matematiksel modelleme tekniği. Bu teknik, iş planlamasında, endüstri mühendisliğinde ve - daha az bir ölçüde - sosyal ve fiziksel bilimlerde nicel kararların yönlendirilmesinde yararlı olmuştur.

optimizasyon: Doğrusal programlama

Günlük karar sorunlarını çözmek için günümüzde yaygın olarak kullanılmasına rağmen, doğrusal programlama 1947'den önce nispeten bilinmemektedir.

Doğrusal bir programlama probleminin çözümü, doğrusal ifadenin (nesnel işlev olarak adlandırılır) optimum değerini (probleme bağlı olarak en büyük veya en küçük) bulmayı azaltır

eşitsizlikler olarak ifade edilen bir dizi kısıtlamaya tabi olarak:

A'lar, b'ler ve c'ler, problemin kapasiteleri, ihtiyaçları, maliyetleri, karları ve diğer gereklilikleri ve kısıtlamaları ile belirlenen sabitlerdir. Bu yöntemin uygulanmasındaki temel varsayım, talep ve kullanılabilirlik arasındaki çeşitli ilişkilerin doğrusal olduğudur; yani, x _i'nin hiçbiri 1 dışında bir güce yükseltilmez. Bu soruna çözüm bulmak için, doğrusal eşitsizlikler sisteminin (yani n değerlerinin kümesinin) çözümünü bulmak gerekir. aynı anda tüm eşitsizlikleri karşılayan x _i değişkenleri). Amaç fonksiyonu daha sonra x değerlerinin değiştirilmesi ile değerlendirilir _ı o tanımlar f denklemde.

Doğrusal programlama yönteminin uygulamaları ilk olarak 1930'ların sonunda Sovyet matematikçi Leonid Kantorovich ve Amerikalı iktisatçı Wassily Leontief tarafından sırasıyla üretim programları ve ekonomi alanlarında ciddi bir şekilde denendi, ancak çalışmaları onlarca yıl göz ardı edildi. II. Dünya Savaşı sırasında, doğrusal programlama, maliyetler ve kullanılabilirlik gibi belirli kısıtlamalara tabi olan kaynakların taşınması, programlanması ve tahsisini ele almak için yaygın olarak kullanılmıştır. Bu uygulamalar, 1947'de Amerikan matematikçi George Dantzig'in doğrusal programlama problemlerinin çözümünü büyük ölçüde basitleştiren simpleks yönteminin tanıtımı ile daha fazla ivme kazandıran bu yöntemin kabul edilebilirliğini belirlemek için çok şey yaptı.

Bununla birlikte, daha fazla değişkeni içeren giderek daha karmaşık problemler denendiğinden, gerekli işlemlerin sayısı katlanarak arttı ve en güçlü bilgisayarların bile hesaplama kapasitesini aştı. Daha sonra, 1979'da Rus matematikçi Leonid Khachiyan, hesaplama adımlarının sayısının katlanarak değil değişken sayısının gücü olarak büyüdüğü bir polinom-zaman algoritması keşfetti ve böylece şimdiye kadar erişilemeyen sorunların çözümüne izin verdi. Bununla birlikte, Khachiyan'ın algoritması (elipsoid yöntemi olarak adlandırılır), pratik olarak uygulandığında simpleks yönteminden daha yavaştı. 1984'te Hintli matematikçi Narendra Karmarkar, simpleks yöntemiyle rekabeti kanıtlayan başka bir polinom-zaman algoritması, iç nokta yöntemi keşfetti.