Ders Notu 6: Doğrusal Optimizasyon Teknikleri

BÖLÜM 6
LİNEER PROGRAMLAMA
6.1 GİRİŞ
Hedef fonksiyonu ve kısıtlayıcıları, tasarım değişkenlerinin lineer formatında verilen
optimizasyon problemleri Lineer Programlama problemi olarak adlandırılır. Her ne
kadar çoğu mühendislik optimizasyon problemleri lineer olmayan denklemler
vasıtasıyla tanımlansalar da, plastik ve limit analiz gibi problemler lineer olarak
tanımlanır. Ayrıca, bazı lineer olmayan optimizasyon problemleri, lineer programlama
problemlerine dönüştürülerek çözüm yapılır. Çoğunlukla, finans, ekonomi alanlarında
uygulamaları olsa bile yukarıda verilen nedenlerden dolayı mühendislik alanında
kullanım alanı bulmaktadır.
Lineer programlama (LP) probleminin genel formu iki şekilde verilebilir:
Skalar formda:
min f ( x1 , x 2 ,..., x n ) = c1 x1 + c 2 x 2 + ... + c n x n
s.t.
a11 x1 + a12 x1 + K + a1n x n = b1
a 21 x1 + a 22 x1 + K + a 2 x n = b2
(6.1)
M
a m1 x1 + a m 2 x1 + K + a mn x n = bm
x1 ≥ 0, x 2 ≥ 0K x n ≥ 0
Matris formunda:
min f (x) = c T x
s.t.
ax = b
x ≥ 0, b ≥ 0
(6.2)
Bu ifadedeki matris vektörler aşağıda açık bir şekilde verilmiştir.
⎡ x1 ⎤
⎡ b1 ⎤
⎡ c1 ⎤
⎡ a11
⎢x ⎥
⎢b ⎥
⎢c ⎥
⎢a
2⎥
2⎥
2⎥
⎢
⎢
⎢
x=
, b=
, c=
, a = ⎢ 21
⎢M ⎥
⎢M⎥
⎢M⎥
⎢ M
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢
⎣ xn ⎦
⎣bn ⎦
⎣c n ⎦
⎣a m1
a1n ⎤
a 22 L a 2n ⎥⎥
M ⎥
⎥
a m 2 L a mn ⎦
a12
L
(6.3)
6-1
LP probleminin genel özellikleri:
1. Hedef fonksiyonu minimum yapılacak optimizasyon problemi tipindedir.
2. Bütün kısıtlayıcı fonksiyonları eşitlik kısıtlayıcı tipindedir.
3. Bütün tasarım değişkenleri pozitiftir.
4.
0 olmalıdır. Bu şart sağlanmadığı durumda kısıtlayıcı -1 ile çarpılır.
Bu formata uymayan lineer optimizasyon problemleri aşağıdaki dönüşüm metotları
yardımıyla LP problemine çevrilirler.
6.2 STANDART LİNEER PROGRAMLAMA PROBLEMİNİN TANIMI
Standart bir lineer programlama problemi “Eşitlik kısıtlayıcılı ve negatif olmayan
tasarım değişkenleri ile bir hedef fonksiyonun minimize edilmesi” olarak tanımlanır.
Ancak pek çok lineer programlama problemi bu standart tanıma uymamasına rağmen
takip eden bölümde verilen yöntemlerle standart formata dönüştürülebilir.
6.2.1 Lineer Kısıtlayıcılar
Standart LP problemlerinde yalnızca eşitlik kısıtlayıcıları bulunduğundan eşitsizlik
kısıtlayıcıları negatif olmayan slack ve surplus değişkenleri yardımıyla eşitlik
kısıtlayıcılarına çevrilir.
Eğer eşitliksiz kısıtlayıcıları “ ≤ ” tipinde ise negatif olmayan si ≥ 0 slack değişkeni
yardımıyla aşağıdaki gibi eşitlik kısıtlyacısını çevrilir:
ai1 x1 + ai 2 x 2 + ... + ain x n + si = bi
(6.4)
Bu kısıtlı optimizasyon problemlerinde kullanılan si2 slack değişkenin benzeridir.
Orada si2 kullanım sebebi ilave si ≥ 0 kısıtlayıcından kaçınmaktı. LP problemlerinde
si2 kullanımı problemi nonlineer yapacağından sadece si kullanılıp ilave bir kısıtlayıcı
probleme eklenir.
Benzer olarak eğer eşitliksiz kısıtlayıcısı “ ≥ ” tipinde ise negatif olmayan bir si>=0
surplus değişkeni kısıtlayıcıdan çıkartılır. Yani:
ai1 x1 + ai 2 x 2 + ... + ain xn − si = bi
(6.5)
Slack ve surplus değişkenler LP problemlerine ilave bir yük getirirler çünki bu
değişkenlerde tasarım değişkenleri gibi değerleri tesbit edilecek bilinmeyenler olarak
probleme ilave edilir.
6-2
6.2.2 Sınırsız değişkenler
Standart LP problemlerinde değişkenler xi ≥ 0 olmak zorundadır. Bu birçok fiziksel
olay için geçerli olan kısıtlayıcıdır. Örneğin; boyut, ağırlık, alan gibi değişkenler pozitif
değer almak zorundadırlar fakat bazı durumlarda değişkenlerin pozitifliği ve negatifliği
üzerinde herhangi bir sınırlama olmayabilir. Bu durumda, değişken iki negatif
olmayan değişkenin farkı olarak yazılabilir. Şöyle ki, eğer xi işaretinde sınır olmayan
bir değişken ise
xi = xi+ − xi−
(6.6)
olarak verilebilir. Burada xi+>=0 ve xi->=0 dır. Bu ifade optimizasyon problemindeki
tüm fonksiyonlara yazılır ve yeni bir format elde edilir.
Örnek 6.1:
Aşağıda verilen optimizasyon problemini standart LP formuna çeviriniz.
max f ( x) = 2 x1 + 5 x2
s.t.
3 x1 + 2 x2 ≤ 12
2 x1 + 3 x2 ≥ 6
x1 ≥ 0, x2 herhangi bir sınırlama yok
6.3 LP PROBLEMLERİNİN ÖNEMLİ BAZI ÖZELLİKLERİ
LP problemlerinin bazı temel özellikleri aşağıda verilmiştir.
•
LP probleminin hedef fonksiyonu ve kısıtlayıcıları lineer olduğundan
feasible alan konvekstir, dolayısıyla eğer bir optimum çözüm elde
ediliyorsa bu aynı zamanda global optimumdur.
•
Eğer bir çözüm varsa bu feasible alanın sınırında bulunur.
6.3.1 LP problemlerindeki bazı önemli tanımlar
LP problemlerinde kullanılan bazı önemli tanımlar aşağıda verilmiştir.
6.3.1.1 TEPE VEYA UÇ NOKTA (VERTEX OR EXTREME POİNT):
Konveks setteki bir noktadır ve bu nokta setteki diğer iki noktayı birleştiren doğru
üzerinde bulunmaz. Örneğin bir çember üzerindeki noktalar veya bir poligonun uç
noktaları tepe verteks nokta olarak adlandırılır.
6-3
6.3.1.2 FEASİBLE ÇÖZÜM:
Bir LP probleminde aşağıdaki kısıtlayıcıları sağlayan herhangi bir çözüm feasible
çözüm olarak adlandırılır.
ax = b
x≥0
(6.7)
Bir LP probleminin feasible çözümleri bir konveks set oluşturur ve bu konveks setin
ekstrem noktaları temel feasible çözümdür.
6.3.1.3 TEMEL ÇÖZÜM (BASIC SOLUTION):
(n-m) kadar değişkenin değeri sıfıra atanarak elde edilen çözümdür. Burada n
değişken sayısı ve m ise kısıtlayıcı fonksiyon sayısını göstermektedir. Sıfıra atanan
değişkenlere temel olmayan değişkenler (nonbasic variables), diğer değişkenlere ise
temel değişken olarak adlandırılır. Temel çözüm sayısı:
n!
⎛n⎞
⎜ ⎟=
⎝ m ⎠ (n − m)!m!
(6.8)
6.3.1.4 ESAS (BASİS):
Sıfıra eşitlenmeyen değişkenlerin toplamına denir.
6.3.1.5 TEMEL FEASİBLE ÇÖZÜM:
Temel çözümlerden elde edilen sonuçlardan değişkenlerinin negatif olmama
koşulunu sağlayan çözümlere denir.
Örnek 6.2:
Aşağıdaki optimizasyon probleminin tüm temel çözümlerini bulup temel feasible
çözümlerini belirleyiniz.
max. Z = 4 x1 + 5 x2
s.t.
− x1 + x2 ≤ 4
x1 + x2 ≤ 6
x1, x2 ≥ 0
6-4
6.4 SIMPLEX METODU
Simplex metodu LP problemlerin çözümünde en fazla kullanılan metottur. Temel
prensibi; temel feasible çözümleri hedef fonksiyonu minimum yapacak şekilde
taramaktır. Lineer programlama da optimum çözüm için aşağıda belirtilen iki teorem
kullanılır.
Teorem 1: Bir lineer programlama probleminin feasible çözümleri, temel feasible
çözüme karşılık gelen ekstrem noktaları bir konveks set oluşturur.
Teorem 2: Eğer LP probleminin bir feasible çözüme varsa bu problemin temel
feasible çözümü de vardır.
Simplex metoduna geçmeden bu metodu kullanmak için gerekli bazı bilgiler
verilecektir.
6.4.1 Canonical Form (Kononik (doğal) biçim:
Aşağıdaki formata sahip denklem takımı kononik biçim olarak adlandırılır:
x1 + a1, m +1 x m +1 + a1, m + 2 x m + 2 + L + a1, n x n = b1
x 2 + a 2, m +1 x m +1 + a 2, m + 2 x m + 2 + L + a 2, n x n = b2
M
(6.9)
x m + a m, m +1 x m +1 + a m, m + 2 x m + 2 + L + a m, n x n = bm
Bu denklemde x1’den xm’e kadar olan değişkenler denklemlerde yalnızca bir kez
bulunur. Yani x1 sadece 1. denklemde x2 sadece 2. denklemde bulunmaktadır. Matris
formatında kononik denklem aşağıdaki gibi verilir:
I ( m) x ( m) + Qx ( n − m) = b
(6.10)
I ( m) : m-boyutlu birim matrisi
x ( m) = [x1 , x 2 ,K, x m ]T m boyutlu vektör
x ( n − m) = [x m +1 , x m + 2 ,K, x n ]T n-m boyutlu vektör
Q : m × (n − m) x m +1 ile x n arasındaki değişkenlerin katsayılarını içeren matris
b = [b1 , b2 ,K, bm ]T
6-5
6.4.2 Simplex tablosu:
Simplex metodunda kononik biçimdeki denklem takımı bir tabloda verilir. Bu tabloda
kıstlayıcı fonksiyonların yanısıra hedef fonksiyonu da içerir. Bu tablonun genel
gösterimi:
temel
x1
x1
x2
M
xn
1
0
M
0
x2 L xm
0
1
M
0
L
L
L
L
x m +1
0 a1, m +1
0 a 2, m + 1
M
M
1 a m , m +1
xm + 2 L xn
a1, m + 2
a 2, m + 2
M
a m, m + 2
L a1, n
L a 2, n
L
M
L a m, n
RHS
b1
b2
M
bm
Örnek 6.3:
Aşağıdaki optimizasyon problemini kononik biçimde simpleks tablosunda gösteriniz.
Min f = −400 x1 − 600 x2
s.t.
x1 + x2 ≤ 16
1
1
x1 + x2 ≤ 1
28
14
1
1
x1 +
x2 ≤ 1
14
24
x1, x2 ≥ 0
6.4.3 Pivot Adımı:
Simplex metodunda, temel feasible çözümler arasında sistematik olarak arama
yaparak optimum değer bulunur. Bir temel feasible çözümden başlanılarak hedef
fonksiyonun değerini azaltan diğer temel feasible çözümler aranır. Bu ise mevcut
temel değişkenlerin temel olmayan değişkenlerle değiştirilerek elde edilir. Bu pivot
adım ile yapılır ve yeni bir kononik denklem takımı elde edilerek temel çözümler elde
edilir.
Örnek 6.4:
Aşağıda verilen optimizasyon problemindeki x3 ve x4 temel değişkenler alarak
problemin kononik formda yazınız ve x1 ve x4 değiştirerek yeni bir kononik form elde
ediniz.
Max f = 4 x1 + 5 x2
6-6
s.t.
− x1 + x2 ≤ 4
x1 + x2 ≤ 4
x1, x2 ≥ 0
6.4.4 Simplex metodunun temel adımları
Simplex metodunda bir temel çözümden başlanır ve civardaki verteks noktalara
hareket edilir. Bu harekette feasibility korunur ve hedef fonksiyonun değeri azaltılır.Bu
ise temel bir değişkenin temel olmayan bir değişken ile değiştirilerek elde edilir.
Simplex metodu iki temel adımı vardır:
1. Temel değişkenlere çevrilecek temel olmayan değişkenlerin seçimi
2. Temel setten temel olmayan değişken olacak değişkenin seçimi
Simplex metodunun yukarıda verilen temel adımlarına dayanarak aşağıdaki adımlar
takip edilir:
1. Optimizasyon problemi standart LP problemi haline dönüştürülür.
2. Simplex metodu optimum çözümü bulmak için bir başlangıç temel feasible
çözümüne gerektirir. Simplex tablosu temel ve temel olmayan değişkenleri
belirtecek şekilde hazırlanır. Kısıtlayıcı fonksiyonlarında sadece bir kez
bulunan değişkenler temel değişkenler olarak seçilir. Eğer bütün kısıtlayıcılar
“≤” tipinde iseler slack değişkenler temel değişkenler olarak atanır ve bir
başlangıç feasible çözüm elde edilir. Diğer değişkenler temel olmayan
değişkenler olarak Simplex tablosuna yerleştirilir. Eğer kısıtlayıcılar “≥”
biçiminde veya eşitlik kısıtlayıcıları iseler suni değişkenler kullanılmalıdır.
3. optimum çözümde simplex tablosunun hedef fonkisyonu içeren satırında temel
olmayan değişkenlere karşılık gelen değerler negatif olmamalıdır. Eğer bu
değerler pozitif ise optimum çözüm elde edilmiş demektir.
4. eğer hedef fonksiyon satırında temel olmayan değişkenlere karşılık gelen
değerler negatif ise pivot işlemi başlatılır ki bu işlemde temel değişkenlerden
biri temel olmayan değişkenle yer değiştirilir. Bunun için
a. hangi temel olmayan değişkenin seçileceği, hedef fonksiyon satırındaki
temel olmayan değişkenlere karşılık gelen değerlerden mutlak değerce
en büyük olan değişken seçilir.
6-7
b. Hangi temel değişkenin pivot işleminde seçileceği ise; seçilen temel
olmayan değişkenin katsayılarından (pivot sütünu) pozitif değere sahip
olanlar en sağ sütündeki b değerlerine bölünür ve elde edilen
oranlardan hangisi küçük ise buna karşılık gelen temel değişken pivot
işleminde seçilir. Eğer pivot sütunundaki katsayıların hepsi negatif
ise,problem sınırsız bir problemdir ve dolayısıyla hedef fonksiyonu eksi
sonsuza kadar minimize edilir demektir yani optimum çözüm yoktur.
Pratik uygulamalarda bu durum düzgün bir şekilde kısıtlanmayan
problemlerde ortaya çıkar. Dolayısıyla problem formülasyonu gözden
geçirilmelidir.
5. Pivot satır ve sütün seçildikten sonra pivot işlemi yapılacak temel olmayan
değişkenin bulunduğu sütundaki katsayılar, pivot
satırındaki 1 ve diğer
satırdaki değerler 0 olacak şekilde eliminasyon işlemi yapılır.
6. Elde edilen değerlere göre yeniden bir Simplex tablosu oluşturulur
7. Yukarıda verilen işlemler hedef fonksiyon satırındaki, temel olmayan
değişkenlere karşılık gelen katsayılar negatif olmayan değere sahip oluncaya
kadar devam edilir.
Eğer hedef fonksiyon satırında temel olmayan
değişkenlere karşılık gelen katsayılardan en az biri sıfır ise optimizasyon
probleminin birden fazla optimum çözümü var demektir.
Örnek 6.5:
Aşağıda verilen LP problemini çözünüz
Max f = 2 x1 + x2
s.t.
4 x1 + 3 x2 ≤ 12
2 x1 + x2 ≤ 4
x1 + 2 x2 ≤ 4
x1, x2 ≥ 0
6.5 BAŞLANGIÇ TEMEL FEASİBLE ÇÖZÜM (SUNİ DEĞİŞKENLER)
Pek çok tasarım probleminde kısıtlayıcı fonksiyonlar “≤” tipinde bulunabilir. LP
probleminde bu tip kısıtlayıcı fonksiyonlar standart LP problemi haline getirebilmek
için surplus değişkenler eklenmektedir. Surplus değişkenler eklenmesine rağmen
6-8
eğer bir temel çözüm yoksa ve LP problemi “≥” tipinde veya “eşitlik kısıtlayıcısı”
şeklinde ise, çözüm elde edebilmek için negatif olmayan değişkenler eklenir ki
bunlara suni değişkenler denir. Bu değişkenler temel değişken olarak kabul edilir ve
temel çözümlere ulaşılır. Bununla birlikte suni değişkenler optimum çözümde
bulunmamalıdır. Bu tür problemlerin çözümünde aşağıda belirtilen iki aşamalı
Simplex metodu (Two phases Simplex Method) kullanılır:
•
Aşama I: Simplex algoritması kullanılarak LP problemlerinin bir feasible
çözümünün olup olmadığı araştırılır. Eğer feasible çözüm varsa temel
feasible çözüm elde edilir.
•
Aşama II: Simplex algoritması kullanılarak problemin sınırlı olup olmadığı
(bounded) belirlenir. Eğer sınırlı çözüm varsa optimum olan temel feasible
çözüm elde edilir.
Optimum çözümde suni değişkenleri elimine etmek için suni bir hedef fonksiyonu
tanımlanır. Bu fonksiyon suni değişkenlerin toplamı olarak ifade edilir ve temel
olmayan değişkenleri içerecek şekilde aşağıdaki gibi tanımlanır:
m
w = ∑ bi −
i =1
n m
∑ ∑ aij x j
(6.11)
j =1i =1
6.5.1 Aşama I’in Adımları:
1. Slack ve surplus değişkenler kullanılarak LP probleminin standart LP
problemine çevrilir.
2. “>=” tipindeki kısıtlayıcılar ve eşitlik kısıtlayıcıları için suni değişkenler ve suni
değişkenlerin toplamından oluşan suni hedef fonksiyon (w) tanımlanır. w
sadece temel olmayan değişkenlerden oluşacak şekilde dönüşüm yapılır.
3. Simplex tablosu oluşturulur ve en son satır suni hedef fonksiyonunu içerir.
4. En son satırdaki en küçük (negatif) değer aranır. Bu sütunu gösteren değer
temel değişken olacaktır.
5. RHS’deki oranlar bulunur ve en küçük değere sahip olan temel değişkenler bir
önceki maddede bulunan değişkenle yer değiştirecektir.
6. Pivot işlemleri yapılır.
7. Eğer son satırdaki negatif değer varsa Adım 4’e gidilir yoksa Adım 8’e gidilir.
6-9
8. Eğer son satırdaki değerlerin hepsi negatif olmayan değerlere sahip ve w
sıfıra eşit ise Aşama I tamamlanmıştır. Eğer son satırdaki değerlerin hepsi
negatif olmayan değerlere sahip fakat w sıfırdan farklı ise problem
infeasibledır.
6.6 AŞAMA II’NİN ADIMLARI
Aşama I’de elde edilen son satır hedef fonksionu ile değiştirilir ve aşağıda verilen
adımlar gerçekleştirilir:
1. Aşama I deki adım 4 ile aynı
2. Aşama I deki adım 5 ile aynı
3. Aşama I deki adım 6 ile aynı
4. Eğer son satırda negatif olmayan değerler varsa adım 1’e aksi halde son tablo
optimum çözümü içermektedir.
Simplex metodu aşağıdaki sonuçlara varmayı garanti ettiğinden LP problemlerinin
çözümünde oldukça güçlü bir yöntemdir:
•
Eğer problem infeasible ise simplex metodu bunu belirtir
•
Eğer problem sınırsız ise (unbounded) simplex metodu bunu belirtir
•
Eğer problemin bir çözümü varsa bu global optimumdur.
•
Eğer birden fazla çözüm varsa simplex metodu buna işaret eder.
Örnek 6.6:
Aşağıda verilen LP problemini çözünüz
Max z = y1 + 2 y 2
s.t.
3 y1 + 2 y 2 ≤ 12
2 y1 + 3 y 2 ≥ 6
y1 ≥ 0
6-10