Sida 1
Problemets kanoniska form kännetecknas av följande tre egenskaper: 1) homogent system begränsningar i form av ett ekvationssystem; 2) homogena icke-negativitetsförhållanden som gäller för alla variabler som är involverade i problemet, och 3) maximering, linjär funktion. I det här problemet bryts alla tre av dessa funktioner.
Problemets kanoniska form kännetecknas av följande tre egenskaper: 1) ett homogent system av begränsningar i form av ett ekvationssystem; 2) homogena icke-negativitetsförhållanden som gäller för alla variabler som är involverade i problemet, och 3) maximering av en linjär funktion. I det här problemet bryts alla tre av dessa funktioner.
Kanonisk form av problemet linjär programmeringär bekvämt genom att det är lätt att hitta den initiala vertexen för den genomförbara regionen.
Låt oss överväga den kanoniska formen av det linjära programmeringsproblemet och Jordan-Gauss-elimineringsmetoden.
Den kanoniska formen av ett linjärt programmeringsproblem är ofta bekvämt.
När man transformerar begränsningssystemet till kanonisk form linjära programmeringsproblem, ojämlikheter (12) och (13) måste ersättas med jämlikheter. För att göra detta introduceras ytterligare icke-negativa variabler.
Bevisa att parvis pendlande reella matriser samtidigt reduceras till den kanoniska formen av Problem 1128 genom en likhetstransformation med hjälp av en ortogonal matris.
I huvudsak kan (4) - (5) betraktas som den kanoniska formen av det olinjära programmeringsproblemet, eftersom metoderna som beskrivs i kap. Vanligtvis i olinjära programmeringsproblem finns det inget krav på att variablerna ska vara heltal.
| Typer av begränsningar och metoder för deras omvandling. |
Problemets kanoniska form kännetecknas av homogeniteten i systemet av begränsningar i form av ett ekvationssystem; maximera den objektiva funktionen; villkoret för icke-negativitet för alla variabler som är involverade i problemet.
Ingen ytterligare egenskaper kanonisk form av problem som övervägs datorkrets lägger inte till.
Låt oss först betrakta den andra kanoniska formen av minimiproblemet.
Simplex-mete-algoritmen kan delas in i två steg. I det första steget hittas en grundläggande lösning genom att eliminera variabler. Om det hittas har vi den kanoniska formen av problemet för att gå vidare till det andra steget. Det andra steget är att kontrollera om det finns ett begränsat optimum. Om det finns, bestäms tillåtna baslösningar och från vilka den optimala väljs.
Om problemet löses i kanonisk form, används endast en del av de operationer som introduceras i andra stycket. Sålunda, för det kanoniska minimiproblemet, realiseras endast fallet i punkt 3.4.1, och endast operationerna med cyklisk omarrangering av kolumner, passage av kolonnen genom den vertikala gränszonen, korrigering av strukturella överträdelser och en del av trunkeringsoperationen behövs. Symmetriskt sett, när man löser det kanoniska maximiproblemet, realiseras endast fallet i punkt 3.4.2, och operationer med cyklisk omarrangering av strängar, att passera en sträng genom den horisontella gränszonen, korrigering av strukturella överträdelser och en annan del av trunkeringsoperationen är behövs. Annars tillför inte den kanoniska formen av problemet någon ytterligare specificitet.
Första stycket i inledningen visade hur ett generellt linjärt programmeringsproblem kan reduceras till en av de kanoniska formerna. För kanoniska problem är beskrivningen av den sekventiella förbättringsmetoden formellt förenklad, eftersom det inte finns något behov av att överväga två alternativ för att bryta mot optimalitetsvillkor och två alternativ för att nå nästa vertex grundmatris A [ /, J ], som huvudsakligen bestämmer komplexiteten hos en shat. Men i många fall visar det sig att tillämpa metoden på de kanoniska formerna av problemet att vara att föredra, och i detta avsnitt kommer vi att uppehålla oss vid varianter av metoden som erhålls för speciella linjära programmeringsproblem.
Sidor: 1
linjära programmeringsproblem
2.1. Definition och inspelningsformer
I det fall där alla begränsningar är ekvationer och alla variabler uppfyller icke-negativitetsvillkoret kallas det linjära programmeringsproblemet kanonisk. Den kan presenteras i koordinat-, vektor- eller matrisnotationsform.
A) kanoniskt problem LP i koordinatform har formen:
,
.
Detta problem kan skrivas med hjälp av summeringstecknet:
,
,
,
,
.
b) det kanoniska LP-problemet i vektorform har formen: ,
,
Var 
;
;
,
;
;
.
c) det kanoniska LP-problemet i matrisform har formen:
,
,
Var 
,
,
.
2.2. Minskning av det allmänna linjära problemet
programmering till kanonisk form
När man sammanställer matematiska modeller av ekonomiska problem, formas begränsningar huvudsakligen till system av ojämlikheter. Därför är det nödvändigt att kunna gå från dem till ekvationssystem. Tänk till exempel på den linjära ojämlikheten
och lägg till ett visst värde på dess vänstra sida 
så att ojämlikhet blir till jämlikhet.
Icke-negativ variabel 
kallas en extra variabel. Följande teorem ger grunden för möjligheten till en sådan transformation.
Sats 2.2.1. Varje beslut 
ojämlikhet (2.2.1) motsvarar en unik lösning på ekvation (2.2.2) och ojämlikhet 
och, omvänt, till varje lösning av ekvation (2.2.2)c 
motsvarar lösningen 
ojämlikheter (2.2.1).
Bevis. Låta 
lösning av ojämlikhet (2.2.1). Sedan. Låt oss ta ett nummer 
. Det är klart det 
. Om vi ställer in i ekvation (2.2.2), får vi
Den första delen av satsen har bevisats.
Låt nu vara en vektor 
uppfyller ekvation (2.2.2) med 
d.v.s. förkasta det icke-negativa värdet på den vänstra sidan av den sista likheten 
, vi tar emot osv.
Således etablerar det beprövade teoremet faktiskt möjligheten att reducera alla LP-problem till kanonisk form. För att göra detta räcker det att införa i varje begränsning som har formen av en ojämlikhet sin egen ytterligare icke-negativa variabel. Dessutom, i olikheter i formen (1.2.1) kommer dessa variabler att visas med "+"-tecknet, och i olikheter i formen (1.2.2) - med "–"-tecknet. Ytterligare variabler införs i objektivfunktionen med nollkoefficienter och påverkar därför inte dess värde.
Kommentar. I framtiden kommer vi att presentera simplexmetoden för det kanoniska LP-problemet när vi studerar objektivfunktionen för ett minimum. I de problem där du behöver hitta det maximala 
, det räcker med att överväga funktionen 
, hitta dess lägsta värde och sedan, ändra tecknet till det motsatta, bestäm det önskade maxvärdet 
.
3. Grafisk metod för att lösa problem
linjär programmering
3.1. Allmänna begrepp, exempel
I de fall det bara finns två variabler i LP-problemet kan du använda grafisk metod. Låt det vara nödvändigt att hitta det maximala (minsta) värdet för funktionen 
under restriktioner
(3.1.1)
Denna metod bygger på möjligheten att grafiskt avbilda regionen med genomförbara lösningar på ett problem, dvs. tillfredsställande system (3.1.1), och hitta den optimala lösningen bland dem. Regionen med genomförbara lösningar på problemet är konstruerade som skärningspunkten (gemensamma delen) av lösningsregionerna för var och en av de givna begränsningarna (3.1.1). Var och en av dem definierar ett halvplan med gräns 
,
. För att bestämma vilket av de två halvplanen som är lösningsdomänen räcker det att ersätta koordinaterna för vilken punkt som helst som inte ligger på linjen med olikheten: om den är uppfylld är lösningsdomänen det halvplan som innehåller denna punkt, om olikheten inte är uppfylld, är lösningsdomänen ett halvplan som inte innehåller den givna punkten.
Skärningen mellan dessa halvplan bildar ett visst område som kallas en lösningspolygon, som är en konvex mängd. (Anta att systemet med begränsningar är konsekvent och att dess lösningars polygon är begränsad.) För att hitta den optimala bland de möjliga lösningarna används nivålinjer och räta referenslinjer.
Nivålinje kallas en rät linje på vilken objektivet fungerar 
tar ett konstant värde. Nivålinjeekvationen har formen
, Var 
. Alla nivålinjer är parallella med varandra. Deras normala 
.
Referenslinje kallas en nivålinje som har minst en gemensam punkt med området för möjliga lösningar, i förhållande till vilken denna region ligger i ett av halvplanen (fig. 1).
Värderingar 
ökning i vektorns riktning 
. Därför är det nödvändigt att flytta nivålinjen 
i riktningen för denna vektor parallellt med sig själv med referenslinjen L 1
i den maximala uppgiften och i motsatt riktning - i den minimala uppgiften (upp till referenslinjen L 2).
Låt oss ge lösningen till exempel 1.1. Kom ihåg att vi måste hitta det maximala av funktionen 
under restriktioner
Lösning. Vi bygger en region med genomförbara lösningar. Vi räknar problemets begränsningar. I ett rektangulärt kartesiskt koordinatsystem (fig. 2) konstruerar vi en rät linje 
, motsvarande begränsning (1). Vi finner vilket av halvplanen i vilka denna räta linje delar hela koordinatplanet som är domänen för lösningar på ojämlikhet (1).
För att göra detta räcker det att ersätta koordinaterna för varje punkt som inte ligger på linjen i ojämlikheten. Eftersom det är rakt 
går inte genom ursprunget, substitut 
till den första begränsningen. Vi får en strikt ojämlikhet 
. Därför poängen 
ligger i lösningarnas halva plan. På samma sätt konstruerar vi en rät linje 
och lösningsdomänen för begränsningen (2). Vi hittar den gemensamma delen av halvplanen av lösningar, med hänsyn till restriktioner (3). Vi lyfter fram den resulterande regionen med möjliga lösningar i mörk färg i fig. 2.
Bygga en nivålinje 
och vektor 
, som anger funktionens ökningsriktning 
och vinkelrätt mot linjen
. Nivålinje 
röra sig parallellt med sig själv i riktningen 
till referenslinjen. Vi finner att den objektiva funktionen når sitt maximum vid punkten 
skärningspunkten för linjer 
Och 
. Lösa ett ekvationssystem för dessa linjer 
, får vi punktens koordinater 
. Därför och 
,
optimal lösning.
Exempel 3.1. Hitta minimum av en funktion 
med ett system av restriktioner 
Lösning. Vi konstruerar området med möjliga lösningar (se fig. 3), vektor 
och en av nivålinjerna 
. Flytta nivålinjen i motsatt riktning 
, eftersom problemet med att hitta minimum av en funktion håller på att lösas. I detta fall går referenslinjen genom punkt A (fig. 3), vars koordinater kommer att hittas från systemets lösning 
Så, 
. Låt oss räkna.
Kommentar. Faktum är att det beror på typen av region för genomförbara lösningar och den objektiva funktionen 
Ett LP-problem kan ha en enda lösning, ett oändligt antal lösningar eller ingen lösning alls.
Exempel 3.2. Hitta minimum av en funktion 
under restriktioner 
Lösning. Vi konstruerar området med genomförbara lösningar, normalen för nivålinjerna 
och en av nivålinjerna 
, som har gemensamma punkter med detta område. Flytta nivålinjen 
i motsatt riktning mot normalriktningen 
, eftersom problemet med att hitta minimum av en funktion håller på att lösas. Normal av nivålinjer 
och gränslinjens normal 
, i vilken riktning nivålinjerna rör sig, är parallella, eftersom deras koordinater är proportionella 
. Därför sammanfaller referenslinjen med gränslinjen 
område av genomförbara lösningar och passerar genom två hörnpunkter i denna region 
Och 
(Fig. 4).
Problemet har ett oändligt antal optimala lösningar, som är punkter i segmentet 
. Dessa punkter 
,
vi finner genom att lösa motsvarande ekvationssystem:
;
;
,
;
,
;
;
.
Låt oss räkna.
Svar: 
på 
,
.
Exempel 3.3. Lös ett linjärt programmeringsproblem
Lösning. Vi konstruerar regionen av genomförbara lösningar, det normala 
och en av nivålinjerna. I detta problem är det nödvändigt att hitta den maximala målfunktionen, så nivålinjen 
rör sig i riktning mot det normala. På grund av det faktum att i denna riktning utbudet av möjliga lösningar inte är begränsat, går nivålinjen till oändlighet (fig. 5).
Problemet har ingen lösning på grund av den objektiva funktionens obegränsade funktion.
Svar: 
.
Linjärt programmeringsproblem av formen ax = b där a är koefficientmatrisen, b är begränsningsvektorn.
Exempel:
I varje LP-problem söks värden på variabler under förutsättning att:
- dessa värden tillfredsställde något system linjära ekvationer eller ojämlikheter;
- vid dessa värden skulle den objektiva funktionen övergå till ett minimum eller maximum.
Instruktioner. Välj antalet variabler och antalet rader (antal begränsningar). Den resulterande lösningen sparas i en Word-fil.
En av universella metoder LP är simplex metod, som dock kan användas om LP-problemet har en kanonisk form.
Definition. LP-problemet har en kanonisk form om alla systembegränsningar endast består av ekvationer (förutom olikheter som uttrycker variablernas icke-negativitet) och den objektiva funktionen måste minimeras.
Ett exempel på ett sådant LP-problem i kanonisk form är Problem 1 – ett balanserat transportproblem med ett system av begränsningar (1) och en objektiv funktion (2).
Men i de flesta ekonomiska problem innefattar systemet av begränsningar oftast inte bara ekvationer utan också ojämlikheter.
Påstående. Alla generella LP-problem kan reduceras till kanonisk form.
Att ta med gemensam uppgift LP till den kanoniska formen uppnås genom att introducera nya (de kallas ytterligare) variabler.
Systemet av begränsningar (3) för detta problem består av fyra olikheter. Genom att införa ytterligare variabler y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 4 ≥ 0, vi kan gå till systemet med begränsningar: 
Dessa ytterligare variabler y Jag har en helt klar ekonomisk innebörd, nämligen att de menar mängden outnyttjad arbetstid (maskinstillestånd i-te typen).
Till exempel, om maskiner av den första typen arbetade under alla 18 timmar, då x + y = 18, därför är y 1 = 0. Men vi tillåter möjligheten av ofullständig användning av drifttiden för den första maskinen x + y<18. В этом случае y 1 får ett positivt värde och kan betraktas som en outnyttjad tidsgräns. Att till exempel känna till lösningen på detta problem från punkt 3.3.2, x = 12, y= 6, kan vi från begränsningssystemet (3.9) dra slutsatsen att y 1 = y 2 = y 3 = 0, och y 4 = 12 – 6 = 6. Det vill säga maskiner av den första, andra, tredje typen använder sin arbetstid helt. Men den fjärde maskinen är bara halvladdad, 6 timmar, och, givet den optimala planen, är den inaktiv. Kanske, efter sådana slutsatser, kommer företagets chef att vilja ladda det med annat arbete, hyra ut det för den här tiden, etc.
Så, genom att introducera ytterligare variabler, kan vi leda vilken typ av olikhetsbegränsning som helst till en ekvation.
Låt oss överväga blandningsproblemet. Systemet med begränsningar har formen: 
Ojämlikheterna vändes mot "mer", därför, inför ytterligare variabler y 1, y 2, y 3 ≥ 0, måste de subtraheras från den vänstra sidan för att utjämna den med den högra. Vi får ett system av begränsningar i kanonisk form:
Variablerna y i kommer också att vara ekonomiskt meningsfulla. Om du kommer ihåg det praktiska innehållet i problemet så kommer variabeln y 1 att betyda mängden överskott av ämne A i blandningen, y 2 kommer att betyda mängden överskott av ämne I i blandningen y 3 – överskott MED i blandningen.
Uppgiften att hitta maximivärdet för målfunktionen kan reduceras till att hitta minimivärdet för funktionen - F på grund av påståendets självklarhet max F = –min (– F). Titta på bilden: om någon gång x= x 0 funktion y= F(x) når sitt maximum, sedan funktionen y= –F(x), symmetrisk till den i förhållande till axeln OXE, vid samma tidpunkt x 0 kommer att nå ett minimum, och F max = – (– F min) kl x = x 0 .
Slutsats. För att representera LP-problemet i kanonisk form är det nödvändigt:
- omvandla ojämlikheterna som ingår i problemets system av begränsningar till ekvationer genom att införa ytterligare variabler;
- om den objektiva funktionen F→max (maximerar), den ersätts av funktionen – F→ min (vilket är minimerat).
Alla linjära programmeringsproblem kan reduceras till ett linjärt programmeringsproblem i kanonisk form. För att göra detta, i det allmänna fallet, måste du kunna reducera maximeringsproblemet till minimeringsproblemet; gå från ojämlikhetsbegränsningar till likhetsbegränsningar och ersätta variabler som inte följer icke-negativitetsvillkoret. Att maximera en viss funktion motsvarar att minimera samma funktion tagen med motsatt tecken, och vice versa.
Regeln för att få ett linjärt programmeringsproblem till kanonisk form är följande:
- om det i det ursprungliga problemet är nödvändigt att bestämma maximum för en linjär funktion, bör du ändra tecknet och leta efter minimum av denna funktion;
- om den högra sidan av restriktionerna är negativ, ska denna restriktion multipliceras med -1;
- om det finns ojämlikheter mellan restriktionerna, omvandlas de till likheter genom att införa ytterligare icke-negativa variabler;
- om någon variabel x j har inga teckenbegränsningar, då ersätts den (i objektivfunktionen och i alla begränsningar) av skillnaden mellan två nya icke-negativa variabler:
x 3 = x 3 + - x 3 - , Var x 3 + , x 3 - ≥ 0 .
Exempel 1. Reducera det linjära programmeringsproblemet till kanonisk form:
min L = 2 x 1 + x 2 - x 3;
2 x 2 - x 3 < 5;
x 1 + x 2 - x 3 > -1;
2 x 1 - x 2 < -3;
x 1 < 0; x2 ≥ 0; x 3 ≥ 0.
Låt oss introducera utjämningsvariabler i varje ekvation i systemet av begränsningar x 4, x 5, x 6. Systemet kommer att skrivas i form av likheter, och i de första och tredje ekvationerna i systemet av begränsningar variablerna x 4, x 6 skrivs in på vänster sida med ett "+"-tecken, och i den andra ekvationen variabeln x 5 anges med ett "-"-tecken.
2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 > 0; x 5 > 0; x 6 ≥ 0.
De fria termerna i den kanoniska formen måste vara positiva för att göra detta, multiplicera de två sista ekvationerna med -1:
2x 2 - x 3 + x 4 = 5;
-xl - x2 + x3 + x5 = 1;
-2x 1 + x 2 - x 6 = 3.
I den kanoniska formen att skriva linjära programmeringsproblem måste alla variabler som ingår i systemet av begränsningar vara negativa. Låt oss anta det x 1 = x 1 " - x 7 , Var x 1 "≥ 0, x 7 ≥ 0 .
Genom att ersätta detta uttryck i systemet av begränsningar och den objektiva funktionen och skriva variablerna i stigande indexordning, får vi ett linjärt programmeringsproblem presenterat i kanonisk form:
L min = 2x 1" + x 2 - x 3 - 2x 7;
2x 2 - x 3 + x 4 = 5;
-x 1 " - x 2 + x 3 + x 5 + x 7 = 1;
-2x 1" + x 2 - x 6 + 2x 7 = 3;
x 1 "≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.
Optimalitetsvillkor för grundplanen för det kanoniska LP-problemet. Enkel metod och dess konvergens.
Den simplexmetoden är universell, eftersom det låter dig lösa nästan alla linjära programmeringsproblem som skrivits in kanonisk form.
Idén med simplexmetoden konsekvent förbättring av planen,är att, utgående från någon initial referenslösning, sekventiellt riktad rörelse från referenslösningarna för problemet till den optimala.
Värdet på objektivfunktionen minskar inte maximalt under denna rörelse för problem.
Eftersom antalet supportlösningar är ändligt så får vi efter ett ändligt antal steg den optimala supportlösningen.
En referenslösning är en grundläggande icke-negativ lösning.
Enkel metodalgoritm
1. Den matematiska modellen av problemet måste vara kanonisk. Om den är icke-kanonisk, måste den föras till kanonisk form.
2. Hitta den initiala referenslösningen och kontrollera att den är optimal.
För att göra detta, fyll i simplextabell 1.
Vi fyller i alla rader i tabellen i det första steget enligt data från systemet med begränsningar och målfunktionen.
Följande fall är möjliga när du löser problem på maximal:
1. Om alla koefficienterna för den sista raden i simplextabellen DJ³ 0, hittade sedan
lösning optimal.
2 Om minst en koefficient DJ £ 0, men för motsvarande variabel finns det inte ett enda positivt utvärderingssamband, då lösningen vi stoppar uppgifter, eftersom F(X) ® ¥ , dvs. den objektiva funktionen är inte begränsad inom området för genomförbara lösningar.
Om minst en koefficient på den sista raden är negativ, och för motsvarande variabel finns det minst en positiv utvärderande attityd, sedan måste du röra på dig till en annan referenslösning.
4. E om det finns flera negativa koefficienter i den sista raden, alltså till den underliggande variabelkolumnen(BP) inför det variabel, vilket motsvarar den största negativa koefficienten i absolut värde.
5. Om minst en koefficient Dk< 0 ,Den där k - din kolumn acceptera för presentatören.
6. För ledande linje vi accepterar den som motsvarar minimum förhållandet mellan fria medlemmar bi till positiva koefficienter ledande, k – den där kolumn.
7. Elementet som ligger i skärningspunkten mellan de ledande raderna och kolumnen kallas ledande element.
Att fylla i simplex tabell 2 :
· fyll baskolumnen med nollor och ettor
· skriv om den inledande raden genom att dividera den med det inledande elementet
· om den inledande raden har nollor, kan motsvarande kolumner flyttas till nästa simplextabell
· vi hittar de återstående koefficienterna med hjälp av "rektangel"-regeln
Vi skaffar en ny referenslösning som vi kontrollerar för optimalitet:
Om alla koefficienter för den sista raden DJ³ 0, sedan hittade lösningen maximal.
Om inte, fyll sedan i simplextabellen för det åttonde steget och så vidare.
Om den objektiva funktionen F(X) kräver att hitta lägsta värde, sedan kriteriet problemets optimalitetär icke-positiva koefficienter D j för alla j = 1,2,...n.
Konvergens av simplexmetoden. Degeneration i LP-problem. Den viktigaste egenskapen hos varje beräkningsalgoritm är konvergens, det vill säga möjligheten att erhålla de önskade resultaten under dess tillämpning (med en given noggrannhet) i ett ändligt antal steg (iterationer).
Det är lätt att se att problem med konvergensen av simplexmetoden potentiellt kan uppstå vid valet av värdet på r (avsnitt 2") i det fall där samma minimivärden av förhållandet
kommer att uppnås för flera rader av tabell T (q) samtidigt. Sedan vid nästa iteration kommer kolumn b(β(q+1)) att innehålla noll element.
I den ursprungliga formuleringen kan PLP tillåta olika former av inspelning. I vissa problem krävs det alltså att maximera den objektiva funktionen, i andra krävs det att minimera den; vissa linjära begränsningar kan ta formen av jämlikheter, andra - ojämlikheter, etc.
För att säkerställa enhetlighet i inspelningen av PAP, den sk kanonisk form uppgifter.
ZLP sägs vara skriven i kanonisk form om den har följande form:
Låt oss notera följande egenskaper hos den kanoniska formen:
1) det krävs för att minimera den objektiva funktionen;
2) alla linjära begränsningar, förutom kraven på icke-negativitet hos variabler, har formen av likheter;
Icke-negativitetskrav ställs på alla variabler.
Låt oss visa att vilken ZLP som helst kan reduceras till kanonisk form.
1) Om det i ZLP krävs att maximera målfunktionen f, så sätter vi g = - f och kräver minimering av funktionen g. Resultatet blir en ny ZLP, som är likvärdig med den ursprungliga i den meningen att varje optimal lösning på det ursprungliga problemet kommer att vara en optimal lösning på det nya problemet och vice versa.
2) Antag att ZLP har en linjär begränsning av formen
Låt oss ersätta denna begränsning med följande två begränsningar:
Var z - en ny variabel som introduceras i målfunktionen med koefficienten 0 (med andra ord, variabeln z introduceras inte i målfunktionen). Värdet på variabeln z kan ignoreras efter att ha löst ett nytt problem.
På samma sätt ersätts visningsbegränsningen av två begränsningar:
3) Låt oss anta att i ZLP inte alla variabler är föremål för kravet på icke-negativitet. Sedan varje variabel 
, som inte omfattas av kravet på icke-negativitet, kan representeras som skillnaden mellan två icke-negativa variabler:
Varje förekomst av en variabel 
i den objektiva funktionen eller begränsningarna ersätter vi den med skillnaden 
. Efter att ha löst det nya problemet med (2.6), återgår vi till de tidigare variablerna.
Genom att använda dessa tekniker reduceras varje ZLP till kanonisk form.
Exempel. Reducera till kanonisk form
Låt oss göra stegen som beskrivs.
Nu får vi ZLP i kanonisk form:
2.7. Konceptet med en stödplan.
Låt VLP ges i kanonisk form (2.3 - 2.5). Låt oss anta att ekvationssystemet (2.4) reduceras till Jordanisk form med icke-negativa högersidor:
(2.6)
Var 
.
Genom att likställa de fria variablerna med noll får vi den grundläggande lösningen av systemet (2.4)
På grund av förhållandena 
uppsättningen av värden av variabler (2.7) uppfyller också begränsningar (2.5). Därför är (2.6). PPP:s godtagbara beslut.
Den tillåtna lösningen (2.7) kallas grundläggande tillåtna beslut eller grundplanen för ZLP. I det här fallet säger de att variablerna 
utgör en godtagbar grund.
Det visar sig att om ODR avbildas geometriskt, så motsvarar varje stödplan för ZLP:en polyederns vertex. Därför är följande teorem sann.
Om ZLP är lösbar, så finns det en optimal supportplan.
3. Enkel metod för att lösa problem
3.1. Allmänna egenskaper och huvudstadier av simplexmetoden
Grundarna av simplexmetoden är den sovjetiske matematikern L.V. Kantorovich och den amerikanske matematikern J. Dantzig.
Med simplexmetoden kan du lösa alla problem eller upptäcka dess olösbarhet. Många specialklasser av problem kan lösas med andra metoder som är mer effektiva för dessa klasser. Men fördelen med simplexmetoden är dess mångsidighet. För nästan alla datorer har standardprogram utvecklats för att lösa problem med simplexmetoden.
Låt oss beskriva den allmänna idén om simplexmetoden.
Vi tror att ZLP är skrivet i kanonisk form och den objektiva funktionen måste minimeras. Som vi redan vet bör den optimala planen sökas bland de grundläggande planerna för ZLP. Simplexmetoden går inte igenom alla referensplaner (vilket ofta skulle vara omöjligt på grund av deras enorma antal), men, med utgångspunkt från en initial referensplan, går den sekventiellt vidare till andra referensplaner med en minskning av målfunktionen. Simplexmetoden slutar fungera när antingen den optimala referensplanen hittats eller om problemets olösbarhet har fastställts.
När du löser ett problem med simplexmetoden kan följande steg urskiljas:
1) föra ZLP till kanonisk form;
2) reducering av systemet med linjära ekvationer till Jordanisk form med icke-negativa högersidor samtidigt som man kontrollerar att LLP är olöslig på grund av inkonsekvensen i systemet med linjära begränsningar;
3) studie av referensplanen för optimalitet;
4) studie av ZLP för oavgörbarhet på grund av obegränsad underifrån på objektivfunktionens ODD;
5) övergång till en ny, "bättre" referensplan.
