Change search

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.

2006.
##### Keywords [en]
Technology, linear programming, linear optimization, simplex method, sparse matrices, algorithm, matlab
Teknik
##### Identifiers
ISRN: LTU-EX--06/285--SELocal ID: ea617416-97e1-413d-bfda-c297ac0cfe59OAI: oai:DiVA.org:ltu-58062DiVA, id: diva2:1031450
##### Subject / course
Student thesis, at least 30 credits
##### Educational program
Engineering Physics, master's level
##### Note
Validerat; 20101217 (root)Available from: 2016-10-04 Created: 2016-10-04Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 440 kBChecksum SHA-512
Type fulltextMimetype application/pdf

#### Search outside of DiVA

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: 34 hits

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
v. 2.34.0
|