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

《管理运筹学第2章线性规划与单纯形法.ppt》由会员分享，可在线阅读，更多相关《管理运筹学第2章线性规划与单纯形法.ppt（120页珍藏版）》请在三一办公上搜索。

1、第二章 线性规划与单纯形法,主讲教师:马越峰,第二章 线性规划与单纯形法,2.1线性规划问题与数学模型2.2图解法2.3线性规划的应用2.4单纯形法基本原理及计算步骤2.5单纯形法的进一步讨论2.6线性规划的对偶问题,2.1 线形规划(Linear Programming)问题及其数学模型,【引例】某工厂在计划期内要安排甲乙两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，以及资源的限制如下表所示：,问:工厂应分别生产多少个产品甲、乙才能使工厂获利最多？,设生产甲产品x1个，生产乙产品x2个,目标函数 max Z=50 x1+100 x2,约束条件,x1+x2 300,2

2、x1+x2 400,x2 250,x10,x2 0,线性规划模型,1.适用条件：（1）优化条件:问题目标最大化、最小化的要求；（2）约束条件:问题目标受一系列条件的限制；（3）选择条件:实现目标存在多种备选方案；（4）非负条件的选择:根据问题的实际意义决定是否非负。2.构建线性规划模型的步骤（1）科学选择决策变量（2）明确目标要求（3）根据实际问题的背景材料，找出所有的约束条件（4）确定是否增加决策变量的非负条件,线性规划模型表示形式,决策变量；,目标函数系数、价值系数或费用系数；,右端项或资源常数；,称为约束系数或技术系数。,（1）一般形式：,（2）集合形式：,（3）向量形式：,（4）矩阵形

3、式：,【例】将线性规划模型一般表达式化为矩阵形式。,解:,设:,例1.目标函数：Max z=50 x1+100 x2 约束条件：s.t.x1+x2 300(A)2 x1+x2 400(B)x2 250(C)x1 0(D)x2 0(E)得到最优解：x1=50，x2=250 最优目标值 z=27500,2图 解 法,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：,步骤：,(1)分别取决策变量X1,X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面

4、。,（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。,（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。,（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。,解的几种可能结果,唯一最优解解无穷多个最优解无界解(可行域无界，常为模型遗漏了某些必要的约束条件)无可行解（可行域为空集，约束条件自相矛盾,资源满足不了人们的需求）

5、,可行解：满足LP问题所有约束条件的解最优解：满足目标要求的可行解,四种结局:,无界解,无可行解：可行域为空集,增加的约束条件,线性规划标准形式,线性规划标准模型的一般表达式：,非标准形式标准化方法：,1.目标函数,2.约束条件为不等式:,引进松驰变量xs:,引进剩余变量xs:,4.决策变量为自由变量:,5.约束右端项为负:,两端乘-1:,0,3.约束条件为不等式:,引入松驰变量（含义是资源的剩余量）【引例】中引入 s1，s2，s3 模型化为 目标函数：Max z=50 x1+100 x2+0 s1+0 s2+0 s3 约束条件：s.t.x1+x2+s1=300 2 x1+x2+s2=400

6、x2+s3=250 x1,x2,s1,s2,s3 0 对于最优解 x1=50 x2=250，s1=0 s2=50 s3=0 说明：生产50单位产品和250单位产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。,【例】将线性规划模型转化为标准式,解:,无约束,(4)在第一、第三约束左端加上松弛变量x4,x60，在第二约束左端减去剩余变量x50,习题,1.用图解法求解下列LP问题（1）minZ=6x1+4x2(2)maxZ=3x1-2x2 2x1+x2 1 x1+x2 1 3x1+4x2 3 2x1+2x2 4 x1，x2 0 x1，x2 0,2、对下面LP问题(1)用图解法求

7、解(2)写出此问题的标准形式(3)求剩余变量的值 minZ=11x1+8x2 s.t.10 x1+2x2 20 3x1+3x2 18 4x1+9x2 36 x1,x2 0,图解法的灵敏度分析,1、目标函数中的系数Ci的灵敏度分析分析Ci在什么范围内变化，原最优解不变 C1=50 C2=100,E,A,D,C,B,F,直线BC 的斜截式为：x2=-x1+300 斜率为-1 直线BF 的斜截式为：x2=0 x1+250 斜率为0 目标函数Z=c1x1+c2x2的斜截式为：x=-c1/c2x1+z/c2 斜率为-c1/c2 所以,当-1-c/c0时，顶点B仍然是最优解 假设c2 不变,则有-1-c1

8、/100 0，解之得0 c1100,，,练习：计算C在什么范围内变化时顶 点B 仍然是最优解,2、约束条件右边b系数的灵敏度分析,b变化时通常引起可行域的变化从而引起最优解的变化。设例1中的设备台时增加了10个台时数,则约束变为：x1+x2310 代入求得新的最优解为x1=60,x2=250 Z=5060+100250=28000比原来最大的利润27500增加了500元,可知每增加一个台时的设备可多获利润500/10=50元,在约束条件右边常量每增加一个单位而使最优目标函数得到改进的量称为这个约束条件的对偶价格,练习：将原料A增加10千克计算最优解和最优值,某一约束条件的对偶价格仅仅在某一范围

9、内有效,总结,当约束条件右边常数增加一个单位时：(1)如果对偶价格大于零,则最优目标函数值得到改进,即求最大值时变得更大;求最小值时变得更小(2)如果对偶价格小于零,则最优目标函数值变坏,即求最大值时变得小了;求最小值时变得大了(3)如果对偶价格等于零,则最优目标函数值不变,练习:某公司目前正生产甲乙两种产品,产量分别为 30个和120个,公司经理希望了解是否通过改变 这两种产品的数量而提高公司的利润.公司制造 每个产品所需的加工工时和各个车间的加工能 力如下表:,(1)假设生产的全部产品都能销售出去,用图解法确定 最优产品组合(2)在上面求得的最优产品组合中,那些车间的能力还 有剩余,剩余多

10、少?是剩余变量还是松弛变量?(3)各车间的能力分别增加一个加工工时数给公司带 来多少额外的利润.(4)当产品甲的利润不变时,产品乙的利润在什么范围 内变化时此最优解不变?当产品乙的利润不变时,产品甲的利润在什么范围内变化时最优解不变.(5)当产品甲的利润从500降为450元,而产品乙的利润 从400元增加为430元时,原来产品组合是否依然是 最优产品组合.,2.3 LP的应用,一.人力资源分配问题例1.某昼夜服务的公交线路每天各时间段所需司机和乘务人员数如下：,设司机和乘务人员分别在各时段一开始时上班,并连续工作8小时,问该公交线路怎样安排人员,既能满足工作需要又配备最少司机和乘务人员。,设x

11、i表示第i班次开始上班的人员,s.t.,minZ=X1+X2+X3+X4+X5+X6 X1+X6 60 X1+X2 70 X2+X3 60 X3+X4 50 X4+X5 20 X5+X630 X1,X2,X3,X4,X5,X6 0,最优解：x=50 x=20 x=50 x=0 x=20 x=10 最优目标函数值 Z=150,【练习】某中型百货商场对售货人员的需求统计如下表,并规定售货员每周工作5天且连续休息2天，问如何安排 人员的作息既满足工作需要又使配备人员最少？,解：设x1为星期一开始休息的人数,x2为星期二开始休息的人数,x7为星期日开始休息的人数,目标函数:minZ=x1+x2+x3+

12、x4+x5+x6+x7,x1+x2+x3+x4+x528x2+x3+x4+x5+x615x3+x4+x5+x6+x724x4+x5+x6+x7+x125x5+x6+x7+x1+x219x6+x7+x1+x2+x3 31 x7+x1+x2+x3+x428 xi 0,最优解：x1=12 x2=0 x3=11 x4=5 x5=0 x6=8 x7=0 目标函数最小值为：36,二 生产计划问题,例2、某公司生产甲，乙，丙三种产品，这三种产品都要经过铸造，机加工和装配三个车间。甲乙两种产品的铸件可以外包协作也可自行生产，但丙产品必须本厂铸造才能保证质量。有关情况见下表；公司中可利用的总工时为铸造8000小

13、时机加工12000小时和装配10000小时。公司为了获得最大利润，甲，乙，丙三种产品各生产多少件，甲乙两种产品的铸造应多少由本公司完成？多少由外包协作？,解：设x1，x2，x3分别为三道工序都由本公司加工的 甲，乙，丙三种产品的件数，设x4，x5分别为由外 协铸造再由本公司机加工和装配的甲乙两种产品的 件数。计算每件产品的利润分别如下：产品甲全部自制的利润=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,目标函数：m

14、ax Z=15X1+10X2+7X3+13 X4+9X5,5X1+10X2+7X3 80006 X1+4X2+8X3+6 X4+4X5 12000 3X1+2X2+2 X3+3X4+2X5 10000X1,X2,X3,X4,X5 0,三 套裁下料问题,例3、某工厂要做100套钢架，每套用29m、21m和15m的原钢各一根。已知原料每根长74m，问应如何下料，可使所用原料最省。,设按各方案下料的原材料根数分别为X1，X2，X3，X4，X5。,目标函数：min Z=X1+X2+X3+X4+X5,约束条件：X1+2X2+X4100 2 X3+2X4+X5 100 3X1+X2+2X3+3X5 100

15、 X1，X2，X3，X4，X5 0,最优解X1=30 X2=10 X3=0 X4=50 X5=0 Z=90,四、投资问题,例4、某部门现有资金200万元，今后五年内考虑以下的项目投资，已知项目A：第一年到第五年年初都可投资，当年末能收回本利110%。已知项目B：第一年到第四年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元。项目C：第三年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过80万元。项目D：第二年初需要投资，到第五年末能回收本利155%，但规定最大投资额不超过100万元。问：应如何确定这些项目的每年投资，使得第五年末拥有资金的本利和金额最

16、大？,这是一个连续投资的问题，设：X i j=第i年初投资j项目的金额，见表：,目标函数：maxz=11X 5A125 X 4B 140X 3C155 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 j0，,五、配料问题,例5：某工厂要用三种原料1、2、3混合调配出三种 不同规格的产品甲、乙、丙，数据如右表。问：该厂应如何安

17、排生产，使利润收入为最大？,解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑：对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，x32，x33；对于原料1：x11，x21，x31；对于原料2：x12，x22，x32；对于原料3：x13，x23，x33；目标函数：利润最大，利润=收入-原料支出 约束条件：规格要求 4 个；供应量限制 3 个,利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数量-甲乙丙使用的原料单价*原料数量，故有目标函数Max 50（x11+x12+x13）+35（x21+x22+x23）+25

18、（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 约束条件：从第1个表中有：x110.5(x11+x12+x13)x120.25(x11+x12+x13)x210.25(x21+x22+x23)x220.5(x21+x22+x23),从第2个表中，生产甲乙丙的原材料不能超过原材料的供应限额，故有(x11+x21+x31)100(x12+x22+x32)100(x13+x23+x33)60,习题,1、某锅炉制造厂要制造一种新锅炉1

19、0台，每台锅炉需要不同长度的锅炉钢管数量如下：,库存的原材料的长度只有5500mm一种规格，问如何下料才能使总的用料根数最少？,2.、前进电器厂生产A，B，C三种产品有关资料如下表：,问:在资源及市场允许的条件下如何安排生产获利最大,3.某公司在今后四个月内需租用仓库堆放物资已知各个月所需的仓库面积数字如下表：,表2,表1,仓库的租借费用,当租借合同期限越长时,享受的折扣优惠也越大,具体数字如表2,租借仓库的合同每月初都可办理,每份合同具体规定租用面积数和期限.因此该厂可根据需要在任何一个月初办理租借合同,且每次办理可签一份也可同时签若干份租用面积和租借期限不同的合同.求一个所付的租借费为最小

20、的租借方案.,设xij(i=1,2,3,4)(j=1,4-i+1)为第i个月初签定的租借期为j个月的合同的租界面积,minZ=2800 x11+4500 x12+6000 x13+7300 x14+2800 x21+4500 x22+6000 x23+2800 x31+4500 x32+2800 x41 x11+x12+x13+x1415s.t x12+x13+x14+x21+x22+x2310 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x4115 xij 0,4、某公司从两个产地A1,A2将货物运往三个销地B1,B2B3,各产地的产量及各销地的销量和各产地

21、运往各销地的每件物品的运费如下表,问如何调运使得总运输费用最小?,设xij表示从产地Ai调运到Bj的运输量(i=1,2;j=1,2,3),min f=6x11+4x12+6x13+6x21+5x22+5x23 x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij0,s.t.,5、某医院昼夜24h各时段内需要的护士数量如下：,若医院可聘用合同工护士，上班时间同正式护士。护士于每班开始上班，并连续工作8小时，若正式工护士报酬为10元/h,合同工为15元/h,问医院是否应聘用合同工护士及聘用多少名？,6、红英公

22、司承诺为某建设项目从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%，于年底取出。,问：该

23、公司应如何运用好这笔筹集到的资金，使2002年底需筹集到的资金数额为最少？,7、某厂生产甲乙丙丁四种产品，产品甲需经过A、B两种机器加工，产品乙需经过A、C两种机器加工，产品丙需经过B、C两种机器加工，产品丁需经过A、B两种机器加工。有关数据如下，试为该厂制定一个最优的生产计划。,8、某快餐店坐落于一个旅游景点，平时游客不多，而在每周六游客猛增。该快餐店雇佣了两名正式员工，正式员工每天工作8小时，其余工作由临时工来担任，临时工每班工作4小时。根据游客就餐情况，在星期六每个营业小时所需职工数（包括正式工和临时工）如下表。已知一名正式工11点开始上班，工作4小时后休息1小时而后再工作4小时；另一名

24、正式工13点开始上班，工作4小时后休息1小时，而后再工作4小时。又知临时工每小时的工资为4元。在满足对职工需求的条件下，如何安排临时工的班次，使得使用临时工的成本最小？,9、某厂按合同规定于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及每台柴油机的成本如下表所示，又如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15元。要求在完成合同的情况下，做出使该厂全年生产费用最小的决策。,2.4 单纯形法基本原理及计算步骤,一、单纯形法的基本思路 从可行域中某一个顶点开始 判断此顶点是否是最优解，如不是则再找另一个使得目标函数值更优的顶

25、点，称之为迭代。再判断此点是否是最优解。直到找到一个顶点为最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解,最优解一定在可行域的顶点上,将顶点坐标代入目标函数有:(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),10830,2 5 8,x2,(0,8),x1,二、单纯形法计算步骤：1、找出一个初始基本可行解 单纯形法中可行域

26、的顶点叫做基本可行解，找到的第一个基本可行解叫做初始基本可行解,目标函数 max Z=50 x1+100 x2 x1+x2+s1=300 2x1+x2+s2=400 x2+s3=250 x1,x2,s1,s2,s3,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

27、 1 0 0 1 0 0 1 0 0 0 1 都是该线性规划的一个基。它们都是由3个线性 无关的系数列向量组成。,基向量:基B中的一列称为一个基向量。基B中共有m 个基向量非基向量:在A中除了基B之外的一切列称为基B的非基 向量基变量:与基向量pi对应的变量xi叫做基变量,基变量有m个非基变量:与非基向量pj对应的变量xj叫做非基变量,基 变量有n-m个.,例中对基B1=1 1 1 来说 1 1 1 2 1 0 2 1 0 0 1 0 0 1 0 都是基B1的基向量,对应的变量x1,x2,s1叫做基变量,s2,s3是基B1的非基变量.,例中对基B2=1 0 0 来说 1 0 0 0 1 0 0

28、 1 0 0 0 1 0 0 1 都是基B2的基向量,对应的变量s1,s2,s3叫做基变量,x2,x3是基B2非基变量.,在约束方程系数矩阵中找到一个基,令这个基的非基变量为零,再求解这个m元线性方程组就可得到唯一的解了,这个解称之为线性规划的基本解.,例取B3=1 1 0 为A的一个基,令非基变量x1,s2 1 0 0 为零,这时约束方程就变为仅含 1 0 1 基变量的约束方程.x2+s1=300 求解得x2=400 s1=-100 s3=-100 x2=400 x1=0 s2=0 x2+s3=250由于s1,s30,显然不是此线性规划的可行解,一个基本解可以是可行解,也可以是非可行解,它们

29、之间的主要区别在于其所有变量的解是否满足非负的条件.把满足非负条件的一个基本解叫做基本可行解,并把这样的基叫做可行基.,它们之间的关系,选B1=1 1 0 2 0 0 0 0 1,令其非基变量x2,s2为零,约束方程 变为基变量的约束方程,x1+s1=300 2x1=400 s3=250,求解得到基变量的唯一解,基变量s3=250 x1=200 s1=100 非基变量x2=0 s2=0所有变量都大于等于零,此基本解为基本可行解.,只要找到一个基是单位矩阵,或者说一个基是由单位矩阵各列向量组成(列向量前后顺序无关紧要),那么所求得的基本解一定是基本可行解.,练习:设B2为基,求一组基本解,并判别

30、其是否为基本 可行解.,2、最优性检验-判断已求得的基本可行解是否 为最优解最优性检验的依据-检验数j 要求只用非基变量来表示目标函数,这只要在约束等式中通过移项处理就可以用非基变量来表示基变量,然后用非基变量的表示式代替目标函数中基变量,这样目标函数中就只含非基变量了,或者说目标函数中基变量的系数都为零了.此时目标函数中所有变量的系数即为各变量的检验数,把变量xi的检验数记为i.显然所有基变量的检验数必为零.,基变量的非基变量表达式：,令所有的非基变量取值为零，即，,由此求出初始基本可行解为：,把以上的表达式代入目标函数，就有,最优解判别定理 对于求最大目标函数的问题中,对于某个基本 可行解

31、,如果所有检验数j0,则这个基本可 行解是最优解.,3、基变换,从可行基中换一个列向量,得到一个新的可行基,使得求解得到新的基本可行解,使得目标函数值更优.（1）入基变量的确定 选检验数大于0的非基变量换到基变量中去(称为入基变量).若有两个以上的j0,则为了使目标函数增加得更大些,一般选其中的j最大者的非基变量为入基变量,（2）出基变量的确定 把已确定的入基变量在各约束方程的系数除以 其所在约束方程中的常数项的值,把其中最小比 值所在的约束方程中的原基变量确定为出基变量.,单纯形法的表格形式,目标函数 max Z=50 x1+100 x2+0s1+0s2+0s3 x1+x2+s1=300 2

32、x1+x2+s2=400 x2+s3=250 x1,x2,s1,s2,s3,0,单纯形法求解步骤：,找出：k=maxj|j0,以alk为中心元素进行迭代,列初始单纯形表,所有aik0?,所有j0？,得到最优解,YES,YES,NO,NO,无界,结束,2.5 单纯形法的进一步讨论,大M法：加入人工变量使系数构成单位矩阵，规定人工变量在目标函数中的系数为-M，这里M为任意大的数.这样只要人工变量大于零,所求的目标函数最大值就是一个任意小的数.这样为了使目标函数实现最大就必须把人工变量从基变量中换出.如果人工变量直到最后仍不能从基变量中换出,也就是说人工变量仍不为零,则该问题无可行解.,Minf=2

33、x1+3x2 x1+x2350 x1 125 2x1+x2600 x1,x2 0,maxZ=-2x1-3x2 x1+x2-s1=350 x1 s2=125 2x1+x2+s3=600 x1,x2,s1,s2,s30,令z=-f,maxZ=-2x1-3x2-Ma1-Ma2 x1+x2-s1+a1=350 x1 s2+a2=125 2x1+x2+s3=600 x1,x2,s1,s2,s30,解的几种特殊情况,无可行解 若线性规划的最优解里有人工变量大于零,则该线性规划问题无可行解,目标函数：maxZ=20X1+30X2约束条件：3X1+10X2150 3X1+10X2+S1=150 X130 X1

34、+S2=30 X1+X240 X1+X2-S3=40 X1，X20 X1，X2,S1,S2,S30,maxZ=20X1+30X2+0S1+0S2+0S3-M a13X1+10X2+S1=150X1+S2=30X1+X2-S3+a1=40X1，X2,S1,S2,S30,2 无界解 在某次迭代的单纯形表中,如果存在一个大于零的检验数j,并且该列的系数向量的每个元素aij(i=1,2,m)都小于或等于零,则此线性规划问题是无界的.,maxZ=x1+x2 x1-x21-3x1+2 x26 x1,x20,maxZ=x1+x2+0s1+0 s2 x1-x2+s1=1-3x1+2 x2+s2=6 x1,x2

35、,s1,s2 0,3 无穷多最优解 对某个最优的基本可行解,如果存在某个非基变量的检验数为零,则此线性规划问题有无穷多最优解.,maxZ=50 x1+50 x2 x1+x2300 2x1+x2400 x2250 x1，x20,4 退化问题,特点：(1)退化解的基变量中至少有一个取零值.(2)退化迭代中基在不断变化,但是解不变.(3)退化迭代不会引起目标函数值的变化.,勃兰特法则:把松弛变量、人工变量都用Xj表示,一般 松弛变量的下标号列在决策变量之后,人工变量的下 标号列在松弛变量之后,计算中遵循以下规则:(1)在所有检验数大于零的非基变量中,选一个下标号最 小的作为入基变量.(2)在存在两个

36、和两个以上最小比值时,选一个下标号最 大的基变量为出基变量.,习题1、已知LP问题 maxZ=x1+3x2 x1+x3=5 x1+x2+x410 x2+x5=4 xi0下表所列的解均满足约束,指出那些是可行解,那些是基本解,那些是基本可行解,序号 x1 x2 x3 x4 x5 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、考虑下面给出的不完全初始单纯形表,把上面表格填写完整按照上面完整的表格,写出此线性规划模型这个初始解的基是什么,并写出这个初始解和其对应的目标函数值在进行第一次迭代

37、时确定入基变量和出基变量,并标明主元。,3、下表为用单纯形法计算时某一步的表格,已知 该线性规划的目标函数为maxZ=5x1+3x2 约束形式为,x3,x4为松弛变量.表中解代入目 标函数后得Z=10,填空并求a-g的值.,4、下表给出某线性规划问题计算过程中的一个单纯形表,目标函数为maxZ=28x4+x5+2x6.约束形式为,表中x1,x2,x3为松弛变量.表中解的目标函数值为Z=14，求a-g的值,5、下表为某求极大值线性规划问题的 初始单纯形表及迭代后的表,x4,x5为松弛变量.试求表中a-l的值及各变量下标m-t的值.,6、用单纯形法求解,7.、下表给出某求极大化问题的单纯形表。问表

38、中各 字母为何值时以及表中变量属哪一种类型时有：,表中解为唯一最优解表中解为无穷多最优解之一下一步迭代将以x1替换基变量x5该线性规划问题具有无界解该线性规划问题无可行解,2.6 线性规划的对偶问题,每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。例1 某工厂在计划期内安排、两种产品，生产单位产品所需设备A、B、C台时如表所示,该工厂每生产一单位产品 可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少 产品和产品，才能使工厂获利最多？,Max z=50 x1+100 x2,x1,x20,假如有另外一个工厂要求租用该厂的设备A、B

39、、C，那么该厂的厂长应该如何来确定合理的租金呢？,设 Y1,Y2，Y3分别为设备A、B、C的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。,目标函数：,这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。,1 求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，

40、有m个变量n个约束条件，其约束条件都为大于等于不等式。2 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i个约束条件的右边常数项就等于零对偶问题的目标函数中的第i个变量的系数。4 对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。,A=,如果我们用矩阵形式来表示，则有原问题：,对偶问题：,加上剩余变量 和人工变量，把此问题化成标准型如下：,从上面可知租金：A设备为50元，B设备为0元，C设备为50元。这样把工厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出租设备的最小费用，因为这是目 标函数的最小值。通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种设备的对偶价格，这在道理上也能讲得通。对于两个有对偶关系的线性规划的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最优值，因为这两个最优值相等。,下面来阐述如何写出一个线性规划问题的对偶问题：,令,当原线性规划问题的第i个约束条件取等号时，则其对偶问题的 i个决策变量没有非负限制。,