fork download
copy 
  1. import java.util.Arrays;
  2.  
  3. class TransportationProblem {
  4.     private static final double INFINITY = Double.MAX_VALUE;
  5.  
  6.     public static void main(String[] args) {
  7.         // Problem data
  8.         String[] canneries = {"Bellingham", "Eugene", "Albert_Lea"};
  9.         String[] warehouses = {"Sacramento", "Salt_Lake", "Rapid_City", "Albuquerque"};
  10.  
  11.         int[] supply = {75, 125, 100};
  12.         int[] demand = {80, 65, 70, 85};
  13.  
  14.         double[][] originalCost = {
  15.             {464, 513, 654, 867},
  16.             {352, 416, 690, 791},
  17.             {995, 682, 388, 685}
  18.         };
  19.  
  20.         // Create a working copy of the cost matrix
  21.         double[][] workingCost = new double[originalCost.length][];
  22.         for (int i = 0; i < originalCost.length; i++) {
  23.             workingCost[i] = Arrays.copyOf(originalCost[i], originalCost[i].length);
  24.         }
  25.  
  26.         // Solve using Vogel's approximation method
  27.         double[][] solution = solveTransportation(supply, demand, workingCost);
  28.  
  29.         // Print solution using original costs
  30.         printSolution(canneries, warehouses, solution, originalCost);
  31.     }
  32.  
  33.     public static double[][] solveTransportation(int[] supply, int[] demand, double[][] cost) {
  34.         int m = supply.length;
  35.         int n = demand.length;
  36.         double[][] solution = new double[m][n];
  37.         int[] s = Arrays.copyOf(supply, m);
  38.         int[] d = Arrays.copyOf(demand, n);
  39.  
  40.         while (true) {
  41.             int[] cell = findNextCell(cost, s, d);
  42.             if (cell == null) break;
  43.  
  44.             int i = cell[0], j = cell[1];
  45.             double amount = Math.min(s[i], d[j]);
  46.             solution[i][j] = amount;
  47.             s[i] -= amount;
  48.             d[j] -= amount;
  49.  
  50.             if (s[i] == 0) {
  51.                 for (int k = 0; k < n; k++) cost[i][k] = INFINITY;
  52.             }
  53.             if (d[j] == 0) {
  54.                 for (int k = 0; k < m; k++) cost[k][j] = INFINITY;
  55.             }
  56.         }
  57.  
  58.         return solution;
  59.     }
  60.  
  61.     private static int[] findNextCell(double[][] cost, int[] s, int[] d) {
  62.         double minCost = INFINITY;
  63.         int[] cell = null;
  64.  
  65.         for (int i = 0; i < cost.length; i++) {
  66.             if (s[i] == 0) continue;
  67.             for (int j = 0; j < cost[0].length; j++) {
  68.                 if (d[j] == 0) continue;
  69.                 if (cost[i][j] < minCost) {
  70.                     minCost = cost[i][j];
  71.                     cell = new int[]{i, j};
  72.                 }
  73.             }
  74.         }
  75.  
  76.         return cell;
  77.     }
  78.  
  79.     public static void printSolution(String[] sources, String[] destinations, 
  80.                                    double[][] solution, double[][] cost) {
  81.         System.out.println("Transportation Solution:");
  82.         double totalCost = 0;
  83.  
  84.         for (int i = 0; i < solution.length; i++) {
  85.             for (int j = 0; j < solution[0].length; j++) {
  86.                 if (solution[i][j] > 0) {
  87.                     double costAmount = solution[i][j] * cost[i][j];
  88.                     System.out.printf("%-10s → %-12s: %6.1f units (Cost: $%8.1f)%n",
  89.                             sources[i], destinations[j], 
  90.                             solution[i][j], costAmount);
  91.                     totalCost += costAmount;
  92.                 }
  93.             }
  94.         }
  95.  
  96.         System.out.printf("%nTotal Transportation Cost: $%.1f%n", totalCost);
  97.     }
  98. }
Success #stdin #stdout 0.13s 54068KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Transportation Solution:
Bellingham → Salt_Lake   :   20.0 units (Cost: $ 10260.0)
Bellingham → Albuquerque :   55.0 units (Cost: $ 47685.0)
Eugene     → Sacramento  :   80.0 units (Cost: $ 28160.0)
Eugene     → Salt_Lake   :   45.0 units (Cost: $ 18720.0)
Albert_Lea → Rapid_City  :   70.0 units (Cost: $ 27160.0)
Albert_Lea → Albuquerque :   30.0 units (Cost: $ 20550.0)

Total Transportation Cost: $152535.0
https://ideone.com/FMlux2
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!