Lineære programmeringsmetoder. Overgang fra objektivfunktionens minimeringsproblem til maksimeringsproblemet

Lineær programmering opstod som en separat gren af ​​anvendt matematik i 40'erne og 50'erne. XX århundrede takket være arbejdet fra den sovjetiske videnskabsmand, nobelprisvinderen L.V. Kantorovich. I 1939 udgav han værket "Matematiske metoder til at organisere og planlægge produktion", hvori han brugte matematik til at løse økonomiske problemer vedr. bedste download maskiner, skæring af materialer til den laveste pris, fordeling af last på tværs af flere transportformer og andre, foreslår metoden til at løse multiplikatorer 8.

L.V. Kantorovich var den første til at formulere så udbredte økonomiske og matematiske begreber som optimal plan, optimal allokering af ressourcer, objektivt bestemte vurderinger, der angiver adskillige økonomiske områder, hvor de kan anvendes.

Koncept lineær programmering blev introduceret af den amerikanske matematiker D. Dantzig, som i 1949 foreslog en algoritme til løsning af et lineært programmeringsproblem, kaldet den "simplekse metode".

Matematisk programmering, som inkluderer lineær programmering, er i øjeblikket et af områderne for operationsforskning. Afhængigt af typen af ​​problemer, der løses, kan områder som lineære, ikke-lineære, diskrete, dynamisk programmering osv. Udtrykket "programmering" blev introduceret på grund af det faktum, at ukendte variabler, der er i færd med at løse et problem, normalt bestemmer programmet eller arbejdsplanen for et økonomisk objekt.

I klassisk matematisk analyse studeres den generelle formulering af problemet med at bestemme et betinget ekstremum. Men i forbindelse med udviklingen af ​​industriel produktion, transport, landbrug og banksektoren var de traditionelle resultater af matematisk analyse ikke nok. Praksisbehovet og udviklingen af ​​computerteknologi har ført til behovet for at bestemme optimale løsninger ved analyse af komplekse økonomiske systemer.

Det vigtigste værktøj til at løse sådanne problemer er matematisk modellering. I dette tilfælde bygges en simpel model først, derefter udføres dens forskning, hvilket gør det muligt at forstå, hvilke af objektets integrerende egenskaber, der ikke er fanget af det formelle skema, hvorefter dens større tilstrækkelighed ved at komplicere modellen til virkeligheden er sikret. I mange tilfælde er den første tilnærmelse til virkeligheden en model, hvor alle afhængigheder mellem de variabler, der karakteriserer objektets tilstand, er lineære. Praksis viser, at et tilstrækkeligt antal økonomiske processer er beskrevet ganske fuldt ud af lineære modeller. Følgelig spiller lineær programmering som et apparat, der gør det muligt at finde et betinget ekstremum på et sæt defineret af lineære ligninger og uligheder. vigtig rolle når man analyserer disse processer.

Lineær programmering har fået en udbredt udvikling, fordi det er fastslået, at en række planlægnings- og styringsproblemer kan formuleres i form af lineære programmeringsproblemer, til løsning af hvilke der findes effektive metoder. Ifølge eksperter vedrører cirka 80-85 % af alle optimeringsproblemer, der løses i praksis, lineære programmeringsproblemer.

Det skabte matematiske apparat i kombination med computerprogrammer, der udfører arbejdskrævende beregninger, gør det muligt i vid udstrækning at anvende lineære programmeringsmodeller i økonomisk videnskab og praksis.

Definition 1 9 . Lineær programmering (LP) er et felt inden for matematisk programmering, som er en gren af ​​matematikken, der studerer metoder til at finde ekstreme (største og mindste) værdier af en lineær funktion af et begrænset antal variabler, hvis ubekendte er underlagt lineære begrænsninger.

Denne lineære funktion kaldes målfunktionen, og begrænsningerne, som repræsenterer kvantitative sammenhænge mellem variable, der udtrykker det økonomiske problems betingelser og krav og er skrevet matematisk i form af ligninger eller uligheder, kaldes et system af begrænsninger.

En bred vifte af spørgsmål om planlægning af økonomiske processer reduceres til lineære programmeringsproblemer, hvor opgaven med at finde den bedste (optimale) løsning stilles.

Et generelt lineært programmeringsproblem (GLP) er at finde den ekstreme værdi (maksimum eller minimum) af en lineær funktion, kaldet målet 10:

fra n variabler x 1 , x 2 , …, x n med pålagte funktionsbegrænsninger:

(3.2)

og direkte restriktioner (kravet om ikke-negativitet af variabler)

, (3.3)

Hvor -en ij , b jeg , c j– givet konstante værdier.

I begrænsningssystemet (3.2) kan tegnene "mindre end eller lig med", "lig med" og "større end eller lig med" optræde samtidigt.

ZLP i en mere kortfattet form har formen:

,

med restriktioner:

;

.

Vektor` x = (x 1 , x 2 , …, x n), hvis komponenter opfylder de funktionelle og direkte begrænsninger af problemet kaldes plan(eller acceptabel løsning) ZLP.

Alle mulige løsninger dannes domæne lineære programmeringsproblemer, eller region med mulige løsninger (ODR). En gennemførlig løsning, der leverer maksimum eller minimum af den objektive funktion f(`x), kaldes den optimale plan for problemet og betegnes f(`x * ), Hvor ` x * =(x 1 * , x 2 * , …, x n * ).

En anden form for registrering af PPP:

,

Hvor f(`x * ) er den maksimale (minimum) værdi f(MED, x), overtaget alle løsninger inkluderet i sættet mulige løsninger x .

Definition 2 11 . Det matematiske udtryk for den objektive funktion og dens begrænsninger kaldes en matematisk model af et økonomisk problem.

At kompilere matematisk model nødvendig:

1) identificere variablerne;

2) skabe en objektiv funktion baseret på målet med problemet;

3) nedskriv et system af restriktioner under hensyntagen til indikatorerne i problemformuleringen og deres kvantitative mønstre.

Lineær programmering er en af ​​de mest betydningsfulde grene af matematikken, hvor det teoretiske og metodiske grundlag for at løse visse problemer studeres. Denne matematiske disciplin er meget udbredt i de sidste år i forskellige økonomiske og tekniske områder, hvor ikke den sidste rolle gives til matematisk planlægning og brug automatiske systemer beregninger. Denne gren af ​​videnskaben er afsat til studiet af lineære optimeringsmodeller. Det vil sige, at lineær programmering handler om tal. Først denne term blev foreslået af T. Koopmans i 1951. Den optimale plan for hver lineært program skal automatisk forbindes med det optimale prisniveau, det vil sige med objektivt fastsatte vurderinger.

Lineær programmering: metoder

Ved hjælp af teknikken er det muligt at løse et betydeligt antal ekstreme problemer relateret til økonomi. I I dette tilfælde Normalt skal du finde ekstremværdierne for nogle funktioner af en variabel værdi. Løsningen til et system af transformerbare ligninger og uligheder er udtrykt som grundlaget for lineær programmering. Denne type programmering er kendetegnet ved en matematisk formulering af variable, en rækkefølge og en bestemt rækkefølge af beregninger samt logisk analyse. Dette gælder:

Hvis der er matematisk sikkerhed og kvantitativ begrænsning mellem de undersøgte faktorer og variable;

Hvis der er udskiftelighed af faktorer på grund af rækkefølgen af ​​beregninger;

Hvis matematisk logik kombineres med en forståelse af essensen af ​​de fænomener, der studeres.

Lineær programmering hjælper med at beregne den optimale ydeevne af alle maskiner, produktionslinjer, enheder, samt løse problemer med rationel brug af tilgængelige materialer.

I landbruget, ved hjælp af denne metode, bestemmes minimumsomkostningerne for en foderration under hensyntagen til den tilgængelige mængde foder. Dette tager hensyn til typer og indhold af visse gavnlige stoffer i dem.

I støberi Denne teknik giver dig mulighed for at finde en løsning transport problem og problemer med blandinger, der er en del af den metallurgiske ladning. Essensen af ​​transportproblemet i dette tilfælde indebærer den optimale tilknytning af forbrugende virksomheder til virksomheder, der er involveret i produktion.

Lineær programmering: problemer

Særpræg af alle økonomiske problemer, der løses ved hjælp af lineære programmeringsteknikker, er valget visse muligheder løsninger, samt begrænsende forhold. Ved at løse et sådant problem er det muligt at finde den optimale løsning fra alle alternative muligheder.

En væsentlig værdi ved at bruge lineære programmeringsteknikker i økonomi er valget af den mest optimale mulighed fra stor mængde alle muligheder, der anses for acceptable. Sådanne problemer er næsten umulige at løse på andre måder, da kun de tillader en at finde graden af ​​rationalitet af anvendelsen Ved hjælp af lineær programmering løses et så grundlæggende problem som transport, hvilket burde minimere lastomsætningen af ​​forbrugsvarer under deres levering fra producenten.

Lineær programmering i Excel

I processen med at løse sådanne problemer er det først nødvendigt at skabe en model, som indebærer formulering af betingelser på matematisk sprog. Efter dette trin kan en løsning findes ved grafisk metode. For at gøre dette i Excel program eksisterer speciel funktion"At finde en løsning."

Som det allerede fremgår af ovenstående, har lineær programmering et meget bredt anvendelsesområde.

Lineære programmeringsmetoder bruges til at løse mange ekstreme problemer, som ofte behandles i økonomi. At løse sådanne problemer kommer ned til at finde de ekstreme værdier (maksimum og minimum) af nogle funktioner af variable mængder.
Lineær programmering er baseret på løsning af et system lineære ligninger(med transformation til ligninger og uligheder), når forholdet mellem de fænomener, der undersøges, er strengt funktionelt. Det er kendetegnet ved et matematisk udtryk for variabler, en bestemt rækkefølge, rækkefølge af beregninger (algoritme), logisk analyse. Det kan kun bruges i tilfælde, hvor de variable og faktorer, der undersøges, har matematisk sikkerhed og kvantitative begrænsninger, når faktorerne som følge af en kendt rækkefølge af beregninger er udskiftelige, når logikken i beregningerne, matematisk logik kombineres med en logisk forståelse af essensen af ​​det fænomen, der undersøges.
Ved at bruge denne metode i industriel produktion for eksempel det optimale overordnet ydelse maskiner, enheder, produktionslinjer (med en given række af produkter og andre givne værdier), er problemet med rationel skæring af materialer (med optimalt udbytte af emner) løst. I landbruget bruges det til at bestemme minimumsomkostninger foderrationer for en given mængde foder (efter type og næringsstoffer indeholdt i dem). Blandingsproblemet kan også finde anvendelse i støberiproduktion (sammensætning af metallurgisk ladning). Samme metode bruges til at løse transportproblemet, problemet med rationelt at knytte forbrugervirksomheder til producerende virksomheder.
Alle økonomiske problemer, der løses ved hjælp af lineær programmering, er kendetegnet ved alternative løsninger og visse begrænsende betingelser. At løse et sådant problem betyder at vælge den bedste, Optimale, blandt alle tilladte (alternative) muligheder. Betydningen og værdien af ​​at bruge den lineære programmeringsmetode i økonomi ligger i, at den optimale mulighed vælges blandt et meget betydeligt antal alternative muligheder. Det er næsten umuligt at løse sådanne problemer ved hjælp af andre metoder.

Som et eksempel kan du overveje at løse problemet med rationel brug af driftstiden for produktionsudstyr.
I overensstemmelse med driftsplanen producerede slibesektionen i den første uge af december 500 ringe til lejer af type A, 300 ringe til lejer af type B og 450 ringe til lejer af type B. Alle ringe blev slebet på to udskiftelige maskiner. anderledes ydeevne. Maskintiden for hver maskine er 5000 minutter. Kompleksiteten af ​​operationer (i minutter pr. ring) i fremstillingen af ​​forskellige ringe er karakteriseret ved følgende data (tabel 6.5).
Tabel 6.5
Det er nødvendigt at bestemme den optimale mulighed for at fordele operationer på tværs af maskiner og den tid, der ville blive brugt med denne optimale mulighed. Lad os fuldføre opgaven simpleks metode.
For at kompilere en matematisk model af dette problem introducerer vi følgende symboler: henholdsvis jc, x2, xъ, - antallet af ringe til lejer af type L, B, V, produceret på maskine I; x4, x5, x6 - henholdsvis antallet af ringe til lejer af type A, B, C, produceret på maskine II.
Lineær form, der afspejler optimalitetskriteriet, vil have formen:
min a(x) = 4x,-f 10x2-f 10x3-f 6x4-f 8x5+20x6 med begrænsninger
4х, -f 10х2 -f 10;t3 lt; 5000
6x4 -f 8x5 -f 20x6 ~lt; 5000
x, = 500
x2 + x5 = 300
x3 + x6 = 450
Xj^0,j=l, ..., 6

Lad os transformere problemtilstanden ved at introducere yderligere (hjælpe) og fiktive variable. Lad os skrive tilstanden sådan:
spids lt;x(x) = 4dg, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Mx9 + Mx(0+Mx(,
Et system af ligninger, der afspejler de restriktive betingelser for computertid og mængden af ​​producerede produkter:
4x, + l(bc2 + 10x3 +x1 = 5000
6x4 + 8x5 + 20x6 + xs = 5000
Xj + x4 + x9 = 500
x2 + x5 + x10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
Løsningen på dette problem er præsenteret i tabel. 6.6. Den optimale mulighed blev opnået på det syvende trin (iteration). Hvis maskine I producerede 125 lejeringe af type A, 450 lejeringe af type B, og maskine II producerede 375 lejeringe af type A og 300 lejeringe af type B, ville 350 minutters maskintid med en sådan belastning af udstyr være frigivet til maskine II. Den samlede tid brugt under den optimale mulighed ville være 9650 minutter, mens der faktisk blev brugt 10.000 minutters computertid.
Et meget typisk problem, der løses ved hjælp af lineær programmering, er transportproblemet. Dens betydning er at minimere lastomsætningen ved levering af forbrugsvarer fra producent til forbruger, fra engroslagre og baser til detailforretninger. Det kan løses ved hjælp af simpleksmetoden eller distributionsmetoden.
Løsningen på transportproblemet ved hjælp af distributionsmetoden blev givet i tredje udgave af lærebogen "Theory of Economic Analysis" ("Finance and Statistics", 1996).

Løsning af problemet med rationel brug af værktøjsmaskiner ved hjælp af simplex-metoden

Basis	Med	Ro	4	10	10	6	8	20	0	0	m	m	m
			L	Rg	R	L	R ъ		Pi	P8	R*	L 0	L,
L	0	5000	4	10	0	0	0	0	і	0	0	0	0
R,	0	5000	0	0	0	6	8	20	0	1	0	0	0
L	m	500	1	0	0	1	0	0	0	0	1	0	0
L 0	m	300	w	0	0	0	1	0	0	0	0	1	0
L.	m	450	0	0	1	0	0	1	0	0	0	0	1
Zj-Cj		1250 mio	M-4	M-10	M-10	M-6	M-8	M-20	0	0	0	0	0
Pi	0	3000	0	10	10	-4	0	0	0	0	-4	0	0
R*	0	5000	0	0	0	6	8	20	1	1	0	0	0
Ro	4	500	1	0	0	1	0	0	0	0	1	0	0
Lo	m	300	0	1	0	0	w	0	0	0	0	1	0
L.	m	450	0	0	1	0	0	1	0	0	0	0	1
zr-9		750L/+2000	0	M-10	M-10	-2	M-8	OM 2	0	0	-M + 4	0	0

Basis	MED	P0	4	Pi	10	6	8	20	0	0	m	m	M
			Pi	10	^3	l	P5	s6	Pi	R"	s9	Pi 0	RC
Pi	0	3000	0	10	10	-4	0	0	1	0	-4	0	0
R*	0	2600	0	-8	0	6	0	20	0	1	0	-8	0
Pi	4	500	1	0	0	1	0	0	0	0	1	0	0
P5	8	300	0	1	0	0	1	0	0	0	0	1	0
RP	M	450	0	0	1	0	0	1	0	0	0	0	1
Zj-Cj		450L/+4400	0	-2	M-10	-2	0	M-20	0	0	-M+4	-M+8	0
R	10	300	0	1	1	4 10	0	0	1 10	0	4 10	0	0
R%	0	2600	0	-8	0	6	0	20	0	1	0	-8	0
Pi	4	500	1	0	0	1	0	0	0	0	1	0	0
P5	8	300	0	1	0	0	1	0	0	0	0	1	0
RC	M	150	0	-1	0	j4_ 10	0	1	_J_ 10	0	4 10	0	1
zrCj		150L/+7400	0	-M+S	0	- M-6 10	0	M-20	- ~M+1 10	0	-±m 10	- Af+8"	0

Basis	Med	L,	4	10	10	6	8	20	0	0			M	M	m
			L	Rg	L	l	PS	s6	Pi	pamp;			P9	Lo	l.
L	10	300	0	1	1	4	0	0	1		0		4	0	0
						“10			At				“ 10
s6	20	130	0	4	0	3	0	1	0		1		0	4	0
				~Ї0		10					20			10
l	4	500	1	0	0	1	0	0	0		0		1	0	0
PS	8	300	0	1	0	0	1	0	0		0		0	1	0
R\\	M	20	0	6	0	1	0	0	1		1		4	4	1
				10		~10			At		20		At	10
Zj-Cj		20M+10000	0		0	-m	0	0	m+\		-m+\		--M	-*M	0
				10		10			10	20			10	10
l	10	380	0	14	1	0	0	0	3		2		12	0	0
				10					10		10		10
R%	20	70	0	14	0	0	0	1	3		2		12	16	-3
				10					10		10		10	10
L	4	300	1	6	0	0	0	0	1		1		-3		-10
											2
p5	8	300	0	1	0	0	1	0	0		0		0	1	0
P4	6	200	0	-6	0	1	0	0	-1		1		4	4	10
											’ 2
Z.-Ci		10000	0	0	0	0	0	0	1	1			-M	-M	-m

Basis		Lgt;	4	10	10	6	8	20	0	0	m	m	l/
	O		L	Rg	ръ	R*	P5	P6	L	Pamp;	s9	L 0	l.
Rg	10	450	0	0	1	0	0	1	0	0
R%	0	350	0	7	0	0	0	5	3 5	1
L	4	125	1	5 2	0	0	0	5 2	1 4	0
PS	8	300	0	1	0	0	1	0	0	0
P4	6	375	0	5 2	0	1	0	5 2	1 4	0
Zj-Cj		9650	0	-7	0	0	0	-5	1 2	0

Anmærkning: Dette foredrag dækker en række emner, der er helliget lineær programmering som en af ​​grenene af matematisk programmering; formulerer især hovedtyperne af lineære programmeringsproblemer, afslører forskellene mellem disse problemer og klassiske problemer matematisk analyse; introducerer forskellige former for registrering af disse opgaver, udfører deres formulering og undersøgelse af strukturen. Spørgsmålet om at løse lineære programmeringsproblemer ved hjælp af simpleksmetoden er mest udforsket.

1. Begrebet matematisk programmering

er en matematisk disciplin, der udvikler metoder til at finde ekstreme værdier objektiv funktion blandt sættet af dets mulige værdier, bestemt af restriktioner.

Tilstedeværelsen af ​​begrænsninger gør problemerne fundamentalt forskellige fra de klassiske problemer med matematisk analyse med at finde ekstreme værdier af en funktion. Metoder til matematisk analyse til søgning ekstremum af funktionen i opgaver matematisk programmering vise sig at være uegnet.

At løse problemer matematisk programmering Særlige metoder og teorier er blevet udviklet og er under udvikling. Da løsning af disse problemer kræver at udføre en betydelig mængde beregninger, hvornår sammenlignende vurdering metoder stor betydning er givet til effektiviteten og bekvemmeligheden af ​​deres implementering på en computer.

Det kan betragtes som et sæt af uafhængige sektioner, der er involveret i undersøgelse og udvikling af metoder til at løse visse klasser af problemer.

Afhængigt af egenskaberne af den objektive funktion og begrænsningsfunktionen, alle problemer matematisk programmering er opdelt i to hovedklasser:

• lineære programmeringsproblemer,
• opgaver ikke-lineær programmering.

Hvis den objektive funktion og begrænsningsfunktionerne er lineære funktioner, så er det tilsvarende problem med at finde et ekstremum et lineært programmeringsproblem. Hvis mindst én af specificerede funktioner er ikke-lineær, så er det tilsvarende problem med at finde et ekstremum problemet ikke-lineær programmering.

2. Begrebet lineær programmering. Typer af lineære programmeringsproblemer

Lineær programmering(LP) – et af de første og mest grundigt studerede afsnit matematisk programmering. Nemlig lineær programmering var det afsnit, hvorfra selve disciplinen begyndte at udvikle sig" matematisk programmering". Udtrykket "programmering" i disciplinens titel har intet til fælles med udtrykket "programmering (dvs. kompilering af et program) til en computer" har intet at gøre med disciplinen " lineær programmering" opstod allerede før den tid, hvor computere begyndte at blive meget brugt til at løse matematiske, tekniske, økonomiske og andre problemer.

Begrebet " lineær programmering" opstod som følge af en unøjagtig oversættelse af det engelske "lineær programmering". En af betydningerne af ordet "programmering" er at lave planer, planlægge. Derfor ville den korrekte oversættelse af det engelske "lineær programmering" ikke være " lineær programmering", A" lineær planlægning", som mere præcist afspejler indholdet af disciplinen. Dog vilkårene lineær programmering, ikke-lineær programmering, matematisk programmering etc. er blevet almindeligt accepterede i vor litteratur og vil derfor blive bevaret.

Så, lineær programmering opstod efter Anden Verdenskrig og begyndte at udvikle sig hurtigt, hvilket tiltrak sig opmærksomhed fra matematikere, økonomer og ingeniører på grund af muligheden for bred praktisk anvendelse såvel som matematisk harmoni.

Det kan man sige lineær programmering anvendelig til at løse matematiske modeller af de processer og systemer, der kan baseres på hypotesen om en lineær repræsentation af den virkelige verden.

Lineær programmering bruges til at løse økonomiske problemer, i opgaver som ledelse og produktionsplanlægning; i problemer med at bestemme optimal placering udstyr på søfartøjer, i værksteder; i problemer med at bestemme optimal plan godstransport (transportopgave); i problemer med optimal personalefordeling mv.

Lineært programmeringsproblem(LP), som det allerede fremgår af det, der blev sagt ovenfor, består i at finde minimum (eller maksimum) af en lineær funktion under lineære restriktioner.

Generel form problemet har formen: find under betingelserne

Sammen med generel form også meget brugt kanonisk Og standard formularer. Både i kanonisk og standardform

De der. alle variabler i enhver acceptabel løsning opgaver skal have ikke-negative værdier (sådanne variabler kaldes normalt ikke-negativ i modsætning til den såkaldte gratis variabler, hvis værdiområde ikke er underlagt sådanne begrænsninger). Forskellen mellem disse former er, at i det ene tilfælde I 2 = 0, og i det andet - I 1 = 0.

LP-problemet i kanonisk form.

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.

Hovedindholdet af simplex-metoden er som følger:

1. Angiv en metode til at finde den optimale referenceløsning
2. Angiv metoden til overgang fra en referenceløsning til en anden, hvor værdien af ​​den objektive funktion vil være tættere på den optimale, dvs. angive en måde at forbedre referenceløsningen på
3. Sæt kriterier, der giver dig mulighed for omgående at stoppe med at søge efter supportløsninger ved den optimale løsning eller drage en konklusion om fraværet af en 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
2. 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 26.1

Løs problemet ved hjælp af simpleksmetoden:

Løsning:

Vi bringer problemet til kanonisk form.

For at gøre dette introducerer vi en ekstra variabel x 6 med koefficient +1 til venstre side af den første ulighedsbegrænsning. Variablen x 6 er inkluderet i objektivfunktionen med en koefficient på nul (dvs. den er ikke inkluderet).

Vi får:

Vi finder den indledende supportløsning. For at gøre dette sætter vi lighedstegn mellem frie (uløste) variabler til nul x1 = x2 = x3 = 0.

Vi får referenceløsning X1 = (0,0,0,24,30,6) med enhedsbasis B1 = (A4, A5, A6).

Vi beregner estimater af vektornedbrydning betingelser på basis af referenceopløsningen ifølge 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 af den tilsvarende vektor A k i henhold til referenceopløsningens basis
• C k er koefficienten 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 ind simplex bord:

Ø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. På korrekte placering Koefficienterne for den objektive funktion i kolonnen "C b" af estimatet af enhedsvektorerne inkluderet i grundlaget er altid lig med nul.

I sidste linje tabeller med estimater af Δ k i kolonnen "A 0" er værdierne af objektivfunktionen 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 ​​objektivfunktionen 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 ΔZ 1 = - 6*(- 2) = 12 i basis, og den tredje vektor ΔZ 3 = - 3*(- 9) = 27.

Derfor for en hurtigere tilgang til optimal løsning det er 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 opnå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 et negativt estimat Δ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 udledt af basis. For at gøre dette beregner vi parameteren θ 02 for den anden kolonne, den er lig med 7 for l = 2. Derfor udleder vi den anden basisvektor A4 fra basis. Vi udfører Jordan-transformationen med elementet x 22 = 3, vi får den tredje referencelø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: max Z(X) = 201 ved X = (0,7,10,0,63).

Lineær programmeringsmetode i økonomisk analyse

Lineær programmeringsmetode gør det muligt at retfærdiggøre den mest optimale økonomiske løsning under forhold med strenge restriktioner relateret til de ressourcer, der bruges i produktionen (anlægsaktiver, materialer, arbejdskraft). Anvendelse af denne metode i økonomisk analyse giver dig mulighed for at løse problemer primært relateret til planlægning af organisationens aktiviteter. Denne metode hjælper med at bestemme de optimale outputniveauer, såvel som anvisningerne for de fleste effektiv brug produktionsressourcer til rådighed for organisationen.

Ved hjælp af denne metode løses de såkaldte ekstreme problemer, som består i at finde ekstreme værdier, det vil sige maksimum og minimum af funktioner af variable mængder.

Denne periode er baseret på løsning af et system af lineære ligninger i tilfælde, hvor de analyserede økonomiske fænomener er forbundet med en lineær, strengt funktionel afhængighed. Den lineære programmeringsmetode bruges til at analysere variable i nærvær af visse begrænsende faktorer.

Det er meget almindeligt at løse det såkaldte transportproblem ved hjælp af den lineære programmeringsmetode. Indholdet af denne opgave er at minimere omkostningerne i forbindelse med driften Køretøj under eksisterende restriktioner med hensyn til antallet af køretøjer, deres bæreevne, varigheden af ​​deres drift, og hvis der er behov for vedligeholdelse maksimal mængde kunder.

Udover, denne metode bruges i vid udstrækning til at løse planlægningsproblemer. Denne opgave består af en sådan fordeling af driftstiden for personalet i en given organisation, som ville være mest acceptabel både for medlemmerne af dette personale og for organisationens kunder.

Denne opgave er at maksimere antallet af klienter, der betjenes under betingelser med begrænsninger af antallet af ledige medarbejdere, såvel som arbejdstidsfonden.

Den lineære programmeringsmetode er således ret almindelig i placerings- og brugsanalyse. forskellige typer ressourcer, såvel som i processen med at planlægge og forudsige organisationers aktiviteter.

Endnu matematisk programmering kan også anvendes på de økonomiske fænomener, hvis forhold ikke er lineært. Til dette formål kan ikke-lineære, dynamiske og konvekse programmeringsmetoder anvendes.

Ikke-lineær programmering er afhængig af den ikke-lineære karakter af den objektive funktion eller begrænsninger eller begge dele. Formerne for den objektive funktion og ulighedsbegrænsninger i disse forhold kan være forskellige.

Ikke-lineær programmering bruges i økonomisk analyse, især ved etablering af forholdet mellem indikatorer, der udtrykker effektiviteten af ​​en organisations aktiviteter og omfanget af denne aktivitet, strukturen af ​​produktionsomkostninger, markedsforhold osv.

Dynamisk programmering er baseret på at konstruere et beslutningstræ. Hvert niveau af dette træ tjener som et trin til at bestemme konsekvenserne af en tidligere beslutning og for at eliminere ineffektive muligheder for denne beslutning. Således har dynamisk programmering en flertrins, flertrins karakter. Denne type programmering bruges i økonomisk analyse til at finde optimale muligheder udvikling af organisationen både nu og i fremtiden.

Konveks programmering er en form for ikke-lineær programmering. Denne type programmering udtrykker den ikke-lineære karakter af forholdet mellem resultaterne af en organisations aktiviteter og dens omkostninger. Konveks (alias konkav) programmering analyserer konvekse objektivfunktioner og konvekse begrænsningssystemer (punkter acceptable værdier). Konveks programmering bruges i analysen af ​​økonomiske aktiviteter med det formål at minimere omkostningerne, og konkav programmering med det formål at maksimere indkomsten under eksisterende restriktioner på virkningen af ​​faktorer, der påvirker de analyserede indikatorer på den modsatte måde. Som følge heraf minimeres konvekse objektivfunktioner med de typer programmering, der overvejes, og konkave objektivfunktioner maksimeres.