Finding the extrema of continuous piecewise linear functions
Sürekli parçalı doğrusal fonksiyonların uç değerinin bulunması
- Tez No: 285329
- Danışmanlar: DOÇ. DR. METİN TÜRKAY
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2011
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 100
Özet
Geniş uygulama alanları olması nedeniyle parçalı doğrusal fonksiyonların etkin tekniklerlemodellenmesi her zaman dikkat çeken bir konu olmuştur. Bu amaçla çeşitli modellemeteknikleri geliştirilmiştir; tamsayı karışık programlama modelleri, dallara ayırma odaklıyöntemler, özel yapıda parçalı doğrusal fonksiyonlar için lineer programlama modelleribu tekniklere örnek olarak gösterilebilir. Bütün bu çalışmalar faydalı olmakla birlikte, yakompleks formüller olmuş veya kısıtlı bir sınıf parçalı doğrusal fonksiyonları modellemeyeyoğunlaşmıştır.Biz bu çalışmada sürekli parçalı doğrusal fonksiyonların uç değerinin başka kısıtlar ol-madığı hallerde bulunmasını sağlayan yeni bir lineer programlama modeli sunmaktayız.Öncelikle modelimizin sürekli parçalı doğrusal fonksiyonların uç değerini tam bir şekildebulduğunu gösteriyoruz. Modelimizi geliştirirken iki gerçekten faydalanıyoruz. Bunlardanilki simplex algoritmasının en iyi sonucu ararken olanaklı bölgenin uç noktalarında gezdiği,ikincisiyse sürekli parçalı doğrusal bir fonksiyonun uç değerinin her zaman kırılma nok-talarında bulunduğudur. Buradan yola çıkarak, geçerli bölgesinin uç noktaları tanımladığıfonksiyonun kırılma noktalarına tamamen denk gelen bir lineer programlama modeli geliştirdik.Böylelikle simplex algoritmasının parçalı doğrusal fonksiyonun uç değerini tam olarak bul-masını sağladık. Modelimiz ikili değişkenler içermediğinden genel amaçlı bir lineer program-lama çözümleyicisiyle çözülebilmektedir. Ayrıca modelimiz literatürde yer alan modellerdendaha az kısıt ve değişken içermektedir. Sonuç olarak, bütün bu özellikler modelimizin kom-pleksitesini azaltırken çözüme ulaşma süresini de kısaltmaktadır. Modelimizi literatürdekien yaygın modellerle hesaplamalı olarak kıyaslayarak da bulgularımızı desteklemekteyiz.Son olarak, modelimizin ayrılabilir parçalı sürekli doğrusal fonksiyonların uç değerlerininbulunması için kullanılabileceğini de gösteriyoruz.
Özet (Çeviri)
Development of accurate models and efficient solution algorithms for piecewise linear functions (PWL)attracted a lot of attention due to the wide range of application areas of PWL functions. There havebeen several attempts to develop exact and efficient optimization models. All of these attempts provideuseful insights; however, they are either complex or target a very specific class of PWL functions.In this study, we present a novel linear programming formulation to find the extrema of continuous PWLfunctions when there are no other constraints. We first prove that our formulation finds the extrema of any continuous PWL exactly. While developing this formulation we make use of two facts: First, simplexalgorithm moves along the extreme points of feasible region while searching the optimal solution. Second, extrema of any continuous PWL function lies at its break points. We develop a linear programming formulationwith a special feasible region such that extreme points of this region overlap with break points of corresponding PWL function. This property enables simplex algorithm to find extrema of PWL function exactly. Our formulation is free from binary variables and has less number of variables and constraints than existing formulations in literature. Hence, all these properties decrease the complexity of our formulation and CPU time to find the optimal solution. We support our findings by computationally benchmarking our formulation with most common formulations in literature. Finally, we show that our formulation can also be used to find the extrema of separable piecewise continuous linear functions.
Benzer Tezler
- Şanlıurfa'da iklimden kaynaklanan risklerin tarımsal meteorolojik açıdan analizi
Agricultural meteorological analysis of risks resulting from climate in Şanlıurafa
BURAK IŞIK
Yüksek Lisans
Türkçe
2024
Meteorolojiİstanbul Teknik ÜniversitesiMeteoroloji Mühendisliği Ana Bilim Dalı
PROF. DR. LEVENT ŞAYLAN
- An empirical investigation on improving fairness testing for machine learning models
Makine öğrenme modelleri için adalet testlerinin geliştirilmesi üzerine ampirik bir araştırma
UMUTCAN KARAKAŞ
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. AYŞE TOSUN KÜHN
- A new method for parameter design optimization of products or processes with an ordinal categorical response
Sıralı kategorik yanıta sahip ürün ve süreçlerin tasarım parametresi en iyilemesi için yeni bir metot
PINAR ERDOĞAN
Yüksek Lisans
İngilizce
2022
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. GÜLSER KÖKSAL
DR. ÖĞR. ÜYESİ LEMAN ESRA DOLGUN
- Seyhan ve Çoruh akarsu havzalarında kuraklık analizi
Drought analysis in Seyhan and Çoruh river basins
NUR BANU ÖZÇELİK
Yüksek Lisans
Türkçe
2021
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. BİHRAT ÖNÖZ
- Portföy yönetiminde dinamik varlık yönetim stratejileri
Dynamic asset allocation strategies in portfolio management
MUSTAFA DUMAN
Yüksek Lisans
Türkçe
2000
BankacılıkMarmara ÜniversitesiSermaye Piyasası ve Borsa Ana Bilim Dalı
YRD. DOÇ. DR. ÖZLEM KOÇ