当前位置：文档之家 › 第四章--目标规划及图解法--运筹学

第四章--目标规划及图解法--运筹学

  • 格式：ppt
  • 大小：605.00 KB
  • 文档页数：29

下载文档原格式

  / 29

合集下载

运筹学第四章

运筹学第四章

运筹学第四章习题答案4.1若用以下表达式作为目标规划的目标函数，其逻辑是否正确？为什么？ （1）max ｛-d -+d ｝ （2）max ｛-d ++d ｝ （3）min ｛-d ++d ｝ （4）min ｛-d -+d ｝（1）合理，令f （x ）+-d -+d =b,当f （x ）取最小值时，-d -+d 取最大值合理。

(2)不合理，+d 取最大值时，f （x ）取最大值，-d 取最大值时，f （x ）应取最小值 （3）合理，恰好达到目标值时，-d 和+d 都要尽可能的小。

（4）合理，令f （x ）+-d -+d =b,当f （x ）取最大值时，-d -+d 取最小值合理。

4.2用图解法和单纯形法解下列目标规划问题（1）min ｛P 13+d ，P 2-2d ，P 3（-1d ++1d ）｝24261121=-+++-d d x x 52221=-+++-d d x x155331=-++-d d x3,2,1,0,,,21=≥+-i d d x x i i（2）min{P 1(+++43d d ),P 2+1d ,P 3-2d ,P 4(--+435.1d d )} 401121=-+++-d d x x1002221=-++--d d x x30331=-++-d d x 15442=-++-d d x4,3,2,1,0,,,21=≥+-i d d x x i i(1)图解法0 A B C X 1由图可知，满足域为线段EG,这就是目标规划方程的解，可求得：E,G 的坐标分别为（0，12），（3,3） 故该问题的解为)312,3()3,3()12,0(21221a a a a a +=+ )1,0,(2121=+≥a a a a(2)图解法 21由图可知，满足域为线段AB A(25,15),B(30,10)故该问题的解可表示为)1015,3025()10,30()15,25(212121a a a a a a ++=+ )1,0(212,1=+≥a a a a(1)单纯形法0 0 P1 0 0 P2 P3 P3CB XB x1 x2 bP3 P2 06 2 0 0 0 0 -1 1 245152 1 0 0 -1 1 0 05 0 -1 1 0 0 0 0P1P2P30 0 1 0 0 0 0 0-1 -1 0 0 1 0 0 0-6 -2 0 0 0 0 2 0P3P20 x1 0 2 1.2 -1.2 0 0 -1 1 6230 1 0.2 0.2 -1 1 0 01 0 -0.2 0.2 0 0 0 0P1 P2 P3 0 0 1 0 0 0 0 0 0 -1 -0.2 0.2 1 0 0 0 0 -2 -1.2 1.2 0 0 2 0P30 0x2x10 0 0.8 -0.8 2 -2 -1 1 2230 1 0.2 -0.2 -1 1 0 01 0 -0.2 0.2 0 0 0 0P1P2P30 0 1 0 0 0 0 00 0 0 0 0 1 0 00 0 -0.8 0.8 -2 2 2 00 0x2x10 0 0.4 -0.4 1 -1 -0.5 -0.5 1330 1 0.6 -0.6 0 0 0.5 0.51 0 -0.2 0.2 0 0 0 0P1P2P30 0 1 0 0 0 0 00 0 0 0 0 1 0 00 0 0 0 0 0 1 10 0 x22 0 0 0 1 -1 -0.5 -0.5 71253 1 0 0 0 0 0.5 0.55 0 -1 1 0 0 0 0P1P2P30 0 1 0 0 0 0 00 0 0 0 0 1 0 00 0 0 0 0 0 1 1故该问题的解为)312,3()3,3()12,0(21221a a a a a +=+ )1,0,(2121=+≥a a a a（2）P2P3P1P4P11.5P4CB XB x1 x2b 0 1 1 -1 1 00 0 0 0 0 401 1 0 0 -1 1 0 0 0 0 100 1 0 0 0 0 0 -1 1 00 301-1115P1 0 0 0 0 0 0 1 0 1 0P21P3 -1 -11 00 0 P4-11.5 0 0 1 0 -1 1 0 0 0 0 1 -1 251 0 0 0 -1 1 0 0 1 -1 85 1 0 0 0 0 0 -1 1 0 0 30 0x2 0 115P1 0 0 00 0 0 1 0 1 0P20 0-1 0P3 -1 01-1 1 P4 -1 00 51 0 x110 -1 1 0 0 0 0 1 -11-1-110 0 1 -1 0 0 -1 1 -1 1 30 0 x2 0 1 0 0 0 0 0 0 0 0 P1 0 0 0 0 0 0 1 0 1 0 P2 0 0 1 0 0 0 0 0 0 0 P3 0 0 -1 1 1 0 0 0 0 0P4-1111.54.3某商标的酒是用三种等级的酒兑制而成。

i第四章 目标规划及其图解法

i第四章 目标规划及其图解法

3x1
10x2 d6 d6 3000
x1, x2 0, di , di 0, (i 1, 2,
目标约束 软约束
, 6)
３．目标规划的目标函数(达成函数)
引入偏差变量使原规划问题中的目标函数变 成了目标约束，那么现在问题的目标是什么呢？
对于满足绝对约束和目标约束的所有解（可行 解），从决策者角度看，判断其优劣的依据是决策 值与目标值的偏差越小越好．从而目标规划的目标 函数就由原目标函数变成的目标约束中偏差变量来 构成．它有三种基本表现形式：
200
4x1
5 x2 2000
3x1 10x2 3000
x1, x2 0, di , di 0,
(i 1, 2,3)
４．优先因子与权系数
目标规划中，当决策者要求实现多个目标时，这
些目标的偏差可能相互替代或抵消，因为我们求的是
所有偏差和最小，而实际问题中的目标之间也有主次、
轻重、缓急之区别．决策者往往有一些最重要的，第
这样根据各个目标的不同要求，确定出总的目标函数
Min Z
(di
d
j
)
i, j
如例4-2
70
x1
x1
120 x2
d1
d
2
d1 d2
45000 250
s.t.9.2x1
x2 d3 d3 200 4 x2 3600
利润希望达
到45000,不
足部分d
越小越好!
4x1
5 x2 2000
一位要求达到的目标，我们赋予它优先因子P1，在它 实现的前提下再去解决次要目标．依次把第二位达到
的目标赋予优先因子P2 ……，并规定Pk » Pk+1，即不 管Pk+1乘以一个多大的正数M，总成立Pk>MPk+1,表示 Pk比Pk+1具有绝对的优先权．因此，不同的优先因子 代表着不同的优先等级．

运筹学课程章节

运筹学课程章节
运筹学课程重点内容总结
对照教学大纲
第1章 线性规划 章
• 线性规划基本理论：模型形式，解的概念， 线性规划基本理论：模型形式，解的概念， 解的性质等 • 线性规划应用：6类问题建模 线性规划应用： 类问题建模 类问题建模* • 图解法 图解法* • 单纯形法：基本单纯形法 ，大M法，两阶 单纯形法：基本单纯形法*， 法 段法， 段法，前者重要
第2章 线性规划的对偶理论
• • • • • 对偶问题的构建：对偶规划 对偶问题的构建：对偶规划* 对偶问题的性质 运用对偶性质进行线性规划求解* 运用对偶性质进行线性规划求解* 影子价格理解* 影子价格理解 灵敏度分析*和参数分析 灵敏度分析 和参数分析
第4章 目标规划
• 目标规划建模* 目标规划建模 • 图解法
第5章 运输问题和指派问题
• 运输问题表示：语言描述，表格表示，数 运输问题表示：语言描述，表格表示， 学模型表示， 学模型表示，几何图形表示 • 标准运输问题的表上作业法 标准运输问题的表上作业法* • 表格建模 ：应用，建立运输问题的供需平 表格建模*：应用， 衡与单位运价表， 衡与单位各位同学的选择 • 祝各位同学 考试顺利通过并取得好成绩
• 指派问题表示：语言描述，表格表示，数 指派问题表示：语言描述，表格表示， 学模型表示， 学模型表示，几何图形表示 • 表格建模：应用，指派问题的指派平衡与 表格建模：应用， 单位效率表 • 指派问题的匈牙利算法
第6章 网络模型
• 最优生成树问题 ：最小树，最大树 最优生成树问题*：最小树， • 最短路问题*：三种算法，有向图法，无向 最短路问题*：三种算法，有向图法， 图法， 图法，表格法 • 最大流问题 ：可行流法，增广链法 最大流问题*：可行流法，

运筹学第4章上

运筹学第4章上

min z f (d , d )
（2）要求决策值不超过目标值，即正偏差尽可能的小，其构 造形式为：


min z f (d )
（3）要求决策值可以超过目标值，即负偏差尽可能的小，其 构造形式为：

min z f (d )
China University of Mining and Technology
China University of Mining and Technology
-9-
运 筹 学
目标规划的数学模型
如：在引例中,利润的目标值为32，可能目标值会达不到，所 以加上一个负偏差变量d3-≥0，把目标函数变成
3x1 5 x2 d3 32
但是同样，目标值也有可能会超出，所以减去一个正偏差变量 d3+≥0，把目标函数变成
另一种差别是相对的，这些目标具有相同的优先因子，它们 的重要程度可用权系数wj的不同来表示。
-13-
China University of Mining and Technology
运 筹 学
4. 目标函数
目标规划的数学模型
目标函数由于偏差变量、优先因子和权系数的出现，显然其 构造与线性规划时的构造要有所不同. 决策者的目标是要做到决策值与目标值的偏差能够尽可能的 小，因此目标函数应该是一个与偏差有关的函数：
China University of Mining and Technology
运 筹 学
3. 目标的优先级与权系数
不同目标的主次轻重有两种差别：
目标规划的数学模型
一种差别是绝对的，可用优先因子Pj来表示。
只有在高级优先因子对应的目标已满足的基础上，才能考虑较低 级优先因子对应的目标；在考虑低级优先因子对应的目标时，绝不 允许违背已满足的高级优先因子对应的目标。 优先因子间的关系为Pj >> Pj+1 ，即Pj对应的目标比Pj+1对应的目 标有绝对的优先性。

第四章 目标规划1-2

第四章 目标规划1-2

例4.1 某工厂生产两种产品，受到原材料供应和设备工时的限 制.在单件利润等有关数据已知的条件下，要求制订一个获利最 大的生产计划，具体数据见表4-1.
设产品Ⅰ、Ⅱ的产量分别为 x1, x2
，建立线性规划模型
m z = 6x1 +8x2 ax
5x1 +10x2 ≤ 60
4x1 + 4x2 ≤ 40
x1, x2 ≥ 0
解之得最优生产计划为
x1 = 8
x 件， 2 = 2 件，
利润为 zmax = 64 元. 工厂作决策时可能还需根据市场和工厂实际情况， 考虑其它问题，如： （1）由于产品Ⅱ销售疲软，故希望产品Ⅱ的产量不 1 超过产品Ⅰ的一半； （2）原材料严重短缺，原料数量只有60； （3）最好能节约4小时设备工时； （4）计划利润不少于48元.
解：设A、B、C三种产品的产量分别为 ， 单位工时的利润分别为1000/5=200、1440/8=180、 2520/12=210，故单位工时的利润比例为20:18:21， 于是得目标规划模型为：
综上分析，可得目标规划的一般模型 （4.2 ） s.t. （4.3） （4.4） （4.5） （4.6） 其中，式（4.2）是目标函数有L个目标，根据L个目标的优先程度，把它们分成K个 优先等级，即 ， 是权系数， 是正负偏差变量；式 （4.3)是目标约束， 是L个目标的期望值，一般都应同时引入下、 负偏差变量 ，但有时也可根据已知条件只引入单个 或 ；式（4.4） 是目标规划的绝对约束，通常是人力、物力、财力等资源的约束；式（4.5）、 （4.6）是目标规划的非负约束.
二、目标规划的基本概念
1、目标值和偏差变量 目标值:决策者对每一个目标都有一个期望值----或称为理想值. 正偏差变量：表示决策值（实现值）超过目标值 的数量，记为 d + ； 负偏差变量:表示决策值（实现值）未达到目标 值的数量，记为 d − .

运筹学习题答案(第四章)

运筹学习题答案(第四章)
9 page 9 23 May 2012
School of Management
运筹学教程
第四章习题解答
4.5 某成品酒有三种商标 红、黄、蓝)，都是由 某成品酒有三种商标(红 ， 三种原料酒(等级 Ⅱ 等级Ⅰ 兑制而成。 三种原料酒 等级 Ⅰ ,Ⅱ， Ⅲ )兑制而成。 三种等级的原 兑制而成 料酒的日供应量和成本见表4-13，三种商标的成品酒 料酒的日供应量和成本见表 ， 的兑制要求和售价见表4-14。决策者规定 ： 首先必须 的兑制要求和售价见表 。 决策者规定： 严格按规定比例兑制各商标的酒；其次是获利最大； 严格按规定比例兑制各商标的酒 ； 其次是获利最大 ； 再次是红商标的酒每天至少生产2 000kg。试列出该问 再次是红商标的酒每天至少生产 。 题的数学模型。 题的数学模型。
13 page 13 23 May 2012
School of Management
运筹学教程
第四章习题解答
已知单位牛奶、牛肉、 4.7 已知单位牛奶、牛肉、鸡蛋中的维生素及胆 固醇含量等有关数据见表4 15。 固醇含量等有关数据见表4 - 15 。如果只考虑这三种食 并且设立了下列三个目标： 物，并且设立了下列三个目标： 第一，满足三种维生素的每日最小需要量； 第一，满足三种维生素的每日最小需要量； 第二，使每日摄人的胆固醇最少； 第二，使每日摄人的胆固醇最少； 第三，使每日购买食品的费用最少。 第三，使每日购买食品的费用最少。 要求建立问题的目标规划模型。 要求建立问题的目标规划模型。
售价（ /kg） 售价（元/kg） 5.5 5.0 4.8
解： x11 = 1125 , x12 = 300 , x13 = 75 , x 21 = 1125 , x 22 = 200 , x 23 = 675 , x 31 = 0 , x 32 = 1000 , x 33 = 0 , d 1− = 225 , d 3− = 50 , d 5− = 375 , d 7+ = 250 满足所有目标

运筹学课堂PPT4.2目标规划的图解法

运筹学课堂PPT4.2目标规划的图解法

x1
,
x2
,
d
j
,
d
j
d1 0
d1
80
(3)
最优解空间：ABCD
(2) C
B
x1
(1) (3)
min
Z
P1d1
P2
(d
2
d
2
)
P3
(d
3
d
3
)
P4d
4
3x1 12
(1)
x2
4 x2 16
复习：两平行直线间的距离公式
Ax By d d C（目标约束）
y
d d 0
Ax By C
d 0 ( x0 , y0 )
d
正负偏差变量中至少有一个零，如：
A2 B2
x Ax By C
Ax By d d C d 0, d 0
Ax By d C
Ax By C d C（在下半平面）
P2d4
P3d
3
P4 (2d1
d
2
)
x1 30 x2 20 / 3
x2
d1 0
d1 0
d
2
25 /
3
d2 0
d
3
680
d
3
0
d
4
0
d4 0
D
E(35/2,15)
(2)
min Z (0, 0, 680, 25 / 3)
F(30,20/3)
A
B
x1
(1)
(4) (3)
4.2 目标规划的图解法
差变量大于零的区域。
(1) (2) (3)
（平行） (4)
(2)
x1

管理运筹学第4章-目标规划

管理运筹学第4章-目标规划

多目标决策问题
多目标规划的矩阵表示： 多目标规划的矩阵表示：
max Z = CX
AX ≤ b
X ≥0
z1 z 其中： 其中： Z = 2 M zm
C = (cij )m×n c11 c = 21 M c m1 c12 c 22 cm 2 L c1n L c2n M L c mn
目标规划的数学模型---相关概念
1、设 x1 , x 2 为决策变量，此外，引进正负偏差变 量 d i+ d i−
d i+ 表示： 决策值超过目标值的部分。 正偏差变量
负偏差变量 d i−表示： 决策值未达到目标值的部分。 因决策值不可能既超过目标值又同时未达到目标值， 即恒有 d + × d − = 0
例：LP----目标规划：加入正负偏差变量
目标规划的数学模型---相关概念
3、优先因子（优先等级）与权系数 依据达到目标的主次或轻重缓急而存在的系数（权）。
要求第一个达到的目标赋予优先因子P1，次位目标P2 …… 并规定PK > PK+1……，表示更大的优先权。
若要区别具有相同优先因子的两个目标的差别，此时可 以分别赋予它们不同的权系数 wi
+ i
目标规划的一般数学模型—p103
− + min z = ∑ Pl ∑ ( wlk d k− + wlk d k+ ) l =1 k =1 L K
式中，
− + wlk , wlk 为权系数
n c kj x j + d k− − d k+ = g k , k = 1K K ∑ j =1 n a x ≤ (=, ≥)b , i = 1L m i ∑ ij j j =1 x j ≥ 0, j = 1L n − + d k , d k ≥ 0, k = 1L K

管理运筹学 第四章 目标规划

管理运筹学 第四章 目标规划

再来考虑风险约束： 总风险不能超过700， 投资的总风险为 0.5x1＋0.2x2 引入两个变量d1+和d1-，建立等式如下： 0.5x1 +0.2x2=700+d1+-d1根据要求有
min ｛d1+｝
0.5x1 +0.2x2-d1++d1-=700。
再来考虑年收入:
3x1+4x2
引入变量 d2+和d2-，分别表示年收入超过与低于 10000 的数量。于是，第2个目标可以表示为 min ｛d2-｝ 3x1+4x2-d2++d2-=10000。
2. 统一处理目标和约束。
对有严格限制的资源使用建立系统约束，数学形式同线性规划 中的约束条件。如C和D设备的使用限制。
x1 2 x2 40 3x2 24
(3)Ｃ和Ｄ为贵重设备，严格禁止超时使用
对不严格限制的约束，连同原线性规划建模时的目标，均通 过目标约束来表达。 （1）力求使利润指标不低于250元：
本问题中第一个目标的优先权比第二个目标大。即最重要 的目标是满足风险不超过700。分配给第一个目标较高的优先 权P1，分配给第二个目标较低的优先权P2。
Minz= P1（d1+）+P2（d2-） s.t. 20x1＋50x2≤90000 0.5x1 +0.2x2-d1++d1-=700 3x1+4x2-d2++d2-=10000 x1,x2,d1+,d1-,d2+,d2-≥0
现假定： 第1优先级P1——企业利润；
第2优先级P2——Ｉ、II产品的产量保持1:2的比例
第3优先级P3——设备A,B尽量不超负荷工作。其中设备A的重要性 比设备B大三倍。

运筹学第4章

运筹学第4章

3x15x2d332
综合考虑后，得到结果
3x15x2d3 d3 32 其中 d3 , d3 0
目标规划的数学模型
产品 甲 乙 资源量
可以用同样的方式来处理其它提出的 资源
决策要求：
设备/台时 3
2
18
原料A/吨
1
0
4
（1）要求甲产品产量不大于乙产品产量。 原料B/吨 0 2 12
如：在引例中，利润的目标值为32， 可能目标值会达不到，所以加上一个
产品 资源
甲 乙 资源量
设备/台时 3
2
18
负偏差变量d3-≥0，把目标函数变成
原料A/吨
1
0
4
3x15x2d332
原料B/吨 单位赢利/
0 3
2 5
12
万元
但是同样，目标值也有可能会超出，所以减去一个正偏差变量
d3+≥0，把目标函数变成
A）恰好达到目标值 B）允许超过目标值 C）不允许超过 目标值
构造一个由优先因子和权系数相对应的偏差变量组成的，要求实 现极小化的目标函数.
用目标规划求解问题的过程：
明确问题，列出 目标的优先级和
权系数
构造目标规 划模型
N
满意否？
Y
据此制定出决策方案
目标规划的数学模型
求出满意解 分析各项目标
完成情况
p （3 3）计划利润指标32，并且尽可能达到或超过这个利润指标.
问：如何安排生产可以使得获利最大？
分析：
p（1 1）要求甲产品的产量不大于乙产品的产量；
（1）产量偏差变量
d1 , d1 0
p 2（2）尽可能充分利用设备台时，不希望加班生产；

运筹学 第四章

运筹学 第四章
1
1
－1
2
表（2）
Cj－Zj
P1
1
P2
1
P3
w1
－w1
w1
w2－4w1
4w1
P4
1
－1
1
（1）由表（1）知，当w1－w2/4 > 0，即 时，满意解为：X＝（13/2，5/4）
（2）由表（2）知，当w2－4w1> 0，即 时，满意解为：X＝（5，2）
（3）当 时，表(1)和表(2)都是满意解
用图解法求解下面的目标规划模型：
东方造船厂生产用于内河运输的客货两用船.已知下年度各季的合同交货量.各季度正常及加班时间内的生产能力及相应的每条船的单位成本
季度
合同交货数
正常生产
加班生产
能力
每条成本/百万
能力
每条成本/百万
1
2
3
4
16
17
15
18
12
13
14
15
5.0
5.1
5.3
5.5
7
7
7
7
6.0
6.4
6.7
7.0
该厂确定安排生产计划的优先级目标为
0
13/2
P4
d1+
－1
1
1
－1
3
w2P3
d4－
－1/4
1/4
[1/4]
－1/4
1
－1
3/4
0
x2
1
1/4
－1/4
－1/4
5/4
表（1）
Cj－Zj
P1
1
P2
1
P3
w2/4
－w2/4

目标规划的图解法课件

目标规划的图解法课件

50 E D
2、先满足P1，OD线段
3、再满足P2，ED线段（满意解） O
50
E (500/11,500/11) ,
d1
d1
d
2
d
2
0
D (360/7,360/7)
,
d1
d1
d
2
0,
d
2
92 / 7
C 100 l2
150
d
2
x1 l1
d
2
l4
第一节 目旳规划旳基本概念与数学模型 一、问题旳提出 二、目旳规划旳基本概念
有关最优解：线性规划是在可行解域内寻找某一点，
使单个目旳到达最优值（最大值或最小值）．而目旳规
划是在可行域内，首先寻找到一种使P1级目旳均满足旳 区域R1，然后再在R1中寻找一种使P2级目旳均满足或尽 最大可能满足旳区域R2（R1），再在R2中寻找一种满 足P3旳各目旳旳区域R3（R2R1），…,如此下去，直 到寻找到一种区域Rk(Rk-1…R1)，满足Pk级旳各目旳， 这个Rk即为所求旳解域，假如某一种Ri (1 i k)已退化 为一点，则计算终止，这一点即为满意解，它只能满足
min
z
P1 (d1
d1 )
P2d
2
s.t 2x1 3x2 300
l1
2x1 1.5x2 180
l 2x2
x1 x2 d1 d1 0
l3
10x1
12 x2
d
2
d
2
1000
1l450
x1,x2
,di
,d
i
0
i 1,2
A
100
l3 d1
B
d1

运筹学线性规划图解法

运筹学线性规划图解法

§2.2 线性规划问题解的概念
设线性规划的标准形式： max z=Σcjxj (1) s.t.Σaijxj=bi i=1,2,…,m (2) xj≥0 j=1,2,…,n (3) 可行域：由约束条件(2)、(3)所围成的区域； 可行解：满足(2)、(3)条件的解X=(x1，x2，…，xn)T为可行解； 基：设A是约束条件方程组的m×n维系数矩阵,其秩为m，B是A中 m×m阶非奇异子矩阵，则称B为线性规划问题的一个基。 设
B=
a11 a21 … am1
a12 … a1m a22 … a2m … … am2 …amm
=(p1,p2, …,pm)
基向量、非基向量、基变量、非基变量： 称pj(j=1,2,…,m）为基向量，其余称为非基向量；与基 向量pj(j=1,2,…,m）对应的xj称为基变量，其全体写成 XB=（x1，x2，…，xm）T；否则称为非基变量，其全体经 常写成XN。 基解：对给定基B,设XB是对应于这个基的基变量 XB=(x1，x2，…，xm)T； 令非基变量xm+1=xm+2=…=xn=0， 由（2）式得出的解X=（x1，x2，…，xm，0，…，0）T 称为基解。 基可行解：所有决策变量满足非负条件(xj ≥0)的基解, 称作基可行解。 可行基：基可行解所对应的基底称为可行基。
x2 x1+2x2=8
4x2=12
线段Q1Q2上的任意点都是最优解
Q1
Q2 x1
3x1=12
x2 •无可行解 例3：
maxz = 3x1 + 2x2 2x1 + x2 ≤ 2 s.t 3x1 + 4x2 ≥ 12 x , x ≥ 0 1 2
约束条件围不成区域 (又称矛盾方程) x1
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
本题三个目标依次表示为： 本题三个目标依次表示为： 产品不超过10 10单位 1、B产品不超过10单位 x2 <=10 利润不低于1600 1600元 2、利润不低于1600元 80x1 + 100x2 >=1600 充分利用2车间的生产能力，尽量不加班。 3、充分利用2车间的生产能力，尽量不加班。 x1 + 2x2 = 40
d2 － d2 +
0 －4/3
σ
C CB 0 0 0 0 XB d3 + x1 d2 － x2 b 12 6 0 3 P1 P2 P3
0 x1 0 1 0 0 0 0 0
0 x2 0 0 0 1 0 0 0
0 x3 1 1/10 －3/5 1/20 0 0 0
P1 d1 － 1 1/2 －1 －1/4 1 0 0
－1 －3/5
－3/10 3/10 1 0 0 0 0 0
σ
P2 P3
最优解 X1 = （24/5，12/5） ， ）
C CB 0 0 0 0 XB x3 x1 d2 － d1 + b 20 8 4 8 P1 P2 P3
0 x1 0 1 0 0 0 0
0 x2 10/3 4/3 10/3 0 0 0
0 x3 1 0 0 0 0 0 0
P1 d1 － 0 0 0 －1 1 0 0
0 d1 + 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
P2 0 0 －1 0 0 1 0
P3 d3 － －5/6 1/6 －2/3 1/6 0 0 1
0 d3 + 5/6 －1/6 2/3 －1/6 0 0 0
+ +
P3( d3-
+ d3 ) }
问题分析ห้องสมุดไป่ตู้
综上所述，本题的数学模型为： 综上所述，本题的数学模型为： 目标函数： 目标函数：min Z={P1d1 , P2d2 , P3( d3 +
+ + d3 )
}
2x1 + 1.5x2 约束 条件 d 1-
≤ 50
+ x2 + - d1 = 10 + = 1600 80x1 + 100x2 + d2 - d2 + x1 + 2x2 + d3 - d3 = 40 + x1 ，x2 ，di ，di ≥0 ,i=1,2,3
d
+ 2
=1600
充分利用2车间的生产能力，尽量不加班。 3、充分利用2车间的生产能力，尽量不加班。 + x1 + 2x2 + d3 - d3 =40
问题分析
目标的重要程度不同， 4）目标的重要程度不同，因此目标的满足有 先有后，即有优先级别。设最重要的为P1 先有后，即有优先级别。设最重要的为P1 次之者为P2 P2级 级，次之者为P2级——
[ 1 ] －2
σ
P2 P3
－6 －8
最终单纯形表
C CB 0 0 0 0 XB x3 x1 d2 － x2 b 12 24/5 36/5 12/5 P1 0 x1 0 1 0 0 0 0 0 0 x2 0 0 0 1 0 0 0 0 x3 1 0 0 0 0 0 0 P1 d1 － 1 2/5 －2/5 0 d1 + －1 －2/5 2/5 0 P2 P3 d3 － －1 1/10 1/20 0 0 1 0 d3 + 1 －1/10 3/5 －1/20 0 0 0 d2 － d2 + 0 0 1 0 0 0 0 0 0 0 0 1 0
问题分析
3）目标约束的目标一定要明确，给出确切的量值， 目标约束的目标一定要明确，给出确切的量值， 即
目标期望值
如：
B产品不超过
10单位
利润不低于
1600元
充分利用2车间的生产能力， 充分利用2车间的生产能力，尽量不加班
问题分析
目标约束不是刚性的，而是弹性的， 4）目标约束不是刚性的，而是弹性的，允许在一定 范围内有偏差，这更接近于实际。为表达这种 范围内有偏差，这更接近于实际。 灵活性， 灵活性，便引入了
目标规划的概念及数学模型
数学模型为： 数学模型为：
目标函数 min Z = {Pl (∑k(Wlk- •dk-+Wlk+ • dk )， 目标约束 l=1,2,…,L} 约束 条件
+)
∑jckjxj+ dk- - dk+ =bk,
k=1,2,…,K
∑jaijxj ≤(= ≥) bi, i=1,2,…,m xj ，dk-，dk+ ≥0 ,j=1,…n;k=1,2,…,K
(
)
− − + + min z = ∑ Pl ∑ Wlk d k + Wlk d k l =1 k =1
L K
(
)
§4.3 解目标规划的单纯形法
目标规划的数学模型结构与线性规划的数学模型结构没有 本质的区别，所以可用单纯形法进行求解。 本质的区别，所以可用单纯形法进行求解。但要考虑目标 规划数学模型的一些特点： 规划数学模型的一些特点： (1) 因目标规划问题的目标函数都是求最小化，所以检验 因目标规划问题的目标函数都是求最小化， 数的最优准则与我们前面讲到的线性规划检验准则是相反 即以所有的σ 为最优准则 为最优准则； 的，即以所有的 j≥0为最优准则； (2) 因为非基变量的检验数中含有不同等级的优先因子，且 因为非基变量的检验数中含有不同等级的优先因子， Pi >>Pi+1，i = 1,2,…,L-1. 所以在判断各检验数大小时得小心； 所以在判断各检验数大小时得小心；
除了前面提到的刚性约束外， 2）除了前面提到的刚性约束外，例2中还提出一 些的希望达到的目标。 些的希望达到的目标。这些要求实际上也是约 束条件，当然这些目标能到达最好， 束条件，当然这些目标能到达最好，实在无法 达到也是可以接受的， 达到也是可以接受的，我们称之为
目标约束
产品不超过10 10单位 如：1、B产品不超过10单位 利润不低于1600 1600元 2、利润不低于1600元 充分利用2车间的生产能力，尽量不加班。 3、充分利用2车间的生产能力，尽量不加班。
≤ ≤
50 40
例2
由于各种原因，对例1的提出一些要求： 由于各种原因，对例1的提出一些要求： 产品不超过10 10单位 1、B产品不超过10单位 2、利润不低于1600元 利润不低于1600 1600元 充分利用2车间的生产能力，尽量不加班。 3、充分利用2车间的生产能力，尽量不加班。
目标的含义
运筹学基础
第四章 目标规划
教 材 运筹学教程》（ 》（第 《运筹学教程》（第三版） 胡运权 主编 清华大学出版社
例1
资源
产品 1车间 2车间 单位利润
A 2 1 80
B 1.5 2 100
限量 50 40
求利润最大的生产方案 利润 约束 条件 max z= 80 x1 + 100x2 2x1 + 1.5x2 x1 + 2x2 x 1， x 2 ≥ 0
优先因子
P看成实数
P1>>P2
问题分析
有时同级别的目标中， 5） 有时同级别的目标中，其重要程度又 有 系数W 差别， 差别，则设置不同的权重（系数W） 。 6) x1 +
2x2 2 x2 +
≤
40 -
系统约束) (系统约束)
+ 3
x1 +
d3
-
d
目标约束) =40 (目标约束)
当对某个资源约束既是系统约束， 当对某个资源约束既是系统约束，又是 目标约束时， 目标约束时，则不再表示为系统约束
问题分析
7）目标规划的目标 ）
产品不超过10 10单位 1、B产品不超过10单位
d 越小越好
-
+ 1
利润不低于1600 1600元 2、利润不低于1600元 d2 越小越好 充分利用2车间的生产能力， 3、充分利用2车间的生产能力，尽量不加班 + d3 和 d3 越小越好
0最佳 0最好
问题分析
7）目标规划的目标函数： ）目标规划的目标函数： 目标规划有多个目标， 目标规划有多个目标，我们已经把它转化 为目标约束， 为目标约束，整个问题的目标就是使得实施结 果与目标期望值的偏差最小 于是本题目标函数表示为： 于是本题目标函数表示为： minZ={P1d1 , P2d2 ,
解目标规划的单纯形法计算步骤
(1) 建立初始单纯形表，在表中将检验数行按优先因 建立初始单纯形表， 子个数分别列成L行 子个数分别列成 行，置k=1。 。 (2) 检查该行中是否存在负数，且对应的前k-1行的系 检查该行中是否存在负数，且对应的前 行的系 数是0。若有，则取其中最小者对应的变量为换入变量， 数是 。若有，则取其中最小者对应的变量为换入变量， 转(3)；否则，转(5)。 ；否则， 。 (3) 按最小比值规则确定换出变量，当存在两个或两 按最小比值规则确定换出变量， 个以上相同的最小比值时， 个以上相同的最小比值时，选取具有较高优先级别的变量 为换出变量。 为换出变量。 (4) 按单纯形法进行基变换运算，建立新的单纯形表。 按单纯形法进行基变换运算，建立新的单纯形表。 (5) 当k=L时，计算结束，表中解即为满意解。否则 时 计算结束，表中解即为满意解。 置k=k+1，返回 。 ，返回(2)
该目标规划和下面线性规划问题等价 Min s.t. z = P1d1- + P2 d2+ + P3 d35x1 + 10x2 + x3 = 60 x1 - 2x2 + d1- - d1+ = 0 4x1 + 4x2 + d2- -d2+ = 36 6x1 + 8x2 + d3- -d3+ = 48 x1 , x2 , x3 , di- ,di+ ≥ 0 , i = 1,2,3.