Appunti di Ricerca operativa

Definizioni, concetti preliminari di problema di ottimizzazione

I vincoli danno origine ad una regione nella quale viene ricercato l'ottimo. iClassification Esempi Problemi e metodologie risolutive Programmazione Emessa.

Definizioni e concetti primi

Insiemi convessi

Si genera un punto che giace sul segmento che congiunge i due punti ed esso si dice combinazione convessa dei due punti.

Si osserva che se si fa variare il coefficiente, si varia la posizione di z.

Se poi il coefficiente si pone molto prossimo al 0 allora ci si avvicina al punto y, al contrario se viene preso un coefficiente vicino ad 1 allora ci si avvicina a x.

È la 2 devono essere variare e usando scrittura coefficienti uno possibile x y per amo per collegati A Ny NAtia N 0Z 1x con e Incolto di convesso.

In questo modo si sta rappresentando una relazione lineare.

Si pensi al caso in cui uno dei due coefficienti diventi negativo: i punti che andrebbero generare sarebbero tutti quelli che stanno al di fuori del segmento stesso, quelli che stanno sulla retta sulla quale giace il segmento.

In generale si genera un coefficiente per ogni vettore considerato.

Cosa succede se i punti non sono più 2 ma 3?? Dove si trova z??

Ma nella pratica, nel piano cartesiano, anche in questo caso i punti che soddisfano la condizione sono infiniti e z si trova ovunque e all'interno del triangolo formato dai tre punti.

Si genera quindi tutta la regione convessa rappresentata dai punti, ossia un politopo in quanto è limitato, non contiene una regione aperta. Bmidi Ida.

Definizione e analisi

Segmento IRiano Xo EX EX te1 E 10.17DI XoXo.

Segmento estremi A dei puri insieme combinazioni convesse non vale.

È importante dimostrare che l'intersezione di due insiemi è un insieme convesso ma questo per l'unione. ha ha ru.

Tipicamente una funzione convessa viene minimizzata, si ricerca il minimo, mentre per una funzione concava si ricerca il massimo, e quindi viene massimizzata.

Dal punto di vista geometrico: per ogni coppia di punti che viene preso sulla funzione il segmento che li congiunge giace al di sopra della funzione.

Interpretazione definizione: presi x e y si genera una combinazione convessa di x e y, ossia si genera z.

Si disegna poi f(z) sulla funzione, tenendo anche conto di f(y) e f(x).

La funzione è convessa quando il valore della combinazione convessa valutato nella funzione giace sotto il segmento.

In sostanza la funzione è convessa quando f(z) è minore o uguale ad un punto giacente sul segmento in corrispondenza del lambda scelto.

Quando viene risolto un problema di ottimizzazione convessa si risolve un problema in cui le funzioni obiettivo sono convesse o concave e il dominio è convesso.

Intorni locali, ottimi minimi e globali

Intorni locali ottimi minimi e globali e fuel Fateful.

A lato è rappresentata una funzione che globalmente non è lineare.

NB: non c'è differenza fra scegliere il minimo dal massimo, infatti se si sta minimizzando una funzione ma si vuole ritrovare il massimo, basta cambiare il segno della funzione di minimo trovata. 2.

I punti di minimo locale sono effettivamente di minimo quando si considerano punti che giacciono dell'intorno di x e le loro immagini tramite la funzione sono maggiori o uguali al minimo locale.

Ma ora come si definisce l'intorno??

Il modo classico e più semplice è il modo euclideo, ossia si sceglie un epsilon e si scelgono tutti i punti tali che la distanza euclidea fra x (stabilito) ed y (scelto dopo) sia minore di epsilon. giusta.

Ha la dimensione per consentire di fare questa affermazione. euclideo.

Convessità e intorno

Il seguente è il teorema base della programmazione convessa ed è fondamentale.

Si ha la doppia convessità, sia della funzione che dell'insieme di definizione.

La x non è un vettore in due dimensioni ma un vettore di .

Questo teorema afferma che ogni punto di ottimo locale è anche globale, con le ipotesi date.

NB: la programmazione lineare, date le relazioni con la programmazione convessa, eredita tutte le proprietà della programmazione convessa, compresa questa affermazione fondamentale. dentro.

Infatti la programmazione lineare giace la programmazione convessa. fix.

Si insostituisce quanto sta nell'inoruodifineerottenerelamaggiorazioneecita magnanimi.

Data l'ipotesi, si sa certamente che per ogni y preso nell'intorno vale.

z potrebbe variare lungo tutto il segmento e si sceglie uno z che stia nell' intorno di x; per garantire questo si sceglie un lambda opportuno, ossia un lambda molto prossimo ad 1, che assicuri che z sia vicino ad x.

Data questa situazione si sa che poiché z giace nell'intorno di x.

Nella dimostrazione si sfrutta la definizione di convessità, dalla quale si isola f(y).

Funzioni concave

Infatti se si congiungono due punti qualsiasi della funzione attraverso un segmento ci si accorge che coincide con parte del grafico della funzione e quindi valgono sia le definizioni di funzione convessa, che concava. lineare.

Programmazione e risoluzione grafica

Programmazione risoluzione Madeffi e grafica enea programmazione L LLL.

La prima cosa da decidere per modellizzare un problema riguarda la scelta delle variabili.

Le variabili in gioco, come scritto nell'immagine sopra sono due e rappresentano le quantità da acquistare di una materia e dell'altra e si sa per certo che non saranno mai negative -> verranno rappresentate quindi nel primo quadrante del piano cartesiano.

La funzione obiettivo sarà da minimizzare, data la natura del problema.

54 6 è lineare obiettivo Funzione 2 almeno maggiore o uguale.

I vincoli riguardano la capacità produttiva, si deve produrre un certo numero di unità: si utilizza un 71,82 la A vincoli di 0,34 O x richiesta per fa lo stesso prodotto per ogni Quindi Osservazione.

I vincoli possono essere moltiplicati per una quantità (sia a destra che a sinistra della maggiorazione) per rendere i coefficienti interi.

Come rappresentare un vincolo graficamente??

Considerando il primo vincolo (moltiplicato per un coefficiente 10), si nota che questo è una retta e si tiene conto dei punti nei quali questa interseca gli assi, tenendo conto che si trova nel primo quadrante, data la maggiorazione.

Si pone a 0 x1 e si ricava x2 e viceversa.

Quando in un vincolo compare una maggiorazione: si rappresenta una retta e poi si indicherà il semipiano superiore o inferiore alla retta in base alla maggiorazione.

Infatti ricorda che ad ogni disequazione corrisponde un'equazione associata, che in questo caso rappresenta una retta. Si deve partire con il disegno della retta.

Determinazione del semipiano

Si prende l'origine degli assi, si sostituisce nell'espressione del vincolo:

• Se l'origine è compresa allora si sceglie il semipiano che la comprende.
• Se l'origine non è compresa (ossia se non soddisfa il vincolo) allora si prende il semipiano che non contiene l'origine, che in questo caso coincide con il semipiano superiore.

a ammissibile regione.

Si nota ora che la regione ammissibile non è limitata, infatti le soluzioni al problema sono estremi infinite. frontiera.

Quello che si va a fare consiste nel rappresentare la della regione ammissibile.

Poliedro, si ha a che fare con una regione non limitata, un limitato dalla spezzata in rosso. Si anche lemmasfruttarequesto perpuòestremi e che da alcuni punti ossia i punti di intersezione fra vincoli diversi. la rappresentazione.

Gli ottimi si trovano sui punti di intersezione di due vincoli, anche se questo non vale sempre. In R2 ogni punto estremo si trova in corrispondenza dell'intersezione fra due retta vincoli, in R3 si troverà all'Intersezione fra 3 vincoli e così via. Lemma datauna nellaformaRb ilEascitbser e Cacon suo.

Come si trova il punto di intersezione fra vincoli?? Ma ora.

Dal punto di vista algebrico si mettono a sistema le espressioni dei vincoli. tao b definizione ortogonale per gradiente il alla i è retta sempre orientato verso semipiano.

Programmazione lineare e vertici

In programmazione lineare la soluzione sta sempre su un vertice!! basecui are.

Basta quindi calcolare l'ottimo (il vertice ottimo) della funzione obiettivo per calcolare la soluzione.

Questo però non è semplice in quanto al crescere della complessità dei problemi, il numero di vincoli cresce in maniera esponenziale.

Ricorda che nella regione ammissibile ci sono tante soluzioni che rispettano i vincoli.

La regione ammissibile è un insieme convesso, essendo intersezione di semipiani.

Curve di livello

Sostanzialmente le curve di livello corrispondono alla funzione obiettivo: viene presa ek, posta uguale ad un certo ossia una costante (determinata arbitrariamente). k.

Si pone variabile e si ottiene le curve di livello come un fascio improprio di rette, tutte parallele.

È necessario poi, prendendo di riferimento una di queste rette e chiedersi in che direzione si spostano le curve di livello.

Problema di massimo: se si ha un la direzione di spostamento è quella del gradiente della problema di minimo funzione obiettivo, al contrario, nel caso di un si ha che la direzione di spostamento è quella dell'antigradiente.

Si ricorda che il gradiente è definito come il vettore le cui componenti sono le derivate parziali della funzione considerata, rispetto gli assi cartesiani.

Le curve di livello si spostano (nella direzione determinata in base al tipo di problema) no al punto di tangenza con la regione ammissibile.

Il punto di tangenza risulterà sempre essere l'intersezione tra due (o più) vincoli, che vengono posti a sistema. La freccia nera indica la direzione della curva di livello.

Direte fascio Geometria improprio e Algebra Una retta la bdi alla byretta unfascio e 0,0 o axrette parallele ra t con improprio appartiene ha KEIR del Kbytipo Oax con un equazione massimizzazione righe o prodotti colonne_processi.

Massimizzazione e risorse

È risorse sono limitate, ogni processo ha un tempo massimo di lavorazione.

Si parte sempre determinando le variabili.

Non bisogna considerare un prodotto tra variabili, in quando ci stiamo occupando della programmazione lineare.

Poiché i processi sono 3, ci si aspetta che i vincoli siano 3.

Il modo più immediato di rappresentazione è quella tale per cui si parte dal calcolo dell'intersezione fra i vincoli e gli assi cartesiani.

Regione ammissibile Kre i vincoli si estrag tabella dalla sopra V3.

I vincoli sono 3 e una volta rappresentati ci si domanda quale semipiano si va a considerare e svolti i calcoli si prendono tutti i semipiani che contengono l'origine degli assi.

Vincolo ridondante: il vincolo in verde viene definito è tale per cui se viene rimosso la regione ammissibile non cambia.

Limitata politopo. Questa regione ammissibile, a differenza del problema precedente, è e dà origine ad un (che in generale è anche un poliedro).

Definizione di problema decisionale

Definizione: problema decisionale problema di scelta elevato.

Un problema decisionale nell'ambito della matematica riguarda un in cui si deve prendere una decisione tra un numero di soluzioni (ammissibili) alternative, sulla base di uno o più criteri.

Essendo un problema decisionale, questo ha infinite soluzioni ammissibili.

Questo accade anche se la regione ammissibile è limitata, poiché contiene comunque un numero infinito di punti.

NB: ricorda che anche gli assi cartesiani sono vincoli. ottima k.

È necessario ora rappresentare le curve di livello, determinando una costante come in soluzione figura, che permette di individuare il fascio di rette parallele. o.

Siamo in un problema di massimo => la direzione di spostamento delle curve di livello è quella del gradiente, ossia la direzione di massima ascesa. di sostamento direzione.

Il vettore che da la direzione è v = (8,10).

Trovare il gradiente (o antigradiente) consiste sostanzialmente nell'individuare la direzione perpendicolare al vincolo.

Saper tradurre in linguaggio matematico un problema reale è spesso fondamentale per trovarne la soluzione (ottima) ed è un compito che un ingegnere sarà chiamato sicuramente ad affrontare!

Principi e formulazioni della programmazione lineare

Fondato principi e linear programmazione.

Questo (dell'esempio) è un caso particolare: è una sicuri modellizzazione con vincoli di uguaglianza.

Una modellizzazione con vincoli di disuguaglianza può sempre essere convertita in una modellizzazione con vincoli di uguaglianza.

Quando tutti i vincoli sono di uguaglianza si parla di formulazione standard:

• Vincoli di uguaglianza.
• Variabili maggiori o uguali a 0.

A loro volta le formulazioni standard possono essere definite di massimo o di minimo in base al risultato voluto.

Formulazione canonica. Con il termine si intende invece la formulazione con vincoli di disuguaglianza.

I due tipi di formulazione, canonica e standard, sono intercambiabili.

Siamo in presenza di un sistema.

Il sistema, in condizioni generali, ammetterà infinite soluzioni.

Il sistema sarà quindi soddisfatto da tantissime soluzioni distinte.

Funzione obiettivo: coefficiente di costo. Osservando la ciascuna variabile viene moltiplicata per il (o profitto).

Dal punto di vista dimensionale, la funzione obiettivo a cosa darà origine?? (Vettore, matrice, scalare??) => la funzione obiettivo è uno scalare. in.

Quello a fianco è un modo alternativo per rappresentare la funzione obiettivo tramite vettori.

Si hanno un vettore riga (c) che contiene tutti i coefficienti e un vettore colonna (x) che contiene tutte le variabili. 1x1.

Si ha che il prodotto commuta (per le regole del prodotto di righe per colonne) e si ottiene quindi una dimensione ossia uno scalare. A.

Considerando poi i vincoli: i coefficienti danno origine ad una matrice che ha tante righe quanti sono i vincoli, e tante colonne quanti sono i coefficienti.

Matrice tecnologica. Prende norme di in quanto fa riferimento ai vincoli del problema. A bxA.

La matrice viene moltiplicata per il vettore delle variabili. manm.

Nel passaggio da forma canonica a forma standard è necessario aggiungere delle variabili, per gestire le disuguaglianze.

In questo caso si ha una forma canonica, e standard di minimo.

Se fossimo in presenza di un problema di massimo avremmo dei vincoli di minore o uguale nella forma canonica.

• Forma canonica di minimo: vincoli maggiore o uguale.
• Forma canonica di massimo: vincoli di minore o uguale.

Variabili slack e surplus

Come si aggiungono variabili ad un vincolo??

Esempio: 3 E vincolo 2 151 2x.

Si introduce una nuova variabile che, come tutte le variabili deve essere maggiore o uguale di 0, che misura la differenza tra il primo e il secondo membro. 3.

La variabile introdotta prende nome di slack, ossia differenza.

152 3 X vincolo 370 con 1 2.

Se ora x3 fosse nulla: si avrebbe già un vincolo di uguaglianza.

Nel caso in cui x3 > 0: indicherebbe quando serve per arrivare a raggiungere il valore a secondo membro.

Nel caso in cui il vincolo è di maggiore o uguale si fa la stessa cosa. In questo caso però si ha che il primo membro è maggiore del secondo e quindi si dovrà togliere qualcosa dal primo membro per arrivare allo stesso valore del secondo.

32 2715 vincolo 1 43 vincolo 2 15X1 2 surplus.

In questo caso la nuova variabile prende il nome di m.

Il problema (che ora è in forma standard) ora avrà tante variabili in più quanti sono i vincoli: variabili in più.

NB: per l'algoritmo che impareremo a utilizzare (algoritmo del simplesso) sarà necessario passare sempre alla forma standard.

Sistemi lineari, rango e soluzioni

L Minore di ordine k = matrice quadrata estratta n-k dalla matrice di partenza sopprimendo righe ed Ax b m-k colonne.

m, Siamo in presenza di un sistema lineare, di rango come il numero di vincoli.

Rango r = il rango di una matrice è quando esister un minore di ordine con determinante diverso da 0 m linearmente indipendenti.

Questo coincide ad affermare che abbiamo vincoli tra loro. e tutti i minori di ordine superiore hanno determinante nullo.

Analogamente si può definire come il massimo.

Quante soluzioni ammette il sistema?? numero di righe (o colonne) linearmente.

Si ha (per Rouché-Capelli) che il sistema ammette soluzioni, nite o infinite. indipendenti della matrice.

m n.

Abbiamo una matrice ottenuta da una forma canonica trasformata in una forma standard è quindi si hanno più variabili x => ci si trova quindi nella situazione in cui si possono avere un numero di variabili maggiori rispetto al numero di vincoli. A.

• N = m: é possibile risolvere il sistema (se é invertibile) e si ottiene quindi la soluzione.
• N > m: si hanno n-m gradi di libertà del sistema e li si pone pari ad un valore costante, eliminandole dal sistema.

Le m-n variabili possono essere scelte liberamente fra quelle disponibili.

Il sistema principale equivalente. Si va a considera a quello dato che, per definizione ha le stesse soluzioni e lo stesso rango di quello di partenza. esponenzialmente grande.

Il valore costante è scelto arbitrariamente e il numero di soluzioni che si può ottenere é.

In questo caso si ottiene un numero di soluzioni pari a:

Se abbiamo n variabili quanti modi abbiamo di prenderne n-m??

Questo risulta essere uguale al coefficiente binomiale di n ed m.

Si tratta di un numero non limitato e che cresce esponenzialmente.

n > m.

Tipicamente noi ci trovere.