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

Characteristic
Description

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)

Phase
Description

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

Model Type
Description

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

Component
Description

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:

  1. Convert inequalities to equations.

  2. Plot the lines on the XY plane.

  3. Determine the feasible region (satisfies all constraints).

  4. Find the corner (extreme) points of the region.

  5. Substitute corner points into the objective function.

  6. Choose the point with the optimal value.

🎯 Example:

Same problem:

  • Z = 30x + 50y

  • Constraint: 2x + 3y ≤ 100

  • Intercepts: If x = 0, y = 33.3; If y = 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

Constraint Type
Symbol
Example

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

Type
Description

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:

D1
D2
D3
Supply

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:

MinimizeZ=∑i=1n∑j=1ncijxijMinimize Z=∑i=1n∑j=1ncijxijMinimizeZ=i=1∑n​j=1∑n​cij​xij​Minimize Z=∑i=1n∑j=1ncijxij\text{Minimize } Z = \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{ij}Minimize Z=i=1∑n​j=1∑n​cij​xij​

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:

  1. Row reduction – subtract min value in each row.

  2. Column reduction – subtract min value in each column.

  3. Cover all zeros using a minimum number of lines.

  4. If the number of lines = n, optimal solution exists.

  5. If not, adjust uncovered values and repeat.

🎯 Example Cost Matrix:

Job A
Job B
Job C

W1

10

12

19

W2

8

20

15

W3

15

13

10

→ Apply Hungarian Method to assign jobs to workers with minimum cost.

🔹 Variations

Type
Description

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

PreviousSerial CommunicationNext✅ Why do we need Linear Programming?

Last updated