duality.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "64cac3a1",
   "metadata": {},
   "source": [
    "## Primal Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3bdb610",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{aligned}\n",
    "\\max z = & 3x + 4y \\\\\n",
    "\\text{Subject to:} & \\\\\n",
    "& 2x + 4y \\le 16 \\\\\n",
    "& 3x + 2y \\le 24 \\\\\n",
    "& x, y \\ge 0 \\\\\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae935b2b",
   "metadata": {},
   "source": [
    "### Standard form of the primal problem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f972252",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{aligned}\n",
    "\\max z = & 3x + 4y \\\\\n",
    "\\text{Subject to:} & \\\\\n",
    "& 2x + 4y + s_1 = 16 \\\\\n",
    "& 3x + 2y + s_2 = 24 \\\\\n",
    "& x, y, s_1, s_2 \\ge 0 \\\\\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bab53204",
   "metadata": {},
   "source": [
    "### Simplex Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c735491c",
   "metadata": {},
   "source": [
    "|      |    x   |     y    |     s1    |      s2      |   Solution  |\n",
    "| :--: | :----: | :------: | :------:  |  :--------:  | :---------: |\n",
    "|  z   |   -3   |     -4   |     0     |      0       |      0      |\n",
    "|  s1  |   2    |     4    |     1     |      0       |     16      |\n",
    "|  s2  |   3    |     2    |     0     |      1       |     24      |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5979dfc",
   "metadata": {},
   "source": [
    "- $y$ enters\n",
    "- Ratios are $16/4 = 4$ and $24/2=12$\n",
    "- $s_1$ exits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "36c7f013",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5-element Vector{Float64}:\n",
       " 0.5\n",
       " 1.0\n",
       " 0.25\n",
       " 0.0\n",
       " 4.0"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = [2.0, 4, 1, 0, 16] / 4.0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "801251ee",
   "metadata": {},
   "source": [
    "|      |    x   |     y    |     s1    |      s2      |   Solution  |\n",
    "| :--: | :----: | :------: | :------:  |  :--------:  | :---------: |\n",
    "|  z   |   -3   |     -4   |     0     |      0       |      0      |\n",
    "|  y   |   0.5  |     1    |   0.25    |      0       |     4       |\n",
    "|  s2  |   3    |     2    |     0     |      1       |     24      |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "7e9a72db",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5-element Vector{Float64}:\n",
       "  2.0\n",
       "  0.0\n",
       " -0.5\n",
       "  1.0\n",
       " 16.0"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s2 = -2 * y + [3, 2, 0, 1, 24.0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea7f300c",
   "metadata": {},
   "source": [
    "|      |    x   |     y    |     s1    |      s2      |   Solution  |\n",
    "| :--: | :----: | :------: | :------:  |  :--------:  | :---------: |\n",
    "|  z   |   -3   |     -4   |     0     |      0       |      0      |\n",
    "|  y   |   0.5  |     1    |   0.25    |      0       |     4       |\n",
    "|  s2  |   2    |     0    |   -0.5    |      1       |     16      |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "8779b13d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5-element Vector{Float64}:\n",
       " -1.0\n",
       "  0.0\n",
       "  1.0\n",
       "  0.0\n",
       " 16.0"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z = y * 4 + [-3, -4, 0, 0, 0.0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d4ac253",
   "metadata": {},
   "source": [
    "|      |    x   |     y    |     s1    |      s2      |   Solution  |\n",
    "| :--: | :----: | :------: | :------:  |  :--------:  | :---------: |\n",
    "|  z   |   -1   |     0    |     1     |      0       |     16      |\n",
    "|  y   |   0.5  |     1    |   0.25    |      0       |     4       |\n",
    "|  s2  |   2    |     0    |   -0.5    |      1       |     16      |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc007dbc",
   "metadata": {},
   "source": [
    "- $x$ enters\n",
    "- Ratios are $4/0.5 = 8$ and $16/2=8$, tie!\n",
    "- Let $s_2$ exits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "ee93fd9b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5-element Vector{Float64}:\n",
       "  1.0\n",
       "  0.0\n",
       " -0.25\n",
       "  0.5\n",
       "  8.0"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [2, 0, -0.5, 1, 16]/ 2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3d86f5a",
   "metadata": {},
   "source": [
    "|      |    x   |     y    |     s1    |      s2      |   Solution  |\n",
    "| :--: | :----: | :------: | :------:  |  :--------:  | :---------: |\n",
    "|  z   |   -1   |     0    |     1     |      0       |     16      |\n",
    "|  y   |   0.5  |     1    |   0.25    |      0       |     4       |\n",
    "|  x   |   1    |     0    |   -0.25   |     0.5      |     8       |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "582d9ddb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5-element Vector{Float64}:\n",
       "  0.0\n",
       "  1.0\n",
       "  0.375\n",
       " -0.25\n",
       "  0.0"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = [0.5, 1, 0.25, 0, 4] + (-1/2) * x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70b9edcb",
   "metadata": {},
   "source": [
    "|      |    x   |     y    |     s1    |      s2      |   Solution  |\n",
    "| :--: | :----: | :------: | :------:  |  :--------:  | :---------: |\n",
    "|  z   |   -1   |     0    |     1     |      0       |     16      |\n",
    "|  y   |   0    |     1    |   0.375   |    -0.25     |     0       |\n",
    "|  x   |   1    |     0    |   -0.25   |     0.5      |     8       |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "bc2fe851",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5-element Vector{Float64}:\n",
       "  0.0\n",
       "  0.0\n",
       "  0.75\n",
       "  0.5\n",
       " 24.0"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z = [-1, 0, 1, 0, 16.0] + (1) * x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19c4add7",
   "metadata": {},
   "source": [
    "|      |    x   |     y    |     s1    |      s2      |   Solution  |\n",
    "| :--: | :----: | :------: | :------:  |  :--------:  | :---------: |\n",
    "|  z   |   0    |     0    |   0.75    |      0.5     |     24      |\n",
    "|  y   |   0    |     1    |   0.375   |    -0.25     |     0       |\n",
    "|  x   |   1    |     0    |   -0.25   |     0.5      |     8       |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bbef9a38",
   "metadata": {},
   "source": [
    "- The solution is optimum.\n",
    "- $x = 8$, $y = 0$, $z = 24$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a86d5700",
   "metadata": {},
   "source": [
    "### JuMP Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "a4e3f435",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms\n",
      "Presolving model\n",
      "2 rows, 2 cols, 4 nonzeros\n",
      "2 rows, 2 cols, 4 nonzeros\n",
      "Presolve : Reductions: rows 2(-2); columns 2(-0); elements 4(-2)\n",
      "Solving the presolved LP\n",
      "Using EKK dual simplex solver - serial\n",
      "  Iteration        Objective     Infeasibilities num(sum)\n",
      "          0    -6.9999931588e+00 Ph1: 2(11); Du: 2(6.99999) 0s\n",
      "          1    -2.4000000000e+01 Pr: 0(0) 0s\n",
      "Solving the original LP from the solution after postsolve\n",
      "Model   status      : Optimal\n",
      "Simplex   iterations: 1\n",
      "Objective value     :  2.4000000000e+01\n",
      "HiGHS run time      :          0.00\n"
     ]
    }
   ],
   "source": [
    "using JuMP, HiGHS\n",
    "m = Model(HiGHS.Optimizer)\n",
    "@variable(m, x)\n",
    "@variable(m, y)\n",
    "@objective(m, Max, 3*x + 4*y)\n",
    "@constraint(m, 2*x + 4*y <= 16)\n",
    "@constraint(m, 3*x + 2*y <= 24)\n",
    "@constraint(m, x >= 0)\n",
    "@constraint(m, y >= 0)\n",
    "JuMP.optimize!(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "6d722e10",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Vector{Float64}:\n",
       "  8.0\n",
       " -0.0"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "JuMP.value.([x, y])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "52b81d82",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24.0"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "JuMP.objective_value(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4353773f",
   "metadata": {},
   "source": [
    "### The Dual Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ddd9041",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{aligned}\n",
    "\\max z = & 3x + 4y \\\\\n",
    "\\text{Subject to:} & \\\\\n",
    "& 2x + 4y + s_1 = 16 \\\\\n",
    "& 3x + 2y + s_2 = 24 \\\\\n",
    "& x, y, s_1, s_2 \\ge 0 \\\\\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07150925",
   "metadata": {},
   "source": [
    "__________________________________________"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50435881",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{aligned}\n",
    "\\min w = & 16a + 24b \\\\\n",
    "\\text{Subject to:} & \\\\\n",
    "& 2a + 3b \\ge 3 \\\\\n",
    "& 4a + 2b \\ge 4 \\\\\n",
    "& a \\ge 0 \\\\\n",
    "& b \\ge 0 \\\\\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "233bb7fd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms\n",
      "Presolving model\n",
      "2 rows, 2 cols, 4 nonzeros\n",
      "2 rows, 2 cols, 4 nonzeros\n",
      "Presolve : Reductions: rows 2(-2); columns 2(-0); elements 4(-2)\n",
      "Solving the presolved LP\n",
      "Using EKK dual simplex solver - serial\n",
      "  Iteration        Objective     Infeasibilities num(sum)\n",
      "          0     0.0000000000e+00 Pr: 2(7) 0s\n",
      "          2     2.4000000000e+01 Pr: 0(0) 0s\n",
      "Solving the original LP from the solution after postsolve\n",
      "Model   status      : Optimal\n",
      "Simplex   iterations: 2\n",
      "Objective value     :  2.4000000000e+01\n",
      "HiGHS run time      :          0.00\n"
     ]
    }
   ],
   "source": [
    "using JuMP, HiGHS\n",
    "d = Model(HiGHS.Optimizer)\n",
    "@variable(d, a)\n",
    "@variable(d, b)\n",
    "@objective(d, Min, 16*a + 24*b)\n",
    "@constraint(d, 2*a + 3*b >= 3)\n",
    "@constraint(d, 4*a + 2*b >= 4)\n",
    "@constraint(d, a >= 0)\n",
    "@constraint(d, b >= 0)\n",
    "JuMP.optimize!(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "18a8a4c9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Vector{Float64}:\n",
       " 0.7499999999999999\n",
       " 0.5000000000000001"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "JuMP.value.([a, b])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "00b5461e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24.0"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "JuMP.objective_value(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffd93d46",
   "metadata": {},
   "source": [
    "- $a = 0.75$\n",
    "- $b = 0.5$\n",
    "- $w = z = 24$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8eaea51e",
   "metadata": {},
   "source": [
    "### Simplex solution of dual problem "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b7c476d",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{aligned}\n",
    "\\min w = & 16a + 24b \\\\\n",
    "\\text{Subject to:} & \\\\\n",
    "& 2a + 3b \\ge 3 \\\\\n",
    "& 4a + 2b \\ge 4 \\\\\n",
    "& a \\ge 0 \\\\\n",
    "& b \\ge 0 \\\\\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "831f4763",
   "metadata": {},
   "source": [
    "_____________________"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe47692e",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{aligned}\n",
    "\\min w = & 16a + 24b + MR_1 + MR_2 \\\\\n",
    "\\text{Subject to:} & \\\\\n",
    "& 2a + 3b - s_1 + R_1 = 3 \\\\\n",
    "& 4a + 2b - s_2 + R_2 = 4 \\\\\n",
    "& a, b, s_1, s_2, R_1, R_2 \\ge 0 \\\\\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22f832f2",
   "metadata": {},
   "source": [
    "|      |   a     |   b    |   s1   |   s2   |   R1   |    R2   |  Solution   |\n",
    "| :--: | :---:   | :--:   | :---:  | :---:  | :---:  | :----:  | :-------:   |\n",
    "|   z  |  -16    |  -24   |   0    |   0    |   -M   |   -M    |     0       |\n",
    "|  R1  |    2    |   3    |   -1   |   0    |    1   |    0    |     3       |\n",
    "|  R2  |    4    |   2    |   0    |  -1    |    0   |    1    |     4       |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3a5a9ab",
   "metadata": {},
   "source": [
    "|      |   a      |   b     |   s1   |   s2   |   R1   |    R2   |  Solution   |\n",
    "| :--: | :---:    | :--:    | :---:  | :---:  | :---:  | :----:  | :-------:   |\n",
    "|   z  |  -16+6M  |  -24+5M |   -M   |  -M    |    0   |    0    |     7M      |\n",
    "|  R1  |    2     |   3     |   -1   |   0    |    1   |    0    |     3       |\n",
    "|  R2  |    4     |   2     |   0    |  -1    |    0   |    1    |     4       |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "2c16c0ba",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$ \\begin{equation}\n",
       "\\left[\n",
       "\\begin{array}{c}\n",
       "-16 + 6 M \\\\\n",
       "-24 + 5 M \\\\\n",
       " - M \\\\\n",
       " - M \\\\\n",
       "0 \\\\\n",
       "0 \\\\\n",
       "7 M \\\\\n",
       "\\end{array}\n",
       "\\right]\n",
       "\\end{equation}\n",
       " $$"
      ],
      "text/plain": [
       "7-element Vector{Num}:\n",
       " -16 + 6M\n",
       " -24 + 5M\n",
       "       -M\n",
       "       -M\n",
       "        0\n",
       "        0\n",
       "       7M"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using Symbolics \n",
    "Symbolics.@variables M \n",
    "z = [-16, -24, 0, 0, -M, -M, 0]\n",
    "R1 = [2, 3, -1, 0, 1, 0, 3]\n",
    "R2 = [4, 2, 0, -1, 0, 1, 4]\n",
    "z + M*R1 + M*R2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "960176dd",
   "metadata": {},
   "source": [
    "- $a$ enters\n",
    "- Ratios are $3/2 = 1.5$ and $4/4=1$\n",
    "- $R_2$ exits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "c2400011",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7-element Vector{Float64}:\n",
       "  1.0\n",
       "  0.5\n",
       "  0.0\n",
       " -0.25\n",
       "  0.0\n",
       "  0.25\n",
       "  1.0"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = R2 / 4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35a9c428",
   "metadata": {},
   "source": [
    "|      |   a      |   b     |   s1   |   s2   |   R1   |    R2   |  Solution   |\n",
    "| :--: | :---:    | :--:    | :---:  | :---:  | :---:  | :----:  | :-------:   |\n",
    "|   z  |  -16+6M  |  -24+5M |   -M   |  -M    |    0   |    0    |     7M      |\n",
    "|  R1  |    2     |   3     |   -1   |   0    |    1   |    0    |     3       |\n",
    "|  a   |    1     |  0.5    |    0   | -0.25  |    0   |  0.25   |     1       |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "02184595",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7-element Vector{Float64}:\n",
       "  0.0\n",
       "  2.0\n",
       " -1.0\n",
       "  0.5\n",
       "  1.0\n",
       " -0.5\n",
       "  1.0"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[2, 3, -1, 0, 1, 0, 3] + (-2) * a"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1809ab7e",
   "metadata": {},
   "source": [
    "|      |   a      |   b     |   s1   |   s2   |   R1   |    R2   |  Solution   |\n",
    "| :--: | :---:    | :--:    | :---:  | :---:  | :---:  | :----:  | :-------:   |\n",
    "|   z  |  -16+6M  |  -24+5M |   -M   |  -M    |    0   |    0    |     7M      |\n",
    "|  R1  |    0     |   2     |   -1   |   0.5  |    1   |  -0.5   |     1       |\n",
    "|  a   |    1     |  0.5    |    0   | -0.25  |    0   |  0.25   |     1       |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "fea2c7a1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$ \\begin{equation}\n",
       "\\left[\n",
       "\\begin{array}{c}\n",
       "0 \\\\\n",
       "-24 + 5 M + 0.5 \\left( 16 - 6 M \\right) \\\\\n",
       " - M \\\\\n",
       " - M - 0.25 \\left( 16 - 6 M \\right) \\\\\n",
       "0 \\\\\n",
       "0.25 \\left( 16 - 6 M \\right) \\\\\n",
       "16 + M \\\\\n",
       "\\end{array}\n",
       "\\right]\n",
       "\\end{equation}\n",
       " $$"
      ],
      "text/plain": [
       "7-element Vector{Num}:\n",
       "            0\n",
       " -24 + 5M + 0.5(16 - 6M)\n",
       "           -M\n",
       "       -M - 0.25(16 - 6M)\n",
       "            0.0\n",
       "            0.25(16 - 6M)\n",
       "       16 + M"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[-16+6M, -24+5M, -M, -M, 0, 0, 7M] + (16-6M) * a"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b02af71",
   "metadata": {},
   "source": [
    "|      |   a      |   b     |   s1   |   s2     |   R1   |    R2   |  Solution   |\n",
    "| :--: | :---:    | :--:    | :---:  | :---:    | :---:  | :----:  | :-------:   |\n",
    "|   z  |    0     | -16+2M  |   -M   |  -4+0.5M |    0   |  4-1.5M |    16+M     |\n",
    "|  R1  |    0     |   2     |   -1   |   0.5    |    1   |  -0.5   |     1       |\n",
    "|  a   |    1     |  0.5    |    0   | -0.25    |    0   |  0.25   |     1       |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "8300b00f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-4.0"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "16 * -0.25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "56cfa539",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.5"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "-6 * -0.25"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "320343f8",
   "metadata": {},
   "source": [
    "- $b$ enters\n",
    "- Ratios are $1/2 = 0.5$, $1/0.5=2$\n",
    "- $R_1$ exits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "f6216410",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7-element Vector{Float64}:\n",
       "  0.0\n",
       "  1.0\n",
       " -0.5\n",
       "  0.25\n",
       "  0.5\n",
       " -0.25\n",
       "  0.5"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = [0, 2, -1, 0.5, 1, -0.5, 1] / 2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a284ced",
   "metadata": {},
   "source": [
    "|      |   a      |   b     |   s1   |   s2     |   R1   |    R2   |  Solution   |\n",
    "| :--: | :---:    | :--:    | :---:  | :---:    | :---:  | :----:  | :-------:   |\n",
    "|   z  |    0     | -16+2M  |   -M   |  -4+0.5M |    0   |  4-1.5M |    16+M     |\n",
    "|  b   |    0     |   1     |  -0.5  |   0.25   |  0.5   |  -0.25  |     0.5     |\n",
    "|  a   |    1     |  0.5    |    0   | -0.25    |    0   |  0.25   |     1       |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "cbce3e9c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7-element Vector{Float64}:\n",
       "  1.0\n",
       "  0.0\n",
       "  0.25\n",
       " -0.375\n",
       " -0.25\n",
       "  0.375\n",
       "  0.75"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1, 0.5, 0, -0.25, 0, 0.25, 1] + (-1/2)*b"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f84e590",
   "metadata": {},
   "source": [
    "|      |   a      |   b     |   s1   |   s2     |   R1   |    R2   |  Solution   |\n",
    "| :--: | :---:    | :--:    | :---:  | :---:    | :---:  | :----:  | :-------:   |\n",
    "|   z  |    0     | -16+2M  |   -M   |  -4+0.5M |    0   |  4-1.5M |    16+M     |\n",
    "|  b   |    0     |   1     |  -0.5  |   0.25   |  0.5   |  -0.25  |     0.5     |\n",
    "|  a   |    1     |   0     |  0.25  | -0.375   | -0.25  |  0.375  |     0.75    |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "483c0837",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$ \\begin{equation}\n",
       "\\left[\n",
       "\\begin{array}{c}\n",
       "0 \\\\\n",
       "0 \\\\\n",
       " - M - 0.5 \\left( 16 - 2 M \\right) \\\\\n",
       "-4 + 0.5 M + 0.25 \\left( 16 - 2 M \\right) \\\\\n",
       "0.5 \\left( 16 - 2 M \\right) \\\\\n",
       "4 - 1.5 M - 0.25 \\left( 16 - 2 M \\right) \\\\\n",
       "16 + M + 0.5 \\left( 16 - 2 M \\right) \\\\\n",
       "\\end{array}\n",
       "\\right]\n",
       "\\end{equation}\n",
       " $$"
      ],
      "text/plain": [
       "7-element Vector{Num}:\n",
       "          0.0\n",
       "          0\n",
       "     -M - 0.5(16 - 2M)\n",
       "     -4 + 0.5M + 0.25(16 - 2M)\n",
       "          0.5(16 - 2M)\n",
       "      4 - 1.5M - 0.25(16 - 2M)\n",
       " 16 + M + 0.5(16 - 2M)"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[0, -16+2M, -M, -4+0.5M, 0, 4-1.5M, 16+M] + (16-2M) * b"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bdf57adb",
   "metadata": {},
   "source": [
    "|      |   a      |   b     |   s1   |   s2     |   R1   |    R2   |  Solution   |\n",
    "| :--: | :---:    | :--:    | :---:  | :---:    | :---:  | :----:  | :-------:   |\n",
    "|   z  |    0     |   0     |  -8    |  0       | 8-M    |   -M    |     24      |\n",
    "|  b   |    0     |   1     |  -0.5  |   0.25   |  0.5   |  -0.25  |     0.5     |\n",
    "|  a   |    1     |   0     |  0.25  | -0.375   | -0.25  |  0.375  |     0.75    |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f45ab38",
   "metadata": {},
   "source": [
    "- This table gives the optimal solution\n",
    "- $b = 0.5$\n",
    "- $a = 0.75$\n",
    "- $w = 24$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d480a0b1",
   "metadata": {},
   "source": [
    "## Primal Dual Optimal Tables "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f181296b",
   "metadata": {},
   "source": [
    "### Primal "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dabd4652",
   "metadata": {},
   "source": [
    "|      |    x   |     y    |     s1    |      s2      |   Solution  |\n",
    "| :--: | :----: | :------: | :------:  |  :--------:  | :---------: |\n",
    "|  z   |   0    |     0    |   0.75    |      0.5     |     24      |\n",
    "|  y   |   0    |     1    |   0.375   |    -0.25     |     0       |\n",
    "|  x   |   1    |     0    |   -0.25   |     0.5      |     8       |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69f1df77",
   "metadata": {},
   "source": [
    "### Dual"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adfd75ad",
   "metadata": {},
   "source": [
    "|      |   a      |   b     |   s1   |   s2     |   R1   |    R2   |  Solution   |\n",
    "| :--: | :---:    | :--:    | :---:  | :---:    | :---:  | :----:  | :-------:   |\n",
    "|   z  |    0     |   0     |  -8    |  0       | 8-M    |   -M    |     24      |\n",
    "|  b   |    0     |   1     |  -0.5  |   0.25   |  0.5   |  -0.25  |     0.5     |\n",
    "|  a   |    1     |   0     |  0.25  | -0.375   | -0.25  |  0.375  |     0.75    |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2d20f7ed",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.10.0-beta3",
   "language": "julia",
   "name": "julia-1.10"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}