MATLAB: Linprog doesn’t satisfy b constraints when it contains negative coefficients

linprog; optimizationMATLAB

I'm trying to maximize an objective function using linprog. A simplified version (of an assignment problem) is to maximize:
-2062595m_10 + 4854093m_01 + 7911803m_11 subject to:
m_10 + m_11 <= 2  
m_01 + m_11 <= 1
m_10>=0, m_01>=0,m_11>=0
The intuition being there are 2 "resources" and 1 "task". The correct solution should assign one resource to the task (7911803 (m_11==1)) and -2062595 (m_10==1) to account for the other unassigned resource. m_01==0 if the task is not assigned to either resource.
I code this in Matlab as:
f=[-2062595;4854093;7911803]; 
A=[1 0 1; 0 1 1];
b=[2; 1];
lb=zeros(length(A),1);
Then I solve it using:
options = optimset('LargeScale', 'off', 'Simplex', 'on');
[x,fval,exitflag,output,lambda] = linprog(-f,A,b,[],[],lb,[],[], options);
The output for x is:
x =
               0
               0
            1.00
But it should be:
x =
            1.00
               0
            1.00
In other words, it should pick x(1) given my b vector of constraints and sum to the number of resources (2 in this case). The problem only occurs when there are negative coefficients in the f vector. If I optimize instead using:
f=[2062595;4854093;7911803];
Then I get the desired x vector (above). My questions are:
Question 1. Why won't it solve when I include negative constraints?
Question 2. How does Matlab choose lambda.eqlin? I get (for the positive coefficients case):
lambda.ineqlin
 ans =
    2062595.81
    5849207.54
Your help is very much appreciated.

Best Answer

The correct solution should assign one resource to the task (7911803 (m_11==1)) and -2062595 (m_10==1) to account for the other unassigned resource. m_01==1 if the task is not assigned to either resource.
This part wasn't clear to me, but it sounds like some of your constraints should have been specified to be equality rather than inequality constraints.
For the problem you've posted, x=[1; 0; 1] is definitely not optimal, as you can readily verify by inspecting dot(f,x) at both that point and the one LINPROG gives you.
I can also independently verify that the solution given by LINPROG is optimal using LCON2VERT. Here I compute all the extreme points (vertices) of the polyhedron defined by your constraints and compute dot(f,x) with all of them. The extreme point x=[0 0 1]' clearly achieves the maximum.
    >> extremepoints=lcon2vert([A;-eye(3)],[b;0;0;0])
    extremepoints =
         0     0     0
         0     0     1
         0     1     0
         1     0     1
         2     0     0
         2     1     0
   >> extremepoints*f
    ans =
               0
         7911803
         4854093
         5849208
        -4125190
          728903
Question 2. How does Matlab choose lambda.eqlin? I get (for the positive coefficients case):
Since you have no equality constraints, these Lagrange multipliers lambda.eqlin are presumably empty.
Related Question