In [32]:
from cvxopt import solvers
import numpy as np
from cvxopt import matrix
import pprint

This question comes from assignment 3 q1 from here: https://class.coursera.org/linearprogramming-001/quiz/feedback?submission_id=262352 We will be trying to solve the following LP problem:

$$Max~-x_0$$

Given the following constraints:

$$-1x_0-1x_1-1x_2-0x_3\le5$$ $$-1x_0+1x_1-2x_2+1x_3\le-10$$ $$-1x_0+1x_1+0x_2-1x_3\le1-20$$ $$-1x_0+1x_1+1x_2+1x_3\le3$$ $$x_0,x_1,x_2,x_3\ge0$$

In [62]:
c = matrix([[-1,0,0,0]],tc="d") #coefficient of x0 is -1
In [57]:
In [58]:
A = matrix([[-1.,-1.,-1.,-1.,-1.,0.,0.,0.], [-1.,1., 1., 1.,0.,-1.,0.,0.],[-1.,-2.,0.,1., 0.,0.,-1.,0.],[0.,1.,-1.,1.,0.,0.,0.,-1.]],tc='d')
print(A)
[-1.00e+00 -1.00e+00 -1.00e+00  0.00e+00]
[-1.00e+00  1.00e+00 -2.00e+00  1.00e+00]
[-1.00e+00  1.00e+00  0.00e+00 -1.00e+00]
[-1.00e+00  1.00e+00  1.00e+00  1.00e+00]
[-1.00e+00  0.00e+00  0.00e+00  0.00e+00]
[ 0.00e+00 -1.00e+00  0.00e+00  0.00e+00]
[ 0.00e+00  0.00e+00 -1.00e+00  0.00e+00]
[ 0.00e+00  0.00e+00  0.00e+00 -1.00e+00]


In [59]:
b = matrix([5, -10, -20, 3, 0, 0, 0, 0], tc='d')
print b
[ 5.00e+00]
[-1.00e+01]
[-2.00e+01]
[ 3.00e+00]
[ 0.00e+00]
[ 0.00e+00]
[ 0.00e+00]
[ 0.00e+00]


In [65]:
sol = solvers.lp(-c, A, b) #Maximize -x0
print (sol['x'])
     pcost       dcost       gap    pres   dres   k/t
 0:  1.6508e+00  2.5321e+01  8e+01  1e+00  6e+00  1e+00
 1:  1.2018e+01  1.8145e+01  2e+01  2e-01  2e+00  8e-01
 2:  1.1164e+01  1.1760e+01  1e+00  2e-02  1e-01  1e-01
 3:  1.0672e+01  1.0681e+01  2e-02  3e-04  2e-03  2e-03
 4:  1.0667e+01  1.0667e+01  2e-04  3e-06  2e-05  2e-05
 5:  1.0667e+01  1.0667e+01  2e-06  3e-08  2e-07  2e-07
 6:  1.0667e+01  1.0667e+01  2e-08  3e-10  2e-09  2e-09
Optimal solution found.
[ 1.07e+01]
[-5.07e-10]
[ 4.33e+00]
[ 9.33e+00]


In [37]:
 
In []:
 
Back to top