Salve a tutti. Avrei dei dubbi su un problema di Knapsack Intero, quindi di programmazione lineare intera. Il problema è il seguente :
max\(\displaystyle 50x1 + 18x2 + 3x3 +11x4 \)
s.v. \(\displaystyle 24x1+9x2+2x3+6x4 \leqslant 70\)
Con \(\displaystyle xj \geqslant 0 \)
Vi spiego il procedimento che uso io. Ho ordinato in ordine decrescente le variabili in base ai rapporti cj/aj.
quindi ho :
max\(\displaystyle 50y1 + 18y2 + 11y3 +3y4 \)
s.v. \(\displaystyle 24y1+9y2+6y3+2y4+y5 =70\)
Poi parto con il primo probelma Po, la cui soluzione è \(\displaystyle (70/24, 0, 0, 0, 0 ,0)^T \)
Non essendo soluzione intera y1 diventa variabile di branching. Ho quindi il problema P1 con \(\displaystyle y1 \leqslant 2 \) e il problema P2 con \(\displaystyle y1\geqslant 3 \)
Fin qui nessun problema. Verifico che P1 non è ancora soluzione ottima e quindi arrivo al problema P4 ottenuto usando y2 come variabile di Branching e in particolare \(\displaystyle y2 \geqslant3 \). (Si parta da Po che si ramifica in P1 e P2. Poi da P1 si ramifica in P3 e P4)
Ora come procedo? Ho imposto che \(\displaystyle y2-s2=3 \) da cui, ovviamente, \(\displaystyle y2=3+s2 \) . Poi ho sostituito questo valore nella funzione obiettivo e nel vincolo ottenendo :
max\(\displaystyle 50y1 + 54+ 18s2 + 11y3 +3y4 \)
s.v. \(\displaystyle 24y1+9s2+6y3+2y4+y5 =43\)
Come faccio a ricavarmi gli altri valori per poi arrivare alla soluzione?
Al valore di y1 devo sostituire 2 poichè il P4 deriva dal problema P1 che aveva come vincolo \(\displaystyle y1\leqslant 2\) ?
O devo calcolare il minimo fra certi valori???
Vi ringrazio anticipatamente. Ovviamente per ulteriori chiarimenti basta chiedere.
Ciao Ciao Francesco!