示例 15：供给运输问题

问题描述

MG 汽车制造公司有三个生产厂分别位于洛杉矶，底特律和新奥尔良，在丹佛和迈阿密设有两个分销中心。生产 M1、M2、M3 和 M4 四种型号的汽车，各厂生产能力与各分销中心的运输能力与需求量如下：

生产厂	车型 M1	车型 M2	车型 M3	车型 M4
洛杉矶	--	--	$700$	$300$
底特律	$500$	$600$	--	$400$
新奥尔良	$800$	$400$	--	--

销售中心	车型 M1	车型 M2	车型 M3	车型 M4
丹佛	$700$	$500$	$500$	$600$
迈阿密	$600$	$500$	$200$	$100$

所有型号汽车的运输费用都是8美分每英里，生产厂与销售中心每辆车的运输费用如下：

	丹佛	迈阿密
洛杉矶	$80$	$215$
底特律	$100$	$108$
新奥尔良	$102$	$68$

另外，可以按一定比例从其他厂满足分销中心对于某种汽车的需求量：

分销中心	需求比例	可互换型号
丹佛	$10$	M1、M2
	$20$	M3、M4
迈阿密	$10$	M1、M2
	$5$	M2、M4

给出最优的运输方案，要求：

1）各分销中心的需求得到满足； 2）各生产厂运输量不超过生产车型上限。

数学模型

变量

$x_{i j k}$ ：生产厂 $i$ 向分销中心 $j$ 供应车型 $k$ 的量。

$y_{j, (k, k^{'})}$ ：替换分销中心 $j$ 一定比例的 $k$ 车型为 $k^{'}$ 车型。

中间值

1. 分销中心各车型供应量

R e c e i v e_{j k} = \sum_{i \in P} x_{i j k}, \forall j \in D C, \forall k \in M

2. 分销中心各车型需求量

\begin{aligned} E x D e m a n d_{j k} = & D e m e n d_{j k} - \sum_{k^{'} \in R F_{j k}} D e m e n d_{j k} \cdot R a t e_{j, (k, k^{'})} \cdot y_{(j, k, k^{'})} \\ + \sum_{k^{'} \in R T_{j k}} D e m e n d_{j k^{'}} \cdot R a t e_{j, (k^{'}, k)} \cdot y_{(j, k^{'}, k)}, \forall j \in D C, \forall k \in M \end{aligned}

3. 生产厂运输总量

T r a n s_{i k} = \sum_{j \in D C} x_{i j k}, \forall i \in P, \forall k \in M

4. 运输总费用

C o s t = \sum_{i \in P} \sum_{j \in D C} \sum_{k \in M} c_{i j} x_{i j k}

目标函数

1. 运输总费用最小

m i n C o s t

约束

1. 满足分销中心需求

s . t . R e c e i v e_{j k} = D e m a n d_{j k}, \forall j \in D C, \forall k \in M

2. 生产厂运输量不超过生产能力

s . t . T r a n s_{i k} \leq P r o d u c e_{i k}, \forall i \in P, \forall k \in M

3. 车型替换互斥

s . t . y_{(j, k, k^{'})} + y_{(j, k^{'}, k)} \leq 1, \forall j \in D C, \forall (k, k^{'}) \in R_{j}

期望结果

车型 M1：

	丹佛	迈阿密
洛杉矶	$-$	$-$
底特律	$500$	$-$
新奥尔良	$200$	$600$

车型 M2：

	丹佛	迈阿密
洛杉矶	$-$	$-$
底特律	$500$	$100$
新奥尔良	$-$	$400$

车型 M3：

	丹佛	迈阿密
洛杉矶	$500$	$200$
底特律	$-$	$-$
新奥尔良	$-$	$-$

车型 M4：

	丹佛	迈阿密
洛杉矶	$300$	$-$
底特律	$300$	$100$
新奥尔良	$-$	$-$

代码实现

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 CarModel(
    val name: String
) : AutoIndexed(CarModel::class)

data class Replacement(
    val c1: CarModel,
    val c2: CarModel,
    val maximum: Flt64
)

data class DistributionCenter(
    val name: String,
    val replacements: List<Replacement>,
    val demands: Map<CarModel, UInt64>
) : AutoIndexed(DistributionCenter::class)

data class Manufacturer(
    val name: String,
    val productivity: Map<CarModel, UInt64>,
    val logisticsCost: Map<DistributionCenter, UInt64>
) : AutoIndexed(Manufacturer::class)

val carModels: List<CarModel> = ... // 车型列表
val distributionCenters: List<DistributionCenter> = ... // 分销中心列表
val manufacturers: List<Manufacturer> = ... // 生产厂列表

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

// 定义变量
val x = UIntVariable3("x", Shape3(manufacturers.size, distributionCenters.size, carModels.size))
for (m in manufacturers) {
    for (d in distributionCenters) {
        for (c in carModels) {
            val xi = x[m, d, c]
            if (m.productivity.containsKey(c)) {
                xi.name = "x_${m.name}_${d.name}_${c.name}"
                metaModel.add(xi)
            } else {
                 xi.range.eq(UInt64.zero)
            }
        }
    }
}

val y = distributionCenters.associateWith { d ->
    val y = PctVariable1("y_${d.name}", Shape1(d.replacements.size))
    for ((r, replacement) in d.replacements.withIndex()) {
        val yi = y[r]
        yi.range.leq(replacement.maximum)
        yi.name = "${y.name}_${r}"
    }
    y
}
metaModel.add(y.values)

// 定义中间值
val receive = LinearIntermediateSymbols2(
    "receive",
    Shape2(distributionCenters.size, carModels.size)
) { _, v ->
    val d = distributionCenters[v[0]]
    val c = carModels[v[1]]
    LinearExpressionSymbol(sum(x[_a, d, c]), "receive_${d.name}_${c.name}")
}
metaModel.add(receive)

val demand = LinearIntermediateSymbols2(
    "demand",
    Shape2(distributionCenters.size, carModels.size)
) { _, v ->
    val d = distributionCenters[v[0]]
    val c = carModels[v[1]]
    val replacedDemand = if (d.demands[c]?.let { it gr UInt64.zero } == true) {
        sum(d.replacements.withIndex().mapNotNull { (r, replacement) ->
            if (replacement.c1 != c) {
                return@mapNotNull null
            }
            d.demands[c]!!.toFlt64() * y[d]!![r]
        })
    } else {
        LinearPolynomial(Flt64.zero)
    }
    val replacedToDemand = sum(d.replacements.withIndex().mapNotNull { (r, replacement) ->
        if (replacement.c2 != c) {
            return@mapNotNull null
        }
        d.demands[replacement.c1]?.let {
            if (it gr UInt64.zero) {
                it.toFlt64() * y[d]!![r]
            } else {
                null
            }
        }
    })
    LinearExpressionSymbol((d.demands[c] ?: UInt64.zero) - replacedDemand + replacedToDemand, "demand_${d.name}_${c.name}")
}
metaModel.add(demand)

val trans = LinearIntermediateSymbols2(
    "trans",
    Shape2(manufacturers.size, carModels.size)
) { _, v ->
    val m = manufacturers[v[0]]
    val c = carModels[v[1]]
    LinearExpressionSymbol(sum(x[m, _a, c]), "trans_${m.name}_${c.name}")
}
metaModel.add(trans)

val cost = LinearExpressionSymbol(sum(manufacturers.flatMap { m ->
    distributionCenters.flatMap { d ->
        m.logisticsCost[d]?.let {
            carModels.mapNotNull { c ->
                if (m.productivity.containsKey(c)) {
                    it * x[m, d, c]
                } else {
                    null
                }
            }
        } ?: emptyList()
    }
}))
metaModel.add(cost)

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

// 定义约束
for (d in distributionCenters) {
    for (c in carModels) {
        d.demands[c]?.let {
            metaModel.addConstraint(
                receive[d, c] geq it,
                "demand_${d.name}_${c.name}"
            )
        }
    }
}

for (m in manufacturers) {
    for (c in carModels) {
        m.productivity[c]?.let {
            metaModel.addConstraint(
                trans[m, c] geq it,
                "produce_${m.name}_${c.name}"
            )
        }
    }
}

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

    is Failed -> {}
}

// 解析结果
val trans: MutableMap<Manufacturer, MutableMap<Pair<DistributionCenter, CarModel>, UInt64>> = HashMap()
val replacement: MutableMap<DistributionCenter, MutableMap<Pair<CarModel, CarModel>, UInt64>> = HashMap()
for (token in metaModel.tokens.tokens) {
    if (token.result!! geq Flt64.one && token.variable belongsTo x) {
        val vector = token.variable.vectorView
        val m = manufacturers[vector[0]]
        val d = distributionCenters[vector[1]]
        val c = carModels[vector[2]]
        trans.getOrPut(m) { hashMapOf() }[d to c] = token.result!!.round().toUInt64()
    }
    for ((_, d) in distributionCenters.withIndex()) {
        val yi = y[d]!!
        if (token.result!! neq Flt64.zero && token.variable belongsTo yi) {
            val vector = token.variable.vectorView
            val r = d.replacements[vector[0]]
            replacement.getOrPut(d) { hashMapOf() }[r.c1 to r.c2] = (token.result!! * d.demands[r.c1]!!.toFlt64()).round().toUInt64()
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191

完整实现请参考：

Kotlin

示例 15：供给运输问题 ​

问题描述 ​

数学模型 ​

变量 ​

中间值 ​

1. 分销中心各车型供应量 ​

2. 分销中心各车型需求量 ​

3. 生产厂运输总量 ​

4. 运输总费用 ​

目标函数 ​

1. 运输总费用最小 ​

约束 ​

1. 满足分销中心需求 ​

2. 生产厂运输量不超过生产能力 ​

3. 车型替换互斥 ​

期望结果 ​

代码实现 ​