Kaj je linearni program. Na kratko o linearnem programiranju. Linearni programi z matrikami

Zgoraj smo obravnavali različne praktične naloge, ki se nanašajo na shemo linearno programiranje... Pri eni od teh nalog linearne omejitve videti kot neenakost, v drugih - enakosti, v drugih - oboje.

Tu bomo obravnavali problem linearnega programiranja z omejitvami enakosti - tako imenovani osnovni problem linearnega programiranja (0PLP).

V nadaljevanju bomo pokazali, kako lahko od problema z omejitvami neenakosti preidemo v LPLP in obratno.

Glavna naloga linearnega programiranja je naslednja.

Obstaja več spremenljivk

Poiskati je treba take negativne vrednosti teh spremenljivk, ki bi zadovoljile sistem linearne enačbe:

in bi poleg tega zmanjšali linearna funkcija

Očitno se primer, ko je treba linearno funkcijo obrniti ne na minimum, ampak na maksimum, zlahka zmanjša na prejšnjo, če spremenimo znak funkcije in namesto tega upoštevamo funkcijo

Strinjamo se, da pokličemo kateri koli niz spremenljivk

izpolnjujejo enačbe (2.1).

Optimalna rešitev je rešitev možnih rešitev, pri kateri linearna funkcija (2.2) postane minimalna.

Osnovnemu problemu linearnega programiranja ni treba imeti rešitve.

Lahko se izkaže, da so enačbe (2.1) v nasprotju; lahko se izkaže, da imajo rešitev, vendar ne v območju negativnih vrednosti. Potem OZLP nima izvedljivih rešitev. Končno se lahko izkaže, da možne rešitve DLP obstajajo, vendar med njimi ni optimalne: funkcija L v območju izvedljivih rešitev ni omejena od spodaj.

S primeri tovrstnih značilnosti OZLP se bomo seznanili v prihodnje.

Najprej razmislimo o vprašanju obstoja dopustnih rešitev LPLP.

Pri reševanju tega vprašanja lahko izločimo linearno funkcijo L, ki jo moramo minimizirati - prisotnost izvedljivih rešitev določajo le enačbe (2.1).

Naj torej obstaja sistem enačb (2.1). Ali obstajajo negativne vrednosti, ki ustrezajo temu sistemu? To vprašanje obravnavamo v posebnem poglavju matematike - linearni algebri.

Podajmo kratek povzetek nekaterih izjav linearne algebre, ne da bi se osredotočali na dokaze ustreznih izrekov

Matrica sistema linearnih enačb

se imenuje tabela, sestavljena iz koeficientov pri

Razširjena matrika sistema linearnih enačb je ista matrika, dopolnjena s stolpcem prostih izrazov:

Uvrstitev matrike je največji vrstni red determinante, ki ni nič, kar lahko dobimo z brisanjem nekaterih vrstic in nekaj stolpcev iz matrice.

V linearni algebri je dokazano, da je za združljivost sistema linearnih enačb (2.1) potrebno in zadostuje, da je rang matrike sistema enak rang njene razširjene matrike.

Primer 1. Podan je sistem treh enačb s štirimi neznankami:

Ugotovite, ali je sistem sodelovalni?

Rešitev. Sistemska matrika:

Razširjena matrika:

Določimo rang prve matrice. Ne sme biti več kot 3 (ker je število vrstic 3). Sestavimo nekaj determinante, tako da izbrišemo nekaj stolpcev iz matrice, na primer zadnjega. Dobimo

Če izračunamo to determinanto po znanem pravilu, dobimo:

Ta determinanta ni enaka nič, kar pomeni, da je rang matrike sistema 3. Očitno je tudi rang razširjene matrike enak 3, saj je ista determinanta lahko sestavljena iz elementov razširjena matrika. Iz enakosti rangov matric sledi, da je sistem enačb skladen.

Primer 2. Za raziskovanje združljivosti sistema dveh enačb s tremi neznankami:

Rešitev. Razširjena sistemska matrika:

(njegova leva stran je sistemska matrika).

Poiščimo rang matrike sistema tako, da sestavimo vse možne determinante drugega reda:

Torej so vse možne determinante drugega reda, sestavljene iz elementov matrike sistema, enake nič; torej rang te matrice sistema

Poiščite uvrstitev razširjene matrike. Odločilno

Zato rang razširjene matrike ni enak rang matrike sistema: Грфг, zato je sistem enačb nedosleden.

Primer 3. Za raziskovanje skladnosti sistema treh enačb s štirimi neznankami:

Rešitev Razširjena sistemska matrika (skupaj s sistemsko matrico):

Poiščimo rang matrike sistema. Vzemimo determinanto tretjega reda, sestavljeno iz njenih elementov, na primer:

Znano je, da če je katera koli vrstica determinante linearna kombinacija dveh drugih vrst, potem je determinanta enaka nič. V našem primeru je tretja vrstica linearna kombinacija prvih dveh: da jo dobimo, je dovolj, da prvo vrstico dodamo s podvojeno drugo.

Preprosto je preveriti, ali ima katera koli determinanta tretjega reda, sestavljena iz elementov sistemske matrike, enako lastnost, zato ima rang sistemske matrice.

Ker obstaja determinanta drugega ničelnega reda, npr.

potem je rang matrike sistema

Z istim sklepanjem bomo zagotovili, da je rang razširjene matrike enak dvema: Sistem enačb je zato skladen

Upoštevajte, da tri enačbe ta primer nista neodvisna: tretjega lahko dobite iz prvih dveh, tako da drugo pomnožite z dvema in prvemu dodate. Zato je tretja enačba preprosta posledica prvih dveh. V sistemu obstajata samo dve neodvisni enačbi: to se odraža v dejstvu, da je rang matrike sistema

Torej, če je sistem enačb-omejitev LPLP skladen, imata matrika sistema in njegova razširjena matrika enak rang.

Ta skupni rang se imenuje rang sistema; ni nič drugega kot število linearno neodvisnih enačb med navedenimi omejitvami.

Očitno rang sistema ne more biti večji od števila enačb:

Očitno je tudi, da rang sistema ne more biti večji od skupnega števila spremenljivk:

Dejansko je rang matrike sistema opredeljen kot največji red determinante, sestavljene iz elementov matrike; ker je število njegovih vrstic enako; ker je število njegovih stolpcev enako, potem.

Struktura problema linearnega programiranja je v bistvu odvisna od ranga sistema omejitev (2.1).

Najprej razmislimo o primeru, ko je, to je, ko je število linearno neodvisnih enačb, vključenih v sistem (2.1), enako številu spremenljivk n. "Nepotrebne" enačbe, ki so linearne kombinacije drugih, zavržemo. Sistem enačb-omejitev LPLP ima obliko:

Ker je determinanta, sestavljena iz koeficientov,

ni nič. Iz algebre je znano, da ima v tem primeru sistem (2.4) edinstveno rešitev. Če želite poiskati vrednost, je dovolj, da stolpec v determinanti zamenjate s stolpcem prostih članov in delite s.

Torej, za sistem enačb-omejitev ima LPLP edinstveno rešitev:

Če je v tej raztopini vsaj ena od količin negativna, to pomeni, da je dobljena raztopina nesprejemljiva in zato LPLP nima rešitve.

Če so vse količine negativne, je ugotovljena rešitev dopustna. Očitno je tudi optimalno (ker drugih ni).

Očitno nas ta trivialni primer ne more zanimati.

Zato bomo v nadaljevanju obravnavali le primer, ko, to je, ko bo število neodvisnih enačb, ki jih morajo zadovoljiti številke spremenljivk samih spremenljivk. Če je sistem združljiv, ima nešteto rešitev. V tem primeru lahko spremenljivkam dodelimo poljubne vrednosti (tako imenovane proste spremenljivke), preostale spremenljivke pa bodo izražene prek njih (te spremenljivke bomo poimenovali osnovne).

Linearni programi so programi, ki so sestavljeni iz preprostih ukazov (operatorjev).
Preprosti ukazi (preprosta navodila algoritma) se imenujejo ukazi, ki pri izvajanju ne uporabljajo pogojev. Enostavni operaterji vključujejo ukaze za dodelitev, vnos in izhod (operaterji), klic pomožnega algoritma (podprogram).

Operater dodelitve. Nastavi ali spremeni trenutno vrednost neke spremenljivke. S tem se spremeni vsebina določenega pomnilniškega elementa, dodeljenega tej spremenljivki. Ker je cilj katerega koli algoritma priti na določeno mesto v pomnilniku želeno vrednost, skoraj vsak program vsebuje tega operaterja. V / I operaterji. Standardni postopki vnosa podatkov se uporabljajo za določanje začetnih vrednosti določenih spremenljivk in so sestavljeni iz imena postopka in vnosnega seznama, ki vsebuje imena spremenljivk, katerih vrednosti bodo vnesene s tipkovnice ali iz datoteke, tj. spremenljivkam bodo dodeljene nekatere posebne vrednosti.
Pogosteje je za določanje začetnih vrednosti bolj priročno uporabiti ukaz za vnos, ne pa ukaza za dodelitev, ker če morate program uporabiti z drugimi izvornimi podatki, vam ni treba spreminjati besedila programa.
Če je v zapisu algoritma vhodni ukaz, se njegovo izvajanje prekine in nadzor se prenese na program, ki lahko izvede vnos podatkov. Po vnosu podatkov se nadzor prenese na naslednji ukaz algoritma.
V Pascalu je postopek vnosa podatkov naslednji:
PREBERI (seznam vnosov);
READLN (Seznam vnosov).
Ko se izvedeta postopka READ in READLN, program preide v stanje čakanja na vnos podatkov. Če je na seznamu vnosov določenih več spremenljivk, jih je mogoče vnesti v eno vrstico, ločeno drug od drugega s presledkom ali v ločene vrstice (v stolpec), pri čemer vnos vsake vrednosti zaključite s tipko Enter.
Postopek se ne bo končal, dokler ne vnesete vrednosti za vse spremenljivke na seznamu. Vrsta vhodnih vrednosti se mora ujemati z vrsto ustrezne spremenljivke.
Stavek READLN se od stavka READ razlikuje po tem, da se po vnosu zahtevane količine podatkov kazalec premakne v naslednjo vrstico.
Če podatke vnašamo s tipkovnice, potem je vnosni seznam seznam spremenljivk, tj. zaporedje imen spremenljivk, ločenih z vejicami. Če je vnos iz datoteke, je prva spremenljivka na vhodnem seznamu datoteka, povezana z imenom prave datoteke.
Standardni postopki za prikaz rezultatov izračunov se uporabljajo za izpis njihovih vrednosti na zaslon, tiskalnik ali datoteko. V Pascalu so postopki sklepanja:
WRITE (seznam izhodov);
WRITELN (seznam izhodov).
Seznam izhodnih elementov je veliko širši kot v vnosnih postopkih. Lahko vključuje:
identifikatorje količin, katerih vrednosti bodo izšle v ustrezno napravo ali datoteko;
izrazi, katerih vrednost se najprej izračuna in nato pošlje v napravo;
so postale količine (številske, znakovne, nizovske).
Razlika med WRITE in WRITELN je v tem, da se stavek WRITE začne na trenutni lokaciji kurzorja na zaslonu monitorja, kurzor pa ostane v isti vrstici po koncu izhoda. Stavek WRITELN natisne vrednosti s trenutne lokacije, nato pa se kazalec premakne v naslednjo vrstico. Za premik kurzorja v novo vrstico lahko uporabite stavek WRITELN brez izhodnega seznama.
Če se izpis izvede na zaslonu monitorja, je izhodni seznam seznam spremenljivk ali zaporedje imen spremenljivk, konstant ali izrazov, ločenih z vejicami. Če se izpis izvede v datoteko, je prva spremenljivka na izhodnem seznamu spremenljivka datoteke, povezana z imenom prave datoteke.
V izhodnem ukazu lahko po elementu izhodnega seznama, ločenem z dvopičjem, določite izhodno obliko, tj. širino zaslona, na katerem bodo vrednosti. Ko prikazujete veljavne podatke, lahko v delnem delu, ki ga želite prikazati, določite tudi število decimalnih mest.
Primer: napišite (A: 10: 3, B: 8).
Operater za klic pomožnega algoritma. V Pascalu se izvajajo rutinski postopki in rutinske funkcije. Podprogram se pokliče po svojem imenu z navedbo dejanskih parametrov. V tem primeru so namesto dejanskih argumentov lahko določene vrednosti, imena dejanskih spremenljivk, izrazi in namesto rezultatov - samo imena dejanskih spremenljivk. V tem primeru morajo biti število, vrste in namen formalnih in dejanskih parametrov na ustreznih seznamih parametrov enaki.

Laboratorijsko delo št

Tema: "Programiranje linearni algoritmi... Delo z razhroščevalnikom "

namen dela

1.1 Obvladovanje najpreprostejše strukture programa C.

1.2 Pridobivanje spretnosti pri organizaciji vnosa-izhoda v jeziku C.

Tehnična podpora

2.1 Osebni računalnik

2.2 Tipkovnica.

2.3 Zaslon.

2.4 Tiskalna naprava.

Programska oprema

3.1 Operacijska soba Sistem Windows

3.2 Programski sistem Visual C ++ različice 6.0 ali Borland C ++ različice 3.1 in novejše.

Formulacija problema

Pisanje najpreprostejši program z obdelavo podatkov.

5.1 Tema in namen dela.

5.2 Izjava o problemu.

5.3 Besedilo programa.

5.4 Rezultati izvajanja programa.

5.5 Sheme algoritma programov.

Splošne informacije

Linearni program

Če se v programu vsi stavki izvajajo zaporedno, drug za drugim, se tak program pokliče linearno. Za primer razmislite o programu, ki izračuna rezultat z uporabo formule.

Naloga 1.1. Izračun po formuli

Napišite program, ki pretvori temperaturo v stopinjah Fahrenheita v stopinje Celzija po formuli:

kjer je C temperatura Celzija in F temperatura Fahrenheita.

Pred pisanjem katerega koli programa je treba jasno opredeliti, kaj je treba vanj vnesti in kaj bi morali dobiti.

V tem primeru:

Začetni podatek je eno realno število, ki predstavlja temperaturo v Celzijah,

Rezultat je drugo resnično število.

Pred pisanjem programa odprimo integrirano okolje Visual C ++:

Start / Programi / Microsoft Visual Studio / Microsoft Visual C ++ 6.00

1) Datoteka> Novo ...

2) V oknu, ki se odpre:

Izberite vrsto aplikacije Win32 Console;

V besedilno polje Ime projekta vnesite ime projekta;

Vnesite (izberite z gumbom ...) ime imenika, v katerem so projektne datoteke, v besedilno polje Lokacija, na primer G: / ASOIZ /

Z levo tipko miške kliknite gumb V redu.

3) Odpre se pogovorno okno Win32 Console - Stepl of 1 in v njem:

Izberite vrsto Prazen projekt;

Kliknite gumb Dokončaj.

4) Po kliku se prikaže okno New Project, v katerem kliknite gumb V redu.

1) Datoteka > Novo .... S tem se odpre pogovorno okno Novo.

2) Na zavihku Datoteke:

Izberite vrsto datoteke (v tem primeru: izvorna datoteka C ++);

V besedilno polje Ime datoteke vnesite želeno ime datoteke;

Potrditveno polje Dodaj v projekt mora biti omogočeno;

Kliknite gumb V redu.

Vtipkamo naslednje besedilo programa:

Razmislimo o vsaki vrstici programa posebej.

Na začetku programa je napisana predprocesorska direktiva, po kateri je datoteka glave povezana z izvorno kodo programa ... To je datoteka, ki vsebuje opise V / I operaterjev cin in cout.

Vsak program C ++ je sestavljen iz funkcij, od katerih mora ena imeti ime main, kar kaže, da se program zažene iz te funkcije. Za oklepaji je telo funkcije zapisano v ukrivljenih oklepajih (), tj. tiste izjave, ki jih želite izvesti.

Pri pisanju programa je vsaka predloga videti tako:

#vključi<…>

izjava spremenljivk;

vnos začetnih podatkov;

izračun rezultata;

izid rezultata;

Za shranjevanje začetnih podatkov in rezultatov morate dodeliti dovolj prostora pomnilnik z naključnim dostopom... Za to se uporablja operater 2. V našem programu moramo shraniti dve vrednosti: temperaturo v Celzijah in temperaturo v Fahrenheitu, zato sta v operaterju definirani dve spremenljivki. Eden, za vzdrževanje temperature v Fahrenheitu, se imenuje fahr, drugi (Celzij) - cels. Imena spremenljivk poda programer glede na njihov namen. Ime je lahko sestavljeno samo iz latiničnih črk, številk in podčrtaja in se ne sme začeti s številko.

Ko opisujete katero koli spremenljivko, jo morate podati tip. Ker lahko temperatura prevzame ne le celoštevilske vrednosti, je za spremenljivke izbran dejanski tip plavati.

Osnovne vrste:

int (kratko, brez podpisa) - cela števila,

float (dvojni, dolgi dvojni) - pravi

char - lik

bool - logično

Da bi uporabnik programa vedel, v katerem trenutku mora vnesti podatke s tipkovnice, se uporabi tako imenovani vnosni poziv (operater 3). Navedeno v operaterju se prikaže na zaslonu. cout niz znakov in kazalec se premakne v naslednjo vrstico. Če se želite premakniti v naslednjo vrstico, uporabite endl.

Izjava 4 izvaja tipkovnico

Za to se uporablja standardni predmet cin in operacijo izvlečenja (branja) >>. Če je potrebnih več vrednosti, se uporabi veriga operacij >>.

Izjava 5 ocenjuje izraz, napisan na desni strani dodelitvene operacije(označeno z =), rezultat pa je dodeljen spremenljivki cels, to je shranjen v pomnilniku, dodeljenem tej spremenljivki. Najprej cel konstanta 5 se deli z poljub konstanta 9, potem se rezultat te operacije pomnoži z rezultatom odštevanja 32 od spremenljivke fahr.

Za prikaz rezultata v stavku 6 se uporablja objekt cout. Prikaže se veriga petih elementov. To je linija "Fahrenheit:", vrednost spremenljivke fahr, vrstica ", v stopinjah Celzija:", vrednost spremenljivke cels in operator preloma vrstice endl.

Zadnji operater (operater 7) tega programa naj bi se vrnil iz njega in vrednost prenesel v zunanje okolje.

Nato sestavimo program. To storite tako, da pritisnete gumb na orodni vrstici ali kombinacijo tipk Ctrl + F7. Izhodno okno (na dnu zaslona) bi moralo prikazati sporočilo 0 napak (e), 0 opozorila (0 napak, 0 opozoril). Če pride do napak, preverite izvirnik.

Za zagon programa pritisnite gumb na orodni vrstici ali kombinacijo tipk Ctrl + F5.

Pri zagonu programa namesto ruskih znakov vidimo ???, kar je posledica različnih standardov za kodiranje cirilicnih znakov v operacijski sistemi MS DOS in Windows. Če želite to popraviti, v program dodajte funkcijo CharToOem (dodatki so zaradi jasnosti označeni z rdečo barvo)

#vključi

char * RUS (const char * besedilo)

CharToOem (besedilo, buf);

float fahr, cels;

cout<

cels = 5/9 * (fahr - 32);

cout<

Funkcija Rus () ni mogoče uporabiti več kot enkrat v verigi operacij<< для одного объекта cout zato smo ga razdelili na dva dela.

Kot lahko vidite, je rezultat izvajanja programa s stabilnostjo nič! To je posledica načina ovrednotenja izraza. Vrnimo se k operatorju 4. Konstanti 5 in 9 sta celoštevilskega tipa, zato je tudi rezultat njihove delitve celoštevilčen. Seveda rezultat nadaljnjih izračunov ne more biti nič drugega kot nič. To napako je enostavno popraviti - dovolj je, da vsaj eno konstanto napišete kot realno število, na primer:

cels = 5/9 * (fahr - 32);