Linear Programming/Examples/Arbitrary Example 1

From ProofWiki
Jump to navigation Jump to search

Examples of Linear Programming

Let it be required to find the minimum of the function:

$\map U {x, y} = 4 x + 3 y$

subject to the conditions:

\(\ds x + y\) \(\le\) \(\ds 20\)
\(\ds 3 x + y\) \(\le\) \(\ds 30\)
\(\ds x\) \(\ge\) \(\ds 0\)
\(\ds y\) \(\ge\) \(\ds 0\)

The maximum feasible value of $U$ is given by:

$U = 65$


Proof

Let us present the above information in a graphical form:


Linear-programming-example.png


The $\color { red } {\text {red} }$ lines represent the boundary lines of the conditions:

the line $AB$ represents the condition $x + y = 20$
the line $CD$ represents the condition $3 x + y = 30$

while the axes represent the conditions $x = 0$ and $y = 0$.

Hence the region in which feasible solutions exist is the colored region $OAED$.


The dashed parallel lines represent the equation $U = 4 x + 3 y$ for various values of $U$.

As $U$ increases, the dashed line moves to the right.


Hence the optimum value of $U$ occurs when $U$ is chosen so that the line passes through the point $E$.

This is where the lines $x + y = 20$ and $3 x + y = 30$ intersect.


Solving these simultaneous equations gives us:

\(\ds x\) \(=\) \(\ds 5\)
\(\ds y\) \(=\) \(\ds 15\)


Hence the maximum feasible value of $U$ is given by:

\(\ds U\) \(=\) \(\ds 4 \times 5 + 3 \times 15\)
\(\ds \) \(=\) \(\ds 65\)

which is the required solution.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Linear_Programming/Examples/Arbitrary_Example_1&oldid=696167"