Geri Dön

Theoretical and experimental analysis of a saddle point algorithm for linear programming

Doğrusal programlama için bir eyer noktası algoritmasının kuramsal ve deneysel analizi

  1. Tez No: 50483
  2. Yazar: DENİZ AKSEN
  3. Danışmanlar: DOÇ.DR. İ. KUBAN ALTINEL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 1996
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Belirtilmemiş.
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 154

Özet

Bu tezde, doğrusal bir amaç fonksiyonunun doğrusal eşitlik ve eşitsizliklerden oluşan kısıtlar kümesi üzerinde eniyilenmesi olarak tanımlanan doğrusal programlama problemleri için, Shang Yi tarafından geliştirilen ve Eyer Noktası Algoritması olarak isimlendirilen bir algoritmanın kuramsal temelleri ile test problemleri üzerindeki deneysel başarımı incelenmiştir. Algoritma, bir doğrusal programlama problemine ait Lagrange fonksiyonundan bir dönüşümle elde edilen fonksiyonun belirlediği yüzeyin eyer noktasını Eniyi Kontrol Kuramı 'ndan bilinen formüller yardımıyla bulur. Bu eyer noktası, doğrusal programlama probleminin eniyi birincil (primal) ve eniyi çifteş (dual) çözümünü içermektedir. Karlin ve Uzawa'nin teoremlerine göre, çözümü olan bir dışbükey programlama probleminin eniyi çözümü ve bu çözüme ait Lagrange çarpanları, programın Lagrange fonksiyonunun eyer noktasını oluştururlar. Bu ifadenin tersi de ek bazı varsayımlar altında doğrudur; çözümlü bir dışbükey programlama probleminin Lagrange fonksiyonunun eyer noktası, o programın eniyi çözümünü ve bu çözüme ait Lagrange çarpanlarını* verir. Shang Yı'nin algoritması her türlü doğrusal programın aynı zamanda bir dışbükey program olduğu gerçeğinden yola çıkmakta ve Lagrange fonksiyonundan bir dönüşümle elde edilen fonksiyonun eyer noktasını bularak doğrusal programa ait birincil ve çifteş problemleri eşzamanda çözmektedir. Eyer Noktası Algoritması'nın yakınsama hızı da bu tezde ele alınmıştır. Algoritma üzerinde yapılan deneyler, yakınsama hızının pratikte çok düşük olduğunu ortaya koymuştur. Bu bulgu, Shang Yı'nin bazı varsayımlara dayananarak algoritmanın kuramsal hızı için önerdiği çokterimli irade üe çelişmektedir. V 14-

Özet (Çeviri)

ABSTRACT In this thesis, theoretical background of a“Saddle Point Algorithm”and its experimental performance have been analyzed. This algorithm which is developed by Shang Yi solves linear programming problems. Using a set of formulae from Optimal Control Theory, the algorithm finds the saddle point of a saddle surface obtained by transforming the Lagrange function of a given linear programming problem. This saddle point covers both the optimal primal and dual solutions. According to Karlin and Uzawa's Theorems, an optimal solution of a feasible convex programming problem and its corresponding Lagrange multipliers constitute the saddle point of the program's Lagrange function. The reverse of this statement is also true under some additional assumptions. At this point, departing from the fact that any linear program is also a convex program, Shang Yi developed an approach that solves simultaneously primal and dual problems of a linear program by finding the saddle point of its Lagrange function. The speed of convergence of the Saddle Point Algorithm has also been discussed. Experimentation with the algorithm has shown that the algorithm is much slower than Shang Yi's claim. This observation contradicts the polynomial expression derived for the algorithm's theoretical speed of convergence.

Benzer Tezler

  1. Tez No

    478604

    Comperative structural analysis of suspension bridges with diagonal and vertical hangers

    Eğik ve düşey askı kablolu asma köprülerin kıyaslamalı yapısal analizi

    MUSTAFA MERT EYÜPGİLLER

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    İnşaat MühendisliğiYıldız Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. ÇAĞRI MOLLAMAHMUTOĞLU

  2. Tez No

    653970

    Theoretical and experimental analysis of a soft and miniature quadruped

    Dört bacaklı ve yumuşak bir minyatür robotun kuramsal ve deneysel analizi

    TAMER TAŞKIRAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2020

    Makine Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ONUR ÖZCAN

  3. Tez No

    323016

    Bir pnömatik motor kontrol sisteminin teorik ve deneysel analizi

    Theoretical and experimental analysis of a pneumatic engine control system

    HALUK GÜNEŞ

    Doktora

    Türkçe

    Türkçe

    2012

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi Üniversitesi

    Makine Eğitimi Ana Bilim Dalı

    DOÇ. DR. RAMAZAN BAYINDIR

    PROF. DR. ATİLLA KOCA

  4. Tez No

    155626

    Buji ateşlemeli motorlarda yakıt-hava çevriminin modellenerek motor performansının teorik ve deneysel analizi

    Theoretical and experimental analysis of engine performance by modelling fuel-air cycle in spark ignition engine

    MEHMET AKİF CEVİZ

    Doktora

    Türkçe

    Türkçe

    2004

    Makine MühendisliğiAtatürk Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    Y.DOÇ.DR. FİKRET YÜKSEL

  5. Tez No

    237717

    Metalik sacların hidrolik şekillendirme ile şekillenebilirliğinin teorik ve deneysel incelenmesi

    Theoretical and experimental analysis of formability of metal sheets by hydroforming

    TAHSİN AĞYEL

    Yüksek Lisans

    Türkçe

    Türkçe

    2009

    Metalurji MühendisliğiKarabük Üniversitesi

    Teknik Eğitim Bölümü

    DOÇ. DR. MUSTAFA YAŞAR

Geri Dön