第五章线性规划LP.doc

第五章 线性规划（LP）第一节 向量和矩阵的基本知识1矩阵的概念定义1：由个数排成的一个行列（数）表叫做一个行列（或）矩阵。叫做这个矩阵的元素；常用大写字母A、B等表示矩阵，有时为明确矩阵记为或。注意：（1）解释几个术语：行、列、下标等。（2）矩阵与行列式形式不同、意义不同，行列式表示一个数，矩阵只是一个数表；行列式要求行列数相同，而矩阵不然。例如：（1）三阶矩阵 （2）的矩阵 B=向量是一种特殊的矩阵，分为行向量和列向量。（1）行向量是的矩阵，它的具体形式为 ；（2）列向量是的矩阵，它的具体形式为： ，或者。例如： ；2几种特殊矩阵（1）零矩阵：元素全为零的矩阵；记为。Note：零矩阵只是给出了元素的特征（全为0），由于行、列数的不同有不同形式的零矩阵。例如 二阶零矩阵： ，零矩阵：。（2）负矩阵：设，则称为的负矩阵；记为。Note：负矩阵是相对于一个给定的矩阵而言的。（3）方阵：行列数相同的矩阵。n行n列矩阵叫n阶矩阵。 二阶方阵 ；四阶方阵.（4）单位矩阵：主对角线上元素全为1，其余元素全为0的方阵。Note：（1）单位阵是一类特殊方阵。（2）定义给出了元素特征，由于阶数不同有不同形式的单位阵。n阶单位矩阵记为。例如，三阶单位阵,（3）矩阵的相等：设A、B是数域F上两个矩阵，若1）A、B具有相同的行数和列数；2）对应位置上的元素相等。则称A与B相等。记为A=B。3、矩阵的运算及性质(1）加法：定义：设，；与的和为矩阵；记为，即=。Note：(1)注意可加的条件以及相加的结果，实质转化为数的加法运算。 (2）利用负矩阵可以定义矩阵的减法：设，定义=。例1：设，于是，。例2：设三阶方阵满足，其中，求。(2）数量乘法定义：设，与的数乘为，记为。 例如：设，则2。(3）乘法(A）定义：设，；与的乘积为，其中；记为。Note：可乘的条件与结果。例如：（1）设,于是，。 （2）设，于是 。(B）性质：（注意下列式子有意义的条件） （1）； （2）； （3）； （4） 。Note：1）由定义及矩阵相等的概念证明（略）。 2）乘法一般不满足交换律（可分析不同的情况）。 3）由于而可能有，所以“消去律”不成立，即“，且不一定有”。(C）方阵的方幂：注：由于乘法满足结合律，所以有限个矩阵相乘有意义，由可乘的条件，只有方阵才可以自乘。定义：设，定义，称为的次方幂；规定。性质：显然。Note：1）幂指数为非负整数。 2）一般地，以及无类于其它指数性质和代数公式，如等。(D）矩阵方程：（线性方程组的矩阵表示）设线性方程组 （1），其系数矩阵为，令，则方程组（1）可写为矩阵方程 （2）。 若，则为齐次线性方程组的矩阵表示。求（1）的解，即求满足（2）的矩阵（列向量）。例3：求解下列方程的解：，首先，把上面的方程组化成矩阵方程的形式，即记 ，于是上面的方程组可以写成如下的形式： 。这种矩阵方程在Matlab中是容易求解的。上面的例子可以这样写： A=1,-5,6;4,7,8;5,-2,7; b=-8,5,7; x=Abx = 3.8696 0.3913 -1.6522例4：求解下列方程的解：，首先，把上面的方程组化成矩阵方程的形式，即记 ，于是上面的方程组可以写成如下的形式：。这种矩阵方程在Matlab中的求解过程如下：A=1,2,3;3,2,1; b=2;3; c=Abc = 0.8750 0 0.3750注意：这个方程组得到的是范数最小的解。4）转置定义：设，把的行变为列、列变为行所得的行列矩阵称为矩阵的转置（矩阵），记为（或者记为）。（可写出具体形式）性质：（1）； （2）； （3）； （4）。第二节 线性规划问题（LP）例1 设有两个煤厂甲和乙，每月进每煤分别为60吨和100吨，联合供应三个居民区A,B,C,三个居民区每月对煤的需求量为50吨，70吨和40吨。煤厂到各个居民区的距离如下表所示。 表一：煤厂到居民区的距离表 居民区煤厂ABC甲10公里5公里6公里乙4公里8公里12公里 如何分配供煤量使得运输量达到最小？解：设甲乙煤厂到各个居民区的供煤量如下表所示： 表二：煤厂到居民区的距离表 居民区煤厂ABC发煤量甲60乙100收煤量507040求最小运输量于是运输量为 。由于发煤量的限制，有下列等式成立： 。又由于收煤量的限制，有下列等式成立：。所以这个运输问题必需满足下列条件： ； 。当然满足这个条件的运输方案有很多，我们要求的是最小的运输量。即求： 我们用向量和矩阵的知识，可以进一步简化上面的表达式。 记 ， ，于是 。方法一：对于这个问题，我们可以用Matlab来计算。首先，在命令窗口，输入： c=10;5;6;4;8;12; beq=60;100;50;70;40; Aeq=1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1; lb=zeros(6,1); x,fval,exitflag,output=linprog(c,Aeq,beq,lb,)运行的结果如下：Optimization terminated successfully.x = 0.0000 20.0000 40.0000 50.0000 50.0000 0.0000fval = 940.0000exitflag = 1output = iterations: 5 cgiterations: 0 algorithm: lipsol注意：对于线性规划问题，Matlab有linprog这个命令可以使用。它可以解决的问题的形式如下： ，其中均为列向量，均为矩阵。linprog这个命令的调用格式有以下几种：（1） x=linprog(c,A,b,Aeq,beq);（2） x=linprog(c,A,b,Aeq,beq,lb,ub,x0);（3） x=linprog(c,A,b,Aeq,beq,lb,ub,x0,options);（4） x,fval=linprog(-);（5） x,fval,exitflag,output=linprog(-);例2：自来水输送问题问题：某市有甲、乙、丙、丁四个居民区，自来水由A,B，C三个水库供应。四个居民区每天必须得到保证的基本生活用水量分别为30，70，10，10千吨。由于水源紧张，三个水库每天最多只能分别供应50，60，50千吨自来水。因为地理位置的差别，自来水公司从各水库向各区送水所需要付出的引水管理费不同（具体见表格，其中水库C与丁区之间没有输水管道），其它管理费用为450元每千吨。按公司规定，各区用户按照统一标准900元每千吨收费。此外，四个区都向公司申请了额外用水量，分别为50，70，20，40千吨。该公司应该如何分配每天的供水量，使得获利最多？为了增加供水量，自来水公司正在考虑进行水库改造，使得三个水库每天的最大供水量提高一倍，问那时的供水方案如何改变？公司利润可以增加多少？ 表格1 各区的引水管理费引水管理费甲乙丙丁A160130220170B140130190150C190200230/ 问题分析： 分配供水量就是安排从三个水库向四个区送水的方案，目标是使得获利最多。从题目中的数据来看，A,B，C三个水库的供水量160千吨，小于四个区的基本生活用水量与额外用水量之和300千吨。故水库的水总能全部卖出获利。于是，公司每天的总收入为元，与供水方案无关。同样，公司每天的其它管理费用为元，也与供水方案无关。所以，要使利润最大，只要使得引水管理费管理费最小即可。另外，供水方案自然要受到三个水库的供应量和四个区的需求量的限制。模型建立决策变量为A,B，C三个水库（）分别向甲、乙、丙、丁四个居民区（）的供水量。设水库向居民区的日供水量为。水库C与丁区之间没有输水管道,所以。 目标函数为 （1）约束条件为两类:第一类为水库的供应量限制，第二类是各居民区的需求量限制。首先，由于供水量总能卖出并获利，所以水库的供应量限制可以表示为： ， （2） ， （3） ， （4）考虑到各区的基本生活用水量和额外用水量，需求量限制可以表示为： ， （5） ， （6） ， （7） ， （8）同时，。对于上面的线性规划模型，我们可以把它化成矩阵形式：令 ，它们是11维的列向量。设 ， ， ，设 ，在Matlab中调用linprog的命令。具体的程序如下：c=160;130;220;170;140;130;190;150;190;200;230;b=80;140;30;50;-30;-70;-10;-10;beq=50;60;50;A=1,0,0,0,1,0,0,0,1,0,0; 0,1,0,0,0,1,0,0,0,1,0; 0,0,1,0,0,0,1,0,0,0,1; 0,0,0,1,0,0,0,1,0,0,0; -1,0,0,0,-1,0,0,0,-1,0,0; 0,-1,0,0,0,-1,0,0,0,-1,0; 0,0,-1,0,0,0,-1,0,0,0,-1; 0,0,0,-1,0,0,0,-1,0,0,0;Aeq=1,1,1,1,0,0,0,0,0,0,0; 0,0,0,0,1,1,1,1,0,0,0; 0,0,0,0,0,0,0,0,1,1,1; lb=zeros(11,1); x,fval,exitflag,output=linprog(c,A,b,Aeq,beq,lb) % the results is following: Optimization terminated successfully.x = 0.0000 50.0000 0.0000 0.0000 0.0000 50.0000 0.0000 10.0000 40.0000 0.0000 10.0000fval = 2.4400e+004exitflag = 1output = iterations: 6 cgiterations: 0 algorithm: lipsol所以，供水方案为：A水库向乙区供水50千吨，B 水库向乙、丁区分别供水50、10千吨，C水库向甲、丙区分别供水40、10千吨。引水管理费为24400元，所以利润为：144000720002440047600元。习题五l.生产炊事用具需要两种资源劳动力和原材料，某公司制定生产计划，生产三种不同的产品，生产管理部门提供的数据如下：ABC劳动力（小时/件）736原材料（公斤/件）445利润（元/件）423每天供应原材料200公斤，每天可供使用的劳动力为150小时。建立线性规划模型，使得总收益最大，并求出各种产品的日产量。2一家广告公司想在电视、广播上作广告，其目的是尽可能地吸引顾客。下面是市场调查的结