An experimental investigation of a new multiplex method for linear programming

Die onlangse interne en iteratiewe metode van Karmarkar het ’n hernude belangstelling in ouer alternatiewe metodes, verskillend van die simpleksmetode, gewek. Hier word ’n nuwe muitipleks- en meetkundige metode, watsekere ooreenstemmings met die ouer metodes toon, voorgestel en geimplementeer. In die metode word die oplossing verkry deur ’n gradientbaan deur die binnekant van die moontlike gebied, en deur subruimtes van kleiner dimensie wat ooreenstem met die begrensende hipervlakke van die moontlike gebied, te voig. Die baan beweeg vanaf ’n aanvanklike moontlike punt deur ’n reeks lineêre stappe na ’n verteks van die politoop wat deur die begrensings gedefinieer is. Alhoewel dit soortgelyk skyn te wees, verskil die huidige metode tog fundamenteel van Rosen se gradiëntprojeksiemetode in die opsig dat die agtereenvolgende soekrigtings verkry word vanaf die gradiënte van gereduseerdeprobleme van kleiner dimensie. Wanneer hierdie rigtings na die oorspronklike ruimte getransformeer word, stem dit nie noodwendig met die gradientprojeksierigtings ooreen nie. As ’n verteks bereik word, bereken die nuwe algoritme of dit optimaal is al dan nie. Dit word gedoen deur ’n eenvoudige perturbasieprosedure toe te pas waardeur geperturbeerde punte, as ’n neweproduk van die berekende baan na die verteks, gegenereer word. Indien nie optimaal nie, gaan die algoritme voort deur oor te begin vanaf ’n geperturbeerde punt (op ’n geskikte rand) met groter funksiewaarde, en die baan word voortgesit totdat ’n nuwe verteks bereik word. Dit sal blyk dat die resultate van hierdie eksperimentele ondersoek na die betrokke metode belowend is, aangesien die metode suksesvol op ’n verskeidenheid toetsprobleme toegepas is