《第七章线性规划模型课件》由会员分享，可在线阅读，更多相关《第七章线性规划模型课件（31页珍藏版）》请在金锄头文库上搜索。
1、线性规划模型,第七章,1 线性规划问题,例1. 运输问题,要把某种货物从m个 工厂 A1,A2, ,Am 运到n个商店 B1,B2, ,Bn去，其中各工厂的库存量为a1,a2, , am，各商店的需求量为b1,b2, ,bn ，这里 。已知从工厂Ai到商店Bj的运费（每一单位货物）Cij。现在要确定一个运输方案，即确定从Ai到Bj的运量xij(i=1,2, ,m，j=1,2, ,n), 使在满足供求的条件下总的运费最小。,数 学 模 型,例2营养问题,某饲养场所用的混合饲料由n种配料组成，要求这种混合饲料必须含m种不同营养成分，并且每一份混合饲料中第i种营养成分的含量不低于bi，已知每单位第j
2、种配料中所含第i种营养成分的量为aij，每单位第j种配料的价格为cj。现在的问题是在保证营养的条件下，如何配方使混合饲料的费用最小？,数 学 模 型,以xj表示一份混合饲料中第j种配料的含量 ,则,2 线性规划的标准形式,目标函数,约束条件,一般形式,矩阵形式,标准形式,化一般形式为标准形式,目标函数的转化,约束条件的转化,变量的非负约束的转化,3 线性规划的一般理论,线性规划的图解法,可行域,最优解B(x1,x2),可行解,一个向量x=(x1,x2, ,xn)如果满足所有的约束条件，则称之为线性规划的一个可行解。,全部可行解所构成的集合称为可行解集,使目标函数达到极小的可行解称为最优解。,可
3、行域,最优解,线性规划可能发生的三种情况,（1）约束条件彼此不相容，可行解集是空的，因而（LP）问题无解；,（2）可行域是无界的，而且随着x趋向无穷，目标函数取任意小的值，此时不存在有限的最优解；,（3）至少存在一个最优解。以后仅研究情况（3）,上例中可行域与最优解的特点：,可行域是凸多边形（凸多胞形）,最优解是凸多边形的一个顶点,1凸集,定义1 设S是Rn中的一个向量集，若对任意 及 任意 ，有 则称S是一个凸集。,定义2 若S是一个凸集， ，但对任意 ，均有 ，则称z是凸集S的一个顶点。,容易证明，线性规划问题（LP）的可行域是一个凸集,2基本可行解,2基本可行解,把 看作一组自由变量,任
4、意一组值 ，则可得到对应的 的一组值，于是 便是约束方程 的一个解 。令 =0，则 ，我们把约束方程这种特殊形式的解 称为基本解。,定义3 设B是矩阵A中的一个m阶满秩方阵，则称B为一个基；B中的m个线性无关的列向量称为基向量；x中与之对应的m个分量称为基本变量，其余变量称为非基本变量；令所有的非基本变量取值为零，得到的解称为对应于B的基本解。,定义4 如果一个基本解满足非负条件 ，即它也是可行的，则称为基本可行解，对应的基B称为可行基。,3基本性质（几个结论）,定义5 如果一个线性规划问题（LP）的基本变量数是m，而两个基本可行解有m1个相同的基本变量，则称它们所代表的顶点是相邻的。,（1）
5、标准线性规划问题的可行域（若存在可行域）是一个闭凸集（凸多面体），这一点容易从闭凸集和约束的线性性得到。,（2）如果可行解集是非空和有界的，那么目标函数的极值一定在可行解集的一个顶点处取得。,（3）如果可行域是无界的，那么目标函数可能无极值，也可能有极值。如果有极值，这一极值一定在可行域的一个顶点处取得。,（4）基本可行解对应可行域的顶点。,穷举法：,求出全部顶点处函数值（至多 ），再进行比较,4 单纯形法,单纯形法的基本思想：,从可行域的一个顶点出发，转移到与它相邻的另一个顶点，使目标函数值下降，不断重复这一步骤，最终可得到最优解。,需要解决以下几个问题：,（1）转移规则,（2）如何判断一个
6、顶点是否是最优解判别准则。,（3） 如何寻找初始顶点。,（4） 计算最优解和最优值。,1.转移规则,在基本变量中找出一个变量（离基变量）， 使之变为非基本变量。,从非基本变量中选取一个变量，代替离基变量，使之成为基本变量，我们称为进基变量。,在基本可行解 处的函数值为,在一般可行解处的函数值为,当且仅当 时目标函数减少，即,中至少有一个分量小于零,rj称为检验数,(1)进基变量的选择,则取xk为进基变量（或ak为进基向量）,(2)离基变量的选择,设xr为离基变量,基变量,非基变量,基可行解,离基变量,进基变量,主元素,转换公式,离基变量的选择,xr为离基变量,2.最优解的判定,对于某个基本可行
7、解，若所有的检验数 则此基本可行解为最优解。,3.初始基本可行解的寻找方法,寻找初始基本可行解的方法有：（a）大M法，（b）二阶段法。这里仅介绍二阶段法。,构造辅助线性规划：,若问题（LP1）的最优基本可行解为 ，则 为原问题的一个基本可行解；,若问题（LP1）的最优基本可行解为 且 ，则原问题无可行解。,4.单纯形表,5.单纯形法的计算步骤,（1）把一般线性规划问题转化为标准型；,（2）建立初始单纯形表；,（3）若所有检验数 ，就得到一个最优解；,（4）若对某个j有 ，取 ，对应 的 为进基变量。,（6）以 为主元素，进行一次Gauss消元，得到一个新的基本可行解。返回（3）。,6.单纯形法
8、的矩阵形式,检验向量,单纯形法的矩阵形式,7.应用举例,例3一家具公司生产桌子和椅子，用于生产的全部劳动力共计450个工时。原料是400个单位的木材。每张桌子要使用15个工时的劳动力，20个单位的木材，售价为80元。每张椅子要使用10个工时，5个单位木材，售价45元。问为达到最大收益应怎样安排生产？,解 设 分别表示应生产的桌子和椅子数，则,X1为进基变量，x3为离基变量,X2为进基变量,x4为离基变量,最优解,X1=14 , x2=24,最优解值,W=2200,用两阶段法求解线性规划,输入： ne=3 c=4,1,0,0 A=3,1,0,0;4,3,-1,0;1,2,0,1 b=3,6,4 v1=0,0,0,0 x=lp(c,A,b,v1,ne) z=c*x,结果： x = 0.4000 1.8000 1.0000 0 z = 3.4000,化为标准形,引入人工变量,考虑辅助问题,最优解： x1=2/5, x2=9/5, x3=1, x4=0 最优化： Z*=3.4,作业（食谱问题）,某公司饲养实验用的动物一供出售。已知这些动物的生长对饲料中三种营养成分：蛋白质、矿物质、维生素特别敏感，每个动物每天至少需要蛋白质70g，矿物质3g,维生素10g,该公司能买到5种不同的饲料，每种饲料1 kg所含的营养成分及成本如表：,五种饲料单位重量（1kg）成本,
