TBF 122 - Genel Matematik II
DERS – 11 :  Kısıtlamalı Minimizasyon
Problemleri
Prof. Dr. Halil İbrahim Karakaş
Başkent Üniversitesi
 kısıtlamalı minimizasyon problemleri
Bundan önceki dersimizde standart
biçimde  kısıtlamalı maksimizasyon
problemlerinin çözümü için simpleks yöntemini gördük. Bu derste, problem
kısıtlarının tümü  biçiminde olan ve amaç fonksiyonunun minimum değerinin
istendiği doğrusal programlama problemlerini ele alacağız. Ancak, göreceğiz ki bu iki
problem türü arasında çok yakın bir ilişki vardır.
Problem kısıtlarının tümü  biçiminde olan ve amaç fonksiyonunun minimum
değerinin istendiği bir doğrusal programlama problemine  kısıtlamalı minimizasyon
problemi denir.
Bir  kısıtlamalı minimizasyon problemini çözmek için, o problemin duali olarak
adlandırılan  kısıtlamalı bir maksimizasyon problemi oluşturulur.
Örnek . M( x1 , x 2 )  33x1  60x 2 fonksiyonunu
 3x 1  5x 2

x 1  2x 2


x1


x2

 45
 16
0
0
kısıtlamaları altında minimize ediniz.
Probleminin duali şöyle elde edilir: Problemin kısıtlamaları ve amaç fonksiyonu
 3x 1  5x 2  45

x 1  2x 2  16

33x  60x  M
1
2


3
5
45


1
2
16


A
        


60
1 

 33
biçiminde yazarak buna karşılık gelen sağdaki A matrisini oluşturalım.
M( x 1 , x 2 )  33x 1  60x 2 fonksiyonunu
3x 1  5x 2

 x 1  2x 2

 x1

x2

 45
 16
0
0

 3x 1  5x 2  45

x 1  2x 2  16

33x  60x  M
1
2



3
5
45


1
2
16


A
        


60
1 

 33
kısıtlamaları altında minimize ediniz.
Bu noktada matrislerle ilgili bir kavramın tanımını hatırlatıyoruz:
Bir m n matris A verildiğinde, A nın devriği ( ya da transpozesi) denilen ve AT ile
gösterilen n m matris şöyle tanımlanır: Her i ve j için AT nin i-j girdisi, A nın
j-i girdisidir.
Bu tanımdan kolayca görülebileceği üzere, AT nin i-inci satırı A nın i-nci sütunu ve AT
nin j-inci sütunu A nın j-inci satırıdır.
Örnek olarak, yukarıdaki A matrisinin transpozesi
T
A

3
1
33


5
2
60



        


16
1 
 45

x 2  33
 3x 1 

 5x 1  2x 2  60
45x  16 x  K
1
2

dır. Şimdi, bu matrise karşılık gelen, sağa yazacağımız,  kısıtlamalı sistemi düşünelim.
Buraya kadar yapılanları özetleyelim:
M( x 1 , x 2 )  33x 1  60x 2 fonksiyonunu
3x 1  5x 2

 x 1  2x 2

 x1

x2

 45
 16

0
0
 3x 1  5x 2  45

x 1  2x 2  16

33x  60x  M
1
2


3
5
45


1
2
16

A
        


60
1 
 33



kısıtlamaları altında minimize ediniz.
Orijinal Problem
x 2  33
 3x 1 

 5x 1  2x 2  60
45x  16 x  K
1
2

T
A

3
1
33


5
2
60


        


16
1 

 45
Son sistemi bir maksimizasyon problemi olarak ifade edersek başlangıçtaki problemin
dualini elde etmiş oluruz. Dual problemle orijinalini ayırt etmek için dual problemin
değişkenlerini farklı sembollerle gösteriyoruz.
K ( y1 , y2 )  45 y1  16 y2 fonksiyonunu
y2
 3 y1 

 5 y1  2 y 2

y1


y2

 33
 60
0
0
kısıtlamaları altında maksimize ediniz.
Dual Problem
Dualite İlkesi. Bir minimizasyon probleminin çözüme sahip olması için gerek ve yeter
koşul, o problemin dualinin çözüme sahip olmasıdır. Çözümün var olması durumunda,
minimizasyon problemindeki amaç fonksiyonunun en iyi değeri (minimumu) ile
dualindeki amaç fonksiyonunun en iyi değeri(maksimumu) çakışır.
M( x 1 , x 2 )  33x 1  60x 2
fonksiyonunu
 3x 1  5x 2  45

 x 1  2x 2  16

0
 x1

x2  0

kısıtlamaları altında minimize ediniz.
K ( y1 , y2 )  45 y1  16 y2
Köşe
x2
0 ,9  540
10 ,3  510
0 ,9 
0 ,8 
10 ,3 
0 ,0 
15 ,0 
16 ,0  528
16 ,0 
x1
y2
fonksiyonunu
 3 y1  y2  33

 5 y1  2 y2  60

y1
0


y2  0

0 ,33 
Köşe
0 ,30 
0 ,0 
0 ,0 
11 ,0 
K
0
11 ,0  495
6 ,15 
6 ,15  510
12 ,0 
kısıtlamaları altında maksimize ediniz.
M
y1
0 ,30  480
Yukarıdaki örnekte de görebileceğimiz gibi
• Minimizasyon problemi için en iyi değeri veren çözüm ile onun duali olan
maksimizasyon problemi için en iyi değeri veren çözüm, genellikle farklıdır.
Bu bağlamda önemli bir husus da şudur:
• Minimizasyon problemi için yazılan dual problem, standart biçimde  kısıtlamalı
maksimizasyon problemi ise, simpleks yöntemi ile çözülebilir.
• Eğer minimizasyon probleminin amaç fonksiyonunun negatif katsayısı yoksa, dual
problem, standart biçimde  kısıtlamalı maksimizasyon problemidir.
• Eğer dual problem simpleks yöntemi ile çözülürken aylak değişkenler olarak
minimizasyon probleminin değişkenleri olan x1 , x2 kullanılırsa, minimizasyon
probleminin en iyi değerini veren çözüm de tablodan okunabilir. Çözümün
sonunda ulaşılan simpleks tablosunun son satırında x1 , x2 nin sütunlarındaki
sayılar, sözü edilen çözümü verir.
Yukarıda tartışılan problem için dual problem, standart biçimde  kısıtlamalı
maksimizasyon problemi olduğundan simpleks yöntemi ile çözülebilir. Şimdi, aylak
değişkenleri de yukarıda açıklandığı biçimde seçerek bu çözümü gerçekleştirelim:
K ( y1 , y2 )  45 y1  16 y2 fonksiyonunu
y2  x 1
 33
 3 y1 

x2
 60
 5 y1  2 y 2 
 45 y  16 y 
K 0
1
2

 3 y1  y2  33

 5 y1  2 y2  60

y1
0


y2  0

kısıtlamaları altında maksimize ediniz.
y1
x1  3

x2
5

K 
  45
y2
x1
x2
K
1
1
0
0
2
0
1
0
 16
0
0
1
33

60

0 

1

0


0
1 3
1 3
0
0
1 3
5 3
1
0
1
15
0
1
y1
y1 1

y2 0

K 
0
y1 = 6, y2 = 15 için
y2
x1
x2
11 

5

495

K
0
2
1
0
1
5
2
0
0
10
3
1
K= 510 maksimum.
x1 = 10, x2 = 3 için M = 510 minimum.
6 

15

510

Şimdiye kadar elde edilen sonuçları şöyle özetleyebiliriz:
 kısıtlamalı bir minimizasyon problemini çözerken şu adımlar izlenir:
Adım 1. Problem kısıtlamaları ve amaç fonksiyonundaki katsayılar kullanılarak, A
matrisi oluşturulur. (Amaç fonksiyonunun katsayıları son satıra, çizgi altına
yazılır.)
Adım 2. A matrisinin transpozesi , AT yazılır.
Adım 3. AT nin satırları kullanılarak,  kısıtlamalı maksimizasyon problemi, yani
dual problem yazılır. Dual problem yazılırken, değişkenler için y1 , y2 , . . . gibi
yeni semboller kullanılır.
Adım 4. Dual problem ( standart biçimde  kısıtlamalı maksimizasyon problemi
ise) simpleks yöntemi ile çözülür. Bu çözümde aylak değişkenler için minimizasyon
probleminin değişkenlerinin sembolleri olan x1 , x2 , . . . kullanılır. En son tabloda,
x1 , x2 , . . . ye karşılık gelen sütunların son girdileri minimum değeri veren çözümü
oluştururlar.
Örnek. M(x1, x2 , x3 )= 120 x1 + 60 x2 + 80 x3 fonksiyonunu
 2x 1  3x 2  5x 3  230

 3x 1  2x 2  2x 3  140

x3  0
x1 , x2 ,

kısıtlamaları altında minimize ediniz.
Çözüm: A matrisini oluşturalım ve transpozesini yazalım.
 2

A
3


120
3
5
2
2
60
80
230

140

1 


T
A
 2

3

 5

230
3
2
2
140
120

60

80 

1 
AT ye karşılık gelen maksimizasyon problemini ve başlangıç simpleks tablosunu yazalım.
K ( y1 , y2 )  230 y1  140 y2
2 y1

3 y1

5 y1
 y
1

fonksiyonunu
 3 y2  120
 2 y2  60
 2 y2  80
,
y2  0
kısıtlamaları altında maksimize ediniz.
K ( y1 , y2 )  230 y1  140 y2 fonksiyonunu
2 y1  3 y2

3 y1  2 y2

5 y1  2 y2
 y ,
y2
1

 120
 60
 80
0
kısıtlamaları altında maksimize ediniz.
y1
y2
x1
x2
x3
K
3
1
0
0
0
2
0
1
0
0
x1  2

x2
3

x3  5

K  230
2
0
0
1
0
 140
0
0
0
1
y1
y2
x1
0
1
1
x 1 0

y2 0

y1 1

K 0
x2
2 y1 
3 y2


3 y1 
2 y2


5 y1 
2 y2

 230 y  140 y
1
2

y1
120

60

80 

0 
x3
K
 11 / 4
5/ 4
0
0
5/ 4
 3/ 4
0
0
0
 1/2
1/2
0
0
0
60
10
1
55 

15

10 

4400
x 1 0

x2 0

y1 1

K 0
 x1

 120
 60
x2

x3

 80
K 0
y2
x1
x2
x3
K
11 / 5
1
0
 2/5
0
4 /5
0
1
 3/5
0
2/5
0
0
1 /5
0
 48
0
0
46
1
88 

12

16 

3680
Son tablodan, minimizasyon probleminin
çözümü elde edilir.
x1 = 0, x2 = 60 ve x3 = 10
için M = 4400 minimum.
Örnek. M(x1, x2 , x3 ) = 13x1 + 10x2 + 16 x3 fonksiyonunu
 x 1  x 2  2x 3  24

 3x 1  x 2  x 3  17

x1 , x2 ,
x3  0

kısıtlamaları altında minimize ediniz.
Çözüm: A matrisini oluşturalım ve transpozesini yazalım.
1

A 3


13
1
2
1
1
10
16
24

17

1 


T
A
 1

1

 2

24
3
1
1
17
13

10

16

1 
AT ye karşılık gelen maksimizasyon problemini ve başlangıç sistemini yazalım.
K ( y1 , y2 )  24 y1  17 y2
fonksiyonunu
y1  3 y2  13


y1  y2  10


 2 y1  y2  16

y1 ,
y2  0

kısıtlamaları altında maksimize ediniz.
y1  3 y 2  x 1


y1 
y2  x 2


y2 
x3
 2 y1 
 24 y  17 y 
K
1
2

 13
 10
 16
0
K ( y1 , y2 )  24 y1  17 y2
fonksiyonunu
y1  3 y 2  x 1


y1 
y2  x 2


y2 
x3
 2 y1 
 24 y  17 y 
K
1
2

y1  3 y2  13


y1  y2  10


 2 y1  y2  16

y1 ,
y2  0

 13
 10
 16
0
kısıtlamaları altında maksimize ediniz.
Başlangıç simpleks tablosunu yazarak çözümü sürdürelim.
y1
x1  1

x2
1

x3  2

K   24
y2
x1
x2
x3
K
3
1
0
0
0
1
0
1
0
0
1
0
0
1
0
 17
0
0
0
1
y1
y 2 0

x2 0

y 1 1

K 0
13 

10

16 

0 
y2
0

0

1

0
x1
x2
x3
1
2 5
0
1 5
0
0
1 5
1
2 5
0
0
1 5
0
3 5
0
0
2
0
11
1
5 2
1
0
1 2
0
1 2
0
0
1 2
0
1 2
0
0
1 2
0
5
0
0
12
1
K
2 

1

7 

202 
Son tablodan, minimizasyon probleminin çözümü elde edilir:
x1 = 2 , x2 = 0 ve x3 = 11 için M = 202 minimum.
5 

2

8 

192 
Örnek. Aşağıdaki minimizasyon problemlerinin duallerini oluşturalım ve simpleks
yöntemi ile çözülüp çözülemeyeceğini görelim.
M  20x 1  5x 2 fonksiyonunu
 3x 1  2x 2  6

x1  x2  7


x1 , x2  0

kısıtlamaları altında minimize ediniz.
M  20x 1  5x 2 fonksiyonunu
3x 1  2x 2  6

 x1  x2  7
 x ,
x2  0
1

kısıtlamaları altında minimize ediniz.
Bu problemlerin dualleri, sırasıyla
K  6 y1  7 y2 fonksiyonunu
K  6 y1  7 y2 fonksiyonunu
 3 y1  y2  20

  2 y1  y 2  5

y1 , y 2  0

 3 y1  y2  20

 2 y1  y2  5

y1 , y 2  0

kısıtlamaları altında maksimize ediniz.
kısıtlamaları altında maksimize ediniz.
Görüldüğü üzere, bu dual problemlerden ilki standart biçimde, ikincisi ise standart
biçimde olmayan  kısıtlamalı maksimizasyon problemidir. Dolayısıyla, bunlardan
ilki için simpleks yöntemi ile çözüm yapılabilir; ikincisi için yapılamaz. İlk problemi
simpleks yöntemi ile, ikincisini grafik yöntemi ile çözünüz.
Problem. Bir madencilik şirketi çalıştırdığı iki maden ocağından üç tür maden cevheri
çıkartıyor: düşük, orta ve yüksek kalite. A ocağından, saatte 2 ton düşük, 3 ton orta
ve 1 ton yüksek kalite cevher çıkartılıyor. B ocağından ise, saatte 2 ton düşük, 1 ton
orta ve 2 ton yüksek kalite cevher çıkartılıyor. Siparişlerin karşılanması için en az 100
ton düşük kalite, 60 ton orta kalite ve 80 ton yüksek kalite cevher çıkartılması
gerekmektedir. Bir saatlik işletme gideri, A ocağı için 400 TL, B ocağı için 600 TL
olduğuna göre, siparişlerin minimum giderle karşılanabilmesi için her bir ocak kaç saat
çalıştırılmalıdır? Minimum gider ne olur?
Çözüm. Verileri bir tabloya yerleştirelim:
OCAK
Düşük Kalite
Orta Kalite
Yüksek Kalite
Gider
A
2
3
1
400
B
2
1
2
600
Sipariş
100
60
80
A ocağı x1 saat, B ocağı x2 saat çalıştırılsın. Bu takdirde toplam gider,
M(x1, x2 ) = 400 x1 + 600 x2
TL olur.
Her tür cevher için söz konusu siparişlerden dolayı aşağıdaki problem kısıtları elde
edilir:
2x 1  2x 2  100

3x 1  x 2  60
 x  2x  80
2
 1
Bunlara negatif olmama kısıtları da katılarak problemin matematiksel modeli aşağıdaki
gibi elde edilir.
M(x1, x2) = 400x1+ 600x2 fonksiyonunu
2x 1  2x 2

3x 1  x 2

 x 1  2x 2
 x
, x2
1

Bu probleme karşılık gelen sistem, A matrisi ve onun devriğini yazarak dual problemi oluşturalım. Dual problemin, standart
biçimde bir ≤ kısıtlamalı maksimizasyon
problemi olacağını şimdiden söyleyebiliriz;
çünkü problemimizin amaç fonksiyonundaki katsayıların tümü pozitiftir.
 100
 60
 80
 0
kısıtlamaları altında minimize ediniz.
2x 1 
2x 2  100


3x 1 
x 2  60


x1 
2x 2  80

400x  600x  M
1
2


 2

3
A
 1

400
2
1
2
600
100

60

80 

1 

T
A
 2


2


100
3
1
1
2
60
80
400

600

1 

Dual problemi, yani AT ye karşılık gelen maksimizasyon problemini yazarak çözümü
sürdürelim.
K(y1,y2,y3) = 100y1 +60y2 + 80y3 fonksiyonunu
 2

T
A  2

100
3
1
1
2
60
80
2 y1  3 y 2  y3  400

2 y1  y 2  2 y3  600
 y , y , y 0
2
3
 1
400

600

1 
kısıtlamaları altında maksimize ediniz.
Dual problemin başlangıç sistemi ve başlangıç simpleks tablosu

2 y  3y  y 
1
3
2


2y 
y  2y

1
2
3


 100 y1  60 y 2  80 y3
 400
x
1
 x2
 600
 K  0
y1
x1
x2
K
 2

2


  100
y2
y3
x1
x2
K
3
1
1
0
0
1
2
0
1
0
 60
 80
0
0
1
400

600

0 

y1
y2
 2
x2  2

K  100

x1
y3
x1
x2
K
3
1
1
0
0
1
2
0
1
0
 60
 80
0
0
1

y1 1

x2 0

K 
0
y1

y1 1

y3 0

K 
0
400

600

0 

3/ 2
1/ 2
1/ 2
0
0
2
1
1
1
0
90
 30
50
0
1
y2
y3
x1
x2
5/ 2
0
1
1/ 2
0
2
1
1
1
0
30
0
20
30
1
200 

200

20 000

K
100 

200

26 000

Son tablodan asıl problem için şu çözümü okuyoruz:
x1 = 20 , x2 = 30 için M=26 000 minimum.
Dolayısıyla, minimum gider için, A ocağı 20 saat B ocağı 30 saat çalıştırılmalıdır.
Minimum gider 26 000 TL olur.
Problem. Bir ayakkabı yapım şirketinin iki fabrikası ve iki deposu vardır: Fabrika A,
Fabrika B; Depo I, Depo II. Fabrikalarda üretilen ayakkabılar depolara gönderilerek
oradan dağıtım gerçekleştiriliyor. Bir ayda, A fabrikasında en çok 700 çift, B
fabrikasında en çok 900 çift ayakkabı üretilebiliyor. Her ay, Depo I ` e en az 500 çift,
Depo II ` ye de en az 1000 çift ayakkabı gönderilmesi gerekiyor. Fabrikalardan depolara
bir çift ayakkabının taşıma maliyeti şöyle: A fabrikasından Depo I ` e 3 TL, A
fabrikasından Depo II ` ye 2 TL, B fabrikasından Depo I ` e 2 TL, B fabrikasından Depo
II ` ye 4 TL. Üretilen ayakkabıların fabrikalardan depolara minimum masrafla
taşınabilmesi için her bir fabrikadan her bir depoya kaç çift ayakkabı gönderilmesinin
uygun olacağını belirleyiniz. Minimum masraf ne olur?
Çözüm. Verileri bir tabloya yerleştirelim:
Dağıtım
Depo I
Depo II
Kapasite
Fabrika A
3
2
700
Fabrika B
2
4
900
500
1000
En az gönderilen
Dağıtım
Depo I
Depo II
Kapasite
Fabrika A
3
2
700
Fabrika B
2
4
900
500
1000
En az gönderilen
A fabrikasından Depo I ` e x1 çift, A fabrikasından Depo II ` ye x2 çift, B
fabrikasından Depo I ` e x3 çift, B fabrikasından Depo II ` ye x4 çift ayakkabı
gönderilsin. Bu takdirde taşıma masrafı M(x1,x2,x3,x4)= 3x1+ 2x2+ 2x3+4x4 TL olur ve
problemin matematiksel modeli şöyledir:
M(x1,x2,x3,x4)= 3x1+ 2x2+ 2x3+4x4 fonksiyonunu
 700
 x1  x2

x 3  x 4  900


 x3
 500
 x1

x2
 x 4  1000


 x1 , x2 , x3 , x 4  0
kısıtlamaları altında minimize ediniz.
M(x1,x2,x3,x4)= 3x1+ 2x2+ 2x3+4x4 fonksiyonunu
 700
 x1  x2

x 3  x 4  900


 x3
 500
 x1

x2
 x 4  1000


 x1 , x2 , x3 , x 4  0

 700
 x 1  x 2

 x 3  x 4  900


 x3
 500
 x1

x2
 x 4  1000

3x 1  2x 2  2x 3  4 x 4  M

kısıtlamaları altında minimize ediniz.
 1

1

 0
T
A 

 0
 ____
 700
0
1
0
0
1
1
1
____
0
____
 900
500
3

2
1

2
0

4
1
_____ __ 
1000 1 
0
 1

0

 1
A

 0
 __

 3
1
0
0
1
0
1
1
__
0
__
2
2
 700

 1  900

0
500 

1 1000 
__
__ 
4
1 

0
Dual problemi, yani AT ye karşılık gelen maksimizasyon problemini yazarak
çözümü sürdürelim.
 1

1

 0
T
A 

 0
 ____
 700
0
1
0
0
1
1
1
____
0
____
 900
500
3

2
1

2
0

4
1
_____ __ 
1000 1 
0
K(y1,y2,y3,y4) = -700y1 – 900y2 + 500y3 + 1000y4
fonksiyonunu
 y3
3
  y1

 y1
 y4  2


 y 2  y3
2


 y2
 y4  4


y3 , y 4  0
 y1 , y 2 ,
kısıtlamaları altında maksimize ediniz.
Bu, standart biçimde  kısıtlamalı maksimizasyon problemidir ve simpleks yöntemi
ile çözülebilir.
K(y1,y2,y3,y4) = -700y1 – 900y2 + 500y3 + 1000y4
fonksiyonunu
 y3
3
  y1

 y1
 y4  2


 y 2  y3
2


 y2
 y4  4


y3 , y 4  0
 y1 , y 2 ,
kısıtlamaları altında maksimize ediniz.
 y3
 x1
  y1

 y4  x2
  y1

 y2
 y3
 x3


 y2
 y4
 x4

700 y  900 y  500 y  1000 y
4
1
2
3

3
2
2
4
K 0
Buradan başlangıç simpleks tablosunu yazıp çözümü sürdürelim
y1
x1   1
x 2  1
y2
y3
y4
0
1
0
x1
1
x2
x3
0
x4
0
0
K
0
3
0
0
1
0
1
0
0
0
2

1
1
0
0
0
1
0
0
2
x3  0

x4  0
1
0
1
0
0
0
1
0
4
        
               
K  700 900  500  1000 0
0
0
0
1
0


y1
y2
y3
y4 x1
x2
x 1  1
0
1
0
1
0
0
0
0
1
0
1
0 0
0
0
0
0
1 0
0
0
0
1
0 1
0
0
0 1000 0 0
1

1
0
0

x3  0
1
1
x4 
1
0
 1
K  300 900  500
y4
x3 x 4 K
3 

2

2 

2 
2000









y1
y2
y3
y4
x1
x2
x3
x 1  1
y 4  1
1
0
0
1
0
1
y2
y3
y4
x1
x2
0
0
0
x4
K
0
0
1


0
0
1
0
1
0
0
0
2



1
1
0
0
0
1
0
0
2
y 3 0

x 4 1

1
0
0
0

1
0
1
0
2


     
         

K 300 400
0
0
0
1000
500
0
1
3000


y1
x1 0
y 4 0
1
1
x3
1
x4
K
1
0
3


1
0
1
0
0
0
1
0
4



1
1
0
0
0
1
0
0
2
y 3 0

y1  1

1
0
0
0

1
0
1
0
2


                          
K 

0
100
0
0
0
700
500
300
1
3600


Minimum masraf için, A fabrikasından Depo II `ye 700, B fabrikasından Depo I `e 500,
B fabrikasından Depo II `ye 300 çift ayakkabı gönderilmelidir.
Minimum masraf: 3600 TL.
Download

ve x - Başkent Üniversitesi