Melyik programot nevezzük lineárisnak. Röviden a lineáris programozásról. Egyszerű programok készítése

Fentebb különféle gyakorlati problémákat vizsgáltunk, amelyek lineáris programozási sémára redukálhatók. E problémák egy részében a lineáris kényszerek egyenlőtlenség formáját öltötték, másokban egyenlőségek, másokban mindkettő.

Itt egy lineáris programozási problémát fogunk megvizsgálni egyenlőségi megszorításokkal – az úgynevezett alapvető lineáris programozási problémát (BLP).

A jövőben megmutatjuk, hogyan léphet át az egyenlőtlenségi kényszerekkel kapcsolatos problémából az OPLP-re, és vissza.

A lineáris programozás fő problémáját a következőképpen fogalmazzuk meg.

Számos változó létezik

Meg kell találni ezeknek a változóknak olyan nemnegatív értékeit, amelyek kielégítik a lineáris egyenletrendszert:

és ráadásul minimálisan fizetne lineáris függvény

Nyilvánvalóan az az eset, amikor egy lineáris függvényt nem minimumra, hanem maximumra kell fordítani, könnyen visszavezethető az előzőre, ha megváltoztatjuk a függvény előjelét, és inkább a függvényt vesszük figyelembe.

Egyezzünk meg abban, hogy bármely változóhalmazt az OLP elfogadható megoldásának nevezzük

kielégítő egyenlet (2.1).

Az optimális megoldást az egyiknek nevezzük elfogadható megoldások, amelynél a lineáris függvény (2.2) minimálisra fordul.

Az alapvető lineáris programozási problémának nem feltétlenül van megoldása.

Kiderülhet, hogy a (2.1) egyenletek ellentmondanak egymásnak; kiderülhet, hogy van megoldásuk, de nem a nem negatív értékek tartományában. Ekkor az OLP-nek nincs elfogadható megoldása. Végül kiderülhet, hogy az OLP-nek vannak elfogadható megoldásai, de ezek között nincs optimális: az L függvény a megengedett megoldások tartományában alulról korlátlan.

Később megismerkedünk az OPLP ilyen jellemzőire vonatkozó példákkal.

Először is vizsgáljuk meg az OLP elfogadható megoldásainak meglétét.

Ennek a kérdésnek a megoldása során kizárhatjuk az L lineáris függvényt, amelyet minimalizálni kell - a megvalósítható megoldások meglétét csak a (2.1) egyenletek határozzák meg.

Tehát legyen egy (2.1) egyenletrendszer. Vannak nem negatív értékek, amelyek kielégítik ezt a rendszert? Ezt a kérdést a matematika egy speciális ága - a lineáris algebra - vizsgálja.

Mutassuk be röviden a lineáris algebra néhány rendelkezését, anélkül, hogy a megfelelő tételek bizonyításain foglalkoznánk

Lineáris egyenletrendszer mátrixa

egy táblázat, amely az együtthatókból áll

Egy lineáris egyenletrendszer kiterjesztett mátrixa ugyanaz a mátrix, kiegészítve egy szabad tagok oszlopával:

A mátrix rangja egy nem nulla determináns legmagasabb rendje, amelyet úgy kaphatunk meg, ha törölünk néhány sort és oszlopot a mátrixból.

A lineáris algebrában bebizonyosodott, hogy ahhoz, hogy a (2.1) lineáris egyenletrendszer konzisztens legyen, szükséges és elegendő, hogy a rendszer mátrixának rangja egyenlő legyen a kiterjesztett mátrixának rangjával.

1. példa Adott egy három egyenletrendszer négy ismeretlennel:

Határozza meg, hogy ez a rendszer együttműködő-e?

Megoldás. Rendszermátrix:

Kiterjesztett mátrix:

Határozzuk meg az első mátrix rangját. Nem lehet nagyobb 3-nál (mivel a sorok száma 3). Hozzunk létre valamilyen determinánst úgy, hogy törölünk egy oszlopot a mátrixból, például az utolsót. Megkapjuk

Ezt a determinánst a jól ismert szabály szerint kiszámítva kapjuk:

Ez a determináns nem egyenlő nullával, ami azt jelenti, hogy a rendszermátrix rangja egyenlő 3-mal. Nyilvánvalóan a kiterjesztett mátrix rangja is egyenlő 3-mal, mivel ugyanaz a determináns összeállítható az elemekből a kiterjesztett mátrixból. A mátrixok sorainak egyenlőségéből az következik, hogy az egyenletrendszer konzisztens.

2. példa Vizsgálja meg egy két egyenletrendszer összeférhetőségét három ismeretlennel:

Megoldás. Kibővített rendszermátrix:

(bal oldala a rendszermátrix).

Határozzuk meg a rendszermátrix rangját az összes lehetséges másodrendű determináns összeállításával:

Tehát minden lehetséges másodrendű determináns, amely a rendszermátrix elemeiből áll, egyenlő nullával; Ez azt jelenti, hogy a rendszer ezen mátrixának rangja a

Keressük meg a kiterjesztett mátrix rangját. Döntő

Ezért a kiterjesztett mátrix rangja nem egyenlő a rendszermátrix rangjával: Grfg, ezért az egyenletrendszer inkonzisztens.

3. példa Vizsgálja meg egy három, négy ismeretlennel rendelkező egyenletrendszer konzisztenciáját:

Megoldás Kibővített rendszermátrix (a rendszermátrixszal együtt):

Keressük meg a rendszermátrix rangját. Vegyünk egy harmadrendű determinánst, amely elemeiből áll, például:

Ismeretes, hogy ha egy determináns bármely sora a másik két sor lineáris kombinációja, akkor a determináns egyenlő nullával. Esetünkben a harmadik sor az első kettő lineáris kombinációja: ahhoz, hogy megkapjuk, elegendő az első sort a duplával a második Ezért hozzáadni.

Könnyen ellenőrizhető, hogy a rendszermátrix elemeiből álló bármely harmadrendű determináns ugyanazzal a tulajdonsággal rendelkezik, ezért a rendszermátrix rangja a.

Mivel van egy nem nulla másodrendű determináns, pl.

akkor a rendszermátrix rangja egyenlő

Ugyanezzel az érveléssel biztosítjuk, hogy a kiterjesztett mátrix rangja egyenlő legyen kettővel: Ezért az egyenletrendszer kompatibilis

Vegye figyelembe, hogy a három egyenlet ezt a példát nem függetlenek: a harmadikat az első kettőből úgy kaphatjuk meg, hogy a másodikat megszorozzuk kettővel, és hozzáadjuk az elsőhöz. Ez azt jelenti, hogy a harmadik egyenlet az első kettő egyszerű következménye. Csak két független egyenlet van a rendszerben: ezt tükrözi, hogy a rendszermátrix rangja

Tehát, ha az OLP egyenlet-kényszerrendszere konzisztens, akkor a rendszer mátrixa és a kiterjesztett mátrixa azonos rangú.

Ezt az általános rangot a rendszer rangjának nevezik; nem jelent mást, mint a lineárisan független egyenletek számát a kiszabott kényszerek között.

Nyilvánvaló, hogy a rendszer rangja nem lehet nagyobb, mint az egyenletek száma:

Az is nyilvánvaló, hogy a rendszer rangja nem lehet nagyobb, mint a változók teljes száma:

Valójában a rendszermátrix rangja a mátrixelemekből álló determináns legmagasabb rendjeként van meghatározva; mivel sorainak száma egyenlő -vel, akkor ; mivel oszlopainak száma egyenlő -vel, akkor .

A lineáris programozási probléma felépítése jelentősen függ a kényszerrendszer rangjától (2.1).

Vizsgáljuk meg először azt az esetet, amikor a (2.1) rendszerben szereplő lineárisan független egyenletek száma megegyezik az n változók számával. Az OZLP egyenlet-megszorítási rendszere a következőképpen alakul:

Mivel az együtthatókból álló determináns,

nem egyenlő nullával. Az algebrából ismert, hogy ebben az esetben a (2.4) rendszernek egyedi megoldása van. Az érték megtalálásához elegendő a determináns oszlopát egy szabad kifejezések oszlopára cserélni, és elosztani vele.

Tehát, ha az OLP egyenlet-megszorítási rendszere egyedi megoldást kínál:

Ha ebben a megoldásban a mennyiségek legalább egyike negatív, az azt jelenti, hogy a kapott megoldás elfogadhatatlan, és ezért az OPLP-nek nincs megoldása.

Ha minden mennyiség nem negatív, akkor a talált megoldás elfogadható. Nyilvánvalóan optimális is (mert nincs más).

Nyilvánvalóan ez a triviális eset nem érdekelhet bennünket.

Ezért a jövőben csak azt az esetet fogjuk figyelembe venni, amikor a független egyenletek száma, amelyet a változóknak ki kell elégíteniük, maguknak a változóknak a száma. Aztán ha a rendszer konzisztens, végtelen sok megoldása van. Ebben az esetben tetszőleges értékeket rendelhetünk a változókhoz (az úgynevezett szabad változókhoz), és a fennmaradó változókat ezeken keresztül fejezzük ki (ezeket a változókat nevezzük alapnak).

Egy programot lineárisnak nevezünk, ha az összes utasítása egymás után, a megírásuk sorrendjében fut. Ez a program legegyszerűbb típusa.

Változók

A változó olyan érték, amely a program futása közben:

megváltoztatni a jelentését. A programban használt összes változót le kell írni a változóleírás részben, kezdve a var függvényszóval.

Minden változóhoz meg van adva a neve és típusa, például:

var szám: integer; x, y: valós; opció: char;

A változó neve azt a helyet adja meg a memóriában, ahol a változó értéke található. A nevet a programozó adja. Ennek tükröznie kell a tárolt érték jelentését, és könnyen felismerhetőnek kell lennie.

A változók típusát az adatábrázolás tartománya és szükséges pontossága alapján választjuk ki.

Deklaráláskor egy változóhoz kezdőértéket rendelhet, pl. inicializálni neki. Az inicializálás egy olyan érték beállítását jelenti, amelyet a program futása előtt hajtanak végre. Az inicializált változók ezt követően deklarálódnak kulcsszó const:

const szám: egész = 100; x: valós = 0,02; opció: char = "yu";

Alapértelmezés szerint a főprogramban definiált összes változó nullára van állítva.

Kifejezések

A kifejezés egy érték kiszámításának szabálya. A kifejezés magában foglalja -

operandusok, működési jelek egyesítik. Egy kifejezés operandusai lehetnek konstansok, változók és függvényhívások. A műveletek meghatározott sorrendben történnek, összhangban prioritások, mint a matematikában. A műveletek sorrendjének módosításához használja a zárójel, fészkelésük szintje gyakorlatilag korlátlan.

Egy kifejezés eredménye mindig egy bizonyos típusú érték, amelyet az operandusok típusai határoznak meg. A kifejezésben szereplő mennyiségeknek kell lenniük kompatibilis típusok.

• 1. Unáris művelet nem, unáris mínusz -, a @ címet véve.
• 2. Szorzás típusú műveletek:* / div mod és shl shr.
• 3. Összeadáshoz hasonló műveletek: + - vagy xor.
• 4. Relációs műveletek: = o = in.

Először a kifejezésben használt függvények kerülnek kiértékelésre

Példák kifejezésekre:

t + sin (x)/2 * x - az eredmény valós típusú; A

(x > 0) és (y

A program felépítése

A PASCAL program egy opcionális fejlécből, egy leírás részből és egy utasítás szakaszból áll:

program neve; (címsor) a leírások szakaszai kezdődnek az állítások szakasza vége. (* a program ponttal végződik *)

A program tartalmazhat megjegyzések, bebörtönözték fogszabályozó() vagy zárójelben, például (* *).

A program általános felépítése az ábrán látható. 2.1.

Az utasítások rész a program végrehajtható utasításait tartalmazza. A kezdő és vég kulcsszavak nem operátorok, hanem arra szolgálnak, hogy összevonják őket az ún összetett operátor vagy tömb. A blokk bárhol felírható a programban, ahol egy szabályos utasítás elfogadható.

A leírási szakaszok többféle típusúak: modulok, konstansok, típusok, változók, címkék, eljárások és függvények leírása.

A modul a programhoz kapcsolódó erőforrások (alprogramok, konstansok stb.) könyvtára.

Rizs. 2.1.

Ha van, akkor a modulleírás szakasz legyen az első. A leírás a uses kulcsszóval kezdődik, amit a programhoz kapcsolódó összes modul vesszővel elválasztott listája követ. saját készítésű, például: crt, graph, my_module;

A fennmaradó szakaszok száma és sorrendje tetszőleges, csak egy korlátozás van: minden értéket le kell írni a használat előtt. A leírás szakasz végét a következő szakasz eleje jelzi. Egy programnak több azonos típusú leírásrésze is lehet, de a programszerkezet egyszerűsítése érdekében ajánlatos az összes hasonló leírást egy szakaszba csoportosítani.

A Változóleírás részben meg kell határoznia a fő programban használt összes változót.

A konstans leírási részt azért használjuk, hogy a konstansok értékei helyett a neveket lehessen használni a programban. A konstans deklarációs szakasznak van egy másik felhasználási módja is: leírja azokat a változókat, amelyekhez értéket kell rendelni, mielőtt a program futhat:

állandó tömeg: valós = 61,5; n=10;

A címkeleírás szakasz a kulcsszó címkéjével kezdődik, amit a programban talált összes címke vesszővel elválasztott listája követ. A címke egy név vagy egy pozitív szám, amely nem haladja meg a 9999-et. A címke minden végrehajtható utasítás elé kerül, és kettősponttal van elválasztva attól. Példa a címke leírására: 1., 2. címke, hiba;

A címkék segítségével megszervezheti az átmenetet egy adott operátorra feltétlen ugrás operátor megy.

Beviteli-kimeneti eljárások Bármely program a kezdeti adatok bevitelekor és az eredmények kiadásakor kölcsönhatásba lép külső eszközök. Szabványos bemeneti és kimeneti eszközök halmaza, pl. billentyűzet és kijelző, ún konzol.

Billentyűzet bemenet. A következő eljárások vannak definiálva a billentyűzet beviteléhez: read és readln: read(list); readln[(lista)];

A vesszővel elválasztott változónevek listája zárójelben van feltüntetve. A szögletes zárójelek azt jelzik, hogy a lista esetleg nincs jelen. Például:

olvas(a, b, c); readln(y); readln;

FIGYELEM

Megadhat egész, valós, karakter és karakterlánc értékeket. A bemeneti értékeket tetszőleges számú szóköz karakterrel kell elválasztani (szóköz, tabulátor, soremelés).

Az egyes változók értékének megadása a következőképpen történik:

• ? a változó értéke határolók között elhelyezkedő karaktercsoportként van kiemelve;
• ? ezeket a szimbólumokat a változó típusának megfelelő belső reprezentációs formává alakítják;
• ? az érték a változónévvel azonosított memóriahelyre kerül.

Ezenkívül a readln eljárás az összes érték megadása után a forrásadatok következő sorába lép. A paraméterek nélküli readln eljárás egyszerűen megvárja az Enter billentyű lenyomását.

Karakterek és karakterláncok bevitelének jellemzői az szóköz karakterek nem különböznek az összes többitől, ezért nem lehetnek elválasztók.

Kimenet a képernyőre. Kiadáskor a fordított átalakítás történik: a belső ábrázolástól a képernyőn megjelenő karakterekig. Ebből a célból a nyelv szabványos eljárásokat határoz meg write és writeln: write (lista); writeln[(lista)];

Az írási eljárás a listában megadott értékeket jeleníti meg a képernyőn, és az írási eljárás ezen túlmenően a kurzort is a következő sorba mozgatja. A paraméterek nélküli írási eljárás egyszerűen a következő sorra mozgatja a kurzort.

Logikai, egész, valós, karakteres és karakterlánc típusú értékeket adhat ki. A lista nemcsak változóneveket, hanem kifejezéseket is tartalmazhat, valamint ezek speciális eseteit - konstansokat. Ezenkívül minden kimeneti értékhez beállíthatja formátum, például: writeln(a:4, b:6:2);

A változó neve után A A kettőspont a számára kiosztott pozíciók számát jelzi, amelyen belül az érték jobbra van igazítva. Mert b két formátum specifikáció van feltüntetve, ami azt jelenti, hogy ehhez a változóhoz csak hat pozíció van hozzárendelve, ebből kettő a tört részhez.

Lineáris egy olyan program, amely egy lineáris algoritmus rögzítése. Egy ilyen programban minden utasítás szigorúan szekvenciálisan hajtódik végre, azaz. mindegyik végrehajtása után (az END kivételével) a számítógép automatikusan folytatja a következő utasítás végrehajtását.

Egyszerű programok készítése

A legegyszerűbb lineáris programokat fogunk hívni, amelyek nem tartalmaznak tömböket. Az ilyen programok összeállítása megköveteli a korábban tárgyalt operátorok ismeretét, az algoritmus diagram blokkjainak való megfelelésük megértését, és ezt az egyszerű szabályt követi:

vegyük figyelembe az algoritmus diagram blokkjait (úgy gondoljuk, hogy adott) sorrendben, az elsőtől kezdve, és mindegyikhez írjuk a megfelelő operátort BASIC, azaz

blokkhoz Indul- REM utasítás a program nevével;

blokkhoz Írja be - bemeneti operátor;

blokkhoz Folyamat - hozzárendelés operátor;

blokkhoz Következtetés - kimeneti operátor;

blokkhoz Stop- END operátor.

Ez az egész szabály!

Most példákat adunk a vizsgált típusú konkrét programokra.

12.2 probléma

Számítsd ki egy derékszögű háromszög kerületét a lábainak hosszával!

12.3. probléma

Rendezd át az A és B mennyiségek értékét.

Megoldás 12.2 és 12.3 problémák. Ezeket a problémákat a 10. fejezet tárgyalja, így az 1. ábrán. A 12.2. ábra magyarázat nélkül mutatja a 10.2. feladat algoritmusának és programjának diagramját, a 10.2. 12.3 - ugyanez a 10.3. feladatnál.

ábrán. A 12.2 és 12.3 ábrákon a nyilak mutatják a programutasítások és az algoritmusdiagram blokkjainak megfelelőségét.

Mutassunk be programokat további két probléma megoldására. A 12.1. feladat programja különböző típusú mennyiségek használatát szemlélteti. A 12.2. feladathoz tartozó program bemutatja a nyomtatóeszközre történő adatkimenet szervezését.

Rizs. 12.2

Probléma 12.1

Számítsa ki az értékeket Ués Z a képlet szerint:

Ahol IN És IN - teljes mennyiségeket.

Megoldás

Kiindulási adatok: E%, V%, C, X, A(a).

Eredmény: Y,Z%.

A műveletek sorrendje itt nyilvánvaló, ezért azonnal írjuk meg a programot:

• 10 REM 1. FELADAT
• 20 NYOMTATJA MEG: "BEÍRÁS D%, B%, C, X, A"
• 30 BEMENET D%, B%, 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 NYOMTATÁS "Z%=";Z%; "Y="; Y 80 PRINT R$
• 90 VÉGE

12.2 probléma

Számítsa ki az Y = L 2 + függvény értékét! B 1és kinyomtatja (nyomtatóra írja ki) a kezdeti adatok és eredmények értékeit.

Megoldás

Függvényszámító program Y:

• 20 REM NYOMTATÁSI KIMENET 30 NYOMTATÁS "ENTER A, B"
• 40 BEMENET A, B 50 U=A L 2+V L 2
• 60 LPRINT "ADATOK:"," A=";A;" B=";B 70 LPRINT
• 80 LPRINT "EREDMÉNY:"," Y=";Y 90 VÉGE

A program 30. sorában lévő operátor szöveget jelenít meg a képernyőn, a 60-80 operátor pedig a nyomtatón. A 70-es vonal kezelője üres sort nyomtat egy papírra.

Lineáris programok tömbökkel

Tömbök a BASIC nyelven. Emlékezzünk vissza a tömb definíciójára: sor homogén mennyiségek rendezett gyűjteménye, mindegyiket ugyanazzal a névvel jelölik, különböző sorrendben változó egész számokkal.

A BASIC egy- és kétdimenziós tömböket használ (a QBASIC-ben még a nyolcdimenziós is megengedett). Ezek, mint az egyszerű változók, lehetnek különféle típusok: egész, valós, szöveg (karakterlánc) stb.

Figyelem! A BASIC-ben általában nincsenek műveletek a tömbök feldolgozására, pl. „Enter array P(1:99)” formájú műveletek, amelyeket a 8. és 9. fejezetben szoktunk használni. Egy tömbön végzett művelet végrehajtásához fel kell sorolni az egyes elemeivel végzett műveleteket.

Nézzük meg a BASIC tömbelemeinek általános megjelenését:

• - egydimenziós tömb eleme: (To);
• - elem kétdimenziós tömb: (i,j),

Ahol - a tömb nevének ugyanazokat a szabályokat kell követnie, mint egy egyszerű változó nevének;

- index egydimenziós tömb elemének (száma), k

én, j - indexek kétdimenziós tömb eleme (annak a sornak és oszlopnak a száma, amelynek metszéspontjában található), i > 0, j > 0. A QBASIC-ban beállíthatja a k, i, j kezdeti értékeit 1-hez. A k, i, j indexek bármilyen számtani kifejezéssel ábrázolhatók. A QBASIC indexet képviselő kifejezés kiértékelésekor az eredményt a rendszer a legközelebbi egész számra kerekíti.

Példák tömbelemek írására:

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

Az algoritmus diagramban ugyanazoknak az elemeknek a jelölése a következő: P 0,

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

Figyelem! Ha a program tömböt használ, akkor azt előzetesen deklarálni kell, pl. A számítógépet a DIM utasítás segítségével tájékoztatni kell ennek a tömbnek a típusáról és méretéről.

Példa: a DIM Р$(6), i_iB% (4,8) operátor jelzi a jelenlétet a programban

szöveg P(0:6) és egész B(0:4, 0:8) tömbök.

A DIM utasításban szereplő információk alapján a számítógép minden tömbhöz lefoglal (lefoglal) egy megfelelő méretű memóriaterületet.

A DIM operátor általános nézete:

Egydimenziós tömb esetén:

HOMÁLYOS d)

Kétdimenziós tömb esetén:

HOMÁLYOS (p, w)

ahol a DIM az operátor neve (a szóból méret - "dimenzió"); - tömbnév; d, p, w- tömbméretek, pl. d- egydimenziós tömb utolsó elemének száma; n(m)- egy kétdimenziós tömb utolsó sorának (utolsó oszlopának) száma.

A tömb méretét a BASIC legtöbb verziója (beleértve a QBASIC-ot is) egész számként vagy egész változóként fejezi ki.

A DIM operátor rögzítésének jellemzői:

• 1) egy DIM utasításban tetszőleges számú tömböt deklarálhat (lásd a példát);
• 2) a DIM utasítást ajánlatos a program elején elhelyezni;
• 3) ne használjon egyszerű változót és azonos nevű tömböt a programban.

Példa: operátor DIM D% (2), A (2,3), K$ (3) jelentések:

• D% tömb - D%(0), D%(1), D%(2) elemeket tartalmazó egydimenziós egész szám;
• A K tömb egy egydimenziós szövegtömb, K$(0), k$(1), K$(2), K$(3) elemeket tartalmaz;
• Az A tömb egy kétdimenziós valós tömb, amely a következő elemeket tartalmazza:

Lineáris programok készítése tömbökkel. Mindenekelőtt jegyezzük meg a programban a tömbökkel való munka jellemzőit.

1. A tömbelemekhez egyszerű változóként bemeneti vagy hozzárendelési operátorok segítségével rendelnek értékeket. Tömbök bevitelekor (kimeneti) az input (output) utasítások felsorolják a tömb összes bemeneti (kimeneti) elemének nevét.

Példa: A P (1:3) tömb bemeneti és kimeneti programja így nézhet ki:

• 20 DIM P(3)
• 30 BEMENET P(1), P(2), P(3)
• 40 NYOMTATÁS P(1), P(2), P(3)
• 50 VÉGE
• 2. Minden tömb két típusra osztható:
  • állandó méretű tömbök(például P(1:7), B(1:4, 1:8)];
  • változó méretű tömbök[például A(1:&); C(1 :T, 1: d). A 8. és 9. fejezetben mindkét típust használtuk anélkül, hogy különbséget tettünk közöttük.

A BASIC egyes verzióiban a DIM operátor nem teszi lehetővé változó méretű tömbök deklarálását, így ezek programban való felhasználása igényel néhány trükköt. A kézikönyvben tárgyalt BASIC verziókban nincs ilyen korlátozás, bármilyen típusú tömb használata megengedett.

Csak emlékezned kell: változók - a tömb méretét meg kell határozni a DIM operátor hívása előtt.

Példa:

10 BEMENET M 20 DIM X(M)

A tömbökkel rendelkező lineáris programokat a legegyszerűbb programok összeállításának korábban tárgyalt szabálya szerint állítják össze, amely kiegészíthető egy ponttal - „a REM operátor után a DIM operátort kell írni a programba”. Ezenkívül figyelembe kell venni az imént bemutatott információkat a tömbökkel végzett munkáról.

Most megmutatjuk a szóban forgó programok felépítését a segítségével konkrét példák. Először térjünk vissza a 8.5-ös feladathoz. Az algoritmus diagramja az ábrán látható. 10.11. Ennek az áramkörnek minden blokkját a megfelelő operátorra cserélve a 12.2-ben megadott szabály szerint, és hozzáadva a DIM operátort, az alábbi programot kapjuk. Miután megismerkedett ezzel a programmal, javasoljuk, hogy az olvasó saját maga készítsen programot a 10.7 probléma megoldására, és hasonlítsa össze az alábbival:

• 10 REM ÖSSZEG
• 20 DIM B(3, 3), S(2)
• 30 NYOMTATJA KI "ENTER MATER. IN(3, 3)"
• 4 0 BEMENET B(1, 1), B(1, 2), B(1, 3)
• 50 BEMENET V(2, 1), V(2, 2), V(2, 3)
• 60 BEMENET V(3, 1), V(3, 2), V(3, 3)
• 70 S(l) =B(1,1)+B(1,2)+B(1,3)
• 80 S (2) =B (1, 3) +B (2, 3) + B (3, 3)
• 90 NYOMTAT "S(1)="; S(1); "S(2)=";
• S (2)
• 100 VÉGE
• 10 REM SHIFT 20 DIM B(4)
• 30 NYOMTATÁS "ENTER ARRAY IN (4)"
• 40 BEMENET B(1), B(2),

• 50 D=B(1)
• 60 V(1)=V(2)
• 70 V(2)=V(3)
• 80V(3)=V(4)
• 90 V(4)=D
• 100 NYOMTATÁS "ARAY B=(";
• 110 NYOMTATÁS B(1); B(2);

B (3) ; B (4); ")"

Biztonsági kérdések

• 1. A BASIC melyik operátora jelzi egy tömb típusát és méretét?
• 2. Mi a tömbelemek jelölése a BASIC-ben? Milyen legkisebb érték tömbelem index?

Önállóan megoldandó problémák

• 2. Számítsa ki a változók számtani átlagát! V, C I.
• 3. Ivanov és Petrov munkások az A, illetve a B részt gyártották a műszak alatt, a normát meghaladóan. Határozza meg a norma túllépésének százalékos arányát (norma - Műszakonkénti részekből).
• 4. Határozza meg a menyasszony életkorának különbségét két testvér, Petya és Dima esetében! Az életkoruk AÉs b illetőleg. A menyasszony életkorát a képlet határozza meg

ahol (7 a vőlegény kora.

5. Számítsa ki az értéket y:

Ahol

Fogadjuk el kf 0; g,f 0.

• 6. Számítsa ki egy átmérőjű henger térfogatát és felületét! KÖRÜLBELÜLés magasság N.
• 7. Számítsa ki a négy széket, két fotelt és egy asztalt tartalmazó bútorkészlet költségét! A termékek költsége A, B és C dörzsölje.
• 8. Határozza meg a C(1:5) tömb elemeinek számtani középértékét!
• 9. Határozza meg a P(1:2, 1:3) mátrix egyes sorai elemeinek összegének szorzatát!
• 10. Rendezzük át az A(1:2, 1:2) mátrix első és második sorának megfelelő elemeit!
• 11. Rendezzük át az R(1: 6) tömb elemeit: 1. elem és 6., 2. és 5., 3. és 4.!

15. Analitikai módszerek. Lineáris programozási módszerek.

15.1. Analitikai módszerek

Az ember egész evolúciója során bizonyos cselekvések végrehajtása során úgy próbált viselkedni, hogy bizonyos értelemben a cselekvés eredményeként elért eredmény bizonyult a legjobbnak. Egyik pontról a másikra haladva a lehető legrövidebb utat kereste. Lakásépítéskor olyan geometriát keresett, amely elfogadható életkörülményeket biztosít a legkisebb üzemanyag-fogyasztás mellett. Hajóépítés közben igyekezett olyan formát adni nekik, amelyben a víz a legkisebb ellenállást nyújtja. A hasonló példák listája könnyen folytatható.

A problémák bizonyos értelemben legjobb megoldásait általában ún optimális. Jelenleg egyetlen többé-kevésbé összetett probléma sem oldható meg optimalizálási elvek alkalmazása nélkül. Az optimalizálási problémák felállítása és megoldása során két kérdés merül fel: mit és hogyan optimalizáljunk?

Az első kérdésre a választ a megoldandó probléma elmélyült tanulmányozása eredményeként kapjuk meg. Azonosítják azt a paramétert, amely meghatározza a felmerült probléma megoldásának tökéletességi fokát. Ezt a paramétert általában hívják cél funkció vagy minőségi kritérium. Ezután meghatározzuk a célfüggvényt meghatározó mennyiségek halmazát. Végül megfogalmazásra kerül minden korlát, amelyet a probléma megoldása során figyelembe kell venni. Ezt követően egy matematikai modell készül, amely a célfüggvény minden argumentumtól való analitikai függésének megállapításából és a problémához kapcsolódó kényszerek analitikus megfogalmazásából áll. Ezután elkezdjük keresni a választ a második kérdésre.

Tehát az alkalmazott probléma formalizálása eredményeként megállapítható, hogy a célfüggvény , ahol az X halmaz a korlátozások általánosítása, azt a megvalósítható megoldások halmazának nevezzük. Az optimalizálási probléma lényege, hogy ilyen megoldást keresünk az X halmazon - a megvalósítható megoldások halmazán
, amelynél a célfüggvény f eléri minimális vagy maximális értékét.

Az optimalizálási módszerek szerves része a lineáris programozás.

15.2. A lineáris programozás alapfogalmai

A hatékony termelésirányítás matematikai módszereinek első említése (1938) L. V. Kantorovich szovjet matematikusé. Egy évvel később, 1939-ben L. V. Kantorovich megjelentette „A termelés szervezésének és tervezésének matematikai módszerei” című munkáját, és gyakorlatilag alkalmazta a kapott eredményeket. A „lineáris programozás” kifejezést J. Danzig és T. Koopmans amerikai matematikusok vezették be a 40-es évek végén. J. Dantzig kidolgozta a szimplex módszer matematikai apparátusát lineáris programozási problémák megoldására (1951). A megoldáshoz a szimplex módszert használják széles körű lineáris programozási problémák, és még mindig az egyik fő módszer.

A lineáris programozás a matematikának egy olyan ága, amely a szélsőségek (maximum vagy minimum) megtalálására összpontosít a lineáris egyenletekkel leírt problémákban. Ezenkívül a lineáris egyenletek leírják mind a célfüggvényt, mind a bemeneti paramétereket (változókat), valamint a bemeneti paraméterekre vonatkozó korlátozások feltételeit. A lineáris programozási problémák szükséges feltétele az erőforrások (alapanyagok, anyagok, finanszírozás, gyártott termékek iránti kereslet stb.) korlátozásának kötelező megléte. Másoknak fontos feltétel a probléma megoldása az algoritmus megállítási kritériumának megválasztása, azaz a célfüggvénynek valamilyen értelemben optimálisnak kell lennie. A célfüggvény optimálisságát mennyiségileg kell kifejezni. Ha a célfüggvényt egy vagy két egyenlet ábrázolja, akkor a gyakorlatban az ilyen problémák meglehetősen könnyen megoldhatók. Az algoritmus leállítási kritériumának (vagy optimalitási feltételnek) a következő követelményeknek kell megfelelnie:

legyen egyedül az adott feladatra;

mennyiségi egységekben mérve;

lineárisan függ a bemeneti paraméterektől.

A fentiek alapján a lineáris programozási problémát általános formában megfogalmazhatjuk:

keresse meg a célfüggvény szélsőértékét

egyenlőség formájában történő korlátozások mellett:

(2.2)

egyenlőtlenségek formájában jelentkező korlátozások mellett:

(2.3)

és a bemeneti paraméterek nem-negativitásának feltételei:

Röviden a lineáris programozási probléma a következőképpen írható fel:

(2.5)

tekintettel arra

Ahol
- bemeneti változók;

A számok pozitívak, negatívak és egyenlők nullával.

Mátrix formában ez a probléma a következőképpen írható fel:

A lineáris programozási feladatok analitikusan és grafikusan is megoldhatók.

15.3. Kanonikus lineáris programozási probléma

, i=1,…,m,

, j=1,…,n.

A lineáris programozási problémák megoldásának főbb számítási módszereit kifejezetten a kanonikus feladatra fejlesztették ki.

15.4. Általános lineáris programozási probléma

Maximalizálni (minimalizálni) szükséges egy lineáris függvényt n változók.

korlátozások alatt

, én=1,…, k,

, én=1+ k,…, m,

, …,

Itt k≤ m, r≤ n. A standard problémát az általános probléma speciális eseteként kapjuk meg k= m, r= n; kanonikus – at k=0, r= n.

Példa.

Az édességgyár többféle édességet gyárt. Nevezzük őket "A", "B" és "C"-nek. Ismeretes, hogy tíz kilogramm „A” édesség értékesítése 90 rubel, „B” - 100 rubel és „C” - 160 rubel nyereséget ad. Cukorka tetszőleges mennyiségben gyártható (az értékesítés garantált), de az alapanyagok készletei korlátozottak. Meg kell határozni, hogy milyen édességet és hány tíz kilogrammot kell előállítani, hogy az értékesítésből származó teljes nyereség maximalizálódjon. Az egyes fajtákból 10 kg édesség előállításához szükséges alapanyag felhasználási arányokat az 1. táblázat tartalmazza.

1. táblázat Nyersanyag felhasználási arányok

gyártáshoz

A probléma közgazdasági és matematikai megfogalmazásának van formája

Keressen ilyen változó értékeket X=(x1, x2, x3), to

célfüggvény

feltételek-korlátozások mellett:

Az egyszerű parancsokból (operátorokból) álló programokat lineárisnak nevezzük.
Az egyszerű parancsok (az algoritmus egyszerű utasításai) olyan parancsok, amelyek végrehajtásuk során nem használnak feltételeket. A számhoz egyszerű operátorok tartalmazza a hozzárendelés, a bemenet és a kimenet parancsait (operátorait), egy segédalgoritmus (szubrutin) meghívását.

Hozzárendelés operátor. Beállítja vagy módosítja valamelyik változó aktuális értékét. Ez megváltoztatja az ehhez a változóhoz lefoglalt adott memóriaelem tartalmát. Mivel minden algoritmus célja a kívánt érték elérése egy bizonyos memóriahelyen, szinte minden program tartalmazza ezt az operátort. I/O operátorok. A szabványos adatbeviteli eljárások bizonyos változók kezdeti értékének meghatározására szolgálnak, és egy eljárásnévből és egy beviteli listából állnak, amely tartalmazza azon változók nevét, amelyek értékeit a billentyűzetről vagy egy fájlból kell bevinni, pl. A változók meghatározott értékeket kapnak.
A kezdeti értékek meghatározásához gyakrabban célszerűbb a bemeneti parancsot használni, mint a hozzárendelési parancsot, mert ha eltérő kezdőadatokkal kell használni a programot, akkor nem kell módosítani a program szövegét.
Ha az algoritmus rekord tartalmaz bemeneti parancsot, akkor annak végrehajtása megszakad, és a vezérlés átkerül egy olyan programhoz, amely képes adatokat bevinni. Az adatok megadása után a vezérlés átkerül az algoritmus következő parancsára.
Pascalban az adatbeviteli eljárás így néz ki:
READ(beviteli lista);
READLN (beviteli lista).
A READ és READLN eljárások végrehajtásakor a program adatbevitelre váró állapotba lép. Ha a beviteli listában több változót adunk meg, akkor azokat egy sorba, egymástól szóközzel elválasztva, vagy külön sorban (egy oszlopban) lehet megadni, az egyes értékek megadását az Enter billentyűvel kiegészítve.
Az eljárás mindaddig nem fejeződik be, amíg a listában szereplő összes változóhoz meg nem adjuk az értékeket. A megadott értékek típusának meg kell egyeznie a megfelelő változóéval.
A READLN utasítás abban különbözik a READ utasítástól, hogy a szükséges adatmennyiség megadása után a kurzor a következő sorra lép.
Ha az adatbevitel a billentyűzetről történik, akkor a beviteli lista változók listája, pl. vesszővel elválasztott változónevek sorozata. Ha a bemenet fájlból származik, akkor a bemeneti lista első változója a fájlváltozó, amely a valódi fájl nevéhez van társítva.
A számítási eredmények szabványos kimeneti eljárásai az értékek képernyőn, nyomtatón vagy fájlon való megjelenítésére szolgálnak. Pascalban a következtetési eljárások így néznek ki:
WRITE(kimeneti lista);
WRITELN (kimeneti lista).
A kimeneti elemek listája sokkal szélesebb, mint a bemeneti eljárásokban. Ez a következőket foglalhatja magában:
azon mennyiségek azonosítói, amelyek értéke a megfelelő eszközre vagy fájlra kerül kiadásra;
kifejezések, amelyek értékeit először kiszámítja, majd kiadja az eszközre;
értékekké váltak (numerikus, szimbolikus, karakterlánc).
A WRITE és a WRITELN közötti különbség az, hogy a WRITE utasítás kimenete a kurzor aktuális helyétől kezdődik a monitor képernyőjén, és a kurzor ugyanazon a sorban marad a kimenet befejezése után. A WRITELN utasítás kiírja az értékeket az aktuális pozícióból, majd a kurzor a következő sorra lép. A WRITELN utasítással kimeneti lista nélkül is áthelyezheti a kurzort egy új sorba.
Ha a kimenet a monitor képernyőjére érkezik, akkor a kimeneti lista változók listája, vagy változónevek, konstansok vagy kifejezések sorozata, vesszővel elválasztva. Ha a kimenet egy fájl, akkor a kimeneti lista első változója a fájlváltozó, amely a valódi fájl nevéhez tartozik.
A kimeneti parancsban a kimeneti lista elem után megadhatjuk a kimeneti formátumot, kettősponttal elválasztva, pl. a képernyő szélessége, amelyen az értékek megjelennek. Valós adatok megjelenítésekor megadható a megjeleníteni kívánt törtrész tizedesjegyeinek száma is.
Példa: write(A: 10: 3, B: 8).
Operátor egy segédalgoritmus hívásához. A Pascal eljárás- és függvény-szubrutinokat valósít meg. Egy szubrutint a neve alapján hívnak meg, jelezve az aktuális paramétereket. Ebben az esetben a tényleges argumentumok helyett konkrét értékek, a tényleges változók nevei, kifejezések, az eredmények helyett pedig csak a tényleges változók nevei lehetnek. Ebben az esetben a megfelelő paraméterlistában szereplő formális és tényleges paraméterek számának, típusának és céljának meg kell egyeznie.