Wilsonin algoritmi: Täydellinen opas, erot EOQ:n ja lauseen välillä

Informatec Digital » Tekniikka » Wilsonin algoritmi: Täydellinen opas, erot EOQ:n ja lauseen välillä

Internetissä termiä "Wilson" käytetään monista eri asioista, mikä on melko hämmentävää: on olemassa Wilsonin algoritmi sokkeloiden luomiseen, Wilsonin inventaariomalli (tai EOQ) ja Wilsonin lause lukuteoriassa. Tässä artikkelissa selvennämme kaiken, alkaen sen alkuperäisestä käytöstä sokkeloissa ja erottamalla huolellisesti muut merkitykset, koska ne eivät ole sama asia eivätkä koske samaa alaa.

Jos olet nähnyt demon tai sovelman, jossa sokkelo "kasvaa" itsestään, olet luultavasti jo törmännyt Wilsonin algoritmiin. Olet ehkä myös kuullut Wilsonin mallista taloudellisen järjestysmäärän laskemiseksi tai jopa lauseesta, joka kuvaa alkulukuja kertomien avulla. Täältä löydät täydellisen selityksen esimerkkeineen, jotta voit tunnistaa jokaisen käsitteen ja käyttää sitä oikein.

Mikä on Wilsonin algoritmi sokkeloille?

Wilsonin algoritmi on sokkeloiden generointimenetelmä, joka perustuu silmukoista poistettuihin satunnaisiin kävelyihin. Sen tärkein etu on, että se tuottaa tasaisen satunnaisen virityspuun ruudukon poikki: yksinkertaisesti sanottuna jokainen mahdollinen sokkelo esiintyy samalla todennäköisyydellä ilman vinoumaa tiettyihin suuntiin tai kuvioihin.

Keskeinen ajatus on, että polkuja lisätään olemassa olevaan verkkoon, mutta kun satunnainen polku leikkaa itsensä, silmukka "pyyhitään pois" ja reitti jatkuu pisteestä, jossa se vapautui. Tämä yksityiskohta estää prosessia suosimasta tarpeettomia pitkiä polkuja tai luomasta syklejä, säilyttäen rakenteen puuna, joka yhdistää kaikki solut. Tuloksena on "reilu" sokkelo: millään polulla tai käännöksellä ei ole tilastollista etua toiseen nähden.

Yhteisön luomat projektit ja sovelmat esittelevät algoritmia visuaalisesti ja viihdyttävästi. Näistä Cruz Godarin sovelmat erottuvat edukseen. Niissä voit valita ruudukon koon ja ajaa sitä nähdäksesi, miten sokkelo muodostuu askel askeleelta. Sen seuraaminen auttaa sinua ymmärtämään, miksi silmukan pyyhkiminen tasoittaa todennäköisyyksiä graafin jokaisella jatkeella.

Sokkeloiden rakentaminen ja ratkaiseminen, vaikka ne näyttävätkin peleiltä, ​​liittyvät läheisesti haku- ja optimointiongelmiin. Niiden suunnittelu vaatii tasapainoa selkeyden ja mielenkiintoisuuden välillä, välttäen triviaaleja ratkaisuja tai mahdottomia umpikujia ja tutkien äärellistä avaruutta valtavilla yhdistelmillä. Siksi sekä paperilla että digitaalisissa simulaatioissa ne toimivat erinomaisina logiikan, todennäköisyyden ja kärsivällisyyden harjoituksina.

Miten se toimii (käytännössä)

Alla on algoritmin yleistason kuvaus ilman koodia, mutta sisältäen olennaiset tiedot sen toiminnan ymmärtämiseksi. Muista, että tavoitteena on rakentaa puu (ilman syklejä), joka yhdistää kaikki solut siten, että minkä tahansa kahden pisteen välillä on vain yksi yksinkertainen polku.

• Se alkaa tyhjällä ruudukolla: solu valitaan satunnaisesti ja merkitään osaksi puuta.
• Toinen solu valitaan satunnaisesti, aloitetaan askel askeleelta satunnainen kävely, ja jos polku leikkaa itsensä, silmukat poistetaan välittömästi (silmukan poisto).
• Kun kävely saavuttaa jo luodun puun, koko hienostunut polku (ilman silmukoita) "liimataan" puuhun.
• Se toistuu: valitsemme uuden yhdistämättömän solun, kävelemme silmukan poiston kanssa ja liitymme puuhun.
• Lopulta kaikki solut ovat yhteydessä toisiinsa ja sokkelo on tasainen satunnainen virittävä puu, joten ei ole suunta- tai topologisia vinoumia.

Verrattuna muihin menetelmiin (kuten Aldous-Broder, Prim tai sokkeloihin sovellettu Kruskal), Wilson erottuu edukseen virittävän puun otannan yhdenmukaisuudella. Sen laskentakustannukset ovat kohtuulliset tyypillisillä ruudukoilla ja ennen kaikkea se takaa, että jokainen ratkaisu on yhtä todennäköinen , mikä on erittäin arvostettua akateemisissa ja simulaatioyhteyksissä.

Muita merkityksiä: Wilsonin malli tai EOQ (varastot)

Logistiikassa Wilsonin mallilla (jota kutsutaan myös EOQ:ksi, Economic Order Quantity) ei ole mitään tekemistä sokkeloiden kanssa. Se on klassinen menetelmä optimaalisen tilausmäärän määrittämiseksi kokonaisvarastokustannusten minimoimiseksi. R.H. Wilson teki sen tunnetuksi vuonna 1934, vaikka alkuperäisen konseptin ehdotti Ford Whitman Harris vuonna 1913.

Sen tarkoituksena on löytää eräkoko Q, joka tasapainottaa tilausten tekokustannukset ja varastointikustannukset. Vuosittaisen kysynnän (D), tilauskohtaisen kustannuksen (K) ja yksikkökohtaisten varastointikustannusten (G) perusteella saadaan suure, joka oletusten puitteissa pienentää varaston kokonaiskustannuksia.

Yleisin kaava ilmaistaan ​​muodossa Q = √(2·D·K/G). Tämä luku antaa kunkin erän koon; siitä vuosittaisten tilausten määrä on D/Q, ja tästä voidaan johtaa tilauskierto. On myös tärkeää asettaa uusintatilauspiste (ottaen huomioon läpimenoajan) ja varmuusvarasto varastokatkosten välttämiseksi, vaikka peruskaava ei eksplisiittisesti ota huomioon epävarmuutta.

Tyypillisiä sovelluksia: Sitä käytetään raaka-aineiden tai minkä tahansa tyyppisten tavaroiden kanssa, joiden hankinta- ja varastointikustannukset voidaan luotettavasti määrittää. Käytännössä, tuntemalla D:n, K:n ja G:n riittävän luotettavasti, yritys voi mitoittaa eränsä ja ajoittaa hankintansa paremmin.

Wilsonin mallin oletukset, edut ja rajoitukset

Oletukset ovat kriittisiä tuloksen pätevyyden kannalta. EOQ-malli olettaa, että kysyntä on vakio ja tunnettu, että yksikköhinta pysyy vakaana, että varastointikustannukset tunnetaan ja riippuvat varastotasosta, että läpimenoajat ovat vakioita, eikä se myöskään ota huomioon määräalennuksia.

• Vakaa ja itsenäinen kysyntä ilman kausivaihteluita tai äkillisiä piikkejä.
• Ostohinta on pysynyt kiinteänä tai käytännössä muuttumattomana analysoitavana ajanjaksona.
• Tunnetut varastointikustannukset yksikköä ja ajanjaksoa kohden.
• Ei määräalennuksia ja välitöntä tai jatkuvaa täydennystä.

Keskeiset edut: Se on helppo ottaa käyttöön, laajalti käytetty ja auttaa minimoimaan tilaus- ja varastointikustannuksia ehtojensa mukaisesti. Hyötyihin kuuluvat ylivarastoinnin väheneminen, pienentynyt varaston loppumisen riski (yhdistettynä uusintatilauspisteeseen ja varmuusvarastoon) sekä parempi selkeys ostosuunnittelussa. Monet organisaatiot arvostavat sitä, koska se tarjoaa selkeän numeerisen perustan tilausmäärien määrittämiseen.

Haitat: Se ei toimi hyvin kausiluonteisen tai epäsäännöllisen kysynnän kanssa, jättää huomiotta määräalennukset ja olettaa välittömän (tai kiinteän) täydennyksen, mikä on epärealistista monissa toimitusketjuissa. Siksi Toyota-konsernin kaltaisissa ympäristöissä EOQ-kaava on korvattu vankemmilla järjestelmillä, kuten Kanbanilla tai Just-in-Time-mallilla, jotka käsittelevät paremmin todellista vaihtelua ja jatkuvaa virtausta.

Käytännön esimerkkejä EOQ:sta (Wilson)

Esimerkki 1 (tyypillinen): Yritys, jonka vuosituotanto on 10 000 yksikköä, hankkii 1 000 kg raaka-ainetta. Jos jokainen tilaus maksaa 200 euroa ja vuotuiset kokonaisvarastointikustannukset ovat 2 000 euroa, kaavan Q = √(2·D·K/G) soveltaminen, jossa D = 1 000, K = 200 ja G = 2 000, antaa Q ≈ 14,14. Tämä viittaa 14 kg:n eriin ja noin 71 tilaukseen vuodessa. Se on havainnollistava harjoitus, jossa kohtuullisilla luvuilla voimme nähdä, miten eräkoko tasapainottaa tilauksia ja varastoa.

Esimerkki 2: Sillas Grandes World SL jakelee 6 000 tuolia (D), jokainen tilaus maksaa 300 euroa (K) ja vuotuiset varastointikustannukset yksikköä kohden ovat 5 euroa (G). Yhtälöä soveltamalla Q ≈ 848,52, mikä tarkoittaa, että yritys tekisi vuosittain noin 7,07 tilausta. Tällä eräkoolla yritys pyrkii tehokkaampaan varastointitasoon , mikä vähentää varastointikustannuksia ilman, että tilausten valmistelukustannukset nousevat merkittävästi.

Itse kaavan lisäksi on suositeltavaa laskea uusintatilauspiste ottaen huomioon läpimenoaika ja ylläpitää varmuusvarastoa, koska puhdas malli ei ota huomioon epävarmuutta. Se ei myöskään arvioi määräalennusten vaikutusta, jotka voivat joskus kompensoida varastokustannuksia, jos käytetään suurempia eriä.

Ei pidä sekoittaa Wilsonin lauseeseen (lukuteoria)

Wilsonin lause kuuluu modulaariseen aritmetiikkaan ja toteaa pohjimmiltaan, että kokonaisluku n > 1 on alkuluku, jos ja vain jos (n − 1)! ≡ −1 (mod n). Implikaatiota "jos n on alkuluku, niin (n − 1)! ≡ −1 (mod n)" kutsutaan yleensä tiukasti "Wilsonin lauseeksi", ja käänteinen implikaatio on myös totta. Historiallisesti Edward Waring antoi tuloksen John Wilsonille (1770), vaikka ensimmäisen tunnetun todistuksen antoi Lagrange (1771), ja lauseen muotoilu on itse asiassa peräisin Alhazenilta 1000-luvulta.

Konkreettinen esimerkki: jos p = 11, ryhmittelemällä jokainen alkio sen multiplikatiivisen käänteisjoukon kanssa joukossa {1, 2, …, p − 1}, kokonaistulo on ≡ −1 (mod p). Kaikki tekijät kumoavat toisensa pareittain, kun g·g^{-1} ≡ 1, paitsi 1 ja p − 1, ja siten 10! ≡ −1 (mod 11) . Tämä lähestymistapa hyödyntää sitä tosiasiaa, että jos p = 11, (Z/pZ)^× on multiplikatiivinen ryhmä ja jokaisella alkiolla (paitsi 1 ja p − 1) on erillinen käänteisjoukko.

Todisteita on useita. Yksi polynomimenetelmä tarkastelee g(x) = (x − 1)(x − 2)···(x − (p − 1)) ja f(x) = g(x) − (x^{p−1} − 1). Modulo p, f(x):llä olisi enintään p − 2 juurta, jos se ei olisi nollapolynomi, vaan kaikki 1, 2, …, p − 1 tekevät f(x):stä nollan Fermat'n pienen lauseen nojalla. Siksi f(x) on identtisesti 0 mod p; vakiotermi johtaa (p − 1)! ≡ −1 (mod p).

Sitä ei käytetä käytännön alkulukutestinä, koska (n − 1)! mod n:n laskeminen suurilla n:llä on kallista, ja nopeampia testejä on olemassa (kuten Miller–Rabin- tai deterministiset testit tietyille riveille). Silti sitä voidaan käyttää hyödyllisten ominaisuuksien päättelemiseen: esimerkiksi jos p = 2n + 1 on alkuluku, saadaan ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). Ja osittaisena seurauksena −1 on toisen asteen jäännös modulo p, jos p ≡ 1 (mod 4), koska se voidaan kirjoittaa tulon 1·2···2k neliönä, kun p = 4k + 1, mikä osoittaa, milloin −1 on neliöity Z/pZ:ssä.

On myös käytännöllinen "käänteislasku": mille tahansa yhdistetylle luvulle n > 5, n jakaa (n − 1)!:n. Tapaus n = 4 on klassinen poikkeus (3! ei ole 4:n monikerta). Yksi tapa nähdä tämä on laskea alkuluvun q potenssit, joka jakaa n:n:ssä (n − 1)! on riittävästi q:n monikertoja kattamaan n:ssä esiintyvä poikkeus, lukuun ottamatta mainittua poikkeusta, joka johtaa tulokseen paitsi tapauksessa n = 4.

Gauss yleisti lauseen: kaikkien yksiköiden tulo modulo n, ∏_{1≤a<n, (a,n)=1} a, on ≡ −1 (mod n), jos n ∈ {4, p^k, 2p^k}, jossa p on pariton alkuluku, ja ≡ 1 (mod n) kaikissa muissa tapauksissa. Äärellisten Abelin ryhmien näkökulmasta kaikkien niiden alkioiden tulo on identiteetti, ellei ole olemassa täsmälleen yhtä kertalukua 2 olevaa alkiota, jolloin tulo on kyseinen kertalukua 2 oleva alkio.

Havainnollistava taulukko (n − 1)! mod n:stä, kun n = 2…30

Seuraava taulukko näyttää n:n tarkat arvot välillä 2–30. Alkulukujen tapauksessa jakojäännös (n − 1)! jaettuna n:llä on yhtä suuri kuin n − 1 (joka on ≡ −1 mod n). Yhdistelmälukujen tapauksessa jakojäännös on usein 0. Vertailun vuoksi taulukkoon on myös liitetty −1 mod n. Nämä tiedot havainnollistavat selvästi, miten Wilsonin lause käyttäytyy pienissä tapauksissa, ja auttavat vahvistamaan intuitiota.

n > 1	(n − 1)!	(n − 1)! mod n	−1 mod n
2	1	1	1
3	2	2	2
4	6	2	3
5	24	4	4
6	120	0	5
7	720	6	6
8	5040	0	7
9	40320	0	8
10	362880	0	9
11	3628800	10	10
12	39916800	0	11
13	479001600	12	12
14	6227020800	0	13
15	87178291200	0	14
16	1307674368000	0	15
17	20922789888000	16	16
18	355687428096000	0	17
19	6402373705728000	18	18
20	121645100408832000	0	19
21	2432902008176640000	0	20
22	51090942171709440000	0	21
23	1124000727777607680000	22	22
24	25852016738884976640000	0	23
25	620448401733239439360000	0	24
26	15511210043330985984000000	0	25
27	403291461126605635584000000	0	26
28	10888869450418352160768000000	0	27
29	304888344611713860501504000000	28	28
30	8841761993739701954543616000000	0	29

Sovellukset, rajoitukset ja suositukset

Jos haluat luoda harhattomia sokkeloita, käytä Wilsonin algoritmia: sen satunnaiskävelyihin ja silmukoiden poistoon perustuva malli varmistaa tasaiset puut. Varastonhallinnassa Wilsonin malli on hyödyllinen, kun kysyntä, hinnat ja kustannukset ovat vakaat ja tarkasti tiedossa; epävakaissa ympäristöissä menetelmät, kuten Kanban, Just-in-Time tai edistyneet suunnitteluohjelmistot, voivat olla sopivampia. Matematiikassa Wilsonin lause on teoreettinen helmi mielenkiintoisine johdannaisineen (kuten toisen asteen residuaalit), mutta se ei ole käytännöllinen alkulukutestinä suurille luvuille.

Tilaus- ja varastointikustannusten laskemiseen ei ole olemassa yhtä ainoaa kaavaa: jokaisen yrityksen on eriteltävä tunnit, prosessit, kuljetus, vastaanotto, henkilöstö, vuokra, energia, vakuutukset ja rahoituskustannukset. Monet ammattilaiset arvioivat tunnit toimintoa kohden ja käyttävät tuntihintaa rahaksi muuttamiseen. Tämä mukauttaminen on avainasemassa sen varmistamisessa, että laskettu tilausmäärä (Q) on hyödyllinen ja auttaa yhdessä hyvän uusintatilauspisteen ja varmuusvaraston kanssa välttämään varaston loppumista tai ylivarastoja.

On syytä muistaa, että termi "Wilsonin algoritmi" hauissa viittaa yleensä sokkelogeneraattoriin, kun taas "Wilsonin malli" tai "EOQ" viittaa inventaarioihin ja "Wilsonin lause" lukuteoriaan. Niiden erottaminen alusta alkaen välttää sekaannusta ja antaa mahdollisuuden hyödyntää paremmin kutakin lähestymistapaa: harhattomat sokkelot, optimaaliset erät realististen oletusten vallitessa ja alkulukujen elegantti karakterisointi, joka, vaikka ei olekaan käytännöllinen alkulukutodistus, on silti arvokas pala matemaattista palapeliä.