求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目 标函数的要求从可行域中找出最优解。 由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。 几个概念： 若x*满足约束条件，则称之为LP问题的可行解 所有可行解的集合称为可行域， 使目标函数达到最优值的可行解称为最优解。 对给定的LP问题，若存在最优解，则称该LP问题有解，否则称LP问题无解。 (二)图解法的步骤： 1建立平面直角坐标系， 标出坐标原点坐标轴的指向和单位长度」 2对约束条件加以图解，找出可行域。 3.画出目标函数等值线。 4.结合目标函数的要求求出最优解。 一般地，将目标函数直线放在可行域中；求最大值时直线沿着矢量方向移动，求最小值时沿着矢量 的反方向移动 具体例题见PPT第一章第39-44页。 图解法学习要点： 1通过图解法了解线性规划有几种解的形式。 2.作图的关键有三点： (1)可行解区域要画正确： (2)目标函数增加的方向不能画错： (3)目标函数的直线怎样平行移动 1.3线性规划的有关概念 （一）线性规划常用的概念 凸集：凸集(Convex set)设K是n维空间的一个点集，对任意两点，时，则称K为凸集。 凸组合：凸组合(Convex combination)设是Rn中的点，若存在，使得成立，则称x为 的凸组合。 极点(Extreme point):设K是凸集，，若X不能用K中两个不同的点的凸组合表示为X=X(1)+(1-)X(2) (0<1),则称X是K的一个极点或顶点。 X是凸集K的极点是指X不可能是K中某一线段的内点，只能是K中某一线段的端点。 可行解：变量满足所有约束条件的一组值。 可行解集：所有可行解构成的集合。 可行域：可行解集构成n维空间的区域. 最优解：使得目标函数达到最优的可行解。 最优值：最优解对应的目标函数值 目的：求最优解和最优值」 求解方法：单纯形法 (仁)线性规划的基本定理 定理1.1若线性规划可行解K非空，则K是凸集 定理1.2线性规划的可行解集合K的点X是极点的充要条件为X是基本可行解
求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目 标函数的要求从可行域中找出最优解。 由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。 几个概念： 若x*满足约束条件，则称之为LP问题的可行解。 所有可行解的集合称为可行域。 使目标函数达到最优值的可行解称为最优解。 对给定的LP问题，若存在最优解，则称该LP问题有解，否则称LP问题无解。 （二）图解法的步骤： 1.建立平面直角坐标系，标出坐标原点, 坐标轴的指向和单位长度。 2.对约束条件加以图解，找出可行域。 3.画出目标函数等值线。 4.结合目标函数的要求求出最优解。 一般地，将目标函数直线放在可行域中； 求最大值时直线沿着矢量方向移动， 求最小值时沿着矢量 的反方向移动。 具体例题见PPT第一章第39-44页。 图解法学习要点： 1.通过图解法了解线性规划有几种解的形式。 2.作图的关键有三点： (1)可行解区域要画正确； (2)目标函数增加的方向不能画错； (3)目标函数的直线怎样平行移动。 1.3 线性规划的有关概念 （一） 线性规划常用的概念 凸集：凸集(Convex set)设K是n维空间的一个点集，对任意两点 ， 时，则称K为凸集。 凸组合：凸组合(Convex combination) 设 是Rn 中的点，若存在，使得成立，则称X为 的凸组合。 极点(Extreme point) ：设K是凸集，，若X不能用K中两个不同的点 的凸组合表示为 X=X(1)+(1-)X(2) (0<<1)，则称X是K的一个极点或顶点。 X是凸集K的极点是指X不可能是K中某一线段的内点，只能是K中某一线段的端点。 可行解：变量满足所有约束条件的一组值。 可行解集：所有可行解构成的集合。 可行域： 可行解集构成n维空间的区域。 最优解：使得目标函数达到最优的可行解。 最优值：最优解对应的目标函数值。 目的：求最优解和最优值。 求解方法：单纯形法 （二）线性规划的基本定理 定理1.1 若线性规划可行解K非空,则K是凸集。 定理1.2 线性规划的可行解集合K的点X是极点的充要条件为X是基本可行解
定理1.3若线性规划有最优解，则最优值一定可以在可行解集合的某个极点上到达，最优解就是极点的 坐标向量。 定理1.2刻划了可行解集的极点与基本可行解的对应关系，极点是基本可行解，反之，基本可行解 定是极点，但它们并非 一对应，有可能辆个或几个基本可行解对应于同一极点（退化基本可行解 时)。 定理1.3描述了最优解在可行解集中的位置，若最优解唯一，则最优解只能在某一极点上达到，若具 有多重最优解，则最优解是某些极点的凸组合，从而最优解是可行解集的极点或界点，不可能是可 行解集的内点 若线性规划的可行解集非空且有界，则一定有最优解；若可行解集无界，则线性规划可能有最优 解，也可能没有最优解。 定理1.2及1.3还给了我们一个启示，寻求最优解不是在无限个可行解中去找，而是在有限个基本可行 解中去寻求。 1.4用EXCEL SOLVER求解线性规划问题 单纯形计算方法(Simplex Method)是先求出一个初始基可行解并判断它是否最优，若不是最优，再换 一个基可行解并判断，直到得出最优解或无最优解。它是一种逐步逼近最优解的迭代方法。 当系数矩阵A中可以观察得到一个可行基时（通常是一个单位矩阵或m个线性无关的单位向量组成的 矩阵)，可以通过解线性方程组求得基本可行解。 由于课时所限，本课程主要讲授如何应用EXCEL求解线性规划模型，所以不再详细讲解单纯形法。 问题定义： (1)输入问题的各种参数（数据单元格） (2)定义问题的决策变量（可变单元格）： (3)求出问题在相应决策下的目标函数值（目标单元格）： 优化求解： (1)启动Excel Solver, (2)指定目标函数； (3)指定决策变量 (4)指定约束； (5)求解。 Excel的使用要点： (1)变量、参数与矩阵的命名、相应的单元格布置： (2)常用函数 SUMPRODUCT(X1,X2):X1、X2可以是向量或矩阵（包含的分量的数量相等）；含义：对应 分量相乘后求和，即X1的某分量与X2的对应分量相乘，所有的对应分量相乘后，再进行求和。 第2章线性规划的对偶理论与灵敏度分析 2.1对偶问题的提出 对偶问题概念 任何一个线性规划问题都有一个伴生的线性规划问题，称为其"对偶"问题。 对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密 切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解， 反之亦然。 对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内 容之一
定理1.3 若线性规划有最优解,则最优值一定可以在可行解集合的某个极点上到达,最优解就是极点的 坐标向量。 定理1.2刻划了可行解集的极点与基本可行解的对应关系，极点是基本可行解，反之，基本可行解一 定是极点，但它们并非一一对应，有可能两个或几个基本可行解对应于同一极点（退化基本可行解 时）。 定理1.3描述了最优解在可行解集中的位置，若最优解唯一，则最优解只能在某一极点上达到，若具 有多重最优解，则最优解是某些极点的凸组合，从而最优解是可行解集的极点或界点，不可能是可 行解集的内点 。 若线性规划的可行解集非空且有界，则一定有最优解；若可行解集无界，则线性规划可能有最优 解，也可能没有最优解。 定理1.2及1.3还给了我们一个启示，寻求最优解不是在无限个可行解中去找，而是在有限个基本可行 解中去寻求。 1.4 用EXCEL SOLVER求解线性规划问题 单纯形计算方法(Simplex Method)是先求出一个初始基可行解并判断它是否最优，若不是最优，再换 一个基可行解并判断，直到得出最优解或无最优解。它是一种逐步逼近最优解的迭代方法。 当系数矩阵A中可以观察得到一个可行基时（通常是一个单位矩阵或m个线性无关的单位向量组成的 矩阵），可以通过解线性方程组求得基本可行解。 由于课时所限，本课程主要讲授如何应用EXCEL求解线性规划模型，所以不再详细讲解单纯形法。 问题定义： （1）输入问题的各种参数（数据单元格）； （2）定义问题的决策变量（可变单元格）； （3）求出问题在相应决策下的目标函数值（目标单元格）； 优化求解： （1）启动Excel Solver； （2）指定目标函数； （3）指定决策变量； （4）指定约束； （5）求解。 Excel的使用要点： （1）变量、参数与矩阵的命名、相应的单元格布置； （2）常用函数 SUMPRODUCT（X1，X2）： X1、X2可以是向量或矩阵（包含的分量的数量相等）；含义：对应 分量相乘后求和，即X1的某分量与X2的对应分量相乘，所有的对应分量相乘后，再进行求和。 第2章 线性规划的对偶理论与灵敏度分析 2.1 对偶问题的提出 对偶问题概念： 任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。 对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密 切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解， 反之亦然。 对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内 容之一
例2-1引用第1章中例1-1的数据，如下表所示 项目 每天可用能幼 设备A(h) 0515 设备Bh) 6224 测试工序h)115 利润 21 其线性规划问题为： (P) 假定有某个公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃 生产活动，出让自己的资源？ 条件：出让代价应不低于用同等数量资源由自己组织生产活动时获取的赢利。 设y1,y2,y3分别代表单位时间(h)设备A、设备B和调试工序的出让代价。y1,y2,y3的取值应满 足 6y2+y32 5y1+2y2+y31 该公司希望用最小代价把美佳公司的全部资源收买过来，即： 其中第一个不等式表示美佳公司用6设备B和1h调试可生产一件家电1，赢利2元；第二个不等式表示 用5h设备A,2h设备B及1h调试可生产一件家电I,赢利1元. (D) (P)和(D)两个线性规划问题，通常称P为原问题，D为前者的对偶问题。 对偶模型的一般式见第2章PPT第4-7页。 原模型P和对偶模型D既有联系又有区别。联系在于，它们都是关于电器厂生产经营的模型，并且使 用相同的数据；区别在于，它们所反映的实质内容是完全不同的：P是站在电器厂经营者的立场上追 求电器厂的销售收入最大：而D则是站在电器厂谈判对手的立场上寻求应付电器厂租金最少的策略。 任何线性规划问题都有对偶问题，而且都有相应的经济意义。由以上不难得到，所谓对偶规划，就 是与性期别原问相取对应并使甲后 组数据按照特定方法形成的另 种反映不同性质问题的线性 规划模型。 2.2线性规划的对偶理论 线性规划的对偶理论包括四个基本定理。 定理1对称性定理：对偶问题的对偶是原问题。 定理2弱对偶原理（弱对偶性）：设和分别是问题(P)和(D)的可行解，则必有， 推论)若和分别是问题(P)和(D)的可行解，则C是(D)的目标函数最小值的一个下界；b是 (P)的目标函数最大值的 个上界。 这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值 的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值 推论(2)在一对对偶问题(P)和(D)中，若其中一个问题可行但目标函数无界，则另一个问题不可 行；反之不成立。这也是对偶问题的无界性 关于无界性有如下结论： 推论)在一对对偶问题(P)和(D)中，若一个可行（如P),而另一个不可行，（如D),则该 可行的问题无界。 定理3最优性判别定理 若X*和Y分别是P和D的可行解且CX*=Yb,则X*、Y*分别是问题P和D的最优解
例2-1 引用第1章中例1-1的数据，如下表所示： 项目 I II 每天可用能力 设备A(h) 设备B(h) 测试工序(h) 0 6 1 5 2 1 15 24 5 利润 2 1 其线性规划问题为： (P) 假定有某个公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃 生产活动，出让自己的资源？ 条件：出让代价应不低于用同等数量资源由自己组织生产活动时获取的赢利。 假设y1,y2,y3分别代表单位时间（h）设备A、设备B和调试工序的出让代价。 y1,y2,y3的取值应满 足： 6y2+y32 5y1+2y2+y31 该公司希望用最小代价把美佳公司的全部资源收买过来，即： 其中第一个不等式表示美佳公司用6h设备B和1h调试可生产一件家电I,赢利2元；第二个不等式表示 用5h设备A,2h设备B及1h调试可生产一件家电Ⅱ，赢利1元。 （D） （P）和（D）两个线性规划问题，通常称P为原问题，D为前者的对偶问题。 对偶模型的一般式见第2章PPT第4-7页。 原模型P和对偶模型D既有联系又有区别。联系在于，它们都是关于电器厂生产经营的模型，并且使 用相同的数据；区别在于，它们所反映的实质内容是完全不同的：P是站在电器厂经营者的立场上追 求电器厂的销售收入最大;而D则是站在电器厂谈判对手的立场上寻求应付电器厂租金最少的策略。 任何线性规划问题都有对偶问题，而且都有相应的经济意义。由以上不难得到，所谓对偶规划，就 是与线性规划原问题相对应并使用同一组数据按照特定方法形成的另一种反映不同性质问题的线性 规划模型。 2.2 线性规划的对偶理论 线性规划的对偶理论包括四个基本定理。 定理1 对称性定理：对偶问题的对偶是原问题。 定理2 弱对偶原理（弱对偶性）：设和 分别是问题（P）和（D）的可行解，则必有。 推论⑴ 若和分别是问题（P）和（D）的可行解，则C是（D）的目标函数最小值的一个下界；b 是 （P）的目标函数最大值的一个上界。 这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值 的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。 推论⑵ 在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可 行；反之不成立。这也是对偶问题的无界性。 关于无界性有如下结论： 推论⑶ 在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行，（如D），则该 可行的问题无界。 定理3 最优性判别定理： 若 X* 和 Y* 分别是 P 和 D 的可行解且 CX* = Y* b，则X* 、Y*分别是问题 P和D 的最优解
定理4对偶定理（强对偶性）： 若一对对偶问题P和D都有可行解，则它们都有最优解，且目标函数的最优值必相等。 推论（网若P和D的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等 综上所述，一对对偶问题的关系，只能有下面三种情况之一出现： ①都有最优解，分别设为X*和Y,则必有CX=Yb; ② 一个问题无界，则另一个问题无可行解 ③两个都无可行解。 定理5互补松弛定理 设X*和Y*分别是问题P和D的可行解，则它们分别是最优解的充要条件是 同时成立，其中XS,YS为剩余变量。 受时肉阳 ,若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是 2.3对偶问项的经烹解强 影子价格 定义：在一对P和D中，若P的某个约束条件的右端项常数b增加一个单位时，所引起的目标函数 最优值Z*的改变量y1称为第1个约束条件的影子价格，又称为边际价格。 影子价格， ·是一个向量，它的分量表示最优目标值随相应资源数量变化的变化 率。 影子价格的经济含义 影子价格是对现有资源实现最大效益时的一种估价。企业可以根据现有资源的影子价格，对资源的 使用有两种考虑：第一，是否将设备用于外加工或租，若租费高于某设备的影 子价格 可考虑出 该设备，否则不 宜出租 是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的 影子价格，可考虑买进该设备，否则不宜买进。 (②)影子价格表明资源增加对总效益产生的影响， ,影子价格反映了不同的局部或个体的增量可以获 得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入 手。这样可以用较少的局部努力，获得较大的整体效益。 需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发 生变化。另外，影子价格的经济含义(2)，是指资源在一定范围内增加时的情况，当某种资源的增 加超过了这个”一定的范围时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问 题还将在灵敏度分析一节中讨论。 2.4灵敏度分析 灵敏度分析，是指对系统或事物因周围条件变化所表现出的敏感性程度的分析。 在前面讲的线性规划问题中， 但实际上这些参数 都是 些估计或预测的数字。 常都是假定间题中的a,b1,c系数是已知的常数， ,©值就会发生变化如果工艺技术条件 改变，则就会变化；如果资源的可用量发生变化，则bi也会发生变化。因此就必然会提出这样的问 题，即当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化，或者说，当这参数在 个多大的范围内变化时问题的最优解才会保持不变。这就是灵敏度分析所要研究解决的问题。 如果线性规划问题中的一个或几个参数变化时，完全可以用单纯形法从头计算，看最优解有无变 化，但这样做既麻烦又没有必要。因为由单纯形的迭代过程我们知道，线性规划的求解是从一组基 向最变换为另一组基向量，其中每步迭代得到的数字只随着基向量的不同选择而有所改变，因此完 全有可能把个别参数的变化直接在获得最优解的 单纯形表上反映出来。这样就不需 算，而只需对获得最优解的单纯形表进行审查，看一些数字变化后是否仍满足最优解的条件，如果 不满足的话，再从这个表开始进行迭代计算，求得最优解即可。这也就是灵敏度分析
定理4 对偶定理（强对偶性）： 若一对对偶问题 P 和 D 都有可行解，则它们都有最优解，且目标函数的最优值必相等。 推论⑷ 若 P 和 D 的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。 综上所述，一对对偶问题的关系，只能有下面三种情况之一出现： ① 都有最优解，分别设为X* 和 Y*，则必有CX* =Y*b； ② 一个问题无界，则另一个问题无可行解； ③ 两个都无可行解。 定理5 互补松弛定理： 设X*和Y*分别是问题 P 和 D 的可行解，则它们分别是最优解的充要条件是 同时成立，其中XS，YS为剩余变量。 一般而言，我们把某一可行点（如X*和Y* ）处的严格不等式约束（包括对变量的非负约束）称为松 约束，而把严格等式约束称为紧约束。所以有如下推论： 设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是 其对偶问题最优解的紧约束。 2.3 对偶问题的经济解释——影子价格 定义：在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi 增加一个单位时，所引起的目标函数 最优值Z* 的改变量y*i 称为第 i 个约束条件的影子价格，又称为边际价格。 影子价格 —— 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化 率。 影子价格的经济含义 影子价格是对现有资源实现最大效益时的一种估价。企业可以根据现有资源的影子价格，对资源的 使用有两种考虑：第一，是否将设备用于外加工或租，若租费高于某设备的影子价格，可考虑出租 该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的 影子价格，可考虑买进该设备，否则不宜买进。 （2） 影子价格表明资源增加对总效益产生的影响。影子价格反映了不同的局部或个体的增量可以获 得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入 手。这样可以用较少的局部努力，获得较大的整体效益。 需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发 生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增 加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问 题还将在灵敏度分析一节中讨论。 2.4 灵敏度分析 灵敏度分析，是指对系统或事物因周围条件变化所表现出的敏感性程度的分析。 在前面讲的线性规划问题中，通常都是假定问题中的aij,bi,cj系数是已知的常数，但实际上这些参数 都是一些估计或预测的数字。在现实中，如果市场条件变化，cj值就会发生变化；如果工艺技术条件 改变，则aij就会变化；如果资源的可用量发生变化，则bi也会发生变化。因此就必然会提出这样的问 题，即当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化，或者说，当这参数在 一个多大的范围内变化时问题的最优解才会保持不变。这就是灵敏度分析所要研究解决的问题。 如果线性规划问题中的一个或几个参数变化时，完全可以用单纯形法从头计算，看最优解有无变 化，但这样做既麻烦又没有必要。因为由单纯形的迭代过程我们知道，线性规划的求解是从一组基 向最变换为另一组基向量，其中每步迭代得到的数字只随着基向量的不同选择而有所改变，因此完 全有可能把个别参数的变化直接在获得最优解的最终单纯形表上反映出来。这样就不需要从头计 算，而只需对获得最优解的单纯形表进行审查，看一些数字变化后是否仍满足最优解的条件，如果 不满足的话，再从这个表开始进行迭代计算，求得最优解即可。这也就是灵敏度分析