{ "cells": [ { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "***********************************\n", "Sensitivity and Parametric Analyses\n", "***********************************\n", "\n", "The `Advanced Simplex Pivot Tool`_ is useful for verifying the application of\n", "the self-dual simplex method.\n", "\n", ".. _Advanced Simplex Pivot Tool: http://www.princeton.edu/~rvdb/JAVA/pivot/advanced.html\n", "\n", "3. The Parametric Self-Dual Simplex Method\n", "==========================================\n", "\n", "Figure 7.1 incorrectly lists the :math:`arg\\,max` criterion. :cite:`aengau5593`\n", "illustrates in Figure 4.2 that it is more appropriate to take the\n", ":math:`arg\\,min` and only select among the ratios with a positive denominator." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 7.1\n", "============\n", "\n", "The matrix form of the original dictionary is\n", "\n", ".. math::\n", "\n", " \\mathcal{B} &= \\{5, 6, 7\\} \\quad & \\quad \\mathcal{N} &= \\{1, 2, 3, 4\\}\\\\\n", " B &= \\mathbf{I}_3 \\quad & \\quad\n", " N &= \\begin{bmatrix}\n", " 2 & 1 & 5 & 1\\\\\n", " 2 & 2 & 0 & 4\\\\\n", " 3 & 1 & 2 & 0\n", " \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= B^{-1} b = \\begin{bmatrix} 8\\\\ 12\\\\ 18 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &=\n", " \\left( B^{-1} N \\right)^\\top c_\\mathcal{B} - c_\\mathcal{N} =\n", " \\begin{bmatrix} -1\\\\ -2\\\\ -1\\\\ -1 \\end{bmatrix}.\n", "\n", "The matrix form of the final dictionary is\n", "\n", ".. math::\n", "\n", " \\mathcal{B} &= \\{2, 3, 7\\} \\quad & \\quad \\mathcal{N} &= \\{1, 5, 6, 4\\}\\\\\n", " B &= \\begin{bmatrix}\n", " 1 & 5 & 0\\\\\n", " 2 & 0 & 0\\\\\n", " 1 & 2 & 1\n", " \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix}\n", " 2 & 1 & 0 & 1\\\\\n", " 2 & 0 & 1 & 4\\\\\n", " 3 & 0 & 0 & 0\n", " \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= B^{-1} b = \\begin{bmatrix} 6\\\\ 0.4\\\\ 11.2 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &=\n", " \\left( B^{-1} N \\right)^\\top c_\\mathcal{B} - c_\\mathcal{N} =\n", " \\begin{bmatrix} 1.2\\\\ 0.2\\\\ 0.9\\\\ 2.8 \\end{bmatrix}.\n", "\n", "(a)\n", "---\n", "\n", "Changing the original objective function to :math:`3 x_1 + 2 x_2 + x_3 + x_4`\n", "requires recomputing\n", "\n", ".. math::\n", "\n", " z^*_\\mathcal{N} =\n", " \\left( B^{-1} N \\right)^\\top c_\\mathcal{B} - c_\\mathcal{N} =\n", " \\left( B^{-1} N \\right)^\\top \\begin{bmatrix} 2\\\\ 1\\\\ 0 \\end{bmatrix} -\n", " \\begin{bmatrix} 3\\\\ 0\\\\ 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} -0.8\\\\ 0.2\\\\ 0.9\\\\ 2.8 \\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}\n", " 1 & 0 & 0.5 & 2\\\\\n", " 0.2 & 0.2 & -0.1 & -0.2\\\\\n", " 1.6 & -0.4 & -0.3 & -1.6\n", " \\end{bmatrix}\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ 0.2\\\\ 1.6 \\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{1}{6}, \\frac{0.2}{0.4}, \\frac{1.6}{11.2}\n", " \\right\\} \\right)^{-1} =\n", " 2.\n", "\n", "Step 5\n", " The leaving variable index is :math:`i = 3 \\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}\n", " 1 & 0.2 & 1.6\\\\\n", " 0 & 0.2 & -0.4\\\\\n", " 0.5 & -0.1 & -0.3\\\\\n", " 2 & -0.2 & -1.6\n", " \\end{bmatrix} \\begin{bmatrix} 0\\\\ 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -0.2\\\\ -0.2\\\\ 0.1\\\\ 0.2 \\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{-0.8}{-0.2} = 4.\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} 6\\\\ 0.4\\\\ 11.2 \\end{bmatrix} -\n", " 2 \\begin{bmatrix} 1\\\\ 0.2\\\\ 1.6 \\end{bmatrix} =\n", " \\begin{bmatrix} 4\\\\ 0\\\\ 8 \\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} -0.8\\\\ 0.2\\\\ 0.9\\\\ 2.8 \\end{bmatrix} -\n", " 4 \\begin{bmatrix} -0.2\\\\ -0.2\\\\ 0.1\\\\ 0.2 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 1\\\\ 0.5\\\\ 2 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " z^*_i \\leftarrow s = 4.\n", "\n", "Step 9\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{2, 1, 7\\} \\quad & \\quad \\mathcal{N} &= \\{3, 5, 6, 4\\}\\\\\n", " B &= \\begin{bmatrix}\n", " 1 & 2 & 0\\\\\n", " 2 & 2 & 0\\\\\n", " 1 & 3 & 1\n", " \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix}\n", " 5 & 1 & 0 & 1\\\\\n", " 0 & 0 & 1 & 4\\\\\n", " 2 & 0 & 0 & 0\n", " \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= B^{-1} b = \\begin{bmatrix} 4\\\\ 2\\\\ 8 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &=\n", " \\left( B^{-1} N \\right)^\\top c_\\mathcal{B} - c_\\mathcal{N} =\n", " \\begin{bmatrix} 4\\\\ 1\\\\ 0.5\\\\ 2 \\end{bmatrix}.\n", "\n", "Iteration 2\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^* = 3 x_1^* + 2 x_2^* + x_3^* + x_4^* = 14.\n", "\n", "(b)\n", "---\n", "\n", "Changing the original objective function to :math:`x_1 + 2 x_2 + 0.5 x_3 + x_4`\n", "requires recomputing\n", "\n", ".. math::\n", "\n", " z^*_\\mathcal{N} =\n", " \\left( B^{-1} N \\right)^\\top c_\\mathcal{B} - c_\\mathcal{N} =\n", " \\left( B^{-1} N \\right)^\\top \\begin{bmatrix} 2\\\\ 0.5\\\\ 0 \\end{bmatrix} -\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 1.1\\\\ 0.1\\\\ 0.95\\\\ 2.9 \\end{bmatrix}.\n", "\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^* = x_1^* + 2 x_2^* + 0.5 x_3^* + x_4^* = 12.2.\n", "\n", "(c)\n", "---\n", "\n", "Changing the original second constraint's RHS to :math:`26`\n", "requires recomputing\n", "\n", ".. math::\n", "\n", " x^*_\\mathcal{B} =\n", " B^{-1} b =\n", " B^{-1} \\begin{bmatrix} 8\\\\ 26\\\\ 18 \\end{bmatrix} =\n", " \\begin{bmatrix} 13\\\\ -1\\\\ 7 \\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 = 3 \\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}\n", " 1 & 0.2 & 1.6\\\\\n", " 0 & 0.2 & -0.4\\\\\n", " 0.5 & -0.1 & -0.3\\\\\n", " 2 & -0.2 & -1.6\n", " \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -0.2\\\\ -0.2\\\\ 0.1\\\\ 0.2 \\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{-0.2}{1.2}, \\frac{-0.2}{0.2}, \\frac{0.1}{0.9}, \\frac{0.2}{2.8}\n", " \\right\\} \\right)^{-1} =\n", " 9.\n", "\n", "Step 5\n", " The leaving variable index is :math:`j = 6 \\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}\n", " 1 & 0 & 0.5 & 2\\\\\n", " 0.2 & 0.2 & -0.1 & -0.2\\\\\n", " 1.6 & -0.4 & -0.3 & -1.6\n", " \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 0.5\\\\ -0.1\\\\ -0.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{-1}{-0.1} = 10.\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} 13\\\\ -1\\\\ 7 \\end{bmatrix} -\n", " (10) \\begin{bmatrix} 0.5\\\\ -0.1\\\\ -0.3 \\end{bmatrix} =\n", " \\begin{bmatrix} 8\\\\ 0\\\\ 10 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " x^*_j \\leftarrow t = 10\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.2\\\\ 0.2\\\\ 0.9\\\\ 2.8 \\end{bmatrix} -\n", " (9) \\begin{bmatrix} -0.2\\\\ -0.2\\\\ 0.1\\\\ 0.2 \\end{bmatrix} =\n", " \\begin{bmatrix} 3\\\\ 2\\\\ 0\\\\ 1 \\end{bmatrix}\n", " \\quad \\land \\quad\n", " z^*_i \\leftarrow s = 9.\n", "\n", "Step 9\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{2, 6, 7\\} \\quad & \\quad \\mathcal{N} &= \\{1, 5, 3, 4\\}\\\\\n", " B &= \\begin{bmatrix}\n", " 1 & 0 & 0\\\\\n", " 2 & 1 & 0\\\\\n", " 1 & 0 & 1\n", " \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix}\n", " 2 & 1 & 5 & 1\\\\\n", " 2 & 0 & 0 & 4\\\\\n", " 3 & 0 & 2 & 0\n", " \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= B^{-1} b = \\begin{bmatrix} 8\\\\ 10\\\\ 10 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &=\n", " \\left( B^{-1} N \\right)^\\top c_\\mathcal{B} - c_\\mathcal{N} =\n", " \\begin{bmatrix} 3\\\\ 2\\\\ 9\\\\ 1 \\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^* =\n", " c_\\mathcal{B}^\\top B^{-1} b =\n", " \\begin{bmatrix} 2 & 0 & 0 \\end{bmatrix} B^{-1}\n", " \\begin{bmatrix} 8\\\\ 26\\\\ 18 \\end{bmatrix} =\n", " 16." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 7.2\n", "============\n", "\n", ":math:`\\Delta c = \\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\end{bmatrix}^\\top`\n", "-------------------------------------------------------------------------------\n", "\n", "Partitioning :math:`\\Delta c` according to the final optimal basis gives\n", "\n", ".. math::\n", "\n", " \\Delta c_\\mathcal{B} = \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\end{bmatrix}\n", " \\quad \\text{and} \\quad\n", " \\Delta c_\\mathcal{N} = \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix}.\n", "\n", "Applying (7.1) yields\n", "\n", ".. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " \\left( B^{-1} N \\right)^\\top \\Delta c_\\mathcal{B} - \\Delta c_\\mathcal{N} =\n", " \\begin{bmatrix}\n", " 1 & 0.2 & 1.6\\\\\n", " 0 & 0.2 & -0.4\\\\\n", " 0.5 & -0.1 & -0.3\\\\\n", " 2 & -0.2 & -1.6\n", " \\end{bmatrix} \\begin{bmatrix} 0\\\\ 0\\\\ 0 \\end{bmatrix} -\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix}\n", "\n", "The current basis will remain optimal as long as (7.2)\n", "\n", ".. math::\n", "\n", " z^*_\\mathcal{N} + t \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1.2\\\\ 0.2\\\\ 0.9\\\\ 2.8 \\end{bmatrix} +\n", " t \\begin{bmatrix} -1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix} \\geq 0\n", " \\quad \\iff \\quad\n", " t \\leq 1.2.\n", "\n", ":math:`\\Delta c = \\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\end{bmatrix}^\\top`\n", "-------------------------------------------------------------------------------\n", "\n", "Partitioning :math:`\\Delta c` according to the final optimal basis gives\n", "\n", ".. math::\n", "\n", " \\Delta c_\\mathcal{B} = \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\end{bmatrix}\n", " \\quad \\text{and} \\quad\n", " \\Delta c_\\mathcal{N} = \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix}.\n", "\n", "Applying (7.1) yields\n", "\n", ".. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " \\left( B^{-1} N \\right)^\\top \\Delta c_\\mathcal{B} - \\Delta c_\\mathcal{N} =\n", " \\begin{bmatrix}\n", " 1 & 0.2 & 1.6\\\\\n", " 0 & 0.2 & -0.4\\\\\n", " 0.5 & -0.1 & -0.3\\\\\n", " 2 & -0.2 & -1.6\n", " \\end{bmatrix} \\begin{bmatrix} 1\\\\ 0\\\\ 0 \\end{bmatrix} -\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 1 \\\\ 0 \\\\ 0.5 \\\\ 2 \\end{bmatrix}\n", "\n", "The current basis will remain optimal as long as (7.2)\n", "\n", ".. math::\n", "\n", " z^*_\\mathcal{N} + t \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1.2\\\\ 0.2\\\\ 0.9\\\\ 2.8 \\end{bmatrix} +\n", " t \\begin{bmatrix} 1 \\\\ 0 \\\\ 0.5 \\\\ 2 \\end{bmatrix} \\geq 0\n", " \\quad \\iff \\quad\n", " -1.2 \\leq t.\n", "\n", ":math:`\\Delta c = \\begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 \\end{bmatrix}^\\top`\n", "-------------------------------------------------------------------------------\n", "\n", "Partitioning :math:`\\Delta c` according to the final optimal basis gives\n", "\n", ".. math::\n", "\n", " \\Delta c_\\mathcal{B} = \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\end{bmatrix}\n", " \\quad \\text{and} \\quad\n", " \\Delta c_\\mathcal{N} = \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix}.\n", "\n", "Applying (7.1) yields\n", "\n", ".. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " \\left( B^{-1} N \\right)^\\top \\Delta c_\\mathcal{B} - \\Delta c_\\mathcal{N} =\n", " \\begin{bmatrix}\n", " 1 & 0.2 & 1.6\\\\\n", " 0 & 0.2 & -0.4\\\\\n", " 0.5 & -0.1 & -0.3\\\\\n", " 2 & -0.2 & -1.6\n", " \\end{bmatrix} \\begin{bmatrix} 0\\\\ 1\\\\ 0 \\end{bmatrix} -\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 0.2 \\\\ 0.2 \\\\ -0.1 \\\\ -0.2 \\end{bmatrix}\n", "\n", "The current basis will remain optimal as long as (7.2)\n", "\n", ".. math::\n", "\n", " z^*_\\mathcal{N} + t \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1.2\\\\ 0.2\\\\ 0.9\\\\ 2.8 \\end{bmatrix} +\n", " t \\begin{bmatrix} 0.2 \\\\ 0.2 \\\\ -0.1 \\\\ -0.2 \\end{bmatrix} \\geq 0\n", " \\quad \\iff \\quad\n", " -1 \\leq t \\leq 9.\n", "\n", ":math:`\\Delta c = \\begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 \\end{bmatrix}^\\top`\n", "-------------------------------------------------------------------------------\n", "\n", "Partitioning :math:`\\Delta c` according to the final optimal basis gives\n", "\n", ".. math::\n", "\n", " \\Delta c_\\mathcal{B} = \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\end{bmatrix}\n", " \\quad \\text{and} \\quad\n", " \\Delta c_\\mathcal{N} = \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix}.\n", "\n", "Applying (7.1) yields\n", "\n", ".. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " \\left( B^{-1} N \\right)^\\top \\Delta c_\\mathcal{B} - \\Delta c_\\mathcal{N} =\n", " \\begin{bmatrix}\n", " 1 & 0.2 & 1.6\\\\\n", " 0 & 0.2 & -0.4\\\\\n", " 0.5 & -0.1 & -0.3\\\\\n", " 2 & -0.2 & -1.6\n", " \\end{bmatrix} \\begin{bmatrix} 0\\\\ 0\\\\ 0 \\end{bmatrix} -\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 0\\\\ -1 \\end{bmatrix}\n", "\n", "The current basis will remain optimal as long as (7.2)\n", "\n", ".. math::\n", "\n", " z^*_\\mathcal{N} + t \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1.2\\\\ 0.2\\\\ 0.9\\\\ 2.8 \\end{bmatrix} +\n", " t \\begin{bmatrix} 0\\\\ 0\\\\ 0\\\\ -1 \\end{bmatrix} \\geq 0\n", " \\quad \\iff \\quad\n", " t \\leq 2.8." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 7.3\n", "============\n", "\n", "(a)\n", "---\n", "\n", "The range of optimality is given by\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " -1 + 2 \\mu &\\geq 0, \\quad & \\quad 3 - \\mu &\\geq 0,\\\\\n", " -1 + \\mu &\\geq 0, \\quad & \\quad -4 + 3 \\mu &\\geq 0,\n", " \\end{aligned}\n", " \\quad \\iff \\quad\n", " \\frac{4}{3} \\leq \\mu \\leq 3.\n", "\n", "(b)\n", "---\n", "\n", "The entering variable is :math:`x_{j = 3 \\in \\mathcal{N}}` because the maximum\n", "is :math:`\\mu^* = 3`.\n", "\n", "Since\n", "\n", ".. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " B^{-1} N e_j =\n", " \\begin{bmatrix} -1 & 1\\\\ -3 & 2\\\\ -1 & -1 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ 2\\\\ -1 \\end{bmatrix}\n", "\n", "and\n", "\n", ".. math::\n", "\n", " \\DeclareMathOperator*{\\argmax}{arg\\,max}\n", " \\argmax_{i \\in \\mathcal{B}} \\frac{\\Delta x_i}{x^*_i + \\mu^* \\bar{x}_i} =\n", " \\argmax_{i \\in \\mathcal{B}} \\left\\{\n", " \\frac{1}{2}, \\frac{2}{5}, \\frac{-1}{2}\n", " \\right\\},\n", "\n", "the leaving variable is :math:`x_4`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 7.4\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:`x^*_\\mathcal{B}` and :math:`z^*_\\mathcal{N}` have some\n", "negative components, define\n", "\n", ".. math::\n", "\n", " \\bar{x}_\\mathcal{B} = \\begin{bmatrix} 1\\\\ 1 \\end{bmatrix}\n", " \\quad \\text{and} \\quad\n", " \\bar{z}_\\mathcal{N} = \\begin{bmatrix} 1\\\\ 1\\\\ 1 \\end{bmatrix}.\n", "\n", "Iteration 1\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{-2}{1}, -\\frac{6}{1}, -\\frac{0}{1}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{-2}{1}, -\\frac{1}{1}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= 2\n", "\n", " shows that one can select either :math:`x_1` to be the entering variable or\n", " :math:`x_4` to be the leaving variable. Applying Bland's rule selects\n", " :math:`x_1` to be the entering variable.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`j = 1 \\in \\mathcal{N}`, so do one step of\n", " the primal simplex method.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " 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", " The index of the leaving variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{i \\in \\mathcal{B}}\n", " \\left\\{\n", " \\frac{x^*_i + \\mu^* \\bar{x}_i}{\\Delta x_i} \\colon \\Delta x_i > 0\n", " \\right\\}\n", " &= \\argmin_{i \\in \\mathcal{B}}\\left\\{\n", " \\frac{1 + \\mu^*}{2}\n", " \\right\\}\\\\\n", " &= 5.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix} -1 & 2\\\\ -1 & -1\\\\ -1 & 1 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} -2\\\\ 1\\\\ -1 \\end{bmatrix}.\n", "\n", "Step 3\n", " The step length adjustments are given by\n", "\n", " .. math::\n", "\n", " t &= \\frac{x^*_i}{\\Delta x_i} = \\frac{1}{2} = 0.5\n", " \\quad & \\quad\n", " \\bar{t} = \\frac{\\bar{x}_i}{\\Delta x_i} = \\frac{1}{2} = 0.5\\\\\n", " s &= \\frac{z^*_j}{\\Delta z_j} = \\frac{-2}{-2} = 1\n", " \\quad & \\quad\n", " \\bar{s} = \\frac{\\bar{z}_j}{\\Delta z_j} = \\frac{1}{-2} = -0.5.\n", "\n", "Step 4\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} &\\leftarrow x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} -2\\\\ 1 \\end{bmatrix} -\n", " 0.5 \\begin{bmatrix} -1\\\\ 2 \\end{bmatrix} =\n", " \\begin{bmatrix} -1.5\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " x^*_j &\\leftarrow t = 0.5\\\\\n", " \\bar{x}_\\mathcal{B} &\\leftarrow\n", " \\bar{x}_\\mathcal{B} - \\bar{t} \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1\\\\ 1 \\end{bmatrix} -\n", " 0.5 \\begin{bmatrix} -1\\\\ 2 \\end{bmatrix} =\n", " \\begin{bmatrix} 1.5\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{x}_j &\\leftarrow \\bar{t} = 0.5\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} &\\leftarrow z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} -2\\\\ 6\\\\ 0 \\end{bmatrix} -\n", " (1) \\begin{bmatrix} -2\\\\ 1\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 5\\\\ 1 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_i &\\leftarrow s = 1\\\\\n", " \\bar{z}_\\mathcal{N} &\\leftarrow\n", " \\bar{z}_\\mathcal{N} - \\bar{s} \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ 1\\\\ 1 \\end{bmatrix} -\n", " (-0.5) \\begin{bmatrix} -2\\\\ 1\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 1.5\\\\ 0.5 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_i &\\leftarrow \\bar{s} = -0.5.\n", "\n", "Step 5\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 4, 1 \\} \\quad & \\quad \\mathcal{N} &= \\{ 5, 2, 3 \\}\\\\\n", " B &= \\begin{bmatrix} 1 & -1\\\\ 0 & 2 \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 0 & -1 & -1\\\\ 1 & -1 & 1 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} -1.5\\\\ 0.5 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} 1\\\\ 5\\\\ 1 \\end{bmatrix}\\\\\n", " \\bar{x}_\\mathcal{B} &= \\begin{bmatrix} 1.5\\\\ 0.5 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_\\mathcal{N} &= \\begin{bmatrix} -0.5\\\\ 1.5\\\\ 0.5 \\end{bmatrix}.\n", "\n", "Iteration 2\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{5}{3 / 2}, -\\frac{1}{1 / 2}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{-3 / 2}{3 / 2}, -\\frac{1 / 2}{1 / 2}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= 1\n", "\n", " shows that :math:`x_4` is the leaving variable.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`i = 4 \\in \\mathcal{B}`, so do one step of\n", " the dual simplex method.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix} 0.5 & 0.5\\\\ -1.5 & -0.5\\\\ -0.5 & 0.5 \\end{bmatrix}\n", " \\begin{bmatrix} 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -0.5\\\\ 1.5\\\\ 0.5 \\end{bmatrix}.\n", "\n", " The index of the entering variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{j \\in \\mathcal{N}}\n", " \\left\\{\n", " \\frac{z^*_j + \\mu^* \\bar{z}_j}{\\Delta z_j} \\colon \\Delta z_j > 0\n", " \\right\\}\n", " &= \\argmin_{j \\in \\mathcal{N}}\\left\\{\n", " \\frac{5 + \\mu^* (1.5)}{1.5}, \\frac{1 + \\mu^* (0.5)}{0.5}\n", " \\right\\}\\\\\n", " &= 3.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " B^{-1} N e_j =\n", " \\begin{bmatrix} 0.5 & -1.5 & -0.5\\\\ 0.5 & -0.5 & 0.5 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} -0.5\\\\ 0.5 \\end{bmatrix}.\n", "\n", "Step 3\n", " The step length adjustments are given by\n", "\n", " .. math::\n", "\n", " t &= \\frac{x^*_i}{\\Delta x_i} = \\frac{-1.5}{-0.5} = 3\n", " \\quad & \\quad\n", " \\bar{t} = \\frac{\\bar{x}_i}{\\Delta x_i} = \\frac{1.5}{-0.5} = -3\\\\\n", " s &= \\frac{z^*_j}{\\Delta z_j} = \\frac{1}{0.5} = 2\n", " \\quad & \\quad\n", " \\bar{s} = \\frac{\\bar{z}_j}{\\Delta z_j} = \\frac{0.5}{0.5} = 1.\n", "\n", "Step 4\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} &\\leftarrow x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} -1.5\\\\ 0.5 \\end{bmatrix} -\n", " (3) \\begin{bmatrix} -0.5\\\\ 0.5 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ -1 \\end{bmatrix}\n", " \\quad & \\quad\n", " x^*_j &\\leftarrow t = 3\\\\\n", " \\bar{x}_\\mathcal{B} &\\leftarrow\n", " \\bar{x}_\\mathcal{B} - \\bar{t} \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1.5\\\\ 0.5 \\end{bmatrix} -\n", " (-3) \\begin{bmatrix} -0.5\\\\ 0.5 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 2 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{x}_j &\\leftarrow \\bar{t} = -3\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} &\\leftarrow z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ 5\\\\ 1 \\end{bmatrix} -\n", " (2) \\begin{bmatrix} -0.5\\\\ 1.5\\\\ 0.5 \\end{bmatrix} =\n", " \\begin{bmatrix} 2\\\\ 2\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_i &\\leftarrow s = 2\\\\\n", " \\bar{z}_\\mathcal{N} &\\leftarrow\n", " \\bar{z}_\\mathcal{N} - \\bar{s} \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} -0.5\\\\ 1.5\\\\ 0.5 \\end{bmatrix} -\n", " (1) \\begin{bmatrix} -0.5\\\\ 1.5\\\\ 0.5 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_i &\\leftarrow \\bar{s} = 1.\n", "\n", "Step 5\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 3, 1 \\} \\quad & \\quad \\mathcal{N} &= \\{ 5, 2, 4 \\}\\\\\n", " B &= \\begin{bmatrix} -1 & -1\\\\ 1 & 2 \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 0 & -1 & 1\\\\ 1 & -1 & 0 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} 3\\\\ -1 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} 2\\\\ 2\\\\ 2 \\end{bmatrix}\\\\\n", " \\bar{x}_\\mathcal{B} &= \\begin{bmatrix} -3\\\\ 2 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_\\mathcal{N} &= \\begin{bmatrix} 0\\\\ 0\\\\ 1 \\end{bmatrix}.\n", "\n", "Iteration 3\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{2}{1}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{-1}{2}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= 0.5\n", "\n", " shows that :math:`x_1` is the leaving variable.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`i = 1 \\in \\mathcal{B}`, so do one step of\n", " the dual simplex method.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix} -1 & 1\\\\ 3 & -2\\\\ -2 & 1 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} -1\\\\ 2\\\\ -1 \\end{bmatrix}.\n", "\n", " The index of the entering variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{j \\in \\mathcal{N}}\n", " \\left\\{\n", " \\frac{z^*_j + \\mu^* \\bar{z}_j}{\\Delta z_j} \\colon \\Delta z_j > 0\n", " \\right\\}\n", " &= \\argmin_{j \\in \\mathcal{N}}\\left\\{\n", " \\frac{2 + \\mu^* (0)}{2}\n", " \\right\\}\\\\\n", " &= 2.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " B^{-1} N e_j =\n", " \\begin{bmatrix} -1 & 3 & -2\\\\ 1 & -2 & 1 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 3\\\\ -2 \\end{bmatrix}.\n", "\n", "Step 3\n", " The step length adjustments are given by\n", "\n", " .. math::\n", "\n", " t &= \\frac{x^*_i}{\\Delta x_i} = \\frac{-1}{-2} = 0.5\n", " \\quad & \\quad\n", " \\bar{t} = \\frac{\\bar{x}_i}{\\Delta x_i} = \\frac{2}{-2} = -1\\\\\n", " s &= \\frac{z^*_j}{\\Delta z_j} = \\frac{2}{2} = 1\n", " \\quad & \\quad\n", " \\bar{s} = \\frac{\\bar{z}_j}{\\Delta z_j} = \\frac{0}{2} = 0.\n", "\n", "Step 4\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} &\\leftarrow x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 3\\\\ -1 \\end{bmatrix} -\n", " (0.5) \\begin{bmatrix} 3\\\\ -2 \\end{bmatrix} =\n", " \\begin{bmatrix} 1.5\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " x^*_j &\\leftarrow t = 0.5\\\\\n", " \\bar{x}_\\mathcal{B} &\\leftarrow\n", " \\bar{x}_\\mathcal{B} - \\bar{t} \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} -3\\\\ 2 \\end{bmatrix} -\n", " (-1) \\begin{bmatrix} 3\\\\ -2 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{x}_j &\\leftarrow \\bar{t} = -1\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} &\\leftarrow z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 2\\\\ 2\\\\ 2 \\end{bmatrix} -\n", " (1) \\begin{bmatrix} -1\\\\ 2\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 3\\\\ 0\\\\ 3 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_i &\\leftarrow s = 1\\\\\n", " \\bar{z}_\\mathcal{N} &\\leftarrow\n", " \\bar{z}_\\mathcal{N} - \\bar{s} \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 1 \\end{bmatrix} -\n", " (0) \\begin{bmatrix} -1\\\\ 2\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 1 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_i &\\leftarrow \\bar{s} = 0.\n", "\n", "Step 5\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 3, 2 \\} \\quad & \\quad \\mathcal{N} &= \\{ 5, 1, 4 \\}\\\\\n", " B &= \\begin{bmatrix} -1 & -1\\\\ 1 & -1 \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 0 & -1 & 1\\\\ 1 & 2 & 0 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} 1.5\\\\ 0.5 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} 3\\\\ 1\\\\ 3 \\end{bmatrix}\\\\\n", " \\bar{x}_\\mathcal{B} &= \\begin{bmatrix} 0\\\\ -1 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_\\mathcal{N} &= \\begin{bmatrix} 0\\\\ 0\\\\ 1 \\end{bmatrix}.\n", "\n", "Iteration 4\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{3}{1}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= -3\n", "\n", " shows that the current solution is optimal. The optimal objective function\n", " 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 7.5\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", "Since only :math:`x^*_\\mathcal{B}` has some negative components, the problem is\n", "dual feasible. Nevertheless, define\n", "\n", ".. math::\n", "\n", " \\bar{x}_\\mathcal{B} = \\begin{bmatrix} 1\\\\ 1 \\end{bmatrix}\n", " \\quad \\text{and} \\quad\n", " \\bar{z}_\\mathcal{N} = \\begin{bmatrix} 1\\\\ 1\\\\ 1 \\end{bmatrix}.\n", "\n", "Iteration 1\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{1}{1}, -\\frac{3}{1}, -\\frac{1}{1}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{-5}{1}, -\\frac{4}{1}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= 5\n", "\n", " shows that :math:`x_4` is the leaving variable.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`i = 4 \\in \\mathcal{B}`, so do one step of\n", " the dual simplex method.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top 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", " The index of the entering variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{j \\in \\mathcal{N}}\n", " \\left\\{\n", " \\frac{z^*_j + \\mu^* \\bar{z}_j}{\\Delta z_j} \\colon \\Delta z_j > 0\n", " \\right\\}\n", " &= \\argmin_{j \\in \\mathcal{N}}\\left\\{\n", " \\frac{3 + \\mu^*}{5}\n", " \\right\\}\\\\\n", " &= 2.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " 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 3\n", " The step length adjustments are given by\n", "\n", " .. math::\n", "\n", " t &= \\frac{x^*_i}{\\Delta x_i} = \\frac{-5}{-5} = 1\n", " \\quad & \\quad\n", " \\bar{t} = \\frac{\\bar{x}_i}{\\Delta x_i} = \\frac{1}{-5} = -0.2\\\\\n", " s &= \\frac{z^*_j}{\\Delta z_j} = \\frac{3}{5} = 0.6\n", " \\quad & \\quad\n", " \\bar{s} = \\frac{\\bar{z}_j}{\\Delta z_j} = \\frac{1}{5} = 0.2.\n", "\n", "Step 4\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} &\\leftarrow 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 & \\quad\n", " x^*_j &\\leftarrow t = 1\\\\\n", " \\bar{x}_\\mathcal{B} &\\leftarrow\n", " \\bar{x}_\\mathcal{B} - \\bar{t} \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1\\\\ 1 \\end{bmatrix} -\n", " (-0.2) \\begin{bmatrix} -5\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 0.8 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{x}_j &\\leftarrow \\bar{t} = -0.2\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} &\\leftarrow z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ 3\\\\ 1 \\end{bmatrix} -\n", " (0.6) \\begin{bmatrix} -2\\\\ 5\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 2.2\\\\ 0\\\\ 1.6 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_i &\\leftarrow s = 0.6\\\\\n", " \\bar{z}_\\mathcal{N} &\\leftarrow\n", " \\bar{z}_\\mathcal{N} - \\bar{s} \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ 1\\\\ 1 \\end{bmatrix} -\n", " (0.2) \\begin{bmatrix} -2\\\\ 5\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 1.4\\\\ 0\\\\ 1.2 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_i &\\leftarrow \\bar{s} = 0.2.\n", "\n", "Step 5\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}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} 2.2\\\\ 0.6\\\\ 1.6 \\end{bmatrix}\\\\\n", " \\bar{x}_\\mathcal{B} &= \\begin{bmatrix} -0.2\\\\ 0.8 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_\\mathcal{N} &= \\begin{bmatrix} 1.4\\\\ 0.2\\\\ 1.2 \\end{bmatrix}.\n", "\n", "Iteration 2\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{2.2}{1.4}, -\\frac{0.6}{0.2}, -\\frac{1.6}{1.2}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{5}{0.8}\n", " \\right\\},\n", " \\right\\}\\\\\n", " &= -1.\\bar{3}\n", "\n", " shows that the current solution is optimal. The optimal objective function\n", " 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 7.6\n", "============\n", "\n", "Rewriting :ref:`Exercise 2.6 ` into matrix form\n", "yields\n", "\n", ".. math::\n", "\n", " \\mathcal{B} &= \\{ 3, 4, 5 \\} \\quad & \\quad \\mathcal{N} &= \\{ 1, 2 \\}\\\\\n", " B &= \\mathbf{I}_3 \\quad & \\quad\n", " N &= \\begin{bmatrix} -1 & -1\\\\ -1 & 1\\\\ 1 & 2 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= b = \\begin{bmatrix} -3\\\\ -1\\\\ 2 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= -c_\\mathcal{N} = \\begin{bmatrix} -1\\\\ -3 \\end{bmatrix}.\n", "\n", "Since both :math:`x^*_\\mathcal{B}` and :math:`z^*_\\mathcal{N}` have some\n", "negative components, define\n", "\n", ".. math::\n", "\n", " \\bar{x}_\\mathcal{B} = \\begin{bmatrix} 1\\\\ 1\\\\ 1 \\end{bmatrix}\n", " \\quad \\text{and} \\quad\n", " \\bar{z}_\\mathcal{N} = \\begin{bmatrix} 1\\\\ 1 \\end{bmatrix}.\n", "\n", "Iteration 1\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{-1}{1}, -\\frac{-3}{1}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{-3}{1}, -\\frac{-1}{1}, -\\frac{2}{1}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= 3\n", "\n", " shows that one can select either :math:`x_2` to be the entering variable or\n", " :math:`x_3` to be the leaving variable. Applying Bland's rule selects\n", " :math:`x_2` to be the entering variable.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`j = 2 \\in \\mathcal{N}`, so do one step of\n", " the primal simplex method.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " B^{-1} N e_j =\n", " \\begin{bmatrix} -1 & -1\\\\ -1 & 1\\\\ 1 & 2 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} -1\\\\ 1\\\\ 2 \\end{bmatrix}.\n", "\n", " The index of the leaving variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{i \\in \\mathcal{B}}\n", " \\left\\{\n", " \\frac{x^*_i + \\mu^* \\bar{x}_i}{\\Delta x_i} \\colon \\Delta x_i > 0\n", " \\right\\}\n", " &= \\argmin_{i \\in \\mathcal{B}}\\left\\{\n", " \\frac{-1 + \\mu^*}{1}, \\frac{2 + \\mu^*}{2}\n", " \\right\\}\\\\\n", " &= 4.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix} -1 & -1 & 1\\\\ -1 & 1 & 2 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ -1 \\end{bmatrix}.\n", "\n", "Step 3\n", " The step length adjustments are given by\n", "\n", " .. math::\n", "\n", " t &= \\frac{x^*_i}{\\Delta x_i} = \\frac{-1}{1} = -1\n", " \\quad & \\quad\n", " \\bar{t} = \\frac{\\bar{x}_i}{\\Delta x_i} = \\frac{1}{1} = 1\\\\\n", " s &= \\frac{z^*_j}{\\Delta z_j} = \\frac{-3}{-1} = 3\n", " \\quad & \\quad\n", " \\bar{s} = \\frac{\\bar{z}_j}{\\Delta z_j} = \\frac{1}{-1} = -1.\n", "\n", "Step 4\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} &\\leftarrow x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} -3\\\\ -1\\\\ 2 \\end{bmatrix} -\n", " (-1) \\begin{bmatrix} -1\\\\ 1\\\\ 2 \\end{bmatrix} =\n", " \\begin{bmatrix} -4\\\\ 0\\\\ 4 \\end{bmatrix}\n", " \\quad & \\quad\n", " x^*_j &\\leftarrow t = -1\\\\\n", " \\bar{x}_\\mathcal{B} &\\leftarrow\n", " \\bar{x}_\\mathcal{B} - \\bar{t} \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1\\\\ 1\\\\ 1 \\end{bmatrix} -\n", " (1) \\begin{bmatrix} -1\\\\ 1\\\\ 2 \\end{bmatrix} =\n", " \\begin{bmatrix} 2\\\\ 0\\\\ -1 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{x}_j &\\leftarrow \\bar{t} = 1\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} &\\leftarrow z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} -1\\\\ -3 \\end{bmatrix} -\n", " (3) \\begin{bmatrix} 1\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} -4\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_i &\\leftarrow s = 3\\\\\n", " \\bar{z}_\\mathcal{N} &\\leftarrow\n", " \\bar{z}_\\mathcal{N} - \\bar{s} \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ 1 \\end{bmatrix} -\n", " (-1) \\begin{bmatrix} 1\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 2\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_i &\\leftarrow \\bar{s} = -1.\n", "\n", "Step 5\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 3, 2, 5 \\} \\quad & \\quad \\mathcal{N} &= \\{ 1, 4 \\}\\\\\n", " B &= \\begin{bmatrix}\n", " 1 & -1 & 0\\\\ 0 & 1 & 0\\\\ 0 & 2 & 1\n", " \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} -1 & 0\\\\ -1 & 1\\\\ 1 & 0 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} -4\\\\ -1\\\\ 4 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} -4\\\\ 3 \\end{bmatrix}\\\\\n", " \\bar{x}_\\mathcal{B} &= \\begin{bmatrix} 2\\\\ 1\\\\ -1 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_\\mathcal{N} &= \\begin{bmatrix} 2\\\\ -1 \\end{bmatrix}.\n", "\n", "Iteration 2\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{-4}{2}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{-4}{2}, -\\frac{-1}{1}\n", " \\right\\},\n", " \\right\\}\\\\\n", " &= 2\n", "\n", " shows that one can select either :math:`x_1` to be the entering variable or\n", " :math:`x_3` to be the leaving variable. Applying Bland's rule selects\n", " :math:`x_1` to be the entering variable.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`j = 1 \\in \\mathcal{N}`, so do one step of\n", " the primal simplex method.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " B^{-1} N e_j =\n", " \\begin{bmatrix} -2 & 1\\\\ -1 & 1\\\\ 3 & -2 \\end{bmatrix}\n", " \\begin{bmatrix} 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -2\\\\ -1\\\\ 3 \\end{bmatrix}.\n", "\n", " The index of the leaving variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{i \\in \\mathcal{B}}\n", " \\left\\{\n", " \\frac{x^*_i + \\mu^* \\bar{x}_i}{\\Delta x_i} \\colon \\Delta x_i > 0\n", " \\right\\}\n", " &= \\argmin_{i \\in \\mathcal{B}}\\left\\{\n", " \\frac{4 + \\mu^* (-1)}{3}\n", " \\right\\}\\\\\n", " &= 5.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix} -2 & -1 & 3\\\\ 1 & 1 & -2 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} -3\\\\ 2 \\end{bmatrix}.\n", "\n", "Step 3\n", " The step length adjustments are given by\n", "\n", " .. math::\n", "\n", " t &= \\frac{x^*_i}{\\Delta x_i} = \\frac{4}{3} = 1.\\bar{3}\n", " \\quad & \\quad\n", " \\bar{t} = \\frac{\\bar{x}_i}{\\Delta x_i} = \\frac{-1}{3} = -0.\\bar{3}\\\\\n", " s &= \\frac{z^*_j}{\\Delta z_j} = \\frac{-4}{-3} = 1.\\bar{3}\n", " \\quad & \\quad\n", " \\bar{s} = \\frac{\\bar{z}_j}{\\Delta z_j} = \\frac{2}{-3} = -0.\\bar{6}.\n", "\n", "Step 4\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} &\\leftarrow x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} -4\\\\ -1\\\\ 4 \\end{bmatrix} -\n", " (1.\\bar{3}) \\begin{bmatrix} -2\\\\ -1\\\\ 3 \\end{bmatrix} =\n", " \\begin{bmatrix} -1.\\bar{3}\\\\ 0.\\bar{3}\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " x^*_j &\\leftarrow t = 1.\\bar{3}\\\\\n", " \\bar{x}_\\mathcal{B} &\\leftarrow\n", " \\bar{x}_\\mathcal{B} - \\bar{t} \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 2\\\\ 1\\\\ -1 \\end{bmatrix} -\n", " (-0.\\bar{3}) \\begin{bmatrix} -2\\\\ -1\\\\ 3 \\end{bmatrix} =\n", " \\begin{bmatrix} 1.\\bar{3}\\\\ 0.\\bar{6}\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{x}_j &\\leftarrow \\bar{t} = -0.\\bar{3}\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} &\\leftarrow z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} -4\\\\ 3 \\end{bmatrix} -\n", " (1.\\bar{3}) \\begin{bmatrix} -3\\\\ 2 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 0.\\bar{3} \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_i &\\leftarrow s = 1.\\bar{3}\\\\\n", " \\bar{z}_\\mathcal{N} &\\leftarrow\n", " \\bar{z}_\\mathcal{N} - \\bar{s} \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 2\\\\ -1 \\end{bmatrix} -\n", " (-0.\\bar{6}) \\begin{bmatrix} -3\\\\ 2 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 0.\\bar{3} \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_i &\\leftarrow \\bar{s} = -0.\\bar{6}.\n", "\n", "Step 5\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 3, 2, 1 \\} \\quad & \\quad \\mathcal{N} &= \\{ 5, 4 \\}\\\\\n", " B &= \\begin{bmatrix}\n", " 1 & -1 & -1\\\\ 0 & 1 & -1\\\\ 0 & 2 & 1\n", " \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 0 & 0\\\\ 0 & 1\\\\ 1 & 0 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix}\n", " -1.\\bar{3}\\\\ 0.\\bar{3}\\\\ 1.\\bar{3}\n", " \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} 1.\\bar{3}\\\\ 0.\\bar{3} \\end{bmatrix}\\\\\n", " \\bar{x}_\\mathcal{B} &= \\begin{bmatrix}\n", " 1.\\bar{3}\\\\ 0.\\bar{6}\\\\ -0.\\bar{3}\n", " \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_\\mathcal{N} &= \\begin{bmatrix}\n", " -0.\\bar{6}\\\\ 0.\\bar{3}\n", " \\end{bmatrix}.\n", "\n", "Iteration 3\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{0.\\bar{3}}{0.\\bar{3}}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{-1.\\bar{3}}{1.\\bar{3}}, -\\frac{0.\\bar{3}}{0.\\bar{6}}\n", " \\right\\},\n", " \\right\\}\\\\\n", " &= 1\n", "\n", " shows that :math:`x_3` is the leaving variable.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`i = 3 \\in \\mathcal{B}`, so do one step of\n", " the dual simplex method.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix}\n", " 0.\\bar{6} & 0.\\bar{3} & 0.\\bar{3}\\\\\n", " -0.\\bar{3} & 0.\\bar{3} & -0.\\bar{6}\n", " \\end{bmatrix} \\begin{bmatrix} 1\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -0.\\bar{6}\\\\ 0.\\bar{3} \\end{bmatrix}.\n", "\n", " The index of the entering variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{j \\in \\mathcal{N}}\n", " \\left\\{\n", " \\frac{z^*_j + \\mu^* \\bar{z}_j}{\\Delta z_j} \\colon \\Delta z_j > 0\n", " \\right\\}\n", " &= \\argmin_{j \\in \\mathcal{N}}\\left\\{\n", " \\frac{0.\\bar{3} + \\mu^* (0.\\bar{3})}{0.\\bar{3}},\n", " \\right\\}\\\\\n", " &= 4.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " B^{-1} N e_j =\n", " \\begin{bmatrix}\n", " 0.\\bar{6} & -0.\\bar{3}\\\\\n", " 0.\\bar{3} & 0.\\bar{3}\\\\\n", " 0.\\bar{3} & -0.\\bar{6}\n", " \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} -0.\\bar{3}\\\\ 0.\\bar{3}\\\\ -0.\\bar{6} \\end{bmatrix}.\n", "\n", "Step 3\n", " The step length adjustments are given by\n", "\n", " .. math::\n", "\n", " t &= \\frac{x^*_i}{\\Delta x_i} = \\frac{-1.\\bar{3}}{-0.\\bar{3}} = 4\n", " \\quad & \\quad\n", " \\bar{t} = \\frac{\\bar{x}_i}{\\Delta x_i} =\n", " \\frac{1.\\bar{3}}{-0.\\bar{3}} = -4\\\\\n", " s &= \\frac{z^*_j}{\\Delta z_j} = \\frac{0.\\bar{3}}{0.\\bar{3}} = 1\n", " \\quad & \\quad\n", " \\bar{s} = \\frac{\\bar{z}_j}{\\Delta z_j} =\n", " \\frac{0.\\bar{3}}{0.\\bar{3}} = 1.\n", "\n", "Step 4\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} &\\leftarrow x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} -1.\\bar{3}\\\\ 0.\\bar{3}\\\\ 1.\\bar{3} \\end{bmatrix} -\n", " (4) \\begin{bmatrix}\n", " -0.\\bar{3}\\\\ 0.\\bar{3}\\\\ -0.\\bar{6}\n", " \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ -1\\\\ 4 \\end{bmatrix}\n", " \\quad & \\quad\n", " x^*_j &\\leftarrow t = 4\\\\\n", " \\bar{x}_\\mathcal{B} &\\leftarrow\n", " \\bar{x}_\\mathcal{B} - \\bar{t} \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1.\\bar{3}\\\\ 0.\\bar{6}\\\\ -0.\\bar{3} \\end{bmatrix} -\n", " (-4) \\begin{bmatrix}\n", " -0.\\bar{3}\\\\ 0.\\bar{3}\\\\ -0.\\bar{6}\n", " \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 2\\\\ -3 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{x}_j &\\leftarrow \\bar{t} = -4\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} &\\leftarrow z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1.\\bar{3}\\\\ 0.\\bar{3} \\end{bmatrix} -\n", " (1) \\begin{bmatrix} -0.\\bar{6}\\\\ 0.\\bar{3} \\end{bmatrix} =\n", " \\begin{bmatrix} 2\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_i &\\leftarrow s = 1\\\\\n", " \\bar{z}_\\mathcal{N} &\\leftarrow\n", " \\bar{z}_\\mathcal{N} - \\bar{s} \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} -0.\\bar{6}\\\\ 0.\\bar{3} \\end{bmatrix} -\n", " (1) \\begin{bmatrix} -0.\\bar{6}\\\\ 0.\\bar{3} \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_i &\\leftarrow \\bar{s} = 1.\n", "\n", "Step 5\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 4, 2, 1 \\} \\quad & \\quad \\mathcal{N} &= \\{ 5, 3 \\}\\\\\n", " B &= \\begin{bmatrix}\n", " 0 & -1 & -1\\\\\n", " 1 & 1 & -1\\\\\n", " 0 & 2 & 1\n", " \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 0 & 1\\\\ 0 & 0\\\\ 1 & 0 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} 4\\\\ -1\\\\ 4 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} 2\\\\ 1 \\end{bmatrix}\\\\\n", " \\bar{x}_\\mathcal{B} &= \\begin{bmatrix} -4\\\\ 2\\\\ -3 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_\\mathcal{N} &= \\begin{bmatrix} 0\\\\ 1 \\end{bmatrix}.\n", "\n", "Iteration 4\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{1}{1}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{-1}{2}\n", " \\right\\},\n", " \\right\\}\\\\\n", " &= 0.5\n", "\n", " shows that :math:`x_2` is the leaving variable.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`i = 2 \\in \\mathcal{B}`, so do one step of\n", " the dual simplex method.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix} -2 & 1 & -1\\\\ -3 & 1 & -2 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -1\\\\ -1 \\end{bmatrix}.\n", "\n", " The index of the entering variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{j \\in \\mathcal{N}}\n", " \\left\\{\n", " \\frac{z^*_j + \\mu^* \\bar{z}_j}{\\Delta z_j} \\colon \\Delta z_j > 0\n", " \\right\\} = \\emptyset.\n", "\n", " Therefore, the dual is unbounded i.e. the primal is infeasible." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 7.7\n", "============\n", "\n", "The previous exercises were solved using the proposed tool." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 7.8\n", "============\n", "\n", "Rewriting the standard form LP into matrix form yields\n", "\n", ".. math::\n", "\n", " \\mathcal{B} &= \\{ 3, 4 \\} \\quad & \\quad \\mathcal{N} &= \\{ 1, 2 \\}\\\\\n", " B &= \\mathbf{I}_2 \\quad & \\quad\n", " N &= \\begin{bmatrix} 1 & -1\\\\ -1 & 1 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= b = \\begin{bmatrix} 1\\\\ -4 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= -c_\\mathcal{N} = \\begin{bmatrix} -3\\\\ 1 \\end{bmatrix}.\n", "\n", "Since both :math:`x^*_\\mathcal{B}` and :math:`z^*_\\mathcal{N}` have some\n", "negative components, define\n", "\n", ".. math::\n", "\n", " \\bar{x}_\\mathcal{B} = \\begin{bmatrix} 1\\\\ 1 \\end{bmatrix}\n", " \\quad \\text{and} \\quad\n", " \\bar{z}_\\mathcal{N} = \\begin{bmatrix} 1\\\\ 1 \\end{bmatrix}.\n", "\n", "Iteration 1\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{-3}{1}, -\\frac{1}{1}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{1}{1}, -\\frac{-4}{1}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= 3\n", "\n", " shows that :math:`x_4` is the leaving variable.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`i = 4 \\in \\mathcal{B}`, so do one step of\n", " the dual simplex method.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix} 1 & -1\\\\ -1 & 1 \\end{bmatrix}\n", " \\begin{bmatrix} 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ -1 \\end{bmatrix}.\n", "\n", " The index of the entering variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{j \\in \\mathcal{N}}\n", " \\left\\{\n", " \\frac{z^*_j + \\mu^* \\bar{z}_j}{\\Delta z_j} \\colon \\Delta z_j > 0\n", " \\right\\}\n", " &= \\argmin_{j \\in \\mathcal{N}}\\left\\{\n", " \\frac{-3 + \\mu^*}{1}\n", " \\right\\}\\\\\n", " &= 1.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " B^{-1} N e_j =\n", " \\begin{bmatrix} 1 & -1\\\\ -1 & 1 \\end{bmatrix}\n", " \\begin{bmatrix} 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ -1 \\end{bmatrix}.\n", "\n", "Step 3\n", " The step length adjustments are given by\n", "\n", " .. math::\n", "\n", " t &= \\frac{x^*_i}{\\Delta x_i} = \\frac{-4}{-1} = 4\n", " \\quad & \\quad\n", " \\bar{t} = \\frac{\\bar{x}_i}{\\Delta x_i} = \\frac{1}{-1} = -1\\\\\n", " s &= \\frac{z^*_j}{\\Delta z_j} = \\frac{-3}{1} = -3\n", " \\quad & \\quad\n", " \\bar{s} = \\frac{\\bar{z}_j}{\\Delta z_j} = \\frac{1}{1} = 1.\n", "\n", "Step 4\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} &\\leftarrow x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1\\\\ -4 \\end{bmatrix} -\n", " (4) \\begin{bmatrix} 1\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} -3\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " x^*_j &\\leftarrow t = 4\\\\\n", " \\bar{x}_\\mathcal{B} &\\leftarrow\n", " \\bar{x}_\\mathcal{B} - \\bar{t} \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1\\\\ 1 \\end{bmatrix} -\n", " (-1) \\begin{bmatrix} 1\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 2\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{x}_j &\\leftarrow \\bar{t} = -1\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} &\\leftarrow z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} -3\\\\ 1 \\end{bmatrix} -\n", " (-3) \\begin{bmatrix} 1\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ -2 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_i &\\leftarrow s = -3\\\\\n", " \\bar{z}_\\mathcal{N} &\\leftarrow\n", " \\bar{z}_\\mathcal{N} - \\bar{s} \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ 1 \\end{bmatrix} -\n", " (1) \\begin{bmatrix} 1\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 2 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_i &\\leftarrow \\bar{s} = 1.\n", "\n", "Step 5\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 3, 1 \\} \\quad & \\quad \\mathcal{N} &= \\{ 4, 2 \\}\\\\\n", " B &= \\begin{bmatrix} 1 & 1\\\\ 0 & -1 \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 0 & -1\\\\ 1 & 1 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} -3\\\\ 4 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} -3\\\\ -2 \\end{bmatrix}\\\\\n", " \\bar{x}_\\mathcal{B} &= \\begin{bmatrix} 2\\\\ -1 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_\\mathcal{N} &= \\begin{bmatrix} 1\\\\ 2 \\end{bmatrix}.\n", "\n", "Iteration 2\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{-3}{1}, -\\frac{-2}{2}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{-3}{2}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= 3\n", "\n", " shows that :math:`x_4` is the entering variable.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`j = 4 \\in \\mathcal{N}`, so do one step of\n", " the primal simplex method.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " B^{-1} N e_j =\n", " \\begin{bmatrix} 1 & 0\\\\ -1 & -1 \\end{bmatrix}\n", " \\begin{bmatrix} 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ -1 \\end{bmatrix}.\n", "\n", " The index of the leaving variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{i \\in \\mathcal{B}}\n", " \\left\\{\n", " \\frac{x^*_i + \\mu^* \\bar{x}_i}{\\Delta x_i} \\colon \\Delta x_i > 0\n", " \\right\\}\n", " &= \\argmin_{i \\in \\mathcal{B}}\\left\\{\n", " \\frac{-3 + \\mu^* (2)}{1}\n", " \\right\\}\\\\\n", " &= 3.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix} 1 & -1\\\\ 0 & -1 \\end{bmatrix}\n", " \\begin{bmatrix} 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -1\\\\ 0 \\end{bmatrix}.\n", "\n", "Step 3\n", " The step length adjustments are given by\n", "\n", " .. math::\n", "\n", " t &= \\frac{x^*_i}{\\Delta x_i} = \\frac{-3}{1} = -3\n", " \\quad & \\quad\n", " \\bar{t} = \\frac{\\bar{x}_i}{\\Delta x_i} = \\frac{2}{1} = 2\\\\\n", " s &= \\frac{z^*_j}{\\Delta z_j} = \\frac{-3}{-1} = 3\n", " \\quad & \\quad\n", " \\bar{s} = \\frac{\\bar{z}_j}{\\Delta z_j} = \\frac{1}{-1} = -1.\n", "\n", "Step 4\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} &\\leftarrow x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} -3\\\\ 4 \\end{bmatrix} -\n", " (-3) \\begin{bmatrix} 1\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 1 \\end{bmatrix}\n", " \\quad & \\quad\n", " x^*_j &\\leftarrow t = -3\\\\\n", " \\bar{x}_\\mathcal{B} &\\leftarrow\n", " \\bar{x}_\\mathcal{B} - \\bar{t} \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 2\\\\ -1 \\end{bmatrix} -\n", " (2) \\begin{bmatrix} 1\\\\ -1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 1 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{x}_j &\\leftarrow \\bar{t} = 2\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} &\\leftarrow z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} -3\\\\ -2 \\end{bmatrix} -\n", " (3) \\begin{bmatrix} -1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ -2 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_i &\\leftarrow s = 3\\\\\n", " \\bar{z}_\\mathcal{N} &\\leftarrow\n", " \\bar{z}_\\mathcal{N} - \\bar{s} \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ 2 \\end{bmatrix} -\n", " (-1) \\begin{bmatrix} -1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 2 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_i &\\leftarrow \\bar{s} = -1.\n", "\n", "Step 5\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 4, 1 \\} \\quad & \\quad \\mathcal{N} &= \\{ 3, 2 \\}\\\\\n", " B &= \\begin{bmatrix} 0 & 1\\\\ 1 & -1 \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix} 1 & -1\\\\ 0 & 1 \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} -3\\\\ 1 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix} 3\\\\ -2 \\end{bmatrix}\\\\\n", " \\bar{x}_\\mathcal{B} &= \\begin{bmatrix} 2\\\\ 1 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_\\mathcal{N} &= \\begin{bmatrix} -1\\\\ 2 \\end{bmatrix}.\n", "\n", "Iteration 3\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{-2}{2}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{-3}{2}, -\\frac{1}{1}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= 1.5\n", "\n", " shows that :math:`x_4` is the leaving variable.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`i = 4 \\in \\mathcal{B}`, so do one step of\n", " the dual simplex method.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix} 1 & 1\\\\ 0 & -1 \\end{bmatrix}\n", " \\begin{bmatrix} 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -1\\\\ 0 \\end{bmatrix}.\n", "\n", " The index of the entering variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{j \\in \\mathcal{N}}\n", " \\left\\{\n", " \\frac{z^*_j + \\mu^* \\bar{z}_j}{\\Delta z_j} \\colon \\Delta z_j > 0\n", " \\right\\} = \\emptyset.\n", "\n", " Therefore, the dual is unbounded i.e. the primal is infeasible." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 7.9\n", "============\n", "\n", "Notice that parametric self-dual simplex method assumes perturbations are all\n", "strictly positive i.e. :math:`\\bar{x}_\\mathcal{B} > 0` and\n", ":math:`\\bar{z}_\\mathcal{N} > 0`.\n", "\n", "The following is a proof by contradiction. Suppose :math:`P_\\mu` is infeasible\n", "and :math:`\\exists \\mu' \\leq \\mu` such that :math:`P_{\\mu'}` is infeasible.\n", "These statements translate to\n", "\n", ".. math::\n", "\n", " x^*_i + \\mu \\bar{x}_i < 0\n", " \\quad \\land \\quad\n", " x^*_i + \\mu' \\bar{x}_i \\geq 0\n", "\n", "where :math:`i \\in \\mathcal{B}`. By inspection,\n", "\n", ".. math::\n", "\n", " x^*_i + \\mu' \\bar{x}_i &> x^*_i + \\mu \\bar{x}_i\\\\\n", " \\mu' \\bar{x}_i &> \\mu \\bar{x}_i\\\\\n", " 0 &> (\\mu - \\mu') \\bar{x}_i,\n", "\n", "which is a contradiction because neither factors are negative. The analogous\n", "proof for the perturbed dual problem can be realized by replacing\n", ":math:`x^*_i` with :math:`z^*_j` and :math:`\\bar{x}_i` with :math:`\\bar{z}_j`\n", "where :math:`j \\in \\mathcal{N}`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 7.10\n", "=============\n", "\n", "Failing to proceed during the primal simplex step implies that the primal is\n", "unbounded and the dual problem is infeasible (i.e. :math:`z^*_\\mathcal{N}` has\n", "some negative components). Likewise, failing to proceed during the dual simplex\n", "step implies that the dual is unbounded and the original problem is infeasible\n", "i.e. (i.e. :math:`x^*_\\mathcal{B}` has some negative components). These\n", "conditions can be detected when taking the\n", ":math:`\\argmin` gives the :math:`\\emptyset`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-7.11:\n", "\n", "Exercise 7.11\n", "=============\n", "\n", "Rewriting the standard form LP into matrix form yields\n", "\n", ".. math::\n", "\n", " \\mathcal{B} &= \\{ 5, 6, 7, 8 \\} \\quad & \\quad\n", " \\mathcal{N} &= \\{ 0, 1, 2, 3, 4 \\}\\\\\n", " B &= \\mathbf{I}_4 \\quad & \\quad\n", " N &= \\begin{bmatrix}\n", " 1 & -1 & 0 & 0 & 0\\\\\n", " 1 & 0 & -1 & 0 & 0\\\\\n", " 1 & 0 & 0 & -1 & 0\\\\\n", " 1 & 0 & 0 & 0 & -1\n", " \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= b = \\begin{bmatrix} 1\\\\ 2\\\\ 4\\\\ 8 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= -c_\\mathcal{N} =\n", " \\begin{bmatrix} -4 + 4 \\mu' \\\\ 2\\\\ 2\\\\ 2\\\\ 2 \\end{bmatrix}.\n", "\n", "To analyze the one parameter family of LPs, define\n", "\n", ".. math::\n", "\n", " \\bar{x}_\\mathcal{B} = \\begin{bmatrix} 1\\\\ 1\\\\ 1\\\\ 1 \\end{bmatrix}\n", " \\quad \\text{and} \\quad\n", " \\bar{z}_\\mathcal{N} = \\begin{bmatrix} 1\\\\ 1\\\\ 1\\\\ 1\\\\ 1 \\end{bmatrix}.\n", "\n", "Evaluating :math:`x^*_\\mathcal{B} + \\bar{x}_\\mathcal{B} \\mu \\geq \\boldsymbol{0}`\n", "and :math:`z^*_\\mathcal{N} + \\bar{z}_\\mathcal{N} \\mu \\geq \\boldsymbol{0}`\n", "reveals the current range for :math:`\\mu` is\n", "\n", ".. math::\n", "\n", " 4 - 4 \\mu' \\leq \\mu \\leq \\infty.\n", "\n", "By inspection, the initial dictionary is optimal as long as :math:`\\mu' \\geq 1`.\n", "\n", "Iteration 1\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{-4 + 4 \\mu'}{1},\n", " -\\frac{2}{1}, -\\frac{2}{1}, -\\frac{2}{1}, -\\frac{2}{1}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= 4 - 4 \\mu'\n", "\n", " shows that :math:`x_0` is the entering variable for :math:`\\mu' < 1`.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`j = 0 \\in \\mathcal{N}`, so do one step of\n", " the primal simplex method.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " B^{-1} N e_j =\n", " \\begin{bmatrix}\n", " 1 & -1 & 0 & 0 & 0\\\\\n", " 1 & 0 & -1 & 0 & 0\\\\\n", " 1 & 0 & 0 & -1 & 0\\\\\n", " 1 & 0 & 0 & 0 & -1\n", " \\end{bmatrix} \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ 1\\\\ 1\\\\ 1 \\end{bmatrix}.\n", "\n", " The index of the leaving variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{i \\in \\mathcal{B}}\n", " \\left\\{\n", " \\frac{x^*_i + \\mu^* \\bar{x}_i}{\\Delta x_i} \\colon \\Delta x_i > 0\n", " \\right\\}\n", " &= \\argmin_{i \\in \\mathcal{B}}\\left\\{\n", " \\frac{1 + \\mu^* (1)}{1},\n", " \\frac{2 + \\mu^* (1)}{1},\n", " \\frac{4 + \\mu^* (1)}{1},\n", " \\frac{8 + \\mu^* (1)}{1}\n", " \\right\\}\\\\\n", " &= 5.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix}\n", " 1 & 1 & 1 & 1\\\\\n", " -1 & 0 & 0 & 0\\\\\n", " 0 & -1 & 0 & 0\\\\\n", " 0 & 0 & -1 & 0\\\\\n", " 0 & 0 & 0 & -1\n", " \\end{bmatrix} \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -1\\\\ 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix}.\n", "\n", "Step 3\n", " The step length adjustments are given by\n", "\n", " .. math::\n", "\n", " t &= \\frac{x^*_i}{\\Delta x_i} = \\frac{1}{1} = 1\n", " \\quad & \\quad\n", " \\bar{t} = \\frac{\\bar{x}_i}{\\Delta x_i} = \\frac{1}{1} = 1\\\\\n", " s &= \\frac{z^*_j}{\\Delta z_j} = \\frac{-4 + 4 \\mu'}{-1} = 4 - 4 \\mu'\n", " \\quad & \\quad\n", " \\bar{s} = \\frac{\\bar{z}_j}{\\Delta z_j} = \\frac{1}{-1} = -1.\n", "\n", "Step 4\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} &\\leftarrow x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1\\\\ 2\\\\ 4\\\\ 8 \\end{bmatrix} -\n", " (1) \\begin{bmatrix} 1\\\\ 1\\\\ 1\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 1\\\\ 3\\\\ 7 \\end{bmatrix}\n", " \\quad & \\quad\n", " x^*_j &\\leftarrow t = 1\\\\\n", " \\bar{x}_\\mathcal{B} &\\leftarrow\n", " \\bar{x}_\\mathcal{B} - \\bar{t} \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1\\\\ 1\\\\ 1\\\\ 1 \\end{bmatrix} -\n", " (1) \\begin{bmatrix} 1\\\\ 1\\\\ 1\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{x}_j &\\leftarrow \\bar{t} = 1\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} &\\leftarrow z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} -4 + 4 \\mu' \\\\ 2\\\\ 2\\\\ 2\\\\ 2 \\end{bmatrix} -\n", " (4 - 4 \\mu') \\begin{bmatrix} -1\\\\ 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ -2 + 4 \\mu'\\\\ 2\\\\ 2\\\\ 2 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_i &\\leftarrow s = 4 - 4 \\mu'\\\\\n", " \\bar{z}_\\mathcal{N} &\\leftarrow\n", " \\bar{z}_\\mathcal{N} - \\bar{s} \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ 1\\\\ 1\\\\ 1\\\\ 1 \\end{bmatrix} -\n", " (-1) \\begin{bmatrix} -1\\\\ 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 2\\\\ 1\\\\ 1\\\\ 1 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_i &\\leftarrow \\bar{s} = -1.\n", "\n", "Step 5\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 0, 6, 7, 8 \\} \\quad & \\quad\n", " \\mathcal{N} &= \\{ 5, 1, 2, 3, 4 \\}\\\\\n", " B &= \\begin{bmatrix}\n", " 1 & 0 & 0 & 0\\\\\n", " 1 & 1 & 0 & 0\\\\\n", " 1 & 0 & 1 & 0\\\\\n", " 1 & 0 & 0 & 1\\\\\n", " \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix}\n", " 1 & -1 & 0 & 0 & 0\\\\\n", " 0 & 0 & -1 & 0 & 0\\\\\n", " 0 & 0 & 0 & -1 & 0\\\\\n", " 0 & 0 & 0 & 0 & -1\n", " \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} 1\\\\ 1\\\\ 3\\\\ 7 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix}\n", " 4 - 4 \\mu'\\\\ -2 + 4 \\mu'\\\\ 2\\\\ 2\\\\ 2\n", " \\end{bmatrix}\\\\\n", " \\bar{x}_\\mathcal{B} &= \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_\\mathcal{N} &= \\begin{bmatrix} -1\\\\ 2\\\\ 1\\\\ 1\\\\ 1 \\end{bmatrix}.\n", "\n", " The current range for :math:`\\mu` is\n", "\n", " .. math::\n", "\n", " \\frac{2 - 4 \\mu'}{2} \\leq \\mu \\leq 4 - 4 \\mu'.\n", "\n", " By inspection, the dictionary is optimal as long as\n", " :math:`0.5 \\leq \\mu' \\leq 1`.\n", "\n", "Iteration 2\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{-2 + 4 \\mu'}{2}, -\\frac{2}{1}, -\\frac{2}{1}, -\\frac{2}{1}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{1}{1}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= 1 - 2 \\mu'\n", "\n", " shows that :math:`x_1` is the entering variable for :math:`\\mu' < 0.5`.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`j = 1 \\in \\mathcal{N}`, so do one step of\n", " the primal simplex method.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " B^{-1} N e_j =\n", " \\begin{bmatrix}\n", " 1 & -1 & 0 & 0 & 0\\\\\n", " -1 & 1 & -1 & 0 & 0\\\\\n", " -1 & 1 & 0 & -1 & 0\\\\\n", " -1 & 1 & 0 & 0 & -1\n", " \\end{bmatrix} \\begin{bmatrix} 0\\\\ 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -1\\\\ 1\\\\ 1\\\\ 1 \\end{bmatrix}.\n", "\n", " The index of the leaving variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{i \\in \\mathcal{B}}\n", " \\left\\{\n", " \\frac{x^*_i + \\mu^* \\bar{x}_i}{\\Delta x_i} \\colon \\Delta x_i > 0\n", " \\right\\}\n", " &= \\argmin_{i \\in \\mathcal{B}}\\left\\{\n", " \\frac{1 + \\mu^* (0)}{1},\n", " \\frac{3 + \\mu^* (0)}{1},\n", " \\frac{7 + \\mu^* (0)}{1}\n", " \\right\\}\\\\\n", " &= 6.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix}\n", " 1 & -1 & -1 & -1\\\\\n", " -1 & 1 & 1 & 1\\\\\n", " 0 & -1 & 0 & 0\\\\\n", " 0 & 0 & -1 & 0\\\\\n", " 0 & 0 & 0 & -1\n", " \\end{bmatrix} \\begin{bmatrix} 0\\\\ 1\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ -1\\\\ 1\\\\ 0\\\\ 0 \\end{bmatrix}.\n", "\n", "Step 3\n", " The step length adjustments are given by\n", "\n", " .. math::\n", "\n", " t &= \\frac{x^*_i}{\\Delta x_i} = \\frac{1}{1} = 1\n", " \\quad & \\quad\n", " \\bar{t} = \\frac{\\bar{x}_i}{\\Delta x_i} = \\frac{0}{1} = 0\\\\\n", " s &= \\frac{z^*_j}{\\Delta z_j} = \\frac{-2 + 4 \\mu'}{-1} = 2 - 4 \\mu'\n", " \\quad & \\quad\n", " \\bar{s} = \\frac{\\bar{z}_j}{\\Delta z_j} = \\frac{2}{-1} = -2.\n", "\n", "Step 4\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} &\\leftarrow x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1\\\\ 1\\\\ 3\\\\ 7 \\end{bmatrix} -\n", " (1) \\begin{bmatrix} -1\\\\ 1\\\\ 1\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 2\\\\ 0\\\\ 2\\\\ 6 \\end{bmatrix}\n", " \\quad & \\quad\n", " x^*_j &\\leftarrow t = 1\\\\\n", " \\bar{x}_\\mathcal{B} &\\leftarrow\n", " \\bar{x}_\\mathcal{B} - \\bar{t} \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix} -\n", " (0) \\begin{bmatrix} -1\\\\ 1\\\\ 1\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{x}_j &\\leftarrow \\bar{t} = 0\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} &\\leftarrow z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 4 - 4 \\mu' \\\\ -2 + 4 \\mu'\\\\ 2\\\\ 2\\\\ 2 \\end{bmatrix} -\n", " (2 - 4 \\mu') \\begin{bmatrix} 1\\\\ -1\\\\ 1\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 2\\\\ 0\\\\ 4 \\mu'\\\\ 2\\\\ 2 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_i &\\leftarrow s = 2 - 4 \\mu'\\\\\n", " \\bar{z}_\\mathcal{N} &\\leftarrow\n", " \\bar{z}_\\mathcal{N} - \\bar{s} \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} -1\\\\ 2\\\\ 1\\\\ 1\\\\ 1 \\end{bmatrix} -\n", " (-2) \\begin{bmatrix} 1\\\\ -1\\\\ 1\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 3\\\\ 1\\\\ 1 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_i &\\leftarrow \\bar{s} = -2.\n", "\n", "Step 5\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 0, 1, 7, 8 \\} \\quad & \\quad\n", " \\mathcal{N} &= \\{ 5, 6, 2, 3, 4 \\}\\\\\n", " B &= \\begin{bmatrix}\n", " 1 & -1 & 0 & 0\\\\\n", " 1 & 0 & 0 & 0\\\\\n", " 1 & 0 & 1 & 0\\\\\n", " 1 & 0 & 0 & 1\\\\\n", " \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix}\n", " 1 & 0 & 0 & 0 & 0\\\\\n", " 0 & 1 & -1 & 0 & 0\\\\\n", " 0 & 0 & 0 & -1 & 0\\\\\n", " 0 & 0 & 0 & 0 & -1\n", " \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} 2\\\\ 1\\\\ 2\\\\ 6 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix}\n", " 2\\\\ 2 - 4 \\mu'\\\\ 4 \\mu'\\\\ 2\\\\ 2\n", " \\end{bmatrix}\\\\\n", " \\bar{x}_\\mathcal{B} &= \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_\\mathcal{N} &= \\begin{bmatrix} 1\\\\ -2\\\\ 3\\\\ 1\\\\ 1 \\end{bmatrix}.\n", "\n", " The current range for :math:`\\mu` is\n", "\n", " .. math::\n", "\n", " \\frac{-4 \\mu'}{3} \\leq \\mu \\leq \\frac{2 - 4 \\mu'}{2}.\n", "\n", " By inspection, the dictionary is optimal as long as\n", " :math:`0 \\leq \\mu' \\leq 0.5`.\n", "\n", "Iteration 3\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{2}{1}, -\\frac{4 \\mu'}{3}, -\\frac{2}{1}, -\\frac{2}{1}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{2}{1}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= -\\frac{4}{3} \\mu'\n", "\n", " shows that :math:`x_2` is the entering variable for :math:`\\mu' < 0`.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`j = 2 \\in \\mathcal{N}`, so do one step of\n", " the primal simplex method.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " B^{-1} N e_j =\n", " \\begin{bmatrix}\n", " 0 & 1 & -1 & 0 & 0\\\\\n", " -1 & 1 & -1 & 0 & 0\\\\\n", " 0 & -1 & 1 & -1 & 0\\\\\n", " 0 & -1 & 1 & 0 & -1\n", " \\end{bmatrix} \\begin{bmatrix} 0\\\\ 0\\\\ 1\\\\ 0\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -1\\\\ -1\\\\ 1\\\\ 1 \\end{bmatrix}.\n", "\n", " The index of the leaving variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{i \\in \\mathcal{B}}\n", " \\left\\{\n", " \\frac{x^*_i + \\mu^* \\bar{x}_i}{\\Delta x_i} \\colon \\Delta x_i > 0\n", " \\right\\}\n", " &= \\argmin_{i \\in \\mathcal{B}}\\left\\{\n", " \\frac{2 + \\mu^* (0)}{1},\n", " \\frac{6 + \\mu^* (0)}{1}\n", " \\right\\}\\\\\n", " &= 7.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix}\n", " 0 & -1 & 0 & 0\\\\\n", " 1 & 1 & -1 & -1\\\\\n", " -1 & -1 & 1 & 1\\\\\n", " 0 & 0 & -1 & 0\\\\\n", " 0 & 0 & 0 & -1\n", " \\end{bmatrix} \\begin{bmatrix} 0\\\\ 0\\\\ 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 1\\\\ -1\\\\ 1\\\\ 0 \\end{bmatrix}.\n", "\n", "Step 3\n", " The step length adjustments are given by\n", "\n", " .. math::\n", "\n", " t &= \\frac{x^*_i}{\\Delta x_i} = \\frac{2}{1} = 2\n", " \\quad & \\quad\n", " \\bar{t} = \\frac{\\bar{x}_i}{\\Delta x_i} = \\frac{0}{1} = 0\\\\\n", " s &= \\frac{z^*_j}{\\Delta z_j} = \\frac{4 \\mu'}{-1} = -4 \\mu'\n", " \\quad & \\quad\n", " \\bar{s} = \\frac{\\bar{z}_j}{\\Delta z_j} = \\frac{3}{-1} = -3.\n", "\n", "Step 4\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} &\\leftarrow x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 2\\\\ 1\\\\ 2\\\\ 6 \\end{bmatrix} -\n", " (2) \\begin{bmatrix} -1\\\\ -1\\\\ 1\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 4\\\\ 3\\\\ 0\\\\ 4 \\end{bmatrix}\n", " \\quad & \\quad\n", " x^*_j &\\leftarrow t = 2\\\\\n", " \\bar{x}_\\mathcal{B} &\\leftarrow\n", " \\bar{x}_\\mathcal{B} - \\bar{t} \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix} -\n", " (0) \\begin{bmatrix} -1\\\\ -1\\\\ 1\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{x}_j &\\leftarrow \\bar{t} = 0\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} &\\leftarrow z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 2 \\\\ 2 - 4 \\mu'\\\\ 4 \\mu'\\\\ 2\\\\ 2 \\end{bmatrix} -\n", " (-4 \\mu') \\begin{bmatrix} 0\\\\ 1\\\\ -1\\\\ 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 2\\\\ 2\\\\ 0\\\\ 2 + 4 \\mu'\\\\ 2 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_i &\\leftarrow s = -4 \\mu'\\\\\n", " \\bar{z}_\\mathcal{N} &\\leftarrow\n", " \\bar{z}_\\mathcal{N} - \\bar{s} \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ -2\\\\ 3\\\\ 1\\\\ 1 \\end{bmatrix} -\n", " (-3) \\begin{bmatrix} 0\\\\ 1\\\\ -1\\\\ 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ 1\\\\ 0\\\\ 4\\\\ 1 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_i &\\leftarrow \\bar{s} = -3.\n", "\n", "Step 5\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 0, 1, 2, 8 \\} \\quad & \\quad\n", " \\mathcal{N} &= \\{ 5, 6, 7, 3, 4 \\}\\\\\n", " B &= \\begin{bmatrix}\n", " 1 & -1 & 0 & 0\\\\\n", " 1 & 0 & -1 & 0\\\\\n", " 1 & 0 & 0 & 0\\\\\n", " 1 & 0 & 0 & 1\\\\\n", " \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix}\n", " 1 & 0 & 0 & 0 & 0\\\\\n", " 0 & 1 & 0 & 0 & 0\\\\\n", " 0 & 0 & 1 & -1 & 0\\\\\n", " 0 & 0 & 0 & 0 & -1\n", " \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} 4\\\\ 3\\\\ 2\\\\ 4 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix}\n", " 2\\\\ 2\\\\ -4 \\mu'\\\\ 2 + 4 \\mu'\\\\ 2\n", " \\end{bmatrix}\\\\\n", " \\bar{x}_\\mathcal{B} &= \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_\\mathcal{N} &= \\begin{bmatrix} 1\\\\ 1\\\\ -3\\\\ 4\\\\ 1 \\end{bmatrix}.\n", "\n", " The current range for :math:`\\mu` is\n", "\n", " .. math::\n", "\n", " \\frac{-2 - 4 \\mu'}{4} \\leq \\mu \\leq \\frac{-4 \\mu'}{3}.\n", "\n", " By inspection, the dictionary is optimal as long as\n", " :math:`-0.5 \\leq \\mu' \\leq 0`.\n", "\n", "Iteration 4\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{2}{1}, -\\frac{2}{1},\n", " -\\frac{-4 \\mu'}{4}, -\\frac{2 + 4 \\mu'}{1}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{4}{1}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= -2 - 4 \\mu'\n", "\n", " shows that :math:`x_3` is the entering variable for :math:`\\mu' < -0.5`.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`j = 3 \\in \\mathcal{N}`, so do one step of\n", " the primal simplex method.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " B^{-1} N e_j =\n", " \\begin{bmatrix}\n", " 0 & 0 & 1 & -1 & 0\\\\\n", " -1 & 0 & 1 & -1 & 0\\\\\n", " 0 & -1 & 1 & -1 & 0\\\\\n", " 0 & 0 & -1 & 1 & -1\n", " \\end{bmatrix} \\begin{bmatrix} 0\\\\ 0\\\\ 0\\\\ 1\\\\ 0 \\end{bmatrix} =\n", " \\begin{bmatrix} -1\\\\ -1\\\\ -1\\\\ 1 \\end{bmatrix}.\n", "\n", " The index of the leaving variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{i \\in \\mathcal{B}}\n", " \\left\\{\n", " \\frac{x^*_i + \\mu^* \\bar{x}_i}{\\Delta x_i} \\colon \\Delta x_i > 0\n", " \\right\\}\n", " &= \\argmin_{i \\in \\mathcal{B}}\\left\\{\n", " \\frac{4 + \\mu^* (0)}{1}\n", " \\right\\}\\\\\n", " &= 8.\n", "\n", " The dual step direction is\n", "\n", " .. math::\n", "\n", " \\Delta z_\\mathcal{N} =\n", " -\\left( B^{-1} N \\right)^\\top e_i =\n", " -\\begin{bmatrix}\n", " 0 & -1 & 0 & 0\\\\\n", " 0 & 0 & -1 & 0\\\\\n", " 1 & 1 & 1 & -1\\\\\n", " -1 & -1 & -1 & 1\\\\\n", " 0 & 0 & 0 & -1\n", " \\end{bmatrix} \\begin{bmatrix} 0\\\\ 0\\\\ 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 0\\\\ 0\\\\ 1\\\\ -1\\\\ 1 \\end{bmatrix}.\n", "\n", "Step 3\n", " The step length adjustments are given by\n", "\n", " .. math::\n", "\n", " t &= \\frac{x^*_i}{\\Delta x_i} = \\frac{4}{1} = 4\n", " \\quad & \\quad\n", " \\bar{t} = \\frac{\\bar{x}_i}{\\Delta x_i} = \\frac{0}{1} = 0\\\\\n", " s &= \\frac{z^*_j}{\\Delta z_j} = \\frac{2 + 4 \\mu'}{-1} = -2 - 4 \\mu'\n", " \\quad & \\quad\n", " \\bar{s} = \\frac{\\bar{z}_j}{\\Delta z_j} = \\frac{4}{-1} = -4.\n", "\n", "Step 4\n", " The current primal and dual solutions are updated to\n", "\n", " .. math::\n", "\n", " x^*_\\mathcal{B} &\\leftarrow x^*_\\mathcal{B} - t \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 4\\\\ 3\\\\ 2\\\\ 4 \\end{bmatrix} -\n", " (4) \\begin{bmatrix} -1\\\\ -1\\\\ -1\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 8\\\\ 7\\\\ 6\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " x^*_j &\\leftarrow t = 4\\\\\n", " \\bar{x}_\\mathcal{B} &\\leftarrow\n", " \\bar{x}_\\mathcal{B} - \\bar{t} \\Delta x_\\mathcal{B} =\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix} -\n", " (0) \\begin{bmatrix} -1\\\\ -1\\\\ -1\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{x}_j &\\leftarrow \\bar{t} = 0\n", "\n", " and\n", "\n", " .. math::\n", "\n", " z^*_\\mathcal{N} &\\leftarrow z^*_\\mathcal{N} - s \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 2 \\\\ 2\\\\ -4 \\mu'\\\\ 2 + 4 \\mu'\\\\ 2 \\end{bmatrix} -\n", " (-2 - 4 \\mu') \\begin{bmatrix} 0\\\\ 0\\\\ 1\\\\ -1\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 2\\\\ 2\\\\ 2\\\\ 0\\\\ 4 + 4 \\mu' \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_i &\\leftarrow s = -2 - 4 \\mu'\\\\\n", " \\bar{z}_\\mathcal{N} &\\leftarrow\n", " \\bar{z}_\\mathcal{N} - \\bar{s} \\Delta z_\\mathcal{N} =\n", " \\begin{bmatrix} 1\\\\ 1\\\\ -3\\\\ 4\\\\ 1 \\end{bmatrix} -\n", " (-4) \\begin{bmatrix} 0\\\\ 0\\\\ 1\\\\ -1\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} 1\\\\ 1\\\\ 1\\\\ 0\\\\ 5 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_i &\\leftarrow \\bar{s} = -4.\n", "\n", "Step 5\n", " The current basis is updated to\n", "\n", " .. math::\n", "\n", " \\mathcal{B} &= \\{ 0, 1, 2, 3 \\} \\quad & \\quad\n", " \\mathcal{N} &= \\{ 5, 6, 7, 8, 4 \\}\\\\\n", " B &= \\begin{bmatrix}\n", " 1 & -1 & 0 & 0\\\\\n", " 1 & 0 & -1 & 0\\\\\n", " 1 & 0 & 0 & -1\\\\\n", " 1 & 0 & 0 & 0\\\\\n", " \\end{bmatrix} \\quad & \\quad\n", " N &= \\begin{bmatrix}\n", " 1 & 0 & 0 & 0 & 0\\\\\n", " 0 & 1 & 0 & 0 & 0\\\\\n", " 0 & 0 & 1 & 0 & 0\\\\\n", " 0 & 0 & 0 & 1 & -1\n", " \\end{bmatrix}\\\\\n", " x^*_\\mathcal{B} &= \\begin{bmatrix} 8\\\\ 7\\\\ 6\\\\ 4 \\end{bmatrix}\n", " \\quad & \\quad\n", " z^*_\\mathcal{N} &= \\begin{bmatrix}\n", " 2\\\\ 2\\\\ 2\\\\ -2 - 4 \\mu'\\\\ 4 + 4 \\mu'\n", " \\end{bmatrix}\\\\\n", " \\bar{x}_\\mathcal{B} &= \\begin{bmatrix} 1\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix}\n", " \\quad & \\quad\n", " \\bar{z}_\\mathcal{N} &= \\begin{bmatrix} 1\\\\ 1\\\\ 1\\\\ -4\\\\ 5 \\end{bmatrix}.\n", "\n", " The current range for :math:`\\mu` is\n", "\n", " .. math::\n", "\n", " \\frac{-4 - 4 \\mu'}{5} \\leq \\mu \\leq \\frac{-2 - 4 \\mu'}{4}.\n", "\n", " By inspection, the dictionary is optimal as long as\n", " :math:`-1 \\leq \\mu' \\leq -0.5`.\n", "\n", "Iteration 5\n", "-----------\n", "\n", "Step 1\n", " Computing\n", "\n", " .. math::\n", "\n", " \\mu^*\n", " &= \\max\\left\\{\n", " \\max_{j \\in \\mathcal{N}, \\bar{z}_j > 0} -\\frac{z^*_j}{\\bar{z}_j},\n", " \\max_{i \\in \\mathcal{B}, \\bar{x}_i > 0} -\\frac{x^*_i}{\\bar{x}_i},\n", " \\right\\}\\\\\n", " &= \\max\\left\\{\n", " \\max\\left\\{\n", " -\\frac{2}{1}, -\\frac{2}{1}, -\\frac{2}{1}, -\\frac{4 + 4 \\mu'}{5}\n", " \\right\\},\n", " \\max\\left\\{\n", " -\\frac{4}{1}\n", " \\right\\}\n", " \\right\\}\\\\\n", " &= -\\frac{4 + 4 \\mu'}{5}\n", "\n", " shows that :math:`x_4` is the entering variable for :math:`\\mu' < -1`.\n", "\n", "Step 2\n", " The maximum is achieved by :math:`j = 4 \\in \\mathcal{N}`, so do one step of\n", " the primal simplex method.\n", "\n", " The primal step direction is\n", "\n", " .. math::\n", "\n", " \\Delta x_\\mathcal{B} =\n", " B^{-1} N e_j =\n", " \\begin{bmatrix}\n", " 0 & 0 & 0 & 1 & -1\\\\\n", " -1 & 0 & 0 & 1 & -1\\\\\n", " 0 & -1 & 0 & 1 & -1\\\\\n", " 0 & 0 & -1 & 1 & -1\n", " \\end{bmatrix} \\begin{bmatrix} 0\\\\ 0\\\\ 0\\\\ 0\\\\ 1 \\end{bmatrix} =\n", " \\begin{bmatrix} -1\\\\ -1\\\\ -1\\\\ -1 \\end{bmatrix}.\n", "\n", " The index of the leaving variable is\n", "\n", " .. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{i \\in \\mathcal{B}}\n", " \\left\\{\n", " \\frac{x^*_i + \\mu^* \\bar{x}_i}{\\Delta x_i} \\colon \\Delta x_i > 0\n", " \\right\\} = \\emptyset.\n", "\n", " Therefore, the primal is unbounded (i.e. the dual is infeasible) when\n", " :math:`\\mu' < -1`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. rubric:: References\n", "\n", ".. bibliography:: chapter-07.bib" ] } ], "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 }