• Stručně o lineárním programování. Lineární programy - abstrakt Mezi lineární programy patří

    Lineární se nazývá program, který je záznamem lineárního algoritmu. V takovém programu jsou všechny příkazy prováděny přísně sekvenčně, tzn. po provedení každého z nich (kromě END) počítač automaticky přejde k provedení operátora následujícího za ním.

    Psaní jednoduchých programů

    Prvoci budeme nazývat lineární programy, které neobsahují pole. Kompilace takových programů vyžaduje znalost dříve uvažovaných operátorů, pochopení jejich korespondence s bloky schématu algoritmu a provádí se podle takového jednoduchého pravidla:

    zvážit bloky schématu algoritmu (věřit, že je dáno) v pořadí, začínáme od prvního a pro každý z nich zapíšeme odpovídající operátor ZÁKLADNÍ, tzn.

    pro blok Start- REM operátor s názvem programu;

    pro blok Vstup - vstupní operátor;

    pro blok proces - operátor přiřazení;

    pro blok Závěr - výstupní operátor;

    pro blok Stop- operátor END.

    To je celé pravidlo!

    Nyní uvádíme příklady konkrétních programů uvažovaného typu.

    Úkol 12.2

    Vypočítejte obvod pravoúhlého trojúhelníku daný délkou jeho nohou.

    Úkol 12.3

    Vyměňte hodnoty A a B.

    Řešeníúkoly 12.2 a 12.3. Tyto úkoly byly probrány v kapitole 10, takže na Obr. 12.2 ukazuje bez vysvětlení schéma algoritmu a programu úlohy 10.2 a na Obr. 12.3 - totéž pro problém 10.3.

    Na Obr. Šipky 12.2 a 12.3 ukazují shodu příkazů programu s bloky schématu algoritmu.

    Představujeme programy pro řešení dalších dvou problémů. Program pro úlohu 12.1 ilustruje použití množství různých typů. Program úlohy 12.2 demonstruje organizaci výstupu dat do tiskového zařízení.

    Rýže. 12.2

    Úkol 12.1

    Vypočítejte hodnoty Na a Z podle vzorců:

    Kde V A V - celočíselné hodnoty.

    Řešení

    Výchozí data: E %, V %, C, X, A(a).

    Výsledek: Y,Z %.

    Pořadí operací je zde zřejmé, takže program rovnou napíšeme:

    • 10 REM ÚKOL 1
    • 20 TISKNOUT "ZADEJTE D%, B%, C, X, A"
    • 30 INPUT D%, V%, C, X, A 40 R$="HBAH0B, 10A CL"
    • 50 Z%=2*D%-3*B%
    • 60 Y=(3*ABS(X)+C:(1/3)+SIN(A)/COS(A))*Z%
    • 70 TISK "Z%=";Z%; "Y="; Y 80 TISK R$
    • 90 KONEC

    Úkol 12.2

    Vypočítejte hodnotu funkce Y \u003d L 2 + V 1 a vytisknout (vytisknout) hodnoty počátečních dat a výsledků.

    Řešení

    Program pro výpočet funkcí Y:

    • 20 REM TISK VÝSTUP 30 TISK "ZADEJTE A, B"
    • 40 VSTUP A, B 50 U=A L 2+B L 2
    • 60 LPRINT "DATA:"," A=";A;" B=";B 70 LPRINT
    • 80 LPRINT "RESULT:"," Y=";Y 90 KONEC

    Příkaz na 30. řádku tohoto programu vypíše text na obrazovku a příkazy 60-80 na tiskárnu. Výpis na řádku 70 vytiskne prázdný řádek na kus papíru.

    Lineární programy s poli

    Pole v BASICu. Připomeňme si definici pole: pole nazývaná uspořádaná kolekce homogenních množství, z nichž každá je označena stejným názvem s různými celočíselnými indexy, měnícími se v pořadí.

    BASIC používá jedno- a dvourozměrná pole (v QBASICu jsou povolena i osmirozměrná). Stejně jako jednoduché proměnné mohou být různých typů: celé číslo, reálné, textové (řetězcové) atd.

    Pozornost! V BASICu nejsou žádné operace pro zpracování polí obecně, tzn. operace jako "zadejte pole P(1:99)", které jsme používali v kapitolách 8 a 9. Chcete-li provést operaci na poli, musíte vypsat operace provedené na každém z jeho prvků.

    Zvažte obecnou formu prvku pole v BASICu:

    • - prvek jednorozměrného pole: (Na);
    • - prvek dvourozměrného pole: (i, j),

    Kde - název pole se musí řídit stejnými pravidly jako název jednoduché proměnné;

    Komu - index(číslo) prvek jednorozměrného pole, to

    já,j- indexy prvek dvourozměrného pole (čísla řádku a sloupce, kde se nachází), i > 0, j > 0. V QBASICu můžete nastavit počáteční hodnoty k, i, j na 1. Indexy k , i, j může být reprezentováno libovolným aritmetickým výrazem . Při vyhodnocování výrazu představujícího index v QBASIC je výsledek zaokrouhlen na nejbližší celé číslo.

    Příklady zápisu prvků pole:

    P$(0), C2(101), X(46,5*K+l), T%(N/2, M).

    Ve schématu algoritmu by stejné prvky měly tato označení: P 0 ,

    C2yu1, X46,5?+i, T w /2>m-

    Pozornost! Pokud je v programu použito pole, pak musí být dříve deklarováno, tzn. Informace o typu a velikosti tohoto pole musí být oznámeny hostiteli pomocí příkazu DIM.

    Příklad: DIM příkaz P$(6), i_iB% (4,8) hlásí přítomnost v programu

    textová pole P(0:6) a celé číslo B(0:4, 0:8).

    Na základě informací obsažených v příkazu DIM počítač přidělí (rezervuje) pro každé pole paměťovou oblast požadované velikosti.

    Celkový pohled na operátora DIM:

    V případě jednorozměrného pole:

    ZTLUMIT (d),

    V případě dvourozměrného pole:

    ZTLUMIT (p, w)

    kde DIM je jméno operátora (od slova rozměr - "dimenze"); - název pole; d, p, w- velikosti polí, tzn. d-číslo posledního prvku jednorozměrného pole; n(m)- číslo posledního řádku (posledního sloupce) dvourozměrného pole.

    Velikost pole je ve většině verzí BASICu (včetně QBASIC) vyjádřena jako celé číslo nebo celočíselná proměnná.

    Funkce vstupu operátora DIM:

    • 1) jeden příkaz DIM může deklarovat libovolný počet polí (viz příklad);
    • 2) příkaz DIM se doporučuje umístit na začátek programu;
    • 3) neměli byste v programu používat jednoduchou proměnnou a pole se stejným názvem.

    Příklad: operátor DIM D% (2), A (2,3), K$ (3) říká:

    • pole D% - jednorozměrné celé číslo obsahující prvky D%(0), D%(1), D%(2);
    • pole K - jednorozměrný text, obsahuje prvky K$(0), k$(1), K$(2), K$(3);
    • pole A - dvourozměrné reálné, obsahuje následující prvky:

    Kompilace lineárních programů s poli. Nejprve si všimneme vlastností práce s poli v programu.

    1. Prvky pole přijímají hodnoty pomocí operátorů vstupu nebo přiřazení jako jednoduché proměnné. Při zadávání (výstupu) polí jsou v příkazech input (output) uvedeny názvy všech vstupních (výstupních) prvků pole.

    Příklad: vstupní a výstupní program pro pole P (1:3) může vypadat takto:

    • 20 DIM P(3)
    • 30 INPUT P(1), P(2), P(3)
    • 40 TISK P(1), P(2), P(3)
    • 50 KONEC
    • 2. Všechna pole lze rozdělit do dvou typů:
      • pole konstantní velikosti(např. P(1:7), B(1:4, 1:8)];
      • pole s proměnlivou velikostí[například A(1:&); C(1 :T, 1: d). V kapitolách 8 a 9 jsme použili oba typy, aniž bychom je rozlišovali.

    V některých verzích BASICu vám příkaz DIM neumožňuje deklarovat pole proměnné velikosti, takže jejich použití v programu vyžaduje určité triky. Ve verzích BASIC zvažovaných v příručce žádná taková omezení nejsou, je přípustné používat pole jakéhokoli druhu.

    Stačí si pamatovat: proměnné - velikosti polí musí být definovány před voláním příkazu DIM.

    Příklad:

    10 VSTUP M 20 DIM X(M)

    Lineární programy s poli se sestavují v souladu s dříve zvažovaným pravidlem pro sestavování nejjednodušších programů, které lze doplnit jedním bodem - "za operátorem REM by měl být v programu zapsán operátor DIM." Navíc je nutné vzít v úvahu právě uvedené informace o práci s poli.

    Nyní si ukážeme konstrukci uvažovaných programů na konkrétních příkladech. Nejprve se vraťme k problému 8.5. Schéma jeho algoritmu je znázorněno na Obr. 10.11. Nahrazením každého bloku tohoto obvodu příslušným příkazem podle pravidla uvedeného v 12.2 a přidáním příkazu DIM získáme níže uvedený program. Po přečtení tohoto programu doporučujeme, aby si čtenář vytvořil program pro řešení úlohy 10.7 a porovnal jej s níže uvedeným:

    • 10 REM SUM
    • 20 DIM B(3, 3), S(2)
    • 30 TISKNOUT "ZADEJTE MATRIX DO(3, 3)"
    • 4 0 INPUT B(1, 1), B(1, 2), B(1, 3)
    • 50 INPUT V(2, 1), V(2, 2), V(2, 3)
    • 60 INPUT B(3, 1), B(3, 2), B(3, 3)
    • 70 S(l) \u003d B (1, 1) + B (1, 2) + B (1, 3)
    • 80 S (2) = B (1, 3) + B (2, 3) + B (3, 3)
    • 90 TISKNOUT "S(1)="; S(l); "S(2)=";
    • S(2)
    • 100 KONEC
    • 10 REM SHIFT 20 DIM B(4)
    • 30 TISKNOUT "ZADEJTE POLE DO (4)"
    • 40 INPUT B(1), B(2),
    • 50 D=B(1)
    • 60 V(1)=V(2)
    • 70 V(2)=V(3)
    • 80 V(3)=V(4)
    • 90V(4)=D
    • 100 TISKNOUT "ARRIGE B=(";
    • 110 TISK B(1); AT 2);

    AT 3); AT 4); ")"

    Kontrolní otázky

    • 1. Který operátor v BASICu určuje typ a velikost pole?
    • 2. Jaké je označení prvků pole v BASICu? Jaká je nejmenší hodnota indexu prvku pole?

    Úkoly pro samostatné řešení

    • 2. Vypočítejte aritmetický průměr proměnných V, Si I.
    • 3. Dělníci Ivanov a Petrov vyrobili díly A a B na směnu, protože překročili normu. Určete procento přeplnění normy (norma - Z dílů za směnu).
    • 4. Určete rozdíl ve věku nevěst pro dva bratry Petyu a Dima. Jejich věk A A b respektive. Věk nevěsty se určuje podle vzorce

    kde (7 je věk ženicha.

    5. Vypočítejte hodnotu na:

    Kde

    Akceptovat srov 0; g, f 0.

    • 6. Vypočítejte objem a povrch válce o průměru O a výška N.
    • 7. Vypočítejte náklady na nábytkovou sestavu obsahující čtyři židle, dvě křesla a jeden stůl. Náklady na produkty, respektive A, B a C rublů.
    • 8. Určete aritmetický průměr prvků pole С(1:5).
    • 9. Určete součin součtů prvků každého řádku matice P (1:2, 1:3).
    • 10. Přeuspořádejte odpovídající prvky prvního a druhého řádku matice A (1:2, 1:2).
    • 11. Uspořádejte prvky pole R(1:6): 1. prvek a 6., 2. a 5., 3. a 4..

    Pokud jsou všechny příkazy v programu 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á výsledek z 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 si musíme jasně definovat, co je do něj potřeba zadat a co bychom jako výsledek měli dostat.

    V tomto případě:

    Počáteční údaj je jedno reálné číslo představující teplotu ve stupních Celsia,

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

    Před psaním programu otevřete Visual C++ IDE:

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

    1) Soubor > Nový...

    2) V otevřeném okně:

    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 myši 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;

    Klepně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 příkazů cin a cout.

    Jakýkoli program C++ se skládá z funkcí, z nichž jedna musí mít název main, což znamená, že s ní začíná provádění programu. Za závorkou ve složených závorkách ( ) se zapisuje tělo funkce, tzn. příkazy, které mají být provedeny.

    Jakákoli mezera při psaní programu má tvar:

    #zahrnout<…>

    #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 paměti RAM přidělit dostatek místa. To se provádí pomocí příkazu 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 příkazu jsou definovány dvě proměnné. Jeden, pro ukládání teploty ve stupních Fahrenheita, se nazývá fahr, druhý (ve stupních Celsia) se nazývá cels. Proměnné pojmenovává programátor na základě jejich účelu. Název se může skládat pouze z latinských písmen, číslic a podtržítek 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.

    Hlavní typy:

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

    plovák (double, long double) – real

    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, slouží tzv. prompt for input (operátor 3). Na obrazovce se zobrazí zadané v operátoru cout znakový řetězec a kurzor se přesune na další řádek. Pro přechod na další řádek použijte endl.

    V příkazu 4 se z klávesnice zadá do proměnné jediné číslo fahr. K tomu se používá standardní objekt. cin a operace extrahování (čtení) >>. Pokud potřebujete zadat několik hodnot, použijte řetězec operací >>.

    V operátoru 5, výraz zapsaný napravo od operace přiřazení(označeno znaménkem =) a výsledek je přiřazen k proměnné cels, to znamená, že je zapsán do paměti přidělené této proměnné. Od začátku Celý konstanta 5 bude dělena polibek konstanta 9, pak se výsledek této operace vynásobí výsledkem odečtení čísla 32 od proměnné fahr.

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

    Poslední příkaz (příkaz 7) tohoto programu je navržen tak, aby se z něj vrátil a přenesl 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 (spodní část obrazovky) by mělo zobrazit zprávu 0 chyb, 0 varování (0 chyb, 0 varování). Pokud jsou chyby, zkontrolujte originál.

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

    Po 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ích systémech MS DOS a Windows. Chcete-li to opravit, přidejte do programu funkci CharToOem (doplňky jsou pro přehlednost zvýrazněny červeně)

    #zahrnout

    #zahrnout

    char* RUS(konst char* text)

    CharToOem(text, buf);

    plovoucí jízdné, cels;

    cout<

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

    cout<

    cout<

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

    Jak vidíte, výsledek běhu 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. Oprava této chyby je jednoduchá – stačí napsat alespoň jednu z konstant jako reálné číslo, například:

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

    Lineární programy jsou programy, které se skládají z jednoduchých příkazů (operátorů).
    Jednoduché příkazy (jednoduché instrukce algoritmu) jsou příkazy, které při svém provádění nevyužívají podmínky. Jednoduché operátory zahrnují příkazy (operátory) pro přiřazení, vstup a výstup a 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 získat požadovanou hodnotu na určitém místě v paměti, obsahuje tento operátor téměř každý program. I/O operátory. Standardní procedury zadávání dat se používají k definování 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 určité hodnoty.
    Častěji je pro určení počátečních hodnot výhodnější použít příkaz input, spíše než příkaz přiřazení, protože pokud potřebujete použít program s jinými počáteční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 je řízení přeneseno na další příkaz algoritmu.
    V Pascalu vypadá procedura zadávání dat takto:
    READ (seznam vstupů);
    READLN (seznam vstupů).
    Při provádění procedur READ a READLN se program dostane do stavu čekání na zadání dat. Pokud je ve vstupním seznamu 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ž zadání každé hodnoty dokončíte klávesou Enter.
    Postup nebude ukončen, dokud nebudou zadány hodnoty pro všechny proměnné uvedené 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 první proměnnou v seznamu vstupů je proměnná souboru spojená s názvem 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 vypadají inferenční procedury takto:
    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 do souboru;
    výrazy, jejichž hodnota bude nejprve vypočtena a poté zobrazena na zařízení;
    se staly veličinami (číselné, znakové, řetězcové).
    Rozdíl mezi WRITE a WRITELN spočívá v tom, že výstup příkazu WRITE začíná v aktuálním umístění kurzoru na obrazovce monitoru a po ukončení výstupu zůstane kurzor na stejném řádku. Příkaz WRITELN vypíše 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 je výstupem soubor, pak první proměnnou v seznamu výstupů je proměnná souboru spojená s názvem 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í reálných dat můžete také určit počet desetinných míst ve zlomkové části, kterou chcete zobrazit.
    Příklad: napište (A: 10: 3, B: 8).
    Operátor volání pomocného algoritmu. Pascal implementuje podprogramy-procedury a podprogramy-funkce. Podprogram je volán svým jménem, ​​udávajícím aktuální parametry. Přitom místo aktuálních argumentů mohou být konkrétní hodnoty, názvy aktuálních proměnných, výrazy a místo výsledků pouze názvy aktuálních proměnných. V tomto případě se musí počet, typy a účel formálních a skutečných parametrů v odpovídajících seznamech parametrů shodovat.

    1.2 Stručně o lineárním programování.

    Co je lineární programování? Toto je jedna z prvních a nejdůkladněji prostudovaných sekcí matematického programování. Právě lineární programování byl úsek, ze kterého se začala vyvíjet samotná disciplína „matematické programování“. Pojem „programování“ v názvu disciplíny nemá nic společného s pojmem „programování (tedy psaní programů) pro počítače“, protože disciplína „lineární programování“ vznikla ještě před dobou, kdy byly počítače široce používány při řešení matematických, inženýrské problémy, ekonomické a jiné úkoly. Pojem „lineární programování“ vznikl v důsledku nepřesného překladu anglického „lineárního programování“. Jedním z významů slova „programování“ je vytváření plánů, plánování. Správný překlad „lineárního programování“ by tedy nebyl „lineární programování“, ale „lineární plánování“, které přesněji odráží obsah disciplíny. Nicméně termín lineární programování, nelineární programování atp. se staly běžnou součástí naší literatury.

    Lineární programování tedy vzniklo po druhé světové válce a začalo se rychle rozvíjet a přitahovalo pozornost matematiků, ekonomů a inženýrů díky možnosti širokého praktického použití a také matematické „harmonii“.
    Dá se říci, že lineární programování je použitelné pro konstrukci matematických modelů těch procesů, které mohou být založeny na hypotéze lineárního znázornění reálného světa: ekonomické problémy, problémy řízení a plánování, optimální umístění zařízení atd.

    Problémy lineárního programování se nazývají problémy, ve kterých jsou jak účelová funkce, tak i omezení ve formě rovností a nerovností lineární. Stručně, problém lineárního programování lze formulovat následovně: najděte vektor proměnných hodnot, které poskytují extrém lineární účelové funkce pod m omezeními ve formě lineárních rovností nebo nerovností.

    Lineární programování je nejpoužívanější optimalizační technika. Problémy lineárního programování zahrnují:

    racionální využívání surovin a materiálů; úkoly optimalizace řezání;

    · optimalizace výrobního programu podniků;

    Optimální umístění a koncentrace výroby;

    sestavení optimálního plánu dopravy, dopravního provozu;

    řízení výrobních zásob;

    a mnoho dalších spadajících do oblasti optimálního plánování.

    Podle amerických expertů tedy asi 75 % z celkového počtu používaných optimalizačních metod tvoří lineární programování. Asi čtvrtina počítačového času stráveného v posledních letech vědeckým výzkumem byla věnována řešení problémů lineárního programování a jejich četných modifikací.

    První výroky o problémech lineárního programování formuloval slavný sovětský matematik L.V.Kantorovič, který byl za tyto práce oceněn Nobelovou cenou za ekonomii.

    V současnosti je lineární programování jedním z nejčastěji používaných nástrojů matematické teorie optimálního rozhodování.

    Lineární programování je tedy věda o výzkumných metodách a hledání největších a nejmenších hodnot lineární funkce, na jejíž neznámé jsou uložena lineární omezení. Problémy lineárního programování tedy souvisejí s problémy pro podmíněný extrém funkce.


    1.3 Hlavní úkol lineárního programování

    Hlavní problém lineárního programování (OLPP) je nastaven následovně: Existuje řada proměnných . Je nutné najít jejich nezáporné hodnoty, které by vyhovovaly systému lineárních rovnic:

    {1.1}

    a navíc by minimalizovala lineární účelovou funkci (TF)

    Je zřejmé, že případ, kdy je potřeba digitální filtr otočit ne 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

    Přípustným řešením OLP je jakákoli množina proměnných, která vyhovuje rovnicím (1.1).

    Optimálním řešením je to z proveditelných řešení, ve kterém se digitální filtr stává minimem.

    V praxi jsou omezení v problému lineárního programování často dána ne rovnicemi, ale nerovnicemi. V tomto případě můžeme přistoupit k hlavnímu problému lineárního programování.

    Zvažte problém lineárního programování s omezeními nerovnosti, které mají tvar

    {1.2}

    a jsou lineárně nezávislé. To druhé znamená, že žádný z nich nemůže být reprezentován jako lineární kombinace ostatních. Je potřeba najít , které nerovnosti uspokojí a minimalizují

    Pojďme si představit rovnice:

    {1.3}

    Kde jsou další proměnné, které jsou také nezáporné.

    Máme tedy obecný problém lineárního programování – najít nezáporné , tak aby vyhovovaly soustavě rovnic (1.3) a otočily se na minimum .

    Koeficienty ve vzorci (1.3) jsou rovny nule.


    1.3. Konstrukce omezení a gradientu účelové funkce: 1.4. Oblastí proveditelných řešení je segment AB. 1.5. Bod A je optimální. Souřadnice bodu A: ; ; . 2. Řešení úlohy lineárního programování simplexovou metodou. přímý úkol. Problém lineárního programování pro jakýkoli vrchol v kompaktní formě lze znázornit takto: K získání použijeme algoritmus uvedený v ...



    Paprsky vycházející z jednoho bodu se nazývají mnohostěnný konvexní kužel s vrcholem v tomto bodě. 1.4 Matematické základy pro grafické řešení úlohy lineárního programování 1.4.1 Matematický aparát Pro další pochopení všeho je užitečné znát a představit si geometrickou interpretaci úloh lineárního programování, kterou lze uvést pro případy n = 2 an = ...

    Úkoly f1(x)=max=g1(x) – pro první podnik; - pro jiné podniky. Řešení problému optimálního rozdělení prostředků mezi podniky metodou dynamického programování Tabulka 12 Prostředky s, tis. Rostlina 1 2 3 4 G1(x) G2(x) G3(x) G4(x) 20 11 13 12 10 40 21 20 22 27 60 40 42 34 33 80 54 45 55 57 100 ... 62 62

    Pokud nastavíme aktuální základní proměnné v takové simplexní tabulce na Ai,0 a volné proměnné na nulu, pak dostaneme optimální řešení. Praxe aplikace simplexové metody ukázala, že počet iterací potřebných k vyřešení úlohy lineárního programování se obvykle pohybuje od 2 m do 3 m, i když u některých speciálně konstruovaných úloh se výpočty podle pravidel simplexové metody mění na přímé . ..

    Přečtěte si více: