Wilson's algoritme: complete gids, verschillen met EOQ en de stelling

Informatic Digital » Machinebouw » Wilson's algoritme: complete gids, verschillen met EOQ en de stelling

Op internet gebruiken mensen de term "Wilson" voor heel verschillende doeleinden, en dat is nogal verwarrend: er is het Wilson-algoritme voor het genereren van doolhoven, het Wilson-model (of EOQ) voor inventarissen, en de stelling van Wilson in de getaltheorie. In dit artikel verduidelijken we alles, beginnend met het oorspronkelijke gebruik in doolhoven en zorgvuldig onderscheidend van de andere betekenissen, omdat Ze zijn niet hetzelfde en zijn ook niet van toepassing op hetzelfde gebied.

Als je een demo of applet hebt gezien waarin een doolhof vanzelf "groeit", ben je waarschijnlijk al bekend met Wilsons algoritme. Je hebt ook wel eens gehoord van het Wilson-model voor het berekenen van de economische ordehoeveelheid of zelfs van de stelling die priemgetallen karakteriseert met behulp van faculteiten. Hier vind je een volledige uitleg met voorbeelden, zodat je... je kunt elk concept identificeren en het correct gebruiken.

Wat is Wilsons algoritme voor doolhoven?

Het algoritme van Wilson is een doolhofgeneratiemethode gebaseerd op lus-gewiste willekeurige wandelingen. Het grote voordeel is dat het een uniforme willekeurige spanningsboom over het raster produceert: simpel gezegd, Elk mogelijk doolhof verschijnt met dezelfde waarschijnlijkheid, zonder voorkeur voor specifieke richtingen of patronen.

Het kernidee is dat paden worden toegevoegd aan de reeds opgebouwde set, maar wanneer een willekeurige wandeling zichzelf kruist, wordt de lus "verwijderd" en gaat de route verder waar hij was gebleven. Dit detail voorkomt dat het proces lange, redundante paden of lussen creëert, waardoor de structuur als een boom die alle cellen verbindt, behouden blijft. Het resultaat is een "eerlijk" doolhof: geen enkele corridor of bocht heeft een statistisch voordeel ten opzichte van een andere.

Er zijn door de community gemaakte projecten en applets die het algoritme op een visuele en zeer vermakelijke manier in actie laten zien. Een paar daarvan zijn de applets van Cruz Godar, die eruit springen. Je kunt de rastergrootte kiezen en het doolhof stap voor stap zien ontstaan. Door het te zien, begrijp je waarom. Lus-uitwissen egaliseert de kansen in elke uitbreiding van de grafiek.

Het bouwen en oplossen van doolhoven zijn taken die, hoewel ze misschien op spelletjes lijken, nauw verbonden zijn met zoek- en optimalisatieproblemen. Het ontwerpen ervan vereist een balans tussen helderheid en interesse, waarbij triviale oplossingen of doodlopende wegen worden vermeden; verken een eindige ruimte met enorme combinaties. Daarom werken ze, zowel op papier als in digitale simulaties, als Geweldige oefeningen in logica, waarschijnlijkheid en geduld.

Hoe het werkt (in de praktijk)

Hieronder vindt u een uitgebreide beschrijving van het algoritme, zonder code maar met de essentiële mechanica om het gedrag te begrijpen. Onthoud dat het doel is om een ​​boom (zonder cycli) te bouwen die alle cellen met elkaar verbindt, zodat er is slechts één eenvoudig pad tussen elk paar punten.

• Het begint met een leeg raster: er wordt willekeurig een cel gekozen en gemarkeerd als onderdeel van de boom.
• Er wordt willekeurig een andere cel gekozen, er wordt een stapsgewijze willekeurige wandeling gestart en als het pad zichzelf kruist, worden de lussen onmiddellijk verwijderd (lus-verwijdering).
• Wanneer de wandeling de reeds gegenereerde boom bereikt, wordt het gehele verfijnde pad (zonder lussen) aan de boom “gelijmd”.
• Het herhaalt zich: we kiezen een nieuwe, niet-verbonden cel, lopen door de lus heen met verwijdering en voegen ons bij de boom.
• Uiteindelijk zijn alle cellen met elkaar verbonden en is het doolhof een uniforme, willekeurige overspannende boom, dus er zijn geen richting- of topologische vertekeningen.

Vergeleken met andere methoden (zoals Aldous-Broder, eerste (of Kruskal aangepast aan labyrinten), Wilson valt op door de uniformiteit van de bemonstering van de genererende boom. De rekenkosten zijn redelijk op typische rasters en, bovenal, zorgt ervoor dat elke oplossing even waarschijnlijk is, iets wat in academische en simulatiecontexten zeer gewaardeerd wordt.

Andere betekenissen: Wilson Model of EOQ (inventarissen)

In de logistiek heeft het "Wilson Model" (ook wel EOQ, Economic Order Quantity; of CEP, Economic Order Quantity genoemd) niets te maken met doolhoven. Het is een klassieke methode om de optimale bestelhoeveelheid te bepalen met als doel de totale voorraadkosten te minimaliseren. Het werd in 1934 gepopulariseerd door R.H. Wilson, hoewel Het eerste voorstel werd in 1913 door Ford Whitman Harris gedaan.

Het doel is om de partijgrootte Q te vinden die de kosten van bestellen en de kosten van voorraadbeheer in evenwicht brengt. Uit de jaarlijkse vraag (D), de kosten per bestelling (K) en de opslagkosten per eenheid en periode (G) wordt een hoeveelheid verkregen die, binnen het kader van de aannames, verlaagt de totale voorraadkosten.

De meest gebruikte formule is Q = √(2 D K/G). Dit geeft de batchgrootte; daaruit volgt D/Q voor het aantal jaarlijkse bestellingen, en hieruit kunt u de tijdscadans afleiden. Het is ook belangrijk om het bestelpunt (rekening houdend met de doorlooptijd) en de veiligheidsvoorraad in te stellen om voorraadtekorten te voorkomen, hoewel de basisformule houdt geen rekening met onzekerheid uitdrukkelijk.

Typische toepassingen: gebruikt met grondstoffen of andere goederen waarvan de inkoop- en opslagkosten betrouwbaar kunnen worden bepaald. In de praktijk, als D, K en G voldoende betrouwbaar bekend zijn, Het bedrijf kan de batches op maat maken en de levering plannen met meer controle.

Veronderstellingen, voordelen en beperkingen van het Wilson-model

Veronderstellingen zijn cruciaal voor de validiteit van de resultaten. Het EOQ-model gaat ervan uit dat de vraag constant en bekend is, dat de eenheidsprijs stabiel blijft, dat de opslagkosten bekend zijn en afhankelijk zijn van de voorraad, dat de leveringstijden constant zijn en bovendien houdt geen rekening met volumekortingen.

• Stabiele, onafhankelijke vraag, zonder seizoensgebondenheid of plotselinge pieken.
• Aankoopprijs vast of nagenoeg ongewijzigd gedurende de geanalyseerde periode.
• Bekende opslagkosten per eenheid en periode.
• Geen kwantumkortingen en directe of constante aanvulling.

Belangrijkste voordelen: Het is eenvoudig te implementeren, breed inzetbaar en helpt bestel- en voorraadkosten te minimaliseren onder uw omstandigheden. De voordelen zijn onder andere minder overvoorraad, een lager risico op voorraadtekorten (indien gepaard gaande met een bestelpunt en veiligheidsvoorraad) en duidelijkheid in de inkoopplanning. Veel organisaties waarderen het omdat biedt een eenvoudige numerieke basis voor het bepalen van hoeveel u moet bestellen.

Nadelen: Het werkt niet goed bij seizoensgebonden of onregelmatige vraag, negeert volumekortingen en gaat uit van onmiddellijke (of vaste) aanvulling, wat in veel toeleveringsketens onrealistisch is. Daarom is de EOQ-formule in omgevingen zoals de Toyota Group vervangen door robuustere systemen zoals Kanban of Just-in-Time, die Ze kunnen beter omgaan met echte variabiliteit en de continue stroom.

Praktische voorbeelden van de EOQ (Wilson)

Voorbeeld 1 (typisch): Een bedrijf met een jaarlijkse productie van 10.000 eenheden koopt 1.000 kg grondstof in. Als elke bestelling € 200 kost en de totale jaarlijkse opslagkosten € 2.000 bedragen, geeft de formule Q = √(2 D K/G) met D = 1.000, K = 200, G = 2.000 Q ≈ 14,14. Dit suggereert batches van 14 kg en ongeveer 71 bestellingen per jaar. Dit is een illustratieve oefening waarbij we met bescheiden aantallen kunnen zien Hoe lotgrootte de orders en voorraad in evenwicht brengt.

Voorbeeld 2: Sillas Grandes World SL distribueert 6.000 stoelen (D), elke bestelling kost € 300 (K) en de opslag per eenheid per jaar bedraagt ​​€ 5 (G). Uitgaande van de vergelijking Q ≈ 848,52, zou het bedrijf ongeveer 7,07 bestellingen per jaar plaatsen. Met deze partijgrootte zou het bedrijf neigt naar een efficiënter voorraadniveau, waardoor de opslagkosten worden verlaagd zonder dat de kosten voor ordervoorbereiding toenemen.

Naast de formule is het een goed idee om het bestelpunt te berekenen met inachtneming van de doorlooptijd en het aanhouden van de veiligheidsvoorraad, omdat het pure model geen rekening houdt met onzekerheid. Het schat ook niet de impact van volumekortingen, die soms... zou de voorraadkosten kunnen compenseren indien er grotere kavels worden gebruikt.

Niet te verwarren met de stelling van Wilson (getallentheorie)

De stelling van Wilson behoort tot de modulaire rekenkunde en zegt in wezen dat een geheel getal n > 1 priem is als en alleen als (n − 1)! ≡ −1 (mod n). De implicatie "als n priem is, dan (n − 1)! ≡ −1 (mod n)" wordt vaak strikt "de stelling van Wilson" genoemd, en de omgekeerde implicatie is ook waar. Historisch gezien schreef Edward Waring het resultaat toe aan John Wilson (1770), hoewel het eerste bekende bewijs werd geleverd door Lagrange (1771), en in feite, De formulering dateert uit de 11e eeuw, toen Alhacen leefde.

Concreet voorbeeld: voor p = 11, wanneer elk element wordt gegroepeerd met zijn multiplicatieve inverse in de verzameling {1, 2, …, p − 1}, wordt het totaalproduct ≡ −1 (mod p). Alle factoren heffen elkaar gelijkmatig op, aangezien g g^{-1} ≡ 1, behalve 1 en p − 1, en dus 10! ≡ −1 (mod 11)Deze aanpak gaat ervan uit dat, met p als priemgetal, (Z/pZ)^× een multiplicatieve groep is en dat elk element (behalve 1 en p − 1) een unieke inverse heeft.

Er zijn verschillende bewijzen. Eén polynomiale techniek beschouwt g(x) = (x − 1)(x − 2)···(x − (p − 1)) en f(x) = g(x) − (x^{p−1} − 1). Modulus p, f(x) zou maximaal p − 2 wortels hebben als het niet de nulpolynoom was, maar alle 1, 2, …, p − 1 verdwijnen f(x) volgens de kleine stelling van Fermat. Dus f(x) is identiek 0 mod p en de onafhankelijke term leidt tot (p − 1)! ≡ −1 (mod p).

Het wordt niet gebruikt als een praktische primaliteitstest, omdat het berekenen van (n − 1) mod n voor grote n duur is en er snellere tests bestaan ​​(zoals Miller-Rabin of deterministische tests voor specifieke bereiken). Toch is het nuttig om nuttige eigenschappen af ​​te leiden: bijvoorbeeld, als p = 2n + 1 een priemgetal is, dan geldt ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). En, als gedeeltelijke gevolgtrekking, is −1 een kwadratisch residu modulo p als p ≡ 1 (mod 4), omdat het kan worden geschreven als het kwadraat van het product 1 2 2k wanneer p = 4k + 1, wat geeft aan wanneer −1 kwadratisch is in Z/pZ.

Er is ook een praktische "inverse": voor elke samengestelde n > 5 geldt dat n deelbaar is door (n − 1)!. Het geval n = 4 is de klassieke uitzondering (3! is geen veelvoud van 4). Een manier om dit te zien is door de machten van een priemgetal q te tellen die n delen: in (n − 1)! zijn er genoeg veelvouden van q om de macht die in n voorkomt te dekken, behalve de aangegeven uitzondering, namelijk leidt tot het resultaat behalve voor n = 4.

Gauss generaliseerde de stelling: het product van alle eenheden modulo n, ∏_{1≤a Het is dat element van orde 2.

Illustratieve tabel van (n − 1)! mod n voor n = 2…30

In de volgende tabel ziet u specifieke waarden voor n tussen 2 en 30. Voor n, dat een priemgetal is, is de rest van (n − 1)!, gedeeld door n, gelijk aan n − 1 (wat ≡ −1 mod n is). In samengestelde getallen is de rest vaak 0. −1 mod n is ook opgenomen ter vergelijking. Deze gegevens illustreren zeer goed hoe de stelling van Wilson zich gedraagt ​​in kleine gevallen en helpen bij het intuïtie repareren.

Toepassingen, limieten en aanbevelingen

Als u objectieve doolhoven wilt genereren, gebruik dan Wilsons algoritme: de basis ervan, in willekeurige wandelingen met lusverwijdering, zorgt voor uniforme bomen. Voor inventarissen is het Wilson-model nuttig wanneer vraag, prijzen en kosten stabiel en nauwkeurig bekend zijn; in volatiele omgevingen zijn methodologieën zoals Kanban, JIT of geavanceerde planningssoftware wellicht geschikter. En in de wiskunde is Wilsons stelling een theoretisch pareltje met interessante afleidingen (zoals kwadratische residuen), maar Het is niet praktisch als primaliteitstest voor grote aantallen.

Er is geen universele formule voor het berekenen van bestel- en opslagkosten: elk bedrijf moet uren, processen, transport, ontvangst, personeel, huur, energie, verzekering en financiële kosten uitsplitsen. Veel professionals schatten uren per operatie en hanteren een uurtarief om deze te verzilveren. Deze maatwerkoplossing is essentieel om de berekende Q nuttig te maken en, samen met een goed bestelpunt en een veiligheidsvoorraad, vermijd voorraadtekorten of overtollige voorraad.

Het is belangrijk om te onthouden dat de term "Wilsons algoritme" in zoekopdrachten meestal verwijst naar de doolhofgenerator, terwijl "Wilsons model" of "EOQ" verwijst naar inventarissen, en "Wilsons stelling" verwijst naar de getaltheorie. Door ze vanaf het begin te onderscheiden, voorkomt u verwarring en kunt u beide benaderingen beter benutten: Onpartijdige doolhoven, optimale batches onder realistische aannames en een elegante karakterisering van priemgetallen wat, hoewel het geen praktische primaliteitstest is, toch een waardevol stukje van de wiskundige puzzel is.

Gerelateerd artikel:

Het algoritme van Kruskal en de toepassing ervan in grafieken