Üldiselt ülesanne lineaarne programmeerimine on kirjutatud nii, et piiranguteks on nii võrrandid kui ka võrratused ning muutujad võivad olla kas mittenegatiivsed või suvaliselt muutuvad. Juhul, kui kõik piirangud on võrrandid ja kõik muutujad vastavad mittenegatiivsuse tingimusele, nimetatakse lineaarse programmeerimise probleemi kanooniliseks. Seda saab esitada koordinaatide, vektori või maatriksi tähistusega.

1. Kanoonilise lineaarse programmeerimise ülesanne koordinaatide tähistuses on kujul

.

Kompaktsemal kujul saab selle ülesande kirjutada liitmismärgiga,

(1.7)

2. Kanoonilise lineaarse programmeerimise probleem sisse vektorsalvestus näeb välja nagu

(1.8)

Kus ,

.

3. Kanoonilise lineaarse programmeerimise ülesanne maatriksmärgistuses on kujul

(1.9)

, .

Siin A– võrrandisüsteemi koefitsientide maatriks, X- maatriks-veerg probleemsed muutujad, – piirangute süsteemi parempoolsete osade maatriks-veerg.

Sageli kasutatakse lineaarse programmeerimise probleeme, nn sümmeetriline, millel on maatriksmärgistuses vorm

(1.10)

(1.11)

1.4. Toomine ühine ülesanne lineaarne programmeerimine
kanoonilisele kujule

Enamikus lineaarse programmeerimise ülesannete lahendamise meetodites eeldatakse, et piirangute süsteem koosneb võrranditest ja muutujate mittenegatiivsuse loomulikest tingimustest. Matemaatiliste mudelite koostamisel aga majanduslikud ülesanded piirangud vormitakse peamiselt ebavõrdsussüsteemideks, seega on vaja osata liikuda võrratussüsteemist võrrandisüsteemi. Selleks tõestame järgmist teoreemi.

Teoreem 1.1. Võrratuse asendamisest võrrandiga. Iga otsus ebavõrdsused

vastab võrrandi ainulaadsele lahendile

ja ebavõrdsused

, (1.14)

ja vastupidi, iga võrrandi (1.13) ja võrratuse (1.14) lahend vastab võrratuse (1.12) ainulaadsele lahendile.

Tõestus. Lase on ebavõrdsuse (1.12) lahendus, siis . Tähistame selle võrratuse parema ja vasaku külje erinevust tähega , s.o.

Ilmselgelt . Asendagem selle asemel võrrandiga (1.13). muutuvaid väärtusi , saame

Seega rahuldab võrrandi (1.13) ja ebavõrdsuse (1.14). See tähendab, et teoreemi esimene osa on tõestatud.

Olgu nüüd täidetud võrrand (1.13) ja ebavõrdsus (1.14), st meil on

JA

Jättes kõrvale viimase võrdsuse vasakul küljel oleva mittenegatiivse väärtuse, saame

st. rahuldab ebavõrdsust (1,12). Teoreem on tõestatud.

Kui ebavõrdsus , siis tuleb sellesse sisestada täiendav mittenegatiivne muutuja vasak pool miinusmärgiga, st .

Mittenegatiivseid muutujaid, mis on sisestatud ebavõrdsuse piirangutesse, et muuta need võrranditeks, nimetatakse täiendavad muutujad. Sisestatakse täiendavad muutujad sihtfunktsioon nullkoefitsientidega ega mõjuta seetõttu selle väärtust.

Juhul, kui probleemis on suvaliselt muutuvaid muutujaid, asendatakse iga selline muutuja kahe mittenegatiivse muutuja erinevusega, s.o. , Kus Ja .

Mõnikord on vaja liikuda probleemis miinimumi leidmiselt maksimumi leidmisele või vastupidi. Selleks piisab, kui muuta kõigi sihtfunktsiooni kordajate märgid vastupidisteks ja muidu jätta probleem muutmata. Sel viisil saadud maksimum- ja miinimumülesannete optimaalsed lahendused langevad kokku ning optimaalsete lahenduste sihtfunktsioonide väärtused erinevad ainult märgi poolest.

Näide 1.1. Viivad kanooniline vorm lineaarse programmeerimise probleem.

D

Lahendus. Liigume edasi eesmärgifunktsiooni maksimumi leidmise probleemi juurde. Selleks muudame sihtfunktsiooni kordajate märke. Kitsenduste süsteemi teise ja kolmanda võrratuse teisendamiseks võrranditeks võtame kasutusele mittenegatiivsed lisamuutujad (matemaatilises mudelis on see tehe tähistatud tähega D). Muutuja sisestatakse teise võrratuse vasakusse serva plussmärgiga, kuna ebavõrdsuse kuju on . Muutuja sisestatakse kolmanda võrratuse vasakusse serva märgiga "-", kuna ebavõrdsuse kuju on . Muutujad sisestatakse sihtfunktsiooni koefitsiendiga võrdne nulliga. Muutuja, millele mittenegatiivsuse tingimust ei kehtestata, asendatakse erinevusega , . Kirjutame ülesande kanoonilises vormis

Mõnel juhul osutub vajalikuks taandada kanooniline probleem sümmeetriliseks probleemiks. Vaatame näidet.

Näide 1.2. Viivad sümmeetriline vaade lineaarse programmeerimise probleem

: Lineaarse programmeerimise probleemid (LPP)

1. Lineaarne programmeerimine

2. Lineaarse programmeerimise ülesannete tüübid

3. PAP-ide salvestamise vormid

4. Lineaarse programmeerimise ülesannete kanooniline vorm

Lineaarne programmeerimine

Lineaarne programmeerimine on matemaatilise programmeerimise haru, mida kasutatakse meetodite väljatöötamiseks mitme muutuja lineaarfunktsiooni äärmuse leidmiseks lineaarse all. täiendavad piirangud, mis on muutujatele peale pandud.

Lahendatavate probleemide tüübi järgi jagunevad LP-meetodid universaalseteks ja spetsiaalseteks. Kasutades universaalsed meetodid Kõik lineaarse programmeerimise probleemid (LPP) on lahendatavad. Spetsiaalsed võtavad arvesse probleemmudeli tunnuseid, selle objektiivset funktsiooni ja piirangute süsteemi.

Lineaarse programmeerimise ülesannete põhijooneks on see, et sihtfunktsiooni ekstreemum asub teostatavate lahenduste piirkonna piiril.

Joonis 1 – sihtfunktsiooni ekstreemum

ZLP matemaatiline mudel on kirjutatud järgmiselt:

max (või min) Z=z(X),(1)

ODR-i saab esindada süsteem lineaarvõrrandid või ebavõrdsus.

Vektor X = (x 1, x 2, .... x p) on juhtvektor või juhtefekt.

Lubatud plaani X, milles optimaalsuse kriteerium Z=z(X) saavutab äärmusliku väärtuse, nimetatakse optimaalseks ja tähistatakse X*-ga, sihtfunktsiooni äärmist väärtust Z*=z(X*).

Lineaarse programmeerimise probleemide tüübid

Lineaarseid programmeerimismeetodeid kasutatakse tööstusettevõtetes laialdaselt tootmisprogrammi optimeerimisel, töökodade ja ajavahemike kaupa jaotamisel, seadmete sortimentide laadimisel, kaubavoogude planeerimisel, käibeplaani koostamisel jne.

Kõige tavalisem ülesannete tüüp on ülesanne optimaalne kasutamine ressursse. Laske mõnel tootmisüksusel (töökoda, ettevõte, ühistu vms), lähtudes turutingimustest, tehnilised võimalused ja olemasolevaid ressursse, suudab toota n erinevat tüüpi numbrite j all tuntud tooted.

Toodete tootmisel on ettevõte piiratud olemasolevate ressurssidega, mille kogust tähistatakse m-ga ja ressursside vektor B = (b 1, b 2, ..., b t). Tuntud on ka tehnoloogilised koefitsiendid a ij, mis näitavad i-nda ressursi kulumäära j-nda toote ühiku tootmiseks. Ühiku väljundi efektiivsus j-i tooted mida iseloomustab kasum p j .

On vaja kindlaks määrata tootmisplaan X = (x 1, x 2, ..., x p), maksimeerides etteantud ressurssidega ettevõtte kasumit.

Sihtfunktsioon näeb välja selline

piirangute all

Sageli on tootevaliku kehtestanud kõrgem organisatsioon, st selle mahud peavad jääma teatud piiridesse D j-s ja D-s j: siis seatakse järgmine piirang:

Selle aluseks on ressursside optimaalse kasutamise probleemi mudel mudelid ettevõtte iga-aastase tootmisprogrammi optimeerimiseks. Mudel sisaldab piiranguid seadmete tööajale.

Sama tähist hoides kirjutame läbi b j ja c j vastavalt müügihinna ja ühiku maksumuse jth tooted. Optimaalsuse kriteeriumidena võib võtta järgmist:

1) maksimaalne kasum

2) minimaalsed tootmiskulud

3) maksimaalne toodang väärtuses (tulu toote müügist)

Näide. Ettevõte suudab toota nelja tüüpi tooteid 1, 2, 3 ja 4. Igas mahus müük on garanteeritud. Kvartali jooksul on ettevõttes tööjõudu 100 meesvahetust, poolfabrikaate kaaluga 260 kg ja tööpinke 370 masinavahetust. Iga tooteliigi ressursitarbimise määrad ja kasum ühiku kohta on toodud tabelis 1.

Vajalik:

a) meik matemaatiline mudelülesanne määrata tootmisplaan, mis saavutab maksimaalse kasumi;

b) lahendada probleem pakendi nõudega nii, et kolmanda toote ühikute arv oleks 3 korda suurem rohkem kogustühikud esiteks;

c) leida optimaalne sortiment lisatingimused: toota vähemalt 25 ühikut esimest toodet, mitte rohkem kui 30 ühikut kolmandat ning teist ja neljandat toodet vahekorras 1:3.

Tabel 1

Esialgsed andmed

Ülesande matemaatiline mudel:

objektiivne funktsioon:

max: Z=40x1 +50x2 +100x3 +80x4

piirangutega:

a) tööjõuressursside puhul:

2,5x1 +2,5x2 +2x3 +1,5x4? 100;

pooltoodete puhul:

4x1 +10x2 +4x3 +6x4? 260;

tööpinkide jaoks:

8x 1 +7x 2 +4x 3 +10x 4 ? 370;

mittenegatiivsuse tingimus:

b) konfiguratsiooni lisanõuet väljendab tingimus

3x1 =x3, st 3x1x3 =0;

c) esitame piirtingimused ja konfiguratsioonitingimused järgmiselt: x 1 ?

x 3?30, 3*x 2 = x 4.

Probleem tellimuste esitamisel või vahetatavate seadmerühmade laadimisel. See on umbes o tellimuste jaotus m (i=1,..., m) erineva tootmis- ja tehnoloogiliste omadustega, kuid tellimuste täitmise mõttes omavahel asendatava ettevõtte (kauplused, masinad, esinejad) vahel. Kohustuslik on koostada tellimuste esitamise plaan, milles ülesanne oleks täidetud ja efektiivsusnäitaja saavutaks äärmusliku väärtuse.

Sõnastame ülesande matemaatiliselt. Olgu vaja toota n tüüpi tooteid, kasutades m homogeenset seadmerühma. Tootmisplaan iga tooteliigi jaoks teatud periood antud hulgaga x j (j=1,2, …n). Igat tüüpi seadmete võimsus on piiratud ja võrdne b i-ga. Tuntud on tehnoloogiline maatriks A=||a ij ||, kus a ij on ajaühikus toodetud j-nda toote ühikute arv i-s varustus. Maatriks C on kulumaatriks, kus c ij on toodanguga seotud kulud j-ndat ühikut tooted i-ndal seadmel. X on väljundmahu vektor.

Probleemi mudel on järgmisel kujul:

eesmärgifunktsioon – kõigi tellimuste elluviimise kulude minimeerimine

piirangutega:

a) seadme võimsuse järgi

b) tootmiseks

c) mittenegatiivsuse tingimus

Seda probleemi nimetatakse jaotus- või jaotusprobleemiks.

Kui mõne tooteliigi puhul lubatakse plaani ületada, võetakse piirangu (b) kuju

Sihtkasumiks võib võtta ka järgmist:

a) maksimaalne kasum

b) masina aja minimaalne kulu

Sest Iga mudel sisaldab lihtsustavaid eeldusi, et saadud tulemusi õigesti rakendada, on vaja nende lihtsustuste olemust selgesti mõista, mis lõpuks võimaldab teha järelduse nende vastuvõetavuse või lubamatuse kohta. Kõige olulisem lihtsustus vaadeldavates mudelites on ressursitarbimise mahtude ja tootmismahtude vahelise otseselt proportsionaalse (lineaarse) seose eeldamine, mis täpsustatakse kulunormide a ij abil. Ilmselgelt ei ole see eeldus alati täidetud. Seega muutuvad paljude ressursside (näiteks põhivara) tarbimismahud järsult – olenevalt tootmisprogrammi X muutustest. Teiste lihtsustavate eelduste hulka kuuluvad eeldused hindade j sõltumatuse kohta mahtudest x j, mis kehtivad vaid teatud piiride puhul. nende muutumisest. Samuti on oluline teada neid "haavatavaid" piirkondi, sest need näitavad mudeli täiustamise põhimõttelisi suundi.

PAP salvestusvormid

PAP-i salvestamiseks on 3 vormi:

1) funktsioonide kujul

max(või min)Z=,max(või min)Z=,

2) vektorvorm

(vektorite skalaarkorrutis)

piirangute all

A 1 x 1 +A 2 x 2 +..+A n x n = B

Kus on vektorid

C = (C 1, C 2 .. C n), X = (X 1, X 2 .. X n) ja.

3) maatriksvorm

piirangute all

kus C = (c 1, c 2,...c n),

Lineaarse programmeerimise ülesannete kanooniline vorm

Kui kõik lineaarse programmeerimise ülesande piirangud on võrrandid ja mittenegatiivsuse tingimused on kehtestatud kõikidele muutujatele x j, siis nimetatakse seda lineaarse programmeerimise probleemiks kanoonilisel kujul või kanooniliseks lineaarse programmeerimise probleemiks (CLP).

piirangute all

ZLP-lt CLLP-le üleminekuks on vaja liikuda ebavõrdsuse piirangutelt võrdsuspiirangutele ja asendada muutujad, mis ei allu mittenegatiivsuse tingimustele.

ZLP kanoonilisse vormi viimise reeglid:

1) piirangute olemasolul parem pool negatiivne, siis tuleks see piir korrutada -1-ga;

2) kui piirangute vahel esineb ebavõrdsusi, siis täiendavate mittenegatiivsete muutujate sisseviimisega muudetakse need võrdsusteks;

3) kui mõnel muutujal xk pole märgipiiranguid, siis asendatakse see sihtfunktsioonis ja kõigis piirangutes kahe uue mittenegatiivse muutuja vahega: xk=x * k - xl, kus l on koondindeks, x * k>=, xl >=0.

Vaatame näidet. Toome selle kanoonilisele kujule:

Toome igasse piirangute süsteemi võrrandisse nivelleerimismuutujad x 4, x 5, x 6. Süsteem kirjutatakse võrduste kujul ning piirangute süsteemi esimeses ja kolmandas võrrandis on muutujad x 4, x 6 sisestatud vasakule küljele plussmärgiga ja teise võrrandisse x. 5 sisestatakse märgiga "-".

Kanoonilisel kujul olevad vabad liikmed peavad selleks olema positiivsed, korrutage kaks viimast võrrandit -1-ga:

Lineaarse programmeerimise ülesannete kirjutamise kanoonilisel kujul peavad kõik piirangute süsteemis sisalduvad muutujad olema mittenegatiivsed. Oletame, et

Asendamine see väljend piirangute ja sihtfunktsiooni süsteemi ning kirjutades muutujad kasvavas indeksi järjekorras, saame kanoonilisel kujul esitatud lineaarse programmeerimise probleemi:

optimeerimise simpleksline lineaarne programmeerimine

MP ülesanded

Üldine PAP helistas <,=,>=)bi (i=1,n) (2) tingimusel, et xj>

Sümmeetriline < либо = и не отрицательных переменных и задача минимизации функции (1) при lineaarsed piirangud ebavõrdsuses märgiga > Kanooniline segatud.

min f(x) = -max(-f(x))

<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>

ZLP eesmärgifunktsiooni ja piirangute geomeetriline tõlgendus. ZLP geomeetriline formuleerimine.

Olgu antud ülesanne f=c1x1+c2x2-max (1).

a11x1+a12x2<=b1 }

am1x1+am2x2<=bm}

x1>=0, x2>=0 (3)

Ülesande plaan (x1,x2) on tasapinna punkt. Iga ebavõrdsus meiega 2 esitust. on poollennuk. Pooltasand on kumer hulk. Kumer nimetatakse hulgaks, milles hulka kuuluvad ka sellesse hulka kuuluvad ühendava lõigu punktid (x1 ja x2). C-ma 2 tähistab pooltasandite ristumiskohta. Ületamisel võite saada:

1) kumer hulknurkne suletud ala.

2) kumer avatud hulknurkne ala

3) üksikpunkt

4) tühi komplekt

5) kiir ja segment

Sihtfunktsiooni geomeetriline tõlgendus: Funktsioon 1 on paralleelsete sirgjoonte perekond, mida nimetatakse tasemejoonteks (sihtfunktsiooni konstantse väärtusega jooned). Funktsiooni osatuletised x1 ja x2 suhtes näitavad sihtfunktsiooni kasvukiirust piki telgede koordinaate. Gradiendi vektor näitab sihtfunktsiooni kiireima kasvu suunda Ülesande 1-3 puhul väljub gradiendi vektor = (c1;c2) punktist (0,0) ja suunatakse koordinaatidega punkti (c1;c2). Gradiendi vektor on nivoojoontega risti. Tavaliselt nimetatakse pooltasapindade ristumiskohta vastuvõetavate lahenduste ala (ADD).

LP põhiteoreem. Skemaatiline diagramm ZLP lahendus, mis tuleneb sellest teoreemist.

Kui ZLP-l on lahendus, siis saavutab sihtfunktsioon äärmusliku väärtuse vähemalt ühes plaani polüeedri äärmuslikus punktis. Kui sihtfunktsioon saavutab äärmusliku väärtuse rohkem kui ühes äärmises punktis, siis jõuab see suvalises punktis ühe ja sama väärtuseni, mis on nende kumer lineaarne kombinatsioon. ZLP käsitsi lahendamisel on mugav kasutada tabelikirjet.

BP		SP -Xm+1 -Xm+2 -Xn
x1	b1o	b11 b12 b1n-m
x2	b2o	b21 b22 b2n-m
xm	bm	bm1 bm2 bmn-m
f	puh	bo1 bo2 bon-m

Simpleksmeetodi algoritm.

1. viia probleemimudel kanoonilisse vormi;

2. leidke esialgne võrdlusplaan;

3. kirjutage ülesanne lihtsas keeles. laud;

5. liikuda uuele võrdlusplaanile, uuele sümptomile. laud. Uuele referentsplaanile üleminekuks piisab ühe põhimuutuja asendamisest vabaga. Aluses sisalduv muutuja ja vastav eraldusvõime veerg määratakse f-rea suurima absoluutse negatiivse elemendiga. Alusest välja jääv muutuja ja vastav lahutusjoon määratakse väikseima simplekssuhtega, s.o. ühiku veeru elementide seos eraldusvõime veeru vastava elemendiga. Lihtsuhe on mittenegatiivne suurus. Lahutava rea ​​ja lahutusveeru ristumiskohas on lahutuselement, mille suhtes simpleksteisendus järgmiseks reegel: 1. lubava stringi elemendid jagatakse lubavaks elemendiks; 2. lahutusveeru elemendid jagunevad lahutuselemendiks ja muudavad oma märgi vastupidiseks; 3. ülejäänud tabeli elemendid on ümber paigutatud vastavalt ristkülikureeglile:

bij bis bkj=(bkj*bis-bij*bks)/bi

Teine duaalsusteoreem.

kui üks duaalülesannetest on optimaalse plaaniga, siis on ka teine ​​lahendatav, st. on optiline plaan. Sel juhul kattuvad sihtfunktsioonide äärmuslikud väärtused (j=1 kuni n) Σcjxj*= (i=1 kuni m)Σbiyi*, kui originaalis. probleem, sihtfunktsioon on plaanide hulgal piiramatu, siis sisse kahekordne probleem piirangute süsteem on ebaühtlane.

Teoreem TK maatriksi astme kohta.

Transpordiülesande maatriksi A aste on võrrandite arvust ühe võrra väiksem: r(A)=m+n-1.

39. Algoritm ZLP esialgse võrdlusplaani koostamiseks.

Esialgse võrdlusplaani leidmiseks saame soovitada järgmist algoritm:

1. kirjuta ülesanne Jordani tabeli kujul nii, et kõik vabade terminite veeru elemendid oleksid mittenegatiivsed, s.t. ebavõrdsus aio>=0 (i=1,m) oli täidetud. Need võrrandid, milles vabad liikmed on negatiivsed, korrutatakse kõigepealt -1-ga.

		-x1… -xn
0=	a1o	a11…. a1n
…..	…..	………………………..
0=	amo	am1……amn
f=		-c1…. -cn

Teisendage tabel Jordani elimineerimise sammude abil, asendades vasakpoolses veerus olevad nullid vastava x-ga. Samas igal sammul saab valida lubava iga veerg, mis sisaldab vähemalt ühte positiivset elementi. Lahutav rida määratakse vabade liikmete ja lahutusveeru vastavate positiivsete elementide suhtega. Kui erandiprotsessi ajal kohtab 0-stringi, siis kõik elemendid mis on nullid, ja vaba liige erineb nullist, siis pole süsteemil restriktiivsetele võrranditele lahendusi. Kui kohtame 0-rida, milles peale vaba liikme pole muid positiivseid elemente, siis pole restriktiivsete võrrandite süsteemil mittenegatiivseid lahendeid liigend, siis pärast teatud arvu samme asendatakse kõik vasakpoolses veerus olevad nullid x-ga ja seeläbi saadakse kindel alus ja sellest tulenevalt ka vastav võrdlusplaan.

40. Algoritm ZLP optimaalse võrdlusplaani koostamiseks.

Ho esialgse toetusplaani optimaalsust uuritakse.

Kui f-reas ei ole negatiivseid elemente (vaba liiget arvestamata), on -plaan optimaalne. Kui f-rida ka ei sisalda null elementi, siis on ainult üks optimaalne plaan; kui elementide hulgas on vähemalt üks null, siis on optimaalseid plaane lõpmatult palju. Kui f-reas on vähemalt üks negatiivne element ja vastavas veerus pole positiivseid elemente, siis ei ole sihtfunktsioon teostatavas piirkonnas piiratud. Probleem ei ole lahendatav. Kui f-real on vähemalt üks negatiivne element ja igas sellise elemendiga veerus on vähemalt üks positiivne element, siis saab liikuda uuele võrdlusplaanile, mis on optimaalsele lähemal. Selleks võetakse f-reas negatiivse elemendiga veerg kui lubav; Nad määravad lahutusstringi minimaalsest simpleksseost ja sooritavad Jordani elimineerimise sammu. Saadud võrdlusplaani optimaalsust kontrollitakse uuesti. Seda korratakse seni, kuni leitakse optimaalne võrdlusplaan või tuvastatakse probleemi lahendamatus.

Gomori meetodi algoritm.

1. Simpleksmeetodi abil leitakse ülesande optimaalne plaan. Kui kõik komponendid optimaalne plaan tervikuna, siis on see optimaalne. Muul juhul jätkake 2. sammuga

2. Mittetäisarvuliste komponentide hulgast tuleks valida see, millel on murdosa on suurim ja kasutades simplekstabeli vastavat rida, sõnastage valemi abil õige piir

(n-m,s=1)∑ (αkm+1)Xm+1≥(βk)

3. Teisenda sõnastatud ebavõrdsus samaväärseks nullvõrdsuseks ja kaasa see hulka simpleks laud mittetäisarvulise optimaalse plaaniga

4. Saadud laiendatud ülesanne lahendatakse simpleksmeetodil. Kui saadud plaan ei ole täisarv, jätkake sammuga 2.

Kui lahendusprotsessi käigus ilmub sirge mittetäisarvulise vaba liikmega ja muude täisarvu koefitsientidega, siis vastaval võrrandil pole lahendust täisarvudes. Sel juhul on algne probleem ka täisarvudes lahendamatu. Tema abiga on soovitav lahendada väikesed ülesanded, sest interaktsioonide arv võib olla väga suur.

Erinevad kujundid ZLP-kirjed (üldised, kanoonilised, sümmeetrilised)

MP ülesanded: optimaalse plaani kindlaksmääramine, optimaalse toodangu mahu määramine, põllukultuuride optimaalse kombinatsiooni määramine, optimaalse varade paketi moodustamine, panga kasumi maksimeerimine jne.

Üldine ZLP kutsutakse maksimeerimise (minimeerimise) probleem lineaarne funktsioon f=Σcj*xj-max(min) (1) lineaarsete piirangute korral ∑aij *xj(=<,=,>=)bi (i=1,n) (2) tingimusel, et xj>=0(j=1,n1), xj-suvaline (j=n1+1,n)(3) kus cj,aij, bi-konstantide arvud .

Sümmeetriline ZLP kirjutamise vormi nimetatakse funktsiooni (1) maksimeerimise probleemiks märgilise ebavõrdsuse lineaarsete piirangute korral< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >või = ja mittenegatiivsed muutujad. Kanooniline ZLP kirjutamise vormi nimetatakse maksimaalse funktsiooni (1) probleemiks võrduste ja mittenegatiivsete muutujate lineaarsete piirangute korral. Nimetatakse mis tahes muud vormi segatud.

min f(x) = -max(-f(x))

Võrratuse teisendamine võrrandiks ja vastupidi toimub lemma alusel: võrratuse a1x1+...+anxn iga lahendi x1...xn korral<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) ja vastupidi. Iga võrrandi 6 ja võrratuse 7 lahend x1…xn,xn+1 vastab võrratuse 5 lahendile x1…xn.

Tagumise sim-vormingult tagumisele kanoonilisele vormile liikumiseks peate sisestama tasakaalu (võrdsustavad) muutujad. See põhineb ebavõrdsuse teoreemil: mis tahes võrratust saab esitada võrrandi või lihtsa võrratusena.

ZLP kanooniline vorm- lineaarne programmeerimisülesanne kujul ax = b kus a on koefitsiendimaatriks, b on piiranguvektor.

Teenuse eesmärk. Veebikalkulaator on mõeldud PPP üleminekuks KZLP-le. Probleemi viimine kanoonilisele kujule tähendab, et kõik piirangud on võrdsuste kujul, lisades täiendavaid muutujaid.
Kui ühelegi muutujale x j piirangut ei kehtestata, siis asendatakse see täiendavate muutujate erinevusega, x j = x j1 - x j2, x j1 ≥ 0, x j2 ≥ 0.

Juhised. Valige muutujate arv ja ridade arv (piirangute arv). Saadud lahendus salvestatakse Wordi faili.

Muutujate arv 2 3 4 5 6 7 8 9 10
Ridade arv (piirangute arv) 2 3 4 5 6 7 8 9 10

Kuidas taandada lineaarse programmeerimise probleem kanooniliseks vormiks

ZLP matemaatilist mudelit nimetatakse põhilised, kui selles sisalduvad piirangud on esitatud võrrandite kujul, eeldusel, et muutujad ei ole negatiivsed.

Matemaatiline mudel on nn kanooniline, kui selle piirangute süsteem on esitatud m lineaarselt sõltumatu võrrandi süsteemina (süsteemi auaste r=m), eraldatakse süsteem ühiku alusel, defineeritakse vabad muutujad ja eesmärgifunktsiooni väljendatakse vabade muutujatena. Sel juhul on võrrandite parempoolsed küljed mittenegatiivsed (b i ≥ 0).

Muutujaid, mis sisalduvad ühes süsteemi võrrandis koefitsiendiga üks ja puuduvad teistes võrrandites, nimetatakse põhilised tundmatud ja kõik teised - tasuta.

Süsteemi lahendust nimetatakse põhilised, kui selles olevad vabad muutujad on võrdsed 0-ga ja sellel on vorm:
X alused = (0, 0; b 1 , …, b m), f (X alused) = c 0

Põhilahendus on süsteemi lahenduste hulga nurgapunkt, s.o. määrab mudeli lahendushulknurga tipu. Selliste lahenduste hulgas on ka see, milles sihtfunktsioon on optimaalne väärtus.

Põhilahendust nimetatakse võrdluslahenduseks, kui see on lubatav, s.t. süsteemi võrrandite (või võrratuste) kõik parempoolsed küljed on positiivsed b i ≥ 0.

Kanoonilise mudeli kompaktne vorm on:
AX = b
X ≥ 0
Z = CX(max)

Lubatava lahenduse kontseptsioon, lubatavate lahenduste piirkond, lineaarse programmeerimisprobleemi optimaalne lahendus.
Definitsioon 1. Vektorit X, mis rahuldab ZLP piirangute süsteemi, sealhulgas mittenegatiivsuse tingimusi, kui neid on, nimetatakse ZLP lubatavaks lahenduseks.
2. definitsioon. Kõigi vastuvõetavate lahenduste kogum moodustab PLP lubatavate lahenduste piirkonna (ADA).
3. määratlus. Teostatavat lahendust, mille puhul eesmärkfunktsioon saavutab maksimumi (või miinimumi), nimetatakse optimaalseks lahenduseks.

Näide nr 1. Vähendage järgmine LP-ülesanne kanooniliseks vormiks: F(X) = 5x 1 + 3x 2 → max vastavalt piirangutele:
2x 1 + 3x 2 ≤20
3x 1 + x 2 ≤15
4x 1 ≤16
3x 2 ≤12
Mudel on sisse kirjutatud standardvorm. Toome sisse tasakaalu mittenegatiivsed muutujad x 3 , x 4 , x 5 , x 6 , mille lisame ebavõrdsuse piirangute vasakule küljele. Sisustusfunktsiooni lisame kõik lisamuutujad, mille koefitsiendid on võrdsed nulliga:
Esimeses tähenduse võrratuses (≤) võtame kasutusele põhimuutuja x 3 . 2. tähenduse võrratuses (≤) võtame kasutusele põhimuutuja x 4 . Kolmandas võrratuses tutvustame põhimuutujat x 5 . Neljandas võrratuses - põhimuutuja x 6. Saame mudeli kanoonilise vormi:
2x 1 + 3x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 20
3x 1 + 1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 = 15
4x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 16
0x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 12
F(X) = 5x1 + 3x2 + 0x3 + 0x4 + 0x5 + 0x6 → max

Näide nr 2. Leidke süsteemi kaks etalonlahendust
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2

Sisseehitatud funktsiooni ja piirangute süsteemi kirjutamine erinevaid ülesandeid lineaarne programmeerimine pole sama: mõnes ülesandes on vaja leida sihtfunktsiooni miinimum ja teistes - maksimaalne; mõnel juhul sõltuvad nõutavad muutujad ühest indeksist, teistel aga kahest; mõnes ülesandes on piirangud määratud süsteemi kujul lineaarsed ebavõrdsused ja teistes – lineaarvõrrandisüsteemi kujul. Praktikas võib esineda ka probleeme, mille puhul osa piirangutest on lineaarsete võrratuste ja osa lineaarsete võrrandite kujul. Samuti ei pruugi kõik probleemid nõuda muutujate mittenegatiivsust.

Selliste erinevate lineaarsete programmeerimisprobleemide arvessevõtmine nõuab spetsiaalsete meetodite väljatöötamist nende üksikute klasside lahendamiseks. Keskendume oma tähelepanu õppimisele üldised omadused ja nn kanoonilisel kujul kirjutatud lineaarseid programmeerimismeetodeid.

Kui lineaarse programmeerimise ülesandes on algpiirangute süsteem võrrandite kujul nagu

ja peate leidma lineaarse sihtfunktsiooni maksimumi

siis loetakse lineaarse programmeerimise ülesanne kanoonilisel kujul kirjutatuks.

Iga lineaarse programmeerimise probleemi saab hõlpsasti taandada kanooniliseks vormiks. Üldjuhul piisab selleks, et esiteks on võimalik taandada eesmärkfunktsiooni minimeerimise probleem selle maksimeerimise probleemiks, teiseks liikuda ebavõrdsuse piirangutelt võrdsuse piirangutele ja kolmandaks muuta neid muutujaid, mis on ei allu mittenegatiivsuse tingimusele .

Juhul, kui peate leidma funktsiooni miinimumi , saame jätkata funktsiooni maksimumi leidmisega , kuna järgmine väide on tõsi:
.

Piirang-ebavõrdsus algne probleem, mis näeb välja nagu " ", saab muuta võrrandipiiranguks, lisades selle vasakule küljele täiendava mittenegatiivse muutuja ja vormi ebavõrdsuse piirangu ” – lahutades selle vasakust servast täiendava mittenegatiivse muutuja.

Pange tähele, et sisestatud täiendavate mittenegatiivsete muutujate arv on alati võrdne ebavõrdsete arvuga esialgses piirangute süsteemis.

Kasutusele võetud lisamuutujatel on väga spetsiifiline majanduslik tähendus. Seega, kui algse lineaarse programmeerimise probleemi piirangud peegeldavad tootmisressursside kulusid ja saadavust, siis numbriline väärtus lisamuutuja näitab vastava kasutamata ressursi hulka.

Pange tähele ka seda, et kui mõni muutuja ei allu mittenegatiivsuse tingimusele, siis tuleb see asendada kahe mittenegatiivse muutujaga Ja , olles vastu võtnud
.

Näide. Kirjutage kanoonilisel kujul järgmine lineaarse optimeerimise ülesanne: leidke funktsiooni miinimum
piirangute all

Lahendus

Selles ülesandes peate leidma sihtfunktsiooni miinimumi ja piirangute süsteem sisaldab nelja ebavõrdsust. Selle kanoonilisel kujul kirjutamiseks peate liikuma ebavõrdsuse piirangutelt võrrandipiirangutele ja teisendama ka sihtfunktsiooni.

Kuna ülesande piirangute süsteemis sisalduvate võrratuste arv on võrdne neljaga, tuleb see üleminek läbi viia nelja täiendava mittenegatiivse muutuja sisseviimisega. Veelgi enam, teises ja neljandas ebavõrdsuses on märk " ", seega lisame nende vasakule küljele täiendavaid muutujaid. Esimeses ja kolmandas ebavõrdsuses on märk " “, mis tähendab, et lahutame nende vasakult küljelt täiendavad muutujad.

Teisendame ka sihtfunktsiooni, muutes kõik märgid vastupidiseks ja leiame selle maksimumi.

Seega kirjutatakse see lineaarse programmeerimise probleem järgmisel kanoonilisel kujul:

funktsiooni maksimumi leidmine

piirangute all