How to draw the graph of the optimised function in linear programming

Question

Ok, I don't know if I am just over thinking this, but I have been tearing my hair out trying to think about this. I have looked at plenty of linear programming examples and solutions online and I can't find anything that explains how the optimised function is drawn.

For example, there is a situation where you are trying to minimise the cost of potatoes and soybeans where $x_s$ is the amount of soybeans and $x_p$ is the amount of potatoes.

Soybeans cost twice the amount that potatoes do so we have a cost function of $C = x_p + 2x_s$ which we are trying to minimize.

There are some other constraints involved which I understand how to derive:

• $2x_p + 3x_s \ge 12$
• $4x_p + x_s \ge 8$
• $x_p \ge 0 $ and $x_s \ge 0 $

The following graph is shown in the answer to the question where the blue line represents the cost function and the red star is the optimal solution (which I also know how to find once the cost function is drawn)

What is the logic behind drawing the blue graph line from $C = x_p + 2x_s$? (Sorry if I am just being really stupid but please explain it I need to sleep.)

Answer 1

The blue line is perpendicular to all the lines of the form $x_p+2x_s=c$ where $c$ is a constant, i.e. to the level sets of the cost function. So each point on it has a different cost, and the cost goes down as you move to the left. The slope of the blue line is $2$ because the slopes of the level sets of the cost function are all $-1/2$. So this graphical technique reduces the optimization question to "what is the leftmost point on the blue line such that if you draw the line perpendicular to the blue line through that point, there is a point on that line in the feasible region?"

This is a little bit of a weird way to do it, I think, but it does work.

Answer 2

A cost isoline is $$ C = x_p + 2 x_s \quad (*) \iff \\ x_s = -\frac{1}{2} x_p + \frac{C}{2} \quad (F) $$ We can rewrite $(*)$ as $$ (1, 2) \cdot (x_p, x_s) = C \iff \\ (1/\sqrt{5}) \, (1,2) \cdot (x_p, x_s) = C/\sqrt{5} \quad (N) $$ which is the equation of an affine hyperplane (sounds complicated, but is just a line which needs not to include the origin in $\mathbb{R}^2$) with unit normal $n = (1/\sqrt{5}) \, (1,2)$ and distance $C/\sqrt{5}$ to the origin.

That blue line is $\alpha \, n$ (for real numbers $\alpha$). The cost isolines run orthogonal to it, and have the distance $C/\sqrt{5}$ from the origin. The lower the (absolute value of the) cost, the closer to the origin runs the cost isoline.

The above image shows the constraints (half spaces in green colour), the feasible region (the region with the darkest green), the normal line $\alpha n$ (blue line), the cost isolines for $C=10$, $C=8$ and $C=6$ (black lines orthogonal to the blue line). Circles of distance with $r = 1$ and $r = 6/\sqrt{5}$ around the origin (purple circles). And finally the optimum with minimal cost (red dot).

Answer 3

Let $a$ be the slope of the cost function. Then the perpendicular line has slope $-1/a$. Along the perpendicular line the cost will grow or fall depending on which way you go.