Løsning af lineære programmeringsproblemer. Lineær programmering

En lang række økonomiske problemer reduceres til lineære matematiske modeller. Traditionelt kaldes de lineære programmeringsmodeller. Lineær programmering betyder lineær planlægning, dvs. modtager optimal plan-løsninger på problemer med lineær struktur. Det bruges normalt af specialister fra hovedkvarteret til at løse produktionsproblemer. Typiske eksempler på anvendelser af den lineære programmeringsmodel er følgende:

integreret produktionsplanlægning (udarbejdelse af produktionsplaner, der minimerer de samlede omkostninger på grund af ændringer i rentesatserne);

planlægning af produktsortimentet (bestemmelse af den optimale struktur for fødevareproduktion til mennesker);

routing af produktproduktion (bestemmelse af det optimale teknologisk vej fremstilling af produktet);

lagerregulering (bestemmelse af den optimale kombination af produkter på lageret);

produktionsplanlægning (udarbejdelse af tidsplaner, der minimerer omkostningerne, under hensyntagen til omkostningerne ved vedligeholdelse af varebeholdninger, betaling af overarbejde og eksterne ordrer);

planlægning af produktdistribution mv.

I sin mest generelle form er lineær programmering reduceret til et optimeringsproblem og er skrevet i følgende form:

For at løse et optimeringsproblem er det nok at finde dens optimale løsning, dvs. angive
sådan at f(x 0 )≥ f(x) på enhver
, eller i tilfælde af minimering - f(x 0 )≤ f(x) på enhver
.

Et optimeringsproblem er uløst, hvis det ikke har optimal løsning. Især vil maksimeringsproblemet være uløst, hvis objektiv funktion f(x) er ikke afgrænset ovenfra på det tilladte sæt W.

Løsningsmetoder optimeringsproblemer afhænger af typen af objektiv funktion f(x) , og fra strukturen tilladt sæt W. Hvis målfunktionen i problemet er en funktion P variable, så kaldes løsningsmetoderne metoder matematisk programmering.

Et lineært programmeringsproblem er et operationsforskningsproblem, hvis matematiske model har formen:

Samtidig er systemet lineære ligninger(2) og uligheder (3), (4), som bestemmer det tilladte sæt af løsninger på problemet W, kaldes systemet af begrænsninger af et lineært programmeringsproblem og den lineære funktion f(x) kaldet den objektive funktion eller optimalitetskriteriet.

Hvis den matematiske model af et lineært programmeringsproblem har formen:

så siger de, at problemet præsenteres i kanonisk form.

Ethvert lineært programmeringsproblem kan reduceres til et lineært programmeringsproblem i kanonisk form, at flytte maksimering til minimering, fra ulighedsbegrænsninger til lighedsbegrænsninger og erstatte variabler, der ikke adlyder ikke-negativitetsbetingelsen. Maksimering af en bestemt funktion svarer til at minimere den samme funktion taget med det modsatte fortegn og omvendt.

Reglen for at reducere et lineært programmeringsproblem til kanonisk form er som følgende:

1) 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;

2) hvis højre side af restriktionerne er negativ, skal denne restriktion ganges med (-1);

3) hvis der er uligheder mellem restriktionerne, så transformeres de til ligheder ved at indføre yderligere ikke-negative variabler;

4) 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 1 , hvor 1 er et frit indeks, x’ k ≥ 0, x 1 ≥ 0.

Ved at opsummere ovenstående kan vi drage følgende konklusioner:

1. Begrænsninger i lineære programmeringsproblemer kan udtrykkes ved både ligheder og uligheder.

2. En lineær funktion kan have tendens til både et maksimum og et minimum.

3. Variabler i modellen er altid ikke-negative.

4. Fra ethvert lineært programmeringsproblem kan du gå til det kanoniske (hoved) lineære programmeringsproblem.

Hvert lineært programmeringsproblem kan sammenlignes med et andet lineært programmeringsproblem, der er dobbelt til det oprindelige (direkte).

Overvej et lineært programmeringsproblem af følgende form:

………………………..

Problemet kræver maksimering af den objektive funktion; alle begrænsninger er uligheder med ≤ fortegn, alle variable x 1 , X 2 ,…,X P P kontrolvariable og m restriktioner. Koefficienter af variable i objektivfunktionen: c 1 , c 2 ,…, c n; gratis medlemmer: b 1 , b 2 ,…, b m .

Det dobbelte lineære programmeringsproblem har formen:

………………………..

I et dobbelt problem er det nødvendigt at finde minimum af den objektive funktion, begrænsninger - uligheder med tegnet ≥, kontrolvariable y 1 , y 2 ,…, y m ikke-negativ. Opgaven indeholder m kontrolvariable og n restriktioner. Koefficienter for problemets objektive funktion b 1 , b 2 ,…, b m er frie vilkår for det originale lineære programmeringsproblem og frie vilkår for det dobbelte problem c 1 , c 2 ,…, c n – koefficienter for den objektive funktion af det oprindelige lineære programmeringsproblem. Koefficientmatricen for det dobbelte problem transponeres, dvs. Rækker erstattes af kolonner, og kolonner erstattes af rækker.

Opgaver (9)–(10) og (11)–(12) danner et par af problemer, kaldet et dobbeltpar i lineær programmering.

Det dobbelte problem i forhold til det originale er sammensat efter følgende regler:

1. Objektiv funktion oprindelige problem er sat til det maksimale, og den dobbelte objektivfunktion er sat til minimum.

2. Matrix EN(13)

sammensat af koefficienter for ukendte i systemet af begrænsninger (10) i det oprindelige problem (9) – (10) og en lignende matrix i det dobbelte problem (11) – (12) opnås fra hinanden ved transponering.

3. Antallet af variabler i det dobbelte problem (11) – (12) er lig med antallet af restriktioner i systemet (10) for det oprindelige problem, og antallet af restriktioner i systemet (12) for det dobbelte problem er lig med antallet af variable i den oprindelige opgave.

4. Koefficienterne for de ukendte i den objektive funktion (11) af det dobbelte problem er de frie led i systemet (10) af det oprindelige problem, og højre side i begrænsningerne af systemet (12) i dobbelt problem er koefficienterne for de ukendte i objektivfunktionen (9) af det oprindelige problem.

5. Hvis variablen x j af det oprindelige problem (9) – (10) kan derfor kun tage ikke-negative værdier j- Begrænsningen i system (12) af det dobbelte problem er en ulighed af formen ≥. Hvis variablen x j kan tage både positive og negative værdier, så j- e begrænsning i system (12) er ligningen. Lignende forbindelser finder sted mellem begrænsninger (10) af det oprindelige problem og variablerne for det dobbelte problem. Hvis jeg- Hvis begrænsningen i system (10) af det oprindelige problem er en ulighed, så jeg- Jeg er variabelen i det dobbelte problem y jeg ≥ 0. Hvis jeg- Hvis begrænsningen er en ligning, så er variablen y jeg kan tage både positive og negative værdier.

Ideen om sekventiel forbedring af løsningen dannede grundlaget for en universel metode til løsning af lineære programmeringsproblemer - simplex-metoden. Den geometriske betydning af denne metode består i en sekventiel overgang fra det ene toppunkt af begrænsningspolyederet (kaldet det indledende) til det tilstødende, hvor den lineære funktion tager bedst (iht. i det mindste, ikke den værste) værdi (i forhold til målet med problemet), indtil den optimale løsning er fundet - det toppunkt, hvor den optimale værdi af målfunktionen opnås (hvis problemet har et endeligt optimum). Metodens ideer blev offentliggjort af den russiske videnskabsmand L.V. Kantorovich i 1939

For at anvende simplex-metoden introduceres yderligere variabler i problembegrænsningerne y 1 , y 2 ,…, y jeg og tilstanden af det oprindelige problem har formen:

……….…………………..

Denne erklæring kan præsenteres i form af en tabel - den første tabel i simpleksmetoden (tabel 1.1).

Tabel 1.1.

Første simpleksbord

	Gratis medlemmer	Gratis variabler
	Gratis medlemmer	x 1	x 2	x n
y 1	b 1	-en 11	-en 12	-en 1n
y 2	b 2	-en 21	-en 22	-en 2n

y m	b m	-en m1	-en m2	-en mn
Indekslinje		-c 1	-c 2	-c n

For at kompilere en simplekstabel kan du anvende visse regler.

1. For det første bord:

a) skriv i første kolonne y m– grundlæggende variable, der er i ligningerne til venstre;

b) frie variable -en mn taget ud til øverste linje borde;

c) koefficienterne foran de frie variable skrives i de resterende kolonner.

2. For efterfølgende tabeller:

a) det mindste negative element i indekslinjen vælges ved at finde maksimum, men det største positive element vælges ved at finde minimum, eksklusive vektoren af frie led;

b) dette element definerer nøglekolonnevektoren, og det indtastes i basis;

c) komponenterne i vektoren af frie udtryk er divideret med de positive elementer i nøglekolonnen;

d) den mindste er valgt fra de opnåede forhold;

e) en rækkevektor, der indeholder den mindste positive kvotient, er nøglen og er afledt af basis;

f) i skæringspunktet mellem nøglerækkerne og kolonnen er der et tilladeligt element;

g) matrix transformation:

Hvert nøglestrengelement er opdelt i et aktiveringselement. De resulterende kvotienter er nøglerækkeelementerne i følgende tabel,

Indtast kolonnen nyt bord– nuller, med undtagelse af det resolverende element,

De resterende elementer i den nye tabel beregnes i henhold til følgende skema:

Nyt element = Gammelt element –

- Nøglerækkeelement*Nøglekolonneelement

Tilladende element

Hvis nulrækken (kolonnen) indeholder nul, så ændres den tilsvarende kolonne (række0 i den nye tabel ikke.

3. Punkterne "a" - "g" gentages, indtil der ikke er et eneste negativt element tilbage i indekslinjen, når man finder maksimum (men ikke et enkelt positivt element, når man finder minimum).

Eksempel 1.1. Det er påkrævet at træffe en beslutning om den optimale plan for produktion af strik i en måned på Sviyazh OJSC ved hjælp af simplex-metoden.

Lad os fastlægge en plan for produktion af mænds strikmodeller for at opnå maksimal profit med givne ressourcer ved at konstruere en matematisk model. De indledende data er vist i tabel 1.2.

Tabel 1.2.

Indledende data

Ressourcer ( jeg)	Produkttype ( j)				Ressourcereserve ( b jeg)
	Sportsbukser model 7060	Herre sweater model 55-1	Herretrøje model 38-0	Sportsdragt model
	specifikt ressourceforbrug ( -en ij)
Arbejdskraft
Materiale
Udstyr

	x 1	x 2	x 3	x 4

De indledende data om det specifikke forbrug af materialer og arbejdskraft er angivet i tabellen. 1.2 i overensstemmelse med den lovgivningsmæssige og teknologiske dokumentation, der er gældende i organisationen. Linjen "Materielle ressourcer" registrerer forbrugsraten for den mest knappe (begrænsede 0) type materialer - uldgarn. Dette materiale har den højeste forbrugsrate og omkostninger.

Linjen "Udstyr" viser den sammenfattende arbejdsintensitet ved fremstilling af en produktenhed i standardtimer som totalen for alle deloperationer. Andre typer ressourcer tages også i naturlige enheder: arbejdsressourcer - i timer; materiale - i dm 2.

Linjen "Profit" afspejler fortjenesten ved salg af en produktenhed, taget fra det planlagte omkostningsestimat for en produktenhed.

igennem x 1 , x 2 , x 3 , x 4 angivet mængden af producerede produkter for hver type sortiment.

Ifølge reglen for at konstruere et standard lineært programmeringsproblem, lad os skabe en matematisk model:

I problemets begrænsninger introducerer vi yderligere variable y 1 , y 2 , y 3 og omskriv problemtilstanden i form af en ligning:

Det sidste udsagn kan præsenteres i form af tabel 1.3 - den første tabel i simpleksmetoden, som vi vil bruge til at løse det lineære programmeringsproblem.

Tabel 1.3.

Første simpleksbord

	Gratis medlemmer	Gratis variabler
	Gratis medlemmer	x 1	x 2	x 3	x 4
y 1
y 2
y 3
Indekslinje

Den første kolonne indeholder y jeg – de grundlæggende variabler er dem til venstre for ligningen, og de frie variable x j placeret i øverste række af tabellen. De resterende kolonner indeholder koefficienterne for de frie variable. Indekslinjen er resultatet af at trække koefficienterne foran de frie variable fra nul.

For at bygge den næste tabel vælges det mindste negative element i indeksrækken (dette er 222). Dette element definerer nøglekolonnevektoren, og den introduceres i basis. Komponenterne i vektoren af frie udtryk divideres med de positive elementer i nøglekolonnen, og den mindste vælges fra de resulterende forhold. Rækkevektoren, der indeholder den mindste positive kvotient, er den vigtigste og er afledt af basis ( y 2 ). I skæringspunktet mellem nøglerækkerne og kolonnen er der et aktiveringselement (dette er 55,50).

Hvert nøglestrengelement opdeles derefter i et aktiveringselement. De resulterende kvotienter er elementerne i nøglerækken i følgende tabel. Som et resultat blev den anden simplex-tabel opnået (tabel 1.4).

Tabel 1.4.

Andet simpleksbord

	Gratis medlemmer	Gratis variabler
	Gratis medlemmer	x 1	x 2	x 3	x 4
y 1
y 2
y 3
Indekslinje

Da et negativt element er dukket op i indekslinjen, skal alle lignende trin gentages, og en tredje simplekstabel skal bygges.

Resultatet er en tabel. 1.5.

Tabel 1.5.

Endelig simplex tabel

	Gratis medlemmer	Gratis variabler
	Gratis medlemmer	x 1	x 2	x 3	x 4
y 1
y 2
y 3
Indekslinje

Baseret på tabel 1.5 kan vi drage konklusioner: i kolonnen med frie udtryk er alle elementer positive (dette betyder, at den resulterende løsning er tilladt); i indekslinjen er alle elementer også positive (dette betyder, at den resulterende løsning er optimal, dvs. den maksimerer den objektive funktion); den optimale plan ville være følgende værdier:
(hvilket betyder, at de er grundlæggende);
(da de er gratis); objektiv funktion L= 4 201 195.

Det følger endvidere af tabel 1.5, at grundvariablen y 3 =9716, og frie variable y 1 = y 2 = 0, dvs. i den optimale plan er reserverne af arbejdskraft og materielle ressourcer lig med nul, da de er fuldt ud brugt. En reserve af udstyrsressourcer y 2 = 9716, hvilket angiver dets overskud.

Som et resultat af anvendelsen af den lineære programmeringsmetode blev det således besluttet at producere herretrøjer af den valgte model i mængden af 3981 styk, herretrøjer model 55-1 i mængden af 29.875 stykker.

Formålet med tjenesten. Online lommeregner designet til at løse lineære programmeringsproblemer simpleks metode ved at gå til KZLP Og SZLP. I dette tilfælde er problemet med at finde minimum af objektivfunktionen reduceret til problemet med at finde maksimum gennem transformationen af objektivfunktionen F*(X) = -F(X) . Det er også muligt at skabe et dobbelt problem.

Løsningen sker i tre trin:

Overgang til KZLP. Enhver LLP af formen ax ≤ b , ax ≥ b , ax = b (F(X) → extr) reduceres til formen ax = b , F(X) → max ;
Overgang til SZLP. En CLLP af formen ax = b reducerer til formen ax ≤ b , F(X) → max ;
Løsning ved hjælp af simplex-metoden;

Instruktioner. Vælg antallet af variable og antallet af rækker (antal begrænsninger). Den resulterende løsning gemmes i en Word-fil.

Overgang fra objektivfunktionens minimeringsproblem til maksimeringsproblemet

Problemet med at minimere den objektive funktion F(X) kan let reduceres til problemet med at maksimere funktionen F*(X) under de samme restriktioner ved at introducere funktionen: F*(X) = -F(X) . Begge problemer har samme løsning X*, og samtidig min(F(X)) = -max(F*(X)) .
Lad os illustrere dette faktum grafisk:

F(x) → min

F(x) → maks

For at optimere målfunktionen bruger vi følgende begreber og metoder.
Grundplan– en plan med definerede gennem frie grundvariable.
Grundplan – referenceplan med nul grundvariable.
Optimal plan– en grundplan, der tilfredsstiller optimal funktion mål (FC).

Førende (løsende) element er koefficienten for det frie ukendte, som bliver den grundlæggende, og selve koefficienten konverteres til enhed.
Vejledning– linjen for det førende element, hvor den grundlæggende ukendte er placeret med en enhedskoefficient, udelukket under transformationen (linje med den minimale begrænsende koefficient, se nedenfor).
Vejledningssøjle– kolonne af det førende element, hvis frie ukendte er konverteret til det grundlæggende (kolonne med maksimalt udbytte, se nedenunder).

Variabler x 1, ..., x m, inkluderet med enhedskoefficienter i kun én af systemets ligning, med nul koefficienter i resten, kaldes grundlæggende eller afhængig. I kanonisk system Hver ligning har nøjagtig én basisvariabel. Overgangen udføres efter Gauss-Jordan-metoden. Hovedideen med denne metode er at reducere et system af ligninger med n ukendte til en kanonisk form ved hjælp af elementære operationer på strenge.
Hvile n-m variable(x m +1 ,…, x n) kaldes ikke-grundlæggende eller uafhængige variabler.

Grundlæggende løsning hedder tilladt basisløsning, hvis værdierne af de grundlæggende variabler inkluderet i det x j ≥0, hvilket svarer til ikke-negativitetsbetingelsen b j ≥0.
En mulig basisløsning er hjørnepunkt tilladeligt sæt S af et lineært programmeringsproblem og kaldes nogle gange referenceplan.
Hvis der blandt de ikke-negative tal b j er lig med nul, så kaldes den tilladte basisløsning degenerere(degenereret hjørnepunkt) og det tilsvarende lineære programmeringsproblem kaldes degenerere.

Eksempel nr. 1. Reducer det lineære programmeringsproblem til en standard ZLP.
F(X) = x 1 + 2x 2 - 2x 3 → min med begrænsninger:
4x 1 + 3x 2 - x 3 ≤10
- 2x 2 + 5x 3 ≥3
x 1 + 2 x 3 =9
Til medbringelse af PAP'er til den kanoniske form er det nødvendigt:
1. Skift fortegn for den objektive funktion. Lad os reducere problemet F(X) → min til problemet F(X) → max. For at gøre dette skal du gange F(X) med (-1). I den første betydningsulighed (≤) introducerer vi grundvariablen x 4 ; i den anden betydningsulighed (≥) introducerer vi grundvariablen x 5 med et minustegn.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Overgang til SZLP.
Udvidet matrix af systemet med lighedsbegrænsninger for dette problem:

4	3	-1	1	0	10
0	-2	5	0	-1	3
1	0	2	0	0	9

Lad os reducere systemet til identitetsmatrixen ved hjælp af Jordan-transformationsmetoden.
1. Du kan vælge x 4 som basisvariabel.
2. Vi vælger x 2 som grundvariabel.
Opløsningselement RE=-2. Linjen svarende til variablen x 2 opnås ved at dividere alle elementer i linjen x 2 med det opløselige element RE = -2. I stedet for det opløsende element får vi 1. I de resterende celler i x 2-kolonnen skriver vi nuller. Alle andre elementer bestemmes af rektangelreglen. Lad os præsentere beregningen af hvert element i form af en tabel:

4-(0 3):-2	3-(-2 3):-2	-1-(5 3):-2	1-(0 3):-2	0-(-1 3):-2	10-(3 3):-2
0: -2	-2: -2	5: -2	0: -2	-1: -2	3: -2
1-(0 0):-2	0-(-2 0):-2	2-(5 0):-2	0-(0 0):-2	0-(-1 0):-2	9-(3 0):-2

Vi får ny matrix:

4	0	6 1 / 2	1	-1 1 / 2	14 1 / 2
0	1	-2 1 / 2	0	1 / 2	-1 1 / 2
1	0	2	0	0	9

3. Vi vælger x 3 som grundvariabel.
Opløsningselement RE=2. Linjen svarende til variablen x 3 opnås ved at dividere alle elementer i linjen x 3 med det opløselige element RE=2. I stedet for det opløsende element får vi 1. I de resterende celler i x 3-kolonnen skriver vi nuller. Alle andre elementer bestemmes af rektangelreglen. Lad os præsentere beregningen af hvert element i form af en tabel:

4-(1 6 1 / 2):2	0-(0 6 1 / 2):2	6 1 / 2 -(2 6 1 / 2):2	1-(0 6 1 / 2):2	-1 1 / 2 -(0 6 1 / 2):2	14 1 / 2 -(9 6 1 / 2):2
0-(1 -2 1 / 2):2	1-(0 -2 1 / 2):2	-2 1 / 2 -(2 -2 1 / 2):2	0-(0 -2 1 / 2):2	1 / 2 -(0 -2 1 / 2):2	-1 1 / 2 -(9 -2 1 / 2):2
1: 2	0: 2	2: 2	0: 2	0: 2	9: 2

Vi får en ny matrix:

3 / 4	0	0	1	-1 1 / 2	-14 3 / 4
1 1 / 4	1	0	0	1 / 2	9 3 / 4
1 / 2	0	1	0	0	4 1 / 2

Da systemet har en identitetsmatrix, tager vi X = (4,2,3) som basisvariable.
De tilsvarende ligninger er:
3 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1/4 x 1 + x 2 + 1/2 x 5 = 9 3/4
1/2 x 1 + x 3 = 4 1/2
Lad os udtrykke de grundlæggende variabler i form af resten:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1/4 x 1 - 1/2 x 5 +9 3/4
x 3 = - 1/2 x 1 +4 1/2
Lad os erstatte dem med målfunktionen:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
eller

System af uligheder:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1/4 x 1 - 1/2 x 5 +9 3/4 ≥ 0
- 1/2 x 1 +4 1/2 ≥ 0
Vi reducerer ulighedssystemet til følgende form:
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1/4 x 1 + 1/2 x 5 ≤ 9 3/4
1/2 x 1 ≤ 4 1/2
F(X) = 1/2 x 1 + x 5 -10 1/2 → maks.
Lad os forenkle systemet.
3/4 x 1 - 1 1/2 x 2 ≤ -14 3/4
1 1/4 x 1 + 1/2 x 2 ≤ 9 3/4
1/2 x 1 ≤ 4 1/2
F(X) = 1/2 x 1 + x 2 -10 1/2 → maks.

Eksempel nr. 2. Find først grafisk metode, og derefter bruge simplex-metoden til at løse problemet
F(X) = x 1 + x 2 - x 3 + x 5 +15 → maks. (min.) med begrænsninger:
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0

Hvis et lineært programmeringsproblem kun har to variable, kan det løses grafisk.

Overvej et lineært programmeringsproblem med to variable og:
(1.1) ;
(1.2)
Her, der er vilkårlige tal. Opgaven kan enten være at finde maksimum (max) eller at finde minimum (min). Systemet med restriktioner kan indeholde både tegn og tegn.

Konstruktion af domænet for gennemførlige løsninger

Den grafiske metode til løsning af problem (1) er som følger.
Først tegner vi koordinatakserne og vælger skalaen. Hver af ulighederne i systemet af begrænsninger (1.2) definerer en halvplan afgrænset af den tilsvarende rette linje.

Altså den første ulighed
(1.2.1)
definerer et halvt plan afgrænset af en ret linje. På den ene side af denne lige linje og på den anden side. På den meget lige linje. For at finde ud af, på hvilken side ulighed (1.2.1) holder, vælger vi et vilkårligt punkt, der ikke ligger på linjen. Dernæst erstatter vi koordinaterne for dette punkt i (1.2.1). Hvis uligheden holder, så indeholder halvplanet det valgte punkt. Hvis uligheden ikke holder, så er halvplanet placeret på den anden side (indeholder ikke det valgte punkt). Skygge det halvplan, som uligheden (1.2.1) gælder for.

Vi gør det samme for de resterende uligheder i systemet (1.2). På denne måde får vi skyggefulde halvplaner. Punkterne i regionen med gennemførlige løsninger opfylder alle uligheder (1.2). Derfor er regionen med mulige løsninger (ADA) grafisk skæringspunktet mellem alle konstruerede halvplaner. Skygger for ODR. Det er en konveks polygon, hvis flader hører til de konstruerede lige linjer. En ODF kan også være en ubegrænset konveks figur, et segment, en stråle eller en lige linje.

Der kan også opstå tilfælde, at halvplanerne ikke indeholder fællespunkter. Så er domænet for mulige løsninger det tomme sæt. Dette problem har ingen løsninger.

Metoden kan forenkles. Du behøver ikke skygge for hvert halvplan, men konstruer først alle de lige linjer
(2)
Vælg derefter et vilkårligt punkt, der ikke hører til nogen af disse linjer. Indsæt koordinaterne for dette punkt i systemet af uligheder (1.2). Hvis alle uligheder er opfyldt, så er området af mulige løsninger begrænset af de konstruerede rette linjer og inkluderer det valgte punkt. Vi skygger området med mulige løsninger langs linjernes grænser, så det inkluderer det valgte punkt.

Hvis mindst én ulighed ikke er opfyldt, så vælg et andet punkt. Og så videre, indtil der findes et punkt, hvis koordinater opfylder systemet (1.2).

At finde yderpunktet af den objektive funktion

Så vi har en skyggefuld region af mulige løsninger (ADA). Den er begrænset af en brudt linje bestående af segmenter og stråler, der hører til de konstruerede lige linjer (2). ODS er altid et konveks sæt. Det kan enten være et afgrænset sæt eller ikke afgrænset langs nogle retninger.

Nu kan vi lede efter yderpunktet af den objektive funktion
(1.1) .

For at gøre dette skal du vælge et hvilket som helst tal og bygge en lige linje
(3) .
For at lette den videre præsentation antager vi, at denne lige linje går gennem ODR. På denne linje er objektivfunktionen konstant og lig med . sådan en ret linje kaldes en funktionsniveaulinje. Denne lige linje deler planet i to halvplaner. På et halvt plan
.
På et andet halvt fly
.
Det vil sige, på den ene side af lige linje (3) øges objektivfunktionen. Og jo længere vi flytter punktet fra den lige linje (3), jo større vil værdien være. På den anden side af lige linje (3) falder objektivfunktionen. Og jo længere vi flytter punktet fra lige linje (3) til den anden side, jo mindre vil værdien være. Hvis vi tegner en ret linje parallelt med linje (3), så vil den nye rette linje også være en niveaulinje af objektivfunktionen, men med en anden værdi.

For at finde den maksimale værdi af den objektive funktion er det således nødvendigt at tegne en ret linje parallel med den rette linje (3), så langt som muligt fra den i retning af stigende værdier, og som passerer gennem mindst et punkt af ODD. For at finde minimumsværdien af objektivfunktionen er det nødvendigt at tegne en ret linje parallelt med lige linje (3) og så langt som muligt fra den i retning af faldende værdier og passere gennem mindst et punkt af ODD.

Hvis ODR er ubegrænset, kan der opstå en sag, hvor en sådan direkte linje ikke kan trækkes. Det vil sige, uanset hvordan vi fjerner den lige linje fra niveaulinjen (3) i retning af stigende (faldende), vil den rette linje altid passere gennem ODR. I dette tilfælde kan den være vilkårligt stor (lille). Derfor er der ingen maksimum (minimum) værdi. Problemet har ingen løsninger.

Lad os overveje tilfældet, når den ekstreme linje parallel med en vilkårlig linje af formen (3) passerer gennem et toppunkt af ODR-polygonen. Ud fra grafen bestemmer vi koordinaterne for dette toppunkt. Derefter bestemmes den maksimale (minimum) værdi af objektivfunktionen af formlen:
.
Løsningen på problemet er
.

Der kan også være et tilfælde, hvor den lige linje er parallel med en af ODR's flader. Derefter passerer den rette linje gennem to hjørner af ODR-polygonen. Vi bestemmer koordinaterne for disse hjørner. For at bestemme den maksimale (minimum) værdi af objektivfunktionen kan du bruge koordinaterne for et hvilket som helst af disse hjørner:
.
Problemet har uendeligt mange løsninger. Løsningen er ethvert punkt placeret på segmentet mellem punkterne og , inklusive punkterne og dem selv.

Et eksempel på løsning af et lineært programmeringsproblem ved hjælp af den grafiske metode

Opgaven

Virksomheden producerer kjoler af to modeller A og B. Der bruges tre typer stof. For at lave en kjole af model A kræves der 2 m stof af den første type, 1 m stof af den anden type, 2 m stof af den tredje type. For at lave en kjole af model B kræves 3 m stof af den første type, 1 m stof af den anden type, 2 m stof af den tredje type. Lagrene af stof af den første type er 21 m, af den anden type - 10 m, af den tredje type - 16 m. Frigivelsen af et produkt af type A giver en indkomst på 400 den. enheder, et produkt type B - 300 den. enheder

Lav en produktionsplan, der giver virksomheden den største indkomst. Løs problemet grafisk.

Løsning

Lad variablerne og angive antallet af producerede kjoler, henholdsvis model A og B. Derefter vil mængden af stof af den første type, der forbruges, være:
(m)
Mængden af forbrugt stof af den anden type vil være:
(m)
Mængden af forbrugt stof af den tredje type vil være:
(m)
Da antallet af producerede kjoler ikke kan være negativt, så
Og .
Indtægterne fra de producerede kjoler vil være:
(den. enheder)

Så har den økonomisk-matematiske model af problemet formen:

Vi løser det grafisk.
Vi tegner koordinatakserne og .

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (0; 7) og (10.5; 0).

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (0; 10) og (10; 0).

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (0; 8) og (8; 0).

Vi skygger området, så punktet (2; 2) falder ind i den skraverede del. Vi får firkantet OABC.

(A1.1) .
kl.
kl.
Tegn en lige linje gennem punkterne (0; 4) og (3; 0).

Vi bemærker endvidere, at da koefficienterne for og af den objektive funktion er positive (400 og 300), stiger den efterhånden som og stiger. Vi tegner en ret linje parallelt med lige linje (A1.1), så langt som muligt fra den i retning af stigende , og passerer gennem mindst et punkt af firkantet OABC. En sådan linje går gennem punkt C. Ud fra konstruktionen bestemmer vi dens koordinater.
.

Løsningen af problemet: ;

Svar

.
Det vil sige, for at opnå den største indkomst, er det nødvendigt at lave 8 kjoler af model A. Indtægten bliver 3200 den. enheder

Eksempel 2

Opgaven

Løs et lineært programmeringsproblem grafisk.

Løsning

Vi løser det grafisk.
Vi tegner koordinatakserne og .

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (0; 6) og (6; 0).

Vi bygger en lige linje.
Herfra.
kl.
kl.
Tegn en lige linje gennem punkterne (3; 0) og (7; 2).

Vi bygger en lige linje.
Vi bygger en lige linje (abscisse-akse).

Området for tilladte løsninger (ADA) er begrænset af de konstruerede rette linjer. For at finde ud af hvilken side, bemærker vi, at punktet tilhører ODR, da det opfylder systemet med uligheder:

Vi skygger for området langs grænserne for de konstruerede linjer, så punktet (4; 1) falder ind i den skraverede del. Vi får trekant ABC.

Vi bygger en vilkårlig linje af niveauet af den objektive funktion, f.eks.
.
kl.
kl.
Tegn en lige plan linje gennem punkterne (0; 6) og (4; 0).
Da objektivfunktionen stiger med stigende og , trækker vi en ret linje parallelt med niveaulinjen og så langt som muligt fra den i retning af stigende , og passerer gennem mindst ét punkt i trekant ABC. En sådan linje går gennem punkt C. Ud fra konstruktionen bestemmer vi dens koordinater.
.

Løsningen af problemet: ;

Svar

Eksempel på ingen løsning

Opgaven

Løs et lineært programmeringsproblem grafisk. Find maksimum- og minimumværdien af objektivfunktionen.

Løsning

Vi løser problemet grafisk.
Vi tegner koordinatakserne og .

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (0; 8) og (2.667; 0).

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (0; 3) og (6; 0).

Vi bygger en lige linje.
kl.
kl.
Tegn en lige linje gennem punkterne (3; 0) og (6; 3).

De rette linjer er koordinatakserne.

Området for tilladte løsninger (ADA) er begrænset af de konstruerede rette linjer og koordinatakser. For at finde ud af hvilken side, bemærker vi, at punktet tilhører ODR, da det opfylder systemet med uligheder:

Vi skygger for området, så punktet (3; 3) falder ind i den skraverede del. Vi opnår et uafgrænset område afgrænset af den stiplede linje ABCDE.

Vi bygger en vilkårlig linje af niveauet af den objektive funktion, f.eks.
(A3.1) .
kl.
kl.
Tegn en lige linje gennem punkterne (0; 7) og (7; 0).
Da koefficienterne for og er positive, stiger den med stigende og .

For at finde maksimum, skal du tegne en parallel linje, som er så langt væk som muligt i retning af stigende , og passerer gennem mindst et punkt i regionen ABCDE. Men da området er ubegrænset på siden af store værdier af og , kan en sådan lige linje ikke tegnes. Lige meget hvilken linje vi trækker, vil der altid være punkter i regionen, der er mere fjernt i retning af stigende og . Derfor er der ikke noget maksimum. du kan lave den så stor som du vil.

Vi leder efter minimum. Vi tegner en lige linje parallelt med lige linje (A3.1) og så langt som muligt fra den i retning af aftagende , og passerer gennem mindst et punkt i regionen ABCDE. En sådan linje går gennem punkt C. Ud fra konstruktionen bestemmer vi dens koordinater.
.
Minimumsværdi objektiv funktion:

Svar

Maksimal værdi eksisterer ikke.
Minimumsværdi
.

Lineær programmering– en gren af matematikken, der studerer metoder til løsning af ekstreme problemer karakteriseret ved lineær afhængighed mellem variable og lineært optimalitetskriterium.

Et par ord om selve begrebet lineær programmering. Det kræver korrekt forståelse. I I dette tilfælde Programmering er selvfølgelig ikke kompilering af computerprogrammer. Programmering her skal fortolkes som planlægning, udarbejdelse af planer, udvikling af et handlingsprogram.

TIL matematiske problemer Lineær programmering omfatter undersøgelser af specifikke produktions- og økonomiske situationer, som i en eller anden form tolkes som problemer vedr optimal brug begrænsede ressourcer.

Udvalget af problemer, der løses ved hjælp af lineære programmeringsmetoder, er ret bredt. Dette er for eksempel:

· problemet med optimal udnyttelse af ressourcerne hvornår produktions planlægning;

· blandingsproblem (planlægning af produktsammensætning);

· problemet med at finde den optimale kombination forskellige typer produkter til opbevaring i lagre (lagerstyring eller "pengeproblemet");

· transportopgaver (analyse af virksomhedens beliggenhed, varebevægelser).

Lineær programmering er den mest udviklede og udbredte sektion af matematisk programmering (derudover inkluderer dette: heltal, dynamisk, ikke-lineær, parametrisk programmering). Dette er forklaret som følger:

· matematiske modeller stort antaløkonomiske problemer er lineære med hensyn til de nødvendige variabler;

· denne type problemer er i øjeblikket de mest undersøgte. Der er udviklet særlige metoder til det, ved hjælp af hvilke disse problemer løses, og tilsvarende computerprogrammer;

· Mange lineære programmeringsproblemer, der er blevet løst, har fundet bred anvendelse;

· nogle problemer, som i den oprindelige formulering ikke er lineære, kan efter en række yderligere begrænsninger og antagelser blive lineære eller kan reduceres til en sådan form, at de kan løses ved lineære programmeringsmetoder.

Den økonomiske og matematiske model for ethvert lineært programmeringsproblem omfatter: en objektiv funktion, hvis optimale værdi (maksimum eller minimum) skal findes; restriktioner i form af et system af lineære ligninger eller uligheder; krav om ikke-negativitet af variable.

Generelt er modellen skrevet som følger:

objektiv funktion:

F = c1x1 + c2x2 + ... + cnxn → max(min);

restriktioner:

a11x1 + a12x2 + ... + a1nxn (≤ = ≥) b1,

a21x1 + a22x2 + ... + a2nxn (≤ = ≥) b2,

am1x1 + am2x2 + ... + amnxn (≤ = ≥) bm;

ikke-negativitetskrav:

Opgaven er at finde optimal værdi funktioner underlagt restriktioner.

Så, 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 et lineært kriterium.

En nødvendig betingelse for at stille et lineært programmeringsproblem er restriktioner på tilgængeligheden af ressourcer, mængden af efterspørgsel, virksomhedens produktionskapacitet og andre produktionsfaktorer.

Essensen af lineær programmering er at finde punkterne for den største eller mindste værdi af en bestemt funktion under et bestemt sæt af restriktioner pålagt argumenterne og danner et system af restriktioner, som som regel har et uendeligt antal løsninger. Hvert sæt værdier af variabler (argumenter for funktionen F), der opfylder systemet af begrænsninger, kaldes en tilladt plan for det lineære programmeringsproblem. Funktionen F, hvis maksimum eller minimum er bestemt, kaldes problemets objektive funktion. En tilladt plan, hvor maksimum eller minimum af funktionen F opnås, kaldes den optimale plan for problemet.

Systemet af restriktioner, der bestemmer mange planer, er dikteret af produktionsforholdene. Opgaven med lineær programmering (LP) er at vælge den mest rentable (optimale) fra et sæt af gennemførlige planer.

Enkel metode er den vigtigste i lineær programmering . Løsningen af problemet begynder med at overveje et af hjørnerne af polyederen af betingelser. Hvis det undersøgte toppunkt ikke svarer til maksimum (minimum), flytter de til naboen, hvilket øger værdien af målfunktionen, når problemet løses for det maksimale, og mindsker det, når problemet løses for minimum. Flytning fra et toppunkt til et andet forbedrer således værdien af målfunktionen. Da antallet af hjørner af polyederet er begrænset, er det garanteret at finde den optimale værdi i et begrænset antal trin eller fastslå, at problemet er uløseligt.

Denne metode er universel, anvendelig til ethvert lineært programmeringsproblem i kanonisk form. Systemet af begrænsninger her er et system af lineære ligninger, hvor antallet af ukendte mere mængde ligninger. Hvis systemets rang er r , så kan vi vælge r ubekendte, som vi vil udtrykke gennem de resterende ubekendte. For bestemthedens skyld antager vi, at de første på hinanden følgende ukendte er valgt x 1 , X2, ..., Xr . Så kan vores ligningssystem skrives som

Det kan bringes til denne form ethvert fælles system , for eksempel ved den Gaussiske metode. Det er rigtigt, at det ikke altid er muligt at udtrykke det i form af de resterende første r ukendte (vi gjorde dette for at definere notationen). Dog sådan r der vil helt sikkert være ukendte. Disse ubekendte (variabler) kaldes grundlæggende, resten er gratis.

Ved at tildele bestemte værdier til frie variable og beregne værdierne af de grundlæggende (udtrykt i form af frie), vil vi opnå forskellige løsninger vores system af restriktioner. Således kan enhver løsning opnås. Vi vil være interesseret i specielle løsninger opnået i det tilfælde, hvor de frie variable er lig med nul. Sådanne løsninger kaldes grundlæggende, der er lige så mange af dem, som der er forskellige grundlæggende typer af et givet system af restriktioner. Grundløsningen hedder tilladt basisløsning eller referenceløsning, hvis værdierne af variablerne i den er ikke-negative. Hvis variable tages som grundlæggende X1, X2, ..., Xr , så er løsningen (b 1 , b 2 ,..., b r , 0, ..., 0) vil støtte, forudsat at b 1 , b 2 ,..., b r ≥ 0 .

Simplexmetoden er baseret på en sætning kaldet simplexmetodens grundlæggende sætning. Blandt de optimale planer for et lineært programmeringsproblem i kanonisk form er der nødvendigvis en referenceløsning til dets system af begrænsninger. Hvis den optimale plan for problemet er unik, falder den sammen med en referenceløsning. Der er et begrænset antal forskellige understøttende løsninger til systemet af begrænsninger. Derfor kunne en løsning på problemet i kanonisk form søges ved at opregne referenceløsningerne og blandt dem vælge den, som værdien for F den største. Men for det første er alle referenceløsninger ukendte og skal findes, og for det andet er der i virkelige problemer mange af disse løsninger, og direkte søgning er næppe mulig. Simplexmetoden er en bestemt procedure til rettet opregning af støtteløsninger. Baseret på en bestemt referenceløsning fundet på forhånd ved hjælp af en bestemt algoritme af simplex-metoden, beregner vi en ny referenceløsning, hvor værdien af den objektive funktion F ikke mindre end den gamle. Efter en række trin kommer vi frem til en referenceløsning, som er den optimale plan.

Så simplex-metoden introducerer en vis rækkefølge både når man finder den første (indledende) basisløsning og når man går over til andre grundlæggende løsninger. Hans idé er som følger.

At have system af restriktioner , reduceret til generelle udseende, altså til et system af m lineære ligninger med n variabler (m< n) , Find enhver grundlæggende løsning dette system, der kun bekymrer sig om at finde det så enkelt som muligt.

Hvis den første fundne grundlæggende løsning viste sig at være acceptabelt , så tjek det efter optimalitet. Hvis det ikke optimalt , så udføres en overgang til en anden, nødvendigvis tilladt basisløsning .

Simplexmetoden garanterer, at med denne nye løsning vil den lineære form, hvis den ikke når det optimale, nærme sig den. Det samme gør de med den nye gennemførlige basisløsning, indtil de finder en løsning, der er optimal.

Hvis den første fundne grundlæggende løsning viser sig at være uacceptabelt , så ved hjælp af simplex-metoden er det muligt at overgang til andre basisløsninger, som bringer os tættere på området for tilladelige løsninger, indtil på et eller andet beslutningstrin enten den grundlæggende løsning viser sig at være tilladelig, og simplex-metodens algoritme anvendes på den, eller vi er overbevist om inkonsistensen af begrænsningssystemet.

Anvendelsen af simplex-metoden er således opdelt i to faser: at finde en acceptabel grundlæggende løsning på begrænsningssystemet eller at fastslå, at det er uforeneligt; finde den optimale løsning.
Desuden kan hvert trin omfatte flere trin svarende til en eller anden basisløsning. Men siden nummeret grundlæggende løsninger er altid begrænset, så er antallet af trin i simpleksmetoden også begrænset.

Det givne diagram af simplex-metoden udtrykker klart dens algoritmiske karakter (naturen af en klar instruktion om udførelse af sekventielle operationer), hvilket gør det muligt med succes at programmere og implementere denne metode på en computer. Opgaverne med et lille antal variabler og begrænsninger kan løses manuelt ved hjælp af simplex-metoden.

Uden at dvæle mere detaljeret ved essensen af algoritmen, vil vi beskrive dens beregningsmæssige side. Beregninger ved hjælp af simpleksmetoden er organiseret i formen simplex tabeller, som er en gengivelse af det lineære programmeringsproblem i kanonisk form. Før kompilering simplex tabeller opgaven skal være konverterede , system af restriktioner reduceret til acceptabel grundform, ved hjælp af hvilke grundvariable skal udelukkes fra målfunktionen. Vi vil overveje spørgsmålet om disse foreløbige transformationer nedenfor. Nu vil vi antage, at de allerede er afsluttet, og opgaven har følgende form.

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 simplex-metoden er mest udforsket.

1. Begrebet matematisk programmering

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

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 uafhængige sektioner, der er involveret i undersøgelse og udvikling af metoder til løsning af 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 en 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 lægge planer, planlægge. Følgelig, korrekt oversættelse Engelsk "lineær programmering" ville ikke være " lineær programmering", og "lineær planlægning", som mere præcist afspejler indholdet af disciplinen. Men 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 ( transport problem); 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 den generelle form er de 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.