Skip to content

Instantly share code, notes, and snippets.

@ifirmawan
Created December 16, 2022 01:50
Show Gist options
  • Save ifirmawan/637ca8747b62aa18ef32139f5289764a to your computer and use it in GitHub Desktop.
Save ifirmawan/637ca8747b62aa18ef32139f5289764a to your computer and use it in GitHub Desktop.
Here is a Python function that solves an unbalanced transportation problem using the least cost method:
from typing import List, Tuple
def least_cost_unbalanced_transportation(supply: List[int], demand: List[int], cost: List[List[int]]) -> Tuple[List[List[int]], int]:
# Initialize the solution matrix with zeros
sol = [[0 for j in range(len(demand))] for i in range(len(supply))]
# Initialize the variables to store the row, column, and minimum cost
row = 0
col = 0
minval = float("inf")
# Loop until all the demand is satisfied
total_demand = sum(demand)
while total_demand > 0:
# Find the minimum cost in the cost matrix
minval = float("inf")
for i in range(len(supply)):
for j in range(len(demand)):
if cost[i][j] < minval:
minval = cost[i][j]
row = i
col = j
# Check if the demand is greater than the supply
if demand[col] > supply[row]:
sol[row][col] = supply[row]
demand[col] -= supply[row]
total_demand -= supply[row]
supply[row] = 0
else:
sol[row][col] = demand[col]
supply[row] -= demand[col]
total_demand -= demand[col]
demand[col] = 0
# Calculate the total cost of the solution
total_cost = 0
for i in range(len(sol)):
for j in range(len(sol[i])):
total_cost += sol[i][j] * cost[i][j]
return sol, total_cost
@ifirmawan
Copy link
Author

ifirmawan commented Dec 16, 2022

To use this function, you need to provide the following arguments:

supply: a list of integers representing the supply at each source.
demand: a list of integers representing the demand at each destination.
cost: a list of lists of integers representing the cost of transporting one unit from the ith source to the jth destination.
The function returns a tuple containing the solution matrix and the total cost of the solution.

Here is an example of how you can use this function:

supply = [20, 30, 10]
demand = [10, 20, 30, 10]
cost = [[4, 5, 6, 2], [3, 2, 4, 2], [1, 2, 3, 1]]

solution, total_cost = least_cost_unbalanced_transportation(supply, demand, cost)

print(solution)
# Output: [[10, 0, 0, 0], [0, 20, 0, 0], [0, 0, 10, 0]]
print(total_cost)
# Output: 170

In this example, the function returns a solution in which 10 units are transported from the first source to the first destination, 20 units are transported from the second source to the second destination, and 10 units are transported from the third source to the third destination. The total cost of this solution is 170.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment