Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
2006.
Keyword [en]
Technology, linear programming, linear optimization, simplex method, sparse matrices, algorithm, matlab
Keyword [sv]
Teknik
Identifiers
URN: urn:nbn:se:ltu:diva-58062ISRN: LTU-EX--06/285--SELocal ID: ea617416-97e1-413d-bfda-c297ac0cfe59OAI: oai:DiVA.org:ltu-58062DiVA: diva2:1031450
Subject / course
Student thesis, at least 30 credits
Educational program
Engineering Physics, master's level
Examiners
Note
Validerat; 20101217 (root)Available from: 2016-10-04 Created: 2016-10-04Bibliographically approved

Open Access in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 308 downloads
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

urn-nbn

Altmetric score

urn-nbn
Total: 13 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf