第2讲 数学规划模型的建立1

数学规划模型I 引言

一个复杂系统往往要受诸多因素的影响，而这 些因素又要受到一定的限制。最优化就是在一定约 束下，如何选取这些因素的值，使某项(或某些) 指标达到最优的一门学科。它包括数学规划、决策 分析、最优控制等等。最优化方法在经济、军事、科技等领域内都有 广泛的应用。

例1

把一根直径为 d 的圆木锯成矩形横梁。已知 横梁强度 z 与宽度 x 成正比，与高度 y 的平 方成正比。求宽、高各为多少时强度最大？

该问题的数学模型为： z kxy2 (k 0)

x y d ,2 2 2

x 0, y 0

用微分法容易求出其解。

数学规划模型格式： 2 z kxy (k 0) max s.t. x2 y2 d 2 ,

x 0, y 0

例2 施工点 j 的坐标为 (a j , b j ), j 1,2, , n 对某材料的需求量为 q j , j 1,2, , n 第 i个料场的容量为 M i 吨, i 1,2, , m . 求料场的位置及各料场向各施工点的供应量，使 材料运输的总吨公里最小。 解 设各料场到各施工点的距离为直线距离，且各施工 点可在不同料场取料。 设 ( xi , yi ) 为第 i 个料场坐标 则 wij 为料场 i 向施工点 j 提供的材料数量 m n min z wij ( xi a j )2 ( yi b j )2 总吨公里数 s.t.

wij q j , j 1,2, , n i 1

m

i 1 j 1

需求限制 容量限制 非负限制

wij 0, i 1,2, , m; j 1,2, , n

wij M i , i 1,2, , m j 1

n

第二个问题不便用微分法求解，可用数学规 划方法求解。学习这一部分需注意的地方： 1. 对给定的实际问题，如何作合理的假设，并建立 模型。如何处理分段函数、矛盾约束等问题。 2. 怎样将一类模型化为另一类模型，易于求解。 3. 同一问题可建立不同模型

II

数学规划模型的建立

数学规划模型的一般形式： min z f ( X ) (或 max n X S ( R ) T X ( x1 , x2 , , xn )

z f ( X ))

若能写出描述S的数学式子，则可直接写出。 2 z kxy (k 0) max 例如： s.t. x2 y2 d 2 ,

x 0, y 0这里

S {( x, y ) | x 2 y 2 d 2 , x, y 0} X ( x, y )T

几个概念：min

目标函数z f ( X ) (或 max

z f ( X ))可行域决策变量

可行解

X S ( Rn )

X ( x1 , x2 , , xn )T描述S 的数学式子

SX

约束条件 问题可行 问题不可行

最优解

z

最优目标值

(或 max) 特别： min z c1 x1 c2 x2 cn xn b1 ) s.t . a11 x1 a12 x2 a1n xn b1 (或 , a21 x1 a22 x2 a2 n xn b2 (或 , b2 ) am1 x1 am 2 x2 amn xn bm(或 , bm) x j 0, j 1,2, , n 线性规划模型 n min z c j x j 或s .t .

x j 0, j 1,2, , n或min z CX s .t . AX b

X O

aij x j ( , )bi , i 1,2, , m j 1

n

j 1

等约束

注：1.min z CX M s .t . AX b X O min z CX s .t . AX b X O min z CX s .t . AX b X O

M是常数

与

有相同的最优解

2.

与

max z0 CXs .t .

AX b X O

有相同的最优解

另外： 1. x j 取整数，称模型为整数规划模型 2. x j 中部分取整数，称模型为混合整数规划模型3. x j 只取0或1两个值，称为 0 — 1 规划模型

4. 目标函数或约束条件是非线性的，称为非线性规划模型 5. 若目标函数只有一个，称为单目标规划模型； 若目标函数不只一个，称为多目标规划模型。

一、运输问题例1运 价 销地

产地

B1c11 c21 cm 1

B2 Bnc12 c22 c1n c2 n

产量

A1 A2 Am需求量

a1 a2 am

cm 2 cmn

b1 b2 bn

求使总运费最少的调运方案。试建模。

42

解

假设

ai b j i 1 j 1 z cij xij xij ai , j 1n i 1 j 1 m n

m

m

产销平衡

设 xij 为产地 Ai 到销地 B j 的运量。则min s .t .

i 1,2, , m

xij 0, i 1,2, , m; j 1,2, , n注：若产大于销，则 若产小于销，则xij ai , j 1n

xij b j , i 1

m

j 1,2, , n

线 性 规 划 模 型

i 1,2, , m

xij b j , i 1

m

j 1,2, , n

重要结论：当供应量 ai 与需求量 b j 均为整数时， X 模型的最优解 是整数解。

例2

自来水输送问题

某市有甲、乙、丙、丁四个居民区，自来水由A、B、 C由三个水库供应。四个区每天必须的基本生活用水 分别为30、70、10、10千吨，但三个水库每天最多只 能分别供应50、60、50千吨自来水。由于地理位置的 差别，自来水公司从各水库向各区送水所付出的引水 管理费不同(如表，其中C水库与丁区间无输水管 道),其它管理费均为450元/千吨。各区用户每千吨 收费900元。此外，各区用户都向公司申请了额外用 水量，分别为每天50、70、20、40千吨。问公司应如 何分配供水量，才能获利最多？

引水管理费(元/千吨)

甲

乙

丙

丁

A B C

160 130 220 170 140 130 190 150 190 200 230 /

解 将有关数据整理列表：输 水 成 居民区 本 甲 水库

乙

丙

丁

供应量

A B C生活用水 额外用水

160 130 220 170 140 130 c190 150 ij 190 200 230 /

50 60 50

a aii

i

160

30 70 10 10 bj 50 70 20 40

bj

j

300

问题分析：…可看成是“产小于销”的运输问题。

模型建立 因160千吨水须 设 xij 分别表示水库A,B,C(i=1,2,3)向居民区甲 ,乙 , 全部输出 丙,丁(j=1,2,3,4)的供水量。其中X34=0. 由题意目标函数为： 3 4 max z1 900 160 450 160 cij xij 可转化为：一般问题中：

min z cij xij i 1 j 1

3

4

i 1

j 1

引水管理费 供给限制

s.t . x11 x12 x13 x14 50

“ x21 x22 x23 x24 ” 60

50 供给限制用“ ” x31 x32 x33 30 x11 x21 x31 80 需求限制用“ ” 70 x12 x22 x32 140 需求限制10 x13 x23 x33 30 50 10 x14 x24 x 0, i 1, 2, 3; j 1, 2, 3,4.ij

注：为了增加供水，公司考虑改造水库，使三个水 库的供水能力提高一倍，问模型将作何改动？ 分析：由于总供水能力为320千吨，总需求量为300千 吨，水不能全部卖出，所以不能将获利最多转化为引 水管理费最少。须算出每千吨净利润。 每千吨净利润=

用户交的900元-其它管理费450元-引水管理费 净利润(元/千吨)

甲

乙

丙

丁

A B C

290 320 230 280 310 320 ij 260 300 260 250 220 /

c

模型改为：

Max Z c xij i, j11 12 13 14

ij

s.t . x x x x 100 50 x x x x 120 6021 22 23 24

x x x31 32

33

100 50

其它同前

二、网络(规划)问题 例3 最大流问题

15

④

20①14

②10③

12

8⑤ 8 ⑥

9 1012

⑦

13

图中弧上的数字表示每小时两结点沿箭头方向的最大 车流量，求①到⑦每小时的最大车流量。

本文来源：https://www.bwwdw.com/article/j5ni.html