0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ The W|A tag is for questions about how to access W|A functionality from Mathematica. community.wolfram.com is open to all things Wolfram $\endgroup$ – Michael E2 Mar 3 '18 at 16:24
  • $\begingroup$ There is a cloud version of Mathematica with a free tier. Could try e.g. NMaximize or KnapsackSolve there. $\endgroup$ – Daniel Lichtblau Mar 3 '18 at 16:25
1
$\begingroup$

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
]

enter image description here

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$
 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}}*)
$\endgroup$
  • $\begingroup$ Cost function bounded below by 1482 $\endgroup$ – Okkes Dulgerci Mar 3 '18 at 17:18
  • $\begingroup$ @OkkesDulgerci. Thanks for info.:) $\endgroup$ – Mariusz Iwaniuk Mar 3 '18 at 17:21
0
$\begingroup$

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}}

$\endgroup$
0
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.