esercizio di programmazione lineare con parametro - help

[uranya]

per favore domani ho l'esame di Ricerca Operativa e ho trovato un tipo di esercizio di programmazione lineare che non capisco come impostare e risolvere. Questo è il testo:

Dato il seguente sistema di vincoli:

`-7x_1 + 8x_2 <= 6`
` 3x_1 + 6x_2 <=56`
`ul x>=0`

Determinare, se esiste, una funzione obiettivo che dia luogo ad una soluzione ottima unica.

Ho tentato di risolverlo imponendo che i coefficienti di costo ridotto siano strettamente minori di zero ponendo una funzione generica `z=k_1x_1+k_2x_2` con parametri k1, k2 ma alla fine mi trovo che sia k1 che k2 devono essere solo >0 il che contrasterebbe con il presupposto che la soluzione deve essere unica quindi andrebbero esclusi i valori per cui k1,k2 mi rendono la funzione obiettivo parallela ad uno dei vincoli (nel qual caso le soluzioni ottime sarebbero infinite).
Spero di essere stata chiara.
Vi prego datemi una mano!!
Grazie

[luca.barletta]

Il poligono ottenuto dalle condizioni offre 4 vertici che possono essere delle soluzioni uniche al problema, dipende ora quale vertice ti piace di più: imposti la funzione obiettivo in modo tale che il gradiente di questa sia compreso nella parte di piano formato dai gradienti delle 2 condizioni che si congiungono nel vertice prescelto.

[Marvin]

Cmq se stai studiando Ricerca Operativa ti consiglio di scaricarti Lindo.
Io quando ho dato l'esame l'ho usato per imparare a leggere l'analisi di sensitività e i vari report..
ti assicuro che si capisce mooolto meglio

MCM

[uranya]

scusa ma a me sembra che la regione ammissibile sia formata da un triangolo quindi da soli tre punti estremi, questo è il grafico che ho ottenuto: (abbiate pazienza per il grafico forse è un po pesante, ma così si vede bene)

[img=http://www.hostfiles.org/miniature/20060419074411_grafico.jpg]

in ogni caso credi che non sia necessaria una funzione obiettivo parametrica? Come faccio a descrivere analiticamente che la funzione scelta, abbia effettivamente un punto di ottimo unico se non verifico i coefficienti di costo ridotto? In effetti graficamente si potrebbe già intuire che un punto di ottimo unico si può avere in P1 con una funzione di MINIMO, ma il mio problema è analitico.

[luca.barletta]

Controlla il grafico, hai sbagliato a tracciare il primo vincolo.

[uranya]

si hai ragione avevo dimenticato un meno. Si in effetti sono 4 i punti estremi, ecco il grafico modificato

[img=http://www.hostfiles.org/miniature/20060419112117_grafico.jpg]

però amcora non ho capito come impostare la funzione, prendiamo ad esempio il punto P1, esso si trova all'intersezione dei due vincoli x1=0 e x2=0. Come sarà in questo caso la funzione? Puoi farmi un esempio pratico?

[uranya]

vediamo se ho capito:

scelgo il punto P3 che è dato dall'intersezione dei due vincoli.
Il gradiente del primo vincolo è `p' =(-7;8) `
Il gradiente del secondo vincolo è `p'' =(3;6)`

Questo vulo dire che data la funzione `z=k_1x_1+k_2x_2`

`-7<=K_1<=3 ` e `6<=K_2<=8 `

spero che riuscirari a darmi la conferma per stasera ...domani ho il compito.
Cmq grazie dell'attenzione.

[uranya]

il compito, credo sia andato proprio bene, per fortuna le funzioni obiettivo con parametro erano di facile soluzione, però sono rimasta con la curiosità per questo esercizio, se vorrai rispondermi ne sarò felice.
Grazie

Ciao

[luca.barletta]

E' molto semplice: i gradienti dei vincoli non sono altro che dei vettori in 2 dimensioni, li puoi anche tracciare sul grafico. Per avere l'ottimo su un determinato vertice basta che il gradiente della funzione obiettivo (anch'esso vettore di R^2) giaccia sulla porzione di piano compresa tra i vettori dei 2 vincoli presi in esame.

[luca.barletta]

Questo vulo dire che data la funzione `z=k_1x_1+k_2x_2`

`-7<=K_1<=3 ` e `6<=K_2<=8 `

No, controesempio: k1=4 e k2=9.