4736387703

(a) — 3x\ — X2 ► min, przy warunkach

I2xi + 3x₂ + x₃ = 6,

2x\ — 3x2 + Xą = 3,

Xi,X2,Xs,Xą > O,

Xi,X2,Xs,Xą G Z,

(b) —X\ — X2 —* min, przy warunkach

2x\ -\- 3x2 ~\~ x₃ = 10,

X\ — X2 + Xą = 3,

<    -X\ + 2X2 +^5=5,

^1,^2, 3^3, ^4,^5 > O,

Xi,X2,Xz,X±,X*> G Z,

(c) 5xi — X2 —> min, przy warunkach

Ixi — x₂ + xs = 5,

X\ + 3X2 + #4 = 8, X\,X2,X3,X± > O, X\, X2i X$_: Xą G Z,

(d) Xi 4- 2^2 —► min, przy warunkach

—2xi + 4x2 + X3 = 15,

—2xi — 2x2 + Xą = —5,

< Xi — X2 + X5 = 3,

Xi, X2, X3, X4, X5 > O,

Xi,X2,X3,X₄,X₅ G Z.

6. Strategie zachłanne

6.1. Przykłady

1. Chcemy kupić 23,5 uncji złota. Mamy do dyspozycji następujące sztab-ki: 10 uncji, 5 uncji, 2 uncje, 1 uncja oraz 0,5 uncji. Zakładamy, że sztabek jest nieograniczona liczba. Jakie i ile sztabek musimy kupić, aby nabyć ich jak najmniejszą liczbę?

Pokażemy zastosowanie strategii zachłannej. Intuicyjnie najbardziej optymalną metodą będzie kupowanie w pierwszej kolejności sztabek o największej gramaturze. W naszej sytuacji powinniśmy nabyć 2 sztab-ki 10 uncjowe. Wtedy będziemy musieli jeszcze kupić 3,5 uncji złota.

6