线性规划的进一步讨论

《线性规划的进一步讨论》由会员分享，可在线阅读，更多相关《线性规划的进一步讨论（38页珍藏版）》请在金锄头文库上搜索。

1、第四章第四章 线性规划进一步讨论线性规划进一步讨论目标规划目标规划目标规划的基本概念目标规划的基本概念目标规划问题的数学模型目标规划问题的数学模型图解法求解目标规划图解法求解目标规划目标规划的基本概念目标规划的基本概念基本概念基本概念（1）偏差变量）偏差变量 d+,d- d+ 0，d- 0，d+ d- = 0（2）绝对约束和目标约束绝对约束和目标约束绝对约束（硬约束）：必须严格满足的约束条件绝对约束（硬约束）：必须严格满足的约束条件目标约束（软约束）目标约束（软约束）（3）优先因子（）优先因子（P）和权系数（和权系数（W）（4）目标函数目标函数 决策值决策值=目标值目标值 min f (d+

2、+ d- ) 决策值决策值 目标值目标值 min f (d- ) 项项 目目甲甲 乙乙拥有量拥有量原材料原材料（kg/kg/件）件）2 21 11111设备工时设备工时（h/h/件）件）1 12 21010利利 润（元润（元/ /件）件）8 81010最优生产计划为甲产品最优生产计划为甲产品4 4件，乙产品件，乙产品3 3件，最大利件，最大利润润6262元。元。但，目前决策时还要考虑以下问题但，目前决策时还要考虑以下问题（1 1）产品甲开始出现滞销现象，故产品甲的产量产品甲开始出现滞销现象，故产品甲的产量应不超过产品乙；应不超过产品乙；（2 2）超过计划供应的原材料要高价采购，生产中）超过计划

3、供应的原材料要高价采购，生产中避免过量消耗；避免过量消耗；（3 3）尽可能充分利用设备台时，但不希望加班；）尽可能充分利用设备台时，但不希望加班；（4 4）尽可能达到并超过计划利润指标）尽可能达到并超过计划利润指标5656元元经过综合考虑，决策者目标经过综合考虑，决策者目标: :（1 1）原材料使用限额不能突破；原材料使用限额不能突破；（2 2）产品甲产量不大于产品乙；）产品甲产量不大于产品乙；（3 3）充分利用设备台时，不希望加班；）充分利用设备台时，不希望加班；（4 4）利润额不少于）利润额不少于5656元。元。 2x2x1 1 + x+ x2 2 1111st. xst. x1 1 -

4、x- x2 2 + d+ d1 1- - - d- d1 1+ + =0 =0 x x1 1 + 2x+ 2x2 2 + d+ d2 2- - - d- d2 2+ + =10 =10 8x 8x1 1 + 10x+ 10x2 2 + d+ d3 3- - - d- d3 3+ + =56 =56 x x1 1,x,x2 2,d,di i- -,d,di i+ + 0 i=1,2,3 0 i=1,2,3min P1d1+ , P2(d2- + d2+) , P3 d3- 目标规划数学模型的一般形式：目标规划数学模型的一般形式： Min Pl（ wlk-dk- + wlk+dk+ ）,l=1,2

5、,Lk =1Kckj xj + dk- - dk+ = gk ， k =1，2，Kj =1naij xj （=，） bi ，i =1，2，mj =1nxj 0 , j =1，2，ndk- ，dk+ 0 , k =1，2，KS.t.x2图解法求解目标规划图解法求解目标规划2x1 + x2 11 x1 - x2 + d1- - d1+ =0 x1 + 2x2 + d2- - d2+ =108x1 + 10x2 + d3- - d3+ =56 x1,x2,di-,di+ 0 i=1,2,3min P1 d1+ , P2 ( d2- + d2+ ) , P3 d3- s.t.x10d1+Bd2+Ad3

6、-GEDCd2-所以满意域为线段所以满意域为线段GD GD ABCDEFd1-d2+满意解为点满意解为点E，x1=24,x2=26d1- = d2+ =d3-=0 d4-=4d3-d4- x1 + x2 + d1- - d1+ =40st. x1 + x2 + d2- - d2+ =50 x1 + d3- - d3+ =24 x2 + d4- - d4+ =30 x1,x2, di-,di+ 0 i=1,2,3,4min P1d1- , P2d2+ , P3d3- , P4d4- 运输问题运输问题运输问题的数学模型运输问题的数学模型表上作业法表上作业法产销不平衡运输问题产销不平衡运输问题 运输

7、问题的数学模型运输问题的数学模型a2=4a3=9b1=3b2=6b3=5b4=6a1=7总总产产 量量供应地供应地运价运价总总销销量量需求地需求地A2A3B2A1B3B4B1311310192874105当总产量当总产量 = = 总销量，称为产销平衡问题总销量，称为产销平衡问题 当总产量当总产量总销量，称为产销不平衡问题总销量，称为产销不平衡问题运输问题线性规划数学模型运输问题线性规划数学模型设从供应地设从供应地Ai 往需求地往需求地Bj 运送货物量为运送货物量为 xij供供应应地地约约束束需需求求地地约约束束运输问题数学模型的特点运输问题数学模型的特点1、运输问题有有限最优解、运输问题有有限

8、最优解2、运输问题约束条件的系数矩阵、运输问题约束条件的系数矩阵（1）约束条件系数矩阵的元素等于）约束条件系数矩阵的元素等于0或或1（2）约束条件系数矩阵的每一列有两个非零）约束条件系数矩阵的每一列有两个非零元素，且一个在前元素，且一个在前m个约束方程中出现，另一个约束方程中出现，另一个在后个在后n个方程中出现。个方程中出现。3、解的特性、解的特性解必须是基可行解，基变量个数为解必须是基可行解，基变量个数为m+n-1个个运输表运输表表上作业法表上作业法步骤：步骤：1、确定初始运输方案（两种方法）、确定初始运输方案（两种方法） 最小元素法、沃格尔法最小元素法、沃格尔法 2、对初始运输方案进行检验

9、，确定是否对初始运输方案进行检验，确定是否为最优运输方案为最优运输方案 闭回路法、对偶变量法闭回路法、对偶变量法 3、如果不是最优运输方案，进行调整得、如果不是最优运输方案，进行调整得到新的运输方案到新的运输方案 闭回路法闭回路法 4、重复、重复2、3步直到找到最优运输方案步直到找到最优运输方案1 1、给出运输问题的初始基可行解（初始调运方案）、给出运输问题的初始基可行解（初始调运方案） 1 1）最小元素法）最小元素法3146332) 2) 沃格尔法沃格尔法列列罚罚数数行罚数行罚数25130116213012 321212017635200126 31433111= c11-c13+c23-c

10、21=3-3+2-1=12 2、解的最优性检验、解的最优性检验 1) 1) 闭回路法闭回路法126 3 341312= c12-c14+c34-c34=11 -10+5 -4=26 3341312122= c22-c23+c13-c14+c34-c34=9-2+3 10+5-4=16 3 3413121-124= c24-c23+c13-c14=8 -2+3 -10=-16 3 3413121-11031= c31-c21+c23-c13+c14-c34=7 -1+2 3+10-5=106 3 3413121-1101233= c33-c13+c14-c34=10 -3+10 -5=12121

11、-11012因为因为2424= -10= -10，所以可行解不是最优解，所以可行解不是最优解所以要重新调整，寻找另一可行解所以要重新调整，寻找另一可行解设设u u1 1、u u2 2、u u3 3、v v1 1、v v2 2、v v3 3、v v4 4分别表示对偶变量分别表示对偶变量2) 2) 对偶变量法（位势法）对偶变量法（位势法）u1u2u3v1v2v3v4基变量的检验数基变量的检验数ij = cij (ui + vj)=0，即即cij = ui + vjv1v2v3v4u1u2u3c13 = u1 + v3 = 3c14 = u1 + v4 = 10c21 = u2 + v1 = 1c2

12、3 = u2 + v3 = 2c32 = u3 + v2 = 4c34 = u3 + v4 = 5c13 = u1 + v3=3c14 = u1 + v4=10c21 = u2 + v1=1c23 = u2 + v3=2c32 = u3 + v2=4c34 = 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=124= -1 31=10 33=12对偶变量法（位势法）对偶变量法（位势法）63 34130310-1 -529121-11012vj u

13、i基变量：基变量：c cijij = u = ui i+v+vj j 非基变量：非基变量：ij ij = c= cij ij (u (ui i + + v vj j) )1、运输问题表上作业法中检验数的经济意义是、运输问题表上作业法中检验数的经济意义是什么？什么？2、运用表上作业法求解运输问题时，计算检验、运用表上作业法求解运输问题时，计算检验数可用（数可用（ ），确定初始方案可用（），确定初始方案可用（ ）。）。a、闭回路法闭回路法 b、最小元素法最小元素法c、位势法位势法 3、判断、判断 解运输问题的表上作业法中，对每一非基空格，解运输问题的表上作业法中，对每一非基空格，均可找到唯一的一条

14、闭回路。均可找到唯一的一条闭回路。3 3、解的改进（闭回路法）、解的改进（闭回路法） 33413-16+- +-= 1413x24521x23 1 5 24 4、再进行检验、再进行检验 3 351261912022因为因为ijij 0 0，所以此运输方案是最优方案，而，所以此运输方案是最优方案，而1111= 0 = 0 说明还有另一最优解说明还有另一最优解 u1=0u2= -2u3= -5v1= 3v2= 9v3 = 3v4 = 10表上作业法求解运输问题的几点说明：表上作业法求解运输问题的几点说明：1、运输问题的某一可行方案有多个检验数为、运输问题的某一可行方案有多个检验数为负，通常取负，通

15、常取ij 总销量总销量产销不平衡运输问题的处理产销不平衡运输问题的处理产销不平衡问题产销不平衡问题 产销平衡问题产销平衡问题假想一销地假想一销地Bn+1，令销量为令销量为 ，运价，运价c = 0总产量总产量 总销量总销量 AAA销量销量 B1 B2 B3 3 12 3 1 11 2 5 2 6 7 1 3 43 5 B4 4 9 5 6 产量产量 8 5 9 B5 0 0 0 4 43542222、总产量、总产量 总销量总销量假想一产地假想一产地Am+1，令产量为令产量为 ，一般运价，一般运价c = 02. 2. 带弹性需求的产销不平衡运输问题带弹性需求的产销不平衡运输问题 需求地需求地化肥厂化肥厂B1B2B3B4产量产量A11613221750A21413191560A319202350最低需求最低需求最高需求最高需求3050707003010不限不限 B1B1B2B3B4B4产量产量A116161322171750A214141319151560A319192023MM50A4M0M0M050需求量需求量30207030105021050200302030103020