An experimental investigation of a new multiplex method for linear programming
Suid-Afrikaanse Tydskrif vir Natuurwetenskap en Tegnologie/South African Journal of Science and Technology
| Field | Value | |
| Title | An experimental investigation of a new multiplex method for linear programming ’n Eksperimentele ondersoek na ’n nuwe multipleksmetode vir lineêre programmering | |
| Creator | Snyman, J. A. van Rooyen, M. | |
| Description | Karmarkar’s recent internal and iterative method for linear programming problems has resulted in a renewed interest in some older alternatives, other than the simplex method. Here a new multiplex and geometric method, which has some features in common with the older methods, is proposed and implemented. In this method the solution is found by following a gradient path through the interior of the feasible region and through subspaces of reduced dimension corresponding to the bounding hyper-surfaces of the feasible region. The path moves from an initial feasible point through a sequence of linear steps to a vertex of the polytope defined by the constraints. Although similar, the current method differs fundamentally from Rosen’s gradient projection method in that the successive search directions are obtained from the gradients of reduced problems of lesser dimension. These directions, when translated to the original space, do not necessarily correspond to the gradient projection directions. Once a vertex has been reached the new algorithm determines whether or not it is optimal by applying a simple perturbation procedure for which the perturbed points are generated as a by-product of the computed path to the vertex. If not optimal the algorithm proceeds by restarting from a perturbed point (on a suitable edge) with increased function value and the path is continued until the next vertex is reached. It is shown that the results of this experimental investigation of this method is promising since it has successfully been applied to a variety of test problems. 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. | |
| Publisher | AOSIS | |
| Date | 1987-03-17 | |
| Identifier | 10.4102/satnt.v6i2.948 | |
| Source | Suid-Afrikaanse Tydskrif vir Natuurwetenskap en Tegnologie; Vol 6, No 2 (1987); 82-88 Suid-Afrikaanse Tydskrif vir Natuurwetenskap en Tegnologie; Vol 6, No 2 (1987); 82-88 2222-4173 0254-3486 | |
| Language | eng | |
| Relation |
The following web links (URLs) may trigger a file download or direct you to an alternative webpage to gain access to a publication file format of the published article:
https://journals.satnt.aosis.co.za/index.php/satnt/article/view/948/1965
|
|
ADVERTISEMENT
