9299.net
大学生考试网 让学习变简单
当前位置:首页 >> 数学 >>

数学规划概述_图文

数学规划概述_图文

数学规划模型概述

假期你想去旅游。假如你只去一个地方而且只 有一条线路可走,反倒省心一些.如果你要去许多 地方,又有许多路线,许多交通工具,而你还想尽 量节省路费,那么你就要考虑“最优决策”或“最 优(方案)设计”的问题了.最优化(optimization) 是企业运作、科技研发和工程设计中常见的问 题.要表述一个最优化问题(即建立数学模型),应 明确三个基本要素: 决策变量(decision variables) 约束条件(constraints) 目标函数(objective function)

决策变量(decision variables):它们是决策者所控 制的那些数量,它们取什么数值需要决策者来决 策,最优化问题的求解就是找出决策变量的最优 取值. 约束条件 (constraints) :它们是决策变量在现实 世界中所受到的限制,或者说决策变量在这些限 制范围之内取值才有实际意义.

目标函数(objective function):它代表决策者希望 对其进行优化的那个指标。目标函数是决策变量 的函数.

如果一个最优化问题的决策变量不是时间的函 数,则属于静态优化(static optimization)或有 限维优化(finite dimensional optimization)的 范畴.

按照静态优化问题的结构是否线性分为线性规 划和非线性规划.线性规划的特征是目标函数 和约束条件中的函数都是决策变量的线性函数, 并且约束是必不可少的(否则不存在有实际意 义的解)

数学规划模型的一般形式
三要素:决策变量;目标函数;约束条件 目标函数 约 束 条 件

min s.t.
决策变量

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

?规划问题:求目标函数在约束条件下的最值 ?可行解(只满足约束)与最优解(取到最优值)

数学规划模型的 简单分类
数学规划 连 续 优 化 离 散 优 化

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(整数)规划

MATLAB优化工具箱能求解的优化模型
优化工具箱3.0 (MATLAB 7.0 R14) 连续优化 无约束优化 非线性 极小 fminunc 非光滑(不可 微)优化 fminsearch 全局 优化 离散优化 纯0-1规划 bintprog 一般IP(暂缺)

约束优化
线性规划 linprog 二次规划 quadprog

非线性 非线性 方程 ( 组 ) 最小二乘 fzero fsolve lsqnonlin lsqcurvefit

暂缺

非线性规划 fmincon fminimax fgoalattain fseminf

约束线性 最小二乘 lsqnonneg lsqlin

上下界约束 fminbnd fmincon lsqnonlin lsqcurvefit

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

连续优化

整数规划

线性规划

二次规划
LINDO

非线性规划

LINGO

LINGO软件的求解过程
1. 确定常数
2. 识别类型

LINGO预处理程序
LP QP NLP IP 全局优化(选) 分枝定界管理程序

ILP
线性优化求解程序 1. 单纯形算法 2. 内点算法(选)

IQP

INLP

非线性优化求解程序 1、顺序线性规划法(SLP) 2、广义既约梯度法(GRG) (选) 3、多点搜索(Multistart) (选)

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

LINDO 公司软件产品简要介绍
美国芝加哥(Chicago)大学的Linus Schrage教授于1980 年前后开发, 后来成立 LINDO系统公司(LINDO Systems Inc.), 网址:http://www.lindo.com
LINDO: Linear INteractive and Discrete Optimizer (V6.1)

LINDO API: LINDO Application Programming Interface (V4.1)
LINGO: Linear INteractive General Optimizer What’s Best!: (SpreadSheet e.g. EXCEL) (V10.0) (V8.0)

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

线性规划模型
? 历史悠久,理论成熟,应用广泛 ? 运筹学的最基本的方法之一,网络规划、整 数规划、目标规划和多目标规划都是以线性规 划为基础的。 ? 解决稀缺资源最优分配的有效方法,使付出

的费用最小或获得的收益最大。

? 线性规划理论的发展
1939年前苏联康托洛维奇(KOHTOPOBUZ) 《生产组织与计划中的 数学方法》提出 “解乘数法”。

列奥尼德· 康托罗维奇,前苏联人,由于在1939年创立 了享誉全球的线性规划要点,对资源最优分配理论做 出了贡献,而获得诺贝尔经济学奖。

美国科学院院士DANTZIG(丹齐克),1948年在 研究美国空军资源的优化配置时提出线性规划及其通用 解法 “单纯形法”。被称为线性规划之父。
线性规划之父的Dantzig (丹齐克)。据说,一次上课,Dantzig迟到 了,仰头看去,黑板上留了几个题目,他就抄了一下,回家后埋头苦做。 几个星期之后,疲惫的去找老师说,这件事情真的对不起,作业好像太 难了,我所以现在才交,言下很是惭愧。几天之后,他的老师就把他召 了过去,兴奋的告诉他说他太兴奋了。Dantzig 很不解 , 后来才知道原 来黑板上的题目根本就不是什么家庭作业,而是老师说的本领域的未解 决的问题,他给出的那个解法也就是单纯形法。这个方法是上个世纪前 十位的算法。

1960年,“最佳资源利用的经济计算” 康托洛维奇 和库伯曼斯(Koopmans) 。两人因对资源最优分配理论的 贡献而获1975年诺贝尔经济学奖

佳林· 库普曼斯,美国人,他将数理统计学成功运用 于经济计量学,对资源最优分配理论做出了贡献。

保罗-萨缪尔逊(PAUL A SAMUELSON ), 他发展了数理和 1961年,查恩斯与库伯提出了目标规划,艾吉利 动态经济理论,将经济科学提高到新的水平。他的研究涉及 提出了用优先因子来处理多目标问题。 经济学的全部领域。于1970年获得诺贝尔经济学奖。
华西里· 列昂惕夫(WASSILY LEONTIEF) ,美国人,他发 20世纪70年代,斯.姆.李与杰斯开莱尼应用计 展了投入产出方法,该方法在许多重要的经济问题中得到运 算机处理目标规划问题 用。曾获 1973年诺贝尔经济科学奖。 肯尼斯 -J阿罗( KENNETH J. ARROW),美国人,因与约翰 从 1964 年诺贝尔奖设经济学奖后,到 1992 年 28年 希克斯(JOHN R. HICKS)共同深入研究了经济均衡理论和 间的32名获奖者中有13人(40%)从事过与线性规划有关 福利理论获得1972年诺贝尔经济学奖。 的 研 究 工 作 , 其 中 著 名 的 有 Simon , Samullson , Leontief ,Arrow ,Miller 牟顿 -米勒( MERTON M. 等。 MILLER),1923-2000, 美国人,由于 他在金融经济学方面做出了开创性工作,于1990年获得诺贝 尔经济奖。

例1 农作物种植
一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水 稻. 种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为 110元, 75元, 60元. 如何规划经营使 经济效益最大. ?种植蔬菜 x1 亩, 棉花 x2 亩, 水稻 x3 亩(决策变量)

?以取得最高的产值的方式达到收益最大的目标.
求f=110x1+75x2+60x3的最大值(目标函数、优劣标准) ?约束条件 x1+x2+x3 ? 50 1/2x1+1/3x2+1/4x3 ?20
目标函数和约束条件是线性的,是线性规划

max : Z =110x1+75x2+60x3 s.t. x1+x2+x3 ? 50 1/2x1+1/3x2+1/4x3 ?20 x1,x2,x3 ≥0

关于线性的界定
? 如果规划问题的数学模型中,决策变量的取值可以
是连续的,目标函数是决策变量的线性函数,约束条件
是含决策变量的线性等式或不等式,则该类规划问题的 数学模型称为线性规划的数学模型。

? 实际问题中线性的含义:
一是严格的比例性

二是可叠加性

? 比例性:决策变量变化引起目标的改变量与决 策变量改变量成正比;

? 可加性:每个决策变量对目标和约束的影响独 立于其它变量;
? 连续性:每个决策变量取连续值; ? 确定性:线性规划中的参数aij , bi , ci为确定值。

线性规划的数学模型及其标准化

正则模型 决策变量: x1,x2,…,xn. 目标函数: Z=c1x1+c2x2+…+cnxn. 求目标函数的最小或最大 约束条件: a11x1+…+a1nxn≤b1, … … am1x1+…+amnxn≤bm

标准化模型 决策变量 x1, x2,…, xn, max Z = c1x1+…+ cnxn, s. t. a11x1+…+ a1nxn= b1, …… am1x1+…+ amnxn= bm, x1 ≥ 0,…, xn ≥ 0,

模型的标准化
10. 引入松弛变量将不等式约束变为等式约束 若有 ai1x1+?+ainxn≤bi, 则引入xn+i≥ 0, 使得 ai1x1+?+ainxn+ xn+i =bi 若有 aj1x1+?+ajnxn≥bj, 则引入xn+j≥ 0, 使得 aj1x1+?+ajnxn- xn+j =bj. 且此时目标函数 Z=c1x1+c2x2+?+cnxn+0xn+1+?+0xn+m. 20. 将目标函数的优化变为目标函数的极大化. 若求 min Z, 令 Z’=–Z, 则问题变为 max Z’. 30. 引入人工变量,使得所有变量均为非负. 若xi没有非负的条件,则引入 xi’≥ 0和xi’’≥0, 令xi= xi’– xi’’,则可使得问题的全部变量均非负.

?线性规划的对偶性和影子价格
农作物种植(续):一个农场有50亩土地,20个劳动力,

计划 种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳 动力1/2 1/3 1/4,预计每亩产值分别为 110 元 ,75 元 ,60元 . 如果出租土地和劳动力如何规划经营使经济效益最大. 决策变量: 对单位土地和单位劳力出租价格分别为 y1 y2 目标函数: g=50y1+20y2

约束条件: y1+1/2y2 ? 110 y1+1/3y2 ? 75 y1+1/4y2 ? 60 (成本 不小于产值)(我出租出去要比自己种植合适。出租底线)
优劣准则: 应求g的最小值. (因为要达到的要求已经通过 约束条件满足,决策者关心的是在最低要求达到时出租价 格的心理底线是多少?)

对偶线性规划
max : Z =110x1+75x2+60x3 s.t. x1+x2+x3 ? 50 min:g=50y1+20y2 s.t. y1+1/2y2 ? 110 y1+1/3y2 ? 75 y1+1/4y2 ? 60
y1,y2 ≥0

1/2x1+1/3x2+1/4x3 ?20
x1,x2,x3 ≥0

A 是m ? n 矩阵, c 是 n ? 1向量,b 是 m ? 1向量 x 是 n ? 1向量, y 是 m ? 1向量
原问题 max f=cTx s.t. Ax ? b xi ? 0,i=1,2,?,n.

对偶问题 min f=bTy s.t. ATy ? c yi ? 0, i=1,2,?,m.

对偶定理: 互为对偶的两个线性规划问题
若其中一个有有穷的最优解,则另一个也有有穷的最优解,且 最优值相等. 若两者之一有无界的最优解,则另一个没有可行解。

模型I 给出了生产中的资源最优分配方案。 模型II 给出了生产中资源的最低估价. 这种价格涉及到资 源的有效利用,它不是市场价格,而是根据资源在生产中 做出的贡献确定的估价,被称为“影子价格”。

线性规划的灵敏度分析
灵敏度分析主要包括下面几个内容: 1:当约束条件的右边常数项变化的影响; 2:约束条件的系数变化的影响; 3:目标函数的系数变化的影响。 可能的影响结果: 1:最优解保持不变; 2:基变量保持不变,但值变了; 3:基本解变化。

附录1:用Lindo(Lingo)解线性规划
例:简单的线性规划(LP)问题

Max s .t .

z ? 2x ? 3 y 4 x ? 3 y ? 10 3 x ? 5 y ? 12 x, y ? 0

在空白的模型窗口中输入这个LP模型: max 2x+3y st 4x+3y<=10 3x+5y<12 end

如图:

模型求解
用鼠标点击工具栏中的图标 , 或从菜单中选择Solve|Solve(Ctrl+S)命令 LINDO首先开始编译这个 模型,编译没有错误则开 始求解;

求解时会首先显示如右图 所示的LINDO “求解器运行状态窗口 ”。

求解器运行状态窗口显示的相应信息及含义
名称
Status (当前状态) Iterations (迭代次数) Infeasibility (不可行性) Objective (当前的目标值) Best IP (整数规划当前的最佳目 标值)

含义
显示当前求解状态:“Optimal”表示已经达到最优解; 其他可能的显示还有三个:Feasible(可行解), Infeasible(不可行), Unbounded(最优值无界)。 显示迭代次数:“2”表示经过了2次迭代。 约束不满足的量(即各个约束条件不满足的“数量” 的和;特别注意不是“不满足的约束个数”):“0” 表示这个解是可行的。 显示目标函数当前的值:7.45455。 显示整数规划当前的最佳目标值:“N/A” (No Answer或Not Applicable)表示无答案或无意义,因 为这个模型中没有整数变量,不是整数规划(IP)。

名称 IP Bound (整数规划的界) Branches (分枝数) Elapsed Time (所用时间)

含义 显示整数规划的界(对最大化问题显示上界;对最小化 问题,显示下界):“N/A”含义同上。 显示分枝定界算法已经计算的分枝数: “N/A”含义同 上。 显示计算所用时间(秒):“0.00”说明计算太快了, 用时还不到0.005秒。

Update Interval 显示和控制刷新本界面的时间间隔:“1”表示1秒;用 (刷新本界面的时间间隔) 户可以直接在界面上修改这个时间间隔。
Interrupt Solver (中断求解程序) 当模型规模比较大时(尤其对整数规划),可能求解时 间会很长,如果不想再等待下去时,可以在程序运行过 程中用鼠标点击该按钮终止计算。求解结束后这个按钮 变成了灰色,再点击就不起作用了。 该按钮只是关闭状态窗口,并不终止计算。如果你关闭 了状态窗口,将来随时可以选择WINDOW | OPEN STATUS WINDOW 菜单命令来再次打开这个窗口。

Close(关闭)

紧接着弹出一对话框,询问你是否需要做灵敏性分析 ( DO RANGE (SENSITIVITY) ANALYSIS? ) 先 选 择 “否( N)”按钮,这个窗口就会关闭。然后,再把状态 窗口也关闭。

报告窗口
用鼠标选择“Window | Reports Window”(报告窗口), 就可以查看该窗口的内容

保存文件
选择File|Save(F5)命令把“结果报告”保存在一个文件中 (缺省的后缀名为LTX,即LINDO文本文件) 类似地,回到模型窗口,可以把输入的模型保存在一个文件 中。保存的文件将来可以用File | Open(F3)和File | View (F4)重新打开,用前者打开的程序可以进行修改,而后者 只能浏览。 如果模型有错误,运行时会弹出出错信息报告窗口(LINDO Error Message),则需要修改模型。

例:某家具公司制造书桌、餐桌和椅子,所用的资源有 三种:木料、木工和漆工。生产数据如下表所示。
每个书桌 每个餐桌 每个椅子 现有资源总数

木料 漆工
木工 成品单价

8单位 4单位
2单位 60单位

6单位 2单位
1.5单位 30单位

1单位 1.5单位
0.5单位 20单位

48单位 20单位
8单位

若要求桌子的生产量不超过 5 件,如何安排三种产品 的生产可使利润最大?

解:

用DESKS、TABLES和CHAIRS分别表示三种产品的 生产量(决策变量),容易建立LP模型。

在LINDO模型窗口中输入模型: MAX 60 DESKS + 30 TABLES + 20 CHAIRS SUBJECT TO 2) 8 DESKS + 6 TABLES + CHAIRS <= 48 3) 4 DESKS + 2 TABLES + 1.5 CHAIRS <= 20 4) DESKS + 1 5 TABLES + O 5 CHAIRS <= 8 5) TABLES <= 5 END 解这个模型,并对弹出的对话框 “ DO RANGE (SENSITIVITY) ANALYSIS? ” 选择“是(Y)”按钮,这表示你需要做灵敏性分析。然后, 查看输出结果。

输出结果的前半部分: LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 280.0000 VARIABLE VALUE REDUCED COST DESKS 2.000000 0.000000 TABLES 0.000000 5.000000 CHAIRS 8.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 24.000000 0.000000 3) 0.000000 10.000000 4) 0.000000 10.000000 5) 5.000000 0.000000 NO. ITERATIONS= 1

前半部分的输出结果的解释: “LP OPTIMUM FOUND AT STEP2”
表示两次迭代(旋转变换)后得到最优解。

“OBJECTIVE FUNCTION VALUE 1)280.000000”
表示最优目标值为280。

“VALUE”
给出最优解中各变量的值:造2个书桌(desks), 0个餐桌(tables), 8个椅子(chairs)。所以desks、chairs是基变量(取值非0), tables是非基变量(取值为0)。

“SLACK OR SURPLUS”
给出松驰变量的值。(在最优的情况下资源的剩余量) 第2行松驰变量 =24 (第1行表示目标函数,第2行对应第1个约束) 第3行松驰变量 =0 第4行松驰变量 =0 第5行松驰变量 =5

本例中:变量 TABLES 对应的 reduced cost 值 “REDUCED COST” 列出最优单纯形表中判别数所在行的变量的系数,表示当变 为 5。 量有微小变动时 , 目标函数的变化率 . 其中 的值从 0变为1 1)表示当非基变量 TABLES 基变量的reduced cost值应为0; 时(此时假定其它非基变量保持不变 ,但为了 非基变量 Xj,相应的 reduced cost值 满足约束条件,基变量显然会发生变化), 此时的最优的目标函数值为 280 - 5=275。 1 )表示当非基变量Xj 增加一个单位时,目标函数相应减少的
量( max型问题)。

2)理解为目前table的单价30元偏低,不 2)理解为:为了使该非基变量变成基变量,目标函数中该变 量前对应系数应增加的量。 值得生产,如果生产的话至少35元。

“DUAL PRICE” (对偶价格)表示当对应约束有微小变动时 , 目标函数的变化率. 输出结果中对应于每一个约束有一个对偶价 格. 若其数值为p, 表示对应约束中不等式右端项若增加1个单位, 目标函数将增加 p个单位( max型问题 ) 。也就是相应的一个单 位的该资源在生产过程中产生的效益,即其价值。 1)如果在最优解处约束正好取等号(也就是“紧约束”现有相 应资源全部使用),该资源的对偶价格才可能不是0。例如本例 中:第3行是紧约束,对应的是资源是漆工,其对偶价格值为10, 表示当紧约束 4 DESKS + 2 TABLES + 1.5 CHAIRS <= 20变 为 4 DESKS + 2 TABLES + 1.5 CHAIRS <= 21时,目标函数 值是280 +10 = 290。即若再增加一名漆工的话,可增加10的利 润。 2 )对于非紧约束(如本例中第 2 行木料是非紧约束), DUAL PRICE 的值为0, 表示对应约束中不等式右端项的微小扰动不影 响目标函数。因为最优的时候还有剩余。

输出结果的后半部分:
RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE DESKS 60.000000 20.000000 4.000000 TABLES 30.000000 5.000000 INFINITY CHAIRS 20.000000 2.500000 5.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 48.000000 INFINITY 24.000000 3 20.000000 4.000000 4.000000 4 8.000000 2.000000 1.333333 5 5.000000 INFINITY 5.000000 (报告中INFINITY表示正无穷 )

这个部分包括两方面的敏感性分析内容: 1. 目标函数中系数变化的范围( OBJ COEFFICIE NT RANGES) 如 本例 中 : 目 标 函 数 中 DESKS 变 量 当 前 的 系 数 (CURRENT COEF)=60 , 允 许 增 加 (Allowable Increase)=4、允许减少(Allowable Decrease)= 2, 说明当这个系数在 [60-4,60+20]=[56,80]范围变 化时,最优基保持不变。对 TABLES 、 CHAIRS 变 量,可以类似解释。由于此时约束没有变化(只是 目标函数中某个系数发生变化),所以最优基保持 不变的意思也就是最优解不变(当然,由于目标函 数中系数发生了变化,所以最优值会变化)。

?

2. 约 束 右 端 项 变 化 的 范 围 ( Right Hand Side RANGES)

如 本 例 中 : 第 2 行 约 束 中 当 前 右 端 项 (CURRENT RHS ) =48 , 允 许 增 加 ( Allowable Increase ) =INFINITY ( 无 穷 ) 、 允 许 减 少 ( Allowable Decrease)=24,说明当它在

?) [48-24,48+ ? ) = [24,
范围变化时,最优基保持不变。第3、4、5行可以类 似解释。不过由于此时约束发生变化,最优基即使不 变,最优解、最优值也会发生变化。

LINDO模型的一些注意事项
1. 变量名由字母和数字组成,但必须以字母开头,且 长度不能超过8个字符,不区分大小写字母,包括关键 字(如MAX、MIN等)也不区分大小写字母。 2. 对目标函数和约束用行号(行名)进行标识,这些标 识会在将来的求解结果报告中用到。 行名可以和变量名一样命名,也可以只用数字命名,还可 以含有中文字符,但长度同样不能超过8个字符。

为了方便将来阅读求解结果报告,建议用户总是自觉地对 每个约束进行命名。
行名结束标志符号、即右括号“)”必须是英文字符,否 则会出现错误。

3. 可以用“TITLE”语句对输入的模型命名,用法是在TITLE 后面写出其名字(最多72个字符,可以有汉字),在程序中单 独占一行,可以在模型的任何地方。

模型命名的第一个作用类似于对模型的注释和说明。
模型命名的另一个目的,是为了方便将来阅读求解结果报告。 因为用户有可能同时处理多个模型,很容易混淆模型与求解结 果的对应关系。这时如果对不同模型分别进行了命名,就可以 随时(例如在求解当前模型前)使用菜单命令“FILE|TITLE” 将当前模型的名字显示在求解结果报告窗口中,这样就容易判 别每个求解结果与每个模型的对应关系。

4. 模型中以感叹号“!” 开头的是注释行(注释语句,或称 为说明语句),可以帮助他人或以后自己理解这个模型。实 际上,每行中“!”符号后面的都是注释或说明。注释语句中 可以使用汉字字符 。

5. 变量不能出现在一个约束条件的右端(即约束条件的右端 只能是常数);变量与其系数间可以有空格(甚至回车),但 不能有任何运算符号(包括乘号“*”等)。 6. 模型中不接受括号“( )”和逗号“,”等符号(除非在注释 语句中)。 例如: 4(X1+X2)需写为4X1+4X2;“10,000”需写为10000。 7. 表达式应当已经经过化简。

如不能出现2X1 + 3X2 - 4X1,而应写成 -2X1 + 3X2等。 8. LINDO 中已假定所有变量非负。若要取消变量的非负假 定,可在模型的“END”语句后面用命令“FREE”。例如, 在“END”语句后输入FREE vname,可将变量vname的非 负假定取消。

9. 可以在模型的“END”语句后面用命令“SUB”(即设置上 界(SET UPPER BOUND)的英文缩写)设定变量的上界, 用命令“SLB” (即设置下界(SET LOWER BOUND)的英 文缩写)设定变量的上下界。其用法是:“SUB vname value”将变量vname的上限设定为value;“SLB”的用法类 似。 用“SUB”和“SLB”表示的上下界约束不计入模型的约束,因 此LINDO也不能给出其松紧判断和敏感性分析。 10. 数值均衡化考虑:如果约束系数矩阵中各非零元的绝对 值的数量级差别很大(相差1000倍以上),则称其为数值不 均衡的。为了避免数值不均衡引起的计算问题, 使用者应尽可 能自己对矩阵的行列进行均衡化。此时还有一个原则, 即系数 中非零元的绝对值不能大于100000 或者小于.0001。LINDO 不能对LP 中的系数自动进行数值均衡化,但如果LINDO 觉得 矩阵元素之间很不均衡, 将会给出警告。

11. 简单错误的检查和避免: 输入模型时可能会有某些输入错误. 当问题规模较大时, 要 查找错误是比较困难的。在LINDO 中有一些可帮助寻找错误的 功能,其中之一就是菜单命令“Report | Picture(Alt+5)” , 它的功能是可以将目标函数和约束表达式中的非零系数通过列 表(或图形)显示出来。

附录2:用MATLAB优化工具箱解线性规划
1. 模型: min z=cX
s.t. AX ? b

命令:x=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.

问题一 :任务分配问题:某车间有甲、乙两台机床, 可用于加工三种工件 . 假定这两台车床的可用台时数 分别为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的数量分别为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

改写为:

min z ? ?13 9 10 11 12 8?X
0 0? ? 0.4 1.1 1 0 ? 800 ? ? ? ? X ?? ? 0 ? ? ? 0 0 0 . 5 1 . 2 1 . 3 900 ? ? ? ?
? 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]; beq=[400 600 500]; vlb = zeros(6,1); vub=[]; [x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub) (linprog只适用于求解最小值问题)

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

问题二:某厂每日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

改写为:

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

编写M文件xxgh4.m如下: c = [40;36]; A=[-5 -3]; b=[-45]; Aeq=[]; beq=[]; 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 ,故它 就是该整数规划的最优解 . 若用线性规划解法求得的最 优解不是整数,将其取整后不一定是相应整数规划的 最优解,这样的整数规划应用专门的方法求解.

整数规划、 0-1 整数规划、 0规划 -1规划模型 ? 如果要求决策变量取整数,或部分取整数 的数学规划问题,称为整数规划. ? 如果要求决策变量只取0 或 1的线性规划 问题, 称为0-1规划. ? 0-1 约束不一定是由变量的性质决定的, 更多地是由于逻辑关系引进问题的.

整数规划问题 一般形式

min n
x?Z

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

s.t.

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

整数规划问题对应的松弛问题
取消整数规划中决策变量为整数的限制(松弛),对 应的连续优化问题称为原问题的松弛问题 整数规划问题 最优解

松弛
松弛问题 最 优 解 整数 非整数 舍入

非最优解

整数

下界(对Min问题) 上界(对Max问题)

用连续优化方法求解松弛问题,如果松弛问题最优解 (分量)全为整数,则也是原整数规划问题的最优解 (见例1) 对松弛问题的最优解(分量)舍入为整数,得到的往 往不是原整数规划问题的最优解(甚至不是可行解)



max z ? 5 x1 ? 8 x2 s.t. x1 ? x2 ? 6 5 x1 ? 9 x2 ? 45 x1 , x2 ? 0 且为整数

6 5

x2
. . . . . .

oP
. .



. . . .

. . . .

. .

6 Zmax x1 去掉整数限制后,可行域为点(0,0), (6,0), (0,5), P (2.25,3.75) 围成的4边形
LP 最优解 P (2.25,3.75) z=41.25 P 的舍入解 (2,4) 不可行 最靠近 P 的可行解 (2,3) z=34 IP 最优解 (0,5) z=40

0

9

从LP最优解经过简单的 “移动”不一定能得到IP最优 解

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

纯整数规划 - 聘用方案
某服 务 部门 一 周中 每 天 需 要 不 同 数 目的 雇 员:周一到周四每天至少 50 人,周五和周日 每天至少 80 人,周六至少 90 人。 现规定应聘者需连续工作 5 天,试确定聘用 方案,即周一到周日每天聘用多少人,使在 满足需要的条件下聘用总人数最少。

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

设系统已进入稳态(不是开始的几周) 连续工作5天 周一工作的应是(上)周四至周一聘用的 x4 ? x5 ? x6 ? x7 ? x1 ? 50
min s.t. z ? x1 ? x2 ? x3 ? x4 ? x5 ? x6 ? x7 x1 ? x4 ? x5 ? x6 ? x7 ? 50

聘用方案

x1 ? x2 ? x5 ? x6 ? x7 ? 50 xi ? Z ?, x1 ? x2 ? x3 ? x6 ? x7 ? 50 即为非负整数 x1 ? x2 ? x3 ? x4 ? x7 ? 50 x1 ? x2 ? x3 ? x4 ? x5 ? 80 x2 ? x3 ? x4 ? x5 ? x6 ? 90 x3 ? x4 ? x5 ? x6 ? x7 ? 80

整数规划
模型(IP)

首先在LINDO模型窗口输入模型 : MIN X1 + X2 + X3 + X4 + X5 + X6 + X7 SUBJECT TO MON) X1 + X4 + X5 + X6 + X7 >= 50 TUE) X1 + X2 + X5 + X6 + X7 >= 50 WED) X1 + X2 + X3 + X6 + X7 >= 50 THU) X1+ X2 + X3 + X4 +X7 >= 50 FRI) X1 + X2 + X3 + X4 - X5 >= 80 SAT) X2 + X3 + X4 - X5 + X6 >= 90 SUN) X3 + X4 - X5 + X6 + X7 >= 90 END GIN 7
其中“GIN 7”表示7个变量都是一般整数变量。 (仍然默认为取值是非负的)

求解后状态窗口中与整数相关的三个域有了相关结果: “Best IP :94”表示当前 得到的最好的整数解的目 标函数值为94(人)。 “IP Bound :93.5” 表示 该整数规划目标值的下界 为93.5 (人)。 “Branches :1”表示分 枝数为1(即在第1个分枝 中就找到了最优解)。
我们前面说过,LINDO求解IP 用的是分枝定界法。 显然,上面第二条“整数规划目标值的下界为93.5 (人)”表明至少要 聘用93.5名员工,由于员工人数只能是整数,所以至少要聘用94(人)。 而第一条说明目前得到的解就是聘用94(人),所以已经是最优的了。

求解结果的报告窗口如下:
LP OPTIMUM FOUND AT STEP 8 OBJECTIVE VALUE = 93.3333359 SET X2 TO >= 4 AT 1, BND= -94.00
NEW INTEGER SOLUTION OF 94.0000000

TWIN= -93.50
1 PIVOT

18
18

AT BRANCH

BOUND ON OPTIMUM: 93.50000 DELETE X2 AT LEVEL 1 ENUMERATION COMPLETE. BRANCHES= 1 PIVOTS= LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION...

18

(接下页)

OBJECTIVE FUNCTION VALUE 1) 94.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 4.000000 1.000000 X3 40.000000 1.000000 X4 2.000000 1.000000 X5 34.000000 1.000000 X6 10.000000 1.000000 X7 4.000000 1.000000 ROW SLACK OR SURPLUS DUAL PRICES MON) 0.000000 0.000000 TUE) 2.000000 0.000000 WED) 8.000000 0.000000 THU) 0.000000 0.000000 FRI) 0.000000 0.000000 SAT) 0.000000 0.000000 SUN) 0.000000 0.000000 NO. ITERATIONS= 18 BRANCHES= 1 DETERM.= 1.000E 0

报告窗口中前两行告诉我们:在8次迭代后找到对应的线 性规划(LP)问题的最优解,最优值=93.3333359。
LINDO求解IP用的是分枝定界法,紧接着几行显示的是分 枝定界的信息,在第1个分枝中设定x2>=4,并在该分枝中 找到了整数解,而且就是全局整数最优解,所以算法停止。 旋转迭代(PIVOT)共18次。 后面显示的是最后的最优解:x=(0,4,40,2,34,10,4). 松弛和剩余变量(SLACK OR SURPLUS)仍然可以表示 约束的松紧程度,但目前IP尚无相应完善的敏感性分析理 论,因此REDUCED COST和DUAL PRICES的结果在整数 规划中意义不大。

聘用方案(续)
邮局一周中每天需要不同数目的雇员,设周 一至少需要 a1人,周二至少需要 a2人,周三至少需 要 a3 人,等等。又规定应聘者需连续工作 5 天,问 邮局每天聘多少雇员才能既满足需求,又使聘用总 人数最少。

进一步考虑,上述指全时雇员(每天工作8小 时)。如果邮局也可聘用半天雇员(每天工作4小 时,连续工作5天),设全时和半时雇员的工资每 小时为3元和2元,并且限制半时雇员的工作量不应 超过总工作量的四分之一,问邮局如何安排聘用方 案,使所付工资总额最少?

? 分析
? 此时决策变量由两部分构成: 全时雇员x1,x2, x3,x4,x5,x6,x7;

半时雇员y1,y2, y3,y4,y5,y6,y7.
? 目标值应该是雇员的总工资,标准是最少: min : Z=3×8×5×∑xi+2×4×5×∑yi

? 约束条件:
每天的工作量应该折合为小时工作量(以周一的工作量为例) 8×(x4+x5+x6+x7+x1)+4 ×(y4+y5+y6+y7+y1) >=8a1

半时雇员的限制
4×5×∑yi=<0.25×8(∑ai)

0-1规划 -背包问题
一个旅行者的背包最多只能装 6 kg 物品. 现有4 件物品 重量为 2 kg , 3 kg, 3 kg, 4 kg, 价值为 1 元, 1.2元, 0.9元, 1.1元. 应携带那些物品使得携带物品的价值最大?
决策变量: xj 旅行者是否携带第 j 件物品, xj = {0, 1}. 约束条件 2x1+3x 2+3x 3+4x 4 ? 6 目标函数 f=x1+1.2x2+0.9x3+1.1x4 优劣标准: 最大.

用Lingo 软件求解0-1规划 Linear Interactive and General Optimizer Model: Max=x1+1.2*x2+0.9*x3+1.1*x4; 2*x1+3*x2+3*x3+4*x4<=6; @bin(x1); @bin(x2); @bin(x3); @bin(x4); end

混合0-1规划 -生产工艺问题
工厂可用k种不同的工艺生产n种产品,每种 产品的利润已知。在各种工艺条件下每种产品所 消耗的资源是确定的,并且,工厂的总资源有一 定限制。问应选择哪种工艺,每种产品各生产多 少,使总利润最大

分析

? 有 关 参 量 : 用 A1,A2,· · · ,Ak 表 示 k 种 工 艺 ; 用 B1,B2,· · · ,Bn 表示 n 种产品;单件 Bi 的利润 pi ;在 工艺Aj下,资源限制Qj,单件Bi的资源消耗cij。 ?决策变量:一是Bi的产量xi;一是工艺的选择。 ?目标函数: max: Z=p1*x1+p2*x2+· · ·· · ·+pn*xn ?资源限制约束: ∑cij*xi=<Qj j=1,2,· · ·· · · ,k

?工艺选择: 引入0-1变量 yj=0 选择第j个工艺; yj=1 否则 ?约束条件: ∑yj=k-1, yj=0,1, xi>=0 为保证yj=1的工艺不被选择,资源限制条件改 为 ∑cij*xi=<Qj +yjM j=1,2, ,k

其中M充分大的一个正数。
(当yj=1时,此约束条件对任何决策变量xi都成 立,所以在k个资源限制约束中只有yj=0的有效。)

二次规划模型-产销计划问题
某厂生产两个牌号的同一种产品,如何确定产量使利润最大

假设A 假设B

产销平衡

牌号 甲 乙

产量 x1 x2

成本 价格 q1 p1 q2 p2

p随x (两种牌号)增加而减小,呈线性关系

p1 ? b1 ? a11 x1 ? a12 x2 , b1 , a11 , a12 ? 0, a11 ? a12
p2 ? b2 ? a21 x1 ? a22 x2 , b2 , a21 , a22 ? 0, a22 ? a21

目标
x1 , x2

利润最大

max z( x1, x2 ) ? ( p1 ? q1) x1 ? ( p2 ? q2 ) x2
= (100-x1-0.1 x2-2)x1 +(280-0.2x1-2x2-3)x2 =98 x1 + 277 x2 - x12 - 0.3 x1 x2 - 2x22

约束
x1 + x2 ≤100 x1 ≤ 2 x2 x1 , x2 ≥ 0

二次规划模型(QP)

若还要求产量为整数,则是整数二次规划模型(IQP)

非线性规划模型-选址问题
某公司有6个建筑工地,位置坐标为(ai, bi) (单位:公里), 水泥日用量di (单位:吨)
i a b d 1 1.25 1.25 3 2 8.75 0.75 5 3 0.5 4.75 4 4 5.75 5 7 5 3 6.5 6 6 7.25 7.75 11

假设:料场 和工地之间 有直线道路

1)现有 2 料场,位于 A (5, 1), B (2, 7), 记(xj,yj),j=1,2, 日储量 ej 各有 20 吨。

目标:制定每天的供应计划,即从 A,

B 两料场分别 向各工地运送多少吨水泥,使总的吨公里数最小。

决策变量:ci j (料场j到工地i的 运量)~12维 线性规划模型(LP) 用例中数 据计算, 最优解为

min

??
j ?1 i ?1 2

2

6

cij [( x j ? ai ) 2 ? ( y j ? bi ) 2 ]1 / 2

s.t.

?c
j ?1 6 i ?1

ij ? d i ,

i ? 1,...,6

?c

ij ? e j ,

j ? 1,2

i ci1 (料场 A) c i 2 (料场 B)

1 3 0

2 5 0

3 0 4

4 7 0

5 0 6

6 1 10

总吨公里数为136.2

2)改建两个新料场,需要确定新料场位置(xj,yj)和 运量cij ,在其它条件不变下使总吨公里数最小。
min

??
j ?1 i ?1 2

2

6

cij [( x j ? ai ) 2 ? ( y j ? bi ) 2 ]1 / 2

决策变量: ci j,(xj,yj)~16维 非线性规划模型 (NLP)

s.t.

?c
j ?1 6 i ?1

ij ? d i ,

i ? 1,...,6

?c

ij ? e j ,

j ? 1,2

习题1:投资问题 现有一笔资金S,今后5年内有以下项目的投资可供选择: 项目 A:若每年初投资 1 元,则两年后收回本利共 (1+a) 元; 项目B:只能在第2年初投资,第5年末收回本利共(1+b)元, 但投资额不能小于R; 项目C:只能在第3年初投资,第5年末收回本利共(1+c)元, 但投资额不能大于Q; 项目D:每年初可购1年期债卷,利率d.

问如何确定每年初这些项目的投资,使得5年末本利总额 最大。

习题2:装货问题
要把7种规格的包装箱装到两辆铁路平板车上去,箱子的 宽、高相同,而厚度和重量不同。

每辆平板车有 10.2 米长的地方用于装箱(象面包片一 样),载重40吨。由于货运限制,对5、6、7三种包装箱 的装载有如下约束:它们所占的空间(厚度)不得超过 302.7厘米。试把包装箱装到平板车上,使浪费的空间最 小。 1 2 3 4 5 6 7 厚度t(cm) 48.7
重量w(kg) 2000 数量n 8

52.0

61.3

72.0 48.7
500 6 4000 4

52.0 64.0
2000 4 1000 8

3000 1000 7 9

习题3

存储问题

有5种药品 S={1,2,3,4,5} 要存放, 有些 药品不能存放在一起, 能存放在一起存放 的药品为的 {{1,2},{1,3,5},{2,4,5},{3},{1},{4,5}}

不同的组合所需的存放费用费用不同其中 第 i 种组合的存储费用为 cj , 求这五种 药品费用最低 的储存方案。

习题4 资源的最优配置策略 某工厂有1000台机器, 生产两种产品 A, B, 若投入 y 台机器生产A 产品, 则纯收入为 5y .若投入 y 台机器生产B 产品, 则纯收入 为 4y . 又知, 生产A 种产品机器的年折损 率为20%, 生产B 种产品机器的年折损率 为10%, 问在5年内如何安排各年度的生产 计划, 才能使总收入最高.

习题5 一家出版社准备再某市开设两个销售点,向七个 区的大学生售书。每个区的大学生数量(千人)如图。 每个销售点只能向本区和一个相邻区的大学生售书。 这两个销售点应该设在何处,才能使所供应的学生数 量最大。

29 34 42 21

56 18 71

THE END
Thank you very much!


网站首页 | 网站地图
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com