# Thread: Linear Programming using graphs

1. ## Linear Programming using graphs

a) Use graphical methods to determine the feasible region for these constraints:
Subject to 2x1+5x2 is greater than or equal to 10
2x1 - x2 is less than or equal to 6
x1 is greater than or equal to 1
x1 + x2 is less or equal to 6
(the 1 & 2 after the x is small which sits just below the x)

b) subject to the constraints in a),
i) minimise P=x2
ii) maximise Q=10x1 + 5x2

2. This is good for practice.

It will be long if I show it all, so let me assume you know how to graph inequalities and how to find the intersection of two inequalities.

I don't know how to sketch figures here so sketch it on paper.

Subject to 2x1+5x2 is greater than or equal to 10
The x1 and x2 will confuse you no end, so let x = x1, and y = x2.
So the four constraints are:
2x +5y >= 10 -------(1)
2x -y <= 6 ----------(2)
x >= 1 --------------(3)
x +y <= 6 -----------(4)

Plot the 4 inequalities on the same x,y rectangular axes.
You'd find that the feasible region is a quadrilateral whose four corner points are
(1,1.6) .......or (1,8/5)
(1,5)
(4,2)
(2.67,0.67)....or (8/3,2/3)

i) minimise P=x2
Or, minimize P = y.
The corner point with the lowest y is (8/3,2/3).
Therefore, minimum P = 2/3 --------------------------answer.

ii) maximise Q=10x1 + 5x2
Or, maximize Q = 10x +5y -------------**
You have to test that to all of the 4 corner points to see which corner gives the highest Q.
----at (1,8/5)---- Q = 10(1) +5(8/5) = 18
----at (1,5)------ Q = 10(1) +5(5) = 35
----at (4,2)------ Q = 10(4) +5(2) = 50
----at (8/3,2/3)-- Q = 10(8/3) +5(2/3) = 90/3 = 30
Therefore, maximum Q is 50. -------------------------answer.

If anything is not clear, ask me.

3. Hello, tondie2!

Use graphical methods to determine the feasible region for these constraints:

. . $\displaystyle \begin{array}{cc}2x+5y \:\geq\:10 & [1] \\ 2x - y \:\leq \:6 & [2]\\ x + y \:\leq\:6 & [3]\\ x \:\geq \:1 & [4]\end{array}$

Graph the line of [1].
It has intercepts: $\displaystyle (5,0),\;(0,2)$
Shade the region above the line.

Graph the line of [2].
It has intercepts: $\displaystyle (3,0),\;(0,-6)$
Shade the region above the line.

Graph the line of [3].
It has intercepts: $\displaystyle (6,0),\;(0,6)$
Shade the region below the line.

Graph the line of [4].
It is a vertical line with x-intercept $\displaystyle (1,0)$.
Shade the region to the right of the line.

As ticbol pointed out, the region is a quadrilateral.
. .
But I differ on one vertex.

$\displaystyle [1] \cap [2]\!:\;\left(\frac{10}{3},\,\frac{2}{3}\right)$

$\displaystyle [1] \cap [4]\!:\;\left(1,\,\frac{8}{5}\right)$

$\displaystyle [2] \cap [3]\!:\;(4,\,2)$

$\displaystyle [3] \cap [4]\!:\;(1,\,5)$

4. Originally Posted by ticbol
This is good for practice.

It will be long if I show it all, so let me assume you know how to graph inequalities and how to find the intersection of two inequalities.

I don't know how to sketch figures here so sketch it on paper.
Originally Posted by Soroban

As ticbol pointed out, the region is a quadrilateral.
But I differ on one vertex.

$\displaystyle [1] \cap [2]\!:\;\left(\frac{10}{3},\,\frac{2}{3}\right)$

$\displaystyle [1] \cap [4]\!:\;\left(1,\,\frac{8}{5}\right)$

$\displaystyle [2] \cap [3]\!:\;(4,\,2)$

$\displaystyle [3] \cap [4]\!:\;(1,\,5)$
If you want to draw graphs badly enough, the picture environment isn't too awful. Here is the quadrilateral.

$\displaystyle \setlength{\unitlength}{1cm} \begin{picture}(4,4) \qbezier(3.33,.667)(3.33,.667)(1,1.6) \qbezier(4,2)(4,2)(3.33,.667) \qbezier(4,2)(4,2)(1,5) \qbezier(1,1.6)(1,1.6)(1,5) \qbezier(0,0)(0,0)(4,0) \qbezier(0,0)(0,0)(0,5) \end{picture}$

Below is the LaTeX code. I have something like this stored in a document. I cut and pasted it here and then modified it.

The lines are drawn by qbezier. \qbezier(X,Y)(X,Y)(V,W) draws a line beteen points (X,Y) and (V,W). Note the (X,Y) is repeated. You could also repeat the (V,W) with same effect and the order of the points does not matter.

The \setlength, \begin{picture} and \end{picture} commands are just a little housekeeping that needs to be done. The (4,4) in \begin{picture} sets the size of the axes. The \setlength sets the size of the picture. If LaTeX complains about the size of the image, reduce the length.

Code:
\setlength{\unitlength}{1cm}
\begin{picture}(4,4)

\qbezier(3.33,.667)(3.33,.667)(1,1.6)
\qbezier(4,2)(4,2)(3.33,.667)
\qbezier(4,2)(4,2)(1,5)
\qbezier(1,1.6)(1,1.6)(1,5)

\qbezier(0,0)(0,0)(4,0)
\qbezier(0,0)(0,0)(0,5)

\end{picture}
The first 4 qbeziers draw the quadrilateral. I just put the coordinates in straight from Soroban's post. The second 2 qbeziers draw the axes.