Vensim software work required for 3 students 3 copies
Lisa09
Week7.pdf
Dr. Daniel Xing Email: [email protected]
EBUS-504
Operations Modelling and Simulation
Lecture 7
Introduction to Linear Programming
University of Liverpool
Management School,
UK
Linear Programming
▪ Linear programming is used to solve optimization problems where all
the constraints, as well as the objective function, are linear equalities or
inequalities.
▪ Linearity is the property of a mathematical relationship (function) that
can be graphically represented as a straight line.
▪ E.g. mass and weight. W=mg
▪ Newton’s second law. F=ma
Key elements of LP
Linear programming is the method of considering different inequalities
relevant to a situation and calculating the best value that is required to be
obtained in those conditions. Some of the assumptions taken while working
with linear programming:
• The number of constraints should be expressed in the quantitative terms
• The relationship between the constraints and the objective function should be linear
• The objective function can be optimised
Components of LP:
▪ Decision variables
▪ Constraints
▪ Data
▪ Objective functions
Key characteristics
Constraints – The limitations should be expressed in the mathematical form, regarding the resource.
Objective Function – In a problem, the objective function should be specified in a quantitative way.
Linearity – The relationship between two or more variables in the function must be linear. It means that the degree of the variable is one.
Finiteness – There should be finite and infinite input and output numbers. In case, if the function has infinite factors, the optimal solution is not feasible.
Non-negativity – The variable value should be positive or zero. It should not be a negative value.
Decision Variables – The decision variable will decide the output. It gives the ultimate solution of the problem. For any problem, the first step is to identify the decision variables.
Recall our previous example
Your company is selling A and B two types of carpets. Machine 1, 2, 3 are
used for production. Particularly, production of per square meter A needs
M1 for 1 hour and M2 for 2 hours and production of per square meter B
needs M1 for 1 hour, M2 for 1 hour and M3 for 1 hour. M1 cannot be used
over 300 hours per period, M2 cannot be used over 400 hours per period
and M3 cannot be used over 250 hours per period. The market price for A
is £50/m2 and for B is £100/m2. How many A and B do you plan to
produce per period to get the best revenue?
Mathematical formulation
𝑥1: square meters of A
𝑥2: square meters of B
Objective: max 𝑥1𝑥2
50𝑥1 + 100𝑥2
s.t.
𝑥1 + 𝑥2 ≤ 300 2𝑥1 + 𝑥2 ≤ 400
𝑥2 ≤ 250 𝑥1, 𝑥2 ∈ 𝑅+
Mathematical formulation
max 𝑥1𝑥2
50𝑥1 + 100𝑥2
s.t.
𝑥1 + 𝑥2 ≤ 300 2𝑥1 + 𝑥2 ≤ 400
𝑥2 ≤ 250 𝑥1, 𝑥2 ∈ 𝑅+
1 1 2 0
1 1
𝑥1 𝑥2
≤ 300 400 250
50 100 𝑥1 𝑥2
Co-efficient
matrix Variable
vector
Column
vector
𝑥1 𝑥2
Vectors and matrix
All constraints define the search space of our system. Particularly,
Coefficient matrix: a matrix consisting of the coefficients of the variables in
a set of linear equations. The matrix is used in solving systems of linear
equations.
➢ Its dimension is always 𝑚 ∗ 𝑛.
➢ 𝑚 rows indicate 𝑚 number of constraints.
➢ 𝑛 columns indicate 𝑛 number of variables will be considered.
Decision vectors: a vector space defined by decision variables.
➢ Its dimension is always 𝑛 ∗ 1
Multiplication between matrix and vector
Matrix-vector product
A general form for LP
max 𝑧 = 𝑐𝑇𝑥
s.t. 𝐴𝑥 = 𝑏 𝑥 ≥ 0
Where
𝐴 is the coefficient matrix
𝑐 =
𝑐1 . . . 𝑐𝑛
, 𝑏 =
𝑏1 . . . 𝑏𝑛
, 𝑥 =
𝑥1 . . . 𝑥𝑛
Solve LP graphically
𝑥1 + 𝑥2 ≤ 300
𝑥1
𝑥2
300
300
2𝑥1 + 𝑥2 ≤ 400
400
200
𝑥2 ≤ 250
50𝑥1 + 100𝑥2 = 0
Corner point
Solve LP
What if your LP problem has more than 3 variables?
Use Excel to solve a LP problem
Use Solver function to solve a LP
Build your cells for obj coefficients, coefficient matrix,
column vectors and decision vectors
Use Excel to solve a LP problem
Use Solver function to solve a LP
➢ Define your objective function and constraints
Build your objective function
Build your constraint function
Use Excel to solve a LP problem
Use Solver function to solve a LP
➢ Call solver to solve the problem
The cell for your obj function
The cells for your constraint functions The cells for your column vector
Proposed exercise
1. A store wants to liquidate 200 of its shirts and 100 pairs of pants from last season. They have
decided to put together two offers, A and B. Offer A is a package of one shirt and a pair of pants
which will sell for 30. Offer B is a package of three shirts and a pair of pants, which will sell for50.
The store does not want to sell less than 20 packages of Offer A and less than 10 of Offer B.
How many packages of each do they have to sell to maximize the money generated from the
promotion?
Formulate your problem accordingly. Use both graphic and Excel solver to find the optimal
solution.
Proposed exercise
1. A factory uses a raw material whose price and availability vary seasonally. The price, availability
and factory requirement for each quarter of the next year are given in the following table.
The cost per ton of storing the material from one quarter to the next is £4 + 10% of the purchase
price. The material may also be stored for two quarters at double the above cost per ton, but will not
keep for longer than two quarters. No stock is held initially and none is required at the end. Find the
pattern of buying and storing that minimises the total cost. State any assumptions that you make.
Formulate your problem accordingly. Use Excel solver to find the optimal solution.
Quarter 1 2 3 4
Price /ton 110 100 120 130
Availability
(tons)
1000 1700 800 400
Requirement
(tons)
750 900 1000 850
Dr. Daniel Xing Email: [email protected]
EBUS-504
Operations Modelling and Simulation
Lecture 7
Introduction to Linear Programming
University of Liverpool
Management School,
UK
