Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

DAL-SINIR ALGORITMASI

No description
by

h n

on 26 October 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of DAL-SINIR ALGORITMASI

Tam Sayılı Programlama - Giriş
Tam Sayılı Programlama - Giriş
Tam Sayılı Programlama - Giriş
DAL-SINIR ALGORITMASI
Dal sınır
TAM SAYILI DOSRUSAL PROGRAMLAMAPROBLEMLER-N-N ÇÖZÜM YÖNTEMLER
Bir emlakçı gayri-menkul alım satımı ile gelir sağlamaktadır. Hali hazırda satın alabileceği iki tip mesken bulunmaktadır. Triplex villa fiyatı 195.000 $ ; apartman fiyatı 273.000 $ . Emlakçının elinde kullanılabilecek 1365.000 $ vardır. Satın alabileceği en fazla Triplex villa sayısı 4’tür. Ayrıca bir Triplex villa pazarlamak için 8 saat bir apartman pazarlamak için ise 80 saate ihtiyacı olan emlakçının toplam mesai süresi 280 saaattir. Triplex villa satıĢından 2000 $ apartman satıĢından 3000 $ kar elde edecek olan emlakçı için en uygun alım satım politikasını belirleyiniz. (x1: Triplex villa sayısı x2: apartman sayısı )

EMLAKÇI PROBLEMI
max. z 2x1 + 3x2
195x1 + 273x2 ≤ 1365
8x1 + 80x2 ≤ 280
x1 ≤4
x1, x2 ≥ 0 ve tamsayı

Matematiksel model LPR olarak çözülür. (LPRelaxation= normal LP sonuç, tamsayılı olduğu düĢünülmeden çözülen sonuç). Tora sonucu z=14.66 x1=2.44 x2=3.26 olarak bulunur. Bu miktarlarda ev alınamayacağı aĢikârdır.
* AS (Alt sınır) : LPR sonucunda elde edilmiĢ kesirli değiĢken değerlerinin bir alt değerlere (x1=2 x2=3 z=13) yuvarlanması ile elde edilen olurlu tamsayılı çözümdür AS=13 olacaktır. LPR= AS olduğunda optimum tamsayılı çözüm bulunmuĢ olur.


1.düğüm sonuçları için değiĢken değerlerinden kesir değeri büyük olanı seçeriz. .44 >.26 olduğundan x1 değiĢkenini kullanarak dallanmayı baĢlatırız. (minimizasyon problemlerinde de yine büyük kesirli olan değiĢken seçilir.)Dallar sırasıyla x1 ≤ 2 ve x1 ≥ 2+ 1 kısıtlarının ilave edildiği modelleri ifade eder. Bu dallar sırasıyla 2. ve 3. düğümü oluĢturur. Bu düğümler grafiksel ve matematiksel olarak aĢağıdaki tablolarda verilmiĢtir.
2. düğüm çözüldüğünde (program yardımıyla) LPR (z)=13.9 x1= 2 x2= 3.3 değerlerini verir. x1= 2 x2= 3 alındığında AS=13 olacaktır. LPR≠AS !


3. düğün çözüldüğünde LPR=14.58 x1= 3 x2= 2.86 olarak bulunur. AS= 12 LPR≠AS ! Bu aĢamada dallanmanın hangi düğümden devam edeceğine LPR değerine bakarak karar veririz. (Maksimizasyon probleminde en büyük, minimizasyon probleminde en küçük LPR’ye sahip olan düğümü seçeriz.) Bu aĢama için 3. düğümden dallandırmaya devam ederiz. 14.58>13.9


Dallar sırasıyla x2 ≤ 2 ve x3 ≥ 3 kısıtlarının ilave edildiği modelleri ifade eder. (önceki dallanmadan var olan x1 ≥ 3 kısıtı her iki dal için ayrıca geçerlidir)


Dallar sırasıyla x2 ≤ 2 ve x3 ≥ 3 kısıtlarının ilave edildiği modelleri ifade eder. (önceki dallanmadan var olan x1 ≥ 3 kısıtı her iki dal için ayrıca geçerlidir)


Karar değişkenlerinin tumu yada bir kısmı tamsayılı değerler
almalıdır.
Orneğin; 7.67 personel istihdam edilmesi, 3.4 banka şubesinin
kurulması bir anlam ifade etmez.
Kesirli değerler alan bu sayıları bir alt sayıya yuvarlamak da
optimal cozum olmayabilir ve hatta uygun cozum bolgesinde
yer almayabilir.
İşletmecilikte bazı karar problemleri “evet-hayır”, “0-
1”,“doğru-yanlış”,”satınalma-uretme” gibi onermeleri iceren
ikili değişken yapıda olabilir.
Bazı işletme sorunlarının doğrusal programlama ile
cozulebilmesine rağmen tam sayılı sonuc alınması
gerekir.
Orneğin; bir fabrikanın kurulup kurulmaması, bir
işcinin bir makinaya atanıp atanmaması “1” ve “0”
değerleri alan karar değişkenleri ile gercekleşebilir.
Yukarıda bahsedilene benzer sorunlarda doğrusal
programlamadaki bolunebilirlik (kesirli değerler)
varsayımı varsayımı gecersizdir.

Tam sayılı programlamada modelin boyutu arttıkça çözüm
de zorlasmaktadır.
DP’de, çözüm mutlaka uç noktalardan birisindedir ancak
Tam Sayılıda böyle bir sart bulunmaz.
DP’de kullanılan “Simplex” tabanlı çözüm algoritmaları
uygun bölgedeki uç noktaları deneyerek sürekli amaç
fonksiyonunu iyilestirecek sekilde ilerler ve optimallik testi
ile bir noktada (Zopt) durur.
Ancak, Tam Sayılıda çözüm uygun bölgedeki on binlerce
tamsayı degerinden birisidir ve DP’ye oranla olası çözüm
noktası daha fazladır.
1. Grafiksel Çözüm Yöntemi:
2. Gomory’nin kesme Düzlemi Yöntemi:
3. Dal S7n7r Yöntemi:
4. Tam Say7 Olmayan Çözümün Yuvarlanmas7 Yöntemi:
TDP problemlerinin deikenlerinin bir ksm veya hepsi
bazen üst veya alt snrla veya hem alt hem de üst snrla ayr ayr
artlanmaktadr. Bu tipteki optimizasyon problemlerinin çözümü için
çok genel bir yaklam dal-snr tekniidir. Bu yöntem A.H. Land ve
A.G. Doig tarafndan gelitirilmitir12. Bu yöntem ile minimizasyon
tipli bir problem çözülürken temel mantk öyledir13:
i. Tam sayl programlama uygun çözüm alan çok sayda alt setlere
ayrlr. Her bir alt set için snr deeri hesaplanr. Alt ve üst
snrlardan, her bir alt set içinde çözüm deeri seçilir.
ii. Bir alt snr (ilk alt setler arasndan en küçüü) ile alt set dier
bölümler için seçilir. Daha önce olduu gibi alt ve üst snrlarn her

ikisi de hesaplanr. Bölünmeye optimal çözüm bulunana kadar devam
edilir. Optimal çözüm herhangi bir alt set için alt snrdan daha büyük
olamaz.
Problem maksimizasyon tipli ise, çözüm yöntemi alt ve üst snr
seçimi dnda minimizasyon tipli problem gibidir.
Full transcript