Je weet wat het betekent om een systeem te optimaliseren om het best mogelijke resultaat te krijgen als je een ingenieursstudent of een ingenieur bent.
Het optimaliseren van een oplossing is de sleutel tot succes in alles, van het bouwen van bruggen tot het maken van software.
Het idee van een haalbare basisoplossing komt op dit punt binnen.
Het is een basisidee in lineaire programmering waarmee u kunt uitzoeken welke van een reeks mogelijke oplossingen de beste is.
Maar waarom maakt het zoveel uit? In dit artikel zal ik het hebben over haalbare basisoplossingen en hoe deze kunnen worden gebruikt om technische problemen in de echte wereld op te lossen.
Ik zal het hebben over hoe je ze kunt vinden, waar ze van gemaakt zijn en waarom ze belangrijk zijn.
Dus, of je nu een ervaren ingenieur bent of een student die net begint, ga met ons mee terwijl ik in de wereld van haalbare basisoplossingen duik en je laat zien hoe je de kracht van lineair programmeren kunt gebruiken.
Een haalbare basisoplossing begrijpen
Formele definitie:
Een basisoplossing voor een lineair programmamodel waarin alle variabelen niet-negatief zijn.
Een basis haalbare oplossing (BFS) is een sleutelidee in lineair programmeren dat helpt bij het vinden van de beste oplossingen.
Een BFS is een oplossing met het kleinst mogelijke aantal niet-nul variabelen.
Het is een hoek van het veelvlak van haalbare oplossingen.
Met andere woorden, een BFS is een basisoplossing die voldoet aan de niet-negatieve beperkingen en zich in de haalbare regio of het probleemgebied bevindt.
Het vinden van een optimale basis haalbare oplossing
Om de beste BFS te vinden, moeten we het volgende doen:
- Schrijf het programma in standaardvorm voor een lineaire reeks.
- Verander het systeem van ongelijkheden in een augmented matrix.
- Zoek uit welke variabelen standaard zijn en welke niet.
- Zoek uit wat de basisvariabelen zijn in termen van de andere variabelen.
- Plaats deze uitdrukkingen in de doelfunctie om een functie te krijgen van alleen de variabelen die niet standaard zijn.
- Zoek een niet-basisvariabele die kan worden verhoogd zonder beperkingen te verbreken en die de doelfunctie beter zal maken.
Deze variabele is nu een basisvariabele en een van de andere basisvariabelen is geen basisvariabele meer.
Als er een optimale oplossing is, moet deze zich aan een van de uiteinden of hoekpunten bevinden van het gebied waar oplossingen mogelijk zijn.
Dus als een LP een optimale oplossing heeft, heeft het een optimale oplossing op een extreem punt van de haalbare set.
Er is ook altijd een optimale BFS als er een optimale oplossing is.
De Simplex-methode gebruiken om een optimale BFS te vinden
De Simplex-methode is een algoritme voor het oplossen van problemen bij lineair programmeren.
Het gaat van de ene BFS naar een "aangrenzende" BFS met behulp van de spilprocedure.
In de spilprocedure wordt een niet-basisvariabele gekozen om een basisvariabele te worden, en vervolgens wordt de huidige BFS gebruikt om de nieuwe basisvariabelen op te lossen.
Als er geen niet-basisvariabele kan worden gewijzigd om de doelfunctie beter te maken, is het algoritme klaar.
Waarom fundamentele haalbare oplossingen cruciaal zijn voor het oplossen van complexe technische problemen
Nog steeds moeilijk te begrijpen? Laat me het standpunt een beetje veranderen:
Wie heeft er eigenlijk behoefte aan eenvoudige, werkbare antwoorden? Gewoon alles bij elkaar gooien en er het beste van hopen.
Want wie heeft optimalisatie nodig als chaos zoveel leuker is? Welkom in de wereld van niet-negatieve variabelen, waar alles slechts een suggestie is en mislukking bijna zeker is.
Of is het?
Laten we onderzoeken waarom het ogenschijnlijk basale concept van haalbare basisoplossingen allesbehalve eenvoudig is en waarom ze misschien wel de sleutel zijn tot het oplossen van zelfs de meest complexe technische problemen.
Oké, dat was maar een grap gemaakt om eruit te zien als een tv-reclame.
Laten we nu teruggaan naar de uitleg.
Het vinden van een haalbare basisoplossing
Een basis haalbare oplossing (BFS) is een oplossing voor een lineair optimalisatieprobleem die aan alle beperkingen voldoet en het minste aantal niet-nulvariabelen heeft.
Elke BFS is een hoek van het veelvlak van haalbare oplossingen vanuit geometrisch oogpunt.
Als er een beste oplossing is, moet er ook een beste eerste stap zijn.
In dit artikel bespreken we hoe je een eerste haalbare basisoplossing kunt vinden, hoe je alle haalbare basisoplossingen kunt vinden en hoe je een haalbare basisoplossing kunt vinden zonder losse variabelen.
Een eerste haalbare basisoplossing vinden
We kunnen verschillende methoden gebruiken, afhankelijk van hoe het probleem is opgezet, om een initiële basisoplossing te vinden die werkt voor een lineair optimalisatieprobleem.
Eén manier is om losse variabelen toe te voegen aan de beperkingen op ongelijkheden en alle andere variabelen op nul te zetten.
De slappe variabelen worden de basisvariabelen en de rest zijn niet-basisvariabelen.
De tweefasige Simplex-methode is een andere manier om het probleem op te lossen.
Deze methode omvat het oplossen van een extra lineair programmeerprobleem om een initiële basisoplossing te vinden die haalbaar is.
Als eenmaal een eerste haalbare basisoplossing is gevonden, kan de Simplex-methode worden gebruikt om van de ene haalbare basisoplossing naar de volgende en vervolgens naar de beste oplossing te gaan.
Alle haalbare basisoplossingen vinden
Er kan meer dan één basisoplossing zijn die werkt voor een lineair programma.
We kunnen het systeem veranderen door slappe variabelen toe te voegen en vervolgens het nieuwe systeem gebruiken om alle haalbare basisoplossingen voor een lineair programma te vinden.
Vervolgens worden deze haalbare basisoplossingen gebruikt om de haalbare basisoplossingen voor het oorspronkelijke probleem te vinden.
Een haalbare basisoplossing vinden zonder slappe variabelen
We moeten slappe variabelen gebruiken om van de minder-dan-beperkingen af te komen, zodat we een basisoplossing kunnen vinden die werkt zonder slappe variabelen.
Een slappe variabele is slechts het verschil tussen de rechterkant van een beperking en de linkerkant.
Voor de eerste beperking definiëren we bijvoorbeeld een slappe variabele x4 = 14 - 2x1 - x2 - x3. In termen van deze nieuwe variabele is de eerste beperking simpelweg gelijk aan x4 ≥ 0, wat een positiviteitsbeperking is voor x4.
Wanneer we deze slappe variabelen toevoegen, krijgen we een lineair programma dat hetzelfde is als het oorspronkelijke, behalve dat alle beperkingen vergelijkingen zijn of beperkingen die zeggen dat iets positief is.
De verzameling basisvariabelen, die in de basisoplossing andere waarden dan nul hebben, wordt de basis genoemd.
Variabelen die in de basisoplossing de waarde nul hebben, zijn geen basisvariabelen.
Om de beste oplossing te vinden, moeten we een vector x vinden die aan alle regels voldoet en de grootste of kleinste waarde voor het doel krijgt.
Maar het vinden van de beste oplossing vergt meer stappen dan alleen het vinden van een oplossing die werkt en geen slappe variabelen heeft.
Het is niet altijd mogelijk om een basisoplossing te vinden zonder slappe variabelen, vooral voor problemen met minder dan beperkingen.
Om een haalbare basisoplossing te vinden, moet u de simplex-methode of een ander lineair programmeeralgoritme gebruiken om te zoeken naar een oplossing die aan alle beperkingen voldoet en de minste niet-nulvariabelen heeft.
Eigenschappen en betekenis van een haalbare basisoplossing
Eigenschappen van een haalbare basisoplossing
Een haalbare basisoplossing heeft maximaal m variabelen die niet nul zijn en ten minste nm variabelen die nul zijn, waarbij n het aantal beslissingsvariabelen is en m het aantal beperkingen.
Een BFS is een hoek van het veelvlak van mogelijke oplossingen, en elke BFS heeft n actieve beperkingen die lineair onafhankelijk zijn.
Als er een beste oplossing is, moet er ook een beste eerste stap zijn.
Het belangrijkste van haalbare basisoplossingen is dat ze de uiteinden zijn van de verzameling convexe oplossingen voor een lineair programmeerprobleem.
Om het beste antwoord te vinden, doorloopt het simplex-algoritme een reeks BFS's.
Het Simplex-algoritme doorzoekt alle mogelijke basisoplossingen op een georganiseerde manier om de beste te vinden.
Betekenis van een haalbare basisoplossing
Het vinden van een mogelijke basisoplossing is belangrijk omdat het helpt bij het vinden van het beste antwoord op lineaire programmeerproblemen.
Het geeft ook complexe algoritmen een startpunt en kan worden gebruikt om erachter te komen of een lineair programma mogelijk is of niet.
Om alle haalbare basisoplossingen voor een lineair programma te vinden, kunt u het systeem wijzigen door losse variabelen toe te voegen en vervolgens het gewijzigde stelsel gebruiken om alle haalbare basisoplossingen te vinden.
Vervolgens worden deze haalbare basisoplossingen gebruikt om de haalbare basisoplossingen voor het oorspronkelijke probleem te vinden.
Video: haalbare basisoplossingen
Tip: Schakel de ondertitelingsknop in als je die nodig hebt. Kies "automatische vertaling" in de instellingenknop, als u de gesproken taal niet kent. Mogelijk moet u eerst op de taal van de video klikken voordat uw favoriete taal beschikbaar komt voor vertaling.
Gebruik gevallen
| Gebruikt in: | Beschrijving: |
|---|---|
| Toewijzing van middelen: | BFS kan worden gebruikt om beperkte middelen over verschillende projecten te verdelen, zodat met zo weinig mogelijk het meeste kan worden gedaan. Deze methode kan op veel verschillende gebieden worden gebruikt, zoals transport, landbouw en financiën. |
| Optimalisatie van het netwerk: | BFS kan worden gebruikt om communicatie-, transport- en logistieke netwerken beter te laten werken. BFS kan helpen bij het vinden van de beste routes voor goederen en diensten, het verminderen van tijd en geld besteed aan transport, en snellere en nauwkeurigere leveringen. |
| Planning voor productie: | BFS kan worden gebruikt om de productie te plannen, zodat middelen zoals arbeid, grondstoffen en apparatuur op de best mogelijke manier worden gebruikt om er het maximale uit te halen. BFS kan helpen de productiekosten te verlagen, afval te verminderen en de efficiëntie te verbeteren. |
| Financiële planning: | Bij financiële planning kan BFS worden gebruikt om investeringsportefeuilles te optimaliseren, risico's te verlagen en het meeste geld terug te krijgen. BFS kan helpen bij het vinden van de beste manier om activa te verdelen, transactiekosten te verlagen en meer geld te verdienen. |
| Beheer van de toeleveringsketen: | BFS kan worden gebruikt om de stroom van goederen en diensten van leveranciers naar klanten te verbeteren als onderdeel van supply chain management. BFS kan helpen bij het bepalen van de beste voorraad om bij de hand te houden, doorlooptijden te verkorten en de klantenservice te verbeteren. |
Conclusie
Nu deze blik op haalbare basisoplossingen ten einde loopt, is het duidelijk dat ze een belangrijk hulpmiddel zijn voor elke ingenieur of technische student.
Van het uitzoeken van de beste manier om een gecompliceerd systeem te bouwen tot het optimaal benutten van de beschikbare middelen, haalbare basisoplossingen bieden een raamwerk voor het verkrijgen van het best mogelijke resultaat.
Maar ze zijn niet alleen nuttig, ze laten ook zien hoe elegant en mooi wiskunde kan zijn.
Het is verbazingwekkend dat je ingewikkelde problemen kunt terugbrengen tot een eenvoudige reeks vergelijkingen en die vergelijkingen vervolgens kunt gebruiken om problemen in de echte wereld op te lossen.
Het is een goede herinnering dat techniek draait om het oplossen van problemen, en dat we door de kracht van wiskunde te gebruiken, antwoorden kunnen vinden die ooit voor onmogelijk werden gehouden.
Dus als je meer leert over engineering, onthoud dan wat je hebt geleerd over eenvoudige oplossingen die werken en gebruik ze om de wereld een betere, efficiëntere plek te maken.
Links en referenties
Boeken:
- Lineaire programmering: basis en uitbreidingen
- Lineair programmeren: theorie en toepassingen
Delen op…
