第2章 线性规划与单纯形法 第3章 对偶理论与灵敏度分析 第4章 运输问题 第5章 目标规划

Presentation on theme: "第2章 线性规划与单纯形法 第3章 对偶理论与灵敏度分析 第4章 运输问题 第5章 目标规划"— Presentation transcript:

1 第2章 线性规划与单纯形法 第3章 对偶理论与灵敏度分析 第4章 运输问题 第5章 目标规划
二、线性规划与目标规划 第2章 线性规划与单纯形法 第3章 对偶理论与灵敏度分析 第4章 运输问题 第5章 目标规划 清华大学出版社

2 第1节 目标规划的数学模型 第2节 解目标规划的图解法 第3节 解目标规划的单纯形法 第4节 灵敏度分析 第5节 应用举例
第5章 目标规划 第1节  目标规划的数学模型 第2节 解目标规划的图解法 第3节 解目标规划的单纯形法 第4节 灵敏度分析 第5节 应用举例 清华大学出版社

3 第1节 目标规划的数学模型 为了说明目标规划与线性规划在处理问题方法上的区别，先通过例子来介绍目标规划的有关概念及数学模型。 清华大学出版社

4 第1节 目标规划的数学模型 例1 某工厂生产Ⅰ，Ⅱ两种产品，已知有关数据见下表。试求获利最大的生产方案。
第1节 目标规划的数学模型 例1 某工厂生产Ⅰ，Ⅱ两种产品，已知有关数据见下表。试求获利最大的生产方案。 解：这是求获利最大的单目标的规划问题，用x1，x2分别表示Ⅰ，Ⅱ产品的产量，其线性规划模型表述为： 清华大学出版社

5 第1节 目标规划的数学模型 用图解法求得最优决策方案为：x1*=4, x2*=3, z*=62(元)。 (4,3) 清华大学出版社

6 第1节 目标规划的数学模型 实际上，工厂在作决策时，需要考虑包括市场因素在内等一系列条件。例如:
第1节 目标规划的数学模型 实际上，工厂在作决策时，需要考虑包括市场因素在内等一系列条件。例如: (1)根据市场信息，产品Ⅰ的销售量有下降的趋势，因而希望产品Ⅰ的产量不应大于产品Ⅱ。 (2)当超过计划供应原材料时，需用高价采购，会使成本大幅度增加。 (3)应尽可能充分利用设备台时，但不希望加班。 (4)应尽可能达到并超过计划利润指标：56元。 清华大学出版社

7 第1节 目标规划的数学模型 这样的产品决策问题便构成了一个多目标决策问题，目标规划方法正是解这类决策问题的方法之一。下面引入与目标规划模型有关的概念。 1.设x1，x2为决策变量，引入正、负偏差变量d+，d−。 正偏差变量d＋表示决策值超过目标值的部分； 负偏差变量d−表示决策值未达到目标值的部分。 因决策值不可能既超过目标值同时又未达到目标值， 即恒有 d+×d− = 0。 清华大学出版社

8 第1节 目标规划的数学模型 2.绝对约束和目标约束
第1节 目标规划的数学模型 2.绝对约束和目标约束 绝对约束是指必须严格满足的等式约束和不等式约束，如线性规划问题的所有约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。 目标约束是目标规划特有的，可把约束右端项看作要追求的目标值。在达到此目标值时允许发生正或负偏差。因此在这些约束中加入正、负偏差变量，它们是软约束。 线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的需要将绝对约束变换为目标约束，如可将例1的 目标函数 z=8x1+10x 变换为目标约束 x1+10x2+d1−−d1+=56 约束条件 x1+x2≤11 变换为目标约束 x1+x2+d2−−d2+=11 清华大学出版社

9 第1节 目标规划的数学模型 3.优先因子(优先等级)与权系数
第1节 目标规划的数学模型 3.优先因子(优先等级)与权系数 一个规划问题常常有若干目标。但决策者在要求达到这些目标时，会有主次或轻重缓急的不同。例如，要求第一位达到的目标赋予优先因子P1，次位的目标赋予优先因子P2，…，并规定 Pk>>Pk+1 k=1,2,…，K 表示Pk比Pk+1有更大的优先权。即首先保证P1级目标的实现，这时可不考虑次级目标；而P2级目标仅在实现P1级目标的基础上才会考虑；依此类推。若要区别具有相同优先因子的两个目标的差别，可分别赋予它们不同的权系数wj，这些都由决策者按具体情况而定。 清华大学出版社

10 第1节 目标规划的数学模型 4.目标规划的目标函数 min z=f(d+,d−)
第1节 目标规划的数学模型 4.目标规划的目标函数 目标规划的目标函数(准则函数)是按各目标约束的正、负偏差变量和赋予的优先因子及权系数而构造的。当每一目标值确定后，决策者的要求是尽可能缩小和目标值的偏差。因此目标规划的目标函数的形式通常是 min z=f(d+,d−) 其具体形式大致有三种： (1) 若要求恰好达到目标值，则应要求正、负偏差变量均尽可能地小，这时，目标函数的形式为 min z=f(d++d−) (2) 若要求不超过目标值，即允许达不到目标值，但正偏差变量要尽可能地小，这时目标函数的形式为 min z=f(d+) (3) 若要求超过目标值，即超过量不限，但负偏差变量要尽可能地小，这时目标函数的形式为 min z=f(d−) 清华大学出版社

11 第1节 目标规划的数学模型 例2 例1的决策者在原材料供应受严格限制的基础上考虑：首先是产品Ⅱ的产量不低于产品Ⅰ的产量；其次是充分利用设备有效台时，不加班；再次是利润额不小于56元。求最佳决策方案 。 解：按决策者所的要求，分别赋予这三个目标优先因子P1，P2，P3，得到本问题的数学模型为： 清华大学出版社

12 第1节 目标规划的数学模型 目标规划的一般数学模型为 为权系数。 清华大学出版社

13 第2节  解目标规划的图解法 对只有两个决策变量的目标规划问题，可以用图解法来求解，以例2说明之（图4-1）。 清华大学出版社

14 第2节  解目标规划的图解法 注意：求解目标规划问题时，把绝对约束作为最高优先级考虑。在本例中，能依先后次序都满足d1+=0，d2++d2−=0，d3−=0，因而z*=0。但在大多数问题中并非如此，会出现某些约束得不到满足，故将目标规划问题的最优解称为满意解。 清华大学出版社

15 第2节  解目标规划的图解法 例3 某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量是24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的目标为： 第一优先级：充分利用装配线每周计划开动40小时； 第二优先级：允许装配线加班；但加班时间每周尽量不超过10小时； 第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机的利润高，取其权系数为2。 试建立本问题的目标规划模型，并求解黑白和彩色电视机的产量。 清华大学出版社

16 第2节  解目标规划的图解法 解：设x1，x2分别表示黑白和彩色电视机的产量，本问题的目标规划模型为： 清华大学出版社

17 第2节  解目标规划的图解法 用图解法求解，见图4.2。 清华大学出版社

18 第2节 解目标规划的图解法 从图4.2可看出： 在考虑具有优先因子P1、P2的目标实现后，x1、x2的取值范围为ABCD。
第2节  解目标规划的图解法 从图4.2可看出： 在考虑具有优先因子P1、P2的目标实现后，x1、x2的取值范围为ABCD。 当考虑P3级目标时，因d3−的权系数大于d4 − ，故先考虑min d3 − 。这时x1、x2的取值范围缩小为区域ABEF。然后考虑d4 − 。在区域ABEF中无法满足d4 − =0，因此只能在ABEF中取一点，使d4 − 尽可能小，这就是E点。故E点为满意解，其坐标为(24，26)。 即该厂每周应装配彩色电视机24台，黑白电视机26台。 清华大学出版社

19 第3节 解目标规划的单纯形法 目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以可用单纯形法求解。但要根据目标规划的特点，作以下规定： (1) 因目标规划问题的目标函数都是求最小化，所以以cj−zj≥0，j=1,2,…，n作为最优性判别准则。 (2) 因非基变量的检验数中含有不同等级的优先因子，即 因为 P1>>P2>>…>>PK 故从每个检验数的整体来看，检验数的正、负首先决定于P1的系数α1j的正、负；若α1j=0，则此检验数的正、负就决定于P2的系数α2j的正、负；下面依此类推。 清华大学出版社

20 第3节 解目标规划的单纯形法 解目标规划问题的单纯形法的计算步骤：
第3节 解目标规划的单纯形法 解目标规划问题的单纯形法的计算步骤： (1) 建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行，置k=1。 (2) 检查该行中是否存在负数，且对应的前k−1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转到(3)；若无负数，则转到(5)。 (3) 按最小比值规则确定换出变量。当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。 (4) 按单纯形法进行基变换运算，建立新的计算表，返回(2)。 (5) 当k=K时，计算结束，表中的解即为满意解。否则，置k=k+1，返回到(2)。 清华大学出版社

21 第3节 解目标规划的单纯形法 例4 试用单纯形法来求解例2。 解：将例2的数学模型化为标准型： 清华大学出版社

22 第3节 解目标规划的单纯形法 ① 取xs，d1−，d2− ，d3−为初始基变量，列初始单纯形表，见表4-1。 清华大学出版社

23 第3节 解目标规划的单纯形法 ② 取k=1，检查检验数的P1行，因该行无负检验数，故转(5)。
第3节 解目标规划的单纯形法 ② 取k=1，检查检验数的P1行，因该行无负检验数，故转(5)。 ③ 因k(=2)＜K(=3)，置k=k+1=3，返回到(2)。 ④ 查出检验数P2行中有−1、 − 2；取min(− 1, − 2)= − 2。它对应的变量x2为换入变量，转入(3)。 ⑤ 在表4-1上计算最小比值 θ=min(11/1，0，10/2，56/10)=10/2 它对应的变量d2-为换出变量，转入(4)。 ⑥ 进行基变换运算，计算结果见表4-2。返回到(2)。依此类推，直至得到最终表为止。见表4-3。 清华大学出版社

24 第3节 解目标规划的单纯形法 表4-2 清华大学出版社

25 第3节 解目标规划的单纯形法 表4-3 清华大学出版社

26 第3节 解目标规划的单纯形法 表4-3所示的解x1*=2，x2*=4为例1的满意解，此解相当于图4-1的G点。 清华大学出版社

27 第3节 解目标规划的单纯形法 检查表4-3的检验数行，发现非基变量d3+的检验数为0，表示存在多重解。在表4-3中，以非基变量d3+为换入变量，d1−为换出变量，经迭代得到表4-4。 清华大学出版社

28 第3节 解目标规划的单纯形法 由表4-4得到解x1*=10/3，x2*=10/3，此解相当于图4-1的D点，G、D两点的凸线性组合都是例1的满意解。 清华大学出版社

29 第4节 灵敏度分析 目标规划的灵敏度分析方法与线性规划相似，但除了分析各类系数的变化外，还可能要分析优先因子的变化问题。 清华大学出版社

30 第4节 灵敏度分析 例 5 已知目标规划问题 在得到最终表（见表4-5）后，若目标函数的优先等级变化为： 试分析原解有什么变化。
(1) min z=P1(2d1++32+)+P2d4++P3− (2) min z= P1d3−+P2(2d1++3d3+)+P3d4+ 试分析原解有什么变化。 清华大学出版社

31 第4节 灵敏度分析 表4-5 清华大学出版社

32 第4节 灵敏度分析 解： 分析(1)。实际是将原目标函数中d4+，d3−的优先因子对换了一下。这时将表4-5的检验数中的P2、P3行和cj行的P2、P3对换即可。可见原解仍满足最优解条件。 分析(2)。将变化后的优先等级直接反映到表4-5上，再计算检验数，得到表4-6。然后进行迭代，直到求得新的满意解为止。从表4-7得到新的满意解为 x1*=4，x2*=12。 清华大学出版社

33 第4节 灵敏度分析 表4-6 清华大学出版社

34 第5节 应用举例 例6 某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定： (1) 不超过年工资总额60000元；
第5节 应用举例 例6 某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定： (1) 不超过年工资总额60000元； (2) 每级的人数不超过定编规定的人数； (3) Ⅱ，Ⅲ级的升级面尽可能达到现有人数的20%，且无越级提升； (4) Ⅲ级不足编制的人数可录用新职工，又Ⅰ级的职工中有10%要退休。 有关资料汇总于表4-8中，问该领导应如何拟订一个满意的方案。 清华大学出版社

35 第5节 应用举例 解：设x1、x2、x3分别表示提升到Ⅰ、Ⅱ级和录用到Ⅲ级的新职工人数。对各目标确定的优先因子为： 先分别建立各目标约束。
第5节 应用举例 解：设x1、x2、x3分别表示提升到Ⅰ、Ⅱ级和录用到Ⅲ级的新职工人数。对各目标确定的优先因子为： P1——不超过年工资总额60000元； P2——每级的人数不超过定编规定的人数； P3——Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%。 先分别建立各目标约束。 年工资总额不超过60000元 2000(10−10×0.1+x1)+1500(12−x1+x2)+1000(15−x2+x3)+ d1−d1+ =60000 清华大学出版社

36 第5节 应用举例 以上目标规划可用单纯形法求解，得到多重解。将这些解汇总于表4-9，单位领导再按具体情况，从表4-9中选出执行方案。
第5节 应用举例 每级的人数不超过定编规定的人数： 对Ⅰ级有 10(1− 0.1)+x1+d2−−d2+=12 对Ⅱ级有 12 − x1+x2+d3−−d3+=15 对Ⅲ级有 15 − x2+x3+d4− −d4+=15 Ⅱ，Ⅲ级的升级面不大于现有人数的20%，但尽可能多提： 对Ⅱ级有 x1+d5− −d5+=12×0.2 对Ⅲ级有 x2+d6− −d6+=15×0.2 目标函数：min z=P1d1++P2(d2++d3++d4+)+P3(d5−+d6−) 以上目标规划可用单纯形法求解，得到多重解。将这些解汇总于表4-9，单位领导再按具体情况，从表4-9中选出执行方案。 清华大学出版社

37 第5节 应用举例 表4-9 清华大学出版社

38 第5节 应用举例 例7 已知有三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价见表4-10。有关部门在研究调运方案时依次考虑以下七项目标，并规定其相应的优先等级： P1——B4是重点保证单位，必须全部满足其需要； P2——A3向B1提供的产量不少于100； P3——每个销地的供应量不小于其需要量的80%； P4——所定调运方案的总运费不超过最小运费调运方案的10%； P5——因路段的问题，尽量避免安排将A2的产品往B4； P6——给B1和B3的供应率要相同； P7——力求总运费最省。 试求满意的 调运方案。 清华大学出版社

39 第5节 应用举例 解 上作业法求得最小运费的调运方案见表4-11。这时得最小运费为2950元，再根据提出的各项目标的要求建立目标规划的模型。
第5节 应用举例 解 上作业法求得最小运费的调运方案见表4-11。这时得最小运费为2950元，再根据提出的各项目标的要求建立目标规划的模型。 表4-11 清华大学出版社

40 第5节 应用举例 供应约束 需求约束： A3向B1提供的产品量不少于100 x11+x12+x13+x14≤300
第5节 应用举例 供应约束 x11+x12+x13+x14≤300 x21+x22+x23+x24≤200 x31+x32+x33+x34≤400 需求约束： x11+x21+x31+d1−− d1+=200 x12+x22+x32+d2− − d2+=100 x13+x23+x33+d3− − d3+=450 x14+x24+x34+d4− − d4+=250 A3向B1提供的产品量不少于100 x31+d5−− d5+=100 清华大学出版社

41 第5节 应用举例 每个销地的供应量不小于其需要量的80% 调运方案的总运费不超过最小运费调运方案的10%
第5节 应用举例 每个销地的供应量不小于其需要量的80% x11+x21+x31+d6−−d6+=200×0.8 x12+x22+x32+d7− − d7+=100×0.8 x13+x23+x33+d8− − d8+=450×0.8 x14+x24+x34+d9− − d9+=250×0.8 调运方案的总运费不超过最小运费调运方案的10% 清华大学出版社

42 第5节 应用举例 因路段的问题，尽量避免安排将A2的产品运往B4 给B1和B3的供应率要相同 力求总运费最省 目标函数为：
第5节 应用举例 因路段的问题，尽量避免安排将A2的产品运往B4 x24+d11−−d11+=0 给B1和B3的供应率要相同 (x11+x21+x31)−(200/450)(x13+x23+x33)+d12−− d12+=0 力求总运费最省 目标函数为： 清华大学出版社

43 第5节 应用举例 计算结果，得到满意调运方案见表4-12。 总运费为 3360元 清华大学出版社

44 注 记 用单纯形法求解线性规划问题是令人满意的算法。但在1972年V.Klee和G. Minty构造了一个n个变量2n个不等约束的例子。用单纯形法求解此线性规划问题时，其计算次数为2n。 从计算复杂性的标准来看，凡算法所需计算工作量是问题规模(变量数或方程数)n的多项式函数时，这算法为有效算法，如高斯消去法的计算量为n3/3的加法，n3/2的乘法，n2/2的除法。即为0(kn3)。 清华大学出版社

45 此后卡玛卡尔(N. Karmarkar)又提出了一种新的投影尺度算法［11］。它本质上是一种内点算法，也属多项式算法。
注 记 若某算法的计算量是问题规模的指数式函数an时，就不是有效算法。因而不能肯定单纯形法是有效算法。于是就产生一问题，能否找到一种解线性规划问题的肯定的多项式算法。1979年苏联科学院计算中心的哈奇扬(XAЧИЯН)发表了求解线性规划问题的多项式算法一文，解决了这问题。他提出的椭球算法，并证明了线性规划问题存在多项式算法。但哈奇扬的椭球算法在应用时，迭代次数比单纯形法要多得多，因此实用价值不大，但理论上意义很大。 此后卡玛卡尔(N. Karmarkar)又提出了一种新的投影尺度算法［11］。它本质上是一种内点算法，也属多项式算法。 清华大学出版社