Linprog doesn't satisfy b constraints when it contains negative coefficients?

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.

Answer 1

[Matt J]

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.

[Sophia]

Sorry, that was a typo, corrected (in bold):

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.

The problem works when you use equality Aeq and beq instead which forces them to be assigned.

Last question is whether you have a recommendation for reading about how lambda is determined using the Simplex method in Matlab? Or is it just a general textbook on Simplex.

[Matt J]

I don't know. The Lagrange multiplier equations for a linear pogram are linear, though, so I assume that once the simplex algorithm finds a solution x and can see which constraints are active at the solution, it solves a linear equation

 M*lambda=f

where the columns of M are the active constraints.