Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

About linear programming

33 views
Skip to first unread message

Marcela Villa Marulanda

unread,
Apr 25, 2012, 12:35:55 AM4/25/12
to
Hi,

I attempt to solve these linear programming problems in Mathematica,
but its result is "Maximize::natt: The maximum is not attained at any
point satisfying the given constraints", why? I've solved this problem
in other applications and the solution is achieved.

I don't know the reasons about it. I'll thank to whom give me some
clues!

Problem 1

Maximize[{5 Subscript[x, 1] + 4 Subscript[x, 2] + 3 Subscript[x, 3],
Subscript[x, 1] + Subscript[x, 3] <= 15 &&
Subscript[x, 2] + 2 Subscript[x, 3] <= 25}, {Subscript[x, 1],
Subscript[x, 2], Subscript[x, 3]}];

Problem 2

Maximize[{30 Subscript[x, 1] + 40 Subscript[x, 2] +
20 Subscript[x, 3] + 10 Subscript[x, 4] - 15 Subscript[x, 5] -
20 Subscript[x, 6] - 10 Subscript[x, 7] - 8 Subscript[x, 8],
0.3 Subscript[x, 1] + 0.3 Subscript[x, 2] + 0.25 Subscript[x, 3] +
0.15 Subscript[x, 4] <= 1000 &&
0.25 Subscript[x, 1] + 0.35 Subscript[x, 2] +
0.3 Subscript[x, 3] + 0.1 Subscript[x, 4] <= 1000 &&
0.45 Subscript[x, 1] + 0.5 Subscript[x, 2] + 0.4 Subscript[x, 3] +
0.22 Subscript[x, 4] <= 1000 &&
0.15 Subscript[x, 1] + 0.15 Subscript[x, 2] +
0.1 Subscript[x, 3] + 0.05 Subscript[x, 4] <= 1000 &&
Subscript[x, 1] + Subscript[x, 5] == 800 &&
Subscript[x, 2] + Subscript[x, 6] == 750 &&
Subscript[x, 3] + Subscript[x, 7] == 600 &&
Subscript[x, 4] + Subscript[x, 8] == 500}, {Subscript[x, 1],
Subscript[x, 2], Subscript[x, 3], Subscript[x, 4], Subscript[x, 5],
Subscript[x, 6], Subscript[x, 7], Subscript[x, 8]}]

Bob Hanlon

unread,
Apr 26, 2012, 5:26:11 AM4/26/12
to
In both cases, a lower bound must be placed on Subscript[x, 3]

eqns1 = {5 Subscript[x, 1] + 4 Subscript[x, 2] + 3 Subscript[x, 3],
Subscript[x, 1] + Subscript[x, 3] <= 15,
Subscript[x, 2] + 2 Subscript[x, 3] <= 25,
Subscript[x, 3] >= x3min};

sol1 = Maximize[eqns1,
{Subscript[x, 1], Subscript[x, 2], Subscript[x, 3]}];

sol1 /. x3min -> 0

{175, {Subscript[x, 1] -> 15, Subscript[x, 2] -> 25, Subscript[x, 3] -> 0}}

eqns2 = Rationalize[{
30 Subscript[x, 1] + 40 Subscript[x, 2] + 20 Subscript[x, 3] +
10 Subscript[x, 4] - 15 Subscript[x, 5] - 20 Subscript[x, 6] -
10 Subscript[x, 7] - 8 Subscript[x, 8],
0.3 Subscript[x, 1] + 0.3 Subscript[x, 2] +
0.25 Subscript[x, 3] + 0.15 Subscript[x, 4] <= 1000,
0.25 Subscript[x, 1] + 0.35 Subscript[x, 2] +
0.3 Subscript[x, 3] + 0.1 Subscript[x, 4] <= 1000,
0.45 Subscript[x, 1] + 0.5 Subscript[x, 2] +
0.4 Subscript[x, 3] + 0.22 Subscript[x, 4] <= 1000,
0.15 Subscript[x, 1] + 0.15 Subscript[x, 2] +
0.1 Subscript[x, 3] + 0.05 Subscript[x, 4] <= 1000,
Subscript[x, 1] + Subscript[x, 5] == 800,
Subscript[x, 2] + Subscript[x, 6] == 750,
Subscript[x, 3] + Subscript[x, 7] == 600,
Subscript[x, 4] + Subscript[x, 8] == 500,
Subscript[x, 3] >= x3min}, 0];

sol2 = Maximize[eqns2,
{Subscript[x, 1], Subscript[x, 2], Subscript[x, 3],
Subscript[x, 4], Subscript[x, 5], Subscript[x, 6],
Subscript[x, 7], Subscript[x, 8]}];

sol2 /. x3min -> 0

{5531000/37, {Subscript[x, 1] -> 660000/37,
Subscript[x, 2] -> -(80000/37), Subscript[x, 3] -> 0,
Subscript[x, 4] -> -(1000000/37), Subscript[x, 5] ->
-(630400/37), Subscript[x, 6] -> 107750/37,
Subscript[x, 7] -> 600, Subscript[x, 8] -> 1018500/37}}


Bob Hanlon


2012/4/25 Marcela Villa Marulanda <mavi...@gmail.com>:

da...@wolfram.com

unread,
Apr 26, 2012, 5:29:46 AM4/26/12
to
Not enough constraints. The example below may give an indication of what can happen. Possibly you also mean to constraing the variables to be nonnegative?

In[164]:= FindInstance[{30 Subscript[x, 1] + 40 Subscript[x, 2] +
20 Subscript[x, 3] + 10 Subscript[x, 4] - 15 Subscript[x, 5] -
20 Subscript[x, 6] - 10 Subscript[x, 7] - 8 Subscript[x, 8] >=
10^6, 0.3 Subscript[x, 1] + 0.3 Subscript[x, 2] +
0.25 Subscript[x, 3] + 0.15 Subscript[x, 4] <= 1000 &&
0.25 Subscript[x, 1] + 0.35 Subscript[x, 2] +
0.3 Subscript[x, 3] + 0.1 Subscript[x, 4] <= 1000 &&
0.45 Subscript[x, 1] + 0.5 Subscript[x, 2] + 0.4 Subscript[x, 3] +
0.22 Subscript[x, 4] <= 1000 &&
0.15 Subscript[x, 1] + 0.15 Subscript[x, 2] +
0.1 Subscript[x, 3] + 0.05 Subscript[x, 4] <= 1000 &&
Subscript[x, 1] + Subscript[x, 5] == 800 &&
Subscript[x, 2] + Subscript[x, 6] == 750 &&
Subscript[x, 3] + Subscript[x, 7] == 600 &&
Subscript[x, 4] + Subscript[x, 8] == 500}, {Subscript[x, 1],
Subscript[x, 2], Subscript[x, 3], Subscript[x, 4], Subscript[x, 5],
Subscript[x, 6], Subscript[x, 7], Subscript[x, 8]}]

Out[164]= {{Subscript[x, 1] -> 800., Subscript[x, 2] -> 49133.3,
Subscript[x, 3] -> -64900., Subscript[x, 4] -> 0.,
Subscript[x, 5] -> 0., Subscript[x, 6] -> -48383.3,
Subscript[x, 7] -> 65500., Subscript[x, 8] -> 500.}}

With such constraints added it will give a max.

In[167]:= Maximize[{30 Subscript[x, 1] + 40 Subscript[x, 2] +
20 Subscript[x, 3] + 10 Subscript[x, 4] - 15 Subscript[x, 5] -
20 Subscript[x, 6] - 10 Subscript[x, 7] - 8 Subscript[x, 8],
0.3 Subscript[x, 1] + 0.3 Subscript[x, 2] + 0.25 Subscript[x, 3] +
0.15 Subscript[x, 4] <= 1000 &&
0.25 Subscript[x, 1] + 0.35 Subscript[x, 2] +
0.3 Subscript[x, 3] + 0.1 Subscript[x, 4] <= 1000 &&
0.45 Subscript[x, 1] + 0.5 Subscript[x, 2] + 0.4 Subscript[x, 3] +
0.22 Subscript[x, 4] <= 1000 &&
0.15 Subscript[x, 1] + 0.15 Subscript[x, 2] +
0.1 Subscript[x, 3] + 0.05 Subscript[x, 4] <= 1000 &&
Subscript[x, 1] + Subscript[x, 5] == 800 &&
Subscript[x, 2] + Subscript[x, 6] == 750 &&
Subscript[x, 3] + Subscript[x, 7] == 600 &&
Subscript[x, 4] + Subscript[x, 8] == 500 &&
And @@ Thread[Table[Subscript[x, j], {j, 8}] >= 0]}, {Subscript[x,
1], Subscript[x, 2], Subscript[x, 3], Subscript[x, 4],
Subscript[x, 5], Subscript[x, 6], Subscript[x, 7], Subscript[x, 8]}]

Out[167]= {64625., {Subscript[x, 1] -> 800., Subscript[x, 2] -> 750.,
Subscript[x, 3] -> 387.5, Subscript[x, 4] -> 500.,
Subscript[x, 5] -> 0., Subscript[x, 6] -> 0.,
Subscript[x, 7] -> 212.5, Subscript[x, 8] -> 0.}}
Daniel Lichtblau
Wolfram Research

Dana DeLouis

unread,
Apr 26, 2012, 5:35:55 AM4/26/12
to
> I attempt to solve these linear programming problems in Mathematica,
> but its result is "Maximize::natt: The maximum is not attained at any
> point satisfying the given constraints", why?

Hi. I believe the problems are caused by being Unbounded in the Negative direction.
Just add a lower limit that each variable is >= 0.

obj = 5 Subscript[x,1]+4 Subscript[x,2]+3 Subscript[x,3] ;

const = {
Subscript[x,1]+Subscript[x,3]<=15,
Subscript[x,2]+2 Subscript[x,3]<=25,
Subscript[x,1]>=0,
Subscript[x,2]>=0,
Subscript[x,3]>=0}

var = {
Subscript[x,1],
Subscript[x,2],
Subscript[x,3]}

Maximize[{obj ,const},var]

{175, {Subscript[x, 1]->15, Subscript[x, 2]->25, Subscript[x, 3]->0}}

When one has many variable as in your example #2, try including Thread, as in this small example...

Thread[var >= 0]
{Subscript[x, 1]>=0,Subscript[x, 2]>=0,Subscript[x, 3]>=0}


Don't know if you would find this useful:

Although LinearProgramming is a Minimizing function, one can multiply the objective by -1 to reverse the logic.
This changes your Maximizing problem into one of Minimizing.

obj ={5,4,3};

LinearProgramming[ - obj, {{1,0,3},{0,1,2}}, {{15,-1},{25,-1}} ]
{15,25,0}

obj . %
175

= = = = = = = = = =
Good luck. HTH :>)
Dana DeLouis
Mac & Math 8
= = = = = = = = = =

Dana DeLouis

unread,
Apr 27, 2012, 6:50:38 AM4/27/12
to
Hi. A little off topic, but I always get confused with the basic input to the function - LinearProgramming.
Here's a little program to take an input that might be easier to read, and put it into the form required by the function.
There's lots of variations one could make. Here's a simple example...
Here, the constraints are definitely not in the required form for the function:

obj = {30,40,20,10,-15,-20,-10,-8};

const =
{
{.3,.3,.25,.15,0,0,0,0} <=1000,
{.25,.35,.3,.1,0,0,0,0} <=1000,
{.45,.5,.4,.22,0,0,0,0} <=1000,
{.15,.15,.1,.05,0,0,0,0} <=1000,
{1,0,0,0,1,0,0,0} ==800,
{0,1,0,0,0,1,0,0} ==750,
{0,0,1,0,0,0,1,0} ==600,
{0,0,0,1,0,0,0,1} ==500
};

LinearProgMax[obj,Rationalize[const]]
{64625, {800,750,775/2,500,0,0,425/2,0}}

%//N
{64625., {800.,750.,387.5,500.,0.,0.,212.5,0.}}

LinearProgMin[obj_,const_]:=Module[{v,sol},
v=const/.(Less|LessEqual)[x_,y_]->{x,{y,-1}};
v=v/.(Greater|GreaterEqual)[x_,y_]->{x,{y,+1}};
v=v/.Equal[x_,y_]->{x,{y,0}};
v=Transpose[v];
sol = LinearProgramming[obj,First[v],Last[v] ];
{sol.obj,sol}]

LinearProgMax[obj_,const_]:=LinearProgMin[-obj,const]/.{x_,y_}->{-x,y}


After copying a table of cells from a Spread Sheet, a macro could convert it into the form above.
One could even include First[v].sol to get the values of the Right hand side to make sure the constraints were met (or calculate slack).
ie change to: {sol.obj, sol, First[v].sol}

= = = = = = = = = =
0 new messages