Definiția corectă a conceptului de cercetare operațională este: Subiectul și sarcinile cercetării operaționale

1. Concepte de bază ale AI

ȘI DESPRE – disidență științifică, angajată în dezvoltarea și aplicarea practică a metodelor pentru cel mai eficient management al diferitelor sisteme organizaționale.

IO include următoarele secțiuni:

1) program matematic. (justificarea planurilor, programelor de activitate economică); cuprinde secțiuni: program liniar, program neliniar, program dinamic

2) teoria cozilor, bazată pe teoria proceselor aleatorii;

3) teoria jocurilor, care permite justificarea deciziilor luate în condițiile unei informații incomplete.

Atunci când se rezolvă o problemă specifică de control, utilizarea metodelor AI implică:

Construirea de modele economice și matematice pentru probleme decizionale în situații complexe sau în condiții de incertitudine;

Studierea relațiilor care determină ulterior luarea deciziilor și stabilirea criteriilor de performanță care să permită evaluarea avantajului unui anumit curs de acțiune.

Concepte de bază și definiții ale IO.

Operațiune – orice activitate controlată care vizează atingerea unui scop. Rezultatul operațiunii depinde de metoda de implementare a acesteia, de organizare, în caz contrar - de alegerea anumitor parametri. O operațiune este întotdeauna un eveniment controlat, adică depinde de noi cum să alegem niște parametri care îi caracterizează organizarea. „Organizare” aici este înțeleasă în sensul larg al cuvântului, inclusiv ansamblul mijloacelor tehnice utilizate în operațiune.

Orice alegere specifică a parametrilor este numită decizie . Deciziile pot fi de succes și nereușite, rezonabile și nerezonabile. Optimal luați în considerare acele soluții care, dintr-un motiv sau altul, sunt preferabile altora. Sarcina principală a cercetării operaționale este justificarea cantitativă preliminară a soluțiilor optime.

Model de operare – aceasta este o descriere destul de precisă a operației folosind aparate matematice (diferite tipuri de funcții, ecuații, sisteme de ecuații și inegalități etc.). Întocmirea unui model al unei operații necesită înțelegerea esenței fenomenului descris și cunoașterea aparatului matematic.

Eficiența operațiunii – gradul de adaptabilitate a acestuia la sarcină se exprimă cantitativ sub forma unui criteriu de eficiență – funcția țintă. Alegerea criteriului de eficacitate determină valoarea practică a studiului. (Un criteriu ales incorect poate fi dăunător, deoarece operațiunile organizate în funcție de un astfel de criteriu de eficiență conduc uneori la costuri nejustificate.)

Sarcini de planificare și management al rețelei luați în considerare relația dintre datele de finalizare a unui complex mare de operațiuni (lucrări) și orele de începere a tuturor operațiunilor complexului. Aceste sarcini constau în găsirea duratei minime a unui set de operațiuni, a raportului optim al valorilor costurilor și a momentului de implementare a acestora.

Probleme de coadă sunt dedicate studiului și analizei sistemelor de servicii cu cozi de aplicații sau cerințe și constau în determinarea indicatorilor de performanță ai sistemelor, a caracteristicilor optime ale acestora, de exemplu, determinarea numărului de canale de servicii, a timpului de serviciu etc.

Sarcini de gestionare a stocurilor constau in gasirea valorilor optime ale nivelului de stoc (punctul de comanda) si al marimii comenzii. Particularitatea unor astfel de sarcini este că, odată cu creșterea nivelului stocurilor, pe de o parte, costurile de stocare a acestora cresc, dar, pe de altă parte, pierderile datorate unei posibile lipsuri a produsului depozitat scad.

Probleme de alocare a resurselor apar în cursul unui anumit set de operațiuni (lucrări) care trebuie efectuate cu resursele disponibile limitate și este necesar să se găsească repartizarea optimă a resurselor între operații sau alcătuirea operațiunilor.

Sarcini de reparare și înlocuire a echipamentelor sunt relevante din cauza uzurii echipamentelor și a necesității înlocuirii acestuia în timp. Sarcinile se rezumă la determinarea momentului optim, a numărului de reparații și inspecții preventive, precum și la momentul înlocuirii echipamentelor cu echipamente modernizate.

Programarea (programarea) sarcinilor constau in determinarea ordinii optime a operatiilor (de exemplu, prelucrarea pieselor) pe diverse tipuri de echipamente.

Sarcini de planificare și plasare nia constau in determinarea numarului si amplasarii optime a noilor obiecte, tinand cont de interactiunea acestora cu obiectele existente si intre ele.

Probleme de selectare a rutei sau reţea problemele întâlnite cel mai des în studiul diverselor probleme din sistemele de transport și comunicații și constau în determinarea celor mai economice rute.

2. Problemă generală a programului liniar. Optimizarea soluției

Model economico-matematic

LP este o ramură a matematicii care dezvoltă teoria și metodele numerice pentru rezolvarea problemelor de găsire a extremului (maxim sau minim) al unei funcții liniare a mai multor variabile în prezența restricțiilor liniare, adică egalități sau inegalități care leagă aceste variabile.

Metodele LP sunt aplicate problemelor practice în care: 1) este necesar să se selecteze cea mai bună soluție (planul optim) dintr-o varietate de posibile; 2) soluția poate fi exprimată ca un set de valori ale unor variabile; a) restricţiile impuse soluţiilor fezabile prin condiţii specifice problemei sunt formulate sub formă de ecuaţii liniare sau inegalităţi; 4) scopul este exprimat sub forma unei funcții liniare a principalelor variabile. Valorile funcției obiective, permițând compararea diferitelor soluții, servesc drept criteriu pentru calitatea soluției.

Pentru a rezolva practic o problemă economică folosind metode matematice, în primul rând ar trebui să fie scrisă folosind un model economico-matematic. Un model economico-matematic este o descriere matematică a procesului sau obiectului economic studiat. Acest model exprimă legile procesului economic într-o formă abstractă folosind relații matematice.

Schema generală de formare a modelului: I

1) selectarea unui anumit număr de mărimi variabile, a căror atribuire de valori numerice determină în mod unic una dintre stările posibile ale fenomenului studiat;

2) exprimarea relaţiilor inerente fenomenului studiat sub forma unor relaţii matematice (ecuaţii, inegalităţi). Aceste relații formează un sistem de constrângeri pentru problemă;

3) exprimarea cantitativă a criteriului de optimitate selectat sub forma unei funcţii obiective; eu

4) formularea matematică a problemei ca problemă de găsire a extremumului funcţiei obiectiv, sub rezerva îndeplinirii restricţiilor impuse variabilelor.

Problemă generală de programare liniară are forma:

Dat un sistem de m ecuații liniare și inegalități cu n variabile

și funcția liniară

Este necesar să se găsească o soluție pentru sistemul X=(x1,x2,…,xj,…,xn), unde funcția liniară F ia valoarea optimă (adică maximă sau minimă).

Sistemul (1) se numește sistem de constrângeri, iar funcția F este numită funcție liniară, formă liniară, funcție obiectiv sau funcție scop.

Mai pe scurt, problema generală de programare liniară poate fi reprezentată ca:

cu restrictii:

Soluție optimă (sau plan optim) a unei probleme LP este o soluție X=(x1,x2,…,xj,…,xn), un sistem de constrângeri (1), care satisface condiția (3), în care funcția liniară (2) ia optim valoare (maximă sau minimă).

Cu condiția ca toate variabilele să fie nenegative, sistemul de constrângeri (1) constă numai din inegalități - o astfel de problemă de programare liniară se numește standard (simetrică); dacă sistemul de constrângeri constă numai din ecuații, atunci problema se numește canonică.

Un caz special al unei probleme canonice este o problemă în formă de bază, caracterizată prin aceea că toți coeficienții vectorului de constrângere b sunt nenegative, iar în fiecare ecuație există o variabilă cu coeficient de 1 care nu este inclusă în niciuna dintre celelalte ecuații. O variabilă cu această proprietate se numește de bază.

Problemele standard și canonice sunt cazuri speciale ale celei generale. Fiecare dintre ele este utilizat în domeniul său specific. Mai mult, toate cele trei formulări sunt echivalente între ele: orice problemă de programare liniară poate fi redusă la o problemă canonică, standard sau generală folosind transformări matematice simple.

4 . Elemente de algebră liniară

Un sistem de m ecuații liniare cu n variabile are forma

sau sub formă scurtă

Orice m variabile ale unui sistem de m ecuații liniare cu n variabile (m< n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

Pentru a rezolva sistemul (2.1) cu condiția m< n сформулируем утверждение.

Afirmația 2.1. Dacă pentru sistemmecuații liniare cunvariabile (m < n) rangul matricei de coeficienți pentru variabile este egal cu m, i.e. Dacă există cel puțin un grup de variabile de bază, atunci acest sistem este nedeterminat și fiecare set arbitrar de valori ale variabilelor nebaze corespunde unei soluții a sistemului.

Soluţie X=(x1,x2,…,xn) al sistemului (2.1) se numește admisibil dacă conține doar componente nenegative, i.e. xj>=0 pentru orice j=1,n. În caz contrar, soluția se numește invalidă.

Dintre numărul infinit de soluții ale sistemului se disting așa-numitele soluții de bază.

Soluție de bază a unui sistem de m ecuații liniare cu n variabile este o soluție în care toate n–m variabile minore sunt egale cu zero.

În problemele de programare liniară, soluțiile de bază admisibile sau, așa cum sunt numite și planurile de referință, prezintă un interes deosebit. O soluție de bază în care cel puțin una dintre variabilele principale este egală cu zero se numește degenerată.

Seturi convexe de puncte

Proprietatea definitorie comună care distinge un poligon convex de unul neconvex este că, dacă luați oricare dintre punctele sale și le conectați cu un segment, atunci întregul segment va aparține acelui poligon. Această proprietate poate fi luată pentru a defini un set convex de puncte.

Un set de puncte se numește convex, dacă acesta, împreună cu oricare două dintre punctele sale, conține întregul segment care leagă aceste puncte.

Seturile convexe au un important proprietate: Intersecția (partea comună) a oricărui număr de mulțimi convexe este o mulțime convexă.

Printre punctele unei mulțimi convexe, se pot distinge punctele interne, de limită și de colț.

Un punct al unei mulțimi se numește intern, dacă o parte din vecinătatea sa conține puncte numai din acest set.

Un punct al unei multimi se numeste punct de limita, dacă oricare dintre vecinătățile sale conține atât puncte aparținând mulțimii date, cât și puncte care nu îi aparțin.

Un interes deosebit în problemele de programare liniară sunt punctele de colț. Se numește punctul mulțimii unghiular(sau extrem), dacă nu este intern niciunui segment aparținând în întregime mulțimii date.

În fig. 2.4 prezintă exemple de diferite puncte ale poligonului: interior (punctul M), limită (punctul N) și colțul (punctele A, B, C, D, E). Punctul A este un punct de colț, deoarece pentru orice segment aparținând în întregime unui poligon, de exemplu, segmentul AP, acesta nu este intern; punctul A este intern segmentului KL, dar acest segment nu aparține în întregime poligonului.

Pentru o mulțime convexă, punctele de colț coincid întotdeauna cu vârfurile poligonului (poliedrul), în timp ce pentru o mulțime neconvexă acest lucru nu este necesar. Un set de puncte se numește închis dacă include toate punctele sale limită. Setul de puncte este numit limitat, dacă există o bilă (cerc) de rază de lungime finită cu un centru în orice punct al mulțimii, care conține în întregime mulțimea dată; altfel se spune că mulţimea este nemărginită.

Un set convex închis de puncte dintr-un plan având un număr finit de puncte de colț se numește poligon convex dacă este mărginit și regiune poligonală convexă dacă este nemărginit.

Semnificația geometrică a soluțiilor la inegalități, ecuații și sistemele acestora

Să luăm în considerare soluțiile inegalităților.

Enunțul 1. Mulțimea soluțiilor inegalității cu două variabile a11x1+a12x2<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>=b1.

Pentru a determina semiplanul dorit (sus sau inferior), se recomandă setarea unui punct de control arbitrar care nu se află pe granița sa - linia dreaptă construită. Dacă o inegalitate este valabilă într-un punct de control, atunci ea se menține în toate punctele semiplanului care conține punctul de control și nu este valabilă în toate punctele celuilalt semiplan. În schimb, dacă o inegalitate nu este satisfăcută la un punct de control, aceasta nu este satisfăcută în toate punctele semiplanului care conține punctul de control și este satisfăcută în toate punctele celuilalt semiplan. Este convenabil să luăm ca punct de control originea coordonatelor O (0;0), care nu se află pe linia construită.

Să luăm în considerare un set de soluții ale sistemelor de inegalități.

Enunțul 2. Mulțimea soluțiilor unui sistem comun de inegalități liniare în două variabile este un poligon convex (sau o regiune poligonală convexă).

Fiecare dintre inegalități, în conformitate cu afirmația 1, determină unul dintre semiplanuri, care este un set convex de puncte. Mulțimea soluțiilor unui sistem comun de inegalități liniare sunt puncte care aparțin semiplanurilor de soluții ale tuturor inegalităților, i.e. aparțin intersecției lor. Conform afirmației despre intersecția mulțimilor convexe, această mulțime este convexă și conține un număr finit de puncte de colț, i.e. este un poligon convex (o zonă poligonală convexă).

Coordonatele punctelor de colț - vârfurile poligonului - se găsesc ca coordonatele punctelor de intersecție ale liniilor corespunzătoare.

La construirea zonelor de soluție pentru sisteme de inegalități pot apărea și alte cazuri: mulțimea soluțiilor este o zonă poligonală convexă (Fig. 2.9, a); un punct (Fig. 2.9, b); o mulțime goală când sistemul de inegalități este inconsecvent (Fig. 2.9, c).

5 . Metoda geometrică pentru rezolvarea problemelor LP

soluție optimă la problema LP

Teorema 1. Dacă problema LP are o soluție optimă, atunci funcția liniară își ia valoarea maximă la unul dintre punctele de colț ale poliedrului soluției. Dacă o funcție liniară ia o valoare maximă la mai mult de un punct de colț, atunci o ia în orice punct care este o combinație liniară convexă a acestor puncte.

Teorema indică modalitatea fundamentală de rezolvare a problemelor LP. Într-adevăr, conform acestei teoreme, în loc să studiem un set infinit de soluții fezabile pentru a găsi soluția optimă dorită între ele, este necesar să studiem doar un număr finit de puncte de colț ale poliedrului de soluție.

Următoarea teoremă este dedicată metodei analitice de găsire a punctelor de colț.

Teorema 2. Fiecărei soluții de bază admisibile a problemei LP îi corespunde un punct de colț al poliedrului de soluție și invers, fiecărui punct de colț al poliedrului de soluție îi corespunde o soluție de bază admisibilă.

Un corolar important rezultă direct din teoremele 1 și 2: Dacă o problemă LP are o soluție optimă, atunci ea coincide cu cel puțin una dintre soluțiile sale de bază admisibile.

Asa de, optimul funcției liniare a problemei LP ar trebui căutat între numărul finit al soluțiilor sale de bază admisibile.

Deci, setul de soluții fezabile (poliedrul de soluție) al problemei LP este un poliedru convex (sau regiunea poliedrică convexă), iar soluția optimă a problemei este situată cel puțin într-unul dintre punctele de colț ale poliedrului de soluție.

Luați în considerare problema în formă standard cu două variabile (P = 2).

Fie imaginea geometrică a sistemului de constrângeri un poligon ABCDE(Fig. 4.1). Este necesar să găsim un punct dintre punctele acestui poligon la care funcția liniară F=c1x1+c2x2 ia valoarea maximă (sau minimă).

Să luăm în considerare așa-numitul linie de nivel funcție liniară F, adică linie de-a lungul căreia această funcție ia aceeași valoare fixă A, adică F = A, sau c1x1+c2x2=a.

Pe poligonul soluției, găsiți punctul prin care trece linia nivelului funcției F cu nivelul cel mai înalt (dacă funcția liniară este maximizată) sau cel mai scăzut (dacă este minimizată).

Ecuația dreptei de nivel a funcției c1x1+c2x2=a este ecuația dreptei. La diferite niveluri A liniile de nivel sunt paralele, deoarece coeficienții lor unghiulari sunt determinați numai de relația dintre coeficienții c1 și c2 și, prin urmare, sunt egale. Astfel, liniile de nivel de funcție F – Acestea sunt „paralele” deosebite, situate de obicei la un unghi față de axele de coordonate.

O proprietate importantă a liniei de nivel a unei funcții liniare este aceea că, atunci când linia este deplasată paralel într-o direcție, nivelul crește doar, iar atunci când este deplasată în cealaltă direcție, scade. Vectorul c=(c1,c2), care iese din origine, indică direcția celei mai rapide creșteri a funcției F. Linia de nivel a funcției liniare este perpendiculară pe vectorul c=(c1,c2).

Procedura pentru rezolvarea grafică a problemei LP:

1. Construiți un poligon de soluții.

2. Construiți un vector c=(c1,c2) ​​și desenați mai întâi o linie de nivel de funcție liniară pentru acesta F, de exemplu, F=0.

3. Prin deplasarea paralelă a dreptei F=0 în direcția vectorului c(-c) găsiți punctul Amax(Bmin), la care F atinge maximul (minimul).

1. Rezolvând împreună ecuațiile dreptelor care se intersectează în punctul optim, găsiți coordonatele acestuia.

2.Calculați Fmax(Fmin).

Cometariu. Punctul minim este punctul de „intrare” în poligonul soluție, iar punctul maxim este punctul de „ieșire” din poligon.

6. Idee generală a metodei simplex. Interpretare geometrică

Metoda grafică este aplicabilă unei clase foarte înguste de probleme de programare liniară: poate rezolva eficient probleme care conțin nu mai mult de două variabile. Au fost luate în considerare teoremele de bază ale programării liniare, din care rezultă că, dacă o problemă de programare liniară are o soluție optimă, atunci aceasta corespunde cel puțin unui punct de colț al poliedrului de soluții și coincide cu cel puțin una dintre soluțiile de bază admisibile ale sistem de constrângeri. A fost indicată o modalitate de rezolvare a oricărei probleme de programare liniară: enumerarea unui număr finit de soluții de bază fezabile ale sistemului de constrângeri și selectarea dintre ele pe cea pentru care funcția obiectiv face soluția optimă. Din punct de vedere geometric, aceasta corespunde cu enumerarea tuturor punctelor de colț ale poliedrului de soluție. O astfel de căutare exhaustivă va duce în cele din urmă la o soluție optimă (dacă aceasta există), dar implementarea sa practică este asociată cu dificultăți enorme, deoarece pentru problemele reale numărul soluțiilor de bază fezabile, deși finit, poate fi extrem de mare.

Numărul de soluții de bază permise care trebuie căutate poate fi redus dacă căutarea nu este efectuată aleatoriu, dar ținând cont de modificările funcției liniare, de exemplu. asigurarea că fiecare soluție ulterioară este „mai bună” (sau cel puțin „nu mai rea”) decât cea anterioară, în funcție de valorile funcției liniare (creșterea acesteia la găsirea unui maxim, scăderea acesteia la găsirea unui minim) . Această căutare vă permite să reduceți numărul de pași atunci când găsiți optimul. Să explicăm acest lucru cu un exemplu grafic.

Fie regiunea soluțiilor fezabile să fie reprezentată printr-un poligon ABCDE. Să presupunem că punctul său de colț A corespunde soluției de bază fezabile inițiale. O căutare aleatorie ar necesita testarea a cinci soluții de bază fezabile corespunzătoare celor cinci puncte de colț ale poligonului. Cu toate acestea, din desen reiese că după vârf A este avantajos să trecem la un vârf învecinat ÎN, iar apoi la punctul optim CU.În loc de cinci, am trecut doar prin trei vârfuri, îmbunătățind constant funcția liniară.

Ideea îmbunătățirii succesive a soluției a stat la baza unei metode universale de rezolvare a problemelor de programare liniară - metoda simplex sau metoda de imbunatatire secventiala a planului.

Sensul geometric al metodei simplex constă într-o tranziție secvențială de la un vârf al poliedrului de constrângere (numit inițial) la cel vecin, în care funcția liniară ia cea mai bună (cel puțin nu cea mai proastă) valoare în raport cu scopul problemei; până când se găsește soluția optimă - vârful unde se realizează valoarea optimă a funcției obiectiv (dacă problema are un optim final).

Metoda simplex a fost propusă pentru prima dată de omul de știință american J. Danzig în 1949, dar în 1939 ideile metodei au fost dezvoltate de omul de știință rus L.V. Kantorovich.

Metoda simplex, care permite rezolvarea oricărei probleme de programare liniară, este universală. În prezent, este folosit pentru calcule computerizate, dar exemplele simple folosind metoda simplex pot fi rezolvate manual.

Pentru a implementa metoda simplex - îmbunătățirea secvențială a soluției - este necesar să stăpâniți trei elemente principale:

o metodă pentru determinarea oricărei soluții de bază fezabile inițiale la o problemă;

regula de tranziție la cea mai bună (mai precis, nu mai rea) soluție;

criteriu de verificare a optimităţii soluţiei găsite.

Pentru a utiliza metoda simplex, problema programarii liniare trebuie redusa la forma canonica, i.e. sistemul de constrângeri trebuie prezentat sub formă de ecuaţii.

Literatura de specialitate descrie suficient de detaliat: găsirea planului de sprijin inițial (soluția de bază admisibilă inițială), folosind și metoda bazei artificiale, găsirea planului de sprijin optim, rezolvarea problemelor folosind tabele simplex.

7 . Algoritmul metodei simplex.

Să luăm în considerare soluția ZLP folosind metoda simplex și să o prezentăm în relație cu problema de maximizare.

1. Pe baza condițiilor problemei, este alcătuit modelul matematic al acesteia.

2. Modelul completat este convertit în forma canonică. În acest caz, se poate identifica o bază cu un plan de referință inițial.

3. Modelul canonic al problemei este scris sub forma unui tabel simplex, astfel încât toți termenii liberi să fie nenegativi. Dacă este selectat planul de referință inițial, treceți la pasul 5.

Tabel simplex: un sistem de ecuații de constrângere și o funcție obiectiv sunt introduse sub formă de expresii rezolvate relativ la baza inițială. Linia în care se scriu coeficienții funcției obiectiv F se numește linia F sau linia funcției obiectiv.

4. Planul de referință inițial se găsește efectuând transformări simplex cu elemente de rezoluție pozitivă corespunzătoare relațiilor simplex minime, și fără a lua în considerare semnele elementelor F-rând. Dacă în timpul transformărilor se întâlnește un rând 0, ale cărui elemente, cu excepția termenului liber, sunt zerouri, atunci sistemul de ecuații de constrângere pentru problemă este inconsecvent. Dacă întâlnim un rând 0 în care, în afară de termenul liber, nu există alte elemente pozitive, atunci sistemul de ecuații restrictive nu are soluții nenegative.

Vom numi reducerea sistemului (2.55), (2.56) la o nouă bază transformare simplex . Dacă transformarea simplex este considerată o operație algebrică formală, atunci se poate observa că, în urma acestei operații, rolurile sunt redistribuite între două variabile incluse într-un anumit sistem de funcții liniare: o variabilă trece de la dependentă la independentă, iar cealaltă. , dimpotrivă, de la independent la dependent. Această operație este cunoscută în algebră ca Etapa de eliminare a Iordaniei.

5. Planul de suport inițial găsit este examinat pentru optimitate:

a) dacă nu există elemente negative în rândul F (fără numărarea termenului liber), atunci planul este optim. Dacă nu există zerouri, atunci există un singur plan optim; dacă există cel puțin un zero, atunci există un număr infinit de planuri optime;

b) dacă în rândul F există cel puțin un element negativ, care corespunde unei coloane de elemente nepozitive, atunci;

c) dacă există cel puțin un element negativ în rândul F și există cel puțin un element pozitiv în coloana sa, atunci puteți trece la un nou plan de referință care este mai aproape de cel optim. Pentru a face acest lucru, coloana specificată trebuie desemnată ca o coloană de rezoluție, folosind raportul simplex minim, găsiți rândul de rezolvare și efectuați o transformare simplex. Planul de referință rezultat este din nou examinat pentru optimitate. Procesul descris se repetă până la obținerea unui plan optim sau până la stabilirea insolubilității problemei.

Coloana de coeficienți pentru o variabilă inclusă în bază se numește rezolvare. Astfel, prin alegerea unei variabile introduse în bază (sau alegând o coloană de rezoluție) pe baza elementului negativ al rândului F, ne asigurăm că funcția F crește .

Este puțin mai dificil să determinați variabila care trebuie exclusă din bază. Pentru a face acest lucru, ei compun raporturile dintre termenii liberi și elementele pozitive ale coloanei de rezoluție (astfel de relații se numesc simplex) și găsesc cel mai mic dintre ei, ceea ce determină rândul (rezolvarea) care conține variabila exclusă. Alegerea unei variabile excluse din bază (sau alegerea unei linii de rezoluție) conform relației simplex minime garantează, așa cum a fost deja stabilit, pozitivitatea componentelor de bază în noul plan de referință.

La punctul 3 al algoritmului, se presupune că toate elementele coloanei de termeni liberi sunt nenegative. Această cerință nu este necesară, dar dacă este îndeplinită, atunci toate transformările simplex ulterioare sunt efectuate numai cu elemente de rezolvare pozitivă, ceea ce este convenabil pentru calcule. Dacă există numere negative în coloana de termeni liberi, atunci elementul de rezolvare este ales după cum urmează:

1) uitați-vă prin rândul corespunzătoare unui termen liber negativ, de exemplu, un rând t, și selectați un element negativ din el, iar coloana corespunzătoare este luată ca rezolvare (presupunem că constrângerile problemei sunt consistente);

2) alcătuiesc relaţiile dintre elementele coloanei de termeni liberi cu elementele corespunzătoare ale coloanei de rezoluţie care au aceleaşi semne (relaţii simple);

3) alegeți cea mai mică dintre relațiile simplex. Aceasta va determina șirul de activare. Să fie, de exemplu, R-linia;

4) la intersecția coloanei de rezolvare și a rândului se găsește un element de rezoluție. Dacă elementul rândului y se dovedește a fi rezolvat, atunci după transformarea simplex termenul liber al acestui rând va deveni pozitiv. În caz contrar, la pasul următor, rândul t este din nou accesat. Dacă problema este rezolvabilă, atunci după un anumit număr de pași nu vor mai rămâne elemente negative în coloana de termeni liberi.

8. Metoda matricei inverse

Să considerăm un LP de forma:

A – matricea constrângerii;

C=(c1,c2,…,cn)–vector rând;

X=(x1,x2,…,xn) – variabile;

este vectorul părții drepte.

Presupunem că toate ecuațiile sunt liniar independente, adică. rang(a)=m. În acest caz, baza este un minor de ordinul matricei A. Adică, există cel puţin o submatrice B de ordinul m astfel încât |B|<>0. Toate necunoscutele corespunzătoare lui B se numesc de bază. Toate celelalte sunt gratuite.

Fie B o bază. Apoi, prin rearanjarea coloanelor matricei A putem întotdeauna reduce A la forma A=(B|N),

unde N este o submatrice formată din coloane ale matricei A care nu aparțin bazei. În același mod, este posibilă partiția vectorului x într-un vector de variabile de bază și.

Orice soluție la problema (1) satisface condiția A*x=b și, prin urmare, sistemul ia următoarea formă:

Deoarece |B|<>0, atunci există o matrice inversă. Înmulțind de la stânga cu inversul, obținem:

- decizie comună.

Soluția de bază (relativă la baza B) este o soluție particulară a problemei (2) obținută în condiția. Apoi este determinată în mod unic.

Soluția de bază se numește realizabil, Dacă.

Baza corespunzătoare soluției de bază implementate. Chemat bază implementabilă. Soluția de bază se numește degenerată dacă vectorul are componente zero.

Soluția generală conține toate soluțiile care există. Să revenim la funcția obiectiv. Introducem Cb – coeficienți în fața variabilelor de bază, Cn – restul.

Astfel obținem. Inlocuim din solutia generala:

Afirmație. Criteriul de optimizare pentru soluția de bază.

Sa spunem. Atunci soluția de bază este optimă. Dacă, atunci soluția de bază nu este optimă.

Document: Lasa. Să luăm în considerare soluția de bază, .

Prin urmare, este valoarea funcției obiectiv pentru soluția de bază.

Să mai existe o soluție: (Xb,Xn).

Atunci hai să ne uităm

Astfel, soluția de bază este cea mai min. Să nu se împlinească, dimpotrivă, adică. există.

Apoi există o soluție pentru care valoarea funcției obiectiv va fi mai mică decât valoarea funcției obiectiv pentru soluția de bază.

Lasă-l să corespundă unei variabile libere Xi:Xj, atribuim o valoare și o introducem în bază și derivăm o altă variabilă și o numim liberă.

Cum să determine? Toate variabilele libere, cu excepția, sunt tot egale cu 0.

Apoi, în soluția generală, unde.

Să scoatem: – o condiție necesară.

O soluție de bază se numește regulată dacă. Deducem variabila din bază. Cu o soluție nouă, funcția obiectiv scade, deoarece

Algoritm:

1.Problemă LP în formă standard.

2. Lăsăm ecuații liniar independente.

3. Găsiți o matrice B astfel încât |B|<>0 și soluția de bază.

Noi calculăm:

dacă, atunci există o soluție optimă – aceasta este soluția de bază;

dacă, atunci găsim componenta, o adăugăm și astfel găsim o altă soluție; – în care una dintre variabilele de bază =0. Îndepărtăm această variabilă din bază și introducem xi. Am obținut o nouă bază B2, conjugată la baza B1. Apoi calculăm din nou.

1. Dacă există o soluție optimă, atunci după un număr finit de pași o vom obține.

Din punct de vedere geometric, procedura este interpretată ca o tranziție de la un punct de colț la un punct de colț conjugat de-a lungul limitei mulțimii X - mulțimea de soluții la problemă. Deoarece există un număr finit de puncte de colț și scăderea strictă a funcției F(x) interzice trecerea de două ori prin același punct extrem, atunci dacă există o soluție optimă, atunci după un număr finit de pași o vom obține.

9. Interpretarea economică a problemei duale cu problema utilizării resurselor

Sarcină. Pentru a produce două tipuri de produse P1 și P2, se folosesc patru tipuri de resurse S1, S2, S3, S4. Sunt date rezervele de resurse, numărul de unități de resurse cheltuite pentru producția unei unități de producție. Profitul primit de la o unitate de producție P1 și P2 este cunoscut. Este necesar să se întocmească un plan de producție în care profitul din vânzarea acestuia să fie maxim.

Sarcinăeu(original):

F=c1x1+c2x2+…+CnXn->max cu restricții:

iar condiția de non-negativitate x1>=0, x2>=0,…,Xn>=0

Întocmește un plan de producție X=(x1,x2,…,Xn) în care profitul (venitul) din vânzările de produse să fie maxim, cu condiția ca consumul de resurse pentru fiecare tip de produs să nu depășească rezervele disponibile.

SarcinăII(dual)

Z=b1y1+b2y2+…+BmYm->min

cu restrictii:

și condiția de non-negativitate

y1>=0, y2>=0,…,yn>=0.

Găsiți un astfel de set de prețuri (estimări) resurselor Y=(y1,y2,…,yn), la care costurile totale ale resurselor vor fi minime, cu condiția ca costurile resurselor în producția fiecărui tip de produs să fie nu mai puțin decât profitul (venitul) din vânzarea acestor produse

În modelul de mai sus, bi(i=1,2,…,m) reprezintă rezerva de resurse Si; aij – numărul de unități de resursă Si consumate în producerea unei unități de ieșire Pj(j=1,2,…,n); cj– profit (venit) din vânzarea unei unități de producție Pj (sau prețul produsului Pj) .

Să presupunem că o organizație a decis să achiziționeze resursele S1, S2,..., Sm ale întreprinderii și este necesar să se stabilească prețuri optime pentru aceste resurse y1, y2,..., ym. Evident, organizația de achiziții este interesată să cheltuiască toate resursele Z în cantități b1,b2,…,bm la prețurile y1,y2,…,ym, respectiv, au fost minime, adică. Z=b1,y1+b2y2+…+bmym->min.

Pe de altă parte, o întreprindere care vinde resurse este interesată să se asigure că venitul primit nu este mai mic decât suma pe care o poate primi întreprinderea atunci când prelucrează resursele în produse finite.

Pentru a produce o unitate de produs P1, a11 unități de resursă S1, a21 unități de resursă S2,...., aj1 unități de resursă Si1,......, am1 unități de resursă Sm sunt consumate la un preț de y1 ,y1,...,yi,...,ym, respectiv. Prin urmare, pentru a satisface cerințele vânzătorului, costurile resurselor consumate în producerea unei unități de produs P1 nu trebuie să fie mai mici decât prețul acesteia c1, adică. a11y1+a21y2+…+am1ym>=c1.

În mod similar, puteți crea restricții sub formă de inegalități pentru fiecare tip de produs P1, P2,...Pn. Modelul economico-matematic și interpretarea semnificativă a problemei duale II astfel obținute sunt date în partea dreaptă a tabelului.

Prețurile resurselor y1,y1,…,yi,…,ym au primit diverse denumiri în literatura economică: contabilitate, implicit, umbră . Sensul acestor nume este că este condiţional , preturi "false". Spre deosebire de prețurile „externe” c1,c2,…,cn pentru produse, cunoscute, de regulă, înainte de începerea producției, prețurile la resurse y1,y2,…,ym sunt intern , deoarece nu sunt date din exterior, ci sunt determinate direct ca urmare a rezolvarii problemei, motiv pentru care sunt numite mai des estimări resurse.

10. Probleme LP reciproc duale și proprietățile lor

Să luăm în considerare formal două probleme I și II de programare liniară, prezentate în tabel, făcând abstracție din interpretarea semnificativă a parametrilor incluși în modelele lor economice și matematice.

Ambele sarcini au următoarele proprietati:

1. Într-o problemă se caută maximul unei funcții liniare, în cealaltă, minimul.

2. Coeficienții variabilelor într-o funcție liniară a unei probleme sunt membri liberi ai sistemului de restricții din alta.

3.Fiecare dintre probleme este dată în formă standard, iar în problema de maximizare toate inegalitățile formei "<=", а в задаче минимизации – все неравенства вида ">=".

4. Matricele de coeficienți pentru variabile din sistemele de constrângeri ale ambelor probleme sunt transpuse între ele.

5. Numărul de inegalități din sistemul de constrângeri al unei probleme coincide cu numărul de variabile din altă problemă.

6. Condiţiile de nenegativitate a variabilelor sunt păstrate în ambele probleme.

Cometariu. Dacă o condiție de non-negativitate este impusă variabilei j a problemei inițiale, atunci constrângerea j a problemei duale va fi o inegalitate, dar dacă a j-a variabilă poate lua atât valori pozitive, cât și valori negative, atunci constrângerea j-a a problemei duale va fi o ecuație; constrângerile problemei inițiale și variabilele dualului sunt similare legate.

Două probleme de programare liniară I și II care au proprietățile indicate se numesc probleme duale simetrice. În cele ce urmează, pentru simplitate, le vom numi pur și simplu sarcini duble.

Fiecare problemă LP poate fi asociată cu sarcina sa duală.

11. Algoritm pentru alcătuirea unei probleme duale:

1. Reduceți toate inegalitățile sistemului de constrângeri ale problemei inițiale la un singur sens: dacă în problema inițială se caută maximul unei funcții liniare, atunci reduceți toate inegalitățile sistemului de restricții la forma "<=", а если минимум – к виду ">=". Pentru aceste inegalități în care această cerință nu este îndeplinită, înmulțiți cu –1.

2. Compuneți o matrice extinsă a sistemului A, care include o matrice de coeficienți pentru variabile, o coloană de termeni liberi ai sistemului de restricții și un rând de coeficienți pentru variabile într-o funcție liniară.

3. Găsiți matricea transpusă în matricea A .

4. Formulați o problemă duală pe baza matricei rezultate şi condiţiile de nenegativitate a variabilelor: ele formează funcţia obiectivă a problemei duale, luând ca coeficienţi pentru variabile membrii liberi ai sistemului de restricţii ale problemei iniţiale; alcătuiește un sistem de restricții pentru problema duală, luând elemente de matrice ca coeficienți pentru variabile și coeficienți pentru variabilele din funcția obiectivă a problemei inițiale ca termeni liberi și notează inegalitățile de sens opus; notează condiția de non-negativitate a variabilelor problemei duale.

12. Prima teoremă a dualității

Legătura dintre soluțiile optime ale problemelor duale se stabilește cu ajutorul teoremelor de dualitate.

Un semn suficient de optimitate.

Dacă X*=(x1*,x2*,…,xn*) Și Y*=(y1*,y2*,…,ym*) – soluții admisibile ale problemelor reciproc duale pentru care este valabilă egalitatea,

atunci este soluția optimă pentru problema inițială I și pentru problema duală II.

Pe lângă semnul suficient al optimității problemelor reciproc duale, există și alte relații importante între soluțiile lor. În primul rând, apar întrebările: există întotdeauna simultan soluții optime pentru fiecare pereche de probleme duale; Este posibil ca una dintre problemele duale să aibă o soluție și cealaltă nu? Răspunsul la aceste întrebări este dat de următoarea teoremă.

Prima (principală) teoremă a dualității. Dacă una dintre problemele reciproc duale are o soluție optimă, atunci o are și cealaltă, iar valorile optime ale funcțiilor lor liniare sunt egale:

Fmax = Zmin sau F(X*)=Z(Y*) .

Dacă funcția liniară a uneia dintre probleme nu este limitată, atunci condițiile celeilalte probleme sunt contradictorii (problema nu are soluție).

Cometariu. Afirmația inversă a celei de-a doua părți a teoremei principale a dualității nu este adevărată în cazul general, i.e. din faptul că condițiile problemei inițiale sunt contradictorii, nu rezultă că funcția liniară a problemei duale este nemărginită.

Sensul economic al primei teoreme a dualității.

Planul de producție X*=(x1*,x2*,…,xn*) și set de prețuri (estimări) resurselor Y*=(y1*,y2*,…,ym*) se dovedesc a fi optime dacă și numai dacă profitul (venitul) din produse, constatat la prețurile „externe” (cunoscute dinainte) c1, c2,…, cn, este egal cu costurile resurselor la „intern” (determinat doar din rezolvarea problemei) prețurile y1 ,y2,…,ym. Pentru toate celelalte planuri XȘi YÎn ambele probleme, profitul (venitul) din produse este întotdeauna mai mic decât (sau egal cu) costurile resurselor.

Semnificația economică a primei teoreme a dualității poate fi interpretată astfel: întreprinderea este indiferentă dacă să producă produse conform planului optim X*=(x1*,x2*,…,xn*) și să primească profit (venit) maxim Fmax sau vinde resurse la prețuri optime Y* =(y1*,y2*,…,ym*) si ramburseaza din vanzare costul minim al resurselor Zmin.

13. A doua teoremă a dualității

Să fie date două probleme reciproc duble. Dacă fiecare dintre aceste probleme este rezolvată folosind metoda simplex, atunci este necesar să le aducem la forma canonică, pentru care ar trebui introdusă în sistemul de constrângeri al Problemei I (pe scurt notație) T variabile nenegative și în sistemul de constrângeri al Problemei II () – n variabile nenegative, unde i(j) este numărul inegalității în care este introdusă variabila suplimentară.

Sistemele de restricții pentru fiecare dintre problemele reciproc duale vor lua forma:

Să stabilim o corespondență între variabilele inițiale ale uneia dintre problemele duale și variabilele suplimentare ale celeilalte probleme (tabel).

Teorema. Componentele pozitive (diferice de zero) ale soluției optime a uneia dintre problemele reciproc duale corespund componentelor zero ale soluției optime a celeilalte probleme, adică. pentru orice i=1,2,…,m u j=1,2,…,n: dacă X*j>0, atunci; Dacă , atunci și în mod similar,

daca atunci ; daca atunci.

Din această teoremă rezultă o concluzie importantă că corespondența introdusă între variabilele problemelor reciproc duale atunci când se atinge optimul (adică la ultimul pas de rezolvare a fiecărei probleme folosind metoda simplex) reprezintă corespondența dintre principal(de regulă, nu egal cu zero) variabile ale uneia dintre problemele duale și non-core(egale cu zero) variabile ale unei alte probleme atunci când formează soluții de bază fezabile.

A doua teoremă a dualității. Componentele soluției optime a problemei duale sunt egale cu valorile absolute ale coeficienților pentru variabilele corespunzătoare ale funcției liniare a problemei inițiale, exprimate prin variabilele nebazice ale soluției sale optime.

Cometariu. Dacă într-una dintre problemele reciproc duale este încălcată unicitatea soluției optime, atunci soluția optimă a problemei duale este degenerată. Acest lucru se datorează faptului că, dacă este încălcată unicitatea soluției optime a problemei inițiale, cel puțin una dintre variabilele principale lipsește în exprimarea funcției liniare a soluției sale optime în ceea ce privește variabilele nebazice.

14. Aprecieri determinate obiectiv și semnificația lor

Componentele soluției optime ale problemei duale se numesc estimări optime (duale) ale problemei inițiale. Le-a numit academicianul L.V. Kantorovich determinată obiectiv" estimări (în literatură se mai numesc și venit ascuns) .

Variabile suplimentare ale problemei inițiale I, reprezentând diferența dintre rezervele bi ale resurselor S1, S2, S3, S4 iar consumul lor, expres resursele rămase , și variabile suplimentare ale problemei duale II, reprezentând diferența dintre costurile resurselor pentru producerea unei unități de producție din acestea și prețurile cj ale produselor P1, P2 , expres excesul de costuri fata de pret.

Astfel, evaluările determinate în mod obiectiv ale resurselor determină gradul de deficit al resurselor: conform planului optim de producție, resursele limitate (adică utilizate pe deplin) primesc evaluări diferite de zero, iar resursele care nu sunt rare primesc evaluări zero. Valoarea y*i este o evaluare a i-a resursă. Cu cât valoarea estimării y*i este mai mare, cu atât este mai mare deficitul de resurse. Pentru o resursă nerară y*i=0.

Deci, numai tipuri de produse profitabile, neprofitabile pot fi incluse în planul optim de producție (totuși, aici criteriul de rentabilitate este unic: prețul produsului nu depășește costurile resurselor consumate în producția lui, ci este exact egale cu ei).

A treia teoremă a dualității . Componentele soluției optime a problemei duale sunt egale cu valorile derivatelor parțiale ale funcției liniare Fmax(b1, b2,…, bm)conform argumentelor corespondente, i.e.

Estimările de resurse determinate obiectiv arată câte unități monetare se va modifica profitul (venitul) maxim din vânzările de produse atunci când stocul resursei corespunzătoare se va modifica cu o unitate.

Evaluările duale pot servi ca instrument de analiză și luare a deciziilor corecte în condițiile unei producții în continuă schimbare. De exemplu, cu ajutorul unor estimări ale resurselor determinate obiectiv, este posibil să se compare costurile condiționate optime și rezultatele producției.

Estimările determinate obiectiv ale resurselor ne permit să judecăm efectul nu al oricăror, ci doar al schimbărilor relativ mici ale resurselor. Cu schimbări bruște, estimările în sine pot deveni diferite, ceea ce le va face imposibil de utilizat pentru analiza eficienței producției. Pe baza rapoartelor de aprecieri determinate obiectiv se pot determina normele calculate de substituibilitate a resurselor, sub rezerva cărora înlocuirile efectuate în limitele stabilității evaluărilor duale nu afectează eficacitatea planului optim. Concluzie. Estimările duale sunt:

1. Un indicator al deficitului de resurse și produse.

2. Un indicator al influenței restricțiilor asupra valorii funcției obiectiv.

3. Un indicator al eficienței producției anumitor tipuri de produse din punctul de vedere al criteriului de optimitate.

4. Un instrument pentru compararea costurilor și rezultatelor condiționate totale.

15. Enunțarea problemei transportului pe baza criteriului costului.

TK - problema celui mai economic plan pentru transportul unui produs omogen sau interschimbabil de la punctul de producție (stațiile de plecare) la punctele de consum (stațiile de destinație) - este cea mai importantă problemă particulară a LP, care are aplicații practice extinse. nu numai la problemele de transport.

Specificația tehnică se distinge în LP prin certitudinea caracteristicilor sale economice, caracteristicile modelului matematic și prezența unor metode specifice de soluție.

Cea mai simplă formulare a specificaţiilor tehnice după criteriul costului este următoarea: în T la punctele de plecare A1,…,Am există respectiv a1,…,am unități de marfă (resurse) omogene care trebuie livrate n consumatorii B1,…,Bn în cantități b1,…,bn unități (nevoi). Sunt cunoscute costurile de transport Cij ale transportului unei unități de marfă de la al-lea punct de plecare la al-lea punct de consum.

Este necesar să se întocmească un plan de transport, adică să se găsească câte unități de marfă trebuie trimise de la al i-lea punct de plecare la al j-lea punct de consum, astfel încât să satisfacă pe deplin nevoile și astfel încât transportul total costurile sunt minime.

Pentru claritate, vă prezentăm condițiile specificației tehnice sub forma unui tabel numit distributie .

Furnizor	Consumator			Stoc de marfă
Nevoie

Aici, cantitatea de marfă transportată de la i-lea punct de plecare la j-a destinație este egală cu xij, stocul de marfă la i-lea punct de plecare este determinat de valoarea ai>=0, iar nevoia de încărcătură la a-a destinație este bj>=0 . Se presupune că toate xij>=0.

Matricea se numește matricea tarifară (costuri sau costuri de transport).

Planul sarcinilor de transport se numește matrice, unde fiecare număr xij indică numărul de unități de marfă care trebuie livrate de la al-lea punct de plecare la j-a destinație. Se numește matricea xij matricea de transport.

Costurile totale totale asociate implementării planului de transport pot fi reprezentate de funcția obiectiv

Variabilele xij trebuie să îndeplinească restricțiile privind stocurile, consumatorii și condițiile de nenegativitate:

– restricții asupra rezervelor (2);

– restricții asupra consumatorilor (2);

– condiţii de non-negativitate (3).

Astfel, matematic, problema transportului se formulează astfel. Sunt date sistemul de restricții (2) în condiția (3) și funcția obiectiv (1). Dintre setul de soluții ale sistemului (2), este necesar să se găsească o soluție nenegativă care să minimizeze funcția (1).

Sistemul de constrângeri al problemei (1) – (3) conține m+n ecuații cu Tn variabile. Se presupune că rezervele totale sunt egale cu nevoile totale, adică.

16. Semn de solubilitate a problemei transportului

Pentru ca o problemă de transport să aibă planuri admisibile este necesară și suficientă satisfacerea egalității

Există două tipuri de probleme de transport: închis , în care volumul total de încărcătură al furnizorilor este egal cu cererea totală a consumatorilor și deschis , în care capacitatea totală de producție a furnizorilor depășește cererea consumatorilor sau cererea consumatorilor este mai mare decât capacitatea totală reală a furnizorilor, adică

Un model deschis poate fi transformat într-un model închis. Deci, dacă, atunci o destinație fictivă (n+1) este introdusă în modelul matematic al problemei transportului. În acest scop, în matricea sarcinilor este prevăzută o coloană suplimentară, pentru care cererea este egală cu diferența dintre capacitatea totală a furnizorilor și cererea reală a consumatorilor:

Toate tarifele pentru livrarea mărfurilor până în acest punct vor fi considerate egale cu zero. Acest lucru transformă modelul deschis al problemei într-unul închis. Pentru o problemă nouă, funcția obiectiv este întotdeauna aceeași, deoarece prețurile pentru transportul suplimentar sunt egale cu zero. Cu alte cuvinte, consumatorul fictiv nu încalcă compatibilitatea sistemului de constrângeri.

Dacă, atunci, se introduce un punct de plecare fictiv (m+1), căruia i se atribuie o rezervă de marfă egală cu.

Tarifele pentru livrarea mărfurilor de la acest furnizor fictiv sunt din nou setate la zero. Un rând va fi adăugat la matrice, acest lucru nu va afecta funcția obiectiv, iar sistemul de constrângeri al problemei va deveni comun, adică va deveni posibil să se găsească planul optim.

Pentru problema transportului este importantă următoarea teoremă.

Teorema. Rangul matricei problemei de transport este cu unul mai mic decât numărul de ecuații, adică r ( A )= m + n -1.

Din teoremă rezultă că fiecare proiect de referință trebuie să aibă (m-1)(n-1) variabile libere egale cu zero și m+n-1 variabile de bază.

Vom căuta planul de transport al sarcinii de transport direct în tabelul de distribuție. Să presupunem că dacă variabila xij ia o valoare, atunci vom scrie această valoare în celula corespunzătoare (I,j), dar dacă xij=0, atunci vom lăsa liberă celula (I,j). Ținând cont de teorema privind rangul matricei în tabelul de distribuție planul de referinţă trebuie să conţină m+n-1 celule ocupate, iar restul va fi gratuit.

Cerințele specificate pentru planul de referință nu sunt singurele. Planurile de referință trebuie să îndeplinească o altă cerință legată de cicluri.

Un set de celule dintr-o matrice de transport în care două și doar două celule adiacente sunt situate pe un rând sau într-o coloană, iar ultima celulă a setului se află în același rând sau coloană ca prima se numește închisă. ciclu .

Grafic, un ciclu este o linie întreruptă închisă, ale cărei vârfuri sunt situate în celulele ocupate ale tabelului, iar legăturile sunt situate numai în rânduri sau coloane. Mai mult, la fiecare vârf al ciclului există exact două verigi, dintre care una este într-un rând și cealaltă într-o coloană. Dacă o linie întreruptă care formează un ciclu se intersectează, atunci punctele de auto-intersecție nu sunt vârfuri.

Următoarele proprietăți importante ale planurilor de probleme de transport sunt asociate cu un set de celule de ciclu:

1) un plan admisibil pentru o problemă de transport este unul de referință dacă și numai dacă din celulele ocupate de acest plan nu se poate forma niciun ciclu;

2) dacă avem un plan de referință, atunci pentru fiecare celulă liberă se poate forma un singur ciclu, care conține această celulă și o parte din celulele ocupate.

17. Construirea planului de referință inițial

Regula „colțului de nord-vest”.

Pentru a întocmi planul inițial de transport, este convenabil să folosiți regula „colțul de nord-vest”, care este după cum urmează.

Vom completa pornind din stânga sus, numit convențional „colțul de nord-vest”, deplasându-ne mai departe de-a lungul liniei la dreapta sau în jos pe coloană. Să punem în celula (1; 1) cel mai mic dintre numerele a1 și b1, adică . Dacă, atunci prima coloană este „închisă”, adică cererea primului consumator este complet satisfăcută. Aceasta înseamnă că pentru toate celelalte celule din prima coloană cantitatea de marfă pentru .

Dacă, atunci prima linie este în mod similar „închisă”, adică pentru . Procedăm la umplerea celulei adiacente (2; 1), în care intrăm.

După ce am completat a doua celulă (1; 2) sau (2; 1), trecem la completarea următoarei a treia celulă de-a lungul celei de-a doua linii sau în a doua coloană. Vom continua acest proces până când, la un moment dat, resursele am și nevoile bn se vor epuiza. Ultima celulă completată va fi în ultima a n-a coloană și în ultimul rând al mi-lea.

Regula „elementului minim”.

Planul de referință inițial, construit conform regulii „colțului de nord-vest”, se dovedește de obicei a fi foarte departe de a fi optim, deoarece determinarea lui nu ia în considerare valorile costurilor cij. Prin urmare, calculele ulterioare vor necesita mai multe iterații pentru a realiza planul optim. Numărul de iterații poate fi redus dacă planul inițial este construit conform regulii „elementului minim”. Esența sa constă în faptul că, la fiecare pas, „mișcarea” maximă posibilă a mărfurilor într-o cușcă se realizează cu un tarif minim cij. Începem să completăm tabelul din celula care corespunde celui mai mic element cij al matricei tarifare. Cel mai mic dintre numerele ai sau bj este plasat în celula cu cel mai mic tarif . Apoi, rândul corespunzător unui furnizor al cărui stoc este complet epuizat, sau coloana corespunzătoare unui client a cărui cerere este complet satisfăcută, este exclus din considerare. Poate fi necesar să eliminați un rând și o coloană în același timp dacă stocul furnizorului este complet epuizat și cererea clientului este pe deplin satisfăcută. În continuare, din celulele rămase ale tabelului, se selectează din nou celula cu cel mai mic tarif și procesul de distribuire a stocurilor continuă până când toate sunt distribuite și cererea este satisfăcută.

18. Metoda potenţialelor

Principiul general de determinare a planului optim pentru o problemă de transport folosind metoda potențialului este similar cu principiul rezolvării unei probleme LP folosind metoda simplex și anume: mai întâi se găsește un plan de referință pentru o problemă de transport, apoi este succesiv îmbunătățit până la obținerea unui plan optim.

Esența metodei potențiale este următoarea. După ce a fost găsit planul inițial de transport de referință, fiecărui furnizor (fiecărui rând) i se atribuie un anumit număr numit potențial furnizor Ai și fiecărui consumator (fiecărei coloană) i se atribuie un anumit număr numit potențial de consumator.

Costul unei tone de marfă într-un punct este egal cu costul unei tone de marfă înainte de transport + costul transportului acesteia: .

Pentru a rezolva o problemă de transport folosind metoda potențială, trebuie să:

1. Construiți un plan de transport de bază conform uneia dintre regulile menționate. Numărul de celule umplute trebuie să fie m+n-1.

2. Calculați potențialele și, în consecință, furnizorii și consumatorii (pentru celulele ocupate): . Numărul de celule umplute este m+n-1, iar numărul de ecuații este m+n. Deoarece numărul de ecuații este cu unul mai mic decât numărul de necunoscute, atunci una dintre necunoscute se dovedește a fi liberă și poate lua orice valoare numerică. De exemplu, . Potențialele rămase pentru o soluție de referință dată vor fi determinate în mod unic.

3. Verificați optimitatea, de ex. pentru celulele libere, calculați estimări. Dacă, atunci transportul este oportun și planul X este optim - un semn al optimității. Dacă există cel puțin o diferență, treceți la un nou plan de referință. În sensul său economic, valoarea caracterizează modificarea costurilor totale de transport care se va produce ca urmare a unei singure livrări de către al-lea furnizor către al-lea consumator. Dacă, atunci o singură livrare va duce la economii la costurile de transport, dar dacă - la o creștere a acestora. În consecință, dacă printre direcțiile de aprovizionare gratuite nu există direcții care să economisească costurile de transport, atunci planul rezultat este optim.

4. Dintre numerele pozitive, se selectează maximul și se construiește un ciclu de recalculare pentru celula liberă căreia îi corespunde. După ce ciclul a fost construit pentru celula liberă selectată, ar trebui să treceți la un nou plan de referință. Pentru a face acest lucru, este necesar să mutați sarcinile din celulele conectate la o celulă liberă dată printr-un ciclu de recalculare.

a) Fiecărei celule conectate printr-un ciclu cu o anumită celulă liberă i se atribuie un anumit semn, iar această celulă liberă este „+”, iar tuturor celorlalte celule (vârfurile ciclului) li se atribuie alternativ semnele „–” și „ +”. Vom numi aceste celule minus și plus.

b) În celulele negative ale ciclului găsim oferta minimă, pe care o notăm cu. Cel mai mic dintre numerele xij situate în celulele minus este transferat în această celulă liberă. În același timp, acest număr se adaugă la numerele corespunzătoare din celulele cu semnul „+” și se scade din numerele din celulele minus. O celulă care anterior era liberă devine ocupată și intră în planul de sprijin; iar celula minus, care conținea minimul numerelor xij, se consideră liberă și părăsește planul de sprijin.

Astfel, a fost stabilit un nou plan de referință. Tranziția descrisă mai sus de la un plan de referință la altul se numește o schimbare în ciclul de recalculare. Când este deplasat de-a lungul ciclului de recalculare, numărul de celule ocupate rămâne neschimbat, și anume, rămâne egal cu m+n-1. Mai mult, dacă există două sau mai multe numere identice xij în celulele negative, atunci doar una dintre aceste celule este eliberată, iar restul rămân ocupate cu zero provizii.

5. Planul de referință rezultat este verificat pentru optimitatea, adică. repetați toți pașii de la pasul 2.

19. Conceptul de programare dinamică.

DP (planificarea) este o metodă matematică pentru găsirea de soluții optime la problemele cu mai multe etape (mai multe etape). Unele dintre aceste probleme se împart în mod natural în pași (etape) separate, dar există probleme în care partiția trebuie introdusă artificial pentru ca acestea să fie rezolvate prin metoda DP.

De obicei, metodele DP optimizează funcționarea unor sisteme controlate, al căror efect este evaluat aditiv, sau multiplicativ, funcția obiectiv. Aditiv se cheamă o funcţie a mai multor variabile f(x1,x2,…,xn), a cărei valoare se calculează ca suma unor funcţii fj care depind doar de o variabilă xj: . Termenii funcției obiective aditive corespund efectului deciziilor luate în etapele individuale ale procesului controlat.

Principiul optimității lui R. Bellman.

Sensul abordării implementate în programarea dinamică este de a înlocui soluția problemei multidimensionale originale cu o succesiune de probleme de dimensiune inferioară. Cerințe de bază pentru sarcini:

1. obiectul cercetării să fie sistem controlat (obiect) cu dat valabil state și acceptabil departamente;

2. sarcina trebuie să permită interpretarea ca un proces în mai multe etape, fiecare pas constând în acceptare solutii O alegerea unuia dintre controalele admisibile conducând la schimbare de stat sisteme;

3. sarcina să nu depindă de numărul de pași și să fie definită la fiecare dintre aceștia;

4. starea sistemului la fiecare pas trebuie descrisă prin același set de parametri (în compoziție);

5. starea ulterioară în care se află sistemul după alegerea unei soluții pe k-m pas, depinde doar de decizia dată și de starea inițială la început k- pasul. Această proprietate este fundamentală din punctul de vedere al ideologiei programării dinamice și se numește fara consecinte .

Să luăm în considerare problemele aplicării modelului de programare dinamică într-o formă generalizată. Fie ca sarcina să fie controlul unui obiect abstract care poate fi în diferite stări. Starea curentă a obiectului va fi identificată cu un anumit set de parametri, care vor fi notați în continuare cu S și numiți vector de stare. Se presupune că este dată o mulțime S a tuturor stărilor posibile. Există, de asemenea, un set definit pentru obiect controale admisibile(acțiuni de control) X, care, fără pierderea generalității, poate fi considerată o mulțime numerică. Acțiunile de control pot fi efectuate la momente discrete în timp și management soluţie constă în alegerea unuia dintre comenzi. Plan sarcini sau strategie de management se numește vector x=(x1,x2,…,xn-1), ale cărui componente sunt controalele selectate la fiecare pas al procesului. Având în vedere cele așteptate nici un efect secundarîntre fiecare două stări consecutive ale obiectului Sk și Sk+1 există o relație funcțională cunoscută, care include și controlul selectat: . Astfel, stabilirea stării inițiale a obiectului și alegerea unui plan X defini clar traiectorie comportamentală obiect.

Controlați eficiența la fiecare pas k depinde de starea curentă Sk, de controlul selectat xk și se cuantifică folosind funcțiile fk(xk,Sk), care sunt termeni funcţie obiectivă aditivă , care caracterizează eficienţa globală a managementului facilităţilor. ( Notă , că definiția funcției fk(xk,Sk) include intervalul de valori admisibile xk , iar această zonă, de regulă, depinde de starea actuală a Sk). Control optim , pentru o stare inițială dată S1, se reduce la alegerea unui astfel de plan optim x* , la care se realizează suma maxima valorile lui fk pe traiectoria corespunzătoare.

Principiul de bază al programării dinamice este că, la fiecare pas, nu trebuie să depuneți eforturi pentru optimizarea izolată a funcției fk(xk,Sk), ci să alegeți controlul optim x*k sub ipoteza că toți pașii următori sunt optimi. Formal, acest principiu este implementat prin constatarea la fiecare pas k controale optime condiționate , oferind cea mai mare eficiență totală începând de la acest pas, presupunând că starea curentă este S.

Fie Zk(s) valoarea maximă a sumei funcțiilor fk pe tot parcursul etapelor de la k inainte de P(obținut cu control optim la un segment dat al procesului), cu condiția ca obiectul de la începutul etapei k este în starea S. Atunci funcțiile Zk(s) trebuie să satisfacă relația de recurență:

Acest raport se numește relație de bază de recurență (ecuația funcțională de bază) programare dinamică. Implementează principiul de bază al programării dinamice, cunoscut și ca Principiul optimității Bellman :

Strategia optimă de control trebuie să îndeplinească următoarea condiție: oricare ar fi starea initiala sk la pasul k și controlul selectat la acest pas xk, conducerea ulterioară (deciziile manageriale) trebuie să fie optimă în raport cu cocmo Ianiya ,rezultată din decizia luată la pasul k .

Relația principală ne permite să găsim funcțiile Zk(s) numai V combinat cu condiția inițială, care în cazul nostru este egalitatea.

Principiul optimității formulat mai sus este aplicabil numai controlului obiectelor pentru care alegerea controlului optim nu depinde de fundalul procesului controlat, adică de modul în care sistemul a ajuns la starea sa actuală. Această împrejurare este cea care ne permite să descompunem problema și să facem posibilă soluția ei practică.

Pentru fiecare sarcină specifică, ecuația funcțională are propria sa formă specifică, dar trebuie să păstreze cu siguranță caracterul recurent inerent expresiei (*) și care întruchipează ideea de bază a principiului optimității.

20. Conceptul de modele de joc.

Se numește modelul matematic al unei situații conflictuale joc , părțile implicate în conflict - jucători, iar rezultatul conflictului este victorie.

Pentru fiecare joc oficial, reguli , acestea. un sistem de condiții care determină: 1) opțiuni pentru acțiunile jucătorilor; 2) cantitatea de informații pe care fiecare jucător o are despre comportamentul partenerilor săi; 3) câștigul la care conduce fiecare set de acțiuni. De obicei, câștigul (sau pierderea) poate fi cuantificat; de exemplu, puteți evalua o pierdere ca zero, o victorie ca unul și o egalitate ca 1/2. Cuantificarea rezultatelor unui joc se numește plată .

Jocul se numește baie de aburi , dacă implică doi jucători și multiplu , dacă numărul de jucători este mai mare de doi. Vom lua în considerare doar jocurile de dublu. Ele implică doi jucători AȘi ÎN, ale căror interese sunt opuse, iar prin joc înțelegem o serie de acțiuni din partea lui AȘi ÎN.

Jocul se numește joc cu suma zero sau antagonist cer , dacă câștigul unuia dintre jucători este egal cu pierderea celuilalt, i.e. suma câștigurilor ambelor părți este zero. Pentru a finaliza sarcina de joc, este suficient să indicați valoarea unuia dintre ele . Dacă desemnăm A– câștigurile unuia dintre jucători, b – câștigurile celuilalt, apoi pentru un joc cu sumă zero b = –A, de aceea este suficient să luăm în considerare, de exemplu A.

Se numește alegerea și implementarea uneia dintre acțiunile prevăzute de reguli progres jucător. Mișcările pot fi personal Și Aleatoriu . Mișcare personală – aceasta este o alegere conștientă de către jucător a uneia dintre acțiunile posibile (de exemplu, o mișcare într-un joc de șah). Setul de opțiuni posibile pentru fiecare mișcare personală este reglementat de regulile jocului și depinde de totalitatea mișcărilor anterioare de ambele părți.

Mișcare aleatorie – este o acțiune aleasă aleatoriu (de exemplu, alegerea unei cărți dintr-un pachet amestecat). Pentru ca un joc să fie definit matematic, regulile jocului trebuie să indice pentru fiecare mișcare aleatorie distribuția probabilității rezultate posibile.

Unele jocuri pot consta doar din mișcări aleatorii (așa-numitele jocuri de noroc pur) sau numai din mișcări personale (șah, dame). Majoritatea jocurilor de cărți aparțin jocurilor de tip mixt, adică conțin atât mișcări aleatorii, cât și mișcări personale. În viitor, vom lua în considerare doar mișcările personale ale jucătorilor.

Jocurile sunt clasificate nu numai după natura mișcărilor (personale, aleatorii), ci și după natura și cantitatea de informații disponibile fiecărui jucător cu privire la acțiunile celuilalt. O clasă specială de jocuri sunt așa-numitele „jocuri cu informații complete”. Un joc cu informații complete este un joc în care fiecare jucător, cu fiecare mișcare personală, cunoaște rezultatele tuturor mișcărilor anterioare, atât personale, cât și aleatorii. Exemple de jocuri cu informații complete includ șahul, damele și binecunoscutul joc „tic-tac-toe”. Majoritatea jocurilor de importanță practică nu aparțin clasei de jocuri cu informații complete, deoarece incertitudinea cu privire la acțiunile inamicului este de obicei un element esențial al situațiilor conflictuale.

Unul dintre conceptele principale ale teoriei jocurilor este conceptul strategii .

Strategie Un jucător este un set de reguli care determină alegerea acțiunii sale la fiecare mișcare personală, în funcție de situația actuală. De obicei, în timpul jocului, cu fiecare mișcare personală, jucătorul face o alegere în funcție de situația specifică. Cu toate acestea, în principiu, este posibil ca toate deciziile să fie luate de jucător în avans (ca răspuns la orice situație dată). Aceasta înseamnă că jucătorul a ales o strategie specifică, care poate fi specificată ca o listă de reguli sau un program. (În acest fel, puteți juca jocul folosind un computer.) Jocul se numește final , dacă fiecare jucător are un număr finit de strategii și fără sfârşit .– in caz contrar.

Pentru a decide joc , sau găsi soluție de joc , pentru fiecare jucător ar trebui să alegem o strategie care să satisfacă condiția optimitatea , acestea. unul dintre jucători trebuie să primească câștig maxim, când al doilea se ține de strategia sa, În același timp, al doilea jucător trebuie să aibă pierdere minimă , dacă primul se ține de strategia lui. Se numesc astfel de strategii optim . Strategiile optime trebuie să satisfacă și condiția durabilitate , acestea. Trebuie să fie dezavantajos pentru fiecare jucător să-și abandoneze strategia în acest joc.

Dacă jocul se repetă de câteva ori, atunci jucătorii ar putea să nu fie interesați să câștige și să piardă în fiecare joc specific, dar A câștig (înfrângere) medie în toate loturile.

Scopul teoriei jocurilor este de a determina strategia optimă pentru fiecare jucător.

21. Matricea de plată. Prețul mai mic și mai mare al jocului

Jocul suprem în care jucătorul A Are T strategiile și jucătorul V – p strategiile se numește joc m×n.

Luați în considerare un joc m×n de doi jucători AȘi ÎN(„noi” și „inamic”).

Lasă jucătorul A are T strategii personale, pe care le notăm A1,A2,…,Am. Lasă jucătorul ÎN disponibil n strategii personale, să le notăm B1,B2,…,Bn.

Lăsați fiecare parte să aleagă o strategie specifică; pentru noi va fi Ai, pentru inamicul Bj. Ca rezultat al alegerii de către jucători a oricărei perechi de strategii Ai și Bj (), rezultatul jocului este determinat în mod unic, adică. câștigurile jucătorului aij A(pozitiv sau negativ) și pierderea (-aij) a jucătorului ÎN.

Să presupunem că valorile lui aij sunt cunoscute pentru orice pereche de strategii (Ai,Bj) . Matricea P=aij , ale căror elemente sunt plățile corespunzătoare strategiilor Ai și Bj, numit matricea de plată sau matricea jocului. Rândurile acestei matrice corespund strategiilor jucătorului A, iar coloanele – strategiile jucătorului B. Aceste strategii se numesc pure.

Matricea jocului m×n are forma:

Luați în considerare un joc m×n cu o matrice și determinați cea mai bună dintre strategiile A1,A2,…,Am . Alegerea strategiei Ai player A trebuie să se aștepte ca jucătorul ÎN ii va raspunde cu una dintre strategiile Bj pentru care jucatorul castiga A minim (jucător ÎN caută să „rănească” jucătorului A).

Să notăm cu cele mai mici câștiguri ale jucătorului A când alege strategia Ai pentru toate strategiile posibile ale jucătorilor ÎN(cel mai mic număr în i al-lea rând al matricei de plată), adică

Dintre toate numerele () o alegem pe cea mai mare: .

Hai sa sunăm cel mai mic preț al jocului, sau câștiguri maxime (maxmin). Acesta este un câștig garantat pentru jucătorul A pentru orice strategie a jucătorului B. Prin urmare,

Strategia corespunzătoare maximinului se numește strategia maximin . Jucător ÎN interesat să reducă câștigurile jucătorului A, atunci când alege strategia Bj, el ține cont de câștigul maxim posibil pentru A. Să notăm

Dintre toate numerele, alege-l pe cel mai mic

și hai să sunăm prețul de top al jocului sau câștig minimax(minimax). Egoul a garantat pierderea jucătorului B. Prin urmare,

Se numește strategia corespunzătoare minimaxului strategia minimax.

Principiul care îi dictează pe jucători să aleagă cele mai „prevăzute” strategii minimax și maximin se numește principiul minimax . Acest principiu decurge din presupunerea rezonabilă că fiecare jucător se străduiește să atingă un obiectiv opus celui al adversarului său.

Teorema. Prețul inferior al jocului nu depășește întotdeauna prețul superior al jocului .

Dacă prețurile superioare și mai mici ale jocului sunt aceleași, atunci valoarea totală a prețurilor superioare și mai mici ale jocului se numește prețul pur al jocului, sau cu costul jocului. Strategiile Minimax corespunzătoare prețului jocului sunt strategii optime , și totalitatea lor - soluție optimă sau solutia jocului. În acest caz jucătorul A primește maximul garantat (independent de comportamentul jucătorului) ÎN) câștiguri v, și jucătorul ÎN atinge minimul garantat (indiferent de comportamentul jucătorului A) pierzând v. Ei spun că soluția la joc are stabilitate , acestea. Dacă un jucător se ține de strategia sa optimă, atunci nu poate fi profitabil pentru celălalt să se abată de la strategia sa optimă.

Dacă unul dintre jucători (de exemplu A)ține de strategia lui optimă, iar celălalt jucător (ÎN) atunci se va abate de la strategia optimă în orice fel pentru jucătorul care a făcut abaterea, aceasta nu poate fi niciodată profitabilă; o astfel de abatere a jucătorului ÎN poate lăsa în cel mai bun caz câștigurile neschimbate. iar în cel mai rău caz, crește-l.

Dimpotrivă, dacă ÎN aderă la strategia sa optimă și A se abate de la el, atunci acest lucru nu poate fi în niciun caz benefic pentru A.

O pereche de strategii pure și oferă o soluție optimă jocului dacă și numai dacă elementul corespunzător este atât cel mai mare din coloana sa, cât și cel mai mic din rândul său. Această situație, dacă există, se numește power point. În geometrie, un punct de pe o suprafață care are proprietatea de a avea un minim simultan într-o coordonată și un maxim într-o alta se numește putere punct, prin analogie acest termen este folosit în teoria jocurilor.

Jocul pentru care , numit jucându-se cu un power point. Un element care are această proprietate este punctul de forță al matricei.

Deci, pentru fiecare joc cu un punct de putere, există o soluție care determină o pereche de strategii optime pentru ambele părți, care diferă în următoarele proprietăți.

1) Dacă ambele părți respectă strategiile lor optime, atunci câștigul mediu este egal cu costul net al jocului v, care este simultan prețul său mai mic și superior.

2) Dacă una dintre părți aderă la strategia sa optimă, iar cealaltă se abate de la propria sa, atunci partea care abate nu poate decât să piardă și în niciun caz nu își poate crește câștigurile.

În teoria jocurilor, se dovedește că, în special, fiecare joc cu informații complete are un punct de putere și, prin urmare, fiecare astfel de joc are o soluție, adică există o pereche de strategii optime ale ambelor părți, oferind un profit mediu. egal cu costul jocului. Dacă un joc cu informații complete constă doar din mișcări personale, atunci când fiecare parte își aplică strategia optimă, ar trebui să se încheie întotdeauna cu un rezultat bine definit, și anume, un câștig exact egal cu costul jocului.

22. Rezolvarea jocului în strategii mixte.

Printre jocurile finite de importanță practică, jocurile cu un punct de forță sunt relativ rare; un caz mai tipic este atunci când prețul inferior și superior al jocului sunt diferite. Analizând matricele unor astfel de jocuri, ajungem la concluzia că, dacă fiecărui jucător i se oferă posibilitatea de a alege o singură strategie, atunci, mizând pe un adversar care acționează rezonabil, această alegere ar trebui determinată de principiul minimax. Prin aderarea la strategia noastră maximin, pentru orice comportament al inamicului ne garantăm, evident, un câștig egal cu prețul mai mic al jocului α. Astfel de strategii combinate, constând în folosirea mai multor strategii pure, alternând după o lege aleatorie cu un anumit raport de frecvență, sunt numite în teoria jocurilor strategii mixte

Strategie mixtă Sa jucătorul A este aplicarea strategiilor pure A1,A1,…,Ai,…,Am cu probabilități p1,p2,…pi,…pm, iar suma probabilităților este egală cu 1: . Strategiile mixte ale jucătorului A sunt scrise ca o matrice

sau ca șir Sa=(p1,p2,…,pi,…,pm).

În mod similar, strategiile mixte ale jucătorului B sunt notate cu:

Sau Sb=(q1,q2,…,qi,…,qn),

unde suma probabilităţilor de apariţie a strategiilor este egală cu 1: .

Evident, fiecare strategie pură este un caz special de una mixtă, în care toate strategiile, cu excepția uneia, sunt aplicate cu frecvențe (probabilități) zero, iar aceasta este folosită cu o frecvență (probabilitate) de 1.

Se dovedește că, folosind nu numai strategii pure, ci și mixte, este posibil ca fiecare joc finit să obțină o soluție, adică o pereche de astfel de strategii (în cazul general mixte), astfel încât atunci când ambii jucători le folosesc, câștigul va fi egal cu prețul jocului, iar atunci când Orice abatere unilaterală de la strategia optimă poate schimba profitul doar într-o direcție nefavorabilă pentru deviant. Deci, pe baza principiului minimax, se determină soluție optimă (sau soluţie) jocuri: acestea sunt o pereche de strategii optime în cazul general, mixt, având următoarea proprietate: dacă unul dintre jucători aderă la strategia sa optimă, atunci nu poate fi profitabil ca celălalt să se abată de la propria sa. Se numește profitul corespunzător soluției optime cu costul jocului v . Prețul jocului satisface inegalitatea:

Unde α și β sunt prețurile mai mici și mai mari ale jocului.

Declarația declarată constituie conținutul așa-numitului teorema fundamentală a teoriei jocurilor. Această teoremă a fost demonstrată pentru prima dată de John von Neumann în 1928. Demonstrațiile cunoscute ale teoremei sunt relativ complexe; Prin urmare, vom da doar formularea acestuia.

Fiecare joc finit are cel puțin o soluție optimă, posibil printre strategii mixte.

Din teorema principală rezultă că fiecare joc finit are un preț.

Lăsați-l să fie – o pereche de strategii optime. Dacă o strategie pură este inclusă într-o strategie mixtă optimă cu o probabilitate diferită de zero, atunci se numește activ (util) .

Corect teorema strategiilor active: dacă unul dintre jucători se ține de strategia sa mixtă optimă, atunci câștigul rămâne neschimbat și egal cu costul jocului v, dacă al doilea jucător nu depășește limitele strategiilor sale active.

Jucătorul poate folosi oricare dintre strategiile sale active în forma sa pură și, de asemenea, le poate amesteca în orice proporție.

Această teoremă are o mare importanță practică - oferă modele specifice pentru găsirea strategiilor optime în absența unui punct de șa.

Sa luam in considerare joc de dimensiune 2x2, care este cel mai simplu caz al unui joc finit. Dacă un astfel de joc are un punct de șa, atunci soluția optimă este o pereche de strategii pure corespunzătoare acestui punct.

Un joc în care nu există nici un punct de șa, în conformitate cu teorema fundamentală a teoriei jocurilor soluţia optimă există şi este determinată de o pereche de strategii mixteȘi.

Pentru a le găsi, folosim teorema strategiilor active. Dacă jucătorul Aține de strategia sa optimă , atunci câștigurile sale medii vor fi egale cu prețul jocului v, indiferent de strategia activă pe care o folosește jucătorul ÎN. Pentru un joc 2x2, orice strategie pură a adversarului este activă dacă nu există un punct de mijloc. Câștigurile jucătorului A(pierderea jucătorului ÎN)– o variabilă aleatoare a cărei așteptare matematică (valoare medie) este prețul jocului. Prin urmare, câștigul jucătorului mediu A(strategia optimă) va fi egală cu v atât pentru prima cât și pentru al doilea inamic.

Lăsați jocul să fie dat de o matrice a plăților.

Câștigurile medii ale jucătorilor A, dacă foloseşte o strategie mixtă optimă şi jucătorul IN - strategia pură B1 (aceasta corespunde primei coloane a matricei de profit R), egal cu prețul jocului v: .

Jucătorul primește aceeași medie de câștiguri A, dacă al 2-lea jucător folosește strategia B2, adică. . Având în vedere acest lucru, obținem un sistem de ecuații pentru determinarea strategiei optime si preturile jocurilor v:

Rezolvând acest sistem, obținem strategia optimă

și prețul jocului.

Aplicarea teoremei despre strategiile active la căutare – strategia optimă a jucătorului ÎN, constatăm că pentru orice strategie pură de jucător A (A1 sau A2) pierderea medie a jucătorilor ÎN egal cu prețul jocului v, adică

Atunci strategia optimă este determinată de formulele: .

Problema rezolvării unui joc, dacă matricea lui nu conține un punct de șa, este mai dificilă, cu cât valorile sunt mai mari. m Și n. Prin urmare, în teoria jocurilor matriceale se consideră metode prin care soluția unor jocuri se reduce la rezolvarea altora, mai simple, în special, prin reducerea dimensiunii matricei. Dimensiunea matricei poate fi redusă prin excludere duplicarea si evident neprofitabile strategii.

Duplicat sunt numite strategii care corespund acelorași valori ale elementelor din matricea de plată, adică matricea conține rânduri (coloane) identice.

Dacă toate elementele rândului i al matricei sunt mai mici decât elementele corespunzătoare ale rândului k, atunci strategia i-a pentru jucător A neprofitabil (câștig mai mic).

Dacă toate elementele coloanei R-a a matricei sunt mai mari decât elementele corespunzătoare ale coloanei j-a, atunci pentru jucător ÎN Strategia r-th este neprofitabilă (pierderea este mai mare).

Procedura de eliminare a strategiilor duplicate și evident neprofitabile ar trebui să precedă întotdeauna soluția jocului.

23. Interpretarea geometrică a jocului 2x2

Soluție de joc 2x2 permite o interpretare geometrică clară.

Fie ca jocul să fie specificat de matricea de plată P=(aij), i, j=1,2.

Pe axa absciselor (Fig.) vom reprezenta un grafic unitate segmentul A1A2; punctul A1 ( X=0) descrie strategia A1, punctul A2 ( X=1) descrie strategia A2, iar toate punctele intermediare ale acestui segment sunt strategii mixte Sa ale primului jucător, iar distanța de la Sa până la capătul drept al segmentului este probabilitatea p1 a strategiei A1 , distanța până la capătul stâng – probabilitatea p2 a strategiei A2 .

Să desenăm două perpendiculare pe axa absciselor prin punctele A1 și A2: axa I-I și axa II-II. Pe axa I-I vom reprezenta castigurile pentru strategia A1; pe axa II-II – profituri pentru strategia A2.

Dacă jucătorul A folosește strategia A1, atunci câștigul său cu strategia B1 a jucătorului B este a11, iar cu strategia B2 este egal cu a12. Numerele a11 și a12 de pe axa I corespund punctelor B1 și B2.

Dacă jucătorul A folosește strategia A2, atunci câștigul său cu strategia B1 a jucătorului B este a21, iar cu strategia B2 este egal cu a22. Numerele a21 și a22 corespund punctelor B1 și B2 de pe axa II.

Conectăm punctele B1 (I) și B1 (II); B2 (I) și B2 (II). Avem două linii drepte. Direct B1B1– dacă jucătorul A aplică o strategie mixtă (orice combinație de strategii A1 și A2 cu probabilități p1 și p2) iar jucătorul B folosește strategia B1. Jucătorul câștigă A corespunde unui punct situat pe această linie. Beneficiul mediu corespunzător strategiei mixte este determinat de formula a11p1+a21p2 și este reprezentat de punctul M1 pe dreapta B1B1.

În mod similar, construim segmentul B2B2, corespunzător utilizării strategiei B2 de către al doilea jucător. În acest caz, câștigul mediu este determinat de formula a12p1+a22p2 și este reprezentat de punctul M2 pe B2B2 direct.

Trebuie să găsim strategia optimă S*a, adică una pentru care beneficiul minim (pentru orice comportament ÎN) s-ar întoarce la maxim. Pentru asta vom construi limita inferioară a câștigurilor pentru strategiile B1B2 , adică linia întreruptă B1NB2 marcată în Fig. linie îndrăzneață. Acest limita inferioară va exprima câștigurile minime ale jucătorului A cu oricare dintre strategiile sale mixte; punctN , în care acest câștig minim atinge un maxim, și determină soluția (strategia optimă) și prețul jocului. Punct ordonat N există un preț pentru joc v. Coordonatele punctului N găsim ca coordonate ale punctelor de intersecție ale dreptelor B1B1 și B2B2. În cazul nostru, soluția jocului a fost determinată de punctul de intersecție al strategiilor. Cu toate acestea, acest lucru nu va fi întotdeauna cazul.

Geometric, se poate determina strategia optimă ca jucător A, la fel și jucătorul ÎN;în ambele cazuri se folosește principiul minimax, dar în al doilea caz nu se construiește limita inferioară, ci superioară a câștigurilor și nu se determină maximul, ci minimul.

Dacă matricea de plată conține numere negative, atunci pentru a rezolva problema grafic este mai bine să treceți la o nouă matrice cu elemente nenegative; Pentru a face acest lucru, este suficient să adăugați numărul pozitiv corespunzător elementelor matricei originale. Soluția jocului nu se va schimba, dar prețul jocului va crește cu acest număr. Metoda grafică poate fi folosită pentru a rezolva jocul 2×n, m×2.

24. Reducerea unui joc de matrice la o problemă de programare liniară

În cazul general, jocul m×n nu are o interpretare geometrică clară. Soluția sa este destul de intensivă în muncă pentru mari TȘi n, cu toate acestea, nu are dificultăți fundamentale, deoarece se poate reduce la rezolvarea unei probleme de programare liniară. Să o arătăm.

Fie jocul m×n dat de matricea plăților . Jucător A are strategii A1,A2,..Ai,..Am , jucător IN - strategii B 1,B 2,..B eu,.. B n. Este necesar să se determine strategiile optime și unde sunt probabilitățile de utilizare a strategiilor pure corespunzătoare Ai,Bj,

Strategia optimă satisface următoarea cerință. Oferă jucătorului A câștiguri medii, nu mai puțin decât prețul jocului v, pentru orice strategie de jucător ÎNși câștiguri egale cu prețul jocului v, cu strategia optimă a jucătorului ÎN. Fără a pierde generalitatea presupunem v> 0; acest lucru se poate realiza prin realizarea tuturor elementelor . Dacă jucătorul A aplică o strategie mixtă împotriva oricărei strategii pure a jucătorului Bj ÎN, apoi primește câștiguri medii , sau așteptarea matematică de a câștiga (adică elemente j-Go coloanele matricei de plată sunt înmulțite termen cu termen cu probabilitățile corespunzătoare strategiilor A1, A2,..Ai,..Am și se adună rezultatele).

Pentru o strategie optimă, toate plățile medii nu sunt mai mici decât prețul jocului v, deci obținem un sistem de inegalități:

Fiecare dintre inegalități poate fi împărțită la un număr. Să introducem noi variabile: . Apoi sistemul ia forma

Golul jucătorului A - maximizați-vă câștigurile garantate, de ex. pretul jocului v.

Împărțind la egalitate, constatăm că variabilele îndeplinesc condiția: . Maximizarea prețului jocului v este echivalent cu minimizarea cantității , Prin urmare, problema poate fi formulată după cum urmează: determinați valorile variabilelor , maastfel încât să satisfacă constrângerile liniare(*) Și în timp ce funcţia liniară (2*) aplicat la minim.

Aceasta este o problemă de programare liniară. Rezolvând problema (1*)–(2*), obținem soluția optimă și strategie optimă .

Pentru a determina strategia optimă, trebuie luat în considerare faptul că jucătorul ÎN urmărește să minimizeze câștigul garantat, adică găsiți max. Variabilele satisfac inegalitățile

care rezultă din faptul că pierderea medie a unui jucător ÎN nu depășește prețul jocului, indiferent de strategia pură pe care o folosește jucătorul A.

Dacă notăm (4*), obținem un sistem de inegalități:

Variabilele satisfac condiția.

Jocul s-a rezumat la următoarea problemă.

Determinați valorile variabilelor , care satisfac sistemul de inegalități (5*)Și maximizează funcția liniară

Soluția problemei de programare liniară (5*), (6*) determină strategia optimă. În același timp, prețul jocului. (7*)

După ce am compilat matrice extinse pentru problemele (1*), (2*) și (5*), (6*), ne asigurăm că o matrice a fost obținută dintr-o alta prin transpunere:

Astfel, problemele de programare liniară (1*), (2*) și (5*), (6*) sunt reciproc duale. Evident, atunci când se determină strategii optime în probleme specifice, ar trebui să se aleagă una dintre problemele reciproc duale a cărei soluție este mai puțin laborioasă și să se găsească o soluție la cealaltă problemă folosind teoremele dualității.

Când rezolvați un joc finit arbitrar de dimensiune m×n, se recomandă să respectați următoarea schemă:

1. Excludeți din matricea de plată strategiile care sunt evident neprofitabile în comparație cu alte strategii. Astfel de strategii pentru jucător A

1. Subiectul și obiectivele cercetării operaționale în economie. Concepte de bază ale teoriei cercetării operaționale.

Subiectul cercetării operaționale îl reprezintă sistemele sau organizațiile de management organizațional, care constau dintr-un număr mare de unități care interacționează care nu sunt întotdeauna consecvente între ele și pot fi opuse.

Scopul cercetării operaționale este de a fundamenta cantitativ deciziile luate pentru gestionarea organizațiilor.

Soluția care se dovedește a fi cea mai benefică pentru întreaga organizație se numește optimă, iar soluția care este cea mai benefică pentru una sau mai multe divizii va fi suboptimă.

Cercetarea operațională este o știință care se ocupă cu dezvoltarea și aplicarea practică a metodelor pentru cel mai optim management al sistemelor organizaționale.

O operațiune este orice eveniment (sistem de acțiuni) unit printr-un singur plan și care vizează atingerea unui scop.

Scopul cercetării operaționale este justificarea cantitativă preliminară a soluțiilor optime.

Orice alegere specifică a parametrilor care depind de noi se numește soluție. Soluțiile optime sunt cele care sunt preferabile altora pe baza anumitor caracteristici.

Parametrii, a căror combinație formează o soluție, se numesc elemente de soluție.

Setul de soluții fezabile sunt date condiții care sunt fixe și nu pot fi încălcate.

Un indicator de eficiență este o măsură cantitativă care vă permite să comparați diferite soluții în ceea ce privește eficiența.

2. Conceptul de planificare și management al rețelei. Model de rețea al procesului și elementelor acestuia.

Metoda de lucru cu graficele de rețea - planificarea rețelei - se bazează pe teoria grafurilor. Tradus din greacă, un graf (grafpho - scriu) reprezintă un sistem de puncte, unele dintre ele fiind legate prin linii - arce (sau muchii). Acesta este un model topologic (matematic) al sistemelor care interacționează. Folosind grafice, puteți rezolva nu numai problemele de planificare a rețelei, ci și alte probleme. Metoda de planificare a rețelei este utilizată la planificarea unui set de lucrări interconectate. Vă permite să vizualizați succesiunea organizațională și tehnologică a muncii și să stabiliți relația dintre acestea. În plus, permite coordonarea operațiunilor de diferite grade de complexitate și identificarea operațiunilor de care depinde durata întregii lucrări (adică, evenimentul organizațional), precum și concentrarea asupra finalizării la timp a fiecărei operațiuni.

Baza planificării și managementului rețelei este modelul de rețea (NM), care modelează un set de lucrări și evenimente interconectate care reflectă procesul de realizare a unui anumit scop. Poate fi prezentat sub forma unui grafic sau tabel.

Concepte de bază ale modelului de rețea:

Eveniment, muncă, cale.

Evenimentele sunt rezultatul unuia sau mai multor joburi. Nu au prelungire în timp.

O cale este un lanț de joburi care se succed, conectând vârfurile de început și de sfârșit.

Durata călătoriei este determinată de suma duratelor lucrărilor sale constitutive.

3. Construirea și organizarea unei diagrame de rețea.

Un model de rețea este utilizat ca model care reflectă relațiile tehnologice și organizaționale ale procesului de lucru de construcție și instalare în sistemele de planificare și management al rețelei (NPS).

Un model de rețea este o reprezentare grafică a proceselor, a cărei implementare duce la atingerea unuia sau mai multor obiective stabilite, indicând relațiile stabilite între aceste procese. Diagrama de rețea este un model de rețea cu parametri de timp calculati.

Structura diagramei de rețea, care determină dependența reciprocă a activităților și evenimentelor, se numește topologia sa.

Munca este un proces de producție care necesită timp, forță de muncă și resurse materiale, care, la finalizare, duce la obținerea unor rezultate.

O dependență (lucrare fictivă) care nu necesită timp este descrisă cu o săgeată punctată. Munca fictivă este folosită într-o diagramă de rețea pentru a arăta relațiile dintre evenimente și activități.

Diagrama de rețea folosește timpul, costul și alte caracteristici ale muncii.

Muncă continuă - timpul necesar pentru finalizarea acestei lucrări în zile lucrătoare sau alte unități de timp care sunt aceleași pentru toate lucrările din programul de rețea. Durata muncii poate fi fie o anumită (deterministă) fie o variabilă aleatoare specificată de legea distribuției sale.

Costul lucrării reprezintă costurile directe necesare pentru finalizarea acesteia, în funcție de durata și condițiile acestei lucrări.

Resursele sunt caracterizate prin nevoia de unități fizice necesare pentru a finaliza un anumit loc de muncă.

Calitatea, fiabilitatea și alți indicatori ai muncii servesc ca caracteristici suplimentare ale muncii.

Un eveniment este faptul de finalizare a unuia sau mai multor joburi, care este necesar și suficient pentru începerea unuia sau mai multor joburi ulterioare. Fiecărui eveniment i se atribuie un număr numit cod. Fiecare job este definit de două evenimente: un cod de eveniment de început, notat cu i, și un cod de eveniment de sfârșit, notat cu j.

Evenimentele care nu au lucrare anterioară sunt numite inițiale; evenimentele care nu au altele ulterioare sunt finite.

1 Direcția construcției rețelei poate fi de natură diferită. Diagrama de rețea poate fi construită de la evenimentul inițial la cel final și de la cel final la cel inițial, precum și de la oricare dintre evenimente la cel inițial sau final.

2 Când construiți o rețea, sunt rezolvate următoarele probleme:

Ce lucrări trebuie finalizate pentru a începe această lucrare;

Ce lucrare este indicat să efectuați în paralel cu această muncă;

3 Programul inițial al rețelei se construiește fără a ține cont de durata lucrării care alcătuiește rețeaua.

4 Forma graficului trebuie să fie simplă și ușor de perceput vizual.

5 Între două evenimente poate apărea o singură lucrare. În timpul construcției clădirilor și structurilor, lucrările se pot executa secvenţial, în paralel sau simultan, unele secvenţial şi altele în paralel, în urma cărora se dezvoltă diverse dependenţe între lucrările individuale.

Numerotarea (codificarea) evenimentelor se realizează după finalizarea construcției rețelei, începând de la evenimentul inițial până la cel final.

4. Calea critică a diagramei de rețea. Rezerve de timp. Datele timpurii și târzii ale evenimentelor și lucrează în programul de rețea.

Într-o diagramă de rețea, pot exista mai multe căi între evenimentele de început și de sfârșit. Calea cu cea mai lungă durată se numește critică. Calea critică determină durata totală a activității. Toate celelalte căi au o durată mai scurtă și, prin urmare, munca efectuată în ele are rezerve de timp.

Calea critică este indicată pe diagrama rețelei prin linii groase sau duble (săgeți).

Două concepte sunt de o importanță deosebită atunci când se elaborează o diagramă de rețea:

Demararea timpurie a lucrărilor este o perioadă înainte de care această lucrare nu poate fi începută fără a încălca secvența tehnologică acceptată. Este determinată de calea cea mai lungă de la evenimentul inițial până la începutul acestei lucrări

Finalizarea cu întârziere a lucrărilor este cel mai recent termen limită pentru finalizarea lucrărilor, la care durata totală a lucrărilor nu crește. Este determinată de calea cea mai scurtă de la un eveniment dat până la finalizarea tuturor lucrărilor.

Terminarea timpurie este un termen înainte de care lucrarea nu poate fi finalizată. Este egal cu începerea timpurie plus durata acestei lucrări

Pornire tardivă - o perioadă după care lucrarea nu poate fi începută fără creșterea duratei totale de construcție. Este egal cu terminarea târzie minus durata acestei lucrări.

Dacă un eveniment este la sfârșitul unui singur job (adică doar o săgeată este îndreptată către el), atunci sfârșitul timpuriu al acestui job coincide cu începutul timpuriu al celui următor.

Rezerva generală (plină) este timpul maxim pentru care finalizarea unei anumite lucrări poate fi amânată fără a crește durata totală a lucrării. Este determinată de diferența dintre începutul târziu și devreme (sau sfârșitul târziu și devreme - care este același lucru).

Rezerva privată (gratuită) este timpul maxim pentru care execuția unui anumit job poate fi întârziată fără a modifica începerea anticipată a următoarei. Această rezervă este posibilă numai atunci când evenimentul include două sau mai multe locuri de muncă (dependențe), i.e. două sau mai multe săgeți (solide sau punctate) sunt îndreptate spre acesta. Apoi, doar unul dintre aceste locuri de muncă va avea o terminare timpurie care coincide cu începerea timpurie a următoarei lucrări, dar pentru restul acestea vor fi valori diferite. Această diferență pentru fiecare loc de muncă va fi rezerva sa privată.

5. Programare dinamică. Principiul lui Bellman al optimității și controlului.

Programarea dinamică este una dintre cele mai puternice metode de optimizare. Specialiști de diferite profiluri se ocupă de problemele de luare a deciziilor raționale, alegerea celor mai bune opțiuni și management optim. Printre metodele de optimizare, programarea dinamică ocupă o poziție specială. Această metodă este extrem de atractivă datorită simplității și clarității principiului său de bază - principiul optimității. Domeniul de aplicare al principiului optimității este extrem de larg; gama de probleme la care poate fi aplicat nu a fost încă pe deplin conturată. De la bun început, programarea dinamică a fost un mijloc de rezolvare practic a problemelor de optimizare.

Pe lângă principiul optimității, principala metodă de cercetare, un rol important în aparatul de programare dinamică îl joacă ideea de a scufunda o problemă specifică de optimizare într-o familie de probleme similare. A treia caracteristică, care o deosebește de alte metode de optimizare, este forma rezultatului final. Aplicarea principiului optimității și a principiului imersiunii în procese discrete, în mai multe etape, conduce la ecuații funcționale recurente privind valoarea optimă a criteriului de calitate. Ecuațiile rezultate fac posibilă redactarea constantă a controalelor optime pentru problema inițială. Avantajul aici este că problema calculării controlului pentru întregul proces este împărțită într-un număr de probleme mai simple de calculare a controlului pentru etapele individuale ale procesului.

Principalul dezavantaj al metodei este, în cuvintele lui Bellman, „blestemul dimensionalității” - complexitatea acesteia crește catastrofal odată cu creșterea dimensiunii problemei.

6. Problema repartizării fondurilor între întreprinderi.

Putem spune că procedura de construire a controlului optim folosind metoda de programare dinamică este împărțită în două etape: preliminară și finală. În etapa preliminară, pentru fiecare pas, SOE se determină în funcție de starea sistemului (realizată ca urmare a pașilor anteriori), și de câștigul optim condiționat la toate etapele rămase, începând de la aceasta, tot în funcție de stare. . În etapa finală, se determină controlul optim (necondiționat) pentru fiecare pas. Optimizarea preliminară (condițională) se realizează pas cu pas în ordine inversă: de la ultimul pas la primul; optimizare finală (necondiționată) - tot în trepte, dar într-o ordine firească: de la primul pas la ultimul. Dintre cele două etape de optimizare, prima este incomparabil mai importantă și consumatoare de timp. După parcurgerea primei etape, parcurgerea celei de-a doua nu prezintă nicio dificultate: nu rămâne decât să „citești” recomandările deja pregătite la prima etapă.

7. Enunțarea problemei de programare liniară.

Programarea liniară este un instrument popular pentru rezolvarea problemelor economice care se caracterizează prin prezența unui criteriu (de exemplu, maximizarea veniturilor din producție prin alegerea optimă a unui program de producție sau, de exemplu, reducerea costurilor de transport etc.). Problemele economice sunt caracterizate de limitări de resurse (materiale și/sau financiare). Ele sunt scrise sub forma unui sistem de inegalități, uneori sub formă de egalități.

Din punctul de vedere al prognozării intervalelor de preț acceptabile (sau volumelor de vânzări) în cadrul metodei neparametrice generalizate, utilizarea programării liniare înseamnă:

Criteriul este prețul MAX al următorului produs din grupul de interes f.

Variabilele controlate sunt prețurile tuturor produselor din grupa f.

Limitările problemei noastre de prognoză folosind metoda neparametrică generalizată sunt:

a) un sistem de inegalități (constrângeri asupra raționalității comportamentului consumatorului) (vezi 4.2. Prognoza în cadrul metodei neparametrice generalizate);

b) cerința de nenegativitate a variabilelor controlate (în problema noastră de prognoză vom cere ca prețurile pentru produsele din grupa f să nu scadă sub 80% din valorile prețurilor la ultimul moment);

c) constrângere bugetară sub formă de egalitate - cerința ca valoarea costurilor pentru achiziționarea produselor din grupa f să fie constantă (ținând cont de inflația de 15%, de exemplu).

8. Metodă grafică de rezolvare a problemelor de programare liniară.

Metoda grafică se bazează pe interpretarea geometrică a problemei de programare liniară și este utilizată în principal la rezolvarea problemelor în spațiul bidimensional și doar a unor probleme în spațiul tridimensional, deoarece este destul de dificil să se construiască un poliedru de soluții care se formează ca rezultat al intersectării semispatiilor. În general, este imposibil să descrii grafic o problemă într-un spațiu de dimensiuni mai mari de trei.

Fie specificată problema de programare liniară într-un spațiu bidimensional, adică constrângerile conțin două variabile.

Găsiți valoarea minimă a unei funcții

(2.1) Z = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2.3) x1 0, x2 0

Să presupunem că sistemul (2.2) în condiția (2.3) este consistent și poligonul său soluție este mărginit. Fiecare dintre inegalitățile (2.2) și (2.3), așa cum s-a menționat mai sus, definește un semiplan cu linii de limită: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0 , x2=0 . Funcția liniară (2.1) pentru valori fixe ale lui Z este ecuația unei drepte: C1x1 + C2x2 = const. Să construim un poligon de soluții ale sistemului de constrângeri (2.2) și un grafic al funcției liniare (2.1) la Z = 0 (Fig. 2.1). Atunci problemei de programare liniară pusă i se poate da următoarea interpretare. Aflați punctul poligonului soluție în care linia de sprijin C1x1 + C2x2 = const și funcția Z atinge un minim.

Valorile lui Z = C1x1 + C2x2 cresc în direcția vectorului N = (C1, C2), așa că mutam linia dreaptă Z = 0 paralelă cu ea însăși în direcția vectorului X. Din fig. 2.1 rezultă că linia dreaptă de două ori devine o linie de referință în raport cu poligonul soluție (în punctele A și C), și ia valoarea minimă în punctul A. Coordonatele punctului A (x1, x2) se găsesc prin rezolvarea sistem de ecuații ale dreptelor AB și AE.

Dacă poligonul soluție este o zonă poligonală nemărginită, atunci sunt posibile două cazuri.

Cazul 1. Linia C1x1 + C2x2 = const, care se deplasează în direcția vectorului N sau opus acestuia, intersectează constant poligonul soluție și nu este un suport pentru acesta în niciun punct. În acest caz, funcția liniară nu este mărginită pe poligonul soluție atât deasupra cât și dedesubt (Fig. 2.2).

Cazul 2. Linia dreaptă, în mișcare, devine totuși un suport relativ la poligonul soluțiilor (Fig. 2.2, a - 2.2, c). Apoi, în funcție de tipul de zonă, funcția liniară poate fi mărginită de sus și nelimitată de jos (Fig. 2.2, a), mărginită de jos și nelimitată de sus (Fig. 2.2, b), sau mărginită atât de jos, cât și de dedesubt. de sus (Fig. 2.2, c).

9. Metoda simplex.

Metoda simplex este cea principală în programarea liniară. Rezolvarea problemei începe prin a lua în considerare unul dintre vârfurile poliedrului de condiții. Dacă vârful studiat nu corespunde maximului (minimului), atunci se deplasează la cel învecinat, crescând valoarea funcției de obiectiv la rezolvarea problemei la maxim și scăzând-o la rezolvarea problemei la minim. Astfel, trecerea de la un vârf la altul îmbunătățește valoarea funcției obiectiv. Deoarece numărul de vârfuri ale poliedrului este limitat, într-un număr finit de pași se garantează găsirea valorii optime sau stabilirea faptului că problema este de nerezolvat.

Această metodă este universală, aplicabilă oricărei probleme de programare liniară în formă canonică. Sistemul de constrângeri aici este un sistem de ecuații liniare în care numărul de necunoscute este mai mare decât numărul de ecuații. Dacă rangul sistemului este r, atunci putem alege r necunoscute, pe care le exprimăm în termeni de necunoscute rămase. Pentru certitudine, presupunem că sunt selectate primele necunoscute consecutive X1, X2, ..., Xr. Atunci sistemul nostru de ecuații poate fi scris ca

Metoda simplex se bazează pe o teoremă numită teorema fundamentală a metodei simplex. Printre planurile optime ale unei probleme de programare liniară în formă canonică există în mod necesar o soluție de referință la sistemul său de constrângeri. Dacă planul optim al problemei este unic, atunci acesta coincide cu o soluție de referință. Există un număr finit de soluții de sprijin diferite pentru sistemul de constrângeri. Prin urmare, o soluție a problemei în formă canonică ar putea fi căutată prin căutarea soluțiilor de referință și alegând dintre ele cea pentru care valoarea F este cea mai mare. Dar, în primul rând, toate soluțiile de referință sunt necunoscute și trebuie găsite și, în al doilea rând, în problemele reale există o mulțime de aceste soluții și căutarea directă este cu greu posibilă. Metoda simplex este o anumită procedură de enumerare direcționată a soluțiilor suport. Pe baza unei anumite soluții de referință găsite în prealabil folosind un anumit algoritm al metodei simplex, calculăm o nouă soluție de referință pe care valoarea funcției obiectiv F nu este mai mică decât pe cea veche. După o serie de pași, ajungem la o soluție de referință, care este planul optim.

10. Enunțarea problemei transportului. Metode de determinare a planurilor de referință.

Există m puncte de plecare („furnizori”) și n puncte de consum („consumatori”) ale unui produs identic. Pentru fiecare articol sunt definite următoarele:

ai - volumele de producție ale furnizorului i, i = 1, …, m;

вj - cererea celui de-al j-lea consumator, j= 1,…,n;

сij este costul transportului unei unități de produs de la punctul Ai, al-lea furnizor, la punctul Bj, al-lea consumator.

Pentru claritate, este convenabil să prezentați datele sub forma unui tabel, care se numește un tabel al costurilor de transport.

Este necesar să se găsească un plan de transport în care cererea tuturor consumatorilor să fie pe deplin satisfăcută, în timp ce ar exista suficiente provizii de la furnizori, iar costurile totale de transport să fie minime.

Planul de transport se referă la volumul de transport, adică cantitatea de mărfuri care trebuie transportată de la al-lea furnizor la al-lea consumator. Pentru a construi un model matematic al problemei, este necesar să introduceți m·n variabile xij, i= 1,..., n, j= 1,..., m, fiecare variabilă xij denotă volumul de transport din punct Ai la punctul Bj. Setul de variabile X = (xij) va fi planul care trebuie găsit pe baza formulării problemei.

Aceasta este o condiție pentru rezolvarea problemelor de transport închise și deschise (CTZ).

Evident, pentru ca problema 1 să fie rezolvabilă, este necesar ca cererea totală să nu depășească volumul producției de la furnizori:

Dacă această inegalitate este strict satisfăcută, atunci problema se numește „deschisă” sau „dezechilibrată”, dar dacă , atunci problema se numește problemă de transport „închisă” și va avea forma (2):

Stare de echilibru.

Aceasta este o condiție pentru rezolvarea problemelor de transport închis (CTP).

11. Algoritm pentru rezolvarea problemei transportului.

Aplicarea algoritmului necesită respectarea unui număr de cerințe preliminare:

1. Costul transportului unei unități de produs din fiecare punct de producție la fiecare destinație trebuie să fie cunoscut.

2. Trebuie cunoscut stocul de produse la fiecare punct de producție.

3. Trebuie cunoscute cerințele de produs în fiecare punct de consum.

4. Oferta totală trebuie să fie egală cu cererea totală.

Algoritmul pentru rezolvarea problemei transportului constă din patru etape:

Etapa I: Prezentați datele sub forma unui tabel standard și găsiți orice alocare fezabilă de resurse. Acceptabilă este o distribuție de resurse care vă permite să satisfaceți toată cererea la destinații și să eliminați întregul stoc de produse din punctele de producție.

Etapa 2. Verificarea optimității alocării resurselor rezultate

Etapa 3. Dacă alocarea rezultată a resurselor nu este optimă, atunci resursele sunt redistribuite, reducând costul transportului.

Etapa 4. Reverificarea optimității alocării resurselor rezultate.

Acest proces iterativ se repetă până când se obține soluția optimă.

12. Modele de gestionare a stocurilor.

În ciuda faptului că orice model de gestionare a stocurilor este conceput pentru a răspunde la două întrebări principale (când și cât de mult), există un număr semnificativ de modele, a căror construcție utilizează o varietate de instrumente matematice.

Această situație se explică prin diferența dintre condițiile inițiale. Baza principală pentru clasificarea modelelor de gestionare a stocurilor este natura cererii de produse depozitate (reamintim că din punctul de vedere al unei gradații mai generale, acum luăm în considerare doar cazurile cu cerere independentă).

Deci, în funcție de natura cererii, modelele de gestionare a stocurilor pot fi

determinat;

probabilistică.

La rândul său, cererea deterministă poate fi statică, când intensitatea consumului nu se modifică în timp, sau dinamică, când cererea sigură se poate modifica în timp.

Cererea probabilistică poate fi staționară, atunci când funcția de densitate de probabilitate a cererii nu se modifică în timp, și nestaționară, când funcția de densitate de probabilitate se modifică în funcție de timp. Clasificarea de mai sus este ilustrată de figură.

Cel mai simplu caz este cazul cererii statice deterministe pentru produse. Cu toate acestea, acest tip de consum este destul de rar în practică. Cele mai complexe modele sunt modele de tip non-staționar.

Pe lângă natura cererii de produse, atunci când se construiesc modele de gestionare a stocurilor, trebuie luați în considerare mulți alți factori, de exemplu:

termenele limită pentru onorarea comenzilor. Durata perioadei de achiziție poate fi constantă sau poate fi o variabilă aleatorie;

procesul de completare a stocurilor. Poate fi instantaneu sau distribuit în timp;

existența unor restricții privind capitalul de lucru, spațiul de depozitare etc.

13. Sisteme de așteptare (QS) și indicatori ai eficienței acestora.

Sistemele de așteptare (QS) sunt sisteme de tip special care implementează execuția repetată a sarcinilor similare. Astfel de sisteme joacă un rol important în multe domenii ale economiei, finanțelor, producției și vieții de zi cu zi. Ca exemple de QS în domeniul financiar și economic; în sferă putem cita bănci de diferite tipuri (comerciale, de investiții, ipotecare, inovatoare, de economii), organizații de asigurări, societăți pe acțiuni de stat, societăți comerciale, firme, asociații, cooperative, inspectorate fiscale, servicii de audit, diverse sisteme de comunicare (inclusiv centrale telefonice), complexe de incarcare si descarcare (porturi, statii de marfa), benzinarii, diverse intreprinderi si organizatii de servicii (magazine, birouri de informatii, coafor, case de bilete, case de schimb valutar, ateliere de reparatii, spitale). Sisteme precum rețele de calculatoare, sisteme de colectare, stocare și procesare a informațiilor, sisteme de transport, zone de producție automatizate, linii de producție, diverse sisteme militare, în special sisteme de apărare antiaeriană sau antirachetă, pot fi considerate și ele ca un fel de QS

Fiecare QS include în structura sa un anumit număr de dispozitive de service, care se numesc canale de service (dispozitive, linii). Rolul canalelor poate fi jucat de diverse aparate, persoane care efectuează anumite operațiuni (casieri, operatori, coafor, vânzători), linii de comunicații, mașini, macarale, echipaje de reparații, căi ferate, benzinării etc.

Sistemele de așteptare pot fi cu un singur canal sau multicanal.

Fiecare QS este proiectat pentru a deservi (îndeplinește) un anumit flux de aplicații (cerințe) care ajung la intrarea sistemului, de cele mai multe ori nu în mod regulat, ci în momente aleatorii. Serviciul aplicațiilor, în acest caz, nu durează, de asemenea, un timp constant, precunoscut, ci un timp aleatoriu, care depinde de multe motive aleatorii, uneori necunoscute nouă. După deservirea cererii, canalul este eliberat și gata să primească următoarea solicitare. Natura aleatorie a fluxului de cereri și timpul de deservire a acestora duce la o încărcare neuniformă a QS: alteori, aplicațiile neservite se pot acumula la intrarea QS, ceea ce duce la o supraîncărcare a QS și, uneori, când există canale libere la intrarea QS-ului, nu vor exista aplicații, ceea ce duce la o subîncărcare a QS-ului, adică de ex. la inactivitatea canalelor sale. Aplicațiile care se acumulează la intrarea în QS fie „intră” în coadă, fie, din cauza imposibilității de a rămâne în continuare în coadă, lasă QS-ul neservit.

Indicatori ai eficacității funcționării perechii „CMO - consumator”, unde consumatorul este înțeles ca întregul set de aplicații sau unele dintre sursele acestora (de exemplu, venitul mediu adus de CMO pe unitatea de timp etc. ). Acest grup de indicatori se dovedește a fi util în cazurile în care unele venituri primite din aplicațiile de service și costurile de service sunt măsurate în aceleași unități. Acești indicatori sunt, de obicei, de natură foarte specifică și sunt determinați de specificul QS, cererile care sunt servite și disciplina de serviciu.

14. Ecuații de dinamică pentru stări probabiliste (ecuații Kolmogorov). Limitarea probabilităților stărilor.

Diferențiând formal ecuația Kolmogorov–Chapman în raport cu s la s = 0, obținem ecuația Kolmogorov directă:

Diferențiând formal ecuația Kolmogorov-Chapman în raport cu t la t = 0, obținem ecuația inversă a lui Kolmogorov

Trebuie subliniat că pentru spațiile cu dimensiuni infinite operatorul nu mai este neapărat continuu și poate să nu fie definit peste tot, de exemplu, să fie un operator diferențial în spațiul distribuțiilor.

Dacă numărul de stări ale sistemului S este finit și pare posibilă trecerea de la fiecare stare (într-un anumit număr de pași) la una alta, atunci probabilitățile limită ale stărilor există și, de asemenea, nu depind de starea inițială. a sistemului.

În fig. se arată un grafic al stărilor și tranzițiilor care satisfac condiția enunțată: din orice stare, sistemul poate trece mai devreme sau mai târziu în orice altă stare. Condiția nu va fi îndeplinită atunci când direcția săgeții 4-3 din graficul din Fig se schimbă, ci în sens invers.

Să presupunem că condiția enunțată este îndeplinită și, prin urmare, există probabilitățile limită:

Probabilitățile limită vor fi notate cu aceleași litere ca și probabilitățile stărilor, în timp ce ele înseamnă numere, nu variabile (funcții de timp).

Este clar că probabilitățile limită ale stărilor trebuie să se adună la unitate: În consecință, în sistem se stabilește un anumit regim staționar limitator: chiar dacă sistemul își schimbă aleatoriu propriile stări, probabilitatea fiecăreia dintre aceste stări nu depind de timp și fiecare dintre ele are loc cu o probabilitate constantă, care este timpul relativ mediu în care sistemul rămâne în această stare.

15. Procesul morții și al reproducerii.

Să numim un proces Markov de moarte și reproducere cu timp continuu un astfel de proces care poate lua numai valori întregi nenegative; modificări în acest proces pot apărea în orice moment al timpului t, în timp ce în orice moment al timpului poate fie să crească cu unu, fie să rămână neschimbat.

Fluxurile de reproducere λi(t) vor fi numite fluxuri Poisson conducând la o creștere a funcției X(t). În consecință, μi(t) sunt fluxurile morții care conduc la o scădere a funcției X(t).

Să compunem ecuația lui Kolmogorov din grafic:

Dacă fluxul este în stare finită:

Sistemul de ecuații Kolmogorov pentru procesul de moarte și reproducere cu un număr limitat de stări are forma:

Procesul de reproducere pură este un proces de moarte și reproducere în care intensitățile tuturor fluxurilor morții sunt egale cu zero.

Procesul morții pure este un proces de moarte și reproducere în care intensitățile tuturor fluxurilor de reproducere sunt egale cu zero.

16. Sisteme de așteptare cu defecțiuni.

Cea mai simplă dintre problemele luate în considerare în cadrul teoriei cozilor de așteptare este modelul unui QS cu un singur canal cu defecțiuni sau pierderi.

Trebuie remarcat faptul că în acest caz numărul de canale este 1 (). Acest canal primește un flux Poisson de cereri, a cărui intensitate este egală cu . Timpul afectează intensitatea:

Dacă o aplicație ajunge pe un canal care nu este în prezent gratuit, este respinsă și nu mai este listată în sistem. Serviciul de aplicații se efectuează într-un timp aleatoriu, a cărui distribuție este implementată în conformitate cu legea exponențială cu parametrul:

17. Sisteme de asteptare cu asteptare.

O solicitare primită când canalul este ocupat este pusă în coadă și așteaptă serviciul.

Sistem cu lungime limitată la coadă. Să presupunem mai întâi că numărul de locuri în coadă este limitat de m, adică dacă o aplicație ajunge într-un moment în care există deja m aplicații în coadă, aceasta lasă sistemul neservit. În viitor, prin direcționarea m către infinit, vom obține caracteristicile unui QS cu un singur canal fără restricții privind lungimea cozii.

Vom numerota stările QS-ului în funcție de numărul de aplicații din sistem (atât în ​​curs de service, cât și în așteptare):

— canalul este liber;

— canalul este ocupat, nu există coadă;

— canalul este ocupat, o cerere este în coadă;

—canalul este ocupat, k - 1 cereri sunt în coadă;

— canalul este ocupat, tone de aplicații sunt la coadă.

18. Metode de luare a deciziilor în condiţii de conflict. Jocuri Matrix. Jocuri de strategie pure și mixte.

Un joc cu matrice este un joc finit cu sumă zero de doi jucători, în care câștigul jucătorului 1 este specificat sub forma unei matrice (rândul matricei corespunde numărului strategiei aplicate a jucătorului 2, coloana corespunde la numărul strategiei aplicate a jucătorului 2; la intersecția rândului și coloanei matricei se află câștigul jucătorului 1, corespunzător strategiilor aplicate).

Pentru jocurile cu matrice, s-a dovedit că oricare dintre ele are o soluție și poate fi găsită cu ușurință prin reducerea jocului la o problemă de programare liniară.

Un joc cu matrice cu sumă zero pentru doi jucători poate fi considerat următorul joc abstract pentru doi jucători.

Primul jucător are m strategii i = 1,2,...,m, al doilea jucător are n strategii j = 1,2,...,n. Fiecare pereche de strategii (i,j) este asociată cu un număr aij, care exprimă câștigul jucătorului 1 în detrimentul jucătorului 2 dacă primul jucător acceptă strategia sa i-a, iar 2 - strategia sa j-a.

Fiecare jucător face o mișcare: jucătorul 1 își alege a-a strategie (i=), 2 - a-a strategie (j=), după care jucătorul 1 primește câștigul aij în detrimentul jucătorului 2 (dacă aij

Fiecare strategie a jucătorului i=; j = este adesea numit o strategie pură.

Definiție. Strategia mixtă a unui jucător este setul complet de probabilități de a folosi strategiile sale pure.

Astfel, dacă jucătorul 1 are m strategii pure 1,2,...,m, atunci strategia sa mixtă x este un set de numere x = (x1,..., xm) care satisfac relațiile

xi³ 0 (i= 1,m), =1.

În mod similar, pentru jucătorul 2, care are n strategii pure, strategia mixtă y este mulțimea de numere

y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.

Deoarece de fiecare dată când un jucător folosește o strategie pură exclude utilizarea alteia, strategiile pure sunt evenimente incompatibile. Mai mult, sunt singurele evenimente posibile.

Strategia pură este un caz special de strategie mixtă. Într-adevăr, dacă într-o strategie mixtă se aplică orice i-a strategie pură cu probabilitatea 1, atunci toate celelalte strategii pure nu sunt aplicate. Și această strategie pură este un caz special de strategie mixtă. Pentru a păstra secretul, fiecare jucător își aplică propriile strategii, indiferent de alegerile celuilalt jucător.

19. Metoda geometrică de rezolvare a unui joc matricial.

Soluția jocurilor de dimensiunea 2xn sau nx2 permite o interpretare geometrică clară. Astfel de jocuri pot fi rezolvate grafic.

Pe planul XY de-a lungul axei absciselor, graficăm un singur segment A1A2 (Figura 5.1). Să atribuim fiecărui punct al segmentului o strategie mixtă U = (u1, u2). Mai mult, distanța de la un punct intermediar U până la capătul drept al acestui segment este probabilitatea u1 de a alege strategia A1, distanța până la capătul din stânga este probabilitatea u2 de a alege strategia A2. Punctul A1 corespunde strategiei pure A1, punctul A2 corespunde strategiei pure A2.

La punctele A1 și A2 vom restabili perpendicularele și vom pune câștigurile jucătorilor pe ele. Pe prima perpendiculară (coincidentă cu axa OY) arătăm profitul jucătorului A când folosește strategia A1, pe a doua - când folosește strategia A2. Dacă jucătorul A folosește strategia A1, atunci câștigul său cu strategia B1 a jucătorului B este egal cu 2, iar cu strategia B2 este egal cu 5. Numerele 2 și 5 de pe axa OY corespund punctelor B1 și B2. În mod similar, pe a doua perpendiculară găsim punctele B"1 și B"2 (câștiguri 6 și 4).

Prin conectarea punctelor B1 și B"1, B2 și B"2, obținem două linii drepte, distanța de la care până la axa OX determină profitul mediu pentru orice combinație de strategii corespunzătoare.

De exemplu, distanța de la orice punct de pe segmentul B1B"1 până la axa OX determină câștigul mediu al jucătorului A pentru orice combinație de strategii A1 și A2 (cu probabilități u1 și u2) și strategia B1 a jucătorului B.

Ordonatele punctelor aparținând liniei întrerupte B1MB"2 determină câștigul minim al jucătorului A atunci când folosește orice strategii mixte. Această valoare minimă este cea mai mare în punctul M, prin urmare, acest punct corespunde strategiei optime U* = ( ,), iar ordonata sa este egală cu costul jocului v .

Găsim coordonatele punctului M ca fiind coordonatele punctului de intersecție a dreptelor B1B"1 și B2B"2.

Pentru a face acest lucru, trebuie să cunoașteți ecuațiile liniilor. Puteți crea astfel de ecuații folosind formula pentru ecuația unei linii care trece prin două puncte:

Să creăm ecuații în linie dreaptă pentru problema noastră.

Linia B1B"1: = sau y = 4x + 2.

Direct B2B"2: = sau y = -x + 5.

Obținem sistemul: y = 4x + 2,

Să rezolvăm: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Astfel, U = (2/5, 3/5), v = 22/5.

20. Jocuri bi-matrice.

Un joc bimatrix este un joc finit de doi jucători cu o sumă diferită de zero, în care plățile fiecărui jucător sunt specificate prin matrice separat pentru jucătorul corespunzător (în fiecare matrice, un rând corespunde strategiei jucătorului 1, o coloană corespunde strategiei jucătorului 2, la intersecția rândului și coloanei din prima matrice este câștigul jucătorului 1, în a doua matrice - câștigul jucătorului 2.)

O teorie a comportamentului optim al jucătorului a fost dezvoltată și pentru jocurile bimatrice, dar rezolvarea unor astfel de jocuri este mai dificilă decât jocurile obișnuite cu matrice.

21. Jocuri cu statistici. Principii și criterii pentru luarea deciziilor în condiții de incertitudine totală și parțială.

În cercetarea operațională, este obișnuit să distingem trei tipuri de incertitudini:

incertitudinea obiectivelor;

incertitudinea cunoștințelor noastre despre mediu și factorii care acționează în acest fenomen (incertitudinea naturii);

incertitudinea acțiunilor unui partener sau adversar activ sau pasiv.

În clasificarea de mai sus, tipul de incertitudine este considerat din perspectiva unuia sau altui element al modelului matematic. De exemplu, incertitudinea obiectivelor este reflectată la stabilirea unei sarcini în alegerea fie a criteriilor individuale, fie a întregului vector al efectului benefic.

Pe de altă parte, celelalte două tipuri de incertitudini afectează în principal formularea funcției obiective a ecuațiilor de constrângere și metoda deciziei. Desigur, afirmația de mai sus este destul de condiționată, așa cum este, într-adevăr, orice clasificare. Îl prezentăm doar cu scopul de a evidenția câteva trăsături suplimentare ale incertitudinilor care trebuie reținute în procesul decizional.

Ideea este că, pe lângă clasificarea incertitudinilor discutată mai sus, este necesar să se țină cont de tipul (sau „genul”) acestora din punctul de vedere al relației lor cu aleatorietatea.

Pe această bază, se poate distinge incertitudinea stocastică (probabilistă), atunci când factorii necunoscuți sunt stabili statistic și, prin urmare, reprezintă obiecte obișnuite ale teoriei probabilităților - variabile aleatoare (sau funcții aleatoare, evenimente etc.). În acest caz, toate caracteristicile statistice necesare (legile de distribuție și parametrii acestora) trebuie cunoscute sau determinate la stabilirea problemei.

Un exemplu de astfel de sarcini poate fi, în special, un sistem de întreținere și reparare a oricărui tip de echipament, un sistem de organizare a răririlor etc.

Un alt caz extrem poate fi incertitudinea de tip non-stohastic (în cuvintele lui E.S. Ventzel - „incertitudine proastă”), în care nu există ipoteze despre stabilitatea stocastică. În sfârșit, putem vorbi despre un tip intermediar de incertitudine, atunci când o decizie este luată pe baza unor ipoteze despre legile de distribuție a variabilelor aleatoare. În același timp, decidentul trebuie să țină cont de pericolul unei discrepanțe între rezultatele sale și condițiile reale. Acest risc de nepotrivire este formalizat folosind coeficienți de risc.

Luarea deciziilor în condiții de risc se poate baza pe unul dintre următoarele criterii:

criteriul valorii așteptate;

combinații de valoare așteptată și varianță;

nivelul limită cunoscut;

cel mai probabil eveniment din viitor.

Operațiune Orice eveniment (sistem de acțiuni) unit printr-un singur plan și care vizează atingerea unui scop anume este numit. Există întotdeauna o operație controlat eveniment, adică Este posibil să decideți cum să selectați anumiți parametri care caracterizează organizarea sa. Acești parametri sunt numiți variabile de control.

Orice alegere specifică a unor astfel de variabile este numită decizie. Deciziile pot fi de succes și nereușite, rezonabile și nerezonabile. Optimal numiți astfel de soluții care, după unele criterii, sunt de preferat altora.

Scopul cercetării operaționale este o justificare cantitativă preliminară a soluțiilor optime, dintre care pot fi mai multe. Alegerea finală a deciziei depășește sfera cercetării operaționale și se face prin intermediul așa-numitei teorii a deciziei.

Orice sarcină de cercetare operațională are condiții inițiale de „disciplinare”, adică astfel de date inițiale care sunt fixate de la bun început și nu pot fi încălcate. Luate împreună, ele formează așa-numitul set de soluții posibile.

Pentru a compara diferite soluții în ceea ce privește eficacitatea, trebuie să aveți un criteriu cantitativ numit indicator de performanta(sau funcție obiectivă). Acest indicator este ales pentru a reflecta orientarea țintă a operațiunii.

Adesea operația este însoțită de acțiunea unor factori aleatori. Apoi, ca indicator al eficienței, nu se ia valoarea în sine pe care s-ar dori să o optimizeze, ci valoarea medie (sau așteptarea matematică) a acesteia.

Uneori, o operație însoțită de factori aleatori urmărește un astfel de scop A, care poate fi atins complet sau deloc (cum ar fi „da-nu”). Apoi probabilitatea atingerii acestui obiectiv este aleasă ca indicator al eficienței p(A). (Dacă p(A) = 0 sau 1, apoi ajungem la problema „cutiei negre” cunoscută în cibernetică.)

Alegerea greșită a indicatorului de performanță este foarte periculoasă. Operațiunile organizate după un criteriu ales fără succes pot duce la costuri și pierderi nejustificate. (De exemplu, „arborele” ca principal criteriu de evaluare a activității economice a unei întreprinderi.)

1.3. Prezentarea generală a problemei cercetării operaționale

Problemele de cercetare operațională se împart în două categorii: a) înainte și b) înapoi.

Sarcini directe răspunde la întrebarea: cu ce va fi egal indicatorul de eficiență? Z, dacă în condiții date y  Y se va lua o decizie X  X. Pentru a rezolva o astfel de problemă, se construiește un model matematic care permite exprimarea indicatorului de eficiență prin condiții date și o soluție și anume:

Unde
factori specificați (date inițiale),

variabile de control (decizie),

Z– indicator de eficiență (funcție țintă),

F– dependenţa funcţională între variabile.

Această dependență este exprimată diferit în diferite modele. Dependenta intre Și exprimate de obicei în termeni de restricţii asupra

Dacă tipul de dependenţă F este cunoscut, apoi indicatorul Z se găseşte prin substituţie directă Și în această funcționalitate.

Probleme inverse raspunde la intrebarea: cum in aceste conditii alege o soluție
astfel încât indicatorul de performanţă Z transformat la maxim (minim). Această problemă se numește o problemă de optimizare a soluției.

Să se rezolve problema directă, adică. este specificat modelul de operare și este specificat tipul de dependență F celebru. Atunci problema inversă (adică problema de optimizare) poate fi formulată după cum urmează.

Trebuie să găsești o astfel de decizie
la care indicatorul de eficienţă Z = opta:

Această formulă se citește astfel: Z există o valoare optimă
preluate toate soluţiile incluse în setul de soluţii posibile X.

Metodă de găsire a extremului indicatorului de eficiență Zși soluția optimă asociată ar trebui întotdeauna ales pe baza caracteristicilor funcției Fși tipul de restricții impuse soluției. (De exemplu, o problemă clasică de programare liniară.)

Problemă de cercetare operațională

Introducere ……………………………………………………………………………………..3

1. Concepte de bază și definiții ale cercetării operaționale……..……..5

2. Expunere generală a problemei cercetării operaționale…………..…………6

Concluzie…………………………………………………………………………………..13

Literatură……………………………………………………………………………………….14

Introducere

Cercetare operațională - o disciplină științifică care se ocupă cu dezvoltarea și aplicarea practică a metodelor pentru managementul cât mai eficient al diverselor sisteme organizaționale.

Managementul oricărui sistem este implementat ca un proces care respectă anumite legi. Cunoștințele lor ajută la determinarea condițiilor necesare și suficiente pentru implementarea acestui proces. Pentru a face acest lucru, toți parametrii care caracterizează procesul și condițiile externe trebuie cuantificați și măsurați. Prin urmare, scopul cercetării operaționale este justificarea cantitativă a deciziilor luate privind organizarea managementului.

La rezolvarea unei probleme specifice de management, utilizarea metodelor de cercetare operațională presupune:

Construirea de modele economice și matematice pentru probleme decizionale în situații complexe sau în condiții de incertitudine;

Studierea relațiilor care determină ulterior luarea deciziilor și stabilirea criteriilor de performanță care să permită evaluarea avantajului unui anumit curs de acțiune.

Exemple de sarcini de cercetare operațională care reflectă specificul acesteia includ următoarele sarcini.

Sarcina 1. Pentru a asigura calitatea înaltă a produselor fabricate, în fabrică este organizat un sistem de control al prelevarii. Este necesar să alegeți astfel de forme de organizare - de exemplu, să atribuiți dimensiunile loturilor de control, să indicați succesiunea operațiunilor de control, să determinați regulile de respingere - pentru a asigura calitatea necesară la costuri minime.

Sarcina 2. Pentru a vinde un anumit lot de produse sezoniere, se creează o rețea de magazine temporare de vânzare cu amănuntul. Este necesar să se selecteze parametrii rețelei - numărul de puncte, locația acestora, numărul de personal - astfel încât să se asigure o eficiență economică maximă a vânzării.

Sarcina 3. Până la o dată dată, este necesar să se efectueze un examen medical în masă a unui grup de populație pentru a identifica anumite boli. Materialele, echipamentele și personalul au fost alocate pentru examinare. Este necesar să se elaboreze un astfel de plan de examinare - să se stabilească numărul de posturi medicale, amplasarea acestora, tipul și numărul de analize, pentru a identifica cel mai mare procent posibil de bolnavi.

De asemenea, este necesar să se constate probleme legate de utilizarea resurselor, despre amestecuri, despre utilizarea capacităților, despre materialele de tăiere, o problemă de transport etc., la care este necesar să se găsească o soluție atunci când unele criteriu de performanta(de exemplu, profitul, veniturile, costurile cu resursele etc.) ia o valoare maximă sau minimă.

Sarcinile date se referă la diferite domenii de practică, dar au caracteristici comune: în fiecare caz vorbim despre unele eveniment controlat (operare), urmărind un anumit ţintă.În sarcina 1 - aceasta este organizarea controlului de prelevare pentru a asigura calitatea produselor; în sarcina 2 - organizarea de magazine temporare de vânzare cu amănuntul în scopul desfășurării vânzărilor sezoniere; în sarcina 3 - un examen medical în masă pentru a determina procentul de cazuri.

Fiecare sarcină conține câteva conditii desfășurarea acestui eveniment, în cadrul căruia este necesar să se desfășoare solutie - astfel încât evenimentul aduce unele beneficii. Condițiile de desfășurare a operațiunii în fiecare sarcină sunt mijloacele de care dispunem, timpul, echipamentul, tehnologia, iar soluția din sarcina 1 este alegerea formei de control - mărimea loturilor de control, regulile de respingere; în sarcina 2 - în alegerea numărului de puncte de plasare și a numărului de personal; în sarcina 3 - în alegerea numărului de posturi medicale, tipului și numărului de analize.

1. Concepte de bază și definiții ale cercetării operaționale

Operațiune- orice eveniment controlat care vizează atingerea unui scop. Rezultatul operațiunii depinde de metoda de implementare a acesteia, de organizare, în caz contrar - de alegerea anumitor parametri.

Orice alegere specifică a parametrilor este numită decizie.

Optimal luați în considerare acele soluții care, dintr-un motiv sau altul, sunt preferabile altora. De aceea sarcina principala cercetarea operațională este cantitativă preliminară justificarea solutiilor optime.

Nota 1. Ar trebui să se acorde atenție enunțului problemei: the a lua decizii depășește sfera cercetării operaționale și este responsabilitatea persoanei responsabile sau a grupului de persoane care poate ține cont de alte considerații decât cele care sunt justificate matematic.

Nota 2. Dacă în unele probleme de cercetare operațională soluția optimă este aceea în care ia un anumit criteriu de eficiență

valoare maximă sau minimă, atunci în alte sarcini acest lucru nu este deloc necesar. Astfel, în sarcina 2, numărul optim de puncte de vânzare cu amănuntul și personalul din acestea poate fi considerat astfel încât timpul mediu de serviciu pentru clienți să nu depășească, de exemplu, 5 minute, iar lungimea medie a cozii în orice moment să nu mai fie. peste 3 persoane.

Pentru a aplica metode de cercetare cantitativă, este necesar să construim modelul matematic al operației. La construirea unui model, operația, de regulă, este simplificată, schematizată, iar schema de funcționare este descrisă folosind unul sau altul aparat matematic.

Model operațiuni - aceasta este o descriere destul de precisă a operației folosind aparate matematice (diferite tipuri de funcții, ecuații, sisteme de ecuații și inegalități etc.). Întocmirea unui model al unei operații necesită înțelegerea esenței fenomenului descris și cunoașterea aparatului matematic.

Eficiența operațiunii - gradul de adaptabilitate a acestuia la sarcină se exprimă cantitativ sub forma unui criteriu de eficiență – funcția țintă. De exemplu, în problema utilizării resurselor, criteriul eficienței este profitul din vânzarea produselor manufacturate, care trebuie maximizat; în problema transportului, costurile totale ale transportului mărfurilor de la furnizori la consumatori, care trebuie reduse la minimum. . Alegerea criteriului de eficacitate determină valoarea practică a studiului. (Un criteriu ales incorect poate fi dăunător, deoarece operațiunile organizate în funcție de un astfel de criteriu de eficiență conduc uneori la costuri nejustificate.)

2. Expunere generală a problemei cercetării operaționale

Este important să înțelegem metodologia de construire a modelelor de probleme de cercetare operațională. Toți factorii incluși în descrierea operațiunii pot fi împărțiți în două grupuri:

factori constanți(condiții de funcționare), pe care nu le putem influența. Să le notăm prin α1, α2,... ;

factori dependenți(elementele soluției) X 1, x2, ...; pe care, în anumite limite, le putem alege la discreția noastră.

De exemplu, în problema utilizării resurselor, factorii constanți ar trebui să includă rezervele de resurse de fiecare tip, matricea de producție, ale cărei elemente determină consumul de materii prime de fiecare tip pe unitatea de producție a fiecărui tip. Elemente ale soluției - un plan de producție pentru fiecare tip de produs.

Un criteriu de performanță exprimat de o funcție numită ţintă, depinde de factorii ambelor grupuri, deci funcția obiectiv Z poate fi scris sub forma

Z= f (x1, x2, ..., α1, α2, ...)

Toate modelele de cercetare operațională pot fi clasificate în funcție de natura și proprietățile operațiunii, natura problemelor rezolvate și caracteristicile metodelor matematice utilizate.

De remarcat, în primul rând, marele clasa de modele de optimizare. Astfel de probleme apar atunci când se încearcă optimizarea planificării și managementului sistemelor complexe, în primul rând sistemelor economice. Problema de optimizare poate fi formulată în formă generală: găsiți variabilele x1, x2, ..., x n , satisfacerea sistemului de inegalități (ecuații)

g i (x1, x2, x3,..., X n )<= b i , i = 1, 2,..., n (0.1)

Și transformarea funcției obiectiv la un maxim (sau minim), adică

Z= f (x1, x2, ..., X n ) - m ah (m în ) (0.2)

(Condițiile pentru non-negativitatea variabilelor, dacă există, sunt incluse în restricțiile (0.1))

Să luăm în considerare o altă problemă tipică pentru cercetarea operațională - problema clasica de consum, de mare importanţă în analiza economică.

Să fie P tipuri de bunuri și servicii, din care cantități (în unități naturale) x1, x2, ..., X n,la preturi corespunzatoare p 1, p 2, ..., p n pentru o unitate. Costul total al acestor bunuri și servicii este ∑ p i X i .

Nivelul consumului Z poate fi exprimat printr-o anumită funcție Z= f (x1, x2, ..., X n ) , chemat Functie utilitara. Este necesar să găsiți un astfel de set de bunuri și servicii x1, x2, ..., X n dat suma venitului I, la asigura un nivel maxim de consum, acestea.

Z= f (x1, x2, ..., X n ) - m Oh (0.3)

dat fiind

∑ p i X i <= eu (0.4)

X i >= 0 ( i = 1, 2,..., n ) (0.5)

Soluții la această problemă care depind de prețuri p 1, p 2, ..., p n si cuantumul venitului eu, sunt numite funcții de cerere.

Este evident că problema de consum considerată (0.3)-(0.5), ca și multe altele, este un caz special al problemei generale (0.1)-(0.2) formulată mai sus pentru a determina extremul funcției P variabile sub anumite restricții, de ex. sarcina pentru condiţional extremum.

În cazurile în care funcţiile fȘi g i, în problema (0.1)-(0.2) sunt de cel puțin două ori diferențiabile, putem folosi clasic metode de optimizare. Cu toate acestea, utilizarea acestor metode în cercetarea operațională este foarte limitată, deoarece sarcina de a determina extremul condiționat al unei funcții de i variabile este foarte dificilă din punct de vedere tehnic: metoda face posibilă determinarea extremului local și datorită multidimensionalității funcția, determinând valoarea maximă (sau minimă) (extremul global) se poate dovedi a fi foarte laborioasă - mai ales că acest extrem este posibil la limita regiunii soluției. Metodele clasice nu funcționează deloc dacă setul de valori ale argumentelor valide este discret sau funcția Z este dat într-un tabel. În aceste cazuri, pentru rezolvarea problemei se folosesc metodele (0.1)-(0.2). programare matematică.

Dacă criteriul de performanţă Z= f (x1, x2, ..., X n ) (0.2) reprezintă o funcție liniară, iar funcțiile g i (x1, x2, x3,..., X n ) în sistemul de constrângeri (0.1) sunt de asemenea liniare, atunci o astfel de problemă este o problemă programare liniară. Dacă, pe baza conținutului, soluțiile sale trebuie să fie numere întregi, atunci această problemă programare liniară cu numere întregi. Dacă criteriul de eficiență și (sau) sistemul de restricții sunt specificate de funcții neliniare, atunci avem problema programare neliniară.În special, dacă funcțiile indicate au proprietăți de convexitate, atunci problema rezultată este o problemă programare convexă.

Dacă într-o problemă de programare matematică există o variabilă de timp și criteriul de eficiență (0.2) este exprimat nu în mod explicit în funcție de variabile, ci indirect - prin ecuații care descriu fluxul operațiilor în timp, atunci o astfel de problemă este o problemă programare dinamică.

Dacă criteriul de eficiență (0.2) și sistemul de restricții (0.1) sunt specificate prin funcții de formă Cu*( X 1^α 1 )*( X 2^α 2 )...( X n ^α n ) , atunci avem problema programare geometrică. Dacă funcţiile fși/sau g iîn expresiile (0.2) și (0.1) depind de parametri, atunci obținem problema programare parametrica, dacă aceste funcții sunt de natură aleatorie, sarcina programare stocastică. Dacă este imposibil să găsiți algoritmul optim exact din cauza unui număr excesiv de mare de opțiuni de soluție, atunci recurgeți la metode euristic programare, permițându-vă să reduceți semnificativ numărul de opțiuni pe care le căutați și să găsiți, dacă nu optimă, atunci o soluție destul de bună, satisfăcătoare din punct de vedere practic.

Dintre metodele enumerate de programare matematică, cea mai comună și dezvoltată este programarea liniară. Acesta acoperă o gamă largă de sarcini de cercetare operațională.

Sarcini de planificare și management al rețelei luați în considerare relația dintre datele de finalizare a unui complex mare de operațiuni (lucrări) și orele de începere a tuturor operațiunilor complexului. Aceste sarcini constau în găsirea duratei minime a unui set de operațiuni, a raportului optim al valorilor costurilor și a momentului de implementare a acestora.

Probleme de coadă sunt dedicate studiului și analizei sistemelor de servicii cu cozi de aplicații sau cerințe și constau în determinarea indicatorilor de performanță ai sistemelor, a caracteristicilor optime ale acestora, de exemplu, determinarea numărului de canale de servicii, a timpului de serviciu etc.

Sarcini de gestionare a stocurilor constau in gasirea valorilor optime ale nivelului de stoc (punctul de comanda) si al marimii comenzii. Particularitatea unor astfel de sarcini este că, odată cu creșterea nivelului stocurilor, pe de o parte, costurile de stocare a acestora cresc, dar, pe de altă parte, pierderile datorate unei posibile lipsuri a produsului depozitat scad.

Probleme de alocare a resurselor apar în cursul unui anumit set de operațiuni (lucrări) care trebuie efectuate cu resursele disponibile limitate și este necesar să se găsească repartizarea optimă a resurselor între operații sau alcătuirea operațiunilor.

Sarcini de reparare și înlocuire a echipamentelor sunt relevante din cauza uzurii echipamentelor și a necesității înlocuirii acestuia în timp. Sarcinile se rezumă la determinarea momentului optim, a numărului de reparații și inspecții preventive, precum și la momentul înlocuirii echipamentelor cu echipamente modernizate.

Programarea (programarea) sarcinilor constau in determinarea succesiunii optime a operatiilor (de exemplu, prelucrarea pieselor) pe diverse tipuri de echipamente.

Sarcini de planificare și plasare constau in determinarea numarului si amplasarii optime a noilor obiecte, tinand cont de interactiunea acestora cu obiectele existente si intre ele.

Probleme de selectare a rutei sau reţea problemele întâlnite cel mai des în studiul diverselor probleme din sistemele de transport și comunicații și constau în determinarea celor mai economice rute.

Dintre modelele de cercetare operațională, modelele de luare a deciziilor optime în situații de conflict, studiate de teoria jocului. Situațiile conflictuale în care interesele a două (sau mai multe) părți se ciocnesc, urmărind scopuri diferite, includ o serie de situații din domeniul economiei, dreptului, afacerilor militare etc. În problemele de teoria jocurilor, este necesar să se elaboreze recomandări pentru comportamentul rezonabil al participanților la conflict, pentru a determina strategiile optime ale acestora.

În practică, în cele mai multe cazuri, succesul unei operațiuni este evaluat nu de unul, ci de mai multe criterii simultan, dintre care unul trebuie maximizat, celelalte ar trebui reduse la minimum. Aparatul matematic poate fi de asemenea util în cazuri probleme de cercetare operațională cu criterii multiple, măcar ajută la renunțarea la soluțiile evident nereușite.

Pentru a selecta o funcție obiectivă dintr-o varietate de criterii, inclusiv cele care se contrazic între ele (de exemplu, profit și cheltuială), este necesar să se stabilească o prioritate criterii. Să notăm f 1 (x), f 2 (X), ..., f n (X)(Aici X - argument condițional). Să fie aranjate în ordinea descrescătoare a priorității. În funcție de anumite condiții, există practic două opțiuni:

Criteriul este ales ca functie obiectiv f 1 (X), având cea mai mare prioritate;

Se are în vedere o combinație

f ( X ) = ω 1 * f 1 ( X ) + ω 2 * f 2 ( X ) + …+ ω n * f n ( X ) , (0.6)

Unde ω 1 , ω 2 , … ω n- unii coeficienți (greutăți).

Magnitudinea f (X), care ia în considerare toate criteriile într-o anumită măsură, este selectată ca funcție obiectiv.

In conditii de certitudine ω i- numere, f i (X)- funcții. În condiţii de incertitudine f i (X) se poate dovedi a fi aleatoriu și în schimb f i (X) așteptarea matematică a sumei (0,6) ar trebui considerată ca funcție obiectiv.

O încercare de a reduce o problemă cu mai multe criterii la o problemă cu un singur criteriu de eficiență (funcția obiectivă) în majoritatea cazurilor nu dă rezultate satisfăcătoare. O altă abordare constă în eliminarea ("culling") din setul de soluții admisibile a soluțiilor evident nereușite care sunt inferioare celorlalți în ceea ce privește toate criteriile. Ca urmare a acestei proceduri, așa-numitul efectiv(sau " Pareto") soluții, al căror set este de obicei semnificativ mai mic decât cel original. Și alegerea finală a unei soluții de „compromis” (nu optimă după toate criteriile, care, de regulă, nu există, dar acceptabil după aceste criterii) rămâne la persoana – decident.

Concluzie

Oamenii de știință ruși L.V. au adus o mare contribuție la crearea unui aparat matematic modern și la dezvoltarea multor domenii de cercetare operațională. Kantorovich, N.P. Buslenko, E.S. Ventzel, N.N. Vorobyov, N.N. Moiseev, D.B. Yudin și mulți alții. De remarcat este rolul academicianului L.V. Kantorovich, care în 1939, după ce a început să planifice funcționarea unităților fabricii de placaj, a rezolvat mai multe probleme: despre cea mai bună încărcare a echipamentelor, despre tăierea materialelor cu pierderi minime, despre distribuirea mărfurilor între mai multe tipuri de transport etc. L.V. Kantorovich a formulat o nouă clasă de probleme extremale condiționate și a propus o metodă universală de rezolvare a acestora, punând bazele unei noi direcții în matematica aplicată - programarea liniară.

Contribuții semnificative la formarea și dezvoltarea cercetării operaționale au fost aduse de oamenii de știință străini R. Akof, R. Bellman, G. Danzig, G. Kuhn, J. Neumann, T. Saaty, R. Churchman, A. Kofman și alții.

Metodele de cercetare operațională, ca orice metodă matematică, simplifică întotdeauna și grosieră problema într-un grad sau altul, reflectând uneori procese neliniare cu modele liniare, sisteme stocastice cu cele deterministe, procese dinamice cu modele statice etc. Viața este mai bogată decât orice schemă. Prin urmare, nu ar trebui nici să exagerăm importanța metodelor cantitative în cercetarea operațională și nici să o minimizăm citând exemple de soluții nereușite. Este oportun să menționăm în acest sens definiția umoristic paradoxală a cercetării operaționale făcută de unul dintre creatorii săi, T. Saaty, drept „arta de a da răspunsuri proaste acelor întrebări practice la care se poate răspunde și mai rău prin alte metode”.

Literatură

1. Kremer N. Sh., Putko B. A., Trishin I. M., Fridman M. N. Cercetarea operațiunilor în economie: Manual pentru universități - M.: UNITI, 2002.

2. Ventzel E.S. Cercetare operațională. Obiective, principii, metodologie - M.: Nauka, 1980.

3. Gorelik V.A., Ushakov I.A. Cercetare operațională. - M.: Inginerie mecanică, 1986.

ÎN. Slinkin

Manual pentru studenții universităților pedagogice

specializarea în Informatică

Shadrinsk, 2003

Slinkina I.N.

Cercetare operațională. Manual educațional și metodologic. – Shadrinsk: editura Institutului Pedagogic de Stat Shadrinsk, 2002. - 106 p.

Slinkina I.N. – Candidat la Științe Pedagogice

Manualul prezintă partea teoretică a cursului de Cercetare operațională. Este destinat studenților cu normă întreagă și cu fracțiune de normă ai facultăților care urmează specialitatea „Informatică”.

© Institutul Pedagogic de Stat Shadrinsk

© Slinkina I.N., 2002

Întrebări pentru unitățile din cursul „Cercetare operațională” 5

1.1. Subiectul și sarcinile cercetării operaționale 7

1.2. Concepte și principii de bază ale cercetării operaționale 8

1.3. Modele matematice ale operațiilor 10

1.4. Conceptul de programare liniară 12

1.5. Exemple de probleme de programare liniară economică. Cea mai bună utilizare a resurselor Problema 13

1.6. Exemple de probleme de programare liniară economică. Problema alegerii tehnologiilor optime 15

1.7. Exemple de probleme de programare liniară economică. Problema amestecului 16

1.8. Exemple de probleme de programare liniară economică. Problema transportului 17

1.9. Tipuri de bază de înregistrare a problemelor de programare liniară 19

1.10. 21 de metode de conversie

1.11. Trecerea la forma canonică 22

1.12. Tranziția la o formă simetrică de înregistrare 25

2.1. Interpretarea geometrică a problemei de programare liniară 28

2.2. Rezolvarea problemelor de programare liniară prin metoda grafică 29

2.3. Proprietăți ale soluțiilor problemelor de programare liniară 34

2.4. Ideea generală a metodei simplex 35

2.5. Construirea planului de referință inițial la rezolvarea problemelor de programare liniară folosind metoda simplex 36

2.6. Semnul optimității planului de referință. Tabele simplex 40

2.7. Trecerea la planul de referință în cel mai rău caz. 44

2.8. Transformări simplex 46

2.9. Optim alternativ (semnul infinitului setului de planuri de referință) 51

2.10. Semn de nelimitare a funcției obiectiv 52

2.11. Conceptul de degenerare. Monotonitatea și caracterul finit al metodei simplex. Buclă 53

2.12. Conceptul de dualitate pentru probleme de programare liniară simetrică 54

3.1. Probleme duale asimetrice 57

3.2. Modele deschise și închise ale problemei de transport 61

3.3. Construirea planului de referință inițial. Colțul de nord-vest Regula 63

3.4. Construirea planului de referință inițial. Regula elementului minim 64

3.5. Construirea planului de referință inițial. Metoda Vogel 64

3.6. Metoda potențială 65

3.7. Rezolvarea problemelor de transport cu restricții de capacitate 69

3.8. Exemple de probleme de programare discretă. Problemă cu transportul containerelor. Problema de atribuire 71

3.9. Esența metodelor de optimizare discretă 72

3.10. Problemă de programare convexă 74

3.11. Metoda multiplicatorului Lagrange 75

3.12. Metode de gradient 77

4.1. Metode de sancționare și funcții de barieră 78

4.2. Programare dinamică. Noțiuni de bază. Esența metodelor de soluție 79

4.3. Programare stocastică. Concepte de bază 81

4.4. Jocuri cu matrice cu sumă zero 83

4.5. Strategii pure și mixte și proprietățile lor 85

4.6. Proprietățile strategiilor pure și mixte 88

4.7. Reducerea unui joc matrice la ZLP 92

4.8. Probleme de teoria cozilor. Clasificarea sistemelor de așteptare 94

4.9. Fluxuri de evenimente 96

4.10. Schema morții și a reproducerii 97

4.11. Formula lui Little 99

4.12. Cele mai simple sisteme de așteptare 101

Întrebări pentru blocuri la cursul „Cercetare operațională”

Blocul 1

1. Subiectul și obiectivele cercetării operaționale.

2. Concepte și principii de bază ale cercetării operaționale.

3. Modele matematice ale operaţiilor.

4. Conceptul de programare liniară.

5. Exemple de probleme de programare liniară economică. Sarcină

6. Exemple de probleme de programare liniară economică. Problema alegerii tehnologiilor optime.

7. Exemple de probleme de programare liniară economică. Problema cu amestecurile.

8. Exemple de probleme de programare liniară economică. Problema transportului.

9. Tipuri de bază de scriere a problemelor de programare liniară.

10. Metode de conversie.

11. Trecerea la forma canonică.

12. Trecerea la o formă simetrică de înregistrare.

Blocul 2

1. Interpretarea geometrică a problemei de programare liniară.

2. Rezolvarea problemelor de programare liniară folosind metoda grafică.

3. Proprietăţi ale soluţiilor problemei de programare liniară.

4. Ideea generală a metodei simplex.

5. Construirea planului de referință inițial la rezolvarea problemelor de programare liniară folosind metoda simplex.

6. Semnul optimității planului de referință. Tabele simplex.

7. Tranziția la planul de referință care nu este cel mai rău.

8. Transformări simplex.

9. Optim alternativ (un semn al infinitității setului de planuri de referință).

10. Semn de nelimitare a funcției obiectiv.

11. Conceptul de degenerare. Monotonitatea și caracterul finit al metodei simplex. Buclă.

12. Conceptul de dualitate pentru probleme de programare liniară simetrică.

Blocul 3

1. Probleme duale asimetrice.

2. Modele deschise și închise ale problemei transportului.

3. Construirea planului de referință inițial. Regula „colțul de nord-vest”.

4. Construirea planului de referință inițial. Regula elementului minim.

5. Construirea planului de referință inițial. metoda Vogel.

6. Metoda potenţialelor.

7. Rezolvarea problemelor de transport cu limitări de capacitate.

8. Exemple de probleme de programare discretă. Problemă cu transportul containerelor. Problemă de atribuire.

9. Esența metodelor de optimizare discretă.

10. Problemă de programare convexă.

11. Metoda multiplicatorului Lagrange.

12. Metode de gradient.

Blocul 4

1. Metoda de penalizare și funcții de barieră.

2. Programare dinamică. Noțiuni de bază. Esența metodelor de soluție.

3. Programare stocastică. Noțiuni de bază.

4. Jocuri cu matrice cu sumă zero.

5. Strategii pure și mixte.

6. Proprietățile strategiilor pure și mixte.

7. Reducerea unui joc matrice la un PLP

8. Probleme de teoria cozilor. Clasificarea sistemelor de aşteptare.

9. Fluxuri de evenimente.

10. Schema morții și reproducerii.

11. Formula lui Little.

12. Cele mai simple sisteme de așteptare.

Blocul 1.

Subiectul și sarcinile cercetării operaționale

Starea actuală a științei și tehnologiei, în special, dezvoltarea instrumentelor de calcul computerizat și fundamentarea matematică a teoriilor a făcut posibilă simplificarea semnificativă a soluționării multor probleme puse diferitelor ramuri ale științei. Multe dintre probleme se rezumă la rezolvarea problemei optimizării producției și controlului optim al procesului.

Nevoile practicii au dat naștere unor metode științifice speciale, care sunt combinate convenabil sub denumirea de „cercetare operațională”.

Definiție: Prin cercetare operațională înțelegem aplicarea metodelor matematice, cantitative, pentru a justifica deciziile în toate domeniile activității umane intenționate.

Să se ia unele măsuri pentru a atinge un anumit scop. Persoana (sau grupul de persoane) care organizează evenimentul are întotdeauna o oarecare libertate de alegere: poate fi organizat într-un fel sau altul. O decizie este o alegere dintr-un număr de posibilități disponibile organizatorului.

Necesitatea de a lua decizii și de a testa ipoteza soluției propuse este confirmată matematic de următoarele exemple:

Sarcina 1. Despre cea mai bună utilizare a resurselor.

Compania produce mai multe tipuri de produse. Unele resurse sunt folosite pentru a le realiza (inclusiv uman, energie etc.). Este necesar să se calculeze modul de planificare a activității întreprinderii, astfel încât costurile cu resursele să fie minime și profiturile să fie maximizate.

Sarcina 2. Despre amestecuri.

Este necesar să se pregătească un amestec care are anumite proprietăți. Pentru a face acest lucru, puteți utiliza unele „produse” (pentru calcularea dietelor - produse alimentare, pentru amestecuri de furaje - produse alimentare pentru animale, pentru amestecuri tehnice - aliaje, lichide pentru scopuri tehnice). sarcina este de a selecta numărul optim de produse (după preț) pentru a obține cantitatea optimă de amestec.

Sarcina 3. Problema transportului.

Există o rețea de întreprinderi care produc produse similare de aceeași calitate și o rețea de consumatori ai acestor produse. Consumatorii și furnizorii sunt legați prin căi de comunicație (drumuri, linii de cale ferată, linii aeriene). Au fost stabilite tarifele de transport. Este necesar să se calculeze planul optim pentru transportul produselor, astfel încât costurile de transport să fie minime, nevoile tuturor consumatorilor să fie satisfăcute și toate bunurile să fie îndepărtate de la furnizori.

În fiecare dintre exemplele date, vorbim despre un fel de eveniment care urmărește un scop specific. Sunt specificate unele condiții care caracterizează situația (în special, mijloacele de care se pot dispune). În aceste condiții, este necesar să luați o decizie pentru ca evenimentul planificat să fie într-un fel mai profitabil.

În conformitate cu aceste trăsături generale, sunt dezvoltate metode generale de rezolvare a unor probleme similare, care împreună constituie schema metodologică și aparatul de cercetare operațională.

În prezent, sistemele de control automatizat (ACS) bazate pe utilizarea tehnologiei informatice sunt din ce în ce mai răspândite. Crearea unui sistem de control automat este imposibilă fără o examinare preliminară a procesului controlat folosind metode de modelare matematică. Odată cu amploarea și complexitatea în creștere a evenimentelor, metodele matematice de fundamentare a deciziilor devin din ce în ce mai importante.

Concepte și principii de bază ale cercetării operaționale

Definiție: O operațiune este orice eveniment (sistem de acțiuni) unit printr-un singur plan și care vizează atingerea unui scop.

O operațiune este întotdeauna un eveniment controlat, de exemplu. Depinde de calcule cum să alegeți parametrii care îi caracterizează organizarea. „Organizare” aici este înțeleasă în sensul larg al cuvântului, inclusiv ansamblul mijloacelor tehnice utilizate în operațiune.

Definiție: Orice alegere specifică în funcție de parametrii decisivi se numește decizie.

Definiție: Soluțiile optime sunt cele care, dintr-un motiv sau altul, sunt de preferat altora.

Scopul cercetării operaționale– justificarea cantitativă prealabilă a soluţiilor optime.

Uneori, în urma studiului, se poate indica o singură soluție, strict definită; mult mai des, este posibil să se identifice o zonă de soluții optime aproape echivalente în cadrul căreia se poate face alegerea finală.

Luarea deciziilor în sine depășește sfera cercetării operaționale și intră în competența persoanei responsabile, de cele mai multe ori - un grup de persoane cărora li se acordă dreptul de a face alegerea finală și cărora le revine responsabilitatea pentru această alegere.

Definiție: Parametrii, a căror combinație formează o soluție, se numesc elemente de soluție.

Elementele soluției pot include diverse numere, vectori, funcții, caracteristici fizice etc. Pentru simplitate, vom nota cu x întregul set de elemente ale soluției.

Pe lângă elementele de soluție în orice problemă de cercetare operațională, există și condiții date care sunt fixate în starea problemei și nu pot fi încălcate. În special, astfel de condiții includ mijloace (materiale, tehnice, umane) care pot fi eliminate și alte restricții impuse deciziei. Luate împreună, ele formează așa-numitul „set de soluții posibile”. Să notăm această mulțime X, iar faptul că soluția x aparține acestei mulțimi se va scrie: xОХ.

Pentru a compara diferite soluții în ceea ce privește eficiența, trebuie să aveți un fel de criteriu cantitativ, așa-numitul indicator de eficiență (funcția obiectivă). Acest indicator este selectat astfel încât să reflecte orientarea țintă a operației. Cea mai bună soluție va fi considerată cea care contribuie în maximum la atingerea scopului. Pentru a alege un indicator de performanță Z, trebuie mai întâi să determinați la ce ar trebui să ducă soluția problemei. La alegerea unei soluții, se preferă cea care transformă indicatorul de eficiență Z la maxim sau la minim. De exemplu, aș dori să maximizez venitul dintr-o operațiune; dacă indicatorul eficienței sunt costurile, este indicat să le reduceți la minimum.

Foarte des, operațiunea este însoțită de factori aleatori: „capriciile” naturii, fluctuațiile cererii și ofertei, defecțiuni ale dispozitivelor tehnice etc. În astfel de cazuri, de obicei nu valoarea în sine ar dori să maximizăm (minimizează), ci valoarea medie (așteptările matematice) care este luată ca indicator al eficienței.

Sarcina de a alege un indicator de performanță este rezolvată pentru fiecare problemă în mod individual.

Sarcina 1. Despre cea mai bună utilizare a resurselor.

Obiectivul operațiunii este de a produce numărul maxim de mărfuri. Indicatorul de eficiență Z – profit din vânzarea mărfurilor cu costuri minime de resurse (max Z).

Sarcina 2. Despre amestecuri.

Un indicator natural al eficienței, sugerat de formularea problemei, este prețul produselor necesare amestecului, sub rezerva necesității menținerii proprietăților specificate ale amestecului (min Z).

Sarcina 3. Problema transportului.

Obiectivul operațiunii este de a asigura furnizarea de bunuri către consumatori cu costuri minime de transport. Indicatorul de eficiență Z este costul total al transportului mărfurilor pe unitatea de timp (min Z).