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

第二章 线性规划与单纯形法 主讲教师:马越峰 第二章 线性规划与单纯形法 n2.1线性规划问题与数学模型 n2.2图解法 n2.3线性规划的应用 n2.4单纯形法基本原理及计算步骤 n2.5单纯形法的进一步讨论 n2.6线性规划的对偶问题 2.1 线形规划(Linear Programming)问题及 其数学模型 【引例】某工厂在计划期内要安排甲乙两种产品的生 产，已知生产单位产品所需的设备台时及A、B两种 原材料的消耗，以及资源的限制如下表所示： 甲乙资源限制 设备11300台时 原料A21400千克 原料B01250千克 单件利润50（元/件）100（元/件） 问:工厂应分别生产多少个产品甲、乙才能使工厂获利最多？ 设生产甲产品x1个，生产乙产品x2个 目标函数 max Z= 50 x1+100x2 约 束 条 件 x1+x2 300 2x1+x2 400 x2 250 x10,x2 0 线性规划模型 n1.适用条件： n（1）优化条件:问题目标最大化、最小化的要求； n（2）约束条件:问题目标受一系列条件的限制； n（3）选择条件:实现目标存在多种备选方案； n（4）非负条件的选择:根据问题的实际意义决定是否非负。 n2. 构建线性规划模型的步骤 n（1）科学选择决策变量 n（2）明确目标要求 n（3）根据实际问题的背景材料，找出所有的约束条件 n（4）确定是否增加决策变量的非负条件 线性规划模型表示形式 决策变变量； 目标标函数系数、价值值系数或费费用系数； 右端项项或资资源常数； 称为约为约 束系数或技术术系数。 （1）一般形式： （2）集合形式： （3）向量形式： （4）矩阵形式： 【例】 将线线性规规划模型一般表达式化为为矩阵阵形式。 解 : 设: 例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的每个约束条件都代表一个半平面。 x2 x1 X20 X2=0 x2 x1 X10 X1=0 （2）对每个不等式(约束条件)，先取其等式在坐标系中作 直线，然后确定不等式所决定的半平面。 100 200 300 100200300 x1+x2300 x1+x2=300 100 100200 2x1+x2400 2x1+x2=400 300 200 300 400 （3）把五个图合并成一个图，取各约束条件的公共部分，如 图2-1所示。 100 100 x2250 x2=250 200300 200 300 x1 x2 x2=0 x1=0 x2=250 x1+x2=300 2x1+x2=400 图2-1 （4）目标函数z=50x1+100x2，当z取某一固定值时得到一条 直线，直线上的每一点都具有相同的目标函数值，称之为 “等值线”。平行移动等值线，当移动到B点时，z在可行域 内实现了最大化。A，B，C，D，E是可行域的顶点，对 有限个约束条件则其可行域的顶点也是有限的。 x1 x2 z=20000=50x1+100x2 图2-2 z=27500=50x1+100x2 z=0=50x1+100x2 z=10000=50x1+100x2 C B A D E 解的几种可能结果 唯一最优解解 无穷多个最优解 无界解(可行域无界，常为模型遗漏了某些必 要的约束条件) 无可行解（可行域为空集，约束条件自相矛 盾,资源满足不了人们的需求） 可行解：满足LP问题所有约束条件的解 最优解：满足目标要求的可行解 四种结结局: x1 x2 唯一最优解 x2 x1 无穷多最优解 x1 x2 无界解 x2 x1 无可行解 无界解 无可行解：可行域为空集 增加的约束条件 线性规划标准形式 线线性规规划标标准模型的一般表达式： 非标标准形式标标准化方法： 1.目标标函数 2.约约束条件为为不等式: 引进进松驰变驰变 量xs: 引进进剩余变变量xs: 4.决策变变量为为自由变变量: 5.约约束右端项为负项为负 : 两端乘-1: 0 3.约约束条件为为不等式: n引入松驰变量（含义是资源的剩余量） 【引例】中引入 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 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 习题 n1.用图解法求解下列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)用图解法求解 (2)写出此问题的标准形式 (3)求剩余变量的值 minZ=11x1+8x2 s.t. 10x1+2x2 20 3x1+3x2 18 4x1+9x2 36 x1,x2 0 图解法的灵敏度分析 n1、目标函数中的系数Ci的灵敏度分析 分析Ci在什么范围内变化，原最优解不变 C1=50 C2=100 E A D C B F 直线BC 的斜截式为：x2= -x1 +300 斜率为-1 直线BF 的斜截式为：x2= 0x1 +250 斜率为0 目标函数Z=c1x1+c2x2的斜截式为： x= -c1/c2x1 +z/c2 斜率为-c1/c2 所以,当-1 -c/c0时，顶点B仍然是 最优解 假设c2 不变,则有-1 -c1/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千克计算最优解和最优值 某一约束条件的对偶价格仅仅在某一 范围内有效 总 结 当约束条件右边常数增加一个单位时： (1)如果对偶价格大于零,则最优目标函数值得到改进 ,即求最大值时变得更大;求最小值时变得更小 (2)如果对偶价格小于零,则最优目标函数值变坏,即 求最大值时变得小了;求最小值时变得大了 (3)如果对偶价格等于零,则最优目标函数值不变 练习:某公司目前正生产甲乙两种产品,产量分别为 30个和120个,公司经理希望了解是否通过改变 这两种产品的数量而提高公司的利润.公司制造 每个产品所需的加工工时和各个车间的加工能 力如下表: 车间车间产产品甲产产品乙车间车间 能力(每天加工工时时 数) 120300 203540 322440 41.21.5300 利润润/每个产产品(元)500400 (1)假设生产的全部产品都能销售出去,用图解法确定 最优产品组合 (2)在上面求得的最优产品组合中,那些车间的能力还 有剩余,剩余多少?是剩余变量还是松弛变量? (3)各车间的能力分别增加一个加工工时数给公司带 来多少额外的利润. (4)当产品甲的利润不变时,产品乙的利润在什么范围 内变化时此最优解不变?当产品乙的利润不变时, 产品甲的利润在什么范围内变化时最优解不变. (5)当产品甲的利润从500降为450元,而产品乙的利润 从400元增加为430元时,原来产品组合是否依然是 最优产品组合. 2.3 LP的应用 n一.人力资源分配问题 n例1.某昼夜服务的公交线路每天各时间段所需司 机和乘务人员数如下： 班次 时间 所需人数 1 6：00-10：0060 2 10：00 -14：0070 3 14：00 -18：0060 4 18：00 -22：0050 5 22：00-2：0020 6 2：00-6：0030 设司机和乘务人员分别在各时段一开始时上班, 并连续工作8小时,问该公交线路怎样安排人员, 既能满足工作需要又配备最少司机和乘务人员。 设xi表示第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天，问如何安排 人员的作息既满足工作需要又使配备人员最少？ 时间所需售货员人数 星期日28 星期一15 星期二24 星期三25 星期四19 星期五31 星期六28 解：设x1为星期一开始休息的人数,x2为星期二开 始休息的人数, x7为星期日开始休息的人数 目标函数:minZ=x1+x2+x3+x4+x5+x6+x7 x1+x2+x3+x4+x528 x2+x3+x4+x5+x615 x3+x4+x5+x6+x724 x4+x5+x6+x7 + x125 x5+x6+x7 + x1+x219 x6+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小时机加工12000小时和 装配10000小时。公司为了获得最大利润， 甲，乙，丙三种产品各生产多少件，甲乙两 种产品的铸造应多少由本公司完成？多少由 外包协作？ 工时时与成本甲乙丙 每件铸铸造工时时510 7 每件机加工工时时648 每件装配工时时322 自产铸产铸 件每件成 本 354 外协铸协铸 件每件成 本 56 机加工每件成本213 装配每件成本322 每件产产品售价231816 解：设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 目标函数：max Z= 15X1 +10X2+ 7X3 +13 X4+9X5 5X1 + 10X2 + 7X3 8000 6 X1 + 4X2 + 8X3 +6 X4+4X5 12000 3X1 + 2X2 +2 X3 + 3X4+2X5 10000 X1 ,X2 , X3,X4,X5 0 三 套裁下料问题 n例3、某工厂要做100套钢架，每套用29m、 21m和15m的原钢各一根。已知原料每根长 74m，问应如何下料，可使所用原料最省。 下料 方案 长度 2912010 2100221 1531203 合计7473727166 余料001020308 设按各方案下料的原材料根数分别为 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 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万 元。问：应如何确定这些项目的每年投资，使得第五年 末拥有资金的本利和金额最大？ 这是一个连续投资的问题，设：X i j=第i年初投资j项 目的金额，见表： 年份 项项目 12345 A X 1AX 2AX 3AX 4AX 5A B X 1BX 2BX 3BX 4B C X 3C D X 2D 目标函数： 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混合调配出三种 不同规格的产品甲、乙、丙，数据如右表。问： 该厂应如何安排生产，使利润收入为最大？ 解：设 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 个 n利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数 量-甲乙丙使用的原料单价*原料数量，故有 目标函数 Max 50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）- 65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33） = -15x11+25x12+15x13-30x21+10x22-40x31-10x33 约束条件： 从第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、某锅炉制造厂要制造一种新锅炉10台，每台锅 炉需要不同长度的锅炉钢管数量如下： 规格（mm）2640165117701440 需要数量（根）835421 库存的原材料的长度只有5500mm一种规格，问 如何下料才能使总的用料根数最少？ 2.、前进电器厂生产A，B，C三种产品有关资料如下表： 产产品材料消耗 （千克/件 ） 台时时消耗 （台时时/件 ） 产产品利 润润 （元/件 ） 市场场容量 （件） A1.0210200 B1.51.212250 C4.0114100 资资源 限制 2000千克1000台时时 问:在资源及市场允许的条件下如何安排生产获利最大 3.某公司在今后四个月内需租用仓库堆放物资 已知各个月所需的仓库面积数字如下表： 月份1234 所需仓库仓库 面积积 (百平方米) 15102012 合同租借期限1个月 2个月 3个月 4个月 合同期内每百平方米 仓库仓库 面积积的租借费费 用 2800450060007300 表2 表1 仓库的租借费用,当租借合同期限越长时,享受 的折扣优惠也越大,具体数字如表2,租借仓库的 合同每月初都可办理,每份合同具体规定租用 面积数和期限.因此该厂可根据需要在任何一 个月初办理租借合同,且每次办理可签一份也 可同时签若干份租用面积和租借期限不同的合 同.求一个所付的租借费为最小的租借方案. 设xij(i=1,2,3,4)(j=1, 4-i+1)为第i个月初签定的租 借期为j个月的合同的租界面积 minZ=2800x11+4500x12+6000x13+7300x14+2800x21+ 4500x22+6000x23+ 2800x31+4500x32+2800x41 x11+x12+x13+x1415 s.t x12+x13+x14 +x21+x22+x2310 x13+x14 +x22+x23+x31+x32 20 x14+x23+x32+x4115 xij 0 4、某公司从两个产地A1,A2将货物运往三个销地B1,B2 B3,各产地的产量及各销地的销量和各产地运往各销 地的每件物品的运费如下表,问如何调运使得总运输 费用最小? 运费费 销销地 单单价 产产地 B1B2B3产产量 (件) A1646200 A2655300 销销量150150200 设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. 班次 时间 所需人数 1 6：00-10：0015 2 10：00 -14：0025 3 14：00 -18：0020 4 18：00 -22：0018 5 22：00-2：0012 6 2：00-6：0010 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两种 机器加工。有关数据如下，试为该厂制定一个最优的生 产计划。 产 品机器生产率（件/小时 ） 原料成本 （元） 产品价 格（元 ）ABC 甲10201665 乙20102580 丙10151250 丁20101870 机器成本 元/小 时 200150225 每周可用小时数 15012070 8、某快餐店坐落于一个旅游景点，平时游客不多，而在 每周六游客猛增。该快餐店雇佣了两名正式员工，正式 员工每天工作8小时，其余工作由临时工来担任，临时 工每班工作4小时。根据游客就餐情况，在星期六每个 营业小时所需职工数（包括正式工和临时工）如下表。 已知一名正式工11点开始上班，工作4小时后休息1小时 而后再工作4小时；另一名正式工13点开始上班，工作4 小时后休息1小时，而后再工作4小时。又知临时工每小 时的工资为4元。在满足对职工需求的条件下，如何安 排临时工的班次，使得使用临时工的成本最小？ 时间时间所需职职工数时间时间所需职职工数 11:00-12:00917:00-18:006 12:00-13:00918:00-19:0012 13:00-14:00919:00-20:0012 14:00-15:00320:00-21:007 15:00-16:00321:00-22:007 16:00-17:003 x2x3x4x51 3 x3x4x5x62 3 x4x5x6x71 6 x5x6x7x82 12 x6x7x8x92 12 x7x8x9x101 7 x8x9x10x111 7 min f=16（x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11） st x11 9 x1 x21 9 x1 x2x32 9 x1x2x3x42 3 9、某厂按合同规定于当年每个季度末分别提供10、15、25、20台 同一规格的柴油机。已知该厂各季度的生产能力及每台柴油机的 成本如下表所示，又如果生产出来的柴油机当季不交货，每台每 积压一个季度需储存、维护等费用0.15元。要求在完成合同的情况 下，做出使该厂全年生产费用最小的决策。 季度1234 生产产能力25353010 单单位成本（万元）10.811.111.011.3 2.4 单纯形法基本原理及计算步骤 一、单纯形法的基本思路 从可行域中某一个顶点开始 判断此顶点是否 是最优解，如不是则再找另一个使得目标函 数值更优的顶点，称之为迭代。再判断此点 是否是最优解。直到找到一个顶点为最优解 ，就是使得其目标函数值最优的解，或者能 判断出线性规划问题无最优解 n最优解一定在可行域的顶点上, 将顶点坐标代入目标函数有: n(0,0):z=30+20=0 n(5,0):z=35+20=15 n(0,8):z=30+28=16 n(2,6):z=32+26=18 n单纯形法的基本思路就是基本 可行解的转移，先找到一个初 始基本可行解，如果不是最优 解，设法转移到另一个基本可 行解，并使目标函数值不断增 加，直到找到最优解。 (5,0) (2,6) 10 8 3 0 2 5 8 x2 (0,8) x1 二、单纯形法计算步骤： 1、找出一个初始基本可行解 1. 单纯形法中可行域的顶点叫做基本可行解，找 2.到的第一个基本可行解叫做初始基本可行解 目标函数 max Z= 50 x1+100x2 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 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 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,显然不是此线性规划的可行解 一个基本解可以是可行解,也可以是非可行解,它们之间 的主要区别在于其所有变量的解是否满足非负的条件. 把满足非负条件的一个基本解叫做基本可行解,并把这 样的基叫做可行基. 它们之间的关系 选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为基,求一组基本解,并判别其是否为基本 可行解. 1. 2、最优性检验-判断已求得的基本可行解是否 2. 为最优解 3. 最优性检验的依据-检验数j 4. 5. 要求只用非基变量来表示目标函数,这只要在约束 6. 等式中通过移项处理就可以用非基变量来表示基 7. 变量,然后用非基变量的表示式代替目标函数中基 8. 变量,这样目标函数中就只含非基变量了,或者说目 9. 标函数中基变量的系数都为零了.此时目标函数中 10.所有变量的系数即为各变量的检验数,把变量xi的 11.检验数记为i.显然所有基变量的检验数必为零. 基变量的非基变量表达式： 令所有的非基变量取值为零，即， 由此求出初始基本可行解为： 把以上的表达式代入目标函数，就有 最优解判别定理 对于求最大目标函数的问题中,对于某个基本 可行解,如果所有检验数j0,则这个基本可 行解是最优解. 3、基变换 n从可行基中换一个列向量,得到一个新的可行基 ,使得求解得到新的基本可行解,使得目标函数 值更优. （1）入基变量的确定 选检验数大于0的非基变量换到基变量中去(称 为入基变量).若有两个以上的j0,则为了使目 标函数增加得更大些,一般选其中的j最大者的非 基变量为入基变量 （2）出基变量的确定 把已确定的入基变量在各约束方程的系数除以 其所在约束方程中的常数项的值,把其中最小比 值所在的约束方程中的原基变量确定为出基变量. 单纯形法的表格形式 目标函数 max Z= 50 x1+100x2 +0s1 +0s2 +0s3 x1+x2+s1 =300 2x1+x2 +s2 =400 x2 +s3=250 x1,x2, s1, s2, s3, 0 基变量CBx1x2s1s2s3B-1b 50100000 s1011100300 s2021010400 s3001001250 检验数50100000 s101010-150 s202001-1150 x210001001250 检验数50000-100 x1501010-150 s2000-21150 x210001001250 检验数00-500-50 单纯形法求解步骤： 找出：k=maxj|j0 以alk为为中心元素进进行迭代 列初始单纯单纯 形表 所有aik0? 所有j0？ 得到最优优解 YES YES NO NO 无界 结结束 2.5 单纯形法的进一步讨论 n大M法： n加入人工变量使系数构成单位矩阵，规定人工变量在目标 函数中的系数为-M，这里M为任意大的数.这样只要人工 变量大于零,所求的目标函数最大值就是一个任意小的数. 这样为了使目标函数实现最大就必须把人工变量从基变量 中换出.如果人工变量直到最后仍不能从基变量中换出,也 就是说人工变量仍不为零,则该问题无可行解. Minf=2x1+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 解的几种特殊情况 n无可行解 若线性规划的最优解里有人工变量大于零, 则该线性规划问题无可行解 目标函数：maxZ=20X1+30X2 约束条件：3X1+10X2150 3X1+10X2+ S1 =150 X130 X1 + S2 =30 X1+X240 X1+X2 - S3 =40 X1，X20 X1，X2,S1,S2,S30 maxZ=20X1+30X2+ 0S1 + 0S2 +0S3 -M a1 3X1+10X2+ S1 =150 X1 + S2 =30 X1+X2 - S3 +a1=40 X1，X2,S1,S2,S30 n2 无界解 在某次迭代的单纯形表中,如果存在一个大 于零的检验数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, s1 , s2 0 基 变变量 CBX1X2S1S2 b 比值值 1 1 0 0 s1 s2 0 1 -1 1 0 1 6 1 0 -3 -2 0 1 zj cj-zj 0 0 0 0 1 1 0 0 0 X1 S2 1 0 1 -1 1 0 0 -1 3 1 1 9 zj cj-zj 1 -1 1 0 0 2 -1 0 1 n 3 无穷多最优解 对某个最优的基本可行解,如果存在某个非基 变量的检验数为零,则此线性规划问题有无穷 多最优解. maxZ=50x1+50x2 x1+x2300 2x1+x2400 x2250 x1，x20 4 退化问题 特点： (1)退化解的基变量中至少有一个取零值. (2)退化迭代中基在不断变化,但是解不变. (3)退化迭代不会引起目标函数值的变化. 勃兰特法则:把松弛变量、人工变量都用Xj表示,一般 松弛变量的下标号列在决策变量之后,人工变量的下 标号列在松弛变量之后,计算中遵循以下规则: (1)在所有检验数大于零的非基变量中,选一个下标号最 小的作为入基变量. (2)在存在两个和两个以上最小比值时,选一个下标号最 大的基变量为出基变量. 习题 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、考虑下面给出的不完全初始单纯形表 迭代 次数 基变变 量 CBx1x2x3s1s2s3b 63025000 0 31010040 02101050 21-100120 Zj Cj-Zj (1)把上面表格填写完整 (2)按照上面完整的表格,写出此线性规划模型 (3)这个初始解的基是什么,并写出这个初始解 和其对应的目标函数值 (4)在进行第一次迭代时确定入基变量和出基变 量,并标明主元。 3、下表为用单纯形法计算时某一步的表格,已知 该线性规划的目标函数为maxZ=5x1+3x2 约束形式为,x3, x4为松弛变量.表中解代入目 标函数后得Z=10,填空并求a-g的值. 基 变变量 CBx1x2x3x4bj x3 x1 c011/53 de01a jb-1fg 4、下表给出某线性规划问题计算过程中的一个 单纯形表,目标函数为maxZ=28x4+x5+2x6.约束形式 为,表中x1,x2,x3为松弛变量.表中解的目标函数 值为Z=14，求a-g的值 基 变量 CBx1x2x3x4x5x6bj x630-14/3011a x26d205/205 x40ef1000 j b c 0 0 -1 g 基变变 量 x1 x2x3x4x5bj c1c2c3 xm xn b c d 1 0 -1 3 e 0 1 6 1 j a -1 2 0 0 xs xt g 2 2 1/2 0 h i 1 1/2 1 f 4 j 0 -7 j k l 5、下表为某求极大值线性规划问题的 初始单纯 形表及迭代后的表,x4, x5为松弛变量.试求表中 a-l的值及各变量下标m-t的值. 6、用单纯形法求解 7. 、下表给出某求极大化问题的单纯形表。问表中各 字母为何值时以及表中变量属哪一种类型时有：