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种种营营养养成成分分的的量量为为aij，每每单单位位第第j种种配配料料的的价价格格为为cj。现现在在的的问问题题是是在在保保证证营营养养的的条条件件下下，如如何何配配方方使使混混合饲料的费用最小？合饲料的费用最小？数数学学模模型型以以xj表示一份混合饲料中第表示一份混合饲料中第j种配料的含量种配料的含量 ,则则2 线性规划的标准形式线性规划的标准形式目标函数目标函数约束条件约束条件一般形式一般形式矩阵形式矩阵形式 标准形式标准形式化一般形式为标准形式化一般形式为标准形式目标函数的转化目标函数的转化约束条件的转化约束条件的转化变量的非负约束的转化变量的非负约束的转化xy03 线性规划的一般理论线性规划的一般理论 线性规划的图解法线性规划的图解法可行域ABCD最优解最优解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，而两个基本可行解有，而两个基本可行解有m1个相同的基本变量，则称它个相同的基本变量，则称它们所代表的顶点是相邻的。们所代表的顶点是相邻的。 （1）标准线性规划问题的可行域（若存在可行域）是一）标准线性规划问题的可行域（若存在可行域）是一个闭凸集（凸多面体），这一点容易从闭凸集和约束的线个闭凸集（凸多面体），这一点容易从闭凸集和约束的线性性得到。性性得到。（2）如果可行解集是非空和有界的，那么目标函数的极）如果可行解集是非空和有界的，那么目标函数的极值一定在可行解集的一个顶点处取得。值一定在可行解集的一个顶点处取得。（3）如果可行域是无界的，那么目标函数可能无极值，）如果可行域是无界的，那么目标函数可能无极值，也可能有极值。如果有极值，这一极值一定在可行域的一也可能有极值。如果有极值，这一极值一定在可行域的一个顶点处取得。个顶点处取得。 （4）基本可行解对应可行域的顶点。）基本可行解对应可行域的顶点。 穷举穷举法：法： 求出全部顶点处函数值（至多求出全部顶点处函数值（至多 ），再进行比较），再进行比较可行域可行域 4 单纯形法单纯形法 单纯形法的基本思想：单纯形法的基本思想： 从从可可行行域域的的一一个个顶顶点点出出发发，转转移移到到与与它它相相邻邻的的另另一一个个顶顶点点，使使目目标标函函数数值值下下降降，不不断断重重复复这一步骤，最终可得到最优解。这一步骤，最终可得到最优解。 需要解决以下几个问题：需要解决以下几个问题： （1）转移规则）转移规则 （2）如何判断一个顶点是否是最优解）如何判断一个顶点是否是最优解判别准则。判别准则。 （3） 如何寻找初始顶点。如何寻找初始顶点。 （4） 计算最优解和最优值。计算最优解和最优值。 在基本变量中找出一个变量（离基变量），在基本变量中找出一个变量（离基变量）， 使之变为非基本变量。使之变为非基本变量。从非基本变量中选取一个变量，代替离基变量，使之成为基本变量，从非基本变量中选取一个变量，代替离基变量，使之成为基本变量，我们称为进基变量。我们称为进基变量。 在基本可行解在基本可行解 处的函数值为处的函数值为在一般可行解处的函数值为在一般可行解处的函数值为当且仅当当且仅当 时目标函数减少，即时目标函数减少，即 中至少有一个分量小于零中至少有一个分量小于零 rj称为检验数称为检验数(1)进基变量的选进基变量的选择择 则取则取xk为进基变量（或为进基变量（或ak为进基向量）为进基向量）(2)离基变量的选离基变量的选择择 设设xr为离基变量为离基变量基变量基变量非基变量非基变量基可行解基可行解离基变量离基变量进基变量进基变量主元素主元素 转换公式转换公式 离基变量的选择离基变量的选择 xr为离基变量为离基变量 对于某个基本可行解，若所有的检验数对于某个基本可行解，若所有的检验数 则此基本可行解为最优解。则此基本可行解为最优解。 寻找初始基本可行解的方法有：（寻找初始基本可行解的方法有：（a）大）大M法，（法，（b）二阶）二阶段法。这里仅介绍二阶段法。段法。这里仅介绍二阶段法。 构造辅构造辅助线性助线性规划：规划： 若问题（若问题（LP1）的最优基本可行解为）的最优基本可行解为 ，则，则 为原问为原问题的一个基本可行解；题的一个基本可行解； 若问题（若问题（LP1）的最优基本可行解为）的最优基本可行解为 且且 ，则原问题无可行解。则原问题无可行解。 检验数检验数 b基本变量基本变量（1）把一般线性规划问题转化为标准型；）把一般线性规划问题转化为标准型； （2）建立初始单纯形表；）建立初始单纯形表； （3）若所有检验数）若所有检验数 ，就得到一个最优解；，就得到一个最优解； （4）若对某个）若对某个j有有 ，取，取 ，对应，对应的的 为进基变量。为进基变量。（6）以）以 为主元素，进行一次为主元素，进行一次Gauss消元，得到一个新消元，得到一个新的基本可行解。返回（的基本可行解。返回（3）。）。 检验向量检验向量 单纯形法的矩阵形式单纯形法的矩阵形式 例例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结果：结果： 0化为标准形化为标准形 引入人工变量引入人工变量 考虑辅助问题考虑辅助问题 cZ410000CW000011CBxBbx1x2x3x4x5x6110x5x6x4364341132010001100010cjzj410000cjwj741000cZ410000CW000011CBxBbx1x2x3x4x5x6010x1x6x41231001/35/35/30100011/34/31/3010cjzj01/3004/30cjwj05/3107/30cZ410000CW000011CBxBbx1x2x3x4x5x6000x1x2x43/56/511000101/53/510013/54/511/53/51cjzj001/508/51/5cjwj000011cZ4100CBxBbx1x2x3x4410x1x2x43/56/511000101/53/51001cjzj001/50cZ4100CBxBbx1x2x3x4410x1x2x32/59/511000100011/53/51cjzj0001/5最优解：最优解：x1=2/5, x2=9/5, x3=1, x4=0最优化：最优化：作业（食谱问题）作业（食谱问题） 某公司饲养实验用的动物一供出售。已知这些动物的某公司饲养实验用的动物一供出售。已知这些动物的生长对饲料中三种营养成分：蛋白质、矿物质、维生素特生长对饲料中三种营养成分：蛋白质、矿物质、维生素特别敏感，每个动物每天至少需要蛋白质别敏感，每个动物每天至少需要蛋白质70g，矿物质，矿物质3g,维维生素生素10g,该公司能买到该公司能买到5种不同的饲料，每种饲料种不同的饲料，每种饲料1 kg所含所含的营养成分及成本如表：的营养成分及成本如表：饲料饲料蛋白质（蛋白质（g）矿物质（矿物质（g）维生素（维生素（g）A10.300.100.05A22.000.050.10A31.000.020.02A40.600.200.20A51.800.050.08饲料饲料蛋白质（蛋白质（g）矿物质（矿物质（g）维生素（维生素（g）A10.300.100.05A22.000.050.10A31.000.020.02A40.600.200.20A51.800.050.08饲料饲料A1A2A3A4A5成本（元）成本（元）0.20.70.40.30.5 五种饲料单位重量（五种饲料单位重量（1kg）成本）成本