Es. di programmazione lineare

[Spike821]

ciao,
avrei questo problema:

Uno vostro collega decide di cercare un lavoro part-time e trova due offerte: la prima consiste in 9 ore di lavoro per un compenso totale di 270 Euro, la seconda consiste in 6 ore di lavoro per 225 Euro di retribuzione totale. Purtroppo lo studente dispone di sole 12 ore e deve decidere quanto tempo allocare a ciascun lavoro. Si assuma che il compenso cresca linearmente con il tempo dedicato a ciascun lavoro (ad esempio, se lo studente dedica 3 ore al secondo lavoro percepira’ 112.5 Euro). Quante ore deve dedicare lo studente al primo e al secondo lavoro per massimizzare il proprio guadagno?

ditemi se baglio.. la forma standard dovrebbe essere:

max: 30*x1 + 37,5*x2

soggetto a:

3<=x2<=6
6<=x1<=9
x1 + x2 = 12

giusto?

Se sì, nel passaggio alla forma slack come mi comporto con quelle due disuguaglianze?

Vi ringrazio

[hamming_burst]

Ciao,
il problema è piuttosto semplice, ti scrivo anche alcune considerazioni "formali".

"Spike82":
ditemi se baglio.. la forma standard dovrebbe essere:

la forma standard è una trasformazione di un problema di programmazione matematica sotto certe condizioni canoniche, per esempio da dare in pasto poi a qualche algoritmo o per semplice standardizzazione.
Perciò è più corretto parlare di formulazione del problema in un programma di ottimizzazione o di programmazione matematica (cioè un qualcosa di generale).

max: 30*x1 + 37,5*x2

ok, si massimizza visto che la funzione obbiettivo è il guadagno, e le varibili in gioco sono le ore/lavoro.

soggetto a:

3<=x2<=6
6<=x1<=9

perchè delimiti in questo modo le variabili?

x1 + x2 = 12

ok, visto che le ore di lavoro totali a disposizione sono un'uguaglianza e non un massimo a disposizione.

[Spike821]

"hamming_burst":Ciao,
[quote="Spike82"]
soggetto a:

3<=x2<=6
6<=x1<=9

perchè delimiti in questo modo le variabili?
[/quote]
perché x1 e x2 non dovrebbero essere chiusi in quegli intervalli affiché "x1+x2=12"?

E' sufficiente x1+x2=12 come vincolo?

Ti ringrazio per le risposte

[apatriarca]

Sì, le disuguaglianze sono corrette. Lo studente sembra infatti poter lavorare al massimo nove ore nel primo lavoro (e quindi lavorarne minimo tre nel secondo) e può lavorare al massimo sei ore nel secondo (e quindi minimo altre 6 nel primo). Nota comunque che, siccome vale la relazione \( x_1 + x_2 = 12 \), puoi usare una sola variabile ed un solo insieme di disuguaglianze. Per cui puoi ad esempio porre \(x_1 = t\) e \(x_2 = 12 - t\) e riscrivere il problema nella forma:
\[ \max_{6 \le t \le 9} \; 30\,t + 75/2\,(12 - t). \]
In questa forma si risolve abbastanza velocemente. Si tratta infatti di un segmento e i massimi e minimi di un segmento si trovato sempre agli estremi.

[hamming_burst]

"apatriarca":Sì, le disuguaglianze sono corrette. Lo studente sembra infatti poter lavorare al massimo nove ore nel primo lavoro (e quindi lavorarne minimo tre nel secondo) e può lavorare al massimo sei ore nel secondo (e quindi minimo altre 6 nel primo).

non ci avevo pensato ad un orario minimo, sono due vincoli inpliciti.
Diciamo che sono contenuti nelle sole disequazioni $x_1<=9$ e $x_2 <=6$ e se si tengono buoni i vincoli minimi di non-negatività (è un programma equivalente, come la riscrittura ottimizzata che hai fatto),

[Spike821]

vi ringrazio! Problema risolto