{ "cells": [ { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "**********\n", "Degeneracy\n", "**********\n", "\n", "The `Simplex Pivot Tool`_ is useful for the first exercise.\n", "\n", ".. _Simplex Pivot Tool: http://www.princeton.edu/~rvdb/JAVA/pivot/simple.html\n", "\n", "Fundamental Theorem of Linear Programming\n", "=========================================\n", "\n", "For an arbitrary linear program in standard form, the following statements are\n", "true:\n", "\n", "#. If there is no optimal solution, then the problem is either infeasible or\n", " unbounded.\n", "#. If a feasible solution exists, then a basic feasible solution exists.\n", "#. If an optimal solution exists, then a basic optimal solution exists.\n", "\n", "Proof of Bland's Rule\n", "=====================\n", "\n", "Bland's rule is essentially a Smallest-Subscript Rule i.e. if more than one\n", "entering variable or leaving variable can be chosen, always choose the variable\n", "with the smallest subscript. Notice that this is very similar to the\n", "Largest-Coefficient Largest-Subscript Rule. The only difference besides the\n", "subscript selection is that the entering variable no longer needs to have the\n", "largest positive coefficient.\n", "\n", "The proof in this chapter and :cite:`burke407s2` lacked some essential\n", "observations that are covered in :cite:`halcsci5654`. The following\n", "derivations provide the necessary details to understand the proof in\n", ":cite:`burke407s3`.\n", "\n", "The objective value never decreases during the simplex method.\n", "--------------------------------------------------------------\n", "\n", "A dictionary is defined as\n", "\n", ".. math::\n", "\n", " \\zeta &= \\nu + \\sum_{j \\in \\mathcal{N}} c_j x_j\\\\\n", " x_i &= b_i - \\sum_{j \\in \\mathcal{N}} a_{ij} x_j\n", " &\\quad& i \\in \\mathcal{B}\n", "\n", "where :math:`\\mathcal{B}` and :math:`\\mathcal{N}` are the basic and nonbasic\n", "integer sets satisfying\n", "\n", "(#) :math:`\\mathcal{B}` contains :math:`m` elements,\n", "(#) :math:`\\mathcal{B} \\cap \\mathcal{N} = \\emptyset`,\n", "(#) and :math:`\\mathcal{B} \\cup \\mathcal{N} = \\{1, \\ldots, n + m\\}`.\n", "\n", "A dictionary is said to be feasible if\n", ":math:`0 \\leq b_i \\forall i \\in \\mathcal{N}`. If a dictionary is feasible, then\n", "a basic feasible solution (BFS) exists for the LP such as\n", ":math:`x_i = b_i` and :math:`x_j = 0`.\n", "\n", "Assume the simplex method is operating with a deterministic pivot rule such as\n", "the\n", "\n", "Largest-Coefficient Largest-Subscript Rule\n", " *Choice of Entering Variable*: Choose :math:`x_{e}` so that :math:`e` is\n", " largest among the variables :math:`x_{j \\in \\mathcal{N}}` such that\n", " :math:`\\hat{c}_j = \\max \\{ \\hat{c}_k \\colon k \\in \\mathcal{N} \\}`.\n", "\n", " *Choice of Leaving Variable*: Choose :math:`x_{l}` so that :math:`l` is\n", " largest among the variables :math:`x_{i \\in \\mathcal{B}}` such that\n", " :math:`\\frac{\\hat{b}_i}{\\hat{a}_{ie}} = \\min \\left\\{\n", " \\frac{\\hat{b}_k}{\\hat{a}_{ke}} \\colon k \\in \\mathcal{B}, \\hat{a}_{ke} > 0\n", " \\right\\}`.\n", "\n", "The pivot step will construct a dictionary for the new basis as follows:\n", "\n", "#. Solve for :math:`x_e` in the equation for :math:`x_l`\n", "\n", " .. math::\n", "\n", " x_e = \\frac{b_l}{a_{le}} -\n", " \\sum_{j \\in \\mathcal{N}'} \\frac{a_{lj}}{a_{le}} x_j\n", "\n", " where :math:`\\mathcal{N}' = N \\cup \\{ l \\} \\setminus \\{ e \\}` and\n", " :math:`a_{ll} = 1`.\n", "\n", "#. Substitute :math:`x_e` in the rest of the dictionary:\n", "\n", " .. math::\n", " :label: P2\n", "\n", " \\zeta &= \\nu + c_e x_e + \\sum_{j \\in \\mathcal{N}'} c_j x_j\\\\\n", " &= \\nu + c_e \\frac{b_l}{a_{le}} + \\sum_{j \\in \\mathcal{N}'}\n", " \\left( c_j - c_e \\frac{a_{lj}}{a_{le}} \\right) x_j\\\\\n", " \\\\\n", " x_i &= b_i - a_{ie} x_e - \\sum_{j \\in \\mathcal{N}'} a_{ij} x_j\n", " & \\quad & i \\in \\mathcal{B}\\\\\n", " &= b_i - a_{ie} \\frac{b_l}{a_{le}} + \\sum_{j \\in \\mathcal{N}'}\n", " \\left( a_{ie} \\frac{a_{lj}}{a_{le}} - a_{ij} \\right) x_j\n", "\n", "Since the pivots are reversible equality-preserving transformations, each\n", "dictionary constructed by the algorithm is still feasible due to the minimum\n", "ratio test. The test is not applicable when the set of leaving variables is\n", "empty, but the LP is unbounded in that case.\n", "\n", "Observe that only the basic variables, :math:`\\zeta`, :math:`x_e`, and\n", ":math:`x_l` changed. Since :math:`c_e > 0`, :math:`a_{le} > 0`, and\n", ":math:`b_l \\geq 0`, the new objective value cannot decrease; it can stay\n", "constant if :math:`b_l = 0`. Once the set of entering variables becomes\n", "empty, the current basis is a local optimum because each variable in a\n", "feasible solution needs to be nonnegative. Since LPs are convex, a local\n", "optimum is the global optimum.\n", "\n", "If the simplex method fails to terminate, then it must cycle.\n", "-------------------------------------------------------------\n", "\n", "Since pivot operations are reversible, the :math:`n + m \\choose m` unique\n", "dictionaries must have identical solution sets. It must also be the case that\n", "each basis is associated with a unique dictionary. To see this, let\n", "\n", ".. math::\n", " :label: D1\n", "\n", " \\zeta &= \\tilde{\\nu} + \\sum_{j \\in \\mathcal{N}} \\tilde{c}_j x_j\\\\\n", " x_i &= \\tilde{b}_i - \\sum_{j \\in \\mathcal{N}} \\tilde{a}_{ij} x_j\n", " &\\quad& i \\in \\mathcal{B}\n", "\n", "and\n", "\n", ".. math::\n", " :label: D2\n", "\n", " \\zeta &= \\hat{\\nu} + \\sum_{j \\in \\mathcal{N}} \\hat{c}_j x_j\\\\\n", " x_i &= \\hat{b}_i - \\sum_{j \\in \\mathcal{N}} \\hat{a}_{ij} x_j\n", " &\\quad& i \\in \\mathcal{B}\n", "\n", "be two dictionaries associated with the same basis :math:`\\mathcal{B}`. Let\n", ":math:`j^{*} \\in \\mathcal{N}` and consider the solution obtained by setting\n", ":math:`x_{j^{*}} = t` and :math:`x_{j \\in \\mathcal{N} \\setminus j^{*}} = 0`.\n", "Since :eq:`D1` and :eq:`D2` have identical solution sets,\n", "\n", ".. math::\n", "\n", " \\tilde{\\nu} + \\tilde{c}_{j^{*}} t\n", " &= \\zeta &= \\hat{\\nu} + \\hat{c}_{j^{*}} t\\\\\n", " \\tilde{b}_i - \\tilde{a}_{ij^{*}} t &= x_i &= \\hat{b}_i - \\hat{a}_{ij^{*}} t\n", " &\\quad& \\forall i \\in \\mathcal{B}.\n", "\n", "Notice that as long as the value :math:`t` takes on does not violate the\n", "constraints, the resulting solution is feasible. Setting :math:`t = 0` reveals\n", ":math:`\\tilde{\\nu} = \\hat{\\nu}` and\n", ":math:`\\tilde{b}_i = \\hat{b}_i \\forall i \\in \\mathcal{B}`. Consequently,\n", "setting :math:`t` to any positive value restricts\n", ":math:`\\tilde{c}_{ij^{*}} = \\hat{c}_{ij^{*}}` and\n", ":math:`\\tilde{a}_{ij^{*}} = \\hat{a}_{ij^{*}} \\forall i \\in \\mathcal{B}`.\n", "Repeating this argument for all :math:`j \\in \\mathcal{N}` demonstrates that\n", ":eq:`D1` and :eq:`D2` are identical dictionaries; thus, each basis gives rise to\n", "a unique dictionary.\n", "\n", "Since there are a finite number of unique bases, the simplex method cannot\n", "deterministically pivot indefinitely unless there exists a repeating sequence of\n", "dictionaries i.e. a cycle.\n", "\n", "The simplex algorithms can only cycle in the presence of degeneracy.\n", "--------------------------------------------------------------------\n", "\n", "Let :math:`D_1, D_2, \\ldots, D_N` denote the cycle of dictionaries in question\n", "with the corresponding :math:`\\zeta_1, \\zeta_2, \\ldots, \\zeta_N`. By the\n", "definition of a cycle, :math:`\\zeta_1 = \\zeta_{N + 1}`. Since the pivoting rule\n", "seeks to maximize the objective function in a nondecreasing manner,\n", "\n", ".. math::\n", "\n", " \\zeta_1 \\leq \\zeta_2 \\leq \\cdots \\leq \\zeta_N \\leq \\zeta_{N + 1} = \\zeta_1.\n", "\n", "Therefore, :math:`\\zeta_i = \\zeta_j` for :math:`1 \\leq i < j \\leq N`.\n", "Consequently, :math:`b_l = 0`, :math:`x_l = 0`, and :math:`x_e = 0`. Thus,\n", "each of the pivots taking :math:`D_i` to :math:`D_j` is necessarily degenerate\n", "for :math:`1 \\leq i < j \\leq N`, and each of the dictionaries\n", ":math:`D_1, D_2, \\ldots, D_N` must be degenerate.\n", "\n", "Notice that the previous degeneracy conditions can be defined more explicitly as\n", "\n", "- A dictionary is degenerate if one or more of the basic variables is set to\n", " zero.\n", "- A pivot is degenerate if one of the ratios in the calculation of the leaving\n", " variable is :math:`+\\infty` i.e. if the numerator is positive and the\n", " denominator vanishes." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 3.1\n", "============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 10 x_1 - 57 x_2 - 9 x_3 - 24 x_4\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= \\epsilon_1 - 0.5 x_1 + 5.5 x_2 + 2.5 x_3 - 9 x_4\\\\\n", " w_2 &= \\epsilon_2 - 0.5 x_1 + 1.5 x_2 + 0.5 x_3 - x_4\\\\\n", " w_3 &= 1 + \\epsilon_3 - x_1\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\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", " x_4 = 0, \\quad\n", " w_1 = \\epsilon_1, \\quad\n", " w_2 = \\epsilon_2, \\quad\n", " w_3 = 1 + \\epsilon_3.\n", "\n", "Choose :math:`x_1` and :math:`w_2` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_1 =\n", " \\min\\left\\{ w_i \\geq 0 \\right\\}_{i = 1}^3 =\n", " \\min\\left\\{ 2 \\epsilon_1, 2 \\epsilon_2, 1 + \\epsilon_3 \\right\\}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 2 \\epsilon_2, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 0, \\quad\n", " x_4 = 0, \\quad\n", " w_1 = \\epsilon_1 - \\epsilon_2, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 1 + \\epsilon_3 - 2 \\epsilon_2.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 20 \\epsilon_2 - 20 w_2 - 87 x_2 + x_3 - 44 x_4\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 2 \\epsilon_2 - 2 w_2 - 3 x_2 + x_3 - 2 x_4\\\\\n", " w_1 &= \\epsilon_1 - \\epsilon_2 + w_2 - 4 x_2 + 2 x_3 - 8 x_4\\\\\n", " w_3 &= 1 - 2 \\epsilon_2 + \\epsilon_3 + 2 w_2 + 3 x_2 - x_3 + 2 x_4\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\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\\{\n", " -2 \\epsilon_2,\n", " \\frac{\\epsilon_2 - \\epsilon_1}{2},\n", " 1 - 2 \\epsilon_2 + \\epsilon_3\n", " \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ \\frac{2}{3}, 2 \\right\\}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 1 + \\epsilon_3, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 1 - 2 \\epsilon_2 + \\epsilon_3, \\quad\n", " x_4 = 0\n", " w_1 = 2 + \\epsilon_1 - 5 \\epsilon_2 + 2 \\epsilon_3, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 0.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 1 + 18 \\epsilon_2 + \\epsilon_3 - 18 w_2 - 84 x_2 - w_3 - 42 x_4\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 1 + \\epsilon_3 - w_3\\\\\n", " x_3 &= 1 - \\epsilon_2 + \\epsilon_3 + 2 w_2 + 3 x_2 - w_3 + 2 x_4\\\\\n", " w_1 &= 2 + \\epsilon_1 - 5 \\epsilon_2 + 2 \\epsilon_3 +\n", " 5 w_2 + 2 x_2 - 2 w_3 - 4 x_4\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "The last dictionary is optimal, so dropping the perturbations results in\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 1 - 18 w_2 - 84 x_2 - w_3 - 42 x_4\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 1 - w_3\\\\\n", " x_3 &= 1 + 2 w_2 + 3 x_2 - w_3 + 2 x_4\\\\\n", " w_1 &= 2 + 5 w_2 + 2 x_2 - 2 w_3 - 4 x_4\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 3.2\n", "============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 10 x_1 - 57 x_2 - 9 x_3 - 24 x_4\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -0.5 x_1 + 5.5 x_2 + 2.5 x_3 - 9 x_4\\\\\n", " w_2 &= -0.5 x_1 + 1.5 x_2 + 0.5 x_3 - x_4\\\\\n", " w_3 &= 1 - x_1\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\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", " x_4 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 1.\n", "\n", "Choose :math:`x_1` and :math:`w_1` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_1 = \\min\\left\\{ w_1, w_2, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 0, 0, 1 \\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 = 0, \\quad\n", " x_4 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 1.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -20 w_1 + 53 x_2 + 43 x_3 - 204 x_4\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= -2 w_1 + 11 x_2 + 5 x_3 - 18 x_4\\\\\n", " w_2 &= w_1 - 4 x_2 - 2 x_3 + 8 x_4\\\\\n", " w_3 &= 1 + 2 w_1 - 11 x_2 - 5 x_3 + 18 x_4\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Choose :math:`x_2` and :math:`w_2` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_2 = \\min\\left\\{ x_1, w_2, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ -11, 0, \\frac{1}{11} \\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 = 0, \\quad\n", " x_4 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 1.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{4} \\left( -27 w_1 - 53 w_2 + 58 x_3 - 392 x_4 \\right)\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= \\frac{1}{4} \\left( 3 w_1 - 11 w_2 - 2 x_3 + 16 x_4 \\right)\\\\\n", " x_2 &= \\frac{1}{4} \\left( w_1 - w_2 - 2 x_3 + 8 x_4 \\right)\\\\\n", " w_3 &= \\frac{1}{4} \\left( 4 - 3 w_1 + 11 w_2 + 2 x_3 - 16 x_4 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Choose :math:`x_3` and :math:`x_1` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_3 = \\min\\left\\{ x_1, x_2, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 0, 0, -2 \\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 = 0, \\quad\n", " x_4 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 1.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 15 w_1 - 93 w_2 - 29 x_1 + 18 x_4\\\\\n", " \\text{subject to} \\quad\n", " x_2 &= \\frac{1}{2} \\left( -w_1 + 5 w_2 + 2 x_1 - 4 x_4 \\right)\\\\\n", " x_3 &= \\frac{1}{2} \\left( 3 w_1 - 11 w_2 - 4 x_1 + 16 x_4 \\right)\\\\\n", " w_3 &= 1 - x_1\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Choose :math:`x_4` and :math:`x_2` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_4 = \\min\\left\\{ x_2, x_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 0, 0 \\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 = 0, \\quad\n", " x_4 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 1.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{2} \\left( 21 w_1 - 141 w_2 - 40 x_1 - 18 x_2 \\right)\\\\\n", " \\text{subject to} \\quad\n", " x_3 &= \\frac{1}{2} \\left( -w_1 + 9 w_2 + 4 x_1 - 8 x_2 \\right)\\\\\n", " x_4 &= \\frac{1}{4} \\left( -w_1 + 5 w_2 + 2 x_1 - 2 x_2 \\right)\\\\\n", " w_3 &= 1 - x_1\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Choose :math:`w_1` and :math:`x_3` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " w_1 = \\min\\left\\{ x_3, x_4 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 0, 0 \\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 = 0, \\quad\n", " x_4 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 1.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -21 w_3 + 24 w_2 + 22 x_1 - 93 x_2\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -2 x_3 + 9 w_2 + 4 x_1 - 8 x_2\\\\\n", " x_4 &= \\frac{1}{2} \\left( x_3 - 2 w_2 - x_1 + 3 x_2 \\right)\\\\\n", " w_3 &= 1 - x_1\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Choose :math:`x_1` and :math:`x_4` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_1 = \\min\\left\\{ x_4, w_1, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 0, 0, 1 \\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 = 0, \\quad\n", " x_4 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 1.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= x_3 - 20 w_2 - 44 x_4 - 27 x_2\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= 2 x_3 + w_2 - 8 x_4 + 4 x_2\\\\\n", " x_1 &= x_3 - 2 w_2 - 2 x_4 + 3 x_2\\\\\n", " w_3 &= 1 - x_3 + 2 w_2 + 2 x_4 - 3 x_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\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\\{ x_1, w_1, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 0, 0, 1 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 1, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 1, \\quad\n", " x_4 = 0, \\quad\n", " w_1 = 2, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 0.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 1 - w_3 - 18 w_2 - 42 x_4 - 30 x_2\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= 2 - 2 w_3 + 5 w_2 - 4 x_4 - 2 x_2\\\\\n", " x_1 &= 1 - w_3\\\\\n", " x_3 &= 1 - w_3 + 2 w_2 + 2 x_4 - 3 x_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 3.3\n", "============\n", "\n", "The previous exercises already gave enough practice." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 3.4\n", "============\n", "\n", "Rewriting the standard form LP with slack variables yields\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\sum_{j \\in \\mathcal{N}} c_j x_j\\\\\n", " \\text{subject to} \\quad\n", " x_i &= -\\sum_{j \\in \\mathcal{N}} a_{ij} x_j\n", " \\quad i \\in \\mathcal{B}.\n", " \\end{aligned}\n", "\n", "If all :math:`c_j \\leq 0` (i.e. the set of entering variables is empty), the\n", "BFS is optimal. Suppose there exists some :math:`x_{e \\in \\mathcal{N}}` such\n", "that :math:`c_e > 0`.\n", "\n", "If all :math:`a_{ie} \\leq 0` (i.e. the set of leaving variables is empty),\n", ":math:`x_e` can be chosen to be arbitrarily large without violating the\n", "constraints, which makes the problem feasible but unbounded. Further suppose\n", "there exists some :math:`x_{l \\in \\mathcal{B}}` such that :math:`a_{le} > 0`.\n", "\n", "Pivoting according to Bland's rule would set\n", "\n", ".. math::\n", "\n", " x_e &= \\frac{b_l}{a_{le}} -\n", " \\sum_{j \\in \\mathcal{N}'} \\frac{a_{lj}}{a_{le}} x_j =\n", " -\\sum_{j \\in \\mathcal{N}'} a_{ej}' x_j\n", " &\\qquad& a_{ej}' = \\frac{a_{lj}}{a_{le}}\n", " \\\\\n", " \\zeta &= c_e x_e + \\sum_{j \\in \\mathcal{N} \\setminus e} c_j x_j =\n", " c_e \\frac{b_l}{a_{le}} + \\sum_{j \\in \\mathcal{N}'}\n", " \\left( c_j - c_e \\frac{a_{lj}}{a_{le}} \\right) x_j =\n", " \\sum_{j \\in \\mathcal{N}'} c_j' x_j\n", " &\\qquad& c_j' = c_j - c_e \\frac{a_{lj}}{a_{le}}\n", " \\\\\n", " x_i &= b_i - a_{ie} x_e - \\sum_{j \\in \\mathcal{N} \\setminus e} a_{ij} x_j =\n", " b_i - a_{ie} \\frac{b_l}{a_{le}} + \\sum_{j \\in \\mathcal{N}'}\n", " \\left( a_{ie} \\frac{a_{lj}}{a_{le}} - a_{ij} \\right) x_j =\n", " -\\sum_{j \\in \\mathcal{N}'} a_{ij}' x_j\n", " &\\qquad& a_{ij}' = a_{ij} - a_{ie} \\frac{a_{lj}}{a_{le}}\n", "\n", "where :math:`\\mathcal{N}' = N \\cup \\{ l \\} \\setminus \\{ e \\}` and\n", ":math:`a_{ll} = 1`. From inspection, the initial BFS is optimal when\n", "subsequent pivots and dictionaries are degenerate.\n", "\n", "Suppose the pivots and dictionaries are nondegenerate. There must exist a\n", "pivot that serves as the transition from degenerate to nondegenerate. Let\n", ":math:`x_e` and :math:`x_l` respectively denote the entering and leaving\n", "variable for that pivot. Recall that a nondegenerate pivot means\n", ":math:`\\zeta_t < \\zeta_{t + 1}` and a nondegenerate dictionary requires\n", ":math:`x_i > 0` for all :math:`i \\in \\mathcal{B}`. This means\n", ":math:`c_e x_e > 0` and :math:`-a_{ie} x_e > 0`. As a consequence of\n", ":math:`c_e > 0`, :math:`x_e > 0` and :math:`a_{ie} < 0`. Since all the nonbasic\n", "variables had a value of zero on iteration :math:`t` and the simplex algorithm\n", "will assign :math:`x_l = 0` on iteration :math:`t + 1`, :math:`x_e = 0`.\n", "Thus, the subsequent pivots and dictionaries are necessarily degenerate." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 3.5\n", "============\n", "\n", "Graphing the feasible region shows that the LP is unbounded." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "from sympy import symbols\n", "from sympy import plot_implicit, And\n", "\n", "x1, x2 = symbols('x_1 x_2')\n", "\n", "c1 = -2 * x1 <= -5\n", "c2 = And(c1, x1 >= 0)\n", "plot_implicit(c2, (x1, -1, 10), (x2, -10, 10),\n", " title='Feasible Region', xlabel='$x_1$', ylabel='$x_2$');" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 3.6\n", "============\n", "\n", "Remember that the pivot step changes only the basic variables, :math:`\\zeta`,\n", ":math:`x_e`, and :math:`x_l`. Since the non-basic variables still take on the\n", "value of zero and :math:`\\zeta` is irrelevant for this proof, :eq:`P2`\n", "simplifies to\n", "\n", ".. math::\n", "\n", " x_i = b_i − a_{ie} \\frac{b_l}{a_{le}}.\n", "\n", "When :math:`a_{ie} \\leq 0`, :math:`x_i \\geq b_i \\geq 0`. Assuming the\n", "initial dictionary is nondegenerate, :math:`x_i \\geq b_i > 0`.\n", "\n", "When :math:`a_{ie} > 0`, the minimum ratio test requires\n", "\n", ".. math::\n", "\n", " \\frac{b_i}{a_{ie}} \\geq \\frac{b_l}{a_{le}}\n", " \\rightarrow\n", " b_i \\geq a_{ie} \\frac{b_l}{a_{le}}.\n", "\n", "Assuming there is never a tie for the choice of leaving variable,\n", ":math:`b_i > a_{ie} \\frac{b_l}{a_{le}}`. Therefore, a pivot step gives a\n", "nondegenerate dictionary if it starts with a nondegenerate dictionary and\n", "has no tie for leaving variable. Since the simplex method can only cycle\n", "in the presence of degeneracy, this LP cannot have a cycle." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 3.7\n", "============\n", "\n", "(a)\n", "---\n", "\n", ".. math::\n", "\n", " \\left\\{ (x_2, x_6), (x_2, x_4), (x_5, x_4), (x_5, x_1) \\right\\}\n", "\n", "(b)\n", "---\n", "\n", ".. math::\n", "\n", " \\left\\{ (x_5, x_4), (x_5, x_1) \\right\\}\n", "\n", "(c)\n", "---\n", "\n", ".. math::\n", "\n", " (x_2, x_4)" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. rubric:: References\n", "\n", ".. bibliography:: chapter-03.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": 0 }