Als je een ingenieur bent of een student engineering, weet je misschien wat het betekent om te optimaliseren.
Om het best mogelijke resultaat te krijgen, is het belangrijk om de beste manier te vinden om dingen te doen.
Bij lineair programmeren kunt u een basisoplossing gebruiken om de beste oplossing te vinden.
Maar wat is een basisoplossing en waarom is het zo belangrijk dat ingenieurs hiervan op de hoogte zijn? In dit artikel zal ik het hebben over wat basisoplossingen zijn, waarom ze belangrijk zijn in engineering en hoe ze kunnen worden gebruikt om de beste resultaten te behalen in verschillende situaties.
Dus gordel om en maak je klaar om in de wereld van basisoplossingen te duiken, waar ik de mysteries zal ontrafelen en je zal laten zien hoe krachtig deze techniek kan zijn.
Basisoplossingen in lineaire programmering
Formele definitie:
Een oplossing voor een lineair programmamodel bestaande uit m vergelijkingen in n variabelen wordt verkregen door m variabelen op te lossen in termen van de resterende (nm) variabelen en de (nm) variabelen gelijk te stellen aan nul.
Een basisoplossing in lineair programmeren is een manier om een lineair programmeerprobleem op te lossen dat aan bepaalde technische vereisten voldoet.
In het bijzonder is een vector x een basisoplossing voor een veelvlak als de vectoren {ai : xi = 0} lineair onafhankelijk zijn.
Dit betekent dat de kolommen van A die variabelen xi hebben die niet nul zijn, lineair onafhankelijk zijn.
Een basisoplossing met niet-negatieve componenten wordt een basis haalbare oplossing (BFS) (BFS) genoemd.
Een BFS voldoet aan alle regels die een veelvlak definiëren.
Elke BFS is een hoek van het veelvlak van haalbare oplossingen vanuit geometrisch oogpunt.
Om een basisoplossing te vinden, moet u nm variabelen die niet standaard zijn op nul zetten en de m variabelen die standaard zijn oplossen.
Het is mogelijk dat verschillende bases tot dezelfde basisoplossing leiden, wat betekent dat er meer dan één manier is om hetzelfde probleem op te lossen.
De Simplex-methode is een iteratief proces dat van de ene BFS naar de volgende BFS gaat totdat het de beste BFS vindt.
Nadat we de simplex-methode hebben gebruikt om een BFS te vinden, kunnen we zien of de oplossing de beste is door te kijken of andere BFS's in de buurt een betere waarde geven voor de doelfunctie.
Als zo'n BFS niet bestaat, dan is de huidige BFS de beste.
Lineair programmeermodel
Een lineair programmeermodel omvat drie hoofdcomponenten: beslissingsvariabelen, een objectieve functie en beperkingen.
Zowel de doelfunctie als de beperkingen moeten lineaire functies zijn en de beslissingsvariabelen moeten continu zijn.
De doelfunctie wordt gebruikt om een getal te verhogen of te verlagen dat staat voor winst, kosten, aantal gemaakte producten, enz.
Beperkingen zijn limieten of beperkingen op de totale hoeveelheid van een bepaalde bron die nodig is om de taken uit te voeren die het succesniveau in de beslissingsvariabelen bepalen.
Bovendien vereisen sommige lineaire programma's dat alle beslissingsvariabelen niet-negatief zijn.
In lineaire programmeermodellen kunt u ook integer- en binaire variabelen gebruiken.
Binaire variabelen kunnen alleen een waarde van 0 of 1 hebben, dus ze kunnen alleen een waarde van 0 of 1 hebben.
De Simplex-methode
Een van de meest gebruikte manieren om lineaire programmeerproblemen op te lossen, is de Simplex-methode.
Basisoplossingen zijn belangrijk in de simplex-methode omdat ze overeenkomen met de hoekpunten van het haalbare gebied, en de simplex-methode gaat van de ene hoek naar de andere totdat een optimale oplossing is gevonden.
De simplex-methode is een snelle manier om het beste antwoord op een lineair programmeerprobleem te vinden door gebruik te maken van de eigenschappen van basisoplossingen.
Om de simplex-methode te gebruiken om de beste BFS te vinden, moeten we een basis B vinden voor de beperkingsmatrix A en het systeem Ax = b oplossen met alle variabelen behalve de basis ingesteld op nul.
De resulterende waarden voor de basisvariabelen vormen een BFS.
Als er een optimale oplossing bestaat, dan bestaat er een optimale BFS.
De Simplex-methode gaat van de ene BFS naar een aangrenzende BFS totdat het een optimale BFS bereikt met behulp van spilprocedures.
Vergelijking tussen basisoplossingen en haalbare oplossingen
Het verschil tussen een basisoplossing en een haalbare oplossing is dat een basisoplossing aan geen enkele voorwaarde hoeft te voldoen.
Het moet met name vectoren hebben die lineair onafhankelijk zijn en waarden hebben die niet gelijk zijn aan nul voor xi, en x moet kleiner zijn dan 0.
Aan de andere kant is een haalbare oplossing elk punt dat binnen de grenzen van het probleem past.
Maar niet alle haalbare oplossingen zijn haalbare basisoplossingen.
Basis haalbare oplossingen (BFS's) zijn alleen oplossingen die overeenkomen met de hoeken van het veelvlak van haalbare oplossingen.
Terug naar de basis: de kracht van basisoplossingen in engineering ontsluiten
Nog steeds moeilijk te begrijpen? Laat me het standpunt een beetje veranderen:
Ben je het beu om ingewikkelde methoden en algoritmen te gebruiken om lastige problemen op te lossen? Zou je willen dat er een eenvoudigere, meer directe manier was om met je lineaire programmamodelproblemen om te gaan?
Maak je geen zorgen, want het antwoord is hier: los voor m variabelen op in termen van de resterende (nm) variabelen, en stel de (nm) variabelen in op nul.
Wie heeft algoritmen nodig die mooi klinken als je terug kunt gaan naar de basis? Dus berg uw rekenmachines op en laten we beginnen met het leren over eenvoudige oplossingen.
Oké, dat was maar een grap gemaakt om eruit te zien als een tv-reclame.
Laten we nu teruggaan naar de uitleg.
Basisoplossing lineaire programmering
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: | De basisoplossing kan worden gebruikt bij problemen met de toewijzing van middelen, waarbij het doel is om beperkte middelen te verdelen over concurrerende behoeften. Een bedrijf moet bijvoorbeeld zijn budget verdelen over verschillende afdelingen of projecten. Door basisoplossingen te gebruiken, kunnen ze de beste manier vinden om hun middelen te gebruiken om het meeste geld te verdienen of zo min mogelijk uit te geven. |
| Planning voor productie: | Bij de productieplanning kan de basisoplossing worden gebruikt om de beste mix van producten te bepalen om het meeste geld te verdienen. Bedrijven kunnen de beste productiemix vinden die het meeste geld opbrengt en het minst kost door de basisoplossing te gebruiken. |
| Het roosteren: | De basisoplossing kan worden gebruikt om erachter te komen hoe taken of taken moeten worden gepland, zodat ze op de meest efficiënte manier kunnen worden uitgevoerd. Een bedrijf moet bijvoorbeeld de werkuren van zijn werknemers plannen om ervoor te zorgen dat ze genoeg werknemers hebben als het druk is. Door een basisoplossing te gebruiken, kunnen ze de beste manier bedenken om dingen te plannen, zodat er zo min mogelijk downtime is en er zoveel mogelijk werk wordt verzet. |
| Beheer van de toeleveringsketen: | Bij supply chain management is het doel ervoor te zorgen dat goederen en diensten zo soepel mogelijk van de leverancier naar de klant gaan. Een bedrijf moet bijvoorbeeld de beste routes voor het transporteren van goederen uitzoeken, zodat de kosten tot een minimum worden beperkt en de goederen op tijd worden afgeleverd. Door basisoplossingen te gebruiken, kunnen ze het beste plan vinden voor het beheer van de toeleveringsketen dat de kosten laag houdt en klanten tevreden houdt. |
| Portfolio-optimalisatie: | Bij portfolio-optimalisatie, waarbij het doel is om de beste mix van investeringen te vinden om het meeste geld te verdienen en het minste risico te nemen, kunnen basisoplossingen worden gebruikt. Een beleggingsonderneming moet bijvoorbeeld mogelijk de beste mix van aandelen, obligaties en andere effecten uitzoeken om hun klanten te helpen hun beleggingsdoelen te bereiken. Door een eenvoudige oplossing te gebruiken, kunnen ze de beste manier vinden om hun portefeuilles te mixen, zodat ze het beste rendement behalen terwijl ze het minste risico nemen. |
Conclusie
Kortom, het idee van een basisoplossing is erg belangrijk op het gebied van engineering en kan op veel verschillende manieren worden gebruikt.
Door te weten wat een basisoplossing is en wat deze doet bij lineair programmeren, kunnen we oplossingen verbeteren, kosten besparen en efficiënter maken.
Maar het is belangrijk om te onthouden dat een basisoplossing geen pasklare oplossing is, ook al is het een krachtig hulpmiddel.
Om de beste resultaten te krijgen, moet elk probleem zorgvuldig worden bekeken en overwogen.
Als ingenieurs moeten we blijven onderzoeken hoe basisoplossingen en andere optimalisatietechnieken ons kunnen helpen vooruitgang te boeken en nieuwe ideeën te bedenken.
Laten we dus de kracht van eenvoudige oplossingen inzien en de grenzen blijven verleggen van wat mogelijk is door nieuwe technieken en strategieën te gebruiken.
Links en referenties
Boeken:
- Lineaire programmering door Vasek Chvatal
- Modelleren en oplossen van lineaire programmering met R door Jose M. Sallan
Delen op…
