Minimum weight directed spanning tree problem with degree, hop and capacity constraints
Derece, hoplama ve kapasite kısıtlamalı yönlü en küçük kapsarağaç problemi
- Tez No: 116488
- Danışmanlar: YRD. DOÇ. DR. CÜNEYT F. BAZLAMAÇCI
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: En Küçük Yönlü Kapsarağaç, Kapasite kısıtlaması, Hoplama kısıtlaması, Derece kısıtlaması, Dal ve Sınır. vı, Minimum Weight Directed Spanning Tree, Capacity Constraint, Hop Constraint, Degree Constraint, Branch and Bound. IV
- Yıl: 2001
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 94
Özet
oz DERECE, HOPLAMA VE KAPASİTE KISITLAMALI YÖNLÜ EN KÜÇÜK KAPSARAĞAÇ PROBLEMİ Ertem, Dilek Yüksek Lisans Tezi, Elektrik ve Elektronik Mühendisliği Bölümü Tez Yöneticisi: Yrd. Doç. Dr. Cüneyt F. Bazlamaca Nisan 2001, 81 Sayfa Yönlü en küçük kapsarağaç problemi (MDTP), kısıtlamaları açısından zengin, iyi bilinen bir katışımsal eniyileme problemidir. Bu çalışmanın amacı MDTP'nin bazı uzantılarını araştırmak ve derece, hoplama ve kapasite kısıtlamaları ile birleştirilmiş bir NP-tam formülasyonunu çözmektir. Olabilir çözümler üretmek için, iki adet buluşsal yaklaşım geliştirilmiştir. Ayrıca, birleşik problemde alt sınırları bulmak iki adet Lagrangean gevşetmelerinin subgradient eniyilemesi geliştirilmiştir. Alt sınırları bulmak için ek olarak doğrusal programlama yaklaşımı da kullanılmıştır. Son olarak birleşik problem, subgradient eniyilemesine dayalı birdal ve sınır stratejisi ile en iyi çözüme ulaştırılmıştır. Önerilen algoritmaların performansları deneysel testler ile araştırılmış ve hesaplama sonuçlan açıklanmıştır.
Özet (Çeviri)
ABSTRACT MINIMUM WEIGHT DIRECTED SPANNING TREE PROBLEM WITH DEGREE, HOP AND CAPACITY CONSTRAINTS Ertem, Dilek M.S., Department of Electrical and Electronics Engineering Supervisor: Asst. Prof. Dr. Cüneyt F. Bazlamaçcı April 2001, 81 pages The minimum weight directed spanning tree problem (MDTP) is a well- known combinatorial optimization problem, which is also rich in its variants. The objective of this study is to survey some extensions of the MDTP and to solve an NP-complete formulation, which incorporates three additional constraints, namely degree, hop and capacity. Two heuristic approaches are developed for generating feasible solutions. Furthermore subgradient optimization of the Lagrangean relaxation for two different formulations is employed to find lower bounds for the combined problem. In addition, linear programming is also used to find lower bounds. Finally the combined problem is solved to optimality with a branch and bound strategy based on subgradient optimization. The performances of the mproposed algorithms are investigated through empirical tests and computational results are reported.
Benzer Tezler
- Solving connection problems in mountains by cooperative game theory
Dağlardaki bağlantı problemlerinin işbirlikçi oyun teorisi ile çözümü
HAMID ALZAKI
Yüksek Lisans
İngilizce
2016
MatematikSüleyman Demirel ÜniversitesiMatematik Ana Bilim Dalı
DOÇ. DR. SIRMA ZEYNEP ALPARSLAN GÖK
- Parçacık takviyeli karma malzemelerdeki artık gerilmelerin sonlu elemanlar yöntemiyle analizi
The finite elements analysis of the thermal residual stresses in the particulate reinforced metal matrix composites
ALİ CANSUN
- İstanbul Çatalca bölgesinde uzaktan algılama yöntemleri ile metropoliten analizi
Başlık çevirisi yok
F.ZEHRA ALKAN
- Telekomünikasyon şebekelerinin trafik yönlendirmesinde yapay zeka uygulamaları
Artificial intelligence applications of routing for telecommunication networks
ERSAN AKSOY
Yüksek Lisans
Türkçe
2001
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. GÜNSEL DURUSOY
- Yapıştırıcıların genel özellikleri ve çekme gerilmesine maruz yapışma birleşmesinin analitik ve nümerik olarak incelenmesi
Başlık çevirisi yok
LEVENT KODAKOĞLU
Yüksek Lisans
Türkçe
1996
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak Mühendisliği Ana Bilim Dalı
DOÇ. DR. TEMEL KATİL