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 hyvin eri tarkoituksiin, ja tämä on melko hämmentävää: on olemassa Wilsonin algoritmi sokkeloiden luomiseen, Wilsonin malli (tai EOQ) inventaarioille ja Wilsonin lause lukuteoriassa. Tässä artikkelissa selvennämme kaiken, alkaen alkuperäisestä käytöstä sokkeloissa ja erottamalla huolellisesti muut merkitykset, koska Ne eivät ole samoja eivätkä koske samaa aluetta.

Jos olet nähnyt demon tai sovelman, jossa sokkelo "kasvaa" itsestään, olet luultavasti jo törmännyt Wilsonin algoritmiin. Olet 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 osaat tunnistaa jokaisen käsitteen ja käyttää sitä oikein.

Mikä on Wilsonin algoritmi sokkeloille?

Wilsonin algoritmi on silmukoista poistettuihin satunnaisiin kävelyihin perustuva sokkeloiden generointimenetelmä. Sen suuri etu on, että se tuottaa tasaisen satunnaisen virittäväpuun ruudukon yli: yksinkertaisesti sanottuna, Jokainen mahdollinen sokkelo ilmestyy samalla todennäköisyydellä, ilman ennakkoasenteita tiettyjä suuntia tai kaavoja kohtaan.

Keskeinen ajatus on, että polut lisätään jo rakennettuun joukkoon, mutta kun satunnainen kävely leikkaa itsensä, silmukka "poistetaan" ja reitti jatkuu siitä, mihin se jäi. Tämä yksityiskohta estää prosessia luomasta pitkiä, tarpeettomia polkuja tai silmukoita, säilyttäen rakenteen puuna, joka yhdistää kaikki solut. Tuloksena on "reilu" sokkelo: millään käytävällä tai käännöksellä ei ole tilastollista etua toiseen nähden.

Yhteisön luomat projektit ja sovelmat esittelevät algoritmin toiminnassa visuaalisesti ja erittäin viihdyttävällä tavalla. Näistä erottuvat Cruz Godarin sovelmat, joissa voit valita ruudukon koon ja asettaa sen toimimaan nähdäksesi, miten sokkelo syntyy askel askeleelta. Sen toiminnan seuraaminen auttaa sinua ymmärtämään miksi. Silmukan poisto tasoittaa kertoimet graafin jokaisessa jatkeessa.

Sokkeloiden rakentaminen ja ratkaiseminen ovat tehtäviä, jotka, vaikka ne saattavatkin vaikuttaa peleiltä, ​​liittyvät läheisesti haku- ja optimointiongelmiin. Niiden suunnittelu vaatii tasapainoa selkeyden ja kiinnostavuuden välillä, välttäen triviaaleja ratkaisuja tai umpikujia; tutkia äärellistä tilaa valtavilla yhdistelmillä. Siksi sekä paperilla että digitaalisissa simulaatioissa ne toimivat Hyviä harjoituksia logiikasta, todennäköisyydestä ja kärsivällisyydestä.

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

Alla on algoritmin yleiskuvaus ilman koodia, mutta sen toiminnan ymmärtämiseksi tarvittavat olennaiset tiedot sisältävä. Muista, että tavoitteena on rakentaa puu (ilman syklejä), joka yhdistää kaikki solut siten, että minkä tahansa pisteparin 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-Broderin menetelmiin, ensimmäinen tai Kruskalin labyrintteihin soveltama menetelmä), Wilson erottuu generoivan puun näytteenoton tasaisuudella. Sen laskentakustannukset ovat kohtuulliset tyypillisillä ruudukoilla ja ennen kaikkea varmistaa, että jokainen ratkaisu on yhtä todennäköinen, jota arvostetaan suuresti akateemisissa ja simulaatioyhteyksissä.

Muita merkityksiä: Wilsonin malli tai EOQ (varastot)

Logistiikassa ”Wilsonin mallilla” (tunnetaan myös nimellä EOQ, Economic Order Quantity; tai CEP, Economic Order Quantity) ei ole mitään tekemistä sokkeloiden kanssa. Se on klassinen menetelmä optimaalisen tilausmäärän määrittämiseksi tavoitteena minimoida kokonaisvarastokustannukset. R.H. Wilson teki sen tunnetuksi vuonna 1934, vaikka Ensimmäisen ehdotuksen teki Ford Whitman Harris vuonna 1913..

Sen tarkoituksena on löytää eräkoko Q, joka tasapainottaa tilauskustannukset ja varastointikustannukset. Vuosittaisesta kysynnästä (D), tilauskustannuksista (K) ja yksikkö- ja jaksokohtaisista varastointikustannuksista (G) saadaan suure, joka oletusten puitteissa alentaa varaston kokonaiskustannuksia.

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

Tyypillisiä sovelluksia: käytetään raaka-aineiden tai minkä tahansa tyyppisten tavaroiden kanssa, joiden osto- ja varastointikustannukset voidaan määrittää luotettavasti. Käytännössä, jos D, K ja G tunnetaan riittävän luotettavasti, Yritys voi mitoittaa eränsä ja aikatauluttaa toimituksensa suuremmalla hallinnalla.

Wilsonin mallin oletukset, edut ja rajoitukset

Oletukset ovat kriittisiä tulosten pätevyyden kannalta. EOQ-malli olettaa, että kysyntä on vakio ja tunnettu, että yksikköhinta pysyy vakaana, että varastointikustannukset tunnetaan ja riippuvat varastotasosta, että toimitusajat ovat vakioita ja lisäksi, ei harkitse 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ä.

Tärkeimmät edut: Se on helppo ottaa käyttöön, sitä käytetään laajalti ja se auttaa minimoimaan tilaus- ja varastointikustannuksia omissa olosuhteissasi. Sen etuihin kuuluvat ylivarastoinnin väheneminen, varaston loppumisen riskin pieneneminen (jos siihen liittyy uusintatilauspiste ja varmuusvarasto) sekä selkeys ostosuunnittelussa. Monet organisaatiot arvostavat sitä, koska tarjoaa yksinkertaisen numeerisen perustan tilausmäärän päättä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 -periaatteella, jotka Ne käsittelevät todellista vaihtelua paremmin ja jatkuva virtaus.

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

Esimerkki 1 (tyypillinen): Yritys, jonka vuosituotanto on 10 000 yksikköä, ostaa 1 000 kg raaka-ainetta. Jos jokainen tilaus maksaa 200 euroa ja kokonaisvuosittaiset varastointikustannukset ovat 2 000 euroa, kaavan Q = √(2 D K/G) soveltaminen, jossa D = 1 000, K = 200, G = 2 000, antaa Q:ksi ≈ 14,14. Tämä viittaa 14 kg:n eriin ja noin 71 tilaukseen vuodessa. Tämä on havainnollistava harjoitus, jossa vaatimattomilla luvuilla voimme nähdä, että 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 varastointikulut yksikköä kohden vuodessa ovat 5 euroa (G). Yhtälöä soveltamalla Q ≈ 848,52 tilauksia olisi noin 7,07 vuodessa. Tällä eräkoolla yritys pyrkii kohti tehokkaampaa varastotasoa, mikä vähentää varastointikustannuksia lisäämättä tilauksen valmistelukustannuksia.

Kaavan lisäksi on hyvä laskea uudelleentilauspiste ottaen huomioon läpimenoaika ja varmuusvaraston ylläpito, koska puhdas malli ei ota huomioon epävarmuutta. Se ei myöskään arvioi määräalennusten vaikutusta, jotka joskus voisi korvata varastokustannuksia jos käytetään suurempia eriä.

Ei pidä sekoittaa Wilsonin lauseeseen (lukuteoria)

Wilsonin lause kuuluu modulaarinen aritmetiikka ja pohjimmiltaan sanoo, 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 usein tiukasti ottaen ”Wilsonin lauseeksi”, ja käänteinen implikaatio pätee myös. Historiallisesti Edward Waring antoi tuloksen John Wilsonille (1770), vaikka ensimmäisen tunnetun todistuksen antoi Lagrange (1771), ja itse asiassa, Muotoilu on peräisin Alhacenilta 1100-luvulta.

Konkreettinen esimerkki: jos p = 11, ryhmitellään jokainen alkio sen kertolaskullisen käänteisfunktion kanssa joukossa {1, 2, …, p − 1}, kokonaistuloksi tulee ≡ −1 (mod p). Kaikki tekijät kumoavat toisensa tasan, kun g g^{-1} ≡ 1, paitsi 1 ja p − 1, joten 10! ≡ −1 (mod 11)Tässä lähestymistavassa käytetään sitä, että p-alkulukulla (Z/pZ)^× on multiplikatiivinen ryhmä ja jokaisella alkiolla (paitsi 1 ja p − 1) on selvä käänteisluku.

Todisteita on useita. Yksi polynomimenetelmä tarkastelee yhtälöitä g(x) = (x − 1)(x − 2)···(x − (p − 1)) ja f(x) = g(x) − (x^{p−1} − 1). Modulilla p, f(x):llä olisi enintään p − 2 juurta, jos se ei olisi nollapolynomi, vaan kaikki 1, 2, …, p − 1 häviävät f(x):n perusteella Fermat'n pienen lauseen nojalla. Näin ollen f(x) on identtisesti 0 mod p ja riippumaton termi 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 alkuluvuille). Silti on hyödyllistä päätellä hyödyllisiä ominaisuuksia: esimerkiksi jos p = 2n + 1 on alkuluku, niin pätee ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). Ja osittaiskorollaarina −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ä näyttää, milloin −1 on neliö Z/pZ-muodossa.

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

Gauss yleisti lauseen: kaikkien yksiköiden tulo modulo n, ∏_{1≤a Se on kertaluvun 2 elementti.

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

Seuraavassa taulukossa näet n:n tarkat arvot väliltä 2–30. Jos n on alkuluku, luvun (n − 1)! jakojäännös jaettuna n:llä on yhtä suuri kuin n − 1 (joka on ≡ −1 mod n). Yhdistelmälaskennoissa jakojäännös on usein 0. Vertailun vuoksi mukaan on myös −1 mod n. Nämä tiedot havainnollistavat erittäin hyvin, miten Wilsonin lause käyttäytyy pienissä tapauksissa, ja auttavat korjaa intuitio.

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 perusta varmistaa yhtenäiset puut. Varastojen osalta Wilsonin malli on hyödyllinen, kun kysyntä, hinnat ja kustannukset ovat vakaat ja tarkasti tiedossa; epävakaissa ympäristöissä menetelmät, kuten Kanban, JIT tai edistyneet suunnitteluohjelmistot, voivat olla sopivampia. Ja matematiikassa Wilsonin lause on teoreettinen helmi mielenkiintoisine johdannaisineen (kuten neliölliset jäännökset), mutta Se ei ole käytännöllinen alkulukutestinä suurille lukumäärille.

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 tekemiseen. Tämä mukauttaminen on avainasemassa, jotta lasketusta määrästä tulee hyödyllinen ja hyvän uudelleentilauspisteen ja varmuusvaraston ohella... välttää varastokatkoksia tai ylitarjontaa.

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 toisistaan ​​alusta alkaen välttää sekaannuksia ja antaa sinulle mahdollisuuden hyödyntää paremmin kutakin lähestymistapaa: Puolueettomia sokkeloita, optimaalisia eriä realististen oletusten vallitessa ja elegantti alkulukujen karakterisointi joka, vaikkakaan ei käytännöllinen alkulukutesti, on silti arvokas pala matemaattisessa palapelissä.