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[][] cost = {
  15.             {464, 513, 654, 867},
  16.             {352, 416, 690, 791},
  17.             {995, 682, 388, 685}
  18.         };
  19.  
  20.         // Solve using Vogel's approximation method
  21.         double[][] solution = solveTransportation(supply, demand, cost);
  22.  
  23.         // Print solution
  24.         printSolution(canneries, warehouses, solution, cost);
  25.     }
  26.  
  27.     public static double[][] solveTransportation(int[] supply, int[] demand, double[][] cost) {
  28.         int m = supply.length;
  29.         int n = demand.length;
  30.         double[][] solution = new double[m][n];
  31.         int[] s = Arrays.copyOf(supply, m);
  32.         int[] d = Arrays.copyOf(demand, n);
  33.  
  34.         while (true) {
  35.             // Find the cell with minimal cost in row or column with max penalty
  36.             int[] cell = findNextCell(cost, s, d);
  37.             if (cell == null) break;
  38.  
  39.             int i = cell[0], j = cell[1];
  40.             double amount = Math.min(s[i], d[j]);
  41.             solution[i][j] = amount;
  42.             s[i] -= amount;
  43.             d[j] -= amount;
  44.  
  45.             if (s[i] == 0) {
  46.                 for (int k = 0; k < n; k++) cost[i][k] = INFINITY;
  47.             }
  48.             if (d[j] == 0) {
  49.                 for (int k = 0; k < m; k++) cost[k][j] = INFINITY;
  50.             }
  51.         }
  52.  
  53.         return solution;
  54.     }
  55.  
  56.     private static int[] findNextCell(double[][] cost, int[] s, int[] d) {
  57.         // Simplified version of Vogel's approximation method
  58.         double minCost = INFINITY;
  59.         int[] cell = null;
  60.  
  61.         for (int i = 0; i < cost.length; i++) {
  62.             if (s[i] == 0) continue;
  63.             for (int j = 0; j < cost[0].length; j++) {
  64.                 if (d[j] == 0) continue;
  65.                 if (cost[i][j] < minCost) {
  66.                     minCost = cost[i][j];
  67.                     cell = new int[]{i, j};
  68.                 }
  69.             }
  70.         }
  71.  
  72.         return cell;
  73.     }
  74.  
  75.     public static void printSolution(String[] sources, String[] destinations, 
  76.                                    double[][] solution, double[][] cost) {
  77.         System.out.println("Transportation Solution:");
  78.         double totalCost = 0;
  79.  
  80.         for (int i = 0; i < solution.length; i++) {
  81.             for (int j = 0; j < solution[0].length; j++) {
  82.                 if (solution[i][j] > 0) {
  83.                     double costAmount = solution[i][j] * cost[i][j];
  84.                     System.out.printf("%-10s → %-12s: %6.1f units (Cost: $%8.1f)%n",
  85.                             sources[i], destinations[j], 
  86.                             solution[i][j], costAmount);
  87.                     totalCost += costAmount;
  88.                 }
  89.             }
  90.         }
  91.  
  92.         System.out.printf("%nTotal Transportation Cost: $%.1f%n", totalCost);
  93.     }
  94. }
Success #stdin #stdout 0.14s 56172KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Transportation Solution:
Bellingham → Salt_Lake   :   20.0 units (Cost: $Infinity)
Bellingham → Albuquerque :   55.0 units (Cost: $Infinity)
Eugene     → Sacramento  :   80.0 units (Cost: $Infinity)
Eugene     → Salt_Lake   :   45.0 units (Cost: $Infinity)
Albert_Lea → Rapid_City  :   70.0 units (Cost: $Infinity)
Albert_Lea → Albuquerque :   30.0 units (Cost: $Infinity)

Total Transportation Cost: $Infinity
https://ideone.com/ecdy7h
language:
Java (12.0.1)
created:
12 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!