第七章线性规划模型

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