1、运筹学期末总复习运筹学期末总复习第二章第二章 线性规划线性规划1、线性规划数学模型的标准形式：、线性规划数学模型的标准形式：),2,1(0),2,1(.max11njxmibxastxczjnjijijnjjj特点：特点：a、目标函数：目标函数：maxb、约束条件：等式约束条件：等式c、决策变量决策变量00d d、b bi i00线性规划数学模型的三个要素：线性规划数学模型的三个要素：决策变量、目标函数、约束条件决策变量、目标函数、约束条件2 2、线性规划问题解的四种情况、线性规划问题解的四种情况:唯一最优解唯一最优解 无穷多最优解无穷多最优解 无界解无界解 无解无解(无可行解无可行解)列出初
2、始单纯形表列出初始单纯形表寻找初始基可行解寻找初始基可行解计算计算，进行最优性检验，进行最优性检验所有所有00 是是否否存在非存在非基变量基变量检验数检验数=0=0 否否是是唯一最唯一最优解优解无穷多无穷多最优解最优解 是否有换出变量是否有换出变量 否否无无界界解解 寻找换入，换出变量寻找换入，换出变量 求新基可行解求新基可行解3 3、单纯形法计算步骤、单纯形法计算步骤存在人工存在人工变量变量0 0 否否是是无无解解 判断：1、图解法同单纯形法虽然求解的形式不同，、图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。但从几何上理解，两者是一致的。2、线性规划模型中增加一个约束条件
3、，可行、线性规划模型中增加一个约束条件，可行域范围一般将缩小，减少一个约束条件，域范围一般将缩小，减少一个约束条件，可行域范围一般将扩大。可行域范围一般将扩大。3、线性规划问题的每一个基解对应可行域的、线性规划问题的每一个基解对应可行域的一个顶点。一个顶点。4、线性规划问题的可行解如为最优解，则该、线性规划问题的可行解如为最优解，则该可行解一定是基可行解。可行解一定是基可行解。判断：5、线性规划可行域无界，则具有无界解。、线性规划可行域无界，则具有无界解。6、线性规划问题的可行域一定是凸集。、线性规划问题的可行域一定是凸集。7、用单纯形法求解一般线性规划时，当目标函、用单纯形法求解一般线性规划
4、时，当目标函数求最小值时，若所有的检验数数求最小值时，若所有的检验数Cj-Zj0，则问题达到最优。则问题达到最优。8、在非标准线性规划问题中，如果在约束条件、在非标准线性规划问题中，如果在约束条件中出现等式约束，为了产生初始可行基需要中出现等式约束，为了产生初始可行基需要增加松弛变量。增加松弛变量。9、当满足最优解，且检验数为零的变量的个数、当满足最优解，且检验数为零的变量的个数大于基变量的个数时，可求得无界解。大于基变量的个数时，可求得无界解。线性规划原问题与对偶问题的关系见：线性规划原问题与对偶问题的关系见：对称形式：对称形式：1 1、线性规划问题的对偶问题：、线性规划问题的对偶问题：方程
5、对变量，变量对方程；方程对变量，变量对方程；正常对正常，不正常对不正常；正常对正常，不正常对不正常；变量正常是非负，方程正常看目标变量正常是非负，方程正常看目标(max ，min)。max z=C Xs.t.AX bX 0min w=bYs.t.AY CY 0第三章第三章 对偶理论对偶理论弱对偶性及其推论弱对偶性及其推论最优性最优性强对偶性强对偶性互补松弛性互补松弛性变量的对应关系变量的对应关系2 2、对偶问题的性质：、对偶问题的性质：3 3、灵敏度分析、灵敏度分析bBCzABCczcbBbABABB1111)(（1 1）系数）系数c cj j变化变化（2 2）b bi i变化变化（3 3）增
6、加一变量）增加一变量x xj j （4 4）增加一个约束条件）增加一个约束条件（5 5）a aijij发生变化发生变化判断：1、对偶问题的对偶问题一定是原问题。、对偶问题的对偶问题一定是原问题。2、根据对偶问题的性质，当原问题为无界解时，、根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，但对偶问题无其对偶问题无可行解，反之，但对偶问题无可行解时，其原问题具有无界解。可行解时，其原问题具有无界解。3、若线性规划问题有无穷多最优解，则其对偶、若线性规划问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。问题也一定具有无穷多最优解。4、在完全市场经济条件下，当某种资源的市场、在
7、完全市场经济条件下，当某种资源的市场价格低于影子价格时，企业应买进资源，否价格低于影子价格时，企业应买进资源，否则应卖出。则应卖出。练习题：练习题：1 1、写出下列线性规划问题的标准形式及对偶问题。、写出下列线性规划问题的标准形式及对偶问题。（1 1）无约束，、432143214321432143210020999128537653432maxxxxxxxxxxxxxxxxxxxxxz（2 2）无约束，32132132132100624322minxxxxxxxxxxxxz（1 1）确定获利最大的产品生产计划；）确定获利最大的产品生产计划；（2 2）求其对偶问题的最优解；）求其对偶问题的最优解
8、；（3 3）产品）产品A A的利润变为的利润变为3 3时，上述最优计划变不变；时，上述最优计划变不变；如变化，请写出新的最优生产计划。如变化，请写出新的最优生产计划。（4 4）若设计一种新产品）若设计一种新产品D D，单件劳动力消耗为，单件劳动力消耗为8 8单位，单位，材料消耗为材料消耗为2 2单位，每件可获利单位，每件可获利3 3元，问该种产品元，问该种产品是否值得生产？是否值得生产？(此时假设此时假设A A的利润仍为的利润仍为1 1元）元）A AB BC C可用量可用量(单位单位)劳动力劳动力6 63 35 56565材材 料料3 34 45 54040产品利润（元产品利润（元/件）件）1
9、 12 24 42 2、某厂生产、某厂生产A,B,CA,B,C三种产品，其所需劳动力、材料三种产品，其所需劳动力、材料等数据见下表。等数据见下表。第四章第四章 线性规划的进一步讨论线性规划的进一步讨论1、目标规划、目标规划（1）偏差变量）偏差变量 d+,d-d+0，d-0，d+d-=0（2）目标函数）目标函数 决策值决策值=目标值目标值 min f(d+d-)决策值决策值目标值目标值 min f(d-)2 2、运输问题、运输问题表上作业法求解运输问题步骤：表上作业法求解运输问题步骤：（1 1）确定初始运输方案：最小元素法、沃格尔法）确定初始运输方案：最小元素法、沃格尔法判断是否为基可行解：基变
10、量个数为判断是否为基可行解：基变量个数为m+n-1m+n-1个个（2 2）对初始运输方案进行检验，确定是否为最优运）对初始运输方案进行检验，确定是否为最优运输方案：对偶变量法输方案：对偶变量法（3 3）如果不是最优运输方案，进行调整得到新的运）如果不是最优运输方案，进行调整得到新的运输方案：闭回路法输方案：闭回路法（4 4）重复）重复2 2、3 3步直到找到最优运输方案步直到找到最优运输方案注意：运输问题解的退化。注意：运输问题解的退化。2 2、产销不平衡运输问题的处理、产销不平衡运输问题的处理产销不平衡问题产销不平衡问题 产销平衡问题产销平衡问题（1）总产量）总产量 总销量总销量 n1jjm
11、1iiba假想一销地假想一销地Bn+1，令销量为令销量为 ，运价，运价c=0 n1jjm1iiba（2）总产量）总产量 总销量总销量 n1jjm1iiba假想一产地假想一产地Am+1，令，令产量为产量为 ，一般运价一般运价c=0 m1iin1jjab判断：1、正偏差变量取正值，负偏差变量应取负值。、正偏差变量取正值，负偏差变量应取负值。2、目标规划模型中，应同时包含绝对约束和目、目标规划模型中，应同时包含绝对约束和目标约束。标约束。3、运输问题是一种特殊的线性规划模型，因而、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况：有唯一求解结果也可能出现下列四种情况：有唯一最优解
12、、无穷多最优解、无界解、无可行解。最优解、无穷多最优解、无界解、无可行解。4、表上作业法实质上就是求解运输问题的单纯、表上作业法实质上就是求解运输问题的单纯形法。形法。判断：5、运输问题给出初始基可行解，从每一空格出、运输问题给出初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。发可以找出而且仅能找出唯一的闭回路。6、如果运输问题单位运价表的某一行（某一列）、如果运输问题单位运价表的某一行（某一列）元素分别加上一个常数元素分别加上一个常数k，最优运输方案不会，最优运输方案不会发生变化。发生变化。7、如果运输问题单位运价表的某一行（某一列）、如果运输问题单位运价表的某一行（某一列）元
13、素分别乘上一个常数元素分别乘上一个常数k，最优运输方案不会，最优运输方案不会发生变化。发生变化。)n,2,1j(0 x)m,2,1i(b),(xa.stxczmax(min)jn1jijijn1jjjxj部分或全部取整数部分或全部取整数第五章第五章 整数规划整数规划整数规划问题的松弛问题整数规划问题的松弛问题整数规划的可行域：整数规划的可行域：R 最优目标函数值最优目标函数值Z*松弛问题的可行域：松弛问题的可行域：R 最优目标函数值最优目标函数值Z*则则 ,Z*优于优于Z*RR 判断：1、整数规划解得目标函数值一般优于其相应的、整数规划解得目标函数值一般优于其相应的线性规划问题的解得目标函数值
14、。线性规划问题的解得目标函数值。2、指派问题效率矩阵的每个元素都乘上同一常、指派问题效率矩阵的每个元素都乘上同一常数数k，不影响最优指派方案。，不影响最优指派方案。3、指派问题数学模型的形式同运输问题十分相、指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。似，故也可以用表上作业法求解。第六章第六章 动态规划动态规划用动态规划的方法求解最短路问题。用动态规划的方法求解最短路问题。AB1B2C1C2C3C4D1D2D3E1E2F452368775854348435621343第七章第七章 网络优化模型网络优化模型图的基本概念图的基本概念树的性质树的性质最小生成树最小生成树最大流问题最大流问题
