DERS 9
Doğrusal Programlama
Doğrusal Programlama, yönetimde belli konularda karar verilirken yararlanılan,
yönetim biliminin en iyi bilinen ve en çok kulanılan yöntemidir. Bu konuyu örneklerle
açıklamaya çalışacağız.
Doğrusal Programlama fikri ilk kez, ikinci dünya savaşı yıllarında, Rus matematikçi L. W.
Kantarovich tarafından savaş operasyonlarında karmaşık planlama problemlerinin
çözümü için geliştirilmiştir. Geliştirilen yöntem savaş süresince gizli tutuldu.
Kantarovich’in 1942 de yazdığı “The best use of economic resources” başlıklı çalışması
ancak 1959 yılında yayınlanmıştı. Savaş sonrası, 1947 yılında G. B. Danzig simpleks
yöntemini yayınladı; J. Von Neumann dualite ilkesini geliştirdi ve oyun teorisine
uyguladı. İlerleyen yıllarda pek çok endüstri günlük planlama problemlerinde doğrusal
programlamayı kullandı. Doğrusal programlamanın yaygın ve etkin olarak kullanıldığı
alanlar arasında üretim planlaması, hava yolu taşımacılığı, deniz taşımacılığı, telekomünikasyon ağları, rafineriler, hisse senetleri piyasası, portföy yönetimi sayılabilir.
Verilen n değişkenli bir doğrusal fonksiyonun değişkenler üzerinde doğrusal eşitlik ve/
veya eşitsizliklerle ifade edilmiş belli kısıtlamalar altında maksimumunu veya minimumunu bulma problemine n değişkenli doğrusal programlama problemi denir.
Bu dersimizde, çok basit (iki değişkenli) doğrusal programlama problemlerini ele
alacağız ve bunların geometrik yaklaşımla çözümlerini tartışacağız. Daha sonraki derslerimizde, çok değişkenli doğrusal programlama problemlerini ve bunların çözümü için
çağdaş yöntemleri (simpleks yöntemi) tartışacağız. Bu dersi bitirdiğinizde
•
•
•
•
iki değişkenli doğrusal programlama problemleri
karar değişkenleri, amaç fonksiyonu
problem kısıt(lama)ları, negatif olmama kısıt(lama)ları
uygun çözüm alanı, en iyi çözüm
gibi konularda bilgi sahibi olabilecek, çok değişkenli doğrusal programlama problemlerinin çözümünde kullanılacak simpleks yöntemine hazırlık olarak
•
•
•
aylak değişkenler, temel ve temel olmayan değişkenler
temel çözümler
uygun temel çözümler, uygun olmayan temel çözümler
gibi kavramları tanıyabileceksiniz.
166 …………………………………………………………………………………………………………………. Ders 9
9.1. İki Değişkenli Doğrusal Programlama Problemleri. Aşağıda, örnekler
üzerinde de göreceğimiz gibi günlük yaşamdan pek çok problem, doğrusal programlama
problemi olarak modellenebilir. Bu dersimizde, iki değişkenli doğrusal programlama
problemlerinin geometrik çözümünü tartışacağız.
Örnek 1. Aşağıdaki problemin matematiksel modelini oluşturalım.
Problem(Üretim Planlaması). Deri giyim üzerinde çalışan bir şirket, ceket ve yelek
üretmektedir. Bir ceket için kesim bölümünde 2 iş saati, dikiş bölümünde 4 iş saati
harcanıyor. Bir yelek için kesim bölümünde 1 iş saati, dikim bölümünde 3 iş saati
harcanıyor. Günlük toplam iş gücü, kesim bölümünde en çok 16 iş saati; dikiş
bölümünde en çok 36 iş saatidir. Her bir ceket 120 TL, her bir yelek de 70 TL kâr bıraktığına ve üretilen tüm ürünlerin satılacağı varsayıldığına göre, şirketin günlük kârının
maksimum olması için kaçar adet ceket ve yelek üretilmesi gerektiğini belirleyiniz.
Bu bir doğrusal programlama problemidir. Verilenleri bir tabloda özetlemek yararlı
olur.
Kesim Bölümü
Dikim Bölümü
Ürün Başı Kâr
Gereken İş Gücü
Ceket
Yelek
2
1
4
3
120 TL
70 TL
Günlük Mevcut
Maksimum İş Gücü
16
36
Bir günde x adet ceket, y adet yelek üretilsin (değişken atama). Bu durumda elde edilecek kâr, K ( x , y ) = 120x + 70 y TL olur (amaç fonksiyonu).
Kesim bölümündeki mevcut iş gücü ve gerekli işgücü bir kısıtlama getirir:
2x + y ≤ 16 .
Benzer biçimde, dikiş bölümünde mevcut ve gerekli iş gücü aşağıdaki eşitsizliği verir:
4 x + 3 y ≤ 36 .
x ve y nin negatif olamayacağı da göz önüne alınırsa, şirketin üretebileceği ceket ve yelek
sayıları, aşağıdaki eşitsizlik sistemini sağlamalıdır.
2x + y ≤ 16
4 x + 3 y ≤ 36


≥0
 x

y ≥0
Doğrusal Programlama …………………………………………………………………………………………. 167
Problemde, K ( x , y ) = 120x + 70 y doğrusal fonksiyonunun yukarıdaki eşitsizlik sisteminin çözüm alanının hangi noktasında maksimum değerini aldığı ve maksimum değerin
ne olduğu sorulmaktadır.
Bu tür problemlerin matematiksel modeli aşağıdaki formatta ifade edilir:
Karar
Değişkenleri
K ( x , y ) = 120x + 70 y fonksiyonunu
 2x + y ≤ 16
 4 x + 3 y ≤ 36


≥0
 x

y ≥0
kısıtlamaları altında maksimize ediniz.
Amaç Fonksiyonu
Problem Kısıtları
Negatif Olmama
Kısıtları
■
Örnek 1’de olduğu gibi, bir doğrusal fonksiyonun bir doğrusal eşitsizlik sisteminin
çözüm alanında aldığı maksimum veya minimum değerin belirlenmesi problemine bir
doğrusal programlama problemi denir. Örnekteki problem iki değişkenli doğrusal
programlama problemidir. Daha çok değişkenli doğrusal programlama problemlerinin
de benzer formatta ifade edilebileceği açıktır.
Doğrusal programlama problemleri, ya da onların matematiksel modelleri yukarıdaki
formatta ifade edilir. Problem modellenirken atanan değişkenlere karar değişkenleri,
maksimum veya minimumu bulunacak fonksiyona amaç fonksiyonu denir. Problemdeki verilerden kaynaklanan eşitsizliklere problem kısıt(lama)ları, değişkenlerin
negatif olamayacağını ifade eden eşitsizliklere de negatif olmama kısıt(lama)ları
denir. Amaç fonksiyonunun belirlenmesi arzu edilen maksimum veya minimum değerine doğrusal programlama probleminin en iyi çözümü denir.
İki değişkenli bir doğrusal programlama probleminin matematiksel modelindeki
doğrusal eşitsizlik sisteminin çözüm alanına (grafiğine) o problemin uygun çözüm
alanı denir.
Bu ders içinde sadece iki değişkenli doğrusal programlama problemleri ele alınacaktır.
168 …………………………………………………………………………………………………………………. Ders 9
9.2. Geometrik Çözüm. Ders 8‘de iki değişkenli bir doğrusal fonksiyonun bir çözüm
alanı üzerinde aldığı maksimum veya minimum değerlerle ilgili sonuçlar elde edilmişti.
Köşe noktası Teoremi (Teorem 8.4.1) ve Teorem 8.4.2 doğrusal programlama problemlerine uyarlanırsa, aşağıdaki ifadeler elde edilir.
Teorem 1. Bir doğrusal programlama probleminin en iyi çözümü varsa, o en iyi çözüm
problemin uygun çözüm alanının köşe noktalarında ortaya çıkar. ■
Teorem 2. a) Bir doğrusal programlama probleminin uygun çözüm alanı boş olmayan
sınırlı bir küme ise, o problemin en iyi çözümü vardır.
b) Bir doğrusal programlama probleminin uygun çözüm alanı sınırsız, amaç fonksiyonunun katsayıları pozitif ise ve amaç fonksiyonunun minimumu isteniyorsa, o takdirde
problemin en iyi çözümü vardır; amaç fonksiyonunun maksimumu isteniyorsa,
problemin en iyi çözümü yoktur. ■
Örnek 1. Önceki kesimde ele alınan üretim planlaması probleminin matematiksel
modeli
K ( x , y ) = 120x + 70 y fonksiyonunu
2x + y ≤ 16
4 x + 3 y ≤ 36


≥0
 x

y ≥0
kısıtlamaları altında maksimize ediniz.
olarak ifade edilmişti. Problemin uygun çözüm alanı aşağıda gösterilmiştir.
y
(0,16)
(0,12)
2x + y = 16
(6,4)
4x +3y = 36
UYGUN
ÇÖZÜM
(0,0) ALANI
(9,0)
(8,0)
x
Doğrusal Programlama …………………………………………………………………………………………. 169
Uygun çözüm alanı boş olmayan sınırlı bir küme olduğundan en iyi çözüm vardır ve
uygun çözüm alanının köşe noktalarında ortaya çıkacaktır.
Amaç fonksiyonu olan K ( x , y ) = 120x + 70 y nin uygun çözüm alanının köşe noktalarındaki değerlerini bir tabloda gösterelim:
Köşe
(0,0)
(0,12)
(6,4)
(8,0)
K(x,y)
0
840
1000
960
Yukarıdaki tablodan görüyoruz ki, amaç fonksiyonunun en büyük (maksimum) değeri
(6,4) köşesinde ortaya çıkmaktadır. Başka bir deyişle, amaç fonksiyonu K(x,y) maksimum değerini x=6 ve y=4 olunca almaktadır.
O halde verilen kısıtlamalar altında, şirketin kârının maksimum olması için günde 6 adet
ceket ve 4 adet yelek üretilmesi gerekir. Şirketin maksimum kârı 1000 TL olacaktır. ■
Örnek problemin çözümü doğrultusunda, iki değişkenli doğrusal programlama problemlerinin geometrik çözümü için aşağıdaki adımlar izlenebilir:
Adım 1. Veri tablosu hazırlanır. Bu, problemin daha iyi anlaşılması ve matematiksel
modelinin kurulmasında yardımcı olur.
Adım 2. Matematiksel model kurulur. Bunun için
a) Karar değişkenleri atanır ve amaç fonksiyonu bu değişkenlerle ifade edilir.
b) Doğrusal eşitsizlik ve/veya eşitliklerden oluşan problem kısıtları ifade edilir.
c) Negatif olmama kısıtlamaları ifade edilir.
Adım 3. Uygun çözüm alanının grafiği çizilir ve en iyi çözümün bulunup bulunmadığına (yukarıdaki teorem doğrultusunda) karar verilir. Çözüm varsa, tüm
köşe noktalarının koordinatları bulunur.
Adım 4. Amaç fonksiyonunun köşe noktalarındaki değerleri bulunur ve bir tabloda
gösterilir. Tablodan yararlanılarak en iyi çözüm belirlenir.
Adım 5 . En iyi çözüm yorumlanır. Problemde sorulan sorular yanıtlanır.
Yukarıdaki adımları izleyerek minimizasyon problemleri için bir örnekle devam edelim:
170 …………………………………………………………………………………………………………………. Ders 9
Örnek 2. Üç farklı üreticiden bir merkeze her gün toplam 36 ton patates taşınmaktadır.
Ton başına taşıma maliyeti birinci üreticiden 40 TL, ikinci üreticiden 30 TL, üçüncü
üreticiden ise 10 TL dir. Taşıyıcı şirketin, 36 tonun tamamını yüklemek için her gün en
fazla 120 dakika zamanı vardır. Bir ton patatesin yüklenmesi, birinci üreticide 1 dakika,
ikinci üreticide 4 dakika, üçüncü üreticide ise 3 dakika zaman almakta ve birinci
üreticiden bir günde en fazla 30 ton, ikincisinden 24 ton, üçüncüsünden ise 18 ton
patates alınabilmektedir. Günlük taşıma maliyetinin en az olması için her bir üreticiden
günde kaç ton patates yüklenmeli ve taşınmalıdır? Taşıma maliyeti en az kaç TL olur?
Çözüm. İlk bakışta üç tane karar değişkeni var gibi görünmesine rağmen problemin matematiksel modeli iki değişkenli doğrusal programlama problemi olarak gerçekleştirilebilir. Bir günde birinci üreticiden x ton, ikinci üreticiden y ton patates yükleneceğini
varsa-yarsak, toplam 36 ton patates yükleneceğinden, üçüncü üreticiden yüklenecek
patates miktarı 36 – (x + y) tondur. Bu durumda günlük taşıma maliyeti,
M( x , y ) = 40x + 30 y + 10(36 − x − y ) = 30x + 20 y + 360
TL olur. Bu, problemin amaç fonksiyonudur.
Problem kısıtlamalarına gelince, zaman kısıtlamasından dolayı
x + 4 y + 3(36 − x − y ) ≤ 120 ⇒ − 2x + y ≤ 12 ,
üreticilerin verebileceği miktarlar üzerindeki kısıtlamalardan dolayı
x ≤ 30 , y ≤ 24 ve 36 − x − y ≤ 18 ⇒ x + y ≥ 18.
Negatif olmama kısıtlamaları x ≥ 0 , y ≥ 0 ve
36 − x − y ≥ 0 ⇒ x + y ≤ 36
da göz önüne alınınca problemimizin matematiksel modeli aşağıdaki gibi kurulur:
M( x , y ) = 30x + 20 y + 360 fonksiyonunu
− 2x + y ≤ 12
 x
≤ 30


y ≤ 24

 x + y ≥ 18
 x + y ≤ 36

≥0
 x

y ≥0

kısıtlamaları altında minimize ediniz.
Doğrusal Programlama …………………………………………………………………………………………. 171
Problemin uygun çözüm alanı aşağıdaki grafikte gösterilmiştir.
y
(12,24)
(6,24)
(2,16)
(30,6)
(0,0)
(18,0)
(30,0)
x
Bu problemde de uygun çözüm alanı sınırlıdır; dolayısıyla, en iyi çözüm vardır. Kaldı ki,
amaç fonksiyonunun tüm katsayıları pozitif olduğundan ve amaç fonksiyonunun
minimum değeri istendiğinden, uygun çözüm alanı sınırlı olmasa da en iyi çözüm
bulunurdu. Amaç fonksiyonu olan M( x , y ) = 30x + 20 y + 360 ın uygun çözüm alanının
köşe noktalarındaki değerlerinin tablosunu yapalım.
Köşe
M(x,y)
(12,24)
1200
(18,0)
900
(30,0)
(30,6)
1260
1380
(2,16)
740
(6,24)
1020
Yukarıdaki tablodan görüyoruz ki, amaç fonksiyonunun en küçük(minimum) değeri
(2,16) köşesinde 740 TL olarak ortaya çıkmaktadır. Bu, problemin en iyi çözümünü
verir. Dolayısıyla, taşıyıcı şirket, birinci üreticiden 2 ton, ikinci üreticiden 16 ton ve
üçüncü üreticiden 18 ton patates yüklerse, taşıma masrafı minimum olur. Minimum
taşıma maliyeti 740 TL dir. ■
172 …………………………………………………………………………………………………………………. Ders 9
Geometrik çözüme üç örnek daha vereceğiz ve daha sonra geometrik çözümden
hareketle değişken sayısı ikiden çok olan doğrusal programlama problemlerinin
çözümünde de kullanılabilecek bir yöntem olan simpleks yöntemi için gerekli bazı
kavramları tanıtarak ön hazırlık yapacağız.
Örnek 3. Bir elektronik şirketi, masa üstü ve diz üstü bilgisayarlar üretmektedir. Bir
masa üstü bilgisayar, 300 TL lik malzeme, 30 saatlik iş gücü; bir diz üstü bilgisayar ise,
600 TL lik malzeme ve 40 saatlik iş gücü gerektirmektedir. Şirketin malzeme için
ayırdığı sermaye, 48000 TL dir ve sahip olduğu iş gücü de 4200 saattir. Şirket ürettiği
bilgisayarların tümüne müşteri bulabilecektir ve bir masa üstü bilgisayardan 150 TL, bir
diz üstü bilgisayardan 250 TL kâr sağlayacaktır. Şirketin kârının maksimum olması için
kaç adet masa üstü ve kaç adet diz üstü bilgisayar üretilmelidir? Maksimum kâr kaç TL
olur?
Çözüm. Problemin matematiksel modelini kurarken, verilenleri bir tabloda özetlemek
yararlı olur.
Malzeme
İş gücü
Ürün başı kâr
Masa üstü
300
30
150 TL
Diz üstü
600
40
250 TL
Mevcut Kaynak
48000
4200
x adet masa üstü, y adet diz üstü bilgisayar üretilsin (değişken atama). Bu durumda elde
edilecek kâr, K ( x , y ) = 150x + 250 y TL olur(amaç fonksiyonu).
Malzeme için ayrılan sermaye bir kısıtlama getirmektedir:
300x + 600 y ≤ 48000 .
Şirketin sahip olduğu iş gücü de bir kısıtlama getirir:
30x + 40 y ≤ 4200 .
Bunlara negatif olmama kısıtları da eklenerek problemimizin matematiksel modeli
aşağıdaki gibi elde edilir:
K ( x , y ) = 150x + 250 y fonksiyonunu
300x + 600 y ≤ 48000
 30x + 40 y ≤ 4200


≥0
 x

y ≥0
kısıtlamaları altında maksimize ediniz.
Doğrusal Programlama …………………………………………………………………………………………. 173
Uygun çözüm alanını aşağıda görülen dörtgen bölgedir.
y
(0,80)
(0,0)
(0,105)
30x + 40y=4200
(100,30)
UYGUN
ÇÖZÜM ALANI
300 x + 600y=48000
(140,0)
(160,0)
x
Uygun çözüm alanı boş olmayan sınırlı bir küme olduğundan, problemimizin en iyi
çözümü (amaç fonksiyonunun maksimum değeri) vardır. Amaç fonksiyonunun maksimum değeri köşe noktalarında ortaya çıkacağından, amaç fonksiyonunun köşe
noktalarındaki değerlerini belirleyerek aşağıdaki tabloyu oluşturuyoruz..
Köşe
(0,0)
(0,80)
(100,30)
(140,0)
K(x,y)
0
20000
22500
21000
Tablodan görüyoruz ki, amaç fonksiyonunun en büyük (maksimum) değeri (100,30)
köşesinde ortaya çıkmaktadır. Başka bir deyişle, amaç fonksiyonu K(x,y) maksi-mum
değerini x=100 ve y=30 olunca almaktadır.
O halde verilen kısıtlamalar altında, şirketin kârının maksimum olması için 100 adet
masa üstü ve 30 adet diz üstü bilgisayar üretilmesi gerekir. Şirketin maksimum kârı 22
500 TL olacaktır. ■
Örnek 4. İki tezgâhı bulunan bir işletmede A ve B diye isimlendirilen iki tür ürün
üretiliyor. Her iki tür ürün için de her iki tezgâhın kullanılması gerekiyor. Eğer birinci
tezgâh sadece A ürünü için çalıştırılırsa, günde 40 birim A nın işini yapabiliyor; eğer bu
tezgâh sadece B ürünü için çalıştırılırsa, günde 60 birim B nin işini yapabiliyor. Benzer
şekilde, eğer ikinci tezgâh sadece A ürünü için çalıştırılırsa, günde 50 birim A; sadece B
ürünü için çalıştırılırsa, günde 50 birim B nin işini yapabiliyor. İşletme, A nın her
biriminden 200 TL, B nin her biriminden de 400 TL kâr sağlamaktadır. İşletmenin
174 …………………………………………………………………………………………………………………. Ders 9
ürettiği tüm ürünleri satabileceği varsayılırsa, günlük kârın maksimum olması için her
tür üründen günde kaç birim üretilmesi gerekir? Maksimum kâr kaç TL dir?
Çözüm. Birinci tezgahın sadece A için kullanılması durumunda 40 birim A işlenebildiğine göre, birinci tezgahta A nın bir biriminin işlenme süresi 1/40 gündür. Benzer
düşünce ile, birinci tezgahta B nin 1 biriminin işlenme süresi 1/60 gündür. Problemin
verilerini bu şekilde yorumladıktan sonra veri tablosuna gerek kalmadan matematiksel
modellemeye geçebiliriz.
Bir günde A ürününden x1 birim, B ürününden x2 birim üretilsin(değişken atama).
Şirketin kârı, x1, x2 cinsinden
TL dir (amaç fonksiyonu).
K ( x 1 , x 2 ) = 250x 1 + 400x 2
1
1
x 1 kısmı x1 birim A üretmek için,
x 2 kısmı da x2 birim B
40
60
üretmek için kullanılacaktır. Buradan
Birinci tezgahta günün
1
1
x1 +
x2 ≤ 1
40
60
eşitsizliği elde edilir. İkinci tezgahtaki işlenme zamanları göz önüne alınınca da
1
1
x1 +
x2 ≤ 1
50
50
eşitsizliği elde edilir. Ayrıca, negatif olmama kısıtlları x1 ≥ 0 ve x2 ≥ 0 da eklenirse
problemin matematiksel modeli şöyle ifade edilebilir:
K ( x 1 , x 2 ) = 250x 1 + 400x 2 fonksiyonunu
1
1
 40 x1 + 60 x2 ≤ 1

 1 x + 1 x ≤1
1
2

50
50
≥0
 x1

x2 ≥ 0

kısıtlamaları altında maksiize ediniz.
Doğrusal Programlama …………………………………………………………………………………………. 175
Şimdi, problemimizin uygun çözüm alanını belirleyelim.
x2
UYGUN ÇÖZÜM
ALANI
(0,50)
(0,60)
(0,0)
1
1
x1 +
x2 = 1
40
60
(20,30)
(40,0)
(50,0)
1
1
x1 +
x2 = 1
50
50
x1
Görüldüğü gibi, uygun çözüm alanı boş olmayan sınırlı bir bölgedir. Amaç fonksiyonu
olan K ( x 1 , x 2 ) = 200x 1 + 400x 2 nin uygun çözüm alanının köşe noktalarında aldığı değerlerle aşağıdaki tabloyu oluşturuyoruz:
Köşe
K(x1 ,x2 )
(20,30)
17000
(0,0)
(0,50)
(40,0)
0
20000
10000
Yukarıdaki tablodan görülmektedir ki, amaç fonksiyonunun uygun çözüm alanında en
büyük (maksimum) değeri (0,50) köşesinde ortaya çıkmaktadır. Dolayısıyla, maksimum
kâr için sadece 50 birim B üretilmelidir. Maksimum kâr 20000 TL dir. ■
Örnek 5. Aşağıdaki doğrusal programlama problemini geometrik yöntemle çözelim.
K ( x 1 , x 2 ) = 20x 1 + 30x 2 fonksiyonunu
2x 1 + x 2 ≤ 20

 x 1 + x 2 ≤ 12

 x 1 + 3x 2 ≤ 30
 x 1 , x 2 ≥ 0
kısıtlamaları altında maksimize ediniz.
176 …………………………………………………………………………………………………………………. Ders 9
Amaç fonksiyonunun verilen kısıtlar altında maksimum değeri istenmektedir.
Uygun çözüm alanını çizelim.
x2
(0,20)
(0,12)
(0,10)
(0,0)
2x1+x2 = 20
(3,9)
x1+x2 = 12
(8,4)
(10,0) (12,0)
x1+3x2 = 30
(30,0)
x1
Uygun çözüm alanı, boş olmayan sınırlı bir küme olduğundan, amaç fonksiyonunun
verilen kısıtlar altında hem maksimum değeri hem de minimum değeri vardır. Amaç
fonksiyonunun köşe noktalarındaki değerlerinden oluşturulan bir tabloya bakıyoruz.
Köşe
(0,0)
(0,10)
(3,9)
(8,4)
(10,0)
K(x1,x2)
0
300
330
280
200
Tablodan görülmektedir ki, amaç fonksiyonunun en büyük (maksimum) değeri uygun
çözüm alanının (3,9) köşesinde 330 olarak ortaya çıkmaktadır. ■
9.3. Simpleks Yöntemine Hazırlık.
İki değişkenli doğrusal programlama
problemlerinin çözümü için kullanılan geometrik yöntem, üç veya daha çok değişkenli
doğrusal programlama problemlerinin çözümü için kullanılamaz. Bununla beraber, bu
çözüm yönteminden yola çıkılarak üç veya daha çok değişkenli doğrusal programlama
problemlerinin çözümünde de kullanılabilecek bir yöntem geliştirilmiştir: Simpleks
Yöntemi. Bu kesimde, iki değişkenli doğrusal programlama problemlerinin geometrik
Doğrusal Programlama …………………………………………………………………………………………. 177
çözümünden hareketle simpleks yöntemine giriş sayılabilecek bir yaklaşım sergileyeceğiz.
Tartışmalarımızı ilk örneğimiz olan “üretim planlaması” problemi üzerinde sürdüreceğiz; ancak, inanıyoruz ki okuyucu bu tartışmaları genel duruma veya başka örneklere
uyarlamakta güçlük çekmeyecektir.
Üretim planlaması probleminin matematiksel modelini, karar değişkenleri için x yerine
x1 ve y yerine x2 yazarak tekrar ifade edelim:
K ( x , y ) = 120x 1 + 70x 2 fonksiyonunu
2x 1 + x 2 ≤ 16

4 x 1 + 3x 2 ≤ 36
 x , x ≥0
2
 1
kısıtlamaları altında maksimize ediniz.
Bu problem, simpleks yöntemini uygulayabileceğimiz bir problem tipidir. Her şeyden
önce amaç fonksiyonunun uygun çözüm alanında aldığı maksimum değer istenmektedir.
Başka bir deyişle, bu bir maksimizasyon problemidir. Ayrıca, problem kısıtlarının tümü
≤ biçimindedir ve bu eşitsizliklerin hepsinin sağ taraf sabitleri negatif olmayan
sayılardır. Bu tür problemlere standart biçimde ≤ kısıtlamalı maksimizasyon problemleri
denir.
Aşağıda örnek problem üzerinde yapacağımız gözlemler tüm standart biçimde≤ kısıt lamalı maksimizasyon problemleri için geçerlidir.
Problem kısıtlaması olan ilk iki eşitsizliğin sol taraflarına yeni değişkenler ekleyerek bu
eşitsizlikleri eşitliğe dönüştürelim ve aşağıdaki doğrusal denklem sistemini elde edelim:
= 16
2x 1 + x 2 + s1

+ s 2 = 36
 4 x 1 + 3x 2
Yeni değişkenler s1 ve s2 ye aylak değişkenler denir.
Üretim planlaması probleminde, eğer günde 3 adet ceket (x1 = 3), 4 adet yelek (x2 = 4)
üretilirse, 2.3+4=10 saatlik iş gücü kullanılmış olur, 6 saatlik iş gücü “aylak” kalır (s1 = 6).
Benzer şekilde, 4.3+3.4=24 saatlik iş gücü kullanılmış olur, 12 saatlik iş gücü “aylak”
kalır (s2 = 12). s1 ve s2 ye aylak değişken denmesinin nedeni budur.
Her iki denklemde de sağ taraf sabitleri pozitif olduğundan, sistemin bir çözümünde
eğer karar değişkenleri x1 ve x2 negatif olmama koşullarını sağlarsa, aylak değişkenler s1
ve s2 de negatif olamaz. Dolayısıyla, doğrusal programlama probleminin en iyi çözümü,
178 …………………………………………………………………………………………………………………. Ders 9
problem kısıtlamalarından aylak değişkenler katılarak elde edilen doğrusal denklem
sisteminin negatif bileşen içermeyen, yani x1, x2, s1, s2 ≥ 0 olan çözümleri arasındadır.
Uygun çözüm alanında en iyi çözümü ararken tüm noktalara değil, sadece köşe
noktalarına bakmamız yeterli olduğu gibi, en iyi çözümü aylak değişkenler katılarak elde
edilen doğrusal denklem sisteminin bileşenleri negatif olmayan çözümleri arasında
ararken de tüm çözümlere bakmamız gerekmeyecektir. Hangi çözümlere bakacağız?
Bunun için bazı tanımlara gereksinim olacak.
Aşağıda vereceğimiz tanımlar herhangi bir denklem sistemi için geçerlidir, ancak biz bu
kavramları daha çok yukarıda olduğu gibi bir doğrusal programlama probleminin
kısıtlamalarından aylak değişkenler yardımıyla türetilen denklem sistemleri ile bağlantılı olarak ele alacağız.
Bir doğrusal denklem sistemi verildiğinde, sistemdeki denklem sayısı kadar değişken
seçilip onlara temel değişkenler, geri kalan değişkenlere de temel olmayan
değişkenler denir.
Bir denklem sisteminde temel olmayan değişkenler yerine sıfır yazılıp temel değişkenler
için çözüm yapılarak bulunan çözümlere temel çözümler denir.
Örnek 1. Yukarıda ele aldığımız
= 16
2x 1 + x 2 + s1

+ s 2 = 36
4 x 1 + 3x 2
sisteminde x1 ve x2 temel değişken olarak seçilirse, elde edilen sistem
2x 1 + x 2 = 16

4 x 1 + 3x 2 = 36
olur ve temel çözüm, Gauss – Jordan yok etme yöntemi ile
2 1 16
1 1 / 2 8 
1 1 / 2 8
1 0 6
4 3 36 → 4 3 36 → 0 1 4 → 0 1 4








x 1 = 6 , x 2 = 4 , s1 = 0 , s2 = 0
olarak elde edilir. Başka bir seçim olarak, eğer x1 ve s1 temel değişken olarak seçilirse,
elde edilen sistem
olur ve temel çözüm,
2x 1 + s1 = 16

= 36
4 x 1
x 1 = 9 , x 2 = 0 , s 1 = −2 , s 2 = 0
Doğrusal Programlama …………………………………………………………………………………………. 179
olarak elde edilir. Böylece elde edilebilecek tüm temel çözümleri aşağıdaki tabloda
gösterilmiştir.
Temel Değişkenler
x1 ,
x1 ,
x1 ,
x2 ,
x2 ,
s1 ,
x2
s1
s2
s1
s2
s2
Temel çözüm
x2
s1
4
0
0
-2
0
0
12
4
16
0
0
16
x1
6
9
8
0
0
0
s2
0
0
4
0
-12
36
Temel çözümlerden her birinde (x1 , x2 ) ikilisine baktığımız zaman bu ikilinin problemin kısıtlamalarını ifade eden eşitsizliklerden ikisine karşılık gelen doğruların kesişim
noktası olduğunu görürüz. Aşağıdaki tablo bu ilişkiyi sergilemektedir:
Temel
Değişkenler
x1
x1 , s1
9
x1 , x2
x1 , s2
x2 , s1
x2 , s2
s1 , s2
Temel çözüm
x2
s1
6
4
8
0
0
0
(6,4)
0
4
(8,0)
0
-2
0
12
4
0
0
0
16
Temel çözümler ve onlara karşılık
gelen (x1,x2) sayı ikililerini problemimizin uygun çözüm alanı ile
birlikte değerlendirdiğimiz zaman
(yanda üretim planlaması probleminin uygun çözüm alanını görüyorsunuz) bir husus daha dikkatimizi çeker ki bu, tartışmamızın
bundan sonrası için çok önemlidir.
Şöyle ki, temel çözümlerden negatif bileşen içermeyen her bir çözüme karşılık gelen (x1,x2) ikilisi uy-
(x1 , x2)
s2
0
16
0
Kesişen Doğrular
2x 1 + x 2 = 16
4 x 1 + 3x 2 = 36
4 x 1 + 3x 2 = 36
x2 = 0
2x 1 + x 2 = 16
x2 = 0
4 x 1 + 3x 2 = 36
x1 = 0
2x 1 + x 2 = 16
x1 = 0
x1 = 0
x2 = 0
(9,0)
0
-12
36
(0,12)
(0,16)
(0,0)
x2
(0,16)
(0,12)
2x1 + x2 = 16
(6,4)
4x1 +3x2 = 36
UYGUN
ÇÖZÜM
ALANI
(9,0)
(8,0)
(0,0)
x1
180 …………………………………………………………………………………………………………………. Ders 9
gun çözüm alanının bir köşe noktasıdır. Bu bağlamda uygun çözüm alanının köşe
noktaları ile temel çözümlerden negatif bileşen içermeyenler arasında bire-bir eşleme
vardır. Temel çözümlerden negatif bileşen içerenlere karşılık gelen (x1,x2) noktaları
uygun çözüm alanının dışında kalan noktalardır.
Bir doğrusal denklem sisteminin temel çözümlerinden negatif bileşen içermeyenlere
uygun temel çözümler, negatif bileşen içerenlere uygun olmayan temel çözümler
denir.
Uygun temel çözümler uygun çözüm alanının köşe noktalarına karşılık gelirler.
Dolayısıyla, doğrusal programlama problemlerinin çözümleri ile ilgili olarak daha önce
ifade ettiğimiz teoremi yeniden şöyle ifade edebiliriz:
Teorem 3. Bir doğrusal programlama probleminin en iyi çözümü varsa, bu çözüm,
uygun temel çözümlerde ortaya çıkar. ■
Örnek 2. Geometrik yöntemle çözdüğümüz son örnek olan
K ( x 1 , x 2 ) = 20x 1 + 30x 2 fonksiyonunu
2x 1 + x 2 ≤ 20

 x 1 + x 2 ≤ 12

 x 1 + 3x 2 ≤ 30
 x 1 , x 2 ≥ 0
kısıtlamaları altında maksimize ediniz.
probleminin problem kısıtlarını aylak değişkenler katarak denklemlere dönüştürürsek
= 20
2x 1 + x 2 + s1

+ s 2 = 12
x 1 + x 2
 x + 3x
+ s3 = 30
2
 1
doğrusal denklem sistemini elde
ederiz. Bu sistemin tüm temel çözümleri yandaki tabloda gösterilmiştir.
Toplam on adet temel çözümden
beş adedi uygun, diğer beş adedi
uygun olmayan temel çözümlerdir.
En iyi çözüm
Temel
Değişkenler
x1, x2, s1
x1, x2, s2
x1, x2, s3
x1, s1, s2
x1, s1, s3
x1, s2, s3
x2, s1, s2
x2, s1 , s3
x2, s2 ,s3
s 1, s 2, s 3
x1
3
6
8
30
12
10
0
0
0
0
x 1 = 3, x 2 = 9, s 1 = 5, s 2 = 0, s 3 = 0
uygun temel çözümünde ortaya çıkmaktadır. ■
x2
9
8
4
0
0
0
10
12
20
0
s1
5
0
0
-40
-4
0
10
8
0
20
s2
0
-2
0
-18
0
2
2
0
-8
12
s3
0
0
10
0
18
20
0
-6
-30
30
Doğrusal Programlama …………………………………………………………………………………………. 181
ALIŞTIRMALAR – 9
1. İki tür ürün üretmekte olan bir şirket, haftalık talebi karşılayacak üretim programı yapmak
istemektedir. Yapılan araştırmaya göre, her iki tür ürün için haftalık toplam talebin en çok 6
birim olduğu anlaşılmıştır. Birinci üründen, haftada en az 3 birim; ikinci üründen, haftada en
az 2 birim üretilme zorunluluğu vardır. Ürünlerden birim başına, sırasıyla, 4 TL ve 5 TL kâr
sağlandığına göre, maksimum kâr için haftalık üretim programı nasıl olmalıdır?
2. Bir okul yöneticisi okul taşımacılığı için otobüs ve minibüs olmak üzere iki çeşit servis aracı
kiralamak istiyor. Kiralanacak otobüslerden her biri 40 öğrenci, minibüslerden her biri 10
öğrenci taşıyabilmektedir. Öğrencilere yardımcı olmak üzere her otobüste 2, her minibüste 1
refakatçi bulunacaktır. Servisleri en az 400 öğrenci kullanacaktır ve refakatçi olarak 30
öğrenci velisi gönüllü olarak görev almayı kabul etmiştir. Aylık kira bedeli bir otobüs için
1000 TL, bir minibüs için 200 TL olduğuna göre aylık taşıma masrafının minimum olması için
her tür araçtan kaçar adet kiralanması uygun olur? Minimum taşıma masrafı ne kadardır?
3. Bir imalatçı, iki tür çadır imal ediyor: A ve B modelleri. Çadır bezi, imalathanenin biçki
bölümünde kesiliyor, dikiş bölümünde dikilip toplanarak piyasaya veriliyor. A modeli
çadırlardan her biri için biçki bölümünde 1 iş saati, dikiş bölümünde 3 iş saati harcanıyor. B
modeli çadırlardan her biri için biçki bölümünde 2 iş saati, dikiş bölümünde 4 iş saati
harcanıyor. Günlük toplam iş gücü, biçki bölümünde en çok 40 iş saati; dikiş bölümünde en
çok 96 iş saatidir. A modeli çadırlardan her biri 7 TL, B modeli çadırlardan her biri de 10 TL
kâr bıraktığına ve üretilen tüm çadırların satılacağı varsayıldığına göre, imalatçının günlük
kârının maksimum olması için her tür çadırdan kaçar adet üretilmesi gerektiğini belirleyiniz.
4. Bir diyet uzmanı, kontrolündeki bir hasta için hazırlayacağı diyette iki tür besin maddesi
kullanacaktır: A ve B besinleri. A besininin her ölçeğinde 10 birim kalsiyum, 10 birim demir,
20 birim A vitamini ve 6 birim kolesterol; B besininin her ölçeğinde 30 birim kalsiyum, 10
birim demir, 10 birim A vitamini ve 8 birim kolesterol bulunmaktadır. Hastanın her gün en az
360 birim kalsiyum, 240 birim demir ve 280 birim A vitamini alması, ancak alacağı kolesterol
miktarının minimum olması için hazırlanacak diyette kaç ölçek A besini ve kaç ölçek B besini
kullanılmalıdır?
5. Bir yatırımcı 150000 TL ile borsadan petrol ve çelik hisseleri ile devlet tahvillerine yatırım
yapmak istiyor. Devlet tahvillerinin %5 getiri sağlayacağı garanti ediliyor; ancak petrol ve
çelik hisseleri değişkendir, zarar da söz konusudur. Muhtemel kayıplara karşı önlem olarak,
yatırımcı petrol hisselerine yaptığı yatırımın 50000 TL yi geçmemesine, petrol ve çelik
hisselerine yaptığı yatırım toplamının devlet tahvillerine yaptığı yatırımdan en çok 25000 TL
fazla olmasına karar veriyor. Petrol hisselerinin %12, çelik hisselerinin %9 getiri sağlayacağı
varsayılarak bu yatırım yapılırsa, maksimum getiri için her bir seçeneğe kaç TL yatırılmalıdır? Maksimum getiri kaç TL olur?
6. Bir madencilik şirketi iki kömür ocağından düşük kalite, orta kalite ve yüksek kalite olmak
üzere üç tür kömür çıkarıyor. A ocağında, bir saatlik iş gücü ile 2 ton düşük kalite, 3 ton orta
kalite ve 1 ton yüksek kalite kömür çıkarılıyor. B ocağında, bir saatlik iş gücü ile 2 ton düşük
kalite, 1 ton orta kalite ve 2 ton yüksek kalite kömür çıkarılıyor. Siparişleri karşılayabilmesi
için, şirketin en az 100 ton düşük kalite, en az 60 ton orta kalite ve en az 80 ton yüksek kalite
kömür çıkarması gerekmektedir. Bir saatlik iş gücünün şirkete maliyeti, A ocağı için 4000
TL, B ocağı için 6000 TL olduğuna göre, minimum giderle siparişlerin karşılanabilmesi için
her bir ocakta kaç saatlik iş gücü kullanılmalıdır? Minimum gider kaç TL olur?
182 …………………………………………………………………………………………………………………. Ders 9
7. K ( x 1 , x 2 ) = 3x 1 + 4 x 2 fonksiyonunu
8. M( x1 , x2 ) = 2x1 + 3x2 fonksiyonunu
kısıtlamaları altında maksimize ve
minimize ediniz.
kısıtlamaları altında maksimize ve
minimize ediniz.
2x 1 + x 2 ≤ 20

 x 1 + 2x 2 ≤ 16
 x , x ≥0
2
 1
9. M( x1 , x2 ) = 20x1 + 30x2 fonksiyonunu
2x 1 + x 2 ≥ 30

 x 1 + x 2 ≤ 20

 x 1 + 2x 2 ≥ 24
 x 1 , x 2 ≥ 0
kısıtlamaları altında maksimize ve
minimize ediniz.
11. K ( x 1 , x 2 ) = 30x 1 + 40x 2 fonksiyonunu
2x1 + x 2 ≤ 30

 x1 + x 2 ≤ 22

 x1 + 2x 2 ≤ 40
 x1 , x 2 ≥ 0
kısıtlamaları altında maksimize ve
minimize ediniz.
2x + 3x 2 + s 1
= 24
13. Yandaki tabloda  1
+ s 2 = 36
4 x 1 + 3x 2
sisteminin tüm temel çözümleri
sıralanmıştır. Bu tabloya göre, her
temel çözüm için
a) temel olan ve temel olmayan
değişkenleri belirleyiniz.
b) bu çözümün uygun temel çözüm
olup olmadığını belirleyiniz.
2x 1 + x 2 ≥ 20

 x 1 + 2x 2 ≥ 16
 x , x ≥0
2
 1
10. K ( x 1 , x 2 ) = 20x 1 + 15x 2 fonksiyonunu
 2x 1 + 3x 2 ≥ 60

 2x 1 + x 2 ≤ 40

− 2x 1 + 3x 2 ≤ 24
 x 1 , x 2 ≥ 0
kısıtlamaları altında maksimize ve
minimize ediniz.
12. K ( x1 , x 2 ) = 20x1 + 15x 2 fonksiyonunu
2x1 + x 2 ≥ 30

 x1 + x 2 ≥ 26

 x1 + 2x 2 ≥ 40
 x1 , x 2 ≥ 0
kısıtlamaları altında maksimize ve
minimize ediniz.
(A)
(B)
(C)
(Ç)
(D)
(E)
x1
0
0
0
12
9
6
x2
0
8
12
0
0
4
s1
24
0
-12
0
6
0
s2
36
12
0
-12
0
0
14. Aşağıdaki eşitsizlik sistemlerinin her birinin çözüm kümesini grafikle gösteriniz. Aylak
değişkenler dahil ederek, eşitsizlikler sistemini denklemler sistemine dönüştürünüz ve
bu sistemin tüm temel çözümlerini bulunuz; uygun temel çözümlerini belirleyiniz. Her
uygun temel çözüme uygun çözüm alanında karşılık gelen köşe noktasını belirleyiniz.
 x 1 + x 2 ≤ 16
a) 2x + x ≤ 20
 1
2
 x ,x ≥ 0
 1 2
2x1 + x2 ≤ 22
b)  x1 + x2 ≤ 12

 x1 + 2x2 ≤ 20
 x1 , x2 ≥ 0
Download

DERS 9 Doğrusal Programlama