0
$\begingroup$

I'm asked to write a function solvelinear[k_,m_] using LinearProgramming that maximizes the expression $$\sum_{i=1}^4\left(i-\frac{k^2}{m}\right)^2x_i$$ subject to constraints

  • $x_1+x_2+x_3+x_4=m$
  • $x_1+2x_2+3x_3+4x_4=k^2$
  • $x_1+x_3\leq k$
  • $x_1,x_2,x_3,x_4$ are integers.

I'm reading the tutorial on LinearProgramming but it seems to minimize things? Following the tutorial I came up with this:

solvelinear[k_, m_] := 
 LinearProgramming[{(1 - k^2/m)^2, (2 - k^2/m)^2, (3 - k^2/m)^2, (4 - 
      k^2/m)^2}, {{1, 1, 1, 1}}, {{m, 0}}, {{1, 2, 3, 4}}, {{k^2, 
    0}}, {{1, 0, 1, 0}}, {{k, -1}}, Integers]

It doesn't work and I should maximize things anyway. Is there a way to do this with LinearProgramming or should I just use Maximize?

$\endgroup$
  • $\begingroup$ What are the constaints on k and m? $\endgroup$ – corey979 Dec 15 '16 at 11:57
  • $\begingroup$ The only information given is that they are integers $\endgroup$ – lis Dec 15 '16 at 11:59
  • $\begingroup$ But doesn't my choice of k and m give a bound for $x_i$? $\endgroup$ – lis Dec 15 '16 at 12:12
  • $\begingroup$ Welcome to Mathematica.SE! 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Take the tour and check the faqs! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$ – user9660 Dec 15 '16 at 12:19
  • $\begingroup$ Just to be sure: by integers you mean also negative integers or only non-negative? Because in the former the constrains allow the sum to be arbitrarily big, while in the latter there's a unique solution. $\endgroup$ – corey979 Dec 15 '16 at 12:51
0
$\begingroup$

Three ways.

Method 1.

Clear[k, m, x, c1, c2, c3, sum, max]

Define the constraints:

c1 = x[1] + x[2] + x[3] + x[4] == m;
c2 = x[1] + 2 x[2] + 3 x[3] + 4 x[4] == k^2;
c3 = x[1] + x[3] <= k;

Define the sum to be maximized:

sum = Sum[(i - k^2/m)^2 x[i], {i, 1, 4}]

Define a function that attempts to maximize the sum for given m, k:

max[k_, m_] := 
 Evaluate @ Maximize[{sum, c1, c2, c3, x[1] >= 0, x[2] >= 0, x[3] >= 0, x[4] >= 0},
    {x[1], x[2], x[3], x[4]}, Integers]

Test:

Quiet @ max[6, 10]

{42/5, {x[1] -> 1, x[2] -> 0, x[3] -> 1, x[4] -> 8}}

Quiet @ max[7, 10]

{-∞, {x[1] -> Indeterminate, x[2] -> Indeterminate, x[3] -> Indeterminate, x[4] -> Indeterminate}}

Quiet is used because in the second case there are no instances that fulfill the conditions, so there's a bunch of warnings.

Method 2.

Clear[k, m, x, c1, c2, c3, sum, con]

Put the constraints into Solve:

con[k_, m_] := 
 Solve[{x[1] + x[2] + x[3] + x[4] == m, 
   x[1] + 2 x[2] + 3 x[3] + 4 x[4] == k^2, x[1] + x[3] <= k, 
   x[1] >= 0, x[2] >= 0, x[3] >= 0, x[4] >= 0}, {x[1], x[2], x[3], x[4]}, Integers]

E.g.

con[6, 10]

{{x[1] -> 0, x[2] -> 0, x[3] -> 4, x[4] -> 6}, {x[1] -> 0, x[2] -> 1, x[3] -> 2, x[4] -> 7}, {x[1] -> 0, x[2] -> 2, x[3] -> 0, x[4] -> 8}, {x[1] -> 1, x[2] -> 0, x[3] -> 1, x[4] -> 8}}

Define the sum as a function:

sum[k_, m_] := Sum[(i - k^2/m)^2 x[i], {i, 1, 4}]

and

sum[6, 10] /. con[6, 10]

{12/5, 22/5, 32/5, 42/5}

The last number, 42/5, is the greatest and corresponds to {x[1] -> 1, x[2] -> 0, x[3] -> 1, x[4] -> 8} - the same as in the previous method.

This can be wrapped into

MaximalBy[Transpose@{sum[6, 10] /. con[6, 10], con[6, 10]}, First]

{{42/5, {x[1] -> 1, x[2] -> 0, x[3] -> 1, x[4] -> 8}}}

which can be given a name

max2[k_, m_] := MaximalBy[Transpose@{sum[k, m] /. con[k, m], con[k, m]}, First]

Both methods work for k = 8 and m = 26, giving 552/13 for {x[1] -> 8, x[2] -> 8, x[3] -> 0, x[4] -> 10}.

Method 3.

As showed by J. M. in the comment, LinearProgramming can be employed as as follows:

max3[k_, m_] := 
 LinearProgramming[-Table[(m i - k^2)^2, {i, 4}], {{1, 1, 1, 1}, {1, 
    2, 3, 4}, {1, 0, 1, 0}}, {{m, 0}, {k^2, 0}, {k, -1}}, 
  Table[0, {4}], Integers]

with

max3[8, 26]

{8, 8, 0, 10}

with a warning:

LinearProgramming::lpip: Warning: integer linear programming will use a machine-precision approximation of the inputs.

$\endgroup$
  • 1
    $\begingroup$ LinearProgramming[-Table[(m i - k^2)^2, {i, 4}], {{1, 1, 1, 1}, {1, 2, 3, 4}, {1, 0, 1, 0}}, {{m, 0}, {k^2, 0}, {k, -1}}, Table[0, {4}], Integers] works fine. $\endgroup$ – J. M. is in limbo Dec 15 '16 at 13:25

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.