Paniere con risposte aperte - Ricerca operativa (2021/2022)

Si definiscono i vincoli che legano tra loro le grandezze note con le variabili del problema. Esprimiamo il vincolo che ogni giorno c'è un fabbisogno minimo pi da assumere per ciascun fattore nutritivo i appartenente ad N.

Le unità di ciascun fattore nutritivo i appartenente ad N acquisite tramite la dieta (incognita) dipendono dalle unità xj degli alimenti j appartenente ad A che contengono il fattore i, ciascuno secondo il coefficiente qij.

Ciascun vincolo i è una disequazione lineare nelle incognite xj a coefficienti qij e termini noti pi.

Detta Q = [qij] con i appartenente ad N e j appartenente ad A ed infine Q appartenente ad R^(|N| x |A|) la matrice dei coefficienti e p il vettore dei termini noti pi possiamo scrivere i vincoli nella forma matriciale:

Qx >= p

La formulazione matematica del problema della dieta è quindi la formulazione del problema di Programmazione Lineare in forma generale:

min c^T x

Qx >= p

x >= 0

|A|

11. Dimostrare che un semispazio chiuso è un insieme convesso

Teorema: Un semispazio chiuso è un insieme convesso

Dimostrazione

Sia a appartenente a Rⁿ un vettore di Rⁿ e b appartenente a R un numero reale.

Consideriamo il semispazio chiuso

S_maggiore = { x appartenente Rⁿ : a^T x >= b }

(dimostrazione analoga per S_minore)

Vogliamo dimostrare che per ogni coppia di vettori u,v appartenenti a S_maggiore e ogni valore g appartenente a [0,1]

gu + (1 - g) v appartiene a S_maggiore

Dimostrazione

u,v appartengono a S_maggiore, ciò implica che

a^T u >= b e a^T v >= b

Si noti che per ogni g appartenente [0,1]

g a^T u >= b e g a^T v >= b

Sia w = gu + (1-g)v.

Dal momento che u,v appartengono a S_maggiore per ogni g appartenente a [0,1], possiamo scrivere

a^T w = a^T (gu + (1-g)v) = g a^Tu + (1-g) a^Tv

>= gb + (1-g)b = b

Quindi w = gu + (1-g)v appartiene ad Smaggiore e possiamo concludere che Smaggiore è un insieme convesso.

12. Si considerino 6 alimenti: frutta, verdura, carne, pesce, pane e pasta.

Ciascun etto di alimento contiene i quantitativi di grassi (in grammi), calorie (in cal) e proteine (in grammi) riportati nella tabella. Tenendo conto che il fabbisogno giornaliero minimo è di 75 grammi di grassi, 2200 calorie e 50 grammi di proteine, e considerati i costi per etto di alimento riportati nella seguente tabella, formulare il problema della dieta a costo minimo

min c = 0.5 x1 + 0.75 x2 + 3 x3 + 3.8 x4 + 0.3 x5 + 0.5 x6

4 x1 + 1 x2 + 18 x3 + 20 x4 + 8 x5 + 9 x6 >= 75

27 x1 + 12 x2 + 210 x3 + 310 x4 + 90 x5 + 180 x6 >= 2200

0.4 x1 + 0.01 x2 + 12 x3 + 14 x4 + 1 x5 + 2 x6 >= 50

con xi >= 0 ed i = 1, 2, 3, 4, 5, 6

13. Si considerino 5 alimenti: frutta, verdura, carne, pesce e pasta. Ciascun etto di alimento contiene i quantitativi di grassi (in grammi), calorie (in

cal)e proteine (in grammi) riportati nella tabella. Tenendo conto che ilfabbisogno giornaliero minimo è di 75 grammi di grassi, 2200 calorie e 50grami di proteine, e considerati i costi per etto di alimento riportatinella tabella sopra, formulare il problema della dieta a costo minimomin c = 0.25 x1 + 0.2 x2 + 2.5 x3 + 2.8 x4 + 0.3 x52x1 + 0.5 x2 + 6 x3 + 12 x4 + 9 x5 >= 7520 x1 + 18 x2 + 190 x3 + 270 x4 +245 x5 >= 22000.4 x1 + 0.1 x2 + 11 x3 + 18 x4 + 19 x5 >= 50con xi >= 0 ed i = 1, 2, 3, 4, 516. Dimostrare che un vettore è una direzione del poliedro P={x∈Rn: Ax≥b}se e solo se è soluzione del sistema omogeneo Ax ≥ 0TeoremaUn vettore y appartenente ad R^n è una direzione del poliedro in R^nP = { x appartenente ad R^n : Ax >= b }se e solo se è una soluzione del sistema omogeneoAx >= 0mDimostrazioneSe y soddisfa il sistema omogeneo Ax >= 0 allora per ogni x appartenente a P e perogni g >= 0 il vettorez = x +

gyè tale cheAz = A (x + gy) = Ax + g Ay >= b + 0m = bQuindi z appartiene a P e quindi y è una direzione di P.Se y è una direzione di P allora la semiretta di origine x e direzione y appartiene a P e{ z appartenente R^n : z = x +gy, g >= 0 } è contenuto in P.QuindiAz = A (x +gy) = Ax + gAy >= bSupponiamo per assurdo che una componente del vettore Ay sia negativa,i.e. (Ay)i < 0.Allora, per g sufficientemente grande, la quantità g(Ay)i sarebbe tale da violare ilvincoloa^Ti x + g(Ay)i >= bOnde la tesi

17. Dare la definizione di direzione di un poliedroUn vettore y appartenente ad R^n si dice direzione di un poliedro P sottoinsieme diR^n se e solo se per ogni vettore x appartenente a P l’insieme{ z appartenente ad R^n : z = x + gy, g>= 0 }è contenuto nel poliedro P{ z appartenente ad R^n : z = x + gy, g>= 0 } contenuto in PL’insieme { z appartenente ad R^n : z = x + gy, g>= 0 } è detto semiretta di originex

18. Dare la definizione di poliedro e dimostrare che è un insieme convesso

Considerato un problema di Programmazione Lineare in forma generale

min c^T x s.t. Ax >= b con x >= 0

la regione ammissibile

P = { x appartiene ad R^n : Ax >= b, x >= 0n }

Rappresenta geometricamente l'intersezione di m semispazi chiusi di R^n.

P si definisce poliedro in quanto intersezione di un numero finito (m) di semispazi chiusi

Intersecato = aP = S1 ∩ S2 ∩ ... ∩ Sm ∩ { x >= 0n }

Ciascuno degli m semispazi chiusi 'Si' è un insieme convesso. Pertanto un poliedro P è un insieme convesso in quanto intersezione di insiemi convessi.

19. Dimostrare che un iperpiano è un insieme convesso

Teorema: Un iperpiano è un insieme convesso

Dimostrazione

Sia a appartenente ad R^n un vettore di R^n e b appartenente ad R un numero reale, consideriamo l'iperpiano

H = {x appartenente R^n : a^T x = b }

L'iperpiano H è l'intersezione di

due semispazi chiusi definiti dalle disequazioni:

a^T x >= b

a^T x <= b

Dal momento che l'intersezione di un numero finito di insiemi convessi è un insieme convesso, è convesso.

20. Descrivere il problema del trasporto e formularlo matematicamente

Siano dati un insieme di punti di depositi (punti di produzione o raccolta) e un insieme di magazzini di destinazione (punti di vendita o servizio). Per ogni deposito è nota la quantità di merce disponibile, mentre per ogni magazzino è nota la domanda di merce.

Dati i costi del trasporto della merce da ogni deposito a ogni magazzino, occorre pianificare la distribuzione di merce a costo minimo che garantisca il soddisfacimento della domanda di ciascun magazzino.

Determiniamo la formulazione matematica del problema del trasporto

Introduciamo innanzi tutti gli insiemi utili alla formulazione matematica del problema, vale a dire

- l'insieme degli n depositi

- l'insieme degli m magazzini

Definiamo quindi

base ammissibilex = (B^-1 b, 0 n-m)è degenere allora una o più componenti del vettorexB = B^-1 b sono nulle.

In tal caso, diverse basi possono produrre la stessa soluzione di base ammissibile.

Se x appartenente a P è una soluzione di base ammissibile non degenere, allora|S(x)| = m e esattamente r = n-m vincoli di non negativitàx >= 0n sono soddisfatti all’uguaglianza.

Se x appartenente a P è una soluzione di base ammissibile degenere, allora|S(x)| < m e più di n-m vincoli di non negatività x >= 0 sono soddisfattiall’uguaglianza.

Quindi una sol