Finne grafisk metode maksimum objektiv funksjon

F= 2x 1 + 3x 2 ® maks

Med restriksjoner

Løsning ved bruk av Excel-tabeller

La oss først bygge på et ark excel-løsning ulikhetssystemer.

Tenk på den første ulikheten.

La oss konstruere en grenselinje fra to punkter. Angi linjen med (L1) (eller Rad1). Koordinater X 2 teller vi etter formlene:

For å bygge, velg et punktplot

Velge data for en rett linje

Endre navnet på linjen:

Velg et diagramoppsett. Endre navnet på koordinataksene:

Rett linje (L1) på diagrammet:

Løsningen på den strenge ulikheten kan finnes ved å bruke et enkelt testpunkt som ikke tilhører linjen (L1). For eksempel ved å bruke punktet (0; 0)W(L1).

0+3×0< 18 или 0 < 18 .

Ulikheten er sann, derfor vil løsningen på ulikheten (1) være halvplanet som testpunktet ligger i (i figuren under linjen L1).

Da løser vi ulikhet (2) .

La oss konstruere grenselinjen 2 fra to punkter. Angi linjen med (L2).

Rett linje (L2) på diagrammet:

Løsningen av streng ulikhet 2 kan finnes ved å bruke det eneste testpunktet som ikke tilhører linjen (L2). For eksempel ved å bruke punktet (0; 0)W(L2).

Ved å erstatte koordinatene til punktet (0; 0), får vi ulikheten

2×0 + 0< 16 или 0 < 16 .

Ulikheten er sann, derfor vil løsningen på ulikheten (2) være halvplanet som testpunktet ligger i (i figuren under, linjen L2).

Da løser vi ulikhet (3) .

La oss konstruere en grenselinje fra to punkter. Angi linjen med (L3).

Rett linje (L3) på diagrammet:

Løsningen av streng ulikhet 2 kan finnes ved å bruke det eneste testpunktet som ikke tilhører linjen (L3). For eksempel ved å bruke punktet (0; 0)W(L3).

Ved å erstatte koordinatene til punktet (0; 0), får vi ulikheten

Ulikheten er sann, derfor vil løsningen på ulikheten (3) være halvplanet som testpunktet ligger i (i figuren under, linje L3).

Da løser vi ulikhet (4) .

La oss konstruere en grenselinje fra to punkter. Angi linjen med (L4).

Legg til data i excel-ark

Rett linje (L4) på ​​diagrammet:

Løsning av streng ulikhet 3 X 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

Ved å erstatte koordinatene til punktet (0; 0), får vi ulikheten

Ulikheten er sann, derfor vil løsningen på ulikheten (4) være halvplanet som testpunktet ligger i (til venstre for linjen L4 i figuren).

Ved å løse to ulikheter (5) og (6)

er 1. kvartal avgrenset av koordinatlinjene og .

Systemet med ulikheter er løst. Ved å løse systemet med ulikheter (1) - (6) in dette eksemplet er en konveks polygon i nedre venstre hjørne av figuren, avgrenset av linjene L1, L2, L3, L4 og koordinatlinjer og . Du kan forsikre deg om at polygonet er riktig valgt ved å erstatte et testpunkt, for eksempel (1; 1) i hver ulikhet i det opprinnelige systemet. Ved å erstatte punktet (1; 1), får vi at alle ulikheter, inkludert de naturlige begrensningene, er sanne.

Vurder nå den objektive funksjonen

F= 2x 1 + 3x 2 .

La oss bygge nivålinjer for funksjonsverdier F=0 og F=12 (numeriske verdier valgt vilkårlig). Legg til data i excel-ark

Nivålinjer på diagrammet:

La oss konstruere en vektor av retninger (eller en gradient) (2; 3). Vektorkoordinatene faller sammen med koeffisientene til objektivfunksjonen F.

La oss konstruere på flyet settet med tillatte løsninger for systemet lineære ulikheter og geometrisk finne minimumsverdi målfunksjon.

Vi bygger inn koordinatsystemet x 1 oh 2 linjer

Vi finner halvplanene bestemt av systemet. Siden ulikhetene til systemet er tilfredsstilt for et hvilket som helst punkt fra det tilsvarende halvplanet, er det tilstrekkelig å kontrollere dem for et hvilket som helst punkt. Vi bruker punktet (0;0). La oss erstatte dens koordinater med den første ulikheten i systemet. Fordi , så definerer ulikheten et halvplan som ikke inneholder punktet (0;0). På samme måte definerer vi de resterende halvplanene. Vi finner settet med gjennomførbare løsninger som generell del av de resulterende halvplanene er det skraverte området.

Vi bygger en vektor og en linje med nullnivå vinkelrett på den.

Ved å flytte linjen (5) i retning av vektoren, ser vi at maksimumspunktet for regionen vil være i punktet A i skjæringspunktet mellom linjen (3) og linjen (2). Vi finner løsningen av ligningssystemet:

Så vi fikk poenget (13;11) og.

Ved å flytte linjen (5) i vektorens retning, ser vi at minimumspunktet for regionen vil være i punktet B i skjæringspunktet mellom linjen (1) og linjen (4). Vi finner løsningen av ligningssystemet:

Så vi fikk poenget (6;6) og.

2. Et møbelfirma produserer kombinerte skap og databord. Produksjonen deres er begrenset av tilgjengeligheten av råvarer (plater av høy kvalitet, beslag) og driftstiden til maskinene som behandler dem. Hvert skap krever 5 m2 brett, for et bord - 2 m2. Beslag for $10 brukes på ett skap, og $8 på ett bord. Selskapet kan motta fra sine leverandører opptil 600 m2 brett per måned og tilbehør for $2000. For hvert skap kreves det 7 timer maskinarbeid, for et bord - 3 timer. Det er mulig å bruke kun 840 timers maskindrift per måned.

Hvor mange kombinasjonsskap og databord bør et firma produsere per måned for å maksimere fortjenesten hvis ett skap bringer inn $100 og hvert bord tjener $50?

• 1. Skriv matematisk modell problemet og løse det ved hjelp av simpleksmetoden.
• 2. Lag en matematisk modell doble oppgaver og skriv ned løsningen basert på løsningen til den opprinnelige.
• 3. Bestem graden av knapphet på ressursene som brukes og begrunn lønnsomheten til den optimale planen.
• 4. Utforsk mulighetene for å øke produksjonen ytterligere, avhengig av bruken av hver type ressurs.
• 5. Vurder muligheten for å introdusere en ny type produkt - bokhyller, hvis 1 m 2 brett og tilbehør for $ 5 brukes på produksjon av en hylle, og det kreves 0,25 timers maskindrift og fortjenesten fra salget av en hylle er $ 20.
• 1. La oss bygge en matematisk modell for dette problemet:

Angi med x 1 - volumet av produksjon av skap, og x 2 - volumet av produksjon av tabeller. La oss komponere et system av begrensninger og en målfunksjon:

Vi løser problemet ved hjelp av simpleksmetoden. La oss skrive det i kanonisk form:

La oss skrive oppgavedataene i form av en tabell:

Tabell 1

Fordi nå er alt delta Over null, da er en ytterligere økning i verdien av målfunksjonen f umulig og vi har fått en optimal plan.

Introduksjon

Det moderne stadiet av menneskelig utvikling er annerledes ved at energiens århundre erstattes av informatikkens tidsalder. Det er en intensiv introduksjon av ny teknologi på alle områder menneskelig aktivitet. Står opp reelt problem overgang til informasjonssamfunnet, hvor utvikling av utdanning bør prioriteres. Også kunnskapsstrukturen i samfunnet er i endring. Alle større verdi til praktisk liv tilegne seg grunnleggende kunnskap som bidrar til kreativ utvikling personlighet. Konstruktiviteten til ervervet kunnskap, evnen til å strukturere den i samsvar med målet er også viktig. Basert på kunnskap, nytt informasjonsressurser samfunn. Dannelse og tilegnelse av ny kunnskap bør være basert på en streng metodikk systemtilnærming, innenfor hvilken en egen plass er okkupert av modelltilnærmingen. Mulighetene for modelleringstilnærmingen er ekstremt mangfoldige både når det gjelder de formelle modellene som brukes og måtene å implementere modelleringsmetoder på. Fysisk modellering gjør det mulig å oppnå pålitelige resultater for ganske enkle systemer.

For tiden er det umulig å nevne et område med menneskelig aktivitet der modelleringsmetoder i en eller annen grad ikke vil bli brukt. Dette gjelder spesielt innen ledelse. ulike systemer, hvor de viktigste er beslutningsprosesser basert på den mottatte informasjonen.

1. Redegjørelse av problemet

minimum objektiv funksjon

Løs problemet med å finne minimum av objektivfunksjonen for systemet av begrensninger spesifisert av beslutningspolygonen i samsvar med alternativ nr. 16 i oppgaven. Beslutningspolygonet er vist i figur 1:

Figur 1 - Polygon av problemløsninger

Systemet med begrensninger og den objektive funksjonen til problemet er presentert nedenfor:

Det er nødvendig å løse problemet ved å bruke følgende metoder:

Grafisk metode for å løse LP-oppgaver;

Algebraisk metode for å løse LP-problemer;

Enkel metode for å løse LP-problemer;

Metode for å finne en gjennomførbar løsning på LP-problemer;

Løser dual LP-problemet;

Metoden for "grener og grenser" for å løse heltalls LP-problemer;

Gomorys metode for å løse heltalls LP-problemer;

Balash-metode for å løse boolske LP-problemer.

Sammenlign resultatene av løsningen ved hjelp av ulike metoder for å trekke passende konklusjoner om arbeidet.

2. Grafisk løsning lineære programmeringsproblemer

Den grafiske metoden for å løse lineære programmeringsproblemer brukes i tilfeller hvor antallet ukjente ikke overstiger tre. Praktisk for kvalitativ forskning egenskaper til løsninger og brukes sammen med andre metoder (algebraisk, gren og bundet, etc.). Ideen til metoden er basert på den grafiske løsningen av et system med lineære ulikheter.

Ris. 2 Grafisk løsning av LP-problemet

Lavt punkt

Ligning av en rett linje som går gjennom to punkter A1 og A2:

AB: (0;1); (3;3)

Sol: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

med restriksjoner:

Løse et lineært programmeringsproblem ved hjelp av den algebraiske simpleksmetoden

Anvendelsen av den algebraiske metoden for å løse problemet krever en generalisering av representasjonen av LP-problemet. Det opprinnelige systemet med begrensninger gitt i form av ulikheter konverteres til standardnotasjonen når begrensningene er gitt i form av likheter. Konvertering av begrensningssystemet til standard skjema inkluderer følgende trinn:

Transformer ulikheter på en slik måte at variabler og frie medlemmer er til venstre, og 0 til høyre, dvs. at venstre side er større enn eller lik null;

Introduser tilleggsvariabler, hvis antall er lik antall ulikheter i restriksjonssystemet;

Kommer inn ytterligere restriksjoner på ikke-negativiteten til de adderte variablene, bytt ut tegnene på ulikheter med tegn på strenge likheter.

Når du skal løse LP-problemet algebraisk metode Det legges til en betingelse: den objektive funksjonen må ha en tendens til et minimum. Hvis denne betingelsen ikke er oppfylt, er det nødvendig å transformere objektivfunksjonen på riktig måte (multipliser med -1) og løse minimeringsproblemet. Etter at løsningen er funnet, erstatter du verdiene til variablene i den opprinnelige funksjonen og beregner verdien.

Løsningen av problemet ved hjelp av den algebraiske metoden anses som optimal når verdiene til alle grunnleggende variabler er ikke-negative, og koeffisientene til frie variabler i objektivfunksjonsligningen er også ikke-negative. Hvis disse betingelsene ikke er oppfylt, er det nødvendig å transformere systemet med ulikheter ved å uttrykke noen variabler i form av andre (endre frie og grunnleggende variabler) for å oppnå begrensningene ovenfor. Verdien av alle frie variabler antas å være null.

Den algebraiske metoden for å løse lineære programmeringsproblemer er en av de mest effektive metoder når du løser problemer av små dimensjoner manuelt. krever ikke et stort antall aritmetiske beregninger. Maskinimplementeringen av denne metoden er mer komplisert enn for eksempel for simpleksmetoden, fordi Algoritmen for å løse den algebraiske metoden er til en viss grad heuristisk og effektiviteten til løsningen avhenger i stor grad av personlig erfaring.

frie variabler

St. lane - legge til. sett

Betingelsene for ikke-negativitet er oppfylt, derfor har vi funnet optimal løsning.

3. Løse et lineært programmeringsproblem ved hjelp av en simplekstabell

Løsning: La oss bringe problemet til et standardskjema for å løse ved hjelp av en simplekstabell.

Vi reduserer alle likninger i systemet til formen:

Vi bygger en simplekstabell:

PÅ øverste hjørne for hver celle i tabellen legger vi inn koeffisientene fra ligningssystemet;

Vi velger det maksimale positive elementet i rad F, bortsett fra at dette vil være den generelle kolonnen;

For å finne det generelle elementet bygger vi en relasjon for alle positive. 3/3; 9/1;- minimumsforhold i linje x3. Derfor - generell streng og =3 - generelt element.

Vi finner =1/=1/3. Vi bringer inn det nedre hjørnet av cellen, der det generelle elementet er plassert;

I alle ufylte nedre hjørner av den generelle linjen legger vi inn produktet av verdien i øvre hjørne av cellen ved;

Velg de øvre hjørnene på den generelle linjen;

I alle nedre hjørner av den generelle kolonnen legger vi inn produktet av verdien i øvre hjørne ved - og velger de resulterende verdiene;

De resterende cellene i tabellen fylles ut som produkter av de tilsvarende valgte elementene;

Deretter bygger vi en ny tabell der betegnelsene til cellene til elementene i den generelle kolonnen og raden er reversert (x2 og x3);

I det øvre hjørnet av den tidligere generelle raden og kolonnen er verdiene som tidligere var i det nedre hjørnet skrevet;

Summen av verdiene til de øvre og nedre hjørnene av disse cellene i den forrige tabellen er skrevet i det øvre hjørnet av de gjenværende cellene

4. Løse det lineære programmeringsproblemet ved å finne en gjennomførbar løsning

La et system med lineære algebraiske ligninger gis:

Vi kan anta at alt, ellers multipliserer vi tilsvarende ligning med -1.

Vi introduserer hjelpevariabler:

Vi introduserer også en hjelpefunksjon

Vi vil minimere systemet under begrensninger (2) og betingelser.

REGEL FOR Å FINNE EN MULIG LØSNING: For å finne en gjennomførbar løsning på system (1), minimerer vi form (3) under begrensninger (2), som frie ukjente tar vi xj som grunnleggende.

Når du løser et problem ved hjelp av simpleksmetoden, kan to tilfeller oppstå:

min f=0, da må all i være lik null. Og de resulterende xj-verdiene vil være akseptabel løsning systemer (1).

min f>0, dvs. det originale systemet har ikke en gyldig løsning.

Kildesystem:

Betingelsen for problemet til forrige emne brukes.

La oss legge til flere variabler:

En tillatt løsning på det opprinnelige problemet er funnet: x1 = 3, x2 = 3, F = -12. Basert på den oppnådde gjennomførbare løsningen finner vi den optimale løsningen på det opprinnelige problemet ved hjelp av simpleksmetoden. For å gjøre dette vil vi bygge en ny simplekstabell fra tabellen ovenfor ved å slette raden og raden med målfunksjonen til hjelpeoppgaven:

Ved å analysere den konstruerte simplekstabellen ser vi at den optimale løsningen for det opprinnelige problemet allerede er funnet (elementene i raden som tilsvarer objektivfunksjonen er negative). Dermed faller den gjennomførbare løsningen som ble funnet når du løser hjelpeproblemet sammen med den optimale løsningen av det opprinnelige problemet:

6. Det doble problemet med lineær programmering

Det innledende systemet med begrensninger og den objektive funksjonen til problemet er vist i figuren nedenfor.

med restriksjoner:

Løsning: Vi bringer systemet med restriksjoner til standardskjemaet:

Oppgaven dual til denne vil se slik ut:

Det doble problemet løses ved simpleksmetoden.

La oss transformere objektivfunksjonen slik at minimeringsproblemet løses og skrive ned systemet av begrensninger i standardformen for løsning med simpleksmetoden.

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

La oss konstruere det innledende simpleks-tableauet for å løse det doble LP-problemet.

Det andre trinnet i simpleksmetoden

Så i det tredje trinnet i simpleksmetoden ble den optimale løsningen av minimeringsproblemet funnet med følgende resultater: y2 = -7 /8, y1 = -11/8, Ф = 12. For å finne verdien av den objektive funksjonen til det doble problemet, erstatter vi de funnet verdiene til de grunnleggende og frie variablene i maksimeringsfunksjonen:

Фmaks = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Siden verdien av den objektive funksjonen til de direkte og doble problemene er den samme, er løsningen på det direkte problemet funnet og er lik 12.

Fmin \u003d Fmax \u003d -12

7. Løse problemet med heltalls lineær programmering ved å bruke "grener og grenser"-metoden

La oss transformere originalt problem på en slik måte at heltallsbetingelsen ikke tilfredsstilles ved løsning med konvensjonelle metoder.

Den innledende polygonen av løsninger på et heltallsprogrammeringsproblem.

For det transformerte løsningspolygonet konstruerer vi nytt system begrensninger.

Vi skriver ned systemet av begrensninger i form av likheter, for å løse etter den algebraiske metoden.

Som et resultat av løsningen ble den optimale oppgaveplanen funnet: x1 = 9/4, x2 = 5/2, F = -41/4. Denne løsningen oppfyller ikke integritetsbetingelsen satt i problemet. Vi deler det opprinnelige løsningspolygonet i to områder, ekskluderer område 3 fra det

Endret polygon av problemløsninger

La oss komponere nye systemer med restriksjoner for de dannede områdene i løsningspolygonet. Det venstre området er en firkant (trapes). Begrensningssystemet for venstre område av løsningspolygonet er presentert nedenfor.

Restriksjonssystem for venstre område

Det høyre området representerer punkt C.

Systemet med begrensninger for riktig beslutningsområde er presentert nedenfor.

De nye begrensningssystemene er to underordnede problemer som må løses uavhengig av hverandre. La oss løse problemet med heltallsprogrammering for venstre område av løsningspolygonet.

Som et resultat av løsningen ble den optimale oppgaveplanen funnet: x1 = 3, x2 = 3, F = -12. Denne planen tilfredsstiller betingelsen til heltallsvariabler i oppgaven og kan tas som den optimale referanseplanen for det opprinnelige heltalls lineære programmeringsproblemet. Det gir ingen mening å gjennomføre løsningen for riktig løsningsregion. Figuren nedenfor viser fremdriften for å løse et heltalls lineært programmeringsproblem i form av et tre.

Forløpet med å løse et heltalls lineært programmeringsproblem ved hjelp av Gomory-metoden.

I mange praktiske applikasjoner er problemet med heltallsprogrammering av stor interesse, der et system med lineære ulikheter og en lineær form er gitt

Det kreves å finne en heltallsløsning av system (1) som minimerer objektivfunksjonen F, og alle koeffisientene er heltall.

En av metodene for å løse heltallsprogrammeringsproblemet ble foreslått av Gomory. Ideen med metoden er å bruke metoder for kontinuerlig lineær programmering, spesielt simpleksmetoden.

1) Ved bruk av simpleksmetoden bestemmes løsningen på oppgave (1), (2), hvor kravet om at løsningen skal være heltall fjernes; hvis løsningen viser seg å være heltall, vil den ønskede løsningen på heltallsproblemet også bli funnet;

2) Ellers, hvis noen koordinater ikke er et heltall, blir den oppnådde løsningen av problemet sjekket for muligheten for eksistensen av en heltallsløsning (tilstedeværelsen av heltallspunkter i et tillatt polyeder):

hvis i en linje med et brøkfritt medlem viser alle andre koeffisienter seg å være heltall, så er det ingen heltall, punkter i et tillatt polyeder, og problemet med heltallsprogrammering har ingen løsning;

Ellers introduseres en ekstra lineær begrensning, som avskjærer fra det tillatte polyederet en del som er lite lovende for å finne en løsning på et heltallsprogrammeringsproblem;

3) For å konstruere en ekstra lineær begrensning, velg den l-te raden med et brøkfritt medlem og skriv ned den ekstra begrensningen

hvor og er henholdsvis brøkdelene av koeffisientene og fri

medlem. La oss introdusere en hjelpevariabel i begrensning (3):

La oss bestemme koeffisientene og inkluderes i begrensningen (4):

hvor og er de nærmeste nedre heltallene for henholdsvis og.

Gomory beviste at et begrenset antall slike trinn fører til et lineært programmeringsproblem hvis løsning er heltall og derfor den ønskede.

Løsning: Vi reduserer systemet med lineære begrensninger og målfunksjonen til den kanoniske formen:

La oss bestemme den optimale løsningen av systemet med lineære begrensninger, midlertidig forkaste heltallstilstanden. Vi bruker simpleksmetoden til dette. Tabellene nedenfor presenterer sekvensielt den første løsningen av problemet, og transformasjonene av den opprinnelige tabellen er gitt for å oppnå den optimale løsningen på problemet:

Løse boolske LP-problemer ved hjelp av Balash-metoden.

Lag din egen variant for problemet med heltalls lineær programmering med boolske variabler, ta hensyn til følgende regler: problemet bruker minst 5 variabler, minst 4 begrensninger, begrensningskoeffisientene og objektivfunksjonen velges vilkårlig, men i en slik måte at begrensningssystemet er kompatibelt. Oppgaven er å løse ZCLP med boolske variabler ved hjelp av Balash-algoritmen og bestemme reduksjonen i beregningskompleksitet i forhold til å løse problemet ved uttømmende søk.

Gjennomføring av restriksjoner

F-verdi

Filterbegrensning:

Beregning Reduksjon Bestemmelse

Løsningen av problemet ved den uttømmende søkemetoden er 6*25=192 beregnede uttrykk. Løsningen av problemet ved Balash-metoden er 3*6+(25-3)=47 beregnede uttrykk. Den totale reduksjonen i kompleksiteten til beregninger i forhold til å løse problemet ved den uttømmende søkemetoden er.

Konklusjon

Prosessen med å designe informasjonssystemer som implementerer ny informasjonsteknologi blir stadig forbedret. Stadig mer komplekse systemer blir i fokus for systemingeniører, noe som gjør det vanskelig å bruke fysiske modeller og øker betydningen av matematiske modeller og datasimulering av systemer. Maskinmodellering har blitt et effektivt verktøy for forskning og design av komplekse systemer. Relevansen til matematiske modeller øker stadig på grunn av deres fleksibilitet, tilstrekkelighet til reelle prosesser, lave kostnader for implementering på grunnlag av moderne PC-er. Flere og flere muligheter gis til brukeren, det vil si en spesialist på modellering av systemer ved hjelp av datateknologi. Bruken av modellering er spesielt effektiv i de tidlige stadiene av design av automatiserte systemer, når kostnadene ved feilaktige beslutninger er størst.

Moderne dataverktøy har gjort det mulig å øke kompleksiteten til modellene som brukes i studiet av systemer betydelig, det har blitt mulig å bygge kombinerte, analytiske og simuleringsmodeller som tar hensyn til hele variasjonen av faktorer som finner sted i virkelige systemer, dvs. bruk av modeller som er mer passende for fenomenene som studeres.

Litteratur:

1. Lyashchenko I.N. Lineær og ikke-lineær programmering / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. Shor. - K .: "Higher School", 1975, 372 s.

2. Retningslinjer for gjennomføring av emneprosjektet i disiplinen "Anvendt matematikk" for studenter av spesialiteten "Datasystemer og nettverk" heltids- og deltidsutdanningsformer / Sammensatt av: I.A. Balakireva, A.V. Skatkov - Sevastopol: SevNTU Publishing House , 2003. - 15 s.

3. Retningslinjer for studiet av faget "Anvendt matematikk", avsnitt "Metoder for globalt søk og endimensjonal minimering" / Komp. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: SevGTU Publishing House, 2000. - 31s.

4. Retningslinjer for å studere disiplinen "Anvendt matematikk" for studenter av spesialiteten "Datasystemer og nettverk" Seksjonen "Løse integer lineære programmeringsproblemer" for heltids- og korrespondanseutdanningsformer / Sammensatt av: I.A. Balakireva, A.V. Skatkov - Sevastopol : SevNTU Publishing House, 2000. - 13 s.

5. Akulich I.L. Matematisk programmering i eksempler og oppgaver:

6. Pros. stønad til studentøkonomi. spesialist. universiteter.-M.: Høyere. skole, 1986.- 319s., ill.

7. Andronov S.A. Optimale designmetoder: Forelesningstekst / SPbGUAP. SPb., 2001. 169 s.: ill.

Lignende dokumenter

Algoritme for å løse lineære programmeringsproblemer ved simpleksmetoden. Konstruksjon av en matematisk modell av et lineært programmeringsproblem. Løse et lineært programmeringsproblem i Excel. Finne profitt og optimal produksjonsplan.

semesteroppgave, lagt til 21.03.2012


Grafisk problemløsning. Å tegne en matematisk modell. Bestemme maksimalverdien til objektivfunksjonen. Løsning ved en simpleksmetode med en kunstig basis av et kanonisk lineært programmeringsproblem. Kontroll av optimaliteten til løsningen.

test, lagt til 04.05.2016


Teoretisk grunnlag for lineær programmering. Problemer med lineær programmering, løsningsmetoder. Analyse av den optimale løsningen. Løsning av et lineært programmeringsproblem med én indeks. Erklæring om problemet og dataregistrering. Modellbygging og løsningstrinn.

semesteroppgave, lagt til 12.09.2008


Konstruksjon av en matematisk modell. Valg, begrunnelse og beskrivelse av metoden for å løse det direkte problemet med lineær programmering ved simpleksmetoden, ved bruk av en simplekstabell. Formulering og løsning av et dobbeltproblem. Analyse av modellen for sensitivitet.

semesteroppgave, lagt til 31.10.2014


Bygge en matematisk modell for å maksimere fortjenesten til bedriften, en grafisk løsning på problemet. Problemløsning ved å bruke SOLVER-tillegget. Analyse av endringer i ressursreserver. Bestemmelse av grensene for endring i koeffisientene til den objektive funksjonen.

semesteroppgave, lagt til 17.12.2014


Matematisk programmering. Lineær programmering. Problemer med lineær programmering. Grafisk metode for å løse et lineært programmeringsproblem. Økonomisk formulering av problemet med lineær programmering. Konstruksjon av en matematisk modell.

semesteroppgave, lagt til 13.10.2008


Løse et lineært programmeringsproblem ved hjelp av en grafisk metode, dets verifisering i MS Excel. Analyse av den interne strukturen til problemløsningen i programmet. Optimalisering av produksjonsplan. Løsning av problemet ved simpleksmetoden. Flerkanals køsystem.

test, lagt til 05.02.2012


Løse problemet med lineær programmering ved simpleksmetoden: å sette problemet, bygge en økonomisk og matematisk modell. Løsning av transportproblemet ved hjelp av potensialmetoden: konstruksjon av den første referanseplanen, bestemmelse av dens optimale verdi.

test, lagt til 04.11.2012


Uttalelse av problemet med ikke-lineær programmering. Bestemmelse av stasjonære punkter og deres type. Konstruksjon av nivålinjer, en tredimensjonal graf av objektivfunksjonen og begrensninger. Grafisk og analytisk løsning av problemet. Brukerhåndbok og algoritmeskjema.

semesteroppgave, lagt til 17.12.2012


Analyse av løsningen av et lineært programmeringsproblem. Enkel metode ved hjelp av simplekstabeller. Modellering og løsning av LP-problemer på en datamaskin. Økonomisk tolkning av den optimale løsningen av problemet. Matematisk formulering av transportproblemet.

TEMA: LINEÆR PROGRAMMERING

OPPGAVE 2.A. Løse et lineært programmeringsproblem med en grafisk metode

Merk følgende!

Dette er en INTRODUKSJONVERSJON av verk nr. 2073, prisen på originalen er 200 rubler. Designet i Microsoft Word.

Innbetaling. Kontakter.

Alternativ 7. Finn maksimums- og minimumsverdienelineær funksjonФ \u003d 2x 1 - 2 x 2med restriksjoner: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 < 2;

x 1 + 2 x 2 < 10;

x i ≥ 0, i = 1,2.

Løsning:

Ved å erstatte betingede tegn på ulikheter med tegn på likhet, får vi et system av ligninger x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Vi konstruerer rette linjer i henhold til disse ligningene, og deretter, i samsvar med tegnene på ulikheter, velger vi halvplanene og får deres felles del - regionen med tillatte løsninger av ODE - firkantet MNPQ.

Minimumsverdien til funksjonen

tsii - ved punktet M (2; 2)

Ф min = 2 2 - 2 2 = 0.

Maksimalverdien nås ved punkt N (10; 0),

Ф maks \u003d 2 10 - 2 0 \u003d 20.

Alternativ 8. Finn maksimums- og minimumsverdiene

lineær funksjon Ф \u003d x 1 + x 2

med restriksjoner: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1,2.

Løsning:

Ved å erstatte betingede tegn på ulikheter med tegn på likhet, får vi et system av ligninger x1 - 4 x2 = 4;

3 x1 - x2 = 0;

Vi konstruerer rette linjer i henhold til disse ligningene, og deretter, i samsvar med tegnene på ulikheter, velger vi halvplan og oppnår deres felles del - regionen med tillatte løsninger av ODE - en ubegrenset polygon MNPQ.

Minimumsverdien til funksjonen

sjoner - på en rett linje NP, for eksempel

ved punktet Р(4; 0)

Ф min = 4 + 0 = 4.

ODE er ikke begrenset ovenfra, derfor er Ф max = + ∞.

Alternativ 10. Finn maksimums- og minimumsverdiene

lineær funksjon Ф \u003d 2 x 1 - 3 x 2

med restriksjoner: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 < 16;

x 2 < 5;

x i ≥ 0, i = 1,2.

Ved å erstatte tegn på ulikheter betinget med tegn på likhet, får vi et ligningssystem

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Vi konstruerer rette linjer i henhold til disse ligningene, og deretter, i samsvar med tegnene på ulikheter, velger vi halvplan og oppnår deres felles del - regionen med tillatte løsninger av ODE - polygonen MNPQRS.

Vi konstruerer vektoren Г(2; -3) og tegner gjennom origo nivålinje- rett.

Vi flytter nivålinjen i retning, mens verdien av F øker. Ved punktet S(7; 0) når objektivfunksjonen sitt maksimum Ф max =2·7–3·0= = 14. Vi flytter nivålinjen i retningen, mens verdien av Ф avtar. Minimumsverdien til funksjonen er ved punktet N(0; 5)

Ф min = 2 0 – 3 5 = –15.

OPPGAVE 2.B. Løse et lineært programmeringsproblem

analytisk simpleksmetode

Alternativ 7. Minimer målfunksjonen Ф \u003d x 1 - x 2 + x 3 + x 4 + x 5 - x 6

under restriksjoner: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 - 4 x 3 + 2 x 6 \u003d 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Løsning:

Antall ukjente n=6, antall ligninger m=3. Derfor kan r = n-m = 3 ukjente tas som frie. La oss velge x 1 , x 3 og x 6 .

Vi uttrykker de grunnleggende variablene x 2 , x 4 og x 5 i form av frie og bringer systemet til enhetsgrunnlaget

x 2 \u003d 2 - 3 x 1 + 4 x 3 - 2 x 6

x 4 \u003d 9 - x 1 - 6 x 6 (*)

x 5 \u003d 6 - x 1 - 2 x 3 - 2 x 6

Objektfunksjonen vil se slik ut:

Ф \u003d x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 - x 1 - 6 x 6 +6 - x 1 - 2 x 3 - 2 x 6 - x 6 =

13 + 2 x 1 - 5 x 3 - 7 x 6

La oss sette x 1 \u003d x 3 \u003d x 6 \u003d 0, mens de grunnleggende variablene vil ta på seg verdiene x 2 \u003d 2; x 4 \u003d 9; x 5 \u003d 6, det vil si den første mulige løsningen (0; 2; 0; 9; 6; 0), objektiv funksjon Ф 1 \u003d 13.

Variablene x 3 og x 6 er inkludert i objektivfunksjonen med negative koeffisienter, derfor vil verdien av Ф reduseres med en økning i verdiene deres. Ta for eksempel x 6 . Fra den første ligningen til systemet (*) kan det sees at en økning i verdien av x 6 er mulig opp til x 6 \u003d 1 (så lenge x 2 ³ 0). I dette tilfellet beholder x 1 og x 3 verdier lik null. Nå, som grunnleggende variabler, tar vi x 4, x 5, x 6, som gratis - x 1, x 2, x 3. La oss uttrykke de nye grunnleggende variablene i form av de nye frie. Få

x 6 \u003d 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3

x 4 \u003d 3 + 8 x 1 + 3 x 2 - 12 x 3

x 5 \u003d 4 + 2 x 1 + x 2 - 6 x 3

Ф \u003d 6 + 25/2 x 1 + 7/2 x 2 - 19 x 3

Tilordne nullverdier til frie variabler, det vil si x 1 \u003d x 2 \u003d x 3 \u003d 0, mens x 6 \u003d 1, x 4 \u003d 3, x 5 \u003d 4, det vil si den tredje gyldig løsning (0; 0; 0; 3; 4; 1). I dette tilfellet, Ф 3 \u003d 6.

Variabelen x 3 inngår i objektivfunksjonen med negativ koeffisient, derfor vil en økning i x 3 i forhold til null føre til en nedgang i F. Fra 2. ligning kan man se at x 3 kan øke opp til 1/ 4, fra 3. ligning - opp til 2/3 . Den andre ligningen er mer kritisk. Vi oversetter variabelen x 3 til antall grunnleggende, x 4 til antall frie.

Nå tar vi x 1 , x 2 og x 4 som nye frie variabler. La oss uttrykke nye grunnleggende variabler x 3 , x 5 , x 6 i form av dem. La oss få systemet

x 3 \u003d 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 \u003d 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Den objektive funksjonen vil ta formen

Ф \u003d 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Variablene x 1 og x 2 er inkludert i objektivfunksjonen med negative koeffisienter, derfor vil verdien av Ф reduseres med en økning i verdiene deres. Ta for eksempel x 2 . Fra den andre ligningen av systemet kan det sees at en økning i verdien av x 2 er mulig opp til x 2 \u003d 5 (så lenge x 5 ³ 0). I dette tilfellet beholder x 1 og x 4 nullverdier, verdiene til andre variabler er lik x 3 = 3/2; x 5 \u003d 0, x 6 \u003d 3/2, det vil si den fjerde gyldige løsningen (0; 5; 3/2; 0; 0; 3/2). I dette tilfellet, Ф 4 \u003d 5/4.

Nå tar vi x 1 , x 4 og x 5 som nye frie variabler. La oss uttrykke nye grunnleggende variabler x 2 , x 3 , x 6 i form av dem. La oss få systemet

x 2 \u003d 5 - 4 x 1 + x 4 - 2 x 5

x 3 \u003d 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Den objektive funksjonen vil ta formen

F \u003d - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

Koeffisientene for begge variablene i uttrykket for Ф er positive, derfor er en ytterligere reduksjon i verdien av Ф umulig.

Det vil si at minimumsverdien på Ф min = - 5, den siste mulige løsningen (0; 5; 3/2; 0; 0; 3/2) er optimal.

Alternativ 8. Maksimer målfunksjonen Ф = 4 x 5 + 2 x 6

med restriksjoner: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 \u003d 30;

x 3 + x 5 - 2 x 6 \u003d 6;

2 x 4 + 3 x 5 - 2 x 6 \u003d 18;

Løsning:

Antall ligninger er 4, antall ukjente er 6. Derfor kan r = n - m = 6 - 4 = 2 variabler velges som frie, 4 variabler som grunnleggende. Vi velger x 5 og x 6 som frie, x 1, x 2, x 3, x 4 som grunnleggende. Vi uttrykker de grunnleggende variablene i form av de frie og reduserer likningssystemet til enhetsgrunnlaget

x 1 \u003d 12 - x 5 - x 6;

x 2 \u003d 30 - 5 x 5 + x 6;

x 3 \u003d 6 - x 5 + 2 x 6;

x 4 \u003d 9 - 3/2 x 5 + x 6;

Vi skriver objektivfunksjonen på formen Ф = 4 x 5 + 2 x 6 . Vi tildeler nullverdier til frie variabler x 5 = x 6 = 0. I dette tilfellet vil de grunnleggende variablene anta verdiene x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 , det vil si at vi får den første gjennomførbare løsningen (12, 30 , 6, 9, 0,) og Ф 1 = 0.

Begge de frie variablene går inn i målfunksjonen med positive koeffisienter, det vil si at det er mulig med en ytterligere økning i F. La oss for eksempel oversette x 6 til antall grunnleggende. Ligning (1) viser at x 1 = 0 ved x 5 = 12, i (2) ÷ (4) x 6 går inn med positive koeffisienter. La oss gå videre til et nytt grunnlag: grunnleggende variabler - x 6, x 2, x 3, x 4, fri - x 1, x 5. La oss uttrykke de nye grunnleggende variablene gjennom nye frie

x 6 \u003d 12 - x 1 - x 5;

x 2 \u003d 42 - x 1 - 6 x 5;

x 3 \u003d 30 - 2 x 1 - 3 x 5;

x 4 \u003d 21 - x 1 - 5/2 x 5;

Objektfunksjonen vil ha formen Ф = 24 - 2 x 1 + 2 x 5 ;

Vi tildeler nullverdier til frie variabler x 1 = x 5 = 0. I dette tilfellet vil de grunnleggende variablene anta verdiene x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 , det vil si at vi får den andre mulige løsningen (0, 42, 30, 21, 0, 12) og Ф 2 = 24.

Målfunksjonen x 5 går inn med en positiv koeffisient, det vil si at en ytterligere økning i F er mulig. La oss gå videre til et nytt grunnlag: grunnleggende variabler - x 6, x 5, x 3, x 4, frie - x 1 , x 2. La oss uttrykke nye grunnleggende variabler gjennom nye gratis

x 6 \u003d 5 - 5/6 x 1 + 1/6 x 2;

x 5 \u003d 7 - 1/6 x 1 - 1/6 x 2;

x 3 \u003d 9 - 3/2 x 1 + 1/2 x 2;

x 4 \u003d 7/2 - 7/12 x 1 + 5/12 x 5;

Objektfunksjonen vil ha formen Ф = 38 - 7/2 x 1 - 1/3 x 2;

Tilordne nullverdier x 1 = x 2 = 0 til frie variabler. I dette tilfellet vil de grunnleggende variablene få verdiene x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7/ 2, det vil si at vi får den tredje mulige løsningen X 3 = (0, 0, 9, 7/2, 7, 5) og Ф 3 = 38.

Begge variablene går inn i målfunksjonen med negative koeffisienter, det vil si at en ytterligere økning i Ф er umulig.

Derfor er den siste mulige løsningen optimal, det vil si Х opt = (0, 0, 9, 7/2, 7, 5) og Ф max = 38.

Alternativ 10. Maksimer målfunksjonen Ф \u003d x 2 + x 3

under restriksjoner: x 1 - x 2 + x 3 \u003d 1,

x 2 - 2 x 3 + x 4 \u003d 2.

Løsning:

Ligningssystemet - begrensninger er konsistent, siden rekkene til matrisen til ligningssystemet og den utvidede matrisen er de samme og lik 2. Derfor kan to variable tas som frie, to andre variabler - grunnleggende - kan være uttrykt lineært i form av to frie.

La oss ta x 2 og x 3 som frie variabler. Da vil variablene x 1 og x 2 være de grunnleggende, som vi vil uttrykke i form av fri.

x 1 \u003d 1 + x 2 - x 3; (*)

x 4 \u003d 2 - x 2 + 2 x 3;

Målfunksjonen er allerede uttrykt i form av x 2 og x 3 , det vil si Ф = x 2 + x 3 .

Ved x 2 \u003d 0 og x 3 \u003d 0 vil de grunnleggende variablene være lik x 1 \u003d 1, x 4 \u003d 2.

Vi har den første mulige løsningen X 1 = (1, 0, 0, 2), mens Ф 1 = 0.

En økning i Ф er mulig med en økning, for eksempel i verdien av x 3, som er inkludert i uttrykket for Ф med en positiv koeffisient (x 2 forblir lik null). I den første ligningen av systemet (*) kan det sees at x 3 kan økes til 1 (fra betingelsen x 1 ³0), det vil si at denne ligningen pålegger en begrensning på å øke verdien av x 3. Den første ligningen i systemet (*) løses. På grunnlag av denne ligningen går vi over til et nytt grunnlag, og endrer x 1 og x 3 steder. Nå vil de grunnleggende variablene være x 3 og x 4, fri - x 1 og x 2. Vi uttrykker nå x 3 og x 4 i form av x 1 og x 2.

Vi får: x 3 \u003d 1 - x 1 + x 2; (**)

x 4 \u003d 4 - 2 x 1 + x 2;

Ф \u003d x 2 + 1 - x 1 + x 2 \u003d 1 - x 1 + 2 x 2

Ved å likestille de frie variablene med null, får vi den andre tillatte grunnløsningen X 2 = (0; 0; 1; 4), der Ф 2 =1.

En økning i F er mulig med en økning i x 2. Økningen i x 2, å dømme etter det siste likningssystemet (**), er ikke begrenset. Derfor vil Ф ta på seg alle store positive verdier, det vil si Ф max = + ¥.

Så objektivfunksjonen Ф er ikke avgrenset ovenfra, så det er ingen optimal løsning.

OPPGAVE 2.D. Skriv en oppgave dual til den gitte.

opprinnelig oppgave.

Alternativ 7. Maksimer målfunksjonen Ф = 2× x 1 - x 4

med restriksjoner: x 1 + x 2 \u003d 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Løsning:

Vi bringer systemet med begrensninger til en enkelt, for eksempel kanonisk form ved å introdusere tilleggsvariabler i 2. og 3. likning

x 1 + x 2 = 20,

x 2 + 2 × x 4 - x 5 \u003d 5,

- x 1 + x 2 + x 3 + x 6 \u003d 8.

Vi fikk et asymmetrisk problem av den andre typen. Det doble problemet vil se slik ut:

Minimer målfunksjonen F = 20 × y 1 + 5 × y 2 + 8 × y 3

for y 1 - y 3 ≥ 2,

y1 + y2 + y3 ≥ 0,

y 3 ≥ 0,

2× y2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Alternativ 8. Maksimer målfunksjonen Ф \u003d x 2 - x 4 - 3× x 5

med restriksjoner: x 1 + 2× x 2 - x 4 + x 5 \u003d 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (Jeg = 1, 6)

Løsning:

Vi har det opprinnelige maksimeringsproblemet med et system av begrensninger i form av ligninger, det vil si at et par doble problemer har en asymmetrisk form av den andre typen, hvis matematiske modell i matriseform har formen:

Opprinnelig problem: Dobbelt problem:

F = C × X maks F = B T × Ymin

hos A × X \u003d B ved A T × Y ≥ C T

I den opprinnelige oppgaven har matriseraden med koeffisienter for variabler i objektivfunksjonen formen С = (0; 1; 0; -1; -3; 0),

kolonnematrisen av frie ledd og matrisen av koeffisienter for variabler i begrensningssystemet har formen

B \u003d 2, A \u003d 0 - 4 1 2 -1 0

Finn den transponerte matrisen av koeffisienter, matriseraden med koeffisienter for variabler i objektivfunksjonen og matrisekolonnen av frie medlemmer

0 1 0 0 V T \u003d (1; 2; 5)

A T = -1 2 0 C T = -1

Det doble problemet kan skrives i følgende form:

finn minimumsverdien til objektivfunksjonen F = y 1 + 2 × y 2 + 5 × y 3

under restriksjoner y 1 ≥ 0,

2× y 1-4 × y 2 + 3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Alternativ 10. Minimer funksjonen Ф = x 1 + x 2 + x 3

begrenset: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Løsning:

Vi har det opprinnelige minimeringsproblemet med et system av begrensninger i form av ulikheter, det vil si at et par doble problemer har en symmetrisk form av den tredje typen, hvis matematiske modell i matriseform har formen:

Opprinnelig problem Dobbelt problem

F = C × X min F \u003d B T × Ymax

hos A × X ≥ B på A T × Y ≤ C T

X ≥ 0 Y ≥ 0

I den opprinnelige oppgaven har matrise-raden av koeffisienter for variabler i objektivfunksjonen, matrise-kolonnen av frie ledd og matrisen av koeffisienter for variabler i begrensningssystemet formen

C \u003d (1; 1; 1), B \u003d 3, A \u003d 6 4 5

La oss finne matrisene til det doble problemet

B T = (2; 3; 4) C T = 3 A T = 9 4 2

Det doble problemet er formulert slik:

Maksimer objektivfunksjonen F = 2y 1 + 3y 2 + 4y 3

under restriksjoner 3 × y 1 + 6 × y 2 + 8 × y 3 ≤ 1,

9× y 1 + 4 × y 2 + 2 × y 3 ≤ 1,

7× y 1 + 5 × y 2 + 4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

OPPGAVE 2.C. Løse et lineært programmeringsproblem ved hjelp av simplekstabeller.

Alternativ 7. Maksimer objektivfunksjonen Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

under restriksjoner: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Løsning:

Vi reduserer systemet med begrensninger til den kanoniske formen

2 x 1 + 3 x 2 - x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

Vi har et system med 3 ligninger med 7 ukjente. Vi velger x 1 , z 1 , z 3 som grunnleggende 3 variabler, x 2 , x 3 , x 4 , z 2 som frie, vi uttrykker grunnvariablene gjennom dem.

Fra (2) har vi x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Vikar i (1) og (3), får vi

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 \u003d 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 \u003d 2.

Lag en simplekstabell

I-iterasjonstabell 1

Grunnleggende AC	Frihet. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z1	2	0	7	-11		1	2	0	1/ 4	1/8
z3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 \u003d (1; 0; 0; 0; 2; 0; 4) F 1 \u003d 2.

II iterasjon Tabell 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 \u003d (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 \u003d 4.

III iterasjon Tabell 3

x 1	1	1	— 6	0	0		-1	— 1		1/2
x4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 \u003d (1; 0; 6/7; 10/7; 0; 0; 0) Ф 3 \u003d 52/7.

IV iterasjon Tabell 4

z1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X 4 \u003d (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 \u003d 149/14.

Det er ingen negative tall i indeksraden i den siste tabellen, det vil si i uttrykket for målfunksjonen, alle Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Svar: Ф maks = 149/14,

optimal løsning (0; 0; 25/14; 37/14; 1/2; 0; 0)

Alternativ 8. Minimer målfunksjonen Ф = 5 x 1 - x 3

under restriksjoner: x 1 + x 2 + 2 x 3 - x 4 \u003d 3,

x 2 + 2 x 4 \u003d 1,

Løsning:

Antall variabler er 4, rangeringen av matrisen er 2, derfor er antallet frie variabler r \u003d 4 - 2 \u003d 2, antall grunnleggende variabler er også 2. Vi tar x 3, x 4 som frie variabler, vil vi uttrykke de grunnleggende variablene x 1, x 2 i form av fri og vi bringer systemet til enhetsgrunnlaget:

x 2 \u003d 1 - 2 x 4,

x 1 \u003d 3 - x 2 - 2 x 3 + x 4 \u003d 3 - 1 + 2 x 4 - 2 x 3 + x 4 \u003d 2 - 2 x 3 + 3 x 4

Ф \u003d 5 x 1 - x 3 \u003d 5 (2 - 2 x 3 + 3 x 4) - x 3 \u003d 10 - 10 x 3 + 15 x 4 - x 3 \u003d 10 - 11 x 3 + 15 x 4

Vi skriver likningssystemet og objektivfunksjonen i en form som er praktisk for simplekstabellen, det vil si x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

Ф + 11 x 3 - 15 x 4 \u003d 10

La oss lage et bord

I-iterasjonstabell 1

Grunnleggende AC	Frihet. AC
x1	2	1	0		— 3		1/2
x2	1	0	1	0	2
F	10	0	0	11	— 15		— 11/2

X 1 \u003d (2; 1; 0; 0) F 1 \u003d 10.

II iterasjon Tabell 2

x3	1	1/2	0	1	-3/2		3/4
x2	1	0	1	0			1/2
F	— 1	— 11/2	0	0	3/2		— 3/4

X 2 \u003d (0; 1; 1; 0) F 2 \u003d -1.

III iterasjon Tabell 3

x3	7/4	1/2	3/4	1	0
x4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X 3 \u003d (0; 0; 7/4; 1/2) F 3 \u003d -7/4.

Det er ingen positive tall i indeksraden til den siste tabellen, det vil si i uttrykket for objektivfunksjonen, alle Г i > 0. Vi har tilfelle I, derfor er den siste grunnleggende løsningen optimal.

Svar: Ф min = -7/4, optimal løsning (0; 0; 7/4; 1/2)

********************

Alternativ 10. Minimer målfunksjonen Ф \u003d x 1 + x 2,

med begrensninger: x 1 -2 x 3 + x 4 \u003d 2,

x 2 - x 3 + 2 x 4 \u003d 1,

Løsning:

Antall variabler er 5, rangeringen av matrisen er 3, derfor er antallet frie variabler r \u003d 6-3 \u003d 2. Vi tar x 3 og x 4 som frie variabler, x 1, x 2, x 5 som grunnleggende. Alle ligningene i systemet er allerede redusert til en enkelt basis (grunnleggende variabler er uttrykt i form av frie), men de er skrevet i en form som ikke er praktisk for bruk av simplekstabeller. Vi skriver ligningssystemet på skjemaet

x 1 - 2 x 3 + x 4 \u003d 2

x 2 - x 3 +2 x 4 \u003d 1

x 5 + x 3 - x 4. = 5

Vi uttrykker objektivfunksjonen i form av frie variabler og skriver den på formen Ф - 3 x 3 +3 x 4 = 3

La oss lage et bord

I-iterasjonstabell 1

Grunnleggende AC	Frihet. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X 1 \u003d (2; 3; 0; 0; 5) F 1 \u003d 3.

tabell 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X 2 \u003d (3/2; 0; 0; 1/2; 11/2) F 2 \u003d 3/2.

Det er ingen positive tall i indeksraden til den siste tabellen, det vil si i uttrykket for objektivfunksjonen, alle Гi > 0. Vi har tilfelle 1, derfor er den siste grunnleggende løsningen optimal.

Svar: Ф min = 3/2, den optimale løsningen er (3/2; 0; 0; 1/2; 11/2).

Vi deler den tredje raden med nøkkelelementet lik 5, vi får den tredje raden i den nye tabellen.

Grunnkolonner tilsvarer enkeltkolonner.

Beregning av gjenværende tabellverdier:

"BP - Grunnplan":

; ;

"x1": ; ;

"x5": ; .

Verdiene til indeksraden er ikke-negative, derfor får vi den optimale løsningen: , ; .

Svar: maksimal fortjeneste fra salg av produserte produkter, lik 160/3 enheter, sikres ved utgivelse av kun produkter av den andre typen i mengden 80/9 enheter.

Oppgave nummer 2

Problemet med ikke-lineær programmering er gitt. Finn maksimum og minimum av objektivfunksjonen ved hjelp av en grafanalytisk metode. Komponer Lagrange-funksjonen og vis den ved ytterpunktene tilstrekkelige forhold minimum (maksimum).

Fordi det siste sifferet i chifferen er 8, så A=2; B=5.

Fordi det nest siste sifferet i chifferen er 1, da bør du velge oppgave nummer 1.

Løsning:

1) La oss tegne området som systemet med ulikheter definerer.

Dette området er en trekant ABC med koordinatene til toppunktene: A(0; 2); B(4; 6) og C(16/3; 14/3).

De objektive funksjonsnivåene er sirkler sentrert i punktet (2; 5). Kvadratene til radiene vil være verdiene til objektivfunksjonen. Deretter viser figuren at minimumsverdien til objektivfunksjonen er nådd ved punkt H, maksimumsverdien er enten ved punkt A eller punkt C.

Verdien av målfunksjonen i punkt A: ;

Verdien av målfunksjonen i punkt C: ;

Dette betyr at maksimalverdien til funksjonen nås ved punktet A(0; 2) og er lik 13.

La oss finne koordinatene til punktet H.

For å gjøre dette, vurder systemet:

ó

ó

En linje er tangent til en sirkel hvis ligningen har en unik løsning. Kvadratisk ligning har en unik løsning hvis diskriminanten er 0.

Deretter ; ; - minimumsverdien til funksjonen.

2) Komponer Lagrange-funksjonen for å finne minimumsløsningen:

På x 1 =2.5; x 2 =4.5 vi får:

ó

Systemet har en løsning for , d.v.s. tilstrekkelige ekstreme forhold er oppfylt.

Vi komponerer Lagrange-funksjonen for å finne den maksimale løsningen:

Tilstrekkelige forhold for et ekstremum:

På x 1 =0; x 2 =2 vi får:

ó ó

Systemet har også en løsning, dvs. tilstrekkelige ekstreme forhold er oppfylt.

Svar: minimum av målfunksjonen er nådd ved ; ; den maksimale målfunksjonen er nådd når ; .

Oppgave nummer 3

To virksomheter tildeles midler i beløpet d enheter. Når tildelt til den første bedriften for et år x andeler av midler det gir inntekter k 1 x enheter, og når de tildeles det andre foretaket y fondsenheter, gir det inntekter k 1 y enheter. Beholdningen av midler ved utgangen av året for det første foretaket er lik nx, og for det andre min. Hvordan fordele alle midler innen 4 år slik at totalinntekten blir størst? Løs problemet ved dynamisk programmering.

i=8, k=1.

A=2200; k 1 = 6; k2=1; n=0,2; m=0,5.

Løsning:

Hele perioden på 4 år er delt inn i 4 stadier, som hver tilsvarer ett år. La oss nummerere stadiene fra og med det første året. La X k og Y k være midlene som tildeles henholdsvis foretak A og B på k-te trinn. Da er summen X k + Y k =a k den totale mengden midler brukt på k - det stadiet og gjenværende fra forrige trinn k - 1. på det første trinnet brukes alle tildelte midler og a 1 = 2200 enheter. inntekten som vil bli mottatt på k - det stadiet, når X k og Y k enheter tildeles, vil være 6X k + 1Y k . la den maksimale inntekten mottatt på de siste stadiene fra k - det stadiet er f k (a k) enheter. La oss skrive den funksjonelle Bellman-ligningen som uttrykker prinsippet om optimalitet: uansett starttilstand og innledende løsning den påfølgende løsningen må være optimal med hensyn til tilstanden som følger av den opprinnelige tilstanden:

For hvert trinn må du velge verdien X k , og verdien Y k=ak- Xk. Med dette i tankene vil vi finne inntekter på k-te trinn:

Den funksjonelle Bellman-ligningen vil se slik ut:

Vurder alle stadiene, start med det siste.

(siden maksimumet av den lineære funksjonen nås ved slutten av segmentet ved x 4 = a 4);