Embedded Files
Bir atölyedeki ürünlerin makine gereksinimleri ve makinelerin haftalık saat limitleri aşağıdaki tabloda verilmiştir:
NOT: Bu örneğin orijinal kaynağı Rama Murthy'nin "Operational Research" kitabıdır. Makine adlarını doğru çevirme zahmetine katlanmayıp, uydurma adlar verdiğimizi hatırlıyoruz.
Problem çözümünün ilk adımı değişkenleri tanımlamaktır.
Bu adımda tek yapmanız gereken şey, optimum performansı sağlamak için değiştirebileceğiniz niceliklere sırayla x1 , x2 , x3 , ... adlarıyla bilinmeyenler olarak semboller atamaktır.
Bu örnek problemde ana soru üç üründen hangisinin ne kadar üretileceğidir. Demek ki değişkenler de bu üç ürünün üretim miktarları (bu durumda üretim adetleri) olacaktır:
Değişkenler:
x1 , x2 , x3 (üç tür ürünün üretim adetleri)
İkinci adım performans fonksiyonunu yazmaktır.
Bunun için hedef olarak hangi nicelik seçmişseniz, onun bir matematiksel ifadesini yazmanız gerekecektir.
Bu örnek problemde hedef bu üç üründen elde edilebilecek toplam kârı mümkün olduğunca yüksek tutmak olduğuna göre, performans fonksiyonu olarak toplam kârın matematiksel bir ifadesini yazmalısınız.
Üretim sayılarına sırasıyla x1 , x2 , x3 sembolleri atadığınıza göre, toplam kâr fonksiyonunu üretim sayılarıyla birim kârlarının çarpımlarının toplamı olarak yazarsınız.
Birim kârlar 50, 20 ve 25 bu fonksiyonda x1 , x2 , x3 değişkenlerinin katsayıları olarak gözükecektir:
Performans fonksiyonu:
Z = 50 x1 + 20 x2 + 25 x3 (Toplam kâr)
Üçüncü adım problem kısıtlarını yazmaktır.
Kısıtlar da performansı etkileyen değişken değerlerine bağlı olan başka niceliklerin alabileceği sınır değerlerin matematiksel ifadeleridir.
Bu örnek problemde üç ürünün üretimlerinin gerektirdiği makinelerin kullanılabilecekleri saatlerin sınır değerleri başlıca kısıtlardır.
Üretim sayılarıyla adet başına harcattıkları kullanım saatlerinin çarpımlarının toplamlarını yazarak bu kısıt ifadelerini oluşturursunuz.
Üretim birimi başına kullanım saatleri bu kısıt ifadelerinde x1 , x2 , x3’ün katsayıları olarak gözükürler.
Sınır değerler de üst sınır ise ≤ , yok alt sınır ise ≥ den sonra ifadenin sağ tarafında yer alırlar:
Kısıtlar:
9 x1 + 3 x2 + 3x3 ≤ 500 (delici saat limiti)
5 x1 + 4 x2 ≤ 350 (torna saat limiti)
3 x1 + 2 x3 ≤ 150 (taşlayıcı saat limiti)
Bu ifadeleri matris yöntemleriyle çözülebilir bir doğrusal denklem sistemine dönüştürmek için kısıt ifadelerindeki eşitsizlikleri birer eşitliğe dönüştürmelisiniz.
Performans fonksiyonunu için bu gerekmez bile.
Tek yapacağınız şey, Z eşitliğinde sağ taraftaki x1 , x2 , x3’’lü terimleri sol tarafa almaktır.
O terimler işaret değiştirerek sol tarafa geçtiklerinde, sağ tarafta 0 kalır. Bu matematiksel ifade zaten bir denklem (eşitlik) idi. Böylece eşitliğin sağ tarafını 0 yapmış olursunuz. ,
Her kısıt ifadesindeki toplamı sağdaki üst sınıra tamamlayacak bir boşluk değişkeni (slack variable) eklersiniz. O zaman üst sınır belirten her eşitsizliği bir eşitlik şeklinde yazabilirsiniz.
Daha önceden üç bilinmeyen sembolü yarattığınıza göre, yeni değişkenlere yeni semboller atayacaksınız:
x4 , x5 , x6 , ...
Bu sembollerden her kısıt ifadesi için bir tane eklersiniz. Bunların her birinin katsayısı 1 olacaktır, yani her boşluk değişkeni kendi başına gözükecektir.
Eğer bir kısıt ifadesinde üst sınır değil de bir alt sınır verilmiş olsaydı, o zaman boşluk
değişkeninin işareti eksi olurdu. Bunun nedeni boşluk değişkenlerinin değerlerinin pozitif
olması gerekliliğine dayanarak çözüm yapacak olmanızdır.
Simplex tablo çözümün yöntemini izlemek için problem denklem sistemindeki katsayıları bir matris düzeninde yazacaksınız.
Performans fonksiyonu değeri Z ilk bilinmeyen olarak en sol sütunda yer alır.
O sütunda, Z’nin katsayısı her denklemde neyse, o katsayı gözükür.
Tabloda ilk satıra da performans fonksiyonundan elde edilen denklem konur.
Problemde asıl bulunması gereken değişken değerleri, bu örnek problemde üç ürünün üretim sayılarına karşılık gelen değişkenler, sonraki üç sütunda yer alır.
Daha sonraki sütunlarda ise sırasıyla kendi eklediğimiz boşluk değişkenleri yer alır.
Boşluk değişkenleri performans fonksiyonunda gözükmedikleri için ilk satırdaki katsayıları 0 olacaktır.
Kısıt ifadelerinin her birinde yalnızca bir boşluk değişkeni yer aldığı için de o satırlarda sırasıyla birinin katsayısı 1, diğerlerininki 0 olacaktır.
Tablo çözüm adımlarını doğru uygulayabilmek için, boşluk değişkenlerini hangi kısıtlar için eklemişseniz, kısıtlardan elde ettiğiniz denklemleri o sırayla tabloya eklemelisiniz.
Örneğin, ilk boşluk değişkeni x 4 ’ü torna kullanım saati kısıtını eşitliğe dönüştürmek için kullanmıştınız.
Bu değişkeni performans fonksiyonu değeri Z ve asıl üç değişkenden sonraki beşinci sütun olarak, o denklemin katsayılarını performans fonksiyonu denkleminden sonraki ikinci satır olarak ekleyeceksiniz.
İkinci boşluk değişkeni x 5 ’i de taşlayıcı kullanım saati kısıtından elde ettiğimiz denklemde kullanmıştınız.
Bu değişkeni altıncı sütun, onun gözüktüğü kısıt denklemini de üçüncü satır olarak ekleyeceksiniz.
Bu eklemeler böyle devam edecektir.
Sonuçta elde edeceğiniz simplex tablosu aşağıdaki gibi olacaktır:
Bu adımları izleyerek, problem sunumunun eklemeli formunu şu şekilde oluşturursunuz:
Simplex tablosunun nasıl oluşturacağınızı daha kolay göresiniz diye, eklemeli formun eşitliklerini aynı değişkenli terimler alt alta gelecek şekilde oluşturduk. Simplex tablosunda aynı değişkenli terimleri yalnızca katsayılarını alır ve bu katsayıları matris sütunlarına yazarsınız:
Simplex tablo çözümünü önceki iki değişkenli kapı-pencere problemindeki adımları izleyerek gerçekleştirirsiniz. İlk adımda ilk satıra koyduğunuz hedef fonksiyon eşitliğinde negatif katsayısı (mutlak değer olarak) en büyük olan değişkene ait sütunu "pivot sütun" olarak seçersiniz:
Pivot sütun olarak x1 değişkenine ait sütunu seçtiniz, çünkü ürün-1'in birim kârı daha yüksekti ve bu üründen üretmekle hedef fonksiyon (toplam kâr) değerini en çabuk yükselteceksiniz.
Yine en sağdaki (eşitliklerin sağ taraflarındaki değerleri içeren) sütun değerlerini pivot sütun değerlerine oranlayacaksınız. En küçük oranı veren satırı da "pivot satır" olarak seçeceksiniz Hatırlarsanız, bunu yaparak hangi kısıtın pivot sütunda seçtiğiniz değişkenin artışını an fazla sınırladığını bulmuş olacaksınız.
Bu örnekte pivot satır olarak taşlayıcı tezgahının kullanım kısıtına karşılık gelen son satırı seçtiniz. Bulduğunuz oran 50 aslında bu tezgahın 150 saatlik kullanım sınırlaması nedeniyle en kârlı ürün olarak seçtiğiniz ürün-1'den en fazla 50 birim üretebileceğiniz anlamına geliyor.
Bu adımda temel ve temel olmayan değişken grupları arasında da bir yer değiştirme yapıyorsunuz. Çözümde asıl hedefiniz olan x1 , x2 , x3 başlangıçta temel olmayan değişkenlerdi. Onların ilk değerleri 0'dı. Temel değişkenlerse boşluk değişkenleri x4, x5 ve x6'dır. Dikkat ederseniz, onların sütunlarındaki katsayılarının biri 1, diğerleri 0'dır. Ürün-1'i bu adımdaki en kârlı ürün olarak seçtiğinizde onun üretim değerine karşılık gelen x1'i temel değişken statüsüne geçirme kararı vermiş oldunuz.
x1'e temel değişken statüsü verirken, şu anki temel değişkenlerden birini de temel olmayan durumuna düşürmeniz gerekiyor. Bu örnekteki ilk adımda temel değişken statüsünü kaybedecek olan değişken x6'dır. Pivot satır olarak seçtiğiniz son satırdaki katsayısı 1'dir; oradan anlayın hangi temel değişkenin x1 ile yer değiştireceğini. Problem tanımını hatırlarsanız, x6 taşlayıcı tezgahın boş kaldığı saat sayısını ifade ediyordu. Bu değişkenle x1'i yer değiştirtirtirken, aslında taşlayıcı tezgahın 150 saatlik boşluğunu ürün-1'den 50 birim üretmeye adamış oluyorsunuz. Yani bu tezgahın boşluğunu sıfırlamış oluyorsunuz. Eh, artık anlamamışsanız da bizden bu kadar.
Pivot satır ve pivot sütunun kesiştiği hücredeki değer 3'dür. Bu da ürün-1'in taşlayıcı tezgahında harcattığı saat sayısıdır. Bu 3 "pivot değer" dir. Bir sonraki adımda pivot satır değerlerini bu pivot değere böleceksiniz:
Sonraki adımda da pivot sütundaki (pivot değer hariç) değerleri sıfırlayacak eliminasyonları gerçekleştireceksiniz:
Eliminasyonları yaparak pivot sütunda yalnızca bir tane 1 bıraktınız ya, bu sütunda yer alan x1 değişkenine temel değişken statüsü vermiş oldunuz. Eşitliklerin sağ taraf değerlerini veren son sütundaki değerlere de dikkat edin:
• Hedef fonksiyon eşitliğini temsl eden ilk satırın sağ taraf değeri 2500 oldu, çünkü taşlayıcı tezgah kısıtının izin verdiği 50 birim ürün-1 üretimiyle toplam kârınız (şimdilik) 2500'dür.
• 50 birim ürün-1 üretimi için delici tezgahı 9*50 = 450 450 saat, torna tezgahı da 5*50 = 250 250 saat çalışacaktır. Bu kısıtlara karşılık gelen satırların sağ taraf değerleri 50 ve 100 bu tezgahların kalan boş saatleridir.
Şu anki haliyle tablo aşağıdaki gibidir:
Simplex tablo çözümünün ikinci adımında yeni bir pivot sütun seçeceksiniz. O da şu an için negatif katsayısı (mutlak değer olarak) en büyük olan x2'ye ait sütun olacaktır. Sağ taraf değerleriyle pivot sütun değerlerini oranlayarak da pivot satırı belirleyeceksiniz.
Pivot satırı belirlemek için oran hesaplarken pivot sütundaki 0 veya negatif değerleri atlarsınız. Yukarıda son satırı dikkate almayışınızın nedeni budur.
Seçtiğiniz pivot satırdaki katsayısı 1 (ama diğer satırlardak katsayıları 0) olan temel değişken x4'dür. Yani bu aşamada x2'ye temel değişken statüsü verirken, ona x4 ile yer değiştirtmiş oluyorsunuz. Pivot satır aslında delici tezgah kısıtına karşılık geliyordu. Bu tezgahın kalan 50 saatlik kullanımını mümkün olduğunca ürün-2'den üretmeye adamış oluyorsunuz. O da size 50/3 = 16,6667 birim üretim imkanı veriyor.
Bu kez de pivot değer 3'dür. Pivot satır değerlerini bu değere bölüp eliminasyonları gerçekleştirin:
• Pivot sütun değeri 0 olan son satır için eliminasyona gerek yoktu. Bu satır taşlayıcı tezgah kısıtıyla ilgiliydi ve o tezgah zaten ürün-2 üretiminde yer almıyordu.
• Öte yandan, pivot satır olarak seçtiğiniz ikinci satırın sağ taraf değeri 16,667 oldu ki bu da delici tezgahın kalan 50 saatinde 50/3 = 16,6667 16,667 birim üretim olacağı anlamına geliyor.
• Torna tezgahı kullanım kısıtına karşılık gelen üçüncü satırın sağ taraf değeri de 33,3333 oldu ki bu da torna tezgahının kalan 100 saatinin 4*16,6667=66,6668 saati ürün-2 üretimine harcandıktan sonra kalan kullanım saatidir.
• Hedef fonksiyon eşitliğine karşılık gelen ilk satırın sağ taraf değeri 2983,3 olmuştur ki bu da 50 birim ürün-1 ve ek olarak 16,6667 birim ürün-2 üretimiyle elde edeceğiniz yeni toplam kâr değeridir.
Simplex tablosunun şu anki haline bakarak, bir pivot sütun seçimi daha yapacaksınız:
Sonra yine pivot satırdaki değerleri pivot değere bölecek ve eliminasyonları gerçekleştireceksiniz:
Asıl ilgilendiğiniz ilk üç değişkeni, yani ürünler için üretim miktarlarını belirlediniz gibi, ama hala da hedef fonksiyon satırında katsayısı negatif olan bir değişken var. O da boşluk değişkeni x4 . Bu da eriştiğiniz bu çözümün henüz optimal (koşulları en iyi sağlayan) çözüm olmadığını gösteriyor. Bir kez daha pivot sütun ve pivot satır belirleyecek ve eliminasyonları yapacaksınız. Bu son adımda pivot satırın son satır olacağını şimdiden görüyorsunuz. Pivot sütun değeri negatif olan satırları bir kenara atınca o kalıyor zaten. O satırda yer alan temel değişken de x1 idi. İlk adımda da pivot satır bu son satırdı ve x1 o anki temel değişken x6 ile yer değiştirmişti. Şimdi de x4 temel değişken statüsünü x1'in elinden alacak. Sizin anlayacağınız, ürün-1 en kârlı ürün gibi gözükse de kaynak kullanımı diğer ürünlere göre fazla oluşu nedeniyle kâr avantajını kaybediyor. Özellikle delici tezgahı fazla kullanan bu ürünün üretimini bırakıyor ve onun yerine delici tezgahın bir parça boş kalmasına razı oluyorsunuz. O adımı da yapın ve görün son değerler ne olacakmış.
Page updated
Report abuse