Yöneticilerin gerçek hayatta karşılaştıkları problemler genellikle üçten fazla değişken içermektedir. Halbuki lineer programlamada grafik kullanarak ancak üç değişkene kadar olan problemleri çözebilmemiz mümkündür. Dolayısıyla bu noktada yeni bir yönteme ihtiyaç duyulmuş ve Simplex Metodu diye anılan bu yöntem 1947 yılında George Dantzig tarafından geliştirilerek ilk olarak Amerika Birleşik Devletleri hava kuvvetlerinde kullanılmıştır.
Simplex metodu hesaplama süreci bir dizi iterasyondan oluşmaktadır. İterasyon sözcüğünün özünde tekrarlamak yatmaktadır. Yani optimum sonuca ulaşmaya çalışılırken sistematik bir kalıp doğrultusunda belli hesaplamalar en iyi sonuca varana dek tekrar tekrar yapılmaktadır.
Simplex metodunun bir başka özelliği de her yeni adımın istikrarlı bir biçimde bizi optimum sonuca daha fazla yaklaştırmasıdır. Ve tabii en önemlisi de bu metodun bize optimum sonuca ulaştığımızı bildirebilmesidir.
Örnek problem 1: Boyut Ltd şirketi masa ve iskemle üretmektedir. Her iki ürün de birincisi montaj, ikincisi ise cilalama aşamaları olmak üzere iki aşamadan geçmek zorundadır. Montaj bölümünün iş kapasitesi 60 saat, cilalama bölümünün iş kapasitesi ise 48 saattır. Bir masanın üretilebilmesi için montaj bölümünün 4 saat, cilalama bölümünün ise 2 saat çalışması gerekmektedir. Bir iskemlenin üretilebilmesi için ise montaj bölümümün 2 saat, cilalama bölümünün 4 saat çalışması gerekmektedir. Şirket masa başına 8 $ iskemle başına da 6 $ kazandığına göre en fazla karı elde edebilmesi için kaçar iskemle ve masa üretmelidir?
BAŞLANGIÇ ÇÖZÜMÜNÜN
OLUŞTURULMASI
İ = iskemle M = masa olsun.
Cebirsel olarak problemi şöyle ifade edebiliriz:
-----------------------------------------------------------
Kısıtlamalar: Montaj: 4.M + 2.İ £ 60
Cilalama: 2.M + 4.İ £ 48
Tüm değişkenler ³ 0
Maximum olması istenen fonksiyon:
Kar = 8.M + 6.İ
-----------------------------------------------------------------------
Eşitsizliklerin denklemlere dönüştürülmesi
En iyi masa ve iskemle sayısı kombinasyonunu elde edebilmek için mutlaka her iki bölümünde tüm iş saati kapasitesini kullanmak gerekmeyebileceğini söyleyebiliriz. Dolayısıyla bunları kullanılmayan zaman değişkeni olarak niteleyip her iki eşitsizliğe eklemek suretiyle bu eşitsizliklerden birer eşitlik elde etmek mümkün olacaktır. Bu işlemden önce var olan değişkenleri ise yapısal değişkenler olarak adlandırabiliriz.
Sm: Montaj bölümünde kullanılmayan zaman
Sc : Cilalama bölümünde kullanılmayan zaman
Bu değişkenleri ekledikten sonra şu denklemleri elde ederiz:
4.M + 2.İ + Sm = 60 saat
2.M + 4.İ + Sc = 48 saat
Simplex metodunun yürütülebilmesi için denklemlerden birinde kullanılan değişkenin diğer denklemlerde de kullanılması gerekmektedir. Eğer bir değişken belli bir denklemi etkilemiyorsa katsayısı sıfır olarak alınmalıdır. Bu değişikliği de gerçekleştirdikten sonra denklemlerimiz şu şekli alacaktır:
------------------------------------------------------------------------------
Kısıtlamalar: Montaj: 4.M + 2.İ + Sm + 0. Sc = 60 saat
Cilalama: 2.M + 4.İ + 0.Sm + Sc = 48 saat
Tüm değişkenler ³ 0
Maximum olması istenen fonksiyon:
Kar = 8.M + 6.İ + 0.Sm + 0.Sc
---------------------------------------------------------------------------------------------
Simplex tablosu
Yukarıdaki denklemleri matris yapısında bir tablo ile de gösterebiliriz:
-------------------------------------------
M İ Sm Sc
-------------------------------------------
60 4 2 1 0
48 2 4 0 1
---------------------------------------------------
Simplex metodunda bir ilk çözümün oluşturulması gerekmektedir. Boyut Ltd için en basit başlangıç çözümü hiçbir masa ve iskemle üretmeyip sıfır kazanç sağlamak olacaktır. Bu çözüm matematiksel olarak mümkündür, ancak finansal olarak pek te cazip bir çözüm gibi gözmemektedir.
M = 0
İ = 0
Sm = 60 – 4.(0) – 2.(0) = 60 saat kullanılmayan zaman
Sc = 48 – 2.(0) –4.(0) = 48 saat kullanılmayan zaman
Karı ise şöyle hesaplayabiliriz:
Kar = 8.M + 6.İ +0.Sm + 0.Sc
= 8.(0) + 6.(0) + 0.(60) + 0.(48)
= 0
Bu ilk geçerli çözüm simplex tablosunda şöyle gösterilebilir:
---------------------------------------------------------
Ürün
Kombinasyonu Miktar M İ Sm Sc
---------------------------------------------------------
Sm 60 4 2 1 0
Sc 48 2 4 0 1
---------------------------------------------------------
Bu çözüm grafik metodu ile karşılaştırılacak olursa aynı problemin çözüm grafiğindeki A noktasına karşılık gelmektedir. Bu da grafikteki konveks bölgenin köşelerinden birini oluşturmaktadır.
Öncelikle aşağıdaki tablonun bileşenlerini inceleyerek her bir bileşenin ne anlama geldiğini görelim:
-----------------------------------------------------------------
Cj 8$ 6$ 0$ 0$
-----------------------------
Ürün kombinasyonu Miktar M İ Sm Sc
-----------------------------------------------------------------
0$ Sm 60 4 2 1 0
0$ Sc 48 2 4 0 1
-----------------------------------------------------------------
Cj sütunu Sm ve Sc değişkenleri için birim başına karı göstermektedir.
Son iki sütun eşitsizlikleri eşitliğe dönüştürmek için eklenen değişkenlerin katsayılarını göstermektedir.
Dört ve beşinci sütunlar imalatı yapılan gerçek ürünlerin katsayılarını göstermektedir. Örneğin M sütunundaki 4 sayısının anlamı, eğer bir masa üretecek olursak (yani 1 masayı çözüme dahil edecek olursak) montaj bölümündeki 4 saatten vazgeçmek zorunda kalmamızdır. Bu durumda dört ve beşinci sütunlardaki elemanların aslında ikame oranlarını gösterdiğini söyleyebiliriz.
Bu ikame oranlarını incelediğimizde iki tür işlem yaptığımızı görebiliyoruz:
1. Üretim programına, veya çözüme, M ve İ gerçek ürünlerini eklemek
2. Başka amaçlarla kullanmak üzere her iki bölümün kullanılmayan iş zamanından fedakarlık etmek.
Şu aşamaya kadar simplex tablosunu oluştururken herhangi bir işlem devreye girmedi. Yaptığımız sadece problemin denklemlerini farklı bir düzende ifade etmekti. Her bir çözüm için elde edilecek karı bulmak ve bu çözümün iyileştirilebilip iyileştirilemeyeceğine karar verebilmek için ilk oluşturduğumuz simplex tablosuna iki satır daha eklememiz gerekir. Bunlar Zj ve Cj – Zj satırlarıdır.
-----------------------------------------------------------------
Cj 8$ 6$ 0$ 0$
-----------------------------
Ürün kombinasyonu Miktar M İ Sm Sc
-----------------------------------------------------------------
0$ Sm 60 4 2 1 0
0$ Sc 48 2 4 0 1
Zj 0$ 0$ 0$ 0$ 0$
Cj – Zj 8$ 6$ 0$ 0$
-----------------------------------------------------------------
Zj satırında miktar sütununa karşılık gelen değer bu özel çözümden elde edilen toplam karı göstermektedir.(İlk çözümümüzde bu değer sıfır idi.)
Zj satırında diğer sütunlara karşılık gelen değerler ise M, İ, Sm, Sc değişkenlerinden bu kombinasyona bir birim eklenmesi halinde karın ne kadar azalacağını göstermektedir. Örneğin bir adet masa imal etmek istediğimiz takdirde M sütunundaki 4 ve 2 bize SM den 4 saat SC den de 2 saat azaltmak zorunda olduğumuzu söylemektedir. Ancak kullanılmayan zamanın değeri 0$ ettiğinden karda bir azalma olmamaktadır.
Cj birim başına kar olarak tanımlanmıştır. Örneğin masa için Cj 8$/masa dır.
Bu durumda Cj – Zj , üretim programına veya diğer bir deyişle çözüme bir birimlik bir değişken eklemenin getireceği net karı göstermektedir. Örneğin 1 birim M eklenmesi çözüme 8$ kar ekliyor ve 0$ zarara sebep oluyor. Yani M için Cj – Zj = 8$ olmaktadır.
***YORUM: Cj – Zj satırının pozitif sayılardan oluşması eklenen her bir birim için fazladan o kadar karın artacağı anlamına gelmektedir. Aynı şekilde bu satırda negatif sayıların olması da eklenen her birim için karın o kadar azalacağını göstermektedir. O halde eğer bu satır da hiçbir pozitif değer kalmamışsa bu, daha fazla kar edilemeyeceği, yani optimum sonuca ulaşıldığı anlamına gelecektir.
Bir kez ilk simplex tablosu oluşturulduktan sonra artık diğer aşama karı nasıl arttırabileceğimizi bulmaktan ibarettir. Bu kısımda verilecek hesaplama yöntemi gerek ikinci çözüm gerekse takip eden çözüm tablolarının oluşturulmasında kullanılacaktır. Bir tablodan diğerine geçme işlemi pivot alma olarak adlandırılır. Ve her bir iterasyon pivot adını alır. İlk pivot şu şekildedir:
1.AŞAMA:
Hangi değişkenin bir biriminin en fazla karı getireceğini saptarız. Bu bilgiyi bize Cj – Zj satırı verecektir. Daha önce de belirttiğimiz gibi bu satırda pozitif sayıların varlığı karın daha fazla arttırılabileceğini ifade eder. Bu satırdaki pozitif sayı ne kadar büyük olursa karı da o kadar çok arttırabileceğimiz anlamı çıkar. Tablomuza baktığımızda kara en fazla katkıda bulunan ürünün 8$ ile M olduğunu görüyoruz. Bu durumda M sütunu optimum sütun olarak alınacaktır. Kolaylıkla görülebileceği gibi optimum sütun Cj – Zj satırında en büyük pozitif değeri alan sütundur, veya bir başka deyişle kara en fazla katkıda bulunan ürüne ait sütundur. Bu durumda ürün kombinasyonunda var olan değişkenlerden biri yerine M değişkeninin koyulması gerekmektedir.
2.AŞAMA:
Bu aşamada M değişkeninin hangi değişkenin yerine geçeceğini saptamamız gerekmektedir. Bunu da şöyle gerçekleştiririz: Miktar sütunundaki 60 ve 48 sayılarını sırasıyla M sütunundaki 4 ve 2 sayılarına bölüp, elde edilen en küçük pozitif oranın bulunduğu satırı yer değiştirilecek satır olarak belirleriz.
Sm satırı (60 saat-kullanılabilir süre) / (4 saat-bir ürün için gereken süre) = 15 tane M ****
Sc satırı (48 saat-kullanılabilir süre) / (2 saat-bir ürün için gereken süre) = 24 tane M
Sm satırı daha küçük pozitif orana sahip olduğundan yer değiştirecek satır olacaktır. Bu arada Sm ve Sc satırlarıyla optimum sütunun kesişiminda yer alan elemanlara da arakesit elemanları adı verilir. Sm satırına ait arakesit elemanı 4, Sc satırına ait arakesit elemanı ise 2 dir.
3.AŞAMA:
Artık optimum sütunu ve yer değiştirecek satırı seçtiğimize göre ikinci simplex çözümü veya diğer adıyla geliştirilmiş çözümü bulabiliriz. Yeni tablodaki ilk işlemimiz yer değiştirecek satırı kaldırıp yerine M satırını koymak olacaktır. Bu yeni satırı ise, yer değiştirecek satırın tüm elemanlarını, yine yer değiştirecek satırın arakesit elemanına bölerek elde ederiz. Yani 60/4 = 15, 4/4 = 1, 2/4 =1/2, 1/4 = 1/4, 0/4 = 0. Böylece yeni M satırının katsayıları ( 15, 1, ½, ¼, 0 ) olarak elde edilecektir.
-----------------------------------------------------------------
Cj 8$ 6$ 0$ 0$
-----------------------------
Ürün kombinasyonu Miktar M İ Sm Sc
-----------------------------------------------------------------
8$ M 15 1 ½ ¼ 0
0$ Sc
Zj
Cj – Zj
-----------------------------------------------------------------
Bu tabloda karşımıza ilk defa bir pozitif Cj değeri çıkmış oldu (8$). Ayrıca üretilen 15 adet masanın grafik çözümde karşılığı olan noktanın C noktası olduğunu gözlemlemekte de fayda vardır. Bu da kapalı konveks bölgenin bir başka köşe noktasını oluşturmaktadır.
4.AŞAMA:
İkinci tabloyu tamamlayabilmek için kalan satırların da yeni değerlerini hesaplamamız gerekmektedir. Bu hesaplama da şu formül ile kolayca yapılabilir:
(eski satır elemanı) – [( eski satırın arakesit elemanı) x ( yeni satırdaki buna karşılık gelen eleman)] = ( yeni satır )
Yukarıdaki formülü her bir elemana uygulayacak olursak tabloyu şu şekilde elde ederiz:
-----------------------------------------------------------------
Cj 8$ 6$ 0$ 0$
-----------------------------
Ürün kombinasyonu Miktar M İ Sm Sc
-----------------------------------------------------------------
8$ M 15 1 ½ ¼ 0
0$ Sc 18 0 3 - ½ 1
Zj 120$ 8$ 4$ 2$ 0$
Cj – Zj 0$ 2$ -2$ 0$
-----------------------------------------------------------------
Cj – Zj satırının İ sütunundaki pozitif sayının varlığı çözümün bir aşama daha öteye götürülebileceğini göstermektedir. Bu durumda aynı aşamaları tekrar gerçekleştirerek üçüncü tabloyu elde ederiz:
-----------------------------------------------------------------
Cj 8$ 6$ 0$ 0$
-----------------------------
Ürün kombinasyonu Miktar M İ Sm Sc
-----------------------------------------------------------------
8$ M 12 1 0 1/3 -1/6
6$ İ 6 0 1 - 1/6 1/3
Zj 132$ 8$ 6$ 5/3$ 2/3$
Cj – Zj 0$ 0$ -5/3$ -2/3$
-----------------------------------------------------------------
Kolayca görülebileceği gibi artık tablonun Cj – Zj satırında hiçbir pozitif değer kalmamıştır. Dolayısıyla karın bundan öteye arttırılması imkansızdır. Yani optimum sonuca ulaşılmıştır. Ayrıca bu çözümün de grafik çözümdeki D noktasına karşılık geldiğini gözlemleyebiliriz.
1.Problemin kısıtlamalarını eşitsizlikler şeklinde kur.
2.Yapay değişkenler eklemek suretiyle eşitsizlikleri denklemlere dönüştür.
3.Denklemleri simplex tablosunda yerleştir.
4.Başlangıç çözümü için Cj ve Zj değerlerini hesapla.
5.En büyük Cj – Zj değerine sahip sütunu optimum sütun seç.
6.Miktar sütunundaki değerlerin karşılıkları olan optimum sütun verilerine bölünmesi ile elde edilen oranların içinde en küçük pozitif olanı seçerek yer değiştirecek satırı belirle
7.Yeni satırın değerlerini hesapla
8.Kalan satırların değerlerini hesapla.
9.Yeni çözüm için Cj ve Zj değerlerini hesapla.
10.Pozitif bir Cj – Zj değeri bulursan 5’inci aşamaya dön.
11.Hiçbir pozitif Cj – Zj değeri kalmadıysa optimum çözüme ulaşıldı demektir.
Örnek problem 2: Beslen Ltd. şirketi özel bir karışımdan oluşan yeni ürününü piyasaya sürecektir. 141-B kodlu üründen şirkete 200 kg sipariş gelmiştir. Ürün iki malzeme içermektedir: P (protein içeren malzeme), C ( karbonhidrat içeren malzeme). P nin kilogramı 3$, C nin kilogramı ise 8$ dır. Bu karışım % 40 tan fazla P ve % 30 dan az C içerememektedir. Şirket yetkilileri maliyeti en aza indirmek için hangi malzemeden ne kadar kullanacaklarını tayin etmeye çalışmaktadırlar.
Cebirsel olarak problemi şöyle ifade edebiliriz:
-----------------------------------------------------------
Kısıtlamalar: P + C = 200 kg
P ≤ 80 kg
C ≥ 60 kg
P ve C ≥ 0
Minimum olması istenen fonksiyon:
Maliyet = 3.P + 8.C
-----------------------------------------------------------------------
BAŞLANGIÇ ÇÖZÜMÜ
Maximizasyon problemimizdeki başlangıç çözümümüz 0 kardı. Bu belki anlamsız bir çözümdü ancak bizim sonuca gitmemiz için bir yerden başlamamız gerekiyordu. Burada da yine bir başlangıç çözümüne ihtiyaç duymaktayız. P = 0 ve C = 200 değerlerini başlangıç çözümü olarak almış olalım. Bu değerler tüm kısıtlamalara uymaktadır. Ancak daha gerçekçi ve örneğin 12 değişken içeren bir problemde gözleme dayalı olarak başlangıç çözümünü oluşturmak neredeyse imkansız gibidir.
Dolayısıyla daha sistematik düşünelim ve başlangıç çözümüne ne P ne de C yi katalım. Onun yerine 200 kg A (yapay değişken olarak böyle yeni bir malzeme olduğunu varsayalım.) malzemesi alalım.
P + C + A1 = 200 : İlk kısıtlama ( A1 in kilogramı 100$ olan ve diğer malzemelerin tamamının yerine geçebilecek bir malzeme olduğunu varsayıyoruz)
Her ne kadar bu maliyet açısından aptalca gözükebilecek bir çözüm ise de tüm kısıtlamalarımıza uymaktadır. Lineer programlama terminolojisinde yapay değişken, sadece hesaplama değeri olan ve “eşit” veya “büyük veya eşit” tipinde kısıtlamaları düzenlemede kullanılmaktadır.
Bu problemdeki ikinci kısıtlama protein içeren malzemeye aittir ve bunu da eşitliğe çevirebilmek için son çözümde kullanılan protein miktarıyla maximum protein miktarı arasındaki farkı gösteren bir S1 değişkeni ekleriz.
P + S1 = 80 kg
Üçüncü kısıtlama ise karbonhidratlara ait olup nihai çözümde karbonhidrat miktarının alt sınır olan 60 kilogramın ne kadar üzerinde olduğunu gösteren bir S2 değişkenini çıkararak bunu da eşitliğe çeviririz.
C – S2 = 60 kg
Ancak burada başlangıç çözümü olarak P = 0 ve C = 0 aldığımızda 0 – S2 = 60 tan S2 = - 60 kg olduğunu görüyoruz. Halbuki negatif kütleye sahip bir malzeme kullanamayacağımız için bu çözüm geçerli olmayacaktır. O halde ne yapmamız gerekir?
Bu durumda yine kilogramı 100$ olan A2 gibi bir yapay değişken daha yaratarak S2 nin ilk çözümde gözükmemesini sağlarız. Böylece denklemimiz şu hali alır:
C – S2 + A2 = 60 (burada artık C = 0 ve S2 = 0 olabilecektir.)
Özellikle üzerinde durmamız gereken şey ise hem A1 hem de A2 nin fiyatlarının P ve C ye kıyasla çok yüksek olmasının, onların nihai çözümde yer almasını imkansız kılarak bizi problemin son aşamasında bu değişkenlerden otomatik olarak kurtarmasıdır. Fakat bazı problemlerde yeterince büyük sayılar kullanmak problemin çözümünü zorlaştıracağından burada hesaplamaları kolaylaştırmak amacıyla yeterince büyük varsayacağımız sembolik bir M sayısını kullanacağız.
---------------------------------------------------------------------------------------
Kısıtlamalar: P + C + A1 = 200 kg
P + S1 = 80 kg
C – S2 + A2 = 60 kg
P, C, A1, S1, S2, A2 ≥ 0
Minimum olması istenen fonksiyon:
Maliyet = 3.P + 8.C +0.S1+0.S2 + M.A1 + M.A2
--------------------------------------------------------------------------------------------------------
Böylece ilk simplex tablosunu da elde etmiş oluruz.
----------------------------------------------------------------------------------------
Cj 3$ 8$ M$ 0$ 0$ M$
----------------------------------------------------
Ürün kombinasyonu Miktar P C A1 S1 S2 A2
----------------------------------------------------------------------------------------
M$ A1 200 1 1 1 0 0 0
0$ S1 80 1 0 0 1 0 0
M$ A2 60 0 1 0 0 -1 1 → Yer değiştirecek satır
Zj 260M$ M$ 2M$ M$ 0$ -M$ M$ (bu satırın bulunma yöntemi diğer problemle aynıdır)
Cj – Zj (3-M)$ (8-2M)$ 0$ 0$ M$ 0$
----------------------------------------------------------------------------------------
↓
Optimum sütun
(en küçük negatif değer)
İkinci simplex tablosu da şöyle elde edilmiş olur:
-----------------------------------------------------------------------------------------------------------------
Cj 3$ 8$ M$ 0$ 0$ M$
------------------------------------------------------------------------
Ürün kombinasyonu Miktar P C A1 S1 S2 A2
-----------------------------------------------------------------------------------------------------------------
M$ A1 140 1 0 1 0 1 -1
0$ S1 80 1 0 0 1 0 0 → Yer değiştirecek satır
8$ C 60 0 1 0 0 -1 1
Zj (140M+480)$ M$ 8$ M$ 0$ (M-8)$ (8-M)$
Cj – Zj (3-M)$ 0$ 0$ 0$ (8-M)$ (2M-8)$
-----------------------------------------------------------------------------------------------------------------
↓
Optimum sütun
Üçüncü simplex tablosu aşağıdaki gibidir:
-----------------------------------------------------------------------------------------------------------------
Cj 3$ 8$ M$ 0$ 0$ M$
------------------------------------------------------------------------
Ürün kombinasyonu Miktar P C A1 S1 S2 A2
-----------------------------------------------------------------------------------------------------------------
M$ A1 60 0 0 1 -1 1 -1 → Yer değiştirecek satır
3$ P 80 1 0 0 1 0 0
8$ C 60 0 1 0 0 -1 1
Zj (60M+720)$ 3$ 8$ M$ (3-M)$ (M-8)$ (8-M)$
Cj – Zj 0$ 0$ 0$ (M-3)$ (8-M)$ (2M-8)$
-----------------------------------------------------------------------------------------------------------------
↓
Optimum sütun
Ve nihayet dördüncü ve son simplex tablosunu elde ederiz (Bu tablo optimum çözümü vermektedir):
-----------------------------------------------------------------------------------------------------------------
Cj 3$ 8$ M$ 0$ 0$ M$
------------------------------------------------------------------------
Ürün kombinasyonu Miktar P C A1 S1 S2 A2
-----------------------------------------------------------------------------------------------------------------
0$ S2 60 0 0 1 -1 1 -1
3$ P 80 1 0 0 1 0 0
8$ C 120 0 1 1 -1 0 0
Zj 1200$ 3$ 8$ 8$ -5$ 0$ 0$
Cj – Zj 0$ 0$ (M-8)$ 5$ 0$ M$
-----------------------------------------------------------------------------------------------------------------
Bu aşamada hiçbir negatif değer kalmadığından optimum değere ulaştığımızı anlarız.