Tamsayılı programlama problemleri için garanti değerli algoritmalar
Algorithms with guarantee value for integer programming problems
- Tez No: 215946
- Danışmanlar: PROF. DR. URFAT G. NURİYEV
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2008
- Dil: Türkçe
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Bölümü
- Bilim Dalı: Matematik Ana Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
Bilindiği gibi çoğu tamsayılı optimizasyon problemi NP-tam problemdir ve P=NP olmadığı sürece bu problemler için polinom zamanda kesin çözüm veren algoritmalar bulma olasılığı azdır. Bu nedenle, son yıllarda NP-tam problemler için garanti değerli algoritmalar tasarlamak ilgi çekici konulardan biri haline gelmiştir.Bu çalışmada teknik ve ekonomik alanlarda birçok uygulamaları olan tek boyutlu Tamsayılı Sırt Çantası Problemleri incelenmiş olup bu problemler için greedy algoritmaları önerilmiştir. Algoritmaların ürettiği sonuçların optimal çözüme ne kadar yakın olduğunun bulunması amacıyla, önerilen algoritmaların garanti değerleri hesaplanmıştır. Ayrıca Tamsayılı Maksimizasyon Sırt Çantası Problemi için tümleyen problem tanımlanmış ve bu probleme dayanarak daha önce hesaplanan garanti değerin iyileştirilmesi amaçlanmıştır.
Özet (Çeviri)
It is known that many integer optimization problems are NP-complete and there is little probabilty to find algorithms for these problems that give exact solutions in polinomial time unless P=NP. As a result, designing algorithms with guarantee value for NP-complete problems has become one of the attractive subjects in recent years.In this thesis, one-dimensional Integer Knapsack Problems, which have many applications in technical and economic area, have been studied; then greedy algorithms have been proposed for these problems. Guarantee values of these algorithms have been calculated in order to determine how much close the results returned by the algorithms are to optimal solutions. Furthermore, complementary problem for Integer Maximization Knapsack Problem has been defined and in terms of this problem, it has been aimed to improve guarantee value calculated before.
Benzer Tezler
- Kapasite ihtiyaç planlaması ve sonlu çizelgeleme
Capacity requirements planning and finite scheduling
CÜNEYT DEĞERTEKİN
- Computational analysis of the search based cuts on the multidimensional 0-1 knapsack problem
Araştırma tabanlı kesmelerin çok boyutlu 0-1 sırt çantası problemleri üzerinde hesapsal analizi
DUYGU PEKBEY
Yüksek Lisans
İngilizce
2003
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. OSMAN OĞUZ
- U-tipi montaj hattı dengeleme problemleri için yeni modeller ve otomotiv yan sanayiinde bir uygulama
New models for U-shaped assembly line balancing problems and an application in automotive spare parts industry
YAKUP KARA
- Esnek üretim sistemlerinde yerleşimi gözönüne alan yükleme ve rotalama problemleri için amaç programlama modeli
Goal programming model for loading and routing problem considering location in flexible manufacturing systems
EDİZ ATMACA
Doktora
Türkçe
2000
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. SERPİL EROL
- Çok ölçütlü akış tipi çizelgeleme problemleri için çözüm yaklaşımları
The solution approaches for multicriteria flowshop scheduling problems
TAMER EREN
Doktora
Türkçe
2004
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ.DR. ERTAN GÜNER