Management Sanitario per il corso di Laurea Magistrale...

Il corso Storia Il presente Un esempio La RO Programmazione Matematica IL problema di assegnamento

Management Sanitarioper il corso di Laurea Magistrale SCIENZE RIABILITATIVE DELLE PROFESSIONI SANITARIE

Modulo di Ricerca Operativa1a lezione

Prof. Laura Palagihttp://www.dis.uniroma1.it/∼palagi

Dipartimento di Ingegneria informatica automatica e gestionale A. RubertiSapienza Universita di Roma

Via Ariosto 25

1a lezione modulo RO L. Palagi


Management SanitarioCrediti formativi 6 cfu cosı suddivisi:

I Ricerca Operativa (MAT/09)- 2 cfu - Docente: Laura Palagi

I Laura Palagi --> didattica --> aa∼2016-17I Iscrizione consigliata a Gruppo Google Gruppomanagementsanitario2017

I Laboratorio (ultime due lezioni)

I Scienze infermieristiche gen. clin. e pediatriche (MED/45)- 2 cfu - Docente: Marianna Chianese

I Scienze infermieristiche e tecniche riabilitativeneuropsichiatriche (MED/48)- 2 cfu - Docente: Antonio Sili Scavalli

Materiale didattico e tutte le informazioni sono distribuite daidocenti in modo autonomo.



Management SanitarioCrediti formativi 6 cfu cosı suddivisi:

I Ricerca Operativa (MAT/09)- 2 cfu - Docente: Laura PalagiI Laura Palagi --> didattica --> aa∼2016-17I Iscrizione consigliata a Gruppo Google Gruppomanagementsanitario2017

I Laboratorio (ultime due lezioni)I Scienze infermieristiche gen. clin. e pediatriche (MED/45)

- 2 cfu - Docente: Marianna ChianeseI Scienze infermieristiche e tecniche riabilitative

neuropsichiatriche (MED/48)- 2 cfu - Docente: Antonio Sili Scavalli

Materiale didattico e tutte le informazioni sono distribuite daidocenti in modo autonomo.



MANAGEMENT

Termine anglosassone che indica:

I L’ insieme delle tecniche di gestione delle organizzazioni;ma anche

I L’insieme di tutte le funzioni di gestione o ancheI il gruppo dirigente di una organizzazione.



OPERATIONS MANAGEMENT

La logistica o gestione delle operations e quell’insieme diattivita di direzione e di controllo che governano i processi ditrasformazione dei diversi input utilizzati dall’impresa nellarealizzazione di beni e/o servizi.

E la funzione che sovrintende l’intero sistema che produce unbene o fornisce un servizio facendo sı che sia massimizzatal’efficacia del complessivo sistema di produzione aziendale.

Rappresenta un insieme di metodologie, strumenti e approcciutilizzati per l’analisi ed il miglioramento dei processi chetrasformano input in output.



I principali flussi di ”operazioni” nel MSI Logistica del paziente (patient flow logistics)

Ottimizzare la gestione dei flussi dei pazientiall’interno delle strutture ospedaliere dalmomento di primo accesso sino alla fasefinale di dimissione e gestione del postacuto.

I Logistica dei beniAssicurare un efficiente, appropriato etempestivo flusso di materiali verso i processidi trasformazione.

Si tratta di PIANIFICARE le operazioni: stabilire come utilizzarele risorse nell’orizzonte temporale di riferimento al fine diraggiungere l’obiettivo voluto;



Pianificazione dei processiI Ad es. una singola operazione chirurgica e un processo di

trasformazione che riceve degli input, assorbe dellerisorse, fornisce degli output;

I Il processo di trasformazione e caratterizzato dal fatto cheavviene nel tempo (ovvero non e istantaneo);

I Lo svolgimento del processo NON e perfettamentepre-determinabile, ovvero puo svolgersi in modo differenteda come ipotizzato (e soggetto a variabilita );

I Quando si hanno piu processi di trasformazione, ad es. piuoperazioni e sale, questi processi possono essere tra lorodipendenti

I La dipendenza deriva dal fatto che i diversi processicondividono parte delle stesse risorse o dalla necessita disincronizzare piu fasi.



Pianificazione (planning) strategico o tatticoI La pianificazione richiede che sia noto come piu processi

di trasformazione (operazioni) sono tra loro legati emutuamente influenzati.

I L’influenza puo riguardare sia l’asse temporale(contemporaneita e sequenzialita ) che l’asse delle risorse(concorrenza sulle stesse risorse).

I Orizzonte temporale: lungo - medio - breveI I concetti di lungo, medio e breve periodo sono relativi al

tipo di processo e non assoluti (possono andare da diversigiorni a diverse settimane/mesi).

I Planning di natura strategica-tattica a secondadell’orizzonte temporale



Pianificazione e previsioneI La pianificazion e concentrata sul futuro: tanto piu

l’orizzonte temporale di riferimento e ampio tanto piu lapianificazione e condizionata dalla previsione di cio chepotra accadere;

I Ad es. un piano operativo di 2 mesi dovra ipotizzare qualesara la domanda di pazienti a cui si dovra far fronte.

I Sebbene il futuro non sia certo, la disponibilita di unaprevisione consente

I poter predisporre la struttura con anticipo considerando il livello diincertezza a cui la previsione puo essere soggetta;

I Anticipare criticita e livellare piu possibile i carichi di lavoro;I Approvvigionamento di materiali;

I La pianificazione in generale conduce a risparmi e facilital’organizzazione.



Pianificazione e previsione

I Pianificazione strategicaI lungo - medio periodo (anni -mesi)I orientata dalla mission aziendali (valori e norme)I decisa dai piu alti livelli ziendali

I Pianificazione tattica e operativaI medio - breve periodo (mesi-settimane - giorni)I volta ad ottimizzare il processo operativo con attivita di

progettazione, controllo e valutazione.I dirigenti intermedi supportati da tecnici



Obiettivi: Ricerca Operativa

Dal sito Sapienza LM in Scienze Riabilitative delle Professioni Sanitarie”Acquisizione di competenze organizzative e gestionali in ambito riabilitativo.Conoscere e applicare: tecniche adeguate di comunicazione verbale e nonverbale individuale e di gruppo; strategie per favorire i processi diintegrazione multiprofessionale ed organizzativa e gestire gruppi di lavoro.”



Obiettivi: Ricerca Operativa

Dal sito Sapienza Laurea in Ingegneria Gestionale (ManagementEngineering): Ricerca Operativa”Introdurre i problemi di programmazione matematica, fornire competenzesulle principali proprieta matematiche di questa classe problemi, analizzarele particolari proprieta geometriche ed analitiche dei problemi diprogrammazione lineare, descrivere le basi del metodo del simplesso perproblemi di programmazione lineare, proporre dei primi esempi direalizzazione e utilizzazione di modelli di programmazione lineare e modellidi programmazione lineare intera. ”



Obiettivi reali e programma Ricerca Operativa”Il modulo ha l’obiettivo di introdurre lo studente alla analisi di problemi didecisionedi natura tattica e operativa che possono presentarsi nelleorganizzazioni sanitarie e alla formulazione di tali problemi in forma di modellimatematici cosı da rendere possibile l’utilizzo di tecniche quantitative.Semplici applicazioni saranno analizzate.”

I Introduzione alla ROI Analisi di problemi: con riferimento ad alcune situazioni

applicative, individuazione degli obiettivi e delle sceltealternative

I Saper ”leggere” un modello e utilizzarlo per il supporto alledecisioni (simulazione e ottimizzazione)



Cosa significa Ricerca Operativa?

I Letteralmente Ricerca Operativa e la traduzionedell’inglese (britannico) Operational Research o(americano) Operations Research abbreviati con la sigla”OR”

I ovvero ”ricerca sulle operazioni”

militariI Negli USA OR e sinonimo di Management Science (MS) e

spesso i due termini sono spesso usati congiuntamente”OR/MS” o ”ORMS”





I ovvero ”ricerca sulle operazioni”

militari

I Negli USA OR e sinonimo di Management Science (MS) espesso i due termini sono spesso usati congiuntamente”OR/MS” o ”ORMS”





I ovvero ”ricerca sulle operazioni”militariI Negli USA OR e sinonimo di Management Science (MS) e

spesso i due termini sono spesso usati congiuntamente”OR/MS” o ”ORMS”



Le prime ”operations” nella II Guerra MondialeIl nome ha un’origine ben identificabile legata ad operazionibelliche della Seconda Guerra Mondiale.Una delle ricostruzioni piu accreditate e dovuta al Prof. J. E.Beasley http://people.brunel.ac.uk/mastjjb/jeb/jeb.html.i dettagli in http://people.brunel.ac.uk/mastjjb/jeb/or/intro.html

I Tra il 1935 e il 1937 il Regno Unito lavoro ad un sistema dicontrollo della difesa antiaerea basato sull’uso del RAdioDetection And Ranging.

I Tecnicamente i radar erano estremamente affidabili per lalocalizzazione di un aereo nemico, ma non erano montatisugli apparecchi e dunque era necessario che il pilotafosse guidato da terra nel posto e nel momento giusti.



Biggin Hill ExperimentI (1937) Il ”Biggin Hill Experiment” costituı il primo tentativo di

integrare i dati ottenuti dai radar con quelli osservati a terra.(Ottimizzazione della distribuzione delle apparecchiature radar sulterritorio e segnalazione via radio ad opportune localita).

I I risultati non furono soddisfacentiI (1938) Si aggiungono altre 4 stazioni radar lungo la costa nel

tentativo di migliorare sia in copertura sia in efficienza il sistemadi localizzazione controllo degli aerei della RAF.

I Invece non migliora. Nasce la necessita di coordinare ecorrelare le tante informazioni, spesso anche in conflitto tra diloro.

I Nell’imminenza della guerra, il sovrintendente della BawdseyRes. St., A.P. Rowe, propose di sviluppare gli aspetti operativi(OPERATIONAL) del sistema e non piu quelli prettamentetecnici che erano da considerare soddisfacenti.

I Fu coniata l’espressione ”operational research”.





I I risultati non furono soddisfacenti

I (1938) Si aggiungono altre 4 stazioni radar lungo la costa neltentativo di migliorare sia in copertura sia in efficienza il sistemadi localizzazione controllo degli aerei della RAF.












I Fu coniata l’espressione ”operational research”.1a lezione modulo RO L. Palagi


Operational Research SectionI Fu selezionato un gruppo di scienziati di varie discipline

per costituire un OR team diretto dal comandante Sir HughDowding.

I (1939) la Gran Bretagna effettuo l’ultima esercitazionepre-bellica dove si evidenzio un notevole miglioramentonelle operazioni di difesa aerea grazie al contributo delgruppo di OR.

I (1943) la RO e usata negli USA1. guerra antisommergibile2. dimensionamento dei convogli navali3. scelta dei bersagli nelle incursioni aeree4. avvistamento ed intercettazione degli aerei nemici



Dantzig e la Programmazione LineareI Nel corso della II guerra mondiale, furono

complessivamente impegnati, nel Regno Unito, in Canadaed in USA, oltre 700 scienziati di diversi settori collaboranoper determinare la piu efficiente utilizzazione di risorseusando tecniche quantitative

I Tra questiGeorge B. Dantzig (1914 - 2005)

considerato il padre della Ricerca Operativa intesa comeI (1947) Programmazione Lineare (PL) e ideatore del

metodo per la sua soluzione (metodo del simplesso), unaparticolare classe di problemi matematici e di metodi per lasoluzione.



La RAND Corporation

I (1948) nasce negli USA il progetto RAND (research anddevelopment) (dal sito http://www.rand.org/about/history/)

” RAND Mission: The RAND Corporation is a nonprofitinstitution that helps improve policy and decision makingthrough research and analysis”.

I (1952) Dantzing entro a farne parte.I (1952) Editoriale dal titolo

Operations Research and Public Healthsulla rivistaAmerican Journal of Public Health and the Nations Health(Vol. 42, No. 10, pp. 1306-1307).



Operations Research and Public Health (1952)Editoriale dal titolo Operations Research and Public Health sulla rivista American Journal of Public Health and the

Nations Health (Vol. 42, No. 10, pp. 1306-1307)

”The problem of translating theory into practice is usually beset withdifficulty,.......Clearly, here are exciting possibilities of interweavingtheoretical insight with practical experience which no health worker can affordto overlook. While the application of operations research to problems ofpublic health is still a matter for the future, there are already indications ofareas where such methods might be employed............How valuableoperations research will eventually be to public health remains to be seen.The surface of the problems presented by such interaction of research andpolicy decisions has barely been touched. All that can be done here is todraw attention to this important branch of scientific activity and to indicate itspossible potential for public health.”http://ajph.aphapublications.org/doi/pdf/10.2105/AJPH.42.10.1306



Practical OR applications for healthcare MG (2009)Practical operations research applications for healthcare managers - Ann. Acad. Med. Singapore, 2009

”Despite its usefulness and proliferation of papers in the academic literature,there are still major issues around getting OR models widely accepted andused as part of mainstream decision-making by clinicians, health managersand policy-makers...... Some possible reasons for this include:

I i) Low levels of engineering/mathematical background in the healthcaresector

I ii) OR scholarly papers written for OR professionals, focusing onspecialised and technical topics, and not reaching healthcareprofessionals

I iii) Lack of process-related data for modellingI iv) Lack of in-house OR expertiseI v) High cost of engaging external OR consultants

Translation from theory to practice is never easy.....In addition, while OR mayrequire a fair bit of mathematical background, OR is also about usingcommon sense....”



La RO oggiLa RO e nata in un’era ”pre-computer”, cionononstante ilvantaggio nell’utilizzo delle tecniche di RO fu enorme.Nel 21o secolo, l’informatizzazione capillare rende disponibili

I enormi quantita di i dati,I la tecnologia fornisce la potenza di calcolo.

La RO ci mette il resto, cioe gli strumenti di analisi e disoluzione.La Ricerca Operativa consiste nell’applicare metodi analiticiavanzati allo scopo di risolvere problemi di decisione complessiche si presentano in molteplici settori della vita reale.La potenza di calcolo non e sufficiente per risolvere tuttiproblemi, ha solo spostato in avanti la frontiera dei problemiaffrontabili



Perche usare strumenti analitici ?Vediamolo su un esempio di assegnamento di personale.G.B. Dantzig - Linear Programming: the story about it began: some legends, a little about historical significance,

and comments about where its many mathematical programming extensions may be headed in History of

Mathematical programming - a collection of personal reminiscences, J.K. Lenstra, A.H.G. Rinnooy Kan and A.

Schrijver eds., NorthHolland (1991).

Un’azienda deve decidere come assegnare i suoi 70 dipendentia 70 differenti mansioni da svolgere.

OvviamenteI ciascun dipendente deve essere assegnato ad un solo

lavoroI ciascuna lavoro deve essere svolta esattamente da un

dipendenteNon e indifferente per l’azienda come effettuarel’assegnamento.



Perche usare strumenti analitici ?Vediamolo su un esempio di assegnamento di personale.G.B. Dantzig - Linear Programming: the story about it began: some legends, a little about historical significance,

and comments about where its many mathematical programming extensions may be headed in History of

Mathematical programming - a collection of personal reminiscences, J.K. Lenstra, A.H.G. Rinnooy Kan and A.

Schrijver eds., NorthHolland (1991).

Un’azienda deve decidere come assegnare i suoi 70 dipendentia 70 differenti mansioni da svolgere.Ovviamente

I ciascun dipendente deve essere assegnato ad un sololavoro

I ciascuna lavoro deve essere svolta esattamente da undipendente

Non e indifferente per l’azienda come effettuarel’assegnamento.



Enumerazione esaustiva delle soluzioniLe motivazioni possono essere diverse:

I preferenze di ciscun dipendente che svolge alcune mansioni piuvolentieri di altri oppure

I capacita lavorative di ogni singolo dipendente diverse per cui alcunilavori/mansioni riescono meglio ad alcuni piuttosto che ad altri

Queste preferenze possono essere quantificate associando un valore V adogni coppia (dipendente-mansione).Il problema consiste nel confrontare tutti i possibili assegnamenti didipendenti ad attivita e selezionare quella migliore.

Cosa significa ”migliore” ?

Naturalmente dipende dal puno di vista ! Per l’azienda (globale) ”migliore”significa ottenere il massimo guadagno medio in termini di gradimentooppure di prestazioni.



Formalizzando:I un insieme D di dipendenti {1,2, . . . ,70},I un insieme A di attivita {1,2, . . . ,70},I ad ogni coppia (dipendente]i , attivita ]j) e associato un

valore Vij > 0;

”migliore” = massimo guadagno medio

Questo guadagno puo essere quantificato con la somma deivalori Vij che corrispondono ad un’assegnazione.Ad esempio se

Vdipendente]i-attivita ]j = Vij =

{1 se i gradisce la j< 1 diversamente

la soluzione ideale sarebbe un assegnamento di dipendentialle attivita di valore pari a 70, ma non sempre e possibile.



Il caso con 3 dipendenti e 3 attivitaIl problema di assegnamento e stato proposto pe la prima voltasulla rivista (Psychometrika, 15(3), (1950) ”The problem of classification of personnel”).

ROBERT L. THORNDIKE 2 1 7

cri terion of job success. Though plenty of problems remain wi th respect to the detailed application of multiple regression techniques to the development of a ba t te ry of prediction tests, choice f rom among them, and combination of the tests into a bat tery, the main outlines for obtaining maximum prediction of a single job cri terion are clear and are famil iar to every s tudent of tests. In the case of the classification problem, however, no such mathematical ly best solution has been formulated. ( I t is, of course, possible tha t no solution exists.)

Before we can hope for a solution to the problem of classification, we must see to it tha t the problem is precisely formulated and clearly stated. What, in its essence, is the problem ? Reduced to its basic elements and to its pure form, it may be s tated as follows:

Given: A set of k job categories with N vacancies to be filled (N _>- k) , and N individuals to be used in filling them.

Requ i red : To assign the individuals to the jobs in such a way tha t the average success* of all the individuals in all the jobs to which they are assigned will be a maximum.

TABLE 1 Aptitudesof ThreeIndividualsforThreeJobs

Individual Job A Job B Job C

I 55 60 65 II 50 50 55

III 45 50 45

We can illustrate this by the example of three men and three jobs presented in Table 1. Suppose that those represent perfect ly valid measures of apt i tudes of the three men for the three jobs, all scores being expressed in s tandard scores of some reference popu- lation. There are, of course, six permutat ions of assignment of the men to the jobs, and examination of these quickly shows that the sum of the apt i tude scores is a maximum when I is assigned to Job C, II to Job A, and II I to Job B. The sum is then 165. It is not nec- essary that the jobs be equally weighted. Thus, if it were especially impor tan t to have the best talent in Job B, for example, tha t job might be given triple weight. The maximum of A ÷ 3B ÷ C is ob- tained by assigning individual I to Job B, l I to C, and III to A.

*The term "success", as it is used in this paper, may be interpreted quite broadly to include measures of job satisfaction as well as ratings of performance or measures of production.

dipendente #1

dipendente #2

dipendente #3

attivita #1

attivita #2

attivita #3



Il caso con 3 dipendenti e 3 attivitaIl problema di assegnamento e stato proposto pe la prima voltasulla rivista (Psychometrika, 15(3), (1950) ”The problem of classification of personnel”).

ROBERT L. THORNDIKE 2 1 7

cri terion of job success. Though plenty of problems remain wi th respect to the detailed application of multiple regression techniques to the development of a ba t te ry of prediction tests, choice f rom among them, and combination of the tests into a bat tery, the main outlines for obtaining maximum prediction of a single job cri terion are clear and are famil iar to every s tudent of tests. In the case of the classification problem, however, no such mathematical ly best solution has been formulated. ( I t is, of course, possible tha t no solution exists.)

Before we can hope for a solution to the problem of classification, we must see to it tha t the problem is precisely formulated and clearly stated. What, in its essence, is the problem ? Reduced to its basic elements and to its pure form, it may be s tated as follows:

Given: A set of k job categories with N vacancies to be filled (N _>- k) , and N individuals to be used in filling them.

Requ i red : To assign the individuals to the jobs in such a way tha t the average success* of all the individuals in all the jobs to which they are assigned will be a maximum.

TABLE 1 Aptitudesof ThreeIndividualsforThreeJobs

Individual Job A Job B Job C

I 55 60 65 II 50 50 55

III 45 50 45

We can illustrate this by the example of three men and three jobs presented in Table 1. Suppose that those represent perfect ly valid measures of apt i tudes of the three men for the three jobs, all scores being expressed in s tandard scores of some reference popu- lation. There are, of course, six permutat ions of assignment of the men to the jobs, and examination of these quickly shows that the sum of the apt i tude scores is a maximum when I is assigned to Job C, II to Job A, and II I to Job B. The sum is then 165. It is not nec- essary that the jobs be equally weighted. Thus, if it were especially impor tan t to have the best talent in Job B, for example, tha t job might be given triple weight. The maximum of A ÷ 3B ÷ C is ob- tained by assigning individual I to Job B, l I to C, and III to A.

*The term "success", as it is used in this paper, may be interpreted quite broadly to include measures of job satisfaction as well as ratings of performance or measures of production.

dipendente #1

dipendente #2

dipendente #3

attivita #1

attivita #2

attivita #31a lezione modulo RO L. Palagi


dipendente #1

dipendente #2

dipendente #3

attivita #1

attivita #2

attivita #3

{(1,1), (2,2), (3,3)}, {(1,1), (2,3), (3,2)}, {(1,2), (2,1), (3,3)},{(1,2), (2,3), (3,1)}, {(1,3), (2,2), (3,1)}, {(1,3), (2,1), (3,2)}.

dipendenti att]1 att]2 att]3dip]1 0,9 0,8 1dip]2 0,7 0,5 1dip]3 0,8 0,4 1



dipendente #1

dipendente #2

dipendente #3

attivita #1

attivita #2

attivita #3

{(1,1), (2,2), (3,3)},

{(1,1), (2,3), (3,2)}, {(1,2), (2,1), (3,3)},{(1,2), (2,3), (3,1)}, {(1,3), (2,2), (3,1)}, {(1,3), (2,1), (3,2)}.




dipendente #1

dipendente #2

dipendente #3

attivita #1

attivita #2

attivita #3

{(1,1), (2,2), (3,3)}, {(1,1), (2,3), (3,2)},

{(1,2), (2,1), (3,3)},{(1,2), (2,3), (3,1)}, {(1,3), (2,2), (3,1)}, {(1,3), (2,1), (3,2)}.




dipendente #1

dipendente #2

dipendente #3

attivita #1

attivita #2

attivita #3

{(1,1), (2,2), (3,3)}, {(1,1), (2,3), (3,2)}, {(1,2), (2,1), (3,3)},

{(1,2), (2,3), (3,1)}, {(1,3), (2,2), (3,1)}, {(1,3), (2,1), (3,2)}.




dipendente #1

dipendente #2

dipendente #3

attivita #1

attivita #2

attivita #3

{(1,1), (2,2), (3,3)}, {(1,1), (2,3), (3,2)}, {(1,2), (2,1), (3,3)},{(1,2), (2,3), (3,1)},

{(1,3), (2,2), (3,1)}, {(1,3), (2,1), (3,2)}.




dipendente #1

dipendente #2

dipendente #3

attivita #1

attivita #2

attivita #3

{(1,1), (2,2), (3,3)}, {(1,1), (2,3), (3,2)}, {(1,2), (2,1), (3,3)},{(1,2), (2,3), (3,1)}, {(1,3), (2,2), (3,1)},

{(1,3), (2,1), (3,2)}.




dipendente #1

dipendente #2

dipendente #3

attivita #1

attivita #2

attivita #3

{(1,1), (2,2), (3,3)}, {(1,1), (2,3), (3,2)}, {(1,2), (2,1), (3,3)},{(1,2), (2,3), (3,1)}, {(1,3), (2,2), (3,1)}, {(1,3), (2,1), (3,2)}.





dipendenti att]1 att]2 att]3dip]1 V11 V12 V13

dip]2 V21 V22 V23

dip]3 V31 V32 V33

Calcoliamo il valore delle diverse possibilita .

{(1,1), (2,2), (3,3)},V11 + V22 + V33 = 0,9 + 0,5 + 1 = 2,4{(1,1), (2,3), (3,2)},V11 + V23 + V32 = 0,9 + 1 + 0,4 = 2,3{(1,2), (2,1), (3,3)},V12 + V21 + V33 = 2,5{(1,2), (2,3), (3,1)},V12 + V23 + V31 = 2,6{(1,3), (2,2), (3,1)}, ,V13 + V22 + V31 = 2,4{(1,3), (2,1), (3,2)},V13 + V21 + V32 = 2,3





dip]2 V21 V22 V23

dip]3 V31 V32 V33

Calcoliamo il valore delle diverse possibilita .{(1,1), (2,2), (3,3)},V11 + V22 + V33 = 0,9 + 0,5 + 1 = 2,4

{(1,1), (2,3), (3,2)},V11 + V23 + V32 = 0,9 + 1 + 0,4 = 2,3{(1,2), (2,1), (3,3)},V12 + V21 + V33 = 2,5{(1,2), (2,3), (3,1)},V12 + V23 + V31 = 2,6{(1,3), (2,2), (3,1)}, ,V13 + V22 + V31 = 2,4{(1,3), (2,1), (3,2)},V13 + V21 + V32 = 2,3





dip]2 V21 V22 V23

dip]3 V31 V32 V33

Calcoliamo il valore delle diverse possibilita .{(1,1), (2,2), (3,3)},V11 + V22 + V33 = 0,9 + 0,5 + 1 = 2,4{(1,1), (2,3), (3,2)},V11 + V23 + V32 = 0,9 + 1 + 0,4 = 2,3

{(1,2), (2,1), (3,3)},V12 + V21 + V33 = 2,5{(1,2), (2,3), (3,1)},V12 + V23 + V31 = 2,6{(1,3), (2,2), (3,1)}, ,V13 + V22 + V31 = 2,4{(1,3), (2,1), (3,2)},V13 + V21 + V32 = 2,3





dip]2 V21 V22 V23

dip]3 V31 V32 V33

Calcoliamo il valore delle diverse possibilita .{(1,1), (2,2), (3,3)},V11 + V22 + V33 = 0,9 + 0,5 + 1 = 2,4{(1,1), (2,3), (3,2)},V11 + V23 + V32 = 0,9 + 1 + 0,4 = 2,3{(1,2), (2,1), (3,3)},V12 + V21 + V33 = 2,5

{(1,2), (2,3), (3,1)},V12 + V23 + V31 = 2,6{(1,3), (2,2), (3,1)}, ,V13 + V22 + V31 = 2,4{(1,3), (2,1), (3,2)},V13 + V21 + V32 = 2,3





dip]2 V21 V22 V23

dip]3 V31 V32 V33

Calcoliamo il valore delle diverse possibilita .{(1,1), (2,2), (3,3)},V11 + V22 + V33 = 0,9 + 0,5 + 1 = 2,4{(1,1), (2,3), (3,2)},V11 + V23 + V32 = 0,9 + 1 + 0,4 = 2,3{(1,2), (2,1), (3,3)},V12 + V21 + V33 = 2,5{(1,2), (2,3), (3,1)},V12 + V23 + V31 = 2,6

{(1,3), (2,2), (3,1)}, ,V13 + V22 + V31 = 2,4{(1,3), (2,1), (3,2)},V13 + V21 + V32 = 2,3





dip]2 V21 V22 V23

dip]3 V31 V32 V33

Calcoliamo il valore delle diverse possibilita .{(1,1), (2,2), (3,3)},V11 + V22 + V33 = 0,9 + 0,5 + 1 = 2,4{(1,1), (2,3), (3,2)},V11 + V23 + V32 = 0,9 + 1 + 0,4 = 2,3{(1,2), (2,1), (3,3)},V12 + V21 + V33 = 2,5{(1,2), (2,3), (3,1)},V12 + V23 + V31 = 2,6{(1,3), (2,2), (3,1)}, ,V13 + V22 + V31 = 2,4

{(1,3), (2,1), (3,2)},V13 + V21 + V32 = 2,3





dip]2 V21 V22 V23

dip]3 V31 V32 V33

Calcoliamo il valore delle diverse possibilita .{(1,1), (2,2), (3,3)},V11 + V22 + V33 = 0,9 + 0,5 + 1 = 2,4{(1,1), (2,3), (3,2)},V11 + V23 + V32 = 0,9 + 1 + 0,4 = 2,3{(1,2), (2,1), (3,3)},V12 + V21 + V33 = 2,5{(1,2), (2,3), (3,1)},V12 + V23 + V31 = 2,6{(1,3), (2,2), (3,1)}, ,V13 + V22 + V31 = 2,4{(1,3), (2,1), (3,2)},V13 + V21 + V32 = 2,3



La migliore scelta tra quelle che rispetta le restrizioni e{(1,2), (2,3), (3,1)} di valore 2,6dipendente #1

dipendente #2

dipendente #3

attivita #1

attivita #2

attivita #3

Attenzione ! Esistono delle combinazioni con valore migliore di2,6 ma non soddisfano le restrizioni di copertura di tutte leattivita .Ad esempio: {(1,3), (2,3), (3,3)} di valore 3 oppure{(1,1), (2,3), (3,1)} di valore 2,7 !Hanno valore piu alto ma non risolvono il problema richiesto.




dipendente #2

dipendente #3

attivita #1

attivita #2

attivita #3

Attenzione ! Esistono delle combinazioni con valore migliore di2,6 ma non soddisfano le restrizioni di copertura di tutte leattivita .

Ad esempio: {(1,3), (2,3), (3,3)} di valore 3 oppure{(1,1), (2,3), (3,1)} di valore 2,7 !Hanno valore piu alto ma non risolvono il problema richiesto.




dipendente #2

dipendente #3

attivita #1

attivita #2

attivita #3

Attenzione ! Esistono delle combinazioni con valore migliore di2,6 ma non soddisfano le restrizioni di copertura di tutte leattivita .Ad esempio: {(1,3), (2,3), (3,3)} di valore 3 oppure

{(1,1), (2,3), (3,1)} di valore 2,7 !Hanno valore piu alto ma non risolvono il problema richiesto.




dipendente #2

dipendente #3

attivita #1

attivita #2

attivita #3

Attenzione ! Esistono delle combinazioni con valore migliore di2,6 ma non soddisfano le restrizioni di copertura di tutte leattivita .Ad esempio: {(1,3), (2,3), (3,3)} di valore 3 oppure{(1,1), (2,3), (3,1)} di valore 2,7 !Hanno valore piu alto ma non risolvono il problema richiesto.



Enumerazione esaustiva delle soluzioniQuante sono le possibili scelte?

dipendenti possibilita3 6 = 3 · 24 24 = 4 · 3 · 25 120 = 5 · 4 · 3 · 2...

...n n!

Nel caso di 70 dipendenti/attivitale possibili assegnazioni sono 70! (70 fattoriale)

Per ciascuna di esse devo calcolare il valore e poi scegliere lamigliore.

Quanto e ”grande” 70! ?




dipendenti possibilita3 6 = 3 · 2

4 24 = 4 · 3 · 25 120 = 5 · 4 · 3 · 2...

...n n!







dipendenti possibilita3 6 = 3 · 24 24 = 4 · 3 · 2

5 120 = 5 · 4 · 3 · 2...

...n n!







dipendenti possibilita3 6 = 3 · 24 24 = 4 · 3 · 25 120 = 5 · 4 · 3 · 2

......

n n!








...

n n!








...n n!








...n n!



Quanto e ”grande” 70! ?1a lezione modulo RO L. Palagi


mooooooooolto granden 2 4 6 10 15 20 60 70

n ! 2 24 720 3628800 1307674368000 2432902008176640000 - -ordine 1 10 102 106 ∼ 1012 ∼ 1018 ∼ 1081 ∼ 10100

di grandezza

Le possibilita sono un numero enorme, piu grande di 10100.

Possiamo farcela con l’attuale tecnologia ?

Fino a giugno 2014 il piu potente supercomputer e Tianhe-2della Sun Yat-sen University, Guangzhou, China che raggiungeil record di 33.86 peta(1015)FLOPSIn informatica FLOPS e un’abbreviazione di FLoating point Operations Per Second e indica il numero di operazioni

in virgola mobile eseguite in un secondo dalla CPU.

Sarebbe questo calcolatore in grado di esaminare tutte le 70!combinazioni possibili ? E in quanto tempo ?



Sarebbe questo calcolatore in grado di esaminare tutte le 70!combinazioni possibili ?

In un anno ci sono (365*24*3600=)31536000∼ 3 · 107 secondi,dunque in un anno Tianhe-2 e in grado di effettuare

∼ 3 · 107 · 33,86 · 1015 =∼ 1024

Floating Point Operations.Dunque per enumerare tutte le possibilita Tianhe-2 dovrebbelavorare circa 10100/1024 = 1076 anni.L’eta dell’universo e di circa 13 miliardi di anni (13·109) !!!!!

La risposta e no,nemmeno se fosse al lavoro dai tempi del Big Bang.



If, there were 1040 Earths circling the sun each filled solid with nanosecond speed computers all programmed in

parallel from the time of the big bang until the Sun grows cold, then perhaps the answer might be, YES.

Perche usare strumenti analitici ?

I In molte situazioni e impensabile esaminare tutti i casipossibili per determinare qual e il migliore.

I approccio “ad hoc” ground-rule: affidarsi al semplice buonsenso di persone competenti del settore che sulla basedell’esperienza acquisita definiscano poche regolespecifiche per risolvere i problemi non e piu sufficiente afar fronte alla sempre piu crescente complessitaorganizzativa dei sistemi di produzione e servizio.



La RO puo definirsi come un approccio quantitativo allasoluzione di problemi di decisione nell’ambito di sistemi

organizzati.

I Interdisciplinarita uso di tecniche e metodologie mutuateda diversi settori disciplinari (logica, algebra lineare,statistica, teoria dei sistemi, teoria delle code, teoria deigiochi, etc.)

I Visione unitaria di un sistema. La maggior parte dei sistemireali coinvolge diversi aspetti di un sistema mutuamenteinteragenti ed essenziale lanalisi dellinterazione reciproca.

I approccio modellistico-ottimizzatorio in contrapposizioneall’approccio “ad hoc ground rule” dalla RO



Un modello sbagliato ?

I e esaustivo; dunque si puo definire solo per valori di npiccoli

I e se cambia n devo ridefinire l’insieme dele posisbilescelte; se cambia un valore nei parametri devo effettuarenuovamente ricostruzione del modello e enumerazioneesautsiva



Programmazione MatematicaIn questo corso tratteremo problemi di ProgrammazioneMatematica.

In questo contesto il termine “programmazione” non deveessere inteso nel senso di di costruzione di programmi per ilcalcolatore, seppur il calcolatore elettronico sia uno strumentoindispensabile per risolvere problemi di ProgrammazioneMatematica.I problemi di Programmazione Matematica rappresentanoproblemi decisionali con

I un solo decisore,I un solo obiettivo che rappresenta il criterio di scelta tra le

diverse alternativeI deterministici, ovvero i dati si considerano ”certi” non affetti

da stocasticit.




In questo contesto il termine “programmazione” non deveessere inteso nel senso di di costruzione di programmi per ilcalcolatore, seppur il calcolatore elettronico sia uno strumentoindispensabile per risolvere problemi di ProgrammazioneMatematica.

I problemi di Programmazione Matematica rappresentanoproblemi decisionali con



da stocasticit.




In questo contesto il termine “programmazione” non deveessere inteso nel senso di di costruzione di programmi per ilcalcolatore, seppur il calcolatore elettronico sia uno strumentoindispensabile per risolvere problemi di ProgrammazioneMatematica.I problemi di Programmazione Matematica rappresentanoproblemi decisionali con



da stocasticit.1a lezione modulo RO L. Palagi


Altre classi di problemi

Si tratta ovviamente di ipotesi siemplficative, ma checonsentono di modellare molte situazioni di interesse incontesto di management sanitario. Possibili estensioni sono:

I i problemi con piu decisori (in ”competizione”) che sonooggetto di studio nella Teoria dei Giochi;

I Problemi con piu obiettivi (in conflitto) che rientrano nell’Ottimizzazione a molti obiettivi;

I i problemi di ottimo in cui i dati sono soggetti da incertezzecaratterizzabili in modo probabilistico che rientrano nellaProgrammazione Stocastica.



Programmazione matematicaSono modelli con una struttura di questo tipo

Ottimizza obiettivorestrizione− 1restrizione− 2...restrizione−m

in cui obiettivo rappresenta il crierio di scelta individuato erestrizione-1, ....,restrizione-m rappresentano lelimitazioni alle scelte. La parola Ottimizza sta a indicare che sivuole individuare la scelta che consente di ottenere il migliorvalore dell’obiettivo.



Programmazione matematica

Obiettivo e restrizioni sono relazioni matematiche chelegano i parametri del problema con le possibili sceltedecisionali.Per introdurre una simbologia matematica, le possibili scelte,leve decisionali sono spesso indicate con la lettera x el’obiettivo e le restrizioni sono funzioni matematiche chedipendono da x .

Una funzione e una relazione tra due insiemi, chiamati dominioe codominio della funzione, che associa ad ogni elemento deldominio uno e un solo elemento del codominio.



Programmazione matematicaLa funzione obiettivo e spesso indicata con f o f (x) per indicarela dipendenza dalle variabili decisionali.Si dice che x e l’argomento della funzione, oppure un valoredella variabile indipendente, mentre y = f (x) e un valore dellavariabile dipendente della funzione.

Inoltre la parola ottimizzare puo essere declinata comemassimizzare, se il criterio di scelta rappresenta un ”vantaggio”(ed es. profitto) oppure minimizzare, se il criterio rappresentauno ”svantaggio” (ad es. un costo).

max f (x) min f (x)



Programmazione matematicaLe restrizioni sono espresse in forma di uguaglianza odisuguaglianze. Si tratta quindi di funzioni a cui si richiede diassumere determinati valori

g1(x) ≤ b1 gm(x) ≤ bm

oppureg1(x) = b1 gm(x) = bm

Un modello matematico di Programmazione Matematica e deltipo

max /min f (x)g1(x) ≤ (=)b1...gm(x) ≤ (=)bm



Programmazione Lineare (PL)

I problemi di Programmazione matematica di interesse inquesto corso sono Problemi Lineari cioe le funzioni chedescrivono obiettivo e restrizioni sono lineari.Una funzione lineare e una funzione polinomiale di gradomassimo uno cioe del tipo

a0 + a1x1 + a2x2 + · · ·+ anxn

where ai ∈ R sono coefficienti a valori reali e xi sono le variabilidi decisione. Qui si assume che le variabili siano n cioe x ∈ Rn.



Ma algoritmo che vuol dire ?La RO si dedica alla definizione di metodi efficienti (algoritmi disoluzione) per determinare una soluzione.Un insieme di istruzioni elementari che eseguite (sucalcolatore) consentono di determinare la soluzione di unproblema in un tempo finito

La scelta dell’algoritmo da utilizzare dipende dal tipo diproblema che necessario risolvere.

Il piu famoso nella RO e il metodo del simplesso che consentedi determinare la soluzione ottima di una classe particolare diproblemi di programmazione matematica (problema diprogrammazione lineare).



Approccio modellistico ai problemi di decisioneI Descrizione e Analisi del problema

I individuare i parametri di controllo, i legami logico-funzionali e gli obiettivi

I Costruzione del modello

I descrizione formalizzata del problema: individuazione di una corrispondenza tra relazioni del

mondo reale (relazioni tecnologiche, leggi fisiche, vincoli di mercato, etc.) e relazioni matematiche

(equazioni, disequazioni, dipendenze logiche, etc.)

I Analisi del modello

I deduzione per via analitica di alcune importanti proprieta, quali esistenza, unicita, stabilita ecc.

I Selezione di “buone” soluzioni

I (ottimizzazione e/o simulazione)

I Validazione del modello

I verifica che i risultati ottenuti siano congruenti con il problema





I Costruzione del modelloI descrizione formalizzata del problema: individuazione di una corrispondenza tra relazioni del



I Analisi del modello

I deduzione per via analitica di alcune importanti proprieta, quali esistenza, unicita, stabilita ecc.












I Analisi del modelloI deduzione per via analitica di alcune importanti proprieta, quali esistenza, unicita, stabilita ecc.













I Selezione di “buone” soluzioniI (ottimizzazione e/o simulazione)











I Selezione di “buone” soluzioniI (ottimizzazione e/o simulazione)

I Validazione del modelloI verifica che i risultati ottenuti siano congruenti con il problema



Assegnamento: definizione del problemaUn’azienda deve decidere come assegnare i suoi 3 dipendentia 3 differenti attivita da svolgere.

Ciascun dipendente puo esprimere una preferenza


I ciascun dipendente deve essere assegnato ad un solaattivita ;

I ciascuna attivita deve essere svolta esattamente da undipendente.

Supponiamo che l’azienda voglia massimizzare il”soddisfacimento” medio.



Assegnamento: definizione del problemaUn’azienda deve decidere come assegnare i suoi 3 dipendentia 3 differenti attivita da svolgere.Ciascun dipendente puo esprimere una preferenza




Supponiamo che l’azienda voglia massimizzare il”soddisfacimento” medio.



Costruzione del modello

Si tratta di individuare le leve decisionali o variabili di decisioneche rappresentano le grandezze che e possibile scegliere, sucui si ha potere decisionale.

Nel caso del problema di assegnamento la scelta chedobbiamo individuare e se assegnare un certo dipendente]i adun’attivita ]j per ogni possibile coppia i , j .



Le leve decisionali

Valori diversi indicano scelte decisionali diversi. Nel caso diproblema di assegnamento si tratta di scelte dicotomiche(assegnato/non assegnato).Formalizzando con un linguaggio matematicoLe scelte decisionali=variabili di decisione

dip]i assegnato alla att]j =

{VEROFALSO

=

{©×

=

{10



Le leve decisionaliDunque una scelta decisionale puo essere rappresentata come

dipendenti att]1 att]2 att]3dip]1 1 0 0dip]2 0 1 0dip]3 0 0 1

Per semplificare la scrittura indichiamo le variabili di decisionecome xij (ma si tratta di un nome !) che puo assumere solo duevalori {0,1} e sono n2 = 9

dipendenti att]1 att]2 att]3dip]1 x11 x12 x13dip]2 x21 x22 x23dip]3 x31 x32 x33



La funzione obiettivoL’ottimizzazione consiste nell’individuare il valore massimo o ilvalore minimo dell’obiettivo ottenuto in corrispondenza a diversivalori delle scelte.Spesso l’insieme delle leve decisionali si rappresenta ”inblocco” x = (x11 x12 x13 x21 x22 x23 x31 x32 x33)L’obiettivo e una funzione matematica che lega i parametridel problema con le possibili scelte decisionali.

dipendenti att]1 att]2 att]3dip]1 x11 x12 x13

dip]2 x21 x22 x23

dip]3 x31 x32 x33


dip]2 V21 V22 V23

dip]3 V31 V32 V33



Ad esempioLa scelta decisionale {(1,1), (2,2), (3,3)} si rappresenta come


Dati i parametri


si ottiene il valoreV11x11 + V22x22 + V33x33 = 0,9 + 0,5 + 1 = 2,4



La funzione obiettivo

V11x11 + V12x12 + V13x13+V21x21 + V22x22 + V23x23+V31x31 + V32x32 + V33x33

Spesso la funzione obiettivo si indica con f e dipende dallascelta x :

f (x) =n∑

i=1

n∑j=1

Vijxij

Ottimizza significa individuare la particolare scelta x∗, tra quellepossibili, che definisce il valore massimo o minimo dell’obiettivof ∗ = f (x∗).Nel nostro caso abbiamo visto che f ∗ = 2,6.



Le restrizioniI vincoli sono funzioni matematiche che esprimono le restrizioniche devono rispettare le scelte decisionali.



dipendenti att]1 att]2 att]3

→

dip]1 1 0 0

→

dip]2 0 1 0

x21 + x22 + x23 = 1→

dip]3 0 0 1

↑ ↑ ↑x12 + x22 + x32 = 1






dipendenti att]1 att]2 att]3→ dip]1 1 0 0→ dip]2 0 1 0 x21 + x22 + x23 = 1→ dip]3 0 0 1

↑ ↑ ↑x12 + x22 + x32 = 1






dipendenti att]1 att]2 att]3

→

dip]1 1 0 0

→

dip]2 0 1 0

x21 + x22 + x23 = 1→

dip]3 0 0 1↑ ↑ ↑

x12 + x22 + x32 = 1



I vincoli

x11 + x12 + x13 = 1 dipendente 1 assegnato esattamente ad una attivitax21 + x22 + x23 = 1x31 + x32 + x33 = 1

x11 + x21 + x31 = 1 attivita 1 assegnata esattamente ad un dipendentex12 + x22 + x32 = 1x13 + x23 + x33 = 1

Sono 2 · n = 6



I vincoliAnche i vincoli sono funzioni gi che dipendono dalle variabili didecisione x

g1(x) = x11 + x12 + x13 = 1 = b1g2(x) = x21 + x22 + x23 = 1 = b2g3(x) = x31 + x32 + x33 = 1 = b3g4(x) = x11 + x21 + x31 = 1 = b4g5(x) = x12 + x22 + x32 = 1 = b5g6(x) = x13 + x23 + x33 = 1 = b6

Una scelta x che soddisfa tutti i vincoli si dice ammissibile.L’insieme di tutte le soluzioni ammissibili si dice insiemeammissibile.



Un modello di programmazione matematica

maxn∑

i=1

n∑j=1

Vijxij

n∑i=1

xi j = 1 per ogni j = 1, . . . ,n

n∑j=1

xi j = 1 per ogni i = 1, . . . ,n

xij ∈ {0,1} i = 1, . . . ,n j = 1, . . . ,n




Determinare il valore x∗ delle variabili di decisione che siaammissibile e massimizzi il valore dell’obiettivo Tale soluzionex∗ si chiama soluzione ottimaNel nostro caso la soluzione ottima x∗ e


o anche x∗ = (0 1 0 0 0 1 1 0 0) e vale f ∗ = 2,6.




ATTENZIONE: le variabili di decisione non possono assumeretutti i valori nel rispetto dei vincoli ma devono {0,1}. Non sitratta di un aspetto secondarioAd esempio il valore delle variabili

dipendenti att]1 att]2 att]3dip]1 1

212 0

dip]2 12

12 0

dip]3 0 0 1

soddisfa tutti i vincoli fi (la somma sulle righe e sulle colonne epari a 1) MA NON e una scelta valida !



Le fuzioni che descrivono l’obiettivo e i vincoli sono linearirispetto alle variabili x .

fi = a1x1 + a2x2 + . . . =N∑

i=1

aixi

Si tratta di un problema di

Programmazione Lineare intera

max f (x)fk (x) = bk k = 1, . . . ,2nxij ∈ {0,1}n

2

In generale xij ∈ {0,1} e un VINCOLO (restrizione)IMPORTANTE. In alcuni casi e possibile ”trascurarlo”garantendo la qualita della soluzione.



Un modello di programmazione matematicaIn particolare, per questa categoria di problemi grazie allaparticolare struttura delle funzioni di vincolo, puo esseresostituito

maxn∑

i=1

n∑j=1

Vijxij

n∑i=1

xij = 1 per ogni j = 1, . . . ,n

n∑j=1

xij = 1 per ogni i = 1, . . . ,n

xij ≥ 0 i = 1, . . . ,n j = 1, . . . ,n



Le fuzioni che descrivono l’obiettivo e i vincoli sono linearirispetto alle variabili x .

fi = a1x1 + a2x2 + . . . =N∑

i=1

aixi

Le variabili possono assumere valori continui nel rispetto deivincoli.Si tratta di un problema di Programmazione Lineare.

max f (x)fk (x) = bk k = 1, . . . ,2nxij ≥ 0 ∀ i , j


Management Sanitario per il corso di Laurea Magistrale...

Documents

Transcript of Management Sanitario per il corso di Laurea Magistrale...