Rosetta Code

Transportation problem: Difference between revisions

Page Discussion

Transportation problem (view source)

Revision as of 15:22, 14 February 2024

165,348 bytes added ,  4 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Racket}}: stub added)
m (→‎{{header|Wren}}: Minor tidy)
 
(74 intermediate revisions by 15 users not shown)
Line 1:
{{draft task}}
The '''[[wp:Transportation_theory_%28mathematics%29|Transportationtransportation problem]]''' in linear programming is to find the optimal transportation plan for certain volumes of resources from suppliers to consumers, taking into account the cost of transportation. The plan is a table (matrix), whose rows and columns correspond to the suppliers and consumers, the cells are placed in cargo volume.
 
Example of the transportation problem:
<centerbr><br>
 
{| border="1" style="border-collapse: collapse; border: 1px solid black; text-align: center;"
:::::: {| border="1" style="border-collapse: collapse; border: 1px solid black; text-align: center;"
|-
!style="width:100pt"|
Line 21 ⟶ 22:
|$5 per kg
|}
</center>
 
<br><br>
 
The object is to solve the classical transport problem using the method of potentials (with redistributive cycle) with the preparation of the initial transportation plan by the north-west corner of the features to be implemented in this task. The input is the number of suppliers and customers, inventory levels, needs and cost matrix transport cargo. The output of the program is the optimal plan. If necessary, enter a fictitious vendor or customer.
For the first time this problem mathematically studied the Soviet mathematician A. N. Tolstoy. In 1930 he published his work on finding the minimum total mileage in rail transportation, which used the redistributive cycles. The main contribution to the development of the mathematical apparatus of the transport problem introduced Soviet economist L. V. Kantorovich during the Great Patriotic War (published in 1939 and 1942). The way to solve the transportation problem by the potential method was it published in conjunction with M. K. Gavurin in 1949.
 
The program is to solve the classical transport problem using the method of potentials (with redistributive cycle) with the preparation of the initial transportation plan by the north-west corner of the features to be implemented in this task. The input is the number of suppliers and customers, inventory levels, needs and cost matrix transport cargo. The output of the program is the optimal plan. If necessary, enter a fictitious vendor or customer.
 
The solution for the above example would be the plan:
<centerbr><br>
 
{| border="1" style="border-collapse: collapse; border: 1px solid black; text-align: center;"
::::::{| border="1" style="border-collapse: collapse; border: 1px solid black; text-align: center;"
|-
!style="width:100pt"|
Line 47 ⟶ 46:
| 5 kg
|}
</centerbr><br>
 
;<nowiki>See also:</nowiki>
* [http://orms.pef.czu.cz/text/transProblem.html The Transportation Problem]
* [https://www.youtube.com/watch?v=BI1SsbDg0vQ&list=PLlCWmLrQuBh1yHhpDfULpRGoTuLgeDB4X| Transportation model - Concepts (youtube)]
* [[Vogel's approximation method]]
<br><br>
 
; Related tasks:
* [[Vogel's approximation method]]
<br><br>
 
=={{header|1C}}==
<syntaxhighlight lang="text">// based on the program of <romix>
 
перем m,n; // Table size
Line 442 ⟶ 445:
Процедура КомандаРассчитать(Команда)
РешениеТранспортнойЗадачи();
КонецПроцедуры</langsyntaxhighlight>
 
=={{header|C sharp|C#}}==
{{trans|Java}}
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
 
namespace TransportationProblem {
class Shipment {
public Shipment(double q, double cpu, int r, int c) {
Quantity = q;
CostPerUnit = cpu;
R = r;
C = c;
}
 
public double CostPerUnit { get; }
 
public double Quantity { get; set; }
 
public int R { get; }
 
public int C { get; }
}
 
class Program {
private static int[] demand;
private static int[] supply;
private static double[,] costs;
private static Shipment[,] matrix;
 
static void Init(string filename) {
string line;
using (StreamReader file = new StreamReader(filename)) {
line = file.ReadLine();
var numArr = line.Split();
int numSources = int.Parse(numArr[0]);
int numDestinations = int.Parse(numArr[1]);
 
List<int> src = new List<int>();
List<int> dst = new List<int>();
 
line = file.ReadLine();
numArr = line.Split();
for (int i = 0; i < numSources; i++) {
src.Add(int.Parse(numArr[i]));
}
 
line = file.ReadLine();
numArr = line.Split();
for (int i = 0; i < numDestinations; i++) {
dst.Add(int.Parse(numArr[i]));
}
 
// fix imbalance
int totalSrc = src.Sum();
int totalDst = dst.Sum();
if (totalSrc > totalDst) {
dst.Add(totalSrc - totalDst);
} else if (totalDst > totalSrc) {
src.Add(totalDst - totalSrc);
}
 
supply = src.ToArray();
demand = dst.ToArray();
 
costs = new double[supply.Length, demand.Length];
matrix = new Shipment[supply.Length, demand.Length];
 
for (int i = 0; i < numSources; i++) {
line = file.ReadLine();
numArr = line.Split();
for (int j = 0; j < numDestinations; j++) {
costs[i, j] = int.Parse(numArr[j]);
}
}
}
}
 
static void NorthWestCornerRule() {
for (int r = 0, northwest = 0; r < supply.Length; r++) {
for (int c = northwest; c < demand.Length; c++) {
int quantity = Math.Min(supply[r], demand[c]);
if (quantity > 0) {
matrix[r, c] = new Shipment(quantity, costs[r, c], r, c);
 
supply[r] -= quantity;
demand[c] -= quantity;
 
if (supply[r] == 0) {
northwest = c;
break;
}
}
}
}
}
 
static void SteppingStone() {
double maxReduction = 0;
Shipment[] move = null;
Shipment leaving = null;
 
FixDegenerateCase();
 
for (int r = 0; r < supply.Length; r++) {
for (int c = 0; c < demand.Length; c++) {
if (matrix[r, c] != null) {
continue;
}
 
Shipment trial = new Shipment(0, costs[r, c], r, c);
Shipment[] path = GetClosedPath(trial);
 
double reduction = 0;
double lowestQuantity = int.MaxValue;
Shipment leavingCandidate = null;
 
bool plus = true;
foreach (var s in path) {
if (plus) {
reduction += s.CostPerUnit;
} else {
reduction -= s.CostPerUnit;
if (s.Quantity < lowestQuantity) {
leavingCandidate = s;
lowestQuantity = s.Quantity;
}
}
plus = !plus;
}
if (reduction < maxReduction) {
move = path;
leaving = leavingCandidate;
maxReduction = reduction;
}
}
}
 
if (move != null) {
double q = leaving.Quantity;
bool plus = true;
foreach (var s in move) {
s.Quantity += plus ? q : -q;
matrix[s.R, s.C] = s.Quantity == 0 ? null : s;
plus = !plus;
}
SteppingStone();
}
}
 
static List<Shipment> MatrixToList() {
List<Shipment> newList = new List<Shipment>();
foreach (var item in matrix) {
if (null != item) {
newList.Add(item);
}
}
return newList;
}
 
static Shipment[] GetClosedPath(Shipment s) {
List<Shipment> path = MatrixToList();
path.Add(s);
 
// remove (and keep removing) elements that do not have a
// vertical AND horizontal neighbor
int before;
do {
before = path.Count;
path.RemoveAll(ship => {
var nbrs = GetNeighbors(ship, path);
return nbrs[0] == null || nbrs[1] == null;
});
} while (before != path.Count);
 
// place the remaining elements in the correct plus-minus order
Shipment[] stones = path.ToArray();
Shipment prev = s;
for (int i = 0; i < stones.Length; i++) {
stones[i] = prev;
prev = GetNeighbors(prev, path)[i % 2];
}
return stones;
}
 
static Shipment[] GetNeighbors(Shipment s, List<Shipment> lst) {
Shipment[] nbrs = new Shipment[2];
foreach (var o in lst) {
if (o != s) {
if (o.R == s.R && nbrs[0] == null) {
nbrs[0] = o;
} else if (o.C == s.C && nbrs[1] == null) {
nbrs[1] = o;
}
if (nbrs[0] != null && nbrs[1] != null) {
break;
}
}
}
return nbrs;
}
 
static void FixDegenerateCase() {
const double eps = double.Epsilon;
if (supply.Length + demand.Length - 1 != MatrixToList().Count) {
for (int r = 0; r < supply.Length; r++) {
for (int c = 0; c < demand.Length; c++) {
if (matrix[r, c] == null) {
Shipment dummy = new Shipment(eps, costs[r, c], r, c);
if (GetClosedPath(dummy).Length == 0) {
matrix[r, c] = dummy;
return;
}
}
}
}
}
}
static void PrintResult(string filename) {
Console.WriteLine("Optimal solution {0}\n", filename);
double totalCosts = 0;
 
for (int r = 0; r < supply.Length; r++) {
for (int c = 0; c < demand.Length; c++) {
Shipment s = matrix[r, c];
if (s != null && s.R == r && s.C == c) {
Console.Write(" {0,3} ", s.Quantity);
totalCosts += (s.Quantity * s.CostPerUnit);
} else {
Console.Write(" - ");
}
}
Console.WriteLine();
}
Console.WriteLine("\nTotal costs: {0}\n", totalCosts);
}
 
static void Main() {
foreach (var filename in new string[] { "input1.txt", "input2.txt", "input3.txt" }) {
Init(filename);
NorthWestCornerRule();
SteppingStone();
PrintResult(filename);
}
}
}
}</syntaxhighlight>
{{out}}
<pre>Optimal solution input1.txt
 
20 - 5
- 30 5
 
Total costs: 180
 
Optimal solution input2.txt
 
- - - 12
20 - 10 10
- 30 - 3
 
Total costs: 130
 
Optimal solution input3.txt
 
- - - 14
- 9 - 1
10 - 5 -
- 5 7 -
- 1 - -
 
Total costs: 1000</pre>
 
=={{header|C++}}==
{{trans|Kotlin}}
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iomanip>
#include <iostream>
#include <fstream>
#include <numeric>
#include <string>
#include <vector>
#include <cfloat>
 
using namespace std;
 
class Shipment {
public:
double costPerUnit;
int r, c;
double quantity;
 
Shipment() : quantity(0), costPerUnit(0), r(-1), c(-1) {
// empty
}
 
Shipment(double q, double cpu, int r, int c) : quantity(q), costPerUnit(cpu), r(r), c(c) {
// empty
}
 
friend bool operator==(const Shipment &lhs, const Shipment &rhs) {
return lhs.costPerUnit == rhs.costPerUnit
&& lhs.quantity == rhs.quantity
&& lhs.r == rhs.r
&& lhs.c == rhs.c;
}
 
friend bool operator!=(const Shipment &lhs, const Shipment &rhs) {
return !(lhs == rhs);
}
 
static Shipment ZERO;
};
Shipment Shipment::ZERO = {};
 
vector<int> demand, supply;
vector<vector<double>> costs;
vector<vector<Shipment>> matrix;
 
void init(string filename) {
ifstream ifs;
 
ifs.open(filename);
if (!ifs) {
cerr << "File not found: " << filename << '\n';
return;
}
 
size_t numSources, numDestinations;
ifs >> numSources >> numDestinations;
 
vector<int> src, dst;
int t;
 
for (size_t i = 0; i < numSources; i++) {
ifs >> t;
src.push_back(t);
}
 
for (size_t i = 0; i < numDestinations; i++) {
ifs >> t;
dst.push_back(t);
}
 
// fix imbalance
int totalSrc = accumulate(src.cbegin(), src.cend(), 0);
int totalDst = accumulate(dst.cbegin(), dst.cend(), 0);
if (totalSrc > totalDst) {
dst.push_back(totalSrc - totalDst);
} else if (totalDst > totalSrc) {
src.push_back(totalDst - totalSrc);
}
 
supply = src;
demand = dst;
 
costs.clear();
matrix.clear();
 
double d;
for (size_t i = 0; i < numSources; i++) {
size_t cap = max(numDestinations, demand.size());
 
vector<double> dt(cap);
vector<Shipment> st(cap);
for (size_t j = 0; j < numDestinations; j++) {
ifs >> d;
dt[j] = d;
}
costs.push_back(dt);
matrix.push_back(st);
}
for (size_t i = numSources; i < supply.size(); i++) {
size_t cap = max(numDestinations, demand.size());
 
vector<Shipment> st(cap);
matrix.push_back(st);
 
vector<double> dt(cap);
costs.push_back(dt);
}
}
 
void northWestCornerRule() {
int northwest = 0;
for (size_t r = 0; r < supply.size(); r++) {
for (size_t c = northwest; c < demand.size(); c++) {
int quantity = min(supply[r], demand[c]);
if (quantity > 0) {
matrix[r][c] = Shipment(quantity, costs[r][c], r, c);
 
supply[r] -= quantity;
demand[c] -= quantity;
 
if (supply[r] == 0) {
northwest = c;
break;
}
}
}
}
}
 
vector<Shipment> matrixToVector() {
vector<Shipment> result;
for (auto &row : matrix) {
for (auto &s : row) {
if (s != Shipment::ZERO) {
result.push_back(s);
}
}
}
return result;
}
 
vector<Shipment> getNeighbors(const Shipment &s, const vector<Shipment> &lst) {
vector<Shipment> nbrs(2);
for (auto &o : lst) {
if (o != s) {
if (o.r == s.r && nbrs[0] == Shipment::ZERO) {
nbrs[0] = o;
} else if (o.c == s.c && nbrs[1] == Shipment::ZERO) {
nbrs[1] = o;
}
if (nbrs[0] != Shipment::ZERO && nbrs[1] != Shipment::ZERO) {
break;
}
}
}
return nbrs;
}
 
vector<Shipment> getClosedPath(const Shipment &s) {
auto path = matrixToVector();
path.insert(path.begin(), s);
 
// remove (and keep removing) elements that do not have a
// vertical AND horizontal neighbor
size_t before;
do {
before = path.size();
path.erase(
remove_if(
path.begin(), path.end(),
[&path](Shipment &ship) {
auto nbrs = getNeighbors(ship, path);
return nbrs[0] == Shipment::ZERO || nbrs[1] == Shipment::ZERO;
}),
path.end());
} while (before != path.size());
 
// place the remaining elements in the correct plus-minus order
vector<Shipment> stones(path.size());
fill(stones.begin(), stones.end(), Shipment::ZERO);
auto prev = s;
for (size_t i = 0; i < stones.size(); i++) {
stones[i] = prev;
prev = getNeighbors(prev, path)[i % 2];
}
return stones;
}
 
void fixDegenerateCase() {
double eps = DBL_MIN;
if (supply.size() + demand.size() - 1 != matrixToVector().size()) {
for (size_t r = 0; r < supply.size(); r++) {
for (size_t c = 0; c < demand.size(); c++) {
if (matrix[r][c] == Shipment::ZERO) {
Shipment dummy(eps, costs[r][c], r, c);
if (getClosedPath(dummy).empty()) {
matrix[r][c] = dummy;
return;
}
}
}
}
}
}
 
void steppingStone() {
double maxReduction = 0;
vector<Shipment> move;
Shipment leaving;
bool isNull = true;
 
fixDegenerateCase();
 
for (size_t r = 0; r < supply.size(); r++) {
for (size_t c = 0; c < demand.size(); c++) {
if (matrix[r][c] != Shipment::ZERO) {
continue;
}
 
Shipment trial(0, costs[r][c], r, c);
vector<Shipment> path = getClosedPath(trial);
 
double reduction = 0;
double lowestQuantity = INT32_MAX;
Shipment leavingCandidate;
 
bool plus = true;
for (auto &s : path) {
if (plus) {
reduction += s.costPerUnit;
} else {
reduction -= s.costPerUnit;
if (s.quantity < lowestQuantity) {
leavingCandidate = s;
lowestQuantity = s.quantity;
}
}
plus = !plus;
}
if (reduction < maxReduction) {
isNull = false;
move = path;
leaving = leavingCandidate;
maxReduction = reduction;
}
}
}
 
if (!isNull) {
double q = leaving.quantity;
bool plus = true;
for (auto &s : move) {
s.quantity += plus ? q : -q;
matrix[s.r][s.c] = s.quantity == 0 ? Shipment::ZERO : s;
plus = !plus;
}
steppingStone();
}
}
 
void printResult(string filename) {
ifstream ifs;
string buffer;
 
ifs.open(filename);
if (!ifs) {
cerr << "File not found: " << filename << '\n';
return;
}
 
cout << filename << "\n\n";
while (!ifs.eof()) {
getline(ifs, buffer);
cout << buffer << '\n';
}
cout << '\n';
 
cout << "Optimal solution " << filename << "\n\n";
double totalCosts = 0.0;
for (size_t r = 0; r < supply.size(); r++) {
for (size_t c = 0; c < demand.size(); c++) {
auto s = matrix[r][c];
if (s != Shipment::ZERO && s.r == r && s.c == c) {
cout << ' ' << setw(3) << s.quantity << ' ';
totalCosts += s.quantity * s.costPerUnit;
} else {
cout << " - ";
}
}
cout << '\n';
}
cout << "\nTotal costs: " << totalCosts << "\n\n";
}
 
void process(string filename) {
init(filename);
northWestCornerRule();
steppingStone();
printResult(filename);
}
 
int main() {
process("input1.txt");
process("input2.txt");
process("input3.txt");
 
return 0;
}</syntaxhighlight>
{{out}}
<pre>input1.txt
 
2 3
25 35
20 30 10
3 5 7
3 2 5
 
Optimal solution input1.txt
 
20 - 5
- 30 5
 
Total costs: 180
 
input2.txt
 
3 3
12 40 33
20 30 10
3 5 7
2 4 6
9 1 8
 
Optimal solution input2.txt
 
- - - 12
20 - 10 10
- 30 - 3
 
Total costs: 130
 
input3.txt
 
4 4
14 10 15 12
10 15 12 15
10 30 25 15
20 15 20 10
10 30 20 20
30 40 35 45
 
Optimal solution input3.txt
 
- - - 14
- 9 - 1
10 - 5 -
- 5 7 -
- 1 - -
 
Total costs: 1000</pre>
 
=={{header|D}}==
{{trans|Java}}
<langsyntaxhighlight lang="d">import std.stdio, std.range, std.algorithm, std.conv, std.math, std.traits;
 
final class Shipment {
Line 688 ⟶ 1,328:
printResult(fileName, demand, supply, costs, matrix);
}
}</langsyntaxhighlight>
{{out}}
<pre>Optimal solution transportation_problem1.txt
Line 713 ⟶ 1,353:
 
=={{header|Glagol}}==
<syntaxhighlight lang="text">ОТДЕЛ Транспорт+;
ИСПОЛЬЗУЕТ
Вывод ИЗ "...\Отделы\Обмен\",
Line 1,162 ⟶ 1,802:
ВывестиПлан
 
КОН Транспорт.</langsyntaxhighlight>
 
=== Input ===
Line 1,183 ⟶ 1,823:
- 30 - 3
--------------------
 
=={{header|Go}}==
{{trans|Java}}
<syntaxhighlight lang="go">package main
 
import (
"bufio"
"container/list"
"fmt"
"io/ioutil"
"log"
"math"
"os"
"strconv"
)
 
type shipment struct {
quantity, costPerUnit float64
r, c int
}
 
var shipZero = shipment{}
 
type transport struct {
filename string
supply, demand []int
costs [][]float64
matrix [][]shipment
}
 
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
 
func minOf(i, j int) int {
if i < j {
return i
}
return j
}
 
func newTransport(filename string) *transport {
file, err := os.Open(filename)
check(err)
defer file.Close()
scanner := bufio.NewScanner(file)
scanner.Split(bufio.ScanWords)
scanner.Scan()
numSources, err := strconv.Atoi(scanner.Text())
check(err)
scanner.Scan()
numDests, err := strconv.Atoi(scanner.Text())
check(err)
src := make([]int, numSources)
for i := 0; i < numSources; i++ {
scanner.Scan()
src[i], err = strconv.Atoi(scanner.Text())
check(err)
}
dst := make([]int, numDests)
for i := 0; i < numDests; i++ {
scanner.Scan()
dst[i], err = strconv.Atoi(scanner.Text())
check(err)
}
 
// fix imbalance
totalSrc := 0
for _, v := range src {
totalSrc += v
}
totalDst := 0
for _, v := range dst {
totalDst += v
}
diff := totalSrc - totalDst
if diff > 0 {
dst = append(dst, diff)
} else if diff < 0 {
src = append(src, -diff)
}
 
costs := make([][]float64, len(src))
for i := 0; i < len(src); i++ {
costs[i] = make([]float64, len(dst))
}
matrix := make([][]shipment, len(src))
for i := 0; i < len(src); i++ {
matrix[i] = make([]shipment, len(dst))
}
for i := 0; i < numSources; i++ {
for j := 0; j < numDests; j++ {
scanner.Scan()
costs[i][j], err = strconv.ParseFloat(scanner.Text(), 64)
check(err)
}
}
return &transport{filename, src, dst, costs, matrix}
}
 
func (t *transport) northWestCornerRule() {
for r, northwest := 0, 0; r < len(t.supply); r++ {
for c := northwest; c < len(t.demand); c++ {
quantity := minOf(t.supply[r], t.demand[c])
if quantity > 0 {
t.matrix[r][c] = shipment{float64(quantity), t.costs[r][c], r, c}
t.supply[r] -= quantity
t.demand[c] -= quantity
if t.supply[r] == 0 {
northwest = c
break
}
}
}
}
}
 
func (t *transport) steppingStone() {
maxReduction := 0.0
var move []shipment = nil
leaving := shipZero
t.fixDegenerateCase()
for r := 0; r < len(t.supply); r++ {
for c := 0; c < len(t.demand); c++ {
if t.matrix[r][c] != shipZero {
continue
}
trial := shipment{0, t.costs[r][c], r, c}
path := t.getClosedPath(trial)
reduction := 0.0
lowestQuantity := float64(math.MaxInt32)
leavingCandidate := shipZero
plus := true
for _, s := range path {
if plus {
reduction += s.costPerUnit
} else {
reduction -= s.costPerUnit
if s.quantity < lowestQuantity {
leavingCandidate = s
lowestQuantity = s.quantity
}
}
plus = !plus
}
if reduction < maxReduction {
move = path
leaving = leavingCandidate
maxReduction = reduction
}
}
}
 
if move != nil {
q := leaving.quantity
plus := true
for _, s := range move {
if plus {
s.quantity += q
} else {
s.quantity -= q
}
if s.quantity == 0 {
t.matrix[s.r][s.c] = shipZero
} else {
t.matrix[s.r][s.c] = s
}
plus = !plus
}
t.steppingStone()
}
}
 
func (t *transport) matrixToList() *list.List {
l := list.New()
for _, m := range t.matrix {
for _, s := range m {
if s != shipZero {
l.PushBack(s)
}
}
}
return l
}
 
func (t *transport) getClosedPath(s shipment) []shipment {
path := t.matrixToList()
path.PushFront(s)
 
// remove (and keep removing) elements that do not have a
// vertical AND horizontal neighbor
var next *list.Element
for {
removals := 0
for e := path.Front(); e != nil; e = next {
next = e.Next()
nbrs := t.getNeighbors(e.Value.(shipment), path)
if nbrs[0] == shipZero || nbrs[1] == shipZero {
path.Remove(e)
removals++
}
}
if removals == 0 {
break
}
}
 
// place the remaining elements in the correct plus-minus order
stones := make([]shipment, path.Len())
prev := s
for i := 0; i < len(stones); i++ {
stones[i] = prev
prev = t.getNeighbors(prev, path)[i%2]
}
return stones
}
 
func (t *transport) getNeighbors(s shipment, lst *list.List) [2]shipment {
var nbrs [2]shipment
for e := lst.Front(); e != nil; e = e.Next() {
o := e.Value.(shipment)
if o != s {
if o.r == s.r && nbrs[0] == shipZero {
nbrs[0] = o
} else if o.c == s.c && nbrs[1] == shipZero {
nbrs[1] = o
}
if nbrs[0] != shipZero && nbrs[1] != shipZero {
break
}
}
}
return nbrs
}
 
func (t *transport) fixDegenerateCase() {
eps := math.SmallestNonzeroFloat64
if len(t.supply)+len(t.demand)-1 != t.matrixToList().Len() {
for r := 0; r < len(t.supply); r++ {
for c := 0; c < len(t.demand); c++ {
if t.matrix[r][c] == shipZero {
dummy := shipment{eps, t.costs[r][c], r, c}
if len(t.getClosedPath(dummy)) == 0 {
t.matrix[r][c] = dummy
return
}
}
}
}
}
}
 
func (t *transport) printResult() {
fmt.Println(t.filename)
text, err := ioutil.ReadFile(t.filename)
check(err)
fmt.Printf("\n%s\n", string(text))
fmt.Printf("Optimal solution for %s\n\n", t.filename)
totalCosts := 0.0
for r := 0; r < len(t.supply); r++ {
for c := 0; c < len(t.demand); c++ {
s := t.matrix[r][c]
if s != shipZero && s.r == r && s.c == c {
fmt.Printf(" %3d ", int(s.quantity))
totalCosts += s.quantity * s.costPerUnit
} else {
fmt.Printf(" - ")
}
}
fmt.Println()
}
fmt.Printf("\nTotal costs: %g\n\n", totalCosts)
}
 
func main() {
filenames := []string{"input1.txt", "input2.txt", "input3.txt"}
for _, filename := range filenames {
t := newTransport(filename)
t.northWestCornerRule()
t.steppingStone()
t.printResult()
}
}</syntaxhighlight>
 
{{out}}
<pre>
input1.txt
 
2 3
25 35
20 30 10
3 5 7
3 2 5
 
Optimal solution for input1.txt
 
20 - 5
- 30 5
 
Total costs: 180
 
input2.txt
 
3 3
12 40 33
20 30 10
3 5 7
2 4 6
9 1 8
 
Optimal solution for input2.txt
 
- - - 12
20 - 10 10
- 30 - 3
 
Total costs: 130
 
input3.txt
 
4 4
14 10 15 12
10 15 12 15
10 30 25 15
20 15 20 10
10 30 20 20
30 40 35 45
 
Optimal solution for input3.txt
 
- - - 14
- 9 - 1
10 - 5 -
- 5 7 -
- 1 - -
 
Total costs: 1000
</pre>
 
=={{header|J}}==
 
The current task description refers to the algorithm by name, but I feel that those names are ambiguous (inadequately descriptive - we need the algorithm specified here on rosettacode, not problems which we expect are so well understood that no one needs to describe them).
 
So, I will be working with this interpretation:
 
(*) Assign shipments for the lowest cost unsatisfied need which can be supplied. When breaking ties, pick the first one which would be encountered when scanning left to right, top to bottom (which is the same order you use when reading english text on a page).
 
(*) Supply however much of the need which can be supplied by that shipment.
 
(*) Repeat until done.
 
(If this algorithm is incorrect for this task, that would just underline the need for a better task description. And, probably, also: the need for a more representative task example.)
 
In other words:
 
<syntaxhighlight lang="j">NB. C's y[m] v= x implemented as x m ndxasgn v y
ndxasgn=: conjunction define
:
((m{y)v x) m} y
)
 
trans=: adverb define
:
need=. x
supl=. y
cost=. m
dims=. supl ,&# need
r=. dims$0
while. 1 e., xfr=. supl *&*/ need do.
'iS iN'=. ndxs=. dims#:(i. <./), cost % xfr
n=. (iS { supl) <. iN { need
need=. n iN ndxasgn - need
supl=. n iS ndxasgn - supl
r=. n (<ndxs)} r
end.
)</syntaxhighlight>
 
Task data:
 
<syntaxhighlight lang="j">need=: 20 30 10
supply=: 25 35
cost=:3 5 7,:3 2 5</syntaxhighlight>
 
Task example:
 
<syntaxhighlight lang="j"> need cost trans supply
20 0 5
0 30 5</syntaxhighlight>
 
=={{header|Java}}==
{{works with|Java|8}}
<langsyntaxhighlight lang="java">import java.io.File;
import java.util.*;
import static java.util.Arrays.stream;
Line 1,409 ⟶ 2,439:
}
}
}</langsyntaxhighlight>
 
<pre>input1.txt
Line 1,464 ⟶ 2,494:
 
Total costs: 1000.0</pre>
 
=={{header|Julia}}==
Code taken from [https://github.com/dylanomics/transportation_problem here] using [https://jump.dev/JuMP.jl/stable/ JuMP].
<syntaxhighlight lang="julia">using JuMP, GLPK
 
# cost vector
c = [3, 5, 7, 3, 2, 5];
N = size(c,1);
 
# constraints Ax (<,>,=) b
A = [1 1 1 0 0 0
0 0 0 1 1 1
1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1];
b = [ 25, 35, 20, 30, 10];
s = ['<', '<', '=', '=', '='];
 
# construct model
model = Model(GLPK.Optimizer)
@variable(model, x[i=1:N] >= 0, base_name="traded quantities")
cost_fn = @expression(model, c'*x) # cost function
@constraint(model, C1, A[1:2,:]*x .<= b[1:2]) # inequality constraints
@constraint(model, C2, A[3:5,:]*x .== b[3:5]) # equality constraints
@objective(model, Min, cost_fn) # objective function
 
# solve model
status = JuMP.optimize!(model);
xstar = value.(x);
println("solution vector of quantities = ", xstar)
println("minimum total cost = ", JuMP.objective_value(model))
 
# recover Lagrange multipliers for post-optimality
λ = [JuMP.dual(C1[1]),JuMP.dual(C1[2])]
μ = [JuMP.dual(C2[1]),JuMP.dual(C2[2]),JuMP.dual(C2[3])]
</syntaxhighlight>
 
{{out}}
<pre>solution vector of quantities = [20.0, 0.0, 5.0, 0.0, 30.0, 5.0]
minimum total cost = 180.0</pre>
 
=={{header|Kotlin}}==
{{trans|Java}}
<syntaxhighlight lang="scala">// version 1.1.51
 
import java.io.File
import java.util.Scanner
import java.util.LinkedList
 
class Transport(val filename: String) {
 
private val supply: IntArray
private val demand: IntArray
private val costs : Array<DoubleArray>
private val matrix: Array<Array<Shipment>>
 
class Shipment(
var quantity: Double,
val costPerUnit: Double,
val r: Int,
val c: Int
)
 
companion object {
private val ZERO = Shipment(0.0, 0.0, -1, -1) // to avoid nullable Shipments
}
 
init {
val sc = Scanner(File(filename))
try {
val numSources = sc.nextInt()
val numDestinations = sc.nextInt()
val src = MutableList(numSources) { sc.nextInt() }
val dst = MutableList(numDestinations) { sc.nextInt() }
 
// fix imbalance
val totalSrc = src.sum()
val totalDst = dst.sum()
if (totalSrc > totalDst)
dst.add(totalSrc -totalDst)
else if (totalDst > totalSrc)
src.add(totalDst -totalSrc)
supply = src.toIntArray()
demand = dst.toIntArray()
 
costs = Array(supply.size) { DoubleArray(demand.size) }
matrix = Array(supply.size) { Array(demand.size) { ZERO } }
for (i in 0 until numSources) {
for (j in 0 until numDestinations) costs[i][j] = sc.nextDouble()
}
}
finally {
sc.close()
}
}
 
fun northWestCornerRule() {
var northwest = 0
for (r in 0 until supply.size) {
for (c in northwest until demand.size) {
val quantity = minOf(supply[r], demand[c]).toDouble()
if (quantity > 0.0) {
matrix[r][c] = Shipment(quantity, costs[r][c], r, c)
supply[r] -= quantity.toInt()
demand[c] -= quantity.toInt()
if (supply[r] == 0) {
northwest = c
break
}
}
}
}
}
 
fun steppingStone() {
var maxReduction = 0.0
var move: Array<Shipment>? = null
var leaving = ZERO
fixDegenerateCase()
 
for (r in 0 until supply.size) {
for (c in 0 until demand.size) {
if (matrix[r][c] != ZERO) continue
val trial = Shipment(0.0, costs[r][c], r, c)
val path = getClosedPath(trial)
var reduction = 0.0
var lowestQuantity = Int.MAX_VALUE.toDouble()
var leavingCandidate = ZERO
var plus = true
for (s in path) {
if (plus) {
reduction += s.costPerUnit
}
else {
reduction -= s.costPerUnit
if (s.quantity < lowestQuantity) {
leavingCandidate = s
lowestQuantity = s.quantity
}
}
plus = !plus
}
if (reduction < maxReduction) {
move = path
leaving = leavingCandidate
maxReduction = reduction
}
}
}
 
if (move != null) {
val q = leaving.quantity
var plus = true
for (s in move) {
s.quantity += if (plus) q else -q
matrix[s.r][s.c] = if (s.quantity == 0.0) ZERO else s
plus = !plus
}
steppingStone()
}
}
 
private fun matrixToList() =
LinkedList<Shipment>(matrix.flatten().filter { it != ZERO } )
 
private fun getClosedPath(s: Shipment): Array<Shipment> {
val path = matrixToList()
path.addFirst(s)
 
// remove (and keep removing) elements that do not have a
// vertical AND horizontal neighbor
while (path.removeIf {
val nbrs = getNeighbors(it, path)
nbrs[0] == ZERO || nbrs[1] == ZERO
}) ; // empty statement
 
// place the remaining elements in the correct plus-minus order
val stones = Array<Shipment>(path.size) { ZERO }
var prev = s
for (i in 0 until stones.size) {
stones[i] = prev
prev = getNeighbors(prev, path)[i % 2]
}
return stones
}
 
private fun getNeighbors(s: Shipment, lst: LinkedList<Shipment>): Array<Shipment> {
val nbrs = Array<Shipment>(2) { ZERO }
for (o in lst) {
if (o != s) {
if (o.r == s.r && nbrs[0] == ZERO)
nbrs[0] = o
else if (o.c == s.c && nbrs[1] == ZERO)
nbrs[1] = o
if (nbrs[0] != ZERO && nbrs[1] != ZERO) break
}
}
return nbrs
}
 
private fun fixDegenerateCase() {
val eps = Double.MIN_VALUE
if (supply.size + demand.size - 1 != matrixToList().size) {
for (r in 0 until supply.size) {
for (c in 0 until demand.size) {
if (matrix[r][c] == ZERO) {
val dummy = Shipment(eps, costs[r][c], r, c)
if (getClosedPath(dummy).size == 0) {
matrix[r][c] = dummy
return
}
}
}
}
}
}
 
fun printResult() {
val text = File(filename).readText()
println("$filename\n\n$text")
println("Optimal solution $filename\n")
var totalCosts = 0.0
for (r in 0 until supply.size) {
for (c in 0 until demand.size) {
val s = matrix[r][c]
if (s != ZERO && s.r == r && s.c == c) {
print(" %3s ".format(s.quantity.toInt()))
totalCosts += s.quantity * s.costPerUnit
}
else print(" - ")
}
println()
}
println("\nTotal costs: $totalCosts\n")
}
}
 
fun main(args: Array<String>) {
val filenames = arrayOf("input1.txt", "input2.txt", "input3.txt")
for (filename in filenames) {
with (Transport(filename)) {
northWestCornerRule()
steppingStone()
printResult()
}
}
}</syntaxhighlight>
 
{{out}}
<pre>
Same as Java entry
</pre>
 
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="nim">import fenv, lists, math, sequtils, strformat, strutils
 
type
 
Shipment = object
quantity: float
costPerUnit: float
r, c: int
 
Transport = object
filename: string
supply: seq[int]
demand: seq[int]
costs: seq[seq[float]]
matrix: seq[seq[Shipment]]
 
ShipmentList = DoublyLinkedList[Shipment]
 
const ShipZero = Shipment()
 
 
template emitError(msg: string) =
raise newException(ValueError, msg)
 
 
proc initTransport(filename: string): Transport =
let infile = filename.open()
let fields = infile.readLine().splitWhitespace().map(parseInt)
let numSources = fields[0]
let numDests = fields[1]
if numSources < 1 or numDests < 1:
emitError "wrong number of sources or destinations."
var src = infile.readLine().splitWhitespace().map(parseInt)
if src.len != numSources:
emitError "wrong number of sources; got $1, expected $2.".format(src.len, numSources)
var dst = infile.readLine().splitWhitespace().map(parseInt)
if dst.len != numDests:
emitError "wrong number of destinations; got $1, expected $2.".format(dst.len, numDests)
 
# Fix imbalance.
let totalSrc = sum(src)
let totalDst = sum(dst)
let diff = totalSrc - totalDst
if diff > 0: dst.add diff
elif diff < 0: src.add -diff
 
var costs = newSeqWith(src.len, newSeq[float](dst.len))
var matrix = newSeqWith(src.len, newSeq[Shipment](dst.len))
 
for i in 0..<numSources:
let fields = infile.readLine().splitWhitespace().map(parseFloat)
if fields.len > dst.len:
emitError "wrong number of costs; got $1, expected $2.".format(fields.len, numDests)
for j in 0..<numDests:
costs[i][j] = fields[j]
 
result = Transport(filename: filename, supply: move(src),
demand: move(dst), costs: move(costs), matrix: move(matrix))
 
 
func northWestCornerRule(tr: var Transport) =
var northWest = 0
for r in 0..tr.supply.high:
for c in northWest..tr.demand.high:
let quantity = min(tr.supply[r], tr.demand[c])
if quantity > 0:
tr.matrix[r][c] = Shipment(quantity: quantity.toFloat, costPerUnit: tr.costs[r][c], r: r, c: c)
dec tr.supply[r], quantity
dec tr.demand[c], quantity
if tr.supply[r] == 0:
northWest = c
break
 
 
func getNeighbors(tr: Transport; s: Shipment; list: ShipmentList): array[2, Shipment] =
for o in list:
if o != s:
if o.r == s.r and result[0] == ShipZero:
result[0] = o
elif o.c == s.c and result[1] == ShipZero:
result[1] = o
if result[0] != ShipZero and result[1] != ShipZero:
break
 
 
func matrixToList(tr: Transport): ShipmentList =
for m in tr.matrix:
for s in m:
if s != ShipZero:
result.append(s)
 
 
func getClosedPath(tr: Transport; s: Shipment): seq[Shipment] =
var path = tr.matrixToList
path.prepend(s)
 
# Remove (and keep removing) elements that do not have a
# vertical and horizontal neighbor.
while true:
var removals = 0
for e in path.nodes:
let nbrs = tr.getNeighbors(e.value, path)
if nbrs[0] == ShipZero or nbrs[1] == ShipZero:
path.remove(e)
inc removals
if removals == 0:
break
 
# Place the remaining elements in the correct plus-minus order.
var prev = s
var i = 0
for _ in path:
result.add prev
prev = tr.getNeighbors(prev, path)[i]
i = 1 - i
 
 
func fixDegenerateCase(tr: var Transport) =
const Eps = minimumPositiveValue(float)
if tr.supply.len + tr.demand.len - 1 != tr.matrix.len * tr.matrix[0].len:
for r in 0..tr.supply.high:
for c in 0..tr.demand.high:
if tr.matrix[r][c] == ShipZero:
let dummy = Shipment(quantity: Eps, costPerUnit: tr.costs[r][c], r: r, c: c)
if tr.getClosedPath(dummy).len == 0:
tr.matrix[r][c] = dummy
return
 
 
func steppingStone(tr: var Transport) =
var maxReduction = 0.0
var move: seq[Shipment]
var leaving = ShipZero
tr.fixDegenerateCase()
 
for r in 0..tr.supply.high:
for c in 0..tr.demand.high:
if tr.matrix[r][c] != ShipZero:
continue
let trial = Shipment(quantity: 0, costPerUnit: tr.costs[r][c], r: r, c: c)
var path = tr.getClosedPath(trial)
var reduction = 0.0
var lowestQuantity = float(int32.high)
var leavingCandidate = ShipZero
var plus = true
for s in path:
if plus:
reduction += s.costPerUnit
else:
reduction -= s.costPerUnit
if s.quantity < lowestQuantity:
leavingCandidate = s
lowestQuantity = s.quantity
plus = not plus
if reduction < maxReduction:
move = move(path)
leaving = leavingCandidate
maxReduction = reduction
 
if move.len != 0:
let q = leaving.quantity
var plus = true
for s in move.mitems:
if plus: s.quantity += q
else: s.quantity -= q
tr.matrix[s.r][s.c] = if s.quantity == 0: ShipZero else: s
plus = not plus
tr.steppingStone()
 
 
proc printResult(tr: Transport) =
echo tr.filename, '\n'
stdout.write tr.filename.readFile()
echo "\nOptimal solution for ", tr.filename, '\n'
var totalCosts = 0.0
for r in 0..tr.supply.high:
for c in 0..tr.demand.high:
let s = tr.matrix[r][c]
if s != ShipZero and s.r == r and s.c == c:
stdout.write &" {int(s.quantity):3} "
totalCosts += s.quantity * s.costPerUnit
else:
stdout.write " - "
echo()
echo &"\nTotal costs: {totalCosts:g}\n"
 
 
when isMainModule:
 
const Filenames = ["input1.txt", "input2.txt", "input3.txt"]
for filename in Filenames:
var tr = initTransport(filename)
tr.northWestCornerRule()
tr.steppingStone()
tr.printResult()</syntaxhighlight>
 
{{out}}
<pre>input1.txt
 
2 3
25 35
20 30 10
3 5 7
3 2 5
 
Optimal solution for input1.txt
 
20 - 5
- 30 5
 
Total costs: 180
 
input2.txt
 
3 3
12 40 33
20 30 10
3 5 7
2 4 6
9 1 8
 
Optimal solution for input2.txt
 
- - - 12
20 - 10 10
- 30 - 3
 
Total costs: 130
 
input3.txt
 
4 4
14 10 15 12
10 15 12 15
10 30 25 15
20 15 20 10
10 30 20 20
30 40 35 45
 
Optimal solution for input3.txt
 
- - - 14
- 9 - 1
10 - 5 -
- 5 7 -
- 1 - -
 
Total costs: 1000</pre>
 
=={{header|Pascal}}==
<langsyntaxhighlight lang="pascal">Program transport;
{ based on the program of <Svetlana Belashova> }
 
Line 1,948 ⟶ 3,482:
GotoXY(40,1);
l1: d:=ReadKey;
END.</langsyntaxhighlight>
 
=={{header|Perl}}==
Just re-using the code from [[Vogel's_approximation_method#Perl|Vogel's approximation method]], tweaked to handle specific input:
<syntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
use List::AllUtils qw( max_by nsort_by min );
 
my $data = <<END;
A=20 B=30 C=10
S=25 T=35
AS=3 BS=5 CS=7
CT=3 BT=2 CT=5
END
 
my $table = sprintf +('%4s' x 4 . "\n") x 3,
map {my $t = $_; map "$_$t", '', 'A' .. 'C' } '' , 'S' .. 'T';
 
my ($cost, %assign) = (0);
while( $data =~ /\b\w=\d/ ) {
my @penalty;
for ( $data =~ /\b(\w)=\d/g ) {
my @all = map /(\d+)/, nsort_by { /\d+/ && $& }
grep { my ($t, $c) = /(.)(.)=/; $data =~ /\b$c=\d/ and $data =~ /\b$t=\d/ }
$data =~ /$_\w=\d+|\w$_=\d+/g;
push @penalty, [ $_, ($all[1] // 0) - $all[0] ];
}
my $rc = (max_by { $_->[1] } nsort_by
{ my $x = $_->[0]; $data =~ /(?:$x\w|\w$x)=(\d+)/ && $1 } @penalty)->[0];
my @lowest = nsort_by { /\d+/ && $& }
grep { my ($t, $c) = /(.)(.)=/; $data =~ /\b$c=\d/ and $data =~ /\b$t=\d/ }
$data =~ /$rc\w=\d+|\w$rc=\d+/g;
my ($t, $c) = $lowest[0] =~ /(.)(.)/;
my $allocate = min $data =~ /\b[$t$c]=(\d+)/g;
$table =~ s/$t$c/ sprintf "%2d", $allocate/e;
$cost += $data =~ /$t$c=(\d+)/ && $1 * $allocate;
$data =~ s/\b$_=\K\d+/ $& - $allocate || '' /e for $t, $c;
}
 
say my $result = "cost $cost\n\n" . $table =~ s/[A-Z]{2}/--/gr;</syntaxhighlight>
{{out}}
<pre>cost 170
 
A B C
S 20 -- 5
T -- 30 5</pre>
 
=={{header|Phix}}==
The simplest solution I could think of.<br>
Assumes 0 cost is not allowed, but using say -1 as the "done" cost instead should be fine.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">needs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">avail</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- the costs parameter should be length(avail/*aka suppliers*/) rows
-- of length(needs/*aka customers*/) cols</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">)==</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">avail</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">)==</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">needs</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">avail</span><span style="color: #0000FF;">)))</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">needs</span><span style="color: #0000FF;">)),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">avail</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">supplier</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">customer</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">csc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">csc</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">best</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">csc</span><span style="color: #0000FF;"><</span><span style="color: #000000;">best</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">csc</span>
<span style="color: #000000;">supplier</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
<span style="color: #000000;">customer</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">best</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- all costs examined</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">amt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">avail</span><span style="color: #0000FF;">[</span><span style="color: #000000;">supplier</span><span style="color: #0000FF;">],</span><span style="color: #000000;">needs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">customer</span><span style="color: #0000FF;">])</span>
<span style="color: #000080;font-style:italic;">-- obviously amt can be 0, in which case this just
-- removes cost entry from further consideration.</span>
<span style="color: #000000;">avail</span><span style="color: #0000FF;">[</span><span style="color: #000000;">supplier</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">amt</span>
<span style="color: #000000;">needs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">customer</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">amt</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">supplier</span><span style="color: #0000FF;">,</span><span style="color: #000000;">customer</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">amt</span>
<span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">supplier</span><span style="color: #0000FF;">,</span><span style="color: #000000;">customer</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">solve</span><span style="color: #0000FF;">({</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">35</span><span style="color: #0000FF;">},{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">}})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{{20,0,5},
{0,30,5}}
</pre>
===stepping stones===
Obviously I did not really quite understand the problem when I rattled out the above... this does much better.
{{trans|Go}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Transportation_problem.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">QTY</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">COST</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">R</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">C</span> <span style="color: #000080;font-style:italic;">-- (a shipment)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">eps</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e-12</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">print_matrix</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">total_costs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0.0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">st</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" - "</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">r</span> <span style="color: #008080;">and</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">C</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">c</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">qty</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">round</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">])</span> <span style="color: #000080;font-style:italic;">-- (remove +/-eps)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">qty</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">st</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" %3d "</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">qty</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">total_costs</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">qty</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">COST</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">st</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">total_costs</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">print_result</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">transport</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">expected</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">matrix</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">transport</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Optimal solution\n\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">total_costs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">print_matrix</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nTotal costs: %g (expected %g)\n\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">total_costs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">expected</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">get_neighbors</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">shipment</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">lst</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">nbrs</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lst</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">o</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lst</span><span style="color: #0000FF;">[</span><span style="color: #000000;">e</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">shipment</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">shipment</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">o</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">C</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">shipment</span><span style="color: #0000FF;">[</span><span style="color: #000000;">C</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">o</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">nbrs</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">matrix_to_list</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">l</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">get_closed_path</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">shipment</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">path</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">matrix_to_list</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">path</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prepend</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">,</span><span style="color: #000000;">shipment</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- remove (and keep removing) elements that do not have a
-- vertical AND horizontal neighbor</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">removals</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">nbrs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_neighbors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">[</span><span style="color: #000000;">e</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">path</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">path</span><span style="color: #0000FF;">[</span><span style="color: #000000;">e</span><span style="color: #0000FF;">..</span><span style="color: #000000;">e</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">removals</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">removals</span><span style="color: #0000FF;">==</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000080;font-style:italic;">-- place the remaining elements in the correct plus-minus order</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">stones</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">)),</span>
<span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">shipment</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stones</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">stones</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prev</span>
<span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_neighbors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">path</span><span style="color: #0000FF;">)[</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">stones</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">fix_degenerate_case</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">)+</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])-</span><span style="color: #000000;">1</span> <span style="color: #0000FF;">!=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix_to_list</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"fixing degenerate case...\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dummy</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">eps</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">get_closed_path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dummy</span><span style="color: #0000FF;">))</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dummy</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">matrix</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- ??</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">matrix</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">initialise</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">])</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">cs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">ppf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_StrFmt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_Indent</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"test %d:\nsrc: %v,\ndst: %v,\ncosts: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cs</span><span style="color: #0000FF;">})</span>
<span style="color: #000080;font-style:italic;">-- check for and fix any imbalance</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">totalSrc</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">totalDst</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">diff</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">totalSrc</span><span style="color: #0000FF;">-</span><span style="color: #000000;">totalDst</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">diff</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"adding dummy consumer...\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">dst</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">diff</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">--DEV...
-- costs[i] &= 0</span>
<span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">diff</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"adding dummy supplier...\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">src</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">diff</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">costs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">)))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"generating initial feasible solution using northwest corner method...\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">matrix</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">)),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">))</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">northwest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">northwest</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">qty</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">],</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">qty</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">qty</span><span style="color: #0000FF;">,</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">],</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">qty</span>
<span style="color: #000000;">dst</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">qty</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">northwest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nTotal costs: %g\n\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">print_matrix</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">stepping_stone</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">transport</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">transport</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">maxReduction</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">move</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">leaving</span>
<span style="color: #000000;">matrix</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">fix_degenerate_case</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">trial_shipment</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">path</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_closed_path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">,</span><span style="color: #000000;">trial_shipment</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">reduction</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0.0</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">lowestQuantity</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e308</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">leavingCandidate</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">plus</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">path</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">plus</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">reduction</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">COST</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">reduction</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">COST</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">lowestQuantity</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">leavingCandidate</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
<span style="color: #000000;">lowestQuantity</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">plus</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">not</span> <span style="color: #000000;">plus</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">reduction</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">maxReduction</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">move</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">path</span>
<span style="color: #000000;">leaving</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">leavingCandidate</span>
<span style="color: #000000;">maxReduction</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduction</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">move</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">leaving</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">plus</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">move</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">plus</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">q</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">q</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">C</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">C</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">plus</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">not</span> <span style="color: #000000;">plus</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stepping_stone</span><span style="color: #0000FF;">({</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">-- -- source dest costs expected total</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">35</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">180</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #000000;">33</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">130</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #000000;">35</span><span style="color: #0000FF;">,</span><span style="color: #000000;">45</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">1000</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">300</span><span style="color: #0000FF;">,</span><span style="color: #000000;">300</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">300</span><span style="color: #0000FF;">,</span><span style="color: #000000;">200</span><span style="color: #0000FF;">,</span><span style="color: #000000;">200</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">80</span><span style="color: #0000FF;">,</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">90</span><span style="color: #0000FF;">,</span><span style="color: #000000;">70</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">39000</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #000000;">60</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">920</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">68</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">18</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">70</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #000000;">60</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">70</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">743</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">17</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">259</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">60</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">70</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">60</span><span style="color: #0000FF;">},{{</span><span style="color: #000000;">16</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">22</span><span style="color: #0000FF;">,</span><span style="color: #000000;">17</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">23</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">3100</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">75</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">60</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">610</span><span style="color: #0000FF;">}}</span>
<span style="color: #000080;font-style:italic;">--for i=1 to length(tests) do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">print_result</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stepping_stone</span><span style="color: #0000FF;">(</span><span style="color: #000000;">initialise</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">4</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #008000;">"done"</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
(Obviously the other eight tests all work fine and produce similar output.)
<pre>
test 3:
src: {14,10,15,12},
dst: {10,15,12,15},
costs: {{10,30,25,15},
{20,15,20,10},
{10,30,20,20},
{30,40,35,45}}
 
adding dummy supplier...
generating initial feasible solution using northwest corner method...
10 4 - -
- 10 - -
- 1 12 2
- - - 12
- - - 1
 
Total costs: 1220
 
fixing degenerate case...
Optimal solution
 
- - - 14
- 9 - 1
10 - 5 -
- 5 7 -
- 1 - -
 
Total costs: 1000 (expected 1000)
</pre>
Note that [[Vogel%27s_approximation_method#Phix]] gets a few of the others wrong and loops on #2, then again that is unbalanced (needs a dummy customer), and I'm not sure whether throwing such at VAM is fair or not.
 
=={{header|R}}==
Using <code>lpSolve::lp.transport</code>.
 
<syntaxhighlight lang="r">library(lpSolve)
 
# cost matrix
costs <- matrix(c(3, 5, 7,
3, 2, 5), nrow = 2, byrow = TRUE)
 
# constraints for suppliers
row.signs <- rep("<=", 2)
row.rhs <- c(25, 35)
# constraints for customers
col.signs <- rep("=", 3)
col.rhs <- c(20, 30, 10)
 
# minimum cost (objective value)
lp.transport(costs, "min", row.signs, row.rhs, col.signs, col.rhs)
# solution matrix
sol = lp.transport(costs, "min", row.signs, row.rhs, col.signs, col.rhs)$solution
rownames(sol) <- c("Supplier 1", "Supplier 2")
colnames(sol) <- c("Customer 1", "Customer 2", "Customer 3")
sol </syntaxhighlight>
{{out}}
<pre>Success: the objective function is 180
 
Customer 1 Customer 2 Customer 3
Supplier 1 20 0 5
Supplier 2 0 30 5
</pre>
 
=={{header|Racket}}==
{{trans|Java}} (I understand the letters in Java!)
 
Using <code>typed/racket</code>, to keep track of Vectors of Vectors of data.
<lang racket>
 
</lang>
<syntaxhighlight lang="racket">#lang typed/racket
;; {{trans|Java}}
(define-type (V2 A) (Vectorof (Vectorof A)))
(define-type VI (Vectorof Integer))
(define-type V2R (V2 Real))
(define-type Q (U 'ε Integer))
(define ε 'ε)
(struct Shipment ([qty : Q] [cost/unit : Real] [r : Integer] [c : Integer]))
(define-type Shipment/? (Option Shipment))
(define-type V2-Shipment/? (V2 Shipment/?))
(define-type Shipment/?s (Listof Shipment/?))
(define-type Shipments (Listof Shipment))
 
(: Q+ (Q Q -> Q))
(: Q- (Q Q -> Q))
(: Q<? (Q Q -> Boolean))
(: Q-zero? (Q -> Boolean))
(: Q-unary- (Q -> Q))
(: Q*R (Q Real -> Real))
 
(define Q+ (match-lambda** [('ε 0) ε] [(0 'ε) ε] [('ε 'ε) ε] [('ε x) x] [(x 'ε) x]
[((? integer? x) (? integer? y)) (+ x y)]))
 
(define Q<? (match-lambda** [('ε 0) #f] [(0 'ε) #t] [('ε 'ε) #f] [('ε x) #t] [(x 'ε) #f]
[((? integer? x) (? integer? y)) (< x y)]))
 
(define Q- (match-lambda** [('ε 0) ε] [(0 'ε) ε] [('ε 'ε) 0] [('ε (? integer? x)) (- x)] [(x 'ε) x]
[((? integer? x) (? integer? y)) (- x y)]))
 
(define Q-unary- (match-lambda ['ε ε] [(? integer? x) (- x)]))
 
(define Q-zero? (match-lambda ['ε #f] [(? integer? x) (zero? x)]))
 
(define Q*R (match-lambda** [('ε _) 0] [((? integer? x) y) (* x y)]))
 
(: vector-ref2 (All (A) ((Vectorof (Vectorof A)) Integer Integer -> A)))
(define (vector-ref2 v2 r c) (vector-ref (vector-ref v2 r) c))
 
(: vector-set!2 (All (A) ((Vectorof (Vectorof A)) Integer Integer A -> Void)))
(define (vector-set!2 v2 r c v) (vector-set! (vector-ref v2 r) c v))
 
(define (northwest-corner-rule! [supply : VI] [demand : VI] [costs : V2R] [M : V2-Shipment/?]) : Void
(define supply-l (vector-length supply))
(define demand-l (vector-length demand))
(let loop ((r 0) (nw 0) (c 0))
(cond [(= r supply-l) (void)]
[(= c demand-l) (loop (add1 r) nw 0)]
[else
(define quantity (min (vector-ref supply r) (vector-ref demand c)))
(cond
[(positive? quantity)
(define shpmnt (Shipment quantity (vector-ref2 costs r c) r c))
(vector-set!2 M r c shpmnt)
(define supply-- (- (vector-ref supply r) quantity))
(define demand-- (- (vector-ref demand c) quantity))
(vector-set! supply r supply--)
(vector-set! demand c demand--)
(if (zero? supply--) (loop (add1 r) c 0) (loop r nw (add1 c)))]
[else (loop r nw (add1 c))])])))
 
(define (stepping-stone! [supply : VI] [demand : VI] [costs : V2R] [M : V2-Shipment/?]) : Void
(fix-degenerate-case! supply demand costs M)
(define-values (move leaving max-reduction)
(for*/fold : (Values Shipments Shipment/? Real)
((move : Shipments null) (leaving : Shipment/? #f) (max-reduction : Real 0))
((r (vector-length supply))
(c (vector-length demand))
(m (in-value (vector-ref2 M r c)))
#:unless m)
(define path (let ((trial (Shipment 0 (vector-ref2 costs r c) r c))) (get-closed-path trial M)))
(define-values (+? reduction leaving-cand lowest-quantity)
(for/fold : (Values Boolean Real Shipment/? (Option Q))
((+? #t) (reduction : Real 0) (leaving-cand : Shipment/? #f) (lowest-q : (Option Q) #f))
((s (in-list path)))
(define s.cpu (Shipment-cost/unit s))
(if +?
(values #f (+ reduction s.cpu) leaving-cand lowest-q)
(let ((reduction-- (- reduction s.cpu))
(s.q (Shipment-qty s)))
(if (or (not lowest-q) (Q<? s.q lowest-q))
(values #t reduction-- s s.q)
(values #t reduction-- leaving-cand lowest-q))))))
(if (< reduction max-reduction)
(values path leaving-cand reduction)
(values move leaving max-reduction))))
(unless (null? move)
(define l.q (Shipment-qty (cast leaving Shipment)))
(for/fold ((+? : Boolean #t)) ((s (in-list move)))
(define s.q+ ((if +? Q+ Q-) (Shipment-qty s) l.q))
(define s+ (struct-copy Shipment s [qty s.q+]))
(vector-set!2 M (Shipment-r s+) (Shipment-c s+) (if (Q-zero? s.q+) #f s+))
(not +?))
(stepping-stone! supply demand costs M)))
 
(: matrix->list (All (T) ((V2 T) -> (Listof T))))
(define (matrix->list m)
(for*/list : (Listof T) ((r (in-vector m)) (c (in-vector r)) #:when c)
c))
 
(define (fix-degenerate-case! [supply : VI] [demand : VI] [costs : V2R] [M : V2-Shipment/?]) : Void
(define m-list (matrix->list M))
(unless (= (+ (vector-length supply) (vector-length demand) -1) (length m-list))
(let/ec ret : Void
(for* ((r (vector-length supply)) (c (vector-length demand)) #:unless (vector-ref2 M r c))
(define dummy (Shipment ε (vector-ref2 costs r c) r c))
(when (null? (get-closed-path dummy M))
(vector-set!2 M r c dummy)
(ret (void)))))))
 
(: get-closed-path (Shipment V2-Shipment/? -> Shipments))
(define (get-closed-path s matrix)
; remove (and keep removing) elements that do not have a vertical AND horizontal neighbour
(define path
(let loop : Shipment/?s
((path (cons s (matrix->list matrix))))
(define (has-neighbours [e : Shipment/?]) : Boolean
(match-define (list n0 n1) (get-neighbours e path))
(and n0 n1 #t))
(define-values (with-nbrs w/o-nbrs)
((inst partition Shipment/? Shipment/?) has-neighbours path))
(if (null? w/o-nbrs) with-nbrs (loop with-nbrs))))
;; place the remaining elements in the correct plus-minus order
(define p-len (length path))
(define-values (senots prev)
(for/fold : (Values Shipments Shipment/?)
((senots : Shipments null) (prev : Shipment/? s))
((i p-len))
(values (if prev (cons prev senots) senots)
(list-ref (get-neighbours prev path) (modulo i 2)))))
(reverse senots))
 
(define (get-neighbours [s : Shipment/?] [lst : Shipment/?s]) : (List Shipment/? Shipment/?)
(define-values (n0 n1)
(for/fold : (Values Shipment/? Shipment/?)
((n0 : Shipment/? #f) (n1 : Shipment/? #f))
((o (in-list lst)) #:when (and o s) #:unless (equal? o s))
(values (or n0 (and (= (Shipment-r s) (Shipment-r o)) o))
(or n1 (and (= (Shipment-c s) (Shipment-c o)) o)))))
(list n0 n1))
 
(define (print-result [S : VI] [D : VI] [M : V2-Shipment/?] [fmt : String] . [args : Any *]) : Real
(apply printf (string-append fmt "~%") args)
(define total-costs
(for*/sum : Real
((r (vector-length S)) (c (vector-length D)))
(when (zero? c) (unless (zero? r) (newline)))
(define s (vector-ref2 M r c))
(cond
[(and s (= (Shipment-r s) r) (= (Shipment-c s) c))
(define q (Shipment-qty s))
(printf "\t~a" q)
(Q*R q (Shipment-cost/unit s))]
[else (printf "\t-") 0])))
(printf "~%Total costs: ~a~%~%" total-costs)
total-costs)
 
;; inits from current-input-port --- make sure you set that before coming in
(define (init) : (Values VI VI V2R V2-Shipment/?)
(define n-sources (cast (read) Integer))
(define n-destinations (cast (read) Integer))
(define srcs. (for/list : (Listof Integer) ((_ n-sources)) (cast (read) Integer)))
(define dsts. (for/list : (Listof Integer) ((_ n-destinations)) (cast (read) Integer)))
(define sum-src--sum-dest (- (apply + srcs.) (apply + dsts.)))
(define-values (supply demand)
(cond [(positive? sum-src--sum-dest) (values srcs. (append dsts. (list sum-src--sum-dest)))]
[(negative? sum-src--sum-dest) (values (append srcs. (list (- sum-src--sum-dest))) dsts.)]
[else (values srcs. dsts.)]))
(define s-l (length supply))
(define d-l (length demand))
(define costs (for/vector : V2R ((_ s-l)) ((inst make-vector Real) d-l 0)))
(define matrix (for/vector : V2-Shipment/? ((_ s-l)) ((inst make-vector Shipment/?) d-l #f)))
(for* ((i n-sources) (j n-destinations)) (vector-set!2 costs i j (cast (read) Real)))
(values (list->vector supply) (list->vector demand) costs matrix))
 
(: transportation-problem (Input-Port -> Real))
(define (transportation-problem p)
(parameterize ([current-input-port p])
(define name (read))
(define-values (supply demand costs matrix) (init))
(northwest-corner-rule! supply demand costs matrix)
(stepping-stone! supply demand costs matrix)
(print-result supply demand matrix "Optimal solutions for: ~s" name)))
 
(module+ test
(require typed/rackunit)
(define (check-tp [in-str : String] [expected-cost : Real])
(define cost ((inst call-with-input-string Real) in-str transportation-problem))
(check-equal? cost expected-cost))
 
(check-tp #<<$
input1
2 3
25 35
20 30 10
3 5 7
3 2 5
$
180)
(check-tp #<<$
input2
3 3
12 40 33
20 30 10
3 5 7
2 4 6
9 1 8
$
130)
 
(check-tp #<<$
input3
4 4
14 10 15 12
10 15 12 15
10 30 25 15
20 15 20 10
10 30 20 20
30 40 35 45
$
1000))</syntaxhighlight>
{{out}}
Output of: <code>raco test Transportation-problem.rkt</code>:
Line 1,978 ⟶ 4,152:
 
3 tests passed
</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2019.03.1}}
Using [[Vogel's_approximation_method#Raku|Vogel's approximation method]]:
<syntaxhighlight lang="raku" line>my %costs = :S1{:3C1, :5C2, :7C3}, :S2{:3C1, :2C2, :5C3};
my %demand = :20C1, :30C2, :10C3;
my %supply = :25S1, :35S2;
 
my @cols = %demand.keys.sort;
 
my %res;
my %g = (|%supply.keys.map: -> $x { $x => [%costs{$x}.sort(*.value)».key]}),
(|%demand.keys.map: -> $x { $x => [%costs.keys.sort({%costs{$_}{$x}})]});
 
while (+%g) {
my @d = %demand.keys.map: -> $x
{[$x, my $z = %costs{%g{$x}[0]}{$x},%g{$x}[1] ?? %costs{%g{$x}[1]}{$x} - $z !! $z]}
 
my @s = %supply.keys.map: -> $x
{[$x, my $z = %costs{$x}{%g{$x}[0]},%g{$x}[1] ?? %costs{$x}{%g{$x}[1]} - $z !! $z]}
 
@d = |@d.grep({ (.[2] == max @d».[2]) }).&min: :by(*.[1]);
@s = |@s.grep({ (.[2] == max @s».[2]) }).&min: :by(*.[1]);
 
my ($t, $f) = @d[2] == @s[2] ?? (@s[1],@d[1]) !! (@d[2],@s[2]);
my ($d, $s) = $t > $f ?? (@d[0],%g{@d[0]}[0]) !! (%g{@s[0]}[0], @s[0]);
 
my $v = %supply{$s} min %demand{$d};
 
%res{$s}{$d} += $v;
%demand{$d} -= $v;
 
if (%demand{$d} == 0) {
%supply.grep( *.value != 0 )».key.map: -> $v
{ %g{$v}.splice((%g{$v}.first: * eq $d, :k),1) };
%g{$d}:delete;
%demand{$d}:delete;
}
 
%supply{$s} -= $v;
 
if (%supply{$s} == 0) {
%demand.grep( *.value != 0 )».key.map: -> $v
{ %g{$v}.splice((%g{$v}.first: * eq $s, :k),1) };
%g{$s}:delete;
%supply{$s}:delete;
}
}
 
say join "\t", flat '', @cols;
my $total;
for %costs.keys.sort -> $g {
print "$g\t";
for @cols -> $col {
print %res{$g}{$col} // '-', "\t";
$total += (%res{$g}{$col} // 0) * %costs{$g}{$col};
}
print "\n";
}
say "\nTotal cost: $total";</syntaxhighlight>
{{out}}
<pre> C1 C2 C3
S1 20 - 5
S2 - 30 5 </pre>
 
=={{header|REXX}}==
{{trans|Java}}
<syntaxhighlight lang="rexx">/* REXX ***************************************************************
* Solve the Transportation Problem using the Northwest Corner Method
Default Input
2 3 # of sources / # of demands
25 35 sources
20 30 10 demands
3 5 7 cost matrix
3 2 5
* 20201210 support no input file -courtesy GS
* Note: correctnes of input is not checked
* 20201226 add optimization
* 20210103 remove debug code
**********************************************************************/
Signal On Halt
Signal On Novalue
Signal On Syntax
 
Parse Arg fid
If fid='' Then
fid='input1.txt'
Call init
matrix.=0
ms=0
Do r=1 To rr
Do c=1 To cc
matrix.r.c=r c cost.r.c 0
End
End
r=1
c=1
Do While r<=rr & c<=cc
q=min(source.r,demand.c)
matrix.r.c=r c cost.r.c q
source.r=source.r-q
demand.c=demand.c-q
If source.r=0 Then r=r+1
If demand.c=0 Then c=c+1
End
Call show_alloc 'after NWC application'
Call steppingstone
Exit
 
/**********************************************************************
* Subroutines for NWC Algorithm
**********************************************************************/
 
init:
If lines(fid)=0 Then Do
Say 'Input file not specified or not found. Using default input instead.'
fid='Default input'
in.1=sourceline(4)
Parse Var in.1 numSources .
Do i=2 To numSources+3
in.i=sourceline(i+3)
End
End
Else Do
Do i=1 By 1 while lines(fid)>0
in.i=linein(fid)
End
End
Parse Var in.1 numSources numDestinations . 1 rr cc .
source_sum=0
Do i=1 To numSources
Parse Var in.2 source.i in.2
ss.i=source.i
source_in.i=source.i
source_sum=source_sum+source.i
End
l=linein(fid)
demand_sum=0
Do i=1 To numDestinations
Parse Var in.3 demand.i in.3
dd.i=demand.i
demand_in.i=demand.i
demand_sum=demand_sum+demand.i
End
Do i=1 To numSources
j=i+3
l=in.j
Do j=1 To numDestinations
Parse Var l cost.i.j l
End
End
Do i=1 To numSources
ol=format(source.i,3)
Do j=1 To numDestinations
ol=ol format(cost.i.j,4)
End
End
ol=' '
Do j=1 To numDestinations
ol=ol format(demand.j,4)
End
 
Select
When source_sum=demand_sum Then Nop /* balanced */
When source_sum>demand_sum Then Do /* unbalanced - add dummy demand */
Say 'This is an unbalanced case (sources exceed demands). We add a dummy consumer.'
cc=cc+1
demand.cc=source_sum-demand_sum
demand_in.cc=demand.cc
dd.cc=demand.cc
Do r=1 To rr
cost.r.cc=0
End
End
Otherwise /* demand_sum>source_sum */ Do /* unbalanced - add dummy source */
Say 'This is an unbalanced case (demands exceed sources). We add a dummy source.'
rr=rr+1
source.rr=demand_sum-source_sum
source_in.rr=source.rr
ss.rr=source.rr
Do c=1 To cc
cost.rr.c=0
End
End
End
Say 'Sources / Demands / Cost'
ol=' '
Do c=1 To cc
ol=ol format(demand.c,3)
End
Say ol
 
Do r=1 To rr
ol=format(source.r,4)
Do c=1 To cc
ol=ol format(cost.r.c,3)
End
Say ol
End
Return
 
show_alloc: Procedure Expose matrix. rr cc demand_in. source_in.
Parse Arg header
If header='' Then
Return
Say ''
Say header
total=0
ol=' '
Do c=1 to cc
ol=ol format(demand_in.c,3)
End
Do r=1 to rr
ol=format(source_in.r,4)
a=word(matrix.r.1,4)
If a>0 Then
ol=format(a,4)
Else
ol=' - '
total=total+word(matrix.r.1,4)*word(matrix.r.1,3)
Do c=2 To cc
a=word(matrix.r.c,4)
If a>0 Then
ol=ol format(a,4)
Else
ol=ol ' - '
total=total+word(matrix.r.c,4)*word(matrix.r.c,3)
End
Say ol
End
Say 'Total costs:' format(total,4,1)
Return
 
/**********************************************************************
* Subroutines for Optimization
**********************************************************************/
 
steppingstone: Procedure Expose matrix. cost. rr cc demand_in.,
source_in. fid
maxReduction=0
move=''
 
Call fixDegenerateCase
 
Do r=1 To rr
Do c=1 To cc
Parse Var matrix.r.c r c cost qrc
If qrc=0 Then Do
path=getclosedpath(r,c)
reduction = 0
lowestQuantity = 1e10
leavingCandidate = ''
plus=1
pathx=path
Do While pathx<>''
Parse Var pathx s '|' pathx
If plus Then
reduction=reduction+word(s,3)
Else Do
reduction=reduction-word(s,3)
If word(s,4)<lowestQuantity Then Do
leavingCandidate = s
lowestQuantity = word(s,4)
End
End
plus=\plus
End
If reduction < maxreduction Then Do
move=path
leaving=leavingCandidate
maxReduction = reduction
End
End
End
End
if move <> '' Then Do
quant=word(leaving,4)
plus=1
Do While move<>''
Parse Var move m '|' move
Parse Var m r c cpu qrc
Parse Var matrix.r.c vr vc vcost vquant
If plus Then
nquant=vquant+quant
Else
nquant=vquant-quant
matrix.r.c = vr vc vcost nquant
plus=\plus
End
move=''
Call steppingStone
End
Else Do
Call show_alloc 'Optimal Solution' fid
End
Return
 
getclosedpath: Procedure Expose matrix. cost. rr cc
Parse Arg rd,cd
path=rd cd cost.rd.cd word(matrix.rd.cd,4)
do r=1 To rr
Do c=1 To cc
If word(matrix.r.c,4)>0 Then Do
path=path'|'r c cost.r.c word(matrix.r.c,4)
End
End
End
path=magic(path)
Return stones(path)
 
magic: Procedure
Parse Arg list
Do Forever
list_1=remove_1(list)
If list_1=list Then Leave
list=list_1
End
Return list_1
 
remove_1: Procedure
Parse Arg list
cntr.=0
cntc.=0
Do i=1 By 1 While list<>''
parse Var list e.i '|' list
Parse Var e.i r c .
cntr.r=cntr.r+1
cntc.c=cntc.c+1
End
n=i-1
keep.=1
Do i=1 To n
Parse Var e.i r c .
If cntr.r<2 |,
cntc.c<2 Then Do
keep.i=0
End
End
list=e.1
Do i=2 To n
If keep.i Then
list=list'|'e.i
End
Return list
 
stones: Procedure
Parse Arg lst
tstc=lst
Do i=1 By 1 While tstc<>''
Parse Var tstc o.i '|' tstc
end
stones=lst
o.0=i-1
prev=o.1
Do i=1 To o.0
st.i=prev
k=i//2
nbrs=getNeighbors(prev, lst)
Parse Var nbrs n.1 '|' n.2
If k=0 Then
prev=n.2
Else
prev=n.1
End
stones=st.1
Do i=2 To o.0
stones=stones'|'st.i
End
Return stones
 
getNeighbors: Procedure
parse Arg s, lst
Do i=1 By 1 While lst<>''
Parse Var lst o.i '|' lst
End
o.0=i-1
nbrs.=''
sr=word(s,1)
sc=word(s,2)
Do i=1 To o.0
If o.i<>s Then Do
or=word(o.i,1)
oc=word(o.i,2)
If or=sr & nbrs.0='' Then
nbrs.0 = o.i
else if oc=sc & nbrs.1='' Then
nbrs.1 = o.i
If nbrs.0<>'' & nbrs.1<>'' Then
Leave
End
End
return nbrs.0'|'nbrs.1
 
pelems: Procedure
Parse Arg p
Do i=1 By 1 While p<>''
Parse Var p x '|' p
End
Return i
 
fixDegenerateCase: Procedure Expose matrix. rr cc ms
Call matrixtolist
If (rr+cc-1)<>ms Then Do
Do r=1 To rr
Do c=1 To cc
If word(matrix.r.c,4)=0 Then Do
matrix.r.c=subword(matrix.r.c,1,3) 1.e-10
Return
End
End
End
End
Return
 
matrixtolist: Procedure Expose matrix. rr cc ms
ms=0
list=''
Do r=1 To rr
Do c=1 To cc
If word(matrix.r.c,4)>0 Then Do
list=list'|'matrix.r.c
ms=ms+1
End
End
End
Return strip(list,,'|')
 
Novalue:
Say 'Novalue raised in line' sigl
Say sourceline(sigl)
Say 'Variable' condition('D')
Signal lookaround
 
Syntax:
Say 'Syntax raised in line' sigl
Say sourceline(sigl)
Say 'rc='rc '('errortext(rc)')'
 
halt:
lookaround:
If fore() Then Do
Say 'You can look around now.'
Trace ?R
Nop
End
Exit 12</syntaxhighlight>
{{out}}
<pre>F:\>rexx tpx2 input1.txt
Sources / Demands / Cost
20 30 10
25 3 5 7
35 3 2 5
 
after NWC application
20 5 -
- 25 10
Total costs: 185.0
 
Optimal Solution input1.txt
20 - 5
- 30 5
Total costs: 180.0
 
F:\>rexx tpx2 input2.txt
This is an unbalanced case (sources exceed demands). We add a dummy consumer.
Sources / Demands / Cost
20 30 10 25
12 3 5 7 0
40 2 4 6 0
33 9 1 8 0
 
after NWC application
12 - - -
8 30 2 -
- - 8 25
Total costs: 248.0
 
Optimal Solution input2.txt
- - - 12
20 - 10 10
- 30 - 3
Total costs: 130.0
 
F:\>rexx tpx2 input3.txt
This is an unbalanced case (demands exceed sources). We add a dummy source.
Sources / Demands / Cost
10 15 12 15
14 10 30 25 15
10 20 15 20 10
15 10 30 20 20
12 30 40 35 45
1 0 0 0 0
 
after NWC application
10 4 - -
- 10 - -
- 1 12 2
- - - 12
- - - 1
Total costs: 1220.0
 
Optimal Solution input3.txt
- - - 14
- 9 - 1
10 - 5 -
- 5 7 -
- 1 - -
Total costs: 1000.0</pre>
 
=={{header|SAS}}==
Use network solver in SAS/OR:
 
<syntaxhighlight lang="sas">/* create SAS data sets */
data cost_data;
input from $ to $ cost;
datalines;
s1 c1 3
s1 c2 5
s1 c3 7
s2 c1 3
s2 c2 2
s2 c3 5
;
 
data supply_data;
input node $ supply;
datalines;
s1 25
s2 35
c1 -20
c2 -30
c3 -10
;
 
/* call OPTMODEL procedure in SAS/OR */
proc optmodel;
/* declare sets and parameters, and read input data */
set <str,str> LINKS;
num cost {LINKS};
read data cost_data into LINKS=[from to] cost;
set NODES = union {<i,j> in LINKS} {i,j};
num supply {NODES} init 0;
read data supply_data into [node] supply;
num flow {LINKS};
 
/* call network solver */
solve with network /
mincostflow links=(weight=cost) nodes=(weight=supply) direction=directed out=(flow=flow);
 
/* print optimal solution */
print _OROPTMODEL_NUM_['OBJECTIVE'];
print flow;
quit;</syntaxhighlight>
 
Output:
<pre>
180
 
flow
c1 c2 c3
s1 20 0 5
s2 0 30 5
</pre>
 
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">Module Module1
 
Class Shipment
Public Sub New(q As Double, cpu As Double, rv As Integer, cv As Integer)
Quantity = q
CostPerUnit = cpu
R = rv
C = cv
End Sub
 
Public ReadOnly Property CostPerUnit() As Double
 
Public Property Quantity() As Double
 
Public ReadOnly Property R As Integer
 
Public ReadOnly Property C As Integer
 
Public Shared Operator =(s1 As Shipment, s2 As Shipment) As Boolean
Return s1.CostPerUnit = s2.CostPerUnit _
AndAlso s1.Quantity = s2.Quantity _
AndAlso s1.R = s2.R _
AndAlso s1.C = s2.C
End Operator
 
Public Shared Operator <>(s1 As Shipment, s2 As Shipment) As Boolean
Return s1.CostPerUnit <> s2.CostPerUnit _
OrElse s1.Quantity <> s2.Quantity _
OrElse s1.R <> s2.R _
OrElse s1.C <> s2.C
End Operator
End Class
 
Class Program
Private demand() As Integer
Private supply() As Integer
Private costs(,) As Double
Private matrix(,) As Shipment
 
Sub Init(filename As String)
Dim file = My.Computer.FileSystem.OpenTextFileReader(filename)
Dim line = file.ReadLine
Dim numArr = line.Split
Dim numSources = Integer.Parse(numArr(0))
Dim numDestinations = Integer.Parse(numArr(1))
 
Dim src As New List(Of Integer)
Dim dst As New List(Of Integer)
 
line = file.ReadLine
numArr = line.Split
For i = 1 To numSources
src.Add(Integer.Parse(numArr(i - 1)))
Next
 
line = file.ReadLine
numArr = line.Split
For i = 1 To numDestinations
dst.Add(Integer.Parse(numArr(i - 1)))
Next
 
REM fix imbalance
Dim totalSrc = src.Sum
Dim totalDst = dst.Sum
If totalSrc > totalDst Then
dst.Add(totalSrc - totalDst)
ElseIf totalDst > totalSrc Then
src.Add(totalDst - totalSrc)
End If
 
supply = src.ToArray
demand = dst.ToArray
 
ReDim costs(supply.Length - 1, demand.Length - 1)
ReDim matrix(supply.Length - 1, demand.Length - 1)
 
For i = 1 To numSources
line = file.ReadLine
numArr = line.Split
For j = 1 To numDestinations
costs(i - 1, j - 1) = Integer.Parse(numArr(j - 1))
Next
Next
End Sub
 
Sub NorthWestCornerRule()
Dim northwest = 1
For r = 1 To supply.Length
For c = northwest To demand.Length
Dim quantity = Math.Min(supply(r - 1), demand(c - 1))
If quantity > 0 Then
matrix(r - 1, c - 1) = New Shipment(quantity, costs(r - 1, c - 1), r - 1, c - 1)
 
supply(r - 1) -= quantity
demand(c - 1) -= quantity
 
If supply(r - 1) = 0 Then
northwest = c
Exit For
End If
End If
Next
Next
End Sub
 
Sub SteppingStone()
Dim maxReduction = 0.0
Dim move() As Shipment = Nothing
Dim leaving As Shipment = Nothing
 
FixDegenerateCase()
 
For r = 1 To supply.Length
For c = 1 To demand.Length
If Not IsNothing(matrix(r - 1, c - 1)) Then
Continue For
End If
 
Dim trial As New Shipment(0, costs(r - 1, c - 1), r - 1, c - 1)
Dim path = GetClosedPath(trial)
 
Dim reduction = 0.0
Dim lowestQuanity = Integer.MaxValue
Dim leavingCandidate As Shipment = Nothing
 
Dim plus = True
For Each s In path
If plus Then
reduction += s.CostPerUnit
Else
reduction -= s.CostPerUnit
If s.Quantity < lowestQuanity Then
leavingCandidate = s
lowestQuanity = s.Quantity
End If
End If
plus = Not plus
Next
If reduction < maxReduction Then
move = path
leaving = leavingCandidate
maxReduction = reduction
End If
Next
Next
 
If Not IsNothing(move) Then
Dim q = leaving.Quantity
Dim plus = True
For Each s In move
s.Quantity += If(plus, q, -q)
matrix(s.R, s.C) = If(s.Quantity = 0, Nothing, s)
plus = Not plus
Next
SteppingStone()
End If
End Sub
 
Sub FixDegenerateCase()
Const eps = Double.Epsilon
If supply.Length + demand.Length - 1 <> MatrixToList().Count Then
For r = 1 To supply.Length
For c = 1 To demand.Length
If IsNothing(matrix(r - 1, c - 1)) Then
Dim dummy As New Shipment(eps, costs(r - 1, c - 1), r - 1, c - 1)
If GetClosedPath(dummy).Length = 0 Then
matrix(r - 1, c - 1) = dummy
Return
End If
End If
Next
Next
End If
End Sub
 
Function MatrixToList() As List(Of Shipment)
Dim newList As New List(Of Shipment)
For Each item In matrix
If Not IsNothing(item) Then
newList.Add(item)
End If
Next
Return newList
End Function
 
Function GetClosedPath(s As Shipment) As Shipment()
Dim path = MatrixToList()
path.Add(s)
 
REM remove (and keep removing) elements that do not have a veritcal AND horizontal neighbor
Dim before As Integer
Do
before = path.Count
path.RemoveAll(Function(ship)
Dim nbrs = GetNeighbors(ship, path)
Return IsNothing(nbrs(0)) OrElse IsNothing(nbrs(1))
End Function)
Loop While before <> path.Count
 
REM place the remaining elements in the correct plus-minus order
Dim stones = path.ToArray
Dim prev = s
For i = 1 To stones.Length
stones(i - 1) = prev
prev = GetNeighbors(prev, path)((i - 1) Mod 2)
Next
Return stones
End Function
 
Function GetNeighbors(s As Shipment, lst As List(Of Shipment)) As Shipment()
Dim nbrs() As Shipment = {Nothing, Nothing}
For Each o In lst
If o <> s Then
If o.R = s.R AndAlso IsNothing(nbrs(0)) Then
nbrs(0) = o
ElseIf o.C = s.C AndAlso IsNothing(nbrs(1)) Then
nbrs(1) = o
End If
If Not IsNothing(nbrs(0)) AndAlso Not IsNothing(nbrs(1)) Then
Exit For
End If
End If
Next
Return nbrs
End Function
 
Sub PrintResult(filename As String)
Console.WriteLine("Optimal solution {0}" + vbNewLine, filename)
Dim totalCosts = 0.0
 
For r = 1 To supply.Length
For c = 1 To demand.Length
Dim s = matrix(r - 1, c - 1)
If Not IsNothing(s) AndAlso s.R = r - 1 AndAlso s.C = c - 1 Then
Console.Write(" {0,3} ", s.Quantity)
totalCosts += (s.Quantity * s.CostPerUnit)
Else
Console.Write(" - ")
End If
Next
Console.WriteLine()
Next
Console.WriteLine(vbNewLine + "Total costs: {0}" + vbNewLine, totalCosts)
End Sub
End Class
 
Sub Main()
For Each filename In {"input1.txt", "input2.txt", "input3.txt"}
Dim p As New Program
p.Init(filename)
p.NorthWestCornerRule()
p.SteppingStone()
p.PrintResult(filename)
Next
End Sub
 
End Module</syntaxhighlight>
{{out}}
<pre>Optimal solution input1.txt
 
20 - 5
- 30 5
 
Total costs: 180
 
Optimal solution input2.txt
 
- - - 12
20 - 10 10
- 30 - 3
 
Total costs: 130
 
Optimal solution input3.txt
 
- - - 14
- 9 - 1
10 - 5 -
- 5 7 -
- 1 - -
 
Total costs: 1000</pre>
 
=={{header|Wren}}==
{{trans|Java}}
{{libheader|Wren-dynamic}}
{{libheader|Wren-ioutil}}
{{libheader|Wren-math}}
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./dynamic" for Struct
import "./ioutil" for FileUtil, File
import "./math" for Nums
import "./seq" for Lst
import "./fmt" for Fmt
 
var Shipment = Struct.create("Shipment", ["quantity", "costPerUnit", "r", "c"])
 
class Transport {
construct new(filename) {
var lines = FileUtil.readLines(filename)
var split = lines[0].split(" ")
var numSources = Num.fromString(split[0])
var numDests = Num.fromString(split[1])
var src = List.filled(numSources, 0)
var dst = List.filled(numDests, 0)
split = lines[1].split(" ")
for (i in 0...numSources) src[i] = Num.fromString(split[i])
split = lines[2].split(" ")
for (i in 0...numDests) dst[i] = Num.fromString(split[i])
 
// fix imbalance
var totalSrc = Nums.sum(src)
var totalDst = Nums.sum(dst)
if (totalSrc > totalDst) {
dst.add(totalSrc - totalDst)
} else if (totalDst > totalSrc) {
src.add(totalDst - totalSrc)
}
_supply = src
_demand = dst
_costs = List.filled(_supply.count, null)
_matrix = List.filled(_supply.count, null)
for (i in 0..._supply.count) {
_costs[i] = List.filled(_demand.count, 0)
_matrix[i] = List.filled(_demand.count, null)
}
for (i in 0...numSources) {
split = lines[i + 3].split(" ")
for (j in 0...numDests) _costs[i][j] = Num.fromString(split[j])
}
_filename = filename
}
 
northWestCornerRule() {
var northwest = 0
for (r in 0..._supply.count) {
var c = northwest
while (c < _demand.count) {
var quantity = _supply[r].min(_demand[c])
if (quantity > 0) {
_matrix[r][c] = Shipment.new(quantity, _costs[r][c], r, c)
_supply[r] = _supply[r] - quantity.floor
_demand[c] = _demand[c] - quantity.floor
if (_supply[r] == 0) {
northwest = c
break
}
}
c = c + 1
}
}
}
 
steppingStone() {
var maxReduction = 0
var move = null
var leaving = null
fixDegenerateCase_()
 
for (r in 0..._supply.count) {
for (c in 0..._demand.count) {
if (_matrix[r][c] != null) continue
var trial = Shipment.new(0, _costs[r][c], r, c)
var path = getClosedPath_(trial)
var reduction = 0
var lowestQuantity = Num.maxSafeInteger
var leavingCandidate = null
var plus = true
for (s in path) {
if (plus) {
reduction = reduction + s.costPerUnit
} else {
reduction = reduction - s.costPerUnit
if (s.quantity < lowestQuantity) {
leavingCandidate = s
lowestQuantity = s.quantity
}
}
plus = !plus
}
if (reduction < maxReduction) {
move = path
leaving = leavingCandidate
maxReduction = reduction
}
}
}
 
if (move) {
var q = leaving.quantity
var plus = true
for (s in move) {
s.quantity = s.quantity + ((plus) ? q : -q)
_matrix[s.r][s.c] = (s.quantity == 0) ? null : s
plus = !plus
}
steppingStone()
}
}
 
matrixToList_() { Lst.flatten(_matrix).where { |s| s != null }.toList }
 
getClosedPath_(s) {
var path = matrixToList_()
path.insert(0, s)
// remove (and keep removing) elements that do not have a
// vertical AND horizontal neighbor
while (true) {
var removals = 0
for (e in path) {
var nbrs = getNeighbors_(e, path)
if (nbrs[0] == null || nbrs[1] == null) {
path.remove(e)
removals = removals + 1
}
}
if (removals == 0) break
}
 
// place the remaining elements in the correct plus-minus order
var stones = List.filled(path.count, null)
var prev = s
for (i in 0...stones.count) {
stones[i] = prev
prev = getNeighbors_(prev, path)[i % 2]
}
return stones
}
 
getNeighbors_(s, lst) {
var nbrs = List.filled(2, null)
for (o in lst) {
if (o != s) {
if (o.r == s.r && nbrs[0] == null) {
nbrs[0] = o
} else if (o.c == s.c && nbrs[1] == null) {
nbrs[1] = o
}
if (nbrs[0] != null && nbrs[1] != null) break
}
}
return nbrs
}
 
fixDegenerateCase_() {
var eps = Num.smallest
if (_supply.count + _demand.count - 1 != matrixToList_().count) {
for (r in 0..._supply.count) {
for (c in 0..._demand.count) {
if (_matrix[r][c] == null) {
var dummy = Shipment.new(eps, _costs[r][c], r, c)
if (getClosedPath_(dummy).count == 0) {
_matrix[r][c] = dummy
return
}
}
}
}
}
}
 
printResult() {
var text = File.read(_filename)
System.print("%(_filename)\n\n%(text)")
System.print("Optimal solution %(_filename)\n")
var totalCosts = 0
for (r in 0..._supply.count) {
for (c in 0..._demand.count) {
var s = _matrix[r][c]
if (s != null && s.r == r && s.c == c) {
Fmt.write(" $3d ", s.quantity.floor)
totalCosts = totalCosts + s.quantity * s.costPerUnit
} else System.write(" - ")
}
System.print()
}
System.print("\nTotal costs: %(totalCosts)\n")
}
}
 
var filenames = ["input1.txt", "input2.txt", "input3.txt"]
for (filename in filenames) {
var t = Transport.new(filename)
t.northWestCornerRule()
t.steppingStone()
t.printResult()
}</syntaxhighlight>
 
{{out}}
<pre>
input1.txt
 
2 3
25 35
20 30 10
3 5 7
3 2 5
 
Optimal solution input1.txt
 
20 - 5
- 30 5
 
Total costs: 180
 
input2.txt
 
3 3
12 40 33
20 30 10
3 5 7
2 4 6
9 1 8
 
Optimal solution input2.txt
 
- - - 12
20 - 10 10
- 30 - 3
 
Total costs: 130
 
input3.txt
 
4 4
14 10 15 12
10 15 12 15
10 30 25 15
20 15 20 10
10 30 20 20
30 40 35 45
 
Optimal solution input3.txt
 
- - - 14
- 9 - 1
10 - 5 -
- 5 7 -
- 1 - -
 
Total costs: 1000
</pre>
PureFox
9,486

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/232180...352155"