用MATLAB求解线性规划课件.ppt

线 性 规 划,Linear Programming,第七章 数学实验,一 用Mathematica求解线性规划,例7.1 用Mathematica求解,输入：,运行得出结果：,例7.2 用Mathematica求解,输入：,运行得出结果：,二 用MATLAB求解线性规划,MATLAB-Matrix Laborotory(矩阵实验室),MATLAB简介,MATLAB自1984年由美国MathWorks公司研发，现已成为国际公认的最优秀的工程应用开发环境。它功能强大、简单易学、编程效率高。在欧美，MATLAB已成为线性代数、自动控制理论、数字信号处理、时间序列分析、动态系统仿真、图像处理等课程的基本教学工具，成为本硕博必须掌握的基本技能。,MATLAB它作为一种编程语言和可视化工具，可解决工程、科学计算和数学学科中许多问题。,MATLAB建立在向量、数组和矩阵的基础上，使用方便，人机界面直观，输出结果可视化。,矩阵是MATLAB的核心。,MATLAB简介,数值计算和符号计算功能 数值计算功能包括：矩阵运算、多项式和有理分式运算、数据统计分析、数值积分、优化处理等。 符号计算将得到问题的解析解。图形功能 可绘制二维、三维乃至四维图形，并可进行图形和坐标的标识、视角和光照设计、色彩精细控制等。,MATLAB功能,MATLAB语言(1)命令行的交互式操作：用户在Matlab的命令窗口键入一个命令，及时返回结果；(2)程序方式：可以由Matlab定义的语言在编辑器中编写程序，运行后返回结果.Matlab其语法与C语言极为类似，但编程效率比C高且语言简单可读性强、调试容易、调用方便。包括有: a. M文件 b. 函数 c. 绘图,MATLAB功能,应用工具箱基本部分中有数百个内部函数。其工具箱分为两大类：1) 功能性工具箱 2) 学科性工具箱 功能性工具箱主要用来扩充其符号计算功能、可视建模仿真功能及文字处理功能等。 学科性工具箱专业性比较强，如控制系统工具箱、信号处理工具箱、神经网络工具箱、最优化工具箱、金融工具箱等，,MATLAB功能,主 要 内 容,三、 举例,四、 线性规划求解,二、 数组与矩阵,一、 变量与函数,Matlab是以矩阵为基本运算单元的，它的大部分运算或命令都是在矩阵运算的意义下执行的。而构成矩阵的基本单元是数字。,一、变量与函数,258369,1、变量 命名规则是：（1）变量名必须是不含空格的单个词；（2）变量名区分大小写；（3）变量名最多不超过19个字符；（4）变量名必须以字母打头，之后可以是 任意字母、数字或下划线，变量名中 不允许使用标点符号.,一、变量与函数,特殊变量表,2、数学运算符号及标点符号,一、变量与函数,注1MATLAB的每条命令语句后，若为逗号或无标点符号，则显示命令的结果；若为分号，则仅仅执行赋值操作，不显示运算结果。注2“%” 后面所有文字为注释。注3“.”表示续行。如果表达式一行写不下，可加上续行符并按下回车键继续写。例如 s=1-1/2+1/3-1/4+1/5-1/6+1/7- 1/8+1/9-1/10+1/11-1/12;,一、变量与函数,3、表达式:用运算符将有关运算量连接起来的式子。(1)算术运算符:(加)、(减)、*(乘)、/(右除)、(左除)、(乘方)对于矩阵来说，左除和右除表示两种不同的矩阵运算。(2)关系运算符:(大于)、=(大于或等于)、=(等于)、=(不等于)(3)逻辑运算符:&(与)、|(或)和(非),一、变量与函数,3、数学函数,MATLAB的内部函数是有限的，有时为了研究某一个函数的各种性态，需要为MATLAB定义新函数，为此必须编写函数文件. 函数文件是文件名后缀为M的文件，这类文件的第一行必须是一特殊字符function开始，格式为： function 因变量名=函数名（自变量名）函数值的获得必须通过具体的运算实现，并赋给因变量.,4、M文件,Matlab的应用程序也以M文件保存。,M文件建立方法：1. 在Matlab中，点:File-New-M-file2. 在编辑窗口中输入程序内容3. 点：File-Save，存盘，M文件名必须与函数名一致。,4、M文件,例7.3 定义函数 f(x1,x2)=100(x2-x12)2+(1-x1)2 ，计算 f(1,2)。,function f=fun(x)f=100*(x(2)-x(1)2)2+(1-x(1)2,解：1.建立M文件：fun.m,MATLAB(fun),2. 可以直接使用函数fun.m,计算 f(1,2), 只需在Matlab命令窗口键入命令：x=1 2fun(x),返回,先建立M文件fun2.m定义函数f（x），再在Matlab命令窗口输入fun2(2),fun2(0.5), fun2(-1)即可。,MATLAB(fun2),返回,4、赋值语句：a、直接赋值语句： (1) 赋值变量=赋值表达式 (2) 赋值表达式 第二种语句形式下，将表达式的值赋给永久变量ans。b、函数调用语句： 返回变量列表=函数名（输入变量列表）,1、创建简单的数组,二、数组与矩阵,x=a b c d e f 创建包含指定元素的行向量,x=first：last 创建从first开始，加1计数，到last结束的行向量,x=first：increment：last 创建从first开始，加increment计数，last结束的行向量,x=linspace(first，last，n） 创建从first开始，到last结束，有n个元素的行向量,x=a b c d e f 创建包含指定元素的行向量,x=first：last 创建从first开始，加1计数，到last结束的行向量,x=first：increment：last 创建从first开始，加increment计数，last结束的行向量,x=a b c d e f 创建包含指定元素的行向量,x=first：last 创建从first开始，加1计数，到last结束的行向量,x=linspace(first，last，n） 创建从first开始，到last结束，有n个元素的行向量,x=first：increment：last 创建从first开始，加increment计数，last结束的行向量,x=a b c d e f 创建包含指定元素的行向量,x=first：last 创建从first开始，加1计数，到last结束的行向量,2、 数组元素的访问,（3）直接使用元素编址序号:x(a b c d) 表示提取数组x的第a、b、c、d个元素构成一个新的数组x(a) x(b) x(c) x(d).,（2）访问一块元素：x(a ：b ：c)表示访问数组x的从第a个元素开始，以步长为b到第c个元素（但不超过c），b可以为负数，b缺省时为1.,（1）访问一个元素：x(i)表示访问数组x的第i个元素.,列向量的数组操作和运算与行向量是一样的，唯一的区别是结果以列形式显示.,产生列向量有两种方法： 直接产生 例 c=1；2；3；4 转置产生 例 b=1 2 3 4; c=b 说明：以空格或逗号分隔的元素指定的是不同列的元素，而以分号分隔的元素指定了不同行的元素.,3、数组的方向,4、数组的运算,（1）标量-数组：,设：a=a1,a2,an, c=标量,则：a+c=a1+c,a2+c,an+c a.*c=a1*c,a2*c,an*c a./c= a1/c,a2/c,an/c(右除） a.c= c/a1,c/a2,c/an (左除） a.c= a1c,a2c,anc c.a= ca1,ca2,can,设：a=a1,a2,an, b=b1,b2,bn,则：a+b= a1+b1,a2+b2,an+bn a.*b= a1*b1,a2*b2,an*bn a./b= a1/b1,a2/b2,an/bn a.b=b1/a1,b2/a2,bn/an a.b=a1b1,a2b2,anbn,（2）数组-数组运算,1、矩阵的建立,（1）将矩阵的元素用方括号括起来，按矩阵行的顺序输入各元素，同一行的各元素之间用空格或逗号分隔，不同行的元素之间用分号分隔。在输入矩阵时，按Enter键也表示开始一新行. 例：键入命令: A=1 2 3;4 5 6;7 8 9 A=1,2,3;4,5,6;7,8,9输出结果： A = 1 2 3 4 5 6 7 8 9,(2)利用M文件建立矩阵：第一步：使用编辑程序输入文件内容。第二步：保存并设文件名为xxx.m。第三步：在MATLAB命令窗口中输入xxx，就会自动建立一个名为AM的矩阵，可供调用。,特殊矩阵的建立：,MATLAB(matrix1),d=eye(m，n) 产生一个m行、n列的单位矩阵,c=ones(m，n) 产生一个m行、n列的元素 全为1的矩阵,b=zeros(m，n) 产生一个m行、n列的零矩阵,a= 产生一个空矩阵，当对一项操作无结 果时，返回空矩阵，空矩阵的大小为零.,2、矩阵中元素的操作,（1）矩阵A的第r行：A（r，：）,（2）矩阵A的第r列：A（：，r）,（3）取矩阵A的第i1i2行、第j1j2列构成新矩阵:A(i1:i2, j1:j2),（4）以逆序提取矩阵A的第i1i2行，构成新矩阵:A(i2:-1：i1，：）,（5）删除A的第i1i2行，构成新矩阵:A(i1:i2，：)= ,（6）删除A的第j1j2列，构成新矩阵:A(：， j1:j2)= ,（7）将矩阵A和B拼接成新矩阵：A B；A；B,3矩阵的基本运算（）矩阵转置 B（）矩阵加和减 B + C（）矩阵乘法 B * C（4）矩阵乘法方阵的逆 inv（A）（5）矩阵除法 Ab=inv(A)*b（6）矩阵的乘方 A2（7）方阵的行列式：det（A）（8）方阵的特征值与特征向量：V，D=eigA,输入命令：C = B C = 1 5 9 2 6 10 3 7 11 4 8 12,输入命令： D = B * C D = 30 70 110 70 174 278 110 278 446,(1)矩阵转置运算：,(2)矩阵乘法：,要求B的列数等于C的行数,（3）矩阵点乘、加减法 当两矩阵维数相同时，运算符.*的结果是两矩阵的对应元素乘，加减法相同。 E = 1 2;3 4; F = 2 3;4 5; G = E .* F G = 2 6 12 20,点运算是两个维数相同矩阵对应元素之间的运算，在有的教材中也定义为数组运算。,（5）矩阵的除法解方程组：ax=b， 其中a是(n*m)的矩阵x=ab 或 x=b/a 注：ab运算等效于求a*x=b的解；而a/b等效于求x*b=a的解。,E = 1 2;3 4;,（6）矩阵的乘方 矩阵为方阵时，可以进行矩阵的乘方运算，运算符为，与矩阵分解有关 E3 ans = 37 54 81 118 若仅是元素进行乘方运算，可用运算符. E.3 ans = 1 8 27 64,( 7）矩阵的逆：利用函数inv计算，此时要求矩阵为方阵且可逆。 X = inv(E) X = -2.0000 1.0000 1.5000 -0.5000（8）矩阵元素的赋值与运算 Matlab允许用户对矩阵的单个元素进行赋值和操作，Matlab此时命令方式为 X(i,j)=变量名,例7.5 求解线性方程组AX=B 1 1.5 2 9 7 3 0 3.6 0.5 -4 4 -4 其中A= 7 10 -3 22 33 ， B= 20 3 7 8.5 21 6 5 3 8 0 90 -20 16,在MATLAB命令窗口输入命令： a=11.5,2,9,7;0,3.6,0.5,-4,4;7,10,-3,22,33;3,7,8.5,21,6;3,8,0,90,-20; b=3;-4;20;5;16; x=ab,得到的结果是： x = 3.5653 -0.9255 -0.2695 0.1435 0.0101,在MATLAB命令窗口输入： p=1,7,0,9,-20; %建立多项式系数向量 x=roots(p) %求根,得到的结果是： x = -7.2254 -0.4286 + 1.5405i -0.4286 - 1.5405i 1.0826,例7.6 求方程 x4+7x3 +9x-20=0的全部根,三、绘图功能,1、二维图形,(1) plot函数函数格式：plot(x,y) 其中x和y为坐标向量函数功能：以向量x、y为轴，绘制曲线。,例7.7 在0 x2内，绘制正弦曲线y=sinx，其程序为：,x=0:pi/100:2*pi;y=sin(x);plot(x,y),x=0:pi/100:2*pi;y1=sin(x);y2=cos(x);plot(x,y1,x,y2),例7.8 在0 x2内，同时绘制正、余弦曲线y1=sinx和y2=cosx，其程序为：,(1) plot函数函数格式：plot(x,y1,x,y2,x,y3, ) 函数功能：是以公共向量x为X轴，分别以y1，y2，y3，为Y轴，在同一幅图内绘制出多条曲线。,x=0:pi/100:2*pi;y1=sin(x);y2=cos(x);plot(x,y1,go,x,y2,b-.)其中参数go和b-.表示图形的颜色和线型。g表示绿色，o表示图形线型为圆圈；b表示蓝色，-.表示图形线型为点划线。,(1) plot函数格式：plot(x,y1,cs,.)，其中c表示颜色， s表示线型。函数功能：绘制出指定颜色和线型的曲线。,【例7.9】 用不同线型和颜色重新绘制例2图形，其程序为：,二维绘图函数小结,lot 二维图形基本函数fplot f(x)函数曲线绘制fill 填充二维多边图形polar 极坐标图bar 条形图loglog 双对数坐标图semilogx X轴为对数的坐标图semilogy Y轴为对数的坐标图stairs 阶梯形图axis 设置坐标轴clf 清除图形窗口内容close 关闭图形窗口,figure 创建图形窗口grid 放置坐标网格线gtext 用鼠标放置文本hold 保持当前图形窗口内容subplot 创建子图text 放置文本title 放置图形标题xlabel 放置X轴坐标标记ylabel 放置Y轴坐标标记,2.三维图形,（1）plot3函数 它是将二维函数plot的有关功能扩展到三维空间，用来绘制三维图形。函数格式：plot3(x1,y1,z1,c1,x2,y2,z2,c2,) 其中x1,y1,z1表示三维坐标向量，c1，c2表示线形或颜色。函数功能：以向量x，y，z为坐标，绘制三维曲线。,t=0:pi/50:10*pi;y=sin(t),z=cos(t);plot3(y,z,t);title(helix),text(0,0,0,origin);xlabel(sin(t),ylabel(cos(t),zlabel(t);grid;,例7.8 绘制三维的螺旋曲线y=sint和z=cost，其程序为：,用MATLAB求解线性规划,1. 模型：,命令：x=linprog（c, A, b）,命令：x=linprog（c，A，b，Aeq, beq）,注：若没有不等式 存在，则令A= ，b= .,2. 模型：,命令：1 x=linprog（c，A，b，Aeq,beq,VLB，VUB）,注：若没有等式约束 , 则令Aeq= ,beq= .,4. 命令：x,fval=linprog()返回最优解及处的目标函数值fval.,3. 模型：,例7.10 求解线性规划,解： 编写M文件xxgh1.m如下：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6;,在命令窗口输入：xxgh1 回车即得,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),b=850;700;100;900; Aeq=; beq=;vlb=0;0;0;0;0;0; vub=;,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;,例7.11 求解线性规划,解: 编写M文件xxgh2.m如下： c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30,0,20; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),在命令窗口输入：xxgh2 回车即得,问题1：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？,解 设需一级和二级检验员的人数分别为x1、x2人,因检验员错检而造成的损失为：,则应付检验员的工资为：,总检验费为：,故目标函数为：,约束条件为：,化简为线性规划模型：,编写M文件xxgh3.m如下：c = 40，36;A=-5， -3;b=-45;Aeq=;beq=;vlb = =0;0; vub=9;15; x,fval = linprog(c,A,b,Aeq,beq,vlb,vub),在命令窗口输入：xxgh3 回车即得,结果为：x = 9.0000 0.0000fval =360,即只需聘用9个一级检验员，总检验费最小为360.,问题2 （ 任务分配问题）某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,工件1、2、3数量分别为400、600和500,解：设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6 , 可建立以下模型：,编写M文件xxgh4.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),在命令窗口输入：xxgh4 回车即得,结果:x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004,即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800,作业一,大润发超市是个建在大学城边上的大型百货商场，每周对收银人员的需求，统计如下表,为了保证收银人员充分休息，收银人员每周工作5天，休息2天。问应如何安排收银人员的工作时间，使得所配收银人员最少？,作业二,某厂生产甲、乙两种口味的饮料,每百箱甲饮料需原料6千克,工人10名,可获利10万元;每百箱乙饮料需原料5千克,工人20名,可获利9万元。工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过800箱。问1）如何安排生产计划使获利最大。进一步讨论:2)若投资0.8万元可增加原料1千克,问应否作这项投资。3)若每百箱甲饮料获利可增加1万元,问应否改变生产计划。,小结,学习要点：1. 掌握用Mathematic求解线性规划； 2.掌握用MATLAB求解线性规划；,为了让员工们休息更愉快、方便，可将每位员工的休息时间安排在连续的两天；则可设,xi（i=1,2,3，7)表示星期一至日开始休息的人数，依题意我们可建立如下数学模型：,作业：,The end!,