管理运筹学-第2章--线性规划与单纯形法讲解学习.ppt

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,管理运筹学-第2章-线性规划与单纯形法,2.1 线形规划(Linear Programming)问题及其数学模型,【,引例,】,某工厂在计划期内要安排甲乙两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，以及资源的限制如下表所示：,甲,乙,资源限制,设备,1,1,300台时,原料A,2,1,400千克,原料B,0,1,250千克,单件利润,50（元/件）,100（元/件）,问:工厂应分别生产多少个产品甲、乙才能使工厂获利最多？,设生产甲产品,x,1,个，生产乙产品,x,2,个,目标函数 max Z=50,x,1,+100,x,2,约,束,条,件,x,1,+,x,2,300,2,x,1,+,x,2,400,x,2,250,x,1,0,x,2,0,线性规划模型,1.适用条件：,（1）优化条件:问题目标最大化、最小化的要求；,（2）约束条件:问题目标受一系列条件的限制；,（3）选择条件:实现目标存在多种备选方案；,（4）非负条件的选择:根据问题的实际意义决定是否非负。,2.构建线性规划模型的步骤,（1）科学选择决策变量,（2）明确目标要求,（3）根据实际问题的背景材料，找出所有的约束条件,（4）确定是否增加决策变量的非负条件,线性规划模型表示形式,决策变量；,目标函数系数、价值系数或费用系数；,右端项或资源常数；,称为约束系数或技术系数。,（1）一般形式：,（2）集合形式：,（3）向量形式：,（4）矩阵形式：,【例】,将线性规划模型一般表达式化为,矩阵形式。,解:,设:,例1.,目标函数：,Max z=50 x,1,+100 x,2,约束条件：,s.t.,x,1,+x,2,300 (A),2 x,1,+x,2,400 (B),x,2,250 (C),x,1,0 (D),x,2,0 (E),得到最优解：,x,1,=50，x,2,=250,最优目标值 z =27500,2图 解 法,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。,下面通过例1详细讲解其方法：,步骤：,(1)分别取决策变量X,1,X,2,为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。,x,2,x,1,X,2,0,X,2,=0,x,2,x,1,X,1,0,X,1,=0,（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。,100,200,300,100,200,300,x,1,+x,2,300,x,1,+x,2,=300,100,100,200,2x,1,+x,2,400,2x,1,+x,2,=400,300,200,300,400,（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。,100,100,x,2,250,x,2,=250,200,300,200,300,x,1,x,2,x,2,=0,x,1,=0,x,2,=250,x,1,+x,2,=300,2x,1,+x,2,=400,图2-1,（4）目标函数z=50 x,1,+100 x,2,，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。,x,1,x,2,z=20000=50 x,1,+100 x,2,图2-2,z=27500=50 x,1,+100 x,2,z=0=50 x,1,+100 x,2,z=10000=50 x,1,+100 x,2,C,B,A,D,E,解的几种可能结果,唯一最优解解,无穷多个最优解,无界解(可行域无界，常为模型遗漏了某些必要的约束条件),无可行解（可行域为空集，约束条件自相矛盾,资源满足不了人们的需求）,可行解：满足LP问题所有约束条件的解,最优解：满足目标要求的可行解,四种结局:,x,1,x,2,唯一最优解,x,2,x,1,无穷多最优解,x,1,x,2,无界解,x,2,x,1,无可行解,无界解,无可行解：可行域为空集,增加的约束条件,线性规划标准形式,线性规划标准模型的一般表达式,：,非标准形式标准化方法,：,1.目标函数,2.约束条件为不等式:,引进松驰变量x,s,:,引进剩余变量x,s,:,4.决策变量为自由变量:,5.约束右端项为负:,两端乘-1:,0,3.约束条件为不等式:,引入松驰变量（含义是资源的剩余量）,【引例】,中引入 s,1,，s,2,，s,3,模型化为,目标函数：Max z=50 x,1,+100 x,2,+0 s,1,+0 s,2,+0 s,3,约束条件：s.t.x,1,+x,2,+s,1,=300,2 x,1,+x,2,+s,2,=400,x,2,+s,3,=,250,x,1,x,2,s,1,s,2,s,3,0,对于最优解,x,1,=50 x,2,=250，s,1,=0 s,2,=50 s,3,=0,说明：生产50单位产品和250单位产品将消耗完所有,可能的设备台时数及原料B，但对原料A则还剩余50千克。,【例】将线性规划模型转化为标准式,解:,无约束,(4)在第一、第三约束左端加上松弛变量x,4,x,6,0,，在第二约束左端减去剩余变量x,5,0,习题,1.用图解法求解下列LP问题,（1）minZ=,6x,1,+4x,2,(2)maxZ=,3x,1,-2x,2,2x,1,+x,2,1,x,1,+x,2,1,3x,1,+4x,2,3 2,x,1,+2x,2,4,x,1,，x,2,0,x,1,，x,2,0,2,、,对下面LP问题,(1)用图解法求解,(2)写出此问题的标准形式,(3)求剩余变量的值,minZ=11,x,1,+8x,2,s.t.10,x,1,+2x,2,20,3,x,1,+3x,2,18,4,x,1,+9x,2,36,x,1,x,2,0,图解法的灵敏度分析,1、目标函数中的系数C,i,的灵敏度分析,分析,C,i,在什么范围内变化，,原最优解不变,C,1,=50 C,2,=100,E,A,D,C,B,F,直线BC 的斜截式为,：,x,2,=-x,1,+300,斜率为-1,直线BF 的斜截式为：,x,2,=0,x,1,+250,斜率为0,目标函数Z=c,1,x,1,+c,2,x,2,的,斜截式为：,x,=-c,1,/c,2,x,1,+z/c,2,斜率为,-c,1,/c,2,所以,当-1,-c,/c,0时，顶点B仍然是最优解,假设,c,2,不变,则有-1,-c,1,/,100,0，解之得0,c,1,100,，,练习,：,计算,C在什么范围内变化时顶,点B 仍然是最优解,2,、,约束条件右边b系数的灵敏度分析,b变化时通常引起可行域的变化从而引起最优解的变化。设例1中的设备台时增加了10个台时数,则约束变为：x,1,+x,2,310 代入求得新的最优解为x,1,=60,x,2,=250,Z=5060+100250=28000,比原来最大的利润27500增加了500元,可知每增加一个台时的设备可多获利润500/10=50元,在约束条件右边常量每增加一个单位而使最,优目标函数得到改进的量称为这个约束条件的,对偶价格,练习：,将原料A增加10千克计算最优解和最优值,某一约束条件的对偶价格仅仅在某一,范围内有效,总,结,当约束条件右边常数增加一个单位时：,(1)如果对偶价格大于零,则最优目标函数值得到改进,即求最大值时变得更大;求最小值时变得更小,(2)如果对偶价格小于零,则最优目标函数值变坏,即求最大值时变得小了;求最小值时变得大了,(3)如果对偶价格等于零,则最优目标函数值不变,练习,:,某,公司目前正生产甲乙两种产品,产量分别为,30个和120个,公司经理希望了解是否通过改变,这两种产品的数量而提高公司的利润.公司制造,每个产品所需的加工工时和各个车间的加工能,力如下表:,车间,产品甲,产品乙,车间能力(每天加工工时数),1,2,0,300,2,0,3,540,3,2,2,440,4,1.2,1.5,300,利润/每个产品(元),500,400,(1),假设生产的全部产品都能销售出去,用图解法确定,最优产品组合,(2)在上面求得的最优产品组合中,那些车间的能力还,有剩余,剩余多少?是剩余变量还是松弛变量?,(3)各车间的能力分别增加一个加工工时数给公司带,来多少额外的利润.,(4)当产品甲的利润不变时,产品乙的利润在什么范围,内变化时此最优解不变?当产品乙的利润不变时,产品甲的利润在什么范围内变化时最优解不变.,(5)当产品甲的利润从500降为450元,而产品乙的利润,从400元增加为430元时,原来产品组合是否依然是,最优产品组合.,2.3 LP的应用,一,.人力资源分配问题,例1.某昼夜服务的公交线路每天各时间段所需司机和乘务人员数如下：,班次,时间,所需人数,1,6：00,-10：00,60,2,10：00,-14：00,70,3,14：00,-18：00,60,4,18：00,-22：00,50,5,22：00-2：00,20,6,2：00-6：00,30,设司机和乘务人员分别在各时段一开始时上班,并连续工作8小时,问该公交线路怎样安排人员,既能满足工作需要又配备最少司机和乘务人员。,设x,i,表示第i班次开始上班的人员,s.t.,minZ=X,1,+X,2,+X,3,+X,4,+X,5,+X,6,X,1,+X,6,60,X,1,+X,2,70 X,2,+X,3,60,X,3,+X,4,50 X,4,+X,5,20 X,5,+X,6,30 X,1,X,2,X,3,X,4,X,5,X,6,0,最优解 ：,x,=50 x=20 x=50,x,=0 x=20 x=10,最优目标函数值,Z=150,【,练习,】,某中型百货商场对售货人员的需求统计如下表,并规定售货员每周工作5天且连续休息2天，问如何安排 人员的作息既满足工作需要又使配备人员最少？,时间,所需售货员人数,星期日,28,星期一,15,星期二,24,星期三,25,星期四,19,星期五,31,星期六,28,解：设x,1,为星期一开始休息的人数,x,2,为星期二开始休息的人数,x,7,为星期日开始休息的人数,目标函数:minZ=,x,1,+x,2,+x,3,+x,4,+x,5,+x,6,+x,7,x,1,+x,2,+x,3,+x,4,+x,5,28,x,2,+x,3,+x,4,+x,5,+x,6,15,x,3,+x,4,+x,5,+x,6,+x,7,24,x,4,+x,5,+x,6,+x,7,+,x,1,25,x,5,+x,6,+x,7,+,x,1,+x,2,19,x,6,+x,7,+,x,1,+x,2,+x,3,31,x,7,+,x,1,+x,2,+x,3,+x,4,28,x,i,0,最优解,：,x,1,=12,x,2,=0,x,3,=11,x,4,=5,x,5,=0,x,6,=8,x,7,=0,目标函数最小值为,：36,二 生产计划问题,例2、,某公司生产甲，乙，丙三种产品，这三种产品都要经过铸造，机加工和装配三个车间。甲乙两种产品的铸件可以外包协作也可自行生产，但丙产品必须本厂铸造才能保证质量。有关情况见下表；公司中可利用的总工时为铸造8000小时机加工12000小时和装配10000小时。公司为了获得最大利润，甲，乙，丙三种产品各生产多少件，甲乙两种产品的铸造应多少由本公司完成？多少由外包协作？,工时与成本,甲,乙,丙,每件铸造工时,5,10,7,每件机加工工时,6,4,8,每件装配工时,3,2,2,自产铸件每件成本,3,5,4,外协铸件每件成本,5,6,机加工每件成本,2,1,3,装配每件成本,3,2,2,每件产品售价,23,18,16,解：,设x,1，,x,2，,x,3,分别为三道工序都由本公司加工的,甲，乙，丙三种产品的件数，设x,4，,x,5,分别为由外,协铸造再由本公司机加工和装配的甲乙两种产品的,件数。,计算每件产品的利润分别如下：,产品甲全部自制的利润 =23-（3+2+3）=15,产品甲铸造外协，其余自制的利润=23-（5+2+3）=13,产品乙全部自制的利润 =18-（5+1+2）=10,产品乙铸造外协，其余自制的利润=18-（6+1+2）=9,产品丙的利润 =16-（4+3+2）=7,目标函数,：,max Z,=,15,X,1,+10X,2,+7X,3,+13 X,4,+9X,5,5X,1,+10X,2,+7X,3,8000,6,X,1,+4X,2,+8X,3,+6 X,4,+4X,5,12000,3X,1,+2X,2,+2 X,3,+3X,4,+2X,5,10000,X,1,X,2,X,3,X,4,X,5,0,三,套裁下料问题,例3、某工厂要做100套钢架，每套用29m、21m和15m的原钢各一根。已知原料每根长74m，问应如何下料，可使所用原料最省。,下料 方案,长度,29,1,2,0,1,0,21,0,0,2,2,1,15,3,1,2,0,3,合计,74,73,72,71,66,余料,0,01,02,03,08,设按各方案下料的原材料根数分别为,X,1,，X,2,，X,3,，X,4,，X,5,。,目标函数：min Z=,X,1,+X,2,+X,3,+X,4,+X,5,约束条件：,X,1,+2X,2,+X,4,100,2 X,3,+2X,4,+X,5,100,3X,1,+X,2,+2X,3,+3X,5,100,X,1,，X,2,，X,3,，X,4,，X,5,0,最优解,X,1,=30 X,2,=10 X,3,=0,X,4,=50 X,5,=0 Z=90,四、投资问题,例4、某部门现有资金200万元，今后五年内考虑以下的,项目投资，已知项目A：第一年到第五年年初都可投资，,当年末能收回本利110%。已知项目B：第一年到第四,年年初都可投资，次年末能收回本利125%，但规定每,年最大投资额不能超过30万元。项目C：第三年初需要,投资，到第五年末能回收本利140%，但规定最大投资,额不超过80万元。项目D：第二年初需要投资，到第五,年末能回收本利155%，但规定最大投资额不超过100万,元。,问,：应如何确定这些项目的每年投资，使得第五年,末拥有资金的本利和金额最大？,这是一个连续投资的问题，设：X,i j,=第i年初投资j项,目的金额，见表：,年份,项目,1,2,3,4,5,A,X,1A,X,2A,X,3A,X,4A,X,5A,B,X,1B,X,2B,X,3B,X,4B,C,X,3C,D,X,2D,目标函数：,maxz=11X,5A,125 X,4B,140X,3C,155 X,2D,X,1A,X,1B,=200，,X,2A,X,2B,X,2D,=,11X,1A,，,X,3A,X,3B,X,3C,=,11 X,2A,125X,1B,，,X,4A,X,4B,=,11 X,3A,125 X,2B,，,X,5A,=,11X,4A,125 X,3B,，,X,i B,30 （i=1，2，3，4），,X,3C,80，,X,2D,100，,X,i j,0，,五、配料问题,例5：,某工厂要用三种原料1、2、3混合调配出三种 不同规格的产品甲、乙、丙，数据如右表。问：,该厂应如何安排生产，使利润收入为最大？,解：设,x,ij,表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑：,对于甲：,x,11,，,x,12,，,x,13,；,对于乙：,x,21,，,x,22,，,x,23,；,对于丙：,x,31,，,x,32,，,x,33,；,对于原料1：,x,11,，,x,21,，,x,31,；,对于原料2：,x,12,，,x,22,，,x,32,；,对于原料3：,x,13,，,x,23,，,x,33,；,目标函数：利润最大，利润=收入-原料支出,约束条件：规格要求 4 个；,供应量限制 3 个,利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数量-甲乙丙使用的原料单价*原料数量，故有,目标函数,Max 50（,x,11,+,x,12,+,x,13,）+35（,x,21,+,x,22,+,x,23,）+25（,x,31,+,x,32,+,x,33,）-65（,x,11,+,x,21,+,x,31,）-25（,x,12,+,x,22,+,x,32,）-35（,x,13,+,x,23,+,x,33,）,=-15,x,11,+25,x,12,+15,x,13,-30,x,21,+10,x,22,-40,x,31,-10,x,33,约束条件：,从第1个表中有：,x,11,0.5(,x,11,+,x,12,+,x,13,),x,12,0.25(,x,11,+,x,12,+,x,13,),x,21,0.25(,x,21,+,x,22,+,x,23,),x,22,0.5(,x,21,+,x,22,+,x,23,),从第2个表中，生产甲乙丙的原材料不能超过原,材料的供应限额，故有,(,x,11,+,x,21,+,x,31,)100,(,x,12,+,x,22,+,x,32,)100,(,x,13,+,x,23,+,x,33,)60,习题,1、某,锅炉制造厂要制造一种新锅炉10台，每台锅炉需要不同长度的锅炉钢管数量如下：,规格（mm）,2640,1651,1770,1440,需要数量（根）,8,35,42,1,库存的原材料的长度只有5500mm一种规格，问,如何下料才能使总的用料根数最少？,2,.、,前进电器厂生产A，B，C三种产品有关资料如下表,：,产品,材料消耗,（千克/件）,台时消耗,（台时/件）,产品利润,（元/件）,市场容量,（件）,A,1.0,2,10,200,B,1.5,1.2,12,250,C,4.0,1,14,100,资源,限制,2000千克,1000台时,问:在资源及市场允许的条件下如何安排生产获利最大,3.,某公司在今后四个月内需租用仓库堆放物资,已知各个月所需的仓库面积数字如下表,：,月份,1,2,3,4,所需仓库面积,(百平方米),15,10,20,12,合同租借期限,1个月,2个月,3个月,4个月,合同期内每百平方米,仓库面积的租借费用,2800,4500,6000,7300,表2,表1,仓库的租借费用,当租借合同期限越长时,享受的折扣优惠也越大,具体数字如表2,租借仓库的合同每月初都可办理,每份合同具体规定租用面积数和期限.因此该厂可根据需要在任何一个月初办理租借合同,且每次办理可签一份也可同时签若干份租用面积和租借期限不同的合同.求一个所付的租借费为最小的租借方案.,设x,ij,(i=1,2,3,4)(j=1,4-i+1)为第i个月初签定的租,借期为j个月的合同的租界面积,minZ=2800 x,11,+4500 x,12,+6000 x,13,+7300 x,14,+2800 x,21,+,4500 x,22,+6000 x,23,+2800 x,31,+4500 x,32,+2800 x,41,x,11,+x,12,+x,13,+x,14,15,s.t x,12,+x,13,+x,14,+x,21,+x,22,+x,23,10,x,13,+x,14,+x,22,+x,23,+x,31,+x,32,20,x,14,+x,23,+x,32,+x,41,15,x,ij,0,4、,某公司从两个产地A,1,A,2,将货物运往三个销地B,1,B,2,B,3,各产地的产量及各销地的销量和各产地运往各销,地的每件物品的运费如下表,问如何调运使得总运输,费用最小?,运费 销地,单价,产地,B,1,B,2,B,3,产量,(件),A,1,6,4,6,200,A,2,6,5,5,300,销量,150,150,200,设x,ij,表示从产地A,i,调运到B,j,的运输量(i=1,2;j=1,2,3),min f=6x,11,+4x,12,+6x,13,+6x,21,+5x,22,+5x,23,x,11,+x,12,+x,13,=200,x,21,+x,22,+x,23,=300,x,11,+x,21,=150,x,12,+x,22,=150,x,13,+x,23,=200,x,ij,0,s.t.,班次,时间,所需人数,1,6：00,-10：00,15,2,10：00,-14：00,25,3,14：00,-18：00,20,4,18：00,-22：00,18,5,22：00-2：00,12,6,2：00-6：00,10,5、某医院昼夜24h各时段内需要的护士数量如下：,若医院可聘用合同工护士，上班时间同正式护士。护士,于每班开始上班，并连续工作8小时，若正式工护士报酬,为10元/h,合同工为15元/h,问医院是否应聘用合同工护士,及聘用多少名？,6、红英公司承诺为某建设项目从2003年起的4年中每年,年初分别提供以下数额的贷款：2003年100万元、2004年,150万元、2005年120万元、2006年110万元。为了充分发,挥这笔资金的作用，在满足每年贷款额的情况下，可将多,余资金分别用于下列投资项目：,（1）于2003年初购买A种债券，期限3年，到期后本息合计,为投资额的140%，但限购60万元。,（2）于2003年初购买B种债券，期限2年，到期后本息合计,为投资额的125%，但限购90万元。,（3）于2004年初购买C种债券，期限2年，到期后本息合计,为投资额的130%，但限购50万元。,（4）于年初将任意数额的资金存放于银行，年息4%，于,年底取出。,问：该公司应如何运用好这笔筹集到的资金，,使2002年底需筹集到的资金数额为最少？,7,、某厂生产甲乙丙丁四种产品，产品甲需经过A、B两,种机器加工，产品乙需经过A、C两种机器加工，产品,丙需经过B、C两种机器加工，产品丁需经过A、B两种,机器加工。有关数据如下，试为该厂制定一个最优的生,产计划。,产 品,机器生产率（件/小时）,原料成本,（元）,产品价,格（元）,A,B,C,甲,10,20,16,65,乙,20,10,25,80,丙,10,15,12,50,丁,20,10,18,70,机器成本 元/小时,200,150,225,每周可用小时数,150,120,70,8、某快餐店坐落于一个旅游景点，平时游客不多，而在,每周六游客猛增。该快餐店雇佣了两名正式员工，正式,员工每天工作8小时，其余工作由临时工来担任，临时,工每班工作4小时。根据游客就餐情况，在星期六每个,营业小时所需职工数（包括正式工和临时工）如下表。,已知一名正式工11点开始上班，工作4小时后休息1小时,而后再工作4小时；另一名正式工13点开始上班，工作4,小时后休息1小时，而后再工作4小时。又知临时工每小,时的工资为4元。在满足对职工需求的条件下，如何安,排临时工的班次，使得使用临时工的成本最小,？,时间,所需职工数,时间,所需职工数,11:00-12:00,9,17:00-18:00,6,12:00-13:00,9,18:00-19:00,12,13:00-14:00,9,19:00-20:00,12,14:00-15:00,3,20:00-21:00,7,15:00-16:00,3,21:00-22:00,7,16:00-17:00,3,x,2,x,3,x,4,x,5,1,3,x,3,x,4,x,5,x,6,2,3,x,4,x,5,x,6,x,7,1,6,x,5,x,6,x,7,x,8,2,12,x,6,x,7,x,8,x,9,2,12,x,7,x,8,x,9,x,10,1,7,x,8,x,9,x,10,x,11,1,7,min f,=,16,（,x,1,+,x,2,+,x,3,+,x,4,+,x,5,+,x,6,+,x,7,+,x,8,+,x,9,+,x,10,+,x,11,）,s,t,x,1,1,9,x,1,x,2,1,9,x,1,x,2,x,3,2,9,x,1,x,2,x,3,x,4,2,3,9、某厂按合同规定于当年每个季度末分别提供10、15、25、20台,同一规格的柴油机。已知该厂各季度的生产能力及每台柴油机的,成本如下表所示，又如果生产出来的柴油机当季不交货，每台每,积压一个季度需储存、维护等费用0.15元。要求在完成合同的情况,下，做出使该厂全年生产费用最小的决策。,季度,1,2,3,4,生产能力,25,35,30,10,单位成本（万元）,10.8,11.1,11.0,11.3,2.4 单纯形法基本原理及计算步骤,一、单纯形法的基本思路,从可行域中某一个顶点开始 判断此顶点是否是最优解，如不是则再找另一个使得目标函数值更优的顶点，称之为迭代。再判断此点是否是最优解。直到找到一个顶点为最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解,最优解一定在可行域的顶点上,将顶点坐标代入目标函数有:,(0,0):z=30+20=0,(5,0):z=35+20=15,(0,8):z=30+28=16,(2,6):z=32+26=18,单纯形法的基本思路就是基本可行解的转移，先找到一个初始基本可行解，如果不是最优解，设法转移到另一个基本可行解，并使目标函数值不断增加，直到找到最优解,。,(5,0),(2,6),10,8,3,0,2 5 8,x,2,(0,8),x,1,二、单纯形法计算步骤：,1、找出一个初始基本可行解,单纯形法中可行域的顶点叫做基本可行解，找,到的第一个基本可行解叫做初始基本可行解,目标函数 max Z=50,x,1,+100,x,2,x,1,+,x,2,+s,1,=300,2x,1,+,x,2,+s,2,=400,x,2,+s,3,=250,x,1,x,2,s,1,s,2,s,3,0,系数矩阵A=,1 1 1 0 0,2 1 0 1 0,0 1 0 0 1,由于A中存在一个不为零的三阶子式，可知A的秩为3,因为A的秩m小于此方程组的变量的个数 n，可知其有,无穷多组解,基本概念,基,：已知A是约束条件的mn系数矩阵，其秩,为m，若B是A中mm阶可逆矩阵，则称B 是线形规划问题中的一个基。B是由A中m个线形无关的系数列向量组成的。,本例中 1 1 1 与 1 0 0,2 1 0 0 1 0,0 1 0 0 0 1,都是该线性规划的一个基。它们都是由3个线性,无关的系数列向量组成。,基向量:基B中的一列称为一个基向量。基B中共有m,个基向量,非基向量:在A中除了基B之外的一切列称为基B,的,非基,向量,基变量:与基向量p,i,对应的变量x,i,叫做基变量,基变量有m个,非基变量:与非基向量p,j,对应的变量x,j,叫做非基变量,基,变量有n-m个.,例中对,基B,1,=1 1 1 来说 1 1 1,2 1 0 2 1 0,0 1 0 0 1 0,都是基B,1,的基向量,对应的变量x,1,x,2,s,1,叫做基变量,s,2,s,3,是基B,1,的非基变量.,例中对,基B,2,=1 0 0 来说 1 0 0,0 1 0 0 1 0,0 0 1 0 0 1,都是基B,2,的基向量,对应的变量s,1,s,2,s,3,叫做基变量,x,2,x,3,是基B,2,非基变量.,在约束方程系数矩阵中找到一个基,令这个基的非基变,量为零,再求解这个m元线性方程组就可得到唯一的解,了,这个解称之为线性规划的,基本解,.,例取B,3,=1 1 0,为A的一个基,令非基变量x,1,s,2,1 0 0,为零,这时约束方程就变为仅含,1 0 1,基变量的约束方程,.,x,2,+s,1,=300,求解得,x,2,=400 s,1,=-100 s,3,=-100,x,2,=400,x,1,=0 s,2,=0,x,2,+s,3,=250,由于,s,1,s,3,0,显然不是此线性规划的可行解,一个基本解可以是可行解,也可以是非可行解,它们之间,的主要区别在于其所有变量的解是否满足非负的条件.,把满足非负条件的一个基本解叫做基本可行解,并把这,样的基叫做可行基.,它们之间的关系,选B,1,=1 1 0,2 0 0,0 0 1,令其非基变量x,2,s,2,为零,约束方程,变为基变量的约束方程,x,1,+s,1,=300,2x,1,=400,s,3,=250,求解得到基变量的唯一解,基变量,s,3,=250,x,1,=200 s,1,=100,非基变量x,2,=0 s,2,=0,所有变量都大于等于零,此基本解为基本,可行解.,只要找到一个基是单位矩阵,或者说一个基是由单位,矩阵各列向量组成(列向量前后顺序无关紧要),那么所,求得的基本解一定是基本可行解.,练习:设B,2,为基,求一组基本解,并判别其是否为基本,可行解.,2、最优性检验-判断已求得的基本可行解是否,为最优解,最优性检验的依据-检验数,j,要求只用非基变量来表示目标函数,这只要在约束,等式中通过移项处理就可以用非基变量来表示基,变量,然后用非基变量的表示式代替目标函数中基,变量,这样目标函数中就只含非基变量了,或者说目,标函数中基变量的系数都为零了.此时目标函数中,所有变量的系数即为各变量的检验数,把变量x,i,的,检验数记为,i.,显然所有基变量的检验数必为零.,基变量的非基变量表达式：,令所有的非基变量取值为零，即，,由此求出初始基本可行解为：,把以上的表达式代入目标函数，就有,最优解判别定理,对于求最大目标函数的问题中,对于某个基本,可行解,如果所有检验数,j,0,则这个基本可,行解是最优解.,3、基变换,从可行基中换一个列向量,得到一个新的可行基,使得求解得到新的基本可行解,使得目标函数值更优.,（1）入基变量的确定,选检验数大于0的非,基变量换到基变量中去(称,为入基变量).若有两个以上的,j,0,则为了使目,标函数增加得更大些,一般选其中的,j,最大者的,非,基变量为入基变量,（2）出基变量的确定,把已确定的入基变量在各约束方程的系数除以,其所在约束方程中的常数项的值,把其中最小比,值所在的约束方程中的原基变量确定为出基变量.,单纯形法的表格形式,目标函数,max Z=50,x,1,+100,x,2,+0s,1,+0s,2,+0s,3,x,1,+,x,2,+s,1,=300,2x,1,+,x,2,+s,2,=400,x,2,+s,3,=250,x,1,x,2,s,1,s,2,s,3,0,基变量,C,B,x,1,x,2,s,1,s,2,s,3,B,-1,b,50,100,0,0,0,s,1,0,1,1,1,0,0,300,s,2,0,2,1,0,1,0,400,s,3,0,0,1,0,0,1,250,检验数,50,100,0,0,0,s,1,0,1,0,1,0,-1,50,s,2,0,2,0,0,1,-1,150,x,2,100,0,1,0,0,1,250,检验数,50,0,0,0,-100,x,1,50,1,0,1,0,-1,50,s,2,0,0,0,-2,1,1,50,x,2,100,0,1,0,0,1,250,检验数,0,0,-50,0,-50,单纯形法求解步骤：,找出：,k,=max,j,|,j,0,以a,lk,为中心元素进行迭代,列初始单纯形表,所有a,ik,0?,所有,j,0？,得到最优解,YES,YES,NO,NO,无界,结束,2.5 单纯形法的进一步讨论,大M法：,加入人工变量使系数构成单位矩阵，规定人工变量在目标函数中的系数为-M，这里M为任意大的数.这样只要人工变量大于零,所求的目标函数最大值就是一个任意小的数.这样为了使目标函数实现最大就必须把人工变量从基变量中换出.如果人工变量直到最后仍不能从基变量中换出,也就是说人工变量仍不为零,则该问题无可行解.,Minf=2x,1,+3x,2,x,1,+x,2,350,x,1,125,2x,1,+x,2,600,x,1,x,2,0,maxZ=-2x,1,-3x,2,x,1,+x,2,-s,1,=350,x,1,s,2,=125,2x,1,+x,2,+s,3,=600,x,1,x,2,s,1,s,2,s,3,0,令z=-f,maxZ=-2x,1,-3x,2,-M,a,1,-Ma,2,x,1,+x,2,-s,1,+a,1,=350,x,1,s,2,+a,2,=125,2x,1,+x,2,+s,3,=600,x,1,x,2,s,1,s,2,s,3,0,解的几种特殊情况,无可行解,若线性规划的最优解里有人工变量大于零,则该线性规划问题无可行解,目标函数：maxZ=20X,1,+30X,2,约束条件：3X,1,+10X,2,150 3X,1,+10X,2,+,S,1,=150,X,1,30 X,1,+,S,2,=30,X,1,+X,2,40 X,1,+X,2,-,S,3,=40,X,1,，X,2,0 X,1,，X,2,S,1,S,2,S,3,0,maxZ=20X,1,+30X,2,+0S,1,+,0S,2,+0S,3,-M a,1,3X,1,+10X,2,+,S,1,=150,X,1,+,S,2,=30,X,1,+X,2,-,S,3,+a,1,=40,X,1,，X,2,S,1,S,2,S,3,0,2 无界解,在某次迭代的单纯形表中,如果存在一个大,于零的检验数,j,并且该列的系数向量的每,个元素a,ij,(i=1,2,m)都小于或等于零,则此,线性规划问题是无界的.,maxZ=x,1,+x,2,x,1,-x,2,1,-3x,1,+2 x,2,6,x,1,x,2,0,maxZ=x,1,+x,2,+0s,1,+0 s,2,x,1,-x,2,+s,1,=1,-3x,1,+2 x,2,+s,2,=6,x,1,x,2,s,1,s,2,0,基,变量,C,B,X,1,X,2,S,1,S,2,b,比值,1 1 0 0,s,1,s,2,0,1 -1 1 0,1,6,1,0,-3 -2 0 1,z,j,c,j,-z,j,0 0 0 0,1 1 0 0,0,X,1,S,2,1,0,1 -1 1 0,0 -1 3 1,1,9,z,j,c,j,-z,j,1 -1 1 0,0 2 -1 0,1,3 无穷多最优解,对某个最优的基本,可行解,如果存在某个非基,变量的检验数为零,则此线性规划问题有无穷,多,最优解.,maxZ=50 x,1,+50 x,2,x,1,+x,2,300,2x,1,+x,2,400,x,2,250,x,1,，x,2,0,4 退化问题,特点：,(1)退化解的基变量中至少有一个取零值.,(2)退化迭代中基在不断变化,但是解不变.,(3)退化迭代不会引起目标函数值的变化.,勃兰特法则,:把松弛变量、人工变量都用X,j,表示,一般,松弛变量的下标号列在决策变量之后,人工变量的下,标号列在松弛变量之后,计算中遵循以下规则:,(1)在所有检验数大于零的非基变量中,选一个下标号最,小的作为入基变量.,(2)在存在两个和两个以上最小比值时,选一个下标号最,大的基变量为出基变量.,习题,1、已知LP问题 maxZ=x,1,+3x,2,x,1,+x,3,=5,x,1,+x,2,+x,4,10,x,2,+x,5,=4,x,i,0,下表所列的解均满足约束,指出那些是可行解,那些是基本解,那些是基本可行解,序号 x,1,x,2,x,3,x,4,x,5,a,2 4 3 0 0,b 10 0 -5 0 4,c 3 0 2 7 4,d 1 4.5 4 0 -0.5,e 0 2 5 6 2,f 0 4 5 2 0,2、,考虑下面给出的不完全初始单纯形表,迭代,次数,基变,量,C,B,x,1,x,2,x,3,s,1,s,2,s,3,b,6,30,25,0,0,0,0,3,1,0,1,0,0,40,0,2,1,0,1,0,50,2,1,-1,0,0,1,20,Z,j,C,j,-Z,j,把上面表格填写完整,按照上面完整的表格,写出此线性规划模型,这个初始解的基是什么,并写出这个初始解和其对应的目标函数值,在进行第一次迭代时确定入基变量和出基变量,并标明主元。,3、下表为用单纯形法计算时某一步的表格,已知,该线性规划的目标函数