Ders Notu 6: Doğrusal Optimizasyon Teknikleri
Transkript
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