示例 13：二级运输问题

问题描述

从三个分销中心向五个经销商运输汽车，运输费用依据起点到终点的距离而定，与运输卡车满载无关。汇总从分销中心到经销商之间的里程以及相应的月供应量和需求量如下表所示：

分销中心	经销商A	经销商B	经销商C	经销商D	经销商E	供应量
1	$100mile$	$150mile$	$200mile$	$140mile$	$35mile$	$400t$
2	$50mile$	$70mile$	$60mile$	$65mile$	$80mile$	$200t$
3	$40mile$	$90mile$	$100mile$	$150mile$	$130mile$	$150t$
需求量	$100t$	$200t$	$150t$	$160t$	$140t$	--

每辆卡车每英里运输费用固定，给出最优运输方案，要求：

1. 分销中心运输量不超过其供应量；
2. 各经销商的需求需得到满足；
3. 卡车装载量不超过上限 $18t$。

数学模型

变量

$x_{ij}$：分销中心 $i$ 向经销商 $j$ 的运输量。

$y_{ij}$：分销中心 $i$ 向经销商 $j$ 运输使用卡车数量。

中间值

1. 分销中心运输总量

$$Tran{s}_i=\sum _{j\in D}{x}_{ij},\mathrm{\forall }i\in DC$$

2. 经销商接收总量

$$Receiv{e}_j=\sum _{i\in DC}{x}_{ij},\mathrm{\forall }j\in D$$

3. 运输总费用

$$Cost=\sum _{i\in DC,j\in D}{d}_{ij}\cdot y_{ij}$$

目标函数

1. 运输费用最小

$$minCost$$

约束

1. 运输量不超过分销中心供应量

$$s.t.Tran{s}_i\le Suppl{y}_i,\mathrm{\forall }i\in DC$$

2. 满足经销商需求

$$s.t.Receiv{e}_j\ge Deman{d}_j,\mathrm{\forall }j\in D$$

3. 卡车装载量不超过上限

$$s.t.y_{ij}\cdot Capacity\ge x_{ij},\mathrm{\forall }i\in DC,\mathrm{\forall }j\in D$$

期望结果

分销中心	经销商A	经销商B	经销商C	经销商D	经销商E
1	$100t$	$-$	$-$	$160t$	$140t$
2	$-$	$50t$	$150t$	$-$	$-$
3	$-$	$150t$	$-$	$-$	$-$

代码实现

kotlin

import fuookami.ospf.kotlin.utils.math.*
import fuookami.ospf.kotlin.utils.concept.*
import fuookami.ospf.kotlin.utils.functional.*
import fuookami.ospf.kotlin.utils.multi_array.*
import fuookami.ospf.kotlin.core.frontend.variable.*
import fuookami.ospf.kotlin.core.frontend.expression.polynomial.*
import fuookami.ospf.kotlin.core.frontend.expression.symbol.*
import fuookami.ospf.kotlin.core.frontend.inequality.*
import fuookami.ospf.kotlin.core.frontend.model.mechanism.*
import fuookami.ospf.kotlin.core.backend.plugins.scip.*

data class Dealer(
    val demand: UInt64
) : AutoIndexed(Dealer::class)

data class DistributionCenter(
    val supply: UInt64,
    val distance: Map<Dealer, UInt64>
) : AutoIndexed(DistributionCenter::class)

val carCapacity = UInt64(18)
val dealers: List<Dealer> = ... // 经销商列表
val distributionCenters: List<DistributionCenter> = ... // 分销中心列表

// 创建模型实例
val metaModel = LinearMetaModel("demo13")

// 定义变量
val x = UIntVariable2("x", Shape2(dealers.size, distributionCenters.size))
metaModel.add(x)

val y = UIntVariable2("y", Shape2(dealers.size, distributionCenters.size))
metaModel.add(y)

// 定义中间值
val trans = LinearIntermediateSymbols1("trans", Shape1(distributionCenters.size)) { i, _ ->
    val distributionCenter = distributionCenters[i]
    LinearExpressionSymbol(
        sum(x[_a, distributionCenter]),
        "trans_${distributionCenter.index}"
    )
}
metaModel.add(trans)

val receive = LinearIntermediateSymbols1("receive", Shape1(dealers.size)) { i, _ ->
    val dealer = dealers[i]
    LinearExpressionSymbol(
        sum(x[dealer, _a]),
        "receive_${dealer.index}"
    )
}
metaModel.add(receive)

val cost = LinearExpressionSymbol(
    sum(dealers.flatMap { dealer ->
        distributionCenters.mapNotNull { distributionCenter ->
            val distance = distributionCenter.distance[dealer] ?: return@mapNotNull null
            distance * y[dealer, distributionCenter]
        }
    }),
    "cost"
)
metaModel.add(cost)

// 定义目标函数
metaModel.minimize(cost, "cost")

// 定义约束
for (distributionCenter in distributionCenters) {
    metaModel.addConstraint(
        trans[distributionCenter] leq distributionCenter.supply,
        "supply_${distributionCenter.index}"
    )
}

for (dealer in dealers) {
    metaModel.addConstraint(
        receive[dealer] geq dealer.demand,
        "demand_${dealer.index}"
    )
}

for (dealer in dealers) {
    for (distributionCenter in distributionCenters) {
        metaModel.addConstraint(
            x[dealer, distributionCenter] leq carCapacity * y[dealer, distributionCenter],
            "car_limit_${dealer.index}_${distributionCenter.index}"
        )
    }
}

// 调用求解器求解
val solver = ScipLinearSolver()
when (val ret = solver(metaModel)) {
    is Ok -> {
        metaModel.tokens.setSolution(ret.value.solution)
    }

    is Failed -> {}
}

// 解析结果
val solution: MutableMap<DistributionCenter, MutableMap<Dealer, UInt64>> = hashMapOf()
for (token in metaModel.tokens.tokens) {
    if (token.result!! geq Flt64.one && token.variable belongsTo x) {
        val vector = token.variable.vectorView
        val dealer = dealers[vector[0]]
        val distributionCenter = distributionCenters[vector[1]]
        solution.getOrPut(distributionCenter) { hashMapOf() }[dealer] = token.result!!.round().toUInt64()
    }
}

完整实现请参考：

• Kotlin