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ı, Dal sınır algoritması, Derece, Kapasite kısıtlama, Kapsarağaç problemi, Minimum Weight Directed Spanning Tree, Capacity Constraint, Hop Constraint, Degree Constraint, Branch and Bound. IV, Branch bound algorithm, Degree, Spanning tree problem
- 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ı: Belirtilmemiş.
Ö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
- İstanbul Çatalca bölgesinde uzaktan algılama yöntemleri ile metropoliten analizi
Başlık çevirisi yok
F.ZEHRA ALKAN
- 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
- Fizyolojik ölçümlerden elde edilen özellikler kullanılarak enerji tüketimi kestirimi için özgün bir yaklaşım geliştirilmesi
Developing a novel approach to estimate energy expenditure using features from physiological measurements
HÜSEYİN YANIK
Doktora
Türkçe
2022
Elektrik ve Elektronik MühendisliğiMersin ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. EVREN DEĞİRMENCİ
- İzmir Bayraklı Toplum Sağlığı Merkezi bölgesinde bulunan ilköğretim ikinci kademe öğrencilerinin tıbbi ve sosyal durumları ve bunları etkileyen değişkenler
Medical and social status of students in second grade of primary schools within İzmir Bayrakli Community Health Center area and effective variables
TÜLAY ŞEN ÖZTÜRK
Yüksek Lisans
Türkçe
2018
Halk SağlığıManisa Celal Bayar ÜniversitesiHalk Sağlığı Ana Bilim Dalı
PROF. DR. ERHAN ESER