Mathematica基础数学实验.ppt

1、实验十一 数学规划模型的计算,一、实验目的 掌握用mathematica软件包求解数学规划(线性规划和非线性规划)模型的计算问题.,二、学习mathematica命令 1. 求解线性规划的命令: (1) LinearProgrammingc,A,b;,min cx st Axb x0,c为n维行向量(目标向量), A为mn矩阵(约束矩阵), b为m维列向量(约束向量), x为n维列向量(决策向量).,其中,求解模型:,(2) mathematica5.0版本的命令 LinearProgrammingc,A,b,L;,其中, b和L为表, b=b1,s1,b2,s2, 当si=0, 1时, 表示

2、第i个约束取=, , ; L=u1,v1,u2,v2, 表示决策变量xi的约束uixivi(ui和vi可以取-和+ ).,(3) mathematica5.0版本中被淘汰的命令 ConstrainedMaxf,约束条件,约束变量; ConstrainedMinf,约束条件,约束变量 默认约束变量非负.,几个可选项: WorkingPrecision: 内部计算使用的有效数字位数(默认16位); AccuracyGoal: 计算结果的绝对精度(默认); PrecisionGoal: 计算结果的相对精度(默认WorkingPrecision的一半); MaxIterations: 最大迭代次数(默

3、认100).,2. 求解非线性规划的命令(5.0以上版本): NMaximizef,x1,x2,(也称无约束极值) NMinimizef,x1,x2, (也称无约束极值) NMaximizef,约束条件,x1,x2, NMinimizef,约束条件,x1,x2,输入: c=3,5; A=1,3,1,1; b=3,2; LinearProgrammingc,A,b,例1 求解线性规划: min 3x+5y st x+3y3 x+y2 x,y0,输出:,只输出最优解, 不输出最优值.,欲求最优值, 再输入: c.%,例2 求解线性规划: max -2x+10y st x-y0 -x+5y5 x,y

4、0,输入: c=-2,10; A=1,-1,1,-5; b=0,-5; LinearProgramming-c,A,b,输出:,欲求最优值, 再输入: -c.%,例3 输入 LinearProgramming-3,2,-1,-1,2,2,-1,4 输出 LinearProgramming:lpsnf: No solution can be found that satisfies the constraints.(无可行解),例4 输入 LinearProgramming2,-3,1,1,1,-1,1,-1,2,0, -1,1,-1,1 输出 1,-1,例5 输入 NMaximizex/(1+

5、Expx),x 输出 0.278465,x-1.27846,例6 输入 NMinimizeCosx-Expx y,x2+y20.795976,y-0.605328,程序1,练习:,1. 求投资策略问题的解.,2. 计算拌合场选址问题的近似解. (注意: 迭代次数超过1000) 或求供应问题的解.,程序2,程序3,线性规划模型及其解法,在前面我们介绍了一般的最优化问题的数学模型, 即 min z = f(x) s.t. gi(x) 0 i=1,2,m 其中对目标函数z= f(x)可以是求最小(min)也可以是求最大(max). 约束条件 gi(x)0 i=1,2,m, 界定了xRn的范围, 我们

6、称为模型的可行解区域, 简称可行域. 属于可行域的x(Rn)称为可行解. 满足min z = f(x)的可行解才是模型的解, 称为最优解. 最优解对应的目标函数值称为最优值. 有些约束优化问题用无约束方法求得的解满足约束条件, 此时的最优解必为可行域的内部点, 但是大多数的约束优化问题的最优解是在可行区域的边界上, 当然我们应该寻求不同约束优化模型的一般解法.,如果函数f (x)和gi (x)均为线性函数时, 被称为线性规划(Linear Programming, 简记为LP)模型; 否则, 被称为非线性规划(Nonlinear Programming, 简记为NLP)模型. 我们还是先引入具

7、体的实例模型, 分别讨论其形式及其解法. 生产计划问题 某厂生产甲乙两种口味的饮料, 生产每百箱甲饮料需用原料6kg, 工人10名, 可获利10万元; 生产每百箱乙饮料需用原料5kg, 工人20名, 可获利9万元; 现该厂共有原料60kg, 工人150名, 又由于其它条件的限制, 甲饮料产量不得超过8百箱. 问应如何安排生产计划, 即两种饮料各生产多少可使获利最大. 进一步讨论以下问题:,一般地, 我们称约束优化模型为数学规划模型.,2)若每百箱甲饮料获利可增加1万元, 是否应改变生产计划; 3)如果以百箱为最小生产单位, 怎么办? 这个问题的数学模型很容易建立. 决策变量是甲乙两种饮料的产量

8、, 分别记作x1, x2(以百箱为单位, 但可以是小数). 目标函数是所获总利润, 约束条件是原料、工人和对甲饮料产量的限制, 则有 max z = 10 x1 + 9 x2 s.t. 6 x1 + 5 x2 60 10 x1 + 20 x2 150 x1 8 x1, x2 0 这是一个非常简单的LP模型.,1)若投资0.8万元可增加原料1kg, 是否应作这项投资;,对于进一步讨论的问题为: 1)考察将原料数量改为61kg后的最优值, 是否比原问题的最优值高出投资额(0.8万元); 即原料数量改变1个单位时, 目标函数(总利润)的变化量, 它度量了这种资源的价值, 经济学上称为影子价格. 2)

9、是将目标函数 z =10 x1+9x2改为 z =11x1+9x2, 这样一来, 最优解是否有变化; 这个问题是对LP目标函数数据的灵敏度分析. 3)附加了解的整数性质, 成为整数(线性)规划(Integer Programming, 简记为IP)问题.,由于这个问题仅有两个变量, 其求解方法可以采用图解法, 并由此引出线性规划的一般求解方法单纯形(Dantzig)方法和Mathematica程序.,10 x1+20 x2=150,6x1+5x2=60,x1=8,10 x1+9x2=0,10 x1+9x2=67.5,10 x1+9x2=80,(0, 7.5),(8, 0),(8,2.4),对图

10、的分析发现最优解应该是直线 10 x1+20 x2=150 和6x1+5x2=60 的交点,最优值为,模型求解 我们先用图解法讨论LP模型的解.,从图上我们进行试算 105+95=95 106+94=96,我们再用图解法讨论IP模型的解.,数学规划模型的图解方法只是为我们在直观上提示了一种求解的思路, 当然不能作为普遍问题的解法.线性规划模型有一种非常好的解法单纯形方法.,107+93=97,108+92=98,所以整数最优解为(8, 2), 最优值为98.,单纯形方法是以线性代数的知识为基础建立的算法, 我们不对此方法作介绍. 只需掌握Mathematica解线性规划的程序命令.,线性规划的

11、对偶规划问题,考虑一般线性规划:,其中c为n维行向量, x为n维列向量, A为mn矩阵, b为m维列向量.,Min cx s.t Axb (LP) x0,线性规划:,Max yb s.t yAc (DLP) y0,为原问题(LP)的对偶规划(DLP), 其中y为m维行向量.,定理: (1) (LP)有最优解当且仅当(DLP)有最优解, 且最优值相等; (2) (LP)最优值无界当且仅当(DLP)无可行解; (3) (LP)无可行解当且仅当(DLP)最优值无界.,如生产计划问题: max z = 9 x1 + 10 x2 s.t. 6 x1 + 5 x2 60 10 x1 + 20 x2 150

12、 x1 8 x1, x2 0,其对偶规划问题为:,min u = 60 y1 + 150 y2+ 8 y3 s.t. 6 y1 +10 y2 + y3 9 5 y1 +20 y2 10 y1, y2 , y3 0,线性规划(LP)与其对偶规划(DLP)有如下结论:,1.57143, 0.0571429, 0, umin = 102.857,生产计划问题的对偶规划的最优解为:,这与我们单独讨论生产计划问题中增加一吨原料和增加一名工人所产生的利润增加值是一致的, 且最优值相等. 实际上, 在一般的生产计划问题中, 其对偶规划的解就是经济学中的影子价格问题.,下面我们看一个稍复杂一点的例子 投资策略

13、问题 某部门现有资金10万元, 五年内有以下投资项目供选择: 项目A: 从第一年到第四年每年初投资, 次年末收回本金且可获利15%; 项目B: 第三年初投资, 第五年末收回本金且可获利25%, 最大投资额为4万元; 项目C: 第二年初投资,第五年末收回本金且可获利40%, 最大投资额为3万元; 项目D: 每年初投资, 年末收回本金且可获利6%. 如何确定投资策略使第五年末的本息总额最大. 问题的目标函数是第五年末的本息总额, 决策变量是每年初各个项目的投资额, 约束条件是每年初所拥有的资金.,用xij表示第 i年初( i=1, 2, 5)项目 j( j=1, 2, 3, 4分别代表A,B,C,

14、D)的投资额, 列表确定需要求解的 xij.,因项目D每年初可以投资且年末能收回本金, 所以每年初应把全部资金投出去, 由此可得约束条件:,第一年初: 10万元资金全部投向A和D, 有 x11+x14=10 第二年初: 拥有的资金为第一年D的 x14收回的本息, 全部投向A,C,D, 有 x21+x23+x24=1.06 x14,第三年初:拥有的资金为第一年A的x11和第二年D的x24收回的本息, 全部投向A,B,D, 有 x31+x32+x34=1.15 x11+1.06 x24 第四年初: 类似地有 x41+x44=1.15 x21+1.06 x34 第五年初: x54=1.15 x31+

15、1.06 x44 此外项目B,C对投资额的限制为 x234, x323 第五年末的本息总额为 z=1.15 x41+1.40 x23+1.25 x32+1.06 x54 将以上列出的目标函数和约束条件归纳在一起, 并加上对的非负限制就得到了该问题的优化模型. 显然, 这也是一个线性规划模型.,Max z=1.15 x41+1.40 x23+1.25 x32+1.06 x54 s.t. x11+x14=10 -1.06 x14+ x21+x23+x24=0 -1.15 x11-1.06 x24+x31+x32+x34=0 -1.15 x21-1.06 x34 x41+x44=0 -1.15 x3

16、1-1.06 x44 +x54=0 x234, x323 xij 0 ( i=1, 2, 5, j=1, 2, 3, 4),如果我们将决策向量表示为 x=(x11, x14, x21, x23, x24, x31, x32, x34, x41, x44, x54)T 则目标向量为 c=(0, 0, 0, 1.4, 0, 0, 1.25, 0, 1.15, 0, 1.06) 右端向量为 b=(10, 0, 0, 0, 0, 3, 4)T,约束条件的系数矩阵为,其中r =-1.06, s =-1.15,故, 此问题可表示为 max z = cx s.t. Axb, 或 Ax=b, 以及 x0 解的

17、结果为 x=(3.8268, 6.1732, 3.5436, 3, 0, 0.4008, 4, 0, 4.0752, 0, 0.4609)T, zmax=14.375.,第一年项目A, D分别投资3.8268和6.1732(万元); 第二年项目A, C分别投资3.5436和3(万元); 第三年项目A, B分别投资0.4008和4(万元); 第四年项目A投资4.0752(万元); 第五年项目D投资0.4609(万元). 五年后总资金为14.375(万元), 盈利43.75%, 平均年盈利8.75%.,14.375, x11 - 3.47826, x14 - 6.52174, x21 - 3.91

18、304, x23 - 3., x24 - 0, x31 - 0, x32 - 4., x34 - 0, x41 - 4.5, x44 - 0, x54 - 0,380/53, 150/ 53, 0, 3, 0, 0, 4, 225/53, 9/2, 0, 0, =7.16981, 2.83019, 0, 3., 0, 0, 4., 4.24528, 4.5, 0, 0 zmax =115/ 8=14.375,这样一个较简单问题是不可能用图解法的.,供应与选址问题: 某建筑公司有6个工地要开工, 每个工地的位置(用平面坐标a, b表示, 距离单位: km)及水泥日用量(用d表示, 单位: 吨)由下表给出. 目前有两个临时料场分别位于坐标为A(5, 1), B(2, 7)的两点, 日储备量各为20吨. 假设从料场到工地之间有直线道