当前位置:首页 >> 学科竞赛 >> 建模辅导-优化部分1

建模辅导-优化部分1


数学建模
优化模型介绍

引言---数学之重要

……数学使人周密…… ---- Francis Bacon 数学处于人类智能的中心领域……数学方 法渗透、支配着一切自然科学的理论分支…… 它已愈来愈成为衡量成就的主要标志。 ---- von Neumann

引言---数学之重要

门科学只有当它达到能够成功地运用 数学时,才算真正发展了。 ---- Karl Marx

数学是一种语言,是一切科学的共同语言
Galileo : 展现在我们眼前的宇宙像一本用数
学语言写成的大书,如不掌握数学符号语言,就像在黑暗 的迷宫里游荡,什么也认识不清。

引言---数学之重要

数学是一种技术,是高技术的本质

数学技术----数学方法与计算技术的结合形 成的一种关键性的、可实现的技术 二十世纪最伟大的数学家---- D.Hilbert 二十世纪最伟大的物理学家---- A.Einstein 诺贝尔
奖 菲尔兹奖
Go back

1. 什么是数学模型?
数学模型是对于现实世界的一个特定对象,一个 特定目的,根据特有的内在规律,做出一些必要的假 设,运用适当的数学工具,得到一个数学结构.
简单地说:就是系统的某种特征的本质的数学表 达式(或是用数学术语对部分现实世界的描述),即 用数学式子(如函数、图形、代数方程、微分方程、 积分方程、差分方程等)来描述(表述、模拟)所研 究的客观对象或系统在某一方面的存在规律.

2. 什么是数学建模?
数学建模是利用数学方法解决实际问题的一种 实践.即通过抽象、简化、假设、引进变量等处 理过程后,将实际问题用数学方式表达,建立起 数学模型,然后运用先进的数学方法及计算机技 术进行求解.
观点:“所谓高科技就是一种数学技术”

数学建模其实并不是什么新东西,可以说有了数 学并需要用数学去解决实际问题,就一定要用数学的 语言、方法去近似地刻画该实际问题,这种刻划的数 学表述的就是一个数学模型,其过程就是数学建模的 过程.数学模型一经提出,就要用一定的技术手段 (计算、证明等)来求解并验证,其中大量的计算往 往是必不可少的,高性能的计算机的出现使数学建模 这一方法如虎添翼似的得到了飞速的发展,掀起一个 高潮. ? 数学建模将各种知识综合应用于解决实际问题中, 是培养和提高同学们应用所学知识分析问题、解决问 题的能力的必备手段之一.
?

数学建模参考书
1.《数学模型》 姜启源、谢金星、叶俊编 高等教育出版社 2.《数学建模方法及其应用》 解放军信息工程大学 韩中庚编 高教社 3.《数学模型与数学建模》 刘来福、曾文艺编著 北师大出版社 4. 叶其孝等,《大学生数学建模竞赛辅导教材(一)~ (四)》,湖南教育出版社 5.赵静等,《数学建模与数学实验》,高等教育出版社,施普 林格出版社

规划模型的应用极其广泛,其作用已为越来 越多的人所重视. 随着计算机的逐渐普及,它越 来越急速地渗透于工农业生产、商业活动、军事 行为 科学研究的各个方面,为社会节省的财富、 创造的价值无法估量.
特别是在数模竞赛过程中,规划模型是最常 见的一类数学模型. 从92-06年全国大学生数模竞 赛试题的解题方法统计结果来看,规划模型共出 现了15次,占到了50%,也就是说每两道竞赛题 中就有一道涉及到利用规划理论来分析、求解.

优化问题,一般是指用“最好”的方式,使 用或分配有限的资源,即劳动力、原材料、机 器、资金等,使得费用最小或者利润最大。

优化模型

数学规划模型的一般形式
(f S)

min f(x) --------目标函数 s.t. x?S ------约束集合,可行集 其中,S ? Rn,f :S ? R,x?S称(f S )的可行解
?

?

最优解: x*?S,满足f (x*)≤ f (x), ? x?S。则称 x*为(f S)的全局最优解(最优解), 记 g.opt.(global optimum),简记 opt. 最优值: x*为(f S)的最优解, 则称 f * = f (x*) 为 (f S)的最优值(最优目标函数值)

?

?

局部最优解: x*?S,? x* 的邻域 N(x*) ,使满足 f (x*)≤ f (x), ? x ?S ? N(x*) 。则称 x*为(f S)的局部最 优解,记 l .opt.(local optimum) 在上述定义中,当x ? x* 时有严格不等式成立,则分别 称 x* 为(f S)的严格全局最优解和严格局部最优解。

严格l .opt .

严格g .opt .

l .opt .

数学规划模型的一般形式
? 函数形式: f(x), gi(x) , hj(x) : Rn?R min f(x) (fgh) s.t. gi(x) ≤ 0 , i = 1,2,…,m hj(x) = 0 , j = 1,2,…,l ? 矩阵形式: min f(x) ,f(x) : Rn?R (fgh) s.t. g(x) ≤ 0 , g(x) : Rn?Rm h(x) = 0 , h(x) : Rn?Rl
当 f(x), gi(x) , hj(x)均为线性函数时,称线性 规划;若其中有非线性函数时,称非线性规划。

优化模型的 简单分类

min s.t.

f ( x) hi ( x) ? 0, i ? 1,...,m g j ( x ) ? 0, j ? 1,...,l x?D ? ?
n

数学规划

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

优化模型的简单分类和求解难度
优化

连续优化

整数规划

线性规划

二次规划

非线性规划

问题求解的难度增加

线性规划
Linear Programming

两个引例 问题一 : 任务分配问题:某车间有甲、乙两台机床,可用
于加工三种工件.假定这两台车床的可用台时数分别为800和 900,三种工件的数量分别为400、600和500,且已知用三种 不同车床加工单位数量不同工件所需的台时数和加工费用如 下表.问怎样分配车床的加工任务,才能既满足加工工件的要 求,又使加工费用最低?
车床 类 型 甲 乙 单位工件所需加工台时数 工件 1 0.4 0.5 工件 2 1.1 1.2 工件 3 1.0 1.3 单位工件的加工费用 工件 1 13 11 工件 2 9 12 工件 3 10 8 可用台 时数 800 900

建立线性规划模型的基本步骤:
(1)设出决策变量 找出待定的未知变量(决策变量),并用代数符号表示 (2)确定目标函数 找到模型的目标或判据,写成决策变量的线性函数,以便求出 其最大值或最小值 (3)确定约束条件 找出问题的所有的限制或约束,写出未知变量的线性方程或 线性不等式



设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3, 在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,可建立以 下线性规划模型:

min z ? 13x1 ? 9x2 ? 10x3 ? 11x4 ? 12x5 ? 8x6
? x1 ? x4 ? 400 ? x ? x ? 600 ? 2 5 ? x3 ? x6 ? 500 ? s.t. ? ?0.4 x1 ? 1.1x2 ? x3 ? 800 ?0.5 x4 ? 1.2 x5 ? 1.3 x6 ? 900 ? ? xi ? 0, i ? 1, 2,? , 6 ?
解答

问题二: 某厂每日8小时的产量不低于1800件.为了进行质量
控制,计划聘请两种不同水平的检验员.一级检验员的标准为: 速度25件/小时,正确率98%,计时工资4元/小时;二级检验员 的标准为:速度15件/小时,正确率95%,计时工资3元/小时.检 验员每错检一次,工厂要损失2元.为使总检验费用最省,该工 厂应聘一级、二级检验员各几名? 解 设需要一级和二级检验员的人数分别为x1、x2人, 则应付检验员的工资为:

8 ? 4 ? x1 ? 8 ? 3 ? x2 ? 32 x1 ? 24 x2
因检验员错检而造成的损失为:

(8 ? 25 ? 2% ? x1 ? 8 ?15 ? 5% ? x2 ) ? 2 ? 8x1 ? 12 x2

故目标函数为:

min z ? (32 x1 ? 24 x2 ) ? (8x1 ? 12 x2 ) ? 40 x1 ? 36 x2
约束条件为:

?8 ? 25 ? x1 ? 8 ? 15 ? x2 ? 1800 ?8 ? 25 ? x ? 1800 ? 1 ? ?8 ? 15 ? x2 ? 1800 ? x1 ? 0, x2 ? 0 ?

线性规划模型:

min z ? 40 x1 ? 36 x2

?5 x1 ? 3 x2 ? 45 ?x ? 9 ? 1 s.t. ? x2 ? 15 ? ? x1 ? 0, x2 ? 0 ?

返 回 解答

–模型特点:目标函数(Objective function) –与约束条件(Constraint)均为线性的; –目标函数实现极大化或极小化。

线性规划问题的一般形式:
Max(Min)S=c1x1+c2x2+…..+cnxn s.t. a11x1+a12x2+….+a1nxn ?(=, ?)b1 a21x1+a22x2+….+a2nxn ?(=, ?)b2 …………………. am1x1+am2x2+….+amnxn ?(=, ?)bm x1,x2….xn ? 0

矩阵形式: min (max) u ? cx Ax ? (?)b s.t. vlb ? x ? vub

?

线性规划的基本概念 1.可行解(Feasible Solution)——任一满足约束条件的 一组决策变量的数值. 2.可行域(Feasible Region)——所有可行解组成的集合, 也称为可行解集. 3. 目标函数等值线(Objective function line)—— 为于同一直线上的点,具有相同的目标函数值.

线性规划模型的解的几种情况
线性规划问题

有可行解(Feasible)



可 行 解 (Infeasible)

有 最 优 解 ( Optimal )



最 优 (Unbounded)



数学建模中线性规划模型的常用解法 线性规划问题的求解在理在理论上有单纯型法,在实际建模 中常用以下解法:
1.图解法 2.LINGO软件包 3.Excel中的规划求解 4. MATLAB 软件包 主要介绍线性规划模型的MATlAB软件包和LINGO软件包解法

模型求解方法 1. 图解法
例1 max z=50x1+100x2 x1 + x2≤300 2x1 + x2≤400 x2≤250 x1、x2≥0

x2

2x1 + x2≤400 A B x2≤250 C D O z*=50x1+100x2=27500 x1 + x2≤300 x1 z2=14000

z1=50x1+100x2=0

该问题的最优解为x1=50;x2=250

用MATLAB优化工具箱解线性规划
1. 模型:

min z=cX
s.t. AX ? b

命令:x=linprog(c, A, b) 式中:linprog 称为调用函数,C, A, b 称为输入参数,全部由用户 提供,必须按规定的位置放置在原括号内. 2. 模型:min z=cX s.t. AX ? b Aeq ? X ? beq 命令:x=linprog(c,A,b,Aeq,beq)

AX 注意:若没有不等式: ? b 存在,则令A=[ ],b=[ ].

3. 模型:min z=cX s.t. AX ? b Aeq ? X ? beq VLB≤X≤VUB
命令:[1] x=linprog(c,A,b,Aeq, beq, VLB,VUB)

[2] x=linprog(c,A,b,Aeq, beq, VLB,VUB, X0)
注意:[1] 若没有等式约束: Aeq ? X ? beq , 则令Aeq=[ ], beq=[ ]. [2]其中X0表示初始点 ,设置它有些情况下可以减少 迭代工作量 4. 命令:[x,fval]=linprog(…)

返回最优解x及x处的目标函数值fval.

例1

max

s.t.

z ? 0.4x1 ? 0.28x2 ? 0.32x3 ? 0.72x4 ? 0.64x5 ? 0.6x6 0.01x1 ? 0.01x2 ? 0.01x3 ? 0.03 x4 ? 0.03 x5 ? 0.03 x6 ? 850 0.02x1 ? 0.05x4 ? 700 0.02x2 ? 0.05x5 ? 100 0.03x3 ? 0.08x6 ? 900 xj ? 0 j ? 1,2,?,6

解 编写M文件xxgh1.m如下: c=[-0.4 -0.28 -0.32 -0.72 -0.64 -0.6]; A=[0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08]; b=[850;700;100;900];

Aeq=[]; beq=[];
vlb=[0;0;0;0;0;0]; vub=[];

To MATLAB (xxgh1)

[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)

例2

min z ? 6x1 ? 3x2 ? 4x3 s.t. x1 ? x2 ? x3 ? 120 x1 ? 30 0 ? x2 ? 50 x3 ? 20

min z ? (6

3

? x1 ? ? ? 4) ? x2 ? ?x ? ? 3?

s.t.

?1 ? ?0

解: 编写M文件xxgh2.m如下: c=[6 3 4]; A=[0 1 0]; b=[50]; Aeq=[1 1 1]; beq=[120]; To MATLAB (xxgh2) vlb=[30,0,20]; vub=[]; [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)

? x1 1?? ? x2 1 0?? ?x ? 3 ? x1 ? ? 3 0? ? 0 ? ? ?x ? ? 2? ? 2 0? ? ? ? x3 ? 1

? ? 120 ? ? ?? ? ? ? 50 ? ? ?

例3 问题一的解答
改写为:

问题

min z ? ?13 9 10 11 12 8?X
0 0? ? 0.4 1.1 1 0 ? 800 ? ? ?X ? ? ? 0 ? ? 900 ? ? 0 0 0.5 1.2 1.3 ? ? ? ?
? x1 ? ? ? ? x2 ? ?x ? 3 ,X ?? ??0 ? x4 ? ?x ? ? 5? ?x ? ? 6?

s.t.

?1 0 0 1 0 0? ? 400 ? ? ? ? ? ? 0 1 0 0 1 0 ? X ? ? 600 ? ?0 0 1 0 0 1? ? 500 ? ? ? ? ?

编写M文件xxgh3.m如下: f = [13 9 10 11 12 8]; A = [0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3]; b = [800; 900]; Aeq=[1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1]; To MATLAB (xxgh3) beq=[400 600 500]; vlb = zeros(6,1); vub=[]; [x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub)

结果:
x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000 fval =1.3800e+004 即在甲机床上加工600个工件2,在乙机床上加工400个工件1、 500个工件3,可在满足条件的情况下使总加工费最小为13800.

例2 问题二的解答
改写为:

问题

? x1 ? min z ? ?40 36 ?? ? ?x ? ? 2? ? x1 ? s.t. ?? 5 ? 3?? ? ? (?45) ?x ? ? 2?

编写M文件xxgh4.m如下: c = [40 36]; A=[-5 -3]; b=[-45]; Aeq=[]; beq=[]; To MATLAB (xxgh4) vlb = zeros(2,1); vub=[9 15]; %调用linprog函数: [x,fval] = linprog(c,A,b,Aeq,beq,vlb,vub)

结果为: x = 9.0000 0.0000 fval =360 即只需聘用9个一级检验员.
注:本问题应还有一个约束条件:x1、x2取整数.故它是一个整数 线性规划问题.这里把它当成一个线性规划来解,求得其最优解刚 好是整数:x1=9,x2=0,故它就是该整数规划的最优解.若用线性规 划解法求得的最优解不是整数,将其取整后不一定是相应整数规划 的最优解,这样的整数规划应用专门的方法求解.

返 回

用LINDO、LINGO优化工具箱解线性规划
LINDO 公司软件产品简要介绍

美国芝加哥(Chicago)大学的Linus Schrage教授于1980 年前后开发, 后来成立 LINDO系统公司(LINDO Systems Inc.), 网址:http://www.lindo.com
LINDO: Linear INteractive and Discrete Optimizer LINGO: Linear INteractive General Optimizer What’s Best!: (SpreadSheet e.g. EXCEL) (V6.1) (V8.0) (V7.0)

LINDO API: LINDO Application Programming Interface (V2.0)

演示(试用)版、学生版、高级版、超级版、工业版、 扩展版… (求解问题规模和选件不同)

LINDO和LINGO软件能求解的优化模型
优化模型

连续优化

整数规划(IP)

线性规划 (LP)

二次规划 (QP)

非线性规划 (NLP) LINGO

LINDO

一、LINDO软件包
下面我们通过一个例题来说明LINDO 软件包的使用方法.

问题:一奶制品加工厂用牛奶生产A1, A2 两种奶制品,一桶

牛奶可以在甲类设备上用12小时生产成3公斤A1,或者在乙类设 备上用8小时加工成4公斤A2.据市场要求,生产的两种奶制品全部 能售出,且每公斤 A1获利24元,每公斤A2获利16元,现在每天加 工厂每天能得到50桶牛奶的供应,每天正式工人总的劳动时间为 480小时,并且甲类设备每天至多能加工100公斤A1,乙类设备的 加工能力没有限制.试为该厂制定一个生产计划,使每天获利最大, 并进一步讨论以下3个附加问题。 1)若用35元可以买到1桶牛奶,应否作这样的投资?若投资, 每天最多购买多少桶牛奶 2)若可以聘用临时工人以增加劳动时间,付给临时工人的 工资最多是每小时几元? 3)由于市场需求变化,每公斤A1的获利增加到30元,应否 改变生产计划?

基本 1桶 模型 牛奶 或

12小时

3kgA1

获利24元/kg

8小时 每天 50桶牛奶 时间480小时 至多加工100kgA1 决策变量 目标函数 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 24×3x1 获利 16×4 x2 每天获利 Max z ? 72 x1 ? 64 x2 原料供应
x1 ? x2 ? 50

4kgA2

获利16元/kg

约束条件

劳动时间 加工能力 非负约束

12x1 ? 8x2 ? 480 3x1 ? 100

线性 规划 模型 (LP)

x1 , x2 ? 0

模型求解
x1 ? x2 ? 50

图解法

约 l2 : 12x1 ? 8x2 ? 480 束 12x1 ? 8x2 ? 480 l4 条 3x1 ? 100 l3 : 3x1 ? 100 件 c l4 : x1 ? 0, l5 : x2 ? 0 x1 , x2 ? 0
0

l1 : x1 ? x2 ? 50

x2 A
l1 B l2 C z=3600 l3

目标 函数

Max z ? 72x1 ? 64x2
z =c (常数) ~等值线

l5
z=0

x1 D z=2400

在B(20,30)点得到最优解 最优解一定在凸多边 形的某个顶点取得。

目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线

模型求解
max 72x1+64x2 st
1)

软件实现

LINDO

OBJECTIVE FUNCTION VALUE 3360.000

2)x1+x2<50
3)12x1+8x2<480 4)3x1<100 end DO RANGE (SENSITIVITY) ANALYSIS? No

VARIABLE
X1 X2

VALUE
20.000000 30.000000

REDUCED COST
0.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES
2) 3) 0.000000 0.000000 48.000000 2.000000

4)

40.000000

0.000000

20桶牛奶生产A1, 30桶生产A2,利润3360元。

结果解释
max 72x1+64x2 st 2)x1+x2<50 3)12x1+8x2<480 4)3x1<100 end 原料无剩余 时间无剩余 加工能力剩余40
OBJECTIVE FUNCTION VALUE

1)
VARIABLE X1

3360.000
VALUE 20.000000 REDUCED COST 0.000000

X2

30.000000

0.000000
DUAL PRICES 48.000000

ROW SLACK OR SURPLUS 2) 0.000000

三 种 资 源

3)
4)

0.000000
40.000000

2.000000
0.000000

―资源” 剩余为零的约束为紧约束(有效约束)

结果解释
1) 3360.000

OBJECTIVE FUNCTION VALUE

VARIABLE
X1 X2

VALUE
20.000000 30.000000

最优解下“资源”增 加1单位时“效益”的 增量 REDUCED COST
0.000000 0.000000

影子价格

ROW SLACK OR SURPLUS DUAL PRICES
2) 3) 4) 0.000000 0.000000 40.000000 48.000000 2.000000 0.000000

原料增加1单位,利润增长48 时间增加1单位, 利润增长2 加工能力增长不影响利润

? 35元可买到1桶牛奶,要买吗?

35 <48, 应该买!

? 聘用临时工人付出的工资最多每小时几元?

2元!

最优解不变时目标函 RANGES IN WHICH THE BASIS IS UNCHANGED: 数系数允许变化范围
DO RANGE(SENSITIVITY) ANALYSIS?

Yes

OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 X2 ROW 2 72.000000 24.000000 8.000000

约束条件不变!
x1系数范围: (72-8, 72+24) = (64, 96)

64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES x2系数范围:(48,72) CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 50.000000 10.000000 6.666667

3
4

480.000000
100.000000

53.333332
INFINITY

80.000000
40.000000

x1系数由24 ?3=72 增至30?3=90<96, 在允许范围内

? A1获利增加到 30元/kg,应否改变生产计划?

不变!

结果解释 影子价格有意义时约束右端的允许变化范围
RANGES IN WHICH THE BASIS IS UNCHANGED: 目标函数不变! OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 X2 ROW 72.000000 24.000000 8.000000

原料 时 间 3
4

64.000000 8.000000 16.000000 原料最多增加10 RIGHTHAND SIDE RANGES CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 时间最多增加53

2

50.000000
480.000000 100.000000

10.000000
53.333332 INFINITY

6.666667
80.000000 40.000000

? 35元可买到1桶牛奶, 每天最多买多少?

最多买10桶!

模型求解
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1 X2 3360.000 VALUE 20.000000 30.000000 REDUCED COST 0.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 4) 0.000000 0.000000 40.000000 2 48.000000 2.000000 0.000000

reduced cost值表 示当该非基变量 增加一个单位时 (其他非基变量 保持不变),目标 函数减少的量(对 max型问题) . 也可理解为: 为了使该非基变 量变成基变量, 目标函数中对应 系数应增加的量

NO. ITERATIONS=

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

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

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

二、LINGO软件包

1. LINGO软件简介
(1) LINGO模型的优点
?包含了LINDO的全部功能 ?提供了灵活的编程语言(矩阵生成器)

(2) 对简单的LINGO程序 ?LINGO也可以和LINDO一样编程 ?但LINGO与LINDO语法有差异

Lindo与简单Lingo程序的比较

?lindo程序:
min 7x1+3x2 st x1+x2>=345.5 x1>=98 2*x1+x2<=600 end gin 2

?lingo程序:
Model: min=7*x1+3*x2; x1+x2>=345.5; x1>=98; 2*x1+x2<=600; @gin(x1); @gin(x2); end

实验作业
某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克, 工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20 名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其 他条件所限甲饮料产量不超过800箱.问如何安排生产计划,即 两种饮料各生产多少使获利最大.进一步讨论: 1)若投资0.8万元可增加原料1千克,问应否作这项投资. 2)若每100箱甲饮料获利可增加1万元,问应否改变生产计 划.

返 回

运输问题 ---Transportation Problem 运输问题(Transportation Problem) 以知有m个生产地点(source)Ai,i=1,…,m,可供 应某种物资,其供应量(产量)(supply)为ai,i=1,…, m;有n个销售地点(destination)Bj,j=1,…,n,需要 该种物资,其需要量(产量)(demand)为bj,j=1,…, n;从Ai到Bj运输单位物资的运价(单价)为cij;设 Σai=Σbj,这些数据可汇总于如下产销平衡表,现要制 定一个使总运费最小的调运方案。

产销平衡表(cost and requirement table)
销地 产地

B1 c11 c21 … cm1 b1

B2 c12 c22 … cm2 b2

… … … … … …

Bn c1n c2n … cmn bn

产量 a1 a2 … am
Σbj Σai

A1 A2 … Am 销量

若用xij表示从Ai到Bj的运量,在产销平衡的条件下, 要求得总运费最小的调运方案,其数学模型如下 (模型Y)

min f ?

??c
i ?1 j ?1

m

n

ij

x ij

? n i ? 1, ? , m ?? x ij ? a i ? j ?1 ? m ? j ? 1, ? n ?? x ij ? b j ? i ?1 ? x ij ? 0, i ? 1, ? , m; j ? 1, ? , n ? ? ?

产销不平衡的运输问题 ----Total Supply not Equal to Total Demand
一、产大于销(total supply exceeds total demand) ? 产大于销的运输问题的特征是Σ ai >Σ bj,其数学模型为:

min f ? ?? cij xij
i ?1 j ?1

m

n

? n i ? 1,?, m ?? xij ? ai ? j ?1 ?m ? j ? 1,? n ?? xij ? b j ? i ?1 ? xij ? 0, i ? 1,?, m; j ? 1,?, n ? ? ?

– 解此类问题可假想一个销地Bn+1 ,其需要量为:bn+1=Σ ai - Σ bj;若用xi,n+1表示从Ai到Bn+1的运量, 可令ci,n+1=0或等于 第Ai产地储存单位物资的费用。 因为xi,n+1实际上表示Ai产地 没有运出去而库存的物资数量。经处理后,问题变成了产销平 衡的运输问题,其数学模型为:

min f ? ?? cij xij
i ?1 j ?1

m

n ?1

? n ?1 i ? 1,?, m ?? xij ? ai ? j ?1 ?m ? j ? 1,? n ? 1 ?? xij ? b j ? i ?1 ? xij ? 0, i ? 1,?, m; j ? 1,?, n ? 1 ? ? ?
这样,m个产地、n个销地的不平衡运输问题,转化成了m个产地、 n+1个销地的平衡运输问题,此时可用表上作业法求解。

二、销大于产(total demand exceeds total supply) ? 销大于产的运输问题的特征是Σ ai < Σ bj,其数学模型为:

min f ? ?? cij xij
i ?1 j ?1

m

n

? n i ? 1,?, m ?? xij ? ai ? j ?1 ?m ? j ? 1,? n ?? xij ? b j ? i ?1 ? xij ? 0, i ? 1,?, m; j ? 1,?, n ? ? ?

? 解此问题可假想一个产地Am+1,其产量为:am+1 = Σ bj-Σ ai; 若用xm+1,j表示从Am+1到Bj的运量,可令cm+1,j=0或等于第Bj产地每 缺单位物资的损失。因为xm+1,j实际上表示Bj销地所缺的物资数量。 经处理后,问题变成了产销平衡的运输问题,其数学模型为:

min f ? ?? cij xij
i ?1 j ?1

m ?1 n

?n i ? 1, ? , m ? 1 ?? xij ? ai ? j ?1 ? m?1 ? j ? 1, ? n ?? xij ? b j ? i ?1 ? xij ? 0, i ? 1, ? , m ? 1; j ? 1, ? , n ? ? ?
?此时,可用表上作业法求解。

例 某公司有6个供货栈(仓库),库存货物总数分别为60,55,51,43, 41,52,现有8个客户各要一批货数量分别为35,37,22,32,41,32, 43,38,各供货栈道8个客户的单位货物运输价见表 供货栈到客户的单位货物运价
客户 货栈 W1 W2 W3 W4 W5 W6 V1 6 4 5 7 2 5 V2 2 9 2 6 3 5 V3 6 5 1 7 9 2 V4 7 3 9 3 5 2 V5 4 8 7 9 7 8 V6 2 5 4 2 2 1 V7 5 8 3 7 6 4 V8 9 2 3 1 5 3

试确定各货栈到各客户处的货物调运数量,使总的运输费用最小。

解 引入决策变量

代表从第

个货栈到第 个

客户的货物运量. 设 表示从第 个货栈到第 个客户的单位货物 表示第 个货栈的最大供货量, 表示第 个客户的订货量.

目标函数是总运输费用最少.
约束条件有三条:1. 各货栈运出的货物总量不超过其库存数 2.各客户收到的货物总量等于其订货数量 3. 决策变量 非负

数学模型为

前面介绍的LinGO的基本用法,其优点是输入模型较直观, 一般的数学表达式无需作大的变换即可直接输入.对于规模较 小的的规划模型,用直接输入的方法是有利的,如果模型的 变量和约束的条件个数比较多,若仍然用直接的输入方式, 虽然也能求解并得到结果,但这种做法有明显的不足之处。 模型的篇幅很长,不便于分析修改和扩展。 LinGO 建模语言引入集合的概念,为建立大规模的数学规 划模型提供了方便. 用LinGO 语言表达一个实际优化问题, 称之为 LinGO模型。 一、集合定义部分
集合是一组相关对象构成的组合,代表模型中的实际事物,并与数学变量与 常量联系起来,是实际问题到数学的抽象。例中的6个仓库可以看成一个集合, 8个客户可以看成另一个集合。

每个集合在使用之前需要预先给出定义,定义集合时要明确三方面的内容:集合 的名称,集合内的成员(元素)、集合的属性(可以看成与该集合有关的变量 或常量,相当于数组). 本例首先定义仓库集合:WH/W1..W6/:AI; 其中WH是集合的名称,W1..W6是集合内的成员, “..” 是特定的省略号 (如果不用该省略号,也可以把成员一一罗列出来,成员之间用逗号或 空格分开),表明该集合有6个成员,分别对应于6个供货栈,AI是集合的属性, 它可以看成是一个数组,有6个分量,分别表示各货栈现有货物的总数。

集合、成员、属性的命名规则与变量相同,可按自己的意愿,用有一定意义 的字母数串来表示,式中“/ ”和“/:” 是规定的语法规则。
本例再定义客户集合:VD/V1..V8/:DJ; 该集合有8个成员,DJ 是集合的属性(有8个分量)表示各客户的需求量.

以上两个集合称为初始集合(或称基本集合、原始集合)初始集合的属性都 相当于一维数组。

为表示数学模型中从货栈到客户的运输关系以及与此相关的运输单价 再定义一个表示运输关系的集合: LINKS(WH,VD): C,X;

和运量

该集合以初始集合WH 和 VD 为基础,称为衍生集合(或称派生集合). C 和 X 是该衍生集合的两个属性,衍生集合的定义语句有如下要素组成: 1)集合的名称; (2) 集合的初始集合; (3)集合的成员(可以省略不写); (4)集合的属性(可以没有)

定义衍生集合时可以用罗列的方式将衍生集合成员一一列举出来,如果省略不写,则 默认衍生集合的成员取它所对应初始集合的所有可能组合,上述衍生集合LINKS的定 以中没有指明成员,则它对应的初始集合WH 有6个成员,VD 有8 个成员,因此 LINKS 成员取WH和VD的所有可能组合,即有48个成员,48个成员可以排列成一个矩阵。其 行数与集合WH的成员个数相等,列数与集合VD成员的个数相等. 相应地,集合LINKS的 属性C和X都相当于二维数组,各有48个分量,C表示货栈Wi 到客户Vj的单位货物运价 X 表示货栈Wi到客户Vj的货物运量.

本模型完整的集合定义为: SETS: 注:集合定义部分以语句 SETS: 开始, WH/W1..W6/:AI; 以ENDSETS语句结束,这两个语句需单独成一行, VD/V1..V8/DJ; ENDSETS后面不加标点符号. LINKS(WH,VD):C,X; ENDSETS 二、数据初始化(数据段)

以上集合中属性X(有48个分量)是决策变量,是待求的未知数, 属性AI、DJ和C(分别有6,8,48个分量)都是已知数,LINKS 建模 语言通过数据初始化部分来实现对已知属性赋以初始值,格式为:
DATA: AI=60,55,51,43,41,52; DJ=35,37,22,32,41,32,43,38; C=6,2,6,7,4,2,5,9 4,9,5,3,8,5,8,2 注:数据初始化部分以语句 DATA:开始,以 5,2,1,9,7,4,3,3 ENDDATE语句结束,这两个语句需单独成一行,数 7,6,7,3,9,2,7,1 据之间的逗号和空格可以互换。 2,3,9,5,7,2,6,5 5,5,2,2,8,1,4,3; ENDDATA

三、目标函数和约束条件 目标函数表达式 MIN=@SUM(LINKS(I,J):C(I,J)*X(I,J)); 式中,@SUM 是LINGO提供的内部函数,其作用是对某个集合的所有成员 求制定表达式的和,该函数需要两个参数,第一个参数是集合名称,制定对该 集合的所有成员求和,如果此集合是一个初始集合,它有m 个成员,则求和运算 对m 个成员进行,相当于求 ,第二个参数是一个表达式,表示求和运算对该 表达式进行,此处, @SUM的第一个参数是 LINKS(I,J),表示求和运算 对 LINKS进行, 该集合的维数为2,共有48个成员,运算规则是:先对48个成员 分别求表达式 C(I,J) *X(I,J) 的值,然后求和,相当于求 ,表达式中的 C 和 X是集合的两个属性,它们各有48个分量。 注:如果表达式中参与酸的属性属于 同一个集合,则 语句中索引(相当于 矩阵或数组的下标可以省略)(隐 藏),假如表达式中参与运算的属性 属于不同的集合,则不能省略属性的 索引.本例的目标函数可以表示成 MIN=@SUM(LINKS:C*X); 用LINGO语句表示为

约束条件

用LINGO 语言描述该约束条件,语句为: @FOR(WH(I): @SUM(VD(J):X(I,J))<=AI(I)); 语句中的@FOR 是LINGO提供的内部函数,它的作用是对某个集合的所有成员 分别生成一个约束表达式,它有两个参数,第一个参数是集合名,表示对该集合 的所有成员生成对应的约束表达式,上式@ FOR 的第一个参数为WH,它表示 货栈,共有6个成员,故应生成6个约束表达式,@FOR 的第二个参数是约束 表达式的具体内容,此处再调用@SUM 函数,表示该约束的左边是求和,是对集合 VD的8个成员,并且对表达式X(I,J) 中的第二维 J 求和,即 约束表达式的右边是集合WH的属性AI,它有6个分量,与6个约束表达式一一对应, 本句中的属性分别属于不同的集合,所以不能省略 I,J. 约束条件 表示为

@FOR(D(J)):@ SUM(VD(J):X(I,J))=DJ(J));

完整的模型MODEL: 以“MODEL:”开 SETS: 始 集合定义部分从 WH/W1..W6/:AI; (―SETS:”到 VD/V1..V8/:DJ; LINKS(WH,VD):C,X; “ENDSETS‖ ): ENDSETS 定义集合及其属性 DATA: AI=60,55,51,43,41,52; DJ=35,37,22,32,41,32,43,38; C=6,2,6,7,4,2,5,9 4,9,5,3,8,5,8,2 集合定义部分从 5,2,1,9,7,4,3,3 (“DATA:”到 7,6,7,3,9,2,7,1 “ENDDATA” ) 2,3,9,5,7,2,6,5 5,5,2,2,8,1,4,3; ENDDATA MIN=@SUM(LINKS (I,J):C(I,J)*X(I,J)); !目标函数 @FOR(WH(I): @SUM(VD(J):X(I,J))<=AI(I)); !约束条件 给出优化目 @FOR(VD(J):@SUM(VD(J):X(I,J))=DJ(J)); 和约 END

?

以“END‖结 束

?

整数规划 -----Integer Programming, IP
整数规划(Integer Programming)主要是指整数线 性规划。一个线性规划问题,如果要求部分决策变量 为整数,则构成一个整数规划问题。 所有变量都要求为整数的称为纯整数规划(Pure Integer Programming)或称全整数规划(All integer Programming); 仅有一部分变量要求为整数的称为混合整数规划 (Mixed Integer Programming); 有的变量限制其取值只能为0或1,这类特殊的整数规 划称为0-1规划(0-1 Integer Programming )

整数规划问题及其数学模型
例 某工厂生产甲、乙两种设备,已知生产这两种 设备需要消耗材料A、材料B,有关数据如下, 问这两种设备各生产多少使工厂利润最大?
设备 材 料 材料A(kg) 材料B(kg) 利润(元/件)


2 1 3


3 0.5 2

资源限量
14 4.5

解:设生产甲、乙这两种设备的数量分别为x1、x2,由 于是设备台数,则其变量都要求为整数,建立模型 如下: Maxz=3x1+2x2 2x1+3x2≤14 x1+0.5x2≤4.5 x1、x2≥0,且为整数

图4-1

要求该模型的解,不考虑整数约束条件,用图解法 对相应线性规划求解,其最优解为:x1=3.25 x2 =2.5 max z=14.75
----凑整得到的(4,2)不在可行域范围内。 --(3,2)点尽管在可行域内,但没有使目标达到极大化。 --(4,1)使目标函数达到最大,即z=14。

IP可用LINDO直接求解
―gin 2‖表示“前2个变量为 整数”,等价于: gin x1 gin x2 max 3x1+2x2 st 2x1+3x2<14 x1+0.5x2<4.5 end gin 2

其中“GIN 2”表示2个变量都是一般整数变量。 (仍然默认为取值是非负的)

LINDO可用于求解线性纯整数规划或混合整数规划(IP),

模型的输入与LP问题类似, 但需在END标志后定义整型变量。
0/1型的变量可由INTEGER(可简写为INT)命令来标识, 有以下两种可能的用法: INT vname INT n 前者只将决策变量vname标识为0/1型, 后者将当前模型中前n 个变量标识为0/1型(模型中变量顺序由 模型中输入时出现的先后顺序决定, 该顺序可由输出结果中的 变量顺序查证是否一致)。 一般的整数变量可用命令GIN (是GENERAL INTEGER的意 思),其使用方式及格式与INT 命令相似。。

SET SET

X2 TO <= 2 AT 1, BND= 14.50 TWIN= 13.50 X1 TO >= 4 AT 2, BND= 14.00 TWIN= 13.00

7 10

NEW INTEGER SOLUTION OF 14.0000000 BOUND ON OPTIMUM: 14.00000 DELETE X1 AT LEVEL 2 DELETE X2 AT LEVEL 1 ENUMERATION COMPLETE. BRANCHES=

AT BRANCH

2 PIVOT

10

2 PIVOTS=

10

LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION...
OBJECTIVE FUNCTION VALUE

最优值

1)

14.00000

VARIABLE VALUE REDUCED COST X1 4.000000 -3.000000 X2 1.000000 -2.000000
松弛和剩余变量(SLACK OR SURPLUS) 仍然可以表示约束的松紧程度,但目前IP尚无 相应完善的敏感性分析理论,因此REDUCED COST和DUAL PRICES的结果在整数规划中 意义不大。

ROW SLACK OR SURPLUS DUAL PRICES 2) 3.000000 0.000000 3) 0.000000 0.000000

NO. ITERATIONS= 10 BRANCHES= 2 DETERM.= 1.000E 0

例2、集装箱运货
货物 体积(米3/箱) 重量(百公斤/箱) 利润(千元/箱)



装运限制

5
4

2
5

20
10

24

13

解:设X1 , X2 为甲、乙两货物各托运箱数

maxZ = 20 X1 + 10 X2
5X1+4X2 ? 24 2X1+5X2 ? 13 X1 , X2 ?0 X1 , X2为整数

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

5

衣服

4

5

15

解:Xi为是否带第 i 种物品 maxZ=20X1 + 30X2 +10X3+18X4 +15X5 5X1+3X2 +X3 +2X4 +4X5 ? 8 2X1+X2 +4X3 +3X4 +5X5 ? 10
Model: Model: Min=-(20*x1+30*x2+10*x3+18*x4+15*x5); 5*x1+3*x2+x3+2*x4+4*x5<8; 2*x1+x2+4*x3+2*x4+5*x5<10; @bin(x1);@bin(x2); @bin(x3);@bin(x4); @bin(x5); END

Xi为0, 1

Lingo求解

Global optimal solution found. Objective value: Extended solver steps: Total solver iterations:

-58.00000 0 0

Variable X1 X2 X3 X4 X5

Value 0.000000 1.000000 1.000000 1.000000 0.000000

Reduced Cost -20.00000 -30.00000 -10.00000 -18.00000 -15.00000

Row Slack or Surplus Dual Price 1 -58.00000 -1.000000 2 2.000000 0.000000 3 3.000000 0.000000

0-1整数规划用(Applications) (一)相互排斥的计划(Mutually exclusive planning) 例4.6 某公司拟在市东、西、南三区中建立门市部,有7个 点Ai (i=1,2,…,7)可供选择,要求满足以下条件:

(1)在东区,在A1,A2,A3三个点中至多选两个;
(2)在西区,A4,A5两个点中至少选一个;

(3)在南区,A6,A7两个点为互斥点。
(4)选A2点必选A5点。 若Ai点投资为bi万元,每年可获利润为ci万元,投资总额为 B万 元,试建立利润最大化的0-1规划模型。

解:设决策变量为

?1, xi ? ? ?0,

当Ai点被选用 当Ai点未被选用

i ? 1,2,?,7

建立0-1规划模型如下:

max z ? c1 x1 ? c2 x2 ? ? ? c7 x7
? 7 bi ? xi ? B ? ? i ?1 ? x1 ? x 2 ? x3 ? 2 ? s.t ? x 4 ? x5 ? 1 ?x ? x ? 1 7 ? 6 ? x 2 ? x5 ? 0 ? ? xi ? 0,或1, i ? 1,2, ? ,7

?

(二)相互排斥的约束条件(Mutually exclusive constraints) 例4.7 某产品有A1和A2两种型号,需要经过B1、B2、B3三道工 序,单位工时和利润、各工序每周工时限制见表所示,问工 厂如何安排生产,才能使总利润最大?(B3工序有两种加工 方式B31和B32,产品为整数)。

工时/件

工序

B3 B1 B2 B31 B32 0.2

型号 A1

利润(元/ 件)
25

0.3

0.2

0.3

A2
每周工时(小 时/月)

0.7
250

0.1
100

0.5
150

0.4
120

40

解:设A1、A2产品的生产数量分别为x1、x2件,在不考虑B31和 B32相互排斥的情况下,问题的数学模型为

max z ? 25x1 ? 40 x2

?0.3x1 ? 0.7 x2 ? 250 ? ?0.2 x1 ? 0.1x2 ? 100 ? s.t.?0.3x1 ? 0.5 x2 ? 150 ?0.2 x ? 0.4 x ? 120 1 2 ? ? x1 , x2 ? 0, 且为整数 ?

(1) (2)

工序B3只能从两种加工方式中选择一种,那么约束条件(1)和 (2)就成为相互排斥的约束条件。为了统一在一个问题中, 引入0-1变量

则数学模型为

?1, yi ? ? ?0,

B3采用B3i 加工方式 B3不采用B3i 加工方式
max z ? 25x1 ? 40 x2

i ? 1,2

?0.3 x1 ? 0.7 x2 ? 250 ? ?0.2 x1 ? 0.1x2 ? 100 ?0.3 x1 ? 0.5 x2 ? 150 ? M (1 ? y1 ) ? s.t.?0.2 x1 ? 0.4 x2 ? 120 ? M (1 ? y 2 ) ?y ? y ?1 2 ? 1 ? x1 , x2 ? 0, 且为整数 ? ? y1 , y 2 ? 0或1

(三)固定成本问题(Fixed cost problem) 例4.8 某公司制造小、中、大三种尺寸的容器,所需资源为金属 板、劳动力和机器设备,制造一个容器所需的各种资源的数量 如下表所示:不考虑固定费用,小、中、大号容器每售出一个 其利润分别为4万元、5万元、6万元,可使用的金属板有500吨, 劳动力有300人/月,机器有100台/月,若生产,不管每种容器 生产多少,都需要支付一笔固定费用:小号为100万元,中号 为150万元,大号为200万元。问如何制定生产计划使获得的利 润最大?
资源 金属板(吨) 劳动力(人/月) 机器设备(台/月) 小号容器 2 中号容器 4 大号容器 8

2 1

3 2

4 3

解:设x1、x2、x3分别为小号容器、中号容器、大号容器的 生产数量。不考虑固定费用,则问题的数学模型为

max z ? 4 x1 ? 5x2 ? 6 x3
?2 x1 ? 4 x2 ? 8 x3 ? 500 ? ?2 x1 ? 3x2 ? 4 x3 ? 300 s.t.? ? x1 ? 2 x2 ? 3 x3 ? 100 ? x1 , x2 , x3 ? 0 ?

若考虑固定费用就必须引入0—1变量:

?1, yi ? ? ?0,

当生产第i种容器即xi ? 0时 当不生产第i种容器时即xi ? 0

i ? 1,2,3

则该问题的数学模型为 max z ? 4x1 ? 5x2 ? 6x3 ? 100y1 ? 150y2 ? 200y3
?2 x1 ? 4 x2 ? 8 x3 ? 500 ? ?2 x1 ? 3 x2 ? 4 x3 ? 300 ? x1 ? 2 x2 ? 3 x3 ? 100 ? ? x1 ? My1 ? 0 s.t .? ? x2 ? My 2 ? 0 可以看出,当xj>0时,为使Z 极大化, ? x3 ? My3 ? 0 应有Yj=0 ? ? x1 , x2 , x3 ? 0 ? y , y , y ? 0or1 ? 1 2 3

(四)布点问题(Location Problem) 例4.9 某城市消防队布点问题。该城市共有6个区,每个区都 可以建消防站,市政府希望设置的消防站最少,但必须满 足在城市任何地区发生火警时,消防车要在15 分钟内赶到 现场。据实地测定,各区之间消防车行驶的时间见表4-9, 请帮助该市制定一个布点最少的计划。
表4-9 消防车在各区间行驶时间表
地区1 地区1 地区2 地区3 地区4 0 10 16 28 地区2 10 0 24 32 地区3 16 24 0 12 地区4 28 32 12 0

单位:min
地区5 27 17 27 15 地区6 20 10 21 25

地区5
地区6

27
20

17
10

27
21

15
25

0
14

14
0

解:引入0-1变量xi作决策变量,令
?1, xi ? ? ?0, 表示在地区 设消防站 i 表示在地区 不设消防站 i i ? 1,2, ?,6

本问题的约束方程是要保证每个地区都有一个消防站在15分 钟行程内。如地区1,由表4-9可知,在地区1及地区2内设 消防站都能达到此要求,即x1+x2≥1 因此本问题的数学模型为: min z=x1+x2+x3+x4+x5+x6 x1+x2 x1+x2 x3+x4 ≥1 +x6 ≥1 ≥1 x3+x4+x5 ≥1 x4+x5+x6 ≥1

x2 +x5+x6 ≥1 xi=1或0 (i=1,…,6)

(五)指派问题(Assignment problem)
? 指派问题是一种特殊的整数规划问题。在实践中经常会遇到一种 问题:某单位有m项任务要m个人去完成(每人只完成一项工 作),在分配过程中要充分考虑各人的知识、能力、经验等,应 如何分配才能使工作效率最高或消耗的资源最少?这类问题就属 于指派问题。引入0-1变量xij

?1 指派第i个人完成第j项任务 x ij ? ? ?0 不指派第i个人完成第j项任务
min z ?

??
i ?1 j ?1

m

m

cij xij

?m ?? xij ? 1 ? j ?1 ?m ? s.t ?? xij ? 1 ? i ?1 ? xij ? 0或1 ? ? ?

i ? 1,2, ?, m j ? 1,2, ?, m

案例:福尔市场营销调查指派问题 ? 福尔市场营销调查公司有3个新客户需要进行市场调查, 目前正好有3个人没有其他工作,由于他们的对不同市场 的经验和能力不同,估计他们完成不同任务所需时间如 下表。公司面临的问题是如何给每个客户指派一个项目 主管(代理商),使他们完成市场调查的时间最短。
预计完成时间
客户 项目主管 1 2 3

1 2 3

10 9 6

15 18 14

9 5 3

设xij=1表示指派主管i完成第j项市场调查, 否则xij=0 则问题的数学模型为:
min f= 10x11+15x12+9x13+9x21+18x22+5x23+6x31+14x32+3x33 x11+x12+x13 = 1 x21+x22+x23 = 1 x31+x32+x33 = 1 x11+x21+x31 = 1 x12+x22+x32 = 1 x13+x23+x33 = 1 xij≥0,i=1,2,3;j=1,2,3

MODEL: SETS: SUPERVISOR/S1,S2,S3/; CUSTOMER/C1,C2,C3/; LINKS(SUPERVISOR,CUSTOMER):C,X; ENDSETS DATA: C=10,15,9, 9,18,5, 6,14,3; ENDDATA MIN=@SUM(LINKS:C*X); @for(SUPERVISOR(I):@SUM(CUSTOMER(J):X(I,J))=1); @for(CUSTOMER(J): @SUM(SUPERVISOR(I):X(I,j))=1); @for(LINKS:@bin(X)); END

Global optimal solution found. Objective value: 26.00000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost C( S1, C1) 10.00000 0.000000 C( S1, C2) 15.00000 0.000000 C( S1, C3) 9.000000 0.000000 C( S2, C1) 9.000000 0.000000 C( S2, C2) 18.00000 0.000000 C( S2, C3) 5.000000 0.000000 C( S3, C1) 6.000000 0.000000 C( S3, C2) 14.00000 0.000000 C( S3, C3) 3.000000 0.000000 X( S1, C1) 0.000000 10.00000 X( S1, C2) 1.000000 15.00000 X( S1, C3) 0.000000 9.000000 X( S2, C1) 0.000000 9.000000 X( S2, C2) 0.000000 18.00000 X( S2, C3) 1.000000 5.000000 X( S3, C1) 1.000000 6.000000 X( S3, C2) 0.000000 14.00000 X( S3, C3) 0.000000 3.000000

1.一般模型: 设c ij ? 0 : 第i个人完成第 项任务的效率 j (时间成本等) ?1 第i个人完成第 项任务 j ? 引入x ij ? ? 否则 ?0 ? 模型: n n ?min f ? ? ? c x ij ij ? i ?1 j ?1 ? s .t . n x ? 1, j ? 1,?, n 每项任务一人 ? ? ij i ?1 (P)? n ? ? x ij ? 1, i ? 1,?, n 每人一项任务 j ?1 ? x ij ? 0或1 ? ?

多目标规划

一、多目标规划问题的提出
多目标问题是现实世界中普遍遇到的一类问 题,其中希望(或必须)考虑多个相互矛盾目标 的影响。 例如证券投资问题中我们希望利润最大 而风险最小,生产销售问题中我们希望费用 较少而获利很大,等等。

主要介绍: ?如何建立目标规划模型 ?如何求解、分析结果 ?如何将求解结果与实际问题联系起来

单目标模型只需简单确定一个目标,而将其 余的列为约束;
在构建多目标模型时,则需要对问题有较 深的理解,必须考虑更全面——虽然费时较多, 却非常有益,更切合实际。

例1 利润最大化问题: 某工厂在计划期内要安排生产Ⅰ、 Ⅱ两种产品,已知 有关数据如下表所示:
原材料 kg Ⅰ 2 Ⅱ 1 拥有量 11

设备台时 hr 利润 元/件

1 8

2 10

10

试求获利最大的方案。 解:这是一个单目标规划问题,可用线性规划模 型表述为:

目标函数

max z = 8x1+10x2
10

x1 + 2x2 ≤ 10

约束条件 2x1 + x2 ≤11 x1 + 2x2 ≤ 10 x1 , x2 ≥ 0
8x1+10x2=c

8

6

4

2

1

2

3

4

5

6

可用图解法求得最优决策方案为: x1*=4, x2*=3, z*=62

2x1 + x2 ≤11

从线性规划的角度来看,问题似乎已经 得到了圆满的解决 。

但是,如果站在工厂计划人员的立场上对此 进行评价的话,问题就不是这么简单了。 第一,这是一个单目标最优化问题。但是, 一般来说,一个计划问题要满足多方面的要 求。例如 财务部门
利润目标:利润尽可能大 节约资金:消耗尽可能小 适销对路:产品品种多样 安排生产:产品批量尽可能大

物资部门
销售部门 计划部门

一个计划问题实际上是一个多目标决策问 题。只是由于需要用线性规划来处理,计划人 员才不得不从众多目标要求中硬性选择其一, 作为线性规划的目标函数 。 但这样做的结果严重违背了某些部门的愿 望,因而使生产计划的实施受到影响;或者在 一开始就由于多方面的矛盾而无法从多个目标 中选出一个目标来。

第二,线性规划有最优解的必要条件是其可行 解集非空,即各约束条件彼此相容。但是,实 际问题有时不能满足这样的要求 。
例如,由于设备维修、能源供应、其它产品生 产需要等原因,计划期内可以提供的设备工时 不能满足计划产量工时需要 。 或由于储备资金的限制,原材料的最大供应 量不能满足计划产量的需要

第三,线性规划解的可行性和最优性具有十分 明确的意义,但那都是针对特定数学模型而言 的。 在实际问题中,决策者在作决策时,往往 还会对它作某种调整和修改,其原因可能是由 于数学模型相对于实际问题的近似性
近似性 建模时对实际问题的抽象 建模时未考虑到的新情况

决策者需要计划人员提供的不是严格的数学 上的最优解,而是可以帮助做出最优决策的 参考性的计划,或是提供多种计划方案

现代决策强调定量分析和定性分析相结合, 强调硬技术和软技术相结合,强调矛盾和冲突 的合理性,强调妥协和让步的必要性。线性规 划无法胜任这些要求。 1961年,查恩斯(A.Charnes)和库柏(W.w.CooPer) 提出目标规划(goal programming),得到广泛重视 和较快发展。 目标规划在处理实际决策问题时,承认各项决 策要求(即使是冲突的)的存在有其合理性;在作 最终决策时,不强调其绝对意义上的最优性。 因此,目标规划被认为是一种较之线性规划更 接近于实际决策过程的决策工具 。

求解多目标决策常用的三种方法(或思想):
1. 加权或效用系数法 2. 序列或优先级法 3. 有效解(非劣解)法

1. 加权法:
加权法把问题中的所有目标用统一的单位来度量(例 如用钱或效用系数) ? 这种方法的核心是把多目标模型化成单目标模型。 优点:适于计算机求解 (例如模型是线性的时候可用一般的单纯形法求解)

缺点:难处在于如何寻到合理的权系数。 例如建设高速公路时,既希望减少开支又希望降低交 通伤亡事故,此时能否用金钱来衡量一个人的生命价 值呢? 2. 序列或优先级法: 序列或优先级法不是对每个目标加权,而是按照目标 的轻重缓急,将其分为不同等级再求解。 优点:避免了权系数的困扰,绝大多数决策者都能采 用,事实上他们在许多决策中也正是这样做的。 例如决定人员的提升时,许多单位是按其工作态度、 工作能力及对单位的有效价值等这样一个先后顺序来 进行评定的。

缺点:难处在于如何确切地定出各个目标的优先顺序 以获得满意的求解结果。 即没有任何其他方案 能在各个方面完全胜 出这个解

3. 有效解(或非劣解)法:

有效解(或非劣解)法“不会产生”象加权法或优先 级法所具有的局限性,它将找出全部有效解集(即非 劣解)以供决策者从中挑选。 缺点:难处在于实际问题中非劣解太多,难于一一推 荐给决策者。

二、多目标规划模型的建立及图解法

例1 利润最大化问题: 某工厂在计划期内要安排生产Ⅰ、 Ⅱ两种产品,已知 有关数据如下表所示:
原材料 kg 设备台时 hr 利润 元/件 Ⅰ 2 1 8 Ⅱ 1 2 10 拥有量 11 10

试求获利最大的方案。 解:这是一个单目标规划问题,可用线性规划模 型表述为:

目标函数

max z = 8x1+10x2
10

x1 + 2x2 ≤ 10

约束条件 2x1 + x2 ≤11 x1 + 2x2 ≤ 10 x1 , x2 ≥ 0
8x1+10x2=c

8

6

4

2

1

2

3

4

5

6

可用图解法求得最优决策方案为: x1*=4, x2*=3, z*=62

2x1 + x2 ≤11

在实际决策时,还应考虑市场等一系列其他条件,如:
(1)市场调查发现:Ⅰ的销量有下降趋势,故应考虑 适当减少Ⅰ的产量增加Ⅱ的产量,使Ⅰ< Ⅱ

(2)原材料的价格不断上涨,增加供应会使成本提高。 故不考虑再购买原材料。

(3)为提高效率,应充分利用设备,但不希望加班。
(4)市场虽发生变化,但利润应尽可能达到或超过56 元。 此时的决策是多目标决策问题——目标规划方 法是解决这类决策问题的方法之一。

一、与建立目标规划模型有关的概念
1. 正、负偏差变量d+,dd+ : 决策值超过目标值的部分

d-

:决策值未达到目标值的部分
恒有 d+×d-=0

例如目标 z = 8x1+10x2 可以变化为目标约束: 8x1+10x2+d1--d1+=56 绝对约束 2x1 + x2 ≤11 可以变换为目标约束: 2x1 + x2 +d2--d2+=11

硬约束 2. 绝对约束、目标约束 绝对约束:必须严格满足的等式或不等式约束

目标约束:目标规划所特有的约束,约束右端项看作 要追求的目标值,在达到目标值时,允许发生正或负 的偏差 软约束
例如,原材料的价格不断上涨,增加供应会使成 本提高。故不考虑再购买原材料 从而 2x1 + x2 ≤11 是硬约束

3 . 优先因子与权系数
目标规划问题常常有多个目标,但这些目标的主 次或轻重缓急是不同的。 最重要的目标赋予优先因子P1,次一级的目标赋 予优先因子P2,…,并规定 Pk>>Pk+1——即表示 Pk 比Pk+1有更大的优先权。 如果要区别具有相同优先因子的两个目标的差别, 则分别赋予它们不同的权系数wj。

d+
4 .目标规划的目标函数

: 决策值超过目标值的部分
min z = f ( d+, d- )

三种基本形式:
目标类型 fi(x) ≤ bi fi(x) ≥ bi fi(x) = bi 目标规划格式 fi(x)+ d--d+ = bi fi(x)+ d--d+ = bi fi(x)+ d--d+ = bi 需要极小化 的偏差变量 d+ d- d-+d+

例2

例1的目标规划模型:
1.原材料供应受严格限制

2x1 + x2 ≤11

硬约束

2.产品Ⅱ的产量不低于产品Ⅰ的产量
x1 ≤ x2 极小化 x1-x2 + d1--d1+ =0

d 1+

3.充分利用设备有效台时,不加班 x1+2x2 = 10

极小化
x1+2x2 + d2--d2+ =10

d2-+d2+

4.利润额不小于56元
8x1+10x2 ≥ 56 极小化 8x1+10x2+d3--d3+ =56

d 3-

综上可得目标规划模型 m i n z ? P1d ? P2 (d ? d ) ? P3 d 2 x1 x1 x1 8 x1 ? ? ? ? x2 x2 2 x2 10 x 2 ? ? ? d d d
? 1 ? 2 ? 3 ? 1 ? 2 ? 2 ? 3

? ? ?

d d d

? 1 ? 2 ? 3

? ? ? ?

11 0 10 56

x1 , x 2 , d i? , d i? ? 0,

i ? 1,2,3
【毕】

建模步骤小结:

反映决策者欲望, 如“利润最大”

配上期望值 1. 建立基础模型 的理想目标 2. 为每一个理想目标确定期望值 3. 对每一个现实目标和约束都加上正负偏差 变量 4. 将目标按其重要性划分优先级,第一优先 级为硬约束 5. 建立目标规划函数

目标规划的数学模型
(一)、模型的一般形式
? ? min Z ? ? Pk (? ? kl d l? ? ? kl d l? ) k ?1 l ?1 K L

? n c kj x j ? d l? ? d l? ? ql ( l ? 1.2 ? L) ?? ? j ?1 ? n ? a x ? ( ? . ?)b ( i ? 1 .2 ? m ) i ?? ij j ? j ?1 ?x j ? 0 (j ? 1.2 ? n) ? ? ? ?d l . d l ? 0 ( l ? 1.2 ? L) ?

二、目标规划的图解法:
x2 d1d1+ d2+ o d2x1 d3+

x1-x2 + d1--d1+ =0 极小化 d 1+

硬约束2x1 + x2 ≤11

d3-

最优解为黄色线段上任一点

一般来说,目标期望值可调整以适应实际情况。

练习:

某单位领导在考虑本单位职工的升级调资方案 时,依次遵守以下规定: 1. 不超过年工资总额60000元 2. 每级的人数不超过定编规定的人数 3. 二、三级升级面尽可能达到现有人数的20% 4. 三级不足编制的人数可录用新职工,又一级 的职工中又10%要退休 试据下表数据建立模型

等级

工资额 (元/年)

现有人数

编制人数


二 三 合计

2000
1500 1000

10
12 15 37

12
15 15 42

参考模型如下:
设x1、x2、x3分别表示提升到一、二级和录用到三级的 新职工人数。各目标确定的优先因子为: P1——不超过年工资总额60000元; P2——每级的人数不超过定编制规定的人数 P3——二、三级的升级面尽可能达到现有人 数的20% 接下来确定各目标约束

年工资总额不超过60000元: 2000 ( 10-10*0.1+x1 ) + 1500 ( 12-x1+x2 ) + 1000 ( 15-x2+x3 ) + d1– -d1+=60000
每级的人数不超过定编规定的人数:

1. 10 - 10*0.1 + x1 + d2– -d2+=12 2. 12 - x1 + x2 + d3– -d3+=15 3. 15 - x2 + x3 + d4– -d4+=15
二、三级的升级面尽可能提升到现有人数的20%:

二级、 x1 + d5– -d5+=12*0.2
三级、 x2 + d6– -d6+=15*0.2

目标函数: min z = P1 d1+ + P2( d2+ + d3+ + d4+ ) + P3( d5- + d6- )

三、用Lindo求解的方法求解目标规划

主要思想:化成单目标问题,多阶段求解
? ? ? ? m i n z ? P1d 3 ? P2 ( 2d1 ? 3d 2 ) ? P3 d 4

x1 x1 5 x1 x1

? ? ?

x2 3 x2 x2

? ? ? ?

? d1 ? d2 ? d3 ? d4

? ? ? ?

? d1 ? d2 ? d3 ? d4

? ? ? ?

10 4 56 12

x1 , x 2 , d i? , d i? ? 0,

i ? 1,2,3,4

用lindo求解步骤: 1. 模型中约束不变,只取第一优先级为目标函数 ? m i n z ? d3

x1 x1 5 x1 x1

? ? ?

x2 3 x2 x2

? ? ? ?

? d1 ? d2

? ? ? ?

? d1 ? d2

? ? ? ?

10 4 56 12

d d

? 3 ? 4

d d

? 3 ? 4

x1 , x 2 , d i? , d i? ? 0,

i ? 1,2,3,4

注:在lindo中输入时,d3-可用d3minus表示, d3-可用d3plus表示。

求出最优目标值为z= d3- =0。

2. 只取第二优先级为目标函数,将上次求解结果 的目标值d3- =0变为约束 ? ? m i n z ? 2d 1 ? 3d 2

x1 x1 5 x1 x1

? ? ?

x2 3 x2 x2

? ? ? ?

? d1 ? d2 ? d3 ? d4 ? d3

? ? ? ?

? d1 ? d2 ? d3 ? d4

? ? ? ? ?

10 4 56 12 0

x1 , x 2 , d i? , d i? ? 0,

i ? 1,2,3,4

求出最优目标值为z= 2d1++3d2+=12。

3. 只取第三优先级为目标函数,将上次求解结果 的目标值2d1++3d2+=12变为约束
? m i n z ? d4

x1 x1 5 x1 x1

? ? ?

x2 3 x2 x2

? ? ? ?

? d1 ? d2 ? d3 ? d4

? ? ? ? ?

? d1 ? d2 ? d3 ? d4

? ? ? ? ? ?

10 4 56 12 0 12

d 2d
? i

? 3

? 1

3d

? 2

x1 , x 2 , d , d ? 0,

? i

i ? 1,2,3,4

求解出最优目标值z=d4+=4,此时x1=4,x2=12。
此时lindo求解结果如下:
OBJECTIVE FUNCTION VALUE 1) 4.000000 VARIABLE VALUE REDUCED COST D4PLUS 4.000000 0.000000 X1 4.000000 0.000000 X2 12.000000 0.000000 D1MINUS 0.000000 0.800000 D1PLUS 6.000000 0.000000 D2MINUS 0.000000 1.200000 D2PLUS 0.000000 0.000000 D3MINUS 0.000000 0.000000 D3PLUS 0.000000 0.600000 D4MINUS 0.000000 1.000000


更多相关文档:

建模优化部分

建模辅导-优化部分1 134页 免费 优化建模-研 44页 1财富值 数学建模竞赛中的...数学建模优秀论文 13页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能...

建模辅导

23页 免费 建模辅导材料 46页 免费 一种智能辅导系统中建模的... 4页 免费 综合建模指导与参考 7页 20财富值 建模辅导-优化部分1 134页 免费喜欢...

数学建模案例分析--最优化方法建模1引言

数学建模案例分析--最优化方法建模1引言_数学_自然科学_专业资料。数学建模数学建模 第六章 最优化方法建模 本章从生产计划、物资运输、产品试验、资源分配、任务均...

数学建模---自习室优化管理论文

数学建模 自习室灯光优化... 15页 免费 网络优化数学建模论文实... 17页 4...管理人员只需要每天晚上开一部分教室供学生上自习,每天晚上从 7: 00---10:00...

数学建模案例分析--最优化方法建模1引言

数学建模案例分析--最优化方法建模1引言_数学_自然科学_专业资料。数学建模案例分析--最优化方法建模第六章 最优化方法建模 本章从生产计划、物资运输、产品试验、...

数学建模:道路优化问题)

数学建模:道路优化问题)_数学_自然科学_专业资料。目录一、问题的提出———2 ...k Psin? r 2 ,由原题坐标图,通过实际情况假设部分数 据,列出方程,利用 ...

数学建模与最优化技术

该书主要分为五部分:数学建 模与最优化的背景、数学建摸的基本概念与分类、...的公理系统出发, 借助于数序推理的方法给出公理系统正确解释的一种数 学建模...

数学建模 铺路问题的最优化模型

铺路问题的最优化模型摘 要 本文采用了两种方法,一种是非线性规划从而得出最优...点位置分成两部分,即以 A 点正东 30km 处为界,将 沙土层分成两部分, 使...

数学建模案例分析--最优化方法建模1消防设施安置

数学建模案例分析--最优化方法建模1消防设施安置 暂无评价|0人阅读|0次下载|举报文档第七章 图与网络方法建模 瑞士数学家欧拉(E.Euler)在研究哥尼斯堡七桥问题...

【数学建模】对HIN1数学模型的优化和评估

【数学建模】对HIN1数学模型优化和评估_理学_高等教育_教育专区。数学建模论文,与传染病有关对HIN1 数学模型优化和评估 摘要:本问题是对 HIN1 数学模型的...
更多相关标签:
数学建模最优化问题 | 数学建模最优化模型 | 数学建模优化模型 | 数学建模优化问题 | 数学建模优化模型论文 | 数学建模 最优化实例 | 最优化技术与数学建模 | 建模和优化 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com