school math, equations and minimal steps problem

32 Views Asked by At

I have the following problem: $ X(20A + 88C) + Y(32B + 72C) + Z(40A + 40B) \ge 616A + 890B + 982C$

the second condition is that the sum of $ X + Y + Z $ should be as low as possible.

If there is more than 1 solution possible, i need only 1.

EDIT: X Y and Z are whole numbers!


what i tried so faar making three equations

$ 20X + 40Z = 616 $

$ 32Y + 40Z = 890 $

$ 88X + 72Y = 982 $


p.s. what sort of math is this ? i tagged it with linear-algebra.

1

There are 1 best solutions below

4
On BEST ANSWER

Your three equality constraints are infeasible; that is, they cannot simultaneously be satisfied. If you relax $=$ to $\ge$, the minimum $X+Y+Z$ turns out to be $28$, attained by $(X,Y,Z)=(3,10,15)$.

But depending on the values of $A$, $B$, and $C$, you might be able to satisfy your original inequality constraint with a smaller $X+Y+Z$.

Here's a proof of optimality, obtained via linear programming duality. Multiply the three inequality constraints by $17/1330$, $13/1064$, and $9/1064$, respectively, and add them up: $$\frac{17}{1330}(20X+40Z)+\frac{13}{1064}(32Y+40Z)+\frac{9}{1064}(88X+72Y)\\ \ge \frac{17}{1330}\cdot 616+\frac{13}{1064}\cdot 890+\frac{9}{1064}\cdot 982,$$ which simplifies to $X+Y+Z \ge 27+36/665$. Because the objective must be integer-valued, $28$ is a lower bound. The $(3,10,15)$ solution attains this bound and is hence optimal.