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. / 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.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-157757 |
| Date | January 2019 |
| Creators | Olsson, Sam |
| Publisher | Linköpings universitet, Optimeringslära |
| Source Sets | DiVA Archive at Upsalla University |
| Language | Swedish |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0012 seconds