Change search
ReferencesLink to record
Permanent link

Direct link
Solving linear optimization problems using a simplex like boundary point method in dual space
2006 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

This thesis treats an algorithm that solves linear optimization problems. The algorithm is based on a similar idea as the simplex method but in this algorithm the start value also might be an inner point or a boundary point at the feasible region. The start value does not necessarily have to be a corner point that the simplex algorithm demands. The algorithm solves problems in standard form. That means that the constraints are with equality and every variable must be positive. The algorithm operates in the dual space to the original problem. During the progress of the algorithm the iteration points will be on the boundary at the feasible region to the dual problem and finally end up in a corner. Afterwards the iteration values go from corner to corner until finally the optimum is reached, just like the simplex algorithm. The expected time to solve linear optimization problems with this algorithm seems to be polynomial in time with respect to the size of the problem, thought the worst case behavior has not been analyzed. If the last iteration value is just an approximate solution to the dual problem the algorithm will transfer it to a quite good approximation to the primal problem. Much of the development in this thesis is a continuation of a similar algorithm which was done one year ago. In the introduction and in the second chapter different forms of linear optimization problems are described. The algorithm is implemented in Matlab and the code can be find in the appendices of this paper. There are also different versions, which solve different types of problems. One for general problems and one for network flow problems.

Place, publisher, year, edition, pages
Keyword [en]
Technology, linear programming, linear optimization, simplex method, sparse matrices, algorithm, matlab
Keyword [sv]
URN: urn:nbn:se:ltu:diva-58062ISRN: LTU-EX--06/285--SELocal ID: ea617416-97e1-413d-bfda-c297ac0cfe59OAI: diva2:1031450
Subject / course
Student thesis, at least 30 credits
Educational program
Engineering Physics, master's level
Validerat; 20101217 (root)Available from: 2016-10-04 Created: 2016-10-04Bibliographically approved

Open Access in DiVA

fulltext(440 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 440 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link