Search code examples
rmathematical-optimizationlinear-programminglpsolve

Getting different solution to linear programming problem when slack variables are added

I am trying to solve a basic linear programming problem using lpSolve in R.

The original problem is:

original problem

In augmented form (i.e. with slack variables added) it is:

augmented form

When I solve the original problem like so:

M = matrix(c(1, 2, 3, 1), nrow = 2, byrow = TRUE)
lp("max", c(1,1), M, c("<=", "<="), c(100, 75))$solution

I get the solution: 10 45, which is correct.

When I solve the augmented problem like so:

A = matrix(c(1, 2, 1, 3, 1, 1), nrow = 2, byrow = TRUE)
lp("max", c(1,1,0,0), A, c("=", "="), c(100, 75))$solution

I get 1e+30 0e+00 0e+00 0e+00, which is incorrect. So I thought it might not like my objective function coefficients, and tried:

A = matrix(c(1, 2, 1, 3, 1, 1), nrow = 2, byrow = TRUE)
lp("max", c(1,1), A, c("=", "="), c(100, 75))$solution

Which returned 0.0000000 0.3333333 -- also incorrect.

The solutions to the original and augmented problem should be the same. I cannot see what I am doing wrong. Why am I getting two different answers?

Solution

  • This is rather obvious. Your problem has 4 variables but your matrix has 3 columns.

    Look at the constraints as:

     x1 + 2x2 + s1        = 100
3x1 +  x2      + s2   =  75

    (Interesting how just a few spaces can change the perception).