Problemi del corso

Scegli un problema, segui l'esempio illustrato e passa al prossimo.

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 5 di 36

LINEAR PROGRAMMING

Dato un sistema di disequazioni lineari, con soluzioni reali (non per forza intere): esiste una soluzione?

PP-completo

Un esempio, passo dopo passo

1 / 3

Traduci i vincoli. I vincoli sono x ≥ 1, y ≥ 0 e x + y ≤ 3, con x e y reali. Nel disegno la retta verticale è x = 1, quella obliqua da (0, 3) a (3, 0) è x + y = 3, e il bordo di y ≥ 0 è l'asse x. Ogni vincolo ammette i punti da un lato della sua retta, retta compresa. — 1. Traduci i vincoli
I vincoli sono $x \ge 1$ , $y \ge 0$ e $x + y \le 3$ , con $x$ e $y$ reali. Nel disegno la retta verticale è $x = 1$ , quella obliqua da $(0, 3)$ a $(3, 0)$ è $x + y = 3$ , e il bordo di $y \ge 0$ è l'asse $x$ . Ogni vincolo ammette i punti da un lato della sua retta, retta compresa.

Scorri l'immagine o usa Avanti.

Si cercano numeri che rispettino tutti i vincoli insieme. Con $x \ge 1$ , $y \ge 0$ e $x + y \le 3$ , la coppia $x = 2$ , $y = 1$ funziona, e lo si verifica una disequazione alla volta.

Ogni vincolo delimita una regione e una soluzione è un punto nella loro intersezione. Sono ammessi anche valori frazionari: $x = 1{,}5$ e $y = 0{,}5$ è un'altra soluzione. In INTEGER PROGRAMMING, invece, le variabili devono essere intere.

Con coefficienti razionali codificati in binario, si decide in tempo polinomiale nella lunghezza dell'input se esiste una soluzione. Il metodo dell'ellissoide, per esempio, garantisce questo limite; il simplesso nel caso peggiore può richiedere tempo esponenziale.

Complemento e collegamenti

Nessun complemento associato.

MAX FLOW è un caso di programmazione lineare
soluzioni reali: in P; soluzioni intere: NP-completo

INTEGER PROGRAMMING è NP-completo

Domande e trappole d'esame

Non confonderlo con INTEGER PROGRAMMING: chiedendo soluzioni intere diventa NP-completo.

Problemi del corso

1. Traduci i vincoli

2. Interseca le regioni

3. Scegli e verifica