Programare dinamică. Problema alocării optime a resurselor. Rezolvarea diverselor probleme practice de programare dinamică: Alocarea optimă a resurselor

Scurtă teorie

Programarea dinamică (cunoscută și sub denumirea de planificare dinamică) este o metodă de găsire a soluțiilor optime în probleme cu o structură în mai multe etape (mai multe etape). Multe procese economice sunt împărțite în etape într-un mod natural. Toate acestea sunt procese de planificare și management dezvoltate în timp. Un pas firesc în ele poate fi un an, un sfert, o lună, un deceniu, o săptămână, o zi etc. Cu toate acestea, metoda de programare dinamică poate fi folosită pentru a rezolva probleme în care timpul nu apare deloc; Împărțirea în trepte în astfel de probleme este introdusă artificial. Prin urmare, „dinamica” problemelor de programare dinamică constă în metoda soluționării.

În practica economică, există mai multe tipuri de probleme care, după formularea sau metoda lor de rezolvare, aparțin unor probleme de programare dinamică. Acestea sunt probleme de planificare optimă pe termen lung și actuală în timp. Acestea sunt rezolvate fie prin compilarea unui set de modele statice interconectate pentru fiecare perioadă, fie prin compilarea unei singure probleme de programare optimă dinamică folosind o procedură de luare a deciziilor în mai multe etape. Problemele programării dinamice includ problemele de găsire în mai multe etape a optimului în plasarea forțelor productive, precum și performanța optimă.

Caracteristici tipice ale problemelor cu mai multe etape.

1. Considerăm un sistem a cărui stare la fiecare pas este determinată de vectorul . O schimbare suplimentară a stării sale depinde numai de această stare și nu depinde de modul în care sistemul a ajuns la ea. Astfel de procese sunt numite procese fără efect secundar.

2. La fiecare pas, se selectează o soluție, sub influența căreia sistemul trece din starea anterioară la una nouă. Această nouă stare este o funcție a stării de la începutul intervalului și a deciziei luate la începutul intervalului, i.e.

3. Actiunea la fiecare pas este asociata cu un anumit castig (venit, profit) sau pierdere (cost), care depinde de starea de la inceputul pasului (etapa) si de decizia luata.

4. Se pot impune restricții asupra vectorilor de stat și de control, a căror unire constituie regiunea soluțiilor fezabile.

5. Este necesar să se găsească un astfel de control admisibil pentru fiecare pas pentru a obține valoarea extremă a funcției de obiectiv pentru toți pașii.

Orice problemă în mai mulți pași poate fi rezolvată în moduri diferite. În primul rând, putem lua în considerare mărimile necunoscute u și găsim extremul funcției obiectiv utilizând una dintre metodele de optimizare existente, adică căutarea tuturor elementelor soluției la toți pașii simultan. Rețineți că această cale nu duce întotdeauna la scop, mai ales când funcția obiectiv este dată sub formă de tabele sau numărul de variabile este foarte mare. A doua modalitate se bazează pe ideea de a realiza optimizarea în etape. Etapatura nu implică izolarea în optimizarea etapelor. Dimpotrivă, controlul la fiecare pas este ales luând în considerare toate consecințele acestuia. De obicei, a doua metodă de optimizare se dovedește a fi mai simplă decât prima, mai ales cu un număr mare de pași. Ideea optimizării graduale, pas cu pas este esența metodei de programare dinamică. Optimizarea unui singur pas este de obicei mai ușoară decât optimizarea întregului proces. Este mai bine să rezolvi o problemă relativ simplă de mai multe ori decât să rezolvi o singură dată una complexă.

La prima vedere, ideea poate părea banală: dacă este dificil să optimizați o problemă complexă, atunci ar trebui să o descompuneți într-o serie de altele mai simple. La fiecare pas, se optimizează o mică problemă, ceea ce nu este dificil. În același timp, principiul programării dinamice nu implică deloc ca fiecare pas să fie optimizat izolat, independent de ceilalți. Dimpotrivă, controlul incremental trebuie ales ținând cont de toate consecințele acestuia.

Putem formula următoarele principii care stau la baza programării dinamice: principiul optimității și principiul imersiunii.

Controlul optim la fiecare pas este determinat de starea sistemului la începutul acestui pas și de obiectivul de control. Sau în formă extinsă: strategia optimă are proprietatea că, oricare ar fi starea inițială și deciziile inițiale, deciziile ulterioare trebuie luate pe baza strategiei optime, ținând cont de starea rezultată din prima decizie. Acest principiu are o interpretare matematică destul de simplă, exprimată în compilarea anumitor relații recurente (ecuații funcționale ale lui R. Bellman).

Natura problemei care permite utilizarea metodei de programare dinamică nu se schimbă atunci când se modifică numărul de pași, adică forma unei astfel de probleme este invariabilă în raport cu . În acest sens, orice proces specific cu un număr dat de pași se dovedește a fi, parcă, cufundat într-o familie de procese asemănătoare acestuia și poate fi considerat din perspectiva unei clase mai largi de probleme.

Implementarea acestor principii garantează că decizia luată la pasul următor va fi cea mai bună în raport cu întregul proces în ansamblu, și nu cu interesele înguste ale acestei etape. O succesiune de soluții pas cu pas conduce la rezolvarea problemei inițiale.

Să dăm o formulare matematică a principiului optimității pentru probleme cu un criteriu de optimitate aditiv (funcție obiectivă separabilă). Pentru simplitate, vom presupune că sunt date stările inițiale și finale ale sistemului. Să notăm prin valoarea funcției de obiectiv în prima etapă în starea inițială a sistemului și în timpul controlului, prin - valoarea corespunzătoare a funcției de obiectiv numai în a doua etapă, ...., cu - în stadiu , ..., prin - la a --a etapă. Este evident că

Este necesar să se găsească controlul optim astfel încât să livreze extremul funcției obiectiv sub constrângeri.

Pentru a rezolva această problemă, o scufundăm într-o familie de altele asemănătoare. Să introducem o notație. Fie, respectiv, domeniile de definire pentru probleme similare la ultima etapă, ultimele două etc.; - domeniul de definire a problemei originale. Să notăm prin

în consecință, valori optime condiționat ale funcției de obiectiv în ultima etapă, ultimele două etc., la ultima etc., în toate etapele.

Să începem de la ultima etapă. Fie stările posibile ale sistemului la începutul etapei. Găsim:

Pentru ultimele două etape obținem:

De asemenea:

…………………….

Expresia (5) este o reprezentare matematică a principiului optimității. Expresia (4) este forma generală de scriere a valorii optime condiționat a funcției scop pentru etapele rămase. Expresiile (1)-(5) se numesc ecuații Bellman funcționale. Natura lor recurentă (de întoarcere) este clar vizibilă, adică. pentru a găsi controlul optim la pași, trebuie să cunoașteți controlul optim condiționat la etapele anterioare etc. Prin urmare, ecuațiile funcționale sunt adesea numite relații Bellman recurente.

Exemplu de rezolvare a problemei

Sarcina

Asociația de producție oferă patru dintre întreprinderile sale membre un împrumut în valoare de 100 de milioane de unități monetare. pentru a extinde producția și a crește producția de produse. Pentru fiecare întreprindere se cunoaște eventuala creștere a producției (în termeni monetari), în funcție de suma alocată acesteia. Pentru a simplifica calculele, sumele alocate sunt multipli de 20 de milioane de unități monetare. În același timp, presupunem că creșterea producției la întreprindere nu depinde de cantitatea de fonduri investite în alte întreprinderi, iar creșterea totală a producției în asociația de producție este egală cu suma creșterilor obținute la fiecare întreprindere. a asociatiei.

Este necesară găsirea unei soluții optime pentru distribuirea creditului între întreprinderi, astfel încât creșterea globală a producției la asociația de producție să fie maximă.

Fonduri alocate, milioane de unități monetare

Companie

№1

№2

№3

№4

Creșterea producției la întreprinderi, milioane de unități monetare.

100

Rezolvarea problemei

Dacă rămâneți fără timp pentru a trimite un test, puteți oricând să comandați o soluție urgentă la probleme folosind metode de soluționare optimă pe site.

Programarea dinamică este o căutare în mai multe etape a soluției optime. Optimizarea unui proces în mai multe etape se bazează pe principiul optimității lui R. Bellman.

Calculele în programarea dinamică sunt efectuate recursiv - soluția optimă pentru o subproblemă este utilizată ca date de intrare pentru a găsi soluția optimă pentru următoarea subproblemă. După rezolvarea ultimei subprobleme, obținem soluția optimă a problemei inițiale.

Fonduri alocate

100

Pasul 1

În conformitate cu schema de calcul a programării dinamice, să luăm în considerare mai întâi cazul, i.e. Să presupunem că toate fondurile disponibile sunt alocate pentru reconstrucția și modernizarea unei întreprinderi. Să notăm cu venitul suplimentar maxim posibil la această întreprindere corespunzător sumei alocate. Fiecare valoare corespunde unei valori foarte specifice (singura) a venitului suplimentar, deci putem scrie ca:

Pasul 2

Lasă acum, adică fondurile sunt distribuite între două întreprinderi. Dacă celei de-a doua întreprinderi i se alocă o sumă, atunci venitul suplimentar din aceasta va fi . Fondurile rămase pentru o altă întreprindere, în funcție de dimensiune (și deci ) vă vor permite să creșteți veniturile suplimentare la valoarea maximă posibilă. În această condiție, venitul suplimentar total la cele două întreprinderi este:

Pasul 3

Lasă acum, adică fondurile sunt distribuite între trei întreprinderi. Dacă celei de-a treia întreprinderi i se alocă o sumă, atunci venitul suplimentar din aceasta va fi . Fondurile rămase, în funcție de mărime (și deci ) vă vor permite să creșteți veniturile suplimentare la valoarea maximă posibilă. În această condiție, venitul suplimentar total la trei întreprinderi este:

Pasul 4

Lasă acum, adică fondurile sunt distribuite între patru întreprinderi. Dacă celei de-a patra întreprinderi i se alocă o sumă, atunci venitul suplimentar din aceasta va fi . Fondurile rămase, în funcție de mărime (și deci ) vă vor permite să creșteți veniturile suplimentare la valoarea maximă posibilă. În această condiție, venitul suplimentar total la patru întreprinderi este:

0 0 0 0 0 20 10 12 12 16 40 31 31 36 37 60 42 43 48 52 80 62 62 67 73 100 76 76 79 85

Răspuns

Planul optim de distribuție pentru 100 de unități de resurse între 4 întreprinderi:

În acest caz, creșterea totală a producției va atinge o valoare maximă de 85.

In medie costul rezolvării unui test este de 700 - 1200 de ruble (dar nu mai puțin de 300 de ruble pentru întreaga comandă). Pretul este foarte influentat de urgenta deciziei (de la o zi la cateva ore). Costul ajutorului online pentru un examen/test este de la 1000 de ruble. pentru rezolvarea biletului.

Puteți pune toate întrebările despre cost direct în chat, după ce ați trimis în prealabil condițiile sarcinii și v-ați informat cu privire la intervalul de timp pentru soluția de care aveți nevoie. Timpul de răspuns este de câteva minute.

Exemple de probleme conexe

Model de bază de gestionare a stocurilor
Folosind exemplul de rezolvare a problemei, se ia în considerare modelul de bază al managementului stocurilor (modelul Wilson). Au fost calculați indicatori de model precum dimensiunea optimă a lotului de comandă, costurile anuale de depozitare, intervalul dintre livrări și punctul de plasare a comenzii.

Problemă de programare cuadratică
Este dat un exemplu de rezolvare a unei probleme de programare pătratică convexă folosind o metodă grafică.

Jocuri de strategie mixte
Conține informații teoretice prezentate într-o formă concisă și accesibilă despre un joc de matrice fără un punct de șa și o metodă de reducere a unei astfel de probleme la o problemă de programare liniară pentru a-și găsi soluția în strategii mixte. Este dat un exemplu de rezolvare a problemei.

ABSTRACT

Introducere

Programare dinamică- o metodă de optimizare adaptată operaţiilor în care procesul decizional poate fi împărţit în etape (etape). Astfel de operații se numesc în mai mulți pași.

Începutul dezvoltării programării dinamice datează din anii 50 ai secolului XX. și este asociat cu numele lui Richard Ernest Bellman.

Dacă modelele de programare liniară pot fi folosite în economie pentru a lua decizii de planificare la scară largă în situații complexe, atunci modelele de programare dinamică sunt folosite pentru a rezolva probleme de o scară mult mai mică:

ü la elaborarea regulilor de gestionare a stocurilor;

ü la distribuirea resurselor de investiții între proiecte alternative;

ü la întocmirea planurilor calendaristice pentru reparațiile curente și majore ale echipamentelor complexe și înlocuirea acestora etc.

1. Formularea generală a problemei de programare dinamică

programarea dinamică a ecuațiilor Bellman

Un proces controlat este considerat, de exemplu, procesul de distribuire a fondurilor între întreprinderi, utilizarea resurselor pe un număr de ani, înlocuirea echipamentelor etc. Ca rezultat al controlului, sistemul (obiectul de control) S este transferat din starea inițială s 0a afirma s n . Lăsați controlul să fie împărțit în n pași, adică decizia se ia secvenţial la fiecare pas, iar controlul care transferă sistemul S din starea iniţială în starea finală este un set de n decizii de management pas cu pas.

Să notăm cu X k decizie de management la pasul k (k=1, 2, …, n). Variabilele X k satisfac unele restricții și în acest sens sunt numite admisibile (X k poate fi un număr, un punct din spațiul n-dimensional sau o caracteristică calitativă).

Fie X=(X 1, X 2, …, X n ) - control care transferă sistemul S din starea s 0a afirma s n . Să notăm cu s k starea sistemului (caracterizată printr-un anumit set de parametri și valorile lor specifice) după pasul k-a de control. Mai mult, starea sistemului s k la sfârșitul pasului k depinde numai de starea anterioară s k-1 și decizia managementului la a k-a pasă X k (adică nu depinde direct de condițiile anterioare și de deciziile de management). Această cerință se numește „nicio consecință” și poate fi exprimată prin următoarele ecuații de stare:

Astfel, obținem o succesiune de stări s0, s1, …, sk-1, sk, …, sn-1, sn. Apoi, procesul de management în n pași poate fi descris schematic după cum urmează:

Fie ca indicatorul de eficiență al pasului k să fie exprimat printr-o funcție:

iar eficiența întregului proces în mai multe etape luat în considerare este următoarea funcție aditivă:

Apoi problema de optimizare pas cu pas (problema de programare dinamică) se formulează astfel: se determină un control admisibil X care transferă sistemul S din starea s0 în starea sn, la care funcția obiectiv Z ia cea mai mare (cea mai mică) valoare.

Problema de programare dinamică are următoarele caracteristici:

Problema de optimizare este interpretată ca un proces de control în n pași.

Funcția obiectiv este egală cu suma funcțiilor obiectiv ale fiecărui pas.

Alegerea controlului la pasul k depinde doar de starea sistemului la acest pas și nu afectează pașii anteriori (fără feedback).

Starea sk după pasul k-a de control depinde doar de starea anterioară sk-1 și de controlul Xk („fără consecințe”).

La fiecare pas, controlul Xk depinde de un număr finit de variabile de control, iar starea sk depinde de un număr finit de parametri.

2. Principiul optimității și ecuațiile Bellman

Principiul optimitățiia fost formulat pentru prima dată de Richard Ernest Bellman în 1953 (așa cum a fost interpretat de E.S. Wentzel):

Oricare ar fi starea sistemului ca urmare a oricărui număr de pași, la pasul următor este necesar să se aleagă controlul în așa fel încât acesta, împreună cu controlul optim la toți pașii următori, să conducă la câștig optim la toți pașii rămași, inclusiv pe acesta.

RE. Bellman a formulat și condițiile în care principiul este adevărat. Cerința principală este ca procesul de control să fie fără feedback, adică. controlul la acest pas nu ar trebui să afecteze pașii anteriori.

Luați în considerare problema generală de programare dinamică prezentată mai sus. La fiecare pas cu excepția ultimului pentru orice stare a sistemului s k-1 decizia managementului X k este necesar să alegeți „cu precauție”, deoarece această alegere afectează starea ulterioară a sistemului sk .

La ultimul pas, pe baza stării sistemului s n-1 decizia managementului X n poate fi planificat local în mod optim, adică bazat numai pe considerentele acestui pas.

Luați în considerare ultimul pas al n-lea:

s n-1 - starea sistemului la începutul pasului a n-a;

s n - starea finală a sistemului;

X n - control la pasul a n-a;

f n (s n-1 , X n ) este funcția obiectivă (recompensă) a pasului a n-a.

Conform principiului optimității, X n trebuie alese astfel încât pentru orice stări ale sistemului s n-1 obțineți optimul funcției obiectiv la acest pas.

Să notăm cu optimul (pentru certitudine vom lua maxim) al funcției obiectiv - un indicator al eficienței pasului a n-a, cu condiția ca la începutul ultimului pas sistemul S să fie într-o stare arbitrară sn-1 , iar la ultimul pas controlul a fost optim.

se numește maximul condiționat al funcției obiectiv la pasul a n-a și este determinat de următoarea formulă:

Maximizarea se realizează peste toate controalele admisibile Xn.

Soluția Xn la care se realizează aceasta depinde și de sn-1 și se numește soluție optimă condiționată la pasul a n-a. Să o notăm prin.

După ce am rezolvat problema de optimizare locală unidimensională folosind ecuația (5), definim două funcții și pentru toate stările posibile sn-1.

Să luăm în considerare o problemă în doi pași: adăugați (n-1) --lea la pasul n-a.

Pentru orice stări sn-2, decizii arbitrare de management Xn-1 și control optim la pasul a n-a, valoarea funcției obiectiv la ultimii doi pași se calculează prin formula:

Conform principiului optimității lui Bellman pentru orice s n-2 soluţia trebuie aleasă astfel încât, împreună cu controlul optim la ultimul (a n-a) pas, să conducă la optimul funcţiei obiectiv la ultimele două etape. Prin urmare, este necesar să se găsească optimul de exprimare (6) pentru toate deciziile de management admisibile Xn-1 :

Se numește maxim condiționat al funcției obiectiv sub control optim la ultimii doi pași. Trebuie remarcat faptul că expresia dintre paranteze în formula (6) depinde numai de sn-2 și Xn-1, deoarece sn-1 poate fi găsit din ecuația stărilor (1) cu:

Controlul corespunzător Xn-1 la pasul (n-1) este notat cu și se numește control optim condiționat la pasul (n-1).

Optimile condiționale ale funcției obiectiv sunt determinate în mod similar pentru controlul optim la (n-k+1) pași, începând de la k-a până la sfârșit, cu condiția ca la începutul k-a pas sistemul să fie în starea sk -1:

Controlul Xk la pasul k, la care se atinge maximul conform (8), este notat și numit control optim condiționat la pasul k.

Ecuațiile (5) și (8) se numesc ecuații Bellman recurente (schemă inversă). Procesul de rezolvare a acestor ecuații se numește optimizare constrânsă.

Ca rezultat al optimizării condiționate, se obțin două secvențe:

, …, - maxime condiționale ale funcției obiectiv la ultimul, ultimii doi, …, la n trepte;

, …, - controale optime condiționate la a n-a, (n-1) - a, …, la primele etape.

Folosind aceste secvențe, putem găsi o soluție la problema de programare dinamică dată n și s0:

Ca rezultat, obținem soluția optimă a problemei de programare dinamică: .

Folosind un raționament similar, putem construi o schemă de optimizare condiționată directă:

Soluția optimă a problemei în acest caz se găsește conform următoarei scheme:

Astfel, construirea unui model de programare dinamică și rezolvarea unei probleme pe baza acestuia poate fi în general reprezentată în următorii pași:

Alegeți o metodă de împărțire a procesului de management în pași.

Definiți parametrii de stare s k și variabilele de control X k La fiecare pas se scriu ecuații de stare.

3. Introduceți funcțiile obiectiv ale pasului k-lea și funcția obiectiv totală, precum și optima condiționată și controlul optim condiționat la pasul k-a ().

Ecuațiile recurente Bellman sunt scrise în conformitate cu schema inversă sau directă și, după efectuarea optimizării condiționate, se obțin două secvențe: () și ().

Se determină valoarea optimă a funcției obiectiv și soluția optimă.

3. Problema de alocare a resurselor

Există o anumită cantitate de resurse s0 care trebuie distribuită între n entități de afaceri pentru activitățile curente în perioada analizată (lună, trimestru, semestru, an etc.) pentru a obține un profit maxim total. Mărimea investițiilor în resurse xi (;) în activitățile fiecărei entități economice este multiplu al unei anumite valori h. Se știe că fiecare entitate economică, în funcție de volumul fondurilor utilizate xi pentru perioada analizată, aduce un profit în valoare de fi(xi) (nu depinde de investiția de resurse în alte entități economice).

Să ne imaginăm procesul de distribuție a resurselor între entitățile de afaceri ca un proces de management în n pași (numărul pasului coincide cu numărul condiționat al entității de afaceri). Fie sk() un parametru de stare, i.e. suma fondurilor disponibile după pasul k pentru distribuire între restul (n - k) entități de afaceri. Atunci ecuațiile de stare pot fi scrise sub următoarea formă:

Sa introducem in considerare functia - profitul total conditionat optim primit de la k-a, (k+1) --a, ..., n-a entitate economica, daca resurse in valoare de sk-1 () au fost repartizate optim între ele. Setul de decizii de management posibile privind mărimea resurselor alocate la pasul k-a poate fi prezentat astfel: .

Apoi ecuațiile recurente ale lui R.E. Bellman (diagrama inversă) va arăta astfel:

Exemplu. Există o anumită cantitate de resurse s0=100, care trebuie distribuită între n=4 entități de afaceri pentru activitățile curente în perioada analizată (lună) pentru a obține profitul maxim total. Mărimea investiției de resurse xi (;) în activitățile fiecărei entități economice este un multiplu al valorii h=20 și este specificată de vectorul Q. Se știe că fiecare entitate economică, în funcție de volumul fondurilor utilizate xi pentru perioada analizată, aduce un profit în valoare de fi(xi) () (nu depinde de investiția de resurse în alte entități economice):

Este necesar să se determine câte resurse trebuie alocate fiecărei întreprinderi pentru ca profitul total să fie cel mai mare.

Soluţie.Să creăm ecuațiile recurente ale lui Bellman (schema inversă):

Să determinăm maximele condiționate în conformitate cu (13), rezultatele calculului sunt prezentate în Tabelul 1.

Tabelul 1. Calculul optimelor condiționale

s k-1 X k s k k=3k=2k=1 123456789101112000000000000200200+20=20 22 200+22=22 2200+22=22 22020022+0=22 17+0=1714+0=14400400+33=33 42 200+42=42 4200+42=42 420202022+20=42 17+22=3914+22=3640021+0=2120+0=2026+0=26600600+46=46 55 200+55=55 59 20 0+59=59 590204022+33=5517+42=59 14+42=56402021+20=4120+22=4226+22=4860037+0=3732+0=3235+0=35800800+30=30 68 200+68=68 72 200+72=72 73 20206022+46=6817+55=7214+59=73 404021+33=5420+42=6426+42=68602037+20=5732+22=5435+22=5780067+0=6761+0=6152+0=5210001000+42=42 87 800+87=87 8700+87=87 870208022+30=5217+68=8514+72=86406021+46=6720+55=7526+59=85604037+33=7032+42=7435+42=77802067+20=87 61+22=8352+22=74100058+0=5872+0=7261+0=61Pe baza rezultatelor optimizării condiționate, vom determina alocarea optimă a resurselor:

Astfel, alocarea optimă a resurselor este:

care va asigura cel mai mare profit în valoare de 87 de unităţi convenţionale. den. unitati

Răspuns: alocarea optimă a resurselor: care asigură cel mai mare profit de 87 de unități convenționale. den. unitati

Concluzie

Programarea dinamică este o zonă de programare matematică care include un set de tehnici și instrumente pentru găsirea soluției optime, precum și optimizarea fiecărui pas din sistem și dezvoltarea unei strategii de control, adică procesul de control poate fi reprezentat ca un proces în mai multe etape. Programarea dinamică, folosind planificarea pas cu pas, permite nu numai simplificarea soluționării problemei, ci și rezolvarea acelor probleme care nu pot fi aplicate folosind metode de analiză matematică. Simplificarea soluției se realizează prin reducerea semnificativă a numărului de opțiuni studiate, deoarece în loc să rezolve o singură problemă complexă multivariată, metoda de planificare pas cu pas presupune rezolvarea de mai multe ori a unor probleme relativ simple. Atunci când planificăm un proces pas cu pas, pornim de la interesele întregului proces în ansamblu, adică. Atunci când luați o decizie într-o anumită etapă, este întotdeauna necesar să aveți în vedere scopul final. Cu toate acestea, programarea dinamică are și dezavantajele sale. Spre deosebire de programarea liniară, în care metoda simplex este universală, nu există o astfel de metodă în programarea dinamică. Fiecare sarcină are propriile sale dificultăți și în fiecare caz este necesar să se găsească cea mai potrivită metodă de rezolvare. Dezavantajul programării dinamice este și complexitatea rezolvării problemelor multidimensionale. O problemă de programare dinamică trebuie să îndeplinească două condiții. Prima condiție este de obicei numită condiția de absență a efectului secundar, iar a doua este condiția de aditivitate a funcției obiective a problemei. În practică, există probleme de planificare în care factorii aleatori joacă un rol semnificativ, influențând atât starea sistemului, cât și câștigul. Există o diferență între problemele de programare dinamică deterministă și stocastică. Într-o problemă deterministă, controlul optim este unic și este specificat în prealabil ca un program rigid de acțiuni. Într-o problemă stocastică, controlul optim este aleatoriu și este selectat în timpul procesului în sine, în funcție de situația aleatorie. Într-o schemă deterministă, parcurgând procesul în etape de la capăt la început, există și o serie întreagă de controale optime condiționate în fiecare etapă, dar dintre toate aceste controale, doar unul a fost efectuat în cele din urmă. Nu este cazul într-o schemă stocastică. Fiecare dintre controalele optime condiționate poate fi efectiv implementat dacă cursul anterior al procesului aleatoriu conduce sistemul la starea corespunzătoare. Principiul optimității stă la baza soluționării pas cu pas a problemelor de programare dinamică. Reprezentanții tipici ai problemelor economice ale programării dinamice sunt așa-numitele probleme de producție și stocare, probleme de distribuție a investițiilor de capital, probleme de programare a producției și altele. Problemele de programare dinamică sunt utilizate în planificarea activităților unei întreprinderi, ținând cont de modificările nevoii de produse în timp. În repartizarea optimă a resurselor între întreprinderi în direcție sau timp. Descrierea caracteristicilor programării dinamice și a tipurilor de probleme care pot fi formulate în cadrul acesteia trebuie neapărat să fie foarte generală și oarecum vagă, deoarece există o varietate imensă de probleme diferite care se încadrează în schema de programare dinamică. Doar studierea unui număr mare de exemple oferă o înțelegere clară a structurii programării dinamice.

Bibliografie

Modele și metode economice și matematice. Programare liniară: un manual pentru studenții specialităților economice / Compilat de: Smirnov Yu.N., Shibanova E.V., Naberezhnye Chelny: Editura KamPI, 2004, 81 p.
Cercetare operațională în economie: manual. manual pentru universități / N.Sh. Kremer, B.A. Putko, I.M. Trishin, M.N. Friedman; Ed. prof. N.Sh. Kremer. - M.: UNITATEA, 2000. - 407 p.
Kuznetsov A.V. şi altele Matematică superioară: Mat. programare: Manual/A.V. Kuznetsov, V.A. Sakovich, N.I. Rece; Sub general ed. A.V. Kuznetsova. - Mn.: Mai sus. şcoală, 1994. - 286 p.: ill.

Îndrumare

Ai nevoie de ajutor pentru a studia un subiect?

Specialiștii noștri vă vor consilia sau vă vor oferi servicii de îndrumare pe teme care vă interesează.
Trimiteți cererea dvs indicând subiectul chiar acum pentru a afla despre posibilitatea de a obține o consultație.

Metoda de programare dinamică vă permite să rezolvați cu succes multe probleme economice (vezi, de exemplu,). Să luăm în considerare una dintre cele mai simple astfel de probleme. Avem la dispozitie o rezerva de fonduri (resurse) K, care trebuie distribuita intre intreprinderi. Fiecare dintre întreprinderi, atunci când unele fonduri sunt investite în ea, generează venituri care depind de , adică reprezentând un fel de funcție. Toate funcțiile sunt date (desigur, aceste funcții sunt nedescrescătoare).

Întrebarea este cum ar trebui să fie distribuite fondurile K între întreprinderi, astfel încât acestea să genereze venituri maxime?

Această problemă este ușor de rezolvat folosind metoda de programare dinamică. Deși în formularea sa nu conține nicio mențiune despre timp, este totuși posibilă desfășurarea mentală a operațiunii de distribuire a fondurilor într-o anumită secvență, considerând că primul pas este investirea fondurilor în întreprindere, al doilea - la etc.

Sistemul gestionat S în acest caz este fondurile sau resursele care sunt distribuite. Starea sistemului S înainte de fiecare pas este caracterizată de un număr S - stocul disponibil de fonduri neinvestit încă. În această sarcină, „managementul în etape” reprezintă fondurile alocate întreprinderilor. Este necesar să se găsească controlul optim, adică un astfel de set de numere pentru care venitul total este maxim:

Să rezolvăm această problemă mai întâi în formă generală, formulă și apoi pentru date numerice specifice. Să găsim pentru fiecare pas câștigul optim condiționat (de la acest pas până la final), dacă am abordat acest pas cu o rezervă de fonduri S. Să notăm câștigul optim condiționat , și controlul optim condiționat corespunzător - fondurile investite în intreprinderea -

Să începem optimizarea de la ultimul pas. Să abordăm acest pas cu un sold de fonduri S. Ce ar trebui să facem? Evident, investiți întreaga sumă S în întreprindere. Prin urmare, controlul optim condiționat la pasul al treilea: acordați ultimei întreprinderi toate fondurile disponibile S, adică.

și câștigul optim condiționat

Având în vedere un întreg interval de valori ale lui S (localizându-le destul de aproape), vom ști pentru fiecare valoare a lui S. Ultimul pas este optimizat.

Să trecem la penultimul pas. Să o abordăm cu o rezervă de fonduri S. Să notăm câștigul optim condiționat la ultimii doi pași: (care este deja optimizat). Dacă alocam fonduri întreprinderii la pas, atunci vor rămâne pentru ultimul pas câștigurile noastre la ultimii doi pași vor fi egale cu

și trebuie să găsiți unul la care acest câștig să fie maxim:

Semnul înseamnă că valoarea maximă este preluată peste toate valorile posibile (nu putem pune mai mult de S), din expresia dintre paranteze. Acest maxim este câștigul optim condiționat pentru ultimii doi pași, iar valoarea la care se atinge acest maxim este controlul optim condiționat la pas.

iar controlul optim condițional corespunzător este valoarea la care se atinge acest maxim.

Continuând în acest fel, vom ajunge în sfârșit la întreprindere. Aici nu va fi nevoie să variem valorile lui S; știm cu siguranță că stocul de fonduri înainte de primul pas este egal cu K:

Deci, a fost găsit câștigul (venitul) maxim din toate întreprinderile. Acum nu mai rămâne decât să „citești recomandările”. Valoarea la care se atinge maximul (13,4) este controlul optim la primul pas.

După ce investim aceste fonduri în prima întreprindere, le vom rămâne. „Citind” recomandarea pentru această valoare a lui S, alocăm suma optimă de fonduri celei de-a doua întreprinderi: și așa mai departe până la sfârșit.

Acum să rezolvăm un exemplu numeric. Stocul inițial de fonduri (unități standard) și este necesar să îl distribuiți în mod optim între cinci întreprinderi Pentru simplitate, presupunem că sunt investite doar sume întregi de fonduri. Funcțiile venitului sunt date în Tabelul 13.1.

Tabelul 13.1

În fiecare coloană, pornind de la o anumită sumă de investiție, veniturile încetează să crească (în realitate, aceasta corespunde faptului că fiecare întreprindere este capabilă să „adopte” doar o cantitate limitată de fonduri).

Să efectuăm optimizarea condiționată așa cum este descris mai sus, pornind de la ultimul pas. De fiecare dată când ne apropiem de pasul următor, având o rezervă de fonduri?, încercăm să alocăm una sau alta sumă de fonduri pentru acest pas, luăm câștigurile la acest pas conform tabelului 13.1, le adăugăm cu câștigurile deja optimizate la toate ulterioare. pași până la final (ținând cont că avem deja mai puține fonduri, doar pentru suma de fonduri pe care am alocat-o) și găsim investiția la care această sumă atinge maximul. Această investiție este controlul optim condiționat la acest pas, iar maximul în sine este câștigul optim condiționat.

Tabelul 13.2 prezintă rezultatele optimizării condiționate pentru toți pașii. Tabelul este construit după cum urmează: prima coloană prezintă valorile stocului de fonduri S cu care abordăm acest pas. Tabelul este împărțit în continuare în cinci perechi de coloane, corespunzătoare numărului pasului.

Tabelul 13.2

Prima coloană a fiecărei perechi dă valoarea controlului optim condiționat, a doua - câștigul optim condiționat. Tabelul este umplut de la stânga la dreapta, de sus în jos. Decizia la al cincilea - ultimul - pas este forțată: toate fondurile sunt alocate; La toți ceilalți pași, soluția trebuie optimizată. Ca urmare a optimizării secvențiale a pasilor 5, 4, 3, 2 și 1, vom primi o listă completă a tuturor recomandărilor pentru controlul optim și câștigul optim necondiționat W pentru întreaga operațiune - în acest caz este egal cu 5,6 . În ultimele două coloane din Tabelul 13.2, este completat un singur rând, deoarece știm exact starea sistemului înainte de începerea primului pas: . Comenzile optime la toate etapele sunt evidențiate cu un cadru. Astfel, am primit concluzia finală: trebuie să alocăm două unități din zece primei întreprinderi, cinci unități celei de-a doua, două celei de-a treia, niciuna celei de-a patra și o unitate celei de-a cincea. Cu această distribuție, venitul va fi maxim și egal cu 5,6.

Trimiteți-vă munca bună în baza de cunoștințe este simplu. Utilizați formularul de mai jos

Studenții, studenții absolvenți, tinerii oameni de știință care folosesc baza de cunoștințe în studiile și munca lor vă vor fi foarte recunoscători.

postat pe http://www.allbest.ru/

Problemă de alocare a resurselor folosind metoda de programare dinamică

Pentru a extinde capacitatea de producție a trei întreprinderi A, B și C, se alocă un anumit număr de unități de energie electrică suplimentară în valoare de x 0 = 8 unități. Electricitatea poate fi eliberată sub formă de 1, 2, 3, 4, 5, 6, 7 și 8 unități. Investind x i unități de energie electrică în dezvoltarea i-a întreprindere, puteți primi venituri de la i unități la întreprindere. Există diferite opțiuni x i (k) pentru alocarea de energie electrică suplimentară. Ele aduc venituri la i (k), k=1,n. Opțiunile posibile pentru dezvoltarea întreprinderilor sunt prezentate în Tabelul 1. Venitul total pentru toate întreprinderile ar trebui să fie maxim, adică y=? y i (k)>max

Masa 1. Opțiuni de dezvoltare a întreprinderii

Opțiunea k	Întreprinderea A	Întreprinderea B	Întreprinderea C

Matematic punerea în scenă sarcini:

y=? la i (k)> max

?X i (k)?x 0

Soluţie:

Să începem să luăm în considerare procedura de rezolvare a problemei în discuție din ultima etapă (3 pași) (Tabelul 2), la care investițiile sunt alocate întreprinderii C. Se caută controlul optim condiționat în etapa a treia ca soluție a ecuației

g C(S2)=max kfc, xC(k)?S2, k=1,2,3,4

Masa 2. Soluții optime condiționat (pasul 3)

Stat		Control

Există patru posibilități de investire a fondurilor - controale în patru etape x C (1) = 0 unități, x C (2) = 1 unitate, x C (3) = 2 unități, x C (4) = 3 unități. și nouă stări teoretic posibile ale sistemului S 2 premergătoare alocării de fonduri către întreprinderea C - volumele de investiții nedistribuite la etapa a 3-a: 0,1,2,3,4,5,6,7,8.

Să presupunem că sistemul a fost în starea S 2 =2 Atunci, pentru controlul pasului x C (2) = 1, venitul lui C (2) va fi egal cu 3 unități. (Tabelul 3) și controlul pas x C (3) = 2 vor fi optime pentru această stare, dând un câștig maxim condiționat g c (S 2) = 5. Dacă sistemul a fost în starea S 2 = 3, atunci toate comenzile pasului sunt permise: x C (1) = 0 unități, x C (2) = 1 unitate, x C (3) = 2 unități, x C (4) = 3 unități, iar controlul optim va fi x C (4) = 3, care oferă un câștig maxim condiționat g c (S 2) = 6.

Tabelul 3 distribuția dinamică a investițiilor în programare

Toate stările posibile care preced etapa a 3-a sunt completate în mod similar. Valorile optime ale indicatorilor sunt evidențiate cu caractere aldine în tabele.

În continuare, în același mod este considerată a doua etapă (Tabelul 4), care constă în alocarea investițiilor către întreprinderea A. În a doua etapă, câștigul total este suma câștigurilor primite în a treia și a doua etapă și este dat prin raportul:

g A (S 1)=max k f A +g c], x A (k)?S 1, k=1,2,3,4

Astfel, pentru starea S 1 =3 cu control în trepte x A (2) = 1 se obține:

g A (S 1)=max k f A +g c ]

Max k 4+g c =4+5=9, unde găsim din tabelul 1, și g c din tabelul 3. Toate stările sunt completate în mod similar.

Masa 4. Soluții optime condiționat (pasul 2)

Stat	f A +g c	Control

Aici apar situații în care soluția optimă nu va fi singura Astfel, în starea S 1 = 3, controalele pas x A (2) = 1 și x A (3) = 2 vor fi optime condiționat, dând același lucru. câștig g A (S 1)=9

Masa 5. Soluții optime necondiționat (pasul 1)

La prima etapă (Tabelul 5) - alocarea investițiilor către întreprinderea B - există o singură stare anterioară a sistemului, corespunzătoare stării inițiale S 0 =8. Câștigul optim necondiționat este determinat de expresia:

y * = g B (S 0)= max k (f A +g A) x în (k)?S 0 =x 0, k=1,2,3,4,5

Controalele optime necondiționat care asigură un venit maxim pot fi diferite.

Schema de găsire a tuturor opțiunilor optime pentru distribuirea investițiilor între întreprinderi (Tabelul 6) este prezentată în Figura 1.

Masa 6. Distribuția optimă a investițiilor.

Figura 1. Schema de repartizare optimă a investițiilor între întreprinderi

Concluzie: având în vedere problema alocării resurselor prin metoda de programare dinamică, au fost identificate două opțiuni pentru alocarea optimă a resurselor.

Postat pe Allbest.ru

...

Documente similare

Caracteristici generale și indicatori de performanță economică a celor trei întreprinderi studiate. Rezolvarea problemei planificării producției, precum și a distribuției investițiilor folosind programare liniară și dinamică. Analiza comparativă a rezultatelor.

lucrare de curs, adăugată 25.04.2015

Procese în mai multe etape în probleme dinamice. Principiul optimității și relațiilor de recurență. Metoda de programare dinamică. Probleme de alocare optimă a fondurilor pentru extinderea producției și planificarea programului de producție.

lucrare de curs, adăugată 30.12.2010

Metoda de programare dinamică și etapele sale principale. Strategia optimă de înlocuire a echipamentelor. Minimizarea costurilor pentru construcția și funcționarea întreprinderilor. Distribuția optimă a resurselor în STROYKROVLYA LLC și investiții în PKT Khimvolokno.

lucru curs, adăugat 01.08.2015

Model matematic de planificare a producției. Intocmirea unui plan optim pentru activitatile de productie ale unei intreprinderi folosind metoda programarii liniare. Găsirea modului optim de distribuire a resurselor financiare în perioada de planificare.

teză, adăugată 08.07.2013

Calculul costurilor de transport folosind metoda costului minim. Găsirea egalității optime condiționate în procesul de programare dinamică. Ecuația algebrică liniară Kolmogorov pentru timpul mediu de funcționare fără defecțiuni a unui sistem redundant.

lucrare de curs, adăugată 14.01.2011

Metoda grafica de rezolvare a problemei de optimizare a proceselor de productie. Aplicarea unui algoritm simplex pentru a rezolva o problemă de management al producției optimizată din punct de vedere economic. Metodă de programare dinamică pentru selectarea profilului de traseu optim.

test, adaugat 15.10.2010

Planul optim de repartizare a fondurilor între întreprinderi. Elaborarea unui plan pentru fiecare întreprindere în care rentabilitatea investiției va fi cea mai mare. Utilizarea metodelor de programare liniară și dinamică.

lucrare curs, adaugat 16.12.2013

Trăsături caracteristice ale problemelor de programare liniară. Formularea generală a problemei de planificare a producţiei. Construirea unui model matematic de distribuție a resurselor companiei. Analiza de sensibilitate a soluției optime. Întocmirea unui raport de sustenabilitate.

prezentare, adaugat 12.02.2014

Găsirea portofoliului optim de valori mobiliare. Revizuirea metodelor de rezolvare a problemei. Construirea unui model matematic. Problemă de programare a conului. Dependența vectorului de distribuție a capitalului inițial de unul dintre parametrii inițiali.

teză, adăugată 02.11.2017

Model de programare dinamică. Principiul optimității și ecuația Bellman. Descrierea procesului de modelare și construire a unei scheme de programare dinamică computațională. Problema minimizării costurilor de construcție și exploatare a întreprinderilor.

Lucrări de laborator

Informatică, cibernetică și programare

Fonduri X alocate căreia întreprindere aduce profit la sfârșitul anului. Funcțiile sunt prezentate într-un tabel: X f1X f2X f3X f4X 1 8 6 3 4 2 10 9 4 6 3 11 11 7 8 4 12 13 11 13 5 18 15 18 16 Determinați câți bani trebuie alocați fiecărei întreprinderi, astfel încât că profitul total este egal cu suma profiturilor primite de la fiecare întreprindere a fost cea mai mare. Să fie suma de fonduri alocată cărei întreprinderi. Ecuațiile de la al m-lea pas îndeplinesc condiția: fie nu alocăm nimic cărei întreprinderi: fie nu mai mult de atât...

Lucrări de laborator 4_2. Rezolvarea problemei alocării resurselor folosind metoda de programare dinamică.

Scopul lucrării explorați capacitățile procesorului de masă MS Excel pentru a rezolva problema alocării resurselor limitate folosind metoda de programare dinamică.

Informații teoretice scurte

Construirea unui model de programare dinamică (DP) și aplicarea metodei DP pentru a rezolva problema se rezumă la următoarele:

alegeți o metodă de împărțire a procesului de management în pași;
definiți parametrii de stare și variabilele de control X k la fiecare pas;
notează ecuațiile de stare;
introduce funcții obiective k pasul și funcția obiectiv total;
introduceți în considerare maxime (minime) condiționate și control optim condiționat asupra pasul k: .
Notați DP principal pentru circuitul de calculEcuații Bellmanpentru si conform regulii:

Ecuațiile Bellman se rezolvă secvențial (optimizare condiționată) și se obțin două secvențe de funcții.
După efectuarea optimizării condiționate, se obține soluția optimă pentru o anumită stare:

a) și

b) de-a lungul lanţului control optim (soluţie).

Enunțarea problemei de programare dinamică în formă generală.

Sarcina . Activitățile a patru întreprinderi industriale sunt planificate pentru anul viitor. Fonduri inițiale: USD Valoarea investiției în fiecare întreprindere este un multiplu de 1 unitate convențională. Facilităţi X, alocat k

f 1 (X)	f2(X)	f 3 (X)	f 4 (X)

Determinați câți bani trebuie alocați fiecărei întreprinderi, astfel încât profitul total (egal cu suma profiturilor primite de la fiecare întreprindere) să fie cel mai mare.

Soluţie. Fie suma de fonduri alocate k -a întreprindere. Profitul total este egal. Variabile X satisface restricţiile: . Este necesar să se găsească variabile care să satisfacă aceste restricții și să maximizeze funcția Z.

Diagrama soluției problema folosind metoda DP are următoarea formă: procesul de rezolvare a repartizării fondurilor poate fi considerat ca un proces în 4 etape, numărul pasului coincide cu numărul întreprinderii; alegerea ecuaţiilor variabilelor pe 1, 2, 3, 4 pași în consecință; - starea finală a procesului de distribuție este egală cu zero, deoarece toate fondurile trebuie investite în producție,=0 .

Ecuațiile de stare și schema de distribuție pot fi reprezentate astfel:

Aici - parametrul de stare suma de fonduri rămase după k -a treaptă, adică fonduri care rămân de distribuit între restul (4- k ) întreprinderi.

Să introducem în considerare o funcție - profitul optim condiționat primit de la i-a, ( k +1 )a, ..., a 4-a întreprinderi, dacă fondurile au fost repartizate optim între ele). Ecuațiile de la pasul a treia îndeplinesc condiția: (sau k Nu alocăm nimic celei de-a --a întreprindere: fie nu mai mult decât pentru ceea ce avem pasul al-lea :).

Ecuațiile lui Bellman au forma:

Ecuațiile sunt rezolvate prin optimizarea secvențială a fiecărui pas.

Pasul 4 Toate fondurile rămase la pasul 4 ar trebui investite în a 4-a întreprindere, deoarece, conform tabelului, profiturile cresc monoton. În acest caz, pentru valorile posibile obținem:

Pasul 3 . Facem ipoteze cu privire la soldul fondurilor până la a treia etapă: poate lua valori 0,1,2,3,4,5 (=0, dacă toate fondurile sunt date întreprinderii 1 și 2 etc.). În funcție de aceasta, selectăm și comparăm valorile sumei pentru diferite valori la valori fixe. Pentru fiecare, maximul acestor valori este profitul optim conditionat obtinut cu repartizarea optima a fondurilor intre intreprinderile a 3-a si a 4-a. Valorile obținute pentru sunt date în tabelul din coloanele 5 și, respectiv, 6.

S k-1	k =3	k =2	k =1
	f3 (X3)+	f2 (X2)+	f1 (X1)+


	0+4=4 3+0=3	0+4=4 6+0=6	0+6=6 8+0=8
	0+6=6 3+4=7 4+0=4	0+7=7 6+4=10 9+0=9	0+10=10 8+6=14 10+0=10
	0+8=8 3+6=9 4+4=8 7+0=7	0+9=9 6+7=13 9+4=13 11+0=11	0+13=13 8+10=18 10+6=16 11+0=11
	0+13=13 3+8=11 4+6=10 7+4=11 11+0=11	0+13=13 6+9=15 9+7=16 11+4=15 13+0=13	0+16=16 8+13=21 10+10=20 11+6=17 12+0=12
	0+16=16 3+13=16 4+8=12 7+6=13 11+4=15 18+0=18	0+18=18 6+13=19 9+9=18 11+7=18 13+4=17 15+0=15	0+19=19 8+16=24 10+13=23 11+10=21 12+6=18 18+0=18

2 pas k =2. Pentru toate valorile posibile, valorile pentru și sunt în coloanele 8 și, respectiv, 9; primii termeni din coloana 7 valorile sunt preluate din condiție, al doilea termeni sunt preluați din coloana 5 când.

1 pas . Optimizarea condiționată se realizează în tabelul de la k =1 pentru.

Dacă, atunci=5; profitul primit de la patru întreprinderi, cu condiția ca = 5 fonduri între celelalte trei întreprinderi să fie repartizate optim, este egal cu.

Dacă, atunci=4; profitul total, cu condiția ca = 4 fonduri între celelalte trei întreprinderi să fie repartizate optim, este egal cu.

În mod similar, când, și;

Când, și;

Comparând valorile obţinute, obţinem la.

Calculând, obținem, iar din tabelul din coloana 9 găsim. În continuare găsim, iar în coloana 6. În sfârșit, și. Soluție optimă.

Răspuns. Profitul total maxim este de 24 USD. cu condiția ca unei întreprinderi să i se aloce 1 USD; A 2-a întreprindere i s-au alocat 2 USD; a 3-a întreprindere - 1 USD; A patra întreprindere - 1 USD

Implementarea sarcinii în MS Excel

Introducerea datelor inițiale în tabel este prezentată în Fig. 1.

Fig.1. Introducerea datelor sursă în celulele foii de lucru MS Excel

2. Ordinea de completare a celulelor tabelului:

1). La celula E 15 introduceți formula INDEX($B$3:$F$8,MATCH($C15,$B$3:$B$8),G$12+1) și copiați formula în intervalul de celule cu E 15 până la E 35.

2). În celula F 15 introduceți formula

INDEX($B$3:$F$8,MATCH($D15,$B$3:$B$8),5) și copiați formula în intervalul de celule cu F 15 până la F 35.

3). În celula G 15 introduceți formula E 15+ F 15 și copiați formula în intervalul: G 15 - G 35.

4). Găsim valoarea maximă pentru fiecare stare de la 0 la 5, în acest scop în celulă H 15 introduceți formula MAX(G15); după introducerea unei formule într-o celulă H 16 trebuie să schimbați intervalul de la G 16 până la G 16: G 17, etc. de-a lungul întregii coloane până la celulă H 30 (Fig. 2a).

3. Găsiți valoarea de control care corespunde valorii maxime a funcției pentru aceasta, introduceți celula; eu 15 să introducem formula INDEX($ C 15: G 15; Potrivire (H 15; G 15;0);1), copiați formula în celulă eu 16 și crește intervalul, rezultând celulă eu 16 obținem: INDEX($ C 16: G 17; MECI (H 16; G 16: G 17;0);1). Apoi, copiați formula în celule I 18, I 21, I 25, I 30 , crescând treptat intervalul (Fig. 2b)

Fig.2a. Tip de fișă de lucru cu formule, k =3.

Fig.2b (partea dreaptă a foii de lucru cu formule, k =3

Ca rezultat obținem:

Orez. 3 . Rezultatul primului pas ( k =3).

4. Selectați un interval E 15:I 35, executați comanda Copie J 15 și executați comanda Inserați .

5. Să schimbăm formula funcției. La celule K 15, K 16, K 18, K 21, K 25, K 30 introducem, respectiv, valorile maxime ale pasului anterior situate în celule H 15, H 16, H 18, H 21, H 25, H 30. În celulele rămase plasăm valorile în aceeași coloană și corespunzătoare celor anterioare S k . :

La celula K 17 copiați valorile celulei K15;

în celulele K19 și K20 valorile K16 și K17;

în K22:K24 valorile K18:K20;

în K26:K29 valorile K21:K24;

în K31:K35 valorile K25:K29;

Ca rezultat obținem:

Fig.4. Rezultatul celui de-al doilea pas ( k =2).

6. Selectați un interval de celule J15:N 35, executați comanda Copie , plasați cursorul în celulă O 15, executați comanda Introduce . Ca urmare, obținem un tabel completat cu o soluție pt k =1 (Fig.5)

7. Să explicăm rezultatele obţinute: la. Calculând, obținem, iar din tabelul din coloana 12 găsim. În continuare determinăm, iar din coloana 6. În sfârșit, și. Astfel, valoarea optimă și valoarea funcției este de 24 cu, ceea ce este în concordanță cu datele obținute manual.

Fig.6. Rezultatul celui de-al treilea pas ( k =1).

Exerciții de control. Opțiuni.

1. Activitățile a patru întreprinderi industriale sunt planificate pentru anul viitor. Fonduri inițiale USD Valoarea investiției în fiecare întreprindere este un multiplu de 1 USD. Facilităţi X, alocat k -a intreprindere (), aduce profit la sfarsitul anului. Funcțiile sunt specificate într-un tabel:

f 1 (X)	f2(X)	f 3 (X)	f 4 (X)

Determinați câți bani trebuie alocați fiecărei întreprinderi, astfel încât profitul total să fie cel mai mare.

2. Activitățile a trei întreprinderi industriale sunt planificate pentru anul viitor. Fonduri inițiale: USD Valoarea investiției în fiecare întreprindere este un multiplu de 1 USD. Facilităţi X, alocat k -a intreprindere (), aduce profit la sfarsitul anului. Funcțiile sunt specificate într-un tabel:

f 1 (X)	f2(X)	f 3 (X)