Witam,
Byłabym bardzo wdzięczna jeśli ktoś byłby tak miły i pomógł mi w rozwiązaniu poniższego problemu
Problem załadunku (problem plecakowy) przy relaksacji lagrange'a ma postać:
\(\displaystyle{ \sum_{j=1}^{n} p_{j} x_{j} + \lambda(c- \sum_{j=1}^{n} w_{j} x_{j}) \to max\\
przy \qquad ograniczeniach\\
x_{j} \in \left\{ 0,1\right\} , j=1,...,n}\)
Mam udowodnić, że rozwiązaniem optymalnym tego problemu jest
\(\displaystyle{ y_{j}=\begin{cases} 1 \qquad gdy \qquad \frac{p_{j}}{w_{j}}> \lambda \\ 0 \qquad gdy \qquad \frac{p_{j}}{w_{j}}<\lambda \end{cases}}\)
Zakładając, że
\(\displaystyle{ \frac{p_{1}}{w_{1}} \ge \frac{p_{2}}{w_{2}} \ge ... \ge \frac{p_{n}}{w_{n}} \\
p_{j}, w_{j} , c \in Z \\
p_{j}, w_{j} , c >0 \\
\sum_{j=1}^{n} w_{j}>c \\
\forall j \in {1,..,n}\qquad w_{j} \le c}\)
Wiadomo również, że \(\displaystyle{ \lambda}\) jest dowolną liczbą rzeczywistą nieujemną.
PROSZĘ POMÓŻCIE
Problem plecakowy, problem załadunku
-
kropka+
- Użytkownik
- Posty: 4386
- Rejestracja: 16 wrz 2010, o 14:54
- Płeć: Kobieta
- Lokalizacja: Łódź
- Podziękował: 1 raz
- Pomógł: 789 razy
Problem plecakowy, problem załadunku
W problemie plecakowym nie trzeba męczyć się z formalnym znajdowaniem ekstremów funkcji wielu zmiennych (opisany jest np. tutaj: ).
\(\displaystyle{ \sum_{j=1}^{n} p_{j} x_{j} + \lambda(c- \sum_{j=1}^{n} w_{j} x_{j})=\lambda c+\sum_{j=1}^{n} (p_{j}-\lambda w _{j}) x_{j}}\)
Dla \(\displaystyle{ p_{j}-\lambda w _{j}=0 \Leftrightarrow \frac{p _{j} }{w _{j} }=\lambda}\) obojętne czy \(\displaystyle{ x _{j}=0}\), czy \(\displaystyle{ x _{j}=1}\), bo wartość naszego wyrażenia nie zmieni się.
Dla \(\displaystyle{ p_{j}-\lambda w _{j}>0 \Leftrightarrow \frac{p _{j} }{w _{j} }>\lambda}\), gdy \(\displaystyle{ x _{j}=1}\) to wartość wyrażenia wzrośnie o \(\displaystyle{ p_{j}-\lambda w _{j}}\), a dla \(\displaystyle{ x _{j}=0}\) nie zmieni się, więc ponieważ chcemy zmaksymalizować nasze wyrażenie to wybieramy \(\displaystyle{ x _{j}=1}\)
Analogicznie dla \(\displaystyle{ p_{j}-\lambda w _{j}<0 \Leftrightarrow \frac{p _{j} }{w _{j} }<\lambda}\), gdy \(\displaystyle{ x _{j}=1}\) to wartość wyrażenia zmaleje, a dla \(\displaystyle{ x _{j}=0}\) pozostanie bez zmian, więc wybieramy \(\displaystyle{ x_{j}=0}\).
\(\displaystyle{ \sum_{j=1}^{n} p_{j} x_{j} + \lambda(c- \sum_{j=1}^{n} w_{j} x_{j})=\lambda c+\sum_{j=1}^{n} (p_{j}-\lambda w _{j}) x_{j}}\)
Dla \(\displaystyle{ p_{j}-\lambda w _{j}=0 \Leftrightarrow \frac{p _{j} }{w _{j} }=\lambda}\) obojętne czy \(\displaystyle{ x _{j}=0}\), czy \(\displaystyle{ x _{j}=1}\), bo wartość naszego wyrażenia nie zmieni się.
Dla \(\displaystyle{ p_{j}-\lambda w _{j}>0 \Leftrightarrow \frac{p _{j} }{w _{j} }>\lambda}\), gdy \(\displaystyle{ x _{j}=1}\) to wartość wyrażenia wzrośnie o \(\displaystyle{ p_{j}-\lambda w _{j}}\), a dla \(\displaystyle{ x _{j}=0}\) nie zmieni się, więc ponieważ chcemy zmaksymalizować nasze wyrażenie to wybieramy \(\displaystyle{ x _{j}=1}\)
Analogicznie dla \(\displaystyle{ p_{j}-\lambda w _{j}<0 \Leftrightarrow \frac{p _{j} }{w _{j} }<\lambda}\), gdy \(\displaystyle{ x _{j}=1}\) to wartość wyrażenia zmaleje, a dla \(\displaystyle{ x _{j}=0}\) pozostanie bez zmian, więc wybieramy \(\displaystyle{ x_{j}=0}\).