Lineær programmering. Metodisk grundlag for udvikling af ledelsesbeslutninger Løsningen kaldes optimal

I øjeblikket omfatter uddannelsesprogrammet for specialer relateret til økonomi, finans og ledelse en disciplin kaldet "Metodes of Optimal Decisions". Inden for denne disciplin studerer eleverne den matematiske side af optimering, operationsforskning, beslutningstagning og modellering. Hovedtræk ved denne disciplin er bestemt af den fælles undersøgelse af matematiske metoder med deres anvendelse til at løse økonomiske problemer.

Optimeringsopgaver: generel information

Hvis vi betragter det generelle tilfælde, så er meningen med optimeringsproblemet at finde den såkaldte optimale løsning, der maksimerer (minimerer) den objektive funktion under visse betingelser.

Afhængigt af funktionernes egenskaber kan optimeringsproblemer opdeles i to typer:

lineært programmeringsproblem (alle funktioner er lineære);
ikke-lineært programmeringsproblem (mindst en af funktionerne er ikke lineær).

Særlige tilfælde af optimeringsproblemer er fraktioneret-lineære, dynamiske og stokastiske programmeringsproblemer.

De mest undersøgte optimeringsproblemer er lineære programmeringsproblemer (LPP), hvis løsninger kun tager heltalsværdier.

OPP: formulering, klassificering

Det lineære programmeringsproblem i det generelle tilfælde består i at finde minimum (maksimum) af en lineær funktion under visse lineære begrænsninger.

En generel ZLP er et formproblem

under restriktioner

hvor er variablerne, er de givne reelle tal, er den objektive funktion, er problemplanen, (*)-(***) er begrænsningerne.

Et vigtigt træk ved ZLP er, at det yderste af den objektive funktion opnås ved grænsen af området for mulige løsninger.

Praktiske økonomiske anvendelser af optimale løsningsmetoder findes ved løsning af problemer af følgende typer:

problemer med blandinger (dvs. planlægning af sammensætningen af produkter);
problemer med optimal ressourceallokering i produktionsplanlægning;

PAP: eksempler

Blandingsproblem

Løsningen på problemet med blandinger består i at finde det billigste sæt, bestående af visse udgangsmaterialer, der giver en blanding med de ønskede egenskaber.

Ressourceallokeringsproblem

Virksomheden producerer n forskellige produkter, hvis produktion kræver m forskellige typer ressourcer. Reserverne af brugte ressourcer er begrænsede og udgør hhv b 1, b 2,…, b m c.u. Derudover kendes teknologiske koefficienter en ij, som viser hvor mange enheder jeg-th ressource er nødvendig for at producere en enhed produkt j-th type (). Den fortjeneste, som en virksomhed får ved salg af et produkt j-th type, udgør c j monetære enheder Det er nødvendigt at udarbejde en plan for produktion af produkter, hvis fortjeneste under gennemførelsen vil være størst.

Problemer, der involverer blandinger og ressourceallokering, er ofte skrevet i tabelform.

Ressourcer	Behov			Reserver
Ressourcer	B 1	…	Bn	Reserver
A 1				b 1
…				…
Er				b m
Profit	c 1	…	c n

Blandings- og ressourceallokeringsproblemer kan løses på flere måder:

grafisk metode (i tilfælde af et lille antal variable i den matematiske model);
simplex metode (hvis antallet af variable i en matematisk model er mere end to).

Transportproblemet refererer til en klasse af opgaver, der har en bestemt specifik struktur. Det enkleste transportproblem er problemet med at transportere et produkt til destinationer fra afgangssteder med minimale omkostninger til transport af alle produkter.

For klarhed og nem opfattelse er tilstanden af transportproblemet normalt skrevet i følgende tabel:

Generelt løses et transportproblem i flere faser:

Fase I: opbygning af den oprindelige referenceplan;
Fase II: kontrol af referenceplanens optimalitet;
Fase III: afklaring af referenceplanen, hvis den ikke er optimal.

Der er flere metoder til at opnå den oprindelige referenceplan, for eksempel metoden i det nordvestlige hjørne, Vogel-metoden og minimumsomkostningsmetoden.

Planen kontrolleres for optimalitet ved hjælp af den potentielle metode:

- for besatte celler,
- for ubesatte celler.

Hvis planen ikke er optimal, så bygges et kredsløb, og transporten omfordeles.

Konklusion

Det er ikke muligt at dække hele teorien og praksis af optimale løsningsmetoder inden for rammerne af en artikel, derfor overvejes kun nogle punkter, der giver os mulighed for at give en generel idé om denne disciplin, problemer og metoder til at løse dem.

Derudover er det godt at bemærke, at for at kontrollere de opnåede løsninger på optimeringsproblemer, kan du meget effektivt bruge tilføjelsen "Solution Search" til MS Excel-pakken. Men det er faktisk en anden historie, ligesom en detaljeret overvejelse af metoder til løsning af optimeringsproblemer.

Her er flere lærebøger til at studere optimale løsningsmetoder:

Bandi B. Grundlæggende om lineær programmering: Trans. fra engelsk – M.: Radio og kommunikation, 1989. – 176 s.
Kremer N.Sh. Operationsforskning i økonomi: Proc. manual til universiteter / N.Sh. Kremer, B.A. Putko, I.M. Trishin, M.N. Friedman; Ed. prof. N.Sh. Kremer. – M.: ENHED, 2005. – 407 s.

Løsning af tilpassede optimeringsmetoder

Vi kan hjælpe dig med at løse eventuelle problemer ved hjælp af optimale løsningsmetoder. Du kan bestille løsninger på problemer på vores hjemmeside. Du skal blot angive deadline og vedhæfte filen med opgaven. din ordre er gratis.

Et lineært programmeringsproblem (LPP) er problemet med at finde den største (eller mindste) værdi af en lineær funktion på et konveks polyedrisk sæt.

Simplexmetoden er en metode til at løse et lineært programmeringsproblem. Essensen af metoden er at finde en indledende gennemførlig plan og efterfølgende forbedre planen, indtil den maksimale (eller minimum) værdi af den objektive funktion i et givent konveks polyedrisk sæt er opnået, eller problemets uløselighed er bestemt.

Overvej følgende lineære programmeringsproblem i kanonisk form:

(1)

(2)

(3)

Kunstig basismetode

Som vist ovenfor, for et problem skrevet i kanonisk form, hvis blandt matrixens kolonnevektorer EN Der er m enhed og lineært uafhængig, kan du direkte angive referenceplanen. Men for mange lineære programmeringsproblemer skrevet i kanonisk form og med referenceplaner, blandt matrixens kolonnevektorer EN ikke altid tilgængelig m enhed og lineært uafhængig. Overvej følgende problem:

Antag, at vi skal finde maksimum af en funktion

under forhold

hvor er de første n elementer er nul. Variabler kaldes kunstige. Vektorer kolonner

(28)

danne et såkaldt kunstigt grundlag m-dimensionelt vektorrum.

Da det udvidede problem har en referenceplan, kan dets løsning findes ved simpleksmetoden.

Sætning 4. Hvis i den optimale plan udvidet problem (24)-(26) værdier af kunstige variable , At er den optimale plan for problem (21)-(23).

Således, hvis værdierne af de kunstige variable i den fundne optimale plan for det udvidede problem er lig med nul, så opnås den optimale plan for det oprindelige problem. Lad os dvæle mere detaljeret ved at finde en løsning på det udvidede problem.

Værdien af målfunktionen for referenceplanen (27):

Det bemærker vi F(X) og består af to uafhængige dele, hvoraf den ene er afhængig af M, og den anden - nej.

Efter beregning F(X) og deres værdier, såvel som de indledende data for den udvidede opgave, indtastes i en simplekstabel, som vist ovenfor. Den eneste forskel er, at denne tabel indeholder en række mere end en almindelig simplekstabel. På samme tid i ( m Den +1) linje indeholder koefficienter, der ikke indeholder M, og i ( m+2) linie − koefficienter for M.

Når du flytter fra en referenceplan til en anden, vil en vektor svarende til det største negative tal i absolut værdi ( m+2) linjer. En kunstig vektor, der er udelukket fra grundlaget, giver ikke mening at blive genindført i grundlaget. Ved flytning til en anden referenceplan kan det ske, at ingen af de kunstige vektorer udelukkes fra grundlaget. Genberegning af simplekstabellen ved flytning fra en referenceplan til en anden udføres efter de sædvanlige regler for simpleksmetoden (se ovenfor).

Den iterative proces udføres iflg m+2 linje så lang som elementer m+2 linjer svarende til variable vil ikke blive ikke-negativ. Desuden, hvis kunstige variable udelukkes fra grundlaget, svarer den fundne plan for det udvidede problem til en referenceplan for det oprindelige problem.

m+2 rækker, kolonner x 0 er negativ, så har det oprindelige problem ingen løsning.

Hvis ikke alle kunstige variable er udelukket fra basis og element m+2 rækker, kolonner x 0 er lig med nul, så er referenceplanen for det oprindelige problem degenereret, og grundlaget indeholder mindst én af vektorerne for det kunstige grundlag.

Hvis den oprindelige opgave indeholder flere enhedsvektorer, bør de indgå i det kunstige grundlag.

Hvis under iterationer m+2 linje indeholder ikke længere negative elementer, så fortsætter iterationsprocessen med m+1 linje, indtil den optimale plan for det udvidede problem er fundet, eller problemets uløselighed afsløres.

Processen med at finde en løsning på det lineære programmeringsproblem (21)−(23) ved hjælp af den kunstige basismetode omfatter således følgende hovedstadier:

Komponer det udvidede problem (24)-(26).
Find referenceplanen for det udvidede problem.
Ved hjælp af simplex-metoden udelukkes kunstige vektorer fra grundlaget. Som et resultat heraf findes referenceplanen for det oprindelige problem, eller dets uløselighed registreres.
Ved at bruge den fundne referenceplan for ZLP (21)-(23), finder de enten den optimale plan for det oprindelige problem eller fastslår dets uløselighed.

For at løse lineære programmeringsproblemer online, brug en lommeregner

Det generelle lineære programmeringsproblem (GLP) er formuleret som følger - find problemvariablerne x 1 , x 2 , ..., x n , som giver yderpunktet for den objektive funktion

En tilladelig løsning (plan) af et lineært programmeringsproblem (LPP) er enhver n-dimensionel vektor x=(x 1 , x 2 , ..., x n) at tilfredsstille systemet med ligheder og uligheder. Sættet af gennemførlige løsninger på et problem udgør domænet af gennemførlige løsninger D.

En optimal løsning (plan) af et lineært programmeringsproblem er en mulig løsning, således at objektivet fungerer Z(x) når et ekstremum.

Det kanoniske lineære programmeringsproblem (CLP) har formen

(1.2)

Det adskiller sig fra OZLP ved, at dets system af begrænsninger er et system af kun ligninger, og alle variabler er ikke-negative.

At bringe OPLP til den kanoniske form af OPLP:

For at erstatte det oprindelige minimeringsproblem med et maksimeringsproblem (eller omvendt, et maksimeringsproblem med et minimeringsproblem), er det nok at gange den objektive funktion med "-1" og se efter maksimum (minimum) af den resulterende funktion;

Hvis der er uligheder mellem restriktionerne, så ved at indføre yderligere ikke-negative variabler x n +1 ≥ 0 transformerer de til ligheder:

ulighed -en jeg 1 x 1 +…+-en i x n ≥ b i erstattes af ligestilling -en jeg 1 x 1 +…+-en i x n+ x n+1 = b jeg,

ulighed -en jeg 1 x 1 +…+-en i x n ≤ b i erstattes af ligestilling -en jeg 1 x 1 +…+-en i x n+ x n+1 = b jeg;

Hvis en eller anden variabel x k har ingen tegnrestriktioner, så erstattes den (i den objektive funktion og i alle restriktioner) af forskellen mellem to nye ikke-negative variable: x k = x" k – x” k , Hvor x" k ≥ 0. x” k ≥ 0.

Grafisk metode til at løse ZLP med to ubekendte

ZLP med to ukendte har formen:

Metoden er baseret på muligheden for grafisk at afbilde regionen med mulige løsninger og finde den optimale løsning blandt dem.

Området for mulige løsninger (ADA) af problemet er en konveks polygon og er konstrueret som skæringspunktet (fælles del) af løsningsområderne for hver af problembegrænsningsulighederne.

Domænet for løsning af uligheden -en jeg 1 x 1 +-en jeg 2 x 2 ≤ b i er et af de to halvplaner, hvorpå linjen -en jeg 1 x 1 +-en jeg 2 x 2 = b i svarende til denne ulighed deler koordinatplanet. For at bestemme hvilken af de to halvplaner der er løsningsregionen, er det nok at erstatte koordinaterne for ethvert punkt, der ikke ligger på skillelinjen, i uligheden:

Hvis uligheden er sand, så er løsningsområdet halvplanet, der indeholder dette punkt;

Hvis uligheden ikke er sand, så er løsningsdomænet et halvt plan, der ikke indeholder dette punkt.

For at finde den optimale blandt de mulige løsninger, bruges niveaulinjer.

En niveaulinje er en ret linje Med 1 x 1 +Med 2 x 2 = l, Hvor l= const, hvor den objektive funktion af problemet har en konstant værdi. Alle niveaulinjer er parallelle med hinanden.

Objektiv funktionsgradient grad Z(x) angiver normalvektoren C = (c 1 , c 2) niveaulinjer. Den objektive funktion på niveaulinjerne øges, hvis niveaulinjerne flyttes i retning af deres normal, og falder i den modsatte retning.

Referencelinjen er en niveaulinje, der har mindst ét fælles punkt med ODR, og i forhold til hvilken ODR er placeret i et af halvplanerne. Problemets ODD har ikke mere end to støttelinjer.

Den optimale løsning af ZLP ligger på referencelinjen ved hjørnepunktet af ODR-polygonen. ZLP har en unik løsning, hvis referencelinjen passerer gennem et hjørnepunkt af ODR'en, og et uendeligt antal løsninger, hvis støttelinjen passerer gennem kanten af ODR-polygonen. ZLP har ingen løsning, hvis ODP er et tomt sæt (når systemet af begrænsninger er inkonsekvent), og hvis ODP er ubegrænset i retning af ekstremum (den objektive funktion er ubegrænset).

Algoritme til den grafiske metode til at løse ZLP med to ukendte:

Byg ODR.

Konstruer normalvektor C = (c 1 , c 2) og niveaulinje Med 1 x 1 +Med 2 x 2 = 0, der går gennem origo og vinkelret på vektoren MED.

Flyt niveaulinjen til referencelinjen i vektorens retning MED i et max problem, eller i den modsatte retning – i et min problem.

Hvis, når niveaulinjen bevæger sig i retning af ekstremum, går ODR til det uendelige, så har ZLP ingen løsning på grund af den ubegrænsede objektivfunktion.

Hvis ZLP har en optimal løsning, så for at finde den, løs i fællesskab ligningerne for linjerne, der begrænser ODR og har fælles punkter med referencelinjen. Hvis ekstremum nås ved to hjørnepunkter, så har ZLP et uendeligt sæt løsninger, der hører til ODR-kanten afgrænset af disse hjørnepunkter. I dette tilfælde beregnes koordinaterne for begge hjørnepunkter.

Beregn værdien af den objektive funktion ved ekstremumpunktet.

Enkel metode til at løse problemet med problemer

Simplexmetoden er baseret på følgende bestemmelser:

ODP'en for et lineært programmeringsproblem er et konveks sæt med et endeligt antal hjørnepunkter;

Den optimale løsning af ZLP er et af hjørnepunkterne i ODR. Hjørnepunkterne i ODR repræsenterer algebraisk nogle grundlæggende (reference) løsninger af systemet af begrænsninger i ZLP.

Den grundlæggende (reference) løsning i ZLP er en sådan tilladelig løsning x 0 =(x 10 , x 20 , ..., x m 0 , 0,...0), for hvilke vektorerne af betingelser (koefficienter for ukendte begrænsninger i systemet) er lineært uafhængige.

Ikke-nul koordinater x 10 , x 20 , ..., x m 0 løsninger x 0 kaldes basisvariablerne, de resterende løsningskoordinater x 0 - frie variable. Antallet af ikke-nul-koordinater for referenceløsningen kan ikke være større end rangordenen r systemer af begrænsninger af PLP (antal lineært uafhængige ligninger i systemet af begrænsninger af PLP). Dernæst antager vi, at systemet med PLP-restriktioner består af lineært uafhængige ligninger, dvs. r = m.

Betydningen af simplex-metoden er en målrettet overgang fra en referenceløsning af PLP til en anden (dvs. fra et hjørnepunkt af ODP til et andet) i retning af ekstremum og består af en sekvens af trin:

Find den første supportløsning;

Foretag overgangen fra en referenceløsning til en anden;

Bestem kriteriet for at opnå en optimal løsning eller lav en konklusion om fraværet af en løsning.

EksekveringsalgoritmeSimplex metode ZLP

Simplex-metodealgoritmen går fra en referenceløsning af PLP'en til en anden i retning af yderpunktet af den objektive funktion.

Lad ZLP angives i den kanoniske form (1.2), og betingelsen være opfyldt

b i ≥ 0, jeg=1,2,…,m, (1.3)

relation (1.3) kan altid opfyldes ved at gange den tilsvarende ligning med "-1" i tilfælde af negativ b jeg. Vi mener også, at ligningssystemet i problemets begrænsninger (1.2) er lineært uafhængigt og har rang r = m. I dette tilfælde har vektoren af støtteopløsningen m ikke-nul koordinater.

Lad den oprindelige opgave (1.2), (1.3) reduceres til den form, hvor de grundlæggende variabler x 1 , x 2 , ..., x m er udtrykt i frie variable x m + 1 , x m + 2 , ..., x n

(1.4)

Ud fra disse sammenhænge vil vi konstruere tabel 1

Tabel 1.

Tabel 1 kaldes en simplekstabel. Alle yderligere transformationer er forbundet med ændringer i indholdet af denne tabel.

Algoritme medkompleks metode:

1. I sidste linje Z Simplex-tabeller i en min-opgave finder det mindste positive element (i et max-problem, det mindste negative element), uden at tælle det frie led. Kolonnen, der svarer til dette element, kaldes aktiveringskolonnen.

2. Beregn forholdet mellem frie led og de positive elementer i opløsningskolonnen (simpleksforhold). Find den mindste af disse simplex-relationer, den svarer til opløsningsstrengen.

3. I skæringspunktet mellem den løsende række og den løsende kolonne er der et opløsningselement.

4. Hvis der er flere simpleksrelationer af samme størrelse, så vælg en af dem. Det samme gælder for de positive elementer i den sidste række i simplekstabellen.

5. Efter at have fundet aktiveringselementet, gå videre til næste tabel. De ukendte variabler, der svarer til opløsningsrækken og -kolonnen, ombyttes. I dette tilfælde bliver grundvariablen en fri variabel og omvendt. Simplextabellen konverteres som følger (tabel 2):

tabel 2

6. Element i tabel 2, svarende til det løsende element i tabel 1, er lig med den gensidige værdi af det løsende element.

7. Elementerne i rækken i tabel 2, der svarer til elementerne i den tilladte række i tabel 1, opnås ved at dividere de tilsvarende elementer i tabel 1 med det tilladte element.

8. Elementerne i kolonnen i tabel 2, svarende til elementerne i opløsningskolonnen i tabel 1, opnås ved at dividere de tilsvarende elementer i tabel 1 med det opløselige element og tages med det modsatte fortegn.

9. De resterende elementer beregnes af rektangel regel: Vi tegner mentalt et rektangel i tabel 1, hvor det ene toppunkt falder sammen med det opløsende element (Re), og det andet med det element, vi leder efter; Lad os betegne elementet i den nye tabel 2 med (Ne), og elementet på samme sted i den gamle tabel 1 med (Se). De resterende to hjørner A og B fuldender figuren til et rektangel. Så er det nødvendige element He fra tabel 2 lig med He = Se – A*B/Re.

10. Optimalitetskriterium. Så snart der opnås en tabel, hvor alle elementer i den sidste række i min-problemet er negative (i max-problemet er alle elementer positive), anses det for, at ekstremum er fundet. Den optimale værdi af objektivfunktionen er lig med det frie led i rækken Z, og den optimale løsning bestemmes af basisvariablenes frie led. Alle frie variable er sat til nul.

11.Hvis alle elementer i opløsningskolonnen er negative, har problemet ingen løsninger (minimum er ikke opnået).

Kunstig basismetode til løsning af ZLP

Simplex-metodealgoritmen er anvendelig, hvis en referenceløsning af PLP'en er valgt, dvs. den originale PLP (1.2) reduceres til formen (1.4). Den kunstige basismetode tilbyder en procedure til at konstruere en sådan referenceløsning.

Den kunstige basismetode er baseret på introduktion af kunstige basisvariable y 1 , y 2 ,…, y m , ved hjælp af hvilket systemet med begrænsninger af PLP (2.2)

(1.5)

kan konverteres til formularen

(1.6)

Systemer (1.5) og (1.6) vil være ækvivalente, hvis alle y jeg vil være lig nul. Som før tror vi på, at alt b jeg ≥ 0. For at på jeg var lig med 0, skal vi transformere problemet, så alle kunstige basisvariabler y jeg skiftet til frie variable. En sådan overgang kan foretages ved hjælp af simplex-metodealgoritmen med hensyn til en yderligere objektivfunktion

F(y) = y 1 + y 2 + ... + y m = d 0 – (d 1 x 1 +d 2 x 2 +…+d n x n). (2,7)

Den indledende simplex-tabel for denne metode ser ud

Først transformeres simplekstabellen med hensyn til objektivfunktionen F(y) indtil der opnås en referenceopløsning. Referenceløsningen findes, når følgende kriterium er opfyldt: F(y) = 0 og alle kunstige variable på jeg omsat til frie variable. Derefter overstreges en række fra simplekstabellen for F(y) og kolonner for på jeg og løse problemet for den oprindelige objektivfunktion Z(x) indtil den optimale opløsning er opnået.

Lineær programmering er en gren af matematikken, der studerer metoder til at finde minimum eller maksimum af en lineær funktion af et endeligt antal variable, forudsat at variablerne opfylder et endeligt antal begrænsninger i form af lineære ligninger eller lineære uligheder.

Det generelle lineære programmeringsproblem (GLP) kan således formuleres som følger.

Find værdier af reelle variabler for hvilke objektiv funktion

tager en minimumsværdi på det sæt af punkter, hvis koordinater opfylder system af restriktioner

Som bekendt en ordnet samling af værdier n variable , , … er repræsenteret af et punkt i n-dimensionelt rum. I det følgende vil vi betegne dette punkt x=( , , … ).

I matrixform kan det lineære programmeringsproblem formuleres som følger:

, EN- størrelse matrix,

Prik x=( , , … ), der opfylder alle betingelser, kaldes gyldigt punkt . Sættet af alle tilladte punkter kaldes gyldigt område .

Optimal løsning (optimal plan) et lineært programmeringsproblem kaldes en løsning x=( , , … ), der tilhører det tilladte område og for hvilket den lineære funktion Q tager den optimale (maksimum eller minimum) værdi.

Sætning. 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 sammen med to af sine punkter indeholder deres vilkårlige konvekse lineære kombination.

Prik x hedder konveks lineær kombination point, hvis betingelserne er opfyldt

Sættet af alle mulige løsninger på et lineært programmeringsproblem er en konveks polyedrisk region, som vi fremover vil kalde polyeder af opløsninger .

Sætning. Hvis ZLP har en optimal løsning, så tager objektivfunktionen den maksimale (minimum) værdi ved et af hjørnerne af løsningspolyederet. Hvis objektivfunktionen tager en maksimal (minimum) værdi ved mere end et punkt, så tager den denne værdi på ethvert punkt, der er en konveks lineær kombination af disse punkter.

Blandt systemets mange løsninger m lineære ligninger, der beskriver opløsningernes polyhedron, skelnes de såkaldte basisløsninger.

Grundlæggende løsning af systemet m lineære ligninger med n variable er en løsning, hvor alle n-m ikke-kernevariabler er nul. I lineære programmeringsproblemer kaldes sådanne løsninger tilladte basisløsninger (referenceplaner).

Sætning. Hver tilladelig basisløsning til et lineært programmeringsproblem svarer til et toppunkt af løsningspolyederet, og omvendt svarer til hvert toppunkt i løsningspolyederet en tilladt basisløsning.

En vigtig konsekvens følger af ovenstående teoremer:

Hvis et lineært programmeringsproblem har en optimal løsning, falder det sammen med mindst én af dets mulige grundlæggende løsninger.

Følgelig skal det optimale af den lineære funktion af målet for et lineært programmeringsproblem søges blandt det endelige antal af dets gennemførlige grundlæggende løsninger.