:::: MENU ::::

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

Review of:
Product by:
Ahmet AKSOY

Reviewed by:
Rating:
5
On Kas 2, 2014
Last modified:Mar 28, 2016

Summary:

Dyoneylem_smallaha ö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 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 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ındatemelde 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.

Anahtar sütunu bulduktan sonra(X2 Sütunu), anahtar sütunda bulunan her bir hücre içindeki değeri Çözüm sütunundaki değerlere oranlarız ve en küçük negatif olmayan değeri belirleriz. Bu işlem hem maksimizasyon hem de minimizasyon modellerinde aynı şekilde yapılır.

 

Not: Z satırı oran işlemine dahil edilmez.

Yaptığımız oran sonucu X4 değişkeninin değerinin daha küçük olduğunu belirledik dolayısıyla X4 temelden çıkacak değişkenimiz oluyor ve X2 temele girecek değişkenimiz oluyor.

 

İterasyon İşlemleri;

Temele girecek ve çıkacak değişkenlerimizi belirledikten sonra sadece yerlerini değiştirip işlemimizi yapamıyoruz maalesef. Onun yerine iterasyon işlemleri yapmamız gerekmektedir. İterasyon işlemlerinin ilk aşaması Temele girecek olan değişkenin(X2) yeni değerlerini hesaplamaktır. Bunun için yukarıdaki tabloda yer alan X4 satırındaki bütün değerleri pivot elemana yani 5’e bölmemi gerekmektedir.

 

Formülüze edersek; Yeni Satır(X2) = Eski Satır(X4) / Pivot Eleman(5)

2.5           5           0              1          55     /    5 (Bütün değerleri böleriz)

0.5          1          0          0.2        11  >>>>> Yeni Satırımız(X2)

 

Tablomuzun yeni hali aşağıdaki gibidir.

 

Şimdide diğer satırlar için iterasyon işlemlerini yapalım. Formülü şu şekildedir;

Yeni Satır = Eski Satır – İlgili satırın Pivot Elemanı * Yeni Anahtar Satır(X2)

 

Z Satırı için İterasyon İşlemi;

Eski Z satırı: –3     -4          0             0             0

İlgili Satır(Z satırı) Pivot Elemanı: (X2 anahtar sütun olduğundan dolayı ilk tablomuzda Z ile X2’nin kesiştiği hücre pivot eleman olur) -4

Yeni Anahtar Satır: (Temele giren X2 satırıdır) 0.5            1             0             0.2          11

Yeni Satır(Z) = (-3        -4          0          0         0)   –   (-4)   *  (0.5            1             0             0.2          11)

 

Ya da daha basit olması açısından işlemleri aşağıdaki formatta yazabiliriz. Pivot eleman (-4) parantez içine dağıtılacağından her bir değerle işlem yapabiliriz.

(-3) – (-4) * 0.5 = -1

(-4) – (-4) * 1     = 0

(0) – (-4) * 0       = 0

(0) – (-4) * 0.2   = 0.8

(0) – (-4) *11     = 44

Matematiksel işlem önceliği olarak çarpma işlemi yapılacaktır. İşlem sonucunda Z satırının yeni değeri;

Yeni Z = -1          0             0             0.8          44

 

Aynı şekilde Yeni X3 satırını da hesaplayalım;

Eski X3 satırı: 15                10           1             0             150

İlgili Satır(X3 satırı) Pivot Elemanı: (X2 anahtar sütun olduğundan dolayı ilk tablomuzda X3 ile X2’nin kesiştiği hücre pivot eleman olur) 10

Yeni Anahtar Satır: (Temele giren X2 satırıdır) 0.5            1             0             0.2          11

Yeni Satır(X3) =( 15         10           1             0             150)   –   (10)   *  (0.5      1             0             0.2          11)

Matematiksel işlemleri yaptığımızda;

Yeni X3 = 10       0             1             -2            40

 

Bulduğumuz değerleri tabloya yazalım.

Tablonun son hali yukarda görüldüğü gibidir. Ama hala Z satırında negatif(X1) değeri bulunmaktadır. Bu nedenle X1’in temele girmesi gerekmektedir. Tekrar oranlama yaparak temelden çıkacak değişkeni bulalım.

Temele girecek olan değişkenimiz X1 ve temelden çıkacak olan değişkenimizi X3 olarak belirledik.

Tekrar iterasyon işlemlerini yapalım.

Yeni Satır için;

Yeni Satır = (10                 0             1             -2            40) /10

Yeni Satır = (1                    0             0.1          -0.2        4)

 

Z Satırı için;

Yeni Z Satırı = (-1              0             0             0.8          44)  –   (-1) *   (1               0             0.1          -0.2        4)

Yeni Z Satırı = (0               0             0.1          0.6          48)

 

X2 satırı için;

Yeni X2 satırı = (0.5         1             0             0.2          11)  –  (0.5)   *   (1             0             0.1          -0.2        4)

Yeni X2 satırı = (0             1             -0.05      0.3          9)

 

Bulduğumuz değerleri Tablomuza yerleştirelim. Tabloya geçerken X3 satırının adını değiştirmeyi unutmayalım.

 

Temelde olmayan değişkenlerimizi kontrol edelim. X3 ve X4 değişkenleri temelde değiller ve değerleri de pozitif. Bu da tablomuzun optimal hale geldiği anlamına gelmektedir.

Bu oyuncak firmasının maksimum kar elde edebilmesi için X1(Oyuncak Asker)’den 4 adet ve X2(Oyuncak Bebek)’den9 adet üretmesi gerekmektedir. Ve bu şartlar altında karı bulduğumuz Z değerimiz yani 48 olacaktır.

Benzer Yazılar

Paylasmak istersen Share on FacebookTweet about this on TwitterShare on Google+Share on LinkedInShare on TumblrBuffer this pageShare on RedditEmail this to someone

9 yorum yapılmış

Evet, Konu hakkındaki düşüncelerini alalım ?

  • 20 + 9 = ? (İşleminin Sonucu)