DOĞRUSAL PROGRAMLAMA: NE IÇINDIR, MODELLER, KISITLAMALAR, UYGULAMALAR - MATEMATIK - 2025

Doğrusal programlama matematiksel yöntemdir olan optimize (en üst düzeye çıkarmak ve uygun olarak en aza indirmek) olan değişkenler kısıtlanır bir işlev için kullanılan olarak sürece fonksiyonu ve kısıtlamalar doğrusal bağımlı değişkenlerdir.

Genel olarak, optimize edilecek işlev, girdileri, işçiliği veya makineleri sınırlı olan bir üreticinin karı gibi pratik bir durumu modeller.

Şekil 1. Doğrusal programlama, kârı optimize etmek için yaygın olarak kullanılmaktadır. Kaynak: Piqsels.

En basit durumlardan biri, yalnızca karar değişkenleri adı verilen iki değişkene bağlı olan maksimize edilecek doğrusal bir fonksiyondur. Şu biçimde olabilir:

Z = k ₁ x + k ₂ y

K ₁ ve k ₂ sabitiyle. Bu işlev, amaç işlevi olarak bilinir. Elbette, çalışma için ikiden fazla değişkeni hak eden, daha karmaşık olan durumlar vardır:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

Ve kısıtlamalar aynı zamanda matematiksel olarak x ve y'de eşit derecede doğrusal olan bir denklemler veya eşitsizlikler sistemi tarafından modellenir.

Bu sistemdeki çözüm setine uygulanabilir çözümler veya uygulanabilir noktalar denir. Ve uygulanabilir noktalar arasında, amaç işlevini optimize eden en az bir tane var.

Doğrusal programlama, Amerikalı fizikçi ve matematikçi George Dantzig (1914-2005) ve Rus matematikçi ve ekonomist Leonid Kantorovich (1912-1986) tarafından II. Dünya Savaşı'ndan kısa bir süre sonra bağımsız olarak geliştirildi.

Simpleks yöntemi olarak bilinen problem çözme yöntemi, ABD Hava Kuvvetleri, Berkeley Üniversitesi ve Stanford Üniversitesi için çalışan Dantzig'in beynidir.

Şekil 2. Matematikçiler George Dantzig (solda) ve Leonid Kantorovich (sağda). Kaynak: F. Zapata.

Doğrusal programlama modelleri

Pratik bir duruma uygun bir doğrusal programlama modeli oluşturmak için gerekli unsurlar şunlardır:

-Amaç fonksiyonu

-Karar değişkenleri

-Kısıtlamalar

Amaç işlevinde, neyi başarmak istediğinizi tanımlarsınız. Örneğin, belirli ürünlerin imalatından elde edilen karı maksimize etmek istediğinizi varsayalım. Daha sonra ürünlerin satıldığı fiyata göre "kar" fonksiyonu kurulur.

Matematiksel terimlerle, bu fonksiyon toplama notasyonu kullanılarak kısaltılmış olarak ifade edilebilir:

Z = ∑k _ben x _ben

Bu denklemde k _i katsayılardır ve x _i karar değişkenleridir.

Karar değişkenleri, kontrolü olan sistemin öğeleridir ve değerleri pozitif reel sayılardır. Önerilen örnekte, karar değişkenleri, maksimum kar elde etmek için üretilecek her bir ürünün miktarıdır.

Son olarak, karar değişkenleri açısından doğrusal denklemler veya eşitsizlikler olan kısıtlamalara sahibiz. Problemin bilinen ve örneğin imalatta mevcut hammadde miktarları olabilen sınırlamalarını tarif ederler.

Kısıtlama türleri

J = 1'den j = M'ye kadar bir dizi M sınırlamanız olabilir. Matematiksel olarak kısıtlamalar üç türdendir:

1. Bir _j = ∑ bir _ij . x _ben
2. B _j ≥ ∑ b _ij . x _ben
3. C _j ≤ ∑ c _ij . x _ben

İlk kısıtlama doğrusal denklem tipindedir ve bilinen A _j değerine saygı duyulması gerektiği anlamına gelir .

Kalan iki kısıtlama doğrusal eşitsizliklerdir ve bu , görünen sembol ≥ (büyük veya eşit) olduğunda veya saygı duyulduğunda veya aşılmadığında, eğer sembol C ise, bilinen B _j ve C _j değerlerine saygı gösterilebileceği veya aşılabileceği anlamına gelir. (küçüktür veya eşittir).

Model örneği

Uygulama alanları işletme yönetiminden beslenmeye kadar çok çeşitlidir, ancak yöntemi anlamak için aşağıda iki değişkenli pratik bir durumun basit bir modeli önerilmiştir.

Yerel bir pastane iki spesiyalitesi ile bilinir: kara orman keki ve sakripantin keki.

Hazırlanırken yumurta ve şeker gerekir. Kara orman için 9 yumurta ve 500 gr şekere, sakripantin için 8 yumurta ve 800 gr şekere ihtiyacınız var. İlgili satış fiyatları 8 dolar ve 10 dolar.

Sorun şu: 10 kilo şeker ve 144 yumurta olduğunu bilen fırın, karını en üst düzeye çıkarmak için her türden kaç kek yapmalıdır?

Karar değişkenleri

Karar değişkenleri, gerçek değerleri alan "x" ve "y" dir:

-x: kara orman keki sayısı

-y: sakripantin tipi kekler.

Kısıtlamalar

Kısıtlamalar, kek sayısının pozitif bir miktar olması ve bunları hazırlamak için sınırlı miktarda hammadde bulunması gerçeğiyle verilmektedir.

Bu nedenle, matematiksel formda bu kısıtlamalar şu şekli alır:

1. x ≥ 0
2. ve ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Kısıtlamalar 1 ve 2, daha önce ortaya çıkan olumsuz olmama koşulunu oluşturur ve ortaya çıkan tüm eşitsizlikler doğrusaldır. Kısıtlamalarda 3 ve 4 aşılmaması gereken değerlerdir: 144 yumurta ve 10 kg şeker.

Amaç fonksiyonu

Son olarak, amaç işlevi, “x” miktarda kara orman keki artı “y” miktarda sakripantin üretilirken elde edilen kardır. Yapılan kek miktarının fiyatı ile çarpılarak her çeşide göre eklenmesiyle oluşturulur. G (x, y) olarak adlandıracağımız doğrusal bir fonksiyondur:

G = 8x + 10y

Çözüm yöntemleri

Çeşitli çözüm metodolojileri arasında grafik metotlar, simpleks algoritma ve iç nokta metodu sayılabilir.

- Grafik veya geometrik yöntem

Önceki bölümdeki gibi iki değişkenli bir probleminiz olduğunda, kısıtlamalar xy düzleminde fizibil bölge veya canlılık bölgesi adı verilen çokgen bir bölge belirler.

Şekil 3. Optimizasyon probleminin çözümünün bulunduğu uygulanabilir bölge. Kaynak: Wikimedia Commons.

Bu bölge, kısıtlamaların eşitsizliklerinden elde edilen çizgiler olan sınır çizgileri kullanılarak yalnızca eşitlik işareti ile çalışılarak inşa edilmiştir.

Kârı optimize etmek isteyen fırın söz konusu olduğunda, kısıtlama satırları şunlardır:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0,5 x + 0,8y = 10

Bu çizgilerin çevrelediği bölgedeki tüm noktalar olası çözümlerdir, dolayısıyla sonsuz sayıda vardır. Uygulanabilir bölgenin boş çıkması durumu dışında, bu durumda ortaya çıkan sorunun bir çözümü yoktur.

Neyse ki, pasta problemi için uygulanabilir bölge boş değil, aşağıda var.

Şekil 4. Hamur işi probleminin uygulanabilir bölgesi. Kazanç 0 olan çizgi başlangıç ​​noktasından geçer. Kaynak: Geogebra ile F. Zapata.

Varsa en uygun çözüm, amaç işlevi yardımıyla bulunur. Örneğin, maksimum kar G'yi bulmaya çalışırken, izo-kar satırı olarak adlandırılan aşağıdaki satıra sahibiz:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

Bu çizgi ile, belirli bir G kazancı sağlayan tüm çiftleri (x, y) elde ederiz, dolayısıyla G'nin değerine göre bir doğrular ailesi vardır, ancak hepsi aynı eğime sahiptir -k ₁ / k ₂ , yani paralel çizgiler.

En uygun çözüm

Şimdi, doğrusal bir problemin en uygun çözümünün her zaman uygulanabilir bölgenin en uç noktası veya tepe noktası olduğu gösterilebilir. Yani:

Menşeye en yakın hat, uygulanabilir bölge ile ortak bir segmente sahipse, sonsuz çözümlerin olduğu söylenir. Bu durum, izo-kar çizgisinin eğiminin, bölgeyi sınırlayan diğer çizgilerin herhangi birine eşit olması durumunda ortaya çıkar.

Pastamız için aday köşeler A, B ve C'dir.

- Dantzig'in simpleks yöntemi

Grafik veya geometrik yöntem iki değişken için geçerlidir. Bununla birlikte, üç değişken olduğunda daha karmaşıktır ve daha fazla sayıda değişken için kullanılması imkansızdır.

İkiden fazla değişkenli problemlerle uğraşırken, amaç fonksiyonlarını optimize etmek için bir dizi algoritmadan oluşan simpleks yöntemi kullanılır. Hesaplamaları yapmak için genellikle matrisler ve basit aritmetik kullanılır.

Tek yönlü yöntem, uygulanabilir bir çözüm seçerek ve bunun optimal olup olmadığını kontrol ederek başlar. Öyleyse sorunu zaten çözdük ama çözülmediyse optimizasyona daha yakın bir çözüme doğru ilerliyoruz. Çözüm varsa, algoritma bunu birkaç denemede bulur.

Uygulamalar

Doğrusal ve doğrusal olmayan programlama, örneğin gerekli zamanı en aza indirmek istiyorsanız, zamanla ölçülebilecekleri için her zaman parasal olmayan maliyetleri düşürme ve karı artırma açısından en iyi kararları vermek için birçok alanda uygulanır. bir dizi işlem yapmak.

İşte bazı alanlar:

-Pazarlamada, belirli bir ürünün reklamını yapmak için en iyi medya kombinasyonunu (sosyal ağlar, televizyon, basın ve diğerleri) bulmak için kullanılır.

-Bir şirket veya fabrika personeline yeterli görevlerin verilmesi veya bunlara programların verilmesi için.

Hayvancılık ve kümes hayvanları endüstrilerinde en besleyici ve en düşük maliyetle gıda seçiminde.

Çözülmüş egzersizler

- 1. Egzersiz

Önceki bölümlerde ortaya konan doğrusal programlama modelini grafiksel olarak çözün.

Çözüm

Problemde belirtilen kısıtlama sistemi tarafından belirlenen değer kümesinin grafiğini çizmek gerekir:

1. x ≥ 0
2. ve ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Eşitsizlikler 1 ve 2 tarafından verilen bölge, Kartezyen düzlemin ilk çeyreğine karşılık gelir. Eşitsizlikler 3 ve 4 ile ilgili olarak, kısıtlama çizgilerini bularak başlıyoruz:

9x + 8y = 144

0,5 x + 0,8y = 10 → 5x + 8y = 100

Uygulanabilir bölge, köşeleri A, B, C ve D noktaları olan bir dörtgendir.

Minimum kar 0'dır, bu nedenle 8x + 10y = 0 doğrusu alt sınırdır ve eş-kar çizgilerinin eğimi -8/10 = - 0.8'dir.

Bu değer, diğer sınırlama çizgilerinin eğimlerinden farklıdır ve uygulanabilir bölge sınırlandırıldığı için benzersiz çözüm mevcuttur.

Şekil 5. Uygulanabilir bölgeyi ve söz konusu bölgenin köşelerinden birindeki C çözüm noktasını gösteren 1. Alıştırmanın grafik çözümü. Kaynak: F. Zapata.

Bu çözüm, koordinatları aşağıdaki gibi olan A, B veya C noktalarının herhangi birinden geçen -0,8 eğim çizgisine karşılık gelir:

Bir (11; 5.625)

B (0; 12,5)

C (16; 0)

En uygun çözüm

Bu noktaların her biri için G değerini hesaplıyoruz:

- (11; 5.625): G, _A = 8 x 11 + 10 x 5,625 = 144,25

- (0; 12.5): G, _B = 8 x 0 + 10 x 12.5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

En yüksek kâr, 11 kara orman keki ve 5,625 sakripantin keki imal etmektir. Bu çözüm, yazılım aracılığıyla bulunan çözümle uyumludur.

- Egzersiz 2

Doğrusal programlamada optimizasyon için Simplex algoritmasını içeren Excel veya LibreOffice Calc gibi çoğu elektronik tabloda bulunan Çözücü işlevini kullanarak önceki alıştırmanın sonucunu doğrulayın.

Çözüm

Şekil 6. Libre Office Calc hesap tablosu aracılığıyla 1. alıştırmadan çözümün ayrıntısı. Kaynak: F. Zapata.

Şekil 7. Libre Office Calc hesap tablosu aracılığıyla 1. alıştırmadan çözümün ayrıntısı. Kaynak: F. Zapata.

Referanslar

1. Parlak. Doğrusal programlama. Brilliant.org'dan kurtarıldı.
2. Eppen, G. 2000. Yönetim Bilimlerinde Yöneylem Araştırması. 5. Baskı. Prentice Hall.
3. Haeussler, E. 1992. Yönetim ve Ekonomi için Matematik. 2. Baskı. Grupo Editoryal Iberoamericana.
4. Hiru.eus. Doğrusal programlama. Kurtarıldı: hiru.eus.
5. Wikipedia. Doğrusal programlama. Kurtarıldığı yer: es. wikipedia.org.