Operations Research 06A: Transportation Problem

Summary

This video script introduces the transportation problem, a special linear programming (LP) issue with practical applications, which can be solved more efficiently using specialized algorithms than the traditional simplex method. It outlines the problem setup involving supply and demand points, shipping costs, and capacity constraints. The script explains the formulation of both balanced and unbalanced transportation problems, the use of dummy nodes for balancing, and the advantages of the transportation simplex method over the regular simplex method for solving these problems.

Takeaways

• 📚 The video discusses the formulation of transportation problems, a special type of Linear Programming (LP) problem with practical applications.
• 🔍 While the simplex method can solve transportation problems, specialized algorithms are more efficient due to the unique structure of these problems.
• 📦 The goal of a transportation problem is to determine the best way to meet the demand of multiple customers using the supply from various sources, considering shipping costs.
• 🏭 An example given involves two factories supplying three customers, with unit shipping costs varying based on distance and factory capacity limits.
• 🔢 Decision variables x_{ij} represent the number of products shipped from one factory to a customer, and the objective function calculates the total shipping cost.
• 🚫 Constraints ensure that each factory does not exceed its capacity and each customer's demand is met.
• 📉 The script introduces the concept of a balanced transportation problem, where total supply equals total demand, contrasting with the general case.
• 🔄 For balanced problems, the transportation simplex method is an efficient algorithm, which will be covered in a different video.
• 📈 The transportation tableau is a visual representation of the problem, showing supply and demand nodes, shipping costs, and decision variables.
• 🔄 Unbalanced problems require the introduction of dummy supply or demand nodes to balance the total supply with the total demand, using penalties for unmet demand.
• 🛠 The transportation simplex method is preferred over the regular simplex method for balanced problems due to its ability to handle equality constraints without additional variables.
• 🔑 The initial step in the transportation simplex method is finding an initial Basic Feasible Solution (BFS) using methods like the northwest corner rule or Vogel's approximation method.

Q & A

What is a transportation problem in the context of linear programming?

A transportation problem is a special type of linear programming problem that deals with the optimal allocation of resources from multiple supply points to multiple demand points, considering the costs of transportation.

Why are specialized algorithms more efficient for solving transportation problems compared to the traditional simplex method?

Specialized algorithms are more efficient for transportation problems because they take advantage of the problem's special structure, which includes the equality constraints inherent in balanced transportation problems.

What are the decision variables in a transportation problem?

The decision variables in a transportation problem are denoted by xij, representing the number of products shipped from Factory i to Customer j.

What is the objective function in a transportation problem?

The objective function in a transportation problem is the total cost of shipping, which is the sum of the product of the unit shipping costs and the decision variables.

What are the constraints in a transportation problem?

The constraints in a transportation problem ensure that the supply capacity of each factory is not exceeded and that the demand of each customer is met.

What is a balanced transportation problem?

A balanced transportation problem is one where the total supply is equal to the total demand, allowing for the use of specialized algorithms like the transportation simplex method.

How is a transportation problem represented in a diagram?

In a diagram, supply nodes are represented along with demand nodes, and transportation routes are shown with arrows indicating the flow of products. Each route has an associated cost, cij.

What is a transportation tableau and how is it used?

A transportation tableau is a tabular representation of a transportation problem, where supply nodes and demand nodes are arranged in rows and columns, respectively. The unit shipping costs are placed in the cells, and decision variables are determined to fill the tableau.

How can an unbalanced transportation problem be made balanced?

An unbalanced transportation problem can be made balanced by introducing a dummy supply node or a dummy demand node, depending on whether supply exceeds demand or vice versa. Penalties for unmet demand or unused capacity are also introduced.

Why is the regular simplex method not very efficient for solving balanced transportation problems?

The regular simplex method is not very efficient for balanced transportation problems because it requires the use of the big M method to handle equality constraints, which introduces artificial variables and increases the problem's complexity.

What are some methods to find an initial basic feasible solution in the transportation simplex method?

Some methods to find an initial basic feasible solution in the transportation simplex method include the northwest corner method, the minimum-cost method, and Vogel's approximation method.

Outlines

00:00

🚚 Introduction to Transportation Problems and LP Formulation

This paragraph introduces the concept of transportation problems, a type of linear programming (LP) problem with practical applications. It explains that while the simplex method can be used to solve these problems, specialized algorithms are more efficient due to the unique structure of transportation problems. The paragraph outlines a scenario where a manufacturing company needs to distribute products from two factories to three customers, considering unit shipping costs and factory capacities. The objective function is to minimize total shipping costs, and constraints ensure that factory capacities are not exceeded and customer demands are met. The decision variables are defined as the number of products shipped from each factory to each customer, and the problem is formulated as a balanced transportation problem where total supply equals total demand.

05:04

🔄 Balancing Unbalanced Transportation Problems

The second paragraph discusses how to handle unbalanced transportation problems, where the total supply does not equal the total demand. It provides an example where the demand exceeds the supply, necessitating the introduction of a dummy supply node, 'Factory 3', with a penalty cost for unmet demand. Conversely, if the supply exceeds demand, a dummy demand node is introduced to represent unused capacity. The paragraph explains how to adjust the transportation tableau to include these dummy nodes and how penalties or zero costs are assigned for unmet demand or unused capacity. It also touches on the inefficiency of the regular simplex method for balanced transportation problems due to the complexity added by equality constraints and artificial variables, and contrasts this with the transportation simplex method, which is more direct and efficient for these types of problems. The paragraph concludes by mentioning different methods to find an initial basic feasible solution for the transportation simplex method, which will be detailed in future videos.

Keywords

💡Transportation Problem

The transportation problem is a type of linear programming (LP) problem that deals with the logistics of delivering goods from multiple supply points to multiple demand points. It is central to the video's theme as it is the main problem being discussed and solved. The script provides an example of a manufacturing company with two factories (supply points) and three customers (demand points), illustrating the application of the transportation problem in real-world scenarios.

💡Simplex Method

The simplex method is an algorithm for solving linear programming problems. In the context of the video, it is mentioned as a traditional approach to solving transportation problems. However, the video emphasizes that due to the special structure of transportation problems, there are more efficient specialized algorithms available.

💡Supply Points

Supply points, represented by factories in the script, are the origins from which products are shipped. They are a fundamental part of the transportation problem, as the video discusses how to efficiently allocate the limited capacities of these supply points to meet the demands of customers.

💡Demand Points

Demand points, or customers in the script, are the destinations where products need to be delivered. The video script outlines the necessity to satisfy the demands of these points using the supplies available, which is a key aspect of formulating and solving the transportation problem.

💡Unit Shipping Cost

Unit shipping cost refers to the cost incurred to transport one unit of product from a supply point to a demand point. In the video, it is used to calculate the total shipping cost and is a critical factor in determining the most cost-effective shipping strategy, as exemplified by the costs from Factory 1 to Customer 1 and other pairs.

💡Capacity Constraints

Capacity constraints limit the amount of products that can be supplied by each factory. The video script specifies that Factory 1 has a capacity of 40 products per day and Factory 2 has a capacity of 50, which are constraints that must be considered when formulating the transportation problem.

💡Decision Variables (xij)

In the context of the transportation problem, decision variables (xij) represent the number of products shipped from a specific factory (i) to a specific customer (j). The video uses these variables to construct the objective function and constraints, which are essential for solving the problem.

💡Objective Function

The objective function in the transportation problem is to minimize the total cost of shipping products from supply points to demand points. The video explains that this function is the sum of the product of the unit shipping costs and the decision variables, aiming to find the most cost-effective solution.

💡Balanced Transportation Problem

A balanced transportation problem is one where the total supply equals the total demand. The video provides an example where the supply from two factories (40+50) equals the combined demand of three customers (30+30+30), which simplifies the problem and allows for the use of specialized algorithms like the transportation simplex method.

💡Transportation Simplex Method

The transportation simplex method is a specialized algorithm for solving balanced transportation problems efficiently. The video mentions that this method can handle the equality constraints directly without the need for artificial variables, making it more efficient than the traditional simplex method for this type of problem.

💡Dummy Supply/Demand Node

In the case of an unbalanced transportation problem, where supply does not equal demand, dummy supply or demand nodes are introduced to balance the problem. The video script illustrates this with the introduction of Factory 3 (dummy supply) and Customer 4 (dummy demand), which helps in formulating the problem for the transportation simplex method.

💡Penalty

A penalty is a cost associated with unmet demand when the supply is less than the demand. The video script explains that a penalty cost is introduced for each unit of unmet demand for customers, such as $20 for Customer 1, which is used to balance the transportation problem and calculate the total cost.

💡Transportation Tableau

The transportation tableau is a graphical representation of the transportation problem, showing supply and demand nodes, unit shipping costs, and decision variables. The video uses the tableau to visually represent the problem and to demonstrate how to introduce dummy nodes and penalties in an unbalanced problem.

Highlights

The video discusses the formulation of a special type of LP problems known as the transportation problem, which has wide real-world applications.

Traditional simplex method can solve transportation problems, but specialized algorithms are more efficient due to the problem's special structure.

A transportation problem aims to find the best solution to meet the needs of multiple demand points using the capacities of supply points, with a cost associated with shipping.

An example is given of a manufacturing company with two factories supplying three customers, with unit shipping costs depending on distance.

Each factory has a limited capacity, and each customer requires a minimum number of products per day.

Decision variables xij represent the number of products shipped from a factory to a customer.

The objective function is to minimize the total cost of shipping products from factories to customers.

Constraints include limited factory capacities and the requirement to meet each customer's demand.

The example provided is a balanced transportation problem where total supply equals total demand.

In a balanced problem, the transportation simplex method is an efficient algorithm for solving it.

The transportation tableau is a visual representation of the problem, showing supply and demand nodes, transportation routes, and costs.

For unbalanced problems, a dummy supply or demand node is introduced to balance the total supply and demand.

Penalties are introduced for unmet demand, representing the financial loss related to it.

The transportation simplex method does not require the introduction of extra variables and can handle equality constraints directly.

The northwest corner method, minimum-cost method, and vogel's method are used to find an initial basic feasible solution in the transportation simplex method.

The regular simplex method is less efficient for balanced transportation problems due to the complexity added by equality constraints and the big M method.

The video concludes with a summary of how to formulate and represent a balanced transportation problem in a diagram or tableau.

Transcripts

In this video, we'll talk about how to formulate a special type of LP problems with wide real-world

applications.

It's called the transportation problem.

This type of problems can be solved using the traditional simplex method.

However, due to their special structure, there exist specialized algorithms that are much

more efficient to solve them.

A typical transportation problem is to find the best solution to fulfill the needs of

n demand points using the capacities of m supply points.

A cost of shipping the products from a supply point to a demand point is involved.

Here is an example.

A manufacturing company has m=2 factories that satisfy the needs of n=3 customers.

The unit shipping cost from a factory to a customer depends on the distance.

For example, from Factory 1 to Customer 1, the unit shipping cost is $8/product.

From Factory 1 to Customer 2, the unit shipping cost is $6/product, and so on.

Each factory has a limited capacity.

Factory 1 can supply at most 40 products per day and Factory 2 can supply at most 50 products

per day.

Each customer will need at least 30 products per day.

For the decision variables, we define xij = the number of products shipped from Factory

i to Customer j.

The objective function is the total cost.

For example, this is the cost of shipping x11 products from Factory 1 to Customer 1.

This is the cost of shipping x12 products from Factory 1 to Customer 2, and so on.

We need to sum up all the cost components.

As for the constraints, each factory has a limited capacity.

The total number of products sent from factory 1 to all three customers should be ≤ 40.

The total number of products sent from factory 2 to all three customers should be ≤ 50.

Each customer's demand should be met.

The total number of products received by customer 1 should be ≥ 30.

Same for Customer 2 and Customer 3.

This is the complete LP problem formulation.

This is a more general form of the transportation problem formulation.

The objective function is the sum of the cost matrix times the decision variables.

The sum of each row is less than or equal to the supply capacity.

The sum of each column is greater than or equal to the required demand.

The example we examined here is also a balanced transportation problem.

This is because the total supply is equal to the total demand.

40+50=90, which is equal to 30+30+30.

This is the formulation of a balanced transportation problem.

The difference between the general transportation problem and the balanced transportation problem

is in the constraints.

These two will be changed to the equality constraints.

And the total supply is equal to the total demand.

For the balanced transportation problem, there is an algorithm called the transportation

simplex to solve it efficiently, which will be talked about in another video.

We can show the mathematical formulation in a diagram like this.

These are the supply nodes, and these are the demand nodes.

These lines with arrows represent the transportation routes.

There is a cost, cij, associated with each route.

We need to determine the amount of products, xij, that will be shipped from supply node

i to the demand node j.

For this balanced problem, the total supply is 90, and the total demand is also 90.

This is another representation of the problem using the transportation tableau.

These are the supply nodes, and these are the demand nodes.

The unit shipping cost is put in the top right corner of each cell.

For example, from Factory 1 to customer 1, the unit shipping cost is $8/product.

We need to determine the amount of products, xij, that will be shipped from supply node

i to the demand node j.

We put the decision variables in the bottom right corner of each cell.

For this balanced problem, the total supply is 90, and the total demand is also 90.

If a problem is unbalanced, we need to balance it first before we use the transportation

simplex method to solve it.

In this example, the demand of customer 1 is increased from 30 to 40.

So the total supply, which is 90, is less than the total demand, which is 100.

In order to balance the problem, we need to introduce a dummy or fake supply node, called

Factory 3, and give it a capacity 10.

Any amount sent from Factory 3 to a customer will represent the unmet demand of that customer.

For each unit of unmet demand, we introduce a penalty, which can be determined by the

financial loss related to the unmet demand.

For example, we assume the penalty for each unit of unmet demand for customer 1 is $20,

for customer 2 is $22, and for customer 3 is $23.

Then the problem is balanced.

For the tableau representation, when we introduce a dummy supply F3, we are actually adding

one row to the original transportation tableau like this.

These are the penalties, and this is the dummy supply amount.

In this example, the supply of factory 1 is increased from 40 to 50.

So the total supply, which is 100, exceeds the total demand, which is 90.

In order to balance the problem, we need to introduce a dummy or fake demand node, called

Customer 4, and give it a demand 10.

Any amount sent from a factory to customer 4 will represent the unused, remaining capacity

of that factory.

For each unused capacity, there is no extra cost involved.

Therefore, c14 and c24 are both 0.

Now the problem is balanced.

For the tableau representation, when we introduce a dummy demand C4, we are actually adding

one column to the original transportation tableau like this.

The unit costs are 0, and this is the dummy demand.

Why is the regular simplex method not very efficient in solving the balanced transportation

problem?

This is because it contains many equality constraints.

The traditional simplex algorithm will have to use the big M method to find the initial

BFS by introducing many artificial variables, which increases the complexity of the problem.

In comparison, the transportation simplex method doesn't need to introduce extra variables

and can deal with the equality constraints directly.

The first step of the transportation simplex method is to find a BFS.

This can be done by using the northwest corner method, the minimum-cost method, or vogel's

method.

They will be introduce in other videos.

Okay, that's how we formulate a balanced transportation problem and represent it in a diagram or transportation

tableau.

Thanks for watching.