运筹学课程讲义(共35页).doc

《运筹学课程讲义(共35页).doc》由会员分享，可在线阅读，更多相关《运筹学课程讲义(共35页).doc（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精选优质文档-倾情为你奉上运筹学课程讲义第一部分 线性规划第一章 线性规划的基本性质1.1 线性规划的数学模型一、 线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个。生产桌子和椅子需木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？ 例：某工厂生产某一种型号的机床。每台机床上需要2.9m、2.1m、1.5m的轴，分别为1根、2根和1根。这些轴需用同一种圆钢制作，圆钢的长度为74m。如果要生产100台

2、机床，问应如何安排下料，才能用料最省？二、 数学模型的标准型1. 繁写形式2. 缩写形式3. 向量形式4. 矩阵形式三、 任一模型如何化为标准型？1. 若原模型要求目标函数实现最大化，如何将其化为最小化问题？2. 若原模型中约束条件为不等式，如何化为等式？3. 若原模型中变量xk是自由变量，如何化为非负变量？4. 若原模型中变量xj有上下界，如何化为非负变量？令1. 2图解法该法简单直观，平面作图适于求解二维问题。使用该法求解线性规划问题时，不必把原模型化为标准型。一、 图解法步骤1. 由全部约束条件作图求出可行域2. 作出一条目标函数的等值线3. 平移目标函数等值线，作图求解最优点，再算出最

3、优值二、 从图解法看线性规划问题解的几种情况1. 有唯一最优解2. 有无穷多组最优解3. 无可行解4. 无有限最优解（无界解） 最优解，最优值3直观结论：1）线性规划问题的可行域为凸集，特殊情况下为无界域（但有有限个顶点）或空集； 2）线性规划问题若有最优解，一定可以在其可行域的顶点上得到。1.3 线性规划的基本概念和基本定理一、 线性规划问题的基与解可行解最优解基基向量非基向量基变量非基变量基本解基本可行解最优基本可行解退化的基本解二、 几何意义上的几个基本概念1. 凸集2. 凸组合3. 顶点三、 线性规划问题的基本定理定理1：若线性规划问题存在可行域，则其可行域是凸集。引理1：线性规划问题

4、的可行解为基本可行解的充要条件是X的正分量对应的系数列向量是线性无关的。定理2：线性规划问题的基本可行解对应于可行域的顶点。引理2：K是有界凸集，则任何一点XK可表示为K的顶点的凸组合。定理3：如果线性规划问题有有限最优解，则其目标函数最优值一定可以在可行域的顶点上达到。四、 求解线性规划问题的基本思路在有限个基本可行解中寻找最优基本可行解。找一个基本可行解（m个线性无关的系数列向量），由其换到另一个基本可行解。实质即为换基。前提是保证新的基本可行解的目标函数值比原来的更优而不是更劣。第二章 单纯形法它是求解线性规划最为成熟的算法。胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价

5、30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？ 将其变形，得 将对应的单位矩阵作为初始可行基。令为基变量，为非基变量。原模型变形为 如果令非基变量等于零，得一个基本可行解（0，0，120，50），对应的目标函数值z = 0最优性检验：该解是否最优？显然不是。经济意义分析：等于零意味着家具厂不开工生产，销售收入为零，资源未得到充分利用。数学角度分析：非基变量前的系数都为正，表明目标函数值有增加的可能。只要将系

6、数为正的非基变量与某一基变量对换，当换入变量的值增加时，目标函数值就可能增加。换基迭代：寻找下一个可行解需要进行换基迭代。换基后需满足：（1）新的解仍是基本可行解；（2）目标函数得到改善。选择入基变量：系数均为正。对求目标函数极大化的问题，我们希望目标值增加得越快越好，因此应选系数最大的入基。选择出基变量：入基后，其值从零增加并引起其他变量取值的变化。由问题的典则表达式和变量必须取正值的条件，得下列不等式关系： 因迭代后仍为取零值的非基变量，上式可简化为很明显，只有选时，才能使上述不等式成立，并使基变量变为零，正好满足非基变量必须为零的条件，所以可令出基，新的典则方程变为 化简后得 代入目标函

7、数可得 得到下一个基本可行解（25，0，20，0），并完成了第一次迭代。新解是最优解吗？需进行最优检验。由于目标函数中的系数仍为正，说明多生产椅子仍有利可图，该解仍不是最优解。再次迭代。入基，出基，换基后典则形式变为 第三个基本可行解为（15，20，0，0），松弛变量都已为零，表明资源已得到充分利用；非基变量在目标函数中的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。2.1 单纯形法原理一、 构造初始可行基1. 引入附加变量，把数学模型化为标准型2. 若约束条件中附加变量的系数是-1或原约束即为等式，则必须引入人工变量，以构成初始可行基3. 目标函数中，附加变量的系数为0，而

8、人工变量的系数为M（很大的正数）二、 求出一个基本可行解1. 用非基变量表示基变量和目标函数式 2. 求出一个基本可行解及相应的z值三、 最优性检验1. 最优性检验的依据检验数2. 最优解判别定理：若在极小化问题中，对于某个基本可行解，所有检验数0，且人工变量为0，则这个基本可行解是最优解。对于极大化问题，只要把上述定理中的0改成0即可。这里的检验数即为（c-z）。3. 无穷多最优解判别定理：若在极小化问题中，对于某个基本可行解，所有检验数0，又存在某个非基变量的检验数为0，且人工变量为0，则线性规划问题有无穷多最优解。4. 无可行解情况若在极小化问题中，对于某个基本可行解，所有检验数0，但人

9、工变量0，则该线性规划问题无可行解。四、 基变换1. 基本可行解的改进定理2. 换入变量的确定3. 换出变量的确定最小非负比值规则 =b/a=b/a|a0 在单纯形法迭代中，基变换带来可行域顶点的变换，且相邻两次迭代所对应的顶点也是相邻的。4. 无有限最优解（无界解）判定定理：若在极小化问题中，对于某个基本可行解，有一个非基变量的检验数0，必有YP=c2. 如果Y P0，必有AX=b4. 如果AXb，必有y=0其中P是A的第j列，A是A的第i行。互补松弛定理意味着：如果原问题最优解X中第j个变量x为正，则其对偶问题中与之对应的第j个约束式在最优情况下必呈严格等式（即其松弛变量为0）；而如果对偶

10、问题中第j个约束式在最优情况下呈严格不等式，则原问题最优解X中第j个变量x必为0。类似地，如果对偶问题最优解Y中第i个对偶变量y为正，则其原问题中与之对应的第i个约束在最优情况下必呈严格等式（即其剩余变量为0）；而如果原问题中第i个约束在最优情况下呈严格不等式，则对偶问题最优解Y中第i个对偶变量y必为0。互补松弛性： 为最优解 对一对对偶规划的最优解而言，如果对应某一约束条件的对偶变量的值为非零，则该约束条件取严格等式；反之，如果某个约束条件取严格不等式，则其对应的对偶变量一定为零。七、 非对称形式对偶的互补松弛定理非对称形式对偶的互补松弛定理：若X和Y分别是原问题和对偶问题的可行解，则X和Y

11、都是最优解的充要条件是，对所有j，下列关系式成立：1. 如果x0，必有YP=c2. 如果Y P c，必有x=0例：已知线性规划问题试用对偶理论证明上述线性规划问题无最优解该问题存在可行解，如又对偶问题为由第一个约束条件知对偶问题无可行解，由此可知其原问题无最优解八、 最优对偶变量（影子价格）的经济解释由对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等。如果在得到最优解时，某种资源并未完全利用，其剩余量就是该约束中剩余变量的取值，那么该约束相对应的影子价格一定为零。因为在得到最优解时，这种资源并不紧缺，故此时再增加这种资源不会带来任何效益。反之，如果某种资源的影子价格大于零，就说明

12、再增加这种资源的可获量，还回带来一定的经济效益，即在原问题的最优解中，这种资源必定已被全部利用，相应的约束条件必然保持等式。3.3 对偶单纯形法一、 对偶单纯形法与单纯形法的区别单纯形法在整个迭代过程中，始终保持原问题的可行性，即常数列 0，而检验数C-CBA(即C-YA)由有负分量逐步变为全部0（即变为满足YAC，Y是对偶问题的可行解），即同时得到原问题和对偶问题的最优解。对偶单纯形法在整个迭代过程中，始终保持对偶问题的可行性，即全部检验数0，而常数列由有负分量逐步变为全部0（即变为满足原问题的可行性），即同时得到原问题和对偶问题的最优解。二、 对偶单纯形法的求解步骤和计算举例1. 给定一个

13、初始对偶可行的基本解2. 进行最优性检验若现行常数列b0,则停止计算。否则，转下步。3. 确定换出变量将现行常数列b中最小的负元素所在行的基变量换出4. 确定换入变量最大负比值规则：在换出变量所在的第r行约束式中，找出各非基变量列中系数为负的那些元素，用相应的检验数分别除以这些负元素，所得各负比值中最大者所在列即为换入列。5. 以为主元素进行取主变换返回步骤2，继续迭代。三、 关于初始对偶可行的基本解1. 构造扩充问题其中R是非基变量下标的集合。再增加一个变量和一个约束条件，得到其扩充问题： 2. 求扩充问题的初始对偶可行的基本解若基本解不是对偶可行的，即检验数中有负的，并假设负检验数中最小的

14、一个为，则以相应的变量为换入变量，以为换出变量，即以为主元素进行取主变换，可得到全部检验数0，即得到一个对偶可行的基本解。3. 用对偶单纯形法求解扩充问题，并得到原问题的解答因为扩充问题的对偶问题有可行解，根据对偶原理可知，扩充问题或无可行解或有有限最优解。若扩充问题无可行解，则原问题也无可行解，若扩充问题得到最优解,则是原问题的可行解。若扩充问题的目标函数最优值与M无关，则就是原问题的最优解。4. 计算举例3.4 灵敏度分析研究初始单纯型表上的系数变化对最优解的影响，研究这些系数在什么范围内变化时，原最优基仍是最优的；若原最优基不再是最优的，如何用最简便的方法找到新的最优解。假定线性规划标准

15、型最终表上已得到最优基B，最优结果为： = 一、 改变价值向量C 1. 在最终表内，是非基变量， 均不变；仅变化。若，即，则最优解不变；若，则原最优基不再是最优的了。以为换入变量，把最终表上的换成，换成，继续用单纯形法求解。2. 在最终表内，是基变量要改变，并因此影响到各个检验数。若，则所有，即最优解不变。若超出上述允许变化范围，即有，则以原最终表为基础，换上变化后的价值系数和检验数，继续迭代，可求出新的最优解。二、 改变限定向量b 若超过上述范围，则新得到的解为不可行解。但由于的变化不影响检验数，故仍保持所有检验数，即满足对偶可行性。这时可在原最终表的基础上，换上改变后的右端常数及相应的值，

16、用对偶单纯形法继续迭代，以求出新的最优解。三、 改变约束矩阵A1. 非基向量列改变为影响最终表上的第j列数据和第j个检验数。 若，则原最优解仍是新问题的最优解。若，则原最优基在非退化情况下不再是最优基。这时，应在原最终表的基础上，换上改变后的第j列数据和，把作为换入变量，用单纯形法继续迭代。2. 基向量列改变为重新计算四、 增加一个新的约束条件即 若原最优解满足这个新约束，则它就是新问题的最优解。否则，引进松弛变量，有 若 0则现行对偶可行的基本解是新问题的可行解，亦即最优解。若 0则在原最终表的基础上，增加新约束式的数据，通过矩阵行的初等变换，把原最终表上的各基向量列及新增列化为单位阵，再用

17、对偶单纯形法继续求解。五、 增加一个新的变量对原问题最优解的可行性无影响。 若 ，则原最优解就是新问题的最优解。若 ，须把加入到原最终表内，并以新变量作为换入变量，按单纯形法继续迭代，得到新的最优解。第四章 应用实例4.1 产销平衡的运输问题由于产销平衡，有n行m行 较为简洁的求解方法表上作业法（不做要求）。另，可与整数规划结合而带来求解的方便。4.2 套裁下料问题思路举例：某工厂要做100套钢架，每套用长为2.9m、2.1m和1.5m的元钢各一根。已知原料长7.4m，问应如何下料，可使所用原料最省。简单裁法将使料头数量增多，应使用套裁的方法。须先设计出若干种较好的套裁方案如下表，分设按各种方

18、案下料的原料根数为，可列写其数学模型：方案下料数（根）长度（m）123452.92.11.5103201022120013合计料头7.407.30.17.20.27.10.36.60.84.3 汽油混合问题变量的选取，是模型设立的关键。逻辑关系的明晰，是模型设立的基础。4.4 购买汽车问题明晰乘和的关系，用数字等数学符号将文字的约束关系表达出来。4.5 产品加工问题顺序理清方可使表达式明了。4.6 投资计划问题列举各可行计划，逐期推算；同时注意限制性条件与同质较劣方案的放弃。4.7 企业年度生产计划问题一、 变量的选择最终产品的产量与新增设备的容量二、 构造线性规划模型1. 国家下达的指令性计

19、划和市场需求约束 其中，为完成国家指令性计划之后，超额生产的第j种产品产量，它也是决策变量；为国家对第j种产品的指令性计划指标；为第j种产品在完成国家指令性计划之后，预测的市场最大需求量；为国家有指令性计划的产品的下标集合对无指令性计划产品，则有 其中，为所预测的市场对第j种产品的最大需求量2. 设备生产能力约束 （i =1,2,9）3. 增加设备容量的限制约束 （i =1, 2, , 9）4. 动力消耗约束 5. 下脚料的回收与复用约束 （k =1, 2, 3, 4）其中，为产生第k种下脚料的产品下标集合 （k =1, 2, 3, 4）6. 决策变量的非负约束 （j =1，2，23） （）

20、（i =1, 2, , 9） （k =1, 2, 3, 4）7. 目标函数 综上，可得本问题的数学模型。4.8 企业年度生产计划的按月分配问题一月份 （i =1，2，m） （j =1，2，n ） （j =1，2，n ）二月份 （i =1，2，m） （j =1，2，n ） （j =1，2，n ）4.9 合金添加的优化问题配料问题的推导 （i =1，2，m） （i =1，2，m） （j =1，2，n）例：某房地产公司有水泥100单位、木材160单位和玻璃400单位。用以建造A型和B型住宅。建一栋A型住宅需要水泥、木材和玻璃分别为1、2、2单位，售价每栋100万元；建一栋B型住宅需要水泥、木材、玻璃分别为1、1、5单位，售价每栋150万元。该公司如何安排两种住宅的建设，才能使总售价最大？ 专心-专注-专业