提高经济效益的线性规划法.ppt

第三章 提高经济效益的 线性规划法,增收节支的两类问题 两变量线性规划的图解法 一般线性规划的单纯形法 应用和推广 线性规划的进一步发展 敏感性分析,第一节 增收节支的两类问题,【例1 】某厂生产甲、乙两种产品，均需经过金工和装配两个车间的加工，有关数据如下。如何决定甲、乙的产量，在满足金工、装配车间现有生产能力的条件下，使总收益为最大。,明确有待决定的未知变量（决策变量）， 设甲产品生产x1件、乙产品生产x2件；,明确问题中所有的限制条件（约束条件），并用决 策变量的关系式来表示。,金工车间：,装配车间：,两类问题,明确目标，用决策变量的关系式表示。,总收益值与甲、乙产量的关系是,产品产量不能为负数，即,综上,两类问题,【例2 】某汽车出租公司有a、b两种 类型的载重车，每种车型的可用于冷藏、非冷藏的体积及每公里租费如下表所示。有一食品工厂，欲把至少为900单位体积的冷藏产品和至少为1200单位体积的非冷藏产品委托出租汽车公司运输到某一仓库，究竟如何决定a、b型车的租用量，在确保各种食品都能运出的前提下，所支付的总运输费用最小。,两类问题,设 a、b型车的租用量分别为x1、x2辆，,两类问题,线性规划模型： 包含若干个决策变量； 求决策变量组成的线性目标函数的极大值或极小值； 所有约束条件是决策变量的线性等式或不等式组； 决策变量一般来说取值非负。,一般形式,两类问题,基本概念,可行解(可行方案)及可行域 可行方案:企业全部经济背景所允许的。 可行解：满足全部约束条件的变量的一组取值。,甲、乙产品各生产x1=20,x2=20，,可行解,可行解一般不唯一。 可行解的全体称为线性规划问题的可行域，记为d。,两类问题,2.最优解（最优方案）,最优方案:在一切可行方案中，能带来最大收益（或 最小支付）的方案。,两类问题,最优解:在一切可行解中，有最大（或最小）目标函 数的可行解。,上例的可行解,对应的目标值,第二节 两变量线性规划的图解法,例1,作直角坐标系， 画出第一象限。,画出约束所对应的 区域,(1)画出可行域,-可行域。,(2)作出收益线，平移 收益线。,e,(3)求出最优解。,3. 无可行解（可行域为空集）,4 .有无界解( 无有限最优解或无最优解 ),一、单纯形法的直观背景,第三节 一般线性规划的单纯形法,【例3】文教用品厂，利用白坯纸生产信封、公文袋、便条纸。每单位产品的收益值、劳动力消耗、原料消耗及人力、原料总量如下表。,设x1、x2分别代表甲、乙、丙的产量。,（一）引进松弛变量，实现线性规划标准化,标准型线性规划 所有变量取值非负； 约束全部为等式； 约束条件有端常数全部非负。,标准型的一般形式,（二）在典型的前提下，求出初始基本可行解,回顾：,典型线性方程组：每一个方程中都有系数为1，并且不出现在其它方程中的一个变量。 变量：基本变量、非基本变量。 基本解：非基变量取值为零，所得到的解。,典型线性规划： 标准型线性规划，约束方程组式典型方程组。,方便取可行解,基本可行解： 可行解； 基本解。,初始基本可行解。,意义？,（三 ）改进初始基本可行解,相对收益系数最大的非基变量进基原则 极小比值对应的基变量出基原则 初等变换实现进出基交换（旋转变换）,1.进基原则,非基变量,甲：,非基变量x1的相对收系数,不生产甲生产1单位甲，目标函数值增加 2,？,2.出基原则,劳动力限制,全部劳动力用来生产乙，,最多能生产,全部白坯纸用来生产乙，,原材料限制,最多能生产,全部白坯纸用来生产乙，剩余量为0，劳动力有剩余。,原非基变量x2 进基，原基变量x5 出基,3. 初等变换实现进出基交换（旋转变换）,令x1=x3=x5=0,得 x4=25, x2=225,（四）再次改进基本可行解 按照上述改进初始基本可行解的步骤，对得到的基可行解进一步改进。,（五）最优性准则,当全部非基变量的相对收益系数非正。,目标函数：求最大收益，相对收益系数； 目标函数：求最小支出，,相对支出系数；,（1）引进松弛变量，化不等式为等式，使线性规划标准化；,（2）如果线性规划是典型的，建立初始单纯形表；,（4）选最大正值的j对应的非基变量进基；,二、单纯形法的表格化,（3）求非基变量的相对收益系数，若全部 j 0，则已 得到最优解，停止计算，否则转入下一步；,（5）根据极小比值，确定出基变量；,（6）进基变量列与出基变量行相交的元素为枢元，实 施初等变换，使枢元成为本列中唯一的非零元素 （取值为1），转（3）。,（步骤）,单纯形法,计算j,选进基变量：选最大的（正的）相对收益系数的变 量为进基变量；,选出基变量：作比值，注意0及负系数不能做分母，,单纯形法,初等行变换：进基变量列与出基变量行相交处为枢元。,0 1 0,1/4 2 0 1/4 225,1/4 -1/3 1 -1/12 25,5/4 -5 0 -3/4 -675,得基可行解：x1=(0, 225 , 0, 25, 0)t ,目标函数z=675,是否最优解？,单纯形法,0 -4/3 4 -1/3 100,1 7/3 -1 1/3 200,0 -10/3 -5 - 1/3 - 800,全部相对收益系数（检验数） j 0，得最优解。,最优值,最优方案？,单纯形法,【例3 】用单纯形法求解,解：引入松弛变量 x3, x4, x5，模型标准化,单纯形法,单纯形法,0 0 0 1 3,1 0 1 -2 2,1 1 0 -1 3,3 0 0 -4 -12,最优解： x*=x(3) =(4,2,0,0,1)t 最优值 z*=20,实际意义?,单纯形法,三、实现线性规划典型化的大m 法,松弛变量的引入可以实现标准化，但不能确保典型化。初始单纯形表？,-大m法。,引入松弛变量，标准化。,引入人工变量x5，x6，,单纯形法,单纯形法,注意： （1）对“”约束,松弛变量“+xi” 对“”约束,松弛变量“-xi”,（2）人工变量:max-目标系数-m min -目标系数+m,（3）进基原则： max-最大正j 对应的 xj 进基。 min -最小负j 对应的 xj 进基。,（4）最小比值：约束系数为0或负数时不计算比 值。,（5）最优性准则： max- j 0 最优； min - j 0 最优。,（6）线性规划问题不一定有最优解。,（7）有时有多个最优解。,单纯形法,第一节 应 用 和 推 广,一、应用,1. 原料配比问题 用甲、乙、丙、丁原料生产a、b、c药物。四种原料成本分别是每公斤5、6、7、8元。每公斤不同原料所能提供的各种药物如下表。药厂要求每天生产a药恰好100克、 b药至少530克， c药不超过160克。要求选配各种原料的数量，既满足生产需要，又使总的成本最小。,设x1、x2、x3、x4分别为甲、乙、丙、丁原料的用量，,a恰好100克 b至少530克 c不超过160克,2. 设备安排问题 某车间加工a、b两种零件，必须1 ：1配套。甲、乙、丙三种设备都可以生产这两种零件，但每种设备加工不同零件的能力不一样，具体如下表。怎样安排生产任务，才能使配套产量最大？,设每一天的生产时间为1，令下列变量 x11:甲设备用来生产零件a的时间百分比; x12:甲设备用来生产零件b的时间百分比 x21:乙 设备用来生产零件a的时间百分比 x22:乙设备用来生产零件b的时间百分比 x31:丙设备用来生产零件a的时间百分比 x312:丙设备用来生产零件b的时间百分比,时间是百分比,每一天零件a的产量,每一天零件b的产量,a、b零件必须1：1配套，,3. 货物运输问题 甲、乙两地分别要运出物资1100吨、2000吨到a、b、c、d仓库。各仓库的收进数量分别是500、1100、600、900吨。供需平衡。甲、乙两地和各仓库之间的距离（公里）如表。确定一个运输方案，使总的吨公里数最小。,设x11、x12、x13、x14分别为甲地运往a、 b、c、d仓库的吨数； x21、x22、x23、x24乙地运往a、b、c、d仓库的吨数。,约束条件：,4下料问题 某建筑工地需要直径相同但长度不同的成套钢筋。每套由7根2米长于7米长的钢筋共同组成。今有15米长的钢筋150根，问应怎样下料，才能使废料最少？,15米长的钢筋分割成7米、2米的，有3种比较经济的方法。,设x1,x2,x3为采用三种方法下料的钢筋数，,得7米:,得2米:,目标:,二、线性规划标准化中的一些情况,设,约束两端同乘（-1），,第二约束式左端加上松弛变量，,三、单纯形计算中的一些情况,多重最优解（无穷多） 最优解中某非基变量的检验数等于零。以这种非基变量作为进基变量，可求得另一基最优解。 任一最优