{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lets look at an example Linear Program for a supply constrainted problem \n",
    "\n",
    "**Example**\n",
    "\n",
    "lets say that we are a manufacturing company and we have two main products (tables and chairs)\n",
    "\n",
    "We can sell each `table for 30` and each `chair for 45`. But both tables and chairs are made up of similar materials and require a certain amount of each to produce one table or chair.\n",
    "\n",
    "Say in order to make a table it requires `22 wood` and `15 steel`\n",
    "and to make a chair it requires `45 wood` and `10 steel`.\n",
    "\n",
    "But we only have a certain amount of `wood(5500)` and `steel(2500)` avalible to make our products. So we must distribute the resources effectively such that we waste the least amount and make the most amount of money.\n",
    "\n",
    "So all in all \n",
    "    We want to Maximize total earned\n",
    "    with constriants of\n",
    "    total wood and steel avalible\n",
    "\n",
    "**Converting Example to standard form**\n",
    "\n",
    "we can reformulate the problem into a Maximization problem of we can make the amount of `tables = x` and amount of `chairs = x2`\n",
    "\n",
    "so we want to find \n",
    "\n",
    "`f(x, x2) = Max(30x + 45x2)` with the constraints of wood `(22x + 45x2) <= 5500` and steel `(15x + 10x2) <= 2500` and of course we want to make a positive amount of tables and chairs so `x,x2 >= 0`. Concisely this looks like\n",
    "```\n",
    "f(x) = Max(30x + 45x2)\n",
    "Subject to. \n",
    "(22x + 45x2) <= 5500\n",
    "(15x + 10x2) <= 2500\n",
    "x,x2 >= 0\n",
    "```\n",
    "\n",
    "*We can see this problem formulated and solved with the cvxpy library below, But if you were to solve it manualy look up simplex method since this is a linear program or look into the interior point method*\n",
    "\n",
    "We can see a graphical solution (hence only two variable) https://www.desmos.com/calculator/su3zgtoa8j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The max amount of money we can make on these chairs and tables is: 6510.989009341022\n",
      "table (x) amount is:  126.37362623933787\n",
      "chair (x2) amount is:  60.43956049246413\n"
     ]
    }
   ],
   "source": [
    "import cvxpy as cp\n",
    "\n",
    "# Defining the variables we want to solve for\n",
    "x = cp.Variable()\n",
    "x2 = cp.Variable()\n",
    "\n",
    "# This is our objective function we want to maximize\n",
    "objective = cp.Maximize(30*x + 45*x2)\n",
    "\n",
    "# These are our constrints representive indiviually as inequalities\n",
    "variableConstraints = (x >= 0)\n",
    "variableConstraints1 = (x2 >= 0)\n",
    "woodConstraint = (22*x + 45*x2 <= 5500)\n",
    "steelConstraint = (15*x + 10*x2 <= 2500)\n",
    "\n",
    "# we put all the constraints into a container(array) called constraints\n",
    "constraints = [variableConstraints, variableConstraints1, woodConstraint, steelConstraint]\n",
    "\n",
    "# Now we have our formulated problem\n",
    "problem = cp.Problem(objective, constraints)\n",
    "\n",
    "# outputing the results\n",
    "print(\"The max amount of money we can make on these chairs and tables is:\", problem.solve())\n",
    "print(\"table (x) amount is: \", x.value)\n",
    "print(\"chair (x2) amount is: \",  x2.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adding a new constraint (feasibility analysis) \n",
    "\n",
    "Lets go back to the example and say that we find out after computing our values that we need we find out that we actually have another product which we have a limited supply of and it is also required. That product is Glue\n",
    "\n",
    "Say that for each `Table it costs 3 glue` and for a `Chair it cost 2 glue` and we only `have 550 glue`.\n",
    "\n",
    "Then it would be pretty easy to add a new constraint as it would just be\n",
    "```\n",
    "glueConstraint = (3*x + 2*x2 <= 550)\n",
    "```\n",
    "\n",
    "now we can plug our previous values into the inequality and we can see if our previous anwser holds\n",
    "```\n",
    "3(126) + 2(60) <= 550 True\n",
    "```\n",
    "Now since the result was true then that means we dont need to do anything because we are already at a feasibility point. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The new max that we can possibly make: 6510.989009058838\n",
      "The new x and x2 values respectivly:  126.37362628453253 60.439560456063575\n"
     ]
    }
   ],
   "source": [
    "# Here we are adding a new constraint to our previous contraints\n",
    "newConstraints = constraints + [3*x + 2*x2 <= 550]\n",
    "\n",
    "# We then reconstruct the problem with the new constraints\n",
    "problem = cp.Problem(objective, newConstraints)\n",
    "\n",
    "# We now print out the computed results to prove that it will be the same as the previous problem\n",
    "print(\"The new max that we can possibly make:\", problem.solve())\n",
    "print(\"The new x and x2 values respectivly: \", x.value, x2.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see that the results were the same as without the new constraint so no need to recompute since we know this to be true.\n",
    "\n",
    "But say instead we only have 300 glue avalible then that means \n",
    "```\n",
    "3(126) + 2(60) <= 300 False\n",
    "```\n",
    "and then we would need to recompute a new feasible value\n",
    "\n",
    "with the added constraint of \n",
    "```\n",
    "glueConstraint = (3*x + 2*x2 <= 300)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The new max that we can possibly make: 5719.7802170083605\n",
      "The new x and x2 values respectivly:  27.472527201573207 108.79120891024809\n"
     ]
    }
   ],
   "source": [
    "# Here we will take the first set of contraints and then add the newer constraint that should tighten the feasible region\n",
    "newConstraints = constraints + [3*x + 2*x2 <= 300]\n",
    "\n",
    "# Redefining the problem with the tighter contraint\n",
    "problem = cp.Problem(objective, newConstraints)\n",
    "\n",
    "# Proof to show that when recomputed we get a tighter response\n",
    "print(\"The new max that we can possibly make:\", problem.solve())\n",
    "print(\"The new x and x2 values respectivly: \", x.value, x2.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see that we get drastically different values for x and x2 because of this new constraint. And we get a smaller value in the objective function\n",
    "\n",
    "Now adding a new constraint is pretty straight forward but next we're going to take a look at adding a new product which invloves the dual problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adding new product (Dual Problem & Sensitivity Analasyis)\n",
    "\n",
    "Now imagine that the big boss said that we are going to be adding a new product to our compnay and thus we need to factor in the amount of materials it uses.\n",
    "\n",
    "Say that we wanted to add dressers to our product line and it takes `30 wood` and `15 steel` to make and we `make 50` off of it. but you may notice that if we were to add this to our original problem it would make a change to every single line, including our objective function.\n",
    "```\n",
    "f(x) = Max(30x + 45x2 + 50x3)\n",
    "Subject to. \n",
    "(22x + 45x2 + 30x3) <= 5500\n",
    "(15x + 10x2 + 15x3) <= 2500\n",
    "x,x2,x3 >= 0\n",
    "```\n",
    "\n",
    "Insead we can take the dual of the problem like so\n",
    "```\n",
    "f(y) = Min(5500y1 + 2500y2)\n",
    "Subject to.\n",
    "22y1 + 15y2 >= 30\n",
    "45y1 + 10y2 >= 45\n",
    "30y1 + 15y2 >= 50\n",
    "y1, y2 is an element of the Reals\n",
    "```\n",
    "\n",
    "you may notice that the dual of the original problem is the same as the dual of the new problem with the last constraint removed which is related to our new product.\n",
    "\n",
    "Now even though it may not be visiblile because it is hidden behind the `cvxpy` library but when we compute the first problem we are given `dual values` or sometimes called `shadow prices` which are our y1 and y2 values. These values seen below give us the same output for the minimization objective function as a the maximization one in the initial problem. as seen below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution to minimization problem:  6510.989015802337\n",
      "Dual value represented in y1:  0.8241758248195796\n",
      "Dual value represented in y2:  0.7912087917178597\n"
     ]
    }
   ],
   "source": [
    "# restating the problem with the original contraints\n",
    "problem = cp.Problem(objective, constraints)\n",
    "\n",
    "# Solve to get the dual values computed and ready to display\n",
    "problem.solve()\n",
    "\n",
    "# showing that the y values multiplied by the shadow/dual values gets us the original solution\n",
    "print(\"Solution to minimization problem: \", 5500*woodConstraint.dual_value + 2500*steelConstraint.dual_value)\n",
    "\n",
    "# printing out dual values\n",
    "print(\"Dual value represented in y1: \", woodConstraint.dual_value)\n",
    "print(\"Dual value represented in y2: \", steelConstraint.dual_value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we can see that our original problem gave us two shadow prices that we could use in the dual problem now we can decide whether or not we need to recalculate for our new product by simply inputing our shadow price values for our new constriant in the dual problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "36.59340662035528\n",
      "this is false\n"
     ]
    }
   ],
   "source": [
    "# Showing that the adding the constraint of dressers with 30 wood and 15 steel multiplied by the dual values\n",
    "# is false meaning we need to recompute the feasibile value\n",
    "print(30*woodConstraint.dual_value + 15*steelConstraint.dual_value)\n",
    "print(\"this is false\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now see that adding a new product makes the problem now infeasible meaning that we need to recompute the solution which is pretty straight forward. Which would be adding a new value to each row and then applying the algorithm of choice. For a linear program you could use the Simplex method\n",
    "\n",
    "*below we are just redefining the problem with the new product but since it touches all of the items we need to*\n",
    "*update each row*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution to problem:  8566.666665947438\n",
      "The amount of Table value:  5.158440996338224e-09\n",
      "The amount of Chair value:  19.99999996726792\n",
      "The amount of Dresser value: 153.33333334531252\n",
      "Wood constraint Dual/Shadow Value:  0.46666666715030436\n",
      "Steel constraint Dual/Shadow Value:  2.4000000005977715\n"
     ]
    }
   ],
   "source": [
    "# Creating new x3 variable\n",
    "x3 = cp.Variable()\n",
    "# creating minimum value for the x3 constraint\n",
    "variableConstraints2 = (x3 >= 0)\n",
    "\n",
    "# Redefining the material constraints with the new product\n",
    "woodConstraint = (22*x + 45*x2 + 30*x3 <= 5500)\n",
    "steelConstraint = (15*x + 10*x2 + 15*x3 <= 2500)\n",
    "\n",
    "# we put all the constraints into a container(array) called constraints\n",
    "constraints = [variableConstraints, variableConstraints1, variableConstraints2, woodConstraint, steelConstraint]\n",
    "\n",
    "# This is our objective function we want to maximize\n",
    "objective = cp.Maximize(30*x + 45*x2 + 50*x3)\n",
    "\n",
    "# Printing results\n",
    "problem = cp.Problem(objective, constraints)\n",
    "print(\"Solution to problem: \", problem.solve())\n",
    "print(\"The amount of Table value: \", x.value)\n",
    "print(\"The amount of Chair value: \", x2.value)\n",
    "print(\"The amount of Dresser value:\", x3.value)\n",
    "print(\"Wood constraint Dual/Shadow Value: \", woodConstraint.dual_value)\n",
    "print(\"Steel constraint Dual/Shadow Value: \", steelConstraint.dual_value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}