Transportation problem: Difference between revisions
Content added Content deleted
(Undo revision 317423 by Dylanomics (talk)) |
(Undo revision 317422 by Dylanomics (talk)) |
||
Line 2,532: | Line 2,532: | ||
solution vector of quantities = [20.000000008747048, 0.0, 4.9999996490783145, 0.0, 30.000000007494098, 5.0000003509216855] |
solution vector of quantities = [20.000000008747048, 0.0, 4.9999996490783145, 0.0, 30.000000007494098, 5.0000003509216855] |
||
minimum total cost = 179.99999927567436</pre> |
minimum total cost = 179.99999927567436</pre> |
||
=={{header|Kotlin}}== |
|||
{{trans|Java}} |
|||
<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() |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
Same as Java entry |
|||
</pre> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |