资源描述：
《《线性规划模型》课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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种配料中所含第i种营养成分的量为
2、aij，每单位第j种配料的价格为cj。现在的问题是在保证营养的条件下，如何配方使混合饲料的费用最小？数学模型以xj表示一份混合饲料中第j种配料的含量,则§2线性规划的标准形式目标函数约束条件一般形式矩阵形式标准形式化一般形式为标准形式目标函数的转化约束条件的转化变量的非负约束的转化xy0§3线性规划的一般理论线性规划的图解法可行域ABCD最优解B(x1,x2)可行解一个向量x=(x1,x2,…,xn)如果满足所有的约束条件，则称之为线性规划的一个可行解。全部可行解所构成的集合称为可行解集使目标函数达到极小的可行解称为最优解。可行域最优解线性规划可能发生的三种情况（1）约束条件彼此不相容，可
3、行解集是空的，因而（LP）问题无解；（2）可行域是无界的，而且随着x趋向无穷，目标函数取任意小的值，此时不存在有限的最优解；（3）至少存在一个最优解。以后仅研究情况（3）上例中可行域与最优解的特点：可行域是凸多边形（凸多胞形）最优解是凸多边形的一个顶点1．凸集定义1设S是Rn中的一个向量集，若对任意及任意，有则称S是一个凸集。定义2若S是一个凸集，，但对任意，均有，则称z是凸集S的一个顶点。容易证明，线性规划问题（LP）的可行域是一个凸集2．基本可行解2．基本可行解把看作一组自由变量,任意一组值，则可得到对应的的一组值，于是便是约束方程的一个解。令=0，则，我们把约束方程这种特殊形式的解称
4、为基本解。定义3设B是矩阵A中的一个m阶满秩方阵，则称B为一个基；B中的m个线性无关的列向量称为基向量；x中与之对应的m个分量称为基本变量，其余变量称为非基本变量；令所有的非基本变量取值为零，得到的解称为对应于B的基本解。定义4如果一个基本解满足非负条件，即它也是可行的，则称为基本可行解，对应的基B称为可行基。3．基本性质（几个结论）定义5如果一个线性规划问题（LP）的基本变量数是m，而两个基本可行解有m－1个相同的基本变量，则称它们所代表的顶点是相邻的。（1）标准线性规划问题的可行域（若存在可行域）是一个闭凸集（凸多面体），这一点容易从闭凸集和约束的线性性得到。（2）如果可行解集是非空和
5、有界的，那么目标函数的极值一定在可行解集的一个顶点处取得。（3）如果可行域是无界的，那么目标函数可能无极值，也可能有极值。如果有极值，这一极值一定在可行域的一个顶点处取得。（4）基本可行解对应可行域的顶点。穷举法：求出全部顶点处函数值（至多），再进行比较可行域§4单纯形法单纯形法的基本思想：从可行域的一个顶点出发，转移到与它相邻的另一个顶点，使目标函数值下降，不断重复这一步骤，最终可得到最优解。需要解决以下几个问题：（1）转移规则（2）如何判断一个顶点是否是最优解——判别准则。（3）如何寻找初始顶点。（4）计算最优解和最优值。1.转移规则在基本变量中找出一个变量（离基变量），使之变为非基本
6、变量。从非基本变量中选取一个变量，代替离基变量，使之成为基本变量，我们称为进基变量。在基本可行解处的函数值为在一般可行解处的函数值为当且仅当时目标函数减少，即中至少有一个分量小于零rj称为检验数(1)进基变量的选择则取xk为进基变量（或ak为进基向量）(2)离基变量的选择设xr为离基变量基变量非基变量基可行解离基变量进基变量主元素转换公式离基变量的选择xr为离基变量2.最优解的判定对于某个基本可行解，若所有的检验数则此基本可行解为最优解。3.初始基本可行解的寻找方法寻找初始基本可行解的方法有：（a）大M法，（b）二阶段法。这里仅介绍二阶段法。构造辅助线性规划：若问题（LP1）的最优基本可行
7、解为，则为原问题的一个基本可行解；若问题（LP1）的最优基本可行解为且，则原问题无可行解。4.单纯形表检验数b基本变量5.单纯形法的计算步骤（1）把一般线性规划问题转化为标准型；（2）建立初始单纯形表；（3）若所有检验数，就得到一个最优解；（4）若对某个j有，取，对应的为进基变量。（6）以为主元素，进行一次Gauss消元，得到一个新的基本可行解。返回（3）。6.单纯形法的矩阵形式检验向量单纯形法的矩阵形式7.应用举例例3
