Introduction LP Formulation

Dr. P. Kalpana, M.E., PhD.

Faculty of Mechanical Engineering
IIITDM Kancheepuram

1
About Myself
Education
Phd - Operations and Supply Chain Management - IIT Madras
M.E – Industrial Engineering - PSG College of Technology, Coimbatore
Industry
Oct 2016-March 2019, Deputy Manager- Manufacturing and supply chain Analytics, Ford Motor Pvt
Ltd, Chennai
Oct 2013-Sep 2016, Operations Research Consultant, Ramco Systems Ltd, Chennai
Teaching
Sep 2007 - Dec 2008, Mookambigai College of Engineering, Trichy
Research Interests
Operations Research, Supply chain Coordination, Logistics and distribution systems management,
transport Network optimization, Scheduling, Forecasting, Inventory Management, Game theory, IoT
and Block chain in SCM, Advanced data analytics, Supply chain resilience, Intelligent transportation
and logistics systems and cold supply chain management.
Projects Handled
Air craft tail allocation, Demand forecasting for Aircraft spare parts, Time table scheduling, Aircraft
hanger scheduling, workforce scheduling for a health care industry, Shuttle optimization, floor space
optimization, container load optimization etc.
Evaluation Pattern
Quiz 1 20%
Quiz2 20%
Assignment/Presentation 20%
Final Assessment 40%
Course Policies
Maintain the minimum attendance requirement to write exams (85%)
Late submission of Assignments/Term paper are not entertained

3
Operations Research (OR)
A scientific approach to complex problem solving
Decision making in engineering, management and public systems
OR techniques
Mathematical programming
Inventory management
Scheduling, Forecasting
Network analysis
Queuing models
Simulation
Origin and Development of OR
Pre world war II development
Development during world war II
Post world war II developments and computer
Inclusion of uncertainty in models

4
 Optimization Techniques
Linear Programming
it involves linear objective function and linear constraints
Integer programming
It is an extension of linear programming with only integer values for the decision variables of the problem
Distance related network techniques
transportation problem
shortest path problem
minimum spanning tree problem
travelling salesmen problem
Project management
To schedule the activities of the project (e.g. construction of the bridges) such that the total project
completion time is minimized
Inventory control
It is a technique to optimally plan and procure/produce raw materials/semi-finished products such that
the total cost of the inventory system is minimized

5
Optimization Techniques
Dynamic programming
Enumeration technique to solve a problem by integrating the solutions of its sub problems
Queuing theory
To study the waiting behaviour of some real-life queuing systems
Replacement analysis
To determine the economic life of an asset as compared to minimum total cost
Game theory
To deal with uncertainty situations related to management decisions, such as bidding for tenders
Goal programming
To convert the multiple objectives into a single goal
Simulation
To deal with probabilistic situation where empirical/mathematical models fail to provide solutions
to real life problems
Scheduling It is the process of preparing calendar for executing a set of jobs mostly in shop floors
Nonlinear programming It is extended version of linear programming problems with nonlinear
objective function and linear constraints or with nonlinear objective and nonlinear constraints which
enable analysts to incorporate realistic assumptions while solving problems 6
 Position of Optimization Techniques in analytics

Source:Gartner's analytics maturity model may be a good starting point to explain and prepare for the transition to AI. Image: Gartner
Image: Gartner
7
Important Terminologies
Objective Function
The problem what we are solving for(max or Min as function of Decision variables)
Decision Variables
Decision or output of the problem
Constraints
Conditions for resource availability or resource requirement
Limits the value of decision variable
≤, ≥, equality constraints
Constraints can be hard (must be satisfied) or soft (is desirable to satisfy).
Constraints can be explicit (stated in the problem) or implicit (obvious to the problem).

8
Important Terminologies
Search space
Range or values of decisions variables that will be searched during optimization

Solution
specifies the values of the decision variables, and therefore also the value of the objective function
A feasible solution satisfies all constraints.
An optimal solution is feasible and provides the best objective function value.
A near-optimal solution is feasible and provides a superior objective function value, but not
necessarily the best

9
Concept of Model
Identify the management/Engineering decision problem
Formulate a model for the real world problem
Identify the parameter and variables that are involved in the management//Engineering problem
Symbolic representation
Construct the model with all real world relationship into system symbolic relationship
Perform symbolic manipulation
Solving system of equations
Iterating set of steps
Making statistical analysis
Interpret the model conclusions into real world problem characteristics
Test and validate the results
Implement the results
Revise the model as and when required

10
Solution Methods for Optimization Problems

Solution
Methods

Exact methods Approximation

Methods

Simplex, Branch and Exhaustive

Calculus method Constructive
Bound Search Search Heuristic
Heuristic
Closed Loop Iterative methods Brute force method Meta Heuristics Rule of thumb
Solution

Search by repeated Search by repeated Search by repeated solution

solution construction solution modification recombination

1.Greedy randomized adaptive search 1.Simulated Annealing 1.Genetic Algorithm

procedure 2.Tabu Search 2.Scatter Search
2.Antcolony optimization 3.Threshold Accepting
4.Iterated Local Search
5.Variable Neighbor hood search
Approximation Methods

Problems Construction Phase(Heuristics) Improvement phase (meta

heuristics)

TSP&VRP Clustering Algorithm, sweep algorithm, Repeated solution Construction

nearest neighbor hood ,Cost Saving GRASP, ACO
heuristics etc. Solution Modification
SA, TA, TS, ILS, VNS,
Solution Recombination
Scheduling SPT, LPT, EDD, Johnson’s Rule
GA, SS

Transportation Least cost method, Stepping Stone method Needs Initial solution

Assignment Hungarian Algorithm

Inventory Optimization Wagner Whitin, Silver Meal Heuristics, NA

Basnet and Leung Method

12
Why approximate solutions
Heuristics are problem-dependent techniques
Meta-heuristics are problem-independent techniques
Suitable for all combinatorial optimization problems
Provide Quality solutions to difficult optimization problems in a reasonable amount of time
There is no guarantee that optimal solutions can be reached
Suitable for global optimization
Termination Criteria for Meta heuristic Search
After a fixed number of iterations (or a fixed amount of CPU time);
After some number of iterations without an improvement in the objective function value (the
criterion used in most implementations);
When the objective reaches a pre-specified threshold value

13
Applications
Defence Applications
Network technique for the shortest path problems,
Scheduling algorithm for vehicle routing
Allocation techniques for shipping food grains and ammunition
Industrial applications
Production
Linear programming for aggregate planning
Integer programming for shop floor production scheduling
Network based techniques for line balancing and project management
Inventory control techniques for planning and procuring raw materials
Queuing theory for designing in-process buffer stock
Marketing
Linear programming product mix problem
Game theory for order bidding decision
Distance network related techniques for shipping finished goods.
14
Applications
Personal
Linear programing for manpower planning
Queuing theory for determining the size of maintenance crews
Scheduling techniques for manpower scheduling
Finance
Integer programming for capital budgeting
Linear programming for break - even analysis
Integer programming or dynamic programming for portfolio selection
Application in public system
government offices
goal programming for policy decisions
Integer programming for budgeting
Postal systems
vehicle scheduling
manpower planning
15
Applications
Banks
queuing theory for determining the number of counters
portfolio models for effective deployment of the funds subject to government regulations
Managing highways
the technique of integer programming for the project selection and vendor selection
simulation for traffic system design
railways
linear programming/ integer programming for cargo loading
scheduling techniques for railways traffic control
Queuing theory to determine the number of platforms
Airways
simulating the air traffic, runway design,
linear/integer programming for cargo loading
Hanger Planning
Tail allocation
16
Applications
Hospitals
Queuing theory for out-patient system design
Linear programming/ integer programming for scheduling the duties of nurses and doctors
Inventory control for procurement of medicines
Algorithms and models for managing the operation theatre
Education
Integer programming for Scheduling exams
Integer programming for Scheduling classes
Sports
Integer programming for Scheduling different events

17
Linear Programming Formulation
It is a mathematical programming technique to optimize performance (profit, cost) under set of
constraints (man, machine, money, material)as specified by organization
The problem written in algebraic form is called mathematical modelling
It consists of
Decision variables
Objective function
Constraints
Non negativity restrictions
Problem Formulation
Identifying decision variables
Writing objective function
Writing constraints
Writing non negativity restriction

Linear objective function, Linear constraints and non negativity restriction

Decision variables - Unrestricted in sign
18
Generalized form of LP

19
Assumptions in linear programming problem
Linearity

Additivity

Proportionality

Divisibility & Multiplicity

Deterministic

Non negativity

20
1.Product mix problem
Consider a small manufacturer making two products A and B. Two resources R1 and R2
are required to make these products. Each unit of A required 1 unit of R1 and 3 units of
R2. Each unit of B required 1 unit of R1 and 2 units of R2. The manufacturer has 5 units
of R1 and 12 units of R2 available. The manufacturer also makes a profit of Rs 6 per unit
of product A and Rs 5 per unit of product B sold. Formulate a linear programming model
to determine the production volume of the each of the product such that the total profit is
maximized?
22
2. A diet planning problem

A nutrition scheme for babies is proposed by a committee of doctors, Babies can be

given two types of food ( I and II ) which are available in standard sized packets
weighing 50 grams. The cost per packet of these foods are Rs 2 and Rs 3
respectively. The vitamin availability in each type of food per packet and the min
vitamin requirement for each type of vitamin are summarized in table. Develop a
linear programming model to determine the optimum combination of food types with
min cost such that the min requirement of vitamin in each type is satisfied.

Vitamin variability/packet
Min daily
Vitamin
required vitamin
Food type I Food type II
1 1 1 6
2 7 1 14
Cost/
2 3
pocket(Rs)

23
3. Man power planning problem
In multispecialty hospital, nurses report to duty at the end of every 4 hours as given in
table. Each nurse after reporting will work for 8 hours continuously. The min number of
nurses required during various periods are summarized in table. Develop a mathematical
to determine the number of nurses to report at the beginning of each period such that the
total number of nurses who have to report in a day is minimized
Time period
Interval Min. No of
Number From To required Nurses

1 12 mid night 4 am 20
2 4 am 8 am 25
3 8 am 12 noon 35
4 12 noon 4 pm 32
5 4 pm 8 pm 22
6 8 pm 12 mid night 15
Problem 4
A textile company can use any or all of the three different process for weaving its
standard white polyester fabric. Each of these production process has a weaving machine
setup cost and per square meter processing cost. These cost and the capacities of each of
three production process are shown in table. The daily demand forecast for its white
polyester fabric is 4000 sq. Meter. The company's production manager wants to make
decision concerning which combination of production process is to be utilized to meet the
daily demand forecast and at what production level of each selected production process to
be operated to minimize the total production cost, develop a linear programming model to
asset the production manager

Weaving Machine Processing Cost/ Max. Daily capacity

Process Number
setup cost (Rs) sq.m (Rs) (sq.m)

1 150 15 2000

2 240 10 3000

3 300 8 3500
5. Cargo loading problem
Consider the cargo loading problem, where five items are to be loaded on a vessel. The
weight (Wi) and volume (Vi) of each unit of the weight of the different items as well as
their corresponding returns per unit (ri) are tabulated. The maximum cargo weight and
volume are given as 112 and 109 respectively. It is required to determine the optimal
cargo load in discrete units of each item such that the total return is maximized.
Formulate the LP
Item (i) Wi Vi ri

1 5 1 4

2 8 8 7

3 3 6 6

4 2 5 5

5 7 4 4
Problem 6
A computer company produces cabinets from three different suppliers (A, B, C) located three
different cities. The company has production plants( P,Q,R) in three other cities. The cost of
transportation per cabinet for different combinations of suppliers and production plant are
summarized in table. The purchase price per cabinet from different suppliers are also indicated in
the same table. The weekly demand at different production plant and the weekly availability of
cabinets at different suppliers are also given in table. Formulate the LP model to find the optimal
procurement plan for the cabinets such that total cost is minimized.
Price/
Suppliers Plant P Plant Q Plant R Supply
Cabinet

A 10 15 8 300 85

B 20 21 15 500 90

C 12 16 13 100 75

Demand 100 200 300

33
7.Production planning problem
Let us consider a company making a single product. The estimated demand for the
product for the next four months are 1000, 800, 1200, 900 respectively. The company
has a regular time capacity of 800 per month and an overtime capacity of 200 per month.
The cost of the regular time production Rs. 20 per unit and cost of the overtime
production is Rs 25 per unit. The company can carry inventory to the next month and the
holding cost is Rs 3 per unit per month. The demand has to be meet every month.
Formulate a LPP for the above situation.
35
36
8. Cutting stock problem
Consider a big steel from which steel sheets of the same length but different width have
to be cut. Let us assume that the roll is 20m wide and the following sizes have to
9 inch 511 numbers
8 inch 301 numbers
7 inch 263 numbers
6 inch 383 numbers
38
39
Problem 9
Consider two manufacturers ( A and B) who are competitors for the same market
segment for the product. Each wants to minimize the market share and adopts two
strategies. The gain (or) pay off for A adopts strategy i and B adopt strategy j is given by
aij
Player 2
3 -2
Player 1
-1 4
41
42