| ALLO și SAMO ...
ALLO, SAMO Limbaj, Sistem Avansat pentru Modelare și Optimizare Lineară, 15 Ian 2021, ISBN 978-973-0-33551-4
ALLO (Algebraic Language for Linear
Optimisation) este un limbaj de
modelare matematică lineară
singurul limbaj de
acest gen din țară. Limbajul împreună cu translatorul său au fost finalizate
și implementate în 1995 de către Institutul Național de
Cercetare-Dezvoltare în Informatică
(ICI) în cadrul Laboratorului de Modelare și Optimizare
condus de către Dr. ing., mat., CP1,
Neculai Andrei.
ALLO permite modelarea cu usurință a unor probleme de modelare lineară într-o formă apropiată de descrierea algebrică. Mult mai important este faptul că permite realizarea de prototipuri legate de probleme practice sau teoretice. Un prototip împreună cu datele concrete instanțiază un model concret. Translatorul instanțiază prototipul într-un model și-l translatează în forma echivalenta MPS ( MPS wiki) care a fost zeci de ani standardul fișierului de intrare recunoscut de orice optimizator consacrat. Acesta rezolvă problema și furnizează o soluție unică dacă există. Putem spune că, la timpul realizării sale, ALLO era în primele zece limbaje similare din lume, majoritatea fiind realizate comercial în câteva țări cu tradiție în cercetare din orice domeniu strategic. Istoric Ideea realizării limbajului ALLO au avut-o doi matematicieni cercetători din ICI specialiști în probleme de optimizare matematică. Este vorba de Dr. mat., CP1, Cornel Resteanu și Dr. ing., mat., CP1, Neculai Andrei care n-a renunțat la proiect și a depășit toate obstacolele printr-o voință de fier. La început aceștia au apelat (prin contract) la catedra de Informatică din cadrul Facultății de Matematic și Informatică, Universitatea București. După un timp au primit o lucrare tipărită. După 1990 a plecat în Germania pentru un stagiu de bursier Humboldt. A chemat lângă el pe Mat. Mircea Bărbulescu, salariat în ICI. Acolo au realizat o primă formă a gramaticii limbajului ALLO după care Mircea Bărbulescu a realizat-o în limbajul Borland C. Este vorba de analizorul lexical-sintactic fără partea expresiei din cauza timpului scurt și a plecării sale pe post de asistent la Fac. Matematică, Universitatea București și de aici în Canada. Rămas singur la întoarcerea din Germania, Neculai Andrei a cooptat pentru proiect pe Mat., CP3, Gheorghe Borcan cu masterat în Limbaje Formale și Tehnici de Construcție Compilatoare (Fac. Mat., Univ. București ) care a avut o contribuție importantă pentru reluarea și continuarea proiectului LPTR. Deoarece la acel moment cei doi nu dispuneau de un PC s-au apucat să proiecteze faza doua a translatorului. Mai întâi a definitivat forma (o poloneză inversă și mixată) ce trebuia produsă de către analizorul lexical-sintactic inclusiv pentru zona expresiei neprogramată încă. După aceea au proiectat procesul de translatare model în format MPS. Între timp Neculai Andrei a primit un PC de la fundația Humboldt din Germania, iar Mircea Bărbulescu a recomandat pe un fost student la Informatică (Fac. Matematică, Univ. București), anume pe Cristian Dubălaru care a fost angajat în ICI. Acesta a realizat programele limbajul Borland C referitoare la expresie și a completat ieșirea din pasul unu, apoi a plecat din ICI din cauza salariului. Pentru a grăbi lucrurile, pasul doi a fost realizat de către Gheorghe Borcan în FORTRAN. Tot acesta s-a ocupat și de ceva corecții de erori din pasul unu. Astfel în 1995 am avut prima versiune a translatorului ALLO. În această perioadă Gheorghe Borcan s-a ocupat de adaptarea unui solver vechi (primit cu peste zece ani în urmă de N.A., compilat și executat pe calculatorul FELIX C256 cu sistem operare francez SIRIS, vezi istoria calculatoarelor românești) și compilarea (cu unicul compilator de care dispunea) pentru a fi executabil (numit acum Dsolver) pe PC cu sistemul de operare WINDOWS 3.1. De asemenea a recompilat și rutinele (circa 100) din pachetul MINOS (primit de N.A. de la Univ. Stanford, California, SUA) Pachetul a fost creat, compilat, taskbildat și executat pe alt sistem de operare decât al nostru. La prima compilare a constatat multiple erori ce păreau insurmontabile căci a modifica rutinele ar fi fost nu numai o muncă serioasă dar și riscantă. Până la urmă a găsit o soluție corectă care a permis teste (efectuate de N.A.) cu probleme nelineare căci pachetul avea și această facilitate pe lângă cea legată de probleme lineare. Mai mult a finalizat sistemul SAMO (Sistem Avansat de Modelare și Optimizare, sistem început de Cristian Dubălaru în Visual Basic) care a integrat un Editor de texte, Translatorul ALLO, Optimizatorul Dsolver precum și un vizualizor de soluție. Există câteva astfel de sisteme comerciale în lume. Rezolvarea unei probleme de optimizare lineară era mult ușurată de SAMO. Astfel am putut testa translatorul pe cîteva sute de modele. Cel mai interesant prototip model a fost legat de CETSUD București. Un model instanțiat CETSUD are mii de variabile și mii de restricții! La acest prototip a avut o contribuție decisivă Prof. Univ. Politehnica București, Alexandru Badea specialist în centrale termo-electrice. Acesta ne-a furnizat (într-o primă aproximare lineară deși modelul mai precis este neliniar) ecuațiile cazanelor, turbinelor, bileror,etc. precum și ecuațiile de cost/profit centrală. Este o premieră în țară de a avea acces la o viziune globală asupra funcționării unei astfel de centrale. Acest fapt n-ar fi fost posibil fără existența translatorului ALLO, a Dsolverului și mai mult a lui SAMO. După circa trei ani de la primele teste și după sute de experimente de modelare, limbajul ALLO a ajuns la versiunea unu prin refacerea sintaxei și semanticii. În limbaj au fost introduse 17 funcții implicite care măresc considerabil forța de exprimare a limbajului. Versiunea 1 a limbajului ALLO a fost realizată în întregime de către Gheorghe Borcan care a implementat și translatorul format din cele două componente Pas1(în C) și Pas2(în Fortran). Aici o listă (RO)/ listă (EN) cu limbaje de programare pe categorii. Gramatica limbajului ALLO a fost adusă la forma care îndeplinește criteriul LL1 SAMO - Sistem Avansat pentru Modelare si Optimizare Un
IDE
(An integrated development environment) pentru sistemul SAMO
a fost început de către mat. Cristian Dubălaru în Visual
Basic la indicațiile lui CP3., Mat. Gheorghe Borcan care l-a finalizat
și cu ajutorul căruia a testat sute de modele. Acesta are integrat un Editor de texte (pentru ușurarea scrierii de modele și corectării acestora în proces de compilare,etc.) Translatorul ALLO, Optimizatorul Dsolver precum și un vizualizor de soluție. Rezolvarea unei probleme de optimizare lineară este mult ușurată de către SAMO. Astfel s-a putut testa translatorul pe câteva sute de modele. Ca și translatorul ALLO credem că este primul sistem de acest fel realizat la noi în țara ca urmare a unor eforturi deosebite în vremuri când asemenea obiective sunt desconsiderate de către mulți decidenți din domeniul IT care s-au aflat din păcate în funcții care-i depășeau. Funcțiuni O imagine SAMO cu fișierul prototipului CETSUD în proces de lucru
Sistem de operare
Translatorul ALLO și sistemul SAMO au supraviețuit pe sistemele de operare WINDOWS 3.1, WINDOWS 95 și WINDOWS Vista. La trecerea pe fiecare din aceste sisteme a fost necesară recompilarea și refacerea taskurilor pornind de la compilatoare compatibile pe aceste sisteme. Având în vedere sursele în Borland C, Fortran și Visual Basic trecerea n-a fost ușoară. Compilatoarele necesare trebuiau schimbate pentru a fi compatibile pe sistemul respectiv. Din acest motiv trebuiau refăcute unele componente sursă. Portabilitatea programelor pe diverse sisteme de operare este încă o problemă nerezolvată. Sisteme sau Limbaje de Modelare Matematică 1.
AIMMS - Advanced Interactive
Multidimensional Modeling System. În AIMMS se pot modela probleme: Lineare, Quadratice,
Nelineare,Mixate cu întregi și altele. Dispune de un IDE complex Pentru soluționare AIMMS lansează
multiple solvere. Exemplu de problemă modelată în ALLO O companie cu mai multe centre de producție/stocare livrează produsele unor piețe/clienți conform cu cerințele acestora. Pentru satisfacerea cererii unei piețe, compania poate livra produse din mai multe centre. Se cunosc costurile de transport, cererea piețelor precum și capacitatea de producție (sau stocare) a centrelor. Pentru simplificare produsele sunt date în unități convenționale deoarece aici sunt semnificative costurile de transport și capacitatea centrelor. Se cere satisfacerea clienților precum și minimizarea costurilor de transport.
MODEL Transport
/*-----------------------------------------------------------------------*/
/* Conditia nu este necesara fiind suplinita de restrictii */
OBJECTIVES
CONSTRAINTS
/* Cantitatea livrata tuturor pietelor din din fiecare centru trebuie sa
*/
/* Cantitatea livrata unei piete din toate centrele */ END Fisierul cu date de instantiere prototip Transport
/* translpl.dat-------------------------------------------*/
/* nrcp */ 10 Extras din MPSul generat de translatorul ALLO care este intrare în Dsolver
NAME Transport
Extras din raportul optimizatorului
după rezolvare
...omis iterațiile până la o solutia optimă
Optimal Solution found in 15 iterations
... omis despre satisfacerea restrictiilor in soluția optimă Extras cu variabilele liniarizate și nenule din soluția optimă
NoVar Name AT Value
Să ne reamintim că variabilele sunt acestea:
x[j,k] Cantitatea transportată din centrul j la
piata k
Se observă că din centrul 9 nu se livrează nici un produs către piețe. Ca să livrăm și de aici (pentru a nu se ajunge la blocaj activitate) ar trebui să punem încă o condiție în model. Spre exemplu vrem ca suma livrărilor din orice centru să fie mai mare decât o anumită parte din capacitatea Iată o variantă care schimbă situația. Dar de regulă funcția obiectiv va avea o valoare mai mare decât cea anterioară: rcapnz[cp] IS FOR[c IN cp] rcapnz[c]:= SUM[m IN mk] (X(c,m)) >= 0.7*A[c] Valoarea funcției obiectiv este 13495.68
Limbajul ALLO este construit pe baza unui set de caractere numit alfabetul limbajului. Pe baza alfabetului se construiesc( conform unor reguli lexicale ) tokenii sau cuvintele limbajului care sunt elemente ale mulțimii numite vocabular al limbajului. Unele cuvinte vor fi utilizate frecvent de către orice utilizator al limbajului. Acestea formează setul de cuvinte rezervate sau setul de cuvinte cheie cu un rol deosebit în construcția sintactică și semantică a ceea ce numim program sursă sau prototip/model sursă. Celelate cuvinte nu sunt cunoscute, ci sunt construite de către cei ce utilizeaza acest limbaj. Vocabularul, ar fi o mulțime infinită dar sunt restricții de limitare lungime cuvânt. Cu alfabetul și cu vocabularul se pot crea asamblaje complexe din componența instrucțiunilor și în final vom putea crea asamblajul cu cea mai ridicată încarcătură semantică numit program. Desigur cu respectarea unor reguli sintactice și semantice căci alfel nu va fi validat de către un asamblor, translator, interpretor sau compilator. Am văzut mai sus o structură globală
a unui program ALLO. Privit doar prin prisma alfabetului un program este
un șir finit de caractere recunoscut de către translator. Acest
șir poate fi rezultatul unui mixaj de șiruri fișier decis
de fisierul principal care face referire la celelalte. Totul este coordonat de către translatorul ALLO. Dăm mai jos alfabetul
sau setul de caractere recunoscut de către limbajul ALLO:
Observatie 1. Operatorul IN poate fi scris în orice combinație de litere Mari/Mici după cum dorește modelatorul. Aceasta este valabilă și pentru operatorul IS dar și pentru orice cuvânt rezervat. 2. Diferența dintre operatorul := și operatorul IS constă în aceea că primul se referă la definiția unei componente de masiv (cu rol de nume funcție obiectiv, nume restricție) pe când IS anunță începutul definiției unei variabile auxiliare de tip masiv sau a condiției de validare a unei variabile auxiliare ( scalară sau de tip masiv), anunță condiția de mărginire (bounds) a unei variabile model ( scalară sau de tip masiv), și în cele din urmă anunță începutul corpului de definire a unei funcții obiectiv sau restricții ( scalară sau de tip masiv). 3. Mulțimea formată din caracterele <CR> <SP> <TAB> , : ; { } [ ] ( ) + - * / < = > este o mulțime specială ale cărei elemente semnalează ănceputul sau sfârșitul unor cuvinte / tokeni recunoscuți de analizorul lexical al translatorului ALLO. Tokenii respectivi fac parte din vocabularul limbajului numai dacă respectă regulile de construcție impuse de limbaj. Elementele limbajului ALLO Pe baza alfabetului și a vocabularului se construiesc noi cuvinte de vocabular sau asamblaje din ce în ce mai complexe pâna la asamblajul cu maximă încarcatură sintactică și semantică numit program sau model. Elementele de bază ale limbajului ALLO sunt :
În continuare vom detalia fiecare din elementele de bază din construcția unui model prezentate mai sus. Comentarii Comentariile sunt elemente deosebit de utile în orice limbaj. În ALLO comentariile sunt acceptate oriunde în fișierele sursă ce țin de un prototip / model. Un comentariu ALLO este o secvență de caractere din setul ALLO care este imbricată de început și sfârșit comentariu . După ce comentariul este deschis analizorul lexical scanează șirul până întâlnește secventa de închidere. Dacă este nevoie se depăsește secvența <CR><LF> de sfârșit linie sursă când un comentariu se continuă pe mai multe linii. Acest fapt este util nu numai în explicarea modelului dar și pentru o posibilă depanare. Comentariile și zonele de spații sunt elemente neproductive cu rol de design și de explicare model sursa. Nume Numele este un element esențial în construcția oricărui prototip / model ALLO fiind un element de vocabular, un token identificabil de către analizorul lexical ALLO. Numele se formează cu ajutorul literelor, cifrelor și caracterului underscore care leagă două sau mai multe componente cărora utilizatorul le atribuie un înțeles. Desigur nimeni nu ne împiedecă să lipim aceste nume și să nu utilizăm această legătură. Depinde de preferință,. Totuși folosirea caracterului este deseori utilă căci pune în evidență componentele. Un nume valid începe numai cu o literă care poate să fie urmată de : o literă, o cifră, caracterul de legatură underscore. Lungimea trebuie să nu depășească maximul permis caz rezolvat prin trunchere. Precizări de metalimbajul folosit în definirea sintaxei ALLO ::= ne spune ca elementul din stânga sa se construiește după cum urmează (sau este prin definiție); | este separator de elementele listei. Orice element poate participa la construcția asamblajului complex respectiv; Spațiul dintre două elemente de metalimbaj sau dintre un element de metalimbaj și un atom (ex. caracterul de link _ ) înseamnă operația de concatenare dintre două șiruri. Un element de metalimbaj semnifică o clasă / mulțime de posibile asamblaje (siruri pe alfabet) construite cu regulile acelui element. lambda este simbolul elementului nul față de operația de concatenare caractere sau șiruri de caractere. Este un șir vid care n-are nici un caracter fiind de lungime zero. Sintaxa nume ::= litera | nume litera
| nume cifra | nume _ Exemple : nrfprod, fprod, ump, xprod, cost_prod, st_cost, per_1 Cuvinte cheie ALLO
Precizari Cuvintele din tabelul de mai sus sunt rezervate. Pot fi utilizate și prin scriere combinată litere mari/mici după cum dorește utilizatorul. Toate (inclusiv combinațiile rezultate) nu mai pot fi utilizate ca nume de variabilă. Cele din intervalul [17,33] sunt nume de funcții implicite care trebuie să fie apelate conform definiției lor cu respectarea numărului de argumente și a tipului cerut.
Constantele sunt elemente
necesare oricărui limbaj de
programare sau specializat. În
limbajul ALLO ele sunt utilizate
fie direct în construcția unui
model fie indirect prin faptul
că servesc la inițializarea unor
variabile auxiliare care sunt
utilizate în construcția
respectivă. ALLO permite
construirea și utilizarea
următoarelor tipuri de constante
: Constante Întregi O constantă întreagă este o secvență de cifre zecimale în fața căreia poate apare semnul + sau - . ALLO permite constante întregi în domeniul de valori pe simplu cuvânt, adică [ -32768 , + 32767 ]. Pentru valori mai mari sunt constante reale sau variabile întregi care pot fi asignate cu expresia dorită. Sintaxa
Exemple: 3457, -15481, +12 , -32768, +32767 Constante Reale Constantele reale sunt compuse din semn, parte întreagă, punct zecimal, parte fracțională urmată eventual de un exponent. Acesta este compus din litera E sau e urmat de un număr întreg cu sau fără semn. Domeniul aproximativ de valori al unei astfel de constante este domeniul negativ [ - 3.4028235E+38, - 1.1754944E-38 ] plus domeniul pozitiv [ 1.1754944E-38 , 3.4028235E+38 ] și desigur valoarea 0 ca element obligatoriu în operații. Sintaxa Observatii. 1. p_int poate lipsi când este prezentă p_frac și invers. dar nu pot lipsi simultan. 2. După cum se vede exponent nu este obligatoriu fapt semnalat prezența lui lambda. 3. exponent se încadrează relativ în limita a două cifre zecimale utile. Exemple : .517, -32.7564, +3. 0.342E-15, -2.51e+9, -3.4028235E+38 Constante domeniu Sunt elemente ale limbajului
ALLO ce definesc un interval pe
axa reală sau în mulțimea
numerelor întregi. Ele conțin
cele două mărimi care definesc
un asemenea interval : marginea
inferioară și marginea
superioară. Aceste mărimi sunt
închise între paranteze drepte
și sunt separate de o virgula.
Mărimile pot fi constante numere
reale sau întregi dar pot fi
și expresii aritmetice calculabile
în acel punct în care apare și
este utilizată constanta domeniu
ca mărime de
initializare a unei variabile
domeniu sau ca un domeniu adhoc.
În ALLO sunt permise constante domeniu care nu pot fi evaluate decât într-un anumit context și a căror valoare poate fi diferită in funcție de valoarea unor indici de ciclare care participă în expresiile de margini. Este cazul așa numitelor constante domeniu dinamice care suportă reevaluarea lor de fiecare dată când se inițializează ciclul de care ține. Sintaxa const_domeniu ::= [ expr_aritm , expr_aritm ] Exemple : [ -2, 17], [ 34.5, 70.18], [ m/2, 3*n ] , [ a+3.2*(k+1), b+18.65 ] Observație. Variabile auxiliare întregi m și n trebuie definite anterior pentru ca expresiile să fie calculabile în momentul întâlnirii acestui domeniu. La fel a și b sunt variabile auxiliare ale căror valori se cunosc deja iar k este un indice de ciclare într-o clauză FOR în al cărui bloc cu instrucțiuni apare această constantă de tip domeniu, deci în acest ciclu expresiile sunt calculabile. Șiruri de caractere Sunt compuse din unul sau mai multe caractere ale alfabetului ALLO delimitate de o pereche de ghilimele duble care astfel nu mai pot fi incluse în nici un sir. Șirurile sunt utilizate în definirea specificației externe de identificare fișier sub sistemul de operare DOS. O asemenea specificație poate să conțină numai numele și tipul despărțite de punct, caz în care fișierul este căutat în directorul de lucru al translatorului, sau poate conține și path-ul respectiv caz în care este căutat în concordanță cu acesta. Sintaxa sir ::= " secv_car " Exemple : "e:\lpmodels\allo\prod.dat" "cetsud.dat" "twood.dat" Masivele sunt creații speciale ale unui limbaj de programare și nu numai. Ele sunt formate din unul sau mai multe celule / obiecte identice organizate după o regulă dimensională cunoscută care permite identificarea locului ocupat (în această structură) de către fiecare obiect. Masivele sunt caracterizate printr-o listă de dimensiuni, prin spațiul alocat fiecărei celule și prin regula de alocare sau de regăsire a fiecărei celule. Masivele unidimensionale sunt cunoscute sub denumirea de vectori, cele cu două dimensiuni sub numele matrici. Masivele cu trei dimensiuni sunt numite masive tridimensionale, cu n dimensiuni masive n-dimensionale. Sintaxa Exemple : storcost [rmat] ump [rmat,fprod] xsmat[rmat,perpext] Lista dimensiuni După cum am spus un masiv este marcat de o listă de dimensiuni care-i definesc dimensiunea, forma sa. O dimensiune a unui masiv este reprezentată de un domeniu de întregi care are un număr de elemente dat de diferența dintre marginea superioară și marginea inferioară după care trebuie adăugat unu. Acest număr participă la calculul numărului total de elemente al tabloului ca fiind produsul tuturor numerelor asociate dimensiunilor. O dimensiune clasică reprezintă un domeniu [1, n] astfel că numărul de elemente reprezentat de aceasta dimensiune este n-1+1 = n, chiar marginea superioara. Un domeniu întreg oarecare și unidimensional poate fi pus în corespondență biunivocă cu un astfel de domeniu clasic. Sintaxa l_dim ::= dim | dim , l_dim Exemple de listă dimensiuni: [1,10] , rmat, / rmat, fprod / (fără cele două /) Observație [1,10] este o constanta de tip domeniu, celelalte sunt construite prin nume de domenii care ar trebui să fie definite înainte de utilizarea lor în alt loc sau în această listă. Mod de alocare În ALLO se face liniarizarea unui masiv "pe linii" în care ultimul indice crește mai repede până la final și se repune la început nu înainte de a-l crește cu 1 pe precedentul, etc. Un domeniu cu două dimensiuni, prima domeniul [1,m] iar a doua domeniul [1,n]) este privită similar cu matricea [m ,n] adică elementele în ordinea linie 1, ... linie m fiecare linie având n elemente cât are o coloană. Elementele matricei sunt aranjate astfel: a[1,1], ... a[1,n], ... a[m,1], ... a[m,n]. Formula de alocare este loc (a[i,j]) = (i-1)* n+ j. Locul primului element este loc (a[1,1]) =1 și al ultimului este loc (a[m,n]) =(m-1)*n +n = m*n adică egal cu numărul de elemente al matricei. Un masiv cu trei dimensiuni, a[m,n,p] este privit ca un cub format din
m*n*p cubulete identice sau format din p etaje de cubulețe fiecare etaj fiind o
matrice de cubulețe a[m,n]. Deci cubulețul a[i,j,k] se află pe
etajul k la
intersecția liniei i cu coloana j. În AlLO variabilele auxiliare de tip întreg sau real, variabilele modelului, variabilele funcții obiectiv și variabilele restricții pot fi declarate ca masive de variabile vectori, matrici, tridimensionale,etc. Aceasta ușurează munca de scriere a unui model complex de mari dimensiuni. Referinta la un element de masiv Am văzut că un masiv este o colecție de celule / obiecte de același tip organizate după o procedură de alocare cunoscută. Accesul la o astfel de celulă / obiect se face prin invocarea numelui acelui masiv și a unei liste de expresii indici al cărei număr de elemente coincide cu numărul de dimensiuni ale masivului. Aceasta constituie așa numita referința la acel element din masiv pe baza căruia îl accesăm. Expresia indice este o expresie aritmetică calculabilă în momentul utilizării ei în lista de referință a unui element de masiv. Se calculează valoarea acesteia, se convertește (dacă este cazul) la o valoare întreagă iar apoi se face testul de apartenență la domeniul corespunzător locului dimensiunii. Similar se procedează cu orice expresie indice dintr-o listă de expresii indiciale. După aceasta se trece la calculul indicelui liniarizat care reprezintă locul elementului referit. Pe baza locului se poate calcula și adresa față de început prin înmulțirea (loc -1) cu unitatea de alocare a tipului variabilei. Sintaxa ref_element_masiv ::=
nume_masiv [ l_expr_ind ] Exemple : ump [r,f], storcost[r], xprod[f,p] Rprd [ATR(opczindl[j],h) + ATR((h-1)/nrprod+1,m)+h-(m-1)*nrprod , f] Observație Expresiile indiciale din primele trei exemplele de mai sus sunt simple învocând numele de variabilă auxiliară r, f, p. În ultimul exemplu prima expresie indicială este o expresie aritmetică complicată în care intervin două acțiuni intermediare. ATR(opczindl[j],h) este funcția care atribuie lui h valoarea calculata a elementului de vector opczindl[j]. Apoi această valoare a lui h intră în calculul expresiei care se atribuie lui m și apoi se calculează valoarea expresiei h-(m-1)*nrprod care convertită la întreg este primul indice de referință al lui Rprd, al doilea fiind m cu valoarea calculată imediat anterior dar care trebuie eventual convertită la întreg. Variabilele limbajului ALLO sunt elementele de bază în construcția unui model. Cu exceptia tipului INDICE (recunoscut implicit din context) toate trebuie să aibă o declarație / definiție . Din punct de vedere al dimensiunii avem două tipuri de variabile : variabile scalare și variabile compuse cu una sau mai multe dimensiuni. Variabilele scalare sunt definite prin nume, tip și eventual o valoare. Variabilele compuse sunt definite prin nume, tip, listă dimensiuni și eventual listă de valori. Elementele variabilelor compuse sunt accesibile prin nume și lista de indici rezultată eventual dintr-o listă de expresii indiciale Pe baza acestei liste si a listei de dimensiuni se calculeaza locul linear al elementului și astfel se calculează valoarea sau un nume scalar linearizat. Amănunte la acest subiect sunt la descrierea masivelor. După scop variabilele limbajului ALLO pot fi încadrate în patru grupe care corespund celor patru secțiuni ale unui model sursa:
- variabile auxiliare;
Variabile auxiliare Variabilele auxiliare împreună cu constantele ajută la construcția modelului prin : coeficienți , ușurarea exprimării relațiilor și restricțiilor,etc. Toate variabilele auxiliare trebuie să aibe o valoare în momentul utilizării lor. în această categorie intră următoarele tipuri:
- variabile auxiliare întregi;
Variabile auxiliare Întregi Aceste variabile pot fi scalare sau compuse, vectori, matrice, etc. O variabilă scalară este reprezentată în cod complementar cu semn și pe patru octeti. O valoare din intervalul [ - 2147483648, 2147483647 ] poate fi atribuită unei asemenea variabile. O variabilă auxiliară întreagă trebuie să apară într-o instrucțiune INTEGER în care se regăsește toată declarația sa. Variabilele auxiliare întregi sunt frecvent utilizate la construcția domeniilor întregi necesari în definirea masivelor sau în instrucțiunile ce conțin secvente de ciclare FOR sau SUM. De asemenea sunt utilizate în expresiile indiciale, în alte scopuri dar nu pe rol de indici de ciclare. Sintaxa var_intreg ::= var_intreg_scalara
| var_intreg_masiv
Exemple : nrfprod, nrperp, opczindl [opcze] Observație. Toate variabilele citate sunt întregi dacă sunt într-o instrucțiune de tip INTEGER în modelul respectiv. Variabile auxiliare Indici Aceste variabile sunt numai de tip scalar prin nume și nu fac obiectul unei declarații explicite. Sunt considerate de tip întreg și pot participa în expresii indiciare, expresii coeficienți, sau chiar la definirea unor domenii dinamice care pot fi evaluate numai într-un anumit context de execuție al unei instrucțiuni. O variabila indice este pezentă ca indice de ciclare în secvențele FOR și SUM. În acel moment acest indice nu trebuie să fie utilizat de alt FOR sau SUM. Deci scopul sau este precis până la sfârșitul operației în care este implicat după care poate fi reutilizat. Sintaxa var_indice ::= nume Exemple : j, k, k1, m, n, r, f, p Observație. Se observă o anumită simplitate pe rolul variabilei auxiliare indice dar putem să utilizăm și nume mai complicate. Variabile auxiliare Reale Variabilele auxiliare reale pot fi scalare sau compuse (vectori , matrice, etc). O variabilă scalară este reprezentată în virgulă mobilă cu semn și pe patru octeți. Domeniul aproximativ de valori al unei astfel de variabile este domeniul negativ [ - 3.4028235E+38, - 1.1754944E-38 ] plus valoarea 0 și domeniul pozitiv [ 1.1754944E-38 , 3.4028235E+38 ]. O variabilă reala trebuie să apară într-o instrucțiune REAL în care se regăsește toată declarația sa. Variabilele auxiliare reale sunt utilizate la construcția expresiilor coeficienți sau a domeniilor reale utilizate ca domenii de mărginire variabile model sau variabile restricții model. Sintaxa var_real ::= var_real_scalara | var_real_masiv
Exemple : prodmax, storcost [rmat] , ump [rmat,fprod] , profdc [fprod,perp] Observație. Toate variabilele citate sunt reale numai dacă sunt incluse într-o instrucțiune de tip REAL. Variabile auxiliare Domeniu Variabilele auxiliare domeniu sunt numai de tip scalar și sunt utilizate ca domenii dimensiuni, domenii de ciclare sau domenii de mărginire variabile model sau variabile restricții model. Primele două tipuri au valori întregi iar celelalte reale. O variabila domeniu are două valori. O valoare reprezinta marginea inferioară iar cealaltă marginea superioară. Deoarece nu se cunoaște utilizarea ulterioara a acestui domeniu (căci translatorul face o singură trecere prin textul sursă) aceste valori sunt reținute ca valori reale dar și ca valori întregi. O astfel de variabilă poate reprezenta un interval pe axa reală sau pe axa numerelor întregi. O variabilă domeniu trebuie să apară într-o instrucțiune RANGE care conține întreaga sa definiție. Sintaxa var_domeniu ::= nume Variabile auxiliare Nume Fisier Limbajul ALLO permite definirea unor astfel de variabile a căror valoare este o specificație de fisier DOS. Definirea se face prin instructiunea FILE care înseamnă și Openul implicit pentru a fi pregătit la satisfacerea primei variabile dintr-o instrucțiune READ care face referire la acest nume. O astfel de variabilă este utilizată ca referință la fișierul auxiliar pe care-l reprezintă și din care pot fi preluate date de asignare pentru alte variabile auxiliare. ALLO permite accesul simultan la mai multe fișiere auxiliare fișierului principal cu textul de bază al modelului. Sintaxa var_fisier ::= nume Exemple : fpp, fdist, fcsd Observație. Numele acestea trebuie să apară în instrucțiunea FILE. Se aleg după dorință, mai simple dacă sunt solicitate mult în model. Variabilele modelului
de optimizat se definesc toate după secțiunea variabilelor auxiliare. Tipul de dată asociat unei
astfel de variabile este numai tipul real. Dacă în definiție nu este clauza de mărginire atunci variabila este presupusă pozitivă. Dacă are clauza de mărginire inferioară atunci domeniul
său este până la plus infinit.
Dacă are numai clauza de marginire superioară atunci această margine trebuie
să fie strict pozitivă iar domeniul considerat pentru aceasta variabilă
este de la zero și până la această valoare. Dacă clauza este de dublă mărginire
atunci domeniul poate fi negativ, pozitiv sau mixt numai sub condiția ca
acesta să fie corect reprezentat de margini, adică marginea inferioară
<= marginea superioară. Rezultatul procesării clauzei de mărginire se
regăsește în secțiunea BOUNDS a fișierului MPS rezultat.
O variabilă model poate fi scalară sau compusă (vector, matrice,etc.) lucru ce ne permite să utilizăm instrucțiuni generale (puternice) de definire atât a clauzelor de mărginire cât și a unor restricții. Variabilele model scalare apar în fișierul MPS cu numele lor când are cel mult opt caractere. În caz contrar numele este rezultatul truncherii la primele 8 caractere. Pentru variabilele compuse apare nevoia de încifrare în nume a indicelui liniarizat al celulei referite. Aceasta se face pe câte caractere este necesar la spate până la cele opt permise. De aceea utilizatorul trebuie să-și aleagă numele generic mai scurt de 8 caractere și corelat cu dimensiunea respectivă. Altfel pot apare incoerențe pe aceeași reprezentare de nume finale căci translatorul nu face această verificare. Această procedură ni s-a părut cea mai bună la momentul respectiv. Altfel ar fi fost necesar construcția unui dicționar foarte util și în operația de refacere, a soluției optimizator, în termenii numelor originale cu indicii nelinearizați. Sintaxa var_model ::= var_model_scalara |
var_model_masiv
Exemple : xprod [fprod,perp], xsmat[rmat,perpext], Rprd[prod,fact], XRZP [hrze] , XIRZP [hrz] , XORZP [hrz] , XAF Aceste variabile
permit definirea funcțiilor obiectiv din secțiunea funcțiilor obiectiv. Pot fi scalare sau compuse. La sfârșitul acestei secțiuni o singură
funcție scalară sau componentă poate fi selectată în instrucțiunea
MINIMIZE / MAXIMIZE. Rezultatul procesării
unei definiții de funcție obiectiv se regăsește în fișierul MPS în sectiunile
ROWS și
COLUMNS.
Sintaxa var_fobj ::= var_fobj_scalara | var_fobj_masiv
Exemple : profit | cost Variabilele restricții
sunt nume pentru liniile restricțiilor din model
necesare pentru întelegerea lui, pentru forma supusă rezolvării de către solver
(la noi MPS-ul) și pentru forma soluției (furnizată de solver) necesară în
interpretarea ei pentru procesul decizional real. Pot fi scalare sau compuse
fiind definite în secțiunea restricțiilor
model. Rezultatul procesării unei restricții se regăseste în
fișierul MPS în secțiunile ROWS, COLUMNS, RHS
(Right Hand Section)
și eventual în secțiunea
RANGES dacă restricția a avut clauză de dublu mărginire.
Sintaxa var_restr ::= var_restr_scalara |
var_restr_masiv
Exemple : limprod [perp] , pmbal [rmat,perp] , rtlim | DRZP [hrz] Operatorii acționează asupra unuia sau mai multor operanzi pentru a produce o valoare, o actiune și o valoare, o limitare de domeniu pentru anumite variabile model sau restricții. Operatorii limbajul ALLO sunt din categorile: Operatori aritmetici Operatorii aritmetici sunt utilizați în construcția expresiilor aritmetice și simbolice. În cadrul expresiilor aritmetice actionează asupra unui operand sau a doi operanzi producînd un nou operand ce participă mai departe în evaluarea expresiei. Într-o expresie simbolică pot fi într-o expresie aritmetică coeficient, operator pe expresie simbolică sau operator asupra a două expresii simbolice producând un nou operand de tip expresie simbolică. Avem operatori unari și operatori binari, aditivi sau multiplicativi. Sintaxa opr_aritm ::= opr_unar | opr_binar
Operatorii funcții sunt invocați numele funcției implicite recunoscute de limbajul și de translatorul ALLO. Aceștia acționează asupra parametrilor de apel o listă închisă între două paranteze rotunde ce urmează după nume. Rezultatul din execuția acelei funcții este un operand ce participă mai departe la calculul expresiei respective. Înainte de execuția funcției sunt evaluați toți parametri de la stânga la dreapta rezultând o listă de valori concrete cu tipul fiecăreia. Se verifică corectitudinea apelului ca număr de parametri și ca tip. Dacă totul a fost corect rezultă operandul respectiv, altfel se semnalează eroarea. Sintaxa opr_fun ::= ABS | AND | APX | ATR | DIP | IFP | IFS | LOR | LOG | apel_fun ::= opr_fun ( l_param_act )
Observatie. Numele de operatori funcție se pot scrie cu litere mici sau chiar în combinație mari cu mici. Exemple apel functie: ATR(rtl[d,w]*((d-1)*nrwhse+w),h) , ABS(a[j,k]+5.3] , SEARCH(h,rtindl[1],find) ,
Functii recunoscute de translatorul ALLO
Sunt utilizați în expresii relaționale necesare pentru validarea unor variabile auxiliare de tip întreg sau real care pot fi supuse unor restricții. Rezultatul este 1 (adevărat) sau 0 (fals) după cum a fost îndeplinită sau nu relația. Sintaxa opr_rel ::= < | <= | = | >= | > | <> Operatori de marginire variabile simbolice Variabile model pot primi valori numai dacă sunt dintr-un anumit domeniu. Această cerere este marcată în fișierul MPS în secțiunea BOUNDS. Astfel optimizatorul ține seama de condiție în procesul de găsirea unei soluții optime. Și variabilele restrictii model pot fi supuse unor condiții similare. Condiționarea este obținuta prin utilizarea operatorilor de mărginire simbolică din clauzele de mărginire variabile sau restrictii model. Sintaxa opr_marg ::= <= | = | >= | IN Observatie. În cazul = avem variabilă model cu valoare fixată (FX în secțiunea BOUNDS). O restricție model este restricție cu egalitate (E în secțiunea ROWS). Operatorul IN determină apartenența la un domeniu cu margini reale finite. Operatorii <= sau >= spun ca variabila model / variabila restricție model are voie să ia și valoarea respectivă. Nu există cazul strict în modelarea standard. Pentru variabila model operatorii <= sau >= transmit UP sau LO în secțiunea BOUNDS.Pentru variabila restricție model operatorii <= sau >= transmit L sau G în secțiunea ROWS. Paranteze Limbajul ALLO utilizeaza trei perechi de paranteze distincte : Parantezele rotunde sunt utilizate în construirea expresiilor complexe sau în construirea apelurilor de funcții implicite. Expresia parantezată se calculează ca valoare și devine operand. Dacă este cazul unui apel de funcție implicită se calculează valorile parametrilor după care se "apelează" funcția care efectuează eventual o acțiune dar produce un operand utilizat în calcul mai departe. Parantezele drepte sunt utilizate în definirea masivelor (lista dimensiuni este între [ ] ), în referința la un element de masiv ( lista indici este între [ ] ), precum și în construcția blocurile FOR și SUM. În funcție de context de utilizare se evaluează și se reținere a lista dimensiuni, se evaluaează expresiile indiciale pe baza cărora se calculeaza indicele liniarizat, evaluare startare si control al operațiunilor de ciclare din blocul respectiv. Parantezele acolade sunt utilizate în delimitarea unui bloc de instrucțiuni din aceeași definiție a unei variabile precum și pentru încadrarea listei cu expresii de inițializare a unei variabile auxiliare de tip masiv de întregi sau de reali. Dacă lista este citită dintr-un fișier secundar atunci aceste paranteze au fost suprimate din rațiuni practice. Sintaxa p_rotunda ::= ( | )
Expresii Elementul de bază al limbajului ALLO îl constituie expresia care este nelipsită aproape din toate instrucțiunile cu excepția instrucțiunilor de structurare pe secțiuni a modelului. Avem următoarele tipuri de expresii: Expresii aritmetice Expresiile aritmetice sunt
construcții cu operanzi, operatori și paranteze rotunde.
Ca operanzi pot fi constante întregi sau reale, variabile auxiliare de
tip întreg sau real, referințe la elemente de masiv de variabile întregi
sau reale, apeluri de funcți implicite.
Rezultatul evaluarii unei expresii aritmetice este un operand, valoare reală sau
întreagă.
Sintaxa expr_aritm ::= termen rest_suma
Exemple : (d-1)*nrwhse+w , h-(m-1)*nrprod , ATR(h+IFS(rtl[d,w],1,0),h) , SUM[f IN fact,p IN prod](Ifp(rpc[f,p],0,1,0)) , +2.3 , N , 5 * M Expresii condiție de validare Aceste expresii sunt construcții bazate pe două expresii aritmetice legate printr-un operator relațional. Rezultatul evaluarii unei asemenea expresii este o valoare întreagă 0 sau 1 cu semnificația de fals sau adevăr. Sunt evaluate mai întâi cele două expresii aritmetice după care se face comparația lor. Aceste expresii sunt utilizate în instrucțiunile de definire a variabilelor auxiliare de tip întreg sau real și anume în clauza de validare. Sintaxa expr_cond_valid ::= expr_aritm opr_rel expr_aritm Exemple : prodmax > 0.0 | omin[f] <= omax[f] | nrdctr < nrwhse Expresiile liniare simbolice sunt expresii construite și evaluate în mod similar cu expresiile aritmetice. Numai că aici apar și operanzi variabile model scalare sau referințe la elemente de masiv. La operatorii binari multiplicativi nu putem să avem simultan expresii simbolice căci expresia rezultată nu ar mai fi lineara lucru semnalat de translator în procesul de evaluare. Variabilele funcții obiectiv sau variabilele restricții n-au ce cauta într-o expresie simbolică. Ele pot primi în definiție ca valoare o expresie simbolică lineară. Sintaxa expr_simb ::= termen_simb rest_suma_simb
Exemple : Sum[f In fprod,p In perp](profdc[f,p]*xprod[f,p]) , xsmat[r,p] - Sum[f In fprod](ump[r,f] * xprod[f,p]) Blocurile repetitive
sunt construcții semantice ALLO care ne permit repetarea (cu alți parametri
legați de ciclu) instrucțiunilor
sau operațiunilor din corpul lor. Această facilitate este deosebit de utilă în scrierea concentrată a modelului
chiar și pentru procesele / sistemele de mari dimensiuni. Blocurile au un antet de definire a unuia sau mai multor cicluri
simultan. Un ciclu este definit de un indice de ciclare precum și un domeniu întreg
în care are voie să
evolueze cu pasul 1 implicit. Pentru inițierea unui ciclu se
evaluează domeniu de ciclare (există domenii dinamice cu
expresii în care intră variabile indici de ciclare ce sunt active/au valoare
doar în acest context) după care indicele de ciclare
este inițializat cu valoarea marginii inferioare a domeniului .
Blocul FOR Acest bloc permite reluarea unui grup de instrucțiuni ce formează corpul ciclului al cărui început și sfârșit sunt sesizate prin sintaxă. Dacă corpul are mai multe instrucțiuni el începe cu { și se termină cu }. Fiecare instrucțiune din corp se termină cu ; afară de ultima al cărui sfârșit este recunoscut prin }. Sintaxa antet_for ::= FOR [ l_expr_apart ]
Exemplu : FOR [p IN perp] | FOR [r IN rmat, f IN fprod] Blocul SUM Acest bloc permite reluarea procesului de sumare a unei expresii cuprinsă între două paranteze rotunde și care formează corpul ciclului. Blocul SUM este deosebit de util în exprimarea expresiilor simbolice foarte mari care pot fi concentrate la maxim. Procesul de sumare porneste cu valoarea 0.0 la care se adaugă ceea ce rezulta la fiecare trecere repetată peste expresie (care se reclaculează și se adună) până la epuizarea ciclului. Sintaxa antet_sum ::= SUM [ l_expr_apart ]
Exemplu : SUM[r IN rmat] , SUM [f IN fprod, p IN perp] Instrucțiuni Instrucțiunile limbajului ALLO sunt asamblaje speciale cu semantică complexă care definesc secțiunile unui model și fiecare variabilă utilizată în fiecare secțiune a modelului. Categoriile de instrucțiuni sunt : Instrucțiuni de structurare model Au rolul de a crea o structură pe secțiuni a unui model ALLO. În afară de instrucțiunea model, toate celelalte sunt definite numai de cuvintele cheie respective care semnalează destinația secțiunii ce urmează sau sfârșit de model. Fiecare secțiune apare o singură dată. Sintaxa instr_struct_model ::= MODEL nume_model |
VARIABLES | OBJECTIVES |
CONSTRAINTS | END
Sintaxa unui program-model ALLO Mai jos este schema sintactică a unui model de optimizare scris în limbajul ALLO. Sintaxa este liberă la zone albe formată din spații, taburi, linii sursă vide. De asemenea cuvintele rezervate nu sunt senzitive la litere mari sau mici și pot fi folosite după dorință. La fel se comportă oricare nume ALLO. Un program ALLO este o concatenare a celor patru secțiuni cu tot ceea ce ține de ele și în ordinea impusă. Fiecare secțiune este o concatenare de una sau mai multe instrucțiuni specifice secțiunii care sunt separate prin tokenul caracter punct și virgulă. Excepția o face ultima instrucțiune din fiecare secțiune deoarece sfârșitul ei este indicat de cuvântul cheie ce urmează obligat. Din acest motiv toate instrucțiunile din secțiunea variabilelor auxiliare n-au nevoie de caracterul de sfârșit punct și virgulă deoarece fiecare instrucțiune începe cu un cuvânt cheie care indică și sfârșitul instrucțiunii precedente. Sintaxa Program ::= MODEL nume_model sect_var_aux VARIABLES
OBJECTIVES
CONSTRAINTS
END Secțiunea variabile auxiliare sect_var_aux ::= s_instr
Secțiunea variabile model sect_var_model ::= s_instr_var_model
Secțiunea variabile funcții obiectiv sect_var_fobj ::= s_instr_fobj instr_select_fobj
instr_select_fobj ::= MINIMIZE ref_fobj | MAXIMIZE ref_fobj Secțiunea variabile restricții sect_var_restr ::= s_instr_restr
Instrucțiuni de pregătire date auxiliare Ne permit definirea variabilelor auxiliare necesare în construcția oricărui model. Avem cîte o instrucțiune specifică pentru fiecare tip de dată. Fiecare instrucțiune începe prin cuvântul cheie corespunzător. Instrucțiunile INTEGER și REAL sunt identice cu excepția cuvântului cheie. Iată tipul de instrucțiuni: Instrucțiunea FILE Cu aceasta putem defini variabile auxiliare de tip FILE a căror valoare este un șir specificație fișier recunoscut de sistemul de operare DOS. Fișierul este secundar cu date atașate prototipului model din fișierul principal. Accesul la el se face prin invocarea numelui variabilei (nume intern pentru fișier) în comanda READ din instrucțiunile de definire a variabilelor auxiliare de tip INTEGER sau REAL în cazul când au datele de inițializare în fișierul asociat. Printr-o instrucțiune putem defini mai multe fișiere secundare separate de caracterul punct și virgulă. Un fișier secundar este deschis implicit în vederea accesului la datele curente din ele. Această instrucțiune poate apare oriunde în cadrul secțiunii. Sintaxa instr_file ::= FILE s_decl_file
Exemple : FILE fpp = "prodplan.dat" , FILE fcsd="cetsud.dat" Instrucțiunea RANGE Permite definirea uneia sau mai multe variabile de tip RANGE (domeniu de tip interval întreg sau real). Printr-o instrucțiune putem defini mai multe domenii separate de caracterul punct și virgulă. Constanta domeniu trebuie să fie calculabilă în momentul definirii în sensul că ambele expresii de margine trebuie să fie calculabile. Dacă conțin alte variabile auxiliare de tip întreg sau real acestea trebuie să fie definite anterior și desigur inițializate. Această instrucțiune poate apare oriunde în cadrul secțiunii. Sintaxa instr_domeniu ::= RANGE s_decl_domeniu
Exemple : RANGE fprod = [1,nrfprod] ; rmat = [1,nrrmat ] Observatie. Deasupra avem definite două domenii într-o singură instrucțiune care poate fi scrisă chiar și pe mai multe linii sursă. Fiecare domeniu putea fi definit într-o instrucțiune separată. Se presupune că variabilele auxiliare nrfprod și nrmat sunt deja cunoscute în momentul atingerii instrucțiuni RANGE așa că expresiile de margini sunt toate calculabile. Mai trebuie ca aceste valori să fie mai mari sau egale cu 1 datorită marginii inferioare prezente și constanta 1. Instrucțiunea INTEGER Permite definirea uneia sau mai multe variabile auxiliare de tip întreg, scalar sau masiv. Dacă sunt multiple atunci definițiile lor trebuie să fie despărțite prin tokenul punct și virgula. Fiecare definiție este compusa din trei componente din care prima este obligatorie căci are numele și dimensiunea variabilei. A doua componentă este dedicată inițializarii variabilei care poate fi făcută chiar si prin citirea datelor dintr-un fișier secundar de la pointerul la care s-a ajuns în momentul comenzii READ. Componenta trei se ocupă de validare. Dacă nu este componenta doi, pentru variabilele dimensionate este interpretată ca o procedură de asignare date pentru unele elemente (chiar toate) ale masivului. În acest caz în secvența de validare poate apare decât operatorul relațional = care este reinterpretat ca operator de atribuire. De aceea în fața acestuia poate sta numai expresii referința la element masiv. Sintaxa instr_integer ::= INTEGER s_decl_integer
Exemple: INTEGER M = 10 ; N = 23 INTEGER V[ [3,5] ] ={1,2,3} INTEGER nrfprod READ fpp IS nrfprod >0 ; nrperp READ fpp IS nrperp >0 Observație. În prima instrucțiune sunt definite variabilele auxiliare M și N cu valorile de inițializare 10 respectiv 23. În a doua instrucțiune am definit un vector cu indici în domeniul [3,5] ale cărui valori initiale sunt acestea V[3]=1, V[4]=2 si V[5]=3. În ultima instrucțiune sunt definite două variabile auxiliare scalare. Pentru fiecare variabilă valoarea este citită din fișierul fpp și validată prin condiția de după cuvântul cheie IS. Instrucțiunea REAL Tot ceea ce s-a spus la variabilele auxiliare de tip INTEGER rămine valabil și aici. Din sintaxă part_init și part_valid sunt definite exact ca în sintaxa precedentă. La ele se adaugă în față numai cele de mai jos: Sintaxa instr_real ::= REAL s_decl_real
Exemple : REAL ump [rmat,fprod] READ fpp IS FOR [r IN rmat,f IN fprod] ump[r,f]>= 0.0 Observație. Mai sus se definește o singura variabilă auxiliară matricială ale cărei valori sunt preluate din fisierul fpp. Fiecare valoare de inițializare a elementului de matrice nu poate fi un număr negativ deoarece nu permite clauza de validare din corpul blocului FOR ce cicleaza pe doi indici ai domeniilor rmat și fprod. Instrucțiunea de definire variabile model Permite să definim variabilele simbolice, elemente de bază ce participă în expresii simbolice din definiția variabilelor funcții obiectiv și a variabilelor restricții model. O variabilă model are un nume, o listă dimensională dacă este de tip masiv precum și o eventuală condiție de mărginire. Variabilele model nu au valoare inițială. Pe rol de valoare inițială putem considera valoarea de condiție dacă există și care este formată din codul operatorului de mărginire și de una sau două valori care reprezintă marginea inferioară sau marginea superioară ca domeniu admisibil de valori. Avem un domeniu cu două valori când operatorul este IN. Variabilele model vor primi valori numai în procesul de optimizare care încearcă să determine o soluție optimă. Acest proces este independent de procesul de analiză, validare și translatare model în format standard MPS. Instrucțiunile sunt separate de caracterul punct si virgula, cu excepția ultimei instrucțiuni. Sintaxa instr_var_model ::= var_model part_cond_marg
Exemple : xprod [fprod,perp] , xsmat[rmat,perpext] IS FOR[r IN rmat] xsmat[r,1] <= stinimax[r] Observație. Prima instrucțiune definește o variabilă model matrice care nu conține nici o clauză de mărginire în care toate elementele sunt presupuse în domeniul real pozitiv. A doua instrucțiune definește o variabilă care conține o clauză de mărginire pentru toate elementele componente care au indicele 1 pe a doua dimensiune și cărora li se cere să nu depășească limita superioară cu valoare în vectorul stinimax primul indice dimensional. Clauza este cu blocul FOR care are o singură componentă: xsmat[r,1] <= stinimax[r]. Instrucțiunea de definire funcții obiectiv O variabilă funcție obiectiv are un nume, o listă dimensională (dacă este de tip masiv) precum și o parte de definire cu expresie simbolică. Instrucțiunile de definire variabile funcții obiectiv sunt separate între ele de caracterul punct și virgulă. Excepție o are ultima instrucțiune care se termină înaintea unui cuvânt cheie MINIMIZE / MAXIMIZE. Sintaxa instr_fobj ::= var_fobj IS proced_def_fobj
Exemplu: fobj IS fobj := SUM[f
IN fprod,p IN perp](profdc[f,p]*xprod[f,p])
Observatie. Mai sus avem o variabilă scalară funcție obiectiv fobj construită ca o sumă de expresii simbolice. Instrucțiunea de selecție funcție obiectiv Această instrucțiune, ultima din secțiunea funcțiilor obiectiv permite nu numai selectarea funcției obiectiv (luată în considerare de optimizator) dar și tipul problemei. Translatorul ALLO pune min / max pe linia corespunzătoare acestei funcții din secțiunea ROWS a fișierului MPS rezultat dar și N în fața numelui. Celelalte funcții obiectiv (dacă există) nu influențează soluția. Referinta la funcția de optimizat constă în citarea numelui unei variabile scalare sau a unui element referință din variabila functie obiectiv de tip masiv. Sintaxa instr_select_fobj ::= MINIMIZE ref_fobj | MAXIMIZE ref_fobj Exemple : MAXIMIZE profit , MINIMIZE cost Instrucțiunea de definire restricții model Structura de baza a unui model liniar este formată din restricții model care furnizează matricea modelului. În limbajul ALLO fiecare restricție poartă un nume cerut și de standardul MPS. Pe de altă parte o variabilă restricție model poate fi un masiv ceeace ușurează munca de definire model. Definirea restricțiilor se face cu instructiunea de mai jos care cuprinde partea de definire nume cu o eventuala dimensionare urmată de cuvântul cheie IS și de procedura de definire concretă. Dacă avem o variabilă restricție de tip masiv, din model vor face parte numai acele linii rezultate din celulele masivului citate ca referința în procedura de definiție care poate fi realizată și prin blocul FOR sau SUM. Instrucțiunile sunt separate de caracterul punct si virgula, cu excepția ultimei instrucțiuni. Aceastase află înaintea instrucțiunii END care încheie atât secțiunea restricțiilor model precum și modelul ALLO. Sintaxa instr_restr ::= var_restr IS proced_defrestr
Exemple: limprod [perp] IS FOR [p IN perp] limprod[p]:= SUM[f IN fprod](xprod [f,p]) <= prodmax; Observație. Instrucțiunea definește o variabilă restricție de tip vector numita limprod. Definiția fiecărei componente este în corpul unui ciclu FOR și conține o expresie simbolică realizată cu operatorul SUM plus o condiție de mărginire superioară. Structura unui program ALLO Modelul are o structură marcată de cuvintele cheie MODEL, VARIABLES, OBJECTIVES, CONSTRAINTS, END MODEL nume_model
VARIABLES
OBJECTIVES
CONSTRAINS
END Secțiunea Variabilelor Auxiliare Model Începe după instrucțiunea MODEL și se termină
înaintea instrucțiunii VARIABLES. Aceasta este dedicată definirii
ți pregătirii tuturor datelor necesare în construcția modelului din ultimile trei secțiuni : secțiunea variabilelor
model, a funcțiilor obiectiv și secțiunea restricțiilor.
Sectiunea Variabilelor Model Este semnalată de instrucțiunea VARIABLES și ține până la instrucțiunea OBJECTIVES. Aici sunt definite toate variabilele model. Într-o definiție/instrucțiune poate să apară condiția de mărginire. Dacă nu apare variabila este considerată pozitivă (de la 0 la +infinit) Pentru variabila de tip masiv restul elementelor din masiv (dacă sunt) care n-au fost invocate în condiția de mărginire sunt considerate variabile model pozitive. Secțiunea Funcțiilor Obiectiv Model Începe cu instrucțiunea OBJECTIVES și ține până la CONSTRAINTS. Aici sunt definite toate funcțiile obiectiv din care selectăm doar una (scalară sau referință la element de masiv) pentru optimizare model. Atât definițiile funcțiilor cât și instrucțiunea de selecție au echivalent în fițierul MPS prin marcarea, în secțiunea ROWS, a tuturor funcțiilor cu N în fața numelui (linearizat dacă provin din masiv) și cu MIN sau MAX după numele funcției selectate. Desigur numele funcțiilor obiectiv sunt invocate și în secțiunea COLUMNS. Toate funcțiile obiectiv neselectate nu influențează soluția. O nouă selecție poate fi făcută ușor prin modificarea instrucțiunii de selecție, generarea unui nou MPS, etc. Secțiunea se încheie cu instrucțiunea de selecție care este obligatorie dacă vrem să rezolvăm problema. Secțiunea Restricțiilor Model Începe cu instrucțiunea CONSTRAINTS și ține până la instrucțiunea END care încheie textul modelului ALLO. în această secțiune sunt definite toate restricțiile modelului. Pot fi definite restricții simple cu egalitate sau nu și restricții dublu mărginite. Acestea produc câte o linie în secțiunea RHS și RANGES a fișierului MPS rezultat. Toate restricțiile produc linii în secțiunea ROWS marcate cu E, L sau G. Desigur numele funcțiilor restricții sunt invocate și în secțiunea COLUMNS din MPS. Sintaxa ALLO Metalimbaj pentru Sintaxa ALLO ::= ne spune ca elementul din stânga sa se construiește după cum urmează (sau este prin definiție); | este separator de elementele listei. Orice element poate participa la construcția asamblajului complex respectiv; Spațiu dintre două elemente de metalimbaj sau dintre un element de metalimbaj și un atom (ex. caracterul de link _ ) înseamnă operația de concatenare dintre două șiruri. Un element de metalimbaj semnifică o clasă / mulțime de posibile asamblaje (siruri pe alfabet) construite cu regulile acelui element. lambda este simbolul elementului nul față de operația de concatenare caractere sau șiruri de caractere. Este un șir vid care n-are nici un caracter fiind de lungime zero. Gramatica limbajului ALLO a fost adusă la forma care îndeplinește criteriul LL1 Început sintaxă ALLO
nume ::= litera | nume litera | nume cifra | nume _
cifra ::= orice element cifra a setului de caractere
secv_cifra ::= cifra | cifra secv_cifra
const_domeniu ::= [ expr_aritm , expr_aritm ]
sir ::= " secv_car "
masiv ::= nume_masiv [ l_dim ]
opr_aritm ::= opr_unar | opr_binar
opr_fun ::= ABS | AND | APX | ATR | DIP | IFP | IFS | LOR | LOG | MAX | MIN |
opr_rel ::= < | <= | = | >= | > | <>
opr_marg ::= <= | = | >= | IN
Program ::= MODEL nume_model
sect_var_aux ::= s_instr
instr_file ::= FILE s_decl_file
instr_domeniu ::= RANGE s_decl_domeniu
instr_integer ::= INTEGER s_decl_integer
instr_real ::= REAL s_decl_real
sect_var_model ::= s_instr_var_model
sect_var_fobj ::= s_instr_fobj instr_select_fobj
instr_select_fobj ::= MINIMIZE ref_fobj | MAXIMIZE ref_fobj
sect_var_restr ::= s_instr_restr
Datorită resurselor umane limitate și a resurselor tehnice
lipsă (PDP 11 cu asembler
Macro 11) facultatea a predat
proiectul institutului ICI. Pe lângă completarea lipsurilor din
proiect
urma partea cea mai grea legată de analiza semantică,
generarea de cod, progamare tot în Macro 11, testare,etc. Institutul
încă nu avea specialiști
pe domeniu (cu o oarecare excepție) deoarece abia în 1974 a angajat zeci de
absolvenți specializați în matematică, informatică,
calculatoare, cibernetică dar nu și pe
construcția compilatoarelor. Pentru continuarea proiectului LPTR s-a
format o echipă (din 8 salariați de la Centrul de Calcul) condusă de
Mat. Petre Preoteasa .
O
Gramatica LL1 a limbajului LPTR
Metalimbajul utilizat este similar cu cel de la ALLO
Caractere Recunoscute: Caractere Ignorate: Ascii Cod(9) - Ascii Cod(13) ! Oricare din interval
Comentariile sunt marginite stanga si dreapta de caracterul "%"
/*-----------------Tokeni rezultati din Analizorul Lexical------------------------*/
nrop ::= cifra
/*-------------Tokenii din Cuvinte Cheie sunt cu Litere Mari------------------*/
/*--------------------------------------------------------
Productii ------------------------------------------*/
Sfârșit gramatica limbajului LPTR | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ALLO și SAMO, Limbaj și Sistem Avansat de Modelare și Optimizare
Subscribe to:
Posts (Atom)