Fondamenti di Ricerca Operativa

Fondamenti di ricerca operativa

Marco Scardovelli / marcoscardovelli@cmail.it

Ricevimento: Lunedì 15-17

Libro: Fond. di Ricerca Operativa 1° Edition

1 modulo didattico integrativo (moodle)

Esame:

• 2 parziale
  • Esame scritto (3 teorie + 2 esercizi)
  • Esame orale

Date competizioni:

• 1°: Giovedì 7 novembre (5 lunedì Prec. Bocca)
• 2°: Giovedì 19 dicembre (eventuale profpello)

2 teorie + 1 esercizio

Voti in 15, per passare somma ≥ 18

1° appello 16 Gennaio partita di calcetto 18:00

Ricerca Operativa (Ottimizzazione)

Operations Research

Nasce negli anni '50 in ambito logistico.

Si occupa di risolvere con metodi quantitativi problemi decisionali.

Utente → Problema reale → Modello matematico → Algoritmo numerico di soluzione → Soluzione

Esempio 1

• Dati del Problema
• Variabili di Decisione

Funzione obiettivo (da massimizzare o min.)

Vincoli sulle variabili di decisioni

Un'azienda ha N centri di produzione di un bene e ha M centri di smistamento (vendita). Indicheremo con C_ij il costo di trasporto di un'unità dal centro di produzione i al punto vendita j. Indico con C_i la capacità produttiva settimanale del centro di prod. i. Indichiamo con D_j la domanda settimanale del punto vendita j.

Vogliamo determinare la quantità del bene da inviare dal centro i a al centro j in modo da minimizzare il costo complessivo di trasporto.

Dati

C_ij D_i D_j

Variabili di Decisione

X_ij = Quantità da trasportare dal centro i al j

• i = 1, 2, ..., N
• j = 1, 2, ..., M

• UN PROBLEMA DI OTTIMIZZAZIONE PUO NON AMMETTERE SOLUZIONE OTTIMA SE:
  1. X = ∅ (caso piu frequente per troppi vincoli, alcuni dei quali possono togliere vincoli)
  2. X ≠ ∅ e f limitata inferiormente su X
  3. X ≠ ∅ e f limitata inf. su X e non posso affermare che il problema ammette soluzione (es. inf f(x) x ∈ X

• CONDIZIONE SUFFICIENTE DI ESISTENZA DELLA SOLUZIONE
  • X ≠ ∅ e X compatto e f continua su X (Chiuso e limitato)
  ⇒ ∃ x* ∈ X (f max e f min) (TEOREMA DI WEIERSTRASS)

Esempio f continua che non e compattato. Non ha minima.

Stabilire se l'insieme ammissibile X e vuoto oppure no non e in generale semplice.

Stabilire se un punto X e ammissibile oppure no è immediato esempio:

min x₁ x₂ - 2x₁ x₂ x₂ + x₂ ≤ 1 x₁ + x₂ ≤ 10 x_i ≥ 0

x = ¹⁄₂, ¹⁄₂ ∈ X

• Una classe importante di problemi di ottimizzazione e la classe di PROGRAMMAZIONE LINEARE (PL) in cui
  1. l'FUNZIONE OBIETTIVO E LINEARE e l'INSIEME AMMISSIBILE definito da VINCOLI LINEARI di uguaglianza e/o disuguaglianza.

DEF f è LINEARE se: f(ax+y) = {ax+g(y) αx+g(y) t ∈ ^Rn α∈^R, x∈^Rn, y∈^R, x∈^Rn

PROP f è LINEARE ↔ g(x) = c^Tx prodotto scalare a * b = Σⁿ_{i = 1} a_i b_i t&a

Soluzione di Base

_X0 ⇒ ∀ Soluzione di Base Ammissibile (SBA)

x = ^{( X_B = A_BB b )}

_X ^h X_N ⇒ Soluzione di Base Non Ammissibile

Se ̅X ̅ è una Soluzione di Base ⇒ ̅X ̅ ha almeno n-m componenti nulle (non è detto il contrario)

Se ̅X ̅ ha componenti nulle ≥ n-m ̅X ̅ ⇒ Soluzione degenere

Esempio

• min 2X₁ - 2X₂ + 3X₃ - X₄
• X₁ + 2X₂ - X₃ - X₄ = 3
• - X₁ - X₁ + 2X₃ - 2X₄ = 1
• X₁/X₂/X₃/X₄ ≥ 0

Prendo come matrice di base quella composta dalle colonne 1, 3 B = {1, 3} N = {2, 4}

A_B = ^{( 1 2 ) ( -1 1 )}

A_N = ^{( 2 ) ( -1 )}

A_B^-1 b = ^{( 2 1 ) ( 1 1 )}

A_B^-1 = ^{( 2 1 ) (1) (3)}

1. b = ( 4 )

det A_B = 2 - 1 = 1 ≠ 0 (mat A_B non singolare) ⇒ Invertibile

^{X = ( 7 ) ( 0 ) ( 4 ) ( 0 )}

Senso 0 perché sono le X_N(dalle regole 2 e 4)

SBA

Dato un PLI in Forma Standard

• min C^T x
• Ax = b
• X ≥ 0

1. X_B
2. ⇒ ∀ perché Rango (A) = m (∆ < n)
3. Non è detto che ∀ SBA X potrebbe essere = 0 o non > 0 (casi rari vuoti)
4. _{( n )} ^{( m )} = n! / m![ (n-m) ]!
5. = N^O Max di SBA

* escluse le sol. indebolibili

esempio E = { x₁, x₂ ∈ Rⁿ }

Il sottospazio minimo che contiene sE 2 punti è un retta.

Se considerato come particelle il segmento dim(E) = 1 quindi il sottospazio minimo che lo contiene è sempre una retta.

Def IPERPIANO M = Rⁿ

H = { x ∈ Rⁿ : a^T x = b }

INTERSEZIONE

tra 2

esempio x₁ ∈ E ⟺ x₁ + x₂ = 3 a^T = \[ 1 1 \] b = 1

SEMISPAZI

Def POLIEDRO

Un poliedro è un insieme ottenuto come intersezione di un numero finito di semispazi.

esempio: H = { x ∈ Rⁿ : a^T x ≤ b } = { x ∈ Rⁿ : a^T x ≥ b } intersezione di semispazi

x₁ + x₂ ≤ 3, x₃ ≤ 1

semispazio intersezione di semispazi

x₁ + x₂ - 3x₃ ≤ 1 semispazio

-2x₁ + x₂ + 3x₃ ≤ 1 semispazio

x₁ + x₂ ≤ 1 - no semispazio no poliedro

A x ≤ b poliedro

x₁ ≤ 0

Poliedro si descritti da equazioni e disequazioni lineari (PL)

Def POLITOP

P. è un poliedro limitato (poligoni R², poliedro R³)

es.

E ⊆ { x ∈ Rⁿ : x ≻≻0} non è un politopo perché semipiano

S = { x ∈ R² : x₁ + x₂ ≤ 1, x₁ ≥ 0, x₂ ≥ 0 } P. = ∅ = poliedro

x₁

Def DISUGUAGLIANZA VALIDA

per un poliedro P

{ x ∈ Rⁿ : α^T x ≤ β } ⇔ ∀x ∈ P → α^T x ≤ β

esempio: P = { x ∈ R² : x₁ + x₂ ≤ 1, x, x₁ ≥ 0 }

x₂ ≤ 2 è una disuguaglianza valida per P? NO

x₂ ≤ 2 DISUG. VALIDA (R⁺² il poliedro)

x₂ ≤ 1

x₂ ≥ 1

alt. NON VALIDA

Se prendo k∈K come disug. essa sarà VALIDA per P.

di IPERPIANO associato a x₂ ≤ 1

l’intersezione P inter il punto (x₁,4) non è in { IPERPIANO in SUPPORTO