Find optimal integer solution to linear equation (Wolfram Alpha)

Question

I'm sorry if this is potentially off topic, but I posted this question at the Math SE and they pointed me here. Both SE sites have a tag for Wolfram Alpha, but maybe you guys are better equipped to help. I do not have Mathematica.

Let's assume I need to buy 2 items. I know the prices of these items, but I can only buy whole values of them. I have a finite amount of money to spend. I want to buy the amount of each item such that I spend the most money when buying both.

Using Wolfram Alpha I can find all integer solutions using this query:

1482 <= 76.61x + 157.84y <= 1560, x>0, y>0 integer solutions

So, then I'd just like it to either display the function's value given the integer solutions for x and y, or show only the most "optimal" solutions (and ideally the function's value with those solutions).

Answer 1

I know you don't have Mathematica but I post it for completeness

f[x_,y_]:=76.61x+157.84y
sol=Maximize[{f[x,y],1482<=f[x,y]<=1560,x>0,y>0},{x,y}\[Element]Integers]

{1559.92, {x -> 8, y -> 6}}

You can visualize this quite nice

c1[x_] = y /. First@Solve[f[x, y] == 1560, y];
c2[x_] = y /. First@Solve[f[x, y] == 1482, y];

points=Table[
 Graphics[
  {
   If[1482<= f[x,y]<=1560,Green,Red],
   PointSize[Medium],
   Point[{x,y}]
  }
 ],{x,0,21},{y,0,11}];

Show[
 ContourPlot[f[x,y],{x,0,21},{y,0,11}],
 Plot[{c1[x],c2[x]},{x,0,21},PlotStyle->Blue],
 Graphics[{PointSize[Large],Point[{x,y}/.sol[[2]]]}],
 points
]

Answer 2

One can also use LinearProgramming[] instead (after applying Rationalize[] to the prices):

v = Rationalize[{76.61, 157.84}];
LinearProgramming[-v, {v, v}, {{1482, 1}, {1560, -1}}, 0, Integers]
   {8, 6}

which is consistent with OhmSweetOhm's answer.

Answer 3

 k = 200;
 f[x_, y_] := 76.61 x + 157.84 y
 sol = FindInstance[{1482 <= f[x, y] <= 1560, x > 0, y > 0}, {x, y} ∈ Integers, k]

 Length[sol] (*Mathematica finds 10 solutions *)

 (*{{x -> 1, y -> 9}, {x -> 3, y -> 8}, {x -> 5, y -> 7}, {x -> 7, 
  y -> 6}, {x -> 8, y -> 6}, {x -> 10, y -> 5}, {x -> 12, 
  y -> 4}, {x -> 14, y -> 3}, {x -> 16, y -> 2}, {x -> 18, y -> 1}}*)

Answer 4

Here is different approach.

coor = Tuples[Range@100, 2];

f[x_, y_] := 76.61 x + 157.84 y

Extract[coor,Join @@ Position[f @@@ coor, #] & /@Select[f @@@ coor, 1482 <= # <= 1560 &]]

{{1, 9}, {3, 8}, {5, 7}, {7, 6}, {8, 6}, {10, 5}, {12, 4}, {14, 3}, {16, 2}, {18, 1}}

Answer 5

Here are some steps you can take without necessarily having Mathematica.

You are solving a linear Diophantine equation $a*x+b*y=c$ for integer $\{x,y\}$. In particular, $7661*x+15784*y=c$, where $148200\le c \le 156000$.

Since GCD[a,b]=1, the general solution is $\{x,y\}=\{x_0+b*k,y_0-a*k\}$, for integer $k$, and integer $\{x_0,y_0\}=\{r,s\}*c$, where $\{r,s\}$ is found via the extended GCD. The extended GCD finds coefficients $\{r,s\}$ such that $a*r+b*s=1$. In Mathematica, {r,s}=ExtendedGCD[a,b][[2]].

Thus, $\{x,y\}=\{r*c+b*k,s*c-a*k\}$. For positive $x>0$ and $y>0$, we must have $-r*c/b<k<s*c/a$. If no integers $k$ exist between these limits then Ceiling[-r*c/b]>Floor[s*c/a].

Check this condition while counting down from the maximum c=156000.

Block[{a = 7661, b = 15784, c = 156000, r, s, k},
   {r, s} = ExtendedGCD[a, b][[2]];
   While[(k = Ceiling[-r*c/b]) > Floor[s*c/a], c -= 1];
   {"k" -> k, {x, y} -> {r, s}*c + {b, -a}*k, a*x/100. + b*y/100. -> c/100.}
]

{k -> 26674, {x, y} -> {8, 6}, 76.61 x + 157.84 y -> 1559.92}