Grafische methode voor het oplossen van lineaire programmeerproblemen. Grafische methoden

De eenvoudigste en meest visuele methode voor het oplossen van een lineair programmeerprobleem (LPP) is de grafische methode. Het is gebaseerd op de geometrische interpretatie van het lineaire programmeerprobleem en wordt gebruikt om de ZLP met twee onbekenden op te lossen:

We zullen de oplossing van dit probleem in een vliegtuig overwegen. Elke ongelijkheid van het systeem van functionele beperkingen definieert geometrisch een halfvlak met een grenslijn een p x, + + a j2 x 2 = b n ik = 1, T. Niet-negativiteitsomstandigheden definiëren halve vlakken met grenslijnen X (= 0, x 2= 0 dienovereenkomstig. Als het systeem consistent is, vormen de halve vlakken die elkaar snijden een gemeenschappelijk deel, dat een convexe verzameling is en een verzameling punten vertegenwoordigt; de coördinaten van elk van deze punten zijn een oplossing voor dit systeem. De verzameling van deze punten wordt genoemd oplossing veelhoek. Het kan een punt, een segment, een straal, een begrensde of onbegrensde veelhoek zijn.

Geometrisch gezien is de ZLP dat wel het vinden van een hoekpunt van de oplossingspolygoon waarvan de coördinaten de maximale (minimale) waarde van de lineaire objectieve functie opleveren, Bovendien zijn alle punten van de oplossingspolygoon toelaatbare oplossingen.

Een lineaire vergelijking beschrijft een reeks punten die op dezelfde lijn liggen. Een lineaire ongelijkheid beschrijft een bepaald gebied in het vlak.

Laten we bepalen welk deel van het vlak de ongelijkheid beschrijft 2x (+ 3x 2 12.

Laten we eerst een rechte lijn 2x construeren, + Zx 2 = 12. Het gaat door de punten (6; 0) en (0; 4). Ten tweede bepalen we welk halfvlak aan de ongelijkheid voldoet. Om dit te doen, selecteert u een punt in de grafiek dat niet bij de lijn hoort en vervangt u de coördinaten ervan in de ongelijkheid. Als de ongelijkheid geldt, dan is dit punt een toelaatbare oplossing en voldoet het halfvlak dat het punt bevat aan de ongelijkheid. Het is handig om de oorsprong van coördinaten te gebruiken om de ongelijkheid te vervangen. Laten we vervangen x( = x2 = 0 tot ongelijkheid 2x, + 3x 2 12. We krijgen 2 0 + 3 0

Op dezelfde manier kunt u alle beperkingen van een lineair programmeerprobleem grafisch weergeven.

De oplossing voor elke ongelijkheid van het ZLP-beperkingssysteem is een halfvlak dat de grenslijn bevat en zich aan één kant ervan bevindt. Het snijpunt van halve vlakken, waarvan elk wordt bepaald door de overeenkomstige ongelijkheid van het systeem, wordt genoemd gebied van haalbare oplossingen(ODR) of domein van definitie.

Er moet aan worden herinnerd dat de regio van haalbare oplossingen voldoet aan de voorwaarden van niet-negativiteit (Xj > 0, j = 1, P). De coördinaten van elk punt dat tot het definitiedomein behoort, zijn een geldige oplossing voor het probleem.

Gebruik om de extreme waarde van de doelfunctie te vinden bij het grafisch oplossen van de ZLP gradiëntvector, waarvan de coördinaten gedeeltelijke afgeleiden zijn van de objectieve functie:

Deze vector toont de richting van de snelste verandering in de doelfunctie. Direct c [ x l + c 2 x 2 = f(x 0), loodrecht op de gradiëntvector is vlakke lijn doelfunctie (Fig. 2.2.2). Op elk punt op de niveaulijn neemt de doelfunctie dezelfde waarde aan. Laten we de doelfunctie gelijkstellen aan een constante waarde A. Het veranderen van de betekenis A, we krijgen een familie van parallelle lijnen, die elk een niveaulijn zijn van de objectieve functie.

Rijst. 2.2.2.

Een belangrijke eigenschap van de niveaulijn van een lineaire functie is dat wanneer de lijn evenwijdig naar één kant wordt verschoven, het niveau alleen neemt toe en wanneer het naar de andere kant wordt verschoven - alleen neemt af.

De grafische methode voor het oplossen van de PLP bestaat uit vier fasen:

• 1. De regio van toelaatbare oplossingen (ADA) van de PLP wordt gebouwd.
• 2. De gradiëntvector van de objectieffunctie (TF) wordt geconstrueerd met het begin op het punt x 0(0; 0): V = (s, vanaf 2).
• 3. Niveaulijn CjXj + c 2 x 2 = een (een - constante waarde) - een rechte lijn loodrecht op de gradiëntvector V, - beweegt in de richting van de gradiëntvector in het geval van het maximaliseren van de objectieve functie f(x v x 2) totdat het de ODR verlaat. Bij het minimaliseren van /(*, x2) de niveaulijn beweegt in de richting tegengesteld aan de gradiëntvector. Het uiterste punt (of punten) van de ODR tijdens deze beweging is het maximale (minimale) punt f(x p jc 2).

Als de rechte lijn die overeenkomt met de niveaulijn de ODR tijdens zijn beweging niet verlaat, dan is het minimum (maximum) van de functie f(x p x 2) bestaat niet.

Als de niveaulijn van de doelfunctie parallel loopt aan de functionele beperking van het probleem waarbij de optimale waarde van de CF wordt bereikt, dan zal de optimale waarde van de CF worden bereikt op elk punt van deze beperking dat tussen twee optimale hoekpunten ligt. , en dienovereenkomstig is elk van deze punten de optimale oplossing van de ZLP.

4. De coördinaten van het maximale (minimale) punt worden bepaald. Om dit te doen, volstaat het om een ​​systeem van vergelijkingen van lijnen op te lossen die een maximaal (minimaal) punt op het snijpunt opleveren. Betekenis f(x(,x2), gevonden op het resulterende punt is de maximale (minimale) waarde van de objectieve functie.

Mogelijke situaties van een grafische oplossing van de ZLP worden weergegeven in de tabel. 2.2.1.

Tabel 2.2.1

Voorbeeld 2.2.1. Planning van de productie van een naaibedrijf (probleem met pakken).

Het is de bedoeling om twee soorten pakken uit te brengen: heren- en damespakken. Voor een damespak is 1 m wol, 2 m lavasan en 1 mandag arbeid nodig; voor mannen - 3,5 m wol, 0,5 m lavsan en 1 mandag arbeid. In totaal zijn er 350 m wol, 240 m lavsan en 150 mandagen arbeid.

Het is vereist om te bepalen hoeveel kleuren van elk type er moeten worden gemaakt om maximale winst te garanderen als de winst uit de verkoop van een damespak 10 den bedraagt. eenheden, en van mannen - 20 den. eenheden Houd er rekening mee dat het noodzakelijk is om minimaal 60 herenpakken te naaien.

Economisch en wiskundig model van het probleem

Variabelen: X, - aantal damespakken; x 2 - aantal herenpakken.

Objectieve functie:

Beperkingen:

De eerste beperking (op wol) heeft de vorm x(+ 3,5x 2 x (+ 3,5x 2 = 350 gaat door de punten (350; 0) en (0; 100). De tweede beperking (volgens lavsan) heeft de vorm 2x (+ 0,5x 2 2x x + 0,5x 2 = 240 gaat door de punten (120; 0) en (0; 480). De derde beperking (op arbeid) heeft de vorm x y + x 2 150. Direct x (+ x 2 = 150 gaat door de punten (150; 0) en (0; 150). De vierde beperking (op het aantal herenpakken) heeft de vorm x 2> 60. De oplossing voor deze ongelijkheid is het halfvlak dat boven de rechte lijn ligt x 2 = 60.

Als resultaat van de kruising van de geconstrueerde vier halve vlakken verkrijgen we een polygoon, het gebied van haalbare oplossingen voor ons probleem. Elk punt op deze polygoon voldoet aan alle vier functionele ongelijkheden, en voor elk punt buiten deze polygoon zal minstens één ongelijkheid worden geschonden.

In afb. 2.2.3 De regio van haalbare oplossingen (ADA) is gearceerd. Om de bewegingsrichting naar het optimale te bepalen, construeren we een gradiëntvector V, waarvan de coördinaten gedeeltelijke afgeleiden zijn van de objectieve functie:

Om zo'n vector te construeren, moet je het punt (10; 20) met de oorsprong verbinden. Voor het gemak kun je een vector construeren die evenredig is met de vector V. Dus in Fig. 2.2.3 toont de vector (30; 60).

Vervolgens bouwen we een niveaulijn 10xj + 20x 2 = A. Laten we de doelfunctie gelijkstellen aan een constante waarde A. Het veranderen van de betekenis A, verkrijgen we een familie van parallelle lijnen, die elk een niveaulijn zijn van de objectieve functie.

Grafische methoden worden voornamelijk geassocieerd met de geometrische weergave van functionele afhankelijkheid met behulp van lijnen in een vlak. Grafieken worden gebruikt om snel de waarde van functies te vinden op basis van de overeenkomstige waarde van het argument, om functionele afhankelijkheden visueel weer te geven.
Bijna alle soorten grafieken worden gebruikt in economische analyses: vergelijkingsgrafieken, tijdreeksgrafieken, distributiecurves, correlatieveldgrafieken, statistische cartogrammen. Vergelijkingsdiagrammen zijn vooral wijdverspreid in de analyse - voor het vergelijken van rapportage-indicatoren met geplande indicatoren, eerdere perioden en toonaangevende ondernemingen van binnenlandse of buitenlandse ondernemingen. Om de dynamiek van economische verschijnselen visueel weer te geven (en bij analyse heb je heel vaak te maken met tijdreeksen), worden tijdreeksdiagrammen gebruikt.
Met behulp van een coördinatenraster worden ook grafieken gemaakt van de afhankelijkheid van bijvoorbeeld het kostenniveau van het volume geproduceerde en verkochte producten. grafieken waarop u correlaties tussen indicatoren kunt weergeven. In een systeem van coördinatenassen toont het beeld de invloed van verschillende factoren op een bepaalde indicator.
De grafische methode wordt veel gebruikt om productieprocessen, organisatiestructuren, programmeerprocessen, enz. te bestuderen. Om bijvoorbeeld de efficiëntie van het gebruik van productieapparatuur te analyseren, worden berekeningsgrafieken gemaakt, inclusief grafieken van meerdere factoren.

Notatie: elke cirkel wordt beschouwd als een van de hoekpunten van de grafiek; het nummer in de bovenste sector van elk hoekpunt betekent het serienummer; Op basis van de nummers van twee aangrenzende hoekpunten wordt de werkcode gevormd; het nummer in de onderste sector van elk hoekpunt is het serienummer van het vorige hoekpunt, en de lijn die deze twee hoekpunten verbindt, betekent een specifieke taak. Onder de streep staat de geplande duur van deze werkzaamheden; het getal in de linkersector van elk hoekpunt betekent de totale duur van al het voorgaande werk, het getal in de rechtersector verschilt van het getal aan de linkerkant door de hoeveelheid reserve (tijdreserve). Voor hoekpunten die op het kritieke pad liggen, vallen de getallen in de linker- en rechtersector van het hoekpunt dus samen, aangezien de tijdmarge 0 is.

In een wiskundig geformaliseerd systeem van analyse, planning en beheer nemen netwerkdiagrammen een bijzondere plaats in. Ze bieden een groot economisch effect bij de bouw en installatie van industriële en andere ondernemingen.
Met het netwerkdiagram (Fig. 6.1) kunt u de belangrijkste uit het gehele complex van werken identificeren, die zich op het kritieke pad bevinden, en de belangrijkste middelen van bouworganisaties hierop concentreren, relaties tot stand brengen tussen verschillende gespecialiseerde organisaties en hun werk. Activiteiten op het kritieke pad vereisen de langste wachttijd tot de volgende gebeurtenis arriveert. In de fase van operationele analyse en beheer maakt het netwerkschema het mogelijk om de voortgang van de bouw effectief te monitoren en tijdig maatregelen te nemen om mogelijke vertragingen in de werkzaamheden te elimineren.
Het gebruik van netwerkdiagrammen voor analyse, planning en beheer zorgt, zoals uit vele voorbeelden blijkt, voor een vermindering van de bouwtijd met 20-30% en een verhoging van de arbeidsproductiviteit met 15-20%.
Bij analyse rechtstreeks op bouwplaatsen draagt ​​het gebruik van materialen voor netwerkplanning en -beheer bij aan de juiste identificatie van de redenen die van invloed zijn op de voortgang van de bouw en de identificatie van bedrijven die niet zorgen voor de voltooiing van de hun toegewezen werkzaamheden of de levering van apparatuur binnen de in het schema vastgestelde termijnen.
De ontwikkeling van een netwerkschema in de bouw wordt uitgevoerd in aanwezigheid van: normen voor de duur van de bouw en de inbedrijfstellingsperiode van een object of complex van objecten, ontwerpramingen, een project voor het organiseren van de bouw en productie van werk, standaard technologische kaarten , actuele normen voor arbeidskosten, materialen en machinebediening. Bovendien wordt bij het opstellen van een schema gebruik gemaakt van de ervaring met het uitvoeren van individuele werken, evenals gegevens over de productiebasis van bouw- en installatieorganisaties.
Op basis van al deze gegevens wordt een tabel met werken en middelen samengesteld, waarin in de technologische volgorde van de werkproductie hun kenmerken, volume, arbeidsintensiteit in mandagen, uitvoerder (organisatie en team), aantal werknemers, ploegendiensten, behoefte aan mechanismen en materialen, bronnen van hun aanbod worden aangegeven, de totale duur van het werk in dagen, evenals de vorige taak, na voltooiing waarvan dit werk kan beginnen. Op basis van de indicatoren van een dergelijke tabel wordt een netwerkdiagram opgesteld, dat verschillende mate van detail kan hebben, afhankelijk van het aangenomen productieschema.
management van werk en managementniveau; Naast het algemene schema ontwikkelen de artiesten een schema voor het werk dat ze uitvoeren.
De belangrijkste elementen van een netwerkdiagram: gebeurtenis, werk, wachten, afhankelijkheid.
Bij het analyseren van de voortgang van de bouw van een object moet worden vastgesteld of de netwerkplanning correct is opgesteld, of het kritieke pad niet is overschat, of bij het optimaliseren van de planning rekening is gehouden met alle mogelijkheden om deze te verkorten, of elk werk kan parallel worden uitgevoerd of de tijd die eraan wordt besteed kan worden verminderd door de mechanisatiemiddelen te vergroten, enz. Dit is vooral belangrijk in gevallen waarin de duur van het werk volgens het schema niet garandeert dat de bouw op tijd wordt voltooid.
Het belangrijkste materiaal voor netwerkplanning dat in de analyse wordt gebruikt, is informatie over de voortgang van de werkzaamheden volgens het schema, dat gewoonlijk minstens één keer per decennium wordt opgesteld. Als voorbeeld wordt een kaart gegeven van de taak en informatie over de voortgang van de werkzaamheden aan een bouwproject uitgevoerd volgens het netwerkschema (Tabel 6.1). Volgens de kaart werden aan het begin van de maand kritieke werkzaamheden eerder dan gepland uitgevoerd, maar daarna mocht de installatie van kraanbalken langs rij B achterblijven en werden de daaropvolgende werkzaamheden - installatie van kraanbalken langs rij A - voltooid. één dag achter op schema.
Optimalisatie van netwerkschema's wordt uitgevoerd in de planningsfase door het kritieke pad te verkorten, dat wil zeggen het minimaliseren van de timing van bouwwerkzaamheden op bepaalde niveaus van middelen, het minimaliseren van het verbruik van materiaal, arbeid en financiële middelen op vaste deadlines voor het voltooien van bouwwerkzaamheden. Een gemengde aanpak is ook mogelijk: voor het ene deel van het werk (duurder) - om het niveau van het hulpbronnenverbruik te minimaliseren met een vaste deadline voor het voltooien van het werk, voor het andere - om de deadline voor een vast niveau van hulpbronnen te minimaliseren.
De oplossing van optimalisatieproblemen wordt aanzienlijk vergemakkelijkt door de aanwezigheid van applicatieprogrammapakketten (APP) die zijn aangepast voor het maken van optimale netwerkdiagrammen op een computer.
In de buitenlandse praktijk van systeemanalyse is een grafo-wiskundige methode, de ‘beslissingsboom’, gebruikelijk. De essentie van deze methode is als volgt.
Door middel van een voorlopige beoordeling van de behoeften, een voorlopige analyse van mogelijke organisatorische, technische of technologische omstandigheden, worden alle mogelijke opties voor het oplossen van een bepaald probleem geschetst. Eerst ontwikkeld

Aanleg van kraanbanen en installatie van torenkraan 7-10
Installatie van steunframes op de fundering voor apparatuur 7-16 Installatie van kraanbalken:
langs rij B 8-11
20/IV 24/IV 4
20/IV 24/IV 4
24/IV 25/IV 2

langs rij A 10-12 25/IV 26/IV
Montage van het eerste deel balken en afdekplaten 12-13 27/IV 4/V
Installatie van kraanbanen voor brug lt;3 kranen 12-14 27/IV 3/V

1. 100 -

vergrote opties. Wanneer er vervolgens aanvullende voorwaarden worden ingevoerd, wordt elk ervan onderverdeeld in een aantal opties. Met een grafische weergave van deze opties kunt u de minder winstgevende opties uitsluiten en de meest acceptabele kiezen.
Deze methode kan worden gebruikt bij het bepalen van de volgorde van verwerking van bepaalde onderdelen op meerdere machines om de totale verwerkingstijd te minimaliseren; bij het bepalen van de omvang van hulpbronnen om de totale productiekosten te minimaliseren; bij het verdelen van kapitaalinvesteringen en andere middelen over industriële faciliteiten; bij het oplossen van transport- en andere problemen.

In deze les maken we kennis met de grafische oplossingsmethode lineaire programmeerproblemen, dat wil zeggen dergelijke problemen waarbij het nodig is een oplossing te vinden voor een systeem van lineaire vergelijkingen en (of) ongelijkheden (systeem van beperkingen) waarin de objectieve functie - een lineaire functie - de optimale waarde aanneemt.

Vanwege het feit dat de duidelijkheid van de grafische oplossing alleen op een vlak wordt bereikt, kunnen we alleen kennis maken met de grafische weergave van het probleem in de tweedimensionale ruimte. Deze representatie is geschikt voor een systeem van ongelijkheidsbeperkingen met twee variabelen of voor systemen van vergelijkingen waarin het aantal variabelen het aantal vergelijkingen met 2 overschrijdt, dat wil zeggen dat het aantal vrije variabelen twee is.

Daarom heeft de grafische methode een zo beperkt toepassingsgebied dat er niet over kan worden gesproken als een speciale methode voor het oplossen van lineaire programmeerproblemen.

Voor het ontwikkelen van visuele representaties van oplossingen voor lineaire programmeerproblemen is de grafische methode echter van zeker belang. Bovendien stelt het ons in staat de geldigheid geometrisch te bevestigen lineaire programmeerstellingen .

Theoretische grondslagen van de grafische methode

Dit is dus een lineair programmeerprobleem. Het is vereist om niet-negatieve waarden van de variabelen te vinden en te voldoen aan het systeem van ongelijkheden

waarbij de lineaire vorm de optimale waarde aanneemt.

Voorbeeld 3.

Voorbeeld 4. Los een lineair programmeerprobleem op met behulp van een grafische methode waarbij je het minimum van een functie onder beperkingen moet vinden

Samen blijven we problemen oplossen via de grafische methode

De tot nu toe getrokken conclusies zijn gebaseerd op het feit dat de reeks oplossingen voor een lineair programmeerprobleem zodanig is geconfigureerd dat de optimale oplossing eindig en uniek is. Laten we nu eens kijken naar voorbeelden waarin deze voorwaarde wordt geschonden. In deze voorbeelden is de oplossingspolygoon geconstrueerd zoals getoond in de voorgaande voorbeelden; laten we stilstaan ​​bij de kenmerken die deze uitzonderlijke voorbeelden onderscheiden.

Voorbeeld 5. Los een lineair programmeerprobleem op met behulp van een grafische methode waarbij je het maximum van een functie onder beperkingen moet vinden

Oplossing. De figuur toont: een onbeperkt veelvlakkig oplossingsgebied voor dit systeem van beperkingen, een initiële niveaulijn (zwart), een vector (bordeauxrode kleur) die de bewegingsrichting van de initiële niveaulijn aangeeft om het maximum van de objectieve functie te vinden.

Het is gemakkelijk te zien dat de functie F kan onbeperkt toenemen onder een bepaald systeem van beperkingen, dus we kunnen voorwaardelijk schrijven dat .

Voorbeeld 6. Los een lineair programmeerprobleem op met behulp van een grafische methode waarbij je het maximum van een functie onder beperkingen moet vinden

Voorbeeld 6.1.

Oplossing:

Het lineaire programmeerprobleem wordt in standaardvorm gegeven en heeft daarom twee ontwerpparameters

Het is mogelijk om het op te lossen met behulp van de geometrische methode.

Fase 1: ( ODR ).

Beschouw de eerste beperking, vervang het ongelijkheidsteken door een gelijkheidsteken en druk de variabele uit x2 door x1:

.

Op dezelfde manier bepalen we de punten voor de resterende beperkingen van het systeem en construeren we daaruit rechte lijnen die overeenkomen met elke ongelijkheid (Fig. 1). We nummeren de lijnen volgens het eerder aangenomen schema.

Stage 2: .

Laten we halve vlakken definiëren - oplossingen voor elk van de ongelijkheden.

Laten we eens kijken naar de eerste ongelijkheid van het probleembeperkingssysteem. Laten we een punt nemen (controlepunt) dat niet behoort tot de lijn die overeenkomt met deze ongelijkheid, bijvoorbeeld punt (0; 0). Laten we het vervangen door de ongelijkheid die we beschouwen:

Bij het vervangen van de coördinaten van het controlepunt blijft de ongelijkheid geldig. Bijgevolg zullen de reeks punten die tot deze lijn behoren (aangezien de ongelijkheid niet strikt is), evenals de punten die zich eronder bevinden, oplossingen zijn voor de ongelijkheid in kwestie (laten we in de grafiek (Fig. 1) de gevonden helft markeren -vlak met twee pijlen die naar beneden wijzen naast de lijn I ) .

Op dezelfde manier bepalen we de oplossingen voor andere ongelijkheden en markeren ze dienovereenkomstig in de grafiek. Als gevolg hiervan ziet de grafiek er als volgt uit:

Fase 3: .

De gevonden halve vlakken (oplossingen voor elk van de ongelijkheden van het systeem van beperkingen) vormen een veelhoek wanneer ze elkaar snijden ABCDEO, wat de ODD is van het probleem dat wordt onderzocht.

Rijst. 1. Regio van haalbare oplossingen voor het probleem

Fase 4:
De gradiëntvector toont de richting van maximalisatie van de objectieve functie. Laten we de coördinaten bepalen: de coördinaten van het beginpunt (toepassingspunt) – (0; 0), de coördinaten van het tweede punt:

Laten we deze vector in de grafiek uitzetten (Fig. 2).

Fase 5: .

Laten we eens kijken naar de objectieve functie van dit probleem:

.

Laten we er een waarde aan geven, bijvoorbeeld . Laten we de variabele uitdrukken x2 door x1:

.

Om met deze vergelijking een rechte lijn te construeren, zullen we twee willekeurige punten specificeren, bijvoorbeeld:

Laten we een rechte lijn construeren die overeenkomt met de doelfunctie (Fig. 2).

Rijst. 2. Constructie van de doelfunctie F(X) en gradiëntvector C

Fase 6: het bepalen van het maximum van de doelfunctie.

Een rechte lijn verplaatsen F(X) evenwijdig aan zichzelf in de richting van de gradiëntvector bepalen we het uiterste punt (punten) van de ODR. Volgens de grafiek (Fig. 3) is zo'n punt punt C - het snijpunt van lijnen I En II .

Rijst. 3. Bepaling van het maximumpunt van de objectieffunctie F(X)

Laten we de coördinaten van punt C bepalen, voor dit doel lossen we het volgende systeem van lineaire vergelijkingen op:

Laten we de gevonden coördinaten vervangen door de objectieve functie en de optimale (maximale) waarde ervan vinden:

Antwoord: onder gegeven beperkingen, de maximale waarde van de objectieve functie F(X)=24, wat wordt bereikt op punt C, waarvan de coördinaten x1=6, x2=4.

Voorbeeld 6.2. Los het lineaire programmeerprobleem op met behulp van de geometrische methode:

Oplossing:

Fasen 1-3 zijn vergelijkbaar met de overeenkomstige fasen van de vorige taak.
Fase 4: constructie van een gradiëntvector.
De constructie van de gradiëntvector wordt op dezelfde manier uitgevoerd als in het vorige probleem. Laten we deze vector in de grafiek uitzetten (Fig. 4). Laten we in deze grafiek ook met een pijl de richting aanduiden die tegengesteld is aan de gradiëntvector - de richting van minimalisatie van de objectieve functie F (X).

Fase 5: constructie van een directe doelfunctie.

Constructie van een directe objectieve functie F(X) wordt op dezelfde manier uitgevoerd als in het vorige probleem (het constructieresultaat wordt getoond in figuur 4).

Rijst. 4. Constructie van de objectieffunctie F(x) en gradiëntvector C

Fase 6: het bepalen van het optimale van de doelfunctie.

Een rechte lijn verplaatsen F(X) evenwijdig aan zichzelf in de richting tegengesteld aan de gradiëntvector, bepalen we het uiterste punt (punten) van de ODR. Volgens de grafiek (Fig. 5) is zo'n punt punt O met coördinaten (0; 0).

Rijst. 5. Bepaling van het minimumpunt van de objectieffunctie

Door de coördinaten van het minimumpunt in de doelfunctie te vervangen, bepalen we de optimale (minimale) waarde, die gelijk is aan 0.
Antwoord: onder gegeven beperkingen, de minimumwaarde van de objectieve functie F(X)=0, die wordt bereikt op punt O (0; 0).

Voorbeeld 6.3. Los het volgende lineaire programmeerprobleem op met behulp van de geometrische methode:

Oplossing:

Het lineaire programmeringsprobleem dat we beschouwen, wordt gegeven in canonieke vorm; we selecteren de basisvariabelen X 1 En X2 .

Laten we een uitgebreide matrix samenstellen en de basisvariabelen selecteren met behulp van de Jordan-Gauss-methode X1 En X 2 .

Vermenigvuldig (element voor element) de eerste regel met –3 en tel deze op bij de tweede:
.

Vermenigvuldig de tweede regel met:

.

Laten we de tweede regel aan de eerste regel toevoegen:

.

Als gevolg hiervan zal het systeem van beperkingen de volgende vorm aannemen:

Laten we de basisvariabelen uitdrukken in termen van vrije variabelen:

Laten we de doelfunctie ook uitdrukken in termen van vrije variabelen; we vervangen de verkregen waarden van de basisvariabelen in de doelfunctie:

Laten we het resulterende lineaire programmeerprobleem schrijven:

Sinds de variabelen X1 En X2 niet-negatief is, kan het resulterende systeem van beperkingen in de volgende vorm worden geschreven:

Vervolgens kan het oorspronkelijke probleem als volgt worden geschreven, equivalent aan een standaard lineair programmeerprobleem:

Dit probleem heeft twee ontwerpparameters en kan daarom worden opgelost met behulp van de geometrische methode.

Fase 1: constructie van rechte lijnen die het gebied van haalbare oplossingen beperken ( ODR ).

Laten we eens kijken naar het systeem van beperkingen van het lineaire programmeringsprobleem (voor het gemak nummeren we de ongelijkheden):

Laten we rechte lijnen construeren die overeenkomen met elke ongelijkheid (Fig. 6). We nummeren de rechte lijnen volgens het eerder aangenomen schema.

Stage 2: bepaling van de oplossing voor elk van de ongelijkheden van het systeem van beperkingen.

Met behulp van controlepunten bepalen we halve vlakken - oplossingen voor elk van de ongelijkheden, en markeren ze op de grafiek (Fig. 6) met pijlen.

Fase 3: bepaling van de ODD van een lineair programmeerprobleem.

De gevonden halve vlakken (dat wil zeggen oplossingen voor elk van de ongelijkheden van het beperkingssysteem) hebben geen gemeenschappelijk snijpunt (dus de oplossingen voor ongelijkheid zijn in het algemeen in tegenspraak met de resterende ongelijkheden van het beperkingssysteem), daarom is het beperkingssysteem dat niet. consistent en het lineaire programmeringsprobleem heeft daarom geen oplossing.

Rijst. 6. Fragment van een MathCAD-document:

het construeren van een regio met haalbare oplossingen voor een probleem

Antwoord: Het beschouwde lineaire programmeringsprobleem heeft geen oplossing vanwege de inconsistentie van het systeem van beperkingen.

Als, na het vervangen van de coördinaten van het controlepunt in de ongelijkheid, de betekenis ervan wordt geschonden, dan is de oplossing voor deze ongelijkheid een halfvlak dat dit punt niet bevat (d.w.z. gelegen aan de andere kant van de lijn).

De richting tegengesteld aan de gradiëntvector komt overeen met de richting waarin de objectieve functie wordt geminimaliseerd.

Korte theorie

Lineair programmeren is een tak van wiskundig programmeren die wordt gebruikt bij de ontwikkeling van methoden voor het vinden van het uiterste van lineaire functies van verschillende variabelen onder lineaire aanvullende beperkingen die aan de variabelen worden opgelegd. Afhankelijk van het soort opgeloste problemen, zijn zijn methoden onderverdeeld in universeel en speciaal. Met behulp van universele methoden kunnen alle lineaire programmeerproblemen (LPP) worden opgelost. Speciale methoden houden rekening met de kenmerken van het probleemmodel, de objectieve functie en het systeem van beperkingen. Een kenmerk van lineaire programmeerproblemen is dat de doelfunctie een extremum bereikt op de grens van het gebied van haalbare oplossingen.

De grafische methode voor het oplossen van lineaire programmeerproblemen maakt het mogelijk om hun structuur te visualiseren, kenmerken te identificeren en opent manieren om complexere eigenschappen te bestuderen. Een lineair programmeerprobleem met twee variabelen is altijd grafisch op te lossen. Reeds in de driedimensionale ruimte wordt een dergelijke oplossing echter ingewikkelder, en in ruimtes met afmetingen groter dan drie is een grafische oplossing in het algemeen onmogelijk. Het geval van twee variabelen heeft geen bijzondere praktische betekenis, maar de overweging ervan verduidelijkt de eigenschappen van de LLP-beperkingen, leidt tot het idee om deze op te lossen en maakt de oplossingsmethoden en manieren van hun praktische implementatie geometrisch duidelijk.

Als de beperkingen en de objectieve functie meer dan twee variabelen bevatten, dan is dit noodzakelijk (of door de methode van sequentiële verbetering van de oplossing) - het is universeel en kan worden gebruikt om elk probleem op te lossen. Voor sommige toegepaste lineaire programmeerproblemen, zoals , zijn speciale oplossingsmethoden ontwikkeld.

Voorbeeld van probleemoplossing

De taak

De onderneming produceert twee soorten producten: Product 1 en Product 2. Om een ​​eenheid Product 1 te produceren, is het noodzakelijk om kg grondstoffen van het eerste type, kg grondstoffen van het tweede type, kg grondstoffen van het tweede type uit te geven. het derde type. Om een ​​eenheid van Product 2 te vervaardigen, is het noodzakelijk om kg van het eerste type, grondstoffen van het tweede type en grondstoffen van het derde type uit te geven. De productie wordt voorzien van grondstoffen van elk type in hoeveelheden van respectievelijk kg, kg, kg. De marktprijs van een eenheid van Product 1 bedraagt ​​duizend roebel, en een eenheid van Product 2 bedraagt ​​duizend roebel.

Vereist:

• Construeer een wiskundig model van het probleem.
• Stel een productieplan op voor producten dat maximale inkomsten uit de verkoop garandeert, met behulp van een grafische methode voor het oplossen van een lineair programmeerprobleem.

Om ervoor te zorgen dat de oplossing voor een lineair programmeerprobleem zo nauwkeurig en correct mogelijk is, bestellen velen goedkoop testwerk op deze site. Meer details (hoe een aanvraag indienen, prijzen, deadlines, betaalmethoden) kunt u lezen op de pagina Koop een testpapier over lineair programmeren...

De oplossing van het probleem

Model gebouw

Laten en geef het aantal vervaardigde producten van het 1e en 2e type aan.

Vervolgens resourcebeperkingen:

Bovendien, afhankelijk van de betekenis van de taak

De doelfunctie van het economisch-wiskundige model, die de inkomsten uit verkopen uitdrukt:

We krijgen het volgende economische en wiskundige model:

Constructie van het domein van haalbare oplossingen

Laten we het resulterende lineaire programmeerprobleem grafisch oplossen:

Om een ​​gebied met haalbare oplossingen te construeren, construeren we grenslijnen die overeenkomen met deze ongelijkheden in het coördinatensysteem:

Laten we de punten vinden waar de lijnen doorheen gaan:

De oplossing voor elke ongelijkheid van het ZLP-beperkingssysteem is een halfvlak dat de grenslijn bevat en zich aan één kant ervan bevindt.

Om een ​​halfvlak te definiëren, neemt u bijvoorbeeld een punt dat niet tot lijn (1 behoort) en vervangt u de coördinaten (0;0) door de overeenkomstige ongelijkheid. Omdat de ongelijkheid is waar:

Het oplossingsgebied van de overeenkomstige eerste ongelijkheid komt overeen met het linker halfvlak

Laten we bijvoorbeeld een punt nemen dat niet tot lijn (2 behoort), en de coördinaten (0;0) vervangen door de overeenkomstige ongelijkheid. Omdat de ongelijkheid is waar:

Laten we bijvoorbeeld een willekeurig punt nemen dat niet tot lijn (3 behoort) en de coördinaten (0;0) vervangen door de overeenkomstige ongelijkheid. Omdat de ongelijkheid is waar:

Het oplossingsgebied van de overeenkomstige tweede ongelijkheid komt overeen met het linker halfvlak

Het gebied van haalbare oplossingen is de figuur.

Het vinden van een oplossing voor het LP-probleem

We construeren een vector waarvan de coördinaten evenredig zijn met de coëfficiënten van de doelfunctie. Hier is de evenredigheidscoëfficiënt.

Teken een niveaulijn loodrecht op de geconstrueerde vector.

We verplaatsen de niveaulijn in de richting van de vector zodat deze het gebied van haalbare oplossingen op het uiterste punt raakt. De oplossing voor het maximum is het punt, waarvan de coördinaten worden gevonden als het snijpunt van de lijnen (2) en (1).

Antwoord

Het is dus noodzakelijk om 56 producten van het 1e type en 64 producten van het 2e type te produceren. In dit geval zijn de inkomsten uit de verkoop van producten maximaal en bedragen ze 5104 geldeenheden.

De grafische oplossingsmethode, als een probleem met twee variabelen lineaire beperkingen heeft en de objectieve functie kwadratisch is, wordt hier in detail besproken
De pagina beschrijft in detail de oplossing voor een lineair programmeerprobleem met behulp van de simplexmethode. Daarnaast toont het de constructie van een duaal lineair programmeerprobleem en het vinden van de oplossing ervan door het directe probleem op te lossen.

Transportprobleem en mogelijke methode
Het transportprobleem, het wiskundige model en de oplossingsmethoden worden in detail besproken: het vinden van het referentieplan met behulp van de minimale elementenmethode en het zoeken naar de optimale oplossing met de potentiële methode.

Convex programmeren - grafische methode
Er wordt een voorbeeld gegeven van het oplossen van een kwadratisch convex programmeerprobleem met behulp van een grafische methode.