{"id":101702,"date":"2021-10-26T16:30:34","date_gmt":"2021-10-26T14:30:34","guid":{"rendered":"https:\/\/learnesy.com\/?p=101702"},"modified":"2023-07-25T10:49:08","modified_gmt":"2023-07-25T09:49:08","slug":"hur-du-loser-det-kortaste-sokvagsproblemet-i-excel","status":"publish","type":"post","link":"https:\/\/learnesy.com\/sv\/hur-du-loser-det-kortaste-sokvagsproblemet-i-excel\/","title":{"rendered":"Hur du l\u00f6ser kortaste v\u00e4gen – problemet i Excel"},"content":{"rendered":"

I dagens inl\u00e4gg l\u00e4r du dig hur du kan anv\u00e4nda Excel f\u00f6r att l\u00f6sa det kortaste s\u00f6kv\u00e4gsproblemet. Problemet med den kortaste v\u00e4gen \u00e4r ett grundl\u00e4ggande optimeringsproblem med ett stort antal applikationer. Det anv\u00e4nds till exempel i logistisk probleml\u00f6sning, budgetplanering och n\u00e4tverksoptimering – f\u00f6r att bara n\u00e4mna n\u00e5gra.<\/span><\/p>\n

H\u00e4r \u00e4r ett enkelt n\u00e4tverk d\u00e4r vi snabbt kan r\u00e4kna ut f\u00f6r hand att det minimala avst\u00e5ndet fr\u00e5n A<\/strong> till F<\/strong> uppn\u00e5s via rutten C -> E -> D<\/strong>, med ett avst\u00e5nd p\u00e5 20.<\/span><\/p>\n

\"\"<\/p>\n

I verkligheten \u00e4r avst\u00e5ndet mellan noder s\u00e4llan rent fysiskt avst\u00e5nd eller ett enda tal, utan en kombination av olika variabler som bidrar till ett tal som representerar de resurser som anv\u00e4nds f\u00f6r att ta sig fr\u00e5n en nod till en annan.<\/span><\/p>\n

Till exempel n\u00e4r en navigator planerar din rutt, ber\u00e4knas rutten med en mycket liknande princip. Det tar h\u00e4nsyn till saker som fysiskt avst\u00e5nd, trafik, v\u00e4garnas skick och hastighetsbegr\u00e4nsningar. Dessa kombineras sedan f\u00f6r att representera en ungef\u00e4rlig tid f\u00f6r f\u00f6rflyttning mellan platser (noder)<\/span>.<\/span><\/p>\n

I en liten datam\u00e4ngd \u00e4r det relativt enkelt att r\u00e4kna ut den kortaste v\u00e4gen utan en algoritm helt enkelt genom att ber\u00e4kna alla m\u00f6jliga kombinationer f\u00f6r hand, men n\u00e4r n\u00e4tverket v\u00e4xer kommer detta att bli n\u00e4stan om\u00f6jligt att g\u00f6ra manuellt. D\u00e4rf\u00f6r beh\u00f6ver vi en generisk l\u00f6sning som vi kan anv\u00e4nda f\u00f6r ett n\u00e4tverk i alla storlekar.<\/span><\/p>\n

Ladda ner \u00f6vningsfilen som inneh\u00e5ller f\u00f6ljande n\u00e4tverk, som vi kommer att l\u00f6sa.<\/p>\n

kortaste_v\u00e4gen.xlsx<\/a><\/p>\n

\"\"
\nVi skapar ett nytt blad d\u00e4r vi kommer att r\u00e4kna ut den kortaste v\u00e4gen fr\u00e5n A<\/strong> till Destination<\/strong>. Vi b\u00f6rjar med att kartl\u00e4gga alla olika rutter i n\u00e4tverket med sina respektive avst\u00e5nd.<\/span><\/p>\n

Fr\u00e5n nod A<\/strong> kan vi flytta oss till B<\/strong> som kostar oss 12, och till C<\/strong> vilket kostar oss 10.\u00a0<\/span><\/p>\n

\"\"
\nF\u00f6ljer vi samma princip, kan vi kartl\u00e4gga hela n\u00e4tverket som f\u00f6ljande.\"\"
\nObservera att vi kan r\u00f6ra oss i n\u00e4tverket i vilken riktning som helst, s\u00e5 vi m\u00e5ste \u00e4ven kartl\u00e4gga vissa rutter i omv\u00e4nd ordning. Till exempel kan ruttens start vara A -> B -> D<\/strong> eller A -> C -> D -> B<\/strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0<\/span><\/p>\n

H\u00e4r har vi ignorerat n\u00e5gra uppenbara omv\u00e4nda v\u00e4gar f\u00f6r att h\u00e5lla kartan mer l\u00e4ttl\u00e4st, men i allm\u00e4nhet \u00e4r det inte en bra metod ifall rutten inte uttryckligen \u00e4r en enkelriktad v\u00e4g.<\/span><\/p>\n

Skapa sedan en tom kolumn bredvid ”Distans”. Dessa celler kommer att fungera som bin\u00e4ra variabler n\u00e4r vi l\u00f6ser den kortaste v\u00e4gen och markerar den korrekta v\u00e4gen. Det vill s\u00e4ga: om kortaste v\u00e4gen b\u00f6rjar fr\u00e5n A<\/strong> och g\u00e5r sedan till C<\/strong>, kommer v\u00e4rdet vara 1 i cell D3<\/strong>, annars 0. Det samma g\u00e4ller alla celler i kolumn D.<\/p>\n

\"\"
\nEftersom vi vet att kolumnen ”Rutt” kommer att markera de korrekta rutterna med 1, skapar vi en ny kolumn som kommer att mata ut rutten i ett mer l\u00e4sbart format.
\n\"\"<\/p>\n

Om den korrekta rutten b\u00f6rjar fr\u00e5n A -> B<\/strong> kommer formeln helt enkelt att mata ut ”A till B”, annars f\u00f6rblir den tom. Kopiera formeln till alla celler nedan.<\/p>\n

Nu m\u00e5ste vi skapa en ny tabell f\u00f6r de begr\u00e4nsningar som vi kommer att skicka in i l\u00f6saren. I den f\u00f6rsta kolumnen skriver vi ner alla noder i n\u00e4tverket. I kolumnen ”Begr\u00e4nsningar” kommer vi att st\u00e4lla in en funktion som f\u00f6rser l\u00f6saren med v\u00e5ra begr\u00e4nsningar – eftersom vi letar efter endast en korrekt rutt.<\/p>\n

Skriv:
\n=SUMMA.OM($A$2:$A$26;H2;$D$2:$D$26)-SUMMA.OM($B$2:$B$26;H2;$D$2:$D$26)<\/strong><\/p>\n

\"\"<\/p>\n

Det kan se komplicerat ut, men allt funktionen g\u00f6r \u00e4r att den returnerar 1<\/strong> om det finns en anv\u00e4nd rutt som g\u00e5r ut ur noden, 0<\/strong> om det finns en anv\u00e4nd rutt som kommer in och ut ur noden, och -1<\/strong> om det finns en rutten kommer in men inte ut. Den kommer ocks\u00e5 att returnera 0 om det inte finns n\u00e5gon rutt som kommer in eller ut \u00f6ver huvudtaget. Kopiera formeln till alla celler nedan.<\/p>\n

Eftersom vi m\u00e5ste ber\u00e4tta f\u00f6r l\u00f6saren vad v\u00e5ra begr\u00e4nsningar b\u00f6r vara lika med, l\u00e4gger vi till ytterligare en kolumn d\u00e4r vi skriver dessa v\u00e4rden manuellt.<\/p>\n

\"\"
\nSammanfattat: vi l\u00f6ser den kortaste v\u00e4gen genom att \u00e4ndra de variabla cellerna i kolumn D<\/strong>, d\u00e5 nod A<\/strong> har v\u00e4rdet 1, och Destination<\/strong> v\u00e4rdet -1<\/strong> i kolumn I<\/strong>. Detta \u00e4r allts\u00e5 ett s\u00e4tt att ange start- och slutnod till probleml\u00f6saren.<\/p>\n

Innan vi l\u00f6ser kortaste v\u00e4gen, vill vi \u00e4ven f\u00e5 reda p\u00e5 det totala avst\u00e5ndet – inte bara den korrekta rutten, s\u00e5 vi skriver in en objektiv funktion som vi vill minimera med PRODUKTSUMMA. Funktionen summerar helt enkelt avst\u00e5nden f\u00f6r de anv\u00e4nda str\u00e4ckorna (SUMMA.OM fungerar ocks\u00e5).<\/p>\n

Skriv:
\n=PRODUKTSUMMA(D2:D26;C2:C26)<\/strong><\/p>\n

\"\"<\/p>\n

Nu \u00e4r vi redo f\u00f6r att l\u00f6sa den kortaste v\u00e4gen! B\u00f6rja med att \u00f6ppna probleml\u00f6saren \u2013 till\u00e4gget. Om du inte har det installerat, g\u00e5 till Arkiv<\/strong> -> <\/span>Fler<\/b>-> Alternativ<\/strong> och v\u00e4lj Till\u00e4gg<\/strong>. Klicka p\u00e5 G\u00e5<\/strong> och v\u00e4lj Probleml\u00f6saren<\/strong> fr\u00e5n menyn. Probleml\u00f6saren hittar du sedan i verktygsf\u00e4ltet l\u00e4ngst till h\u00f6ger under Data-fliken.<\/strong><\/span><\/p>\n

\"\"<\/p>\n

I probleml\u00f6saren beh\u00f6ver vi nu markera objektivfunktionen (E27<\/strong>) som vi l\u00f6ser med att \u00e4ndra variabla cellerna i kolumn<\/strong> D<\/strong>. Vi v\u00e4ljer MIN<\/strong>\u00a0f\u00f6r att minimera, och Simplex LP-metoden<\/strong> f\u00f6r att l\u00f6sa den kortaste v\u00e4gen.\u00a0<\/span><\/p>\n

\"\"<\/p>\n

F\u00f6re vi l\u00f6ser b\u00f6r vi \u00e4ven mata in v\u00e5ra begr\u00e4nsingar. Klicka p\u00e5 L\u00e4gg till<\/strong>, v\u00e4lj lika med\u00a0<\/strong>och mata in kolumnerna f\u00f6r begr\u00e4nsningar. Med andra ord: vi l\u00f6ser vilken kombination av siffror i kolumn D ger det minsta m\u00f6jliga resultatet i objektivfunktionen (E27) <\/strong>inom begr\u00e4nsingens ramar.<\/span><\/p>\n

\"\"<\/p>\n

Klicka sedan p\u00e5 OK\u00a0<\/strong>och p\u00e5 L\u00f6s<\/strong>, f\u00f6r att f\u00e5 fram den kortaste v\u00e4gen fr\u00e5n A\u00a0<\/strong>till Destination – <\/strong>vilket blir rutten A -> B -> E -> G -> J -> Destination<\/strong>. Totala distansen f\u00f6r rutten \u00e4r 27, vilket returneras av den objektiva funktionen.<\/p>\n

\"\"<\/p>\n

\"\"<\/p>\n

Det \u00e4r viktigt att kunna identifiera vilka problem som g\u00e5r att l\u00f6sa med en liknande princip. En bra tumregel \u00e4r att problemet b\u00f6r ha en livscykel, eller f\u00f6ruts\u00e4gbar utveckling d\u00e4r vi vet eller kan uppskatta hur mycket resurser vi f\u00f6rbrukar med att r\u00f6ra oss mellan punkter. En resurs blir ofta en enhet, vilket kan vara allt fr\u00e5n tid till pengar eller koldioxidutsl\u00e4pp.<\/p>\n","protected":false},"excerpt":{"rendered":"

I dagens inl\u00e4gg l\u00e4r du dig hur du kan anv\u00e4nda Excel f\u00f6r att l\u00f6sa det kortaste s\u00f6kv\u00e4gsproblemet. Problemet med den kortaste v\u00e4gen \u00e4r ett grundl\u00e4ggande optimeringsproblem med ett stort antal applikationer. Det anv\u00e4nds till exempel […]<\/p>\n","protected":false},"author":2,"featured_media":101988,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"_eb_attr":"","footnotes":""},"categories":[30],"tags":[287,218,208],"class_list":["post-101702","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-ovrigt","tag-avancerad-excel","tag-excel-online","tag-onlinekurs"],"acf":[],"_links":{"self":[{"href":"https:\/\/learnesy.com\/sv\/wp-json\/wp\/v2\/posts\/101702","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/learnesy.com\/sv\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/learnesy.com\/sv\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/learnesy.com\/sv\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/learnesy.com\/sv\/wp-json\/wp\/v2\/comments?post=101702"}],"version-history":[{"count":104,"href":"https:\/\/learnesy.com\/sv\/wp-json\/wp\/v2\/posts\/101702\/revisions"}],"predecessor-version":[{"id":245769,"href":"https:\/\/learnesy.com\/sv\/wp-json\/wp\/v2\/posts\/101702\/revisions\/245769"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/learnesy.com\/sv\/wp-json\/wp\/v2\/media\/101988"}],"wp:attachment":[{"href":"https:\/\/learnesy.com\/sv\/wp-json\/wp\/v2\/media?parent=101702"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/learnesy.com\/sv\/wp-json\/wp\/v2\/categories?post=101702"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/learnesy.com\/sv\/wp-json\/wp\/v2\/tags?post=101702"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}