Geri Dön

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

  1. Tez No: 116488
  2. Yazar: DİLEK ERTEM
  3. Danışmanlar: YRD. DOÇ. DR. CÜNEYT F. BAZLAMAÇCI
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. 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
  7. Yıl: 2001
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2016

    MatematikSüleyman Demirel Üniversitesi

    Matematik Ana Bilim Dalı

    DOÇ. DR. SIRMA ZEYNEP ALPARSLAN GÖK

  2. 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

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    PROF.DR. AHMET ARAN

  3. 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

    Türkçe

    2001

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    PROF.DR. GÜNSEL DURUSOY

  4. 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

    Türkçe

    1996

    Uçak Mühendisliğiİstanbul Teknik Üniversitesi

    Uçak Mühendisliği Ana Bilim Dalı

    DOÇ. DR. TEMEL KATİL