线性规划及单纯形法

运筹学

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

运筹学在国内中国古代朴素的运筹学思想〔田忌赛马、都江堰工程、丁渭修复皇宫〕1956年中科院成立运筹学小组1957年正式将OperationsResearch命名为“运筹学〞1958年提出运输问题的图上作业法〔解决粮食合理运输问题〕1962年提出中国邮路问题〔管梅谷〕1964年华罗庚推广统筹方法1980年中国运筹学学会正式成立1982年中国参加国际运筹学联合会1999年8月我国组织了第15届大会4精选课件＊齐王赛马〔齐王和田忌〕战国时期，齐威王与田忌赛马，规定双方各出上中下三个等级的马各一匹。如果按同等级的马比赛，齐王可获全胜。田忌的谋士孙膑提出的以下、上、中对齐王的上、中、下对策，使处于劣势的田忌战胜齐王，这是从总体出发制定对抗策略的一个著名事例。5精选课件丁渭主持皇宫的修复〔北宋，皇宫因火焚毁〕北宋真宗年间，皇城失火，宫殿烧毁，大臣丁谓主持了皇宫修复工程。他采用了一套综合施工方案:①先在需要重建的大道上就近取土烧砖；②在取土后的深沟中引水，形成人工河，再由此水路运入建筑材料，从而加快了工程进度；③皇宫修复后，又将碎砖废土填入沟中，重修大道。使烧砖、运输建筑材料和处理废墟三项繁重工程任务协调起来，从而在总体上得到了最正确解决，一举三得，节省了大量劳力、费用和时间。6精选课件运筹学为决策机构对所控制的业务活动作决策时，提供以数量为根底的科学方法——Morse和Kimball运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是开展一个科学的系统模式，并运用这种模式预测、比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策——英国运筹学会运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理——中国百科全书现代运筹学涵盖了一切领域的管理与优化问题，称为ManagementScience运筹学的定义二、运筹学的特点及研究对象7精选课件运筹学的特点：优化：从全局观点看问题，追求总体效果最优量化：通过建立和求解模型使问题在量化的根底上得到合理决策综合：多学科交叉运筹学的研究对象：生产与经济等各种实践活动中提出来的实际问题二、运筹学的特点及研究对象8精选课件三、运筹学的工作步骤明确问题建立模型设计算法整理数据求解模型评价结果简化？满意？YesNoNo明确问题建立模型设计算法整理数据求解模型评价结果9精选课件四、运筹学内容介绍线性规划及单纯形法对偶理论及灵敏度分析运输问题整数规划动态规划图与网络分析

10精选课件第一章线性规划及单纯形法1939年苏康托洛维奇发表“生产组织与方案中的数学方法〞，1960年出版“最正确资源利用的经济计算〞获诺贝尔经济学奖1941年美Hichcock提出运输问题1947年美丹捷格〔G.B.Dantzig〕提出单纯形法，1963年出版“线性规划及其扩展〞

在生产管理中如何有效地利用现有人力、物力完成更多的任务，或在预定的任务目标下，如何耗用最少的人力、物力去实现目标。11精选课件第一节线性规划问题及数学模型例1生产方案问题(P4)

III资源限量设备128台时原材料A4016公斤原材料B0412公斤单位利润23设I、II两种产品的产量分别为x1,x2。建立该问题的数学模型为：目标函数约束条件决策变量一、实例12精选课件例2合理下料问题

现要做100套钢架，每套需2.9米、2.1米和1.5米的圆钢各一根。原料长7.4米，问如何下料，使用的原料最少〔余料最少或根数最少〕？解：设x1,x2,x3,x4,x5分别代表五种不同的原料用量方案〔余料最少〕13精选课件方案2.9米2.1米1.5米合计余料x11037.40x22017.30.1x30227.20.2x41207.10.3x50136.60.8决策变量？目标函数？特点？约束条件？决策方案？最优方案？最优值？14精选课件二、总结目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。线性规划问题〔LP问题〕的共同特征：每一个问题变量都用一组决策变量〔x1,x2,…,xn〕表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的。存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。线性规划模型的一般形式与标准形式〔P7稍后讲〕15精选课件三、两变量线性规划问题的图解法1.线性不等式的几何意义—半平面作出LP问题的可行域作出目标函数的等值线移动等值线到可行域边界得到最优点2.图解法步骤16精选课件4x1=164x2=12x1+2x2=8x1x248430例1〔书P4〕：Q(4,2)Z=2x1+3x2做目标函数2x1+3x2的等值线，与阴影局部的边界相交于Q(4,2)点，说明最优生产方案为：生产I产品4件，生产II产品2件。最大利润：14.根本概念：可行解、可行域、最优解？17精选课件例2Z=3618精选课件3.图解法的作用能解决少量问题LP问题有可行解有最优解唯一解无穷多解无最优解〔可行域为无界〕无可行解〔无解〕规律1：揭示了线性规划问题的假设干规律见P9-10例题19精选课件结论：假设LP问题有最优解，那么要么最优解唯一，要么有无穷多最优解。★20精选课件

规律2：线性规划问题的可行域为一凸集线性规划问题凸集的顶点个数是有限的最优解肯定可在凸集的某顶点处到达21精选课件四、线性规划问题的标准型1.一般形式22精选课件2.标准型LP模型的各种表示法见P723精选课件3.所有LP问题均可化为标准型1.目标函数最大化2.约束条件为等式3.变量约束为非负4.约束右端项非负24精选课件例1可化为25精选课件例2化标准型26精选课件课堂作业27精选课件五、标准型LP问题的解LP模型向量表示法见P728精选课件29精选课件令B==(P1,P2,…,Pm)且|B|0，称A中基B对应的列向量Pj(j=1,2,…,m)

为基向量。与基向量Pj对应的变量xj称为基变量，记为XB=(x1,x2,…,xm)T，其余的变量称为非基变量，记为XN=(xm+1,xm+2,…,xm+n)T。基变量：30精选课件根本解令非基变量XN=0，求得的一组基变量XB的值称为根本解。基可行解〔顶点〕既是根本解，又是可行解。基最优点既是根本解，又是使目标函数值到达最优的解31精选课件如引例中：

基基变量非基变量根本解是否可行目标函数值ZB1x1,x2x3,x4〔-2，3，0，0〕否B2x1,x3x2,x4〔3，0，1，0〕是Z=3B3x1,x4x2,x3〔4，0，0，-3〕否B4x2,x3x1,x4〔0，9/5，2/5，0〕是Z=9/5B5x1,x4x2,x3〔2，0，0，-1〕否B3x3,x4x1,x2〔0，0，4，9〕是Z=032精选课件

线性规划标准型问题解的关系约束方程的解空间基解可行解非可行解基可行解LP解的根本定理见P1233精选课件第二节单纯型法

一、根本思想化LP问题为标准型，确定一个初始根本可行解检验解的最优性结束Y枢轴运算〔旋转运算〕确定另一个根本可行解N34精选课件二、枢轴运算35精选课件又如：36精选课件三、检验数的意义P1737精选课件四、单纯形表基变量非基变量常数项约束方程增广矩阵检验数+目标函数值P1738精选课件第三节单纯型法的步骤一、步骤化LP问题为标准型,建立初始单纯型表;直接求最小化问题，P23说明39精选课件二、用单纯形表求解LP问题实例化为标准型例1.40精选课件单纯型表

算法步骤：Cj23000

CBXBbX1X2X3X4X50X30X40X58161212100440010-0[4]0013023000以[4]为枢轴元素进行旋转运算，x2为换入变量，x5为换出变量Cj23000

CBXBbX1X2X3X4X50X30X43X22163[1]010-1/2240010401001/4--92000-3/4以[1]为枢轴元素进行运算，x1为换入变量，x3为换出变量〔1〕建立初始单纯形表；〔2〕求检验数并判断最优性，假设最优，终止，否那么转下一步；〔3〕确定出基与进基变量；〔4〕换基迭代，转入〔2〕。41精选课件Cj23000

CBXBbX1X2X3X4X52X10X43X22831010-1/2-00-41[2]401001/412-1300-201/4以[2]为枢轴元素进行运算，x5为换入变量，x4为换出变量Cj23000

CBXBbX1X2X3X4X52X10X53X24421001/4000-21/21011/2-1/80-1400-3/2-1/80此时到达最优解。X*=(4,2),MaxZ=14。42精选课件例243精选课件解:化标准型44精选课件

21000

01505100

0

24620100511001

21000

—24/65/1主元化为1主列单位向量换出换入表1：列初始单纯形表〔单位矩阵对应的变量为基变量〕正检验数中最大者对应的列为主列最小的值对应的行为主行45精选课件

21000

01505100

2

412/601/600104/60-1/61

01/30-1/30

15/524/26/4

0*52*2/6+0*4/61-2/3=表2：换基〔初等行变换，主列化为单位向量，主元为1〕检验数>0确定主列最小确定主列主元46精选课件

21000

015/20015/4-15/2

2

7/21001/4-1/213/2010-1/43/2000-1/4-1/2

检验数<=0最优解为X=(7/2,3/2,15/2,0,0)目标函数值Z=8.5

2*7/21*3/2+0*15/28.5表3：换基〔初等行变换，主列化为单位向量，主元为1〕47精选课件

21000

01505100

0

24620100511001

21000练习:一般主列选择正检验数中最大者对应的列,也可选择其它正检验数的列.以第2列为主列,用单纯形法求解。正检验数对应的列为主列注：1.几种特殊情形P20-23；2.对于极小化的LP问题，只须改成检验数≥0为最优。48精选课件第四节LP问题的进一步讨论一、人工变量法49精选课件1.大M法(M为任意大的正数)参加松弛变量x4;剩余变量x5;人工变量x6,x750精选课件1)人工变量的识别2)目标函数的处理3)计算(单纯型法)51精选课件Cj-31100MMCBXBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011-3+6M1-M1-3M0M000x4103-20100-1-Mx610100-11-211x31-2010001--11-M00M03M-1注意：本例是求最小值，所以用所有来判别目标函数是否实现了最小化。因而换入变量xk的选取标准为52精选课件结果得:X*=(4,1,9,0,0,0,0)Z*=2Cj-31100MMCBXBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2-1x31-2010001--10001M-1M+1-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/30001/31/3M-1/3M-2/3〔接上表〕53精选课件两阶段法(将LP问题分成两个阶段来考虑)第I阶段:求解模型〔1〕得到原问题的一个根本可行解。做法是：先不考虑原问题是否存在可行解，给原LP问题参加人工变量，并构造仅含人工变量之和的目标函数w并要求最小化；然后用单纯型法求解，假设得w=0，那么求得原问题的一个根本可行解，进行第二阶段计算，否那么无可行解。54精选课件第II阶段：求解模型〔2〕得到原LP问题的最优解。做法是：将第一阶段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初始表。解的理论见：P24命题1.5.1，1.5.255精选课件参加松弛变量x4;剩余变量x5;人工变量x6,x7用单纯形法求解第一阶段的结果得：56精选课件Cj0000011CBXBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-201000116-1-301000x4103-20100-1-1x610100-11-210x31-2010001-0-1001030x4123001-22-540x210100-11-2-0x31-2010000-0000011此时，到达第一阶段的最优解，W=057精选课件Cj-31100CBXBbx1x2x3x4x50x4123001-241x210100-1-1x31-20100--10001-3x141001/3-2/31x210100-11x390012/3-4/30001/31/3由于人工变量x6=x7=0,所以〔0,1,1,12,0〕T是该线性规划问题的基可行解。于是转入第二阶段运算：此时到达该LP问题的最优解：x1=4,x2=1,x3=9;目标函数值Z=-2。58精选课件二、单纯型法中存在的问题1.存在两个以上的最大正检验数。选择任何变量〔对应最大正检验数〕作为进基变量。2.最小比值相同。LP问题出现退化现象，即基变量取值为0★59精选课件Cj3/4-201/2-6000CBXBbX1X2X3X4X5X6X70X501/4-8-191000X601/2-12-1/230100X71001000103/4-201/2-600060精选课件Cj3/4-201/2-6000CBXBbX1X2X3X4X5X6X73/4X101-32-4364000X60043/2-150100X7100100010047/221-300选取x1为换入变量；按Bland算法，选取下标最小的x5为换出变量，得下表：此时换出变量为x1，换入变量为x4，迭代后目标函数值不变，继而出现了循环现象，达不到最优解。Cj3/4-201/2-6000CBXBbX1X2X3X4X5X6X73/4X101-32-4364000X60043/2-150100X7100100010047/221-30061精选课件解决退化的方法有：“摄动法〞、“辞典序法〞、Bland规那么等1974年Bland提出Bland算法规那么：62精选课件3.最小比值原那么失效Cj2300CBXBbX1X2X3X40X36-20113X24-3101Cj-Zj-121100-3经过一次迭代后可得右表★63精选课件4.在最优表中出现某非基变量检验数为064精选课件CBXBbX1X2X3X4X50X340012/3-1/34X260101/203X14100-2/31/3Cj-Zj-360000-10X46003/21-1/24X2301-3/401/43X1810100Cj-Zj-360000-1Cj-Zj034000结论：假设线性规划问题存在某非基变量检验数为0,而其对应列向量ak≤0,仍可判断线性规划问题有无穷多最优解。任一个LP问题最优解都可表示成其根本最优解的凸组合加上其凸方向的线性组合.65精选课件第五节应用举例例1某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。产品的规格要求、单价和原材料的供给量、单价。该厂应如何安排生产使利润最大？产品名称规格要求单价