EM302 Yöneylem Araştırması 2

Dr. Özgür Kabak

İstanbul Teknik Üniversitesi

Endüstri Mühendisliği Bölümünde Yardımcı Doçent

Doktora İTÜ’den 2008

Olabilirsel doğrusal programlama ile tedarik zinciri ağ yapısının modellenmesi ve bir uygulama

Doktora üstü çalışma Belgium Nuclear Research Centre (SCK.CEN), Mol, Belçika Şubat 2009 – Şubat 2010

Nükleer koruma uygulamaları için bir çok ölçütlü karar verme yaklaşımı

Çalışma Alanları Yöneylem Araştırması (Matematiksel programlama)

Tedarik Zinciri Yönetimi

Bulanık karar verme

Özgür Kabak

Özgür Kabak

E-posta: kabak@itu.edu.tr

Tel.: 0212 2931300 / 2039

Ofis: İTÜ İşletme Fakültesi, Maçka, A311

web sayfası : http://web.itu.edu.tr/kabak

Ders web sayfası

http://web.itu.edu.tr/~kabak/dersler/EM302/

Ders kitabı

Winston W.L. (2004) "Operations Research: Applications and Algorithms", Duxbury Press, Wadsworth Inc., Belmont, USA.

Diğer kaynaklar

Lieberman, H. (2005), "Introduction to Operations Research", Eigh Edition, Mc-Graw-Hill, Singapore

Taha, H.A. (2007), "Operations Research: An Introduction", Eighth Edition, Pearson International Edition, London

Taha, H. (2000), “Yöneylem Araştırması”, 6. Basımdan Çevirenler . Ş. Alp Baray- Şakir Esnaf,

Haftalık Ders Planı (Geçici) Hafta Tarih Konu Ödev

1 21.09.2012 Ders yapılamadı - telafi edilecek

2 28.09.2012 Tamsayılı Programlama (TP) Temel Kavramlar, TP Modellemeye Giriş

3 05.10.2012 Modelleme (TP'de Formülasyon), Grafik Çözüm Ödev 1

4 12.10.2012 TP Model Türleri. Tüm Tamsayı Modellerin Çözüm Yöntemleri

5 19.10.2012 Tüm Tamsayı Modellerin Çözüm Yöntemleri Ödev 1

teslim

6 26.10.2012 BAYRAM

7 02.11.2012 Karışık Tamsayılı Modellerin Çözüm Yöntemleri: Dal ve sınır

03.11.2012 Telafi dersi: sınav için soru çözümü

8 09.11.2012 YARIYILİÇİ SINAVI I

9 16.11.2012 0-1 Tamsayılı modeller için: Kapalı sayma, Değişken sabitleme, Kısıt

sıkılaştırma, gereksiz kısıt belirleme Ödev 2

10 23.11.2012 Deterministik Dinamik Programlama Modellerinin Formülasyonu

11 30.11.2012 Deterministik Dinamik Programlama Modellerinin Formülasyonu,

ve Çözümü Ödev 2

teslim

12 07.12.2012 Probabilistik Dinamik Programlama Modellerinin Formülasyonu ve

çözümü, Ödev 3

13 14.12.2012 Doğrusal Olmayan Programlamaya Giriş

14 21.12.2012 Doğrusal Olmayan Programlamaya Giriş Ödev 3

teslim

15 28.12.2012 YARIYILİÇİ SINAVI II

Ders kapsamı

Konular

Tamsayılı programlama Fomülasyonu

Tamsayılı programlama Çözümü

Deterministik dinamik programlama

Probabilistik dinamik programlama

Doğrusal olmayan programlama

Değerlendirme Ödev (3 adet) %15

Kısa sınav (3 adet) %15

Yarıyıl içi sınavı (2 adet) %30

Yarıyıl sonu sınavı %40

Başarı notları (alt sınır):

85-100 A+ 80-85 A 75-80 B+ 65-75 B 60-65 C+ 50-60 C 45-50 D+ 40-45 D < 40 F

Sınavlar Kısa Sınavlar

Habersiz olarak ders saatinde yapılacaktır

Telafisi olmayacaktır

Yarıyıl için sınavları 1. yarıyıliçi sınavı

09.11.2012 ders saatinde

İlk 7 hafta işlenen tüm konular dahil

2. yarıyıliçi sınavı 28.12.2012 ders saatinde

9.-14. haftalar arasında işlenen tüm konular dahil

Yarıyıl sonu sınavı Final haftasında

Derste işlenen tüm konular dahil

Tüm sınavlarda defter/kitap açık olacaktır.

Ödevler

Dönem boyunca 3 ödeviniz olacak.

Ödevler 2 kişilik gruplar halinde yapılabilir.

Ödevler web sayfasında ilan edilecek

Ödev Konu İlan tarihi Teslim tarihi

1 Tam sayılı programlama formülasyonu 05.10.2012 19.10.2012

2 Tamsayı Modellerin Çözüm Yöntemleri 16.11.2012 30.11.2012

3 Dinamik programlama 07.12.2012 21.12.2012

Derse katılım

Derse katılma Doğuş Üniversitesi kuralları gereği

%70’tir.

Derse katılım ile beklenen sadece yoklamayı

imzalamak değil derse aktif olarak katkı sağlamaktır.

Ders saatleri

09:00 – 10:00 1. Ders

10:00 – 10:15 ara

10:15 – 11:15 2. Ders

11:15 – 11:30 ara

11:30 – 12:50 3. Ders

Lütfen Derse zamanında gelin!

Tam Sayılı Programlama

13

Bazı doğrusal programlama modellerinde sonuçların tam

sayı çıkmaması problemin gerçek hayattaki problemlere

uygunluğunu bozmaktadır.

Örneğin bir üretim probleminde masa ve sandalye üretimi

yapılacaksa sonuçların kesirli çıkması gerçekçi değildir.

Sonuçların tam sayıya yuvarlatılması bazı kısıtları

sağlamayabileceği için çözüm olmamaktadır.

Tam sayılı programlama tekniği, kısıtları bozmadan

sonucun tam sayı olmasını sağlamaktadır.

Tam sayılı / Karma sayılı / 0-1 tam sayılı programlama

modellerinde

Hatırla

Doğrusal Programlama

Simpleks algoritması

DP Örneği - Giapetto Örneği

15

(Winston 3.1., s. 49)

Giapetto tahtadan oyuncak asker ve tren yapmaktadır. Satış fiyatları, bir oyuncak asker için $27, bir oyuncak tren için

$21'dır.

Bir asker için $10'lık hammadde ve $14'lık işçilik kullanılmaktadır.

Bir tren için ise söz konusu rakamlar sırasıyla $9 ve $10'dır.

Her bir asker için 2 saat montaj ve 1 saat marangozluk gerekirken,

her bir tren için 1 saat montaj ve 1 saat marangozluk gerekmektedir.

Eldeki hammadde miktarı sınırsızdır,

fakat haftada en çok 100 saat montaj ve 80 saat marangozluk kullanabilen

Giapetto'nun haftada en fazla 40 oyuncak asker satabileceğini göz önünde bulundurarak

karını enbüyüklemek için hangi oyuncaktan haftada kaç adet üretmesi gerektiğini bulunuz.

Tam sayılı program

(Integer Program)

Karar değişkenlerinin tam sayı olması gereken problemler için kurulan doğrusal modellere tam sayılı program denir.

Söz konusu programların çözümü konusu Tamsayılı Programlama (TP) olarak isimlendirilir.

Tüm değişkenlerin tamsayı olduğu bir programlama sorunu

tamamen tamsayılı programlama sorunu olarak isimlendirilir.

Eğer değişkenlerin bazıları tamsayı, bazıları kesirli ise söz konusu sorun karma tamsayılı programlama sorunu adını alır.

Bazı durumlarda tamsayı değişkenler sadece 0 veya 1 değerlerini alabilir. Bu tip sorunlar da tamamen (karma) 0-1 programlama sorunları veya tamamen (karma) ikili tamsayı programlama sorunları olarak isimlendirilir.

Tamamem Tam Sayılı Programlama

17

Tüm karar değişkenli tam sayı

maks z = x1+ x2+x3

öyle ki x1 + 6x2 + x3 ≤ 8

x1 + 2x2+1,5x3 ≤ 2

2x1 + x2 + 5x3 ≤ 8

x1,x2,x3 tam sayı

0-1 Tam Sayılı Programlama

18

Tüm karar değişkenleri 0 veya 1 değerini alır.

maks z = 2x1+ 3x2+ 4x3 + 7x4+ 2x5

Öyle ki; x1+ 2x2+ 3x3 + x4+ 2x5 ≤ 8

x1,x2,x3,x4,x5 = 0 or 1

Karma Tam Sayılı Programlama

19

Karar değişkenlerinin en az bir tanesi tam sayı veya

0-1 tam sayı olan doğrusal programlama modelleri

maks z = x1 - 2x2+x3 +2x4

Öyle ki x1 + 6x2+ x3 - 2x4 ≤ 8

x1 + 2x2+1,5x3 +x4 ≤ 2

2x1 + x2+ 5x3 +2x4 8

x1 0; x2,x3 tam sayı; x4 0 veya 1

Tam sayılı programlama modellerinin

formülasyonu

20

Sermaye Bütçeleme 0-1 tamsayılı modeli

Sırt çantası problemi

Sabit maliyetlerin modellenmesi

Ya - ya da kısıtları

Eğer – ise kısıtları

Ya hep – Ya hiç

Gezgin satıcı sorunu

Grup kapsama ve ayırma modelleri

Küme kapsama problemi

Parçalı fonksiyonların modellenmesi

Sermaye Bütçeleme 0-1 tamsayılı modeli

21

Stockco dört yatırımı değerlendirmektedir. Yatırımların getirileri şöyledir:

1- $16,000; 2- $22,000; 3- $12,000; 4- $8,000.

Yatırımlar için aşağıdaki miktarların yatırılması gerekmektedir:

1- $5,000; 2- $7,000; 3- $4,000; 4- $3,000.

Firmanın elinde $14,000 bulunduğuna göre en büyük toplam getiriyi elde etmek için hangi yatırıma para yatırması gerektiğini verecek 0-1 tamsayılı modeli kurunuz.

Sırt Çantası Problemi!!

Sırt Çantası Problemi Sadece bir kısıtı olan herhangi bir TP sırt çantası sorunu olarak isimlendirilir.

Bir diğer özellik de kısıtın ve amaç fonksiyonunun katsayıları negatif olmayan sayılardır.

Örneğin aşağıdaki model sırt çantası sorunudur:

max z = 8x1 + 11x2 + 6x3 + 4x4

Öyle ki; 5x1 + 7x2 + 4x3 + 3x4 ≤ 14

xj = 0 or 1 (j = 1,2,3,4)

Geleneksel öykü, bir sırt çantasında (örnekte kapasitesi 14’dür) bazı eşyaları (dört çeşit eşya) taşımak ile ilgilidir. Her eşyanın bir büyüklüğü ve taşıma sonucu elde edilecek bir değeri vardır (eşya 2 için büyüklük 7, değer 11’dir).

Amaç, sırt çantasına sığabilecek eşyaların toplam değerini enbüyüklemektir.

Sırt çantası sorunları genellikle kolay çözülürler.

Bütçeleme 0-1 tamsayılı modeli

Yeni kısıtlar

23

Stockco için önerilen modeli aşağıdaki koşulları

sağlayacak şekilde düzenleyiniz:

Stockco en fazla iki yatırım aracına yatırım yapabilir.

Stockco eğer ikinci yatırımı seçerse, birinci yatırımı da

seçmelidir.

Stockco eğer ikinci yatırımı seçerse dördüncü yatırımı

seçemez.

Çok Dönemli Sermaye Bütçeleme

Önümüzdeki üç yıllık planlama dönemi için dört

projenin değerlendirilmesi yapılacaktır. Her projeye

ait beklenen getiriler ile yıllık harcamalar aşağıdaki

tabloda gösterilmiştir. Üç yıl boyunca uygulamaya

konulacak projeleri belirleyiniz.

Harcamalar

Proje Getiri (NŞD) 1. Yıl 2.Yıl 3.Yıl

1 0.2 0.5 0.3 0.2

2 0.3 1 0.5 0.2

3 0.5 1.5 1.5 0.3

4 0.1 0.1 0.4 0.1

Kullanılabilir sermaye 3.1 2.5 0.4

Sabit maliyetlerin modellenmesi

Çok sayıda üretim ve yer seçimi sorunlarının

modellenmesi için de TP kullanılabilir.

Sabit maliyetleri ifade etmek için 0-1 değişken

tanımlanır

Bu değişken ile diğer değişkenler arası ilişki

kurulmalıdır!

Gandhi örneği

Çek Tahsilatı Ofisi Örneği

Sabit maliyetlerin modellenmesi

26

Gandhi tekstil firması üç tür ürün üretmektedir: t-shirt, şort ve pantolon.

Bu ürünleri üretmek için firma, haftalık olarak makine kiralamalıdır. T-shirt makinesinin kirası 200$, şort makinesinin kirası 150$ ve pantolon makinesinin kirası 100$’dır.

Üretimi gerçekleştirmek için kumaş ve işçilik de gerekmektedir.

Her hafta 150 saat işçilik ve 160 yard2 kumaş kullanılabilmektedir.

Ürünler için satış fiyatı ve değişken maliyetleri verilmiştir.

Gandhi’nin haftalık karını enbüyüklemek için tam sayılı programlama modelini kurunuz.

Ürün İşçilik

(saat)

Kumaş

(yard^2)

Satış fiyatı $ Değişken

maliyet $

T-shirt 3 4 12 6

Şort 2 3 8 4

Pantalon 6 4 15 8