fork download
copy 
  1. import java.util.Arrays;
  2.  
  3. class TransportationProblem {
  4.  
  5.     private static final double INFINITY = Double.MAX_VALUE;
  6.  
  7.     public static void main(String[] args) {
  8.         // ========== INPUT DATA ==========
  9.         String[] canneries = {"Bellingham", "Eugene", "Albert_Lea"};
  10.         String[] warehouses = {"Sacramento", "Salt_Lake", "Rapid_City", "Albuquerque"};
  11.  
  12.         int[] supply = {75, 125, 100};  // Cannery capacities
  13.         int[] demand = {80, 65, 70, 85}; // Warehouse requirements
  14.  
  15.         double[][] costMatrix = {  // Cost per truckload ($)
  16.             {464, 513, 654, 867}, // Bellingham costs
  17.             {352, 416, 690, 791}, // Eugene costs
  18.             {995, 682, 388, 685}  // Albert Lea costs
  19.         };
  20.  
  21.         // ========== SOLUTION ==========
  22.         printProblemStatement(canneries, warehouses, supply, demand, costMatrix);
  23.  
  24.         double[][] optimalShipments = solveTransportationProblem(
  25.             supply, 
  26.             demand, 
  27.             deepCopyMatrix(costMatrix) // Preserve original
  28.         );
  29.  
  30.         printOptimalSolution(canneries, warehouses, optimalShipments, costMatrix);
  31.     }
  32.  
  33.     // ========== CORE ALGORITHM ==========
  34.     public static double[][] solveTransportationProblem(
  35.         int[] supply, int[] demand, double[][] cost) {
  36.  
  37.         int m = supply.length, n = demand.length;
  38.         double[][] solution = new double[m][n];
  39.         int[] remainingSupply = Arrays.copyOf(supply, m);
  40.         int[] remainingDemand = Arrays.copyOf(demand, n);
  41.  
  42.         while (true) {
  43.             int[] nextShipment = findCheapestValidRoute(cost, remainingSupply, remainingDemand);
  44.             if (nextShipment == null) break; // Termination condition
  45.  
  46.             int from = nextShipment[0], to = nextShipment[1];
  47.             double amount = Math.min(remainingSupply[from], remainingDemand[to]);
  48.  
  49.             // Record shipment
  50.             solution[from][to] = amount;
  51.             remainingSupply[from] -= amount;
  52.             remainingDemand[to] -= amount;
  53.  
  54.             // Mark exhausted routes
  55.             if (remainingSupply[from] == 0) 
  56.                 Arrays.fill(cost[from], INFINITY); // Entire row
  57.             if (remainingDemand[to] == 0) 
  58.                 for (int i = 0; i < m; i++) cost[i][to] = INFINITY; // Entire column
  59.         }
  60.  
  61.         return solution;
  62.     }
  63.  
  64.     // ========== HELPER METHODS ==========
  65.     private static int[] findCheapestValidRoute(double[][] cost, int[] supply, int[] demand) {
  66.         double minCost = INFINITY;
  67.         int[] bestRoute = null;
  68.  
  69.         for (int i = 0; i < cost.length; i++) {
  70.             if (supply[i] == 0) continue; // Skip exhausted sources
  71.  
  72.             for (int j = 0; j < cost[0].length; j++) {
  73.                 if (demand[j] == 0) continue; // Skip satisfied destinations
  74.  
  75.                 if (cost[i][j] < minCost) {
  76.                     minCost = cost[i][j];
  77.                     bestRoute = new int[]{i, j};
  78.                 }
  79.             }
  80.         }
  81.         return bestRoute;
  82.     }
  83.  
  84.     private static double[][] deepCopyMatrix(double[][] original) {
  85.         return Arrays.stream(original)
  86.                    .map(row -> Arrays.copyOf(row, row.length))
  87.                    .toArray(double[][]::new);
  88.     }
  89.  
  90.     // ========== OUTPUT FORMATTING ==========
  91.     private static void printProblemStatement(
  92.         String[] sources, String[] destinations, 
  93.         int[] supply, int[] demand, double[][] cost) {
  94.  
  95.         System.out.println("===== TRANSPORTATION PROBLEM =====");
  96.         System.out.println("\nSources (Supply):");
  97.         for (int i = 0; i < sources.length; i++) 
  98.             System.out.printf("- %-12s: %d truckloads%n", sources[i], supply[i]);
  99.  
  100.         System.out.println("\nDestinations (Demand):");
  101.         for (int j = 0; j < destinations.length; j++) 
  102.             System.out.printf("- %-12s: %d truckloads%n", destinations[j], demand[j]);
  103.  
  104.         System.out.println("\nCost Matrix ($ per truckload):");
  105.         System.out.print("From\\To\t");
  106.         for (String dest : destinations) System.out.printf("%-12s\t", dest);
  107.         System.out.println();
  108.  
  109.         for (int i = 0; i < sources.length; i++) {
  110.             System.out.printf("%-12s\t", sources[i]);
  111.             for (int j = 0; j < destinations.length; j++) 
  112.                 System.out.printf("$%-11.0f\t", cost[i][j]);
  113.             System.out.println();
  114.         }
  115.     }
  116.  
  117.     private static void printOptimalSolution(
  118.         String[] sources, String[] destinations,
  119.         double[][] shipments, double[][] costMatrix) {
  120.  
  121.         System.out.println("\n===== OPTIMAL SOLUTION =====");
  122.         double totalCost = 0;
  123.  
  124.         System.out.println("\nShipment Plan:");
  125.         for (int i = 0; i < shipments.length; i++) {
  126.             for (int j = 0; j < shipments[0].length; j++) {
  127.                 if (shipments[i][j] > 0) {
  128.                     double shipmentCost = shipments[i][j] * costMatrix[i][j];
  129.                     System.out.printf(
  130.                         "%-12s → %-12s: %5.1f truckloads @ $%-5.0f = $%-7.0f%n",
  131.                         sources[i], destinations[j],
  132.                         shipments[i][j], costMatrix[i][j], shipmentCost
  133.                     );
  134.                     totalCost += shipmentCost;
  135.                 }
  136.             }
  137.         }
  138.  
  139.         System.out.printf("%nTotal Transportation Cost: $%.2f%n", totalCost);
  140.         System.out.println("============================");
  141.     }
  142. }
Success #stdin #stdout 0.13s 54516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
===== TRANSPORTATION PROBLEM =====

Sources (Supply):
- Bellingham  : 75 truckloads
- Eugene      : 125 truckloads
- Albert_Lea  : 100 truckloads

Destinations (Demand):
- Sacramento  : 80 truckloads
- Salt_Lake   : 65 truckloads
- Rapid_City  : 70 truckloads
- Albuquerque : 85 truckloads

Cost Matrix ($ per truckload):
From\To	Sacramento  	Salt_Lake   	Rapid_City  	Albuquerque 	
Bellingham  	$464        	$513        	$654        	$867        	
Eugene      	$352        	$416        	$690        	$791        	
Albert_Lea  	$995        	$682        	$388        	$685        	

===== OPTIMAL SOLUTION =====

Shipment Plan:
Bellingham   → Salt_Lake   :  20.0 truckloads @ $513   = $10260  
Bellingham   → Albuquerque :  55.0 truckloads @ $867   = $47685  
Eugene       → Sacramento  :  80.0 truckloads @ $352   = $28160  
Eugene       → Salt_Lake   :  45.0 truckloads @ $416   = $18720  
Albert_Lea   → Rapid_City  :  70.0 truckloads @ $388   = $27160  
Albert_Lea   → Albuquerque :  30.0 truckloads @ $685   = $20550  

Total Transportation Cost: $152535.00
============================
https://ideone.com/zDrRYT
language:
Java (12.0.1)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!