Giriş
Doğrusal programlama, çok sayıda değişkeni içeren konularda karar vericilere yardımcı olmayı amaçlayan bir dizi rasyonel analiz ve problem çözme tekniğidir.
Doğrusal programlamanın adı bilgisayar programlarının yaratılmasından değil, askeri bir terim olan programlamadan gelir, bu da "eğitim, lojistik veya savaş birimlerinin konuşlandırılması için planlar veya zaman teklifleri yapmak" anlamına gelir.
Doğrusal programlamanın 1776'da G. Monge tarafından kullanıldığı görülmesine rağmen, LV Kantorovich yaratıcılarından biri olarak kabul edilir. Bunu organizasyon ve üretim için matematiksel yöntemler (1939) adlı kitabında sundu ve Kitlelerin transferi üzerine (1942) adlı çalışmasında geliştirdi. Kantorovich, insan kaynaklarının en iyi şekilde tahsis edilmesi sorununa yaptığı katkılardan dolayı 1975'te ekonomi dalında Nobel Ödülü'nü aldı.
Bilgisayarlar sayesinde genel olarak yöneylem araştırması ve özellikle doğrusal programlama büyük bir destek aldı. En önemli anlardan biri simpleks yönteminin ortaya çıkışıydı.
hedefler
- Doğrusal programlamayı ve günlük yaşamdaki uygulamalarını bilmek, Doğrusal programlama ile durum oluşturma ve çözme, Bir modelin oluşturulması için adımlar.
Çözüm Türü
İki değişkenli doğrusal programlar genellikle sundukları çözüm türüne göre sınıflandırılır. Bunlar şunlar olabilir:
- Uygulanabilir: Kısıtlamaları karşılayan bir dizi çözüm veya değer varsa. Bunlar sırasıyla şunlar olabilir: tek bir çözümle, çoklu çözümle (birden fazla çözüm varsa) ve sınırsız bir çözümle (amaç işlevi için sınır olmadığında) Uygulanabilir değil: kısıtlamalar, yani kısıtlamalar tutarsız olduğunda.
Çözüm yöntemleri
Doğrusal programlama problemlerini çözmenin üç yöntemi vardır:
- Grafik metodu: Seviye çizgileri, objektif fonksiyonun aynı değeri aldığı düzlemin noktalarını verir.Analitik metot: Doğrusal programlamanın temel teoremi olarak adlandırılan aşağıdaki sonuç, iki değişkenli bir programı çözmenin başka bir yöntemini bilmemizi sağlar.: “İki değişkenli doğrusal bir programda, amaç işlevini optimize eden benzersiz bir çözüm varsa, bu sınırlı uygulanabilir bölgenin en uç noktasında (tepe noktası) bulunur, asla söz konusu bölgenin içinde değildir. Amaç işlevi iki köşede aynı optimum değeri alırsa, belirledikleri segmentin noktalarında da aynı değeri alır. Uygulanabilir bölgenin sınırlı olmaması durumunda, nesnel doğrusal fonksiyon mutlaka belirli bir optimal değere ulaşmaz, ancak ulaşırsa, bölgenin köşelerinden biridir ”.Pratik şema: Doğrusal programlama problemleri, fonksiyon, hedefler ve kısıtlamalar vererek standart formda sunulabilir veya bir ifade ile ifade edilebilir.
Basit yapı:
Aşağıdakilerden alınan doğrusal programlama örnekleri:
www.superprof.es/apuntes/escolar/matematicas/algebralineal/pl/ejembres-de-programacion-lineal.html
Bir mağaza, bir üreticiden pantolon ve spor ceket sipariş eder.
Üreticinin yapabileceği 750 m pamuklu kumaş ve 1000 m polyester kumaş var. Her pantolon 1 m pamuk ve 2 m polyester gerektirir. Her ceket için 1,5 m pamuk ve 1 m polyester gerekir.
Pantolonun fiyatı 50 dolar ve ceketin fiyatı 40 dolar olarak belirlendi.
Üreticinin, maksimum satış kaydetmeleri için depolara kaç tane pantolon ve ceket tedarik etmesi gerekir?
1. Bilinmeyenlerin seçimi.
- X = pantolon sayısı Y = ceket sayısı
2. Amaç işlevi
- F (x, y) = 50x + 40y
3. Kısıtlamalar
Kısıtlamaları yazmak için kendimize bir tablo ile yardımcı olacağız:
| Pantolon | Ceketler | Mevcut | |
|
Pamuk |
bir |
1.5 |
750 |
|
Polyester |
iki |
bir |
1000 |
- X + 1.5y <750 à 2x + 3y <1500 2x + y <1000
Pantolon ve ceket sayısı doğal sayı olduğu için iki kısıtlamamız daha olacak:
- X> 0Y> 0
4. Uygulanabilir çözüm kümesini bulun
Kısıtlamaları grafiğe dökmeliyiz.
X> 0 ve y> 0 olduğundan birinci çeyrekte çalışacağız.
Çizgileri eksenlerle kesişme noktalarından başlayarak temsil ediyoruz.
Doğrusal programlama
Eşitsizliği grafiksel olarak çözüyoruz: 2x + 3y <1500, bunun için düzlemin bir noktasını alıyoruz, örneğin (0,0).
0 <1500 olduğundan, (0,0) noktası eşitsizliğin sağlandığı yarım düzlemdedir.
Benzer şekilde 2x + y <1000'i çözün.
Doğrusal programlama
Eşitsizliklerin çözümlerinin kesişme alanı, uygulanabilir çözümler dizisini oluşturan eşitsizlikler sistemine çözüm olacaktır.
5. Uygulanabilir çözümlerin mahfazasının köşelerinin koordinatlarını hesaplayın.
En uygun çözüm, eğer benzersizse, muhafazanın bir köşesinde bulunur. Sistemlere yönelik çözümler şunlardır:
2x + 3y = 1500; x = 0 (0,500)
2x + y = 1000; y = 0 (500,0)
2x + 3y = 1500; 2x + y = 1000 (375, 250)
Doğrusal programlama
6. Amaç fonksiyonunun değerini hesaplayın
Amaç işlevinde her bir köşeyi değiştiririz.
- F (x, y) = 50x + 40yF (0,500) = 50 * 0 + 40 * 500 = 20.000 ABD DolarıF (500,0) = 50 * 500 + 40 * 0 = 25.000 ABD DolarıF (375.250) = 50 * 375 + 40 * 250 = 28750 ABD doları
En uygun çözüm, 28.750 $ kar için 375 pantolon ve 250 ceket yapmaktır.
Kaynakça:
Aşağıdakilerden alınan doğrusal programlama örnekleri:
www.superprof.es/apuntes/escolar/matematicas/algebralineal/pl/ejembres-de-programacion-lineal.html
