LINEAR PROGRAMMING

Linear programming (LP, also called linear optimization) is a metho

(such as maximum profit or lowest cost) in a mathematical model who

Linear programming helps in attaining the optimum use of productive

can employ his productive factors effectively by selecting and distributing (a
the quality of decisions.

Constrained optimization models have three major components:

(1) decision variables, (2) objective function, and (3
Decision Variables
The variables in a linear program are a set of quantities that need to
i.e., the problem is solved when the best values of the variabl
A decision variable is a quantity that the decision-maker controls. Fo
the number of nurses to employ during the morning shift in an
Other examples are the number of tables to produce, the num
These decision variables are represented by any variable like x, y, a, b

Objective Function
The objective function in a mathematical optimization problem is the re
is to be either minimized or maximized over the set of feasible alternatives. I

The objective function is a mathematical equation that describes the

maximization of profits with respect to production. ... In other words, it's a fo

let: x be the purse

y be the wallet
Z = 5.75x + 3.25y

Example 1:A self-employed carpenter earns $90 for the sale of a table an
for him to make a table and 5 hours to manufacture a rocking chair. He
The average manufacturing cost is $15 per table and $45 per rocking chair. He
at $ 315 per week. How many tables and rocking chairs should he mak
Determine the maximum profit he make per week.

let: T be the number of table

R be the number of rocking chair
S be the sales

S = 90T + 180R

Constraints
 The linear inequalities or equations or restrictions on the variables of
The conditions x ≥ 0, y ≥ 0 are called non-negative restrictions
A linear constraint is a mathematical expression where linear terms (
are added or subtracted and the resulting expression is forced
or exactly equal to a right-hand side value.
The constraints are the restrictions or limitations on the decision variab
Some examples of constraints are time, budget, resources av

In example 1, constraints are time and manufacturing cost to produce t

2T + 5R < 40

15T + 45R < 315

The feasible region in a linear program is the set of all possible feas
An optimal solution to a linear program is the feasible solution with the
In mathematical optimization, a feasible region, feasible set, search s
points (sets of values of the choice variables) of an optimization proble
potentially including inequalities, equalities, and integer constraints.

If the feasible region is empty, then there is no maximum or minimum

 no points that satisfy all of the constraints. If there are no points that sa
to have a maximum or minimum value.  If a feasible region is empty (c
inconsistent and the problem has no solution.

Slack variables are defined to transform an inequality expression into

The slack variable is defined by setting a lower bound of zero (>0)
The term "slack" applies to less than or equal constraints, and the term
The slack value is the amount of the resource, as represented by the l
When a greater-than-or-equal constraint is not binding, then the surplu
that is being produced or utilized.
 imization) is a method to achieve the best outcome
thematical model whose requirements are represented by linear relationships.

mum use of productive resources. It also indicates how a decision-maker

ting and distributing (allocating) these resources. Linear programming techniques improve

ajor components:
ctive function, and (3) constraints.
uantities that need to be determined in order to solve the problem;
t values of the variables have been identified.
on-maker controls. For example, in an optimization model for labor scheduling,
he morning shift in an emergency room may be a decision variable.
s to produce, the number of vaccines to manufacture, the amount of money to invest,
variable like x, y, a, b, etc.

ation problem is the real-valued function whose value 

f feasible alternatives. In problem P above, the function f is the objective function.

on that describes the production output target that corresponds to the

In other words, it's a formula businesses use to achieve profitability and production goals.

(minimization example)

the sale of a table and $180 for the sale of a rocking chair. It takes 2 hours
re a rocking chair. He is limited to working 40 hours per week.
45 per rocking chair. He wishes to keep his manufacturing costs
 chairs should he make to maximize his weekly sales?

(maximization example)

s on the variables of a linear programming problem are called constraints.

n-negative restrictions.
n where linear terms (i.e., a coefficient multiplied by a decision variable)
g expression is forced to be greater-than-or-equal, less-than-or-equal,

on the decision variables. They usually limit the value of the decision variables.
budget, resources availability, etc.

uring cost to produce table and rocking chair.

(for time constraint)

T, R > 0 non-negativity constraint

(for cost constraint)

 et of all possible feasible solutions.
sible solution with the largest objective function value (for a maximization problem).
feasible set, search space, or solution space is the set of all possible
an optimization problem that satisfy the problem's constraints,
nteger constraints.

maximum or minimum values. An empty region results when there are

e are no points that satisfy the constraints, there can be no points
ble region is empty (contains no points), then the constraints are

uality expression into an equality expression with an added slack variable.

er bound of zero (>0).
nstraints, and the term "surplus" applies to greater than or equal constraints.
s represented by the less-than-or-equal constraint, that is not being used.
nding, then the surplus is the extra amount over the constraint
onships.

niques improve
heduling,

money to invest, etc.

oduction goals.
straints.

ariables.
on problem).
traints.
 A self-employed carpenter earns $90 for the sale of a table and $180
Example 1:
for him to make a table and 5 hours to manufacture a rocking chair. He is limit
The average manufacturing cost is $15 per table and $45 per rocking chair. He wishes
at $ 315 per week. How many tables and rocking chairs should he make to ma
Determine the maximum profit he make per week.
T R Objective Function:
Sales $90 $180 S = 90T + 180R
Time 2hrs 5hrs
Cost $15 $45 Subject to Constraints: 2T + 5R < 40
2T + 5R < 40 2T + 5(0) = 40
15T + 45R < 315 T = 20
T, R > 0 (20,0)

R 2(0) + 5R = 40
R=8
(0, 8)

2T + 5R = 40
15T + 45R = 315

2T + 5R = 40
2(15) + 5R = 40
5R = 40-30
(0,8) 2T + 5R < 40 R=2
8
15T + 45R < 315
(0,7)

(0,0)

Objective Function:
S = 90T + 180R
Corner Pts T R Sales
(0,0) 0 0 0 Subject to Constraints:
(0,7) 0 7 1260 2T + 5R < 40 time-constraint
(15,2) 15 2 1710 15T + 45R < 315 cost-costraint
(20,0) 20 0 1800 T, R > 0 non-neg

P = S-C
P = 1800 - 315
P = $1485
a table and $180 for the sale of a rocking chair. It takes 2 hours
chair. He is limited to working 40 hours per week.
g chair. He wishes to keep his manufacturing costs
d he make to maximize his weekly sales?

x - intercept/ t - intercept
2T + 5R < 40 15T + 45R < 315
2T + 5(0) = 40 15T + 45(0) = 315
T = 21
(21,0)
y - intercept/ r - intercept
2(0) + 5R = 40 15(0) + 45R = 315
R=7
(0,7)

by elimination of variables
2T + 5R = 40 18T + 45R = 360
-
15T + 45R = 315 15T + 45R = 315
3T =45
2T + 5R = 40 T=15
2(15) + 5R = 40
5R = 40-30 (15,2)

C (T,R) = (15,2)

(20,0) (21,0)

20 T
 A company receives in sales $20 per book and $18 per calculato
Example 2:
calculator are $5 and $4 respectively. The monthly (30 day) cost must no
equipment used by the company takes 5 minutes to produce a book and 15 minu
and calculators should the company make to maximize profit? Determine

Objective Function:

Subject to Constraints:
$18 per calculator. The cost per unit to manufacture each book and
ay) cost must not exceed $27,000 per month. If the manufactuting
book and 15 minutes to produce a calculator, how many books
rofit? Determine the maximum profit the company earns in a 30 day period.
Simplex Method
Maximize P = 5x + 4y
Subject to: 3x + 5y < 78 3x + 5y + S1 = 78
4x + y < 36 4x + y + S2 = 36
non-negativity constraints x, y > 0 -5x - 4y + P = 0

x y S1 S2 P

Eliminate all the negative values x y S1 S2 P

at the bottom row 3 5 1 0 0
4 1 0 1 0
Choose the column (key column) of -5 -4 0 0 1
most negative value at the bottom row
"4" is the key element, convert it to 1 by dividing all the elements
in the key row by 4

x y S1 S2 P
3 5 1 0 0
1 1/4 0 1/4 0
-5 -4 0 0 1

Convert all other elements (except for key element) in the key column
to zero to make the variable as basic variable
New R1 = Old R1 - 3R2
New R3 = Old R3 + 5 R2

x y S1 S2 P
0 17/4 1 -3/4 0
1 1/4 0 1/4 0
Choose the column (key column) of 0 -11/4 0 5/4 1
most negative value at the bottom row

"17/4" is the key element, convert it to 1 by multiplying all the elemen

in the key row by 4/17

x y S1 S2 P
0 1 4/17 -3/17 0
1 1/4 0 1/4 0
0 -11/4 0 5/4 1

Convert all other elements (except for key element) in the key column
to zero to make the variable as basic variable

New R2 = Old R2 - 1/4 R1

New R3 = Old R3 + 11/4 R1
 x y S1 S2 P
0 1 4/17 -3/17 0
1 0 -1/17 20/51 0
0 0 11/17 52/51 1
Stop the process since no more negative value is present at the bottom row.

THEREFORE, x=6 S1 = 0
y = 12 S2 = 0
P = 78

P = 5x + 4y
3x + 5y < 78 3x + 5y + S1 = 78
4x + y < 36 4x + y + S2 = 36
x, y > 0 -5x - 4y + P = 0
 C

C
78 (78/3 = 26) take the row of the
36 (36/4 = 9) lower value as the key row
0

ividing all the elements

78
9
0

element) in the key column

51 51/(17/4) = 12 take the row of the

9 9/(1/4 = 36 lower value as the key row
45

by multiplying all the elements

12
9
45

element) in the key column

 12
6
78
sent at the bottom row.
Maximize P = 3x + 4y + z
Subject to: 3x + 10y + 5z < 120 3x + 10y + 5z + S1 = 120
5x + 2y + 8z < 6 5x + 2y + 8z + S2 = 6
8x + 10y + 3z < 105 8x + 10y + 3z + S3 = 105
non-negativity constraints x, y, z > 0 -3x -4y - z + P = 0

x y z S1
3 10 5 1
5 2 8 0
8 10 3 0
-3 -4 -1 0

x y z S1
3 10 5 1
5/2 1 4 0
8 10 3 0
-3 -4 -1 0

NewR1 = OldR1 - 10R2

NewR3 = OldR3 - 10R2
NewR4 = OldR4 + 4R2

x y z S1
-22 0 -35 1
5/2 1 4 0
-17 0 -37 0
7 0 15 0

x=0 S1 = 90
y=3 S2 = 0
z=0 S3 = 75
P =12

P = 3x + 4y + z
30 < 120 3x + 10y + 5z < 120 3x + 10y + 5z + S1 = 120
6=6 5x + 2y + 8z < 6 5x + 2y + 8z + S2 = 6
30 < 105 8x + 10y + 3z < 105 8x + 10y + 3z + S3 = 105
x, y, z > 0 -3x -4y - z + P = 0
S2 S3 P
0 0 0 120 120/10 12
1 0 0 6 6/2 3
0 1 0 105 105/10 10.5
0 0 1 0

S2 S3 P
0 0 0 120
1/2 0 0 3
0 1 0 105
0 0 1 0

S2 S3 P
-5 0 0 90
1/2 0 0 3
-5 1 0 75
2 0 1 12
Minimize C = x + y + 3z
Subject to: 2x + y + 3z > 6
x + 2y + 4z > 8
3x + y - 2z > 4
non-negativity constraints x, y, z > 0

x y z Constant
2 1 3 6
1 2 4 8
3 1 -2 4
1 1 3

Maximize P = 6u + 8v + 4w

2u + v +3w < 1 2u + v +3w + x = 1

u + 2v + w < 1 u + 2v + w + y = 1
3u + 4v - 2w < 3 3u + 4v - 2w + z = 3
-6u - 8v -4w + P = 0

u v w x
2 1 3 1
1 2 1 0
3 4 -2 0
-6 -8 -4 0

u v w x
2 1 3 1
1/2 1 1/2 0
3 4 -2 0
-6 -8 -4 0

NewR1 = OldR1 - R2
NewR3 = OldR3 -4R2
NewR4 = OldR4 + 8R2

u v w x
1 1/2 0 2 1/2 1
1/2 1 1/2 0
1 0 -4 0
-2 0 0 0

u v w x
 1 0 1 2/3 2/3
1/2 1 1/2 0
1 0 -4 0
-2 0 0 0

NewR2 = OldR2 - 1/2R1

NewR3 = OldR3 - R1
NewR4 = OldR4 + 2R1

u v w x
1 0 1 2/3 2/3
0 1 - 1/3 - 1/3
0 0 -5 2/3 - 2/3
0 0 3 1/3 1 1/3

w = 10/3
x = 4/3
y = 10/3
C14/3
 Maximize P = 6u + 8v + 4w
u v w Constant
2 1 3 1 2u + v +3w < 1
transpose to => 1 2 1 1 u + 2v + w < 1
3 4 -2 3 3u + 4v - 2w < 3
6 8 4

y z P Constant
0 0 0 1 1/1 1
1 0 0 1 1/2 0.5
0 1 0 3 3/4 0.75
0 0 1 0

y z P Constant
0 0 0 1
1/2 0 0 1/2
0 1 0 3
0 0 1 0

y z P Constant
- 1/2 0 0 1/2 1/2
1/2 0 0 1/2 1
-2 1 0 1 1
4 0 1 4

y z P Constant
 - 1/3 0 0 1/3
1/2 0 0 1/2
-2 1 0 1
4 0 1 4

y z P Constant
- 1/3 0 0 1/3
2/3 0 0 1/3
-1 2/3 1 0 2/3
3 1/3 0 1 4 2/3

u, v , z, P = 0