Linear programming can also handle maximization problems, and transportation problems are no exception. While the standard transportation problem seeks to minimize transportation costs, there might be scenarios where you want to maximize something else, like profit or total delivered goods. Here’s how we approach these maximization problems:
Conversion to Minimization:
The most common approach to solving a maximization transportation problem is to convert it into an equivalent minimization problem. This conversion allows you to leverage the well-established methods like the simplex method or stepping stone method, which are designed for minimization problems.
Here’s the conversion trick:
-
Identify the Maximization Objective: Clearly define what you want to maximize, be it profit per unit delivered (profit_i) or total delivered quantity.
-
Find the Highest Unit “Return”: Identify the highest value among your profit per unit or other relevant measure you’re trying to maximize. Let’s call this highest value ‘M’.
-
Subtract Unit Values from M: In your transportation table, subtract each cell’s unit value (profit_i) from ‘M’. This essentially transforms profit into a transportation cost where a higher value initially represents a lower transportation cost (since it’s further from M).
-
Solve as Minimization Problem: With the adjusted table (where higher values represent lower costs), use your preferred method (simplex method, stepping stone method, etc.) to solve for the minimum transportation cost. Remember, minimizing transportation cost in this transformed table translates to maximizing the original objective in the actual problem.
Example: Maximizing Delivered Quantity
Imagine you have a transportation problem where you want to maximize the total quantity of a good delivered to various destinations from different factories.
-
The transportation table shows the available quantity at each factory and the demand at each destination.
-
Solve the problem as a minimization problem, but instead of minimizing transportation cost, you’re minimizing the negative delivered quantity (obtained by subtracting the actual delivered quantity from the maximum possible delivery).
Benefits of Conversion Approach:
- Leverages Existing Methods: By converting to minimization, you can utilize the well-developed tools and algorithms designed for minimization problems.
- Intuitive Interpretation: Even after solving the minimization problem, it’s easy to translate the results back to the original maximization problem, as minimizing negative delivered quantity translates to maximizing actual delivered quantity.
Alternative Methods:
While conversion is a common approach, some specialized algorithms are designed specifically for maximization transportation problems. These algorithms might be more efficient for certain scenarios, but familiarity with the conversion method offers a broader applicability using established LP techniques.