Christmas LP Assignment

We have by now realized that LP problems, Simplex Methods, and LP theorems, all have several aspects interwoven in magical and deep ways. It pays a lot to go back to the first and old exercises and try to look at them from as many angles as possible. I am suggesting to first practice all of the ideas you have encountered on a same single (and simple) problem with the purpouse of giving unity to what learned until now. For example, you could go back to PROBLEM 1 among the `` Mathematical problems in agriculture'' in the document ``But ..., this is just an LP problem !!!''.

PROBLEM 1: A farmer owns 2 hectars of land. The farmer can not work at his estate for more than 5 months each year. Each hectar planted with Renette Golden (a variety of apples) demands for 3 working months, whereas an hectar planted with the Canada variety demands only 2 working months. However, each hectar planted with Renette Golden currently payes about 5 silver coins whereas the same hectar planted with Canada would fruit 4. Under which planting policy would the farmer maximize his profit? Formulate the problem within the LP model.

What I am suggesting to do is to stop on a single same old problem and put yourself new questions, practicing all the spectrum of techniques seen. For example: solve the problem with the Simplex Method but also geometrically (since it only has 2 decision variables you can do it). Formulate the dual problem. Grab an optimal solution for the dual problem from the last dictionary for the primal problem. You can get to the same dual solution by running the Simplex Method on the dual, or even geometrically. Can you provide a meaning for the dual variables and an interpretation for the dual problem? On this line, can you argue for the optimality of the primal solution on the basis of the dual one? Put the complementary slackness conditions in action to obtain a dual optimal solution from the primal optimal one, and viceversa. Consider possible variations to the problem and analize how the optimal solution would change. More precisely, try considering a change in the profits (number of silver coins for each hectar planted X). Otherwise, try considering a change in resources available (number of hectars owned by the farmer and working months). The questions you should here consider are for example as follows. Should the farmer consider renting land? At which price? Is it worth renting man-power, or should the farmer dedicate his own time to more fruitful activities? When the answer to such questions is positive, we could consider introducing new variables (amount of rented land, working-houers hired) and the corresponding bounds. We could here try to solve the problem hence obtained starting from the old optimal solution or dictionary (warm start, in case feasibility is preserved). But it can certainly happen that new constraints kill out the current solution. This is what actually happens in practice, where offen the complete formulation comes gradually to light only by trials and errors. (A sequence of optimal solutions is produced, but they get subsequently trimmed away becouse they lead to realize new sources of infeasibility). How is it possible to take advantage of the previous work in this kind of situations? Indeed, the addition of new constraints destroyies primal feasibility. But what about dual feasibility?

If you will enter this most rewarding approach, you will soon have abundance of problems on which to practice. But let me propose some more concrete exercises for making up an assignment which you are asked to perform during the Christmas holidays.



Solve the following problems saving as much work as possible

PROBLEM 1:


\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }6x_1 + 7x_2\\
\left\{
\b...
...{array} \\
x_1, x_2 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

PROBLEM 2:


\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }x_1 + x_2 + x_3 \\
\left\...
...y} \\
x_1, x_2, x_3 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

PROBLEM 3:


\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }2x_1 -3x_2 + 5x_3 \\
\lef...
...y} \\
x_1, x_2, x_3 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

Note that the last constraint is of the form $x_1-5x_2-x_3 = c$. What is the biggest value of $c$ which makes the problem feasible?


Spaces of Optimal Solutions

PROBLEM 4:

Find the space of optimal solutions and list all the optimal basic solutions.

\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }2x_1 +x_2 \\
\left\{
\be...
...{array} \\
x_1, x_2 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

PROBLEM 5:


\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }2x_1 +x_2 \\
\left\{
\be...
...y} \\
x_1, x_2, x_3 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

Find next the optimal solutions which maximize $-2x_1-x_2-x_3$.


Dealing with Changes in the Formulation

PROBLEM 6:


\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }x_1 +x_2 +x_3\\
\left\{
...
...y} \\
x_1, x_2, x_3 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

What happens in case the second constraint is dropped?

PROBLEM 7:


\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }x_1 +x_2 \\
\left\{
\beg...
...y} \\
x_1, x_2, x_3 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

What happens in case the first constraint is dropped? What happens in case the second constraint is dropped?

PROBLEM 8:


\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }6x_1 +8x_2 +7x_3\\
\left\...
...y} \\
x_1, x_2, x_3 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

Add next the constraint $x_1+4x_2+3x_3\leq 30$.

PROBLEM 9:


\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }x_1 +2x_2 +3x_3 +2x_4\\
\...
...
x_1, x_2, x_3, x_4 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

Add next the constraints $2x_1-x_2+5x_3 +x_4\leq 16$ and $x_1-2x_2-3x_3 +4x_4\geq -8$.

PROBLEM 10:


\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }2x_1 +x_2 \\
\left\{
\be...
...{array} \\
x_1, x_2 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

Add next the constraints $x_1, x_2 \leq 1$.

PROBLEM 11:


\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }x_1 +x_2 +x_3 +x_4 +x_5 +x_...
...2, x_3, x_4, x_5, x_6 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

Solve it by first ignoring the last two constraints.


Complementary Slackness

PROBLEM 12:


\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }x_1 +x_2 -3x_3 -2x_4\\
\l...
...
x_1, x_2, x_3, x_4 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

Consider the solution $x_1 = x_2 = 5$ e $x_3 = x_4 = 0$. Is it admissible? Is it basic? Is it optimal?

PROBLEM 13:


\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }4x_1 +5x_2 -3x_3 -8x_4\\
...
...
x_1, x_2, x_3, x_4 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

Consider the solution $x_1 = x_2 = 3$ e $x_3 = x_4 = 0$. Is it admissible? Is it basic? Is it optimal?

PROBLEM 14:


\begin{displaymath}
\begin{array}{l}
\max \mbox{\ }3x_1 +4x_2 +2x_3 +5x_4\\
...
...
x_1, x_2, x_3, x_4 \geq 0
\end{array} \right.
\end{array}\end{displaymath}

The little bird told me that in the optimal solution the variables $x_2$ and $x_4$ are strictly positive and that the third constraint is satified with strict inequality ($<$). Find the optimal solution. If the optimal solution represents the profit of an activity, how much would be considering to pay to increment by one unit the constant in the first, second or third constraint? And up to what extent would it be reasonable to pay such price? How much should we alter the single coefficients into the objective function to destroy optimality of the solution?


Enjoy!



2001-12-19 © Dipartimento di Matematica - Università di Trento