Linear Programming Example - Assignment 3q1

Ass3q1LP.ipynb

{
 "metadata": {
  "name": "Assigment3q1"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from cvxopt import solvers\n",
      "import numpy as np\n",
      "from cvxopt import matrix\n",
      "import pprint"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 32
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "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:\n",
      "    \n",
      "$$Max~-x_0$$\n",
      "\n",
      "Given the following constraints:\n",
      "\n",
      "$$-1x_0-1x_1-1x_2-0x_3\\le5$$\n",
      "$$-1x_0+1x_1-2x_2+1x_3\\le-10$$\n",
      "$$-1x_0+1x_1+0x_2-1x_3\\le1-20$$\n",
      "$$-1x_0+1x_1+1x_2+1x_3\\le3$$\n",
      "$$x_0,x_1,x_2,x_3\\ge0$$"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "c = matrix([[-1,0,0,0]],tc=\"d\") #coefficient of x0 is -1\n",
      "\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 62
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 57
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\n",
      "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')\n",
      "print(A)\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[-1.00e+00 -1.00e+00 -1.00e+00  0.00e+00]\n",
        "[-1.00e+00  1.00e+00 -2.00e+00  1.00e+00]\n",
        "[-1.00e+00  1.00e+00  0.00e+00 -1.00e+00]\n",
        "[-1.00e+00  1.00e+00  1.00e+00  1.00e+00]\n",
        "[-1.00e+00  0.00e+00  0.00e+00  0.00e+00]\n",
        "[ 0.00e+00 -1.00e+00  0.00e+00  0.00e+00]\n",
        "[ 0.00e+00  0.00e+00 -1.00e+00  0.00e+00]\n",
        "[ 0.00e+00  0.00e+00  0.00e+00 -1.00e+00]\n",
        "\n"
       ]
      }
     ],
     "prompt_number": 58
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "b = matrix([5, -10, -20, 3, 0, 0, 0, 0], tc='d')\n",
      "print b\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[ 5.00e+00]\n",
        "[-1.00e+01]\n",
        "[-2.00e+01]\n",
        "[ 3.00e+00]\n",
        "[ 0.00e+00]\n",
        "[ 0.00e+00]\n",
        "[ 0.00e+00]\n",
        "[ 0.00e+00]\n",
        "\n"
       ]
      }
     ],
     "prompt_number": 59
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sol = solvers.lp(-c, A, b) #Maximize -x0\n",
      "print (sol['x'])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "     pcost       dcost       gap    pres   dres   k/t\n",
        " 0:  1.6508e+00  2.5321e+01  8e+01  1e+00  6e+00  1e+00\n",
        " 1:  1.2018e+01  1.8145e+01  2e+01  2e-01  2e+00  8e-01\n",
        " 2:  1.1164e+01  1.1760e+01  1e+00  2e-02  1e-01  1e-01\n",
        " 3:  1.0672e+01  1.0681e+01  2e-02  3e-04  2e-03  2e-03\n",
        " 4:  1.0667e+01  1.0667e+01  2e-04  3e-06  2e-05  2e-05\n",
        " 5:  1.0667e+01  1.0667e+01  2e-06  3e-08  2e-07  2e-07\n",
        " 6:  1.0667e+01  1.0667e+01  2e-08  3e-10  2e-09  2e-09\n",
        "Optimal solution found.\n",
        "[ 1.07e+01]\n",
        "[-5.07e-10]\n",
        "[ 4.33e+00]\n",
        "[ 9.33e+00]\n",
        "\n"
       ]
      }
     ],
     "prompt_number": 65
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 37
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}