CIS-341 OPERATIONS

RESEARCH
By
Dr. Abdul Basit

1
2
3
 CHAPTER 3
Introduction to Linear Programming

4
Definition of Linear Programming
■ Linear Programming (LP) is a versatile technique for
assigning a fixed amount of resources among
competing factors, in such a way that some objective
is optimized and other defined conditions are also
satisfied
■ LP is a mathematical technique for determining the
optimal allocation of resources and obtaining a
particular objective when there are alternative uses
of the resources. The objective may be cost
minimization or inversely profit maximization.

5
Linear programming
■ Linear programming has been successfully applied to a
variety of problems of management, such as
production, advertising, transportation, refinery
operation, investment analysis, etc.
■ Over the years, linear programming has been found
useful not only in business and industry but also in non-
profit organizations such as government, hospitals,
libraries, education, etc.
■ Actually, linear programming improves the quality of
decisions by amplifying the analytic abilities of a
decision maker.
6
Terminology
■ Linear Function
– A linear function contains terms each of which is
composed of only a single, continuous variable
raised to (and only to) the power of 1.
■ Objective Function
– It is a linear function of the decision variables
expressing the objective of the decision-maker. The
most typical forms of objective functions are:
maximize f(x) or minimize f(x).
■ Decision Variables
– physical quantities whose numerical values indicate
the solution
7
Terminology
■ Constraints
– These are linear equations arising out of practical limitations. e.g.
f(x) ≥ b or f(x) ≤ b or f(x) = b
■ Nonnegativity Restrictions
– In most practical problems the variables are required to be
nonnegative; xj ≥ 0, for j = 1.....n
■ Feasible Solution
– Any non-negative solution which satisfies all the constraints is known as
a feasible solution. The region comprising all feasible solutions is
referred to as feasible region.
■ Optimal Solution
– Is when objective function is maximized or minimized.

8
Example 1
■ A manufacturer produces two different products, say
chairs and tables, using three machines M1; M2
and M3. Each machine can be used for only a
limited period of time. Production time for each
product on each machine is given as Production
time (hrs/unit) Machine Chair Table Available time
The objective is to maximize M1 1 1 9
M2 1 3 19
the combined time of utilization M3 2 1 14
of all three machines. Total 4 hr 5hr

9
LP Mathematical Model
■ Let x1 and x2 denote the number of chairs and tables.
■ Constraints:
– x1 + x2 ≤ 9;
– x1 + 3x2 ≤ 19;
– 2x1 + x2 ≤ 14;
– where x1 ≥ 0; x2 ≥ 0:
■ Objective: maximizing the combined production time of
three machines, that is 4x1 + 5x2

10
Standards LP Form
■ Maximize z = 4x1 + 5x2
■ subject to
■ x1 + x2 ≤ 9
x1 + 3x2 ≤ 19
2x1 + x2 ≤ 14
x1 ≥ 0, x2 ≥ 0

11
Example 2
■ Universal Corporation manufactures two products- P1 and P2.
The profit per unit of the two products is Rs. 30 and Rs. 50
respectively. Both the products require processing in three
machines. The following table indicates the available
machine hours per week and the time required on each
machine for one unit of P1 and P2. Formulate this product mix
problem in the linear programming form.
Machine Product P1 Product P2 Available time
hours / week
1 1 0 4
2 0 2 12
3 3 2 18
Profit Rs. 30 Rs. 50
12
LP Model
■ Let x1 and x2 be the amounts manufactured of products P1 and P2
respectively.
■ The objective here is to maximize the profit, which is given by the linear
function
– Maximize z = 30x1 + 50x2
■ Since one unit of product P1 requires two hours of processing in machine 1,
while the corresponding requirement of P2 is one hour, the first constraint
can be expressed as
x1 + 0x2 ≤ 4
■ Similarly, constraints corresponding to machine 2 and machine 3 are
0x1 + 2x2 ≤ 12
3x1 + 2x2 ≤ 18
■ In addition, there cannot be any negative production that may be stated
algebraically as x1 ≥ 0, x2 ≥ 0

13
Standards LP Form
■ Maximize z = 30x1 + 50x2
■ subject to
■ x1 ≤4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1 ≥ 0, x2 ≥ 0

14
Example 3
■ Assume that there are two products, cereal and milk, for
breakfast and assume that a person must consume at
least 60 units of iron and at least 70 units of protein to
stay alive. Assume that
■ one unit of cereal costs $20 and contains 30 units of
iron and 5 units of protein and
■ one unit of milk costs $10 and contains 17 units of iron
and 9 units of protein. The goal is to find the cheapest
diet which will satisfy the minimum daily requirement.

15
LP Model
■ Let x1 represents the number of units of cereal that the
person consumes a day and
■ x2 represents the number of units of milk consumed.
■ For the diet to meet the minimum requirements, we
must have
■ Iron Requirement : 30x1 + 17x2 ≥ 60;
■ Protein Requirement : 5x1 + 9x2 ≥ 70;
– where x1 ≥ 0; x2 ≥ 0
■ The cost of the diet is: 20x1 + 10x2

16
Example 4
■ A person requires 8; 15; 16 units of chemicals A;B;C;
respectively, for his garden. The liquid product
contains 4; 5; 3 units of A;B;C; respectively per jar.
The dry product contains 3; 5; 6 units of A;B;C
respectively per packet. The person wants to spend
a minimum possible amount on his garden, where it
is given that the liquid product is available for $40
per jar and the dry product is available for $25 per
packet.

17
LP Model
■ Suppose that person purchases x1 jars and x2
packets of the products.
■ Constraints:
– 4x1 + 3x2 ≥ 8; 5x1 + 5x2 ≥ 15; 3x1 + 6x2 ≥ 16;
where x1 ≥ 0; x2 ≥ 0:
■ Objective: Minimizing cost, that is 40x1 + 25x2:

18
Graphical Solution
■ Find feasible region by drawing all the constraints
■ Find the value of objective function on all corners of
the feasible region
■ Choose the optimal value which will be the desired
solution

19
Assignment 1 due date: 7/10/19
 Book Problems at the end of Chapter 3
 Page # 81-83
 Problem Number
1) 3.1-5 6) 3.2-1
2) 3.1-6 7) 3.2-5
3) 3.1-7(c) 8) 3.2-6
4) 3.1-8 9) 3.4-4
5) 3.1-9 10)3.4-7

20
Multiple Optimal Solutions
■ Maximize z = x1 + 2x2
■ subject to
■ x1 ≤ 80
x2 ≤ 60
5x1 + 6x2 ≤ 600
x1 + 2x2 ≤ 160
■ x1, x2 ≥ 0.

21
Infeasible Problem
■ In some cases, there is no feasible solution area, i.e., there
are no points that satisfy all constraints of the problem. An
infeasible LP problem with two decision variables can be
identified through its graph.
■ Minimize z = 200x1 + 300x2
■ subject to
■ 2x1 + 3 x2 ≥ 1200
x1 + x2 ≤ 400
2x1 + 1.5x2 ≥ 900

■ x1, x2 ≥ 0

22
Unbounded Solution
■ It is a solution whose objective function is infinite. If the
feasible region is unbounded then one or more decision
variables will increase indefinitely without violating feasibility,
and the value of the objective function can be made arbitrarily
large.
■ Maximize z = 40x1 + 60x2 Although it is possible to construct
linear programming problem with
■ subject to
unbounded solutions numerically,
■ 2x1 + x2 ≥ 70 but no LPP formulated from a real
x1 + x2 ≥ 40 life situation can have unbounded
x1 + 3x2 ≥ 90
solution
■ x1, x2 ≥ 0

23
Ingredients Mixing Problem
Fauji Foundation produces a cereal SUNFLOWER, which they
advertise as meeting the minimum daily requirements for
vitamins A and D. The mixing department of the company uses
three main ingredients in making the cereal-wheat, oats, and rice,
all three of which contain amounts of vitamin A and D. Given that
each box of cereal must contain minimum amounts of vitamin A
and D, the company has instructed the mixing department
determine how many ounces of each ingredient should go into
each box of cereal in order to minimize total cost.
Vitamin Wheat Oats Rice Milligrams
(mg./oz.) (mg./oz.) (mg./oz.) Required/Box
A 10 20 8 100
D 7 14 12 70
The cost of one ounce of wheat is Rs. 0.4, the cost of an ounce of oats is
Rs. 0.6, and the cost of one ounce of rice is Rs. 0.2. 24
Standard LP form
■ Let X1, X2 and X3 are ounces of wheat, oats and
rice respectively

■ Minimize Z = Rs. 0.4 X1 + 0.6 X2 + 0.2 X3

25
Transportation Problem
■ The Philips Company produces and ships LED TV from three
warehouses to three retail stores on a monthly basis. Each warehouse
has a fixed demand per month. The manufacturer wants to know the
number of LED sets to ship from each warehouse to each store in
order to minimize the total cost of transportation.
■ Each warehouse has the following supply of LED available for
shipment each month
■ Warehouse Supply(sets)
1. Karachi 300
2. Lahore 100
3. Islamabad 200
Total 600
26
Transportation Problem cont.
■ Each retail store has the following monthly
demand for television sets: Warehouse Supply(sets)
■ Store Demand(sets) 1. Karachi 300
A. Faisalabad 150 2. Lahore 100
B. Peshawar 250 3. Islamabad 200
C. Hyderabad 200 Total 600
Total 600
■ The costs for transporting LED sets from
each warehouse to each retail store are
different as a result of different modes of
transportation and distances. The shipping
costs per LED set for each route are,

27
Mathematical Model
■ The model for this problem consists of nine decision
variables representing the number of LED sets transported
from each of the three warehouses to each of the three
stores
■ Xij = the No. of LED sets shipped from warehouse "i" to
store "j" where i = 1, 2, 3 and j = A, B, C.
■ Decision variable X3A means Islamabad to store A in
Faisalabad
■ Minimize Z = Rs. 6X1A + 8X1B + 1X1C + 4X2A + 2X2B +
3X2C + 3X3A + 5X3B + 7X3C
■ The constraints in this model are available LED sets at
each warehouse and the number of sets demanded at
each store.
28
Mathematical Model
■ X1A + X1B + X1C = 300
This constrain is an equality (=) for two reasons. First, more than 300 LED sets
cannot be shipped, because that is cannot be shipped, because all 300 are
needed at the three stores, the three warehouses must supply all that can be
supplied. Thus, since the total shipped from warehouse 1 cannot exceed 300 or
be less than 300 the constraint is equality. Similarly, the other two supply
constraints for warehouse 2 and 3 are also equalities.
■ X2A + X2B +X2C = 100
■ X3A + X3B + X3C = 200
The three demand constraints are developed in the same way except that
television sets can be supplied from any of the three warehouses. Thus, the
amount shipped to one store is the sum of the shipments from the three
warehouses:
■ X1A + X2A + X3A = 150
■ X1B + X2B + X3B = 250
■ X1C + X2C + X3C = 200 29
Generalized LP Model
■ Page 33

30
Quiz 1
■ Minimize Z = 40x1 + 50x2,
subject to

(a) Use the graphical method to solve this model.