线性规划及单纯形法

1、运筹学Operational Research运筹帷幄，决胜千里 史记张良传1 绪 论一、运筹学发展简介二、运筹学的特点及研究对象三、运筹学的工作步骤四、运筹学内容介绍2一、运筹学（OR）发展简介运筹学在国外英国称为 Operational Research美国称为 Operations Research起源于二战期间的军事问题，如雷达的设置、运输船队的护航舰队的规模、反潜作战中深水炸弹的深度、飞机出击队型、军事物资的存储等。二战以后运筹学应用于经济管理领域（LP、计算机）1948年英国首先成立运筹学会；1952年美国成立运筹学会。1952年，Morse 和 Kimball出版运筹学方法195

2、9年成立国际运筹学联合会3运筹学在国内中国古代朴素的运筹学思想（田忌与齐王对马、都江堰工程、丁渭修复皇宫）1956年成立运筹学小组1958年提出运输问题的图上作业法1962年提出中国邮路问题1964年华罗庚推广统筹方法我国于1982年加入国际运筹学联合会，并于1999年8月组织了第15届大会4二、运筹学的特点及研究对象运筹学的定义运筹学为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法Morse 和 Kimball运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测、比较各种决策及其产生的后果，以帮助主

3、管人员科学地决定工作方针和政策英国运筹学会运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理中国百科全书现代运筹学涵盖了一切领域的管理与优化问题，称为 Management Science5三、运筹学的工作步骤明确问题建立模型设计算法整理数据求解模型评价结果简化？ 满意？YesNoNo明确问题建立模型设计算法整理数据求解模型评价结果6四、运筹学内容介绍排队论 线性规划及单纯形法 对偶理论及灵敏度分析 运输问题 整数规划 动态规划 图与网络分析7第一章 线性规划及单纯形法 第一节 线性规划问题及数学模型1939年

4、 苏 康托洛维奇1941年 美 Hichook1947年 G.B.Dantzig 单纯形法1979年 苏 哈奇安算法1984年 Karmarkar算法 8一、实例例1 (书P8) I II设 备 1 2 8台时 原材料A 4 0 16公斤原材料B 0 4 12公斤设I、II两种产品的产量分别为x1, x2 。建立该问题的数学模型为：例2 现要做100套钢架，每套需2.9米、2.1米和1.5米的圆钢各一根。已知原料长7.4米，问如何下料，使用的原料最少（余料最少或根数最少）？9解：设 x1, x2 , x3, x4 , x5分别代表五种不同的原料用量方案（余料最少）方案2.9米2.1米1.5米合

5、计余料x11037.40 x22017.30.1x30227.20.2x41207.10.3x50136.60.81011二、总结 目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。线性规划问题（LP问题）的共同特征： 每一个问题变量都用一组决策变量（x1, x2, , xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的。 存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。12三、两变量线性规划问题的图解法1.线性不等式的几何意义 半平面作出LP问题的可行域作出目标函数的等值线移动等值线到可行域边界得到最优点2.图解法步骤

6、134x1=164x2=12x1+2x2=8x1x248430例1 （书P8）：Q(4,2)Z=2x1+3x2 做目标函数2x1+3x2的等值线，与阴影部分的边界相交于Q(4,2)点，表明最优生产计划为：生产I产品4件，生产II产品2件。14例2Z=36153. 图解法的作用 能解决少量问题LP问题有可行解有最优解唯一解无穷多解无最优解（可行域为无界）无可行解（无解）规律1： 揭示了线性规划问题的若干规律16结论2：若LP问题有最优解，则要么最优解唯一，要么有无穷多最优解。17 规律2：线性规划问题的可行域为一凸集线性规划问题凸集的顶点个数是有限的最优解肯定可在凸集的某顶点处达到 18四、 线

7、性规划问题的标准型1. 标准型192. 所有LP问题均可化为标准型20例1可化为21例2 化标准型22课堂作业23五、标准型LP问题的解2425令B = =( P1 , P2 , , Pm ) 且| B | 0 ，则称Pj (j=1,2,m) 为基向量。与基向量Pj对应的变量xj称为基变量，记为XB = ( x1 , x2 , , xm )T，其余的变量称为非基变量，记为 XN = ( xm+1 , xm+2 , , xm+n ) T 。基变量：26基本解令非基变量 XN = 0，求得的一组基变量 XB的值称为基础解。 基可行解（顶点）既是基本解，又是可行解。基最优点既是基本解，又是使目标函数

8、值达到最优的解27 线性规划标准型问题解的关系约束方程的解空间基解可行解非可行解基可行解28 10/3 244x1x2x1+x2=43x1 +5x2=1029 可行解、基础解和基础可行解举例30第二节 单纯型法 一、基本思想化LP问题为标准型，确定一个初始基本可行解检验解的最优性结束Y枢轴运算（旋转运算）确定另一个基本可行解N31二、枢轴运算32三、检验数的意义33第三节 单纯型法的步 骤一、步骤化LP问题为标准型,建立初始单纯型表;34二、实例化为标准型35单纯型表算法以4为枢轴元素进行旋转运算，x2为换入变量，x5为换出变量以1为枢轴元素进行运算，x1为换入变量， x3为换出变量36以2为

9、枢轴元素进行运算，x5为换入变量， x4为换出变量此时达到最优解。X*=(4,2), MaxZ=14。37第四节 LP问题的进一步讨论一、人工变量法381. 大M法(M为任意大的正数)加入松弛变量x4;剩余变量x5;人工变量x6,x7391) 人工变量的识别2) 目标函数的处理3) 计算(单纯型法)40注意：本例是求最小值，所以用所有 来判别目标函数是否实现了最小化。因而换入变量xk的选取标准为41结果得: X*=(4,1,9,0,0,0,0) Z*=2（接上表）42 两阶段法(将LP问题分成两个阶段来考虑) 第I 阶段: 不考虑原问题是否存在可行解，给原LP问题加入人工变量，并构造仅含人工变

10、量的目标函数和要求最小化；然后用单纯型法求解，若得w=0，则进行第二阶段计算，否则无可行解。 第II 阶段：将第一阶段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初始表。43加入松弛变量x4;剩余变量x5;人工变量x6,x7用单纯形法求解第一阶段的结果得：44此时，达到第一阶段的最优解，W=045由于人工变量x6 =x7=0,所以（0,1,1,12,0）T是该线性规划问题的基可行解。于是转入第二阶段运算：此时达到该LP问题的最优解：x1=4,x2=1,x3=9; 目标函数值Z=-2。46二、单纯型法中存在的问题1. 存在两个以上的最大正检验数。选择任何变量（对应

11、最大正检验数）作为进基变量。2. 最小比值相同。LP问题出现退化现象，即基变量取值为0 4748选取x1为换入变量；按Bland算法，选取下标最小的x5为换出变量，得下表：此时换出变量为x1，换入变量为x4，迭代后目标函数值不变，继而出现了循环现象，达不到最优解。49解决退化的方法有：“摄动法”、“辞典序法”、 Bland规则等1974年Bland提出Bland算法规则：503. 最小比值原则失效Cj2300CBXBbX1X2X3X40X36-20113X24-3101Cj-Zj-121100-3经过一次迭代后可得右表514. 在最优表中出现某非基变量检验数为052CBXBbX1X2X3X4X

12、50X340012/3-1/34X260101/203X14100-2/31/3Cj-Zj-360000-10X46003/21-1/24X2301-3/401/43X1810100Cj-Zj-360000-1Cj-Zj034000结论：若线性规划问题存在某非基变量检验数为0,而其对应列向量ak0,仍可判断线性规划问题有无穷多最优解。任一个LP问题最优解都可表示成其基本最优解的凸组合加上其凸方向的线性组合.53第五节 应用举例例1 某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、C。已知产品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？产品名称规格要求

13、单价(元/kg）A原材料C不少于50%原材料P不超过25%50B原材料C不少于25%原材料P不超过50%35D不限25原材料名称每天最多供应量(kg)单价(元/kg)C10065P10025H603554用单纯型法计算得结果:每天生产A产品200kg,分别需要原料:C为100kg;P为50kg;H为50kg. 总利润收入Z=500元/天.55先考虑一月份的线性规划模型:例2 （书P41 例12）56以一月份内各种设备的生产能力总和为分母,生产产品所需要的各类设备的总台时数为分子,可计算出一月份的平均设备利用系数Z,将Z作为目标函数,可得下面的模型:57 考虑二月份线性规划模型时:(1)从全年计

14、划中减去一月份已生产的数量;(2)对批量小的产品,如一月份已经安排较大产量的,二月份将剩余部分安排生产;(3)保证第4号产品在月底前交货.这样,我们可以依次对12个月列出线性规划模型并求解,再根据具体情况对计算结果进行必要调整.58例3 某部门在今后5年内连续给以下项目投资： 项目A，第一年至第四年每年年初投资，次年末回收本利 115%； 项目B，第三年初投资，第五年末回收本利 125%，最大投资额不超过4万元； 项目C，第二年初投资，第五年末回收本利 140%，最大投资额不超过3万元； 项目D，五年内每年初可购买公债，当年末归还，并加利息6% 。 该部门现有资金 10万元，问该如何确定投资方案，使第五年末拥有的资金本利和最大？5960班次时间所需人数16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030例4 某公交线路每天各时段内所需司乘 人员数如下： 设所有的司乘人员分别在各时段的开始上班，并连续工作8小时，问该公交线路至少需配备多少司乘人员。列出该问题的线性规划模型