CHAPTER ONE

Introduction to Operations Research

OR – Quantitative approach to decision making

- Decision-making is complex in today's environment due to uncertainty and competition
- Personal experiences, guesswork, and intuition are not enough for decision-making
- Operations Research offers a quantitative method of evaluating every possible alternative
- Management decision-making involves both quantitative and qualitative perspectives
- Information from both perspectives needs to be assessed in the context of the problem
- Evaluating each alternative is difficult due to the amount and complexity of information and the
large number of alternatives
- Decision-makers use quantitative methods and computers to arrive at optimal solutions
- Operations Research is the study of these methods and how decision-makers use them in the
decision process.
1.2. History of Operations Research
- Operations Research started during World War II to manage scarce resources
- A group of specialists in mathematics, economics, statistics, engineering, and sciences were
formed to deal with military problems
- After the war, scientists applied OR to civilian problems in business, industry, and research
- OR became popular due to the economic and industrial boom after the war
- Advancements in OR techniques were made, such as linear programming, statistical quality
control, and queuing theory
- High-speed computers made it possible to apply OR techniques for practical decision analysis
- OR is useful in balancing conflicting objectives and finding the optimal solution for the
organization as a whole.
1.3. Nature and Significance Operations Research
- Operations Research helps balance conflicting objectives in decision-making
- It finds the best solution for the organization as a whole, not just one department
- OR analyzes inter-relationships among system components to find the global optimum
- The optimal solution may not be acceptable to one department but benefits the organization as a
whole.
 Operation Research: Some definitions
 Operations Research uses math and scientific methods to solve problems related to systems
and operations.
 It helps decision-makers find the best solution while considering limited resources and
conflicting objectives.
 OR involves a collection of techniques and tools that are applied to solve practical problems
in economics and engineering.
 The goal of OR is to provide managers with optimum solutions for their operations.
 OR uses mathematical modeling to analyze decision problems and find the best course of
action.
CHARACTERISTICS OF OPERATION RESEARCH
- examines how different parts of a company interact with each other.
- uses an interdisciplinary approach, bringing together different fields of study to solve problems
- Solving MS/OR problems can uncover new problems that need to be addressed.
- MS/OR uses a modeling process approach to problem-solving, where both managers and MS
experts work together to find the best solution.
Qualitative Approach to Decision Making
 The qualitative analysis is based on primarily upon the manager's judgment and experience.
 The type of analysis includes the manager's intuitive "feel" for the problem and is more of an art
than a science.
 If the manager has had experience with similar problems, or if the problem is relatively simple,
heavy emphasis may be placed up on qualitative analysis.
 However, if the manager has had little experience with similar problems, or if the problem is
sufficiently important and complex, then quantitative analysis of the problem can be a very
important consideration in the managers’ final decision.
 It is considered when the decision maker doesn’t have data about the problem.
 The skills in qualitative approach to problem solving are inherent in the decision maker.
 It is used when the problem under consideration doesn't involve too many variables or it is not
complex, it is not new or familiar, when the cost of the decision is not heavy and when
immediate action is required.
 Quantitative Approach to Problem Solving
 In this approach, an analyst will concentrate on the quantitative factors or data associated with
the problem and develops mathematical expressions that describe the objectives, constraints and
relationships that exist in the problem.
 It is supported by the available data.
 It uses mathematical models.
 The skills in quantitative approach is acquired by studying the mathematical tools or OR
techniques.
 It is used under the following situations
 When the problem involves too many variables
 When the problem is new (not familiar)
 When the decision is very important involving a great amount of money
 When the problem is repetitive (unique)
 This approach is believed to reduce time and effort to make decisions.
OPERATIONS RESEARCH TECHNIQUES
1. Linear Programming Method
It is primarily concerned with optimum allocation of scarce resources subject to certain limitation. It
uses simplex procedure to solve product mix in portfolio analysis and transportation algorithm.
2. Decision Analysis (Theory)
It is concerned with making decision under conditions of risk and uncertainty. Decision theory
represents a generalized approach to decision making which often serves as the basis for a wide range of
managerial decision making. The decision model includes a list of courses of action that are available
and the possible consequences of each course of action. An important factor in making decision is the
degree of certainty associated with the consequences. This can range anywhere from complete certainty
to complete uncertainty, and it generally affects the way a decision is reached.
3. Network Analysis
It is considered under risk and uncertainty situation, and involves determination of an optimum sequence
of performing certain activities in a project - this is to minimize the overall cost (time).
Networks are important tools of management science. Not only can networks are used to models a wide
variety of problems they can often be solved more easily than other models of the same problem, and
they present models in a visual format.
The techniques in network analysis includes PERT, CPM, and Gant Chart.
4. Inventory Model
It is a model which operates to optimize inventory levels. The main emphasis is minimizing,
carrying, ordering and being out of stock costs.
5. Queuing Model (Waiting Line Model)
It determines the average time spent in line waiting for service.
6. Markov Analysis
It is used to determine the purchasing behavior of customers-brand loyalty of customers- given
that the behavior of customers is known.
Significance of Operation Research
 It provides a tool for scientific analysis and provides solution for various business
problems.
 It enables proper deployment and optimum allocation of scarce resources.
 It helps in minimizing waiting and servicing costs.
 It enables the management to decide when to buy and how much to buy through the
technique of inventory planning.
 It helps in evaluating situations involving uncertainty.
 It enables experimentation with models, thus eliminating the cost of making errors while
experimenting with reality.
 It allows quick and inexpensive examination of large numbers of alternatives.
 In general OR facilitates and improves the decision making process.

Areas of Application
 Inventory control
 Facility design (distribution decision)
 Product mix determination
 Portfolio analysis
 Allocation of scarce resources
 Investment decisions (constructing new plant, expanding programs, sub-contracting and
the like)
  Project management.

Chapter two
INTRODUCTION TO LINEAR PROGRAMMING

Linear programming models are mathematical representations of linear programming problems.

- They have certain characteristics in common, which can be grouped into two categories:
components and assumptions.
- The components of LP models include the objective function, decision variables, constraints,
parameters, and right-hand side values.
- The objective function is the mathematical expression of the objective of the model, which can
be either maximization or minimization.
- The decision variables represent unknown quantities to be solved for by the decision maker.
- The constraints are mathematical relationships that limit the resources available for the
problem.
- Parameters are numerical values that specify the impact of each decision variable on the
objective and constraints.
- Right-hand side values indicate the availability of resources.
- Understanding the components of LP models is essential for correctly formulating an LP
model.

Formulation of Linear Programming Model

The characteristics can be grouped into two categories: Components and assumptions. The
components relate to the structure of a model, whereas the assumptions describe the conditions
under which the model is valid.
Components Assumptions
1. Objective function 1. Linearity
2. Decision variables 2. Divisibility
3. Constraints 3. Certainty
4. Parameters and Right. 4. Non-negativity
Hand Side Values
 Components of LP Models
 Objective Function: It's the goal of the model, like making money or minimizing costs.
 Decision Variables: These are things we don't know yet, like how many of each product
to make to get the most profit.
 Constraints: These are limits on resources, like how much raw material is available.
 Parameters: These are fixed values that tell us how much each decision affects the goal
and the limits.
 Right Hand Side Values: These show how much of each resource is available.

Assumptions of the Linear Programming Models

 Proportionality or Linearity: Assumes that the contribution to the goal (like profit) from each unit
of a product is consistent, and that increasing the number of units increases the contribution
proportionally.
 Additively: Assumes that the total goal is the sum of the contributions from each activity, and that
there is no interaction between different activities.
 Continuity/Divisibility: Assumes that decision variables can take fractional values, allowing for
combinations of activities with partial quantities.
 Certainty: Assumes that all parameters, such as profit per unit and resource requirements, are
known with certainty.
 Finite Choices (Non-negativity): Assumes that there are limited choices available and that decision
variables cannot have negative values.

FORMULATING LP MODELS
Formulating linear programming models involves the following steps:
1. Problem definition
2. Represent unknown quantities
3. Determine the objective function
4. Identify the constraints
- System constraints:- more than one
- Individual constraints
- Non-negativity constraints

LINEAR PROGRAMMING APPLICATIONS

- Product Mix: Using resources like labor, equipment, and materials to decide how much of
each product to make for maximum profit.
- Diet Problems: Mixing raw materials or ingredients to create a product that meets specific
dietary needs at the lowest cost.
- Blending Problems: Similar to diet problems, with an additional requirement to achieve a
specific consistency in the mix.
- Portfolio Selection: Allocating a fixed amount of money among different investments to
maximize income or total return, while meeting specific investment requirements.

Important Definitions
- Solution: The values of decision variables that satisfy the constraints of a linear programming
(LP) problem.
- Feasible Solution: The values of decision variables that satisfy all constraints and non-
negativity conditions of an LP problem at the same time.
- Infeasible Solution: The values of decision variables that do not satisfy all constraints and non-
negativity conditions of an LP problem at the same time.
- Basic Solution: A solution obtained by setting some variables to zero and solving for the
remaining variables in a set of simultaneous equations.
- Basic Feasible Solution: A feasible solution to an LP problem that is also a basic solution,
where all basic variables have non-negative values. It can be degenerate (if at least one basic
variable is zero) or non-degenerate (if all basic variables are non-zero and positive).
- Optimal Basic Feasible Solution: A basic feasible solution that optimizes the objective
function value of the given LP problem.
- Unbounded Solution: A solution where the value of the objective function of the LP problem
can increase or decrease indefinitely.
GRAPHICAL SOLUTIONS
- Graphical linear programming is used to find the best solution for problems with two decision
options.
- It helps in understanding important concepts of models and solutions.
- The optimal solution is where the constraint lines intersect, meaning all resources are used or
met.
- Constraints without slack are called binding constraints and limit the solution.
- Unused capacity can be useful for planning, such as scheduling activities or considering
expansion.
- Slack variables can represent any difference between the left and right sides of a constraint, and
are added to make the constraints equalities.
- Slack variables do not contribute to the objective, so they are assigned a coefficient of zero in
the objective function.

LINEAR PROGRAMMING: THE SIMPLEX METHOD

- Simplex method is a step-by-step process to find the best solution. It starts with a solution that
works but isn't the best. It keeps improving the solution until it can't get any better. It uses
algebra to make the solution better. It's based on solving several equations at the same time.
Linear Programming uses an objective function and linear equations.

SOME SPECIAL ISSUES IN SIMPLEX ALGORITHM

 Unbounded Solutions
- Occurs when the objective function can be improved without limit.
- Recognized in a simplex solution by the absence of positive ratios in the quantity and
pivot/key columns.
- Arises due to incorrectly formulated constraints or objective function.
 Degeneracy
- Happens when there is a tie for the lowest non-negative ratio when identifying the leaving
variable in the simplex tableau.
- Can lead to cycling in subsequent solutions.
 - Resolved by selecting one row (variable) arbitrarily and continuing computations.

 Multiple Optimal Solutions

- Some linear programming problems have multiple optimal solutions.
- Occurs when the objective function is parallel to a binding constraint.
- Detected in the final tableau by a zero in the column of a non-basic variable, indicating the
existence of an alternate solution.
 Infeasibility
- Happens when no combination of decisions and slack/surplus variables can satisfy all the
requirements at the same time.
- Can occur due to a mistake in setting up the problem or because the constraints are too strict.
- In the simplex method, infeasibility can be detected when an artificial variable is present in a
solution that seems to be the best.

Table 5-1 Summary of Use of Slack, Surplus, and Artificial Variables

Type of Constraint To put into Standard Form
 Add a slack variable
= Add an artificial variable
 Subtract a surplus variable and
add an artificial variable

POST-OPTIMALITY OR SENSITIVITY OR WHAT IF ANALYSIS

Sensitivity analysis, also called post-optimality analysis, goes beyond finding the best solution in
linear programming.
It starts with the final table of numbers used in the problem-solving process.
It helps understand how changes in the problem's parameters, like constraint coefficients or
objective function coefficients, would impact the solution.
This analysis is useful for decision-makers as it provides insights into how different factors can
affect the optimal solution.

A Change in the RHS of A Constraint

The same general rule always applies when computing the upper and lower limits on the range of
feasibility for a maximization problem:
For a minimization problem, the rules are reversed: The allowable decrease is the negative ratio
closest to zero and the allowable increase is the smallest positive ratio.

A Change in an Objective Function Coefficient

Managers need to know how much a decision variable's contribution to the objective function
can change without affecting the optimal solution.
Changes can happen due to cost, pricing, product design, or other factors.
Two Cases to Consider:
 Non-Basic Variable:
- The range over which its objective function coefficient can change without entering the
solution mix is called its range of insignificance.
 Basic Variable:
The range over which its objective function coefficient can change without affecting optimal
values is called its range of optimality.
Note: It will change the optimal value of the objective function.
Maximization Problem:
If a variable is not in the solution, its coefficient must increase beyond a critical value (C-Z
value) in the final tableau to become a basic variable in the optimal solution.
SUMMARY
- Linear programming models find the best solutions for problems with specific rules.
- These models use decision variables, objective functions, and constraints to solve problems.
- They are commonly used for product mix, blending, distribution, and other planning problems.
- Graphical techniques can be used for two-variable problems, but they have limitations.
- The simplex algorithm is a more general method for solving linear programming problems.
- It involves creating a series of tables to find the best solution progressively.
- While manual development of solutions provides insight, computer programs are often used for
larger problems.
- Converting constraints to standard form allows for manual solving using the simplex method.
- The issue of infeasibility and how to recognize it in a table format is also discussed.
 CHAPTER 3
Transportation Problem

FORMULATING THE MODEL

A transportation problem typically involves a set of sending locations, which are referred to as origins,
and a set of receiving locations, which are referred to as destinations. In order to develop a model of a
transportation problem, it is necessary to have the following information:
a. Supply quantity (capacity) of each origin.
b. Demand quantity of each destination.
c. Unit transportation cost for each origin-destination route.
Assumptions
The transportation algorithm requires the assumption that:
• All goods be homogeneous, so that any origin is capable of supplying any destination, and
• Transportation costs are a direct linear function of the quantity shipped over any route.
• Though it will be modified later in our discussion, we shall add one additional requirement that the
total quantity available is equal to the total demand.

FINDING AND INITIAL FEASIBLE SOLUTION

A feasible solution ensures that all supply and demand requirements are met.
Number of occupied cells should be one less than the sum of rows and columns in the transportation
table.
Northwest-Corner Method:
 It's a simple approach to find an initial feasible solution.
 The starting point is the upper left-hand corner of the transportation table.
Principles:
 Allocate as many units as possible to the first cell, considering the smaller value of row
supply and column demand.
 Continue allocating units in the row or column until supply or demand is exhausted.
Drawbacks:
 Simple approach to find an initial feasible solution.
  Doesn't consider transportation costs, so the allocation may not be optimal.
Intuitive Approach (Minimum-Cost Method):
- Selects routes based on lowest cell cost.
- Allocates quantity to the cell with the lowest cost, considering supply and demand.
- Continues allocating based on lowest cost until all supply and demand are exhausted.
- Results in a lower total cost compared to the Northwest-Corner method.
Vogel’s Approximation Method (VAM):
- Based on penalty cost or regret concept.
- Prefers the allocation with the lowest cost penalty.
- Results in an initial feasible solution that is either optimal or very close to the optimal.
- Preferred over other methods due to its effectiveness in obtaining optimal or near-optimal
solutions.
Evaluating a Solution for Optimality
Involves assessing empty cells to see if a better solution is possible
Two methods for cell evaluation:
- Stepping-stone method
- MODI method
 Stepping-stone Method:
Traces closed paths in the transportation table for each empty cell.
Represents shifting one unit into an empty cell to understand the impact on total cost
Determines cost change per unit shifted and potential cost savings.
Helps identify maximum number of units that can be shifted into the empty cell and modifications
needed for other cells.
 MODI method
The MODI method evaluates a transportation solution for optimality using index numbers based on unit
costs of occupied cells.
Index numbers for rows and columns help to assess empty cells without using stepping-stone paths.
It provides a quicker way to compute improvement indices for each unused cell, saving time compared
to the stepping-stone method.
MODI helps find the unused route with the largest negative improvement index, requiring tracing only
one closed path to determine the maximum units that can be shipped via the best unused route.
 CHAPTER FOUR
ASSIGNMENT PROBLEMS

The Assignment Problem (A.P) is a special case of the Transportation Problem (T.P) where the
number of origins is equal to the number of destinations (m=n).
Assignments are made on a one-to-one basis, meaning the number of jobs equals the number of
machines or persons.
Each person or machine is loaded with one and only one job, and they can handle any of the jobs
being presented.
Loading criteria must be specified, such as minimizing operating time, maximizing profit, or
minimizing production cost.
The objective is to assign the given job to the most appropriate machine or person to optimize
the objective, like minimizing cost.

Cost Vector (Cij):

Cost vector (Cij) is the cost of assigning the ith job to the jth machine.

Assignment Vector (Xij):

Xij = 0 if the ith job is not assigned by the jth machine, or Xij = 1 if the ith job is assigned to the
jth machine.

Cost Matrix (Cij):

- The assignment problem is represented in the form of an (n*n) matrix called a cost matrix,
where Cij represents the cost of assigning the ith job to the jth machine.

Remark:
 The Assignment Problem is a variation of the Transportation Problem with a square cost matrix
and only one assignment per row or column.
 Adding or subtracting a constant from each element in a row or column doesn't affect the optimal
solution.
 HUNGARIAN ASSIGNEMNT METHOD (HAM)

The Hungarian Assignment Method (HAM) is an efficient way to solve assignment problems.

Steps for the Hungarian Assignment Method:

- Step 1: Reduce each row by subtracting the smallest element from all elements in that row.
- Step 2: Reduce each column by subtracting the smallest element from all elements in that
column.
- Step 3: Draw lines to cover all zeros. If the number of lines equals the number of
rows/columns, the solution is optimal. Otherwise, proceed to step 4.
- Step 4: Adjust costs and repeat steps 3 and 4 until an optimal solution is obtained.
- Step 6: Make job assignments based on the zero elements and determine the total cost with
reference to the original cost table.

Special Issues
When we solve assignment problems, there are cases which are treated differently from the usual
way.
Unbalanced Assignment Problems:
When the number of workers and machines is not equal, it's called an unbalanced problem.
In unbalanced situations, we add dummy rows or columns with zeros as the cost elements to
make the problem balanced.
Excess machines or workers may remain idle in unbalanced problems.

Constrained/Prohibited Assignment Problems:

In some cases, a worker cannot perform a certain job or is not allowed to be assigned a
particular job.
To handle this, the cost of performing that job by the person is set to a very large value
(denoted as M).
Then the assignment problem is solved as usual, and the person-job combinations with
prohibitive costs are not included in the final solution.
 UNIT FIVE
DECISION THEORY/ANALYSIS

Decision Theory Characteristics

 List of Alternatives: Set of mutually exclusive and collectively exhaustive decisions available to the
decision maker.
 States of Nature: Possible future conditions or events beyond the decision maker's control that
determine the consequences of the decision.
 Payoffs: Profits, revenues, costs, or other measures of value associated with each alternative and state
of nature combination.
 Degree of Certainty: The level of certainty or uncertainty regarding the likelihood of different states
of nature.
 Decision Criteria: The decision maker's attitudes and preferences, such as maximizing expected
payoffs.
Payoff Table
A summary device used to organize information about alternatives, states of nature, and associated
payoffs. It may also include probabilities for the states of nature if available.

Decision Making Situations under Certainty

Decision making under complete certainty where the decision maker focuses on selecting the
alternative with the best payoff for the known state of nature

Decision Making Under Complete Uncertainty (Without Probabilities):

In this situation, the decision maker is unable to estimate the probabilities of future events or lacks
confidence in available estimates.
The decision maker is uncertain about which future event, known as the state of nature, will occur and
has no control over them.
 Decision Criteria:
 Maximax: Selecting the decision that will result in the maximum of the maximum payoffs,
assuming the most favorable state of nature for each decision alternative.
 Maximin: Identifying the worst (minimum) payoff for each alternative and selecting the
alternative with the best (maximum) of the worst payoffs, a conservative approach.
 Minimax Regret: Considers all payoffs and aims to minimize the potential regret of not choosing
a different alternative. It uses more information than Maximin or Maximax.

Principle of Insufficient Reason/Equal Likelihood/Laplace:

This principle assumes that all possible outcomes are equally likely and focuses on the average payoff
for each option to make a decision.
It aims to incorporate more information by treating the states of nature as if they have an equal chance
of occurring.

Hurwitz Criterion:
- Strikes a balance between extreme optimism and extreme pessimism in decision making.
- Uses a coefficient of optimism (α) to weigh decision payoffs, where α is between 0 and 1.
- The maximum payoff is multiplied by α, and the minimum payoff is multiplied by 1-α for each
alternative.
- A limitation is that α is determined subjectively by the decision maker, making it a completely
subjective criterion.

Decision Making Under Risk (With Probabilities):

- In this situation, the decision maker has some information about the likelihood of different outcomes
and can assign probabilities to them.
- The term "risk" is used when there are probabilities for the occurrence of different outcomes, which
can be based on subjective estimates or historical frequencies.
Expected Opportunity Loss (EOL)
- Uses a table of opportunity loss weighted by probabilities to find the best choice.
- Equivalent to minimizing opportunity losses when maximizing payoffs.

Expected Value of Perfect Information (EVPI)

- Measures the benefit of knowing the certain state of nature.
- EVPI is equal to EOL, indicating expected opportunity loss due to imperfect information.
Decision Trees
- Visual portrayal of decision alternatives and their possible consequences.
- Composed of squares (decision points) and circles (chance events).
- Used for sequential decisions, not commonly for single decisions.
In summary, EOL and EVPI provide valuable insights into decision making under risk, while decision
trees offer a visual representation of decision alternatives and their consequences, particularly in the
context of sequential decisions.
 CHAPTER SIX
Networks and Project Management
A project is a series of activities with a specific goal and a clear start and end.
Network analysis breaks down a project into its activities and presents them in a diagram.
Networks are management tools that visually solve problems, like allocating resources and
managing time and costs.
Planning and Scheduling with Gantt chart
- Gantt charts help plan and schedule simple projects, allowing managers to track progress over
time.
- Gantt charts are simple and popular but may not show all activity relationships in complex
projects.
NETWORK DIAGRAMS
- Network diagrams are graphic representations of connected activities and events in a project.
Basic Components of Network Diagram
- Activities are time-consuming efforts represented by arrows in the network diagram.
- Events or nodes are points in the line representing the start or end of an activity.
- Merge events are where multiple activities end, while burst events are where multiple activities
begin.
Preceding, succeeding and concurrent activities
- Preceding activities must be done before a certain event, succeeding activities can only be
done after an event, and concurrent activities can be done at the same time as other activities.
- Activities can be both preceding and succeeding or concurrent depending on different events.
Dummy Activity
- Dummy activities don't take time or resources and are used to show a connection between
events.
- They help maintain a unique numbering system and logical flow in the network.
Numbering the Events
- Event numbers should be unique and assigned sequentially from left to right.
- The initial event with only outgoing arrows is numbered 0 or 1.
- Arrow heads should have higher numbers than the tail.
 - Gaps should be left for adding activities later.
Rules for Drawing a Network
- A complete network should have one start event and one finish event.
- Each activity has one preceding event (tail) and one following event (head).
- Multiple activities can share the same tail or head event, but not both.
- Time flows from left to right, and activities must be completed in order.
- Dummy activities are used only when necessary.
Convention for Drawing Networks
There are two conventions for drawing network diagrams: activity-on-arrow (A-O-A) and
activity-on-node (A-O-N).
- When using the activity-on-arrow convention:
- Networks proceed from left to right.
- Networks are not drawn to scale.
- Arrows representing activities should point from left to right.
- Events or nodes should be numbered so that activities always move from a lower numbered
event to a higher one.
- Lines that cross should be avoided if possible.
- The start event may be represented as a line instead of a circle, particularly when several
activities may begin at the start point.
Common errors in drawing networks include:
- Formation of a loop: This happens when an activity is represented as going back in time,
creating a closed loop. It's also known as a cycling error and can occur if an activity is repeated
before the next one starts.
- Dangling: This occurs when an activity ends without being connected to the end event. To fix
this, a dummy activity is added to maintain system continuity. End-events other than the overall
project end are called dangling events.
- Redundancy: If a dummy activity is the only one coming from an event, it can be removed.
Shortest Route Problem:
- Objective: Find the shortest path from origin to destination, minimizing distance, time, or
costs.
- Steps to Solve: Total steps required are n-1 for n locations in the network.
- Labeling Procedure: Each node is assigned two numbers - the 1st label represents the distance
from the original node, and the 2nd number refers to the node immediately preceding the labeled
node.
- Algorithm: Nodes are labeled permanently or temporarily, with temporary labels indicating
that the labeling might be revised until it's ascertained that no shorter route to a node exists.

Minimum Spanning Tree Model:

- Objective: Connect all nodes in a network using as little connecting material as possible.
- Example: Nodes representing oil storage tanks, with lines representing pipelines used to carry
oil between tanks.
- Cost Consideration: The cost of the pipeline is proportional to its length, so the objective is to
connect all tanks using as little pipeline as possible.
- Applications: Designing communication systems, highway networks, etc., using minimal
amounts of materials.