Multiple and alternate optima of lp problems via recursive milp: A matlab implementation
Dp problemlerinde özyineli ktdp ile çoklu ve alternatif optimal çözümler: Matlab uygulaması
- Tez No: 325597
- Danışmanlar: PROF. DR. UĞUR AKMAN
- Tez Türü: Yüksek Lisans
- Konular: Kimya Mühendisliği, Chemical Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2012
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Kimya Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 147
Özet
Bu çalışma, Carnegie Mellon Üniversitesi'nde Prof. Grosmann'ın ekibi tarafindan geliştirilen Özyineli Karma Tamsayılı Doğrusal Programlama (ÖKTDP) algoritması üzerinedir. Bu algoritma, Doğrusal Programlama (DP) problemlerinin tüm alternatif optimal çözümlerini kesin olarak bulmaktadır. Algoritmanın temel avantajı, GAMS cebirsel molelleme sistemi gibi verimli bir dilde yazılabilmesi ve DP çözücüsünde değişiklik gerektirmemesidir. GAMS'te yazılmış olan ÖKTDP kodu genel olmayıp probleme özel olduğundan, her farklı problem için değiştirilmesi gerekmekteydi. Prof. Akman başlangıç seviyesindeki bir kullanıcı tarafından bile ÖKTDP kısmının değiştirilmesi gerekmeden kolayca kullanılabilecek genel bir GAMS kodu yazmıştır. Bu tez çalışmasında, Prof. Akman'ın bu çalışmasının son sınamaları yapılmış ve algoritma MATLAB'a uyarlanmıştır. Ana ve fonksiyon kısımlarından oluşan bir MATLAB kodu geliştirilmiştir. Ana kısımda kullanıcı, probleme özel verileri tanıtmalı ve bitiş kriterini belirlemelidir. Bu kısmın sonunda DP ve ÖKTDP problemlerinin özyinelemeli olarak çözüldüğü, standart DP problemleri için değişiklik gerektirmeyen, fonksiyon kısmı çağırılmaktadır. Geliştirilen MATLAB kodu genel olup, her DP/ÖKTDP çözücüsü ile kullanılabilmektedir. Bu kod, kullanıcıya bir DP probleminin tüm alternatif optimal çözümlerini ve sonraki en iyi K köşe çözümü verir. Karar alacak olan kişi, kodun bir defa çalıştırılması ile amaç fonksiyonu değeri ile bir sonraki en iyi değer veya sonraki en iyi K değer arasındaki farkı görebilecektir. Alternatif çözümler, kullanıcının optimizasyon modeline açıkça eklenemeyen etmenleri de göz önünde bulundurarak karar vermesine imkan sağlamaktadır. Birtakım DP örnekleri GAMS ve MATLAB kullanılarak çözülmüş ve her iki yazılımla aynı sonuçlar elde edilmiştir. Her iki yazılımda da, kullanılan DP/ÖKTDP çözücülerine bağlı olarak, bazı sonuçların tekrarlandığı gözlemlenmiştir. Alterfatif optimal çözümlerin yakınlığını gözlemlemek ve tekrarlanan çözümleri elemek amacıyla hiyerarşik çözüm kümelerini gösteren öbekağacı çizimi kullanılmıştır.
Özet (Çeviri)
In this thesis, the Recursive Mixed Integer Linear Programming (RMILP) algorithm invented by Prof. Grossman?s group at the Carnegie Mellon University is studied. The algorithm is guaranteed to find all the alternate optima of the LP problems. The main advantage of the proposed algorithm is that it can be built on efficient tools such as GAMS algebraic modeling system and does not require any modification of the LP solver. But the RMILP code written in GAMS was not generic. Since it was problem specific coding, it must be changed for each different problem. Prof. Akman generated a generic GAMS code that can be used even by a novice LP user without modification of the recursive MILP part by the user. In this thesis, final tests of Prof. Akman?s work and implementation in MATLAB were performed. With this purpose, a MATLAB code consisting of two parts namely, a function part and a main part is developed. In the main part, the user enters the problem specific data and termination criterion. Then the function part is called, where LP and MILP problems are solved recursively. The same function part can be used for any standard LP problem without any modification. The MATLAB code is generic; it can accommodate any LP/MILP solver. The MATLAB code developed provides the user with all the alternate optimal solutions, as well as next K best vertex solutions of an LP problem. With this capability, the decision maker will see the difference between the optimal value and the next best objective function value, or next K best objective function values with a single run of the code. Alternate solutions enable decision maker to make choice by considering other incremental factors that are not explicitly incorporated into the optimization model. Several LP problems were solved using GAMS and MATLAB and the same results were obtained on both software platforms. In both GAMS and MATLAB, some solutions were replicated depending on the LP/MILP solvers. A dendrogram, representing hierarchical solution clusters, was used to visualize the proximity of the alternate solutions and to eliminate replicates.
Benzer Tezler
- Kaynak kısıtlı proje programlama problemlerinin çözümü için yeni yöntem ve algoritmalar
New methods and algorithms for solving the resource-constrained project scheduling problem
İHSAN UĞUR
- Bulanık çok modlu kaynak kısıtlı proje çizelgeleme problemlerinin çözümü için matematiksel bir model
A mathematical model for the solution of the fuzzy multi mode resource-constrained project scheduling problems
ÖMER ATLI
Doktora
Türkçe
2012
Endüstri ve Endüstri MühendisliğiHava Harp Okulu KomutanlığıEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. CENGİZ KAHRAMAN
- Veri zarflama analizi ve bankacılık sektöründe bir uygulama
Data envelopment analysis and an application in the banking sector
İBRAHİM İLERİ
Yüksek Lisans
Türkçe
1997
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. TUFAN V. KOÇ
- Location-allocation problems with multi-commodity flows: Exact and approximate solution methods
Çok mallı yerleşim-dağıtım problemleri: Kesin ve yaklaşık çözüm yöntemleri
MEHMET HAKAN AKYÜZ
Doktora
İngilizce
2011
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. TEMEL ÖNCAN
PROF. İ. KUBAN ALTINEL
- New capacity allocation policies in revenue management
Gelir yönetiminde yeni kapasite dağıtım politikaları
NURŞEN AYDIN
Doktora
İngilizce
2014
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ŞEVKET İLKER BİRBİL