ECE 594 OPERATIONS RESEARCH
)
๐น 1.1 What is Operations Research?
Operations Research (OR) is the science of decision-making. It uses mathematical models, statistics, and algorithms to help organizations make better decisions and solve complex problems.
โค Key Definition:
Operations Research is the application of scientific and analytical methods to aid in decision-making and problem-solving.
๐น 1.2 Characteristics of Operations Research
Decision-oriented
Focuses on finding the best possible decision among alternatives.
Scientific approach
Uses mathematics, modeling, and analysis.
Interdisciplinary
Combines knowledge from engineering, economics, statistics, and management.
System-oriented
Considers the entire system and its interactions.
Iterative
Often requires refinement and simulation.
๐น 1.3 Scope of Operations Research
OR is used in various industries and functions, including:
๐ญ Industrial Engineering
Optimizing production schedules
Inventory control
Equipment maintenance planning
๐ข Business and Management
Human resource allocation
Marketing and advertisement strategy
Investment and finance modeling
๐ฐ๏ธ Telecommunications & Networks
Bandwidth allocation
Routing and switching
Load balancing
๐ Logistics and Supply Chain
Transportation routing
Warehouse location planning
Fleet management
๐ฅ Healthcare
Scheduling surgeries
Managing hospital resources
๐น 1.4 Phases of an OR Study (Problem-Solving Cycle)
1. Problem Definition
Understand and define the real-world problem.
2. Model Construction
Build a mathematical model (equations, inequalities, graphs).
3. Model Solution
Use techniques like Simplex, Simulation, or Dynamic Programming.
4. Model Validation
Compare model outputs to real-world data. Adjust if needed.
5. Implementation
Apply the optimized solution to the real-world system.
6. Monitoring & Feedback
Monitor results and improve based on feedback.
๐น 1.5 Types of OR Models
Descriptive
Describes how a system works.
Predictive
Forecasts future outcomes based on data.
Prescriptive
Suggests optimal actions to achieve goals.
Deterministic
All input data is known with certainty.
Stochastic
Some input data is uncertain or probabilistic.
๐น 1.6 Example Problem (Real-World)
Problem: A telecom company wants to minimize the cost of installing cell towers while ensuring 100% signal coverage of a city.
OR Solution Approach:
Define variables: tower locations, costs, coverage zones.
Build a mathematical model (e.g., set covering problem).
Use an optimization algorithm to minimize cost.
Simulate the result to verify coverage.
๐น 1.7 Benefits of Operations Research
โ Data-driven decision-making โ Improved efficiency and productivity โ Reduced costs โ Optimized resource usage โ Better forecasting and planning โ Objective evaluation of options
๐น 1.8 Limitations of Operations Research
โ ๏ธ Heavily reliant on accurate data โ ๏ธ Complex mathematical modeling โ ๏ธ May be costly/time-consuming โ ๏ธ Sometimes results are sensitive to assumptions โ ๏ธ Real-world resistance to model implementation
๐ MODULE 2: Linear Programming (LP)
Linear Programming (LP) is a foundational topic in Operations Research used to find the optimal solution (maximum or minimum) for a linear objective function, subject to linear constraints.
๐น 2.1 What is Linear Programming?
โค Definition:
Linear Programming is a mathematical technique for optimizing (maximizing or minimizing) a linear objective function, subject to a set of linear equality or inequality constraints.
๐น 2.2 Components of an LP Problem
Decision Variables
What you are solving for (e.g., how many products to produce).
Objective Function
A function to maximize or minimize (e.g., profit or cost).
Constraints
Limitations or restrictions (e.g., labor hours, materials).
Non-negativity
Decision variables must be โฅ 0 (can't produce a negative quantity).
โ
Example:
A factory produces x chairs and y tables. Each chair takes 2 hours, and each table takes 3 hours. The factory has 100 hours available. Each chair earns $30 profit, each table earns $50.
Maximize profit.
Formulation:
Objective: Maximize
Z = 30x + 50y
Subject to:
2x + 3y โค 100
(time constraint)x โฅ 0
,y โฅ 0
(non-negativity)
๐น 2.3 Graphical Solution (for 2 variables)
โค Steps:
Convert inequalities to equations.
Plot the lines on the XY plane.
Determine the feasible region (satisfies all constraints).
Find the corner (extreme) points of the region.
Substitute corner points into the objective function.
Choose the point with the optimal value.
๐ฏ Example:
Same problem:
Z = 30x + 50y
Constraint:
2x + 3y โค 100
Intercepts: If
x = 0
,y = 33.3
; Ify = 0
,x = 50
โ Feasible region is below the line 2x + 3y = 100
in the first quadrant.
โ Test points: (0,0)
, (50,0)
, (0,33.3)
๐น 2.4 Algebraic Solution (for more than 2 variables)
Use the Simplex Method (covered in detail in Module 2.5) to solve LP problems involving 3 or more variables, since graphical method becomes impractical.
๐น 2.5 Standard Form of LP
To use algebraic methods, the LP problem must be in standard form:
Objective: Maximize
Z = cโxโ + cโxโ + ... + cโxโ
Subject to:
cssCopyEditaโโxโ + aโโxโ + ... + aโโxโ โค bโ aโโxโ + aโโxโ + ... + aโโxโ โค bโ ... xโ, xโ, ..., xโ โฅ 0
๐น 2.6 Types of Constraints
Less-than
โค
2x + 3y โค 100
Greater-than
โฅ
4x + y โฅ 40
Equality
=
x + y = 50
Slack/surplus variables are added to convert these into equalities for algebraic methods.
๐น 2.7 Applications of LP in Engineering
Optimizing production processes
Power generation/load distribution
Telecommunications bandwidth allocation
Resource allocation in embedded systems
Transportation and logistics planning
๐ MODULE 3: Transportation and Assignment Models
Transportation and assignment problems are special types of Linear Programming Problems (LPPs) used in logistics, production, and resource allocation to minimize cost or maximize efficiency.
๐น 3.1 The Transportation Problem
โค Objective:
To determine the least-cost shipping schedule from multiple sources (e.g., factories) to multiple destinations (e.g., warehouses), while satisfying supply and demand constraints.
โ
Standard Assumptions:
m sources and n destinations
Supply at each source and demand at each destination is known
Cost per unit of transport from each source to each destination is known
๐น Formulation
Let:
xijx_{ij}xijโ: units transported from source iii to destination jjj
cijc_{ij}cijโ: cost per unit from iii to jjj
aia_iaiโ: supply at source iii
bjb_jbjโ: demand at destination jjj
Objective Function:
Minimize Z=โi=1mโj=1ncijxij\text{Minimize } Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij}Minimize Z=i=1โmโj=1โnโcijโxijโ
Subject to:
Supply constraints: โj=1nxij=ai\sum_{j=1}^{n} x_{ij} = a_iโj=1nโxijโ=aiโ
Demand constraints: โi=1mxij=bj\sum_{i=1}^{m} x_{ij} = b_jโi=1mโxijโ=bjโ
xijโฅ0x_{ij} \geq 0xijโโฅ0
๐น Types of Transportation Problems
Balanced
Total supply = total demand
Unbalanced
Supply โ demand โ Add dummy source/destination
Maximization
Convert to minimization by subtracting costs from a large number
๐น Solution Methods
1. Finding an Initial Feasible Solution
North-West Corner Method (NWCM)
Least Cost Method (LCM)
Vogelโs Approximation Method (VAM) โ Best for closer optimality
2. Finding Optimal Solution
MODI Method (Modified Distribution Method)
Stepping Stone Method
๐ฏ Example:
S1
2
3
1
30
S2
5
4
8
40
S3
5
6
8
30
Demand
20
50
30
โ Balanced (supply = demand = 100) โ Use VAM to find initial solution โ Apply MODI for optimality check
๐น 3.2 The Assignment Problem
โค Objective:
Assign n workers to n jobs (or machines to tasks, students to projects, etc.) such that the total cost is minimized or efficiency is maximized.
๐น Formulation
Let:
xij=1x_{ij} = 1xijโ=1 if worker iii is assigned to job jjj, otherwise 0
cijc_{ij}cijโ: cost (or time) for worker iii on job jjj
Objective Function:
Subject to:
Each worker gets exactly one job: โj=1nxij=1\sum_{j=1}^{n} x_{ij} = 1โj=1nโxijโ=1
Each job is assigned to exactly one worker: โi=1nxij=1\sum_{i=1}^{n} x_{ij} = 1โi=1nโxijโ=1
xijโ{0,1}x_{ij} \in \{0, 1\}xijโโ{0,1}
๐น Solution Method: Hungarian Algorithm
Step-by-step:
Row reduction โ subtract min value in each row.
Column reduction โ subtract min value in each column.
Cover all zeros using a minimum number of lines.
If the number of lines = n, optimal solution exists.
If not, adjust uncovered values and repeat.
๐ฏ Example Cost Matrix:
W1
10
12
19
W2
8
20
15
W3
15
13
10
โ Apply Hungarian Method to assign jobs to workers with minimum cost.
๐น Variations
Unbalanced
Add dummy rows/columns with zero cost
Maximization
Convert to minimization by subtracting all values from the highest entry
Multiple assignments
Use generalized assignment model
Last updated