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... mx₁... x_n ∈ R (oppure Z in caso di PLI)

Esempio: Lindiet

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₂ ≥ 30.8 x₁ + 0.9 x₂ ≥ 10

x₁, x₂ ≥ 0

Ricorda:

• Mai moltiplicare le variabili
• 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| i ∀i = 1 ... mx₁ ... x_n ∈ R (Oppure Z in caso di PLI)

Esempio: Limdiet

Lim diet vuole commercializzare un prodotto dietetico che contenga le giuste miscele tra B₁ e B₂ (vitamine) che sia il costo minimo e che rispetti le direttive:

• S₁: 0,5 kg
• S₂: 0,35 kg
• B₁ 0,8 mg
• B₂ 0,6 mg
• B₃

Min 0,5 x₁ + 0,35 x₂

0,8 x₁ + 0,6 x₂ ≥ 2,8

x₁ + 0,6 x₂ ≥ 30,8 x₁ + 0,9 x₂ ≥ 10

x₁, x₂ ≥ 0

Ricorda:

• Mai moltiplicare le variabili
• 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₁]

Silicomputer

L’obiettivo è 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 11550 banchi di memoria. (1 NOTE, 2 PC)
2. 2500 minuti tempo di assemblaggio (4 NOTE, 3 PC)
3. NOTE: 750 $, PC: 1000 $

x_i, i=1,2

x_i numero di computer del tipo i da produrre.

Max 750x₁ + 1000x₂

x₁ + x₂ = 1000

100x₁ + 2x₂ = 15501004x₁ + 3x₂ = 2500100

Vincolo CPU

Vincolo memoria

Vincolo 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 w_i e un punteggio p_i. Scegliere quali e quanti di questi oggetti mettere nello zaino per ottenere punteggio max senza eccedere nel peso.

Esempio: 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

x_i: numero di confezione di tipo i da inserire 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₅ ≥