提高经济效益的线性规划法.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及负系数不能做分母，,单纯形法,初等行变换：进基变量列与出基变量行相交处为枢元。,010,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），,第二约束式左端加上松弛变量，,三、单纯形计算中的一些情况,多重最优解（无穷多）最优解中某非基变量的检验数等于零。以这种非基变量作为进基变量，可求得另一基最优解。任一最优解可表示为所有基最优解的凸组合。,max z=3x1+5x2 3x1+5x2 15 2x1+x2 5 2x1+2x2 11 x1,x2 0,如果将x1换入基底，得另一解，由可行域凸性易知，有两个最优解必有无穷多组最优解当非基底变量的检验数中有取零值，或检验数中零的个数大于基变量个数时，有无穷多解。,2.不可行,典型化:,3.无界情形,例 3 用单纯形法求解,