第1章线性规划及其扩展精选文档.ppt

《第1章线性规划及其扩展精选文档.ppt》由会员分享，可在线阅读，更多相关《第1章线性规划及其扩展精选文档.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章线性规划及其扩展本讲稿第一页，共三十七页一个LINGO程序一般会包含集合段、数据输入段、优化目标和约束段、初始段和数据预处理段等部分，每一部分有其独特的作用和语法规则，读者可以通过查阅相关的参考书或者LINGO的HELP文件详细了解，这里就不展开介绍了。LINGO的主要功能特色为：既能求解线性规划问题，也有较强的求解非线性规划问题的能力；输入模型简练直观；运算速度快、计算能力强；内置建模语言，提供几十个内部函数，从而能以较少语句，较直观的方式描述大规模的优化模型；将集合的概念引入编程语言，很容易将实际问题转换为LINGO模型；并且能方便地与Excel、数据库等其他软件交换数据。本讲稿第二

2、页，共三十七页LINGO的语法规定：的语法规定：（1）求目标函数的最大值或最小值分别用）求目标函数的最大值或最小值分别用MAX=或或MIN=来表示；来表示；（2）每个语句必须以分号）每个语句必须以分号“；”结束，每行可以有许多语结束，每行可以有许多语句，语句可以跨行；句，语句可以跨行；（3）变量名称必须以字母）变量名称必须以字母(AZ)开头，由字母、数字开头，由字母、数字(09)和下和下划线所组成，长度不超过划线所组成，长度不超过32个字符，不区分大小写；个字符，不区分大小写；（4）可以给语句加上标号，例如）可以给语句加上标号，例如OBJMAX=200*X1+300*X2；（5）以惊叹号）以惊

3、叹号“！”开头，以分号开头，以分号“；”结束的语句是注结束的语句是注释语句释语句;（6）如果对变量的取值范围没有作特殊说明，则默认所有决策变）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；量都非负；（7）LINGO模型以语句模型以语句“MODEL：”开头，以开头，以“END”结束，结束，对于比较简单的模型，这两个语句可以省略。对于比较简单的模型，这两个语句可以省略。本讲稿第三页，共三十七页在LINGO的MODEL窗口内输入如下模型：model:max=2*x1+3*x2;x1+2*x2=8;4*x1=16;4*x260;0.1*x1+0.05*x2+0.02*x3+0.2*x4

4、+0.05*x53;0.05*x1+0.1*x2+0.02*x3+0.2*x4+0.08*x58;X1+x2+x3+x4+x552;例例1.5.2 用用LINGO求解例求解例1.1.3食谱问题。食谱问题。解解 例例1.1.3食谱问题的数学模型为（食谱问题的数学模型为（1.1.6）本讲稿第八页，共三十七页求解输出结果如下:Global optimal solution found at iteration:4Objective value:22.40000Variable Value Reduced CostX1 0.000000 0.7000000X2 12.00000 0.000000X3

5、0.000000 0.6166667X4 30.00000 0.000000X5 10.00000 0.000000Row Slack or Surplus Dual Price1 22.40000 -1.0000002 0.000000 -0.58333333 4.100000 0.0000004 0.000000 -4.1666675 0.000000 0.8833333本讲稿第九页，共三十七页因此,每周每个动物的配料为饲料A2、A4、A5分别为12、30和10，合计为52，可使得饲养成本达到最小，最小成本为22.4元；不选用饲料和的原因是因为这两种饲料的价格太高了，没有竞争力。“Redu

6、ced Cost”分别等于0.7和0.617，说明当这两种饲料的价格分别降低0.7元和0.62元以上时，不仅选用这两种饲料而且使得饲养成本降低。从“Slack or Surplus”可以看出，蛋白质和维生素刚达到最低标准，矿物质超过最低标准4.1；从“Dual Price”可以得到降低标准蛋白质1单位可使饲养成本降低0.583元，降低标准维生素1单位可使饲养成本降低4.167元，但降低矿物质的标准不会降低饲养成本，如果动物的进食量减少，就必须选取精一些的饲料但要增加成本，大约进食量降低1可使得饲养成本增加0.88元。本讲稿第十页，共三十七页(1.5.1)1.5.2 应用应用MATLAB求解线性

7、规划求解线性规划MATLAB（MATrix LABoratory）的基本含义是矩阵实验室，它是由美国MathWorks公司研制开发的一套高性能的集数值计算、信息处理、图形显示等于一体的可视化数学工具软件。它是建立在向量、数组和矩阵基础之上的，除了基本的数值计算、数据处理、图形显示等功能之外，还包含功能强大的多个“工具箱”，如优化工具箱（optimization toolbox）、统计工具箱、样条函数工具箱和数据拟合工具箱等都是优化计算的有力工具。在这里仅介绍用MATLAB6.5优化工具箱求解线性规划问题。一般线性规划问题的数学模型为本讲稿第十一页，共三十七页其中其中C是目标函数的系数行向量（常

8、数）是目标函数的系数行向量（常数）,X 是是n维列向维列向量（决策变量），量（决策变量），A,A1是常数矩阵，是常数矩阵，b,b1是常数向量，是常数向量，lb,ub是是n维列向量分别表示决策变量维列向量分别表示决策变量X的下界与上界。的下界与上界。在在Matlab优化工具箱（优化工具箱（Optimization Toolbox）中，求解）中，求解(1.5.1)的程序如下：的程序如下：x，fval，exitflag，output，lambda=linprog(c，A，b，Aeq，beq，lb，ub，x0，options)说明：说明：(1)A是不等式约束的系数矩阵，是不等式约束的系数矩阵，b是相应

9、的常数列是相应的常数列向量，若没有不等式约束，则均用向量，若没有不等式约束，则均用 代替；代替；(2)Aeq是等式约束的系数矩阵，是等式约束的系数矩阵，beq是相应的常数列向是相应的常数列向量，若没有等式约束，则均用量，若没有等式约束，则均用代替；代替；(3)如果某个变量无下界，则用如果某个变量无下界，则用-inf表示；如果某个变量无表示；如果某个变量无上界，则用上界，则用inf表示，若决策变量表示，若决策变量 无下界，则无下界，则lb用用代替；代替；若决策变量若决策变量 无上界，则无上界，则ub用用代替；代替；(4)x0是线性规划的初始解，这种设计仅对中规模算法有是线性规划的初始解，这种设计

10、仅对中规模算法有效，通常可以缺省。效，通常可以缺省。本讲稿第十二页，共三十七页(5)输出输出 是最优解，是最优解，fval是最优值。是最优值。(6)输出输出exitflag描述了程序的运行情况，若其值大于零，描述了程序的运行情况，若其值大于零，表示程序收敛到最优解表示程序收敛到最优解 ；若其值等于零，表示计算达；若其值等于零，表示计算达到了最大次数；若其值小于零，表示问题无可行解，到了最大次数；若其值小于零，表示问题无可行解，或程序运行失败。或程序运行失败。(7)输出输出output表示程序运行的某些信息，如迭代次数表示程序运行的某些信息，如迭代次数(iterations)、所用算法、所用算法

11、(algorithm)、共轭梯度、共轭梯度(cgiterations)等。等。(8)lambda表示解处的拉格朗日乘子，其中表示解处的拉格朗日乘子，其中lower，upper，ineqlin，eqlin分别对应于下界、上界、不等式约分别对应于下界、上界、不等式约束与等式约束。束与等式约束。本讲稿第十三页，共三十七页例1.5.3 用MATLAB解线性规划问题（1.5.2）本讲稿第十四页，共三十七页解解 Matlab程序如下程序如下:c=-2,-1,1;A=1,4,-1;2,-2,1;b=4;12;Aeq=1,1,2;beq=6;lb=0,0,-inf;ub=inf,inf,5;x,z=linpr

12、og(c,A,b,Aeq,beq,lb,ub)运行后得到输出运行后得到输出Optimization terminated successfully.x=4.6667 0.0000 0.6667z=-8.6667本讲稿第十五页，共三十七页例例1.5.4 用MATLAB求解线性规划问题（1.5.3）解解 首先转化为求最小值问题本讲稿第十六页，共三十七页Matlab程序如下程序如下c=-2,-3,5;A=-2,5,-1;b=-10;Aeq=1,1,1;beq=7;lb=0,0,0;x,z=linprog(c,A,b,Aeq,beq,lb)运行后得到输出运行后得到输出x=6.4286 0.5714 0

13、.0000z=-14.5714键入键入 s=-z 运行后得到原问题的目标函运行后得到原问题的目标函数最大值数最大值 s=14.5714本讲稿第十七页，共三十七页用用MATLAB求解例求解例1.5.2的程序与输出结果为：的程序与输出结果为：c=0.2,0.7,0.4,0.3,0.5;A=-0.3,-2,-1,-0.6,-1.8;-0.1,-0.05,-0.02,-0.2,-0.05;-0.05,-0.1,-0.02,-0.2,-0.08;1,1,1,1,1;b=-60;-3;-8;52;lb=0,0,0,0,0;x,z=linprog(c,A,b,lb)Optimization terminat

14、ed successfully.x=0.0000 12.0000 0.0000 30.0000 10.0000z=22.4000本讲稿第十八页，共三十七页习题习题11.建立下列线性规划问题的数学模型（1）某工厂生产A、B、C三种产品，三种产品对于材料费用、劳动力和电力的单位消耗系数，资源限量和单位产品价格如表1.1所示。问应如何确定生产计划可使得总产值达到最大？建立线性规划问题的数学模型。表表1.1 生产计划问题的数据生产计划问题的数据 产品产品资资源源ABC资资源源限量限量材料材料费费用（元）用（元）22.54320劳动劳动力（人天）力（人天）618640电电力（度）力（度）5510750单

15、单位价格（百元）位价格（百元）6410本讲稿第十九页，共三十七页（2）某疗养院营养师要为某类病人拟订一周的菜单。可供选择的蔬菜及其费用和所含营养成分的数量以及这类病人每周所需各种营养成分的最低数量如表1.2所示。另外，为了口味的需要，规定一周内所用卷心菜不多于2份，其他蔬菜不多于4份。若病人每周需要14份蔬菜，问选用每种蔬菜各多少份，可使生活费用最小。建立线性规划问题的数学模型。表表1.2 食谱问题的数据食谱问题的数据蔬菜蔬菜每份蔬菜所含每份蔬菜所含营营养成分养成分费费用用（元（元/份）份）铁铁(mg)磷磷(mg)VA(单单位位)VC(mg)烟酸烟酸(mg)青豆青豆0.451041580.31

16、.5胡胡萝萝卜卜0.4528906530.351.5花菜花菜1.05502550530.62.4卷心菜卷心菜0.42575270.150.6甜菜甜菜0.5221550.251.8土豆土豆0.57523580.81.0每周每周营营养养最低需求量最低需求量6.0325175002455.0本讲稿第二十页，共三十七页播种计划表亩产量表土地作物作物面积100600700500500800500850400400150300土地面积200300500本讲稿第二十一页，共三十七页（4）某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙，已知各种牌号的糖果中A、B、C的含量，原料成本，各种原料的每月

17、限制用量，三种牌号糖果的单位加工费及售价如表1.4所示，问该厂每月应生产这三种牌号的糖果各多少千克，使该厂获利最大？试建立这个问题的线性规划数学模型。甲乙丙原料成本(元/千克)每月限制用量（千克）A8.002000B6.002500C4.001200加工费（元/千克）2.01.61.2售价（元）13.611.49表表1.4 糖果厂生产计划数据表糖果厂生产计划数据表本讲稿第二十二页，共三十七页0.00.51.01.51.92.53.03.54.04.51.00.90.71.52.02.43.22.02.73.55.05.56.06.67.07.68.59.010.01.04.03.62.75.7

18、4.66.06.87.3表1.5 随 变化的数据表求拟合以上数据的直线 ，目标为使y的各个观察值同按直线关系所预期的值的绝对偏差总和为最小（即：误差绝对值之和最小）。建立线性规划问题的数学模型。（提示：对任意的 ，令：那么，）本讲稿第二十三页，共三十七页2.将下列线性规划问题化成标准形(1)(2)本讲稿第二十四页，共三十七页3.用图解法求解下列线性规划问题(1)(2)本讲稿第二十五页，共三十七页(3)(4)本讲稿第二十六页，共三十七页(5)本讲稿第二十七页，共三十七页4.试将下述问题改写成线性规划问题本讲稿第二十八页，共三十七页本讲稿第二十九页，共三十七页8.用单纯形方法求解下列线性规划问题(

19、1)(2)本讲稿第三十页，共三十七页(3)(4)本讲稿第三十一页，共三十七页9某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制和每单位产品的获利如表1.6。问工厂应分别生产甲、乙产品多少单位才能使工厂获利最大？建立线性规划问题数学模型，并用单纯形方法求出最优解。产品资源甲乙资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元表1.6 资源配置问题的数据本讲稿第三十二页，共三十七页10.对于线性规划问题：（1）求该线性规划问题的全体基本最优解；（2）确定任意最优解的表达式。本讲稿第三十三页，共三

20、十七页11.用两阶段法求解线性规划问题。(1)(2)本讲稿第三十四页，共三十七页(3)(4)本讲稿第三十五页，共三十七页12.某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，以及资源的限制和每单位产品的获利如下表1.7。问工厂应分别生产甲、乙产品多少单位才能使工厂获利最大？对应的最大利润是多少？建立线性规划问题的数学模型，并用单纯形方法求出所有的基础最优解。产品资源甲乙资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元50元 表1.7 资源配置问题的数据本讲稿第三十六页，共三十七页13.考虑下述线性规划问题14用LINGO和MATLAB求解本章习题中的线性规划问题。本讲稿第三十七页，共三十七页