|
-
Linear programming problems are related to distribution of resources which are limited in the best way possible so as to minimise costs or maximise profits
-
A linear programming model can be formulated by following the steps given below:
|
|
|
|
Formulating a mathematical model for a situation based on the given constraints and presenting it graphically
|
- A mathematical model consisting of constraints or objective functions can be obtained from the situation or problem given
-
The model can be formulated by using the variables \(x \text{ and } y\) with the constraints in each situation being \(\leqslant, \ \geqslant, \ \text{< or >} \)
-
Given a straight line \(ax+by=c\), then,
|
|
Region above the straight line |
Region below the straight line |
|
|
|
|
Satisfies the inequalities
\(ax+by \geqslant c \text{ and } ax+by \text{ > }c\)
|
|
|
|
|
|
|
|
|
|
Satisfies the inequalities
\(ax+by \leqslant c \text{ and } ax+by \text{ < }c\)
where \(b \text{ > }0\)
|
|
|
|
|
|
|
|
|
|
Region on the right side of line |
Region on the left side of line |
|
|
|
|
Satisfies the inequalities
\(ax \geqslant c \text{ and } ax \text{ > }c\)
|
|
|
|
|
|
|
|
|
|
Satisfies the inequalities
\(ax \leqslant c \text{ and } ax \text{ < }c\)
|
|
|
|
|
|
|
|
|
|
|
|
1. |
\(\geqslant \text{ or } \leqslant\), then a solid line is used |
|
|
2. |
\(\text{< or >}\), then a dotted line is used |
|
|
|
|
|
|
|
Example |
|
|
|
|
(a) |
Write a mathematical model for the following situation:
The perimeter of the rectangular photo frame must not be more than \(180 \text{ cm}\).
|
|
|
(b) |
Present the inequalities \(x-2y \geqslant -4\) graphically. |
|
|
|
|
Solution: |
|
|
(a) |
Supposed \(x \text{ and } y\) are the width and length of the rectangular photo frame.
Then, \(2x+2y \text{ < }180\).
|
|
|
(b) |
Given \(x-2y \geqslant -4\).
Since \(b=-2 \ (\text{< }0)\).
Hence, the region lies below the line
\(x-2y=-4\).
|
|
|
|
|
|
|
|
|
|
|
|
Optimisation in linear programming
- Note that \(ax +by\) is a linear expression
- In general, an objective function is written as
|
|
Remark |
|
|
|
|
Steps to determine the suitable value of \(k\) for
\(k=ax+by\):
|
|
|
|
|
|
-
Note that \(a\text{ and }b\) are coefficients of \(x\text{ and }y\) respectively
-
Find the common multiples of \(a\text{ and }b\)
-
Take \(k\) as the common multiple
|
|
|
|
|
|
|
|
|
Example:
|
|
Example |
|
|
|
|
The diagram above shows the shaded region that satisfies a few constraints of a situation.
Given \(k = x+2y\), find
|
|
|
|
|
(a) |
the maximum value of \(k\),
|
|
|
(b) |
the minimum value of \(k\). |
|
|
|
|
Solution: |
|
|
(a) |
Substitute the maximum point for the shaded region, which is \((15,55)\) into \(k = x+2y\).
\(\begin{aligned} k&=15+2(55)\\ &=125 \end{aligned}\)
Therefore, the maximum value of \(k\) is \(125\).
|
|
|
(b) |
Substitute the minimum point for the shaded region, which is \((15,8)\) into \(k = x+2y\).
\(\begin{aligned} k&=15+2(8)\\ &=31 \end{aligned}\)
Therefore, the minimum value of \(k\) is \(31\)
|
|
|
|
|
|
|
|
|