Yöneylem Araştırması Primal Simpleks Yöntemi

Daha önceki konularımızda yöneylem araştırmasına giriş yapmıştık(bkz: Yöneylem Araştırması ve Endüstri Mühendisliği ) ve Yöneylem araştırmasında Grafik Çözümünden (bkz: Yöneylem Araştırması Grafik Çözümü) bahsetmiştik. Bu yazımızın konusu ise Yöneylem Araştırmasında Primal Simpleks Yöntemi’dir.

Grafik çözüm yönteminde bildiğiniz üzere en fala 2 kısıtlı modellerde işlem yapabiliyorduk. Eğer modelimizdeki kısıtlarımız 2’den fazla ise şu an için öğreneceğimiz Primal Simpleks yöntemini ya da ilerde öğreneceğimiz Büyük M Yöntemi, Dual Simpleks Yöntemi ve İki Aşamalı Yöntemi kullanabiliriz.

  • Primal Simpleks bahsettiğimiz üzere 2 ya da  daha fazla değişken bulunan (X1, X2, X3..XN) modellerde kullanılabilir.
  • Ekstremum noktalarda yani, köşe noktalarda çözüm arar.
  • Ekonomik Yorumlara ve Duyarlılık Analizi’ne imkan verir.

Fakat Primal Simpleks yöntemi bütün matematiksel modellere uygulanamamaktadır. Primal Simpleks yöntemini uygulayabilmek için;

  1. Kısıtların sağ taraf değerleri negatif olmamalıdır.
  2. Tüm kısıtlar küçük eşittir “<=” şeklinde olmalıdır.

Primal Simpleks yöntemi ile çözüm yapabilmek için modelimizi standart forma çevirmemiz gerekmektedir. Daha anlaşılır olması için bir model kurup onun üzerinden anlatıma devam etmekte fayda var.

 

Model Sorusu;

Bir oyuncak firması oyuncak asker ve oyuncak bebek üretmektedir. Oyuncak asker için 15 TL’lik hammadde ve 2.5 TL’lik işçilik kullanılmaktadır. Oyuncak bebek için ise 10 TL’lik hammadde ve 5 TL’lik işçilik kullanılmaktadır.

Haftalık kullanılabilecek hammadde miktarı 150 TL’dir ve İşçi masrafı için ayrılan bütçe 55 TL’dir.

Oyuncak askerden elde edilen kar 3 TL, oyuncak bebekten elde edilen kar ise 4 TL’dir. Firmanın maksimum kar elde etmesi için gereken modeli kurarak Primal Simpleks yöntemi ile çözünüz.

 

Matematiksel Model:

Öncelikle değişkenlerimizi Xn türünden isimlendirmemiz gerekmektedir.

X1 = Oyuncak Asker
X2 = Oyuncak Bebek

Bizden istenen maksimum kar olduğu için amaç fonksiyonumuz Max Z olacaktır.

Max Z = 3X1 + 4X2

Hammadde Kısıtı;

15X1 + 10X2 <= 150

İşçilik Kısıtı:

2.5X1 + 5X2 <= 55

Her zaman olduğu gibi X1 ve X2 negatif olamaz.

X1,X2 >=0

 

Standart Forma Çevirme

Standart Formun en temel özelliği bütün kısıtların “=” şeklinde olmasıdır. Eğer küçük eşittir(<=) ya da büyük eşittir(>=) şeklinde bir kısıt varsa “=” formuna dönüştürülmesi gerekir.

Hiçbir değişken negatif olamaz, hepsi non-negatif değerler olmak zorundadır. Eğer negatif bir değer var ise -1 ile çarpılarak non-negatif forma dönüştürülür.

Amaç fonksiyonu maksimizasyon ya da minimizasyon olabilir.

İlk olarak kısıtların “=” formuna çevrilmesini ele alalım

Eğer yazdığımız kısıtlarımız küçük eşittir (<=) formunda ise kısıtın sol tarafına Dolgu değişkeni eklenir.

Eğer yazdığımız kısıtlarımız büyük eşittir (>=) formunda ise kısıtın sol tarafından Artık değişken çıkarılır.

 

Matematiksel modelimizdeki Hammadde kısıtını ve işçilik kısıtını standart formda yazarsak;

15X1 + 10X2 <= 150   >>>  15X1 + 10X2 + X3  + 0X4      =150

2.5X1+ 5X2 <= 55       >>> 2.5X1+ 5X2    + 0X3 + X4        = 55

Hammadde kısıtına X3 dolgu değişkenini işçilik kısıtına ise X4 dolgu değişkeninin ekledik. Değişkenleri sadece bir kısıta ekleyemiyoruz bu nedenle bir değişkeni eklediğimiz kısıtın dışındaki kısıtlara 0 katsayıyı ile ekleyerek işlevsiz kılıyoruz. Ayrıca burada dikkat edilmesi gereken bir diğer nokta ise aynı türden olan bütün kısıtların alt alta gelecek şekilde yazılmasıdır. Bu ileriki konularda duyarlılık analizi yaparken kullanılacak olan birim matris için önemli bir noktadır.

Modelimizde büyük eşittir “>=” şeklinde bir kısıt yok ama olsaydı artık değişken çıkarmamız gerekmekteydi.

Mesela hammadde kısıtımız 15X1 + 10X2 >= 150 olsaydı artık değişken çıkarılmış hali;

15X1 + 10X2 – X3  = 150 olur. –X3 artık değişkenimizdir.

 

Matematiksel modelimizde negatif bir kısıt yok ama eğer olsaydı şu şekilde çözecektik;

2X1 + 3X2 – 7X1 = -5 gibi bir kısıtın olduğunu varsayalım. Bu durumda kısıtımızı -1 ile çarpmamız gerekmektedir.

Kısıtın yeni hali;

-2X1 – 3X2 + 7X1 = 5 olur.

Eğer büyük ya da küçük eşittir şeklinde yazılmış bir kısıtı -1 ile çarparsak eşitsizliğin yönü de değişmek zorundadır.

2X1 + 3X2 – 7X1 <= -5  >>>> -1 ile çarpılır >>>>>>  -2X1 – 3X2 + 7X1 >= 5 olur.

Bu bilgiler ışığında matematiksel modelimizi Standart Forma dönüştürdüğümüzde aşağıdaki gibi olmaktadır.

 

Standart Form;

Amaç Fonksiyonu;

MaxZ = 3X1 + 4X2

Kısıtlar:

15X1 + 10X2  + X3  + 0X4       = 150

2,5X1 + 5X2   + 0X3 + X4          = 55

X1 , X2, X3, X4 >= 0

Not: X3 ve X4 doldu değişkenlerinin birim matris oluşturmasına dikkat ediniz.

 

Standart Forma çevirdiğimiz matematiksel modelimizi artık başlangıç tablosuna geçirebiliriz. Tablonun formatı şu şekildedir.

Başlangıç Tablosu

Tabloda ilk satıra bütün değişkenleri sırasıyla yazıyoruz. İlk sütunda ise Temelde olmayan değişkenler ve Z satırı yer almaktadır. Temelde olmayan değişkenler demek Amaç fonksiyonunda olmayan fakat bizim kısıtlara eklediğimiz değişkenlerdir. Kullandığımız matematiksel model için bu değişkenler X3 ve X4 değişkenleridir ve tabloya yerleştirme sıraları önemlidir.

Z Satırına amaç fonksiyonunda yer alan değişkenlerin katsayılarını başlarına eksi koyarak yazacağız.

X3 ve X4 değerlerini ise değer aldıkları denklemlerden çekmemiz gerekmektedir.

15X1 + 10X2  + X3  + 0X4       = 150             1. Denklem

2,5X1 + 5X2   + 0X3 + X4          = 55             2. Denklem

 

X3 satırı için 1. Denklemde X1, X2, X3 ve X4’ün katsayı değerlerini kendi sütunlarına ve eşitliğin karşı tarafındaki değeri ise Çözüm sütununa yazıyoruz.

X4 satırı için 2. Denklemde X1, X2, X3 ve X4’ün katsayı değerlerini kendi sütunlarına ve eşitliğin karşı tarafındaki değeri ise Çözüm sütununa yazıyoruz.

X3 ve X4 ‘ün birim matris oluşturacak şekilde yerleştirilmesi gerektiğini söylemiştik. Görüldüğü üzere birim matrisimiz oluşmuştur.

Tablomuzda Z satırında negatif değerlerimiz(-3 ve -4) var. Modelimiz maksimizasyon olduğundan dolayı Z satırında temelde olmayan değişkenlerde negatif değer olmaması gerekmektedir. Bu nedenle temelde olan (X3 ve X4) değişkenleriyle temelde olmayan (X1 ve X2) değişkenlerinden birinin yer değiştirmesi gerekmektedir.

Pe ki temele girecek değişken nasıl seçilecek?

  •   Maksimizasyonda en negatif değere sahip değişken,
  •   Minimizasyonda ise en pozitif değere sahip değişken seçilir.

Temele girecek değişkeni bulduk, X2 değişkenidir ve X2 sütunu anahtar sütun olur. Birde temelden çıkacak değişkeni belirlememiz gerekmektedir. Continue reading

Yöneylem Araştırması Grafik Çözümü

Günümüzde komplike yapıda bulunan şirketler için kaynakların yönetilmesi önemlidir. Bahsi geçen şirket kaynaklarının farklı faaliyetlerde “en etkili” şekilde kullanımı normal şartlarda mümkün olmayabilir. Bu noktada devreye giren Endüstri Mühendisleri önlerine çıkan zorlukları aşmak için kullanılan çeşitli yöntemlerden biri olan “Yöneylem Araştırması – Operation Research” tekniklerini kullanarak en etkili yani optimum çözümü sunarlar. Burada ki anahtar kelimemiz en etkili yöntemdir.

Yöneylem araştırmasının temel amacı maksimum kar ya da minimum maliyettir. YA karar problemlerinin analizini ve model kurulumunu matematiksel bir model aracılığıyla yapar. Yani basitçe söylemek gerekirse işimiz matematiksel bir model oluşturup optimum çözüme ulaşmaktır.

(Not: YA’da sadece matematiksel modeller yoktur. Benzetim ya da başka yöntemlerle de çözüm yapılabilir.)

Kurduğumuz matematik modelinin çözümü kurulan modelden fazla ise bu tür modellere “Karar Modelleri” denir.

Karar verme aşamasının temel elemanlar;

  • Karar alternatifleri
  • Problem kısıtları
  • Amaç fonksiyonu

Bu konuya devam etmeden önce Yöneylem Araştırması ve Endüstri Mühendisliği konusunu okumanız kavram kargaşasını ortadan kaldıracaktır.

Yöneylem araştırmasının en önemli aşaması belki de matematiksel modeli kurmaktır. Çünkü kuracağınız model yanlış ise yapacağınız çözümlerin hepsi yanlış olacaktır ve dolayısıyla şirketi yanlış yönlendirmiş olacaksınızdır. Dolayısıyla çözüm yöntemlerine geçmeden önce model kurmayı öğrenmeniz gerekmektedir. Ben model kurma yöntemlerini anlatmayacağım. Google arama motoruna “Yöneylem Araştırması model kurma” şeklinde yazdığınızda bir çok kaynağa ulaşabilirsiniz.

Bu noktadan sonra model kurmayı bildiğinizi varsayarak devam ediyorum.

Yöneylem araştırması çözüm yöntemlerinden en basiti olan Grafik Çözümü yöntemine bakalım.

Grafik Çözümü;

  • İki değişkenin olduğu durumlarda kullanılabilir.
  • Basit bir çözüm sunar.

Örnek bir problemin modelini oluşturup grafik çözümünü ele alalım.

Bir yatak fabrikasında yatak ve baza üretilmektedir. Satış fiyatları yatağın 65 TL bazanın 100 TL’dir.

Bir yatağın üretiminde 25 TL’lik pamuk 15 TL’lik işçilik gideri bulunmaktadır.

Bir bazanın üretiminde ise 10 TL’lik pamuk ve 40 TL’lik işçilik gideri bulunmaktadır.

Bir yatağın üretimi 30 dakika sürerken bazanın üretimi 75 dakika sürmektedir.

Bir günde toplamda en fazla 5 yatak, 3 baza üretilebilmektedir.

Üretim için en fazla 130 TL’lik pamuk kullanılmaktadır.

Günlük işçilik giderinin ise 260 TL’yi geçmemesi istenmektedir.

Yatağı ve bazayı üreten makine haftada 24 saat çalışmaktadır.

    Bu fabrikanın karını maksimum yapması için bir günde hangi üründen kaç adet üretmelidir?

 

Bizden istenen maksimum kar, dolayısıyla matematiksel modelimiz maksimizasyon olacaktır. Öncelikle karar değişkenlerimizi yazalım.

Karar Değişkenleri;

X1 : Yatak Sayısı

X2 : Baza Sayısı

Bu değişkenleri kullanarak Amaç Fonksiyonumuzu oluşturmamız gerekmektedir. Dikkat edilmesi gerekilen husus Amaç Fonksiyonu oluşturulurken maliyetlerin satış fiyatlarından çıkarılarak ürün başına elde edilen karın bulunması ve amaç fonksiyonunda yer almasıdır.

     AMAÇ FONKSİYONU

Yatak karı(X1):    65-(25+15)=25TL

Baza  karı(X2):    100-(40+10)=50TL

     Amaç Fonk.  =>  MaxZ = 25X1 + 50X2

Geriye kısıtlarımız kaldı;

KISITLAR

30X1 + 75X2 <= 1440 (1.Kısıt, Zaman kısıdı) Zaman kısıdı dakikaya çevrilmiştir.

25X1 + 10X2 <= 130 (2.Kısıt, Pamuk kısıdı)

15X1 + 40X2 <= 260 (3.Kısıt, İşçilik kısıdı)

X1,X2 >= 0 (Pozitiflik kısıdı) (Değerler asla negatif olamaz.)

Grafik çözümünde amaç fonksiyonumuzu ve kısıtlarımızı yazdıktan sonra, yani matematiksel modelimizi oluşturduktan sonra geriye pek bir şey kalmıyor. Yapmamız gereken her bir kısıtta değişkenlere sırayla 0 değeri vererek diğer değişkenin değerini hesaplamaktır.

Zaman kısıdı için;

30X1 + 75X2 <= 1440 (1.Kısıt, Zaman kısıdı)

X1=0 ise X2 = 19.2

X2=0 ise X1 = 48

Pamuk kısıdı için;

25X1 + 10X2 <= 130   (2.Kısıt, Pamuk kısıdı)

X1=0 ise X2 = 13

X2=0 ise X1 = 5.2

İşçilik kısıdı için;

15X1 + 40X2 <= 260   (3.Kısıt, İşçilik kısıdı)

X1=0 ise X2 = 6.5

X2=0 ise X1 = 17.3

Her bir kısıt için X1 ve X2 değişkenin değerini bulduğumuza göre artık grafik çizimine geçebiliriz.

 

Grafik Çözümü;

Öncelikle bir hatırlatma yapalım, sorumuz maksimizasyon sorusudur. Grafik çözümüne başlarken temel birkaç şeyden bahsetmek gerekirse, kısıtlarımızı yazarken X1,X2 >= 0 şeklinde bir kısıt yazdık, pozitiflik kısıdı. Bunun anlamı koordinat sisteminde X ve Y eksenlerinin pozitif bölgelerini kullanmamız gerektiğidir. Continue reading