Co je lineární program. Stručně o lineárním programování. Lineární programy s poli

Výše jsme prozkoumali různé praktické úkoly, které spadají do schématu lineární programování... V jednom z těchto úkolů lineární omezení vypadalo to jako nerovnost, v jiných - rovnosti, v jiných - obojí.

Zde budeme uvažovat problém lineárního programování s omezeními rovnosti – tzv. základní problém lineárního programování (0PLP).

V následujícím si ukážeme, jak lze přejít od problému s omezeními nerovnosti k LPLP a naopak.

Hlavní úkol lineárního programování je následující.

Existuje celá řada proměnných

Je potřeba najít takové nezáporné hodnoty těchto proměnných, které by systém uspokojily lineární rovnice:

a navíc by se minimalizovalo lineární funkce

Je zřejmé, že případ, kdy je třeba lineární funkci obrátit nikoli na minimum, ale na maximum, lze snadno zredukovat na předchozí, pokud změníme znaménko funkce a místo toho vezmeme v úvahu funkci

Domluvme se na volání libovolné sady proměnných

vyhovující rovnice (2.1).

Optimální řešení je takové z možných řešení, pro které se lineární funkce (2.2) stává minimem.

Základní problém lineárního programování nemusí mít řešení.

Může se ukázat, že rovnice (2.1) si odporují; může se ukázat, že mají řešení, ale ne v oblasti nezáporných hodnot. Pak OZLP nemá žádná schůdná řešení. Nakonec se může ukázat, že proveditelná řešení DLP existují, ale mezi nimi není žádné optimální: funkce L v oblasti proveditelných řešení je zdola neomezená.

S příklady takových vlastností OZLP se seznámíme v budoucnu.

Podívejme se nejprve na otázku existence přípustných řešení LPLP.

Při řešení této otázky můžeme vyloučit z uvažování lineární funkci L, kterou je nutné minimalizovat - přítomnost možných řešení určují pouze rovnice (2.1).

Nechť tedy existuje soustava rovnic (2.1). Existují nezáporné hodnoty, které splňují tento systém? Tato otázka je zvažována ve speciální části matematiky - lineární algebře.

Uveďme stručné shrnutí některých tvrzení lineární algebry, aniž bychom se zabývali důkazy odpovídajících vět.

Matice soustavy lineárních rovnic

se nazývá tabulka složená z koeficientů at

Rozšířená matice soustavy lineárních rovnic je stejná matice doplněná o sloupec volných členů:

Hodnost matice je největší řád nenulového determinantu, který lze získat odstraněním některých řádků a některých sloupců z matice.

V lineární algebře je dokázáno, že aby byl systém lineárních rovnic (2.1) kompatibilní, je nutné a postačující, aby hodnost matice systému byla rovna hodnosti jeho rozšířené matice.

Příklad 1. Je dána soustava tří rovnic se čtyřmi neznámými:

Zjistit, zda je systém kolaborativní?

Řešení. Systémová matice:

Rozšířená matice:

Stanovme hodnost první matice. Nesmí být více než 3 (protože počet řádků je 3). Poskládejme nějaký determinant tak, že z matice smažeme nějaký sloupec, například ten poslední. Dostaneme

Výpočtem tohoto determinantu podle známého pravidla dostaneme:

Tento determinant se nerovná nule, což znamená, že hodnost matice systému je 3. Je zřejmé, že hodnost rozšířené matice je také rovna 3, protože stejný determinant lze vytvořit z prvků rozšířená matice. Z rovnosti řad matic vyplývá, že soustava rovnic je konzistentní.

Příklad 2. Prozkoumat kompatibilitu systému dvou rovnic se třemi neznámými:

Řešení. Rozšířená matice systému:

(jeho levá strana je matice systému).

Pojďme najít hodnost matice systému složením všech možných determinantů druhého řádu:

Takže všechny možné determinanty druhého řádu, složené z prvků systémové matice, jsou rovny nule; tedy hodnost této matice systému

Najděte hodnost rozšířené matice. Determinant

Hodnost rozšířené matice se tedy nerovná hodnosti matice systému: Грфг, proto je systém rovnic nekonzistentní.

Příklad 3. Prozkoumat konzistenci soustavy tří rovnic se čtyřmi neznámými:

Řešení Rozšířená matice systému (společně se systémovou maticí):

Pojďme najít hodnost matice systému. Vezměte determinant třetího řádu složený z jeho prvků, například:

Je známo, že pokud je kterýkoli řádek determinantu lineární kombinací dvou jeho dalších čar, pak je determinant roven nule. V našem případě je třetí řada lineární kombinací prvních dvou: abychom ji získali, stačí přidat první řadu se zdvojenou druhou.

Je snadné ověřit, že každý determinant třetího řádu složený z prvků systémové matice má stejnou vlastnost, tedy hodnost systémové matice.

Protože existuje nenulový determinant druhého řádu, např.

pak je hodnost matice systému

Za použití stejného uvažování zajistíme, aby hodnost rozšířené matice byla rovna dvěma: V důsledku toho je systém rovnic konzistentní

Všimněte si, že tři rovnice tento příklad nejsou nezávislé: třetí lze získat z prvních dvou vynásobením druhého dvěma a přičtením k prvnímu. Třetí rovnice je tedy jednoduchým důsledkem prvních dvou. V systému jsou pouze dvě nezávislé rovnice: to se odráží ve skutečnosti, že hodnost matice systému

Pokud je tedy systém rovnic-omezení LPLP konzistentní, pak matice systému a jeho rozšířená matice mají stejnou úroveň.

Tato celková hodnost se nazývá hodnost systému; není to nic jiného než počet lineárně nezávislých rovnic mezi uloženými omezeními.

Je zřejmé, že hodnost systému nemůže být větší než počet rovnic:

Je také zřejmé, že hodnost systému nemůže být větší než celkový počet proměnných:

Hodnost matice systému je skutečně definována jako největší řád determinantu složeného z prvků matice; protože počet jeho řádků je stejný, pak; protože počet jeho sloupců je stejný.

Struktura problému lineárního programování v podstatě závisí na hodnosti systému omezení (2.1).

Uvažujme nejprve případ, kdy, tedy kdy počet lineárně nezávislých rovnic zahrnutých v soustavě (2.1) je roven počtu proměnných n. Zahodíme „zbytečné“ rovnice, které jsou lineárními kombinacemi jiných. Systém rovnic-omezení LPLP má podobu:

Od té doby determinant, složený z koeficientů,

není nula. Z algebry je známo, že v tomto případě má systém (2.4) jedinečné řešení. Pro zjištění hodnoty stačí nahradit sloupec v determinantu sloupcem volných členů a vydělit.

Takže pro systém rovnic-omezení má LPLP jedinečné řešení:

Pokud je v tomto řešení alespoň jedna z veličin záporná, znamená to, že výsledné řešení je nepřijatelné, a proto ZZLP nemá řešení.

Pokud jsou všechny veličiny nezáporné, pak je nalezené řešení přípustné. To je samozřejmě také optimální (protože žádné jiné neexistují).

Je zřejmé, že tento triviální případ nás nemůže zajímat.

Proto v následujícím budeme uvažovat pouze případ, kdy, tj. kdy počet nezávislých rovnic, který musí být splněn proměnnými počty proměnných samotných. Pak, pokud je systém kompatibilní, má nespočet řešení. V tomto případě můžeme proměnným přiřadit libovolné hodnoty (tzv. volné proměnné) a zbytek proměnných bude vyjádřen jejich prostřednictvím (těmto proměnným budeme říkat základní).

Lineární programy jsou programy, které se skládají z jednoduchých příkazů (operátorů).
Jednoduché příkazy (jednoduché instrukce algoritmu) se nazývají příkazy, které při svém provádění nevyužívají podmínky. Jednoduché operátory zahrnují přiřazení, vstupní a výstupní příkazy (operátory), volání pomocného algoritmu (podprogramu).

Operátor přiřazení. Nastavuje nebo mění aktuální hodnotu nějaké proměnné. Tím se změní obsah konkrétního paměťového prvku přiděleného této proměnné. Protože cílem každého algoritmu je dostat se na určité místo v paměti požadovanou hodnotu Tento operátor obsahuje téměř každý program. Vstupně-výstupní operátory. Standardní procedury zadávání dat se používají k určení počátečních hodnot určitých proměnných a skládají se z názvu procedury a vstupního seznamu obsahujícího názvy proměnných, jejichž hodnoty budou zadány z klávesnice nebo ze souboru, tzn. proměnným budou přiřazeny nějaké konkrétní hodnoty.
Častěji je vhodnější použít k určení počátečních hodnot příkaz input, spíše než příkaz přiřazení, protože pokud potřebujete program používat s jinými zdrojovými daty, nemusíte měnit text programu.
Pokud je v záznamu algoritmu vstupní příkaz, jeho provádění je přerušeno a řízení je přeneseno na program, který může provádět zadávání dat. Po zadání dat se řízení přenese na další příkaz algoritmu.
V Pascalu je postup zadávání dat:
READ (seznam záznamů);
READLN (Seznam položek).
Po provedení procedur READ a READLN přejde program do stavu čekání na vložení dat. Pokud je v seznamu položek uvedeno více proměnných, lze je zadat na jeden řádek, oddělené od sebe mezerou, nebo na samostatné řádky (ve sloupci), přičemž každou hodnotu dokončíte klávesou Enter.
Postup nebude ukončen, dokud nebudou zadány hodnoty pro všechny proměnné v seznamu. Typ vstupních hodnot musí odpovídat typu odpovídající proměnné.
Příkaz READLN se od příkazu READ liší tím, že po zadání požadovaného množství dat se kurzor přesune na další řádek.
Pokud se data zadávají z klávesnice, pak je vstupní seznam seznam proměnných, tzn. posloupnost názvů proměnných oddělených čárkami. Pokud je vstup ze souboru, pak v seznamu vstupů je první proměnnou proměnná souboru spojená se jménem skutečného souboru.
Standardní postupy pro výstup výsledků výpočtů se používají k výstupu jejich hodnot na obrazovku, tiskárnu nebo soubor. V Pascalu jsou postupy odvození:
WRITE (výstupní seznam);
WRITELN (výstupní seznam).
Seznam výstupních prvků je mnohem širší než u vstupních procedur. Může zahrnovat:
identifikátory veličin, jejichž hodnoty budou odeslány do odpovídajícího zařízení nebo souboru;
výrazy, jejichž hodnota bude nejprve vypočtena a poté odeslána do zařízení;
se staly veličinami (číselné, znakové, řetězcové).
Rozdíl mezi WRITE a WRITELN spočívá v tom, že příkaz WRITE spustí výstup z aktuální pozice kurzoru na obrazovce monitoru a kurzor zůstane na stejném řádku po ukončení výstupu. Příkaz WRITELN vytiskne hodnoty z aktuálního umístění a poté se kurzor přesune na další řádek. K přesunutí kurzoru na nový řádek můžete použít příkaz WRITELN bez výstupního seznamu.
Pokud se výstup provádí na obrazovce monitoru, je seznam výstupů seznamem proměnných nebo posloupností názvů proměnných, konstant nebo výrazů oddělených čárkami. Pokud se výstup provádí do souboru, pak první proměnnou v seznamu výstupů je proměnná souboru spojená se jménem skutečného souboru.
V příkazu output můžete za prvkem výstupního seznamu odděleným dvojtečkou zadat výstupní formát, tzn. šířka obrazovky, na které budou hodnoty umístěny. Při zobrazování platných dat můžete také zadat počet desetinných míst ve zlomkové části, která se má zobrazit.
Příklad: napište (A: 10: 3, B: 8).
Operátor pro volání pomocného algoritmu. Pascal implementuje rutinní rutiny a funkční rutiny. Podprogram je volán svým jménem se skutečnými parametry. V tomto případě mohou být místo skutečných argumentů specifické hodnoty, názvy skutečných proměnných, výrazy a místo výsledků pouze názvy skutečných proměnných. V tomto případě musí být počet, typy a účel formálních a skutečných parametrů v odpovídajících seznamech parametrů stejný.

Laboratorní práce č.1

Téma: "Programování lineární algoritmy... Práce s debuggerem "

Objektivní

1.1 Zvládnutí nejjednodušší struktury C programu.

1.2 Získání dovedností v organizaci input-output v jazyce C.

Technická podpora

2.1 Osobní počítač

2.2 Klávesnice.

2.3 Displej.

2.4 Tiskové zařízení.

Software

3.1 Operační sál systém Windows

3.2 Programovací systém Visual C++ verze 6.0 nebo Borland C++ verze 3.1 a novější.

Formulace problému

Psaní nejjednodušší program se zpracováním dat.

5.1 Téma a účel práce.

5.2 Popis problému.

5.3 Text programu.

5.4 Výsledky provádění programu.

5.5 Schémata algoritmu programů.

Obecná informace

Lineární program

Pokud jsou v programu všechny příkazy prováděny postupně, jeden po druhém, je takový program volán lineární. Vezměme si jako příklad program, který vypočítá výsledek pomocí daného vzorce.

Úkol 1.1. Výpočet vzorce

Napište program, který převede teplotu ve stupních Fahrenheita na stupně Celsia pomocí vzorce:

kde C je teplota ve stupních Celsia a F je teplota ve stupních Fahrenheita.

Před napsáním jakéhokoli programu je potřeba jasně definovat, co je do něj potřeba zadat a co bychom ve výsledku měli dostat.

V tomto případě:

Počáteční údaj je jedno reálné číslo, což je teplota ve stupních Celsia,

Výsledkem je další reálné číslo.

Před napsáním programu si otevřeme integrované prostředí Visual C++:

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

1) Soubor> Nový...

2) V okně, které se otevře:

Vyberte typ Aplikace konzoly Win32;

Do textového pole Název projektu zadejte název projektu;

Do textového pole Umístění zadejte (vyberte pomocí tlačítka ...) název adresáře, kde jsou umístěny soubory projektu, například G: / ASOIZ /

Klikněte levým tlačítkem na tlačítko OK.

3) Otevře se dialogové okno Win32 Console Application - Stepl of 1 a v něm:

Vyberte typ Prázdný projekt;

Klikněte na tlačítko Dokončit.

4) Po kliknutí se zobrazí okno Nový projekt, ve kterém klikněte na tlačítko OK.

1) Soubor > Nový .... Otevře se dialogové okno Nový.

2) Na kartě Soubory:

Vyberte typ souboru (v tomto případě: C ++ Source File);

Do textového pole Název souboru zadejte požadovaný název souboru;

Musí být zaškrtnuto políčko Přidat do projektu;

Klepněte na tlačítko OK.

Zadáme následující text programu:

Uvažujme každý řádek programu zvlášť.

Na začátku programu je napsána direktiva preprocesoru, podle které je hlavičkový soubor propojen se zdrojovým kódem programu ... Toto je soubor, který obsahuje popisy I/O operátorů cin a cout.

Jakýkoli program v jazyce C++ se skládá z funkcí, z nichž jedna musí mít název main, což znamená, že se program spouští z této funkce. Tělo funkce se zapisuje za závorkou ve složených závorkách (), tzn. ty příkazy, které chcete provést.

Při psaní programu vypadá jakákoli šablona takto:

#zahrnout<…>

deklarace proměnných;

zadání počátečních dat;

výpočet výsledku;

výstup výsledku;

Chcete-li uložit počáteční data a výsledky, musíte v ní přidělit dostatek místa paměť s náhodným přístupem... K tomu slouží operátor 2. V našem programu potřebujeme uložit dvě hodnoty: teplotu ve stupních Celsia a teplotu ve stupních Fahrenheita, takže v operátoru jsou definovány dvě proměnné. Jeden, pro udržování teploty ve stupních Fahrenheita, se nazývá fahr, druhý (ve stupních Celsia) - cels. Názvy proměnných udává programátor na základě jejich účelu. Název se může skládat pouze z latinských písmen, číslic a podtržítka a nesmí začínat číslicí.

Při popisu jakékoli proměnné ji musíte specifikovat typ. Protože teplota může nabývat nejen celočíselných hodnot, je pro proměnné zvolen skutečný typ plovák.

Základní typy:

int (krátké, bez znaménka) - celá čísla,

plovák (double, long double) - skutečný

char - znak

bool - boolovský

Aby uživatel programu věděl, v jakém okamžiku je požadováno zadání dat z klávesnice, je aplikována tzv. výzva k zadání (operátor 3). Na obrazovce se zobrazí údaj zadaný v operátoru. coutřetězec znaků a kurzor se přesune na další řádek. Pro přechod na další řádek použijte endl.

Příkaz 4 provádí vstup z klávesnice

K tomu se používá standardní objekt cin a operace extrahování (čtení) >>. Pokud je požadováno více než jedna hodnota, použije se řetězec operací >>.

Příkaz 5 vyhodnocuje výraz psaný napravo od operace přiřazení(označeno znaménkem =) a výsledek je přiřazen do proměnné cels, to znamená, že je uložen v paměti přidělené této proměnné. za prvé Celý konstanta 5 bude děleno pusa konstanta 9, pak se výsledek této operace vynásobí výsledkem odečtení 32 od proměnné fahr.

K zobrazení výsledku v příkazu 6 se používá objekt cout. Zobrazí se řetězec pěti prvků. Toto je čára "Fahrenheita:", hodnota proměnné fahr, řádek ", ve stupních Celsia:", hodnota proměnné cels a operátor zalomení řádku endl.

Poslední operátor (operátor 7) tohoto programu se z něj má vrátit a přenést hodnotu do vnějšího prostředí.

Dále program zkompilujeme. Chcete-li to provést, stiskněte tlačítko na panelu nástrojů nebo kombinaci kláves Ctrl + F7. Výstupní okno (ve spodní části obrazovky) by mělo zobrazit zprávu 0 chyb, 0 varování (0 chyb, 0 varování). Pokud jsou chyby, zkontrolujte je podle originálu.

Program spustíte stisknutím tlačítka na panelu nástrojů nebo kombinací kláves Ctrl + F5.

Při spuštění programu se místo ruských znaků zobrazí ???, což je způsobeno odlišnými standardy pro kódování znaků azbuky v operační systémy MS DOS a Windows. Chcete-li to opravit, přidejte do programu funkci CharToOem (přídavky jsou pro přehlednost zvýrazněny červeně)

#zahrnout

char * RUS (konst char * text)

CharToOem (text, buf);

float fahr, cels;

cout<

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

cout<

Funkce Rus () nelze použít více než jednou v řetězci operací<< для одного объекта cout tak jsme to rozdělili na dvě části.

Jak vidíte, výsledek provádění programu se stabilitou je nulový! To je způsobeno způsobem vyhodnocení výrazu. Podívejme se znovu na operátor 4. Konstanty 5 a 9 jsou celočíselného typu, takže výsledek jejich dělení je také celočíselný. Výsledek dalších výpočtů přirozeně nemůže být nic jiného než nula. Tuto chybu je snadné opravit - stačí napsat alespoň jednu z konstant jako reálné číslo, například:

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