2/5/2025
Chapter 2
LINEAR PROGRAMMING
Instructor: Assoc. Prof. Dr. PHAN THỊ MAI HÀ
TABLE OF CONTENTS
1. Introduction about Linear Programming
2. The Linear Programming Model
3. Assumptions of Linear Programming
4. Formulating and Solving LP Models on a
Spreadsheet
1
2/5/2025
INTRODUCTION
❖ Many decisions in management are related with the best
usage resources of organizations.
❖ Manager makes Decisions to satisfy Objectives, Goals of
organizations.
❖ Resources: Materials, Machines, Man, Money, Time,
Space → limit
❖ Linear Programming (LP) is a mathematical method that
helps managers to make decision related with Resources
Allocation.
❖ Extensively using computer.
INTRODUCTION – LP PROBLEM
❖ Problem: Maximize or Minimize some variables, usually
Profit/ Cost, called Objective function.
❖ Constraints: are functions show resources limitation of
companies/ organizations. The problem is to find
solution that maximize profits (or minimize lost/cost) in
given constraints.
❖ Form of constraint functions could be:
❖ Inequality (form ≤ or ≥)
❖ Equality ( = )
❖ All Objective function and Constraint functions are linear
functions.
2
2/5/2025
PROTOTYPE EXAMPLE – Wyndor Glass Co.
Wyndor Glass Co.
❖ Glass products: windows and glass doors.
❖ Plant 1: Aluminum frames and hardware: Product 1
❖ Plant 2: Wood frame: Product 2
❖ Plant 3: The glass and assembles the products: Product 1 & 2.
❖ Product 1: An 8-foot glass door with aluminum framing
❖ Product 2: A 4x6 foot double-hung wood-framed window
❖ Problem: Determine what the production rates should be for
the two products in order to maximize their total profit
The production rate = The number of batches of
the products to be produced / week
5
PROTOTYPE EXAMPLE – Wyndor Glass Co.
3
2/5/2025
PROTOTYPE EXAMPLE – Formulation
▪ x1 = number of batches of product 1 produced per week
▪ x2 = number of batches of product 2 produced per week
▪ Z = total profit per week (in thousands of dollars) from
producing these two products
▪ The objective function is
Maximize profit Z = 3x1 + 5x2
Subject to the restrictions:
3x1 + 2x2 18
2x2 12 Linear Programming
Problem
x1 4
x1 0 → resource-allocation
x2 0. problem
7
PROTOTYPE EXAMPLE – Graphical Solution
▪ Two decision variables → two dimensions → x1 and x2 as
the axes → Values of (x1, x2) by the restrictions
4
2/5/2025
PROTOTYPE EXAMPLE – Graphical Solution
▪ pick out the point in this feasible region that maximizes the
value of Z = 3x1 + 5x2 by trial and error
Max Profit: Z=3*2+5*6=36
LINEAR PROGRAMMING MODEL
❖ The general problem of allocating resources to activities.
▪ Z = value of overall measure of performance →
Objective function (OF)
▪ xj = level of activity j (for j = 1, 2, . . . , n) → decision
variable (DV)
▪ cj = increase in Z that would result from each unit
increase in level of activity j.
▪ bi = amount of resource i that is available for
allocation to activities (for i = 1, 2, . . . , m).
▪ aij = amount of resource i consumed by each unit of
activity j.
→ parameters
10
10
5
2/5/2025
LINEAR PROGRAMMING MODEL
11
11
LINEAR PROGRAMMING MODEL
12
12
6
2/5/2025
LINEAR PROGRAMMING MODEL
13
13
LINEAR PROGRAMMING MODEL
❖ The legitimate forms:
14
14
7
2/5/2025
LINEAR PROGRAMMING MODEL
❖ Terminology for Solutions of the Model:
▪ A feasible solution is a solution for which all the
constraints are satisfied.
▪ An infeasible solution is a solution for which at least
one constraint is violated.
▪ feasible region
▪ optimal solution: most favorable value of objective
function (maximized or minimized)
15
15
LINEAR PROGRAMMING MODEL
16
16
8
2/5/2025
LINEAR PROGRAMMING MODEL
Multiple
optimal
solutions
17
17
LINEAR PROGRAMMING MODEL
Unbounded Objective
→ No optimal solutions
18
18
9
2/5/2025
LINEAR PROGRAMMING MODEL
A corner-point feasible
(CPF) solution
19
19
ASSUMPTIONS OF LINEAR PROGRAMMING
❖ Proportionality assumption:
▪ Objective function Z – proportional to xj,
▪ left-hand side of each functional constraint –
proportional to xj
20
20
10
2/5/2025
ASSUMPTIONS OF LINEAR PROGRAMMING
❖ Proportionality assumption:
21
21
ASSUMPTIONS OF LINEAR PROGRAMMING
❖ Proportionality assumption:
22
22
11
2/5/2025
ASSUMPTIONS OF LINEAR PROGRAMMING
❖ Additivity assumption:
▪ Every function in a linear programming model (OF or or
the function on the left-hand side of constraint) is the
sum of the individual contributions of the respective
activities.
Z0 = 3x1 + 5x2 Z1 = 3x1+5x2+x1x2 ; Z2 =3x1+5x2 - x1x2
23
23
ASSUMPTIONS OF LINEAR PROGRAMMING
❖ Additivity assumption:
Z0 = 3x1 + 5x2 Z1 = 3x1+5x2+x1x2 ; Z2 =3x1+5x2 - x1x2
24
24
12
2/5/2025
ASSUMPTIONS OF LINEAR PROGRAMMING
❖ Additivity assumption:
3x1 + 2x2 ≤ 18 3x1+5x2+ 0.5x1x2 ; 3x1+ 2x2–0.1x1x2
25
25
ASSUMPTIONS OF LINEAR PROGRAMMING
❖ Divisibility assumption:
▪ Decision variables in a linear programming model are
allowed to have any values, including noninteger
values, that satisfy the functional and nonnegativity
constraints.
❖ Certainty assumption:
▪ The value assigned to each parameter of a linear
programming model is assumed to be a known
constant
26
26
13
2/5/2025
ADDITIONAL EXAMPLES
Design of Radiation Therapy
27
27
ADDITIONAL EXAMPLES
Design of Radiation Therapy
28
28
14
2/5/2025
ADDITIONAL EXAMPLES
Controlling Air Pollution: cost-benefit–tradeoff problem
29
29
ADDITIONAL EXAMPLES
Controlling Air Pollution cost-benefit–tradeoff problem
30
30
15
2/5/2025
ADDITIONAL EXAMPLES
Controlling Air Pollution: cost-benefit–tradeoff problem
31
31
ADDITIONAL EXAMPLES
Distributing Goods through a Distribution Network
32
32
16
2/5/2025
ADDITIONAL EXAMPLES
Distributing Goods through a Distribution Network
33
33
FORMULATING & SOLVING LP MODELS ON A
SPREADSHEET
34
34
17
2/5/2025
FORMULATING & SOLVING LP MODELS ON A
SPREADSHEET
35
35
FORMULATING & SOLVING LP MODELS ON A
SPREADSHEET
36
36
18
2/5/2025
FORMULATING & SOLVING LP MODELS ON A
SPREADSHEET
37
37
FORMULATING & SOLVING LP MODELS ON A
SPREADSHEET
38
38
19
2/5/2025
FORMULATING & SOLVING LP MODELS ON A
SPREADSHEET
39
39
20
