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ı: 61
Ö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
- Bütünleşik üretim ve dağıtım çizelgeleme problemleri için çözüm yaklaşımları
Solution approaches for integrated production and distribution scheduling problems
ECE ÇETİN YAĞMUR
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiKonya Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. SAADETTİN ERHAN KESEN
- Hipersezgisel yöntemlerle lojistik ağ tasarımı ve optimizasyon
Logistic network design and optimization using hyperheuristic methods
VURAL EROL
Doktora
Türkçe
2017
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MURAT BASKAK
PROF. DR. GÜLGÜN KAYAKUTLU
- Planning of train movements in single track railways
Tek hatlı demiryollarında tren hareketlerinin planlanması
GÖKÇE AYDIN
Doktora
İngilizce
2015
UlaşımYıldız Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. İSMAİL ŞAHİN
- Parameter synthesis for timed automata via path analysis
Zamanlı otomat için yol analizi ile parametre sentezi
BURKAY SUCU
Doktora
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. EBRU AYDIN GÖL
- An integrated approach for robust airline scheduling aircraft fleeting and routing with cruise speed control
Dayanıklı havayolu çizelgeleme, filo tipi atama ve uçak rotalama problemlerine seyir süresi kontrolü ile bütünleşik bir yaklaşım
HÜSEYİN GÜRKAN
Yüksek Lisans
İngilizce
2014
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET SELİM AKTÜRK
DOÇ. DR. SİNAN GÜREL