10/8/2014
IENG 202
YÖNEYLEM ARAŞTIRMASI
PAU
ENDÜSTRİ MÜHENDİSLİĞİ BÖLÜMÜ
2014-2015 Güz Yarıyılı
SİMPLEKS ALGORİTMASI
Yrd. Doç. Dr. Leyla DEMİR
Bu sunum PAU Endüstri Mühendisliği Öğretim Üyesi Dr. Özcan Mutlu ile ITU Endüstri Mühendisliği Öğretim Üyeleri Dr. Y. İlker Topçu
ve Dr. Özgür Kabak’ın Yöneylem Araştırması Ders Notlarından derlenerek hazırlanmıştır.
08.10.2014
Giriş
IENG 202-Dr. Leyla Demir
2
Temel özellikleri
• Simpleks algoritması 1949 yılında Dantzig
tarafından geliştirilmiştir.
• Bu algoritma günümüze kadar geliştirilmiş en
etkin 10 algoritma arasında yer almaktadır.
08.10.2014
IENG 202-Dr. Leyla Demir
• Doğrusal programlamada kısıtlar tarafından
oluşturulan olurlu çözüm alanı konvekstir.
• En iyi çözüm bir uç noktadır.
3
08.10.2014
IENG 202-Dr. Leyla Demir
4
1
10/8/2014
Temel özellikleri
Tanım
• Simpleks algoritmasında olurlu çözüm alanının
bir uç noktasından başlanarak her seferinde
amaç fonksiyonunun değerinin daha iyi olduğu
başka bir komşu uç nokta olup olmadığı
araştırılır.
• Bu işleme daha iyi bir komşu uç nokta
bulunamayıncaya kadar devam edilir.
• İki uç nokta aynı olurlu çözüm alanının bir
kenarını paylaşıyor ise bu iki uç nokta birbirine
komşudur.
08.10.2014
08.10.2014
IENG 202-Dr. Leyla Demir
5
IENG 202-Dr. Leyla Demir
6
Adımları
Özellikler
1. Olurlu çözüm alanında bir uç nokta seç.
2. Eğer bu noktada amaç fonksiyonunun değeri
komşu uç noktalardan daha iyi ise en iyi
çözüm bulunmuştur. Değilse 3. adıma git.
3. Amaç fonksiyonunun değerinin daha iyi
olduğu bir uç noktaya git ve 2. adıma git.
• Simpleks algoritması sadece amaç fonksiyonu
değerinin daha iyi olduğu uç noktalara giderek
hızlı bir şekilde en iyi çözüme ulaşmaktadır.
• Bu nedenle büyük boyutlu problemleri bile
makul sürelerde çözme kapasitesine sahiptir.
08.10.2014
IENG 202-Dr. Leyla Demir
7
08.10.2014
IENG 202-Dr. Leyla Demir
8
2
10/8/2014
Örnek
Standart Biçim
Bir deri firması iki tip kemer üretmektedir. Her iki
tip kemerin üretimi için de 1 m2 deriye ihtiyaç
duyulmaktadır. 1. tip kemer 2 saatlik işçilik
gerektirirken 2. tip kemer 1 saatlik işçilik
gerektirmektedir. Her hafta kullanılabilecek deri
miktarı 40 m2 ile, işçilik ise 60 saat ile sınırlıdır.
Firma 1. tip kemerin satışından $4, 2. tip
kemerden ise $3 kar elde etmektedir. Firmanın
karını maksimize etmesi için her iki tip kemerden
üretmesi gereken miktarı bulunuz.
08.10.2014
IENG 202-Dr. Leyla Demir
9
• Doğrusal programlamada kısıtlar genellikle
eşitsizlik olarak ifade edilirler.
• Simpleks algoritmasının uygulanabilmesi için
önce problemdeki tüm kısıtların eşitlik olarak
ifade edilmesi gerekir.
• Bu şekilde elde edilen modele standart biçim
denir.
• Tüm doğrusal karar modelleri uygun işlemlerle
standart biçime dönüştürülebilirler.
08.10.2014
IENG 202-Dr. Leyla Demir
10
Standart Biçim
Standart Biçim
• Eğer problemdeki bir kısıt ≤ şeklinde ise bu
kısıtı eşitliğe dönüştürmek için pozitif bir aylak
değişken (slack variable) eklenir.
• Aylak değişkenler kaynaklarda kullanılmayan
miktarları temsil ederler.
• Eğer problemdeki bir kısıt ≥ şeklinde ise bu
kısıtı eşitliğe dönüştürmek için pozitif bir artık
değişken (excess variable) bu kısıttan çıkartılır.
• Artık değişkenler ise fazla üretimleri temsil
ederler.
08.10.2014
08.10.2014
IENG 202-Dr. Leyla Demir
11
IENG 202-Dr. Leyla Demir
12
3
10/8/2014
Temel Çözüm ve Temel Olurlu Çözüm
Temel Çözüm ve Temel Olurlu Çözüm
• Standart biçime dönüştürülmüş bir DP
modelinde değişken sayısı n ve kısıt sayısı m
olmak üzere iki farklı durum ile karşılaşılabilir:
• Değişken sayısı kısıt sayısından küçük veya eşit
olabilir. Bu durumda problemin bir çözümü
varsa bu çözüm tektir.
• Değişken sayısı kısıt sayısından fazla ise bu
durumda problemin bir çözümü varsa bu
çözüm ya tektir yada sonsuzdur.
• DP modellerinde kısıtlar genellikle eşitsizlik
olduğundan modele ilave edilen aylak yada
artık değişkenler nedeniyle değişken sayısı
kısıt sayısından fazladır.
• Bu nedenle genellikle DP modellerinin sonsuz
sayıda çözümü vardır.
• Simpleks algoritmasında bu çözümler içinden
sadece uç noktada olanlar dikkate
alınmaktadır.
08.10.2014
08.10.2014
IENG 202-Dr. Leyla Demir
13
IENG 202-Dr. Leyla Demir
14
Temel Çözüm ve Temel Olurlu Çözüm
Tanım
• Genel olarak bir problemdeki çözümleri olurlu ve
olurlu olmayan çözümler olarak ikiye ayırabiliriz.
• Tüm kısıtları sağlayan çözümlere olurlu çözüm
(feasible solution), en az bir kısıtı sağlamayan
çözümlere ise olurlu olmayan çözüm (infeasible
solution) denir.
• Standart biçimde bir çözümün olurlu çözüm
olması için tüm değişkenlerin negatif olmayan
değerler alması gerekir.
• Standart biçimde n-m adet değişkene 0 değeri
atanarak bulunan çözüme temel çözüm (basic
solution) denir.
08.10.2014
IENG 202-Dr. Leyla Demir
15
08.10.2014
IENG 202-Dr. Leyla Demir
16
4
10/8/2014
Tanım
Tanım
• Temel çözümde 0 değeri atanan değişkenlere
temel dışı değişkenler (nonbasic variables),
diğer değişkenlere ise temel değişkenler
(basic variables) denir.
• Bir temel çözümde değişkenlerin tamamı 0
veya pozitif değer alıyorsa bu çözüme temel
olurlu çözüm (basic feasible solution) denir.
Bir temel çözümdeki temel değişken sayısı kısıt
sayısı kadar olmalıdır!
08.10.2014
IENG 202-Dr. Leyla Demir
17
08.10.2014
Teorem
IENG 202-Dr. Leyla Demir
18
Tanım
• DP problemlerinde her temel olurlu çözüme
bir uç nokta karşılık gelir.
08.10.2014
IENG 202-Dr. Leyla Demir
• İki temel olurlu çözümde m-1 temel değişken
ortak ise bu iki çözüm birbirine komşudur
(adjacent).
• Bir başka ifade ile iki temel olurlu çözümde
sadece bir temel değişken farklı ise bu iki
çözüm birbirine komşudur.
19
08.10.2014
IENG 202-Dr. Leyla Demir
20
5
10/8/2014
Tanım
• Amaç fonksiyonundaki karar değişkenlerinin katsayılarına
indirgenmiş maliyet (reduced cost) denir.
• İndirgenmiş maliyet bir değişkenin çözüme alınması
durumunda amaç fonksiyonunun nasıl değişeceğini gösterir.
• Eğer bir değişkenin indirgenmiş maliyeti negatif ise bu
değişkenin çözüme alınması durumunda amaç fonksiyonunun
değeri artar, pozitif ise amaç fonksiyonun değeri azalır.
• Bu nedenle maksimizasyon problemlerinde bütün indirgenmiş
maliyetler pozitif ise mevcut çözüm aynı zamanda en iyi
çözümdür.
• Simpleks algoritmasında bu duruma en iyilik koşulu denir.
• Eğer en iyilik koşulu sağlanmıyorsa bu durumda mutlak değerce
en büyük indirgenmiş maliyete sahip değişkenin çözüme
girmesi gerekir.
08.10.2014
IENG 202-Dr. Leyla Demir
21
SIMPLEKS TABLOSU
08.10.2014
Örnek
IENG 202-Dr. Leyla Demir
22
Başlangıç Simpleks Tablosu
Dakota mobilya şirketi sıra, masa ve sandalye
yapmaktadır. Her ürün için, aşağıdaki tabloda
görüldüğü gibi, sınırlı miktarda kullanılabilen tahta,
marangozluk ve cilalama işçiliği gerekmektedir. Aynı
tabloda ürünlerin satış fiyatları da verilmiştir. Haftada
en fazla 5 masa satılabilmektedir. Şirketin haftalık
kazancını maksimize edecek üretim planını
oluşturunuz.
08.10.2014
IENG 202-Dr. Leyla Demir
• Başlangıç simpleks tablosunun oluşturulması için
önce temel değişkenlerin belirlenmesi gerekir.
• Simpleks tablosunda her kısıta bir temel değişken
karşılık gelmektedir.
• Problemde tüm kısıtlar (≤) şeklinde ve sağ taraf
sabitleri negatif değilse bu kısıtlara ilave edilen
aylak değişkenler temel değişkenler olarak
kullanılırlar.
• Eğer en az bir kısıt (≥) veya (=) şeklinde ise bu
kısıtlara ilave edilen yapay (artık) değişkenler
temel değişken olarak kullanılır.
23
08.10.2014
IENG 202-Dr. Leyla Demir
24
6
10/8/2014
Temele girecek değişkenin belirlenmesi
Temelden çıkacak değişkenin belirlenmesi
• Başlangıç tablosu oluşturulduktan sonra bu tabloya karşı gelen
çözümün en iyi çözüm olup olmadığını anlamak için z satırına
bakılır.
• Maksimizasyon problemlerinde eğer temel dışı değişkenlerin
indirgenmiş maliyetleri pozitif ise en iyi çözüme ulaşılmıştır.
• Minimizasyon problemlerinde ise en az bir temel dışı değişkenin
indirgenmiş maliyeti negatif ise bulunan çözüm en iyi çözüm
değildir.
• Bu durum simpleks algoritmasında en iyilik şartı olarak
isimlendirilir.
• Bir simpleks tablosunda en iyilik şartı sağlanmıyorsa mutlak değerce
en büyük indirgenmiş maliyete sahip değişken temele girecek
değişken olarak belirlenir.
• Temele girecek değişkene karşı gelen sütun da anahtar sütun olarak
isimlendirilir.
• Bu işlem yapılırken kısıtların sağlanmasına dikkat edilmelidir.
• Bu amaçla temele girecek değişkenin alabileceği maksimum değer
belirlenir.
• Bunun için simpleks tablosunun sağ tarafındaki değerler anahtar
sütundaki değerlere bölünür.
• Karar değişkenleri negatif değer alamayacağından bölme işleminde
anahtar sütundaki sadece pozitif değerler dikkate alınır.
• Bu oranlar içinden en küçüğüne karşı gelen değişken temelden
çıkacak değişken olarak seçilir.
• Eşitlik durumunda rasgele seçim yapılır.
• Simpleks algoritmasında bu işleme uygunluk şartı denir.
• Temelden çıkacak değişkenin bulunduğu satır anahtar satır olarak
belirlenir.
08.10.2014
08.10.2014
IENG 202-Dr. Leyla Demir
25
Yeni temel uygun çözümün belirlenmesi
• Simpleks tablosunda temel değişkene bir birim vektör
karşılık gelmelidir.
• Bunu sağlamak için satır işlemleri yapılır:
Adım 1: Anahtar sütun ve anahtar satırın kesişimindeki
değeri anahtar eleman olarak belirle. Anahtar satırı
anahtar elemana bölerek yeni anahtar satırı oluştur.
Yeni anahtar satır=Anahtar satır/anahtar elaman
Adım 2: Diğer satırlar için aşağıdaki işlemleri yap.
Yeni i. Satır= (-aij × yeni anahtar satır) + eski i. Satır
aij: anahtar sütundaki i. değerdir.
08.10.2014
IENG 202-Dr. Leyla Demir
IENG 202-Dr. Leyla Demir
26
Maksimizasyon problemi için simpleks
algoritmasının adımları
0. Adım: Modeli standart biçime dönüştür.
1. Adım: Başlangıç temel uygun çözümü belirle.
2. Adım: (En iyilik şartı) Eğer amaç fonksiyonundaki temel dışı
değişkenlerin indirgenmiş maliyetleri pozitif ise mevcut çözüm
en iyi çözümdür, DUR. Değilse, negatif indirgenmiş maliyetler
içinden mutlak değerce en büyük değere sahip değişkeni
temele girecek değişken olarak belirle.
3. Adım: (Uygunluk şartı) Sağ taraf sabitlerini temele girecek
değişkene karşı gelen sütundaki pozitif değerlere böl, en küçük
orana sahip olan değişkeni temelden çıkacak değişken olarak
belirle.
4. Adım: Satır işlemleri yaparak temel değişkenlerin ve amaç
fonksiyonlarının değerini belirle ve 2. adıma git.
27
08.10.2014
IENG 202-Dr. Leyla Demir
28
7
10/8/2014
Ödev
Giapatto örneğini Simpleks algoritmasını
kullanarak çözünüz.
08.10.2014
IENG 202-Dr. Leyla Demir
29
8
Download

Sunu 4 - LEYLA DEMIR