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
Klassificeringsmodeller för transportproblemet
Linköping University, Department of Mathematics, Optimization .
2019 (Swedish)Independent thesis Basic level (degree of Bachelor), 10,5 credits / 16 HE creditsStudent thesis
Abstract [sv]

Det klassiska transportproblemet är ett linjärt och kontinuerligt optimeringsproblem vilket vanligtvis kan lösas till optimalitet snabbt och effektivt med t.ex. simplex-metoden. Men väldigt stora instanser (> 10 000 000 variabler) är minneskrävande och tar lång tid att lösa även för state-of-the-art lösare.Syftet med undersökningen är att hitta ett eller flera sätt att skatta det optimala målfunktionsvärdet för transportproblemet utan att lösa problemet. Olika nyckeltal och karakteristika för probleminstanser till transportproblemet har tagits fram, och dessa har sedan använts för att ta fram linjära regressionsmodeller. För att få en helhetsbild av hur funktionerna och nyckeltalen fungerar på transportproblemet skapas ett antal extremfall. Dessa extremfall är olika sätt att placera ut noder. Resultatet visar att linjär regression inte är tillräckligt för att lösa problemet i samtliga fall. Vi ser dock att det är möjligt att hitta bra skattningar till det optimala målfuntionsvärdet i vissa specialfall.

Abstract [en]

The classical transportation problem is a linear and continous optimization problem which can usually be solved quickly and easily with for example the simplex method. However, larger instances of the problem (> 10 000 000 variables) requires a lot of memory and takes a long time to solve, even for state-of-the-art solvers. The purpose of this investigation is to find one or more ways to estimate the optimal objective value for the transportation problem without solving it. Different key values and characteristics for the transportation problem have been investigated and these values have then been used to derive linear regression models. In order to get the big picture of how the functions and key values work on the transportation problem, a set of extreme cases is created. These extreme cases are different ways to place nodes. The results show that linear regression is not enough to solve the problem in all cases. However, under certain circumstances we see that it is possible to find good estimates to optimal objective value.

Place, publisher, year, edition, pages
2019. , p. 73
Keywords [sv]
Transportproblemet, stegvis regression
National Category
Natural Sciences
Identifiers
URN: urn:nbn:se:liu:diva-157757ISRN: LiTH-MAT-EX--2019/06--SEOAI: oai:DiVA.org:liu-157757DiVA, id: diva2:1328005
Subject / course
Mathematics
Presentation
2019-06-11, 11:35 (Swedish)
Supervisors
Examiners
Available from: 2019-06-27 Created: 2019-06-20 Last updated: 2019-06-27Bibliographically approved

Open Access in DiVA

fulltext(1282 kB)15 downloads
File information
File name FULLTEXT01.pdfFile size 1282 kBChecksum SHA-512
927fbc006a15bb5b9587ef633f94984150642a033773c8ba59ccc89cb95408c2a0cba7529c4788b93ffd68b19f122e0e9b7ab0ab2e29bea573722a678c721029
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Olsson, Sam
By organisation
Optimization
Natural Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 15 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: 112 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