Lecture Note Linear Programming (LP)
Chapter 4
Linear Programming (LP)
1 System of Linear Inequalities in Two Variables
Example 1
A manufacturer makes two grades of concrete. Each bag of the high-grade concrete
contains 10 kg of gravel and 5 kg of cement, while each bag of low-grade concrete
contains 12 kg of gravel and 3 kg of cement. There are 1,920kg of gravel and 780 kg
of cement currently available. The manufacturer can make a profit of $1.20 on each
bag of the high-grade and $1.00 on each bag of the low-grade concrete and wishes to
determine how many bags of each grade to make from the available supplies to
generate the largest possible profit. Formulate this problem in mathematical terms.
Solution
We summarize the problem by the table as follows
High-grade
(kg)Low-grade
(kg)Amount
available(kg)
Gravel 10 12 1,920
Cement 5 3 780
Profit per bag 1.20 1.00If we let H denote the number of bags of high-grade concrete produced and L denote
the number of bags of low-grade cencrete produced, we can represent the
manufacturer ‘s profit P by the linear function
PHL=1.20 +1.00
with the constraints
10 HL+≤ 12 1, 920 for gravel
5 HL+≤ 3 780 for cement
and also, number of bag must be non-negative. Hence. Therefore the
problem can be stated mathematically as follows:
HL≥≥0 and 0Maximize the profit function PHL=1.20 +1.00
Subject to the constraints
10 12 1, 920
5 3 780
,0
HL
HL
HL
+ ≤
+≤
≥
Note that in this problem, the optimum point we seek lies in the solution set of a
system of linear inequalities.
1.1 Graphing a Linear Inequality in Two Variables
When a plane is divided in half by a line, each side is called a half-plane. A vertical
line divides the plane into left and right half-planes, and any nonveritical line divides
the plane into upper and lower half-planes.
There are four different kinds of inequalities in two variables that can arise: