MBA数据模型与决策：线性规划进一步讨论.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单纯形法,线性规划问题是求一个线性目标函数在一组线性约束条件下的极值问题目标函数根据实际问题的要求可能求最大化也可能是求最小化；每一个函数约束分为,等价约束,即约束函数=右端项和,不等式约束,即约束函数右端项或约束函数右端项因此，线性规划问题的形式有许多种，它们之间也可以相互转化.,单纯形法,为了方便讨论，我们将选择线性规划问题的如下形式为标准形式：,Maximize,Z,=,c,1,x,1,+,c,2,x,2,+.+,c,n,x,n,a,11,x,1,+,a,12,x,2,+,.,+a,1,n,x,n,=,b,1,a,21,x,1,+,a,22,x,2,+,.,+a,2,n,x,n,=,b,2,.,a,m1,x,1,+,a,m2,x,2,+,.,+a,mn,x,n,=,b,m,x,1,0,x,2,0,.,x,n,0.,单纯形法,1)目标函数的转化,若原问题的目标函数是求最小化，即:,minimize,Z,=,c,1,x,1,+,c,2,x,2,+.+,c,n,x,n,则可将目标函数乘以-1，等价转化为求如下最大化问题：,Maximize -,Z,=-,c,1,x,1,-,c,2,x,2,-.,c,n,x,n,转化后的问题与原问题有相同的最优解,单纯形法,2)不等式约束转化为等式约束,(1)如果约束条件是线性不等式:,a,11,x,1,+,a,12,x,2,+,.,+a,1,n,x,n,b,1,则通过引入松弛变量,x,n+1,，将其转化为等价的等式约束条件:,a,11,x,1,+,a,12,x,2,+,.,+a,1,n,x,n,+x,n+1,=,b,1,单纯形法,(2)如果约束条件是线性不等式:,a,11,x,1,+,a,12,x,2,+,.,+a,1,n,x,n,b,1,则通过引入剩余变量,x,n+1,0,，,将其转化为等价的等式约束条件:,a,11,x,1,+,a,12,x,2,+,.,+a,1,n,x,n,-x,n+1,=,b,1,单纯形法,3)变量约束的转换,在标准形式中，我们要求每个决策变量满足非负约束，如果原问题中某个变量是自由变量（即无非负限制）则可令,x,i,=x,i,x,I,x,I,0,x,i,0,.,代入原问题，即在原问题中将用两个非负变量之差代替,单纯形法,例：,将下列线性规划问题化为标准形式:,首先将最小化问题乘以-1，转化为最大化问题,在第一约束中引入松弛变量,x4,，第二个约束中引入剩余变量x5，再令自由变量,x,2,=x,2,x”,2,，并将第三约束方程两边同乘以（-1),得到与原问题等价的线性规划标准形式：,单纯形法,单纯形法,化为标准型后:,Maximize,Z,=,c,1,x,1,+,c,2,x,2,+.+,c,n,x,n,a,11,x,1,+,a,12,x,2,+,.,+a,1,n,x,n,=,b,1,a,21,x,1,+,a,22,x,2,+,.,+a,2,n,x,n,=,b,2,.,a,m1,x,1,+,a,m2,x,2,+,.,+a,mn,x,n,=,b,m,x,1,0,x,2,0,.,x,n,0.,一般来说,m.n,即:约束个数小于变量个数,单纯形法,由上章讨论可知,最优解里,x,1,x,2,x,3,x,n,中一般会有m个不为0(我们称为基变量,用,x,B,),其余n-m个必须为0(我们称其为非基变量,x,N,),将约束方程组系数矩阵A分为两块(B,N),其中B为基变量,x,B,系数子矩阵,为mXm方阵,N为非基变量,x,N,系数子矩阵,为mX(n-m)矩阵,单纯形法,我们希望找到最优的,x,B,即:确定,x,B,包含,x,1,x,2,x,3,x,n,中哪m个,(同时也确定,x,N,包含,x,1,x,2,x,n,中剩余的n-m个),然后令,x,N,=,0,在约束方程组中解出,x,B,可以枚举,最多有组合数,单纯形法,例红星重型机械厂的产品组合问题,的线性规划问题引入松弛变量化为如下标准形式：,单纯形法,故约束系数矩阵,单纯形法,由于,P,3,P,4,P,5,线性无关,故,B,0,是线性规划的一个基。

对于基,B,0,，,x,3,x,4,x,5,是基变量，,x,1,x,2,是非基变量单纯形法,由于P,2,P,3,P,4,线性无关,也是线性规划的一个基对于基基,B1,，,x,2,x,3,x,4,是基变量，,x,1,x,5,是非基变量,单纯形法,因此，约束方程组,变为,单纯形法,由于B可逆，将 左乘以上式的两边得:,令,x,N,=,0,，则,此时约束方程组有一个特殊形式的解,称为线性规划的,基本解,单纯形法,下面我们给出例2中基阵、基本解、基本可行解以及可行区域顶点之间的对应关系,基阵(,P,3,P,4,P,5,）基本可行解,x,3,=6,x,4,=8,x,5,=18,x,1,=,x,2,=,0,对应可行区域顶点O(0,0),基阵（,P,2,P,3,P,5,）基本可行解(0,4,6,0,6)对应可行区域顶点E(0,4),基阵（,P,1,P,2,P,4,）基本可行解(6,2,0,4,0)对应可行区域顶点B(6,2),基阵（,P,1,P,3,P,4,）,基本解(9,0,-3,8,0)对应顶点A(9,0),.,另外，A的另外两个m=3阶子矩阵（P,2,P,4,P,5,）和（P,1,P,3,P,5,）不可逆，不能构成基阵.,单纯形法,事实上，对于一般的线性规划问题（m个约束，n个决策变量）有类似的特性：,每个基本可行解对应于可行域的顶点。

可行域中相邻的两个顶点对应基阵中只有一个基向量不同，其余的个基向量相同由于线性规划的最优解是在可行域的顶点获得，由顶点与基可行解的对应关系，我们有以下线性规划的基本定理：,线性规划问题如果存在最优解，则一定存在一个基本可行解是最优解单纯形法,单纯形法一般从可行域一个顶点（通常是原点）出发，试图在其相邻的可行域顶点中找目标函数值更好的顶点，若在某顶点的相邻的顶点中找不出使目标函数有改进的顶点，则现有顶点就是最优解单纯形法,新的基阵变为B=（,P,1 ,P,2 ,P,4,），,x,B,=(,x,1,x,2,x,4,）为基变量,x,3,x,5,将看作自由变量，用高斯消元法将原约束方程组写为:,单纯形法,将上式代入Z=4,x,1,+3,x,2,中得:,Z=30-2,x,3,x,5,令,x,N,=(,x,3,x,5,)=,0,得基本可行解X=(6,2,0,4,0),Z=30,由于非基变量在目标函数中系数均为小于等于零，故X=(6,2,0,4,0)是线性规划问题最优解,.,线性规划应用,线性规划在很多领域都有应用,除经典应用模型外,一些较为复杂应用案例来进一步说明线性规划建模技术与用Excel求解方法.,混合问题,在生产安排问题中,管理层有时必须决定怎么混合两类以上的资源来生产多种产品,最终产品中包含资源中一种以上的基本成份,而且成品包含一定比例的各类资源;因此,管理层要决定每类资源的采购量,使得在成本最低的条件下满足产品规格以及生产该产品的需求:这类问题通常称之为混合问题,广泛应用于石油、化工和食品等行业.,巨斯特石油公司混合问题,巨斯特石油公司要生产两种汽油产品,一种是一般的汽油,另一种是特殊的汽油,公司炼油厂希望通过合成4类石油成份来生产这两种汽油产品;这些汽油的售价不同,4种石油成份成本也不同;公司希望确定一种混合这4类石油成份以生产两种汽油产品的方案来获取最大的利润.,巨斯特石油公司混合问题,这类混合问题是要决定一般汽油和特殊汽油的每类石油成份的用量分别是多少.明显是与定量因素有关的决策问题;希望通过调研收集如下相关数据:,(1)每类石油成份单位成本及供应量;,(2)每种汽油产品售价以及对各类石油成份的要求;,巨斯特石油公司混合问题,我们建立此问题的线性规划模型。

由于此问题是决定两个汽油产品中每个汽油产品中各类成分的含量，我们引入决策变量,xij,（,i,=1，2，3，4；,j,=1，2）表示第,j,种汽油产品中成份,i,的含量（这里，,j,=1，2分别表示 般汽油产品和特殊汽油产品）,具体模型与求解见P76,劳动力分配问题,劳动力分配问题属于资源分配问题，在求得最优方案后发现某些资源相对过剩，而有些资源又相对紧缺；假设在一些条件下，不同种类资源量在一定条件下可以置换或可以共享；我们可以把相对过剩的资源“置换”成相对紧缺的资源以达到扩大生产规模增加利润的目的具体案例如美克制造公司的劳动力分配问题,线性规划在不同领域的应用,线性规划在很多领域都有应用,除前面的经典应用模型外,本章继续举例研究一些较为复杂应用案例:,如航线安排问题P80,水力发电问题P82,用来进一步说明线性规划建模技术与用Excel求解方法.这里不再一一列举.,。