数学建模竞赛中的优化问题 数学建模 培训组 2009.3.

Presentation on theme: "数学建模竞赛中的优化问题 数学建模 培训组 2009.3."— Presentation transcript:

1 数学建模竞赛中的优化问题 数学建模 培训组 2009.3

2 本次讲座目的 让大家了解数学建模中常常遇到的问题——优化问题； 初步认识数学建模需要准备的算法，软件。

3 优化问题 优化问题的解题步骤： 1、确定最优目标函数。 2、寻找构成目标函数的各元素应该遵守的约束条件。 3、利用相应软件或算法求解。

4 数学规划 线性规划(linear programming) 是康托洛维奇1939年提出的， 1947年（G.B.Dantzig）提出求线性规划的单纯形法（simple method），理论上趋向成熟，实际上的应用也越来越广泛，几乎各行各业都可建立线性规划模型。

5 § 线性规划问题 例1 生产计划问题 某企业要在计划期内安排生产甲、乙两种产品，这个企业现有的生产资料是：设备18台时，原材料A 4吨，原材料 B 12吨；已知单位产品所需消耗生产资料及利润如下表。问应如何确定生产计划使企业获利最多。

6 表1 产品 资源 甲 乙 资源量 设备/台时 3 2 18 原料A/吨 1 4 原料B/吨 12 单位赢利/万元 5

7 Formulation as a linear programming problem
x1=number of units of product 1 x2 =number of units of product 2 z=total profit from producting these two products x1, x2 are the decision variables for the model. maximize z=3x1+5x2

8 18 2 3 £ + x 设备限制 原料A的限制 原料B的限制 非负约束 产品 资源 甲 乙 资源量 设备/台时 3 2 18 原料A/吨
4 原料B/吨 12 单位赢利/万元 5 18 2 3 1 + x 设备限制 原料A的限制 原料B的限制 非负约束

9 产品 资源 甲 乙 资源量 设备/台时 3 2 18 原料A/吨 1 4 原料B/吨 12 单位赢利/万元 5 相应的数学模型

10 资源的合理利用问题 -the allocating resources to activities 一般的资源利用问题可表述为： 设某企业利用 m 种资源来生产 n 种产品，已知该企业拥有的第 i 种资源的数量是b i , 生产单位第 j 种产品所消耗的第 i 种资源的数量为 aij ，第j种产品的单位利润是 c j。现制定一个生产计划方案，使总利润最大。

11 Resource Usage per Unit of Activity
z=value of overall measure of performance xj=level of activities j (for j=1,2,…,n) cj=increase in z that would resule from each unit increase in level of activity j--价值系数 Resource Resource Usage per Unit of Activity Amount of Resource Available Activity … n 1 2 … m a a … a1n a a … a2n … … … … am am … amn b1 b2 bm Contribution to z per unit of activity c c … c1

12 Resource Usage per Unit of Activity
bi=amount of resource i that is available for allocation to activities (for i=1,2,…,m) )--资源系数 aij=amount of resource i consumed by each unit of activity j .---技术系数 Resource Resource Usage per Unit of Activity Amount of Resource Available Activity … n 1 2 … m a a … a1n a a … a2n … … … … am am … amn b1 b2 bm Contribution to z per unit of activity c c … c1

13 Resource Usage per Unit of Activity
x1,x2,…xn are called the decision variables. cj, bi, aij(for i=1,2,…,m and j=1,2,…,n) are the input constants or the parameters for the model. Resource Resource Usage per Unit of Activity Amount of Resource Available Activity … n 1 2 … m a a … a1n a a … a2n … … … … am am … amn b1 b2 bm Contribution to z per unit of activity c c … c1

14 资源利用问题的数学模型为： the objective function functional constrains
nonegativeconstrains

15 例2 资源定价问题 假设企业决策者不考虑自己生产产品甲乙，而是将厂里的现有资源（见表1）买出。试问该厂的决策者应给每种资源制定一个怎样的价格，才能获得良好收益？ 产品 资源 甲 乙 资源量 设备/台时 3 2 18 原料A/吨 1 4 原料B/吨 12 单位赢利/万元 5

16 问题分析 解： 决策者显然要考虑两个因素： 第一，每种资源所收回的费用应不底于自己生产 时所获得的利润；
解：　决策者显然要考虑两个因素： 第一，每种资源所收回的费用应不底于自己生产 时所获得的利润； 第二，定价又不能太高，要使对方容易接受。 总之，定价要公平合理，使双方都能接受。

17 问题分析 设y1,y2,y3分别表示这三种资源的收费单价。则由第一条原则：将用于加工产品甲或乙的所有资源，如用来加工外来产品所获得的收回的费用，应不低于可获得的利润，即

18 当然对价格还要有非负限制。即： 将该厂所有的资源都用来加工外来产品，其总收入（即对方的总支出）是 从工厂的决策者来看当然是Ｗ越大越好。但是根据第二条原则，也应该使对方的支出尽可能的少； 从而这个问题就可以转化为下述数学问题：

19 定价问题的数学模型

20 例3 人员分配问题 设某单位现有n个人员A1,A2……,An来完成 n项工作B1,B2,……,Bn。按工作要求，每
例3 人员分配问题 设某单位现有n个人员A1,A2……,An来完成 n项工作B1,B2,……,Bn。按工作要求，每 个人员需干一项工作，每项工作也需一人 去完成。已知人员A i做工作B j的效率是c ij。 问应如何分配，才使总效率最好。

21 问题分析 令x ij表示分配人员A i完成工作 B j的决策变量。 x ij = 1 表示分配Ai干工作Bj
按问题要求，每人要做一项工作，每项工作需一人去做。 建立该问题的数学模型的过程：

22 对人员A i；要求承担一项工作： 问题分析 对工作B j ；要求一人员去完成 派工方案的总效益

23 分配问题的数学模型

24 例4 物资运输问题 某公司要运销一种物资。该物资有甲、乙两个产地，产量分别是2000吨、1000吨；另有A、B、C三个销地，销量分别是1700吨、1100吨、200吨。已知该物资的单位运价如表1-2。问应如何确定调运方案，才能使在产销平衡的条件下，总运费最低？

25 表3 销 地 单位运价 产 地 甲 乙 销 量 A B C 产 量 2000 1000 分析 确定调运方案就是确定从不同产地到各个销地的运输量。 设 x ij 表示这些要找的运量。 即x 11 、 x 12 、 x 13分别表示从甲地调往A、B、C三地的运量。 x 21 、 x 22 、 x 23分别表示从已地调往A、B、C三地的运量。

26 由于要求产销平衡： 从两产地甲、乙分别调往三销地A、B、C的物资数量应该分别等于两产地甲、乙的产量，所以 x ij 应满足：

27 运到A、B、C三销地的物资数量应分别等于A、B、C三销地的销量，所以x ij 还应该满足：
调运方案的总运费为： 建立产销平衡下运费最省的调运问题的数学模型：

28 运输问题的数学模型 A B C 产 量 销 地 单位运价 产 地 甲 乙 销 量 21 25 7 51 51 37
销 地 单位运价 产 地 甲 乙 销 量 A B C 产 量 2000 1000

29 某种物资有 m 个产地，A1 ,A2, … ,Am ，产量分别
运输问题的一般提法： 某种物资有 m 个产地，A1 ,A2, … ,Am ，产量分别 a1,a2, …,am个单位，另有 n 个销地B1,B2 , …,Bn , 销 量分别是b1,b2, … ,bn个单位。假设产销是平衡的， 即总产量等于总销量。已知由产地A i 向销地B j 运输一 个单位物资的运价x ij ；问应该怎样调运物资才能使总 运费最省。 令 x ij 表示由产地A i 向销地B j 的运量

30 运输问题的数学模型为：

31 上述例子，虽然有不同的实际内容， 但是它们都是要求一组变量的值，这组值满足一定的约束条件，如资源限制、供求关系等。 这种约束条件都可以用一组线性不等式或线性方程来表示，同时使某个线性函数指标达到最大或最小。具有这些特征的问题，称为线性规划问题。

32 §1.2 图解法-graphical method
图解法适用于来解只有两个变量的线性规划问题.

33 A feasible solution is a solution for which all the constraints are satisfied.
It is possible for a problem to have not feasible solutions. An in feasible solution is a solution for which at least one constraint is violated. The feasible region is the collection of all feasible solutions. An optimal solution is a feasible solution that has the most favorable value (the largest or the smallest) of the objective function. It is possible for a problem to have more than one optimal solution. Any problem having multiple optimal solutions will have an infinite number of them.

34 例1 图解法求解线性规划问题 解 该线性规划问题的可行域见图1。 图解法简单直观，有助于了解线性规划问题求解的基本原理和思想。
下面举例说明图解法求解线性规划问题的步骤。 例1 图解法求解线性规划问题 解 该线性规划问题的可行域见图1。

35 可行域-the feasible region
图1-1 图解法解题过程 x2 8 6 4 2 x1=4 Q1(0,6) Q2(2,6) 2 x 2 = 12 Q Q3(4,3) 可行域-the feasible region 3x1+2x2=18 Q4(4,0) x1 Q0(0,0)

36 图1-1 图解法解题过程 x2 8 6 4 2 让直线束 Q 沿正法线 在可行域Q移动， 通过点 (2,6) 的直线： 2 4 6 x1
x1=4 Q1(0,6) Q2(2,6) 2 x 2 = 12 让直线束 3x1+5x2=z=36 Q Q3(4,3) 沿正法线 3x1+2x2=18 在可行域Q移动， Q4(4,0) 通过点 (2,6) 的直线： x1 Q0(0,0) 3x1+5x2=z=20 3x1+5x2=z=0

37 例1的最优生产方案为： 生产产品甲为2件，生产产品乙6件，最大利润为36万元。
x1 8 6 4 2 注：本问题只有唯一最优解。 x1=4 Q1(0,6) Q2(2,6) 例1的最优生产方案为： 生产产品甲为2件，生产产品乙6件，最大利润为36万元。 Q Q3(4,3) Q4(4,0) x1 Q0(0,0)

38 注： x2 8 问题的可行域是 一个有界的凸多边形， 6 其边界由5条直线所围成： X 1 = 0, 4 X 2 = 0 X 1 = 4 2
最优解(2,6)在 凸多边形的顶点Q2上。 x2 8 6 4 2 x1=4 Q1(0,6) Q2(2,6) Q Q3(4,3) Q4(4,0) x1 Q0(0,0)

39 例2

40 解 该问题的可行域 Q 是一个有界的凸多边形（如图1-2）。
6x1+2x2=21 x2 X1+x2=5 -x1+x2=0 A(11/4,9/4) x1 B(21/6,0) 3x 1 + x 2 = z =6 3x 1 + x 2 = z =21/2 3x 1 + x 2 = z =0

41 让直线束3x 1 + x 2 = z 沿正法线向移动，到达线段AB时，使 Z 达到最大。所以线段 AB上的每一点都可使Z达到最大值，
注：本问题有无穷多个最优解。 6x1+2x2=21 x2 x1+x2=5 -x1+x2=0 A(11/4,9/4) x1 B(21/6,0) 3x 1 + x 2 = z =6 3x 1 + x 2 = z =21/2 3x 1 + x 2 = z =0

42 例3

43 解 该问题的可行域是一个无界的凸多边形 图1-3

44 注：本问题有可行解，但无最优解。 让直线束 沿其负法线方向移动，可以无限制地移动下去，一直与 相交，所以其最小值为 ；即函数 在 上无下界。

45 例4

46 解 该问题的可行域是空的，即无可行解 X1-x2=-1 x1+x2=-1 注：本问题无可行解，更无最优解。

47 进一步讨论 给定只有两个变量的线性规划问题： 图解法求解线性规划问题的步骤如下：

48 如果 不是空集，那么 是平面上的一个凸多边形，这个凸多边形可能是有界的（封闭的），也可能是无界的（不封闭的）。
在平面 上取定直角坐标系，画出可行域，记为 。 若 是空集，则说明线性规划问题无可行解。 如果 不是空集，那么 是平面上的一个凸多边形，这个凸多边形可能是有界的（封闭的），也可能是无界的（不封闭的）。 表示一个以 z 为参数的平行直线束。 沿正法线方向 移动可得最大值，沿负法线方向 移动可得最小值。 注意:一定要精确

49 通过以上例子可以看出，两个变量的线性规划的解可 能有以下4种情况： ①有唯一的最优解。 最优解一定是可行域的一个顶点。 ②有无穷多的最优解。 最优解是可行域的一段边界。 ③有可行解，但无最优解。目标函数值无界. ④无可行解。 （最大值点（最小值点）一定在可行域的边界上） 问题是对于一般的线性规划问题有无类似结论，结论成立的判定准则如何。

50 1.3 整数规划 例1、集装箱运货 货物 体积(米3/箱) 重量(百公斤/箱) 利润(千元/箱) 甲 5 2 20 乙 4 5 10
1.3 整数规划 例1、集装箱运货 货物 体积(米3/箱) 重量(百公斤/箱) 利润(千元/箱) 甲 乙 装运限制

51 解：设X1 , X2 为甲、乙两货物各托运箱数 maxZ = 20 X X2 5X1+4X2  24 2X1+5X2  13 X1 , X2 0 X1 , X2为整数

52 例2、背包问题 背包可再装入8单位重量，10单位体积物品 物品 名称 重量 体积 价值 1 书 5 2 20 2 摄像机 3 1 30
物品 名称 重量 体积 价值 书 摄像机 枕头 休闲食品 衣服

53 解：Xi为是否带第 i 种物品 maxZ=20X1 + 30X2 +10X3+18X4 +15X5 5X1+3X2 +X3 +2X4 +4X5  8 2X1+X2 +4X3 +3X4 +5X5  10 Xi为0, 1

54 一般形式： ,整数

55 (1)、 Xi为i 物品携带数量 ai为i 物品单位重量 ci为i 物品重要性估价 b为最大负重 (2)、 投资决策 Xi为在i 地区建厂规模 ai为在i 地区建厂基建费用 ci为在i 地区建厂单位利润 b为最大资本 (3)、 Xi 取0或1时，可作项目投资模型

56 例3、选址问题 A1 A3 B2 B4 B3 B1 A2 Ai: 可建仓库地点，容量ai ,投资费用bi ，建2个
Bj: 商店，需求dj ( j=1…4 ) Cij: 仓库 i 到商店 j 的单位 运费 问：选择适当地点建仓库，在满足商店需求条件下，总费用最小。

57 y11 + y21 = d1 y12 + y22 + y32 = d2 y23+ y33 = d3 y14 + y24 + y34 = d4
解：设Xi ( i=1,2,3)为是否在 Ai 建仓库 yij ( i=1,2,3, j=1…4)由 i仓库向 j商店运货量 y11 + y21 = d1 y12 + y22 + y32 = d2 y23+ y33 = d3 y14 + y24 + y34 = d4 x1 + x2 + x3= 2 y11 + y12 + y14 a1x1 y21 + y22 + y23 + y24a2x2 y32 + y33 + y34 a3x3 xi 为0－1， yij 0 混合整数规划

58 0－1决策变量的应用 可用于相互排斥计划中 例1、运输方式：火车、船。 火车：5X1+4X2  (体积) 船： 7X1+3X2  (体积)

59 maxZ=20X1 + 10X2 2X1+5X2  13 5X1+4X2  24+MX3 7X1+3X2  45+M(1-X3 ) X1 , X2 0 整数 X3为0或 M>0 当 X3 =0 火车 X3 = 船

60 例2、ai1x1+ai2x2 +…+ainxn  bi (i=1,…,m)
ai1x1+…+ainxn  bi+yi M (i=1,…,m) y1 +…+ ym =m-1 yi为0或 M>0

61 例4: 聘用方案 决策变量：周一至周日每天(新)聘用人数 x1, x2,x7 目标函数：7天(新)聘用人数之和
约束条件：周一至周日每天需要人数

62 聘用方案 设系统已进入稳态（不是开始的几周） 连续工作5天 周一工作的应是(上)周四至周一聘用的 整数规划 模型(IP)

63 0-1规划 －混合泳接力队的选拔 例5： 5名候选人的百米成绩 如何选拔队员组成4100米混合泳接力队?
甲 乙 丙 丁 戊 蝶泳 1’06”8 57”2 1’18” 1’10” 1’07”4 仰泳 1’15”6 1’06” 1’07”8 1’14”2 1’11” 蛙泳 1’27” 1’06”4 1’24”6 1’09”6 1’23”8 自由泳 58”6 53” 59”4 1’02”4 如何选拔队员组成4100米混合泳接力队? 丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5, 组成接力队的方案是否应该调整？ 穷举法：组成接力队的方案共有5!=120种。

64 0-1规划模型 cij(秒)~队员i 第j 种泳姿的百米成绩 若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0 0-1规划:
66.8 57.2 78 70 67.4 j=2 75.6 66 67.8 74.2 71 j=3 87 66.4 84.6 69.6 83.8 j=4 58.6 53 59.4 62.4 若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0 0-1规划:　 整数规划的特例 目标函数 每人最多入选泳姿之一 每种泳姿有且只有1人 约束条件

65 整数规划问题一般形式 整数规划问题的分类 整数线性规划(ILP) 目标和约束均为线性函数
整数非线性规划(NLP) 目标或约束中存在非线性函数 纯(全)整数规划(PIP) 决策变量均为整数 混合整数规划(MIP) 决策变量有整数，也有实数 0-1规划 决策变量只取0或1

66 整数规划问题对应的松弛问题 取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题 整数规划问题 最优解
非最优解 松弛问题 松弛 最优解 整数 非整数 整数 舍入 下界（对Min问题） 上界（对Max问题）

67 用连续优化方法求解松弛问题，如果松弛问题最优解（分量）全为整数，则也是原整数规划问题的最优解
对松弛问题的最优解（分量）舍入为整数，得到的往往不是原整数规划问题的最优解（甚至不是可行解） IP可行解对应于整点A(2,2)和B(1,1),而最优解为A点. 但LP松弛的最优解为C(3.5,2.5) 目标函数下降方向 x1 x2 C A B O

68 例1.6 x2 5 P o 9 Zmax 6 x1 去掉整数限制后，可行域为点（0,0), (6,0), (0,5),
． x1 x2 P o 6 9 Zmax 5 例1.6 去掉整数限制后，可行域为点（0,0), (6,0), (0,5), P (2.25,3.75) 围成的4边形 从LP最优解经过简单的 “移动”不一定能得到IP最优解

69 分枝定界法（B&B: Branch and Bound）
基本思想：隐式地枚举一切可行解（“分而治之”） 所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题）. 这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举. 这里仅介绍整数线性规划的分枝定界算法 对于极小化问题，在子域上解LP，其最优值是IP限定在该子域时的下界；IP任意可行点的函数值是IP的上界。

70 某厂生产两个牌号的同一种产品，如何确定产量使利润最大
1.4 二次规划模型 例1：产销计划问题 某厂生产两个牌号的同一种产品，如何确定产量使利润最大 假设A 产销平衡 假设B p随x (两种牌号)增加而减小，呈线性关系

71 若还要求产量为整数，则是整数二次规划模型(IQP)
目标 利润最大 =　（100-x1-0.1 x2-2）x1 　+（ x1-2x2-3）x2 =98 x x2 － x12 － 0.3 x1 x2 － 2x22 约束 x1 + x2 ≤100 x1 ≤ 2 x2 x1 , x2 ≥ 0 二次规划模型(QP) 若还要求产量为整数，则是整数二次规划模型(IQP)

72 1.5 非线性规划模型 例2：选址问题 某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里),水泥日用量di (单位：吨）
假设：料场和工地之间有直线道路

73 决策变量：ci j (料场j到工地i的运量）~12维
线性规划模型(LP) 用例中数据计算，最优解为 总吨公里数为136.2

74 选址问题：NLP 2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij ，在其它条件不变下使总吨公里数最小。 决策变量：
ci j，(xj,yj)~16维 非线性规划模型 (NLP)

75 优化建模与LINDO/LINGO软件 http://faculty.math.tsinghua.edu.cn/~jxie/lindo
［原书相关信息］ 谢金星, 薛毅编著, 清华大学出版社, 2005年7月第1版.

76 内容提要 1. 优化模型的基本概念 2. 优化问题的建模实例 3. LINDO/LINGO 软件简介

77 1. 优化模型的基本概念

78 最优化: 在一定条件下，寻求使目标最大(小)的决策
优化模型和算法的重要意义 最优化: 在一定条件下，寻求使目标最大(小)的决策 最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题, 如: 结构设计 资源分配 生产计划 运输方案 解决优化问题的手段 经验积累，主观判断 作试验，比优劣 建立数学模型，求解最优策略

79 优化问题的一般形式 优化问题三要素：决策变量；目标函数；约束条件 目标函数 约束条件 决策变量 无约束优化(没有约束)与约束优化(有约束)
可行解（只满足约束）与最优解(取到最优值)

80 局部最优解与整体最优解 局部最优解 (Local Optimal Solution, 如 x1 )
* f(x) x1 x2 o 局部最优解 (Local Optimal Solution, 如 x1 ) 整体最优解 (Global Optimal Solution, 如 x2 )

81 优化模型的 简单分类 数学规划 连续优化 线性规划(LP) 目标和约束均为线性函数 非线性规划(NLP) 目标或约束中存在非线性函数
二次规划(QP) 目标为二次函数、约束为线性 整数规划(IP) 决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划 离散优化

82 优化模型的简单分类和求解难度 优化 连续优化 整数规划 线性规划 非线性规划 二次规划 问题求解的难度增加

83 2. 优化问题的建模实例

84 线性规划模型 例1: 家具厂生产计划 例2: 奶制品生产计划 例3: 运输问题

85 例2: 奶制品生产计划 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 每天： 50桶牛奶
例2: 奶制品生产计划 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 每天： 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到 30元/公斤，应否改变生产计划？

86 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 50桶牛奶 每天 时间480小时 至多加工100公斤A1 决策变量 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 24×3x1 获利 16×4 x2 目标函数 每天获利 线性规划模型(LP) 原料供应 劳动时间 约束条件 加工能力 非负约束

87 线性规划模型的解的几种情况 线性规划问题 有可行解(Feasible) 无可行解（Infeasible） 有最优解（Optimal）
无最优解(Unbounded)

88 更多的优化问题 无约束优化 非线性规划 不确定规划 多目标规划 线性规划 整数规划 组合优化 目标规划 网络优化 动态规划 连续优化
离散优化 从其他角度分类 应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等 实际问题规模往往较大，用软件求解比较方便

89 LINDO / LINGO软件使用简介

90 使用LINDO的一些注意事项 “>”（或“<”）号与“>=”（或“<=”）功能相同
变量与系数间可有空格(甚至回车), 但无运算符 变量名以字母开头，不能超过8个字符 变量名不区分大小写（包括LINDO中的关键字） 目标函数所在行是第一行，第二行起为约束条件 行号(行名)自动产生或人为定义。行名以“）”结束 行中注有“!”符号的后面部分为注释。如: ! It’s Comment. 在模型的任何地方都可以用“TITLE” 对模型命名（最多72个字符），如： TITLE This Model is only an Example

91 使用LINDO的一些注意事项 变量不能出现在一个约束条件的右端
表达式中不接受括号“( )”和逗号“,”等任何符号, 例: 400(X1+X2)需写为400X1+400X2 表达式应化简，如2X1+3X2- 4X1应写成 -2X1+3X2 缺省假定所有变量非负；可在模型的“END”语句后用“FREE name”将变量name的非负假定取消 可在 “END”后用“SUB” 或“SLB” 设定变量上下界 例如： “sub x1 10”的作用等价于“x1<=10” 但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。 14. “END”后对0-1变量说明：INT n 或 INT name 15. “END”后对整数变量说明：GIN n 或 GIN name

92 二次规划(QP)问题 LINDO可求解二次规划(QP)问题，但输入方式较复杂，因为在LINDO中不许出现非线性表达式
需要为每一个实际约束增加一个对偶变量（LAGRANGE乘子），在实际约束前增加有关变量的一阶最优条件，转化为互补问题 “END”后面使用QCP命令指明实际约束开始的行号，然后才能求解 建议总是用LINGO解QP [注意]对QP和IP: 敏感性分析意义不大

93 状态窗口（LINDO Solver Status）
当前状态：已达最优解 迭代次数：18次 约束不满足的“量”(不是“约束个数”)：0 当前的目标值：94 最好的整数解：94 整数规划的界：93.5 分枝数：1 所用时间：0.00秒（太快了，还不到0.005秒） 刷新本界面的间隔:1(秒)

94 选项设置 Preprocess：预处理(生成割平面)； Preferred Branch：优先的分枝方式： Nonzero Limit：
“Default”（缺省方式）、 “Up”（向上取整优先）、 “Down”（向下取整优先）； IP Optimality Tol：IP最优值允许的误差上限（一个百分数，如5%即0.05）； IP Objective Hurdle：IP目标函数的篱笆值，即只寻找比这个值更优最优解（如当知道当前模型的某个整数可行解时，就可以设置这个值）； IP Var Fixing Tol：固定一个整数变量取值所依据的一个上限（如果一个整数变量的判别数（REDUCED COST）的值很大，超过该上限，则以后求解中把该整数变量固定下来）。 Nonzero Limit： 非零系数的个数上限； Iteration Limit： 最大迭代步数； Initial Contraint Tol： 约束的初始误差上限； Final Contraint Tol： 约束的最后误差上限； Entering Var Tol： 进基变量的REDUCED COST的误差限； Pivot Size Tol： 旋转元的误差限

95 Report/Statistics ROWS= VARS= INTEGER VARS= ( = 0/1) QCP= 4 NONZEROS= CONSTRAINT NONZ= ( = +-1) DENSITY=0.760 SMALLEST AND LARGEST ELEMENTS IN ABSOLUTE VALUE= OBJ=MIN, NO. <,=,>: , GUBS <= VUBS >= SINGLE COLS= REDUNDANT COLS= 第一行：模型有5行（约束4行），4个变量，两个整数变量（没有0-1变量），从第4行开始是二次规划的实际约束。 第二行：非零系数19个，约束中非零系数12个(其中6个为1或-1)，模型密度为0.760(密度=非零系数/[行数＊(变量数＋１)]) 。 第三行的意思：按绝对值看，系数最小、最大分别为0.3和277。 第四行的意思：模型目标为极小化；小于等于、等于、大于等于约束分别有２、０、２个；广义上界约束（GUBS）不超过１个；变量上界约束（VUBS）不少于０个。所谓GUBS，是指一组不含有相同变量的约束；所谓VUBS，是指一个蕴涵变量上界的约束，如从约束X1+X2-X3=0可以看出，若X3=0，则X1=0，X2=0（因为有非负限制），因此X1+X2-X3=0是一个VUBS约束。 第五行的意思：只含１个变量的约束个数=０个；冗余的列数=０个

96 LINGO软件简介 LINGO模型的优点 LINGO模型的构成：5个段 包含了LINDO的全部功能 提供了灵活的编程语言（矩阵生成器）
目标与约束段 集合段（SETS ENDSETS） 数据段（DATA ENDDATA） 初始段（INIT ENDINIT） 计算段 (CALC ENDCALC) - LINGO9.0

97 集合的类型 集合 派生集合 基本集合 稀疏集合 稠密集合 元素列表法 元素过滤法 直接列举法 隐式列举法
setname(parent_set_list) [/member_list/] [: attribute_list]; setname [/member_list/] [: attribute_list]; 集合 派生集合 基本集合 稀疏集合 稠密集合 元素列表法 元素过滤法 直接列举法 隐式列举法 SETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CITIES, CITIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D; ENDSETS SETS: STUDENTS /S1..S8/; PAIRS( STUDENTS, STUDENTS) | &2 #GT# &1: BENEFIT, MATCH; ENDSETS

98 集合元素的隐式列举 类型 隐式列举格式 示例 示例集合的元素 数字型 1..n 1..5 1, 2, 3, 4, 5 字符-数字型
stringM..stringN Car101..car208 Car101, car102, … , car208 星期型 dayM..dayN MON..FRI MON, TUE, WED, THU, FRI 月份型 monthM..monthN OCT..JAN OCT, NOV, DEC, JAN 年份-月份型 monthYearM..monthYearN OCT2001..JAN2002 OCT2001, NOV2001, DEC2001, JAN2002

99 运算符的优先级 三类运算符： 算术运算符 逻辑运算符 关系运算符 优先级 运算符 最高 #NOT# —（负号） ^ * / + —（减法）
算术运算符 逻辑运算符 关系运算符 优先级 运算符 最高 #NOT# —（负号） ^ * / + —（减法） #EQ# #NE# #GT# #GE# #LT# #LE# #AND# #OR# 最低 <(=) = >(=)

100 集合循环函数 四个集合循环函数：FOR、SUM 、 MAX、MIN Example:
@function( setname [ ( set_index_list)[ | condition]] : expression_list); Example: [objective] MAX PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J)); @FOR(STUDENTS( I): [constraints] @SUM( PAIRS( J, K) | J #EQ# I #OR# K #EQ# I: MATCH( J, K)) =1); @FOR(PAIRS( I, MATCH( I, J))); I, J): BENEFIT( I, J)); I, J): BENEFIT( I, J));

101 状态窗口 Model Class: LP， QP，ILP， IQP，PILP, PIQP，NLP，INLP，PINLP State:
Global Optimum Local Optimum Feasible Infeasible Unbounded Interrupted Undetermined Solver Type: B-and-B Global Multistart

102 7个选项卡(可设置80-90个控制参数)

103 使用外部数据文件 Cut (or Copy) – Paste 方法 @FILE 输入数据、@TEXT输出数据（文本文件）
@OLE函数与电子表格软件（如EXCEL）连接 @ODBC函数与数据库连接 LINGO命令脚本文件 程序与数据分离 LG4 （LONGO模型文件） LNG （LONGO模型文件） LTF （LONGO脚本文件） LDT （LONGO数据文件） LRP （LONGO报告文件） 文 本 件 常用文件后缀

104 @FILE和@TEXT：文本文件输入输出
MODEL: SETS: MYSET / ENDSETS MIN MYSET( I): SHIP( I) * COST( I)); @FOR( MYSET( I): [CON1] SHIP( I) > NEED( I); [CON2] SHIP( I) < SUPPLY( I)); DATA: COST NEED SUPPLY @DUAL(CON1); ENDDATA END myfile.txt文件 的内容、格式： Seattle,Detroit,Chicago,Denver~ COST,NEED,SUPPLY,SHIP~ 12,28,15,20~ 1600,1800,1200,1000~ 1700,1900,1300,1100 演示 MyfileExample.lg4

105 @OLE ：与EXCEL连接 mydata.xls文件中必须有下列名称(及数据)：
MODEL: SETS: MYSET: COST,SHIP,NEED,SUPPLY; ENDSETS MIN MYSET( I): SHIP( I) * COST( I)); @FOR( MYSET( I): [CON1] SHIP( I) > NEED( I); [CON2] SHIP( I) < SUPPLY( I)); DATA: MYSET COST,NEED,SUPPLY @OLE(mydata.xls,'SOLUTION')=SHIP; ENDDATA END mydata.xls文件中必须有下列名称(及数据)： CITIES， COST，NEED，SUPPLY，SOLUTION 在EXCEL中还可以通过“宏”自动调用LINGO(略) 也可以将EXCEL表格嵌入到LINGO模型中(略)

106 @ODBC ：与数据库连接 使用数据库之前，数据源需要在ODBC管理器注册 具体例子略
目前支持下列DBMS: (如为其他数据库，则需自行安装驱动) ACCESS， DBASE，EXCEL，FOXPRO，ORACLE， PARADOX，SQL SERVER， TEXE FILES 输入基本集合元素： [, ‘tablename’ [, ‘columnname’]]])/ 输入派生集合元素： [, ‘column1’[, ‘column2’…]]]])/ 输入数据： [, ‘column1’[, ‘column2’…]]]]) 输出数据： @ODBC([‘source’[,‘table’ [, ‘column1’[, ‘column2’…]]]])= Attr_list 具体例子略

107 需要掌握的几个重要方面 1、LINDO: 正确阅读求解报告（尤其要掌握敏感性分析） 2、LINGO： 掌握集合(SETS)的应用；
正确阅读求解报告； 正确理解求解状态窗口； 学会设置基本的求解选项(OPTIONS) ； 掌握与外部文件的基本接口方法

108 常用优化软件 1. LINDO/LINGO软件 2. MATLAB优化工具箱 / Mathematic的优化功能
3. SAS(统计分析)软件的优化功能 4. EXCEL软件的优化功能 5. 其他（如CPLEX等）

109 MATLAB优化工具箱能求解的优化模型 优化工具箱3.0 (MATLAB 7.0 R14) 纯0-1规划 bintprog 一般IP(暂缺)
连续优化 离散优化 无约束优化 约束优化 非线性 极小 fminunc 非光滑(不可 微)优化 fminsearch 线性规划 linprog 二次规划 quadprog 非线性 方程(组) fzero fsolve 非线性 最小二乘 lsqnonlin lsqcurvefit 全局 优化 暂缺 非线性规划 fmincon fminimax fgoalattain fseminf 约束线性 最小二乘 lsqnonneg lsqlin 上下界约束 fminbnd fmincon lsqnonlin lsqcurvefit

110 LINDO 公司软件产品简要介绍 美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.）， 网址： LINDO: Linear INteractive and Discrete Optimizer (V6.1) LINDO API: LINDO Application Programming Interface (V4.1) LINGO: Linear INteractive General Optimizer (V10.0) What’s Best!: (SpreadSheet e.g. EXCEL) (V8.0) 演示(试用)版、高级版、超级版、工业版、扩展版… （求解问题规模和选件不同）

111 LINDO/LINGO软件能求解的模型 优化 连续优化 整数规划 线性规划 非线性规划 二次规划 LINDO LINGO

112 LINGO软件的功能与特点 LINGO模型的优点 集成了线性(非线性) / 连续(整数) 优化功能 具有多点搜索 / 全局优化功能
提供了灵活的编程语言(矩阵生成器)，可方便地输入模型 提供与其他数据文件的接口 提供与其他编程语言的接口 LINDO API 可用于自主开发 运行速度较快

113 LINGO软件的求解过程 1. 确定常数 2. 识别类型 LINGO预处理程序 LP QP NLP IP 全局优化(选)
ILP IQP INLP 分枝定界管理程序 线性优化求解程序 非线性优化求解程序 1、顺序线性规划法(SLP) 2、广义既约梯度法(GRG) (选) 3、多点搜索(Multistart) (选) 1. 单纯形算法 2. 内点算法(选)

114 建模时需要注意的几个基本问题 1、尽量使用实数优化，减少整数约束和整数变量 2、尽量使用光滑优化，减少非光滑约束的个数
如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等 3、尽量使用线性模型，减少非线性约束和非线性变量的个数 （如x/y <5 改为x<5y） 4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当 (如小于103)

115 解决优化问题常用的算法 遗传算法 遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。

116 Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质； 所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些 假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体” 群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

117 模拟退火算法 　模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

118 数学建模的常用算法 1、蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时通过模拟可以来检验自己模型的正确性。
2、数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关 键就在于这些算法，通常使用Matlab作为工具。 3、线性规划、整数规划、多元规划、二次规划等规划类问题。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo、MATLAB软件实现。

119 4、图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。
5、动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中。 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法。这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7、网格算法和穷举法。网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。

120 8、一些连续离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。
9、数值分析算法。如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10、图象处理算法。赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理。

121 从历年竞赛题来看，常用的方法： 线性规划 整数规划 非线性规划 动态规划 层次分析法 图论方法 拟合方法 插值方法 随机方法 微分方程 方法

122 一些小建议 1、多多阅读数学建模论文，熟悉常见题型及其解法。 2、熟悉常用数学软件的基本命令。 3、熟练掌握论文的写作格式，熟练掌握word的各项功能。

123 建模时主要用到的工具 Word Mathtype（公式编辑器） Excel（数据处理功能超强） Matlab（无所不能） Lingo（优化）
Origin（简单易用的数据分析软件）

124 其他工具 What’s best!——lindo公司出品的一个优化软件，是以插件的形式存在于excel中，简单易用。
Sas\spss——国际权威数据统计、分析软件。 autocad——专业绘图软件 其他工具，有待根据你们的需要去发现。

125 …… 常用的网址 数模网——www.shumo.com 北峰数模网——http://mcm.zjnu.net.cn/
矿大数模网—— ……

126 布置作业内容 每位同学选择完成大学生数模竞赛 1995年A题 1999年B、C题 2000年B、D题
2001年C题 年B、D题 年B题

127 祝大家 学有所成！ 校数学建模 组委会