{ "cells": [ { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "********************************\n", "Efficiency of the Simplex Method\n", "********************************" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 4.1\n", "============\n", "\n", ".. list-table:: Pivots\n", " :header-rows: 1\n", "\n", " * - Largest-Coefficient Rule\n", " - Smallest-Index Rule\n", " * - :math:`x_2 \\leftrightarrow w_3`\n", " - :math:`x_1 \\leftrightarrow w_2`\n", " * - :math:`x_1 \\leftrightarrow w_1`\n", " - :math:`x_2 \\leftrightarrow w_1`\n", " * -\n", " - :math:`w_2 \\leftrightarrow w_3`" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 4.2\n", "============\n", "\n", ".. list-table:: Pivots\n", " :header-rows: 1\n", "\n", " * - Largest-Coefficient Rule\n", " - Smallest-Index Rule\n", " * - :math:`x_1 \\leftrightarrow w_1`\n", " - :math:`x_1 \\leftrightarrow w_1`\n", " * - :math:`x_2 \\leftrightarrow x_1`\n", " - :math:`x_2 \\leftrightarrow x_1`" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 4.3\n", "============\n", "\n", ".. list-table:: Pivots\n", " :header-rows: 1\n", "\n", " * - Largest-Coefficient Rule\n", " - Smallest-Index Rule\n", " * - :math:`x_2 \\leftrightarrow w_3`\n", " - :math:`x_1 \\leftrightarrow w_2`\n", " * - :math:`x_1 \\leftrightarrow w_1`\n", " - :math:`x_2 \\leftrightarrow w_1`\n", " * - :math:`w_3 \\leftrightarrow w_2`\n", " -" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 4.4\n", "============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 100 x_1 + 10 x_2 + x_3\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= 1 - x_1\\\\\n", " w_2 &= 100 - 20 x_1 - x_2\\\\\n", " w_3 &= 10000 - 200 x_1 - 20 x_2 - x_3\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Initial feasible solution:\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = 1, \\quad\n", " w_2 = 100, \\quad\n", " w_3 = 10000.\n", "\n", "Choose :math:`x_3` and :math:`w_3` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_3 = \\min\\left\\{ w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 10000 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 10000, \\quad\n", " w_1 = 1, \\quad\n", " w_2 = 100, \\quad\n", " w_3 = 0.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 10000 - 100 x_1 - 10 x_2 - w_3\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= 1 - x_1\\\\\n", " w_2 &= 100 - 20 x_1 - x_2\\\\\n", " x_3 &= 10000 - 200 x_1 - 20 x_2 - w_3\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 4.5\n", "============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -4 b_1 - 2 b_2 - b_3 + 8 x_1 + 4 x_2 + 2 x_3 + x_4\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= b_1 - x_1\\\\\n", " w_2 &= 2 b_1 + b_2 - 4 x_1 - x_2\\\\\n", " w_3 &= 4 b_1 + 2 b_2 + b_3 - 8 x_1 - 4 x_2 - x_3\\\\\n", " w_4 &= 8 b_1 + 4 b_2 + 2 b_3 + b_4 - 16 x_1 - 8 x_2 - 4 x_3 - x_4\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3, 4\n", " \\end{aligned}\n", "\n", ".. math::\n", "\n", " x_1 &\\leftrightarrow w_1\\\\\n", " x_2 &\\leftrightarrow w_2\\\\\n", " w_1 &\\leftrightarrow x_1\\\\\n", " x_3 &\\leftrightarrow w_3\\\\\n", " x_1 &\\leftrightarrow w_1\\\\\n", " w_2 &\\leftrightarrow x_2\\\\\n", " w_1 &\\leftrightarrow x_1\\\\\n", " x_4 &\\leftrightarrow w_4\\\\\n", " x_1 &\\leftrightarrow w_1\\\\\n", " x_2 &\\leftrightarrow w_2\\\\\n", " w_1 &\\leftrightarrow x_1\\\\\n", " w_3 &\\leftrightarrow x_3\\\\\n", " x_1 &\\leftrightarrow w_1\\\\\n", " w_2 &\\leftrightarrow x_2\\\\\n", " w_1 &\\leftrightarrow x_1\\\\" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-4.6:\n", "\n", "Exercise 4.6\n", "============\n", "\n", "Since :math:`w_{i < k}` do not contain :math:`x_k`, pivoting\n", ":math:`x_k \\leftrightarrow w_k` will only affect :math:`x_k`, :math:`w_k`,\n", ":math:`\\zeta`, and :math:`w_{k < i \\leq n}`:\n", "\n", ".. math::\n", "\n", " x_k &= \\sum_{j = 1}^{k - 1} \\epsilon_k \\epsilon_j 10^{k - j} (b_j - 2 x_j) +\n", " (b_k - w_k)\n", " = \\sum_{j = 1}^{k - 1} \\epsilon'_k \\epsilon'_j 10^{k - j} (b_j - 2 x_j) +\n", " (b_k - w_k)\\\\\n", " \\\\\n", " w_{i < k} &=\n", " \\sum_{j = 1}^{i - 1} \\epsilon_i \\epsilon_j 10^{i - j} (b_j - 2 x_j) +\n", " (b_k - x_i)\n", " = \\sum_{j = 1}^{i - 1} \\epsilon'_i \\epsilon'_j 10^{i - j} (b_j - 2 x_j) +\n", " (b_k - x_i)\n", "\n", ".. math::\n", "\n", " \\zeta &= -\\sum_{j = 1}^n \\epsilon_j 10^{n - j}\n", " \\left( \\frac{1}{2} b_j - x_j \\right)\\\\\n", " &= -\\epsilon_k 10^{n - k} \\left( \\frac{1}{2} b_k - x_k \\right) -\n", " \\sum_{j = 1}^{k - 1} \\epsilon_j 10^{n - j}\n", " \\left( \\frac{1}{2} b_j - x_j \\right) -\n", " \\sum_{j = k + 1}^n \\epsilon_j 10^{n - j}\n", " \\left( \\frac{1}{2} b_j - x_j \\right)\\\\\n", " &= -\\epsilon_k 10^{n - k} \\frac{1}{2} b_k + \\epsilon_k 10^{n - k}\n", " \\left[\n", " \\sum_{j = 1}^{k - 1} \\epsilon_k \\epsilon_j 10^{k - j} (b_j - 2 x_j) +\n", " (b_k - w_k)\n", " \\right] -\n", " \\sum_{j = 1}^{k - 1} \\epsilon_j 10^{n - j}\n", " \\left( \\frac{1}{2} b_j - x_j \\right) -\n", " \\sum_{j = k + 1}^n \\epsilon_j 10^{n - j}\n", " \\left( \\frac{1}{2} b_j - x_j \\right)\\\\\n", " &= -\\epsilon_k 10^{n - k} \\frac{1}{2} b_k +\n", " \\epsilon_k 10^{n - k} (b_k - w_k) +\n", " \\sum_{j = 1}^{k - 1} \\epsilon_j 10^{n - j} (b_j - 2 x_j) -\n", " \\sum_{j = 1}^{k - 1} \\epsilon_j 10^{n - j}\n", " \\left( \\frac{1}{2} b_j - x_j \\right) -\n", " \\sum_{j = k + 1}^n \\epsilon_j 10^{n - j}\n", " \\left( \\frac{1}{2} b_j - x_j \\right)\n", " & \\quad & \\text{since}\\ \\epsilon_k^2 = 1\\\\\n", " &= \\left[\n", " \\sum_{j = 1}^{k - 1} \\epsilon_j 10^{n - j}\n", " \\left( \\frac{1}{2} b_j - x_j \\right)\n", " \\right] +\n", " \\epsilon_k 10^{n - k} \\left( \\frac{1}{2} b_k - w_k \\right) -\n", " \\sum_{j = k + 1}^n \\epsilon_j 10^{n - j}\n", " \\left( \\frac{1}{2} b_j - x_j \\right)\\\\\n", " &= -\\epsilon'_k 10^{n - k} \\left( \\frac{1}{2} b_k - w_k \\right) -\n", " \\sum_{j = 1, j \\neq k}^n \\epsilon'_j 10^{n - j}\n", " \\left( \\frac{1}{2} b_j - x_j \\right)\n", "\n", ".. math::\n", "\n", " w_{i > k} &=\n", " \\sum_{j = 1}^{i - 1} \\epsilon_i \\epsilon_j 10^{i - j} (b_j - 2 x_j) +\n", " (b_k - x_i)\\\\\n", " &= (b_k - x_i) +\n", " \\epsilon_i \\epsilon_k 10^{i - k} (b_k - 2 x_k) +\n", " \\sum_{j = 1}^{k - 1} \\epsilon_i \\epsilon_j 10^{i - j} (b_j - 2 x_j) +\n", " \\sum_{j = k + 1}^{i - 1} \\epsilon_i \\epsilon_j 10^{i - j} (b_j - 2 x_j)\\\\\n", " &= (b_k - x_i) +\n", " \\epsilon_i \\epsilon_k 10^{i - k} b_k -\n", " 2 \\epsilon_i \\epsilon_k 10^{i - k} \\left[\n", " (b_k - w_k) +\n", " \\sum_{j = 1}^{k - 1} \\epsilon_k \\epsilon_j 10^{k - j} (b_j - 2 x_j)\n", " \\right] +\n", " \\sum_{j = 1}^{k - 1} \\epsilon_i \\epsilon_j 10^{i - j} (b_j - 2 x_j) +\n", " \\sum_{j = k + 1}^{i - 1} \\epsilon_i \\epsilon_j 10^{i - j} (b_j - 2 x_j)\\\\\n", " &= (b_k - x_i) -\n", " \\epsilon_i \\epsilon_k 10^{i - k} (b_k - 2 w_k) -\n", " 2 \\sum_{j = 1}^{k - 1} \\epsilon_i \\epsilon_j 10^{i - j} (b_j - 2 x_j) +\n", " \\sum_{j = 1}^{k - 1} \\epsilon_i \\epsilon_j 10^{i - j} (b_j - 2 x_j) +\n", " \\sum_{j = k + 1}^{i - 1} \\epsilon_i \\epsilon_j 10^{i - j} (b_j - 2 x_j)\n", " & \\quad & \\text{since}\\ \\epsilon_k^2 = 1\\\\\n", " &= \\left[\n", " -\\sum_{j = 1}^{k - 1} \\epsilon_i \\epsilon_j 10^{i - j} (b_j - 2 x_j)\n", " \\right] -\n", " \\epsilon_i \\epsilon_k 10^{i - k} (b_k - 2 w_k) +\n", " \\left[\n", " \\sum_{j = k + 1}^{i - 1} \\epsilon_i \\epsilon_j 10^{i - j} (b_j - 2 x_j)\n", " \\right] + (b_k - x_i)\\\\\n", " &= \\epsilon'_i \\epsilon'_k 10^{i - k} (b_k - 2 w_k) +\n", " \\sum_{j = 1, j \\neq k}^{i - 1}\n", " \\epsilon'_i \\epsilon'_j 10^{i - j} (b_j - 2 x_j) +\n", " (b_k - x_i)\n", "\n", "where :math:`\\epsilon'_{i < k} = -\\epsilon_{i < k}`,\n", ":math:`\\epsilon'_k = -\\epsilon_k`, and\n", ":math:`\\epsilon'_{i > k} = \\epsilon_{i > k}`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-4.7:\n", "\n", "Exercise 4.7\n", "============\n", "\n", "Let :math:`\\epsilon_i^t` denote the relationship between the\n", ":math:`\\epsilon_i`'s before and after each pivot. Evidently,\n", ":math:`\\epsilon_i^{t = 0} = 1` for all :math:`1 \\leq i \\leq n`.\n", "\n", "As shown in :ref:`Exercise 4.6 `, pivoting between\n", ":math:`x_k` and :math:`w_k` results in a dictionary that is of the same form as\n", "before. The only significant differences are the sign changes of\n", ":math:`\\epsilon_i`'s:\n", "\n", ".. math::\n", "\n", " \\epsilon_i^{t + 1} =\n", " \\begin{cases}\n", " -\\epsilon_i^t & \\text{if}\\ i \\leq k\\\\\n", " \\epsilon_i^t & \\text{otherwise.}\n", " \\end{cases}\n", "\n", "Observe that applying the simplex method's largest-coefficient rule in this case\n", "is equivalent to picking the first positive :math:`\\epsilon_k^t` where :math:`k`\n", "is the smallest subscript over the ordered sequence\n", ":math:`\\left[ \\epsilon_1^t, \\epsilon_2^t, \\ldots, \\epsilon_n^t \\right]`.\n", "\n", "Let :math:`T(n)` denote the number of iterations (i.e. pivots) needed before\n", "selecting the variable associated with :math:`\\epsilon_{n + 1}` as the entering\n", "variable for the first time.\n", "\n", "From the initial conditions, obviously :math:`T(0) = 1`. Now that\n", ":math:`\\epsilon_1^{t = 1}` is negative, :math:`\\epsilon_2^{t = 1}` is chosen\n", "as the next entering variable. Pivoting will make :math:`\\epsilon_1^{t = 2}`\n", "eligible as an entering variable again, which means the same sequence of pivots\n", ":math:`T(0)` needs to occur before :math:`\\epsilon_3` can even be considered as\n", "the next entering variable. Thus, :math:`T(1) = 1 + T(0) = 2`. This process\n", "generalizes to the following geometric series\n", "\n", ".. math::\n", "\n", " T(n) = 1 + \\sum_{i = 0}^{n - 1} T(i) = 1 + 2 + 4 + 8 + \\cdots\n", " = a \\frac{1 - r^n}{1 - r}\n", "\n", "where :math:`a = 1` and :math:`r = 2`. Therefore, the Klee-Minty problem\n", "requires :math:`2^n - 1` iterations." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 4.8\n", "============\n", "\n", "Rewriting the Klee-Minty problem with :math:`b_i = \\beta^{i - 1}` where\n", ":math:`\\beta > 1` yields\n", "\n", ".. math::\n", "\n", " \\sum_{j = 1}^{i - 1} 10^{i - j} b_j + b_i =\n", " \\sum_{j = 1}^{i - 1} 10^{i - j} \\beta^{j - 1} + \\beta^{i - 1}\n", "\n", "and\n", "\n", ".. math::\n", "\n", " \\begin{array}{*{5}{@{}c@{}}}\n", " 0 & \\leq & x_1 & \\leq & 1\\\\\n", " 0 & \\leq & x_2 & \\leq & 10 + \\beta\\\\\n", " 0 & \\leq & x_3 & \\leq & 10^2 + 10 \\beta + \\beta^2\\\\\n", " 0 & \\leq & x_4 & \\leq & 10^3 + 10^2 \\beta + 10 \\beta^2 + \\beta^3\\\\\n", " & & \\vdots & &\\\\\n", " 0 & \\leq & x_n & \\leq &\n", " \\sum_{j = 1}^{n - 1} 10^{n - j} \\beta^{j - 1} + \\beta^{n - 1}.\n", " \\end{array}\n", "\n", "In order to force the simplex method to proceed as in\n", ":ref:`vanderbei2014linear-ex-4.7`, :math:`\\beta` needs to be chosen such that\n", "the leaving variable's subscript matches the entering variable's subscript.\n", "\n", "Suppose the entering variable's index is :math:`e \\in \\mathcal{N}` and let\n", ":math:`l \\in \\mathcal{B}` denote the leaving variable's index. From the\n", "definition of the Klee-Minty problem, :math:`l \\geq e`. Out of the remaining\n", "possible candidates, the minimum ratio test chooses one according to:\n", "\n", ".. math::\n", "\n", " \\frac{\\hat{b}_l}{\\hat{a}_{le}} =\n", " \\min\\left\\{\n", " \\frac{\\hat{b}_i}{\\hat{a}_{ie}}\n", " \\colon\n", " i \\in \\mathcal{B},\n", " \\hat{b}_i \\in\n", " \\left[\n", " \\beta^{i - 1} - \\sum_{j = 1}^{i - 1} 10^{i - j} \\beta^{j - 1},\n", " \\beta^{i - 1} + \\sum_{j = 1}^{i - 1} 10^{i - j} \\beta^{j - 1}\n", " \\right]_{\\geq 0},\n", " \\hat{a}_{ie} =\n", " \\epsilon'_i \\epsilon'_e \\cdot 2^{1 - \\delta_{i - e}} \\cdot 10^{i - e} > 0\n", " \\right\\}.\n", "\n", "Observe that for :math:`l = k > e` to be even feasible where :math:`k`\n", "represents another leaving variable, the intervals represented by\n", ":math:`\\frac{\\hat{b}_e}{\\hat{a}_{ee}}` and\n", ":math:`\\frac{\\hat{b}_k}{\\hat{a}_{ke}}` need to intersect. Since each\n", "constraint's upper bound (i.e. the right hand side of each inequality) grows\n", "exponentially in terms of :math:`\\beta` and\n", ":ref:`each pivot only induces sign changes `, if the\n", "pair of intervals indexed by :math:`e = 1` and :math:`l = n \\neq e` never\n", "overlaps, no pair of intervals in between them will intersect. Therefore, the\n", "infimum (a.k.a. greatest lower bound) satisfies\n", "\n", ".. math::\n", "\n", " \\frac{\\hat{b}_e}{\\hat{a}_{ee}} &< \\frac{\\hat{b}_l}{\\hat{a}_{le}}\\\\\n", " 1 &< \\frac{\n", " \\beta^{n - 1} - \\sum_{j = 1}^{n - 1} 10^{n - j} \\beta^{j - 1}\n", " }{\n", " 2^{1 - \\delta_{n - 1}} \\cdot 10^{n - 1}\n", " }\\\\\n", " 2 \\cdot 10^{n - 1} &<\n", " \\beta^{n - 1} - \\sum_{j = 1}^{n - 1} 10^{n - j} \\beta^{j - 1}." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 4.9\n", "============\n", "\n", "Recall that Stirling's approximation is\n", "\n", ".. math::\n", "\n", " n! \\approx \\left( \\frac{n}{e} \\right)^n \\sqrt{2 \\pi n}.\n", "\n", "A crude estimate for the desired binomial coefficient is then\n", "\n", ".. math::\n", "\n", " {2n \\choose n} = \\frac{(2n)!}{n! (2n - n)!} \\approx\n", " \\frac{2^{2n} (n / e)^{2n} \\cdot 2 \\sqrt{\\pi n}}{(n / e)^{2n} \\cdot 2 \\pi n} =\n", " \\frac{2^{2n}}{\\sqrt{\\pi n}}.\n", "\n", "From inspection,\n", "\n", ".. math::\n", "\n", " \\frac{2^{2n}}{2n} \\leq \\frac{2^{2n}}{2 \\sqrt{n}} \\leq\n", " {2n \\choose n} \\leq 2^{2n}\n", "\n", "holds for any positive integer :math:`n`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 4.10\n", "=============\n", "\n", "Recall that a feasible solution satisfies all of the constraints. If that is\n", "no longer a requirement, :ref:`Exercise 2.15 `\n", "has illustrated the desired dictionary can be arrived at in exactly\n", ":math:`k` pivots via the following process.\n", "\n", "#. Pivot all the non-zero elements that have the matching indices first\n", " i.e. :math:`x_i \\leftrightarrow w_i`.\n", "#. The remaining pivots are degenerate and require adopting the convention\n", " of treating :math:`\\frac{0}{0} = 0`." ] } ], "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 }