Een grafische methode voor het oplossen van lineaire programmeerproblemen. Grafische methoden

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

We zullen de oplossing van dit probleem in het vliegtuig bekijken. Elke ongelijkheid van het systeem van functionele beperkingen definieert geometrisch een halfvlak met een grenslijn een n x, + + een j2 х 2 \u003d b n ik \u003d 1, t. Niet-negativiteitscondities definiëren halfvlakken met grenslijnen x (= 0, x 2= 0 respectievelijk. Als het systeem compatibel is, vormen de elkaar snijdende halfvlakken een gemeenschappelijk deel, dat een convexe verzameling is en een verzameling punten; de coördinaten van elk van deze punten zijn de oplossing voor dit systeem. De verzameling van deze punten wordt gebeld polygoonoplossingen. Het kan een punt, lijn, straal, begrensde of onbegrensde veelhoek zijn.

Geometrisch is de LPP het vinden van zo'n hoekpunt van de oplossingspolygoon, waarvan de coördinaten de maximale (minimum) waarde van de lineaire objectieve functie opleveren, en alle punten van de oplossingsveelhoek zijn haalbare oplossingen.

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

Laten we bepalen welk deel van het vlak wordt beschreven door de ongelijkheid 2x (+ Zx 2 12.

Bouw eerst een lijn 2x, + Zx 2 \u003d 12. Het passeert de punten (6; 0) en (0; 4). Ten tweede bepalen we welk halfvlak aan de ongelijkheid voldoet. Om dit te doen, selecteert u elk punt in de grafiek dat niet tot een rechte lijn behoort en vervangt u de coördinaten door de ongelijkheid. Als de ongelijkheid blijft bestaan, dan is dit punt een toelaatbare oplossing en voldoet het halfvlak dat het punt bevat aan de ongelijkheid. Voor substitutie in ongelijkheid is het handig om de oorsprong te gebruiken. Plaatsvervanger x (\u003d x 2 \u003d 0 in de ongelijkheid 2x, + Зх 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 LPP-systeem van beperkingen is een halfvlak dat de grenslijn bevat en zich aan één kant ervan bevindt. Het snijpunt van halve vlakken, die elk worden bepaald door de overeenkomstige ongelijkheid van het systeem, wordt genoemd domein van haalbare oplossingen (ODR) of domein van de definitie.

Er moet aan worden herinnerd dat het gebied met haalbare oplossingen voldoet aan de niet-negativiteitsvoorwaarden (Xj > 0, j \u003d 1, p). De coördinaten van elk punt dat tot het definitiedomein behoort, zijn een haalbare oplossing voor het probleem.

Gebruik om de extreme waarde van de objectieve functie voor de grafische oplossing van de LPP te vinden vector-verloop, waarvan de coördinaten partiële afgeleiden zijn van de doelfunctie:

Deze vector toont de richting van de snelste verandering in de doelfunctie. Rechtdoor c [X l + c 2 X 2 \u003d f (X 0), loodrecht op de verloopvector is niveau lijn objectieve functie (Fig.2.2.2). Op elk punt op de niveaulijn krijgt de doelfunctie dezelfde waarde. Laten we de doelfunctie gelijkstellen aan een constante waarde een. Door de betekenis te veranderen een, we krijgen een familie van parallelle rechte lijnen, die elk een lijn zijn van het objectieve functieniveau.

Figuur: 2.2.2.

Een belangrijke eigenschap van de lijn van het niveau van een lineaire functie is dat bij een parallelle verplaatsing van de lijn in één richting, het niveau alleen stijgt, en wanneer verschoven naar de andere kant - alleen neemt af.

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

• 1. Het gebied van toelaatbare oplossingen (ODS) van het LPP is geconstrueerd.
• 2. Construeer de vectorgradiënt van de doelfunctie (CF) met het begin bij het punt x 0 (0; 0): V \u003d (s, c 2).
• 3. Niveauregel CjXj + c 2 x 2 \u003d een (een - constante) - een rechte lijn loodrecht op de gradiëntvector V, - beweegt in de richting van de gradiëntvector bij het maximaliseren van de doelfunctie f (x v x 2) totdat het de grenzen van de ODR verlaat. Bij het minimaliseren van / (*, x 2) de niveaulijn beweegt in de tegenovergestelde richting van de verloopvector. Het uiterste punt (of de punten) van de ODR tijdens deze beweging is het maximale (minimum) punt f (x p jc 2).

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

Als de lijn van het objectieve functieniveau parallel loopt aan de functionele beperking van het probleem, waarbij de optimale waarde van de CF wordt bereikt, dan wordt de optimale waarde van de CF bereikt op elk punt van deze beperking dat tussen twee optimale hoekpunten ligt, en dienovereenkomstig is elk van deze punten de optimale oplossing voor de LPP.

4. De coördinaten van het maximale (minimum) punt worden bepaald. Om dit te doen, volstaat het om het stelsel van vergelijkingen van rechte lijnen op te lossen die een maximum (minimum) punt op het snijpunt geven. Waarde f (x (, x 2),gevonden op het verkregen punt is de maximale (minimum) waarde van de doelfunctie.

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

Tabel 2.2.1

Voorbeeld 2.2.1. Productieplanning voor een naai-onderneming (kostuumprobleem).

Het is de bedoeling om twee soorten pakken uit te brengen: mannen en vrouwen. Een damespak vereist 1 m wol, 2 m lavsan en 1 persoon per dag arbeid; voor mannen - 3,5 m wol, 0,5 m lavsan en 1 persoon per dag 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 moeten worden genaaid om de maximale winst te garanderen, als de winst uit de verkoop van een damespak 10 den is. eenheden, en van de man - 20 den. eenheden Houd er rekening mee dat er minimaal 60 herenpakken moeten worden genaaid.

Economisch en wiskundig model van het probleem

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

Objectieve functie:

Beperkingen:

De eerste beperking (voor wol) is x (+ 3.5x 2 x (+ 3.5x 2 \u003d 350 passeert de punten (350; 0) en (0; 100). De tweede beperking (door lavsan) heeft de vorm 2x ( + 0,5x 2 2x + 0,5x 2 \u003d 240 passeert de punten (120; 0) en (0; 480). De derde beperking (op arbeid) heeft de vorm x y + x 2 150. Recht x (+ x 2 \u003d 150 passeert punten (150; 0) en (0; 150). De vierde beperking (van het aantal herenpakken) is x 2 \u003e 60. De oplossing voor deze ongelijkheid is het halfvlak dat boven de rechte lijn ligt x 2 \u003d 60.

Als resultaat van de kruising van de geconstrueerde vier halfvlakken, krijgen we een polygoon, die het gebied is van haalbare oplossingen voor ons probleem. Elk punt van deze polygoon voldoet aan alle vier functionele ongelijkheden, en voor elk punt buiten deze polygoon zal ten minste één ongelijkheid worden geschonden.

In afb. 2.2.3 het gebied van toelaatbare oplossingen (ODS) is gearceerd. Om de bewegingsrichting optimaal te bepalen, construeren we een gradiëntvector V, waarvan de coördinaten partiële afgeleiden zijn van de doelfunctie:

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

Vervolgens trekken we een lijn van niveau 10xj + 20x 2 \u003d een. Laten we de doelfunctie gelijkstellen aan een constante waarde een. Door de betekenis te veranderen eenkrijgen we een familie van parallelle rechte lijnen, die elk een niveaulijn zijn van de doelfunctie.

Grafische methoden worden voornamelijk geassocieerd met de geometrische weergave van functionele afhankelijkheid met behulp van lijnen op een vlak. Grafieken worden gebruikt om snel de waarde van functies te vinden aan de hand van de overeenkomstige waarde van het argument, voor een visuele weergave van functionele afhankelijkheden.
Bijna alle soorten grafieken worden gebruikt bij economische analyse: vergelijkingsgrafieken, tijdreeksgrafieken, verdelingskrommen, correlatieveldgrafieken, statistische cartogrammen. Vergelijkingsgrafieken zijn vooral wijdverbreid in de analyse - voor het vergelijken van gerapporteerde indicatoren met geplande indicatoren, van voorgaande perioden en geavanceerde ondernemingen in binnen- of buitenland. Tijdreeksdiagrammen worden gebruikt om de dynamiek van economische verschijnselen in beeld te brengen (en in de analyse met tijdreeksen heb je heel vaak te maken).
Met behulp van een coördinatenraster worden afhankelijkheidsgrafieken gemaakt, bijvoorbeeld ook het kostenniveau op het volume van vervaardigde en verkochte producten. grafieken waarop u de correlaties tussen indicatoren kunt weergeven. In het coördinatensysteem toont de afbeelding 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 rekengrafieken gemaakt, inclusief grafieken van meerdere factoren.

Legenda: elke cirkel wordt beschouwd als een van de hoekpunten van de grafiek; het nummer in de bovenste sector van elk hoekpunt betekent het serienummer; uit de nummers van twee aangrenzende hoekpunten wordt de werkcode toegevoegd; het nummer in de onderste sector van elk hoekpunt is het rangtelwoord van het vorige hoekpunt, en de lijn die deze twee hoekpunten verbindt, geeft een bepaald werk aan. Onder de streep staat de geplande duur van deze werkzaamheden; het cijfer in de linker sector van elk hoekpunt betekent de totale duur van alle voorgaande werken, het cijfer in de rechter sector verschilt van het cijfer in de linker door de hoeveelheid reserve (tijdreserve). Dus voor de hoekpunten die op het kritieke pad liggen, vallen de getallen in de linker- en rechtersector van het hoekpunt samen, aangezien de tijdmarge 0 is.

In een wiskundig geformaliseerd systeem van analyse, planning en beheer nemen netwerkdiagrammen een speciale plaats in. Ze geven een groot economisch effect bij de bouw en installatie van industriële en andere ondernemingen.
Het netwerkschema (Fig.6.1) stelt u in staat om de belangrijkste op het kritieke pad van het hele complex van werken te markeren en om daarop de belangrijkste middelen van bouw- en installatieorganisaties te focussen, om relaties op te bouwen tussen verschillende gespecialiseerde organisaties en hun werk te coördineren. De werkzaamheden op het kritieke pad vereisen het langst wachten op de volgende gebeurtenis. In de fase van operationele analyse en beheer maakt het netwerkschema het mogelijk om de voortgang van de bouw effectief te volgen en tijdig maatregelen te nemen om mogelijke vertragingen in het werk te elimineren.
Het gebruik van netwerkdiagrammen van analyse, planning en beheer levert, zoals veel voorbeelden laten zien, een vermindering van de bouwtijd met 20-30%, een toename van de arbeidsproductiviteit met 15-20% op.
Bij de analyse die rechtstreeks op bouwplaatsen wordt uitgevoerd, draagt \u200b\u200bhet gebruik van materialen voor netwerkplanning en -beheer bij tot de juiste bepaling van de oorzaken die de voortgang van de bouw beïnvloeden, en de identificatie van ondernemingen die de uitvoering van de aan hen toevertrouwde werkzaamheden of de levering van apparatuur niet binnen het tijdsbestek van het tijdschema garanderen.
De ontwikkeling van een netwerkschema in de bouw wordt uitgevoerd in aanwezigheid van: normen voor de duur van de bouw en de periode van inbedrijfstelling van een object of een complex van objecten, ontwerpschattingen, een project voor het organiseren van constructie en productie van werk, standaard stroomdiagrammen, huidige normen voor arbeidskosten, materialen en machinebediening. Bovendien wordt bij het opstellen van de planning 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 hun kenmerken, volume, arbeidsintensiteit in mandagen, uitvoerder (organisatie en team), aantal werknemers, ploegen, de behoefte aan mechanismen en materialen, bronnen van ontvangst worden aangegeven in de technologische volgorde van het werk , de totale duur van het werk in dagen, evenals de vorige taak, waarna u met dit werk kunt beginnen. Op basis van de indicatoren van een dergelijke tabel wordt een netwerkschema opgesteld, dat een variërende mate van detail kan hebben, afhankelijk van het aangenomen productieschema.
werkleiderschap en managementniveau; Naast het algemene schema stellen artiesten een schema op voor het werk dat ze uitvoeren.
De belangrijkste elementen van het netwerkschema: evenement, werk, verwachting, afhankelijkheid.
Bij het analyseren van de voortgang van de bouw van een object, moet worden vastgesteld of het netwerkschema correct is opgesteld, of het kritieke pad niet is overschat, of bij het optimaliseren van het schema rekening is gehouden met alle mogelijkheden om het te verkleinen, of het mogelijk is om werkzaamheden parallel uit te voeren of de tijd die eraan wordt besteed te verkorten door vergroting van de mechanisatiemiddelen enz. Dit is vooral van belang in gevallen waarin de duur van het geplande werk niet garandeert dat de bouw op tijd kan worden voltooid.
Het belangrijkste materiaal voor netwerkplanning dat bij de analyse wordt gebruikt, is informatie over de voortgang van het werk volgens een schema, dat gewoonlijk ten minste eenmaal per decennium wordt opgesteld. Als voorbeeld wordt een kaart van de opdracht gegeven en informatie over de voortgang van de werkzaamheden aan het bouwobject, uitgevoerd volgens de netwerkplanning (tabel 6.1). Volgens de kaart werd er aan het begin van de maand eerder dan gepland kritisch werk uitgevoerd, maar toen was een vertraging in de installatie van kraanbalken langs rij B toegestaan \u200b\u200ben werd het daaropvolgende werk - installatie van kraanbalken langs rij A - met een dag vertraging voltooid.
Optimalisatie van netwerkschema's wordt uitgevoerd in de planningsfase door het kritieke pad te verminderen, d.w.z. de timing van bouwwerkzaamheden op een bepaald niveau van middelen te minimaliseren, het niveau van materiaal-, arbeids- en financiële middelen te minimaliseren met een vaste timing van bouwwerkzaamheden. Een gemengde aanpak is ook mogelijk: voor het ene deel van het werk (duurder) - om het verbruik van middelen op een vast tijdsbestek te minimaliseren voor het werk, voor het andere - om de tijd te minimaliseren op een vast niveau van middelen.
De oplossing van optimalisatieproblemen wordt aanzienlijk vergemakkelijkt door de aanwezigheid van toepassingssoftwarepakketten (APP's) die zijn aangepast voor het samenstellen van optimale netwerkdiagrammen op een computer.
In de buitenlandse praktijk van systeemanalyse is een grafisch-wiskundige methode genaamd "beslissingsboom" wijdverbreid. De essentie van deze methode is als volgt.
Door middel van een voorlopige behoeftenanalyse, een voorlopige analyse van mogelijke organisatorische, technische of technologische omstandigheden, worden alle mogelijke opties voor het oplossen van dit probleem geschetst. Voor het eerst ontwikkeld

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

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

1. 100 -

vergrote opties. Vervolgens, als er aanvullende voorwaarden worden geïntroduceerd, wordt elk ervan onderverdeeld in een aantal opties. Door de grafische weergave van deze opties kunt u de minder winstgevende opties uitsluiten en de meest acceptabele kiezen.
Deze methode kan in ons bedrijf worden gebruikt bij het bepalen van de volgorde van bewerking van bepaalde onderdelen op meerdere machines om de totale verwerkingstijd te minimaliseren; bij het instellen van de omvang van middelen om de totale productiekosten te minimaliseren; bij het verdelen van kapitaalinvesteringen en andere middelen voor industriële faciliteiten; bij het oplossen van transport- en andere problemen.

In deze les maken we kennis met de grafische methode van oplossen lineaire programmeerproblemen , dat wil zeggen, dergelijke problemen waarbij het nodig is om een \u200b\u200boplossing te vinden voor een systeem van lineaire vergelijkingen en (of) ongelijkheden (een systeem van beperkingen), waarbij de doelfunctie - een lineaire functie - de optimale waarde aanneemt.

Gezien het feit dat de duidelijkheid van de grafische oplossing alleen in het vlak wordt bereikt, kunnen we alleen in een tweedimensionale ruimte kennismaken met de grafische weergave van het probleem. Deze weergave is geschikt voor een systeem van ongelijkheidsbeperkingen met twee variabelen of voor stelsels vergelijkingen waarin het aantal variabelen 2 meer is dan het aantal vergelijkingen, dat wil zeggen het aantal vrije variabelen is gelijk aan twee.

Daarom heeft de grafische methode een zo beperkt toepassingsgebied dat men er niet van kan spreken als een speciale methode om lineaire programmeerproblemen op te lossen.

De grafische methode is echter van zeker belang om visuele weergaven van oplossingen voor lineaire programmeerproblemen te ontwikkelen. Bovendien kunt u hiermee de geldigheid van lineaire programmeerstellingen .

Theoretische grondslagen van de grafische methode

Een lineair programmeerprobleem dus. 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 grafisch een lineair programmeerprobleem op waarin u het minimum van een functie onder beperkingen wilt vinden

Samen blijven we problemen grafisch oplossen

Tot nu toe zijn de bereikte conclusies gebaseerd op het feit dat de reeks oplossingen voor een lineair programmeerprobleem zo is geconfigureerd dat de optimale oplossing eindig en uniek is. Laten we nu eens kijken naar voorbeelden wanneer deze voorwaarde wordt geschonden. In deze voorbeelden is de beslissingspolygoon geconstrueerd zoals getoond in de vorige voorbeelden, maar laten we stilstaan \u200b\u200bbij de kenmerken die deze uitzonderlijke voorbeelden onderscheiden.

Voorbeeld 5.Los een lineair programmeerprobleem grafisch op waarin u het maximum van een functie onder beperkingen wilt vinden

Besluit. De figuur toont: een onbeperkt veelzijdig gebied van oplossingen van dit systeem van beperkingen, de initiële niveaulijn (zwart), een vector (bordeauxrood) die de bewegingsrichting aangeeft van de initiële niveaulijn om het maximum van de doelfunctie te vinden.

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

Voorbeeld 6.Los een lineair programmeerprobleem grafisch op waarin u het maximum van een functie onder beperkingen wilt vinden

Voorbeeld 6.1.

Besluit:

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

Het is mogelijk om het op te lossen met een geometrische methode.

Fase 1: ( SDT ).

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

.

Op dezelfde manier bepalen we de punten voor de resterende beperkingen van het systeem en construeren we rechte lijnen die overeenkomen met elke ongelijkheid (figuur 1). De rechte lijnen zijn genummerd volgens het eerder aangenomen schema.

Stage 2: .

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

Beschouw de eerste ongelijkheid van het systeem van beperkingen van het probleem. Neem een \u200b\u200bpunt (controlepunt) dat niet behoort tot de lijn die overeenkomt met deze ongelijkheid, bijvoorbeeld het punt (0; 0). We vervangen het in de beschouwde ongelijkheid:

Bij het vervangen van de coördinaten van het controlepunt blijft de ongelijkheid waar. Bijgevolg zullen de reeks punten die tot deze rechte lijn behoren (aangezien de ongelijkheid niet strikt is), evenals de punten die eronder liggen, oplossingen zijn van de ongelijkheid in kwestie (we markeren in de grafiek (figuur 1) het gevonden halfvlak met twee pijlen die naar beneden wijzen naast de rechte lijn. ik ) .

Evenzo definiëren we oplossingen voor andere ongelijkheden en markeren deze dienovereenkomstig in de grafiek. Als resultaat ziet de grafiek er als volgt uit:

Stap 3: .

De gevonden halfvlakken (oplossingen van elk van de ongelijkheden van het systeem van beperkingen) op hun snijpunt vormen een veelhoek ABCDEO, wat de ODR is van het probleem in kwestie.

Figuur: 1. Domein van haalbare oplossingen voor het probleem

Stap 4:
De gradiëntvector toont de richting van maximalisatie van de doelfunctie. Laten we de coördinaten definiëren: coördinaten van het beginpunt (toepassingspunt) - (0; 0), coördinaten van het tweede punt:

Laten we deze vector op de grafiek bouwen (Fig. 2).

Stap 5: .

Overweeg de objectieve functie van deze taak:

.

Laten we het bijvoorbeeld wat waarde geven. Laten we de variabele uitdrukken x2 aan de overkant x1:

.

Om een \u200b\u200brechte lijn te construeren volgens deze vergelijking, stellen we twee willekeurige punten in, bijvoorbeeld:

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

Figuur: 2. Constructie van de doelfunctie F (X) en de gradiëntvector С

Stap 6: bepaling van het maximum van de objectieve functie.

Rechtdoor gaan F.(X) evenwijdig aan zichzelf in de richting van de gradiëntvector definiëren we het uiterste punt (de punten) van de ODR. Volgens de grafiek (Fig. 3) is zo'n punt punt C - het snijpunt van rechte lijnen ik en II .

Figuur: 3. Bepaling van het maximale punt van de objectieve functie F (X)

Bepaal de coördinaten van punt C, hiervoor lossen we het volgende stelsel lineaire vergelijkingen op:

Vervang de gevonden coördinaten door de doelfunctie en vind de optimale (maximale) waarde:

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

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

Besluit:

Stappen 1-3 zijn vergelijkbaar met de overeenkomstige stappen in de vorige taak.
Stap 4: constructie van een vectorgradiënt.
De constructie van de verloopvector wordt op dezelfde manier uitgevoerd als in de vorige taak. Laten we deze vector op de grafiek bouwen (Fig. 4). We noteren in deze grafiek ook met een pijl de richting tegengesteld aan de gradiëntvector - de richting van minimalisatie van de doelfunctie F. (X).

Stap 5: constructie van een directe objectieve functie.

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

Figuur: 4. Constructie van de doelfunctie F (x) en de gradiëntvector С

Stap 6: bepaling van het optimum van de doelfunctie.

Rechtdoor gaan F.(x) parallel aan zichzelf in de richting tegengesteld aan de gradiëntvector, definiëren we het uiterste punt (de punten) van de ODR. Volgens de grafiek (Fig. 5) is zo'n punt punt O met coördinaten (0; 0).

Figuur: 5. Bepaling van het minimum punt van de objectieve functie

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

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

Besluit:

Het weloverwogen lineaire programmeerprobleem wordt gegeven in de 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 .

Laten we de eerste rij vermenigvuldigen (element voor element) met –3 en deze toevoegen met de tweede:
.

Vermenigvuldig de tweede regel met:

.

Voeg de tweede toe aan de eerste regel:

.

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

Laten we de basisvariabelen uitdrukken in termen van gratis:

We drukken de objectieve functie ook uit in termen van vrije variabelen, hiervoor vervangen we de verkregen waarden van de basisvariabelen in de objectieve functie:

Laten we het resulterende lineaire programmeerprobleem schrijven:

Omdat de variabelen x1 en x2 zijn niet-negatief, dan kan het resulterende systeem van beperkingen in de volgende vorm worden geschreven:

Dan kan het oorspronkelijke probleem worden geschreven als het volgende equivalente standaard lineaire programmeerprobleem:

Deze taak heeft twee ontwerpparameters en kan daarom worden opgelost met een geometrische methode.

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

Beschouw het systeem van beperkingen voor het lineaire programmeerprobleem (gemakshalve noemen we de ongelijkheden):

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

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

Met behulp van de controlepunten definiëren we de halfvlakken - de oplossingen van elk van de ongelijkheden, en markeren ze in de grafiek (Fig. 6) met behulp van de pijlen.

Stap 3: definitie van ODR van een lineair programmeerprobleem.

De gevonden halfvlakken (d.w.z. oplossingen voor elk van de ongelijkheden van het systeem van beperkingen) hebben geen gemeenschappelijk snijpunt (dus de oplossingen van ongelijkheid zijn in het algemeen in tegenspraak met de andere ongelijkheden van het systeem van beperkingen), daarom is het systeem van beperkingen niet compatibel en heeft het probleem van lineaire programmering daarom geen oplossing.

Figuur: 6. Fragment van het MathCAD-document:

constructie van het domein van haalbare oplossingen voor het probleem

Antwoord: het overwogen lineaire programmeerprobleem heeft geen oplossing vanwege de incompatibiliteit van het restrictiesysteem.

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 rechte lijn).

De richting tegengesteld aan de gradiëntvector komt overeen met de richting van minimalisatie van de objectieve functie.

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 met lineaire aanvullende beperkingen die aan de variabelen worden opgelegd. Afhankelijk van het soort taken dat wordt opgelost, zijn zijn methoden onderverdeeld in universeel en speciaal. Elk lineair programmeerprobleem (LPP) kan worden opgelost met behulp van universele methoden. Bij speciale methoden wordt rekening gehouden met de eigenaardigheden van het probleemmodel, de objectieve functie en het systeem van beperkingen. Kenmerkend voor lineaire programmeerproblemen is dat de doelfunctie zijn uiterste punt 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 visueel weer te geven, kenmerken te identificeren en manieren te openen om complexere eigenschappen te bestuderen. Een lineair programmeerprobleem met twee variabelen kan altijd grafisch worden opgelost. In een driedimensionale ruimte wordt zo'n oplossing echter al ingewikkelder, en in ruimtes met een afmeting van meer dan drie is een grafische oplossing in het algemeen onmogelijk. Het geval van twee variabelen is niet van bijzonder praktisch belang, maar de overweging ervan verduidelijkt de eigenschappen van de LPP-beperkingen, leidt tot het idee van de oplossing, maakt geometrisch duidelijke manieren om op te lossen en manieren voor hun praktische implementatie.

Als de beperkingen en de doelfunctie meer dan twee variabelen bevatten, dan is het noodzakelijk (of door de methode van opeenvolgende verbetering van de oplossing) - het is universeel en kan worden gebruikt om elke LPP op te lossen. Voor sommige toegepaste lineaire programmeerproblemen, zoals, zijn speciale oplossingsmethoden ontwikkeld.

Een voorbeeld van het oplossen van het probleem

De taak

De onderneming produceert twee soorten producten: Product 1 en Product 2. Voor de vervaardiging van een eenheid van Product 1 is het nodig om kg grondstoffen van het eerste type, kg grondstoffen van het tweede type, kg grondstoffen van het derde type te besteden. Voor de vervaardiging van een eenheid van Product 2 is het nodig om kg van het eerste type, grondstoffen van het tweede type, grondstoffen van het derde type te besteden. De productie is voorzien van grondstoffen van elk type in de hoeveelheid kg, kg, kg, respectievelijk. De marktprijs van een eenheid van product 1 is duizend roebel en een eenheid van product 2 is duizend roebel.

Verplicht:

• Bouw een wiskundig model van het probleem.
• Stel een plan op voor de productie van producten dat de maximale opbrengst uit hun verkoop oplevert met behulp van een grafische methode om het lineaire programmeerprobleem op te lossen.

Om de oplossing van het lineaire programmeerprobleem zo nauwkeurig en correct mogelijk te maken, bestellen velen goedkoop een test op deze site. U kunt meer details (hoe u een aanvraag achterlaat, prijzen, voorwaarden, betalingsmethoden) lezen op de pagina Koop lineaire programmeertest ...

De oplossing van het probleem

Het model bouwen

Met en geven we het aantal vervaardigde producten van het 1e en 2e type aan.

Dan zijn de resource limieten:

Bovendien, in de zin van het probleem

De objectieve functie van het economische en wiskundige model, waarbij de opbrengst van de verkoop wordt uitgedrukt:

We krijgen het volgende economische en wiskundige model:

Bouw van de regio van haalbare oplossingen

Laten we het resulterende lineaire programmeerprobleem grafisch oplossen:

Om het gebied van haalbare oplossingen te construeren, construeren we in het coördinatensysteem de grenslijnen die overeenkomen met deze ongelijkheidsbeperkingen:

Laten we de punten zoeken waar de lijnen doorheen gaan:

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

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

Het oplossingsdomein van de corresponderende 1e ongelijkheid komt overeen met het linker halfvlak

Neem bijvoorbeeld elk punt dat niet tot de rechte lijn (2) behoort, vervang de coördinaten (0; 0) door de overeenkomstige ongelijkheid. Omdat de ongelijkheid is waar:

Neem bijvoorbeeld een punt dat niet tot de rechte lijn (3) behoort, vervang de coördinaten (0; 0) door de overeenkomstige ongelijkheid. Omdat de ongelijkheid is waar:

Het oplossingsdomein van de corresponderende 2e ongelijkheid komt overeen met het linker halfvlak

Het gebied van toegestane oplossingen is de figuur.

Een oplossing vinden 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.

Verplaats de niveaulijn in de richting van de vector zodat deze het gebied met 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 nodig om 56 artikelen van het 1e type en 64 artikelen van het 2e type te produceren. In dit geval zal de opbrengst van de verkoop van producten maximaal zijn en 5104 monetaire eenheden bedragen.

De grafische oplossingsmethode, als een probleem met twee variabelen lineaire beperkingen heeft en de doelfunctie kwadratisch is, wordt hier in detail besproken
De pagina beschrijft de oplossing van een lineair programmeerprobleem door middel van de simplex-methode, daarnaast toont het de constructie van een dubbel lineair programmeerprobleem en het vinden van de oplossing door een direct probleem op te lossen.

Transportprobleem en mogelijke methode
Het transportprobleem, het wiskundige model en de oplossingsmethoden worden in detail beschouwd - het referentieplan vinden door de minimum-elementenmethode en de optimale oplossing vinden door de potentiële methode.

Convex programmeren - grafische methode
Een voorbeeld van het oplossen van het probleem van kwadratisch convex programmeren door middel van een grafische methode wordt gepresenteerd.