Show simple item record

dc.contributor.advisorTürkay, Metin
dc.contributor.authorArslan, Özge
dc.date.accessioned2020-12-08T08:00:19Z
dc.date.available2020-12-08T08:00:19Z
dc.date.submitted2011
dc.date.issued2018-08-06
dc.identifier.urihttps://acikbilim.yok.gov.tr/handle/20.500.12812/169874
dc.description.abstractGeniş 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.
dc.description.abstractDevelopment 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.en_US
dc.languageEnglish
dc.language.isoen
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightsAttribution 4.0 United Statestr_TR
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectEndüstri ve Endüstri Mühendisliğitr_TR
dc.subjectIndustrial and Industrial Engineeringen_US
dc.titleFinding the extrema of continuous piecewise linear functions
dc.title.alternativeSürekli parçalı doğrusal fonksiyonların uç değerinin bulunması
dc.typemasterThesis
dc.date.updated2018-08-06
dc.contributor.departmentEndüstri Mühendisliği Anabilim Dalı
dc.subject.ytmModelling
dc.subject.ytmMathematics programming
dc.subject.ytmLinear programming
dc.identifier.yokid398672
dc.publisher.instituteFen Bilimleri Enstitüsü
dc.publisher.universityKOÇ ÜNİVERSİTESİ
dc.identifier.thesisid285329
dc.description.pages100
dc.publisher.disciplineDiğer


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

info:eu-repo/semantics/openAccess
Except where otherwise noted, this item's license is described as info:eu-repo/semantics/openAccess