Appunti Ricerca Operativa

PROGRAMMAZIONE LINEARE

min _{j = 1}ⁿ∑ c_jx_j (oppure max _{j = 1}ⁿ∑ c_jx_j)

_{ij = 1}^m∑ a_ijx_j = {≥ b_i{≤ b_i Vedi... i = 1... m

x₁... x_n ∈ R (oppure Z in caso di PLI)

ESEMPIO: LINDET

Lindiet vuole commercializzare un prodotto dietetico che contenga la giusta miscela tra B₁ e S₂ (vitamine) che sia il costo minimo e che rispetti le direttive:

• S₁, 0.5€/h, 0.8 mg/h B₁ imp, 0.8 mg/h B₂, 0.9 mg/h B₃
• S₂, 0.35€/h, 0.6€/h B₁, 0.6€/h B₂, 0.9€/h B₃
• B₁ ≥ 2.8 mg, B₂ ≥ imp, B₃ ≥ 0.10 mg

X: kg di sostanza i-esima da comprare per la miscela

min 0.5 x₁ + 0.35 x₂

0.8 x₁ + 0.6 x₂ ≥ 2.8

X₁ + 0.6 x₂ ≥ 3

0.8 x₁ + 0.9 x₂ ≥ 10

x₁, x₂ ≥ 0

RICORDA:

1. Mai moltiplicare le variabili

2. Le variabili sono incognite e non dati del testo

PROGRAMMAZIONE LINEARE

min _i=1ⁿ c_j x_j (oppure max _j=1ⁿ c_j)Σ a_ij x_j = | > b_i| < b_i ∀i = 1 ... mx₁ ... x_n ∈ R (Oppure Z in caso di PLI)

ESEMPIO: LIMDIET

Lim diet vuole commercializzare un prodotto dieteticoche contenga le giuste miscele tra B₁ e B₂ (vitamine)che sia il costo minimo e che rispetti le direttive:S₁: 0,5 kgS₂: 0,35 kgB₁0,8 mgB₂0,6 mgB₃min 0,5 x₁ + 0,35 x₂0,8 x₁ + 0,6 x₂ ≥ 2,8x₁ + 0,6 x₂ ≥ 30,8 x₁ + 0,9 x₂ ≥ 10x₁, x₂ ≥ 0

RICORDA: 1) Mai moltiplicare le variabili2) Le variabili sono incognite e non dati del testo

RAPPRESENTAZIONE GRAFICA

1. RIPORTO I VINCOLI SULLA GRIGLIA
   • 0,8x₁ + 0,6x₂ ≥ 2,8
   • x₁ + 0,6x₂ ≥ 9
   • 0,8x₁ + 0,8x₂ ≥ 10

La parte segnata (///) è la regione ammissibile

2. TRACCIO LE RETTE ISOPROFITTO

0,95x₁ + 0,35x₂ = k

Nota che la soluzione ottima è data da x₁ = 5 e x = 6,6 in corrispondenza della soluzione della funzione obiettivo vale 7,83 [PUNTO DI INTERSEZIONE TRA I VINCOLI TROVO x₂ E x₁]

SILICOMPUTERS

L’obbiettivo è stabilire quanti notebook e pc produrre al fine di massimizzare il profitto.Preferisce produrre lotti da 100 elementi.

1. Si hanno 1000 CPU, ogni computer ha bisogno di 1
2. 1550 banchi di memoria. (1 NOTE, 2 PC)
3. 2500 minuti tempo di assemblaggio (4 NOTE, 3 PC)
4. NOTE: 750 $, PC: 1000 $

x_i, i=1,2x_i numero di computer del tipo i da produrre.

max 750x₁ + 1000x₂

• x₁ + x₂ = 1000100
• x₁ + 2x₂ = 1550100
• 4x₁ + 3x₂ = 2500100

Vincolo CPUVincolo memoriaVincolo tempo

x₁, x₂ ∈ N

Importante la scelta delle variabili intere, il numero di pc o notebook non può essere frazionario!!!

PROBLEMA DELLO ZAINO

Dato uno zaino che possa portare un peso massimo W.

Dati N oggetti di tipo i, ognuno caratterizzato da un

peso wi e un punteggio pi. Scegliere quali e quanti

di questi oggetti mettere nello zaino per ottenere punteggio

max senza eccedere nel peso.

ES.: MASSIMIZZA IL PUNTEGGIO

Capienza zaino 10kg, oggetti:

• CIOCCOLATA (500g a confezione) 10 punti min 2
• SUCCHI (1ℓ) 30pt min 2
• LATINE (0,33ℓ) 6 min 6
• PANSINI (100g l'uno) 3 min 10
• ACQUA (1ℓ) 20 min 1
• BISCOTTI (500g) 8 min 2

xi: numero di confezione di tipo i da inserire n

con i: 1...6

max 10x₁ + 30x₂ + 6x₃ + 3x₄ + 20x₅ + 8x₆

0,5x₁ + x₂ + ¹⁄₃x₃ + ¹⁄₁₀x₄ + x₅ + 0,5x₆ ≤ 10 _{vincolo capienza}

• x₁ ≥ 2
• x₂ ≥ 2
• x₃ ≥ 6
• x₄ ≥ 10
• x₅ ≥