{ "cells": [ { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "******************\n", "The Simplex Method\n", "******************\n", "\n", "The `Simplex Method Tool`_ and the `Simplex Pivot Tool`_ were useful in\n", "the exercises.\n", "\n", ".. _Simplex Method Tool: http://www.zweigmedia.com/RealWorld/simplex.html\n", ".. _Simplex Pivot Tool: http://www.princeton.edu/~rvdb/JAVA/pivot/simple.html\n", "\n", "Transformation to Standard Form\n", "===============================\n", "\n", ":cite:`burke407s1` provides a step-by-step procedure for transforming any\n", "LP to one in standard form." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-2.1:\n", "\n", "Exercise 2.1\n", "============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 6 x_1 + 8 x_2 + 5 x_3 + 9 x_4\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= 5 - 2 x_1 - x_2 - x_3 - 3 x_4\\\\\n", " w_2 &= 3 - x_1 - 3 x_2 - x_3 - 2 x_4\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, \\ldots, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\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 = 5, \\quad\n", " w_2 = 3.\n", "\n", "Choose :math:`x_4` as the entering variable and :math:`w_2` as the leaving\n", "variable, based on the pivot rules in the section after (2.6) and (2.7), where\n", "\n", ".. math::\n", "\n", " x_4 = \\min\\left\\{ w_1, w_2 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ \\frac{5}{3}, \\frac{3}{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 = \\frac{3}{2}, \\quad\n", " w_1 = \\frac{1}{2}, \\quad\n", " w_2 = 0.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 0.5 \\left( 27 + 3 x_1 - 11 x_2 + x_3 - 9 w_2 \\right)\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= 0.5 \\left( 1 - x_1 + 7 x_2 + x_3 + 3 w_2 \\right)\\\\\n", " x_4 &= 0.5 \\left( 3 - x_1 - 3 x_2 - x_3 - w_2 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, \\ldots, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\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, x_4 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 1, 3 \\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 = 0, \\quad\n", " x_4 = 1, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 15 - 3 w_1 + 5 x_2 + 2 x_3\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 1 + 7 x_2 + x_3 - 2 w_1 + 3 w_2\\\\\n", " x_4 &= 1 - 5 x_2 - x_3 + w_1 - 2 w_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, \\ldots, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "Choose :math:`x_2` and :math:`x_4` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_2 = \\min\\left\\{ x_4 \\right\\}_{\\geq 0} = \\frac{1}{5}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = \\frac{12}{5}, \\quad\n", " x_2 = \\frac{1}{5}, \\quad\n", " x_3 = 0, \\quad\n", " x_4 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 16 + x_3 - x_4 - 2 w_1 - 2 w_2\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 0.2 \\left( 12 - 2 x_3 - 7 x_4 - 3 w_1 + w_2 \\right)\\\\\n", " x_2 &= 0.2 \\left( 1 - x_3 - x_4 + w_1 - 2 w_2 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, \\ldots, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "Choose :math:`x_3` and :math:`x_2` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_3 = \\min\\left\\{ x_1, x_2 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 6, 1 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 2, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 1, \\quad\n", " x_4 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 17 - 5 x_2 - 2 x_4 - w_1 - 4 w_2\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 2 + 2 x_2 - x_4 - w_1 + w_2\\\\\n", " x_3 &= 1 - 5 x_2 - x_4 + w_1 - 2 w_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, \\ldots, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-2.2:\n", "\n", "Exercise 2.2\n", "============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 2 x_1 + x_2\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= 4 - 2 x_1 - x_2\\\\\n", " w_2 &= 3 - 2 x_1 - 3 x_2\\\\\n", " w_3 &= 5 - 4 x_1 - x_2\\\\\n", " w_4 &= 1 - x_1 - 5 x_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, \\ldots, 4\n", " \\end{aligned}\n", "\n", "Initial feasible solution:\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = 4, \\quad\n", " w_2 = 3, \\quad\n", " w_3 = 5, \\quad\n", " w_4 = 1.\n", "\n", "Choose :math:`x_1` and :math:`w_4` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_1 = \\min\\left\\{ w_1, w_2, w_3, w_4 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 2, \\frac{3}{2}, \\frac{5}{4}, 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", " w_1 = 2, \\quad\n", " w_2 = 1, \\quad\n", " w_3 = 1, \\quad\n", " w_4 = 0.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 2 - 9 x_2 - 2 w_4\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 1 - 5 x_2 - w_4\\\\\n", " w_1 &= 2 + 9 x_2 + 2 w_4\\\\\n", " w_2 &= 1 + 7 x_2 + 2 w_4\\\\\n", " w_3 &= 1 + 19 x_2 + 4 w_4\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, \\ldots, 4\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-2.3:\n", "\n", "Exercise 2.3\n", "============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 2 x_1 - 6 x_2\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -2 + x_1 + x_2 + x_3\\\\\n", " w_2 &= 1 - 2 x_1 + x_2 - x_3\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "Initial infeasible solution:\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = -2, \\quad\n", " w_2 = 1.\n", "\n", "The auxiliary problem is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " -x_0 &\\\\\n", " \\text{subject to} \\quad\n", " -x_1 - x_2 - x_3 - x_0 &\\leq -2\\\\\n", " 2 x_1 - x_2 + x_3 - x_0 &\\leq 1\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2, 3\n", " \\end{aligned}\n", "\n", "and its initial infeasible dictionary is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -x_0\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -2 + x_1 + x_2 + x_3 + x_0\\\\\n", " w_2 &= 1 - 2 x_1 + x_2 - x_3 + x_0\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "Initial infeasible solution for auxiliary problem:\n", "\n", ".. math::\n", "\n", " x_0 = 0, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = -2, \\quad\n", " w_2 = 1.\n", "\n", "Pivot the infeasible dictionary with :math:`x_0` as the entering variable and\n", ":math:`w_1`, the most infeasible variable, as the leaving variable. The\n", "resulting dictionary is then\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -2 + x_1 + x_2 + x_3 - w_1\\\\\n", " \\text{subject to} \\quad\n", " x_0 &= 2 - x_1 - x_2 - x_3 + w_1\\\\\n", " w_2 &= 3 - 3 x_1 - 2 x_3 + w_1\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "and its feasible solution is updated to\n", "\n", ".. math::\n", "\n", " x_0 = 2, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 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 = \\min\\left\\{ x_0, w_2 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 2, 1 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_0 = 1, \\quad\n", " x_1 = 1, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0.\n", "\n", "Pivot auxiliary dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{3} \\left( -3 + 3 x_2 + x_3 - 2 w_1 - w_2 \\right)\\\\\n", " \\text{subject to} \\quad\n", " x_0 &= \\frac{1}{3} \\left( 3 - 3 x_2 - x_3 + 2 w_1 + w_2 \\right)\\\\\n", " x_1 &= \\frac{1}{3} \\left( 3 - 2 x_3 + w_1 + w_2 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "Choose :math:`x_2` and :math:`x_0` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_2 = \\min\\left\\{ x_0 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 1 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_0 = 0, \\quad\n", " x_1 = 1, \\quad\n", " x_2 = 1, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0.\n", "\n", "Pivot auxiliary dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -x_0\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= \\frac{1}{3} \\left( 3 - 2 x_3 + w_1 - w_2 \\right)\\\\\n", " x_2 &= \\frac{1}{3} \\left( 3 - 3 x_0 - x_3 + 2 w_1 + w_2 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "The dictionary is optimal for the auxiliary problem, so :math:`x_0` can be\n", "dropped and the original objective function can be reintroduced with the basic\n", "variables substituted appropriately:\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -4 + \\frac{2}{3} x_3 - \\frac{10}{3} w_1 - \\frac{8}{3} w_2\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= \\frac{1}{3} \\left( 3 - 2 x_3 + w_1 - w_2 \\right)\\\\\n", " x_2 &= \\frac{1}{3} \\left( 3 - x_3 + 2 w_1 + w_2 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "Initial feasible solution:\n", "\n", ".. math::\n", "\n", " x_1 = 1, \\quad\n", " x_2 = 1, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0.\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 \\geq 0 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ \\frac{3}{2}, 3 \\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 = \\frac{1}{2}, \\quad\n", " x_3 = \\frac{3}{2}, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -3 - x_1 - 3 w_1 - 3 w_2\\\\\n", " \\text{subject to} \\quad\n", " x_2 &= \\frac{1}{2} \\left( 1 + x_1 + w_1 + w_2 \\right)\\\\\n", " x_3 &= \\frac{1}{2} \\left( 3 - 3 x_1 + w_1 - w_2 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-2.4:\n", "\n", "Exercise 2.4\n", "============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -x_1 - 3 x_2 - x_3\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -5 - 2 x_1 + 5 x_2 - x_3\\\\\n", " w_2 &= 4 - 2 x_1 + x_2 - 2 x_3\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "Initial infeasible solution:\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = -5, \\quad\n", " w_2 = 4.\n", "\n", "The auxiliary problem is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " -x_0 &\\\\\n", " \\text{subject to} \\quad\n", " 2 x_1 - 5 x_2 + x_3 - x_0 &\\leq -5\\\\\n", " 2 x_1 - x_2 + 2 x_3 - x_0 &\\leq 4\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2, 3\n", " \\end{aligned}\n", "\n", "and its initial infeasible dictionary is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -x_0\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -5 - 2 x_1 + 5 x_2 + x_3 + x_0\\\\\n", " w_2 &= 4 - 2 x_1 + x_2 + 2 x_3 + x_0\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "Initial infeasible solution for auxiliary problem:\n", "\n", ".. math::\n", "\n", " x_0 = 0, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = -5, \\quad\n", " w_2 = 4.\n", "\n", "Pivot the infeasible dictionary with :math:`x_0` as the entering variable and\n", ":math:`w_1`, the most infeasible variable, as the leaving variable. The\n", "resulting dictionary is then\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -5 - 2 x_1 + 5 x_2 + x_3 - w_1\\\\\n", " \\text{subject to} \\quad\n", " x_0 &= 5 + 2 x_1 - 5 x_2 - x_3 + w_1\\\\\n", " w_2 &= 9 - 4 x_2 + x_3 + w_1\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "and its feasible solution is updated to\n", "\n", ".. math::\n", "\n", " x_0 = 5, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 9.\n", "\n", "Choose :math:`x_2` and :math:`x_0` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_2 = \\min\\left\\{ x_0, w_2 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 1, \\frac{9}{4} \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_0 = 0, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 1, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 5.\n", "\n", "Pivot auxiliary dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -x_0\\\\\n", " \\text{subject to} \\quad\n", " x_2 &= \\frac{1}{5} \\left( 5 + 2 x_1 - x_0 - x_3 + w_1 \\right)\\\\\n", " w_2 &= \\frac{1}{5} \\left( 25 - 8 x_1 + 4 x_0 + 9 x_3 + w_1 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "The dictionary is optimal for the auxiliary problem, so :math:`x_0` can be\n", "dropped and the original objective function can be reintroduced with the basic\n", "variables substituted appropriately:\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{5} \\left( -15 - 8 x_1 - 2 x_3 - 3 w_1 \\right)\\\\\n", " \\text{subject to} \\quad\n", " x_2 &= \\frac{1}{5} \\left( 5 + 2 x_1 - x_3 + w_1 \\right)\\\\\n", " w_2 &= \\frac{1}{5} \\left( 25 - 8 x_1 + 9 x_3 + w_1 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "Initial feasible solution:\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 1, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 5,\n", "\n", "which happens to be the optimal solution since all the coefficients in\n", ":math:`\\zeta` are negative." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 2.5\n", "============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= x_1 + 3 x_2\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -3 + x_1 + x_2\\\\\n", " w_2 &= -1 + x_1 - x_2\\\\\n", " w_3 &= 4 - x_1 - 2 x_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Initial infeasible solution:\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = -3, \\quad\n", " w_2 = -1, \\quad\n", " w_3 = 4.\n", "\n", "The auxiliary problem is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " -x_0 &\\\\\n", " \\text{subject to} \\quad\n", " -x_1 - x_2 - x_0 &\\leq -3\\\\\n", " -x_1 + x_2 - x_0 &\\leq -1\\\\\n", " x_1 + 2 x_2 - x_0 &\\leq 4\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\n", " \\end{aligned}\n", "\n", "and its initial infeasible dictionary is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -x_0\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -3 + x_0 + x_1 + x_2\\\\\n", " w_2 &= -1 + x_0 + x_1 - x_2\\\\\n", " w_3 &= 4 + x_0 - x_1 - 2 x_2\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Initial infeasible solution for auxiliary problem:\n", "\n", ".. math::\n", "\n", " x_0 = 0, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = -3, \\quad\n", " w_2 = -1, \\quad\n", " w_3 = 4.\n", "\n", "Pivot the infeasible dictionary with :math:`x_0` as the entering variable and\n", ":math:`w_1`, the most infeasible variable, as the leaving variable. The\n", "resulting dictionary is then\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -3 + x_1 + x_2 - w_1\\\\\n", " \\text{subject to} \\quad\n", " x_0 &= 3 - x_1 - x_2 + w_1\\\\\n", " w_2 &= 2 - 2 x_2 + w_1\\\\\n", " w_3 &= 7 - 2 x_1 - 3 x_2 + w_1\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "and its feasible solution is updated to\n", "\n", ".. math::\n", "\n", " x_0 = 3, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 2, \\quad\n", " w_3 = 7.\n", "\n", "Choose :math:`x_1` and :math:`x_0` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_1 = \\min\\left\\{ x_0, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 3, \\frac{7}{2} \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_0 = 0, \\quad\n", " x_1 = 3, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 2, \\quad\n", " w_3 = 1.\n", "\n", "Pivot auxiliary dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -x_0\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 3 - x_0 - x_2 + w_1\\\\\n", " w_2 &= 2 - 2 x_2 + w_1\\\\\n", " w_3 &= 1 + 2 x_0 - x_2 - w_1\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "The dictionary is optimal for the auxiliary problem, so :math:`x_0` can\n", "be dropped and the original objective function can be reintroduced with\n", "the basic variables substituted appropriately:\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 3 + 2 x_2 + w_1\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 3 - x_2 + w_1\\\\\n", " w_2 &= 2 - 2 x_2 + w_1\\\\\n", " w_3 &= 1 - x_2 - w_1\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\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 = 3, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 2, \\quad\n", " w_3 = 1.\n", "\n", "Unbounded Solution\n", "------------------\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\\{ 3, 1, 1 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 2, \\quad\n", " x_2 = 1, \\quad\n", " w_1 = 0, \\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 &= 5 + 2 w_1 - w_2\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= \\frac{1}{2} \\left( 4 + w_1 + w_2 \\right)\\\\\n", " x_2 &= \\frac{1}{2} \\left( 2 + w_1 - w_2 \\right)\\\\\n", " w_3 &= \\frac{1}{2} \\left( -3 w_1 + w_2 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Since the entering variable\n", "\n", ".. math::\n", "\n", " w_1 = \\min\\left\\{ x_1, x_2, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ -4, -2, 0 \\right\\},\n", "\n", "the problem is unbounded.\n", "\n", "Bounded Solution\n", "----------------\n", "\n", "Choose :math:`x_2` and :math:`w_3` 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\\{ 3, 1, 1 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 2, \\quad\n", " x_2 = 1, \\quad\n", " w_1 = 0, \\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 &= 5 - w_1 - 2 w_3\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 2 + 2 w_1 + w_3\\\\\n", " x_2 &= 1 - w_1 - w_3\\\\\n", " w_2 &= 3 w_1 + 2 w_3\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-2.6:\n", "\n", "Exercise 2.6\n", "============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= x_1 + 3 x_2\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -3 + x_1 + x_2\\\\\n", " w_2 &= -1 + x_1 - x_2\\\\\n", " w_3 &= 2 - x_1 - 2 x_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Initial infeasible solution:\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = -3, \\quad\n", " w_2 = -1, \\quad\n", " w_3 = 2.\n", "\n", "The auxiliary problem is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " -x_0 &\\\\\n", " \\text{subject to} \\quad\n", " -x_1 - x_2 - x_0 &\\leq -3\\\\\n", " -x_1 + x_2 - x_0 &\\leq -1\\\\\n", " x_1 + 2 x_2 - x_0 &\\leq 2\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\n", " \\end{aligned}\n", "\n", "and its initial infeasible dictionary is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -x_0\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -3 + x_0 + x_1 + x_2\\\\\n", " w_2 &= -1 + x_0 + x_1 - x_2\\\\\n", " w_3 &= 2 + x_0 - x_1 - 2 x_2\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Initial infeasible solution for auxiliary problem:\n", "\n", ".. math::\n", "\n", " x_0 = 0, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = -3, \\quad\n", " w_2 = -1, \\quad\n", " w_3 = 2.\n", "\n", "Pivot the infeasible dictionary with :math:`x_0` as the entering variable and\n", ":math:`w_1`, the most infeasible variable, as the leaving variable. The\n", "resulting dictionary is then\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -3 + x_1 + x_2 - w_1\\\\\n", " \\text{subject to} \\quad\n", " x_0 &= 3 - x_1 - x_2 + w_1\\\\\n", " w_2 &= 2 - 2 x_2 + w_1\\\\\n", " w_3 &= 5 - 2 x_1 - 3 x_2 + w_1\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "and its feasible solution is updated to\n", "\n", ".. math::\n", " x_0 = 3, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 2, \\quad\n", " w_3 = 5.\n", "\n", "Notice that either :math:`x_1` or :math:`x_2` can be selected. As shown\n", "below, both routes will lead to a negative optimal solution. Thus, the\n", "original problem is infeasible.\n", "\n", "Route 1\n", "-------\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_1 = \\min\\left\\{ x_0, w_2, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 3, 1, \\frac{5}{3} \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_0 = 2, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 1, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 2.\n", "\n", "Pivot auxiliary dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{2} \\left( -4 + 2 x_1 - w_1 - w_2 \\right)\\\\\n", " \\text{subject to} \\quad\n", " x_0 &= \\frac{1}{2} \\left( 4 - 2 x_1 + w_1 + w_2 \\right)\\\\\n", " x_2 &= \\frac{1}{2} \\left( 2 + w_1 + w_2 \\right)\\\\\n", " w_3 &= \\frac{1}{2} \\left( 6 - 4 x_1 + 2 w_2 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Choose :math:`x_1` and :math:`w_3` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_1 = \\min\\left\\{ x_0, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 2, \\frac{3}{2} \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_0 = \\frac{1}{2}, \\quad\n", " x_1 = \\frac{3}{2}, \\quad\n", " x_2 = 1, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 0.\n", "\n", "Pivot auxiliary dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{2} \\left( -1 - w_1 - w_3 \\right)\\\\\n", " \\text{subject to} \\quad\n", " x_0 &= \\frac{1}{2} \\left( 1 + w_1 + w_3 \\right)\\\\\n", " x_1 &= \\frac{1}{2} \\left( 3 + w_2 - w_3 \\right)\\\\\n", " x_2 &= \\frac{1}{2} \\left( 2 + w_1 - w_2 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Route 2\n", "-------\n", "\n", "Choose :math:`x_1` and :math:`w_3` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_1 = \\min\\left\\{ x_0, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 3, \\frac{5}{2} \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_0 = \\frac{1}{2}, \\quad\n", " x_1 = \\frac{5}{2}, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 2, \\quad\n", " w_3 = 0.\n", "\n", "Pivot auxiliary dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{2} \\left( -1 - w_1 - w_3 \\right)\\\\\n", " \\text{subject to} \\quad\n", " x_0 &= \\frac{1}{2} \\left( 1 + w_1 + w_3 \\right)\\\\\n", " x_1 &= \\frac{1}{2} \\left( 5 - 2 x_2 + w_1 - w_3 \\right)\\\\\n", " w_2 &= \\frac{1}{2} \\left( 4 - 4 x_2 + 2 w_1 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 2.7\n", "============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= x_1 + 3 x_2\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -3 + x_1 + x_2\\\\\n", " w_2 &= -1 + x_1 - x_2\\\\\n", " w_3 &= 2 + x_1 - 2 x_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Initial infeasible solution:\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = -3, \\quad\n", " w_2 = -1, \\quad\n", " w_3 = 2.\n", "\n", "The auxiliary problem is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " -x_0 &\\\\\n", " \\text{subject to} \\quad\n", " -x_1 - x_2 - x_0 &\\leq -3\\\\\n", " -x_1 + x_2 - x_0 &\\leq -1\\\\\n", " -x_1 + 2 x_2 - x_0 &\\leq 2\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\n", " \\end{aligned}\n", "\n", "and its initial infeasible dictionary is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -x_0\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -3 + x_0 + x_1 + x_2\\\\\n", " w_2 &= -1 + x_0 + x_1 - x_2\\\\\n", " w_3 &= 2 + x_0 + x_1 - 2 x_2\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Initial infeasible solution for auxiliary problem:\n", "\n", ".. math::\n", "\n", " x_0 = 0, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = -3, \\quad\n", " w_2 = -1, \\quad\n", " w_3 = 2.\n", "\n", "Pivot the infeasible dictionary with :math:`x_0` as the entering variable and\n", ":math:`w_1`, the most infeasible variable, as the leaving variable. The\n", "resulting dictionary is then\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -3 + x_1 + x_2 - w_1\\\\\n", " \\text{subject to} \\quad\n", " x_0 &= 3 - x_1 - x_2 + w_1\\\\\n", " w_2 &= 2 - 2 x_2 + w_1\\\\\n", " w_3 &= 5 - x_2 + w_1\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "and its feasible solution is updated to\n", "\n", ".. math::\n", "\n", " x_0 = 3, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 2, \\quad\n", " w_3 = 5.\n", "\n", "Choose :math:`x_1` and :math:`x_0` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_1 = \\min\\left\\{ x_0 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 3 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_0 = 0, \\quad\n", " x_1 = 3, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 2, \\quad\n", " w_3 = 5.\n", "\n", "Pivot auxiliary dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -x_0\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 3 - x_0 - x_2 + w_1\\\\\n", " w_2 &= 2 - 2 x_2 + w_1\\\\\n", " w_3 &= 5 - x_2 + w_1\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "The dictionary is optimal for the auxiliary problem, so :math:`x_0` can be\n", "dropped and the original objective function can be reintroduced with the\n", "basic variables substituted appropriately:\n", "\n", ".. math::\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 3 + 2 x_2 + w_1\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 3 - x_2 + w_1\\\\\n", " w_2 &= 2 - 2 x_2 + w_1\\\\\n", " w_3 &= 1 - x_2 + w_1\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\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 = 3, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 2, \\quad\n", " w_3 = 1.\n", "\n", "Notice that as long as :math:`w_1 \\geq 2 x_2`, the constraints are satisfied.\n", "As shown below, the original problem is feasible but has an unbounded objective.\n", "\n", "Route 1\n", "-------\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\\{ 3, 1, 1 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 2, \\quad\n", " x_2 = 1, \\quad\n", " w_1 = 0, \\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 &= 5 + 2 w_1 - w_2\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= \\frac{1}{2} \\left( 4 + w_1 + w_2 \\right)\\\\\n", " x_2 &= \\frac{1}{2} \\left( 2 + w_1 - w_2 \\right)\\\\\n", " w_3 &= \\frac{1}{2} \\left( w_1 + w_2 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Since the entering variable\n", "\n", ".. math::\n", "\n", " w_1 = \\min\\left\\{ x_1, x_2, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ -4, -2, 0 \\right\\},\n", "\n", "the problem is unbounded.\n", "\n", "Route 2\n", "-------\n", "\n", "Choose :math:`x_2` and :math:`w_3` 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\\{ 3, 1, 1 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 2, \\quad\n", " x_2 = 1, \\quad\n", " w_1 = 0, \\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 &= 5 + 3 w_1 - 2 w_3\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 2 + w_3\\\\\n", " x_2 &= 1 + w_1 - w_3\\\\\n", " w_2 &= -w_1 + 2 w_3\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "Since the entering variable\n", "\n", ".. math::\n", "\n", " w_1 = \\min\\left\\{ x_2, w_2 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ -1, 0 \\right\\}_{\\geq 0},\n", "\n", "the problem is unbounded." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 2.8\n", "============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 3 x_1 + 2 x_2\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= 1 - x_1 + 2 x_2\\\\\n", " w_2 &= 2 - x_1 + x_2\\\\\n", " w_3 &= 6 - 2 x_1 + x_2\\\\\n", " w_4 &= 5 - x_1\\\\\n", " w_5 &= 16 - 2 x_1 - x_2\\\\\n", " w_6 &= 12 - x_1 - x_2\\\\\n", " w_7 &= 21 - x_1 - 2 x_2\\\\\n", " w_8 &= 10 - x_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, \\ldots, 8\n", " \\end{aligned}\n", "\n", "Initial feasible solution:\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = 1, \\quad\n", " w_2 = 2, \\quad\n", " w_3 = 6, \\quad\n", " w_4 = 5, \\quad\n", " w_5 = 16, \\quad\n", " w_6 = 12, \\quad\n", " w_7 = 21, \\quad\n", " w_8 = 10.\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_i \\geq 0 \\right\\}_{i = 1}^7\n", " = \\min\\left\\{ 1, 2, 3, 5, 8, 12, 21 \\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", " w_1 = 0, \\quad\n", " w_2 = 1, \\quad\n", " w_3 = 4, \\quad\n", " w_4 = 4, \\quad\n", " w_5 = 14, \\quad\n", " w_6 = 11, \\quad\n", " w_7 = 20, \\quad\n", " w_8 = 10.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 3 - 3 w_1 + 8 x_2\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 1 - w_1 + 2 x_2\\\\\n", " w_2 &= 1 + w_1 - x_2\\\\\n", " w_3 &= 4 + 2 w_1 - 3 x_2\\\\\n", " w_4 &= 4 + w_1 - 2 x_2\\\\\n", " w_5 &= 14 + 2 w_1 - 5 x_2\\\\\n", " w_6 &= 11 + w_1 - 3 x_2\\\\\n", " w_7 &= 20 + w_1 - 4 x_2\\\\\n", " w_8 &= 10 - x_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, \\ldots, 8\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, \\left\\{ w_i \\right\\}_{i = 2}^8 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{\n", " -\\frac{1}{2}, 1, \\frac{4}{3}, 2, \\frac{14}{5}, \\frac{11}{3}, 5, 10\n", " \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 3, \\quad\n", " x_2 = 1, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 1, \\quad\n", " w_4 = 2, \\quad\n", " w_5 = 9, \\quad\n", " w_6 = 8, \\quad\n", " w_7 = 16, \\quad\n", " w_8 = 9.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 3 + 5 w_1 - 8 w_2\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 3 + w_1 - 2 w_2\\\\\n", " x_2 &= 1 + w_1 - w_2\\\\\n", " w_3 &= 1 - w_1 + 3 w_2\\\\\n", " w_4 &= 2 - w_1 + 2 w_2\\\\\n", " w_5 &= 9 - 3 w_1 + 5 w_2\\\\\n", " w_6 &= 8 - 2 w_1 + 3 w_2\\\\\n", " w_7 &= 16 - 3 w_1 + 4 w_2\\\\\n", " w_8 &= 9 - w_1 + w_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, \\ldots, 8\n", " \\end{aligned}\n", "\n", "Choose :math:`w_1` and :math:`w_3` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " w_1 = \\min\\left\\{ x_1, x_2, \\left\\{ w_i \\right\\}_{i = 3}^8 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ -3, -1, 1, 2, 3, 4, \\frac{16}{3}, 9 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 4, \\quad\n", " x_2 = 2, \\quad\n", " w_1 = 1, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 0, \\quad\n", " w_4 = 1, \\quad\n", " w_5 = 6, \\quad\n", " w_6 = 6, \\quad\n", " w_7 = 13, \\quad\n", " w_8 = 8.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 3 - 5 w_3 + 7 w_2\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 4 - w_3 + w_2\\\\\n", " x_2 &= 2 - w_3 + 2 w_2\\\\\n", " w_1 &= 1 - w_3 + 3 w_2\\\\\n", " w_4 &= 1 + w_3 - w_2\\\\\n", " w_5 &= 6 + 3 w_3 - 4 w_2\\\\\n", " w_6 &= 6 + 2 w_3 - 3 w_2\\\\\n", " w_7 &= 13 + 3 w_3 - 5 w_2\\\\\n", " w_8 &= 8 + w_3 - 2 w_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, \\ldots, 8\n", " \\end{aligned}\n", "\n", "Choose :math:`w_2` and :math:`w_4` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " w_2 = \\min\\left\\{\n", " x_1, x_2, w_1, \\left\\{ w_i \\right\\}_{i = 4}^8\n", " \\right\\}_{\\geq 0}\n", " = \\min\\left\\{\n", " -4, -1, -\\frac{1}{3}, 1, \\frac{3}{2}, 2, \\frac{13}{5}, 4\n", " \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 5, \\quad\n", " x_2 = 4, \\quad\n", " w_1 = 4, \\quad\n", " w_2 = 1, \\quad\n", " w_3 = 0, \\quad\n", " w_4 = 0, \\quad\n", " w_5 = 2, \\quad\n", " w_6 = 3, \\quad\n", " w_7 = 8, \\quad\n", " w_8 = 6.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 23 + 2 w_3 - 7 w_4\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 5 - w_4\\\\\n", " x_2 &= 4 + w_3 - 2 w_4\\\\\n", " w_1 &= 4 + 2 w_3 - 3 w_4\\\\\n", " w_2 &= 1 + w_3 - w_4\\\\\n", " w_5 &= 2 - w_3 + 4 w_4\\\\\n", " w_6 &= 3 - w_3 + 3 w_4\\\\\n", " w_7 &= 8 - 2 w_3 + 5 w_4\\\\\n", " w_8 &= 6 - w_3 + 2 w_4\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, \\ldots, 8\n", " \\end{aligned}\n", "\n", "Choose :math:`w_3` and :math:`w_5` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " w_3 = \\min\\left\\{ x_2, w_1, w_2, w_5, w_6, w_7, w_8 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ -4, -2, -1, 2, 3, 4, 6 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 5, \\quad\n", " x_2 = 6, \\quad\n", " w_1 = 8, \\quad\n", " w_2 = 3, \\quad\n", " w_3 = 2, \\quad\n", " w_4 = 0, \\quad\n", " w_5 = 0, \\quad\n", " w_6 = 1, \\quad\n", " w_7 = 4, \\quad\n", " w_8 = 4.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 27 - 2 w_5 + w_4\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 5 - w_4\\\\\n", " x_2 &= 6 - w_5 + 2 w_4\\\\\n", " w_1 &= 8 - 2 w_5 + 5 w_4\\\\\n", " w_2 &= 3 - w_5 + 3 w_4\\\\\n", " w_3 &= 2 - w_5 + 4 w_4\\\\\n", " w_6 &= 1 + w_5 - w_4\\\\\n", " w_7 &= 4 + 2 w_5 - 3 w_4\\\\\n", " w_8 &= 4 + w_5 - 2 w_4\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, \\ldots, 8\n", " \\end{aligned}\n", "\n", "Choose :math:`w_4` and :math:`w_6` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " w_4 = \\min\\left\\{ x_1, x_2, w_1, w_2, w_3, w_6, w_7, w_8 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{\n", " 5, -3, -\\frac{8}{5}, -1, -\\frac{1}{2}, 1, \\frac{4}{3}, 2\n", " \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 4, \\quad\n", " x_2 = 8, \\quad\n", " w_1 = 13, \\quad\n", " w_2 = 6, \\quad\n", " w_3 = 6, \\quad\n", " w_4 = 1, \\quad\n", " w_5 = 0, \\quad\n", " w_6 = 0, \\quad\n", " w_7 = 1, \\quad\n", " w_8 = 2.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 28 - w_5 - w_6\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 4 - w_5 + w_6\\\\\n", " x_2 &= 8 + w_5 - 2 w_6\\\\\n", " w_1 &= 13 + 3 w_5 - 5 w_6\\\\\n", " w_2 &= 6 + 2 w_5 - 3 w_6\\\\\n", " w_3 &= 6 + 3 w_5 - 4 w_6\\\\\n", " w_4 &= 1 + w_5 - w_6\\\\\n", " w_7 &= 1 - w_5 + 3 w_6\\\\\n", " w_8 &= 2 - w_5 + 2 w_6\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, \\ldots, 8\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-2.9:\n", "\n", "Exercise 2.9\n", "============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 2 x_1 + 3 x_2 + 4 x_3\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= 5 - 2 x_2 - 3 x_3\\\\\n", " w_2 &= 4 - x_1 - x_2 - 2 x_3\\\\\n", " w_3 &= 7 - x_1 - 2 x_2 - 3 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 = 5, \\quad\n", " w_2 = 4, \\quad\n", " w_3 = 7.\n", "\n", "Choose :math:`x_3` and :math:`w_1` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_3 = \\min\\left\\{ w_1, w_2, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ \\frac{5}{3}, 2, \\frac{7}{3} \\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 = \\frac{5}{3}, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = \\frac{2}{3}, \\quad\n", " w_3 = 2.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{3} \\left( 20 + 6 x_1 + x_2 - 4 w_1 \\right)\\\\\n", " \\text{subject to} \\quad\n", " x_3 &= \\frac{1}{3} \\left( 5 - 2 x_2 - w_1 \\right)\\\\\n", " w_2 &= \\frac{1}{3} \\left( 2 - 3 x_1 + x_2 + 2 w_1 \\right)\\\\\n", " w_3 &= 2 - x_1 + w_1\\\\\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", "Choose :math:`x_1` and :math:`w_2` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_1 = \\min\\left\\{ w_2, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ \\frac{2}{3}, 2 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = \\frac{2}{3}, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = \\frac{5}{3}, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = \\frac{4}{3}.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 8 + x_2 - 2 w_2\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= \\frac{1}{3} \\left( 2 + x_2 + 2 w_1 - 3 w_2 \\right)\\\\\n", " x_3 &= \\frac{1}{3} \\left( 5 - 2 x_2 - w_1 \\right)\\\\\n", " w_3 &= \\frac{1}{3} \\left( 4 - x_2 + w_1 + 3 w_2 \\right)\\\\\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", "Choose :math:`x_2` and :math:`x_3` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_2 = \\min\\left\\{ x_1, x_3, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ -2, \\frac{5}{2}, 4 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = \\frac{3}{2}, \\quad\n", " x_2 = \\frac{5}{2}, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = \\frac{1}{2}.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{2} \\left( 21 - 3 x_3 - w_1 - 4 w_2 \\right)\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= \\frac{1}{2} \\left( 3 - x_3 + w_1 - w_2 \\right)\\\\\n", " x_2 &= \\frac{1}{2} \\left( 5 - 3 x_3 - w_1 \\right)\\\\\n", " w_3 &= \\frac{1}{2} \\left( 1 + x_3 + w_1 + w_2 \\right)\\\\\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 2.10\n", "=============\n", "\n", "Rewriting the LP in standard form yields\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " 6 x_1 + 8 x_2 + 5 x_3 + 9 x_4 &\\\\\n", " \\text{subject to} \\quad\n", " x_1 + x_2 + x_3 + x_4 &\\leq 1\\\\\n", " -x_1 - x_2 - x_3 - x_4 &\\leq -1\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4.\n", " \\end{aligned}\n", "\n", "An equivalent representation with slack variables is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 6 x_1 + 8 x_2 + 5 x_3 + 9 x_4\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= 1 - x_1 - x_2 - x_3 - x_4\\\\\n", " w_2 &= 1 + x_1 + x_2 + x_3 + x_4\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\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 = 1, \\quad\n", " w_2 = 1.\n", "\n", "Choose :math:`x_4` and :math:`w_1` as the entering and leaving variable\n", "respectively since that's the only choice.\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 = 1, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 2.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 9 - 3 x_1 - x_2 - 4 x_3 - 9 w_1\\\\\n", " \\text{subject to} \\quad\n", " x_4 &= 1 - x_1 - x_2 - x_3 - w_1\\\\\n", " w_2 &= 2 - w_1\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3, 4\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 2.11\n", "=============\n", "\n", "Rewriting the LP in standard form yields\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " -\\text{maximize} \\quad\n", " -x_1 - 8 x_2 - 9 x_3 - 2 x_4 - 7 x_5 - 3 x_6 &\\\\\n", " \\text{subject to} \\quad\n", " -x_1 - x_2 - x_3 &\\leq -1\\\\\n", " -x_1 + x_4 + x_4 &\\leq 0\\\\\n", " x_1 - x_4 - x_4 &\\leq 0\\\\\n", " -x_2 - x_4 + x_6 &\\leq 0\\\\\n", " x_2 + x_4 - x_6 &\\leq 0\\\\\n", " x_3 + x_5 + x_6 &\\leq 1\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\n", " \\end{aligned}\n", "\n", "An equivalent representation with slack variables is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " -\\text{maximize} \\quad\n", " \\zeta &= -x_1 - 8 x_2 - 9 x_3 - 2 x_4 - 7 x_5 - 3 x_6\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -1 + x_1 + x_2 + x_3\\\\\n", " w_2 &= x_1 - x_4 - x_5\\\\\n", " w_3 &= -x_1 + x_4 + x_5\\\\\n", " w_4 &= x_2 + x_4 - x_6\\\\\n", " w_5 &= -x_2 - x_4 + x_6\\\\\n", " w_6 &= 1 - x_3 - x_5 - x_6\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\n", " \\end{aligned}\n", "\n", "Initial infeasible 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", " x_5 = 0, \\quad\n", " x_6 = 0, \\quad\n", " w_1 = -1, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 0, \\quad\n", " w_4 = 0, \\quad\n", " w_5 = 0, \\quad\n", " w_6 = 1.\n", "\n", "The auxiliary problem is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " -x_0 &\\\\\n", " \\text{subject to} \\quad\n", " -x_1 - x_2 - x_3 - x_0 &\\leq -1\\\\\n", " -x_1 + x_4 + x_4 - x_0 &\\leq 0\\\\\n", " x_1 - x_4 - x_4 - x_0 &\\leq 0\\\\\n", " -x_2 - x_4 + x_6 - x_0 &\\leq 0\\\\\n", " x_2 + x_4 - x_6 - x_0 &\\leq 0\\\\\n", " x_3 + x_5 + x_6 - x_0 &\\leq 1\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, \\ldots, 6\n", " \\end{aligned}\n", "\n", "and its initial infeasible dictionary is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -x_0\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -1 + x_1 + x_2 + x_3 + x_0\\\\\n", " w_2 &= x_1 - x_4 - x_5 + x_0\\\\\n", " w_3 &= -x_1 + x_4 + x_5 + x_0\\\\\n", " w_4 &= x_2 + x_4 - x_6 + x_0\\\\\n", " w_5 &= -x_2 - x_4 + x_6 + x_0\\\\\n", " w_6 &= 1 - x_3 - x_5 - x_6 + x_0\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, \\ldots, 6\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\n", " \\end{aligned}\n", "\n", "Initial infeasible solution for auxiliary problem:\n", "\n", ".. math::\n", "\n", " x_0 = 0, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 0, \\quad\n", " x_4 = 0, \\quad\n", " x_5 = 0, \\quad\n", " x_6 = 0, \\quad\n", " w_1 = -1, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 0, \\quad\n", " w_4 = 0, \\quad\n", " w_5 = 0, \\quad\n", " w_6 = 1.\n", "\n", "Pivot the infeasible dictionary with :math:`x_0` as the entering variable and\n", ":math:`w_1`, the most infeasible variable, as the leaving variable. The\n", "resulting dictionary is then\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -1 + x_1 + x_2 + x_3 - w_1\\\\\n", " \\text{subject to} \\quad\n", " x_0 &= 1 - x_1 - x_2 - x_3 + w_1\\\\\n", " w_2 &= 1 - x_2 - x_3 - x_4 - x_5 + w_1\\\\\n", " w_3 &= 1 - 2 x_1 - x_2 - x_3 + x_4 + x_5 + w_1\\\\\n", " w_4 &= 1 - x_1 - x_3 + x_4 - x_6 + w_1\\\\\n", " w_5 &= 1 - x_1 - 2 x_2 - x_3 - x_4 + x_6 + w_1\\\\\n", " w_6 &= 2 - x_1 - x_2 - 2 x_3 - x_5 - x_6 + w_1\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, \\ldots, 6\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\n", " \\end{aligned}\n", "\n", "and its feasible solution is updated to\n", "\n", ".. math::\n", "\n", " x_0 = 1, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 0, \\quad\n", " x_4 = 0, \\quad\n", " x_5 = 0, \\quad\n", " x_6 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 1, \\quad\n", " w_3 = 1, \\quad\n", " w_4 = 1, \\quad\n", " w_5 = 1, \\quad\n", " w_6 = 2.\n", "\n", "Even though :math:`x_1` and :math:`x_2` are valid choices, selecting\n", ":math:`x_3` will make phase two much easier. Choose :math:`x_3` and\n", ":math:`x_0` as the entering and leaving variable respectively where\n", "\n", ".. math::\n", "\n", " x_3 = \\min\\left\\{ x_0, w_2, w_3, w_4, w_5, w_6 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 1, 1, 1, 1, 1, 1 \\right\\}_{\\geq 0}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_0 = 0, \\quad\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 1, \\quad\n", " x_4 = 0, \\quad\n", " x_5 = 0, \\quad\n", " x_6 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 0, \\quad\n", " w_4 = 0, \\quad\n", " w_5 = 0, \\quad\n", " w_6 = 0.\n", "\n", "Pivot auxiliary dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -x_0\\\\\n", " \\text{subject to} \\quad\n", " x_3 &= 1 - x_0 - x_1 - x_2 + w_1\\\\\n", " w_2 &= x_0 + x_1 - x_4 - x_5\\\\\n", " w_3 &= x_0 - x_1 + x_4 + x_5\\\\\n", " w_4 &= x_0 + x_2 + x_4 - x_6\\\\\n", " w_5 &= x_0 - x_2 - x_4 + x_6\\\\\n", " w_6 &= 2 x_0 + x_1 + x_2 - x_5 - x_6 - w_1\\\\\n", " x_i &\\geq 0 \\quad i = 0, 1, \\ldots, 6\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\n", " \\end{aligned}\n", "\n", "The dictionary is optimal for the auxiliary problem, so :math:`x_0` can\n", "be dropped and the original objective function can be reintroduced with\n", "the basic variables substituted appropriately:\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " -\\text{maximize} \\quad\n", " \\zeta &= -9 + 8 x_1 + x_2 - 2 x_4 - 7 x_5 - 3 x_6 - 9 w_1\\\\\n", " \\text{subject to} \\quad\n", " x_3 &= 1 - x_1 - x_2 + w_1\\\\\n", " w_2 &= x_1 - x_4 - x_5\\\\\n", " w_3 &= -x_1 + x_4 + x_5\\\\\n", " w_4 &= x_2 + x_4 - x_6\\\\\n", " w_5 &= -x_2 - x_4 + x_6\\\\\n", " w_6 &= x_1 + x_2 - x_5 - x_6 - w_1\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\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 = 1, \\quad\n", " x_4 = 0, \\quad\n", " x_5 = 0, \\quad\n", " x_6 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 0, \\quad\n", " w_4 = 0, \\quad\n", " w_5 = 0, \\quad\n", " w_6 = 0.\n", "\n", "Choose :math:`x_1` and :math:`w_3` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_1 = \\min\\left\\{ x_3, w_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 1, 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 = 1, \\quad\n", " x_4 = 0, \\quad\n", " x_5 = 0, \\quad\n", " x_6 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 0, \\quad\n", " w_4 = 0, \\quad\n", " w_5 = 0, \\quad\n", " w_6 = 0.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " -\\text{maximize} \\quad\n", " \\zeta &= -9 + x_2 + 6 x_4 + x_5 - 3 x_6 - 9 w_1 - 8 w_3\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= x_4 + x_5 - w_3\\\\\n", " x_3 &= 1 - x_2 - x_4 - x_5 + w_1 + w_3\\\\\n", " w_2 &= -w_3\\\\\n", " w_4 &= x_2 + x_4 - x_6\\\\\n", " w_5 &= -x_2 - x_4 + x_6\\\\\n", " w_6 &= x_2 + x_4 - x_6 - w_1 - w_3\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\n", " \\end{aligned}\n", "\n", "Choose :math:`x_4` and :math:`w_5` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_4 = \\min\\left\\{ x_3, w_5 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 0 \\right\\}.\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 = 1, \\quad\n", " x_4 = 0, \\quad\n", " x_5 = 0, \\quad\n", " x_6 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 0, \\quad\n", " w_4 = 0.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " -\\text{maximize} \\quad\n", " \\zeta &= -9 - 5 x_2 + x_5 + 3 x_6 - 9 w_1 - 8 w_3 - 6 w_5\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= -x_2 + x_6 - w_3\\\\\n", " x_3 &= 1 - x_5 - x_6 + w_1 + w_3 + w_5\\\\\n", " x_4 &= -x_2 + x_6 - w_5\\\\\n", " w_2 &= -w_3\\\\\n", " w_4 &= -w_5\\\\\n", " w_6 &= -w_1 - w_3 - w_5\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\n", " \\end{aligned}\n", "\n", "Choose :math:`x_6` and :math:`x_3` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_6 = \\min\\left\\{ x_3 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 1, 0 \\right\\}.\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 = 0, \\quad\n", " x_4 = 1, \\quad\n", " x_5 = 0, \\quad\n", " x_6 = 1, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 0, \\quad\n", " w_4 = 0, \\quad\n", " w_5 = 0, \\quad\n", " w_6 = 0.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " -\\text{maximize} \\quad\n", " \\zeta &= -6 - 5 x_2 - 3 x_3 - 2 x_5 - 6 w_1 - 5 w_3 - 3 w_5\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 1 - x_2 - x_3 - x_5 + w_1 + w_5\\\\\n", " x_4 &= 1 - x_2 - x_3 - x_5 + w_1 + w_3\\\\\n", " x_6 &= 1 - x_3 - x_5 + w_1 + w_3 + w_5\\\\\n", " w_2 &= -w_3\\\\\n", " w_4 &= -w_5\\\\\n", " w_6 &= -w_1 - w_3 - w_5\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6\n", " \\end{aligned}\n", "\n", "Since no other coefficients are positive, the solution is optimal." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 2.12 and Exercise 2.13\n", "===============================\n", "\n", "The previous exercises were solved using the proposed tool." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 2.14\n", "=============\n", "\n", "Choose :math:`x_6` and :math:`w_1` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_6 = \\min\\left\\{ w_1, w_2 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ 1, \\frac{5}{3} \\right\\}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 1, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 2.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 9 + 7 x_1 - 6 w_1\\\\\n", " \\text{subject to} \\quad\n", " x_2 &= 1 + x_1 - w_1\\\\\n", " w_2 &= 2 - 5 x_1 + 3 w_1\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-2.15:\n", "\n", "Exercise 2.15\n", "=============\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 4 - w_1 - 2 x_2\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 3 - 2 x_2\\\\\n", " w_2 &= 1 + w_1 - x_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "Suppose the optimal solution for the above dictionary :math:`D_0` is\n", "\n", ".. math::\n", "\n", " x_1 = 3, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 1.\n", "\n", ":doc:`Since pivot operations are reversible `,\n", "one can mechanically trace back to original problem where :math:`w_1` and\n", ":math:`w_2` are the initial slack variables. As shown in\n", ":ref:`Exercise 2.17 ` and\n", ":ref:`Exercise 2.18 `, reverse pivots only need to\n", "examine the variables whose coefficient is negative in the objective function.\n", "\n", "Even though the following dictionaries are still feasible with the proposed\n", "optimal solution, none of them have :math:`w_1` and :math:`w_2` as the initial\n", "slack variables:\n", "\n", "- :math:`D_{1 \\mapsto 0}` cannot be pivoted to :math:`D_0` with one iteration.\n", "- :math:`D_{6 \\mapsto 3} = D_{4 \\mapsto 2}`, but :math:`D_{4 \\mapsto 2}` cannot\n", " be pivoted to :math:`D_{6 \\mapsto 3}` with one iteration.\n", "- :math:`D_{5 \\mapsto 2} = D_{1 \\mapsto 0}`, but :math:`D_{1 \\mapsto 0}` cannot\n", " be pivoted to :math:`D_{5 \\mapsto 2}` with one iteration.\n", "- :math:`D_{7 \\mapsto 4}` cannot be pivoted to :math:`D_{4 \\mapsto 2}` with one\n", " iteration.\n", "\n", "If feasibility preservation of intermediate dictionaries are no longer\n", "necessary, then choose :math:`w_1` and :math:`x_1` as the entering and leaving\n", "variable respectively where\n", "\n", ".. math::\n", "\n", " w_1 = \\frac{3 - x_1 - 2 x_2}{0}.\n", "\n", "Adopting the convention where :math:`\\frac{0}{0}` is treated as a zero, the\n", "corrresponding pivoted dictionary is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 4 - \\frac{3 - x_1 - 2 x_2}{0} - 2 x_2\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= \\frac{3 - x_1 - 2 x_2}{0}\\\\\n", " w_2 &= 1 + \\frac{3 - x_1 - 2 x_2}{0} - x_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", ":math:`D_{1 \\mapsto 0}`\n", "-----------------------\n", "\n", "Let :math:`w_1` be the previous leaving variable and :math:`w_2` be the previous\n", "entering variable.\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 5 - 3 x_2 - w_2\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 3 - 2 x_2\\\\\n", " w_1 &= -1 + x_2 + w_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "No need to continue along this path since the reverse pivot is not reversible.\n", "\n", ":math:`D_{2 \\mapsto 0}`\n", "-----------------------\n", "\n", "Let :math:`x_2` be the previous leaving variable and :math:`w_2` be the previous\n", "entering variable.\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 2 - 3 w_1 + 2 w_2\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 1 - 2 w_1 + 2 w_2\\\\\n", " x_2 &= 1 + w_1 - w_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", ":math:`D_{3 \\mapsto 0}`\n", "-----------------------\n", "\n", "Let :math:`x_2` be the previous leaving variable and :math:`x_1` be the previous\n", "entering variable.\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 1 + x_1 - w_1\\\\\n", " \\text{subject to} \\quad\n", " x_2 &= \\frac{1}{2} (3 - x_1)\\\\\n", " w_2 &= \\frac{1}{2} (-1 + x_1 + 2 w_1)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", ":math:`D_{4 \\mapsto 2}`\n", "-----------------------\n", "\n", "Let :math:`w_1` be the previous leaving variable and :math:`x_1` be the previous\n", "entering variable.\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{2} (1 + 3 x_1 - 2 w_2)\\\\\n", " \\text{subject to} \\quad\n", " x_2 &= \\frac{1}{2} (3 - x_1)\\\\\n", " w_1 &= \\frac{1}{2} (1 - x_1 + 2 w_2)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", ":math:`D_{5 \\mapsto 2}`\n", "-----------------------\n", "\n", "Let :math:`w_1` be the previous leaving variable and :math:`x_2` be the previous\n", "entering variable. The resulting dictionary is equal to\n", ":math:`D_{1 \\mapsto 0}`.\n", "\n", ":math:`D_{6 \\mapsto 3}`\n", "-----------------------\n", "\n", "Let :math:`w_1` be the previous leaving variable and :math:`w_2` be the previous\n", "entering variable. The resulting dictionary is equal to\n", ":math:`D_{4 \\mapsto 2}`.\n", "\n", ":math:`D_{7 \\mapsto 4}`\n", "-----------------------\n", "\n", "Let :math:`w_2` be the previous leaving variable and :math:`w_1` be the previous\n", "entering variable.\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{2} (3 + x_1 - 4 w_1)\\\\\n", " \\text{subject to} \\quad\n", " x_2 &= \\frac{1}{2} (3 - x_1)\\\\\n", " w_2 &= \\frac{1}{2} (-1 + x_1 + 2 w_1)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "No need to continue along this path since the reverse pivot is not reversible.\n", "The only choice for a pivot is choosing :math:`x_1` and :math:`x_2` as the\n", "entering and leaving variable respectively resulting in\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= 3 - x_2 - 2 w_1\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 3 - 2 x_2\\\\\n", " w_2 &= 1 - x_2 + w_1\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 2.16\n", "=============\n", "\n", "The sequence of basic solutions produced by the simplex method starts at\n", ":math:`(0, 0)` and advances counter-clockwise along the perimeter of the\n", "plot until the vertex :math:`(4, 8)` is encountered." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "raw_mimetype": "text/x-python" }, "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 = x1 - 2 * x2 <= 1\n", "c2 = And(c1, x1 - x2 <= 2)\n", "c3 = And(c2, 2 * x1 - x2 <= 6)\n", "c4 = And(c3, x1 <= 5)\n", "c5 = And(c4, 2 * x1 + x2 <= 16)\n", "c6 = And(c5, x1 + x2 <= 12)\n", "c7 = And(c6, x1 + 2 * x2 <= 21)\n", "c8 = And(c7, x2 <= 10)\n", "c9 = And(c8, x1 >= 0)\n", "c10 = And(c9, x2 >= 0)\n", "\n", "plot_implicit(c10, (x1, 0, 5.5), (x2, 0, 11),\n", " title='Feasible Region', xlabel='$x_1$', ylabel='$x_2$');" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-2.17:\n", "\n", "Exercise 2.17\n", "=============\n", "\n", "See Exercise 2.9." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-2.18:\n", "\n", "Exercise 2.18\n", "=============\n", "\n", "The general linear programming problem with slack variables is\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", " w_i &= b_i - \\sum_{j \\in \\mathcal{N}}^n a_{ij} x_j\n", " \\quad i \\in \\mathcal{B}\\\\\n", " x_j &\\geq 0 \\quad j = 1, 2, \\ldots, n\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, \\ldots, m\n", " \\end{aligned}\n", "\n", "Without loss of generality, the entering variable :math:`x_e` will be chosen\n", "from :math:`\\{j \\in \\mathcal{N} \\colon c_j > 0 \\}`; consequently, the leaving\n", "variable :math:`w_l` will be chosen from\n", ":math:`\\{i \\in \\mathcal{B} \\colon a_{ie} > 0 \\text{ and } \\frac{b_i}{a_{ie}} \\text{is minimal}\\}`.\n", "\n", "Pivoting will result in\n", "\n", ".. math::\n", "\n", " x_e &= a_{le}^{-1} \\left(\n", " b_l - w_l - \\sum_{j \\in \\mathcal{N} \\setminus e}^n a_{lj} x_j\n", " \\right)\\\\\n", " \\\\\n", " \\zeta &= c_e x_e + \\sum_{j \\in \\mathcal{N} \\setminus e}^n c_j x_j\n", " = \\frac{c_e}{a_{le}} b_l - \\frac{c_e}{a_{le}} w_l +\n", " \\sum_{j \\in \\mathcal{N} \\setminus e}^n\n", " \\left( c_j - \\frac{c_e a_{lj}}{a_{le}} \\right) x_j\n", "\n", "where the other constraints are replaced appropriately, but is not essential\n", "to the conclusion of this proof.\n", "\n", "Since :math:`-\\frac{c_e}{a_{le}}` must be negative, the nonbasic variable\n", ":math:`w_l` cannot be selected in the next iteration." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-2.19:\n", "\n", "Exercise 2.19\n", "=============\n", "\n", "The equivalent problem with slack variables is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\sum_{j = 1}^n p_j x_j\\\\\n", " \\text{subject to} \\quad\n", " w_0 &= \\beta - \\sum_{j = 1}^n q_j x_j\\\\\n", " w_j &= 1 - x_j\\\\\n", " x_j &\\geq 0 \\quad j = 1, 2, \\ldots, n\\\\\n", " w_j &\\geq 0 \\quad j = 1, 2, \\ldots, n\\\\\n", " w_0 &\\geq 0\n", " \\end{aligned}\n", "\n", "where the initial feasible solution is\n", "\n", ".. math::\n", "\n", " x_j = 0 \\qquad \\land \\qquad w_0 = \\beta \\qquad \\land \\qquad w_j = 1.\n", "\n", "Suppose :math:`x_1` is the first entering variable. Pivoting requires\n", "determining\n", "\n", ".. math::\n", "\n", " x_1 = \\min\\left\\{ w_0, w_1 \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ \\frac{\\beta}{q_1}, 1 \\right\\}.\n", "\n", "In order to make progress and simplify the analysis, assume\n", "\n", ".. math::\n", "\n", " \\beta \\geq q_1 + q_2 + \\cdots + q_{k - 2} + q_{k - 1}\n", "\n", "where :math:`k \\in [0, n]` is the largest possible index. This will cause the\n", "simplex algorithm to swap :math:`x_j` and :math:`w_j` in each constraint where\n", ":math:`1 \\leq j < k` resulting in\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\sum_{j = 1}^{k - 1} p_j (1 - w_j) + \\sum_{j = k}^n p_j x_j\\\\\n", " \\text{subject to} \\quad\n", " w_0 &= \\beta - \\sum_{j = 1}^{k - 1} q_j (1 - w_j) - \\sum_{j = k}^n q_j x_j\\\\\n", " x_j &= 1 - w_j \\quad j < k\\\\\n", " w_j &= 1 - x_j \\quad j \\geq k\\\\\n", " x_j &\\geq 0 \\quad j = 1, 2, \\ldots, n\\\\\n", " w_j &\\geq 0 \\quad j = 1, 2, \\ldots, n\\\\\n", " w_0 &\\geq 0\n", " \\end{aligned}\n", "\n", "Now pivot :math:`x_k \\leftrightarrow w_0` since\n", "\n", ".. math::\n", "\n", " x_k = \\min\\left\\{ w_0, w_k \\right\\}_{\\geq 0}\n", " = \\min\\left\\{ \\frac{\\beta - \\sum_{j = 1}^{k - 1} q_j}{q_k}, 1 \\right\\}.\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_j &= 1 \\quad j < k,\\\\\n", " x_k &= \\frac{\\beta - \\sum_{j = 1}^{k - 1} q_j}{q_k},\\\\\n", " x_j &= 0 \\quad j > k,\\\\\n", " w_0 &= 0,\\\\\n", " w_j &= 0 \\quad j < k,\\\\\n", " w_k &= 1 - \\frac{\\beta - \\sum_{j = 1}^{k - 1} q_j}{q_k},\\\\\n", " w_j &= 1 \\quad j > k.\n", "\n", "The resulting dictionary is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{p_k}{q_k} (\\beta - w_0) +\n", " \\sum_{j = 1}^{k - 1} p_j - \\frac{p_k}{q_k} q_j +\n", " \\left( \\frac{p_k}{q_k} q_j - p_j \\right) w_j +\n", " \\sum_{j = k + 1}^n \\left( p_j - \\frac{p_k}{q_k} q_j \\right) x_j\\\\\n", " \\text{subject to} \\quad\n", " x_k &= \\frac{1}{q_k}\n", " \\left(\n", " \\beta - \\sum_{j = 1}^{k - 1} q_j (1 - w_j) - w_0 -\n", " \\sum_{j = k + 1}^n q_j x_j\n", " \\right)\\\\\n", " x_j &= 1 - w_j \\quad j < k\\\\\n", " w_k &= 1 - \\frac{1}{q_k}\n", " \\left(\n", " \\beta - \\sum_{j = 1}^{k - 1} q_j (1 - w_j) - w_0 -\n", " \\sum_{j = k + 1}^n q_j x_j\n", " \\right)\\\\\n", " w_j &= 1 - x_j \\quad j > k\\\\\n", " x_j &\\geq 0 \\quad j = 1, 2, \\ldots, n\\\\\n", " w_j &\\geq 0 \\quad j = 1, 2, \\ldots, n\\\\\n", " w_0 &\\geq 0\n", " \\end{aligned}\n", "\n", "This dictionary is optimal if all objective coefficients are non-positive\n", "since that would make the set of entering variables empty. This is the\n", "case if the following assumption\n", "\n", ".. math::\n", "\n", " \\frac{p_1}{q_1} > \\cdots > \\frac{p_{k - 1}}{q_{k - 1}} >\n", " \\frac{p_k}{q_k} > \\frac{p_{k + 1}}{q_{k + 1}} > \\cdots > \\frac{p_n}{q_n}\n", "\n", "holds since that would make :math:`\\frac{p_k}{q_k} q_j - p_j < 0` for\n", ":math:`j < k` and :math:`p_j - \\frac{p_k}{q_k} q_j < 0` for :math:`j > k`.\n", "\n", "Note that if one applies the book's proposed assumption, the optimal solution\n", "is the reverse order. The derivation would start with :math:`x_n` instead of\n", ":math:`x_1` and\n", ":math:`\\beta \\geq q_{k + 1} + q_{k + 2} + \\cdots + q_{n - 1} + q_n` where\n", ":math:`k \\in [0, n]` is the smallest possible index." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. rubric:: References\n", "\n", ".. bibliography:: chapter-02.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 }