Capitolul 1. Subiectul și sarcinile cercetării operaționale.

§ 1. Ce este cercetarea operațională și ce face.

§ 2. Concepte şi principii de bază ale cercetării operaţionale.

§ 3. Modele matematice ale operaţiilor.

Capitolul 2. Varietăți de sarcini în cercetarea operațională și abordări ale soluționării acestora.

§ 4. Probleme directe şi inverse ale cercetării operaţionale. Sarcini deterministe.

§ 5. Problema alegerii unei soluţii în condiţii de incertitudine.

§ 6. Probleme multicriteriale ale cercetării operaţionale. „Abordarea sistemelor”.

Capitolul 3. Programarea liniară.

§ 7. Probleme de programare liniara.

§ 8. Problema principală a programării liniare.

§ 9. Existenta unei solutii 03LP si modalitati de gasire a acesteia.

§ 10. Problema transportului de programare liniara.

§ 11. Probleme de programare intregi. Conceptul de programare neliniară.

Capitolul 4. Programare dinamică.

§ 12. Metoda de programare dinamică.

§ 13. Exemple de rezolvare a problemelor de programare dinamică.

§ 14. Problema programării dinamice în formă generală. Principiul optimității.

capitolul 5 procese aleatorii Markov.

§ 15. Conceptul unui proces Markov.

§ 16. Fluxuri de evenimente.

§ 17. Ecuaţiile lui Kolmogorov pentru probabilităţi de stare. Probabilitățile finale ale stărilor.

Capitolul 6

§ 18. Sarcini ale teoriei cozii de aşteptare. Clasificarea sistemelor de aşteptare.

§ 19. Schema morții și reproducerii. Mică formulă.

§ 20. Cele mai simple sisteme de asteptare si caracteristicile acestora.

§ 21. Probleme mai complicate în teoria cozilor.

Capitolul 7. Modelarea statistică a proceselor aleatoare (metoda Monte Carlo).

§ 22. Ideea, scopul și domeniul de aplicare al metodei.

§ 23. Lot unic și forme de organizare a acestuia.

§ 24. Determinarea caracteristicilor unui proces aleator staționar dintr-o implementare.

Capitolul 8

§ 25. Subiectul şi problemele teoriei jocurilor.

§ 26. Jocuri matrice antagoniste.

§ 27. Metode de rezolvare a jocurilor finite.

§ 28. Probleme ale teoriei soluţiilor statistice.

SUBIECTUL ŞI OBIECTIVELE CERCETĂRII OPERAŢIONALE

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

În această secțiune, ne vom familiariza cu terminologia, conceptele de bază și principiile științei „cercetării operaționale”.

O operațiune este orice eveniment (un sistem de acțiuni) unit printr-o singură idee și care vizează atingerea unui scop (toate evenimentele discutate în paragrafele 1 - 8 din paragraful anterior sunt „operații”).

O operațiune este întotdeauna un eveniment controlat, adică depinde de noi cum să alegem unii dintre parametrii 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 definită a parametrilor în funcție de noi se numește soluție. Deciziile pot fi de succes și nereușite, rezonabile și nerezonabile. Soluțiile sunt numite optime dacă sunt preferate altora dintr-un motiv sau altul. Scopul cercetării operaționale este o justificare cantitativă preliminară a soluțiilor optime.

Uneori (relativ rar) în urma studiului, este posibil să se indice o singură soluție strict optimă, mult mai des - să se identifice o zonă de soluții optime (rezonabile) practic echivalente în cadrul căreia se poate face alegerea finală.

Rețineți că însăși luarea deciziilor depășește sfera studiului operațiunii și intră în competența persoanei responsabile, de cele mai multe ori - un grup de persoane cărora li sa dat dreptul de a face alegerea finală și care sunt responsabile pentru această alegere. Atunci când fac o alegere, aceștia pot lua în considerare, alături de recomandările care decurg din calculul matematic, o serie de considerații (de natură cantitativă și calitativă) care nu au fost luate în considerare de acest calcul.

Prezența indispensabilă a unei persoane (ca autoritate finală de luare a deciziei) nu este anulată nici măcar în prezența unui sistem de control complet automatizat, care, se pare, ia o decizie fără participarea umană. Nu trebuie să uităm că însăși crearea unui algoritm de control, alegerea uneia dintre posibilele sale opțiuni, este, de asemenea, o decizie, și una foarte responsabilă. Odată cu dezvoltarea automatelor de control, funcțiile umane nu sunt anulate, ci pur și simplu mutate de la un nivel, elementar, la altul, superior. În plus, o serie de sisteme de control automatizate asigură intervenția umană activă în timpul procesului controlat.

Acei parametri, a căror totalitate formează o soluție, se numesc elemente ale soluției. Ca elemente ale soluției pot apărea diverse numere, vectori, funcții, semne fizice etc.. De exemplu, dacă se întocmește un plan pentru transportul mărfurilor omogene din punctele de plecare A 1, A 2, ..., A m spre destinații ÎN 1,В 2 , ..., В n , atunci elementele soluției vor fi numerele x ij , arătând câtă marfă va fi trimisă de la primul punct de plecare A i V j-a destinație În j . Set de numere X 11 , X 12, …, X 1 n , …, X m 1 , X m2, …, xmn formează o soluție.

În cele mai simple probleme de cercetare operațională, numărul elementelor de soluție poate fi relativ mic. Dar în majoritatea problemelor de importanță practică, numărul de elemente de soluție este foarte mare, pe care cititorul le poate verifica încercând să selecteze și să „numească după nume” elementele de soluție din exemplele 1 - 8 din paragraful anterior. Pentru simplitate, vom desemna întregul set de elemente ale soluției printr-o literă Xși spune „decizie X".

Pe lângă elementele de soluție de care, într-o oarecare măsură, le putem dispune, în orice sarcină de cercetare operațională sunt date și condiții „disciplinare” care sunt fixate de la bun început și nu pot fi încălcate (de exemplu, capacitatea de încărcare a mașinii; dimensiunea sarcinii planificate;

caracteristicile de greutate ale echipamentelor etc.). În special, astfel de condiții includ mijloacele (materiale, tehnice, umane) de care avem dreptul să dispunem și alte restricții impuse soluției. În totalitatea lor, ele formează așa-numitul „set de soluții posibile”.

Să notăm din nou acest set cu o literă X, ci faptul că soluţia X aparține acestui set, îl vom scrie sub formă de formulă: X X(a se citi: element X incluse in set X).

Este vorba de faptul că în multitudinea de soluții posibile X evidențiați soluțiile respective X(uneori - una, și mai des - o gamă întreagă de soluții), care dintr-un punct de vedere sau altul sunt mai eficiente (mai reușite, mai de preferat) decât altele. 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ță (este adesea numit „funcția obiectivă”). Acest indicator este ales astfel încât să reflecte orientarea țintă a operației. „Cea mai bună” soluție va fi considerată cea care contribuie la atingerea scopului în măsura maximă. Pentru a selecta măsura de performanță „spune după nume”. W,În primul rând, trebuie să te întrebi: ceea ce vrem La ce ne străduim prin efectuarea operațiunii? Atunci când alegem o soluție, vom prefera în mod firesc una care inversează indicatorul de eficiență W maxim (sau minim). De exemplu, aș dori să maximizez venitul dintr-o operațiune; dacă costurile sunt un indicator al eficienței, este de dorit să le minimizeze. Dacă este de dorit să maximizăm indicatorul de eficiență, îl vom scrie în formular W => max, iar dacă este minimizat - W => min.

Foarte des, operațiunea este însoțită de acțiunea unor factori aleatori („capricii” vremii, fluctuații ale cererii și ofertei, defecțiuni ale dispozitivelor tehnice etc.). În astfel de cazuri, de obicei, nu valoarea în sine, pe care am dori să o maximizăm (minimizam), ci valoarea sa medie (așteptările matematice) este luată ca indicator al eficienței.

În unele cazuri, se întâmplă ca operația, însoțită de factori aleatori, să urmărească un scop foarte specific. A, care poate fi realizat doar complet sau deloc atins (schema „da-nu”) și nu ne interesează niciun rezultat intermediar. Apoi, ca indicator al eficienței, se alege probabilitatea atingerii acestui scop. R(A). De exemplu, dacă un obiect este tras cu o condiție indispensabilă pentru a-l distruge, atunci indicatorul de eficiență va fi probabilitatea de a distruge obiectul.

Alegerea greșită a indicatorului de performanță este foarte periculoasă. Operațiunile organizate din punctul de vedere al unui criteriu ales fără succes pot duce la costuri și pierderi nejustificate (amintim, de exemplu, notoriul „val” ca principal criteriu de evaluare a activității economice a întreprinderilor).

Pentru a ilustra principiile alegerii unui indicator de eficiență, să revenim din nou la exemplele 1 - 8 din § 1, alegem pentru fiecare dintre ele un indicator natural de eficiență și indicăm dacă este necesar să îl maximizăm sau să îl minimizăm. Atunci când examinăm exemplele, trebuie să rețineți că nu toate au posibilitatea de a alege un indicator de eficiență dictat fără ambiguitate de descrierea verbală a sarcinii, astfel încât să existe diferențe între cititor și autor pe această problemă.

1. Plan de aprovizionare a întreprinderilor. Sarcina operațiunii este de a asigura aprovizionarea cu materii prime cu costuri minime de transport. Indicator de performanta R- costul total al transportului materiilor prime pe unitatea de timp, de exemplu, o lună ( R => min).

2. Construirea unui tronson de autostrada. Este necesară planificarea construcției în așa fel încât să fie finalizată cât mai curând posibil. Un indicator natural al eficienței ar fi timpul de finalizare a construcției, dacă nu ar fi asociat cu factori aleatori (defecțiuni ale echipamentelor, întârzieri în efectuarea lucrărilor individuale). Prin urmare, ca indicator al eficienței, puteți alege timpul mediu așteptat T finalizarea constructiei (T => min).

3. Vânzarea mărfurilor de sezon. Ca indicator al eficienței, putem lua profitul mediu așteptat P din vânzarea mărfurilor pentru sezon (P => max).

4. Protecția drumurilor împotriva zăpezii. Acesta este cel mai avantajos plan de protecție împotriva zăpezii din punct de vedere economic, prin urmare, ca indicator al eficienței, puteți alege costurile medii pe unitatea de timp (de exemplu, pe an) R pentru întreținerea și exploatarea drumurilor, inclusiv costurile asociate atât cu construcția de dispozitive de protecție, cât și cu eliberarea drumului și întârzierile în trafic (R => min).

5. Raid antisubmarin. Din moment ce raidul are un scop foarte specific A - distrugerea bărcii, apoi ca indicator al eficienței, ar trebui să alegeți probabilitatea R(A) că barca va fi distrusă.

6. Controlul selectiv al produselor. Măsura naturală a performanței sugerată de enunțul problemei este costul mediu așteptat. R pentru control pe unitatea de timp, cu condiția ca sistemul de control să ofere un anumit nivel de calitate, de exemplu, procentul mediu de refuzuri nu este mai mare decât cel specificat ( R=> min).

7. Examen medical. Ca indicator al eficienței, puteți alege procentul mediu (cota) Q pacienţii şi purtătorii infecţiei care au fost identificaţi (Q=> Verifica).

8. Serviciul bibliotecă. O oarecare vagitate a fost admisă în mod deliberat în formularea problemei:

nu este clar ce se înțelege prin „cel mai bun serviciu pentru clienți” sau „întâmpinarea nevoilor acestora în cea mai mare măsură posibilă”. Dacă calitatea serviciului este judecată după timpul în care abonatul care a solicitat cartea așteaptă să fie primită, atunci timpul mediu poate fi luat ca indicator al eficienței. T așteptările cititorului care a solicitat cărții la carte ( T=> min). Puteți aborda problema dintr-o perspectivă ușor diferită, alegând numărul mediu ca indicator al eficienței. M cărți emise pe unitatea de timp (M => max).

Exemplele luate în considerare sunt special alese pentru a fi atât de simple încât alegerea unui indicator de eficiență este relativ ușoară și este direct dictată de formularea verbală a sarcinii, orientarea (aproape întotdeauna) fără ambiguitate a țintei. Cu toate acestea, în practică, acest lucru nu este întotdeauna cazul. Cititorul se poate convinge de acest lucru încercând, de exemplu, să aleagă un indicator al eficienței transportului urban. Ce ar trebui luat ca un astfel de indicator? Viteza medie de circulație a pasagerilor în oraș? Sau numărul mediu de pasageri transportați? Sau numărul mediu de kilometri pe care va trebui să-i parcurgă o persoană, pe care transportul nu-i poate livra la locul potrivit? Este ceva de gândit aici!

Din păcate, în majoritatea problemelor de importanță practică, alegerea unui indicator de eficiență nu este simplă și se rezolvă ambiguu. Pentru orice sarcină complexă, o situație este tipică când eficacitatea unei operațiuni nu poate fi caracterizată în mod exhaustiv printr-un singur număr - trebuie să implice pe alții pentru a o ajuta. Ne vom familiariza cu astfel de probleme „multicriteriale” în § 6.

Exemple de rezolvare a problemelor de programare dinamică

În această secțiune, vom lua în considerare (și chiar vom rezolva până la sfârșit) câteva exemple simple (extrem de simplificate) de probleme de programare dinamică

1. Aşezarea celui mai avantajos traseu între două puncte. Să ne amintim problema 4 din paragraful precedent și să o rezolvăm până la capăt în condiții extrem de (și intenționat) simplificate. Trebuie să construim o cale de legătură

două puncte AȘi ÎN, dintre care al doilea se află la nord-est de primul. Pentru simplitate, să spunem. că așezarea potecii constă dintr-o serie de trepte, iar la fiecare treaptă ne putem deplasa fie spre est, fie spre nord; orice cale de la A V ÎN este o linie întreruptă în trepte, ale cărei segmente sunt paralele cu una dintre axele de coordonate (Fig. 13.1). Costurile de construcție ale fiecăruia dintre aceste segmente sunt cunoscute. Este necesar să se tragă o astfel de cale de la A V ÎN, unde costul total este minim.

Cum să o facă? Puteți face una din două moduri: fie parcurgeți toate opțiunile de cale posibile și alegeți cea pe care costurile sunt minime (și cu un număr mare de segmente acest lucru este foarte, foarte dificil!); sau despărțiți procesul de tranziție din A V ÎNîn pași individuali (un pas - un segment) și optimizați controlul pe pași. Se pare că a doua metodă este incomparabil mai convenabilă! Aici, ca și în alte părți în cercetarea operațională, există avantaje căutării intenționate și organizate pentru o soluție față de enumerarea naivă „oarbă”.

Să demonstrăm cum se face acest lucru cu un exemplu specific. Împărțiți distanța de la A inainte de ÎNîn direcția est, să zicem, în 7 părți, iar în direcția nord - în 5 părți (în principiu, fragmentarea poate fi arbitrar mică). Apoi orice cale de la A V ÎN cuprinde T\u003d 7 + 5 \u003d= 12 segmente îndreptate spre est sau nord (Fig. 13.2). Să punem pe fiecare dintre segmente un număr care exprimă (în unele unități arbitrare) costul trasării unei căi de-a lungul acestui segment. Este necesar să alegeți o astfel de cale din A V ÎN, pentru care suma numerelor de pe segmente este minimă.

Vom considera calea construită ca un sistem controlat S, deplasându-se sub influenţa controlului din starea iniţială A la finală ÎN. Starea acestui sistem înainte de începerea fiecărei etape va fi caracterizată de două coordonate: est (X) si nordica (y), ambele sunt întregi (0 X 5 7, 0 la 5). Pentru fiecare dintre stările sistemului (punctul nodal al grilei dreptunghiulare din Fig. 13.2), trebuie să găsim controlul optim condiționat: mergem din acest punct spre nord (controlul „c”) sau spre est (controlul „c”). c"). Acest control este ales astfel încât costul tuturor pașilor rămași (inclusiv acesta) să fie minim. Vom continua să numim acest cost „câștig optim condiționat” (deși în acest caz nu este un „câștig”, ci o „pierdere”) pentru o anumită stare a sistemului. Sînainte de a începe pasul următor.

Vom desfășura procedura de optimizare condiționată în direcția opusă - de la sfârșit până la început. În primul rând, efectuăm optimizarea condiționată a ultimului pas, al 12-lea. Luați în considerare separat colțul din dreapta sus al grilei noastre dreptunghiulare (Fig. 13.3). Unde putem fi după al 11-lea pas? Numai

unde într-un (ultim) pas poți ajunge ÎN, adică într-unul din puncte ÎN 1 sau LA 2 . Dacă suntem la punct ÎN 1 , nu avem de ales (control forțat): trebuie să mergem spre est și ne va costa 10 unități. Să scriem acest număr 10 într-un cerc în apropierea punctului ÎN 1 , iar controlul optim va fi indicat printr-o săgeată scurtă care emană din ÎN 1şi îndreptată spre est. Pentru punct LA 2 controlul este de asemenea forțat (nord), debitul până la capăt este 14, îl vom scrie în cerc în punctul LA 2 . Astfel, se face optimizarea condiționată a ultimului pas și câștigul optim condiționat pentru fiecare dintre puncte B1, B2 găsit și înregistrat în cana corespunzătoare.

Acum să optimizăm penultimul (al 11-lea) pas. După penultima (al 10-lea) pas, am putea ajunge la unul dintre puncte C1, C2, C3(Fig. 13.4). Să găsim pentru fiecare dintre ele un control optim condiționat și un profit optim condiționat. Pentru punct De la 1 management forțat: mergi spre est;

ne va costa 21 de unități până la final (11 la acest pas, plus 10, scrise în cerc la ÎN 1). Numărul 21 este scris într-un cerc la un punct De la 1 . Pentru punct De la 2 managementul nu mai este forțat: putem merge și spre est și spre nord. În primul caz, vom cheltui 14 unități la acest pas și din LA 2 până la sfârșit - încă 14, doar 28 de unități. Dacă mergem spre nord, vom cheltui 13 + 10, pentru un total de 23 de unități. Prin urmare, controlul optim condiționat la punct De la 2 - mergeți spre nord (marcați acest lucru cu o săgeată și scrieți numărul 23 într-un cerc lângă C 2), Pentru punct De la 3 controlul este din nou forțat (“c”), va costa 22 de unități până la sfârșit (puneți săgeata spre nord, scrieți numărul 22 într-un cerc când De la 3).

În mod similar, „în retragere” de la penultimul pas înapoi, găsim pentru fiecare punct cu coordonate întregi controlul optim condiționat („c” sau „b”), pe care îl notăm cu o săgeată, și câștigul optim condiționat (cheltuieli pentru capătul drumului), pe care îl scriem în cerc. Se calculează astfel: debitul la un pas dat se adaugă debitului deja optimizat, scris în cercul unde duce săgeata. Astfel, la fiecare pas, optimizăm doar acest pas, iar cei care îl urmează sunt deja optimizați. Rezultatul final al procedurii de optimizare este prezentat în Fig. 13.5.

Astfel, optimizarea condiționată a fost deja realizată: indiferent unde ne aflăm, știm deja unde să mergem (săgeată) și cât ne va costa să ajungem la final (număr în cerc). Într-un cerc la un punct A rambursarea optimă pentru întreaga construcție a căii de la A V ÎN:

W* = 118.

Acum rămâne să construim un control optim necondiționat - o traiectorie care duce de la AȘi ÎNîn cel mai ieftin mod. Pentru a face acest lucru, trebuie doar să „ascultați de trăgători”, adică să citiți ce prescriu aceștia să facă la fiecare pas. O astfel de traiectorie optimă este marcată în Fig. 13,5 s-au încercuit de două ori. Controlul optim necondiționat corespunzător va fi:

x* =(s, s, s, s, în, în, s, în, în, în, în, în),

adică trebuie să facem primii patru pași spre nord, următorii doi către est, apoi din nou unul spre nord și restul cinci către est. Problema rezolvata.

Rețineți că în cursul optimizării condiționate, putem întâlni cazul în care ambele controale pentru un anumit punct al planului sunt optime, adică duc la același cost al fondurilor din acest punct până la sfârșit. De exemplu, în punctul cu coordonatele (5; 1) ambele controale „c” și „b” sunt optime și dau fluxul până la capăt egal cu 62. Alegem în mod arbitrar oricare dintre ele (în cazul nostru, am ales „c”; am putea la fel de bine să alegem „c”). Astfel de cazuri de alegere ambiguă a controlului optim sunt întâlnite constant în programarea dinamică; în viitor, nu le vom marca în mod special, ci pur și simplu alegem arbitrar oricare dintre opțiunile echivalente. Desigur, controlul optim al întregului proces poate depinde de acest arbitrar, dar nu și de câștigul optim. În general, în problemele de programare dinamică (precum și în problemele de programare liniară), soluția este departe de a fi întotdeauna unică.

Și acum să revenim la început și să încercăm să rezolvăm problema într-un mod „naiv”, alegând la fiecare pas, începând de la primul, direcția cea mai profitabilă (pentru acest pas) (dacă sunt două, alegem orice). În acest fel obținem controlul

x = (s, s, în, în, în, în, s, în, în, în, s, s).

Să calculăm costurile pentru această traiectorie. Vor fi egali W=10 +12 +8+10 +11 +13 +15+8 + +10+9+8+14=128, ceea ce este cu siguranță mai mult decât W* = 118. În acest caz diferența nu este foarte mare, dar în altele poate fi semnificativă.

În problema rezolvată mai sus, condițiile au fost simplificate în mod deliberat până la extrem. Desigur, nimeni nu va conduce calea ferată „pe trepte”, deplasându-se doar spre nord sau spre est. Am făcut o astfel de simplificare pentru a alege doar dintre două controale în fiecare punct: „de la” sau „la”. În loc de două direcții posibile, ar fi posibil să se introducă mai multe dintre ele și, în plus, să se facă pași mai mici; acest lucru nu are o importanță fundamentală, dar, desigur, complică și prelungește calculele.

Rețineți că sarcini similare celor considerate mai sus sunt întâlnite foarte des în practică: de exemplu, atunci când alegeți calea cea mai rapidă între două puncte sau cel mai economic (din punct de vedere al consumului de combustibil) câștigul de viteză și altitudine de către o aeronavă.

Să facem o remarcă trecătoare. Cititorul atent a observat probabil că în problema noastră punctele AȘi ÎN(începutul și sfârșitul) nu sunt în principiu diferite unul de celălalt: ar fi posibil să se construiască controale optime condiționate nu de la sfârșit la început, ci de la început până la sfârșit și necondiționat - în direcția opusă. Într-adevăr, așa este: în orice problemă de programare dinamică, „începutul” și „sfârșitul” pot fi schimbate. Aceasta este complet echivalentă cu metoda descrisă anterior în ceea ce privește calculul, dar este oarecum mai puțin convenabil când se explică verbal ideea metodei: este mai ușor de argumentat, referindu-se la condițiile „deja stabilite” de la începutul acestei pas decât celor care încă „vin” după acest pas. În esență, ambele abordări sunt complet echivalente.

2. Problema alocării resurselor. Metoda de programare dinamică face posibilă rezolvarea cu succes a multor probleme economice (vezi, de exemplu, ). Luați în considerare una dintre cele mai simple astfel de probleme. Avem ceva stoc de fonduri (resurse) la dispoziție LA, care ar trebui distribuite între Tîntreprinderile P 1 , P 2 , ..., P m . Fiecare dintre întreprinderi i atunci când investesc în el X generează venituri pe baza X, adică reprezentând o anumită funcție ( X). Toate funcțiile ( X) (i = 1, 2, ..., T) sunt date (desigur, aceste funcții sunt nedescrescătoare). Întrebarea este cum să alocați fondurile LA. intre intreprinderi, astfel incat in total sa dea venitul maxim?

Această problemă se rezolvă cu ușurință prin metoda programării dinamice.Deși în formularea ei nu conține o mențiune a timpului, totuși se poate desfășura mental operația de distribuire a fondurilor într-o anumită secvență, considerând investiția fondurilor în întreprinderea P 1 ca fiind primul pas, iar în P 2 etc.

Sistem gestionat Sîn acest caz, fondurile sau resursele care sunt distribuite. Starea sistemului Sînainte ca fiecare pas să fie caracterizat de un număr S- rezerva de numerar neinvestită încă. În această problemă, „controalele pasului” sunt mijloacele x 1, x 2, ..., x 3, alocate afacerilor. Este necesar să găsiți controlul optim, adică un astfel de set de numere x 1, x 2, ..., xm, la care venitul total este maxim:

(13.1)

Vom rezolva această problemă mai întâi într-o formă generală, formulă și apoi - pentru date numerice specifice. Găsiți pentru toată lumea i- pasul este recompensa optimă condiționată (de la acest pas până la sfârșit), dacă am abordat acest pas cu o marjă de fonduri S. Indicați recompensa optimă condiționată W i (S), iar controlul optim condiționat corespunzător este fondurile în care sunt investite i afacere, - x i (S).

Să începem optimizarea de la ultima, T - Etapa. Să ajungem la acest pas cu restul fondurilor S. Ce ar trebui sa facem? Evident, investește toată suma Sîn întregime întreprinderii P m. Prin urmare, controlul optim condiționat pe m-al-lea pas: acordați ultimei întreprinderi toate fondurile disponibile S, adică

și recompensa optimă condiționată

Wm (S)= (S).

Având în vedere o întreagă gamă de valori S(plasându-le suficient de aproape), noi pentru fiecare valoare S noi vom sti x m (S)Și Wm (S). Ultimul pas este optimizat.

Să trecem la penultimul (T- 1) pasul. Să ne apropiem de el cu o rezervă de fonduri S. Denota L m -1 (S) recompensa optimă condiționată în ultimii doi pași: ( m- 1)-m și m-m (care este deja optimizat). Dacă alocam la ( m- 1) pasul ( m- 1)a-a întreprindere înseamnă X, atunci ultimul pas va fi S x. Recompensa noastră pentru ultimii doi pași va fi egală cu

,

și trebuie să-l găsești X, la care acest câștig este maxim:

Semnul înseamnă că valoarea maximă este preluată de toate X, ceea ce este posibil (a investi mai mult decât S, nu putem) din expresia în acolade. Acest maxim este recompensa optimă condiționată pentru ultimii doi pași și apoi valoarea X, la care se atinge acest maxim este controlul optim conditionat pe (T- 1) pasul.

şi controlul optim condiţional corespunzător x i (S) - acea valoare X, la care se atinge acest maxim.

Continuând în acest fel, ajungem în sfârșit la prima întreprindere P 1 . Aici nu trebuie să schimbăm valorile S; stim sigur ca stocul inainte de primul pas este egal cu LA:

Deci, se găsește câștigul (venitul) maxim din toate întreprinderile. Acum rămâne doar „să citești recomandările”. Acest sens X, la care se atinge maximul (13.4), iar la prima treaptă există un control optim. După ce investim aceste fonduri în prima întreprindere, vom avea LA- .„Citind” recomandarea pentru această valoare S, alocam suma optima de fonduri celei de-a doua intreprinderi:

,

si tot asa pana la final.

Acum să rezolvăm un exemplu numeric. Stocul inițial de fonduri K = 10 (unități convenționale) și este necesar să-l distribuie optim între cinci întreprinderi (t = 5). Pentru simplitate, vom presupune că sunt investite doar sume întregi de fonduri. funcții de venit ( X) sunt date în Tabelul 13.1.

Tabelul 13.1

X
	0,5 1,0 1,4 2,0 2,5 2,8 3,0 3,0	0,1 0,5 1,2 1,8 2,5 2,9 3,5 3,5	0,6 1,1 1,2 1,4 1,6 1,7 1,8 1,8	0,3 0,6 1,3 1,4 1,5 1,5 1,5 1,5	1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3

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

Să efectuăm optimizarea condiționată așa cum este descris mai sus, începând de la ultimul pas. De fiecare dată când ajungem la pasul următor, având o rezervă de fonduri S,încercăm să alocăm una sau alta sumă de fonduri pentru acest pas, luăm câștigul la acest pas conform tabelului 13.1, îl adăugăm la câștigul deja optimizat la toți pașii următori până la final (având în vedere că avem deja mai puține fonduri, doar printr-o asemenea sumă de fonduri, pe care le-am alocat) și găsim investiția la care această sumă atinge maximul. Această investiție este controlul optim condiționat la acest pas, iar maximul în sine este câștigul optim condiționat.

Tabelul 13.2 prezintă rezultatele optimizării condiționate pentru toți pașii. Tabelul este structurat astfel: prima coloană prezintă valorile stocului de fonduri S, cu cu care abordam acest pas. În plus, tabelul este împărțit în cinci perechi de coloane, corespunzătoare numărului pasului. Prima coloană a fiecărei perechi conține valoarea

Tabelul 13.2

S	i=5	i=4	i=3	i=2	i=1
x5(S)	W 5(S)	x4(S)	W4(S)	x 3(S)	W 3(S)	x2(S)	W2(S)	x 1(S)	W 1(S)
		1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3 1,3 1,3		1,0 1,3 1,6 2,3 2,5 2,6 2,7 2,8 2,8 2,8		1,0 1,6 2,1 2,4 2,9 3,4 3,6 3,7 3,9 4,1		1,0 1,6 2,1 2,4 2,9 3,5 4,1 4,6 5,1 5,6		5,6

control optim condiționat, în al doilea - profit optim condiționat. Tabelul este umplut de la stânga la dreapta, de sus în jos. Decizia la al cincilea - ultimul - pas este forțată: toate fondurile sunt alocate;

La toți ceilalți pași, soluția trebuie optimizată. Ca urmare a optimizării secvențiale a pasilor 5, 4, 3, 2 și 1, vom obține o listă completă a tuturor recomandărilor pentru un control optim și un câștig optim necondiționat W* pentru întreaga operațiune - în acest caz, este egal cu 5,6. În ultimele două coloane din Tabelul 13.2, este completată doar o singură linie, deoarece știm exact starea sistemului înainte de începerea primului pas:

S0 = K = 10. Controalele optime la toate etapele sunt încadrate. Astfel, am ajuns la concluzia finală: trebuie să alocăm două unități din zece primei întreprinderi, cinci unități celei de-a doua, două celei de-a treia, niciuna celei de-a patra, o unitate celei de-a cincea. Cu această distribuție, venitul va fi maxim și egal cu 5,6.

Pentru a clarifica cititorului cum este completat tabelul 13.2, vom demonstra acest lucru pe un eșantion de calcul. De exemplu, trebuie să optimizăm soluția x 3(7)- ce să facem în a treia etapă, dacă am abordat-o cu o rezervă de fonduri S= 7, și care este maximul pe care îl putem câștiga cu toate cele rămase

Tabelul 13.3

X	7 - X		W4(7 - X)	+W 4 (7 - X)
		1,8 1,7 1,6 1,4 1,2 1,1 0,6	1,0 1,3 1,6 2,3 2,5 2,6 2,7	1,8 2,7 2,9 3,0 3,5 3,2 2,7

pași, inclusiv al treilea? Să presupunem că toți pașii de după al treilea (al 4-lea și al 5-lea) au fost deja optimizați, adică primele două perechi de coloane din Tabelul 13.2 au fost completate. Sa gasim X 3 (7) și W 3(7). Pentru a face acest lucru, vom compila o placă auxiliară (vezi tabelul 13.3). Prima coloană listează toate atașamentele posibile. X pe treapta a treia, nedepasind S = 7.În a doua coloană - ce va rămâne după o astfel de investiție din stocul de fonduri S = 7.În a treia coloană - câștigul din a treia etapă din investiție Xîn a treia întreprindere se completează după coloană (tabelul 13.1). În a patra coloană - plata optimă pentru toți pașii rămași (al patrulea și al cincilea), cu condiția să ne apropiem de al patrulea pas cu fondurile rămase (completate în coloana i = 4 tabele 13.2). În a cincea coloană - suma a două plăți: pas și optimizat în continuare pentru o anumită investiție Xîn a treia etapă.

Dintre toate plățile din ultima coloană, este selectată cea maximă (în tabelul 13.3 este egal cu W 3(7) = 3,6 și controlul corespunzător X(7) = 2).

Se pune întrebarea: ce se întâmplă dacă în tabelul auxiliar de tip 13.3 maximul este atins pentru mai mult de un X, și la două sau mai multe? Răspundem: nu contează pe care să o alegem; castigul nu depinde de el. În general, în problemele de programare dinamică, soluția nu ar trebui să fie deloc unică (am menționat deja acest lucru).

3. Problema încărcării mașinii. Folosind metoda de programare dinamică, puteți rezolva cu succes o serie de probleme de optimizare descrise în Capitolul 3, în special unele probleme de programare cu numere întregi. Rețineți că integralitatea soluțiilor, care face problemele de programare liniară atât de dificilă, în acest caz nu complică, ci, dimpotrivă, simplifică procedura (cum a fost simplificată pentru noi prin integralitatea înglobărilor în problema anterioară).

Ca exemplu, luați în considerare problema încărcării unei mașini (am menționat-o deja în capitolul anterior): există un anumit set de obiecte P 1 , P 2 ,..., P n (fiecare într-o singură copie); greutățile lor sunt cunoscute q 1 , q 2 , ..., q n si cost de la 1, cu 2 , ..., cu n . Capacitatea de încărcare a mașinii este Q.Întrebarea este care dintre articole ar trebui să fie luate în mașină, astfel încât costul lor total (cu greutatea totală Q) a fost maximul?

Ar trebui să înveți conceptele și definițiile de bază ale cercetării operaționale.

O operațiune este 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. Orice alegere definită de parametri se numește soluție. Soluțiile optime sunt considerate a fi cele care, dintr-un motiv sau altul, sunt preferabile altora. Prin urmare, sarcina principală a cercetării operaționale este o justificare cantitativă preliminară a soluțiilor optime.

Observație 1

Trebuie acordată atenție formulării problemei: luarea deciziei în sine depășește sfera cercetării operaționale și ține de competența persoanei responsabile sau a grupului de persoane, care poate lua în considerare și alte considerente decât cele justificate matematic.

Observația 2

Dacă în unele sarcini de cercetare operațională soluția optimă este cea în care criteriul de eficiență ales capătă valoarea maximă sau minimă, atunci în alte sarcini acest lucru nu este deloc necesar. Deci, în problemă, putem considera optim, de exemplu, un astfel de număr de puncte de vânzare și personal în ele, în care timpul mediu de serviciu pentru clienți nu depășește, de exemplu, 5 minute, iar lungimea medie a cozii în orice moment va să nu fie mai mult de 3 persoane (1, pag. .10-11).

Eficiența activităților de producție și comerciale este în mare măsură determinată de calitatea deciziilor luate zilnic de managerii de diferite niveluri. În acest sens, sunt de mare importanță sarcinile de îmbunătățire a proceselor de luare a deciziilor, pe care cercetarea operațională le permite să le rezolve. Termenul „cercetare operațională” a fost folosit pentru prima dată în 1939-1940. în zona militară. În acest moment, echipamentele militare și gestionarea acestuia deveniseră fundamental mai complicate ca urmare a revoluției științifice și tehnologice. Și, prin urmare, până la începutul celui de-al Doilea Război Mondial, a existat o nevoie urgentă de a efectua cercetări științifice în domeniul utilizării eficiente a noilor echipamente militare, a evaluării cantitative și a optimizării deciziilor luate de comandament. În perioada postbelică, succesele noii discipline științifice au fost solicitate în domenii pașnice: în industrie, activități antreprenoriale și comerciale, în instituțiile guvernamentale și în instituțiile de învățământ.

Cercetarea operațională este o metodologie de aplicare a metodelor matematice cantitative pentru a justifica soluțiile la probleme în toate domeniile activității umane intenționate. Metodele și modelele de cercetare operațională vă permit să obțineți soluții care îndeplinesc cel mai bine obiectivele organizației.

Cercetarea operațională este o știință preocupată de dezvoltarea și aplicarea practică a metodelor pentru cel mai eficient (sau optim) management al sistemelor organizaționale.

Principalul postulat al cercetării operaționale este următorul: soluția optimă (controlul) este un astfel de set de valori ale variabilelor care realizează valoarea optimă (maximum sau minim) a criteriului de eficiență (funcția obiectivă) a operației și respectă restricții specificate.

Obiectul cercetării operaționale este problema luării deciziilor optime într-un sistem cu control bazat pe evaluarea eficienței funcționării acestuia. Conceptele caracteristice cercetării operaționale sunt: ​​model, variabile variabile, constrângeri, funcție obiectiv.

Subiectul cercetării operaționale în realitate îl reprezintă sistemele de management organizațional (organizații), care constau dintr-un număr mare de departamente care interacționează, iar interesele departamentelor nu sunt întotdeauna concordante între ele și pot fi opuse.

Scopul cercetării operaționale este de a fundamenta cantitativ deciziile luate cu privire la managementul organizațiilor.

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

Ca exemplu de sarcină tipică a managementului organizațional, în care interesele conflictuale ale departamentelor se ciocnesc, luați în considerare problema gestionării inventarului unei întreprinderi.

Departamentul de producție se străduiește să producă cât mai multe produse la cel mai mic cost. Prin urmare, el este interesat de o producție cât mai lungă și continuă, adică de producția de produse în loturi mari, deoarece o astfel de producție reduce costul de reconfigurare a echipamentelor și, prin urmare, costurile totale de producție. Totuși, producția de produse în cantități mari necesită crearea unor volume mari de stocuri de materiale, componente etc.

Departamentul de vânzări este, de asemenea, interesat de stocuri mari de produse finite pentru a satisface orice cerere a clienților la un moment dat. Încheind fiecare contract, departamentul de vânzări, străduindu-se să vândă cât mai multe produse, trebuie să ofere consumatorului cea mai largă gamă de produse. Ca urmare, există adesea un conflict între departamentul de producție și departamentul de vânzări cu privire la gama de produse. Totodată, departamentul de vânzări insistă asupra includerii în plan a multor produse produse în cantități mici, chiar și atunci când acestea nu aduc profituri mari, iar departamentul de producție cere excluderea unor astfel de produse din gama de produse.

Departamentul financiar, căutând să minimizeze cantitatea de capital necesară pentru funcționarea întreprinderii, încearcă să reducă cantitatea de capital de lucru „aferent”. Prin urmare, este interesat să reducă stocurile la minimum. După cum puteți vedea, cerințele pentru dimensiunea stocurilor pentru diferite departamente ale organizației sunt diferite. Se pune întrebarea care strategie de inventar va fi cea mai benefică pentru întreaga organizație. Aceasta este o sarcină tipică a managementului organizațional. Este legat de problema optimizării funcționării sistemului în ansamblu și afectează interesele conflictuale ale diviziilor sale.

Caracteristici cheie ale cercetării operaționale:

1. O abordare sistematică a analizei problemei puse. Abordarea sistemelor, sau analiza sistemelor, este principalul principiu metodologic al cercetării operaționale, care este după cum urmează. Orice sarcină, oricât de privată ar părea la prima vedere, este considerată din punctul de vedere al influenței sale asupra criteriului de funcționare a întregului sistem. Mai sus, abordarea sistematică a fost ilustrată prin exemplul problemei managementului stocurilor.

2. Este tipic pentru cercetarea operațională ca atunci când rezolvăm fiecare problemă, apar tot mai multe sarcini noi. Prin urmare, dacă la început sunt stabilite obiective înguste, limitate, aplicarea metodelor operaționale nu este eficientă. Cel mai mare efect poate fi atins doar cu cercetarea continuă, asigurând continuitate în trecerea de la o sarcină la alta.

3. Una dintre caracteristicile esențiale ale cercetării operaționale este dorința de a găsi soluția optimă a problemei. Cu toate acestea, o astfel de soluție se dovedește adesea a fi de neatins din cauza limitărilor impuse de resursele disponibile (bani, timp de calculator) sau de nivelul științei moderne. De exemplu, pentru multe probleme combinatorii, în special, probleme de planificare cu numărul de mașini n > 4, soluția optimă cu dezvoltarea modernă a matematicii poate fi găsită doar printr-o simplă enumerare de opțiuni. Apoi trebuie să se limiteze la căutarea unei soluții „suficient de bună” sau suboptimă. Prin urmare, unul dintre creatorii săi, T. Saaty, a definit cercetarea operațională drept „... arta de a da răspunsuri proaste acelor întrebări practice cărora li se oferă răspunsuri și mai proaste prin alte metode”.

4. O caracteristică a cercetării operaționale este că se desfășoară într-o manieră complexă, în multe domenii. Se creează un grup operațional pentru realizarea unui astfel de studiu. Este format din specialiști din diferite domenii de cunoaștere: ingineri, matematicieni, economiști, sociologi, psihologi. Sarcina creării unor astfel de grupuri operaționale este un studiu cuprinzător al întregului set de factori care influențează soluția problemei și utilizarea ideilor și metodelor diferitelor științe.

Fiecare cercetare operațională parcurge următoarele etape principale în succesiune:

1) descrierea sarcinii de planificare,

2) construirea unui model matematic,

3) găsirea unei soluții,

4) verificarea si corectarea modelului,

5) implementarea în practică a soluției găsite.

Descrierea sarcinii de planificare:

Sarcini de planificare și management al rețelei

luați în considerare relația dintre termenele de finalizare a unui complex mare de operațiuni (lucrări) și momentele începerii tuturor operațiunilor complexului. Aceste sarcini constau în găsirea duratei minime a unui set de operațiuni, a raportului optim de cost și a calendarului de implementare a acestora.

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

Sarcinile de gestionare a stocurilor sunt de a găsi valorile optime ale nivelurilor de inventar (puncte de comandă) și dimensiunile comenzilor. Particularitatea unor astfel de sarcini este că, odată cu creșterea nivelului stocurilor, pe de o parte, costurile depozitării acestora cresc, dar, pe de altă parte, pierderile datorate unei posibile lipsuri a produsului stocat scad.

Problemele de alocare a resurselor apar cu un anumit set de operațiuni (lucrări) care trebuie efectuate cu resursele disponibile limitate și se impune găsirea repartizării optime a resurselor între operații sau componența operațiunilor.

Sarcinile de reparare și înlocuire a echipamentelor sunt relevante din cauza uzurii echipamentelor și a necesității înlocuirii acestuia în timp. Sarcinile se reduc la stabilirea momentului optim, a numărului de reparații și verificări preventive, precum și a momentelor de înlocuire a echipamentelor cu altele modernizate.

Sarcinile de programare (programare) sunt de a determina secvența optimă a operațiunilor (de exemplu, prelucrarea pieselor) pe diverse tipuri de echipamente.

Sarcinile de planificare și plasare sunt de a determina numărul și locația noilor obiecte, ținând cont de interacțiunea acestora cu obiectele existente și între ele.

Problemele de selecție a rutelor, sau problemele de rețea, se întâlnesc cel mai des în studiul diverselor probleme din transport și în sistemul de comunicații și constau în determinarea celor mai economice rute (1, p. 15).

Sub Operațiune este înțeles ca orice eveniment unit printr-o singură idee și direcție pentru a atinge un scop specific.

O operațiune este întotdeauna un eveniment gestionat, de exemplu. depinde de noi să alegem parametrii care caracterizează modul în care este organizat.

Orice alegere definită a parametrilor în funcție de noi va fi apelată decizie.

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

Scopul principal al cercetării operaționale este justificarea cantitativă prealabilă a soluţiilor optime. Cercetarea operațională nu își propune să automatizeze complet luarea deciziilor. Decizia este întotdeauna luată de persoană. Scopul cercetării operaționale este de a produce date cantitative și recomandări care să faciliteze luarea deciziilor unei persoane.

Alături de sarcina principală - fundamentarea solutiilor optime - Sfera cercetării operaționale include și alte sarcini:

Evaluarea comparativă a diferitelor opțiuni de organizare a operațiunii,

Evaluarea impactului asupra funcționării diferiților parametri,

Investigarea „gâturilor de sticlă”, i.e. elemente, a căror întrerupere are un efect deosebit de puternic asupra succesului operațiunii etc.

Aceste sarcini auxiliare sunt de o importanță deosebită atunci când o anumită operațiune este considerată nu izolat, ci ca un element integral al întregului. sisteme operațiuni. O abordare „sistemică” a sarcinilor cercetării operaționale necesită luarea în considerare a dependenței reciproce și a condiționalității unei game întregi de activități, de exemplu. ia decizia finală ținând cont de rolul și locul acestei operațiuni în sistem.

Sub eficienţă operațiunea este înțeleasă ca gradul de adaptare a acesteia la îndeplinirea sarcinii care i se confruntă.

Pentru a aprecia eficacitatea unei operațiuni și pentru a compara eficacitatea operațiunilor organizate diferit, trebuie să aveți niște cifre numerice. criteriul de evaluare sau indicator de performanta.

Secvența acțiunilor în cercetarea operațională.

1. Se formulează scopul studiului și se elaborează enunțul problemei.

2. Pentru a aplica metode cantitative în orice domeniu, este întotdeauna necesară construirea unui model matematic al fenomenului. Pe baza analizei proprietăților originalului, se construiește acest model.

3. După construirea modelului, se obțin rezultate pe acesta

4. Sunt interpretate în termenii originalului și transferate în original.

5. Cu ajutorul comparației, rezultatele simulării sunt comparate cu rezultatele obținute dintr-un studiu direct al originalului.

Dacă rezultatele obținute folosind modelul sunt apropiate de rezultatele obținute în studiul originalului, atunci în ceea ce privește aceste proprietăți, modelul poate fi considerat adecvat originalului.

La proiectarea și operarea sistemelor de control automatizate apar adesea sarcini legate de analiza modelelor atât cantitative, cât și calitative de funcționare a acestora, determinarea structurii lor optime etc.

Experimentarea directă pe obiecte pentru a rezolva aceste probleme are o serie de dezavantaje semnificative:

1. Este încălcat modul de funcționare stabilit al obiectului.

2. Într-un experiment la scară completă, este imposibil să se analizeze toate opțiunile alternative pentru construirea unui sistem etc.

Este indicat să rezolvați aceste probleme pe un model separat de obiect și implementat pe un computer.

La modelarea sistemelor informatice, modelele matematice sunt utilizate pe scară largă.

Metoda modelării matematice este o metodă de studiere a diferitelor obiecte prin alcătuirea unei descrieri matematice adecvate și calcularea, pe baza acesteia, a caracteristicilor obiectului studiat.

Este necesar să se construiască un model matematic. Reflectă în mod oficial funcționarea originalului și descrie principalele modele ale comportamentului său. În acest caz, toți factorii secundari, nesemnificativi, sunt excluși din luare în considerare.

Obiectul modelării matematice sunt sistemele complexe. Un sistem complex este un anumit mod organizat și funcțional set de un număr mare de elemente legate de informații și care interacționează sub influența factorilor externi.

Există 4 etape principale ale sistemelor de modelare pe un computer:

Construirea unui model conceptual al sistemului și formalizarea acestuia;

Algoritmizarea modelului de sistem și dezvoltarea unui program de modelare;

Obținerea și interpretarea rezultatelor preliminare de simulare;

Verificarea adecvării modelului și sistemului; ajustarea modelului

Calculul principal al indicatorilor de calitate a funcționării sistemului pe baza rezultatelor modelării, implementării modelului.

Curs 3. Concepte de bază ale metodei evaluărilor experților. Formarea grupurilor de experți. proceduri de votare. Metode de ierarhizare, comparații perechi, evaluare la scară relativă.

1. Concepte de bază ale IO

ȘI DESPRE – disciplină științifică, angajată în dezvoltarea și aplicarea practică a metodelor pentru managementul cât mai eficient al diverselor sisteme organizaționale.

IO include următoarele secțiuni:

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

2) teoria stării de aşteptare bazată pe teoria proceselor aleatorii;

3) teoria jocurilor, care face posibilă fundamentarea deciziilor luate în condiții de incompletitudine a informațiilor.

La rezolvarea unei probleme specifice de control, utilizarea metodelor IO implică:

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

Studierea interrelațiilor care determină luarea ulterioară a deciziilor și stabilirea criteriilor de performanță care să permită evaluarea avantajului unuia sau altui 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 unii dintre parametrii 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 dată de parametri este apelată 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 aparatul matematic (diferite tipuri de funcții, ecuații, sisteme de ecuații și inegalități etc.). Întocmirea unui model de operare necesită înțelegerea esenței fenomenului descris și cunoașterea aparatului matematic.

Eficiența operațiunii – gradul de adaptabilitate a acestuia la îndeplinirea sarcinii se exprimă cantitativ sub forma unui criteriu de eficienţă – funcţia obiectivă. Alegerea criteriului de eficiență determină valoarea practică a studiului. (Un criteriu ales incorect poate fi dăunător, deoarece operațiunile organizate sub 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 termenele de finalizare a unui complex mare de operațiuni (lucrări) și momentele începerii tuturor operațiunilor complexului. Aceste sarcini constau în găsirea duratei minime a unui complex de operațiuni, a raportului optim de cost și a calendarului de implementare a acestora.

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

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

Sarcini de alocare a resurselor iau naștere cu un anumit set de operațiuni (lucrări) care trebuie efectuate cu resurse disponibile limitate și se impune găsirea repartizării optime a resurselor între operații sau componența operațiunilor.

Sarcini de reparare și înlocuire a echipamentelor relevante din cauza uzurii echipamentelor și a necesității înlocuirii acestuia în timp. Sarcinile se reduc la stabilirea momentului optim, a numărului de reparații și verificări preventive, precum și a momentelor de înlocuire a echipamentelor cu altele 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 nia constau in determinarea numarului si amplasarii optime a unor obiecte noi, tinand cont de interactiunea acestora cu obiectele existente si intre ele.

Sarcini de selectare a rutei, sau reţea sarcini intalnite cel mai des in studiul diverselor sarcini in transport si in sistemul de comunicatii si constau in determinarea celor mai economice rute.

2. Sarcina generală a unui program liniar. Soluție optimă

Model economic și matematic

LP este o zonă 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 constrângerilor liniare, adică egalități sau inegalități care leagă aceste variabile.

Metodele LP sunt aplicate problemelor practice în care: 1) este necesară alegerea celei mai bune soluții (planul optim) dintr-un set de posibile; 2) soluția poate fi exprimată ca un set de valori ale unor variabile de mărime; a) restricţiile impuse soluţiilor fezabile de condiţiile specifice problemei sunt formulate sub formă de ecuaţii liniare sau inegalităţi; 4) scopul este exprimat ca o funcție liniară a principalelor variabile. Valorile funcției obiective, permițându-vă să comparați diferite soluții, servesc drept criteriu pentru calitatea soluției.

Pentru o rezolvare practică a unei probleme economice prin metode matematice, în primul rând, aceasta trebuie scrisă folosind un model economico-matematic. Model economico-matematic - o descriere matematică a procesului sau obiectului economic investigat. Acest model exprimă tiparele procesului economic într-o formă abstractă folosind relații matematice.

Schema generală de formare a modelului: I

1) alegerea unui anumit număr de variabile, a căror atribuire - 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 ale problemelor;

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 constrângerilor impuse variabilelor.

Problemă generală a programării liniare se pare ca:

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 astfel de 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 obiectiv.

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

cu restrictii:

Soluție optimă (sau plan optim) Problema LP este o soluție X=(x1,x2,…,xj,…,xn), a sistemului de constrângeri (1), care satisface condiția (3), în care funcția liniară (2) ia optimul (maxim sau valoare 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 problemei canonice este problema în formă de bază, care diferă prin faptul că toți coeficienții vectorului de constrângere b sunt nenegative, iar în fiecare ecuație există o variabilă cu coeficientul 1, care nu este inclusă în niciuna dintre celelalte ecuații. O variabilă cu această proprietate se numește variabilă 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ă

Sistemul de m ecuații liniare cu n variabile are forma

sau în stenografie

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. există cel puțin un grup de variabile de bază, atunci acest sistem este nedefinit ș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 setul infinit de soluții ale sistemului se disting așa-numitele soluții de bază.

Soluție de bază un sistem de m ecuații liniare cu n variabile se numește soluție în care toate n–m variabile nebaze sunt egale cu zero.

În problemele de programare liniară, soluțiile de bază admisibile sau, așa cum se mai numesc și planurile de sprijin, 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 generală definitorie 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 acestui poligon. Această proprietate poate fi luată ca definiție a unui set convex de puncte.

Setul 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 evidenția punctele interioare, de limită și de colț.

Punctul mulțimii se numește intern, dacă o parte din vecinătatea sa conține puncte numai din acest set.

Punctul mulțimii se numește graniță, dacă oricare dintre vecinătățile sale conține atât puncte care aparțin 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 pentru niciun segment care aparține în întregime mulțimii date.

Pe fig. 2.4 prezintă exemple de diferite puncte ale poligonului: interior (punctul M), limită (punctul N) și colț (punctele A, B, C, D, E). Punctul A este unghiular, deoarece pentru orice segment care aparține în întregime poligonului, 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 acest lucru nu este necesar pentru o mulțime neconvexă. 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ă centrată în orice punct al mulțimii care conține complet mulțimea dată; în caz contrar, mulţimea se numeşte nemărginită.

Un set convex închis de puncte dintr-un plan care are 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 inegalităților, ecuațiilor și sistemelor 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 limita sa - linia construită. Dacă inegalitatea este satisfăcută la un punct de control, atunci este satisfăcută și în toate punctele semiplanului care conține punctul de control și nu este satisfăcută în toate punctele celuilalt semiplan. Și invers, dacă inegalitatea nu este satisfăcută la punctul 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. Ca punct de control, este convenabil să luăm originea coordonatelor O (0; 0), care nu se află pe linia construită.

Luați în considerare setul de soluții ale sistemelor de inegalități.

Afirmația 2. Mulțimea soluțiilor unui sistem compatibil m 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, definește 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, adică. 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ții pentru sistemele de inegalități pot apărea și alte cazuri: mulțimea soluțiilor este o regiune 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

rezolvarea optimă a problemei LP

Teorema 1. Dacă problema LP are o soluție optimă, atunci funcția liniară ia o valoare 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 acelor puncte.

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

Următoarea teoremă este dedicată metodei analitice pentru găsirea 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ă.

Din teoremele 1 și 2 rezultă imediat un corolar important: 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 un număr finit de soluții de bază admisibile.

Deci, setul de soluții admisibile (poliedrul de soluție) al problemei LP este un poliedru convex (sau regiune 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 o problemă în formă standard cu două variabile (P = 2).

Fie reprezentarea geometrică a sistemului de constrângeri un poligon ABCDE(Fig. 4.1). Este necesar să se găsească între punctele acestui poligon un astfel de punct în care funcția liniară F=c1x1+c2x2 ia valoarea maximă (sau minimă).

Luați î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ție, găsiți punctul prin care trece linia de nivel a funcției F cu nivelul cel mai mare (dacă funcția liniară este maximizată) sau cel mai mic (dacă este minimizată).

Ecuația dreptei de nivel a funcției c1x1+c2x2=a este ecuația unei drepte. La diferite niveluri A liniile de nivel sunt paralele, deoarece pantele lor sunt determinate doar de raportul dintre coeficienții c1 și c2 și, prin urmare, sunt egale. Deci liniile de nivel de caracteristică 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ă, cu o deplasare paralelă a liniei într-o direcție, nivelul crește doar, iar cu o deplasare în cealaltă direcție, acesta doar scade. Vectorul c=(c1,c2) ​​​​începând de la 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).

Ordinea rezolvării grafice a problemei LP:

1. Construiți un poligon soluție.

2. Construiți un vector c = (c1, c2) și trasați o linie a nivelului unei funcții liniare pentru acesta F, de exemplu, F=0.

3. Deplasarea paralelă a dreptei F=0 în direcția vectorului c(-c) pentru a găsi punctul Amax(Bmin), unde 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 de decizie, iar punctul maxim este punctul de „ieșire” din poligon.

6. Ideea 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 principalele teoreme 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 alegerea dintre ele pe cea asupra căreia funcția scop ia decizia optimă. Din punct de vedere geometric, aceasta corespunde enumerarii tuturor punctelor de colț ale poliedrului soluție. O astfel de enumerare va duce în cele din urmă la o soluție optimă (dacă există), dar implementarea ei 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ă admisibile care trebuie enumerate poate fi redus dacă enumerarea nu se realizează aleatoriu, ci ținând cont de modificările funcției liniare, i.e. căutând să se asigure că fiecare soluție următoare este „mai bună” (sau cel puțin „nu mai rea”) decât cea anterioară în ceea ce privește valorile funcției liniare (creșterea acesteia la găsirea maximului, scăderea acesteia la găsirea minimului) . O astfel de enumerare permite reducerea numărului de pași în găsirea optimului. Să explicăm acest lucru cu un exemplu grafic.

Fie ca aria soluțiilor fezabile să fie reprezentată printr-un poligon ABCDE. Să presupunem că punctul său de colț A corespunde soluției de bază admisibile inițiale. O enumerare aleatorie ar trebui să încerce cinci soluții de bază fezabile corespunzătoare celor cinci puncte de colț ale poligonului. Cu toate acestea, desenul arată că după vârf A avantajos să mergi la următorul vârf ÎN, iar apoi la punctul optim CU.În loc de cinci, au fost parcurse doar trei vârfuri, îmbunătățind constant funcția liniară.

Ideea îmbunătățirii secvențiale a soluției a stat la baza unei metode universale pentru rezolvarea problemelor de programare liniară - metoda simplex sau metoda de perfectionare succesiva 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 atinge valoarea optimă a funcției obiectiv (dacă problema are un optim finit).

Metoda simplex a fost propusă pentru prima dată de omul de știință american J. Danzig în 1949, dar încă din 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 pe calculator, dar exemplele simple folosind metoda simplex pot fi rezolvate și manual.

Pentru a implementa metoda simplex - îmbunătățirea succesivă a soluției - este necesar să se stăpânească trei elemente principale:

o metodă pentru a determina o soluție de bază fezabilă inițială a problemei;

regula de tranziție la cea mai bună (mai precis, nu cea 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 referință inițial (soluție de bază fezabilă inițială), de asemenea folosind metoda bazei artificiale, găsirea planului de referință optim, rezolvarea problemelor folosind tabele simplex.

7 . Algoritmul metodei simplex.

Să luăm în considerare soluția LLP prin metoda simplex și să o prezentăm în raport cu problema de maximizare.

1. În funcție de starea problemei, modelul ei matematic este compilat.

2. Modelul construit este convertit la forma canonică. În acest caz, poate ieși în evidență 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 restrictive și o funcție obiectiv sunt introduse sub formă de expresii rezolvate față de baza inițială. Linia în care se introduc coeficienții funcției obiectiv F se numește linie F sau linia funcției obiectiv.

4. Planul de referință inițial se găsește prin realizarea de transformări simplex cu elemente de rezoluție pozitivă corespunzătoare rapoartelor simplex minime, și neținând cont de semnele elementelor rândului F. Dacă în cursul transformărilor există un rând 0, ale cărui elemente, cu excepția termenului liber, sunt zerouri, atunci sistemul de ecuații restrictive ale problemei este inconsecvent. Dacă, pe de altă parte, există 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.

Se va apela la reducerea sistemului (2.55), (2.56) la o nouă bază transformare simplex . Dacă o transformare 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ă și celălalt invers – de la independent la dependent. Această operație este cunoscută în algebră ca Etapa de eliminare a Iordaniei.

5. Planul de bază 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 planul optim este unic; 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 cel puțin un element pozitiv în coloana sa, atunci putem trece la un nou plan de referință care este mai aproape de cel optim. Pentru a face acest lucru, coloana specificată trebuie să fie atribuită ca rezoluție, prin raportul simplex minim, găsiți rândul de rezolvare și efectuați o transformare simplex. Planul de bază obținut este reexaminat pentru optimitate. Procesul descris se repetă până când se obține un plan optim sau până când problema este de nerezolvat.

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

Puțin mai dificil este să determinați variabila care trebuie exclusă din bază. Pentru a face acest lucru, ei alcătuiesc rapoartele dintre membrii liberi și elementele pozitive ale coloanei de rezoluție (astfel de relații se numesc simplex) și îl găsesc pe cel mai mic dintre ei, care determină rândul (rezolvarea) care conține variabila exclusă. Alegerea unei variabile care trebuie exclusă din bază (sau alegerea unui șir de rezoluție) în funcție de raportul simplex minim garantează, așa cum s-a stabilit deja, pozitivitatea componentelor de bază în noul design de referință.

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

1) uitați-vă la linia corespunzătoare unui membru liber negativ, de exemplu, un rând t, și selectați orice element negativ din ea, iar coloana corespunzătoare acestuia este considerată ca fiind permisă (presupunem că constrângerile problemei sunt compatibile );

2) alcătuiesc raporturile dintre elementele coloanei de membri liberi la elementele corespunzătoare ale coloanei de rezoluție care au aceleași semne (raporturi simplex);

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

4) la intersecția coloanelor și rândurilor de rezoluție se găsește un element de rezoluție. Dacă elementul șirului y s-a dovedit a fi rezolvat, atunci după transformarea simplex membrul liber al acestui șir va deveni pozitiv. În caz contrar, la pasul următor, rândul t este din nou adresat. Dacă problema este rezolvabilă, atunci după un anumit număr de pași nu vor exista elemente negative în coloana de termeni liberi.

8. Metoda matricei inverse

Luați în considerare un LP de forma:

A este matricea constrângerilor;

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 minorul ordinului 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 permutarea coloanelor matricei A, se poate aduce întotdeauna 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ă împărțirea vectorului x în – vectorul variabilelor de bază și.

Orice soluție a problemei (1) satisface condiția A*x=b și, în consecință, sistemul ia următoarea formă:

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

- decizie comună.

O soluție de bază (în raport cu 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. numit bază realizabilă. 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 coeficienții Cb în fața variabilelor de bază, Cn-restul.

Astfel, primim. 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ă.

Doc-in: Lasa. Luați î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).

Apoi ne uităm

Astfel, soluția de bază este min. Să nu țin, 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ă.

Fie că corespunde unei variabile libere Xi:Xj, atribuim o valoare și introducem-o în bază, derivăm o altă variabilă și numim-o liberă.

Cum să determine? Toate variabilele libere, cu excepția lui, sunt încă 0.

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

Scoatem: - o conditie necesara.

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ă.

Calculam:

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

dacă, atunci găsim componenta, atașăm-o, astfel vom găsi o altă soluție; – la care una dintre variabilele de bază =0. Renunțăm la această variabilă din bază, introduceți 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 graniței mulțimii X, mulțimea soluțiilor problemei. 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, problema duală a utilizării resurselor

Sarcină. Pentru fabricarea a două tipuri de produse P1 și P2 se folosesc patru tipuri de resurse S1, S2, S3, S4. Având în vedere stocurile de resurse, numărul de unități de resurse cheltuite pentru fabricarea 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 de produse î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 astfel de plan de producție X=(x1,x2,…,Xn), în care profitul (venitul) din vânzarea produselor să fie maxim, cu condiția ca consumul de resurse pentru fiecare tip de produs să nu depășească cel disponibil. stocuri

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 costul total al resurselor va fi minim, cu condiția ca costul 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ă stocul de resursă Si; aij- numărul de unități de resurse Si consumate în producția unei unități de producție Pj(j=1,2,…,n); cj- profit (venit) din vânzarea unei unități de producție Pj (sau prețul producției Pj) .

Să presupunem că o organizație a decis să achiziționeze resursele întreprinderii S1,S2,…,Sm și este necesar să se stabilească prețuri optime pentru aceste resurse y1,y2,…,ym. Este evident că organizația de achiziții este interesată de faptul că costurile tuturor resurselor 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ă de faptul că veniturile primite nu sunt mai mici decât suma pe care o poate primi întreprinderea atunci când prelucrează resursele în produse finite.

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 cheltuite pentru producerea unei unități de produs P1 la prețul y1,y1,…,yi ,…,ym, respectiv. Prin urmare, pentru a satisface cerințele vânzătorului, costul resurselor consumate la fabricarea unei unități de producție P1 trebuie să fie cel puțin prețul acesteia c1, adică. a11y1+a21y2+…+am1ym>=c1.

În mod similar, este posibil să se compună constrângeri 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ă condiţional , preturi "false". Spre deosebire de prețurile „externe” c1,c2,…,cn pentru produse, care sunt cunoscute, de regulă, înainte de începerea producției, prețurile resurselor y1,y2,…,ym sunt intern , deoarece nu sunt setate din exterior, ci sunt determinate direct ca urmare a rezolvarii problemei, de aceea sunt adesea numite 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 de la interpretarea semnificativă a parametrilor incluși în modelele lor economice și matematice.

Ambele sarcini au următoarele proprietati:

1. Într-o problemă, ei caută maximul unei funcții liniare, în cealaltă - un minim.

2. Coeficienții pentru variabilele dintr-o funcție liniară a unei probleme sunt membri liberi ai sistemului de constrângeri dintr-o altă problemă.

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

4. Matricele de coeficienți pentru variabile în 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 este același cu numărul de variabile dintr-o altă problemă.

6. Condiţiile de nenegativitate a variabilelor se păstrează în ambele probleme.

Cometariu. Dacă condiția 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 problemei duale sunt în mod similar legate.

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

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

11. Algoritm pentru compilarea unei probleme duale:

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

2. Compilați o matrice augmentată a sistemului A, care include o matrice de coeficienți pentru variabile, o coloană de membri 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 iar condiţiile de nenegativitate a variabilelor: alcătuiesc funcţia obiectivă a problemei duale, luând ca coeficienţi ai variabilelor membrii liberi ai sistemului de constrângeri ai problemei iniţiale; alcătuiește un sistem de constrângeri pentru problema duală, luând elementele matricei ca coeficienți ai variabilelor, iar coeficienții variabilelor din funcția obiectivă a problemei inițiale ca membri 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*) sunt soluții admisibile ale problemelor reciproc duale pentru care este valabilă egalitatea,

atunci este soluția optimă a problemei inițiale I și este soluția optimă a problemei duale II.

Pe lângă un criteriu suficient pentru optimitatea problemelor reciproc duale, între soluțiile lor există și alte relații importante. În primul rând, apar întrebări: există întotdeauna o soluție optimă simultană pentru fiecare pereche de probleme duale; este posibil ca una dintre problemele duale să aibă o soluție și cealaltă nu. La aceste întrebări se răspunde prin următoarea teoremă.

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

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 opusă 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 nu este mărginită.

Sensul economic al primei teoreme a dualității.

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

Semnificația economică a primei teoreme a dualității poate fi interpretată și astfel: întreprinderii nu îi pasă dacă să producă produse conform planului optim X*=(x1*,x2*,…,xn*) și să obțină profitul maxim ( venituri) Fmax sau vinde resurse la prețuri optime Y* =(y1*,y2*,…,ym*) si ramburseaza din vanzare egal cu aceasta 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ă prin metoda simplex, atunci este necesar să le reducă la o formă canonică, pentru care este necesar să se introducă în sistemul de constrângeri a problemei I (pe scurt notație) T variabile nenegative, dar î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 constrângeri 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 (diferite 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 la atingerea optimului (adică, la ultimul pas de rezolvare a fiecărei probleme prin metoda simplex) reprezintă o corespondență între 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ă admisibile.

A doua teoremă a dualității. Componentele soluției optime a problemei duale sunt egale cu valorile absolute ale coeficienților la variabilele corespunzătoare ale funcției liniare a problemei inițiale, exprimate în termenii variabilelor minore 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 a problemei duale se numesc estimări optime (duale) ale problemei inițiale. Le-a numit academicianul L.V. Kantorovich conditionat obiectiv estimări (în literatură se mai numesc și venit ascuns) .

Variabile suplimentare ale problemei inițiale I, reprezentând diferența dintre stocurile bi de resurse 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 cost în exces față de preț.

Astfel, estimări ale resurselor determinate obiectiv determină gradul de deficit al resurselor: conform planului optim de producție, resursele limitate (adică, utilizate pe deplin) primesc estimări non-zero, iar nerare - estimări zero. Valoarea y*i este estimarea celei de-a i-a resurse. 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 tipurile de produse rentabile, neprofitabile pot intra în planul optim de producție (deși criteriul de rentabilitate aici este deosebit: prețul unui produs nu depășește costurile resurselor consumate la fabricarea sa, ci este exact egal lor).

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ânzarea produselor atunci când stocul resursei corespunzătoare se va modifica cu o unitate.

Estimările duale pot servi ca instrument de analiză și luare a deciziilor corecte într-o industrie în continuă schimbare. Deci, de exemplu, cu ajutorul estimărilor de resurse determinate obiectiv, este posibil să se compare costurile condiționate optime și rezultatele producției.

Estimările determinate obiectiv ale resurselor fac posibilă aprecierea efectului nu al oricăror, ci doar al modificărilor relativ mici ale resurselor. Cu schimbări bruște, estimările în sine pot deveni diferite, ceea ce va duce la imposibilitatea utilizării lor pentru analiza eficienței producției. În funcție de rapoartele estimărilor determinate obiectiv, se pot determina normele calculate de substituire a resurselor, în baza cărora înlocuirile în curs în cadrul stabilității estimărilor duale nu afectează eficiența planului optim. Concluzie. Scorurile duble 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 de comparare a costurilor contingente totale și a rezultatelor.

15. Declarația sarcinii de transport după criteriul costului.

TK - sarcina celui mai economic plan pentru transportul unui produs omogen sau interschimbabil de la un punct de producție (stații de plecare) la punctele de consum (stații de destinație) - este cea mai importantă sarcină privată a LP, care are aplicații practice extinse nu doar la probleme de transport.

TK se distinge în LP prin certitudinea caracteristicilor economice, caracteristicile modelului matematic, prezența unor metode specifice de soluție.

Cea mai simplă formulare a TOR din punct de vedere al costului este următoarea: în T punctele de plecare A1,…,Am sunt respectiv a1,…,am unități de marfă (resurse) omogene care urmează să fie 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 nevoile să fie pe deplin satisfăcute și încât costurile totale de transport sunt minime.

Pentru claritate, condițiile TK vor fi prezentate sub forma unui tabel, care se numește distributie .

Furnizor	Consumator			Stoc de marfă
Nevoie

Aici, cantitatea de marfă transportată de la i-lea punct de origine până 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 cererea destinației j-a în marfă 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 trafic.

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, asupra consumatorilor și condițiile de nenegativitate:

– restricții asupra stocurilor (2);

– restricții asupra consumatorilor (2);

sunt condițiile de non-negativitate (3).

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

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

16. Semn al solubilității problemei transportului

Pentru ca problema transportului să aibă planuri admisibile este necesar și suficient ca egalitatea

Există două tipuri de sarcini 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 de transport. Pentru a face acest lucru, în matricea sarcinilor este prevăzută o coloană suplimentară, pentru care nevoia 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. În acest fel, modelul deschis al problemei se transformă într-unul închis. Pentru o nouă problemă, funcția obiectiv este întotdeauna aceeași, deoarece costul transportului suplimentar este zero. Cu alte cuvinte, consumatorul fictiv nu încalcă consistența sistemului de constrângeri.

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

Tarifele pentru livrarea mărfurilor de la acest furnizor fictiv sunt din nou presupuse a fi egale cu 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 compatibil, adică va deveni posibil să se găsească planul optim.

Următoarea teoremă este de mare importanță pentru problema transportului.

Teorema. Rangul matricei problemei de transport este cu unul mai mic decat numarul de ecuatii, i.e. 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. 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 celula (I,j) liberă. Ținând cont de teorema privind rangul unei matrice în tabelul de distribuție planul general ar trebui să includă m+n-1 celule ocupate iar restul va fi gratuit.

Aceste cerințe pentru planul de bază nu sunt singurele. Planurile de bază trebuie să îndeplinească o altă cerință legată de cicluri.

Un set de celule matrice de trafic în care două și doar două celule învecinate 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, ciclul 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 decât atât, la fiecare vârf al ciclului există exact două legături, dintre care una este într-un rând, iar cealaltă într-o coloană. Dacă polilinia care formează ciclul se intersectează, atunci punctele de auto-intersecție nu sunt vârfuri.

Următoarele proprietăți importante ale planurilor de sarcini de transport sunt asociate cu setul de celule de ciclu:

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

2) dacă avem un plan de bază, atunci pentru fiecare celulă liberă este posibil să se formeze un singur ciclu care să conțină această celulă și o parte din celulele ocupate.

17. Construirea liniei de bază inițiale

Regula colțului de nord-vest.

Pentru a întocmi un plan inițial de transport, este convenabil să folosiți regula colțului de nord-vest, care este după cum urmează.

Vom completa, începând 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ă. 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 ale primei coloane, cantitatea de marfă pentru .

Dacă, atunci prima linie este în mod similar „închisă”, adică pentru . Continuăm la completarea 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ă din al doilea rând sau din 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 m-lea rând.

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 optim, deoarece costurile cij nu sunt luate în considerare la determinarea acestuia. Prin urmare, în calculele ulterioare, vor fi necesare 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 încărcăturii în celulă se realizează cu tariful minim cij. Începem să completăm tabelul din celulă, 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 furnizorului, ale cărui stocuri sunt complet epuizate, sau coloana corespunzătoare consumatorului, a cărui cerere este complet satisfăcută, este exclus din considerare. Se poate dovedi că un rând și o coloană ar trebui excluse în același timp dacă stocul furnizorului este complet epuizat și cererea consumatorului este complet satisfăcută. Apoi, din celulele rămase ale tabelului, celula cu cel mai mic tarif este din nou selectată ș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 al determinării planului optim al sarcinii de transport prin metoda potențială este similar cu principiul rezolvării problemei LP prin metoda simplex și anume: mai întâi se găsește planul de bază al sarcinii de transport, iar apoi este succesiv. îmbunătățit până la obținerea unui plan optim.

Esența metodei potențiale este următoarea. După ce este 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țialul furnizorului Ai, iar fiecărui consumator (fiecărei coloană) i se atribuie un anumit număr numit potențialul consumatorului.

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 problema transportului prin metoda potențială, este necesar:

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

2. Calculați potențialele și, respectiv, furnizorii și consumatorii (pentru celule 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 este liberă și poate lua orice valoare numerică. De exemplu, . Potențialele rămase pentru o soluție de referință dată sunt determinate în mod unic.

3. Verificați optimitatea, de ex. pentru celulele libere calculați scorurile. Dacă, atunci transportul este oportun și planul X este optim - un semn al optimității. Dacă există cel puțin o diferență, atunci mergeț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 implementării unei singure aprovizionări de către al-lea furnizor către al-lea consumator. Dacă, atunci o singură livrare va duce la economii ale costurilor de transport, dacă - la o creștere a acestora. Prin urmare, 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 alege maximul, construit pentru o celulă liberă, căruia îi corespunde ciclul de recalculare. 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, trebuie să mutați încărcăturile din celulele asociate cu această celulă liberă prin ciclul 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 toate celelalte celule (vârfurile ciclului) sunt alternativ semne „–” și „+” . Vom numi aceste celule minus și plus.

b) În celulele minus ale ciclului, găsim oferta minimă, pe care o notăm cu. Cel mai mic dintre numerele xij din celulele negative este transferat în această celulă liberă. În același timp, acest număr se adaugă numerelor 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 referință; iar celula minus, în care a stat minimul numerelor xij, este considerată liberă și părăsește planul de referință.

Astfel, a fost stabilită o nouă linie de bază. Tranziția de la o linie de bază la alta descrisă mai sus se numește o schimbare în ciclul de recalculare. La deplasarea 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 minus, 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 paragraful 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 a fi rezolvată prin metoda DP.

De obicei, metodele DP optimizează funcționarea unor sisteme controlate, al căror efect este estimat aditiv, sau multiplicativ, funcție obiectivă. Aditiv este o funcție a mai multor variabile f(x1,x2,…,xn) a căror valoare se calculează ca suma unor funcții fj care depind de o singură 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ă constă în înlocuirea soluției 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 admisibile departamente;

2. sarcina trebuie să permită interpretarea ca un proces în mai multe etape, fiecare pas constând în adoptare 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ă pe fiecare dintre aceștia;

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

5. starea ulterioară în care se află sistemul după alegerea unei soluții pe k-a pas, depinde doar de soluția dată și de starea inițială până la început k- Etapa. Această proprietate este principala din punctul de vedere al ideologiei programării dinamice și se numește lipsa de consecinte .

Luați în considerare problemele aplicării modelului de programare dinamică într-o formă generalizată. Să existe o sarcină de a gestiona un 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ă mulțimea S a tuturor stărilor posibile. Setul este definit și 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 în momente discrete în timp, iar controlul soluţie constă în alegerea unuia dintre comenzi. plan sarcini sau strategie de management se numește vectorul x=(x1,x2,…,xn-1), ale cărui componente sunt controalele selectate la fiecare pas al procesului. Având în vedere cele așteptate lipsa efectelor secundareîntre fiecare două stări succesive ale obiectului Sk și Sk+1, există o dependență funcțională cunoscută, care include și controlul selectat: . Astfel, stabilirea stării inițiale a obiectului și alegerea unui plan X definiți în mod unic traiectoria comportamentului obiect.

Eficiența managementului la fiecare pas k depinde de starea curentă Sk, de controlul selectat xk și se cuantifică folosind funcțiile fk(xk,Sk), care sunt sume funcţie obiectivă aditivă , care caracterizează eficienţa globală a managementului facilităţii. ( 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 suma maxima valorile lui fk pe traiectoria corespunzătoare.

Principiul principal al programării dinamice este că la fiecare pas trebuie să ne străduim nu pentru o optimizare 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 se realizează 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.

Notăm cu Zk(s) valoarea maximă a sumei funcțiilor fk pe tot parcursul etapelor de la k inainte de P(obținut sub control optim pe un anumit segment 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 recursivă:

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 lui Bellman :

Strategia optimă de control trebuie să îndeplinească următoarea condiție: oricare ar fi starea initiala sk la pasul k și controlul ales la acest pas xk, controalele ulterioare (deciziile de management) ar trebui să fie optime în raport cu cocmo yanyu ,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 obiectelor de control pentru care alegerea controlului optim nu depinde de preistoria procesului controlat, adică de modul în care sistemul a ajuns la starea curentă. Această împrejurare face posibilă descompunerea problemei și soluționarea ei practică posibilă.

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 principală 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 și rezultatul conflictului învingătoare.

Pentru fiecare joc oficial, vă prezentăm 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; 3) răsplata la care conduce fiecare set de acțiuni. De obicei, câștigul (sau pierderea) poate fi cuantificat; de exemplu, puteți evalua o pierdere cu zero, o victorie cu unu și un egal cu 1/2. Cuantificarea rezultatelor unui joc se numește plată .

Jocul se numește baie de aburi , dacă sunt doi jucători implicați și multiplu , dacă numărul de jucători este mai mare de doi. Vom lua în considerare doar jocurile în pereche. Sunt jucați de 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 skoy , dacă câștigul unuia dintre jucători este egal cu pierderea celuilalt, i.e. suma profiturilor ambelor părți este zero. Pentru a finaliza sarcina jocului, este suficient să indicați valoarea unuia dintre ele . Dacă desemnăm A- câștigă unul dintre jucători, b – plata celuilalt, apoi pentru un joc cu sumă zero b= –A, deci este suficient să luăm în considerare, de exemplu A.

Se numește alegerea și implementarea uneia dintre acțiunile prevăzute de reguli mișcare jucător. Mișcările pot fi personal Și Aleatoriu . mișcare personală – 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 jocul să fie definit matematic, regulile jocului trebuie să specifice 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 pure de noroc) 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 cele ce urmează, 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 de care dispune fiecare jucător cu privire la acțiunile altuia. O clasă specială de jocuri sunt așa-numitele „jocuri cu informații complete”. Un joc cu informații complete Se numește un joc în care fiecare jucător la 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 sunt șahul, damele și binecunoscutul joc tic-tac-toe. Majoritatea jocurilor de importanță practică nu aparțin clasei de jocuri cu informații complete, întrucât necunoscutul despre acțiunile adversarului este de obicei un element esențial al situațiilor conflictuale.

Unul dintre conceptele de bază ale teoriei jocurilor este conceptul strategii .

strategie Un jucător este numit un set de reguli care determină alegerea acțiunii sale pentru fiecare mișcare personală, în funcție de situație. De obicei, în timpul jocului, la 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 anumită strategie, care poate fi dată sub forma unei liste de reguli sau a unui program. (Deci 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 decizie de joc , este necesar ca fiecare jucător să aleagă 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 aderă la strategia sa. Se numesc astfel de strategii optim . Strategiile optime trebuie să satisfacă și condiția durabilitate , acestea. ar trebui să fie neprofitabil pentru oricare dintre jucători să-și abandoneze strategia în acest joc.

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

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

Sfârșit jocul în care jucătorul A Are T strategiile și jucătorul B - 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 "adversarul").

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

Lasă fiecare parte să aleagă o anumită strategie; pentru noi va fi Ai, pentru adversarul Bj. Ca urmare a alegerii de către jucători a oricărei perechi de strategii Ai și Bj (), rezultatul jocului este determinat în mod unic, adică. win aij player A(pozitiv sau negativ) și pierderea (-aij) a jucătorului ÎN.

Să presupunem că valorile 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 sunt 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 unei strategii Ai jucătorul A ar trebui să se aștepte la jucător ÎN ii va raspunde cu una dintre strategiile Bj pentru care este recompensa pentru jucator A minim (jucător ÎN caută să „rănească” jucătorului A).

Indicați cu cea mai mică remunerație a jucătorului A când alege strategia Ai pentru toate strategiile posibile ale jucătorului ÎN(cel mai mic număr în i--lea rând al matricei de plăți), adică

Dintre toate numerele () alegeți cel mai mare: .

Hai sa sunăm prețul mai mic al jocului, sau câștig maxim (maxmin). Acesta este câștigul garantat al jucătorului 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ă profitul jucătorului A, alegand strategia Bj ia in calcul profitul maxim posibil pentru A. Denota

Dintre toate numerele, alege-l pe cel mai mic

si suna pret de top joc sau recompensa minimax(minimax). Egoul a garantat pierderea jucătorului B. Prin urmare,

Se numește strategia minimax strategia minimax.

Se numește principiul care dictează jucătorilor alegerea celor mai „prevăzute” strategii minimax și maximin principiul minimax . Acest principiu decurge din presupunerea rezonabilă că fiecare jucător caută să atingă obiectivul opus adversarului.

Teorema. Prețul inferior al jocului nu depășește niciodată 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 net al jocului, sau prețul jocului. Strategiile minimax corespunzătoare prețului jocului sunt strategii optime , si totalitatea lor soluție optimă sau decizie de joc. În acest caz jucătorul A primește maximul garantat (independent de comportamentul jucătorului) ÎN) victorie v, și jucătorul ÎN atinge minimul garantat (indiferent de comportamentul jucătorului A) pierzând v. Se spune că o soluție la joc durabilitate , acestea. dacă unul dintre jucători se ține de strategia sa optimă, atunci nu poate fi avantajos ca 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, acest lucru nu poate fi niciodată benefic; o astfel de abatere a jucătorului ÎN poate, în cel mai bun caz, să lase câștigul neschimbat. 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 fel benefic pentru A.

O pereche de strategii pure 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. O astfel de situație, dacă există, se numește power point. În geometrie, un punct de pe o suprafață care are proprietatea: minim simultan de-a lungul unei coordonate și maxim de-a lungul celeilalte, se numește putere punct, prin analogie acest termen este folosit în teoria jocurilor.

Jocul pentru care , numit joc power point. Elementul care are această proprietate este punctul de putere 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 atât prețul său mai mic, cât și cel mai mare.

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

În teoria jocurilor, se dovedește că, în special, fiecare joc cu informații complete are un punct de putere și, în consecință, fiecare astfel de joc are o soluție, adică există o pereche de strategii optime pentru o parte și cealaltă, dând un profit mediu egal cu prețul jocului. Dacă un joc cu informații complete constă doar din mișcări personale, atunci, atunci când fiecare parte își aplică propria strategie optimă, acesta trebuie să se încheie întotdeauna cu un rezultat destul de cert, și anume, o răsplată exact egală cu prețul jocului.

22. Rezolvarea jocului în strategii mixte.

Printre jocurile finite de importanță practică, jocurile cu un punct de forță sunt relativ rare; mai tipic este cazul când prețurile inferioare și superioare ale 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, pe baza unui adversar care acționează în mod rezonabil, această alegere ar trebui să fie determinată de principiul minimax. Aderând la strategia noastră maximin, pentru orice comportament al adversarului, cu siguranță ne garantăm un profit egal cu prețul mai mic al jocului α. strategii mixte

strategie mixtă Sa jucătorul A se numește 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 se aplică cu o frecvență (probabilitate) de 1.

Se dovedește că prin aplicarea nu numai strategii pure, ci și mixte, este posibil să se obțină o soluție pentru fiecare joc finit, adică o pereche de astfel de strategii (în general mixte), astfel încât atunci când ambii jucători le aplică, câștigul să fie egal. la prețul jocului, iar atunci când orice abatere unilaterală de la strategia optimă, câștigul se poate schimba doar într-o direcție nefavorabilă pentru deviant. Deci, pe baza principiului minimax, se determină soluție optimă (sau soluţie) jocuri: aceasta este 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 a lui. Se numește profitul corespunzător soluției optime cu prețul de a juca v . Prețul jocului satisface inegalitatea:

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

Această afirmație este 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, prezentăm 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ț.

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

corect teorema strategiei active: dacă unul dintre jucători aderă la 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 strategiile sale active.

Jucătorul poate folosi oricare dintre strategiile sale active în forma lor 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.

Considera 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 fără un punct de șa, conform teoremei fundamentale 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 aderă la strategia sa optimă , atunci câștigul său mediu va fi egal cu prețul jocului v, indiferent de strategia activă pe care o folosește jucătorul ÎN. Pentru un joc 2v2, strategia pură a oricărui adversar este activă dacă nu există niciun punct ssdl. Câștigă jucător A(pierderea jucătorului ÎN)- o variabilă aleatorie, a cărei așteptare matematică (valoarea medie) este prețul jocului. Prin urmare, câștigul mediu al unui jucător A(strategia optimă) va fi egală cu v atât pentru prima cât și pentru al doilea adversar.

Lăsați jocul să fie dat de matricea plăților.

Câștigul mediu al jucătorului 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 recompensă medie A, dacă al 2-lea jucător folosește strategia B2, adică. . Având în vedere asta, 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 strategiei active pentru a găsi – strategia optimă a jucătorului ÎN, obținem asta pentru orice strategie pură a jucătorului A (A1 sau A2) pierderea medie a jucătorilor ÎN egal cu prețul jocului v, adică

Atunci strategia optimă este determinată de formulele: .

Sarcina de a rezolva jocul, dacă matricea acestuia nu conține un punct de șa, este cu atât mai dificilă, cu atât valoarea este mai mare. 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. Este posibil să se reducă dimensiunea unei matrice prin excludere duplicat si evident dezavantajos strategii.

Duplicat se numesc strategii care corespund acelorași valori ale elementelor din matricea de plăți, adică matricea conține aceleași rânduri (coloane).

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ând mai puțin).

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

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

23. Interpretarea geometrică a jocului 2×2

Decizie de joc 2×2 permite o interpretare geometrică clară.

Fie jocul dat de matricea de profit P=(aij), i, j=1,2.

Pe abscisă (Fig.) Pune deoparte 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 din stânga este probabilitatea p2 a strategiei A2 .

Să desenăm două perpendiculare pe axa x prin punctele A1 și A2: axa I-I și axa II-II. Pe axa I-I vom amâna câștigurile în cadrul strategiei A1; pe axa II-II - plăți conform strategiei A2.

Dacă jucătorul A folosește strategia A1, atunci câștigul său în cadrul strategiei B1 a jucătorului B este a11, iar în cadrul strategiei B2 este 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 în cadrul strategiei B1 a jucătorului B este a21, iar în cadrul strategiei 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). Am două linii drepte. Linie dreaptă 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 aplică strategia B1. Jucător câștigător A corespunde unui punct de pe această linie. Beneficiul mediu corespunzător strategiei mixte este determinat de formula a11p1+a21p2 și este reprezentat de punctul M1 pe linia 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 linia dreaptă B2B2.

Trebuie să găsim o strategie optimă S*a, adică una pentru care beneficiul minim (pentru orice comportament ÎN) s-ar întoarce la maxim. Pentru a face acest lucru, vom construi limita inferioară a câștigului cu strategii B1B2 , adică linia întreruptă B1NB2 marcată în Fig. linie groasă. Acest limita inferioară va exprima profitul minim al jucătorului A pentru oricare dintre strategiile sale mixte; punctN , în care acest profit minim atinge un maxim, și determină soluția (strategia optimă) și prețul jocului. Ordonata punctuala N există un preț pentru a juca 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.

Din punct de vedere geometric, este posibil să se determine strategia optimă ca jucător A, precum și jucătorul ÎN;în ambele cazuri, se utilizează principiul minimax, dar în al doilea caz, nu se construiește limita inferioară, ci superioară a plății și nu se determină maximul, ci minimul.

Dacă matricea de plăți conține numere negative, atunci pentru o soluție grafică a problemei 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. Decizia 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ă

Jocul m×n, în general, nu are o interpretare geometrică vizuală. Soluția sa este destul de laborioasă 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 aplicare a strategiilor pure corespunzătoare Ai,Bj,

Strategia optimă satisface următoarea cerință. Oferă jucătorului A câștig mediu nu mai mic decât prețul jocului v, pentru orice strategie a jucătorului ÎNși o răsplată egală cu prețul jocului v, cu strategia optimă a jucătorului ÎN. Fără a pierde generalitatea, ne-am stabilit v> 0; acest lucru se poate realiza prin realizarea tuturor elementelor . Dacă jucătorul A aplică o strategie mixtă împotriva oricărui jucător Bj cu strategie pură ÎN, apoi primește recompensa medie , sau așteptarea matematică de a câștiga (adică elemente j-Go coloanele matricei de plăți 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 câștigurile 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ă profitul garantat, de ex. pretul jocului v.

Împărțind la egalitate, obținem că variabilele îndeplinesc condiția: . Maximizarea prețului jocului v este echivalent cu minimizarea cantității , deci problema poate fi formulată după cum urmează: definiți valori variabile , mapentru a satisface constrângerile liniare(*) Și în timp ce funcţia liniară (2*) transformat 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 profitul garantat, de ex. găsiți max. Variabilele satisfac inegalitățile

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

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

Variabilele satisfac condiția.

Jocul a fost redus la următoarea sarcină.

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

Rezolvarea 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ă strategiile optime în probleme specifice, ar trebui să alegeți una dintre problemele reciproc duale, a cărei rezolvare este mai puțin laborioasă, și să găsiți soluția celeilalte probleme folosind teoreme de dualitate.

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

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

cercetare operațională) - o zonă relativ nouă, a cărei o scurtă istorie datează de la începutul celui de-al Doilea Război Mondial. Exact acest covor. știința conține un set bine definit de principii generale, to-rye oferă cercetătorilor un plan de implementare a operațiunilor de cercetare științifică. Acesta include următoarele etape. 1. Formularea problemei. 2. Construcția unui covoraș. model reprezentând sistemul studiat. 3. Obținerea unei soluții din acest model. 4. Verificarea modelului si a solutiei obtinute din acesta. 5. Stabilirea controlului asupra deciziei. 6. Prakt. implementare solutie: implementare. Formularea problemei Trebuie acordată o atenție serioasă definirii naturii generale a problemei și, mai important, a obiectivelor cercetării. Aceste obiective ar trebui formulate în termeni comportamentali pentru a minimiza sau elimina ambiguitatea și incertitudinea. De asemenea, trebuie acordat timp pentru a prioritiza corect obiectivele realizabile în mod realist. O listă prea lungă de obiective poate cauza dificultăți potențiale în implementarea lor, mai ales dacă aceste obiective nu sunt legate clar într-o secvență logică. Construirea unui model matematic Faza a doua de cercetare cu t. sp. Și despre. sugerează o descriere a modelului. Scopul modelului este de a reprezenta lumea reală. În I. o. astfel de modele sunt simbolice, exprimate în mat. termeni. Ecuația clasică E \u003d mc2 este un exemplu tipic de covoraș. modele. Formele tradiționale pentru astfel de modele sunt ecuațiile algebrice, to-rye nu numai val. mai economice decât formulările verbale, dar presupun și minuțiozitatea și precizia definiției necesare pentru o exprimare și înțelegere clară a elementelor individuale și a relațiilor dintre ele. Cea mai importantă sarcină în construirea unui astfel de model este dezvoltarea și definirea clară și precisă a funcției obiective. Această funcție exprimă relația dintre variabile independente și dependente. Derivarea unei soluții dintr-un model dat A treia fază este găsirea unei soluții. De regulă, este de dorit să se găsească o soluție optimă sau mai bună, dar ar trebui să se țină cont de faptul că o astfel de soluție va avea valoare doar în contextul modelului luat în considerare. Deoarece modelul este doar o reprezentare a problemei lumii reale, există multe situații în care soluția optimă poate să nu fie asociată cu cea mai bună alegere. Totuși, atunci când soluția optimă este combinată cu soluții alternative mai puțin optime sau mai realiste, cu posibilitatea de testare ulterioară a acestora în raport cu o problemă reală, utilizarea soluției optime atrage anumite beneficii. Un astfel de beneficiu se referă la definiția de la sfârșitul studiului. distanța relativă dintre această soluție ideală și alternativa acceptată. Un produs secundar al acestei metodologii este utilizarea I. o. este presupunerea că soluțiile mai puțin optime pot fi văzute ca trepte în calea atingerii scopului. Această metodă de aproximări succesive poate conduce cercetătorul operațional la rezultate mai fructuoase. Sunt multe rogojini. proceduri de obţinere a soluţiilor în I. o. Aceste proceduri se bazează pe aplicații ale teoriei probabilităților. Validarea modelului și a soluției derivate din acesta Validarea modelului și a soluției este legată de implementarea a doi pași. Prima constă într-o analiză amănunțită a tuturor elementelor modelului, inclusiv. reverificarea factorilor săi algebrici pentru prezența unor erori cosmetice simpliste, care pot afecta validitatea. Dr. un pas și mai important implică redefinirea relației modelului cu ipotezele care au fost utilizate inițial pentru dezvoltarea acestui model. Un plan de revizuire mai sistematic include, de asemenea, utilizarea ist. date care pot fi introduse cu ușurință în model astfel încât să se poată obține o soluție prototip. Aceste date trebuie revizuite cu atenție pentru a asigura validitatea verificării cercetătorului operațional. Trebuie remarcat faptul că, de îndată ce acest model este practic dezvoltat pe baza surselor anterioare. date și nevoi, se poate comporta foarte diferit în viitor. Dr. o greșeală comună este introducerea de factori în model, to-secara nu au fost prezentate în ist. Bază de date. Stabilirea controlului A cincea etapă, stabilirea controlului asupra deciziei, apare în cursul utilizării repetate a modelului. Controlul asupra modelului se stabilește atunci când cercetătorul operațional permite discrepanțe în valorile ist. date și recunoaște că aceste discrepanțe pot afecta relațiile dintre elementele modelului și soluțiile rezultate. Dr. un pas important ar putea fi dezvoltarea restricţiilor asupra bazelor selectate. parametrii modelului pentru a stabili o gamă de valori acceptabile pe baza datelor reale. Implementarea modelului Pasul final este introducerea datelor reale în model. Prakt. implementarea modelului este asociată cu pasul evident de introducere a datelor reale și obținerea unei soluții la o problemă reală. În plus, este de asemenea important să se evalueze proximitatea soluției reale față de ist. soluțiile obținute anterior, precum și consecințele acestei decizii pentru îmbunătățirea modului de utilizare a modelului. Acești pași oferă o legătură importantă între covoraș. natura I. o. si practica. rezultatele cercetării. În cele din urmă, aceste decizii și implicațiile lor manageriale sunt folosite de un specialist experimentat în IA. pentru a rafina modelul pentru o posibilă utilizare ulterioară. Vezi și Metodologia cercetării (științifice) R. S. Endrulis