-3

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.

Trips
  • 3

1 Answers1

0

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.

RobPratt
  • 45,619
  • First of all thanks for bothering with that question! I see your concern about A B and C. How can i describe that...A B and C are not numbers, lets say A stands for Apples, B for Bananas and C for Carrots. That was bad on my behalf, i thought thats called constants.

    I will give you the Checkmark if noone finds a lower solution. (i can´t verify it, otherwise i wouldn´t have asked in first place)

    Anyway, is it too much to ask for the solution steps ? So that i could understand and verify that this is the correct answer.

     – Trips Mar 20 '20 at 15:09
  • I added a short proof of optimality. – RobPratt Mar 20 '20 at 15:48
  • Lets say i understand how you get to the 28. I don´t quite get how you came across those big numbers ? (1330 and 1064) And how do you know that the distribution has to be 3,10,15? (but that was not part of the original question). So there goes your checkmark! – Trips Mar 20 '20 at 16:50
  • To find the optimal integer solution $(3,10,15)$, I used an integer linear programming solver. To find the magic dual multipliers with the big denominators, I used a linear programming solver. – RobPratt Mar 20 '20 at 17:00