ülesandeid lineaarne programmeerimine

2.1. Salvestamise mõiste ja vormid

Juhul, kui kõik piirangud on võrrandid ja kõik muutujad vastavad mittenegatiivsuse tingimusele, nimetatakse lineaarse programmeerimise ülesannet. kanooniline. Seda saab esitada koordinaatide, vektori või maatriksmärgistuse kujul.

a) kanoonilise LP-ülesande koordinaatkujul on vorm:

,
.

Selle probleemi saab kirjutada liitmismärgi abil:

,

,

,
,
.

b) kanooniline LP ülesanne vektorkujul on kujul: ,

,

Kus
;
;

,
;;
.

c) kanoonilise LP probleemi maatrikskujul on vorm:

,
,

Kus
,,.

2.2. Üldise lineaarse probleemi vähendamine

programmeerimine kanoonilisele kujule

Majandusprobleemide matemaatiliste mudelite koostamisel vormitakse piirangud peamiselt ebavõrdsuse süsteemideks. Seetõttu on vaja nendelt võrrandisüsteemidele üle minna. Mõelge näiteks lineaarsele ebavõrdsusele

ja lisage selle vasakule küljele teatud väärtus
nii, et ebavõrdsus muutub võrdsuseks.

Mittenegatiivne muutuja
nimetatakse täiendavaks muutujaks. Alljärgnev teoreem annab aluse sellise teisenduse võimalikkusele.

Teoreem 2.2.1. Iga otsus
ebavõrdsus (2.2.1) vastab võrrandi (2.2.2) ja ebavõrdsuse ainulaadsele lahendile
, ja vastupidi, igale võrrandi (2.2.2)c lahendile
vastab lahendusele
ebavõrdsused (2.2.1).

Tõestus. Lase
ebavõrdsuse lahendus (2.2.1). Siis. Võtame numbri
. Selge see
. Asendades võrrandisse (2.2.2), saame

Teoreemi esimene osa on tõestatud.

Olgu nüüd vektor rahuldab võrrandi (2.2.2) koos
, st viimase võrdsuse vasakpoolsest mittenegatiivsest väärtusest loobumine
, saame vastu jne.

Seega loob tõestatud teoreem tegelikult võimaluse viia mis tahes LP probleem kanoonilisele kujule. Selleks piisab, kui sisestada igasse piirangusse, millel on ebavõrdsuse kuju, oma täiendav mittenegatiivne muutuja. Veelgi enam, vormi (1.2.1) ebavõrdsuses ilmuvad need muutujad "+" märgiga ja vormi ebavõrdsuses (1.2.2) - märgiga "-". Sisestatakse täiendavad muutujad sihtfunktsioon nullkoefitsientidega ja seetõttu ei mõjuta selle väärtust.

kommenteerida. Edaspidi esitame kanoonilise LP-ülesande simpleksmeetodi, kui uurime sihtfunktsiooni miinimumi jaoks. Nendes probleemides, kus tuleb leida maksimum
, piisab funktsiooni kaalumisest
, otsi ta üles minimaalne väärtus ja seejärel, muutes märki vastupidiseks, määrake soovitud maksimaalne väärtus
.

3. Graafiline meetod ülesannete lahendamiseks

lineaarne programmeerimine

3.1. Üldmõisted, näited

Juhtudel, kui LP-ülesandes on ainult kaks muutujat, võite kasutada graafiline meetod. Olgu vaja leida funktsiooni maksimaalne (minimaalne) väärtus
piirangute all

(3.1.1)

See meetod põhineb võimalusel kujutada graafiliselt probleemi teostatavate lahenduste piirkonda, s.t. süsteemi (3.1.1) rahuldamine ja nende hulgast optimaalse lahenduse leidmine. Ülesande teostatavate lahenduste piirkond konstrueeritakse iga antud piirangu (3.1.1) lahenduspiirkondade lõikepunktina (ühisosana). Igaüks neist määratleb pooltasandi piiriga
,
. Selleks et määrata, kumb kahest pooltasandist on lahenduspiirkond, piisab, kui asendada võrratusesse suvalise punkti, mis ei asu sirgel, koordinaadid: kui see on täidetud, siis on lahenduspiirkonnaks pooltasapind, mis sisaldab see punkt, kui ebavõrdsus ei ole täidetud, siis on lahenduspiirkonnaks pooltasapind, mis ei sisalda antud punkti.

Nende pooltasandite ristumiskoht moodustab teatud ala, mida nimetatakse lahenduspolügooniks ja mis on kumer hulk. (Eeldame, et piirangute süsteem on järjekindel ja selle lahenduste hulknurk on piiratud.) Võimalike lahenduste hulgast optimaalse leidmiseks kasutatakse nivoojooni ja võrdlussirge.

Tasejoon nimetatakse sirgeks, millel sihtfunktsioon võtab konstantse väärtuse. Tasemejoone võrrandil on vorm

, Kus
. Kõik taseme jooned on üksteisega paralleelsed. Nende normaalne
.

Võrdlusjoon nimetatakse tasapinnaliseks sirgeks, millel on vähemalt üks ühine punkt teostatavate lahenduste piirkonnaga, mille suhtes see piirkond asub ühes pooltasanditest (joonis 1).

Väärtused
suurenemine vektori suunas
. Seetõttu on vaja tasemejoont liigutada
selle vektori suunas paralleelselt endaga võrdlusjoonega L 1 maksimaalses ülesandes ja vastupidises suunas - minimaalses ülesandes (kuni võrdlusjooneni L 2).

Anname näite 1.1 lahenduse. Tuletame meelde, et peame leidma funktsiooni maksimumi
piirangute all

Lahendus. Ehitame teostatavate lahenduste piirkonna. Numerdame probleemi piirangud. Ristkülikukujulises Descartes'i koordinaatsüsteemis (joonis 2) konstrueerime sirge

, mis vastab piirangule (1). Leiame, milline pooltasanditest, milleks see sirge kogu koordinaattasandi jagab, on ebavõrdsuse (1) lahendite valdkond.

Selleks piisab, kui asendada ebavõrdsusega mis tahes punkti koordinaadid, mis ei asu sirgel. Kuna see on sirge ei läbi päritolu, asendaja
esimese piiranguni. Saame range ebavõrdsuse
. Seetõttu punkt
asub lahenduste pooltasandil. Samamoodi konstrueerime sirge

ja piirangu (2) lahenduspiirkond. Leiame lahenduste pooltasandite ühisosa, arvestades piiranguid (3). Toome joonisel 2 esile võimalike lahenduste piirkonna tumeda värviga.

Tasajoone ehitamine
ja vektor
, mis näitab funktsiooni suurendamise suunda ja joonega risti

. Tasejoon
liikuda endaga paralleelselt suunas
võrdlusjoonele. Leiame, et eesmärgifunktsioon saavutab punktis maksimumi
joonte lõikepunkt Ja . Nende sirgete võrrandisüsteemi lahendamine
, saame punkti koordinaadid
. Seetõttu ja
,
optimaalne lahendus.

Näide 3.1. Leia funktsiooni miinimum
piirangute süsteemi alusel

Lahendus. Konstrueerime teostatavate lahenduste piirkonna (vt joonis 3), vektori
ja üks tasemejoontest
. Liigutage tasemejoont vastassuunas
, kuna lahendatakse funktsiooni miinimumi leidmise probleem. Sel juhul läbib võrdlusjoon punkti A (joonis 3), mille koordinaadid leitakse süsteemi lahendusest

Niisiis,
. Arvutame.

kommenteerida. Tegelikult oleneb see teostatavate lahenduste piirkonna tüübist ja eesmärgifunktsioonist
LP-ülesandel võib olla üks lahendus, lõpmatu arv lahendusi või üldse mitte lahendust.

Näide 3.2. Leia funktsiooni miinimum
piirangute all

Lahendus. Konstrueerime teostatavate lahenduste piirkonna, nivoojoonte normaalse
ja üks tasemejoontest , millel on selle piirkonnaga ühised punktid. Tasemejoone liigutamine tavalisele suunale vastupidises suunas , kuna lahendatakse funktsiooni miinimumi leidmise probleem. Tasajoonte normaalne
ja piirjoone normaal , mille suunas nivoojooned liiguvad, on paralleelsed, kuna nende koordinaadid on võrdelised
. Seetõttu ühtib võrdlusjoon piirijoonega teostatavate lahenduste piirkonda ja läbib selle piirkonna kahte nurgapunkti Ja (joonis 4).

Probleemil on lõpmatu arv optimaalseid lahendusi, mis on segmendi punktid
. Need punktid
,
leiame vastavate võrrandisüsteemide lahendamisel:

;
;

,
;
,
;

;
.

Arvutame.

Vastus:
juures
,
.

Näide 3.3. Lahendage lineaarse programmeerimise ülesanne

Lahendus. Ehitame teostatavate lahenduste piirkonna, normaalse
ja üks tasemejoontest. Selles ülesandes on vaja leida sihtfunktsiooni maksimum, seega nivoojoon liikuda normaalses suunas. Tulenevalt asjaolust, et selles suunas ei ole teostatavate lahenduste valik piiratud, läheb nivoojoon lõpmatuseni (joon. 5).

Probleemil pole lahendust, kuna eesmärkfunktsioon on piiramatu.

Vastus:
.

: 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 ekstreemumi leidmise meetodite väljatöötamiseks lineaarsed funktsioonid mitu muutujat lineaarsega 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õrdsused.

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, saab 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 inimvahetust, pooltooteid kaaluga 260 kg ja masinaid 370 masinavahetust. Iga tooteliigi ressursitarbimise määrad ja kasum ühiku kohta on toodud tabelis 1.

Vajalik:

a) meik matemaatiline mudel maksimaalset kasumit teeniva tootmisplaani kindlaksmääramise ülesanne;

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, siis piirang (b) võtab 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" punkte, kuna need näitavad mudeli täiustamise põhisuundi.

PAP-i 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 osa 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 sisestatakse muutujad x 4, x 6 vasak pool"+" märgiga ja x 5 "-" märgiga sisestatakse teise võrrandisse.

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

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 otsitavad 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:
.

Algse probleemi ebavõrdsuse piirang, mille vorm on " ", 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 see ülesanne lineaarne programmeerimine kirjutatakse järgmisel kanoonilisel kujul:

funktsiooni maksimumi leidmine

piirangute all

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 olevad piirangud on esitatud võrrandite kujul, eeldusel, et muutujad ei ole negatiivsed.

Matemaatilist mudelit nimetatakse kanooniline, kui selle piirangute süsteem on esitatud m lineaarselt sõltumatu võrrandi süsteemi kujul (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)

Vastuvõetava lahenduse kontseptsioon, vastuvõetavate lahenduste valdkond, optimaalne lahendus lineaarse programmeerimise probleemid.
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 sihtfunktsioon 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 piirangute korral:
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 kanooniline vorm mudelid:
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