MAT106U-MATEMATİK-II
Ünite 3: Doğrusal Programlamaya Giriş
Bu ünitenin konusu çoğunlukla firmaların üretimlerini planlarken, imkanları ölçüsünde en yüksek geliri elde etmek veya masrafları olabildiğince azaltmak için kullandıkları doğrusal programlamadır. Burada programlama kelimesi bilgisayar programlamadaki anlamında değil, planlama anlamında kullanılmaktadır.
a, b, c sabit sayılar olmak üzere;
a x + b y ≤ c
eşitsizliğine doğrusal eşitsizlik denir.
Bu ünite içerisinde doğrusal programlamanın temel kavramları, üretim planlaması ile ilgili bir örnek ele alarak incelenmektedir.
Masa ve sandalye üretilen küçük bir atölyede tahta ve tutkal kullanılarak üretim yapılmaktadır. Atölyenin deposunda 3000 dm3 tahta ve 20 kg tutkal mevcuttur.
Bir tane masa üretebilmek için 60 dm3 tahta ve 0,2 kg tutkal; bir tane sandalye için de 10 dm3 tahta ve 0,1 kg
tutkal gerekmektedir.
Masanın tanesini 150 liradan, sandalyenin tanesini de 50 liradan satılmaktadır. Üretilen masa ve sandalyelerin tümünün satılacağını kabul edecek olursak; sadece eldeki malzemeleri kullanarak geliri maksimum yapmak için kaç tane masa ve kaç tane sandalye üretilmelidir?
Üretilen masa sayısını x ile sandalye sayısını da y ile gösterilecek olursa; ne kadar malzeme kullanılacağı aşağıdaki denklemlerle ifade edilmektedir.
60 x + 10 y ≤ 3000
0.2 x + 0.1 y ≤ 20
x ≥ 0
y ≥ 0
Bu örnek doğrusal programlama probleminde amaç; yukarıdaki eşitsizlikleri kullanarak bulunacak olan x ve y değerleri için 150 x + 50 y fonksiyonu maksimum değer almasıdır.
Burada 150 x + 50 y fonksiyonu amaç fonksiyonu, x ve y değişkenleri de karar değişkenleri olarak adlandırılır. Bu şekilde ifade edilen problemlere doğrusal programlama problemleri denilmektedir.
a1, b1, c1, . . . , ak, bk, ck sayıları pozitif olmak üzere;
𝑎!𝑥 + 𝑏! 𝑦 ≤ 𝑐! 𝑎!𝑥 + 𝑏! 𝑦 ≤ 𝑐! ⋮ 𝑎!𝑥 + 𝑏! 𝑦 ≤ 𝑐! 𝑥 ≥ 0, 𝑦 ≥ 0
doğrusal eşitsizliklerine maksimizasyon probleminin kısıtları denilmektedir.
Çokgen Bölge
Doğrusal programlama örneği için elde edilen;
60 x + 10 y ≤ 3000
0.2 x + 0.1 y ≤ 20
x ≥ 0
y ≥ 0
eşitsizliklerini aynı anda sağlayan (x, y) noktalarının kümesini belirlemesi gerekmektedir. x ≥ 0 ve y ≥ 0 olduğundan bu küme x y− düzleminde birinci bölgede yer alır.
60 x + 10 y ≤ 3000, x ≥ 0 ve y ≥ 0 koşullarını sağlayan noktaların kümesi S1 ile gösterilecek olursa:
S1 = {(x, y) | 60 x +10 y ≤ 3000, x ≥ 0, y ≥ 0}.
0,2x +0,1 y ≤ 20, x ≥ 0 ve y ≥ 0 koşullarını sağlayan noktaların kümesi de
S2 = {(x, y) | 0,2x +0,1 y ≤ 20, x ≥ 0, y ≥ 0},
şeklinde ifade edilebilir.
Doğrusal programlama örneği için elde edilen bütün denklemlerini sağlayan değerler S1 ∩ S2 arakesit kümesini oluşturur (S:68, Şekil 3.8).
a1, b1, c1, . . . , ak, bk, ck sayıları pozitif olmak üzere;
𝑎!𝑥 + 𝑏! 𝑦 ≤ 𝑐! 𝑎!𝑥 + 𝑏! 𝑦 ≤ 𝑐! ⋮ 𝑎!𝑥 + 𝑏! 𝑦 ≤ 𝑐! 𝑥 ≥ 0, 𝑦 ≥ 0
eşitsizliklerini sağlayan tüm (x, y) noktalarının kümesine düzlemde bir çokgen veya çokgen bölge denir (S:69, Şekil 3.9).
Böylelikle problemin tanım kümesini köseleriyle birlikte belirlenmiş olur (S: 69, Şekil 3.10).
Grafik Yöntemle Çözüm
Bulunan köşe noktaları doğrusal programlama problemlerinin çözümünde önemli bir yer teşkil etmektedir. Bu köşe noktalardan problemin çözümüne ulaşılmaktadır. Problemin ortaya koyduğu kısıtlar ve amaç fonksiyonu kullanılarak doğrusal programlama problemleri çözülebilir.
a1, b1, c1, . . . , ak, bk, ck sayıları pozitif olmak üzere;
𝑎!𝑥 + 𝑏! 𝑦 ≤ 𝑐! 𝑎!𝑥 + 𝑏! 𝑦 ≤ 𝑐! ⋮ 𝑎!𝑥 + 𝑏! 𝑦 ≤ 𝑐! 𝑥 ≥ 0, 𝑦 ≥ 0
kısıtları altında
𝑓 𝑥, 𝑦 = 𝑎𝑥 + 𝑏𝑦
doğrusal amaç fonksiyonunun değerini en büyük yapan noktayı belirleme problemine bir doğrusal programlama problemi denir.
𝑓 𝑥, 𝑦 = 𝑎𝑥 + 𝑏𝑦 doğrusal fonksiyonu çokgen bölge üzerinde en büyük değerini çokgenin bir köşe noktasında alır.
Bu ünitede verilen örnek doğrusal programlama problemin içerisinde de depodaki malzemeler ile ilgili kısıtlar bulunmakta ve amaç bu kısıtlar altında geliri maksimum yapan masa sandalye sayısını belirlemektir.
Elde edilen çokgen bölge üzerinde
150 x +50 y
doğrusal amaç fonksiyonu en büyük değerini çokgenin bir köşe noktasında alır.
150x +50y amaç fonksiyonunun tanım kümesinin köşe noktalarındaki değerleri hesaplanacak olursa:
(0,0) noktasındaki değer 150 · 0+50 · 0 = 0,
(50,0) noktasındaki değer 150 · 50+50 · 0 = 7500,
(25,150) noktasındaki değer 150 · 25+50 · 150 = 11250,
(0,200) noktasındaki değer 150 · 0+50 · 200 = 10000
olarak elde edilir.
Buna göre 150x +50y amaç fonksiyonu tanım kümesi üzerindeki en büyük değerini (25,150) noktasında ve en fazla 11250 lira gelir elde edecek şekilde alıyor.
150x + 50y amaç fonksiyonunun maksimum değerini neden (25,150) noktasında aldığına bakmak gerekmektedir.
z = f (x, y) = 150x + 50y denklemiyle gösterilecek olsun. z’ye farklı değerler vererek ax + by = z doğrusunun hareketine bakarak
f (x, y) = ax + by
amaç fonksiyonunun maksimum değerini bulabiliriz. z’ye sıfırdan başlayıp artan değerler verdiğimizde doğrunun çokgen bölgeyle son temas ettiği nokta amaç fonksiyonunun en büyük değerini verir.
z = 0 için 150x +50y = 0,
z = 3000 için 150x +50y = 3000,
z = 7000 için 150x +50y = 7000,
z = 11250 için 150x +50y = 11250,
doğruları grafik üzerinde incelenirse; z değeri arttırıldıkça, 150x + 50y = z doğrusu 150x + 50y = 0 doğrusuna paralel kalarak hareket ettiği ve çokgen bölgeyi en son f (x, y) = 150x + 50y amaç fonksiyonunun maksimum
değerini aldığı (25,150) noktasında kestiği görülmektedir (S:73, Şekil 3.14).
Verilen örnekten de anlaşılacağı gibi, hedef amaç fonksiyonunu maksimize etmeye çalışmaktır. Bu yöntem amaç fonksiyonunun minimum değerinin araştırıldığı problemlerde de kullanılabilir.
Sonuç olarak doğrusal programlama yardımıyla yapılan bu modelleme çalışmasında sonsuz seçenekli bir durumda sonlu tane noktanın kontrol edilmesiyle çözüme nasıl ulaşıldığını da gösterilmiştir.