Új monoton jellegű szimplex algoritmusok elemzése megengedettségi feladatok esetén

Bilen, Filiz and Csizmadia, Zsolt and Illés, Tibor (2007) Új monoton jellegű szimplex algoritmusok elemzése megengedettségi feladatok esetén. ALKALMAZOTT MATEMATIKAI LAPOK, 24. pp. 163-185. ISSN 0133-3399

Preview

Text 08ALKMAT_24.pdf - Published Version Download (2MB) | Preview

Abstract

Anstreicher és Terlaky (1994) monoton szimplex algoritmusának megfogalmazzuk egy olyan új variánsát megengedettségi feladatokra, amelynek a lépésszámát egy a szokásostól gyengébb nem degeneráltsági feltevés mellett mA adja meg, ahol Д a feladat adataiból kiszámítható konstans, m a feltételek száma. А Д konstans, a feladat leírásához szükséges számítógépes tárigénynek - az adatok bithosszának - egy polinomjával nem mindig korlátozható. Erősen degenerált feladatok esetén a végességet olyan index választási szabályok segítségével biztosítjuk, melyek nagyfokú flexibilitást tesznek lehetővé a pivot pozíció meghatározásakor, elősegítve a numerikusan nehéz pivot pozíciók elkerülését. Az algoritmusunk végességének a bizonyításához olyan általános keretet használunk - s-monoton pivotálási szabályok tulajdonságait - , amely magában foglalja a szokásos minimál indexes szabály mellett, a "Last In First Out" (LIFO) és a "mostoften- selected-variable" (MOSV) szabályt is. Az s-monoton pivotálási szabályok fogalma jól illeszkedik a lineáris programozási pivot algoritmusok témaköréhez is. A megengedettségi feladatok egy pivot algoritmusára (MBU-szimplex módszer új variánsára) bemutatott, az s-monoton pivot szabály fogalmát használó végesség bizonyítás természetes módon vihető át több lineáris programozási pivot algoritmus végességének az igazolására is. Az algoritmus lépésszámának elemzése az eredeti monoton szimplex algoritmus és a prímái szimplex algoritmus első, illetve második fázisára, továbbá az úgynevezett exterior-point simplex algoritmusra is átvihető nem degeneráltsági feltevés mellett. Kulcsszavak: megengedettségi feladat, monoton szimplex algoritmusok, degeneráltság, lineáris programozás, index választási szabályok.

Actions (login required)

Edit Item