3318-Corn and Barley via Simplex Method.sagews

This worksheet uses a special module not available in the standard distribution of Sage. You can access it via the third menu list above ("Data..."), if you wish to look at the code or download it separately. The following command makes functionality of this module available for later use in the worksheet and should be executed first. It is also recommended to check "Typeset" box located after the fourth menu list.

load DATA + "interactive_simplex_method.py"

Corn and Barley via Simplex Method

We are working (still) on the following problem:

A farmer has 1000 acres available to grow corn and barley. Corn has a net profit of \$10/acre while barley has a net profit of \$5/acre. The farmer has 1500 kilogramms of fertilizer available with 3kg/acre needed for corn and 1kg/acre needed for barley. According to local laws, at least 40% of available land must be used. The farmer wants to maximize the profit.

We have seen, that in the standard form you can formulate this problem as

$$ \begin{array}{l}

\max\ 10 x_1 + 5 x_2 \\

x_1 + x_2 \leq 1000 \\

3x_1 + x_2 \leq 1500 \\

- x_1 - x_2 \leq -400 \\

x_1, x_2 \geq 0,

\end{array} $$

where $x_1$ is the land (in acres) used to plant corn and $x_2$ is the land used to plant barley. Alternatively, this problem (and any other in the standard form) can be written as

$$ \begin{array}{l}

\max\ c x \\

A x \leq b \\

x \geq 0,

\end{array} $$

where $A$ is a matrix of coefficients in the inequalities, $b$ is the vector of constant terms in the inequalities, $c$ is the vector of coefficients of the objective function, and $x$ is the vector of decision variables. We can define these objects and set up an LP problem in Sage as follows.

A = matrix([
[1, 1],
[3, 1],
[-1, -1]
])

b = (1000, 1500, -400)
c = (10, 5)
P = StandardFormLPP(A, b, c)
P

\newcommand{\Bold}[1]{\mathbf{#1}}ParseError: KaTeX parse error: Expected & or \\ or \cr or \end at end of input: … \\ \end{array} \\ x_{1}, x_{2} \geq 0 \end{array}

If the output above does not look "pretty", e.g. you see "x1" instead of "$x_1$", check the "Typeset" box on the top.

To solve this problem using Simplex Method, we start with the Initial Dictionary:

ID = P.initial_dictionary()
ID

ID.is_feasible()

\newcommand{\Bold}[1]{\mathbf{#1}}{\rm False}

Unfortunately, this dictionary is infeasible, so we need to go through the Phase I and solve the Auxiliary Problem first.

A = P.auxiliary_problem()
A

\newcommand{\Bold}[1]{\mathbf{#1}}ParseError: KaTeX parse error: Expected & or \\ or \cr or \end at end of input: … \\ \end{array} \\ x_{1}, x_{2}, x_{0} \geq 0 \end{array}

AD = A.initial_dictionary()
AD

AD.is_optimal()

\newcommand{\Bold}[1]{\mathbf{#1}}{\rm False}

AD.is_feasible()

\newcommand{\Bold}[1]{\mathbf{#1}}{\rm False}

It is no surprise to us that this dictionary is not optimal and not even feasible. But for the auxiliary problem we know how to get a feasible dictionary: let $x_0$ enter and the variable with the most negative constant coefficient leave. The following commands set $x_0$ as the entering variable, $x_5$ as the leaving variable, then update the dictionary (which is usually the longest step if you do it by hand - now you can avoid its computational details, but remember that no computers can be used on the tests), and show it.

AD.enter("x0")
AD.leave("x5")
AD.update()
AD

AD.is_feasible()

\newcommand{\Bold}[1]{\mathbf{#1}}{\rm True}

AD.is_optimal()

\newcommand{\Bold}[1]{\mathbf{#1}}{\rm False}

The dictionary is still not optimal, but now it is feasible and we can use the "usual" Simplex Method. On each step we want to do the same operations as above, for convenience you can call the "elusive" method:

• Enter
• Leave
• Update
• Show
• Is feasible/optimal VErification

AD.elusive("x1", "x0")

Entering:

\newcommand{\Bold}[1]{\mathbf{#1}}x_{1}

Leaving:

\newcommand{\Bold}[1]{\mathbf{#1}}x_{0}

Optimal!

It is actually possible to call this method without specifying entering and leaving variables: it will not guess them for you, but will just show the dictionary and its status.

AD.elusive()

Optimal!

With an optimal dictionary for the auxiliary problem (and with the optimal value ZERO), we can construct a Feasible Dictionary for the original problem and use it for Phase II.

FD = P.feasible_dictionary(AD)
FD.elusive()

Feasible.

FD.elusive("x5", "x4")

Entering:

\newcommand{\Bold}[1]{\mathbf{#1}}x_{5}

Leaving:

\newcommand{\Bold}[1]{\mathbf{#1}}x_{4}

Feasible.

FD.elusive("x2", "x3")

Entering:

\newcommand{\Bold}[1]{\mathbf{#1}}x_{2}

Leaving:

\newcommand{\Bold}[1]{\mathbf{#1}}x_{3}

Optimal!

From this optimal dictionary we can read-off the Optimal Value 6250 and an Optimal Solution  $x_1 = 250,\ x_2 = 750$.

 

Now let's turn our attention to the Dual Problem.

D = P.dual()
D

\newcommand{\Bold}[1]{\mathbf{#1}}ParseError: KaTeX parse error: Expected & or \\ or \cr or \end at end of input: … \\ \end{array} \\ y_{1}, y_{2}, y_{3} \geq 0 \end{array}

In order to be able to solve it using the Simplex Method, we need to convert it to standard form. Fortunately, it is easy for dual problems:

DasP = D.convert_to_negative_primal()
DasP

\newcommand{\Bold}[1]{\mathbf{#1}}- \left\{ ParseError: KaTeX parse error: Expected & or \\ or \cr or \end at end of input: … \\ \end{array} \\ y_{1}, y_{2}, y_{3} \geq 0 \end{array} \right.

AD = DasP.auxiliary_problem().initial_dictionary()
AD.elusive()

Infeasible!

AD.elusive("y0", "y4")

Entering:

\newcommand{\Bold}[1]{\mathbf{#1}}y_{0}

Leaving:

\newcommand{\Bold}[1]{\mathbf{#1}}y_{4}

Feasible.

AD.elusive("y1", "y0")

Entering:

\newcommand{\Bold}[1]{\mathbf{#1}}y_{1}

Leaving:

\newcommand{\Bold}[1]{\mathbf{#1}}y_{0}

Optimal!

FD = DasP.feasible_dictionary(AD)
FD.elusive()

Feasible.

FD.elusive("y2", "y5")

Entering:

\newcommand{\Bold}[1]{\mathbf{#1}}y_{2}

Leaving:

\newcommand{\Bold}[1]{\mathbf{#1}}y_{5}

Optimal!

The optimal value of the dual problem is the same as for the primal one, 6250 (remember "the minus in front"). An optimal solution is given by $y_1 = 2.5,\ y_2 = 2.5,\ y_3 = 0$.

 

You can use the same framework for any other problem (in standard form). When doing this beware that most of the "typos" will be caught for you, e.g.

FD.elusive("y3", "y2")

Entering:

\newcommand{\Bold}[1]{\mathbf{#1}}y_{3}

Leaving:

\newcommand{\Bold}[1]{\mathbf{#1}}y_{2}

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_27.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("RkQuZWx1c2l2ZSgieTMiLCAieTIiKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmp2eoWVw/___code___.py", line 2, in <module> exec compile(u'FD.elusive("y3", "y2")' + '\n', '', 'single') File "", line 1, in <module> File "/sagenb/servers/sage_notebook-sagenb.sagenb/home/Novoseltsev/0/data/interactive_simplex_method.py", line 516, in elusive self.leave(leaving) File "/sagenb/servers/sage_notebook-sagenb.sagenb/home/Novoseltsev/0/data/interactive_simplex_method.py", line 559, in leave raise ValueError("%s cannot leave when %s enters!" % (v, entering)) ValueError: y2 cannot leave when y3 enters!

but you are still free to shoot yourself in a foot:

FD.elusive("y3", "y1")

Entering:

\newcommand{\Bold}[1]{\mathbf{#1}}y_{3}

Leaving:

\newcommand{\Bold}[1]{\mathbf{#1}}y_{1}

Infeasible!

If you have any issues that you cannot resolve, please let me know and I will try to help. If you "share" your worksheet with me (using "Share" blue button on the top right of the page) and send me an email with your username and short description of the problem, I should be able to correct it (and leave some comments) directly in your worksheet.