线性规划2-1

1线性规划的单纯形法2美国数学家，美国全国科学院院士。线性规划的奠基人。1914年11月8日生于美国俄勒冈州波特兰市。1946年在伯克利加利福尼亚大学数学系获哲学博士学位。1947年丹齐克在总结前人工作的基础上创立了线性规划,并提出了解决线性规划问题的单纯形法。1937～1939年任美国劳工统计局统计员，1941～1952年任美国空军司令部数学顾问、战斗分析部和统计管理部主任。1952～1960年任美国兰德公司数学研究员，1960～1966年任伯克利加利福尼亚大学教授和运筹学中心主任。1966年后任斯坦福大学运筹学和计算机科学教授。1971年当选为美国科学院院士。1975年获美国科学奖章和诺伊曼理论奖金。GeorgeBernardDantzig(1914～)3康托罗维奇，Л.В.苏联经济学家，苏联科学院院士，最优计划理论的创始人。1912年生，1930年毕业于列宁格勒大学物理数学系，1935年获数学博士学位。1964年被选为苏联科学院院士。因提出资源最大限度分配理论，1975年与美籍荷兰学者T.C.库普曼斯一起获得诺贝尔经济学奖金。康托罗维奇的主要贡献是把线性规划用于经济管理，创立了最优计划理论。对有效利用资源和提高企业经济效益起了重大作用。他还提出经济效果的概念和衡量经济效果的统一指标体系,作为经济决策的定量依据,来选择最合理的社会生产结构。主要著作有《生产组织与计划的数学方法》(1939)、《资源最优利用的经济计算》(1959)、《最优计划的动态模型》(1964)等。4佳林·库普曼斯(1910年—1985年)，美国人，1910年8月28日生于荷兰，1940年离开荷兰移居美国。1975年，他和康托罗维奇同时获得诺贝尔经济学奖。线性规划经济分析法的创立者。5冯•诺依曼（匈牙利语：NeumannJános；英语：JohnvonNeumann，1903年12月28日－1957年2月8日）是出生于匈牙利的美国籍犹太人数学家，现代电子计算机创始人之一。他在计算机科学、经济、物理学中的量子力学及几乎所有数学领域都作过重大贡献。冯•诺伊曼从小就显示出数学天才，关于他的童年有不少传说。大多数的传说都讲到冯•诺伊曼自童年起在吸收知识和解题方面就具有惊人的速度。六岁时他能心算做八位数乘除法，八岁时掌握微积分，十二岁就读懂领会了波莱尔的大作《函数论》要义。冯•诺伊曼记忆力惊人，读书过目成涌，自幼爱好历史学，他的历史知识堪称渊博，宛如百科全书。6他的父亲由于考虑到经济上原因，请人劝阻年方17的冯•诺依曼不要专攻数学，后来父子俩达成协议，冯•诺依曼便去攻读化学。其后的四年间，冯•诺依曼在布达佩斯大学注册为数学方面的学生，但并不听课，只是每年按时参加考试。1926年他在苏黎世的获得化学方面的大学毕业学位，他也获得了布达佩斯大学数学博士学位。当他结束学生时代的时候，他已经漫步在数学、物理、化学三个领域的某些前沿。1926年春，冯•诺依曼到哥廷根大学任希尔伯特的助手。中学时，他的老师认为按传统的办法教冯•诺依曼中学数学课程将是毫无意义的，他接受了大学教师的单独的数学训练。1921年，已被大家当作数学家了。他的第一篇论文是和菲克特合写的，那时他还不到18岁。l933年担任普林斯顿高级研究院教授，当时高级研究院聘有六名教授，其中就包括爱因斯坦，而年仅30岁的冯•诺依曼是他们当中最年轻的一位。7冯•诺伊曼是二十世纪最重要的数学家之一，在纯粹数学和应用数学方面都有杰出的贡献。他研究希尔伯特空间上线性自伴算子谱理论，为量子力学打下数学基础；运用紧致群解决了希尔伯特第五问题；他和默里创造了算子环理论，即现在所谓的冯•诺伊曼代数。1940年以后，冯•诺伊曼转向应用数学。在力学、经济学、数值分析和电子计算机方面作出了卓越贡献。第二次世界大战时冯•诺伊曼因战事需要建立冲击波理论和湍流理论，发展了流体力学；从1942年起，他同莫根施特恩合作，写作《博弈论和经济行为》一书，使他成为数理经济学的奠基人之一。冯•诺伊曼对世界上第一台电子计算机ENIAC的设计有决定性的影响，被称为“计算机之父”。他是现代数值分析——计算数学的缔造者之一。8§2线性规划的标准型和基本概念线性规划问题及其数学模型线性规划的图解法线性规划的标准形式标准型线性规划的解的概念线性规划的基本理论问题的提出：在生产管理的经营活动中，通常需要对“有限的资源”寻求“最佳”的利用或分配方式。有限资源：劳动力、原材料、设备或资金等最佳：有一个标准或目标，使利润达到最大或成本达到最小。有限资源的合理配置有两类问题如何合理的使用有限的资源，使生产经营的效益达到最大；在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少。线性规划问题及其数学模型例１，某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：每吨产品的消耗每周资源总量甲乙维生素（公斤）3020160设备（台班）5115已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据市场需求调查的结果，甲药品每周的产量不应超过4吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？定义x1为生产甲种药品的计划产量数，x2为生产乙种药品的计划产量数。数学模型为s.t.（subjectto)(suchthat)121212112maxZ=5x+2x30x20x1605xx15x4x0,x0每吨产品的消耗每周资源总量甲乙维生素（公斤）3020160设备（台班）5115单位利润（万元）5２12•例2靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小工厂1工厂2200万m3500万m313决策变量：x1、x2——分别代表工厂1和工厂2处理污水的数量(万m3)。则目标函数：minz=1000x1+800x2约束条件：第一段河流（工厂1——工厂2之间）：(2－x1)/500≤0.2%第二段河流：[0.8(2－x1)+(1.4－x2)]/700≤0.2%此外有：x1≤2；x2≤1.4化简有：minz=1000x1+800x2x1≥10.8x1+x2≥1.6x1≤2x2≤1.4x1、x2≥0称之为上述问题的数学模型。例３，某铁器加工厂要制作100套钢架，每套要用长为2.9米，2.1米和1.5米的圆钢各一根。已知原料长为7.4米，问应如何下料，可使材料最省？分析：在长度确定的原料上截取三种不同规格的圆钢，可以归纳出8种不同的下料方案：圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料头（米）00.10.20.30.80.91.１1.4问题归纳为如何混合使用这8种不同的下料方案，来制造100套钢架，且要使剩余的料头总长为最短。设xj表示用第j种下料方案下料的原料根数，j=1,2…8,数学模型s.t.这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量x1至x8的值,使目标函数取得最小值。12345678124634567123568jminZ=x+x+x+x+x+x+x+xx2xxx1002x2xxx3x1003xx2x3xx4x100x0j1,28,，圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料头（米）00.10.20.30.80.91.11.4且为整数线性规划的一般数学模型线性规划模型的特征：（1）用一组决策变量x1，x2，…xn表示某一方案，且在一般情况下，变量的取值是非负的。（2）有一个目标函数，这个目标函数可表示为这组变量的线性函数。（3）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式来表达。（4）要求目标函数实现极大化（max）或极小化（min）。满足上述4个特征的规划问题称为线性规划问题线性规划的一般数学模型目标函数满足约束条件通常称为决策变量，为价值系数，为消耗系数,为资源限制系数。1122nnmax(min)Z=cx+cx++cx1111221nn12112222nn2m11m22mnnm12naxaxax(,)baxaxax(,)baxaxax(,)bx,x,x012nx,x,,x12nc,c,,c1112mna,a,,a12mb,b,,b线性规划的图解法适用于求解两个变量的线性规划问题图解法的基本步骤例4,利用例1说明图解法的主要步骤，例1的数学模型为s.t.121212112maxZ5x2x30x20x1605xx15x4x0,x0O51015x1x1=4x25101AB(2,5)C▽Z5x1+x2=1530x1+20x2=1605x1+2x2=5121212112maxZ5x2x30x20x1605xx15x4x0,x012ZZZ==52xx，（，）图解法的几种可能结果(1）有唯一最优解，如例1。（2）有无穷多最优解如例1中的目标函数设为maxZ=10x1+2x2则目标函数等值线10x1+2x2=Z与第二约束5x1+x2≤15的边界线平行。将等值线沿梯度▽Z=（10，2）正方向平移至B点时与可行域OABC的整条边界线AB重合。这表明线段AB上的每一点都使目标函数取得同样的最大值，因而都是最优解。21O51015x1x1=4x25101AB（2，5）C▽Z5x1+x2=1530x1+20x2=16010x1+2x2=5212xx10maxZ12ZZZ==2xx，（10，）例5，试用图解法求解下列线性规划问题st.（3）无界解（或称无最优解）无界解是指线性规划问题的最优解无界。若是极大化问题，则可使目标函数值Z→+∝,极小化问题则可使目标函数值Z→-∝，有无界解的线性规划问题的可行域是无界区域，但反之则不必然。12121212minZ3x2x-2xx2x-3x3x0,x0-1O24x1x224-▽Z=(3,2)-2x1+x2=2x1-3x2=3-1O3312121212minZ3x2x-2xx2x-3x3x0,x012ZZZ==2xx，（-3,-）（4）无可行解某些线性规划问题的可行域是空集，既不存在满足所有约束条件的点，这时问题无可行解，当然更谈不上最优解了。在实际中出现这种情况可以认为资源条件无法满足人们的要求，既不存在可行方案。25例6maxz=x1+2x2－x1+2x2≥1x1+x2≤－2x1、x2≥0无可行解。1－112OA2x1xX1+x2=-2-x1+2x2=126以上几种情况的图示如下：可行域有界—唯一最优解可行域有界—多个最优解27可行域无界—唯一最优解可行域无界—无穷多最优解28可行域无界—目标函数无界可行域为空集—无可行解291.有最优解唯一最优解无穷多最优解2.最优解无界3.无可行解30直观结论：（1）可行域可以是个凸多边形，可能无界，也可能为空；（2）若线性规划问题的最优解存在，它一定可以在可行域的某一个顶点上得到；（3）若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即LP有无穷多最优解；（4）若可行域非空有界