线性规划的进一步讨论.ppt

第四章 线性规划进一步讨论,目标规划 运输问题,目标规划,目标规划的基本概念 目标规划问题的数学模型 图解法求解目标规划,目标规划的基本概念,基本概念 （1）偏差变量 d+,d- d+ 0，d- 0，d+ d- = 0 （2）绝对约束和目标约束 绝对约束（硬约束）：必须严格满足的约束条件 目标约束（软约束） （3）优先因子（P）和权系数（W） （4）目标函数 决策值=目标值 min f (d+ + d- ) 决策值目标值 min f (d- ) ,最优生产计划为甲产品4件，乙产品3件，最大利润62元。 但，目前决策时还要考虑以下问题 （1）产品甲开始出现滞销现象，故产品甲的产量应不超过产品乙； （2）超过计划供应的原材料要高价采购，生产中避免过量消耗； （3）尽可能充分利用设备台时，但不希望加班； （4）尽可能达到并超过计划利润指标56元,经过综合考虑，决策者目标: （1）原材料使用限额不能突破； （2）产品甲产量不大于产品乙； （3）充分利用设备台时，不希望加班； （4）利润额不少于56元。,min P1d1+ , P2(d2- + d2+) , P3 d3- ,目标规划数学模型的一般形式：,x2,图解法求解目标规划,x1,0,d1+,B,A,G,C,所以满意域为线段GD,A,B,C,D,E,F,满意解为点E， x1=24,x2=26 d1- = d2+ =d3-=0 d4-=4,x1 + x2 + d1- - d1+ =40 st. x1 + x2 + d2- - d2+ =50 x1 + d3- - d3+ =24 x2 + d4- - d4+ =30 x1,x2, di-,di+ 0 i=1,2,3,4,min P1d1- , P2d2+ , P3d3- , P4d4- ,运输问题,运输问题的数学模型 表上作业法 产销不平衡运输问题,运输问题的数学模型,a2=4,a3=9,b1=3,b2=6,b3=5,b4=6,a1=7,总产 量,供应地,运价,总销量,需求地,A2,A3,B2,A1,B3,B4,B1,3,11,3,10,1,9,2,8,7,4,10,5,当总产量 = 总销量，称为产销平衡问题 当总产量总销量，称为产销不平衡问题,运输问题线性规划数学模型,设从供应地Ai 往需求地Bj 运送货物量为 xij,供应地约束,需求地约束,运输问题数学模型的特点,1、运输问题有有限最优解 2、运输问题约束条件的系数矩阵 （1）约束条件系数矩阵的元素等于0或1 （2）约束条件系数矩阵的每一列有两个非零元素，且一个在前m个约束方程中出现，另一个在后n个方程中出现。 3、解的特性 解必须是基可行解，基变量个数为m+n-1个,运输表,表上作业法,步骤：1、确定初始运输方案（两种方法） 最小元素法、沃格尔法 2、对初始运输方案进行检验，确定是否为最优运输方案 闭回路法、对偶变量法 3、如果不是最优运输方案，进行调整得到新的运输方案 闭回路法 4、重复2、3步直到找到最优运输方案,1、给出运输问题的初始基可行解（初始调运方案） 1）最小元素法,3,1,4,6,3,3,2) 沃格尔法,6,3,3,5,1,2,1,11= c11-c13+c23-c21=3-3+2-1=1,2、解的最优性检验 1) 闭回路法,1,2,6,3,3,4,1,3,12= c12-c14+c34-c34=11 -10+5 -4=2,6,3,3,4,1,3,1,2,1,22= c22-c23+c13-c14+c34-c34=9-2+3 10+5-4=1,6,3,3,4,1,3,1,2,1,-1,24= c24-c23+c13-c14=8 -2+3 -10=-1,6,3,3,4,1,3,1,2,1,-1,10,31= c31-c21+c23-c13+c14-c34=7 -1+2 3+10-5=10,6,3,3,4,1,3,1,2,1,-1,10,12,33= c33-c13+c14-c34=10 -3+10 -5=12,因为24= -10，所以可行解不是最优解 所以要重新调整，寻找另一可行解,设u1、u2、u3、v1、v2、v3、v4分别表示对偶变量,2) 对偶变量法（位势法）,u1 u2 u3 v1 v2 v3 v4,基变量的检验数ij = cij (ui + vj)=0，即cij = ui + vj,v1,v2,v3,v4,u1,u2,u3,c13 = u1 + v3 = 3 c14 = u1 + v4 = 10 c21 = u2 + v1 = 1 c23 = u2 + v3 = 2 c32 = u3 + v2 = 4 c34 = u3 + v4 = 5,c13 = u1 + v3=3 c14 = u1 + v4=10 c21 = u2 + v1=1 c23 = u2 + v3=2 c32 = u3 + v2=4 c34 = u3 + v4=5,令 u1 = 0 u2 = -1 u3 = -5 v1 = 3 v2 = 10 v3 = 4 v4 = 11,代入ij = cij (ui + vj) 11=1 12=2 22=1 24= -1 31=10 33=12,对偶变量法（位势法）,6,3,3,4,1,3,0,3,10,-1,-5,2,9,1,2,1,-1,10,12,基变量：cij = ui+vj,非基变量：ij = cij (ui + vj),1、运输问题表上作业法中检验数的经济意义是什么？ 2、运用表上作业法求解运输问题时，计算检验数可用（ ），确定初始方案可用（ ）。 a、闭回路法 b、最小元素法 c、位势法 3、判断 解运输问题的表上作业法中，对每一非基空格，均可找到唯一的一条闭回路。,3、解的改进（闭回路法）,3,3,4,1,3,-1,6,+,- ,+,-,= 1,1,5,2,4、再进行检验,1,9,12,0,2,2,因为ij 0，所以此运输方案是最优方案，而11= 0 说明还有另一最优解,u1=0,u2= -2,u3= -5,v1= 3,v2= 9,v3 = 3,v4 = 10,表上作业法求解运输问题的几点说明： 1、运输问题的某一可行方案有多个检验数为负，通常取ij 0 中最小的为换入变量 2、最优方案时，如果某非基变量的= 0 ，说明运输问题有多重解。 3、解的退化： 如果出现退化解应在同时划去的一行或一列中的某个格子中填入0，以使基变量的个数保持m + n - 1个,5,3,1,2,解的退化,5,3,1,2,解退化的处理,0,0,1.一般产销不平衡运输问题,1)总产量 总销量,产销不平衡运输问题的处理,假想一销地Bn+1，令销量为 ，运价c =