{ "cells": [ { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "*************************************\n", "The Simplex Method in Matrix Notation\n", "*************************************" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 6.1\n", "============\n", "\n", "(a)\n", "---\n", "\n", ".. math::\n", "\n", " \\mathcal{B} = \\{ 3, 1 \\}\n", " \\quad \\land \\quad\n", " \\mathcal{N} = \\{ 2, 4, 5 \\}\n", "\n", "(b)\n", "---\n", "\n", ".. math::\n", "\n", " x^*_\\mathcal{B} =\n", " \\begin{bmatrix} x^*_3\\\\ x^*_1 \\end{bmatrix} =\n", " \\begin{bmatrix} 2\\\\ 0 \\end{bmatrix}\n", "\n", "(c)\n", "---\n", "\n", ".. math::\n", "\n", " z^*_\\mathcal{N} = -c_\\mathcal{N} =\n", " \\begin{bmatrix} z^*_4\\\\ z^*_2 \\end{bmatrix} =\n", " \\begin{bmatrix} 3\\\\ -2 \\end{bmatrix}\n", "\n", "(d)\n", "---\n", "\n", ".. math::\n", "\n", " B^{-1} N =\n", " \\begin{bmatrix}\n", " 1 & -4 & 2\\\\\n", " -2 & 1 & -3\n", " \\end{bmatrix}\n", "\n", "(e)\n", "---\n", "\n", "Applying (6.10) shows that the associated current primal solution is feasible.\n", "\n", "(f)\n", "---\n", "\n", "Since :math:`z^*_\\mathcal{N}` has some negative components, the current\n", "solution is not optimal.\n", "\n", "(g)\n", "---\n", "\n", "The dictionary is degenerate because one of its basic variables is zero." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 6.2\n", "============\n", "\n", "(a)\n", "---\n", "\n", ".. math::\n", "\n", " \\mathcal{B} = \\{ 6, 7 \\}\n", " \\quad \\land \\quad\n", " B = \\begin{bmatrix} 1 & 0\\\\ 0 & 1 \\end{bmatrix}\n", "\n", "(b)\n", "---\n", "\n", ".. math::\n", "\n", " \\mathcal{N} = \\{ 1, 2, 3, 4, 5 \\}\n", " \\quad \\land \\quad\n", " N =\n", " \\begin{bmatrix}\n", " 1 & 2 & 3 & 4 & 5\\\\\n", " 7 & 5 & -3 & -2 & 0\n", " \\end{bmatrix}\n", "\n", "(c)\n", "---\n", "\n", ".. math::\n", "\n", " b = \\begin{bmatrix} 2\\\\ 0 \\end{bmatrix}\n", "\n", "(d)\n", "---\n", "\n", ".. math::\n", "\n", " c_\\mathcal{B} = \\begin{bmatrix} 0\\\\ 0 \\end{bmatrix}\n", "\n", "(e)\n", "---\n", "\n", ".. math::\n", "\n", " c_\\mathcal{N} = \\begin{bmatrix} 1\\\\ 2\\\\ 4\\\\ 8\\\\ 16 \\end{bmatrix}\n", "\n", "(f)\n", "---\n", "\n", ".. math::\n", "\n", " B^{-1} N = N\n", "\n", "(g)\n", "---\n", "\n", ".. math::\n", "\n", " x^*_\\mathcal{B} = B^{-1} b = b\n", "\n", "(h)\n", "---\n", "\n", ".. math::\n", "\n", " \\zeta^* = c_\\mathcal{B}^\\top B^{-1} b = \\boldsymbol{0}\n", "\n", "(i)\n", "---\n", "\n", ".. math::\n", "\n", " z^*_\\mathcal{N} =\n", " \\left( B^{-1} N \\right)^\\top c_\\mathcal{B} - c_\\mathcal{N} =\n", " -c_\\mathcal{N} = \\begin{bmatrix} -1\\\\ -2\\\\ -4\\\\ -8\\\\ -16 \\end{bmatrix}\n", "\n", "(j)\n", "---\n", "\n", "The primal dictionary in succinct form (6.10) is\n", "\n", ".. math::\n", "\n", " \\zeta &= \\zeta^* - {z^*_\\mathcal{N}}^\\top x_\\mathcal{N} =\n", " \\boldsymbol{0} -\n", " \\begin{bmatrix} -1\\\\ -2\\\\ -4\\\\ -8\\\\ -16 \\end{bmatrix}^\\top\n", " \\begin{bmatrix} x_1\\\\ x_2\\\\ x_3\\\\ x_4\\\\ x_5 \\end{bmatrix} =\n", " x_1 + 2 x_2 + 4 x_3 + 8 x_4 + 16 x_5\n", "\n", ".. math::\n", "\n", " x_\\mathcal{B} &= x^*_\\mathcal{B} - B^{-1} N x_\\mathcal{N}\\\\\n", " &= \\begin{bmatrix} 2\\\\ 0 \\end{bmatrix} -\n", " \\begin{bmatrix}\n", " 1 & 2 & 3 & 4 & 5\\\\\n", " 7 & 5 & -3 & -2 & 0\n", " \\end{bmatrix} \\begin{bmatrix} x_1\\\\ x_2\\\\ x_3\\\\ x_4\\\\ x_5 \\end{bmatrix}\\\\\n", " \\begin{bmatrix} x_6\\\\ x_7 \\end{bmatrix}\n", " &= \\begin{bmatrix}\n", " 2 - x_1 - 2 x_2 - 4 x_3 - 8 x_4 - 16 x_5\\\\\n", " -7 x_1 - 5 x_2 + 3 x_3 + 2 x_4\n", " \\end{bmatrix}." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 6.3\n", "============\n", "\n", "Rewriting :ref:`Exercise 2.1 ` into matrix form\n", "yields\n", "\n", ".. math::\n", "\n", " \\mathcal{B} &= \\{ 5, 6 \\} \\quad & \\quad \\mathcal{N} &= \\{ 1, 2, 3, 4 \\}\\\\\n", " B &= \\mathbf{I}_2 \\quad & \\quad\n", " N &= \\begin{bmatrix} 2 & 1 & 1 & 3\\\\ 1 & 3 & 1 & 2 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= b = \\begin{bmatrix} 5\\\\ 3 \\end{bmatrix} \\quad & \\quad\n", " z^*_\\mathcal{N} &= -c_\\mathcal{N} =\n", " \\begin{bmatrix} -6\\\\ -8\\\\ -5\\\\ -9 \\end{bmatrix}.\n", "\n", "Iteration 1\n", "-----------\n", "\n", "Step 1\n", " Since :math:`z^*_\\mathcal{N}` has some negative components, the current\n", " solution is not optimal.\n", "\n", "Step 2\n", " Applying Bland's rule restricts the entering variable index to\n", " :math:`j = 1 \\in \\mathcal{N}`.\n", "\n", "Step 3\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} = B^{-1} N e_j =\n", " \\begin{bmatrix} 2 & 1 & 1 & 3\\\\ 1 & 3 & 1 & 2 \\end{bmatrix}\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 2\\\\ 1 \\end{bmatrix}.\n", "\n", "Step 4\n", " The primal step length is\n", "\n", " .. math::\n", "\n", " t = \\left( \\max_{i \\in \\mathcal{B}} \\frac{\\Delta x_i}{x^*_i} \\right)^{-1} =\n", " \\left( \\max \\left\\{ \\frac{2}{5}, \\frac{1}{3} \\right\\} \\right)^{-1} =\n", " \\frac{5}{2}.\n", "\n", "Step 5\n", " The leaving variable index is :math:`i = 5 \\in \\mathcal{B}`.\n", "\n", "Step 6\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top \\mathbf{e}_i =\n", " -\\begin{bmatrix} 2 & 1\\\\ 1 & 3\\\\ 1 & 1\\\\ 3 & 2 \\end{bmatrix}\n", " \\begin{bmatrix} 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -2\\\\ -1\\\\ -1\\\\ -3 \\end{bmatrix}.\n", "\n", "Step 7\n", " The dual step length is\n", "\n", " .. math::\n", "\n", " s = \\frac{z^*_j}{\\Delta z_j} = \\frac{-6}{-2} = 3.\n", "\n", "Step 8\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} \\leftarrow\n", " x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 5\\\\ 3 \\end{bmatrix} -\n", " \\frac{5}{2} \\begin{bmatrix} 2\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ \\frac{1}{2} \\end{bmatrix}\n", " \\quad \\land \\quad\n", " x^*_j \\leftarrow t = \\frac{5}{2}\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} \\leftarrow\n", " z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} -6\\\\ -8\\\\ -5\\\\ -9 \\end{bmatrix} -\n", " 3 \\begin{bmatrix} -2\\\\ -1\\\\ -1\\\\ -3 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ -5\\\\ -2\\\\ 0 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " z^*_i \\leftarrow s = 3.\n", "\n", "Step 9\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 1, 6 \\} \\quad & \\quad \\mathcal{N} &= \\{ 5, 2, 3, 4 \\}\\\\\n", " B &= \\begin{bmatrix} 2 & 0\\\\ 1 & 1 \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 1 & 1 & 1 & 3\\\\ 0 & 3 & 1 & 2 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &=\n", " \\begin{bmatrix} \\frac{5}{2}\\\\ \\frac{1}{2} \\end{bmatrix} \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} 3\\\\ -5\\\\ -2\\\\ 0 \\end{bmatrix}.\n", "\n", "Iteration 2\n", "-----------\n", "\n", "Step 1\n", " Since :math:`z^*_\\mathcal{N}` has some negative components, the current\n", " solution is not optimal.\n", "\n", "Step 2\n", " Applying Bland's rule restricts the entering variable index to\n", " :math:`j = 2 \\in \\mathcal{N}`.\n", "\n", "Step 3\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} = B^{-1} N e_j =\n", " \\left(\n", " \\frac{1}{2}\n", " \\begin{bmatrix} 1 & 1 & 1 & 3\\\\ -1 & 5 & 1 & 1 \\end{bmatrix}\n", " \\right)\n", " \\begin{bmatrix} 0\\\\ 1\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} \\frac{1}{2}\\\\ \\frac{5}{2} \\end{bmatrix}.\n", "\n", "Step 4\n", " The primal step length is\n", "\n", " .. math::\n", "\n", " t = \\left( \\max_{i \\in \\mathcal{B}} \\frac{\\Delta x_i}{x^*_i} \\right)^{-1} =\n", " \\left( \\max \\left\\{\n", " \\frac{0.5}{2.5}, \\frac{2.5}{0.5}\n", " \\right\\} \\right)^{-1} =\n", " \\frac{1}{5}.\n", "\n", "Step 5\n", " The leaving variable index is :math:`i = 6 \\in \\mathcal{B}`.\n", "\n", "Step 6\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top \\mathbf{e}_i =\n", " -\\left(\n", " \\frac{1}{2}\n", " \\begin{bmatrix} 1 & -1\\\\ 1 & 5\\\\ 1 & 1\\\\ 3 & 1 \\end{bmatrix}\n", " \\right)\n", " \\begin{bmatrix} 0\\\\ 1 \\end{bmatrix} =\n", " \\frac{1}{2} \\begin{bmatrix} 1\\\\ -5\\\\ -1\\\\ -1 \\end{bmatrix}.\n", "\n", "Step 7\n", " The dual step length is\n", "\n", " .. math::\n", "\n", " s = \\frac{z^*_j}{\\Delta z_j} = \\frac{-5}{-5 / 2} = 2.\n", "\n", "Step 8\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} \\leftarrow\n", " x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} \\frac{5}{2}\\\\ \\frac{1}{2} \\end{bmatrix} -\n", " \\frac{1}{5} \\begin{bmatrix} \\frac{1}{2}\\\\ \\frac{5}{2} \\end{bmatrix} =\n", " \\begin{bmatrix} \\frac{12}{5}\\\\ 0 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " x^*_j \\leftarrow t = \\frac{1}{5}\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} \\leftarrow\n", " z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 3\\\\ -5\\\\ -2\\\\ 0 \\end{bmatrix} -\n", " 2 \\left(\n", " \\frac{1}{2} \\begin{bmatrix} 1\\\\ -5\\\\ -1\\\\ -1 \\end{bmatrix}\n", " \\right) =\n", " \\begin{bmatrix} 2\\\\ 0\\\\ -1\\\\ 1 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " z^*_i \\leftarrow s = 2.\n", "\n", "Step 9\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 1, 2 \\} \\quad & \\quad \\mathcal{N} &= \\{ 5, 6, 3, 4 \\}\\\\\n", " B &= \\begin{bmatrix} 2 & 1\\\\ 1 & 3 \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 1 & 0 & 1 & 3\\\\ 0 & 1 & 1 & 2 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &=\n", " \\begin{bmatrix} \\frac{12}{5}\\\\ \\frac{1}{5} \\end{bmatrix} \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} 2\\\\ 2\\\\ -1\\\\ 1 \\end{bmatrix}.\n", "\n", "Iteration 3\n", "-----------\n", "\n", "Step 1\n", " Since :math:`z^*_\\mathcal{N}` has some negative components, the current\n", " solution is not optimal.\n", "\n", "Step 2\n", " Applying Bland's rule restricts the entering variable index to\n", " :math:`j = 3 \\in \\mathcal{N}`.\n", "\n", "Step 3\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} = B^{-1} N e_j =\n", " \\left(\n", " \\frac{1}{5}\n", " \\begin{bmatrix} 3 & -1 & 2 & 7\\\\ -1 & 2 & 1 & 1 \\end{bmatrix}\n", " \\right)\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} \\frac{2}{5}\\\\ \\frac{1}{5} \\end{bmatrix}.\n", "\n", "Step 4\n", " The primal step length is\n", "\n", " .. math::\n", "\n", " t = \\left( \\max_{i \\in \\mathcal{B}} \\frac{\\Delta x_i}{x^*_i} \\right)^{-1} =\n", " \\left( \\max \\left\\{\n", " \\frac{0.4}{2.4}, \\frac{0.2}{0.2}\n", " \\right\\} \\right)^{-1} =\n", " 1.\n", "\n", "Step 5\n", " The leaving variable index is :math:`i = 2 \\in \\mathcal{B}`.\n", "\n", "Step 6\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top \\mathbf{e}_i =\n", " -\\left(\n", " \\frac{1}{5}\n", " \\begin{bmatrix} 3 & -1\\\\ -1 & 2\\\\ 2 & 1\\\\ 7 & 1 \\end{bmatrix}\n", " \\right)\n", " \\begin{bmatrix} 0\\\\ 1 \\end{bmatrix} =\n", " \\frac{1}{5} \\begin{bmatrix} 1\\\\ -2\\\\ -1\\\\ -1 \\end{bmatrix}.\n", "\n", "Step 7\n", " The dual step length is\n", "\n", " .. math::\n", "\n", " s = \\frac{z^*_j}{\\Delta z_j} = \\frac{-1}{-1 / 5} = 5.\n", "\n", "Step 8\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} \\leftarrow\n", " x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} \\frac{12}{5}\\\\ \\frac{1}{5} \\end{bmatrix} -\n", " (1) \\begin{bmatrix} \\frac{2}{5}\\\\ \\frac{1}{5} \\end{bmatrix} =\n", " \\begin{bmatrix} 2\\\\ 0 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " x^*_j \\leftarrow t = 1\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} \\leftarrow\n", " z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 2\\\\ 2\\\\ -1\\\\ 1 \\end{bmatrix} -\n", " 5 \\left(\n", " \\frac{1}{5} \\begin{bmatrix} 1\\\\ -2\\\\ -1\\\\ -1 \\end{bmatrix}\n", " \\right) =\n", " \\begin{bmatrix} 1\\\\ 4\\\\ 0\\\\ 2 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " z^*_i \\leftarrow s = 5.\n", "\n", "Step 9\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 1, 3 \\} \\quad & \\quad \\mathcal{N} &= \\{ 5, 6, 2, 4 \\}\\\\\n", " B &= \\begin{bmatrix} 2 & 1\\\\ 1 & 1 \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 1 & 0 & 1 & 3\\\\ 0 & 1 & 3 & 2 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &=\n", " \\begin{bmatrix} 2\\\\ 1 \\end{bmatrix} \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} 1\\\\ 4\\\\ 5\\\\ 2 \\end{bmatrix}.\n", "\n", "Iteration 4\n", "-----------\n", "\n", "Step 1\n", " Since :math:`z^*_\\mathcal{N}` has all non-negative components, the current\n", " solution is optimal. The optimal objective function value is\n", "\n", " .. math::\n", "\n", " \\zeta^* = 6 x_1^* + 8 x_2^* + 5 x_3^* + 9 x_4^* = 17." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 6.4\n", "============\n", "\n", "Rewriting :ref:`Exercise 2.4 ` into matrix form\n", "yields\n", "\n", ".. math::\n", "\n", " \\mathcal{B} &= \\{ 4, 5 \\} \\quad & \\quad \\mathcal{N} &= \\{ 1, 2, 3 \\}\\\\\n", " B &= \\mathbf{I}_2 \\quad & \\quad\n", " N &= \\begin{bmatrix} 2 & -5 & 1\\\\ 2 & -1 & 2 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= b = \\begin{bmatrix} -5\\\\ 4 \\end{bmatrix} \\quad & \\quad\n", " z^*_\\mathcal{N} &= -c_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ 3\\\\ 1 \\end{bmatrix}.\n", "\n", "Iteration 1\n", "-----------\n", "\n", "Step 1\n", " Since :math:`x^*_\\mathcal{B}` has some negative components, the current\n", " solution is not optimal.\n", "\n", "Step 2\n", " Applying Bland's rule restricts the entering variable index to\n", " :math:`i = 4 \\in \\mathcal{B}`.\n", "\n", "Step 3\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top \\mathbf{e}_i =\n", " -\\begin{bmatrix} 2 & 2\\\\ -5 & -1\\\\ 1 & 2 \\end{bmatrix}\n", " \\begin{bmatrix} 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -2\\\\ 5\\\\ -1 \\end{bmatrix}.\n", "\n", "Step 4\n", " The dual step length is\n", "\n", " .. math::\n", "\n", " s = \\left( \\max_{j \\in \\mathcal{N}} \\frac{\\Delta z_j}{z^*_j} \\right)^{-1} =\n", " \\left( \\max \\left\\{\n", " \\frac{-2}{1}, \\frac{5}{3}, \\frac{-1}{1}\n", " \\right\\} \\right)^{-1} =\n", " \\frac{3}{5}.\n", "\n", "Step 5\n", " The leaving variable index is :math:`j = 2 \\in \\mathcal{N}`.\n", "\n", "Step 6\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} = B^{-1} N e_j =\n", " \\begin{bmatrix} 2 & -5 & 1\\\\ 2 & -1 & 2 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -5\\\\ -1 \\end{bmatrix}.\n", "\n", "Step 7\n", " The primal step length is\n", "\n", " .. math::\n", "\n", " t = \\frac{x^*_i}{\\Delta x_i} = \\frac{-5}{-5} = 1.\n", "\n", "Step 8\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} \\leftarrow\n", " x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} -5\\\\ 4 \\end{bmatrix} -\n", " (1) \\begin{bmatrix} -5\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 5 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " x^*_j \\leftarrow t = 1\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} \\leftarrow\n", " z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ 3\\\\ 1 \\end{bmatrix} -\n", " \\frac{3}{5} \\begin{bmatrix} -2\\\\ 5\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} \\frac{11}{5}\\\\ 0\\\\ \\frac{8}{5} \\end{bmatrix}\n", " \\quad \\land \\quad\n", " z^*_i \\leftarrow s = \\frac{3}{5}.\n", "\n", "Step 9\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 2, 5 \\} \\quad & \\quad \\mathcal{N} &= \\{ 1, 4, 3 \\}\\\\\n", " B &= \\begin{bmatrix} -5 & 0\\\\ -1 & 1 \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 2 & 1 & 1\\\\ 2 & 0 & 2 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} 1\\\\ 5 \\end{bmatrix} \\quad & \\quad\n", " z^*_\\mathcal{N} &=\n", " \\begin{bmatrix} \\frac{11}{5}\\\\ \\frac{3}{5}\\\\ \\frac{8}{5} \\end{bmatrix}.\n", "\n", "Iteration 2\n", "-----------\n", "\n", "Step 1\n", " Since :math:`x^*_\\mathcal{B}` has all non-negative components, the current\n", " solution is optimal. The optimal objective function value is\n", "\n", " .. math::\n", "\n", " \\zeta^* = -x_1^* - 3 x_2^* - x_3^* = -3." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 6.5\n", "============\n", "\n", "Rewriting :ref:`Exercise 2.3 ` into matrix form\n", "yields\n", "\n", ".. math::\n", "\n", " \\mathcal{B} &= \\{ 4, 5 \\} \\quad & \\quad \\mathcal{N} &= \\{ 1, 2, 3 \\}\\\\\n", " B &= \\mathbf{I}_2 \\quad & \\quad\n", " N &= \\begin{bmatrix} -1 & -1 & -1\\\\ 2 & -1 & 1 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= b = \\begin{bmatrix} -2\\\\ 1 \\end{bmatrix} \\quad & \\quad\n", " z^*_\\mathcal{N} &= -c_\\mathcal{N} =\n", " \\begin{bmatrix} -2\\\\ 6\\\\ 0 \\end{bmatrix}.\n", "\n", "Since both :math:`b` and :math:`c_\\mathcal{N}` have some negative components,\n", "arbitrarily set\n", ":math:`c_\\mathcal{N} = \\begin{bmatrix} -1\\\\ -1\\\\ -1 \\end{bmatrix}` to make the\n", "problem dual feasible.\n", "\n", "Iteration 1\n", "-----------\n", "\n", "Step 1\n", " Since :math:`x^*_\\mathcal{B}` has some negative components, the current\n", " solution is not optimal.\n", "\n", "Step 2\n", " Applying Bland's rule restricts the entering variable index to\n", " :math:`i = 4 \\in \\mathcal{B}`.\n", "\n", "Step 3\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top \\mathbf{e}_i =\n", " -\\begin{bmatrix} -1 & 2\\\\ -1 & -1\\\\ -1 & 1 \\end{bmatrix}\n", " \\begin{bmatrix} 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ 1\\\\ 1 \\end{bmatrix}.\n", "\n", "Step 4\n", " The dual step length is\n", "\n", " .. math::\n", "\n", " s = \\left( \\max_{j \\in \\mathcal{N}} \\frac{\\Delta z_j}{z^*_j} \\right)^{-1} =\n", " \\left( \\max \\left\\{\n", " \\frac{1}{1}, \\frac{1}{1}, \\frac{1}{1}\n", " \\right\\} \\right)^{-1} = 1.\n", "\n", "Step 5\n", " Applying Bland's rule restricts the leaving variable index to\n", " :math:`j = 1 \\in \\mathcal{N}`.\n", "\n", "Step 6\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} = B^{-1} N e_j =\n", " \\begin{bmatrix} -1 & -1 & -1\\\\ 2 & -1 & 1 \\end{bmatrix}\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -1\\\\ 2 \\end{bmatrix}.\n", "\n", "Step 7\n", " The primal step length is\n", "\n", " .. math::\n", "\n", " t = \\frac{x^*_i}{\\Delta x_i} = \\frac{-2}{-1} = 2.\n", "\n", "Step 8\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} \\leftarrow\n", " x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} -2\\\\ 1 \\end{bmatrix} -\n", " (2) \\begin{bmatrix} -1\\\\ 2 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ -3 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " x^*_j \\leftarrow t = 2\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} \\leftarrow\n", " z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ 1\\\\ 1 \\end{bmatrix} -\n", " (1) \\begin{bmatrix} 1\\\\ 1\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 0 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " z^*_i \\leftarrow s = 1.\n", "\n", "Step 9\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 1, 5 \\} \\quad & \\quad \\mathcal{N} &= \\{ 4, 2, 3 \\}\\\\\n", " B &= \\begin{bmatrix} -1 & 0\\\\ 2 & 1 \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 1 & -1 & -1\\\\ 0 & -1 & 1 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} 2\\\\ -3 \\end{bmatrix} \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} 1\\\\ 0\\\\ 0 \\end{bmatrix}.\n", "\n", "Iteration 2\n", "-----------\n", "\n", "Step 1\n", " Since :math:`x^*_\\mathcal{B}` has some negative components, the current\n", " solution is not optimal.\n", "\n", "Step 2\n", " Applying Bland's rule restricts the entering variable index to\n", " :math:`i = 5 \\in \\mathcal{B}`.\n", "\n", "Step 3\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top \\mathbf{e}_i =\n", " -\\begin{bmatrix} -1 & 2\\\\ 1 & -3\\\\ 1 & -1 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} -2\\\\ 3\\\\ 1 \\end{bmatrix}.\n", "\n", "Step 4\n", " The dual step length is\n", "\n", " .. math::\n", "\n", " s = \\left( \\max_{j \\in \\mathcal{N}} \\frac{\\Delta z_j}{z^*_j} \\right)^{-1} =\n", " \\left( \\max \\left\\{\n", " \\frac{-2}{1}, \\frac{3}{0}, \\frac{1}{0}\n", " \\right\\} \\right)^{-1} = 0.\n", "\n", "Step 5\n", " Applying Bland's rule restricts the leaving variable index to\n", " :math:`j = 2 \\in \\mathcal{N}`.\n", "\n", "Step 6\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} = B^{-1} N e_j =\n", " \\begin{bmatrix} -1 & 1 & 1\\\\ 2 & -3 & -1 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ -3 \\end{bmatrix}.\n", "\n", "Step 7\n", " The primal step length is\n", "\n", " .. math::\n", "\n", " t = \\frac{x^*_i}{\\Delta x_i} = \\frac{-3}{-3} = 1.\n", "\n", "Step 8\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} \\leftarrow\n", " x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 2\\\\ -3 \\end{bmatrix} -\n", " (1) \\begin{bmatrix} 1\\\\ -3 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ 0 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " x^*_j \\leftarrow t = 1\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} \\leftarrow\n", " z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 0 \\end{bmatrix} -\n", " (0) \\begin{bmatrix} -2\\\\ 3\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 0 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " z^*_i \\leftarrow s = 0.\n", "\n", "Step 9\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 1, 2 \\} \\quad & \\quad \\mathcal{N} &= \\{ 4, 5, 3 \\}\\\\\n", " B &= \\begin{bmatrix} -1 & -1\\\\ 2 & -1 \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 1 & 0 & -1\\\\ 0 & 1 & 1 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} 1\\\\ 1 \\end{bmatrix} \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} 1\\\\ 0\\\\ 0 \\end{bmatrix}.\n", "\n", "Iteration 3\n", "-----------\n", "\n", "Since :math:`x^*_\\mathcal{B}` has all non-negative components, the current\n", "solution is optimal for the modified objective. The original objective\n", "\n", ".. math::\n", "\n", " c_\\mathcal{N'} x_\\mathcal{N'} =\n", " \\begin{bmatrix} 2 & -6 & 0 \\end{bmatrix}\n", " \\begin{bmatrix} x_1\\\\ x_2\\\\ x_3 \\end{bmatrix} =\n", " 2 x_1 - 6 x_2\n", "\n", "can be reinstated by setting\n", "\n", ".. math::\n", "\n", " z^*_\\mathcal{N} =\n", " \\left( B^{-1} N \\right)^\\top c_{\\mathcal{N'} \\cap \\mathcal{B}}+\n", " \\sum_{j \\in \\mathcal{N'} \\cap \\mathcal{N}} c_j e_j =\n", " \\left(\n", " \\frac{1}{3} \\begin{bmatrix} -1 & 1 & 2\\\\ -2 & -1 & 1 \\end{bmatrix}\n", " \\right)^\\top \\begin{bmatrix} 2\\\\ -6 \\end{bmatrix} + 0 e_3 =\n", " \\frac{1}{3} \\begin{bmatrix} 10\\\\ 8\\\\ -2 \\end{bmatrix}\n", "\n", "where :math:`c_{\\mathcal{N'} \\cap \\mathcal{B}}` is a vector whose elements are\n", "zero when the corresponding variable index\n", ":math:`i \\in \\mathcal{B} \\setminus \\mathcal{N'}`.\n", "\n", "Step 1\n", " Since :math:`z^*_\\mathcal{N}` has some negative components, the current\n", " solution is not optimal.\n", "\n", "Step 2\n", " Applying Bland's rule restricts the entering variable index to\n", " :math:`j = 3 \\in \\mathcal{N}`.\n", "\n", "Step 3\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} = B^{-1} N e_j =\n", " \\frac{1}{3} \\begin{bmatrix} -1 & 1 & 2\\\\ -2 & -1 & 1 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} \\frac{2}{3}\\\\ \\frac{1}{3} \\end{bmatrix}.\n", "\n", "Step 4\n", " The primal step length is\n", "\n", " .. math::\n", "\n", " t = \\left( \\max_{i \\in \\mathcal{B}} \\frac{\\Delta x_i}{x^*_i} \\right)^{-1} =\n", " \\left( \\max \\left\\{\n", " \\frac{2 / 3}{1}, \\frac{1 / 3}{1} \\right\\}\n", " \\right)^{-1} =\n", " \\frac{3}{2}.\n", "\n", "Step 5\n", " The leaving variable index is :math:`i = 1 \\in \\mathcal{B}`.\n", "\n", "Step 6\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top \\mathbf{e}_i =\n", " -\\frac{1}{3} \\begin{bmatrix} -1 & -2\\\\ 1 & -1\\\\ 2 & 1 \\end{bmatrix}\n", " \\begin{bmatrix} 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} \\frac{1}{3}\\\\ \\frac{-1}{3}\\\\ \\frac{-2}{3} \\end{bmatrix}.\n", "\n", "Step 7\n", " The dual step length is\n", "\n", " .. math::\n", "\n", " s = \\frac{z^*_j}{\\Delta z_j} = \\frac{-2 / 3}{-2 / 3} = 1.\n", "\n", "Step 8\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} \\leftarrow\n", " x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1\\\\ 1 \\end{bmatrix} -\n", " \\frac{3}{2} \\begin{bmatrix} \\frac{2}{3}\\\\ \\frac{1}{3} \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ \\frac{1}{2} \\end{bmatrix}\n", " \\quad \\land \\quad\n", " x^*_j \\leftarrow t = \\frac{3}{2}\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} \\leftarrow\n", " z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\frac{1}{3} \\begin{bmatrix} 10\\\\ 8\\\\ -2 \\end{bmatrix} -\n", " \\frac{1}{3} \\begin{bmatrix} 1\\\\ -1\\\\ -2 \\end{bmatrix} =\n", " \\frac{1}{3} \\begin{bmatrix} 9\\\\ 9\\\\ 4 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " z^*_i \\leftarrow s = 1.\n", "\n", "Step 9\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 3, 2 \\} \\quad & \\quad \\mathcal{N} &= \\{ 4, 5, 1 \\}\\\\\n", " B &= \\begin{bmatrix} -1 & -1\\\\ 1 & -1 \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 1 & 0 & -1\\\\ 0 & 1 & 2 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &=\n", " \\begin{bmatrix} \\frac{3}{2}\\\\ \\frac{1}{2} \\end{bmatrix} \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} 3\\\\ 3\\\\ 1 \\end{bmatrix}.\n", "\n", "Iteration 4\n", "-----------\n", "\n", "Step 1\n", " Since :math:`z^*_\\mathcal{N}` has all non-negative components, the current\n", " solution is optimal. The optimal objective function value is\n", "\n", " .. math::\n", "\n", " \\zeta^* = 2 x_1^* - 6 x_2^* = -3." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 6.6\n", "============\n", "\n", "Rewriting the LP in standard form according to :cite:`burke407s1` yields\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{P} \\quad \\text{maximize} \\quad\n", " \\mathbf{c}^\\top \\mathbf{w} + \\mathbf{c}^\\top \\mathbf{l} &\\\\\n", " \\text{subject to} \\quad\n", " \\mathbf{A} \\mathbf{w} &\\leq \\mathbf{b} - \\mathbf{A} \\mathbf{l}\\\\\n", " -\\mathbf{A} \\mathbf{w} &\\leq -\\mathbf{a} + \\mathbf{A} \\mathbf{l}\\\\\n", " 0 &\\leq \\mathbf{w}\n", " \\end{aligned}\n", "\n", "where :math:`\\mathbf{w} = \\mathbf{x} - \\mathbf{l}`. Note that the constant\n", ":math:`\\mathbf{c}^\\top \\mathbf{l}` in the objective function can and will be\n", "ignored in the following analysis.\n", "\n", "The dual of :math:`\\mathcal{P}` is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{D} \\quad \\text{minimize} \\quad\n", " \\mathbf{y}_b^\\top \\left( \\mathbf{b} - \\mathbf{A} \\mathbf{l} \\right) +\n", " \\mathbf{y}_a^\\top \\left( -\\mathbf{a} + \\mathbf{A} \\mathbf{l} \\right) &\\\\\n", " \\text{subject to} \\quad\n", " \\mathbf{A}^\\top\n", " \\left( \\mathbf{y}_b - \\mathbf{y}_a \\right) &\\geq \\mathbf{c}\\\\\n", " 0 &\\leq \\mathbf{y}_a, \\mathbf{y}_b\n", " \\end{aligned}\n", " \\quad = \\quad\n", " \\begin{aligned}\n", " -\\mathcal{D} \\quad \\text{maximize} \\quad\n", " -\\mathbf{y}_b^\\top \\left( \\mathbf{b} - \\mathbf{A} \\mathbf{l} \\right) -\n", " \\mathbf{y}_a^\\top \\left( -\\mathbf{a} + \\mathbf{A} \\mathbf{l} \\right) &\\\\\n", " \\text{subject to} \\quad\n", " \\mathbf{A}^\\top\n", " \\left( \\mathbf{y}_a - \\mathbf{y}_b \\right) &\\leq -\\mathbf{c}\\\\\n", " 0 &\\leq \\mathbf{y}_a, \\mathbf{y}_b.\n", " \\end{aligned}\n", "\n", "Observe that the dual to :math:`\\mathcal{D}` is indeed :math:`\\mathcal{P}`:\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{P} \\quad \\text{minimize} \\quad\n", " -\\mathbf{c}^\\top \\mathbf{w} &\\\\\n", " \\text{subject to} \\quad\n", " -\\mathbf{A} \\mathbf{w} &\\leq -\\mathbf{b} + \\mathbf{A} \\mathbf{l}\\\\\n", " \\mathbf{A} \\mathbf{w} &\\leq \\mathbf{a} - \\mathbf{A} \\mathbf{l}\\\\\n", " 0 &\\leq \\mathbf{w}\n", " \\end{aligned}\n", " \\quad = \\quad\n", " \\begin{aligned}\n", " \\mathcal{P} \\quad \\text{maximize} \\quad\n", " \\mathbf{c}^\\top \\mathbf{w} &\\\\\n", " \\text{subject to} \\quad\n", " \\mathbf{A} \\mathbf{w} &\\leq \\mathbf{b} - \\mathbf{A} \\mathbf{l}\\\\\n", " -\\mathbf{A} \\mathbf{w} &\\leq -\\mathbf{a} + \\mathbf{A} \\mathbf{l}\\\\\n", " 0 &\\leq \\mathbf{w}.\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 6.7\n", "============\n", "\n", "Computing the gradient is not useful for this problem because the only\n", "constraints are :math:`x, y \\geq 0`. The optimization can be carried out\n", "through reasoning in 1D without loss of generality.\n", "\n", "(a)\n", "---\n", "\n", "Define\n", "\n", ".. math::\n", "\n", " p(x) &= \\min_{y \\geq 0} c^\\top x - y^\\top A x + b^\\top y\\\\\n", " &= c^\\top x + \\min_{y \\geq 0} y^\\top (b - A x)\\\\\n", " &= c^\\top x +\n", " \\begin{cases}\n", " 0 & \\text{if } Ax \\leq b\\\\\n", " -\\infty & \\text{otherwise.}\n", " \\end{cases}\n", "\n", "The primal LP is\n", "\n", ".. math::\n", "\n", " \\mathcal{P} \\quad \\max_{x \\geq 0} p(x) =\n", " \\text{maximize} \\quad c^\\top x&\\\\\n", " \\text{subject to} \\quad\n", " Ax &\\leq b\\\\\n", " 0 &\\leq x.\n", "\n", "(b)\n", "---\n", "\n", "Define\n", "\n", ".. math::\n", "\n", " d(y) &= \\max_{x \\geq 0} c^\\top x - y^\\top A x + b^\\top y\\\\\n", " &= b^\\top y + \\max_{x \\geq 0} \\left( c - A^\\top y \\right)^\\top x\\\\\n", " &= b^\\top y +\n", " \\begin{cases}\n", " 0 & \\text{if } A^\\top y \\geq c\\\\\n", " \\infty & \\text{otherwise.}\n", " \\end{cases}\n", "\n", "The dual LP is\n", "\n", ".. math::\n", "\n", " \\mathcal{D} \\quad \\min_{y \\geq 0} d(y) =\n", " \\text{minimize} \\quad b^\\top y&\\\\\n", " \\text{subject to} \\quad\n", " A^\\top y &\\geq c\\\\\n", " 0 &\\leq y." ] } ], "metadata": { "anaconda-cloud": {}, "celltoolbar": "Raw Cell Format", "kernelspec": { "display_name": "Python [default]", "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.5.2" } }, "nbformat": 4, "nbformat_minor": 1 }