Matematiske modeller af lineære programmeringsproblemer. Matematisk model af et lineært programmeringsproblem Generelt billede af en lineær programmeringsmodel
Statens uddannelsesinstitution for videregående uddannelser
erhvervsuddannelse
"Moscow State Technical University opkaldt efter N.E. Bauman"
Kaluga gren
"Løsning af et lineært programmeringsproblem ved hjælp af simpleksmetoden"
Formålet med arbejdet: at studere og lære at anvende simplex-metoden i praksis til løsning af direkte og dobbelt lineære programmeringsproblemer
Teoretisk del.
Matematisk formulering af det lineære programmeringsproblem.
Fra praksis med at overveje matematiske programmeringsproblemer følger det, at det generelt er næsten umuligt at løse dem. Det er tilrådeligt at overveje separate klasser (typer) af problemer. For hver sådan klasse er det muligt at formulere en løsningsalgoritme, der kun er acceptabel for denne klasse af problemer. De mest udviklede problemer inden for matematisk programmering er problemer med lineær programmering (LP).
I lineære programmeringsproblemer er objektivfunktionen lineær, og begrænsningsbetingelserne indeholder lineære ligheder og lineære uligheder. Variabler kan være underlagt kravet om ikke-negativitet eller ej. Det samme lineære programmeringsproblem kan skrives i forskellige former. Hvis alle begrænsninger er i form af uligheder, så er problemet skrevet i standardform. Hvis alle dens begrænsninger, undtagen
repræsentere ligheder, så skrives det lineære programmeringsproblem i kanonisk form.
Generelt billede af det lineære programmeringsproblem
,
Begrænsninger:
1. Den højre side af alle begrænsninger skal være ikke-negative 
. Hvis nogen af koefficienterne< 0, то необходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;
2. Alle restriktioner skal præsenteres i form af ligheder, derfor, når man går fra ulighed til lighed, anvendes apparatet med yderligere variable.
Hvis de indledende restriktioner bestemmer forbruget af en eller anden ressource (""-tegnet), så variablerne 
skal fortolkes som resten eller ubrugt del af en ressource. I dette tilfælde er det en restvariabel og indtastes i ligningen med et "+"-tegn.
Hvis de indledende begrænsninger bestemmer overskuddet af en ressource (""-tegnet), så introduceres en overskydende variabel 
skilt "-".
Variabler:
Alle variable skal være ikke-negative, dvs. 
.
Hvis en variabel ikke har nogen fortegnsbegrænsninger, skal den repræsenteres som forskellen mellem to ikke-negative variable: , hvor . Denne substitution skal bruges i alle begrænsninger, der indeholder denne variabel, såvel som i udtrykket for den objektive funktion.
Hvis en sådan variabel falder ind i den optimale løsning, så
Objektiv funktion:
Skal maksimeres eller minimeres.
Et system af restriktioner i form af ligheder og uligheder danner et konveks sæt - et konveks polyeder. Dette sæt kan være begrænset eller ubegrænset. Den objektive funktion af et lineært programmeringsproblem er også en konveks funktion. Det lineære programmeringsproblem er således et specialtilfælde af det konvekse programmeringsproblem.
Lad os overveje systemet af begrænsninger af det lineære programmeringsproblem i form af ligheder
(1)
System (1) af lineære ligninger er konsistent, hvis det har mindst én løsning. System (1) kaldes redundant, hvis en af ligningerne kan udtrykkes som en lineær kombination af de andre.
I system (1) er antallet af variable (ukendte n) større end antallet af begrænsninger m. Vi antager, at rangen af dette system er lig med m (systemet er ikke-redundant), og at system (1) er konsistent. Så danner m variable ud af deres samlede antal basisvariablene, og de resterende variable kaldes ikke-basiske Hvis et ligningssystem har en løsning, så har det også en grundlæggende løsning En løsning til et ligningssystem (1) kaldes tilladt, hvis alle dets komponenter er ikke-negative. Hvis et system af lineære ligninger har en tilladelig løsning, så har det også en grundlæggende tilladt løsning. Sæt af alle tilladte løsninger af system (1) er en konveks mængde, dvs. mængden af løsninger på det lineære programmeringsproblem er konveks. Da dette sæt er dannet af planer (hyperplaner), har det form af et konveks polyeder. Den grundlæggende tilladte løsning svarer til det konvekse polyeders yderpunkt (dets ansigt eller toppunkt). Hvis der er en optimal løsning på et lineært programmeringsproblem, så er der en grundlæggende optimal løsning.
Den objektive funktion af et lineært programmeringsproblem er ligningen af et plan (eller et hyperplan for antallet af variable større end tre). Den objektive funktion af et lineært programmeringsproblem når sin maksimum- eller minimumværdi enten ved toppunktet af et konveks polyeder eller på en af dets flader. Løsningen/løsningerne til det lineære programmeringsproblem ligger således i hjørnerne af et konveks polyeder, og for at finde det er det nødvendigt at beregne værdierne af den objektive funktion ved hjørnerne af det konvekse polyeder bestemt af betingelserne- problemets begrænsninger.
Løsning af et lineært programmeringsproblem ved hjælp af en grafisk metode.
Vanskeligheden ved at konstruere en matematisk model ligger i at identificere variablerne og derefter repræsentere målet og begrænsningerne som matematiske funktioner for disse variable. Hvis modellen kun indeholder to variable, så kan det lineære programmeringsproblem løses grafisk. I tilfælde af tre variable bliver den grafiske løsning mindre klar, og med større værdier af variablerne endda umulig. Den grafiske løsning giver os dog mulighed for at drage konklusioner, der tjener som grundlag for at udvikle en generel metode til løsning af et lineært programmeringsproblem.
Det første trin ved brug af den grafiske metode er at repræsentere de mulige løsninger geometrisk, dvs. at konstruere en admissible solution region (ADA), hvor alle modelbetingelser samtidig er opfyldt. Ved opnåelse af en grafisk løsning plottes variablen langs den vandrette akse og langs den lodrette akse. Ved dannelse af ODD er det nødvendigt at forhindre opnåelse af uacceptable løsninger, der er forbundet med behovet for at opfylde betingelsen om ikke-negativitet af variabler. Før byggeriet er det nødvendigt at bestemme kvadranter, hvori ODR vil blive placeret. Kvadranterne bestemmes af fortegnene for variablerne og . Betingelserne for ikke-negativitet af variabler begrænser rækkevidden af deres tilladte værdier til den første kvadrant. Hvis variablen ikke er begrænset i fortegn, så er regionen begrænset af første og anden kvadrant, hvis , så af første og fjerde kvadrant. Andre grænser for løsningsrummet på planet er afbildet af rette linjer konstrueret ved hjælp af begrænsningsligningerne, med forbehold for at tegnet erstattes af tegnet "=". I dette tilfælde skal følgende tages i betragtning: højre side af alle restriktioner skal være ikke-negative . Hvis nogen begrænsning< 0, то необходимо коэффициенты соответствующего ограничения слева и справа до-множить на "-1" и изменить знак неравенства данного ограничения на противоположный. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных.
Som et resultat af konstruktionen opnås en polygon, der definerer løsningsrummet. Hvis en af restriktionerne har tegnet "=", så degenererer ODD til et segment.
Ved hvert punkt, der hører til området eller grænserne for løsningspolygonen, er alle begrænsninger opfyldt, så alle løsninger, der svarer til disse punkter, er gyldige. Løsningsrummet indeholder et uendeligt antal af sådanne punkter, men på trods af dette er det muligt at finde en optimal løsning. For at gøre dette er det nødvendigt at konstruere, i variablens plan, gradienten af den objektive funktion. Bestemmelsen af det optimale punkt afhænger af det problem, der skal løses.
Hvis objektivfunktionen definerer et maksimeringsproblem, vil det optimale punkt være placeret i retning af at øge gradienten; hvis minimeringsproblemet er defineret, så i retning af at mindske gradienten af objektivfunktionen. For at bestemme det optimale punkt vil vi flytte objektivfunktionen i retning af at øge (reducere) gradienten, indtil den bevæger sig ind i området med uacceptable løsninger.
Efter at have fundet det optimale punkt i løsningsrummet, bestemmes dets koordinater og værdien af den objektive funktion i det. Rigtigheden af valget af det optimale punkt kan kontrolleres ved at beregne objektivfunktionen ved hjørnerne af opløsningspolyederet. I ZLP er regionen med mulige løsninger altid et konveks sæt, dvs. sådan et sæt, at det segment, der forbinder disse to punkter, sammen med hvilke som helst to punkter, der hører til dette sæt, også tilhører det samme sæt. Enhver funktion øges hurtigst i retning af dens gradient.
Løsning af et lineært programmeringsproblem ved hjælp af simpleksmetoden.
Direkte opgave.
Overvej det lineære programmeringsproblem i kanonisk form:
Find maksimum (minimum) af en funktion 
under forhold
Det antages, at der findes en løsning på dette problem. For at finde den optimale løsning er det nødvendigt at finde gennemførlige basisløsninger, og ud fra dem vælge den optimale basisløsning.
Simplexmetoden er en algebraisk metode til løsning af lineære programmeringsproblemer. Under beregningsprocessen udføres en sekventiel gennemkøring af hjørnerne af opløsningspolyhedronen (SDP), der kontrollerer optimalitetsbetingelserne ved hvert vertex. Desuden er hver overgang til et tilstødende toppunkt ledsaget af en forbedring af den objektive funktion.
Beregningsprocedurer af simplex-metoden.
Med den grafiske metode til løsning af LLP svarer den optimale løsning altid til et af hjørnepunkterne (ekstrem) af løsningsrummet. Dette resultat danner grundlag for konstruktionen af simpleksmetoden. Simplexmetoden har ikke en klar geometrisk repræsentation af løsningsrummet.
Simplex-metoden implementerer en ordnet proces, hvor der, startende fra et indledende gennemførligt hjørnepunkt, foretages successive overgange fra et muligt yderpunkt til et andet, indtil det optimale løsningspunkt er fundet.
Lad os betegne: – det samlede antal variabler i LLP, præsenteret i kanonisk form; - antal indledende variabler; - antallet af restriktioner - antallet af yderligere variabler 
.
Hvert hjørne af løsningspolyederet har - variabler, der ikke er nul og () - nul-variabler.
Ikke-nul-variabler kaldes grundlæggende, nulvariabler kaldes ikke-grundlæggende.
Lad os supplere lighedssystemet med ligheden i den objektive funktion, og vi vil antage, at dette er en grundvariabel, der altid er til stede i grundlaget for ethvert vertex.
For at opnå en løsning opstilles et indledende tilladt grundlag, hvor basisvariablerne skal præsenteres i form af enhedsenhedsvektorer. Det betyder, at ligningerne, der repræsenterer et givet toppunkt, kun skal inkludere hver basisvariabel i én række med en koefficient lig med 1.
Når der vælges et indledende tilladt grundlag for kompilering af en simplekstabel i det første trin ST(0), er startvariablerne lig med nul og er ikke-grundlæggende; blandt de indførte yderligere variable vælges variable med koefficienter lig med én. Variablerne i ligheder (2) - (4) er grundlæggende og er inkluderet i - rækken med koefficienter lig med 0. For at udfylde simplekstabellen er det nødvendigt at transformere objektivfunktionen til formen 
. Så får vi endelig:
Når du kompilerer en simplekstabel, skal du overholde følgende regler:
i kolonnen længst til venstre er de grundlæggende variabler og ;
kolonnen længst til højre indeholder de højre dele af begrænsningerne;
Den første linje indeholder variablerne i en bestemt rækkefølge:
først, derefter ikke-grundlæggende variabler, er grundvariable placeret i de sidste kolonner før højre side (RF). Lad os skrive koefficienterne i ST(0):
| HVIS | |||||||
| 1 | 0 | 0 | 0 | 0 | |||
| 0 | 1 | 0 | 0 | ||||
| 0 | 0 | 1 | 0 | ||||
| 0 | 0 | 0 | 1 |
Optimiteten af et hvilket som helst af hjørnerne bestemmes af koefficienterne for ikke-grundlæggende variable i rækken af den aktuelle simplex-tabel:
For et maksimeringsproblem er dette toppunkt optimalt, hvis alle koefficienter for ikke-grundlæggende variable i rækken – er ikke-negative (>0);
For et minimeringsproblem er dette toppunkt optimalt, hvis alle koefficienter for ikke-grundlæggende variable i rækken – er ikke-positive (< 0).
Hvis i et maksimerings- (minimerings-) problem har én ikke-grundlæggende variabel i rækken – en koefficient<0(>0), så er det aktuelle punkt ikke optimalt, og grundlaget skal ændres. For at gøre dette skal du vælge en ikke-grundlæggende variabel, der har den mest negative (positive) koefficient i rækken –. Den valgte ikke-basisvariabel vil indgå i det nye grundlag og kaldes derfor en inkluderet variabel. Den basisvariabel, der vil blive afledt fra basisen, kaldes den eliminerede variabel.
Den udelukkede variabel vil være den basisvariabel, der først bliver til "0", når du flytter til et tilstødende toppunkt efter at have indtastet den inkluderede variabel.
Kolonnen for den inkluderede variabel kaldes aktiveringskolonnen.
Strengen for den ekskluderede variabel kaldes den tillade streng.
Skæringspunktet mellem den løsende kolonne og række bestemmer opløsningselementet (RE).
Sådan definerer du en ekskluderet variabel:
divider højresiden af alle grundvariable (undtagen rækken) med de tilsvarende positive koefficienter for den løsende kolonne;
vælg det mindste af de resulterende forhold.
Det er umuligt at dividere med "0" og en negativ værdi, da dette fører til fraværet af et skærende toppunkt eller til et toppunkt uden for ODR.
For at flytte til et tilstødende toppunkt er det nødvendigt at generere en overgangsmatrix B(0), som bestemmer forbindelsen mellem ST(0) og ST(1): ST(1) = B(0) ST(0).
For en vilkårlig kvadratisk matrix med dimension n, der har som (n - 1) kolonner enhedsvektorerne arrangeret i overensstemmelse med enhedsvektorerne i enhedsmatrixen, og en vilkårlig kolonne med et ikke-nul element på hoveddiagonalen, den inverse matrix findes efter følgende regel:
Hvert element i j-kolonnen er opdelt i RE og skifter fortegn til det modsatte, undtagen det løsende element.
Kunstigt startgrundlag. M – metode.
Hvis den oprindelige begrænsning er skrevet i form af ligheden "=" eller har tegnet "", så er det umuligt umiddelbart at opnå en acceptabel indledende grundlæggende løsning, da når du skriver problemet i standardform, efter at have introduceret yderligere variabler, en variant kan opstå, når de resulterende ligninger ikke tillader dannelsen indledende tilladelige grundlag i form af enhed enhed ord.
I dette tilfælde indføres yderligere kunstige variabler for at finde det oprindelige tilladte grundlag. Kunstige variable er ikke relateret til indholdet af problemet; deres introduktion er kun tilladt, hvis det tilsvarende beregningsskema vil give en optimal løsning, hvor alle kunstige variable vil være lig med nul.
R-variablerne bestemmer det indledende tilladte grundlag ud fra synspunktet om en eventuel videre overgang til et af ODR's hjørner. For brug af kunstige variable i den objektive funktion indføres en straf M. I maksimeringsproblemet er M negativ (M<<0), в задаче минимизации М положительное (М>>0).
Egenskab M: Når man adderer (subtraherer) med enhver endelig værdi, der bestemmer enhver værdi, som hver af variablerne i den oprindelige ZLP kan tage, ændres dens værdi (af variablen M) ikke, nemlig,
Formel (1.2), restriktioner for variables ikke-negativitet (ja, nej) - formel (1.3) (1.1) i = 1,... m (1.2) (1.3) Algoritmen til løsning af lineære programmeringsproblemer kræver at bringe deres formulering til kanonisk form, når den objektive funktion ...
I praksis er begrænsninger i et lineært programmeringsproblem ofte ikke specificeret af ligninger, men af uligheder.
Lad os vise, hvordan du kan gå fra et problem med ulighedsbegrænsninger til et grundlæggende lineært programmeringsproblem.
Lad der være et lineært programmeringsproblem med variable, hvor de begrænsninger, der er pålagt variablerne, har form af lineære uligheder. I nogle af dem kan ulighedstegnet være anderledes end andre (den anden type reduceres til den første ved blot at ændre tegnet på begge sider). Derfor sætter vi alle ulighedsbegrænsninger i standardform:
Det er påkrævet at finde et sæt ikke-negative værdier, der ville tilfredsstille uligheder (4.1), og derudover ville minimere den lineære funktion:
Fra problemet stillet på denne måde er det let at gå videre til hovedproblemet med lineær programmering. Faktisk, lad os introducere følgende notation:
hvor er nogle nye variabler, som vi vil kalde "yderligere". Ifølge betingelser (4.1) skal disse yderligere variable også være ikke-negative.
Således står vi over for et lineært programmeringsproblem i følgende formulering: find sådanne ikke-negative værdier af variablerne, at de opfylder ligningssystemet (4.3) og minimer samtidig den lineære funktion af disse variable:
Som du kan se, har vi foran os i sin rene form det primære lineære programmeringsproblem (LPLP). Ligninger (4.3) er givet i en form, der allerede er løst med hensyn til grundvariablerne, som udtrykkes gennem frie variable Det samlede antal variable er lig med , heraf "initial" og "additional". Funktionen L udtrykkes kun gennem de "indledende" variable (koefficienterne for de "yderligere" variabler i den er lig med nul).
Således har vi reduceret problemet med lineær programmering med ulighedsbegrænsninger til hovedproblemet med lineær programmering, men med et større antal variable, end der oprindeligt var i problemet.
Eksempel 1 Der er et lineært programmeringsproblem med ulighedsbegrænsninger: find ikke-negative værdier af variable, der opfylder betingelserne
og minimering af den lineære funktion
Det er påkrævet at bringe dette problem i form af en OPLP.
Løsning. Vi reducerer uligheder (4.4) til standardform;
Vi introducerer yderligere variabler:
Opgaven handler om at finde ikke-negative værdier af variablerne
opfylder ligningerne (4.6) og minimerer den lineære funktion (4.5).
Vi viste, hvordan vi kan bevæge os fra et lineært programmeringsproblem med ulighedsbegrænsninger til et lighedsbegrænsningsproblem (ICP). Den omvendte overgang er altid mulig - fra OLP til et problem med ulighedsbegrænsninger. Hvis vi i det første tilfælde øgede antallet af variabler, så reducerer vi det i det andet tilfælde, eliminerer grundlæggende variabler og efterlader kun frie.
Eksempel 2. Der er et lineært programmeringsproblem med lighedsbegrænsninger (LPLP):
og funktionen skal minimeres
Det er påkrævet at skrive det som et lineært programmeringsproblem med ulighedsbegrænsninger.
Løsning. Siden vælger vi nogle to af variablerne som frie. Bemærk, at variabler ikke kan vælges som frie, da de er relateret til den første af ligningerne (4 7): værdien af en af dem er fuldstændig bestemt af værdien af den anden, og frie variable skal være uafhængige
Af samme grund er det umuligt at vælge variabler som frie (de er forbundet med den anden ligning). Lad os vælge de frie variable og udtrykke resten gennem dem:
Da betingelser (4 9) kan erstattes af uligheder:
Lad os videregive udtrykket af den lineære funktion L til frie variabler, og erstatte deres udtryk (4.9) i L i stedet for og. vi får det.
FORBUNDSORGAN FOR UDDANNELSE
Forbundsstatens uddannelsesinstitution "PSKOV COLLEGE OF CONSTRUCTION AND ECONOMICS"
Emne "Matematiske metoder"
Lineært programmeringsproblem
Kursusarbejde
Elev af gruppe 315-PO
Andreev Dmitry Alexandrovich
Kursusleder
Vasilyeva Natalya Anatolevna
Pskov 2009
Introduktion
Kapitel Ι Lineær programmering
§ 1 Generel formulering af det lineære programmeringsproblem
§ 2 Matematisk model af det lineære programmeringsproblem
§ 3 Kanonisk form af det lineære programmeringsproblem
Kapitel ΙΙ Løsning af problemet ved hjælp af simpleksmetoden
§ 1 Problemformulering
§ 2 Udarbejdelse af en matematisk model af problemet
§ 3 Algoritmer til løsning af problemet ved brug af simpleksmetoden
§ 4 Konstruktion af den initiale referenceløsning ved brug af Gauss-metoden
§ 5 Løsning af problemet
Konklusion
Litteratur
Introduktion
I øjeblikket løses mange planlægnings- og ledelsesproblemer i sektorer af den nationale økonomi, såvel som en stor mængde private anvendte problemer, ved matematiske programmeringsmetoder. De mest udviklede metoder inden for løsning af optimeringsproblemer er lineære programmeringsmetoder. Disse metoder gør det muligt med tilstrækkelig nøjagtighed at beskrive en lang række opgaver inden for kommerciel aktivitet, såsom planlægning af handelsomsætning; placering af byens detailhandelsnetværk; planlægning af levering af varer til en by eller region; knytte handelsvirksomheder til leverandører; organisering af rationel transport af varer; fordeling af handelsarbejdere til stillinger; organisering af rationel indkøb af fødevarer; ressourceallokering; planlægning af kapitalinvesteringer; optimering af tværsektorielle forbindelser; udskiftning af kommercielt udstyr; bestemmelse af det optimale sortiment af varer under forhold med begrænset plads; etablering af en rationel driftsform.
I lineære programmeringsproblemer er effektivitetskriteriet og funktionerne i systemet af begrænsninger lineære.
Hvis et matematisk programmeringsproblem har en tidsvariabel, og effektivitetskriteriet er udtrykt gennem ligninger, der beskriver strømmen af operationer i tid, så er et sådant problem et dynamisk programmeringsproblem.
I mange økonomiske modeller kan sammenhængen mellem faste og variable faktorer betragtes som lineære.
Brugen af matematiske programmeringsmetoder i kommercielle aktiviteter involverer indsamling af nødvendige oplysninger af en forretningsmand, økonom eller finansmand og derefter formulering af et problem sammen med matematik. Da matematiske programmeringsmetoder allerede er implementeret på computeren i form af en pakke med standardprogrammer, er adgangen til dem normalt enkel, automatiseret og giver ikke særlige vanskeligheder.
Herefter omfatter driften af modellen indsamling og bearbejdning af information, indtastning af de bearbejdede informationer i en computer, beregninger baseret på udviklede skemaprogrammer og endelig udsendelse af beregningsresultater (i en brugervenlig form) til deres brug inden for området. produktionsaktiviteter.
Kapitel Ι Lineær programmering
§ 1 Generel formulering af det lineære programmeringsproblem
Lineær programmering er en gren af matematisk programmering, der studerer metoder til løsning af ekstreme problemer, der er karakteriseret ved en lineær sammenhæng mellem variable og en lineær objektiv funktion. For at løse lineære programmeringsproblemer udarbejdes en matematisk model af problemet, og der vælges en løsningsmetode.
Formuleringen af problemet med kommerciel aktivitet kan præsenteres i form af en matematisk model for lineær programmering, hvis den objektive funktion kan repræsenteres i form af en lineær form, og forholdet til begrænsede ressourcer kan beskrives gennem lineære ligninger eller uligheder . Derudover indføres en yderligere begrænsning - værdierne af variablerne skal være ikke-negative, da de repræsenterer mængder som omsætning, driftstid, omkostninger og andre økonomiske indikatorer.
Geometrisk fortolkning af økonomiske problemer gør det muligt at visualisere deres struktur, identificere træk og åbner op for måder at studere mere komplekse egenskaber på. Et lineært programmeringsproblem med to variable kan altid løses grafisk. Men allerede i det tredimensionelle rum bliver en sådan løsning mere kompliceret, og i rum, hvis dimensioner er mere end tre, er en grafisk løsning generelt umulig. Tilfældet med to variable har ikke nogen særlig praktisk betydning, men dets overvejelse tydeliggør egenskaberne ved lineære programmeringsproblemer, fører til ideen om at løse det og gør geometrisk klarhed over metoderne til løsning og måderne til deres praktiske implementering.
§ 2 Matematisk model af det lineære programmeringsproblem
Før vi løser et problem, sammensætter vi dens matematiske model.
En matematisk model er et sæt af sammenhænge bestående af en lineær objektiv funktion og lineære restriktioner på en variabel.
Princippet om at kompilere en matematisk model.
1. Vælg opgavevariabler.
Variablerne for problemet er mængderne
Hvilket fuldt ud karakteriserer den økonomiske proces beskrevet i problemstillingen. Normalt skrevet som en vektor X = () Desuden 
)
2. Opret et system til at begrænse problemet.
Et system af begrænsninger er et sæt af ligninger og uligheder, der opfyldes af problemvariablerne, og som følger af problemets begrænsede økonomiske forhold.
Generelt er systemet skrevet i form
3. Indstil objektivfunktionen.
Den objektive funktion er en funktion Z(X), der karakteriserer kvaliteten af opgaven, hvis yderpunkt skal findes. Generelt skrives objektivfunktionen Z(X) =
At. den matematiske model ser ud til at finde variablerne i problemet
opfylder begrænsningssystemet: 
og betingelsen om ikke-negativitet
0 (j = ), som giver yderpunktet for objektivfunktionen Z(Y) =
En tilladt løsning på et lineært programmeringsproblem er ethvert sæt af variable værdier, der opfylder et system af begrænsninger og betinget ikke-negativitet.
Sættet af tilladte løsninger danner domænet af tilladte løsninger på problemet (ADP).
En optimal løsning er en gennemførlig løsning på et problem, hvor den objektive funktion når et ekstremum.
§ 3 Kanonisk form af det lineære programmeringsproblem
Den matematiske model af problemet skal have en kanonisk form.
Hvis begrænsningssystemet kun består af en ligning, og alle variabler opfylder betingelsen om ikke-negativitet, så har problemet en kanonisk form.
Hvis systemet har mindst én ulighed, eller en variabel er ubegrænset under betingelse af ikke-negativitet, så har problemet en standardform. For at bringe problemet til kanonisk form skal du:
gå fra uligheder til ligningen som følger: på venstre side af ulighederne introducerer vi en ekstra variabel med en koefficient (+1) for uligheden (
) og (-1) for ulighed () pålægges yderligere variabler ikke mål-ikke-negativitet, så erstattes de af forskellen mellem to ikke-negative variable, dvs.: = – ( 
Generelt syn på den kanoniske form:
Kapitel ΙΙ Løsning af problemet ved hjælp af simpleksmetoden
Simplexmetoden er en metode til sekventiel forbedring af planen (løsningen), den mest effektive og bruges til at løse ethvert lineært programmeringsproblem.
Navnet på metoden kommer fra det latinske simplecx – simpelt fordi. fra den første havde regionen med mulige løsninger på problemet den enkleste form. Ideerne til metoden blev foreslået af den russiske matematiker L.V. Kontarovich. i 1939 og derefter blev denne idé udviklet og udviklet af J. Danzig i 1949.
Simplexmetoden giver dig mulighed for enten at finde en optimal løsning eller bevise, at den ikke eksisterer i et begrænset antal trin.
§ 1 Problemformulering
Virksomheden bruger 3 typer maskiner i produktionsprocessen: Ι, ІΙ, ІΙІ. Samtidig forbruges råvarer, arbejdskraft, og der tages højde for overheadomkostninger.
Ethvert lineært programmeringsproblem kan reduceres til et lineært programmeringsproblem i kanonisk form. For at gøre dette skal du i det generelle tilfælde være i stand til at reducere maksimeringsproblemet til minimeringsproblemet; bevæge sig fra ulighedsbegrænsninger til lighedsbegrænsninger og erstatte variabler, der ikke overholder betingelsen om ikke-negativitet. Maksimering af en bestemt funktion svarer til at minimere den samme funktion taget med det modsatte fortegn, og omvendt.
Reglen for at bringe et lineært programmeringsproblem til kanonisk form er som følger:
- hvis det i det oprindelige problem er nødvendigt at bestemme maksimum af en lineær funktion, skal du ændre tegnet og se efter minimum af denne funktion;
- hvis højre side af restriktionerne er negativ, så skal denne restriktion ganges med -1;
- hvis der er uligheder mellem restriktionerne, så transformeres de til ligheder ved at indføre yderligere ikke-negative variabler;
- hvis en eller anden variabel x j har ingen tegnrestriktioner, så erstattes den (i den objektive funktion og i alle restriktioner) af forskellen mellem to nye ikke-negative variable:
x 3 = x 3 + — x 3 — , Hvor x 3 + , x 3 — ≥ 0 .
Eksempel 1. Reduktion af det lineære programmeringsproblem til kanonisk form:
min L = 2 x 1 + x 2 - x 3;
2 x 2 - x 3 < 5;
x 1 + x 2 – x 3 ≥ -1;
2 x 1 - x 2 < -3;
x 1 < 0; x 2 > 0; x 3 ≥ 0.
Lad os introducere nivelleringsvariable i hver ligning i systemet af begrænsninger x 4, x 5, x 6. Systemet skrives i form af ligheder, og i begrænsningssystemets første og tredje ligning vil variablerne blive skrevet. x 4, x 6 indtastes i venstre side med et "+"-tegn, og i den anden ligning variablen x 5 indtastes med et "-"-tegn.
2 x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 > 0; x 6 ≥ 0.
De frie led i den kanoniske form skal være positive; for at gøre dette skal du gange de sidste to ligninger med -1:
2 x 2 - x 3 + x 4 = 5;
-x1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 – x 6 = 3.
I den kanoniske form for at skrive lineære programmeringsproblemer skal alle variable, der indgår i systemet af begrænsninger, være negative. Lad os antage det x 1 = x 1 ' - x 7 , Hvor x 1 ' ≥ 0, x 7 ≥ 0 .
Ved at erstatte dette udtryk i systemet af begrænsninger og den objektive funktion og skrive variablerne i stigende indeksrækkefølge, får vi et lineært programmeringsproblem præsenteret i kanonisk form:
L min = 2 x 1' + x 2 - x 3 - 2 x 7;
2 x 2 - x 3 + x 4 = 5;
-x 1 ' — x 2 + x 3 + x 5 + x 7 = 1;
-2x 1’ + x 2 – x 6 + 2x 7 = 3;
x 1 ' ≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.
Optimalitetsbetingelse for grundplanen for det kanoniske LP-problem. Simplex metode og dens konvergens.
Simplex metoden er universel, da det giver dig mulighed for at løse næsten ethvert lineært programmeringsproblem skrevet ind kanonisk form.
Ideen om simplex-metoden konsekvent forbedring af planen, er, at startende fra en indledende referenceløsning, sekventielt rettet bevægelse fra problemets referenceløsninger til den optimale.
Værdien af den objektive funktion falder ikke under denne bevægelse for problemer til det maksimale.
Da antallet af støtteløsninger er begrænset, så opnår vi efter et begrænset antal trin den optimale støtteløsning.
En referenceløsning er en grundlæggende ikke-negativ løsning.
Simplex metode algoritme
1. Den matematiske model af problemet skal være kanonisk. Hvis det er ikke-kanonisk, så skal det bringes til kanonisk form.
2. Find den oprindelige referenceløsning, og kontroller den for optimalitet.
For at gøre dette skal du udfylde simplekstabel 1.
Vi udfylder alle rækker i tabellen i 1. trin i henhold til dataene fra systemet med begrænsninger og den objektive funktion.
Følgende tilfælde er mulige ved løsning af problemer på maksimum:
1. Hvis alle koefficienterne for den sidste række i simplekstabellen DJ³ 0, så fundet
løsning optimal.
2 Hvis mindst én koefficient DJ £ 0, men for den tilsvarende variabel er der ikke en eneste positiv evaluerende sammenhæng, så er løsningen vi stopper opgaver, da F(X) ® ¥ , dvs. den objektive funktion er ikke begrænset til området for gennemførlige løsninger.
Hvis mindst én koefficient i den sidste række er negativ, og for den tilsvarende variabel er der mindst én positiv evaluerende holdning, så skal du flytte dig til en anden referenceløsning.
E hvis Der er altså flere negative koefficienter i den sidste række til den underliggende variabel kolonne(BP) indfør det variabel, hvilket svarer til den største negative koefficient i absolut værdi.
5. Hvis mindst én koefficient Dk< 0 ,At k - ty kolonne acceptere for oplægsholderen.
6. For førende linje vi accepterer den der svarer minimum forholdet mellem gratis medlemmer bi til positive koefficienter ledende, k – den kolonne.
7. Elementet placeret i skæringspunktet mellem de førende rækker og kolonnen kaldes førende element.
Udfyldning af simplex tabel 2 :
· fyld grundkolonnen med nuller og ettaller
· omskriv den førende linje ved at dividere den med det førende element
· hvis den forreste række har nuller, kan de tilsvarende kolonner flyttes til den næste simplekstabel
· vi finder de resterende koefficienter ved at bruge "rektangel"-reglen
Vi får en ny referenceløsning, som vi tjekker for optimalitet:
Hvis alle koefficienter i den sidste række DJ³ 0, så er løsningen fundet maksimum.
Hvis ikke, så udfyld simplex-tabellen på 8. trin og så videre.
Hvis den objektive funktion F(X) kræver at finde minimumsværdi, derefter kriteriet optimaliteten af problemet er ikke-positive koefficienter D j for alle j = 1,2,…n.
Konvergens af simplex-metoden. Degeneration i LP-problemer. Den vigtigste egenskab ved enhver beregningsalgoritme er konvergens, dvs. muligheden for at opnå de ønskede resultater under dens anvendelse (med en given nøjagtighed) i et begrænset antal trin (iterationer).
Det er let at se, at problemer med konvergensen af simplex-metoden potentielt kan opstå på tidspunktet for valg af værdien af r (afsnit 2") i det tilfælde, hvor de samme minimumsværdier af forholdet
vil blive opnået for flere rækker af tabel T (q) samtidigt. Så ved næste iteration vil kolonne b(β(q+1)) indeholde nul elementer.
⇐ Forrige12345Næste ⇒
Udgivelsesdato: 2015-11-01; Læst: 4190 | Krænkelse af ophavsret på siden
Studopedia.org - Studopedia.Org - 2014-2018 (0,002 s)...
Optimal løsning - problem - lineær programmering
Side 1
Den optimale løsning på et lineært programmeringsproblem opnås ved et af referencepunkterne, hvor mindst k n, - m variable er lig med nul.
Ved at bruge den optimale løsning på det lineære programmeringsproblem kan man finde de tilladte ændringer i DS, hvor L forbliver konstant.
Hvis der er en optimal løsning på et lineært programmeringsproblem, så er der en grundlæggende optimal løsning.
Det er blevet bevist, at den optimale løsning på et lineært programmeringsproblem er placeret på grænsen af området med tilladte værdier af kontrollerede variable, som er et polyeder i n-dimensionelt rum og defineret af et system af lineære begrænsninger.
Da z er den optimale løsning på et lineært programmeringsproblem med m begrænsninger, indeholder denne løsning højst m strengt positive variabler.
Det er bevist, at den optimale løsning på det lineære programmeringsproblem er placeret på grænsen af området med tilladte værdier for de kontrollerede variable, som er et polyeder i det /-dimensionelle rum, defineret af et system af lineære begrænsninger. Koordinaterne for hvert toppunkt bestemmes ved at løse et ligningssystem (begrænsninger), og i nærvær af n kontrollerede variable og m begrænsninger er det nødvendigt at løse ligningssystemet. Kombinationen Cpt n (m - n vokser meget hurtigt med stigende type, så at finde en løsning kræver et meget stort antal beregninger, selv utilgængelige for en computer.
Så i tilfælde af D 1 viser den optimale løsning på det lineære programmeringsproblem sig automatisk at være heltal.
Som det blev vist i del 1, er den optimale løsning på et lineært programmeringsproblem ikke nødvendigvis heltal, og samtidig er der mange problemer, hvis natur kræver en heltalsløsning. Nogle af disse problemer ser ikke ud til at være heltalsprogrammeringsproblemer, men de kan formuleres som sådan.
Det er indlysende, at ikke enhver grundlæggende løsning er en optimal løsning på et lineært programmeringsproblem. Den optimale løsning på et ikke-degenereret problem skal dog altid være basisløsningen for ligningssystemet (VIII, 42), og derfor består opgaven med at finde den optimale løsning i kun at opregne basisløsningerne for systemet af ligninger (VIII, 42), blandt hvilke den optimale findes.
Det er indlysende, at ikke enhver grundlæggende løsning er en optimal løsning på et lineært programmeringsproblem. Den optimale løsning på et ikke-degenereret problem skal dog altid være basisløsningen for ligningssystemet (VIII42), og opgaven med at finde den optimale løsning består således kun i at søge basisløsningerne af ligningssystemet (VIII42) ), blandt hvilke den optimale findes.
Efter adskillige iterationer af trin 3 kan der dukke flere alternative optimale løsninger på det lineære programmeringsproblem op.
LINEÆR PROGRAMMERINGSPROBLEM
Denne form for cykling kaldes undertiden kontinuerlig degeneration. Desværre forekommer dette fænomen ofte i højdimensionelle medium PI-problemer. Der er også mange eksempler på lavdimensionelle problemer (ikke mere end 10 variabler og ligninger), der kræver tusindvis af iterationer for at opnå konvergens.
I disse tilfælde anvendes simplex-metoden, som er en iterativ (trin-for-trin) procedure til at bestemme den optimale løsning på et lineært programmeringsproblem. Beregninger ved hjælp af simplex-metoden begynder med at identificere en mulig løsning og derefter søge efter andre mulige løsninger og kontrollere mulighederne for at forbedre dem. Overgangen fra en løsning til en anden fortsætter, indtil nye forbedringer ikke længere er mulige. Standard computerprogrammer er meget udbredt, der bruger simplex-metoden til at løse ledelsesproblemer, der kan repræsenteres som lineære programmeringsproblemer.
Hvis systemet med lineære begrænsninger har en speciel struktur, for eksempel hvis det danner en netværksmodel, kan denne omstændighed bruges i trin 2, når man finder den optimale løsning på det lineære programmeringsproblem.
Ideen om proportional fordeling blev implementeret i form af en to-trins beregningsalgoritme foreslået af I.I. Dikin, som i det væsentlige bruger egenskaben ved den indre punktmetode til at generere et relativt indre punkt af et sæt optimale løsninger til en lineær programmering problem. Denne egenskab betyder, at grænseværdierne under ulighederne (2.3.2) - (2.3.4) kun opnås for de variable, der har disse grænseværdier for enhver anden optimal løsning.
Sider: 1 2
Grafisk metode til løsning af et lineært programmeringsproblem
Lad os overveje ZLP i standardform for tilfælde af to variable:
(10)
Lad systemet af uligheder (10) være konsekvent (hav mindst én løsning). Enhver ulighed i dette system definerer geometrisk et halvt plan med en grænselinje 
Ikke-negativitetsbetingelser definerer halvplaner med tilsvarende grænselinjer Og.
Da systemet er konsistent, danner halvplaner, ligesom konvekse mængder, der krydser hinanden, en fælles del, som er en konveks mængde og er en samling af punkter, hvor koordinaterne for hver af dem er en løsning på dette system. Sættet af alle disse punkter kaldes løsningspolygon. Det kan være et punkt, et segment, en stråle, en ret linje, en lukket polygon eller et ubegrænset polygonalt område.
At løse ZLP'en geometrisk repræsenterer en søgning efter et punkt i løsningspolygonen, hvis koordinater giver den maksimale (mindste) værdi til objektivfunktionen. Desuden er alle punkter i polyederet en gyldig løsning.
Lad os overveje den såkaldte niveau linje objektiv funktion z, det vil sige linjen, langs hvilken denne funktion har den samme faste værdi: eller 
Algoritme til løsning af et lineært programmeringsproblem ved hjælp af den grafiske metode (antal variable).
1. Et polygonalt område af mulige løsninger på det plan, der svarer til restriktionerne, er konstrueret. Derefter konstrueres gradientvektoren
objektiv funktion z på ethvert tidspunkt regionen med mulige løsninger.
2. Lige linje (funktionsniveaulinje z), vinkelret på gradientvektoren, bevæger sig parallelt med sig selv i retning af gradientvektoren i tilfælde af et maksimalt problem (og i den modsatte retning i tilfælde af et minimumsproblem), indtil det forlader området med mulige løsninger. Grænsepunktet (eller punkterne) for regionen er de optimale punkter.
3. For at finde koordinaterne til det optimale punkt er det nødvendigt at løse et ligningssystem, der svarer til de rette linjer, hvis skæringspunkt danner dette punkt.
Formulering af hovedtyper af LP-problemer, konstruktion af deres matematiske modeller
Værdien af den objektive funktion på dette tidspunkt vil være optimal, og selve punktets koordinater vil være en løsning på LP-problemet .
Eksempel. Løs problemet geometrisk:
Lad os konstruere en polygon af alle mulige løsninger OABCD og retningsvektoren for objektivfunktionen (fig. 1). Gradientvektorens retning angiver retningen, hvori objektivfunktionen øges. Da det overvejede problem er at finde maksimum, flytter vi linjen vinkelret på vektoren i retningen af denne vektor parallelt med sig selv, indtil denne linje forlader området med mulige løsninger. På grænsen af regionen, i vores tilfælde på punktet MED, og der vil være en løsning på problemet. Prik MED er i skæringspunktet mellem linjer og . Følgelig bestemmes dens koordinater ved at løse systemet af disse ligninger:
hvorfra dvs. prik MED har koordinater (6, 4).
Maksimum (maksimal værdi af objektivfunktionen) er lig med: Svar: med en optimal løsning dvs. maksimal fortjeneste kan opnås ved at producere 6 enheder af det første og 4 enheder af det andet produkt.
INTRODUKTION
Moderne økonomisk teori, både på mikro- og makroniveau, inkluderer matematiske modeller og metoder som et naturligt, nødvendigt element. Brugen af matematik i økonomi tillader for det første at identificere og formelt beskrive de vigtigste, væsentlige forbindelser mellem økonomiske variabler og objekter: studiet af et så komplekst objekt kræver en høj grad af abstraktion. For det andet kan man ud fra klart formulerede indledende data og sammenhænge ved brug af deduktive metoder opnå konklusioner, der er tilstrækkelige til det undersøgte objekt i samme omfang som de præmisser, der er lagt. For det tredje giver metoderne til matematik og statistik os mulighed for induktivt at opnå ny viden om et objekt: at evaluere formen og parametrene for afhængighederne af dets variabler, som er mest i overensstemmelse med eksisterende observationer. Endelig, for det fjerde, giver brugen af matematikkens sprog mulighed for præcist og kompakt at præsentere den økonomiske teoris bestemmelser, formulere dens begreber og konklusioner.
Matematiske modeller brugt i økonomi kan opdeles i klasser efter en række karakteristika relateret til egenskaberne ved det objekt, der modelleres, formålet med modelleringen og de anvendte værktøjer: mikro- og makroøkonomiske modeller, teoretiske og ligevægtsmodeller, statistiske og dynamiske.
Essensen af optimeringsmetoder er, at baseret på tilgængeligheden af visse ressourcer vælges en metode til deres brug (distribution), der sikrer det maksimale (minimum) af den indikator, vi er interesseret i.
Alle hovedafsnit af matematisk programmering (planlægning) bruges som optimeringsmetoder i økonomi.
En matematisk disciplin, der beskæftiger sig med studiet af ekstreme (maksimum eller minimum) kontrol- og planlægningsproblemer og udvikling af metoder til at løse dem kaldes matematisk programmering.
Generelt består den matematiske formulering af det ekstremale problem i at bestemme den største eller mindste værdi af den objektive funktion 
givet det 
,
hvor og er givet funktioner, og er nogle reelle tal.
Afhængigt af typen af målfunktion og begrænsninger er matematisk programmering opdelt i lineær og ikke-lineær. Mest
Den studerede gren af matematisk programmering er lineær programmering.
Definition.
Lineær programmeringsproblem (side 1 af 3)
Lineær programmering – videnskaben om metoder til at bruge og finde ekstreme (største og mindste) værdier af en lineær funktion, hvis ubekendte er underlagt lineære begrænsninger.
Denne lineære funktion kaldes målfunktionen, og begrænsningerne i form af ligninger eller uligheder kaldes et system af begrænsninger.
Definition. Det matematiske udtryk for en objektiv funktion og dens begrænsninger kaldes matematisk model af et økonomisk problem.
Lad os overveje nogle lineære programmeringsproblemer (LPP'er).
1. Ressourceforbrugsproblem (produktionsplanlægningsproblem).
Til fremstilling af forskellige produkter 
Virksomheden anvender tre forskellige typer råvarer. Standarder for forbrug af råvarer til produktion af ét produkt 
, samt det samlede antal
råvarer af hver type, der kan bruges af virksomheden, er angivet i tabel.
Lav en produktionsplan for produkter, hvor den samlede pris for alle produkter produceret af virksomheden er maksimal.
Lad os bygge en matematisk model af dette problem.
Lad os betegne med det krævede output af produkter, biprodukter,
gennem – produkter.
Da der er omkostningsstandarder for hver type råvare, så kan vi finde de samlede omkostninger for hver type råmateriale til fremstilling af alle produkter. Af tabellen følger, at den samlede mængde råvarer af type I vil være, II – 
,
III – 
. Og da der er restriktioner på fonden af råvarer, bør den samlede mængde af hver type råvare ikke være mere end den samlede mængde af råvarer, dvs.
vi opnår følgende system af uligheder
(1)
I økonomiske termer, variable 
kan kun tage ikke-negative værdier:
(2)
Prisen for alle produkter af denne type vil være 
– 
– 
Følgelig vil de samlede omkostninger for produkter produceret af virksomheden være (3)
Vi skal finde 
denne funktion. Blandt alle ikke-negative løsninger af system (1) er det således nødvendigt at finde en, ved hvilken funktion (3) tager den maksimale værdi.
Dette problem kan let generaliseres til tilfældet med at producere typer af produkter ved hjælp af typer af råmaterialer (ressourcer).
Lad os betegne med 
– antal produkter, der er planlagt til produktion 
– lager af – type ressourcer – specifikt forbrug af – ressource til fremstilling – produkter. – fortjeneste ved salg af en enhed af produktet – type.
Så vil den økonomisk-matematiske model for problemet med at bruge ressourcer i den generelle formulering tage formen: find en sådan plan 
output, der opfylder det grundlæggende system af begrænsninger 
yderligere begrænsningssystem
hvor den objektive funktion er 
tager den maksimale værdi.
Kommentar. For at skabe en matematisk model af ZLP er det nødvendigt:
– indføre variable betegnelser;
– baseret på formålet med økonomisk forskning, skabe en objektiv funktion;
– under hensyntagen til restriktionerne i brugen af økonomiske indikatorer for problemet og deres kvantitative mønstre, nedskriv et system af restriktioner.
Løsningen af lineære programmeringsproblemer er baseret på begreberne analytisk geometri i – dimensionelt vektorrum.
At bringe den generelle ZLP til kanonisk form.
Den generelle opfattelse af ZLP er som følger:
(1)
(2)
(3)
hvor relation (1) er den objektive funktion, (2) er systemet med hovedrestriktioner, (3) er systemet med yderligere restriktioner.
Relationerne (2) og (3) udgør et komplet system af restriktioner.
At bringe systemet med hovedrestriktioner til kanonisk form udføres ved at indføre yderligere ikke-negative variable med koefficienterne "+1" hvis formens uligheder og "-1" hvis formens uligheder. Yderligere variable er inkluderet i objektivfunktionen med nulkoefficienter.
Definition . En ZLP siges at være givet i kanonisk form, hvis dens system af hovedbegrænsninger er repræsenteret af ligninger.
Definition. En PLP siges at være givet i standardform af kanonisk form, hvis følgende betingelser er opfyldt:
1) systemet af hovedbegrænsninger er repræsenteret af ligninger, og de er alle lineært uafhængige;
2) antallet af ligninger er mindre end antallet af variable;
3) problemet med at minimere den objektive funktion er løst;
4) højre side af systemet af hovedbegrænsninger er ikke-negative;
5) alle variabler er også ikke-negative.
I de fleste metoder til løsning af lineære programmeringsproblemer antages det, at systemet af begrænsninger består af ligninger og naturlige betingelser for variables ikke-negativitet.
Men når man laver modeller for mange problemer, dannes begrænsninger hovedsageligt i form af et system af uligheder, så det er nødvendigt at kunne gå fra et system af uligheder til et ligningssystem.
Dette kan gøres sådan:
Lad os tage den lineære ulighed
og tilføje til venstre side en vis værdi, således at uligheden bliver til lighed
Desuden er denne værdi ikke-negativ.
Eksempel
Bring det lineære programmeringsproblem til kanonisk form:
Løsning:
Lad os gå videre til problemet med at finde maksimum af den objektive funktion.
For at gøre dette ændrer vi tegnene på koefficienterne for den objektive funktion.
For at omdanne den anden og tredje ulighed i systemet af begrænsninger til ligninger, introducerer vi ikke-negative yderligere variable x 4 x 5 (i den matematiske model er denne operation markeret med bogstavet D).
Variablen x 4 indføres i venstre side af den anden ulighed med "+" tegnet, da uligheden har formen "≤".
Variablen x 5 indføres i venstre side af den tredje ulighed med et "-"-tegn, da uligheden har formen "≥".
Variablerne x 4 x 5 indtastes i objektivfunktionen med en koefficient. lig med nul.
Vi skriver problemet i kanonisk form:
ENKEL METODE TIL LØSNING AF LINEÆRE PROGRAMMERINGSPROBLEMER
Denne metode er en metode til målrettet opregning af referenceløsninger til et lineært programmeringsproblem. Det giver mulighed for, i et begrænset antal trin, enten at finde en optimal løsning eller at fastslå, at der ikke er nogen optimal løsning.
Algoritme af simplex-metoden til løsning af lineære programmeringsproblemer
For at løse et problem ved hjælp af simplex-metoden skal du gøre følgende:
1. Bring problemet til kanonisk form
Emne 8. Lineær programmering
Find den indledende supportløsning med et "enhedsgrundlag" (hvis der ikke er nogen supportløsning, så har problemet ikke en løsning på grund af inkompatibiliteten af systemet af begrænsninger)
3. Beregn estimater af vektornedbrydninger baseret på referenceopløsningen og udfyld simplexmetodens tabel
4. Hvis kriteriet for den optimale løsnings unikke karakter er opfyldt, slutter løsningen af problemet
5. Hvis betingelsen for eksistensen af et sæt af optimale løsninger er opfyldt, så findes alle optimale løsninger ved simpel opregning
Et eksempel på løsning af et problem ved hjælp af simpleksmetoden
Eksempel 1
Løs problemet ved hjælp af simpleksmetoden:
Minimer funktionsværdi
F = 10×1 – 4×3 max
I nærvær af restriktioner i form af uligheder
Vi bringer problemet til kanonisk form.
For at gøre dette introducerer vi en ekstra variabel x 5 med koefficient +1 til venstre side af den første ulighedsbegrænsning. Variablen x 5 er inkluderet i objektivfunktionen med en koefficient på nul (dvs. den er ikke inkluderet).
Vi får:
F = 10×1 – 4×3+0∙x5 max
I nærvær af restriktioner i form af uligheder
Vi finder den indledende supportløsning. For at gøre dette sætter vi lighedstegn mellem frie (uløste) variabler til nul x1 = x3 = 0.
Vi opnår en referenceløsning X1 = (0,0,0,5,9/15,6) med en enhedsbasis B1 = (A4, A5, A6).
Vi beregner estimater af udvidelser af tilstandsvektorer baseret på referenceløsningen ved hjælp af formlen:
Δ k = C b X k - c k
· C b = (c 1 , c 2 , … , c m) - vektor af koefficienter for den objektive funktion for de grundlæggende variable
· X k = (x 1k , x 2k , … , x mk) - ekspansionsvektor for den tilsvarende vektor A k i henhold til referenceopløsningens basis
· C k - koefficient for objektivfunktionen for variablen x k.
Estimaterne af de vektorer, der indgår i grundlaget, er altid lig nul.
Referenceløsningen, udvidelseskoefficienter og estimater af udvidelser af tilstandsvektorer baseret på referenceløsningen er skrevet i en simplekstabel:
Øverst i tabellen, for at lette beregningen af estimater, er koefficienterne for den objektive funktion skrevet. I den første kolonne "B" er de vektorer, der indgår i referenceløsningens basis, skrevet. Rækkefølgen, hvori disse vektorer er skrevet, svarer til antallet af tilladte ukendte i begrænsningsligningerne. I den anden kolonne i tabellen "C b" er koefficienterne for den objektive funktion for de grundlæggende variable skrevet i samme rækkefølge. Med det korrekte arrangement af koefficienterne for den objektive funktion i kolonnen "C b" er estimaterne af enhedsvektorerne inkluderet i grundlaget altid lig med nul.
I den sidste række af tabellen med estimater af Δ k i kolonnen "A 0" er værdierne af den objektive funktion på referenceløsningen Z(X 1) skrevet.
Den initiale støtteløsning er ikke optimal, da estimaterne Δ 1 = -2, Δ 3 = -9 for vektorerne A 1 og A 3 i det maksimale problem er negative.
Ifølge sætningen om forbedring af støtteløsningen, hvis mindst én vektor i et maksimalt problem har et negativt estimat, så kan du finde en ny støtteløsning, hvor værdien af den objektive funktion vil være større.
Lad os bestemme, hvilken af de to vektorer, der vil føre til en større stigning i objektivfunktionen.
Forøgelsen af den objektive funktion findes ved formlen:
Vi beregner værdierne af parameteren θ 01 for den første og tredje kolonne ved hjælp af formlen:
Vi får θ 01 = 6 for l = 1, θ 03 = 3 for l = 1 (Tabel 26.1).
Vi finder stigningen af den objektive funktion, når vi indfører den første vektor i basis
ΔZ 1 = - 6*(- 2) = 12,
og den tredje vektor ΔZ3 = - 3*(- 9) = 27.
For en hurtigere tilgang til den optimale løsning er det derfor nødvendigt at indføre vektor A3 i basis af referenceopløsningen i stedet for den første vektor af basis A6, da minimum af parameteren θ 03 er opnået i den første række ( l = 1).
Vi udfører Jordan-transformationen med elementet X13 = 2, vi får den anden referenceløsning
X2 = (0,0,3,21,42,0)
med basis B2 = (A3, A4, A5).
(Tabel 26.2)
Denne løsning er ikke optimal, da vektor A2 har en negativ score Δ2 = -6.
For at forbedre løsningen er det nødvendigt at indføre vektor A2 i referenceopløsningens basis.
Vi bestemmer antallet af vektoren afledt af basis. For at gøre dette beregner vi parameteren θ 02 for den anden kolonne, den er lig med 7 for l = 2.
Følgelig udleder vi den anden basisvektor A4 fra basisen.
Vi udfører Jordan-transformationen med elementet x 22 = 3, vi får den tredje støtteløsning
X3 = (0,7,10,0,63,0)
B2 = (A3, A2, A5) (Tabel 26.3).
Denne løsning er den eneste optimale, da estimaterne for alle vektorer, der ikke er inkluderet i grundlaget, er positive
Δ1 = 7/2, Δ4 = 2, Δ6 = 7/2.
Svar: maks. Z(X) = 201 ved X = (0,7,10,0,63).
⇐ Forrige123456789Næste ⇒
T10. Redegørelse for det lineære programmeringsproblem
Matematisk model Et økonomisk problem er et sæt matematiske sammenhænge, der beskriver den økonomiske proces.
For at kompilere en matematisk model skal du bruge:
1. Vælg opgavevariabler;
2. skabe et system af restriktioner;
3. sæt den objektive funktion.
Opgavevariabler kaldes de mængder x 1, x 2,..., x n, som fuldstændig karakteriserer den økonomiske proces. De skrives normalt som en vektor X = (x 1, x 2,..., x n).
Problembegrænsningssystem er et sæt af ligninger og uligheder, der tilfredsstilles af problemets variabler, og som følger af de begrænsede ressourcer og andre økonomiske forhold, for eksempel variablenes positivitet. Generelt ser de sådan ud:
Den objektive funktion kaldes funktion F(X) = f(x 1, x 2,..., x n) af opgavevariabler, som karakteriserer opgavens kvalitet og hvis yderpunkt skal findes.
Generelt matematisk programmeringsproblem er formuleret som følger: find opgavevariablerne x 1, x 2,..., x n, som giver yderpunktet for den objektive funktion
F(X) = f(x 1, x 2,…, x n) ® max (min) (2)
og opfylde begrænsningssystemet (1).
Hvis objektivfunktionen (2) og systemet af begrænsninger (1) er lineære, kaldes det matematiske programmeringsproblem lineært programmeringsproblem (LPP).
Vektor X (sæt af problemvariabler) kaldes acceptabel løsning, eller ZLP-planen, hvis den opfylder begrænsningssystemet (1). En tilladt plan X, der giver et ekstremum af den objektive funktion, kaldes optimal løsning ZLP.
2. Eksempler på udarbejdelse af matematiske modeller for økonomiske problemer
Undersøgelsen af specifikke produktionssituationer fører til ZLP, som tolkes som problemer omkring optimal udnyttelse af begrænsede ressourcer.
1.Optimal produktionsplan problem
For at producere to typer produkter T 1 og T 2 bruges tre typer ressourcer S 1, S 2, S 3. Ressourcereserver, antallet af ressourceenheder brugt på at producere en produktenhed samt fortjeneste ved salg af en produktenhed er vist i tabellen:
Det er nødvendigt at finde en produktionsplan, der vil maksimere fortjenesten fra salget.
Løsning.
Lad os betegne x 1, x 2 - antallet af produktionsenheder, henholdsvis T 1 og T 2, der er planlagt til produktion. For at producere dem skal du bruge (x 1 + x 2) enheder af ressource S 1, (x 1 + 4x 2) enheder af ressource S 2, (x 1) enheder af ressource S 3. Forbrug af ressourcer S 1 , S 2 , S 3 bør ikke overstige deres reserver, henholdsvis 8, 20 og 5 enheder.
Derefter kan den økonomiske og matematiske model af problemet formuleres som følger:
Find produktionsplanen X = (x 1, x 2), der opfylder systemet af begrænsninger: 
og tilstand,
hvor funktionen tager den maksimale værdi.
Problemet kan let generaliseres til tilfældet med at producere n typer produkter ved hjælp af m typer ressourcer.
2.Optimalt kostproblem
Der er to typer fødevarer, K 1 og K 2, der indeholder næringsstofferne S 1, S 2 og S 3. Indholdet af antallet af næringsenheder i 1 kg af hver fodertype, det nødvendige minimum af næringsstoffer samt prisen på 1 kg foder er vist i tabellen:
Det er nødvendigt at skabe en daglig kost, der har en minimumsomkostning, hvor indholdet af hver type næringsstof ikke vil være mindre end den fastsatte grænse.
Løsning.
Lad os betegne x 1, x 2 - mængden af foder K 1 og K 2 inkluderet i den daglige kost. Så vil denne diæt omfatte (3x 1 + x 2) enheder af næringsstof S 1, (x 1 + 2x 2) enheder af næringsstof S 2, (x 1 + 6x 2) enheder af næringsstof S 3. Da indholdet af næringsstoffer S 1, S 2 og S 3 i kosten skal være henholdsvis 9, 8 og 12 enheder, kan den økonomiske og matematiske model for problemet formuleres som følger:
Opret en daglig ration X = (x 1, x 2), der opfylder begrænsningssystemet:
og tilstand,
hvor funktionen tager minimumsværdien.
Formularer til PAP-optagelse
I ZLP er det nødvendigt at finde yderpunktet for den lineære objektivfunktion:
med restriktioner:
og betingelsen om ikke-negativitet
hvor a ij, b i, c j ( , ) er givet konstante værdier.
Sådan er ZLP skrevet ind generel form. Hvis systemet med restriktioner kun indeholder uligheder, præsenteres LLP i standard form. Kanonisk (hoved) ZLP-notationsformen er en notation, når systemet af begrænsninger kun indeholder ligheder. Så ovenstående ZLP'er er skrevet i standardform.
De generelle, standard- og kanoniske former for ZLP er ækvivalente i den forstand, at hver af dem kan omskrives i en anden form ved hjælp af simple transformationer. Det betyder, at hvis der er en måde at løse et af de specificerede problemer på, så kan den optimale plan for ethvert af problemerne fastlægges.
For at flytte fra en form for registrering af PLP til en anden, skal man være i stand til at bevæge sig fra ulighedsbegrænsninger til lighedsbegrænsninger og omvendt.
Ulighedsbegrænsningen (£) kan konverteres til en lighedsbegrænsning ved at tilføje en ekstra ikke-negativ variabel til dens venstre side, og ulighedsbegrænsningen (³) kan konverteres til en lighedsbegrænsning ved at trække en yderligere ikke-negativ variabel fra dens venstre side. Antallet af introducerede yderligere ikke-negative variabler er lig med antallet af transformerede ulighedsbegrænsninger.
Input yderligere variabler giver en vis økonomisk mening. Hvis begrænsningerne af det oprindelige PPP således afspejler forbruget og tilgængeligheden af ressourcer, så er værdien af den ekstra PPP-variabel i kanonisk form lig med volumen af den ubrugte tilsvarende ressource.
Eksempel 1. Skriv i den kanoniske form af ZLP:
med restriktioner:
Løsning.
Den objektive funktion forbliver uændret:
Systemet af uligheder omdannes til et system af ligheder:
Ved løsning af ZLP ved den grafiske metode kræves en overgang fra den kanoniske form til standardformularen.
For at bringe PPP til en standardform, brug Jordan-Gauss metode SLAU løsninger. I modsætning til Gauss-metoden, hvor systemets udvidede matrix reduceres til en trinvis form, dannes der i Jordan-Gauss-metoden en enhedsmatrix som en del af den udvidede matrix. Derfor er det ikke nødvendigt at bakke her.
Sådan konverteres den originale kanoniske ZLP til den tilsvarende standard ZLP:
a) i den udvidede matrix af begrænsningssystemet vælges et ikke-nul element a qp. Dette element kaldes eftergivende, og q er i rækken og pth kolonnen kaldes opløsningsrække og opløsningskolonne.
b) tilladelsesrækken omskrives uden ændring, og alle elementer i tilladelseskolonnen, undtagen den tilladelsende, erstattes med nuller. De resterende elementer i den udvidede matrix bestemmes ved hjælp af "rektangelreglen":
Lad os betragte fire elementer i den udvidede matrix: element a ij, der skal transformeres, opløse element a qp og elementer a i p og a qj. For at finde elementet a ij, skal man fra elementet a ij trække produktet af elementerne a i p og en qj placeret i modsatte hjørner af rektanglet, divideret med det opløsende element a qp:
c) samtidig udelukkes tilladte ukendte fra den objektive funktion. For at gøre dette skrives objektivfunktionens koefficienter i den sidste række af den udvidede matrix. Beregningerne tager højde for, at aktiveringselementet i sidste linje ikke kan vælges.
Eksempel 2. Reducer til standardform:
Løsning.
Ved at bruge Jordan-Gauss-metoden reducerer vi systemet af ligninger-begrænsninger i ZLP til et ækvivalent system af uligheder. Lad os vælge det tredje element i den første række som det løsende element:
Tallet -9 opnået i sidste kolonne i sidste række skal skrives ind i objektivfunktionen med modsat fortegn. Som et resultat af transformationer antager ZLP formen:
Fordi variable x 2 og x 3 er ikke-negative, og hvis vi kasserer dem, kan vi skrive ZLP i en symmetrisk form:
I den kanoniske form af ZLP kan den objektive funktion enten minimeres eller maksimeres. At gå fra at finde maksimum til at finde minimum eller omvendt, er det nok at ændre tegnene for koefficienterne for den objektive funktion: F 1 = - F. Det resulterende problem og den oprindelige ZLP har den samme optimale løsning, og værdierne af de objektive funktioner på denne løsning adskiller sig kun i skilt.
Egenskaber ved ZLP
1. Sættet af alle mulige løsninger på systemet af begrænsninger for et lineært programmeringsproblem er konveks.
Punktsættet kaldes konveks, hvis den indeholder hele segmentet, der forbinder to punkter i dette sæt.
Ifølge denne definition er polygonen i fig. 1a en konveks mængde, men polygonen i fig. 1b er det ikke, fordi segmentet MN mellem dets to punkter M og N hører ikke fuldstændig til denne polygon.
Ikke kun polygoner kan være konvekse mængder. Eksempler på konvekse sæt er cirkel, sektor, segment, terning, pyramide osv.
2. Hvis ZLP har en optimal løsning, så tager den lineære funktion en maksimal (minimum) værdi ved et af hjørnepunkterne i løsningspolyederet. Hvis en lineær funktion tager en maksimal (minimum) værdi ved mere end ét hjørnepunkt, så tager den den på ethvert punkt, der er en konveks lineær kombination af disse punkter.
Punkt X kaldes konveks lineær kombination punkt X 1, X 2,..., X n, hvis følgende betingelser er opfyldt:
X = α 1 X 1 + α 2 X 2 +…+ α n X n,
α j ≥ 0, Σα j = 1.
Det er klart, at i det specielle tilfælde for n = 2, er en konveks lineær kombination af to punkter det segment, der forbinder dem.
3. Hver tilladelig basisløsning af systemet af begrænsninger af den kanoniske ZLP svarer til et hjørnepunkt af opløsningspolyederet, og omvendt, til hvert hjørnepunkt af opløsningspolyederet svarer der en tilladt basisløsning.
Af de sidste to egenskaber følger det: hvis en ZLP har en optimal løsning, så falder den sammen med mindst en af dens tilladte basisløsninger.
Således skal ekstremummet af den lineære ZLP-funktion søges blandt det endelige antal af dens tilladte basisløsninger.
1.
2. vejledning til brug af mat. modeller i økonomi.
Matematiske modeller gør det muligt at bestemme de optimale værdier af ukendte parametre for økonomiske systemer, hvilket er vigtigt i beslutningsprocessen. Matematisk programmering giver netop det apparat, der gør det muligt at optimere processen med at udvælge de bedste varianter af planer i processen med ledelse i økonomiske systemer.
Anvendes i matematisk statistik, optimeringsmetoder, økonomiske metoder. kybernetik, eksperimentelle problemer.
Når man studerer komplekse processer og fænomener i økonomi, bruges modellering meget ofte - en meget specifik, specifik afspejling af egenskaberne ved det objekt, der undersøges. Dens essens er, at det fænomen, der undersøges, reproduceres under eksperimentelle forhold ved hjælp af en model på en anden tid og rumlig skala. En model er et specielt skabt objekt, ved hjælp af hvilket meget specifikke karakteristika ved det undersøgte system gengives med det formål at studere det. Matematisk modellering er den mest avancerede og samtidig effektive metode til at indhente information om det undersøgte objekt. Det er et stærkt værktøj til analyse i økonomi. Resultaterne af forskning ved hjælp af modeller vil være af praktisk interesse, når den konstruerede model er tilstrækkeligt tilstrækkelig til det pågældende fænomen, dvs. afspejler den virkelige situation godt nok.
2. matematisk programmering som videnskab, dens struktur. Optimeringsproblemer. Vanskeligheder med at anvende klassiske optimeringsmetoder ved løsning af økonomiske problemer.
Matematisk programmering er en gren af anvendt matematik, der udvikler teoretiske grundlag og metoder til løsning af ekstreme problemer.
Matematisk programmering omfatter en række sektioner, hvoraf de vigtigste er følgende:
1. Lineær programmering. Dette afsnit omfatter problemer, hvor ukendte variable indgår i matematiske relationer i første grad.
2. Ikke-lineær programmering. Dette afsnit indeholder problemer, hvor den objektive funktion og (eller) begrænsninger kan være ikke-lineære.
3. Dynamisk programmering. Dette afsnit indeholder opgaver, hvor løsningsprocessen kan opdeles i separate faser.
4. Heltalsprogrammering. Dette afsnit indeholder problemer, hvor ukendte variable kun kan have heltalsværdier.
5. Stokastisk programmering. Dette afsnit indeholder problemer, der indeholder tilfældige variabler i den objektive funktion eller begrænsninger.
6. Parametrisk programmering. Dette afsnit omfatter problemer, hvor koefficienterne for ukendte variable i den objektive funktion eller begrænsninger afhænger af visse parametre.
For at løse matematiske programmeringsproblemer er det vanskeligt at bruge klassiske metoder til at finde et ekstremum, fordi i matematiske programmeringsproblemer når objektivfunktionen sin ekstreme værdi ved grænsen af området for tilladte værdier af ukendte variable, og der findes ikke afledte ved grænsepunkterne. En fuldstændig søgning af tilladte punkter er umulig på grund af deres betydelige antal.
3. Begrebet en matematisk model, matematiktyper. modeller
Matematisk model er en abstraktion af et virkeligt fænomen eller proces skrevet i matematiske symboler og udtryk. Matematiske modeller for økonomiske processer og fænomener kaldes økonomisk-matematiske modeller
Modellerne er opdelt i:
1. lineær, hvor alle afhængigheder er beskrevet af lineære relationer,
2. ikke-lineær, hvor der er ikke-lineære forhold;
3. stokastisk, som tager højde for den tilfældige karakter af de processer, der undersøges,
4. deterministisk, som tager højde for gennemsnitsværdierne for alle parametre.
5. dynamisk modeller, hvor de undersøgte systemer betragtes i udvikling over flere perioder,
6. statisk, hvor tidsfaktoren ikke tages i betragtning.
7. optimering modeller, hvor valget træffes afhængigt af ekstremisering et eller andet kriterium
8. ikke-optimerende, hvor der ikke er noget optimalitetskriterium.
9. makromodeller(hele gården som helhed)
10. mikromodeller(individuelle forbindelser eller processer i økonomien).
Typer af matematiske modeller: lineære, ikke-lineære, kvadratiske, heltal, diskrete, parametriske, lineære fraktioner, dynamiske, stokastiske
4. Generel formulering af matematiske programmeringsproblemer.
Lad os overveje den generelle formulering af det matematiske programmeringsproblem.
Det generelle problem med matematisk programmering er at bestemme den optimale værdi af den objektive funktion, og værdierne af variablerne skal tilhøre et vist område af acceptable værdier. Matematisk udtrykkes bestemmelse af den optimale løsning ved at finde ekstremum (maks eller min) af en funktion af mange variable
Z = f (x1, x2, …, xn)
i en given række af ændringer i disse variable
gi (x1, x2,…, xn)Ribi (i = 1, 2,…, m),
hvor Ri er et af tegnene ≥, =, ≤.
5. Problemet med at optimere produktionsplanen. Økonomisk formulering og konstruktion af en matematisk problemmodel.
Økonomisk redegørelse:
Virksomheden producerer n typer af produkter, der bruger m typer af råvarer. For at producere en produktenhed bruges en strengt defineret mængde råmateriale af en eller anden type. Råvarer af hver type er begrænset på virksomheden. Virksomheden modtager en vis fortjeneste ved salg af en produktionsenhed. Det er nødvendigt at finde en produktionsplan, hvor virksomheden vil modtage det maksimale samlede overskud.
Matematisk udsagn:
Lad j være indekset for produkttypen j = 1, n
i – indeks for ressourcetype i = 1, m
og ij – råvareomkostninger jeg-th type produktion pr. outputenhed j-th type;
Аi – en given begrænsning på den tilgængelige mængde ressourcer af den i-te type;
Рj - fortjeneste modtaget fra salg af en produktenhed af den j. type;
xj – volumen af fremstillede produkter af den j. type.
z = Р1x 1 + Р2x 2 + … +Pnx n → max
а11x 1 + а12x 2 +…+ а1nx n ≤ A1
а21x 1 + а22x 2 +…+ а2nx n ≤ A2
…………………………….
a m1x1 + a m2x2 +…+ a m n x n ≤ Am
xj ≥ 0, j = 1, n
6. Kostproblem. Økonomisk formulering og konstruktion af en matematisk model af problemet.
Økonomisk redegørelse
På nogle bedrifter opfedes dyr. Anvendes til opfedning n fodertyper. Indholdet af næringsstoffer (calcium, fosfor osv.) i en foderenhed af hver type er kendt. For tilstrækkelig ernæring af dyr er det nødvendigt at indtage næringsstoffer ikke mindre end de angivne mængder. Prisen pr. enhed af hvert foder er kendt. Det er nødvendigt at bestemme dyrefodringsdiæten, hvor de samlede omkostninger til opfedning vil være minimale.
Matematisk udsagn:
j – fodertypeindeks, j = 1, n
i – næringsstoftypeindeks, i = 1, m
Аi – påkrævet dagligt forbrug af næringsstof af typen i;
Cj er prisen pr. foderenhed af den j. type.
Lad os introducere ukendte variable:
xj er den daglige mængde af fodring af dyr med den j. fodertype.
Med hensyn til den introducerede notation kan dette problem skrives som følger:
а11x1 + а12x2 +…+ а1nxn ≥ A1
а21x1 + а22x2 +…+ а2nxn ≥ A2
…………………………….
am1x1 + аm2x2 +…+ og mnxn ≥Am
xj ≥ 0, j = 1, n
7. Transportproblem . Økonomisk formulering og konstruktion af en matematisk model af problemet.
Økonomisk redegørelse :
Ledig m leverandører af homogene produkter og n forbrugere af disse produkter. Enhedsomkostningerne ved at levere en enhed produkt fra hver leverandør til hver forbruger er kendt. Leverandører har begrænsede lagre. Hver forbrugers produktbehov er også kendt.
Det er nødvendigt at fastlægge en plan for transport af produkter fra leverandører til forbrugere, hvor de samlede transportomkostninger vil være minimale.
Matematisk udsagn :
Lad os introducere betegnelserne for de angivne parametre:
j – forbrugerindeks, j = 1, n
i – leverandørindeks, i = 1, m
Аi – mængden af tilgængelige produkter fra den i-te leverandør;
Вj – mængden af efterspørgsel efter produkter fra den j. forbruger;
Cij er enhedsomkostningerne ved at transportere en enhed produkt fra den i-te leverandør til den j-te forbruger.
Lad os introducere ukendte variable:
xij er mængden af transport af produkter fra den i-te leverandør til den j-te forbruger.
z = С11x11 + С12x12 +…+С1nx1n + С21x21 +...+ Сm(n -1)xm (n-1) + Сmnxmn → min
Problembegrænsninger.
I. Fra hver leverandør kan du højst trække produkter tilbage end den tilgængelige mængde:
x11 + x12 +…+ x1n ≤ A1
x21 + x22 +…+ x2n ≤ A2 (2)
…………………….
xm1 + xm2 +…+ xmn ≤ Am
II. Den enkelte forbrugers behov for produkter skal opfyldes
x11 + x21 +…+ xm1 ≥B1
x12 + x22 +…+ xm2 ≥B2
……………………. (3)
x1n + x2n +…+ xmn ≥Bn
III. Ikke-negativitetstilstand: xij ≥0, i = 1, m ; j = 1, n
Det er ofte praktisk at skrive et matematisk udsagn i sammenklappet form:
, i = 1, m 
, j = 1, n
8. Problemet med at vælge opgaver eller opgaver. Økonomisk formulering og konstruktion af en matematisk model af problemet.
Økonomisk redegørelse :
Ledig n typer arbejde og n kunstnere. Hver af de optrædende kan udføre et hvilket som helst, men kun ét job. Omkostningerne ved at udføre hvert job af hver udøver er specificeret. Det er nødvendigt at tildele kunstnere til arbejdet på en sådan måde, at de samlede omkostninger ved at udføre arbejdet er minimale.
Matematisk udsagn .
Lad os introducere betegnelserne for de givne parametre.
i – arbejdsindeks, i = 1, m
j – indeks over udøvende kunstnere, j = 1, n
Cij er omkostningerne ved at udføre det i-te arbejde af den j-te entreprenør.
Lad os introducere ukendte variable. I denne opgave kan ukendte variable kun have to værdier: 0 eller 1. Sådanne variable kaldes nul.
1 - hvis den j. udøver er tildelt det i-te job;
0 - ellers.
Med hensyn til den introducerede notation vil dette problem blive skrevet som følger:
z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n -1)x(n-1)(n-1) + Сnnxnn → min
I gruppe af restriktioner.
Der bør kun tildeles én kunstner til hvert job:
x11 + x12 +…+ x1n = 1
x21 + x22 +…+ x2n = 1
……………………..
xn1 + xn2 +…+ xnn = 1
II. gruppe af restriktioner.
Hver kunstner kan kun udføre ét job:
x11 + x21 +…+ xn1 = 1
x12 + x22 +…+ xn2 = 1
……………………..
x1n + x2n +…+ xnn = 1
x ij = (0,1) i = 1, n; j = 1, n
9. Problem med at skære materialer. Økonomisk formulering og konstruktion af en matematisk model af problemet.
Økonomisk redegørelse .
Det originale materiale af samme størrelse leveres til skæring. Det skal skæres i stykker af en given størrelse i en given mængde, så det samlede spild bliver minimalt.
Matematisk udsagn .
Lad os introducere følgende notation:
i – emneindeks,
Аi – påkrævet antal emner af den i-te type;
j – indeks over skæremuligheder,
Сj – affaldsstørrelse ved skæring af en enhed af kildemateriale i henhold til mulighed j;
og ij er antallet af emner af den i-te type ved skæring af en enhed af kildemateriale i henhold til mulighed j.
Lad os introducere notationen for ukendte variable.
xj er mængden af råmateriale skåret i henhold til mulighed j.
Med hensyn til den introducerede notation vil dette problem blive skrevet som følger:
z = С1x1 + С2x2 + … +Сnxn → min
а11x1 + а12x2 +…+ а1nxn = A1
а21x1 + а22x2 +…+ а2nxn = A2
…………………………….
am1x1 + аm2x2 +…+ аmnxn = Am
xj ≥ 0, j = 1, n
Brugen af matematiske modeller giver mulighed for at spare råmaterialer op til 20 %.
Den matematiske skæremodel er bygget i to trin.
I det første trin konstrueres skæremuligheder, som et resultat af, at værdierne af antallet af muligheder n, antallet af emner af hver type opnået med forskellige skæremuligheder (aij), samt spildværdierne (Cj) bestemmes.
Konstruktionen af skæremuligheder for en enhed af kildemateriale udføres i form af følgende tabel:
| Mulighed nr. |
Emne i1 |
Emne i2 |
Arbejdsemne im |
Emnerne er arrangeret i rækkefølge efter ikke-stigende størrelse. Konstruktionen af muligheder udføres ved hjælp af den udtømmende søgemetode.
10. Generel form for LP-problemmodellen og dens funktioner
Den generelle form for ZLP er:
z = С1x1 + … + Сnxn max (min)
a11 X1 + a12 X2 + … + a1n Xn R1 a1
a21 X1 + a22 X2 + … + a2n Xn R2 a2
………………………………………………….
am1 X1 + am2 X2 +…+ amnxn Rm am
xj ≥ 0, j = 1, k, k ≤ n
I generel form betyder hvert symbol R1, R2,..., Rm et af tegnene: ≥, = eller ≤.
Den generelle form for LP-problemmodellen har følgende funktioner.
1. Systemet af restriktioner præsenteres i form af ligninger (rigide forhold) og uligheder (ikke-rigide forhold).
2. Ikke-negativitetsbetingelser er ikke pålagt alle variabler
3. Den objektive funktion har tendens til enten et maksimum eller et minimum.
11. Standardform for LP-problemmodellen og dens funktioner
Standardformularen er som følger.
Find maksimum eller minimum af objektivfunktionen z:
z = С1x1 + … + Сnxn → max (min) (1)
Underlagt følgende begrænsninger:
а11 Х1 + а12 Х2 + … + а1n Хn ≤ а1
a21 X1 + a22 X2 + … + a2n Xn ≤ a2
…………………………………………..
am1 X1 + am2 X2 +… + amn Xn ≥ am
xj ≥ 0, j = 1, k, k ≤ n
Funktionerne i standardformularen for LP-problemmodellen er som følger:
1. begrænsningssystemet præsenteres i form af uligheder (ikke-rigide betingelser)
2. ikke-negativitetsbetingelser er pålagt alle variabler
3. objektivfunktionen har en tendens til enten max eller min
12. Kanonisk form af LP-problemmodellen og dens funktioner
Den kanoniske form er:
Find minimum af målfunktionen z:
z = С1x1 + … + Сnxn → min
Underlagt følgende begrænsninger:
a11 X1 + a12 X2 + … + a1n Xn = a1
a21 X1 + a22 X2 + … + a2nxn = a2
…………………………
am1x1 + am2 X2 +… + amn Xn = am
Xj ≥0, j = 1, n
Funktionerne i den kanoniske form er som følger:
1. Systemet af restriktioner præsenteres i form af ligninger (strenge betingelser).
2. Ikke-negativitetsbetingelser pålægges alle variabler
3. Den objektive funktion har tendens til
I nogle kilder tenderer den objektive funktion af LP-problemet, præsenteret i kanonisk form, til et maksimum. Dette gøres for at gøre det nemmere at løse problemet ved hjælp af en algoritme designet til at maksimere den objektive funktion.
13. Mulig, tilladelig, optimal referenceplan for problemet, ODZ for LP-problemet
Definition 1. Værdierne af de ukendte variabler, der opfylder alle begrænsningerne for et lineært programmeringsproblem, kaldes acceptabelt værdier af variable eller planer .
Definition 2. Sættet af alle planer for et lineært programmeringsproblem kaldes domænet af tilladte værdier af variable ( ODZ ).
Definition 3. Planen for et lineært programmeringsproblem, hvor objektivfunktionen tager minimum (eller maksimum) værdi på ODZ kaldes optimal .
14. Typer af registreringer af LP-problemer: udvidet, sammenklappet, matrix, vektor.
Modeller af LP-problemer kan skrives i forskellige former.
1. Udvidet visning af modelposten
Z = c1 X1 + c2 X2 + … + cn Xn → min
a11 X1 + a12 X2 + … + a1n Xn = a1,
a21 X1 + a22 X2 + … + a2n Xn = a2,
……………………………………………
a m1 X1 + am2 X2 + … + amn Xn = am,
Xj ≥ 0, j = 1, n.
2. Skjult visning:
,
Xj ≥ 0, j = 1, n.
3. Model af LP-problemet i matrixform:
X ≥ 0
Hvor 
a11 a12 … a1n X1 a1
A= a21 a22 … a2n, X= X2, A0 = a2
… … … … … …
amn 1 am2 … amn X3 am
4. Model af LP-problemet i vektorform:
Hvor
Х1 a11 a12 a1n a1
X2, a21, a22, a2n, a2
… … … … …
Хn am 1 am 2 am 2 am
15. Overgang fra den standard og generelle form for LP-problemer til den kanoniske. Kommunikationssætning
For at skifte fra en generel eller standardform til en kanonisk, bruges følgende teknikker.
1. Konvertering af variabler. Hvis en variabel Xk er ikke-positiv (Xk ≤ 0), så introduceres en ny variabel Xk ", så Xk " = –Xk. Det er indlysende, at Xk " ≥ 0. Efter dette, i hver begrænsning og objektiv funktion, erstattes variablen Xk med [ – Xk "].
Hvis en variabel Xt kan antage en hvilken som helst værdi, så erstattes den af forskellen mellem to ikke-negative variable Xt' og Xt'', dvs. det antages, at Xt = Xt' – Xt'', hvor Xt' 0 ≥ og Xt'' ≥ 0.
2. Transformation af begrænsninger. Hvis nogen af begrænsningerne i modellen har form af en ulighed, så konverteres den til en lighed ved at addere (hvis uligheden er af typen ≤) eller subtrahere (hvis uligheden er af typen ≥) fra dens venstre side. Disse variabler kaldes balancevariable. Balancevariable indgår i objektivfunktionen med nulkoefficienter. Balancevariablen antager indeksværdien sekventielt efter de eksisterende. Hvis systemet af restriktioner for eksempel har 5 variable, så vil den første balancevariabel være X6, og den anden vil være X7 osv.
16. Overgang fra ZLP-modellens kanoniske form til standardmodellen
For at flytte fra den kanoniske form til den standard, kan du hver af
ligninger, der skal erstattes af et system af uligheder:
En anden måde er at reducere ligningssystemet til en speciel form og yderligere eliminere nogle variable.
Ved hjælp af Jordan-Gauss-metoden vælger vi den grundlæggende variabel i hver ligning. Denne udvælgelse udføres ved hjælp af ækvivalente (elementære) Gauss-transformationer. Disse omfatter:
a) at gange enhver ligning med en anden konstant end nul;
b) at lægge enhver anden ligning til en hvilken som helst ligning ganget med en konstant.
Før transformation er det praktisk at skrive det originale system af lineære ligninger i form af en matrix eller tabel:
Vi skriver opgaven ned i en standardform.
17. Konceptet med et halvt plan hyperplan, støtte hyperplan.
18. Geometrisk fortolkning af systemet af begrænsninger og objektiv funktion til LP-problemer
19. Konveks sæt: ekstreme (hjørne)punkter på sættet. Konveks polyeder
Definition Et sæt M kaldes konveks, hvis det sammen med to punkter, der hører til dette sæt, også indeholder et segment, der forbinder dem.
 |
Konveks sæt
Definition Et punkt x i et sæt M kaldes et hjørne eller et ekstremt punkt, hvis det ikke er internt i et segment, der helt tilhører dette sæt.
Sætning 1. Ethvert punkt på et segment kan repræsenteres som en konveks kombination af dets hjørnepunkter.
x = λ 1 A + λ 2 V
λ 1, λ 2 ≥ 0 konveks kombination af punkter i hjørnepunkterne A og B
λ 1 + λ 2 = 1
Sætning 2. Ethvert punkt i et konveks lukket sæt kan repræsenteres som en konveks kombination af dets hjørnepunkter.
20. Algoritme af den grafiske metode til løsning af LP-problemer
1. Det kontrolleres om den originale ZLP er i standardform, hvis ikke, så skal problemet konverteres til standardform.
2. Antallet af ukendte variable kontrolleres. Hvis dette tal er mere end tre, kan problemet ikke løses grafisk (der er andre effektive metoder til at løse sådanne problemer).
3. Rækken af tilladte værdier af variabler for ZLP er konstrueret.
4. En guidevektor er ved at blive konstrueret c .
5. Den indledende isocoel trækkes gennem ODZ'en (vinkelret på retningsvektoren).
6. Den indledende isocoel bevæges mentalt i retning af vektoren c, hvis den maksimale værdi af den objektive funktion er bestemt, eller i den modsatte retning, hvis dens minimumsværdi er bestemt, indtil isocoel bliver reference til ODZ. Skæringspunkterne for referenceisocoel og ODZ vil være de optimale punkter for problemet.
7. For at bestemme koordinaterne for det optimale punkt er det nødvendigt at løse et system af tilsvarende lineære ligninger.
8. For at finde den optimale værdi af objektivfunktionen er det nødvendigt at erstatte de optimale værdier af variablerne i objektivfunktionen og beregne dens værdi.
20. grafisk algoritme metode til at løse LP-problemer
Algoritme for den grafiske metode.
1. Ved sekventielt at konstruere hver af betingelserne for systemet af begrænsninger af problemet udføres konstruktionen af ODZ.
2. Retningsvektoren C er konstrueret ved hjælp af koefficienterne for de objektive funktionsvariable.
3. Den oprindelige isocoel tegnes vinkelret på retningsvektoren gennem koordinaternes oprindelse.
4. Den initiale isocoel bevæges mentalt i retning af stigende værdier af vektoren C, hvis den maksimale værdi af den objektive funktion er bestemt, eller i den modsatte retning, hvis dens minimumværdi er bestemt, indtil isocoel bliver reference til ODZ. Skæringspunkterne for referenceisocoel og ODZ vil være de optimale punkter for problemet.
5. For at bestemme koordinaterne for det optimale punkt er det nødvendigt at løse et system af tilsvarende lineære ligninger for de forhold, hvor det optimale punkt er placeret.
6. For at finde den optimale værdi af objektivfunktionen er det nødvendigt at erstatte koordinaterne for det optimale punkt i objektivfunktionen og beregne dens værdi.
23. teoremer om rækkevidden af tilladte værdier for LP-problemet og om målfunktionen
ODZ-sætning. Området med mulige løsninger på LP-problemet er et konveks sæt (lukket og afgrænset i n-dimensionelt rum)
Sætning 2. Om den objektive funktion af det lineære programmeringsproblem.
ZLP-objektivets funktion tager sin optimale værdi ved et af hjørnepunkterne i området med variablenes tilladte værdier. Hvis objektivfunktionen tager sin optimale værdi ved flere hjørnepunkter, så tager den samme værdi på ethvert punkt, der er en konveks kombination af disse hjørnepunkter.
24. Sætning om hjørnepunktet. Tilstrækkelig og nødvendig stand
25. Følger fra sætningen om egenskaberne ved løsninger til LP-problemer og konklusioner. Konceptet med en referenceplan.
Følger fra sætningerne.
Definition. Plan = (x1,x2,…,xn), hvis positive koordinater svarer til lineært uafhængige vektorer, kaldes grundlæggende plan for ZLP .
Konsekvens 1. Referenceplanen har højst m positive koordinater.
Hvis den har præcis m positive koordinater, så kaldes en sådan støtteplan ikke-degenereret, ellers degenereret.
Konsekvens 2. Hvert hjørnepunkt i ODZ er en referenceplan.
27. Simplexmetodens algoritme.
Når du løser LP-problemer ved hjælp af simplex-metoden, er det nødvendigt at udføre følgende rækkefølge af handlinger.
1. Det kontrolleres, om LP-problemet er i kanonisk form. Hvis ikke, så er det nødvendigt at konvertere den originale model til den kanoniske form.
2. Den oprindelige referenceplan og værdien af målfunktionen for denne referenceplan identificeres.
3. Den indledende simplex-tabel er konstrueret.
4. Værdierne af optimalitetsestimaterne i indekslinjen kontrolleres. Hvis der ikke er positive estimater, skrives den optimale løsning ud, og algoritmen afslutter sit arbejde. I modsat fald udføres punkt 5.
5. I grundlaget indføres en vektor, der svarer til det største positive skøn. Denne kolonne kaldes aktiveringskolonnen.
6. Ud fra grundlaget udledes en vektor, som svarer til simpleksforholdet beregnet med formlen 0< Ө ≤ . Данная строка называется разрешающей строкой.
7. Et nyt simpleksbord er konstrueret. Kolonne B og C B modificeres i overensstemmelse hermed. Resten af tabellen er udfyldt fra den forrige ved hjælp af Gauss-transformationer, hvor indeksrækken betragtes som en m+1 række og også transformeret ved hjælp af Gauss-transformationer. Lad os gå videre til trin 4 i denne algoritme.
Efter at have konstrueret hver tabel, kan du kontrollere rigtigheden af beregningerne ved hjælp af formlerne til beregning af estimaterne givet i det foregående afsnit.
28. udvælgelse af grundlag og opbygning af en indledende referenceplan ved problemløsning ved brug af simpleksmetoden.
29. Simplex tabeller, udfylde dem. Formler til beregning af indekslinjekoefficienter.
30 . Optimitetssætningen for planen af et lineært programmeringsproblem er en følge af optimalitetsvurderingssætningen, når man løser problemer ved hjælp af simpleksmetoden.
Sætning 1: Hvis for en vektor  j i systemet
X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + … + a 1 n X n = a 1
X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n = a 2
…………………………………………………..
X m + а mn +1 X m +1 + а mn +2 X m +2 + … + а mn X n = a m
Hvis relationen Z j – c j > 0 er opfyldt, så er plan X B0 ikke optimal, og vi kan flytte til plan X B1, således at Z (X B1) ≤ Z (X B0).
Her er Z j = (C, Ā j) skalarproduktet af vektorer.
С – vektor bestående af koefficienter for de grundlæggende variable i objektivfunktionen Z
Ā j er en vektor bestående af ekspansionskoefficienter af den tilsvarende vektor til basisvektorer.
c j – koefficient for objektivfunktionen Z for variabel X j
Følge fra teoremer: Hvis for alle vektorer Ā 1 , Ā 2 , …, Ā n af en referenceplan X er relationen Z j – c j opfyldt< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.
Således gør sætningen og følgen det muligt at afgøre, om den næste referenceplan er optimal, og hvis ikke, så er det nødvendigt at flytte til en anden referenceplan, hvor værdien af den objektive funktion vil være mindre.
Kommentar. Sætningen og følgen antager, at problemet er i kanonisk form med den objektive funktion som minimum. Simplexmetoden kan dog også bruges til maksimalt at løse problemer med en objektiv funktion. I dette tilfælde, når man analyserer værdierne af estimaterne, bruges deres modsatte betydning, det vil sige, at planen vil være optimal, hvis alle optimalitetsestimater ikke er negative (positive eller negative).
31. Udvælgelse af vektoren indført i basis og output fra basis. Enkelt forhold.
For at flytte til en ny referenceplan skal du bruge en af de frie vektorer 
gå ind i grundlaget og udlæse nogle af basisvektorerne. For at introducere det i grundlaget vælger vi en vektor, der har mindst én positiv koordinat. Lad en sådan vektor være vektor A m+1.
Henfald -
hhv. vektor, kat vil være en referenceplan, hvis dens koordinater er ikke-negative, og antallet af positive koordinater er lig med m.
Koordinaterne for X1 vektoren skal være ikke-negative, dvs. .
Hvis 
, så vil denne koordinat være ikke-negativ.
Lad minimum i forhold (5) opnås ved i = 1, så hvis vi tager
derefter den første koordinat af vektor 1 x bliver lig med nul.
Relation (6) kaldes simpleks forhold. Så vi er flyttet fra den oprindelige referenceplan 0 x(grundlæggende vektorer A1, A2, ... Am) til referenceplan 1 x(basisvektorer A2,A3,…,Am,Am+1).
32. tilladelige element i tabellen, dets valg. Reglen for komplette Jordan-undtagelser for genberegning af en simplekstabel.
33. "firkant"-reglen for genberegning af simplekstabellen
34. Et tegn på det unikke ved en optimal plan, et sæt af optimale planer og fraværet af en optimal plan ved løsning af et LP-problem ved hjælp af simpleksmetoden.
Ved løsning af problemer ved hjælp af simplex-metoden er følgende typer optimale løsninger mulige:
1. Unikhed . Hvis estimaterne af alle frie vektorer er strengt negative, så er den resulterende referenceplan optimal og unik. (se eksempel i forrige afsnit).
2. Alternativt optimum (sæt af optimale løsninger).
Hvis der blandt de ikke-positive estimater af frie vektorer er mindst et nul, vil den resulterende referenceplan være optimal, men ikke den eneste. I dette tilfælde kan du gå videre til andre støtteplaner (vektorer, der svarer til nul estimater, indføres i grundlaget) og derefter skrive den generelle optimale løsning i form af en konveks kombination af de opnåede optimale støtteplaner.
3. ZLP har ikke en optimal løsning, da objektivfunktionen ikke er afgrænset nedefra . Hvis der er et positivt estimat i simplex-tabellen, og alle elementer i denne kolonne er negative og nul, så kan denne vektor indtastes i grundlaget. Ingen af basisvektorerne kan dog udledes fra basis. Det følger heraf, at et yderligere fald i den objektive funktion er mulig ved overgang til en ikke-referenceplan.
4. ZLP har ikke en optimal løsning, da begrænsningssystemet er modstridende. Da der ved løsning af en ZLP ved hjælp af den sædvanlige simplex-metode skal være en indledende referenceplan, er systemet af lineære ligninger bestemt ikke inkonsekvent. Et sådant tilfælde kan derfor ikke forekomme, når der løses ved den sædvanlige simpleksmetode.
5. Hvis ODZ består af et punkt, så er løsningen på et sådant problem triviel og kan opnås uden at bruge simpleksmetoden.
35. I hvilke tilfælde anvendes den kunstige basismetode?
kunstig.
36. Konstruktion af M-problemet i den kunstige basismetode
Hvis det lineære programmeringsproblem er i kanonisk form, er basisvariablerne imidlertid ikke til stede i alle ligninger, dvs. det oprindelige referencedesign mangler. I dette tilfælde, i de ligninger, hvor der ikke er nogen grundlæggende variable, er det nødvendigt at tilføje en ikke-negativ variabel med en koefficient på +1. En sådan variabel kaldes kunstig.
Der skal tilføjes en kunstig variabel til objektivfunktionen med et meget stort positivt tal (da objektivfunktionen er at finde minimum). Dette tal er angivet med det latinske bogstav M. Det kan betragtes som lig med +∞. I denne forbindelse kaldes den kunstige basismetode undertiden M-metoden. Denne transformation af det oprindelige problem kaldes konstruktionen af et udvidet problem. Hvis du løser et problem med en objektiv funktion for at finde en kunstig variabel, skal du tilføje den til objektivfunktionen med et meget stort positivt tal (da objektivfunktionen er at finde minimum). Dette tal er angivet med det latinske bogstav M. Det kan betragtes som lig med +∞. I denne forbindelse kaldes den kunstige basismetode undertiden M-metoden. Denne transformation af det oprindelige problem kaldes konstruktionen af et udvidet problem. Hvis et problem løses med en objektiv funktion for at finde maksimum, så indgår kunstige variable i objektivfunktionen med en koefficient –M.
I den udvidede opgave har vi således et referencedesign (selvom nogle af basisvariablerne er kunstige).
Den indledende simplex-tabel er konstrueret.
37. at konstruere en indekslinje i den kunstige basismetode
En indledende simplextabel er konstrueret, hvor indeksrækken er opdelt i to rækker, da estimaterne består af to led. Evalueringsleddet uden M skrives i den øverste linje, og i nederste linje skrives koefficienterne for M. Estimatets fortegn bestemmes af fortegnet for koefficienten for M, uanset værdien og fortegn for leddet uden M, da M er et meget stort positivt tal.
For at bestemme vektoren, der indføres i grundlaget, er det således nødvendigt at analysere den nedre indekslinje. Hvis en kunstig vektor udledes af grundlaget, skal den tilsvarende kolonne i efterfølgende simplekstabeller ikke beregnes, hvis der ikke er behov for at få en løsning på det dobbelte problem (se næste emne).
Efter at alle kunstige vektorer er blevet udledt fra basis, vil den nederste række have alle nul-elementer undtagen de scorer, der svarer til de kunstige vektorer. De vil være lig med –1. En sådan linje kan fjernes fra overvejelse, og yderligere løsning kan udføres ved hjælp af den sædvanlige simpleksmetode, hvis der ikke er behov for at opnå en løsning på det dobbelte problem (se næste emne).
38. Optimalitetskriterium i den kunstige basismetode. Tegnet på at konstruere den oprindelige referenceplan for det oprindelige problem.
39. Algoritme for dual simplex-metoden
Algoritme for dual simplex-metoden:
1. udfyld den første simplex-tabel på sædvanlig måde uden at være opmærksom på de frie vilkårs tegn. Det menes, at et sådant problem skal have et indledende enhedsgrundlag.
2. Vælg ledelinjen i henhold til det største i absolutte værdi negative element i kolonnen med frie led A0
3. Vælg guidekolonnen i henhold til det mindste absolutte værdiforhold mellem elementerne i indeksrækken og de negative elementer i guiderækken.
4. Genberegn simplekstabellen ved at bruge reglen om komplette Jordan-elimineringer
5. tjek den modtagne plan for antagelighed. Et tegn på at opnå en acceptabel referenceplan er fraværet af negative elementer i kolonne A0. Hvis der er negative elementer i kolonne A0, så gå til det andet punkt. Hvis de ikke er der, fortsætter de med at løse det resulterende problem på den sædvanlige måde.
6. Et tegn på at opnå en optimal løsning ved brug af dual simplex-metoden er optimalitetskriteriet for den konventionelle simplex-metode.
41. Åbne og lukkede transportmodeller. Overgang fra en åben transportmodel til en lukket.
Typer af transportopgaver.
Ledig m leverandører af homogene produkter med kendte varelagre og n forbrugere af disse produkter med givne mængder af behov. Enhedsomkostningerne ved transport er også kendte.
Hvis summen af mængderne af produktbeholdninger er lig med mængden af behov hos alle forbrugere, kaldes dette problem lukket transportproblem
(dvs. hvis ∑ Ai = ∑ Bj), ellers kaldes transportproblemet åben. For at løse et transportproblem er det nødvendigt, at det lukkes.
Et åbent transportproblem kan konverteres til et lukket som følger.
Lad ∑Ai > ∑Bj. I dette tilfælde er det nødvendigt at indføre en fiktiv n+1-forbruger med behovsmængden ∑Ai – ∑Bj.Enhedsomkostningerne ved transport fra leverandører til den fiktive forbruger antages at være lig med 0, da en sådan transport i virkeligheden vil ikke blive udført, og en del af produkterne forbliver hos leverandørerne.
Hvis ∑Bj > ∑Ai . I dette tilfælde er det nødvendigt at indtaste en fiktiv m+1-leverandør med lagervolumen ∑Bj – ∑Ai . Enhedsomkostningerne ved transport fra den fiktive leverandør til forbrugerne antages at være lig med 0, da en sådan transport i realiteten ikke vil blive udført, og forbrugerne ikke vil modtage nogle af produkterne.
42. Metoder til at konstruere startfordelingen i transportproblemet: nordvesthjørnemetoden og metoden for det mindste element i matricen.
Nordvestlig metode til at konstruere en referenceplan. Ifølge denne metode begynder dannelsen af transportværdier fra nordvest. hjørne af bordet, dvs. fra celle x11. Ifølge denne metode distribueres den første leverandørs varer først. Desuden tilfredsstiller den første leverandør først den første forbruger så meget som muligt. Så hvis leverandøren stadig har varerne,
Metode for det mindste element i en matrix.
Essensen af metoden er, at den maksimalt mulige forsyning altid placeres i den celle, der svarer til den laveste tarif i matricen.
Først laver vi mærker (for eksempel med et ▼-tegn) i de celler i linjerne, hvor den laveste pris for linjen er observeret. Derefter går vi rundt i tabellen kolonne for kolonne og laver de samme noter i de celler, der indeholder den laveste pris i kolonnerne.
Yderligere fordeling foretages først, så meget som muligt, i celler med to mærker, derefter med et, og derefter rebalanceres opgaven til (m + n – 1) fyldninger. Vi organiserer fyldningerne ved at bevæge os gennem bordet fra venstre mod højre og fra top til bund.
43. Egenskaber ved transportproblemer
Transportproblemet har nogle egenskaber, som kan afspejles i følgende sætninger.
Sætning 1. Et lukket transportproblem har altid en løsning.
Sætning 2. Hvis mængderne af produktbeholdninger og mængder af behov er heltal, så vil løsningen på transportproblemet også være heltal.
Sætning 3. systemet af begrænsninger for et lukket transportproblem er altid lineært afhængigt.
Af denne sætning følger det, at fordelingen af et lukket transportproblem altid har m + n – 1 grundvariable og (m – 1) (n – 1) fritidsvariable.
44. Degenereret fordeling i transportproblemer, at slippe af med degeneration. Overstreget kombination.
Fordelingen kaldes degenereret, hvis antallet af celler er mindre end m + n – 1.
45. Optimalitetssætninger for transportproblemet.
Sætning. Hvis for nogle fordeling af transportproblemet du
betingelser er opfyldt:
EN). ui+vj = сij for besatte celler
b) ui+vj ≤ сij, for frie celler,
så er denne fordeling optimal.
Størrelserne ui kaldes rækkepotentialer, og størrelserne vj kaldes kolonnepotentialer.
46. Potentialer og metoder til deres beregning.
For at finde potentialerne for rækker og kolonner, brug følgende ræsonnement, baseret på betingelse a) i optimalitetssætningen.
Antallet af ligninger baseret på denne betingelse er lig med m + n – 1, og antallet af ukendte ui og vj er lig med m + n. At. antallet af variable er større end antallet af ligninger, og alle ligninger er lineært uafhængige. Løsningen på sådan et system af lineære ligninger er usikker, så et af potentialerne skal tildeles en hvilken som helst værdi. I praksis er ui = 0. Der opnås et system af m + n – 1 ligninger med m + n – 1 ukendte variable. Dette system kan løses ved enhver metode. I praksis, for at beregne potentialer, overvejes besatte celler, for hvilke et af deres potentialer er kendt, og baseret på betingelse a) i sætningen beregnes værdierne af de resterende ukendte potentialer.
47. beregning af optimalitetsskøn for fordelingen af transportopgaver og optimalitetskriterium.
Ud fra relation b) i sætningen kan vi skrive følgende formel til beregning af estimater: δ ij= ui +vj – сij. For at sikre, at estimater ikke forveksles med transportmængder, er de (estimater) omgivet af cirkler.
Optimalitetsestimater i frie celler af TZ repræsenterer et optimalitetskriterium, ved hjælp af hvilket fordelingen kontrolleres for optimalitet. Hvis scoren for alle frie celler er mindre end eller lig med nul, så er denne fordeling optimal.
48. omfordeling af forsyninger i transportproblemet
Hvis fordelingen ikke er optimal, så er det nødvendigt at omfordele forsyninger.
For omfordeling konstrueres en genberegningscyklus. Cellen med den højeste positive score vælges som cellen. Denne celle er markeret med et "+"-tegn, det vil sige, at en vis mængde levering skal skrives ind i den. Men så vil balancen i denne kolonne blive forstyrret, derfor skal en af de besatte celler i denne kolonne markeres med et "-"-tegn, det vil sige, at forsyningsvolumen skal reduceres med samme mængde. Men så vil balancen for denne linje ændre sig, derfor skal en besat celle på denne linje markeres med et "+"-tegn. Denne proces fortsætter, indtil "-"-tegnet er placeret på linjen, hvor den oprindelige celle var placeret.
For enhver fri celle er der en genberegningscyklus og desuden en unik.
49. omfordelingskæder, deres typer.
Lad den undersøgte transportplan ikke være optimal, dvs. der er positive relative skøn. Derefter tages en ugunstig celle (en af de ugunstige), og der bygges en genberegningscyklus til den, hvorefter den planlagte transport så omfordeles. Cyklusen er konstrueret i form af en brudt lukket linje, hvis segmenter løber enten langs søjlen eller langs linjen. I et af hjørnerne af den stiplede linje er der en ugunstig celle, der kappes om produktet, og i de andre hjørner fyldes cellerne, dvs. Når vi konstruerer en cyklus, starter vi fra kandidatcellen og vender tilbage til den langs en stiplet linje, men vi kan kun lave drejninger i udfyldte celler (svarende til de grundlæggende variable). Lad en ugunstig celle gøre krav på produkt Q. For at undgå ubalance i tabellen er det nødvendigt at skiftes til overgange gennem cyklussen
tilføje og trække Q til eksisterende transport. Da der er et lige antal vinkler, vil Q i halvdelen af cellerne blive tilføjet, og i den anden halvdel vil det blive trukket fra. Gennemgangen af cyklussen begynder med uret eller mod uret fra den konkurrerende celle, hvor produktet Q placeres der, derefter trækkes Q fra den tilstødende celle, tilføjes derefter osv. Værdien af selve Q vælges således, at en af cellerne tømmes, men ingen af forsyningerne bliver negative.
For at gøre dette skal Q vælges lig med den mindste minuend af de celler, hvori Q trækkes fra. I den følgende fig. 7.1 og 7.2 viser vi eksempler på sløjfer og regnereglen.
I dette tilfælde tømmes to celler. Men det er nødvendigt, at kun én celle bliver gensidigt tom. De gør dette: en af tømmecellerne gøres tom i den nye tabel, og der sættes et nul i den anden tømmecelle. Denne celle betragtes som grundlæggende (udfyldt) i den nye tabel.
50. Valg af omfordelingsvolumen.
Bestemmelse af mængden af transporterede produkter. Når vi bestemmer mængden af produkter, der flyttes gennem genberegningscyklussen, skal vi gå ud fra følgende to overvejelser:
a) efter transformationen bør tabelcellerne ikke indeholde negative tal;
b) en af de besatte celler skal blive fri.
For at disse betingelser skal være opfyldt, er det nødvendigt at vælge volumen af transporterede produkter som følger: θ=min (хij) -, hvor (хij) er transportvolumen fra cellerne i genberegningscyklussen markeret med tegnet "-".
θ = min(20;30)=20
θ lægges til værdierne af celler markeret med et "+"-tegn. θ trækkes fra værdierne af celler markeret med et "-"-tegn. Forsyningsværdien af de resterende celler omskrives uden ændringer. Som et resultat får vi følgende tabel.
53. Algoritme for den potentielle metode.
Algoritme:
1. Tjek om opgaven er lig med 
hvis ikke, så introduceres en fiktiv leverandør eller forbruger i problemet
2. Problemstillingens tilstand skrives i form af en transporttabel
3. Den indledende referenceplan bygges
4. Potentialer for indlæg og forbrugere bestemmes
5. Fri cellescore beregnes. Hvis ikke alle er negative, er planen optimal, og du skal skrive svaret ned. Transportmatrix X og bestemme størrelsen af transportomkostninger. Hvis planen ikke er optimal, det vil sige, at der er negative estimater blandt estimaterne, så vælg en lovende celle med den største negative værdi. vurdering og gå videre i størrelse til den næste.
6. Indlæs en lovende celle. Formatering af en ny referenceplan i form af en transp.tabel. Gå til punkt 4.
54. Regnskab for omkostninger til produktion og transport af produkter. Transportproblem med forsyningsrestriktioner.
Når du løser nogle problemer, er det nødvendigt at tage hensyn til omkostningerne ikke kun ved transport af last, men også til produktion af transporterede produkter. For at gøre dette, i matrix transp. opgaver
Hvor Cij ' er de reducerede omkostninger ved at producere en outputenhed.
Cij "er omkostningerne ved at transportere en enhed produkt.
Problemer med leveringsforbud.
I nogle situationer kan produkter ikke transporteres ad nogen rute.
For at gøre dette indtastes der i matricen for transportopgaven, hvorigennem transport er forbudt, en prohibitiv tarif M. Herefter løses problemet på sædvanlig måde, dog vil denne celle altid svare til en negativ score for cellen.
55. under hensyntagen til begrænsninger på ruternes kapacitet, under hensyntagen til den obligatoriske karakter af visse leverancer i transportproblemet.
under hensyntagen til rutekapacitetsbegrænsninger.
I nogle transportopgaver er der på nogle ruter installeret mindre kapacitet end nødvendigt for at tilfredsstille forbrugsstedets efterspørgsel.
under hensyntagen til nødvendigheden af visse leverancer i transportproblemet.
I nogle tilfælde kræver problemet, at der for eksempel langs Ak Bs-ruten skal leveres en mængde A-enheder. I dette tilfælde tages den obligatoriske levering i betragtning fra produktionsmængden af punkt A og mængden S Bs, og problemet er løst med hensyn til leveringsmuligheden. Efter at have opnået den optimale løsning, tilføjes tilførslen nødvendigvis til mængden af Ak B'er, der står i buret.
56. Mulige konklusioner med økonomisk fortolkning af optimal allokering til åbne transportproblemer.
Når man opnår den optimale fordeling, er det nødvendigt at vende tilbage til det oprindelige problem og træffe de passende økonomiske beslutninger. konklusioner. De er som følger:
1. Hvis der indføres et forbrugspunkt, betyder det, at der i det analyserede system er for store produktionsmængder, og uden at det pågældende system beskadiges, er det muligt at reducere kapaciteten af disse produktionspunkter med værdien af forbindelsen, der er bundet. til det fiktive forbrugspunkt.
2. Hvis der indføres et fiktivt produktionssted, betyder det, at kapaciteten af reelle produktionssteder ikke er nok, og de skal øges. Kapaciteten af de produktionspunkter, der er tættest på de forbrugspunkter, der er forbundet med et fiktivt produktionspunkt, øges. Producentens kapacitet øges med det bindende beløb. For at gøre dette skal du overveje kolonnen for forbrugspunktet, som er bundet til et fiktivt produktionspunkt, og finde den laveste takst i den. Det er mest effektivt at øge produktionsstedets kapacitet svarende til denne tarif med den bindende værdi.
57. Dualitetsbegrebet. Økonomisk formulering af dobbelte problemer ved at bruge eksemplet med problemet med at optimere produktionsplanen.
Et dobbelt problem er et lineært hjælpeprogrammeringsproblem formuleret ved hjælp af bestemte regler direkte fra betingelserne for det oprindelige eller direkte problem.
Lad der være et problem med at optimere produktionsplanen. Det ser sådan ud:
Indledende opgave:
a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤b 1 | ved 1
a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤b 2 | kl 2
……………….. |.. (1)
EN T 1 x 1 +a T 2 x 2 +…+ a T n x n ≤i 1 | på T
x j ≥0, j = 1,n(2)
z = c 1 x 1 +c 2 x 2 +…+c n x n ->max(3)
X = (x 1, x 2 ,…, x n)
a ij – mængden af råmaterialer af den i-te type brugt til at fremstille den j-te type produkt
Dobbelt problem
Lad virksomheden af en eller anden grund ikke være i stand til at producere produkter. For at reducere omkostningerne ved nedetid kan en virksomhed sælge de råvarer, den har. Til hvilke priser skal råvarer sælges?
y i er prisen på den i-te type råvare, der er tilgængelig i virksomheden.
a 11 y 1 +a 21 y 2 +…+ a T 1 år T≥s 1
a 12 x 1 + a 22 y 2 +…+ a T 2 x p ≥s 2
……………….. (1’)
EN 1 s y 1 +a 2 p y 2 +…+ a tp på T≥s P
y i ≥0, j = 1,m(2')
F = b 1 y 1 +b 2 y 2 +...+b m y m ->min(3')
58. Overensstemmelse mellem de strukturelle elementer i de direkte og dobbelte problemer
Hvert lineært programmeringsproblem kan forbindes med
dobbelt problem i henhold til følgende regler:
1. I alle begrænsninger af det oprindelige problem skal de gratis vilkår
være til højre, og vilkår med ukendte er til venstre.
2. Ulighedsbegrænsningerne i det oprindelige problem skal have fortegn
rettet i én retning.
3. Hvis målfunktionen i den oprindelige opgave er minimeret, skal ulighedsbegrænsningerne skrives med tegnet "≤", så i dobbeltopgaven vil målfunktionen blive minimeret, og fortegnene for ulighedsbegrænsningerne vil være "≥".
4. Hver begrænsning af det oprindelige problem svarer til en variabel i
dobbelt problem. Hvis en variabel svarer til en ulighed, er den ikke-negativ, hvis den svarer til lighed, så er den en variabel uden begrænsninger for tegnet ("vilkårlig").
5. Koefficienterne for variablerne i det dobbelte problems begrænsninger fås ved at transponere matrixen sammensat af
koefficienter for variablerne i det oprindelige problem.
6. De frie vilkår for det oprindelige problem er koefficienterne for
variabler i målfunktionen af det dobbelte problem, og gratis
led i det dobbelte problem – koefficienter for variablerne i
funktioner af det oprindelige problem Bemærk også, at dualitetsrelationen er gensidig, dvs. et problem dobbelt til et dobbelt problem falder sammen med det oprindelige. Dobbelte problempar er opdelt i symmetriske og asymmetriske. I et symmetrisk par er begrænsningerne for de direkte og dobbelte problemer svage uligheder, og derfor kan variablerne for begge problemer kun have ikke-negative værdier.
59. Konstruktion af dobbelte problemer til de originale problemer skrevet i modellens standard, kanoniske og generelle form (konstruktion af symmetriske og asymmetriske dobbelte problemer)
Standardform (original)
Σ a ij x j ≤ bi, i=1,n(1)
x j ≥0, j=1,n(2)
z = Σ c j x j ->max(3)
Dobbelt standard
Σ a ij y i ≤ c j , j=1,n(1)
y i ≥0, j=1,m(2)
F = Σ b i y i -> min(3)
Det oprindelige problem i kanonisk form:
Σ a ij x j = bi, i=1,m(1)
x j ≥0, j=1,n(2)
z = Σ c j x j ->min(3)
Dobbelt kanonisk
Σ a ij y i ≤ c j , j=1,n(1)
y i - enhver (2)
F = Σ b i y i ->max(3)
Lad os give en økonomisk fortolkning af et par dobbelte problemer. Lad os overveje problemet med rationel brug af ressourcer. Lad virksomheden have ressourcer b1,b2,...bm, som kan bruges til at producere n-typer af produkter. Lad også vide prisen på en enhed af j-typen af produktet cj (j=1,n) og forbrugshastigheden for den i-te ressource (i=1,m) til produktion af en enhed af j-te produkt – aij. Det er nødvendigt at bestemme produktionsvolumen for hver type produkt xj ( j=1,n), maksimere de samlede omkostninger
f= c1x1+…+cnxn (1)
I dette tilfælde bør forbruget af ressourcer ikke overstige deres tilgængelighed:
a11x1+…+a1nxn<=b1 }
…………………….. } (2)
am1x1+…+amnxn<=bm }
Alle kendte i deres økonomiske betydning er ikke-negative:
Xj>=0 (j=1,n). (3)
Bemærk, at dette problem danner et simuleret dobbelt problem.
Asymmetriske dobbeltproblemer.
Lad os tage ZLP til det maksimale i kanonisk form:
Max Z=(n;j=1)Σcj*xj
(n;j=1)Σaij*xj=bi (i=1,m)
Xj>=0 (j=1,n).
60. Hoved- og anden dualitetssætning (angiv sætningerne og forklar)
Første dualitetssætning.
Sætning: hvis et af de dobbelte problemer har en optimal plan, så er det andet løseligt, dvs. har en optisk plan. I dette tilfælde falder de ekstreme værdier af objektivfunktionerne sammen (j=fra 1 til n) Σcjxj*= (i=fra 1 til m)Σbiyi* hvis den er i originalen. problem, den objektive funktion er ubegrænset på sættet af planer, så i det dobbelte problem er systemet af begrænsninger inkonsekvent.
Den anden dualitetssætning og dens økonomiske fortolkning.
For at tilladelige løsninger på et par dobbelte problemer skal være optimale, er det nødvendigt og tilstrækkeligt at opfylde følgende betingelse: xj*(∑aij yi*-cj)=0, j fra 1 til n, yi*(∑aij) xj*-bi)=0, I fra 1 til m. Disse er betingelser for komplementær ikke-stivhed. Det følger af dem: hvis en begrænsning af et dobbelt problem bliver til en streng lighed ved en optimal plan, så er den tilsvarende komponent i opt. plan for det dobbelte problem skal være lig med nul.Hvis en del af opt. plan er lig med nul, så konverteres den tilsvarende begrænsning af det dobbelte problem af den optiske plan til den strenge lighed xj*>0 derfor (i= fra 1 til m)Σaij yi*=cj (produktionsomkostninger = pris) – Hvis produktet er inkluderet i engrosplanen, så hvis omkostninger>priser, produktionsvolumen=0 Σaij yi* >cj derfor xj*=0
yi*>0 derfor (j=fra 1 til n) Σaij xj*=bi (fordeling af ressourcer = bestand af ressourcer).
(j=1 til n) Σaij xj* Betydningen af sætningen kommer ned til følgende: Hvis omkostningsestimatet for produktionsomkostningerne for en produktenhed = pris, så er denne type produkt inkluderet i den optimale plan; Hvis omkostningerne overstiger prisen, skal produktet ikke produceres; Hvis ressourceforbrug = lager, så er omkostningsestimatet for denne ressource positivt. Sådanne ressourcer kaldes knappe. Den mest underskudsressource har den højeste vurdering; Hvis ressourcen ikke er helt opbrugt, er dens omkostningsestimat 0. 61. Konstruktion af den optimale referenceplan for det dobbelte problem ved hjælp af simplekstabellen for det oprindelige problem Information fra kolonnerne i den inverse matrix af lineære transformationer, der førte til det optimale resultat. Meget nyttig information kan hentes fra kolonnerne i D-1-matricen. Kolonne A3: "skygge"-prisen for ressource S2 er y01=0, kolonnen forbliver enhed og fra første linje kan man læse at x3=9, dvs. ved implementering af den fundne optimale plan vil den 1. ressource være i overskud, og dette overskud (underudnyttelse) vil være nøjagtigt 9 konventionelle enheder. Kolonne A4: "skygge" prisen for ressource S2 er lig med y02=1, ressourcen vil blive brugt fuldt ud, og dens mulige stigning vil føre til en stigning i den objektive funktion (dvs. indkomst). Og fordi y02=1, så stigningen i ressource S2 med 1.u. vil give en ekstra indkomst med.Z = y02·.в2 = = 1,1 = 1 (tusind UAH) (her.в2 er stigningen i ressource S2 og.Z er den tilsvarende stigning i indkomst). Med en sådan stigning i ressource S2 vil den maksimale indkomst allerede være Zmax=58 tusind UAH. + 1 tusind UAH = 59 tusind UAH. I fig. 6.2 illustrerer denne situation, som vil blive givet en kommentar nedenfor. Af kolonne A4 følger også, at med en forøgelse af ressource S2 med 1 c.u. for det nye optimale punkt vil produktionen af varer T1 blive reduceret med ½ ton (ved skæringspunktet mellem rækken af grundvariablen x1 og kolonne A4 er der "-1/2"), og produktionen af varer T2 vil stige med 3/2 tons (da vi i rækken med grundvariablen x2 i kolonne A4 har "3/2"). Hvad der er blevet sagt i kolonne A4 vil blive kommenteret nedenfor ved hjælp af grafiske konstruktioner (Fig. 6.2). Spalte A5 : "skygge"-prisen for ressource S3 er lig med y03 = 2. Det betyder, at en forøgelse af S3-ressourcen med 1.u. vil bringe en tilføjelse i Z med.Z = y03· .в3 = 2,1 =2(tusind UAH) og vil være Zmax=58 tusind UAH. + 2 tusind UAH = 60 tusind UAH. Samtidig som det følger af kolonne A5 i tabellen. 3, vil output fra T1 stige med ½ ton, og T2 vil falde med ½ ton. Beholdningen af råvarer S1 (se 1. linje) vil stige med 3/2 cu. 62. Ideen om den dynamiske programmeringsmetode og dens geometriske fortolkning. Bellmans optimalitetsprincip. Den optimale løsning på problemet ved hjælp af den dynamiske programmeringsmetode findes ud fra den funktionelle ligning For at bestemme det skal du: 1.skriv den funktionelle ligning for den sidste tilstand af processen (den svarer til l=n-1) fn-1(Sl-1)=optimum(Rn(Sn-1,Un)+f0(Sn)) 2.find Rn(Sn-1,Un) fra et diskret sæt af dets værdier for nogle faste Sn-1 og Un fra de tilsvarende tilladte områder (da f0(Sn)=0, derefter f1(Sn-1)= optimal(Rn(Sn-1,Un) Som et resultat, efter det første trin, er løsningen Un og den tilsvarende værdi af funktionen f1(Sn-1) kendt 3.Reducer værdien af l med én og skriv den tilsvarende funktionelle ligning. For l=n-k (k= 2,n) har den formen fk(Sn-k)=optimum(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2) 4.finde en betinget optimal løsning baseret på udtryk (2) 5.tjek hvad værdien af l er lig. Hvis l=0, er beregningen af betinget optimale løsninger afsluttet, og den optimale løsning på problemet for processens første tilstand er fundet. Hvis l ikke er lig med 0, fortsæt til trin 3. 6.Beregn den optimale løsning på problemet for hvert efterfølgende trin i processen, flytning fra slutningen af beregningerne til begyndelsen. Den dynamiske programmetode tillader et problem med mange variable at blive erstattet af et antal sekventielt løste problemer med et mindre antal variable. Løsningen udføres i trin. Det grundlæggende princip, som optimeringen af en flertrinsproces er baseret på, samt egenskaberne ved beregningsmetoden, er Bellmans optimalitetsprincip. Optimal adfærd har den egenskab, at uanset den oprindelige tilstand og den oprindelige beslutning, skal efterfølgende beslutninger være optimale i forhold til den tilstand, der er resultatet af den oprindelige beslutning. Matematisk er det skrevet som udtryk for formen: fn-1(Sl)=optimum(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1) (l=0,n-1)Optimum i udtrykket betyder maksimum eller minimum afhængig af problemets betingelser. 63. Krav til problemer løst ved DP-metoden Dynamisk programmering er en matematisk metode til at finde optimale løsninger på flertrinsproblemer. En flertrinsproces er en, der udvikler sig over tid og opdeles i en række trin eller stadier. Et af kendetegnene ved den dynamiske programmeringsmetode er, at beslutninger, der træffes i forhold til flertrinsprocesser, ikke betragtes som en enkelt handling, men som et helt kompleks af indbyrdes forbundne beslutninger. Denne sekvens af indbyrdes forbundne beslutninger kaldes en strategi Målet med optimal planlægning er at vælge en strategi, der giver det bedste resultat i forhold til et forudvalgt kriterium. Denne strategi kaldes optimal. Et andet vigtigt træk ved metoden er uafhængigheden af den optimale beslutning, der træffes på næste trin fra forhistorien, dvs. om, hvordan processen, der optimeres, nåede sin nuværende tilstand. Den optimale løsning vælges kun under hensyntagen til de faktorer, der karakteriserer processen i øjeblikket. Den dynamiske programmetode er også kendetegnet ved, at valget af den optimale løsning på hvert trin skal ske under hensyntagen til dens konsekvenser i fremtiden. Det betyder, at mens du optimerer processen på hvert enkelt trin, må du aldrig glemme alle efterfølgende trin. 64. Økonomisk formulering og konstruktion af en matematisk model af et problem løst ved DP-metoden (ved at bruge eksemplet med problemet med fordelingen af kapitalinvesteringer). Bellman gentagelsesforhold. Lad os først forklare, at den dynamiske programmeringsmetode primært anvendes på de problemer, hvor den optimerede proces (eller situation) udspiller sig i rum eller tid, eller begge dele. Lad selve processen (situationen) være så kompleks, at det ikke er muligt at optimere den ved hjælp af kendte metoder. Derefter, ved hjælp af den dynamiske programmeringsmetode, opdeles (inddeles) en KOMPLEKS proces (drift, situation) i et antal trin (trin). Denne nedbrydning er naturlig i mange tilfælde, men generelt er den indført kunstigt. .
For eksempel, når man overvejer ethvert skakspil, tjener ethvert træk fra hver spiller opdeling af hele batchen i separate trin (stadier). Og i en militær operation for at forfølge et missil med et andet, skal hele den kontinuerlige proces kunstigt opdeles i stadier, for eksempel efter hvert sekunds observation. Den dynamiske programmeringsmetode tillader optimering af hele den komplekse proces at blive erstattet af betinget optimering for hvert trin (trin) efterfulgt af syntese af optimal kontrol af hele processen. I dette tilfælde sørger metoden for, at betinget optimering på et separat trin (stadie) udføres af hensyn til først og fremmest hele operationen. Alle beregninger, der gør det muligt at finde den optimale værdi af effekten opnået i n trin, fn(S0), udføres efter formel (1), som kaldes den grundlæggende funktionelle Bellman-ligning eller gentagelsesrelation. Ved beregning af den næste værdi af funktionen fn-1, bruges værdien af funktionen fn-(l+1) opnået i det foregående trin, og den direkte værdi af effekten Rl+1(Sl,Ul+1), opnået som følge af valg af løsningen Ul+1 for et givet tilstandssystem Sl. Processen med at beregne værdien af funktionen fn-1(l=0,n-1) Den udføres under den naturlige begyndelsestilstand f0(Sn)=0, hvilket betyder, at ud over systemets endelige tilstand er effekten nul. 65. Problem med fordeling af kapitalinvesteringer (eksempel). For at løse problemet med optimal fordeling af kapitalinvesteringer vil vi bruge Bellmans funktionelle ligning. Først vil vi ved hjælp af den enkleste situation illustrere udledningen af den funktionelle Bellman-ligning, og derefter vil vi ved hjælp af et eksempel bevise, hvordan man bruger denne ligning til at løse problemet af interesse for os. Lad os starte med den optimale fordeling af allokerede kapitalinvesteringer i mængden af K mellem to virksomheder. Virksomhedernes planlægningsafdelinger dannede ud fra deres beregninger indkomstfunktionerne q(x) for virksomhed P1 og h(x) for virksomhed P2. Disse funktioner betyder, at hvis den første eller anden virksomhed modtager en investering på x, så den første virksomhed indkomsten q(x) vil blive modtaget, og den anden h(x), og værdien x kan tage kontinuerlige eller kendte diskrete værdier fra 0 til K. Så lad virksomhed P1 få allokeret kapitalinvesteringer i mængden af x, så vil virksomhed P2 få tildelt beløbet K - x. I dette tilfælde vil indkomst q(x) blive modtaget fra den første virksomhed og indkomst h(K - x) fra den anden. Hvis anlægsinvesteringer K blev afsat til én planperiode, vil den samlede indkomst fra de to virksomheder være R(K, x) = q(x) + h(K - x). Det er klart, x og følgelig K - x skal vælges således, at R(K, x) får sin maksimale værdi, hvilket vi betegner med F(K): Denne post er som et skelet for mere komplette poster Bellmans funktionelle ligning. LAD OS FULDFØRE vores opgave ved at fordele kapitalinvesteringer over to planlægningsperioder (to faser) .
Lad det i første omgang besluttes at allokere beløbet x til den første virksomhed P1 og x til den anden virksomhed K. Generelt vil indkomsten være lig med R(K, x) = q(x) + h(K - x). Hvis vi husker på, at kapitalinvesteringerne er fordelt over 2 perioder (2 faser), så vil balancen af kapitalinvesteringer ved den første virksomhed være .x, hvor , og ved den anden - .(K - x), hvor I overensstemmelse hermed, indkomsten for den anden periode vil være q( .x) - for den første virksomhed og h[.(K - x)] - for den anden. Optimering ved hjælp af den dynamiske programmeringsmetode starter som regel fra slutstadiet. Lad os derfor starte fra anden fase og angive F1 den maksimalt mulige indkomst fra to virksomheder i den anden scene. Vi får Derefter tilføjer vi den forrige (i vores tilfælde den første) fase til den betragtede sidste (i vores tilfælde den anden) fase og finder den maksimale indkomst fra de to faser sammen: Tilsvarende opnår vi for n stadier hvor Fn-1 er den objektivfunktion, der giver det bedste resultat over de sidste (n - 1) stadier. Den resulterende funktionelle Bellman-ligning er tilbagevendende i naturen, dvs. relaterer Fn-værdien til Fn-1-værdien. I en mere generel oversigt har Bellman-ligningen formen hvor , Fn-1 - maksimal indkomst for (n - 1) sidste stadier, Fn - maksimal indkomst for alle n faser. 66. Konceptet med at løse ikke-lineære programmeringsproblemer Lad det ikke-lineære programmeringsproblem stilles i følgende generelle form: find værdier af variablerne x1, x2,..., xn, der opfylder betingelserne: og bringe det påkrævede ekstremum (maksimum eller minimum) af den objektive funktion f = f(x1, x2,…, xn), (13,2) hvor f(x1, …, xn) og qi(x1, …, xn) (m, 1 i =) er reelle ikke-lineære, regulære funktioner af n reelle variable. Ved deres generelle egenskaber kan ikke-lineære programmeringsproblemer væsentligt anderledes end lineære. For eksempel kan området med gennemførlige løsninger allerede være ikke-konveks, og yderpunktet af den objektive funktion kan observeres på et hvilket som helst punkt i den gennemførlige region. Metoder til løsning af ikke-lineære problemer adskiller sig også væsentligt. Lad os bare overveje nogle tilgange til at løse disse problemer. Først og fremmest er den grafiske tilgang også gyldig, når man løser de enkleste ikke-lineære programmeringsproblemer. Så hvis argumenterne for problemet er variablerne x1 og x2, så konstrueres først et område med mulige løsninger på planet af disse variable, og derefter bestemmes det optimale punkt i regionen ved hjælp af niveauerne af den objektive funktion f( x1,x2). I ikke-lineær programmering bruges en gradienttilgang til at løse mange problemer. Der er en række gradientmetoder, hvis essens er at finde det optimale resultat ved hjælp af gradienten af den objektive funktion - en vektor, der angiver retningen af den maksimale stigning i målet for det pågældende punkt. I det generelle tilfælde udføres søgeproceduren i en iterativ tilstand fra det oprindeligt valgte punkt til punkter med den bedste indikator. Lad f.eks. -
region med mulige løsninger problem under overvejelse, og den iterative proces med beregninger begynder fra punktet Dernæst foretages først en overgang langs gradienten af den objektive funktion, og derefter en tilbagevenden til regionen. langs gradienten til den brudte grænse af O2 O3-regionen.. I fig. 13.3 viser, at Ai med ulige indeks hører til regionen, og punkter Ai med lige indeks hører ikke til. Når vi nærmer os det optimale punkt Q, kommer retningerne af arbejdsgradienterne tættere på. Derfor ville det ideelle kriterium for at stoppe processen være kollineariteten af målgradienten og gradienten af den overtrådte grænse. 67. Begrebet parametrisk og heltalsprogrammering
. Udsagn og matematisk model af ZTsLP. I problemer med udelelige objekter pålægges integeritetsbetingelser for variabler. Nogle gange gælder disse betingelser for alle variabler, nogle gange for en del af variablerne. Overvej et problem med heltal f=(n,j=1)∑CjXi max (n,j=1)∑AijXj=bi, i=1,m xi-heltal,j=1,n Nu, i modsætning til det generelle lineære programmeringsproblem, vil den optimale plan ikke nødvendigvis være i toppunktet for polyederet af planer. Følgende metoder findes til at løse heltalsproblemer: 1.Skæringsmetoder 2.Kombinatorisk 3. Omtrentlige metoder.. Parametrisk programmering er en gren af matematisk programmering, der er viet til studiet af optimeringsproblemer, hvor gennemførlighedsbetingelserne og den objektive funktion afhænger af nogle deterministiske parametre.
