linprog send wrong output

I'm trying ro solve linear programing problem and I'm sure of result

max 350 x1 +300 x2 +350 x3 +350x4

5 x1 + 7 x3 ≤ 119

5 x2 + 7 x4 ≤ 91

x1 + x2 ≤ 23

x3 + x4 ≤ 15

x≥0

here my command;

c=[-300 -300 -350 -350]
A=[5 0 7 0; 0 5 0 7;1 1 0 0 ; 0 0 1 1]
b =[119; 91; 23; 15]
Aeq=[]
beq=[]
lb=[0; 0; 0 ; 0]
ub=[]
linprog(c,A,b,Aeq,beq,lb,ub)

Optimal solution found.

ans =

23

0

4/7

13

right output is

24/5

91/5

95/7

0

What mistake am I making?

i tried to use the web Matlab but I got the same result.

I asked my collegue and He got the right result which the same input.

Answer 1

[Steven Lord]

Your objective is written mathematically as "max 350 x1 +3 x2 +3.5 x3 +3.5x4" but the c vector you've defined is "c=[-300 -300 -350 -350]".Shouldn't your c vector contain 3.5 somewhere? That seems to me to be a sign that you're not solving the problem you think you're solving.

Also you can check if your expected vector gives a larger value for the expression you're trying to maximize than the vector you believe to be the correct answer, to confirm or disprove your belief that your answer is the correct one. [Multiply -c times your vector and -c times the vector from linprog.]

[RICCARDO]

Excuse me I corrected mistakes during previous typing.

[RICCARDO]

I'd like to highlight my collegue got the right result

[Steven Lord]

Okay, so let's check.

c=[-300 -300 -350 -350];
A=[5 0 7 0; 0 5 0 7;1 1 0 0 ; 0 0 1 1];
b =[119; 91; 23; 15];
format longg
linprogSolution = linprog(c, A, b, [], [], zeros(1, 4))

Optimal solution found.

linprogSolution = 4x1

23 0 0.571428571428573 13

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

objectiveValueLinprog = -c*linprogSolution

objectiveValueLinprog = 
       11650

constraintsCheck = [A*linprogSolution, b]

constraintsCheck = 4x2

119 119 91 91 23 23 13.5714285714286 15

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

So the solution from linprog satisfies the constraints (all the elements in the first column of constraintsCheck are less than or equal to the corresponding elements in the second column) and gives an objective value of 11650. How about your solution?

riccardoSolution = [24/5; 91/5; 95/7; 0];
objectiveValueRiccardo = -c*riccardoSolution

objectiveValueRiccardo = 
       11650

constraintsCheck = [A*riccardoSolution, b]

constraintsCheck = 4x2

119 119 91 91 23 23 13.5714285714286 15

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

checkIfSameAnswer = objectiveValueLinprog == objectiveValueRiccardo

checkIfSameAnswer = logical
   1

Your expected solution gives the same objective value as the one from linprog and the constraints are satisfied with your expected solution. Your system has at least two solutions. linprog found one of them and you expected a different one. Both are correct.

[RICCARDO]

Ok, thank you very much. I understood your explanation.

This one is a university exercise so ?m interesting to get the other solution iven if both are correct.

Is there way to get the other solution by linprog ?

[Matt J]

No, when infinite solutions exist to a linear program, as is the case here, there is no reliable way to ensure the code returns a particular solution. You would have to modify the problem with additional constraints.

[RICCARDO]

thanks again.

[Steven Lord]

This isn't directly about linprog but you might find this article that's somewhat related to your question interesting. It was written by Cleve Moler, chief scientist and one of the founders of MathWorks, about "impossible problems".

In it Cleve asks "I'm thinking of two numbers. Their average is 3. What are the numbers?" He shows how to compute two answers in MATLAB (one answer is 6 and 0, another is 3 and 3.) At the end, he wrote:

But three people said "2 and 4." That is certainly another "nice" answer, but the constraints it satisfies are more subtle. They have something to do with requiring the solution to have integer components that are distinct, but near the average. It's harder to state and compute in MATLAB without just giving the answer.

[John D'Errico]

In the simple example @Steven Lord gives, where the mean of two numbers is known, the solution can be written as

[3 - t, 3 + t]

where any value for t will generate the same mean, yet a completely different, and equally valid result.

How about the question posed in the linear program? Are they both valid solutions? (Now that the equations have been correctly written.)

c=[-300 -300 -350 -350];
A=[5 0 7 0; 0 5 0 7;1 1 0 0 ; 0 0 1 1];
b =[119; 91; 23; 15];
x1 = [23;0;4/7;13];
x2 = [24/5;91/5;95/7;0];

A*x1 <= b

ans = 4x1 logical array
   1
   1
   1
   1

A*x2 <= b

ans = 4x1 logical array
   1
   1
   1
   1

c*x1

ans = -11650

c*x2

ans = -11650

Both return the same solution, so both are equally valid. We might decide to find a more general family of solutions, given x1 and x2.

dx = x2 - x1

dx = 4x1

-18.2000 18.2000 13.0000 -13.0000

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

syms t

xgeneral = x1 + dx*t

xgeneral = 

c*xgeneral

ans = 

Again, the objective is unchanged, for any value of t.

A*xgeneral <= b

ans = 

As well, we see the inequality constraints are satisfied for all values of t. Although the 4th inequality constraint is never apparently active.

It is likely that the bound constraints will not always be satisfied. As long as t lies between 0 and 1, then the bound constraints wil be satisfied.

So what do we see happening here? The first three constraints can be visualized as forming a line in the 4 dimensional parameter space. AND that line just happens to be orthogonal to the objective function. So any point along that line will be a solution.