Aiuto esercizio di PLI

[Desirio]

$ \leq j_{h} $Salve a tutti ho il seguente problema di PLI

$ min 6x_{1} + x_{2} + 5x_{3} + 2x_{4}$ con $4x_{1} + 2x_{2} + 2x_{3} + 8x_{4} \geq 10 $ e $x_{i} \in {0,1}$ per $i \in {1,2,3,4}$.

Dovrei applicare il metodo branch and bound.
Quindi inizio inizializzando la lista dei problemi aperti con il problema dato $L = {P0}, i = 0, x' = ?, UB = ?$.

Visto che $L$ è non vuoto seleziono $P0$ e lo risolvo con il metodo del rilassamento lineare.
Quindi
$ min 6x_{1} + x_{2} + 5x_{3} + 2x_{4}$ con $4x_{1} + 2x_{2} + 2x_{3} + 8x_{4} \geq 0 $ e $0 \leq x_{i} \leq 1$ per $i \in {1,2,3,4}$.

1) Ordino le variabili secondo la relazione del i rapporto costo/ingombro, essendo un problema di minimizzazione secondo la relazione del $\leq$. Quindi ${4, 2,1,3} : \frac{2}{8} \leq \frac{1}{2} \leq \frac{6}{4} \leq \frac{5}{2}$.
2) Devo determinare l'indice $h$ tale che $\sum_{k = 1}^{h} a_{jh} > b = 10$ e quindi abbiamo $j_{h} = 1, h = 3$.
3) Determino l'ottimo del rilassamento lineare $x^{*} = (\frac{1}{4}(10-10) 0 , 0, 0 ) = (0 , 0, 0, 0)$ (dovrei porre a zero tutte le componenti dell'ottimo il cui indice è maggiore di jh = 1 ... e quella in cui l'indice è $j_{h}$ dovrebbe essere $1/a_{j_{h}} (b - \sum_{k = 1}^{h-1} a_{j_{k}}$ a cui corrisponde un ottimo che è un LB pari a $LB = 0$.
Da qui il diagramma mi dice che posso calcolare la soluzione ammissibile $x'$ andando a porre le componenti di tale soluzione pari a $1$ se l'indice è $\leq j_{h}$. Altrimenti se è maggiore le comonenti assumono il valore zero. Quindi dovrebbe essere $x' = (1, 0, 0, 0)$: che ovviamente non è una soluzione ammissibile! Quindi non capisco cosa sto sbagliando nell'applicazione di tale procedimento ...


Potreste spiegarmi un metodo per risolvere questo problema o meglio dove sto sbagliando?

[Quinzio]

$ \leq j_{h} $Salve a tutti ho il seguente problema di PLI

$ min 6x_{1} + x_{2} + 5x_{3} + 2x_{4}$ con $4x_{1} + 2x_{2} + 2x_{3} + 8x_{4} \geq 10 $ e $x_{i} \in {0,1}$ per $i \in {1,2,3,4}$.

Dovrei applicare il metodo branch and bound.
Quindi inizio inizializzando la lista dei problemi aperti con il problema dato $L = {P0}, i = 0, x' = ?, UB = ?$.

Visto che $L$ è non vuoto seleziono $P0$ e lo risolvo con il metodo del rilassamento lineare.
Quindi
$ min 6x_{1} + x_{2} + 5x_{3} + 2x_{4}$ con $4x_{1} + 2x_{2} + 2x_{3} + 8x_{4} \geq 0 $ e $0 \leq x_{i} \leq 1$ per $i \in {1,2,3,4}$.

1) Ordino le variabili secondo la relazione del i rapporto costo/ingombro, essendo un problema di minimizzazione secondo la relazione del $\leq$. Quindi ${4, 2,1,3} : \frac{2}{8} \leq \frac{1}{2} \leq \frac{6}{4} \leq \frac{5}{2}$.
2) Devo determinare l'indice $h$ tale che $\sum_{k = 1}^{h} a_{jh} > b = 10$ e quindi abbiamo $j_{h} = 1, h = 3$.

Ci va messo il $\ge$, quindi
2) Devo determinare l'indice $h$ tale che $\sum_{k = 1}^{h} a_{jh} \ge b = 10$ e quindi abbiamo $j_{h} = 2, h = 2$.

3) Determino l'ottimo del rilassamento lineare $x^{*} = (\frac{1}{4}(10-10) 0 , 0, 0 ) = (0 , 0, 0, 0)$ (dovrei porre a zero tutte le componenti dell'ottimo il cui indice è maggiore di jh = 1

Non dovrebbe essere:
dovrei porre a zero tutte le componenti dell'ottimo il cui indice è maggiore di $h = 2$ ?
Ovvero le $x$ con indice $1$ e $3$.
La soluzione finale dovrebbe essere $x_(1..4) = (0, 1, 0, 1) $.

... e quella in cui l'indice è $j_{h}$ dovrebbe essere $1/a_{j_{h}} (b - \sum_{k = 1}^{h-1} a_{j_{k}}$ a cui corrisponde un ottimo che è un LB pari a $LB = 0$.
Da qui il diagramma mi dice che posso calcolare la soluzione ammissibile $x'$ andando a porre le componenti di tale soluzione pari a $1$ se l'indice è $\leq j_{h}$. Altrimenti se è maggiore le comonenti assumono il valore zero. Quindi dovrebbe essere $x' = (1, 0, 0, 0)$: che ovviamente non è una soluzione ammissibile! Quindi non capisco cosa sto sbagliando nell'applicazione di tale procedimento ...


Potreste spiegarmi un metodo per risolvere questo problema o meglio dove sto sbagliando?