当前位置：文档之家 › 第四章 数学规划问题(中文)汇编

第四章 数学规划问题(中文)汇编

  • 格式：ppt
  • 大小：468.50 KB
  • 文档页数：48

下载文档原格式

  / 48

合集下载

运筹学——.整数规划与分配问题

运筹学——.整数规划与分配问题

2.4 匈牙利法实例(2)
第二步：找出矩阵每列的最小元素，再分别从各列中减去。
必定满足：bij = aij–ui–vj
0 11 2 0 0
8 0 3 11 0
7 5 0 11 10 4 2 5 0 9 5 0 5 0
8 2 5 0 5 4 3 0 0 11 4 5
二、分配问题与匈牙利法
2.3 匈牙利法
分配问题可以用单纯形法或运输表求解。 库恩(W.W.Kuhn)于1955年提出了指派问题的解 法，他引用了匈牙利数学家康尼格(D.Kö nig)一 个关于矩阵中零元素的定理：系数矩阵中独立0 元素的最多个数等于能覆盖所有0元素的最少直 线数。这个解法称为匈牙利法。
二、分配问题与匈牙利法
2.2 分配问题实例(1)
例：有一份中文说明书，需要译成英、日、德、 俄四种文字。现有甲、乙、丙、丁四人，他们 将中文说明书译成不同语种的说明书所需时间 如下，问应指派何人去完成工作，使所需总时 间最少? 人员
任务 译成英文 译成日文 译成德文 译成俄文 甲 乙 丙 丁 7 8 11 9 2 15 13 4 10 4 14 15 9 14 16 13
一、整数规划的特点及作用
1.2 0-1整数规划
某公司拟在市东、西、南三区建立门市部。拟 议中有7个位置（点）Ai供选择。规定
在东区，由A1，A2，A3三个点中至多选两个； 在西区，由A4，A5两个点中至少选一个； 在南区，由A6，A7两个点中至少选一个。
如选用Ai点，设备投资估计为bi元，每年可获利 润估计为ci元，但投资总额不能超过B元。 问：应如何选址，可使年利润为最大？
第一步：找出每 行的最小元素， 每行对应减去这 个元素。

第4章 整数规划

第4章 整数规划

第4章 整数规划判断:用分枝定界法求解一个极大化的整数规划问题，任何一个可行解的目标函数值是该问题目标函数值的下界；指派问题数学模型的形式同运输问题十分相似，故也可以用表上作用法求解；效率矩阵的任一行（或列）减去（或加上）任一常数，指派问题最优解不会受到影响； 匈牙利法只能用于平衡分配问题；对于极大化问题，匈牙利法不能直接求解。

整数规划问题解的目标函数值优于其相应的线性规划问题的解的目标函数。

用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解。

用分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可行解时，通常可任取其中一个作为下界值，在进行比较剪枝。

分配问题的每个元素都加上同一个常数k ，并不会影响最优分配方案。

分配问题的每个元素都乘上同一个常数k ，并不会影响最优分配方案。

分配问题域运输问题的数学模型结构形式十分相似，故也可以用表上作业法求解。

隐枚举法也可以用来求解分配问题简答试述分枝定界法求解问题的主要思想。

试述隐枚举法的步骤。

试讲述割平面方法的基本原理. 试例举三种应该剪枝的情况。

计算题分枝定界法用分枝定界法求解下列整数规划问题12max Z x x =+1212129511414123,x x x x x x +≤-+≤≥0且为整数用分枝定界法求解下列整数规划问题12max 32Z x x =+121212231429,x x x x x x +≤+≤≥0且为整数用分枝定界法求解下列整数规划问题12max 2010Z x x =+1232312312324434323,,x x x x x x x x x x x ++≤≤+≤≥－--0且为整数用分枝定界法求解下列整数规划问题12max 79Z x x =+121212136735,x x x x x x x +≤+≤≥－0，且为整数用分枝定界法求解下列整数规划问题123max 33Z x x x =++123231231231324432323,,,x x x x x x x x x x x x x ++≤≤+≤≥－--0，且为整数用分枝定界法解下列整数规划问题：1212121212232478188..3219,0MaxZ x x x x x x s t x x x x =+-+≤⎧⎪+≤⎪⎨+≤⎪⎪≥⎩且为整数用分枝定界法解下列整数规划问题1212121212250..6221,0MaxZ x x x x x x s t x x x x =++≤⎧⎪-+≤⎪⎨+≤⎪⎪≥⎩且为整数用分枝定界法解下列整数规划问题12312121225231050..7228,0,MaxZ x x x x x s t x x x x x =-+-+≤⎧⎪-≤⎨⎪≥⎩为整数用分枝定界法解下列整数规划问题12312341234345272222..0,1,2,3,4,5,j MaxZ x x x x x x x x x x x s t x j x x =-+-⎧-+-+=⎪⎪⎪-++=⎨⎪≥=⎪⎪⎩为整数用分枝定界法求解下列整数规划模型12max 23z x x =+121257354936x x x x +≤+≤12,0x x ≥且为整数有如下整数规划问题12max z x x =+12129511414123x x x x +≤-+≤12,0x x ≥且为整数试用分枝定界法求其最优解。

数学规划问题

数学规划问题
首先将问题转化为matlab要求的格式;即求出 fun,A,b,aeq,beq,X0,Lb,Ub 解:首先建立一个m文件fun3.m
x1
function y=fun3(x)
y=-exp(x(1))*x(2)^2*(3-exp(x(1))-x(2)^2); 存储为fun3.m
因题目中有非线性约束条件，所以建立非线性约束m-文件。 然后建立一个 m文件 fun4.m function [c,cep]=fun4(x) c=[]; % c为非线性不等式,且为c<=0 cep=exp(x(1))+x(2)^2-3; % cep为非线性等式 然后存储为fun4.m 最后在命令窗口中输入：
同时返回fval=-2
对应到原来的线性规划中即知目标函数的最大值为2，此时 x1=4,x2=1,x3=9。
第二节 无约束规划计算方法
一、实验目的
1、了解无约束规划问题的求解原理与方法 ；
2、会用Matlab软件求解无约束规划问题。
二、实验原理和方法
无约束规划问题的解法一般按目标函数的形式分为两大类： 一类是一元函数的一维搜索法，如黄金分割法、插值法等； 另一类是求解多元函数的下降迭代法。
在命令窗口输入： x0=[0;0]; x=fminunc(‘fun2’,x0) 结果显示： f =5.2979e-011 x =1.0673 0.1392 则非线性方程组的解为x1=1.0673,x2=0.1392。
第三节 约束非线性规划计算方法 一、实验目的
1、了解约束非线性规划问题的求解原理与方法； 2、会用Matlab软件求解约束非线性规划问题。
三、实验内容与步骤
在Matlab软件中，求解无约束规划的常用命令是：
x=fminunc(‘fun’,x0) 其中，fun函数应预先定义到M文件中，并设置初始 解向量为x0。

第四章 规划问题

第四章 规划问题
j=1
p
i=1
yi
=q
三、固定成本问题 (Fixed cost problem)
例4.8 某公司制造小、中、大三种尺寸的容器，所需 资源为金属板、劳动力和机器设备，制造一个容器所 需的各种资源的数量如下表所示：不考虑固定费用， 小、中、大号容器每售出一个其利润分别为4万元、5 万元、6万元，可使用的金属板有500吨，劳动力有300 人/月，机器有100台/月，另外若生产，不管每种容器 生产多少，都需要支付一笔固定费用：小号为100万元， 中号为150万元，大号为200万元。问如何制定生产计 划使获得的利润对大？
0.3x1 + 0.7x2 <= 250
s.t.
00..32xx
1 1
+ 0.1x2 + 0.5x2
<= 100 <= 150
(1)
0.2x1 + 0.4x2 <= 120
(2)
x1, x2 >= 0,且为整数
• 工序B3只能从两种加工方式中选择一种，那么约束条件 （1）和（2）就成为相互排斥的约束条件。为了统一在一
– 仅有一部分变量要求为整数的称为混合整数规划 （Mixed Integer Programming）；
– 有的变量限制其取值只能为0或1，这类特殊的整数规 划称为0－1规划(0-1 Integer Programming )。
第一节 整数规划问题及其数学模型
一、整数规划问题
例4.1 某工厂生产甲、乙两种设备，已知生产这两种设 备需要消耗材料A、材料B，有关数据如下，问这两种 设备各生产多少使工厂利润最大？
y1
+ y2
=1
xy11,,
x2 y2

第4章整数规划

第4章整数规划

第一步：分枝。在B的最优解中任选一个取值不满足整数约 束的变量xj，设其值为bj。用[bj]表示小于bj的最大整数，构 造两个约束条件： xj≤[bj]和xj≥ [bj]+1
将这两个约束条件分别加入到B问题中，形成两个后继 线性规划问题B1和B2，求解这两个问题。 定界：对于后继问题求得的结果，找出最优目标函数 值最大者作为新的上界z+，符合整数约束的最优目标函数值 的最大者作为新的下界z-。 第二步：比较和剪枝。各分枝的最优目标函数值中若有小于 z-者，则剪掉这枝。若大于z-且不符合整数条件，则重复第 一步骤，继续分枝。直到z-=z*=z+为止，得最优解。
1
0 0
0
1 0
1 4 3 4
-1/4
3/4 -1/2
1 4 1 4
1/4
1/4 -1/2
3 4 7 4
cj zj
找出非整数解变量中分数部分最大的一个基变量！
m a x z x1 x 2 x1 x 2 1 3 x1 x 2 4 x ,x 0 1 2
B A (3
1 4
, 2
1 2
)
B2 问 题
2 x1 3 x 2 1 4 x1 0 .5 x 2 4 .5 x1 4 x ,x 0 1 2
C
0
x1
B点 (3,
2
2 3
)
B3 问 题
m a x z 3 x1 2 x 2 2 x1 3 x 2 1 4 x1 0 .5 x 2 4 .5 x1 3 x 2 2 x1 , x 2 0 m a x z 3 x1 2 x 2 2 x1 3 x 2 1 4 x 0 .5 x 2 4 .5 1 x1 3 x 3 2 x1 , x 2 0

第4章整数规划——指派问题

第4章整数规划——指派问题


13 11 2 0 10 11 57 4 4 2 13 7 0 0 6 9 5 32 0 0
0 0 X 1 0
0 0 1 1 0 0 0 0 0 0 1 0

故可得到指派问题的最优解X，这样 安排能使总的维修时间最少，维修时间为 z=4＋4＋9＋11=28（小时）。
X (2)
都是指派问题的最优解。
4 指派问题
4.3 指派问题的求解 指派问题既是一类特殊的整数规划问题，又是特殊的运输问 题，因此可以用多种相应的解法来求解，然而这些解法都没有充 分利用指派问题的特殊性质，有效地减少计算量，直到1955年库 恩（W. W. Kuhn）提出的匈牙利法才有效地解决了指派问题。 匈牙利法的理论基础 定义2 独立零元素组 在效率矩阵中，有一组在不同行不同 列的零元素，称为独立零元素组，其每个元素称为独立零元素。 5 0 2 0 2 3 0 0 C 【例4】 已知效率矩阵 0 5 6 7 4 8 0 0 求其独立零元素组。
4 指派问题
0 , 不 指 派 第 i小 组 维 修 第 j台 机 床 x ij ( i , j 1, 2 ,3, 4 ) 1, 指 派 第 i 小 组 维 修 第 j 台 机 床 机车 该问题的数学模型为： 1 2 3 4 4 小组 min z cij xij i 1 j 1 1 x11 x12 x13 2 x11 15 x12 2 x21 x22 x23 任务约束 4 x 1, j 1, 2 , 3 , 4 3 x31 x32 x33 ij i 1 4 x41 x42 x43 人员约束 4 x ij 1, i 1, 2 , 3, 4 j 1 x ij 0 或 1 i , j 1 , 2 , 3 , 4

运筹学第四章--整数规划和分配问题(新)aPPT课件


-
1
整数线性规划的一般形式: n max(或min)z cj xj j 1
n
aij xj ( 或 ）bi (i 1,2,...m)
j 1
xj 0( j 1,2,...n),且部分或全部取整数
例1.求下述整数规划问题的最优解
max z 3x1 2x2
2x1 3x2 14 x1 0.5x2 4.5
先不考虑整数解的限制，用单纯形法求 解其松弛问题，如果求得的解恰好是整数解， 则得整数规划最优解，停止计算。否则，将 松弛问题分解为两个子问题（也称后继问 题），每个子问题都是在原松弛问题的基础 上增加一个变量取整数的约束条件，这样就 缩小了原来的可行域，然后用单纯形法求解， 直至得到最终结果。
-
21
-
23
例.用分枝定界法求下述数整规划问题的最优
maxz 3x1 2x2
2x1 3x2 14 x1 0.5x2 4.5 x1, x2 0,且均取整数值
-
24
-
25
-
26
-
27
-
28
-
29
第四节 割平面法 一、割平面法的基本思想
先不考虑整数条件，用单纯形法求解其 松弛问题，若得整数解，即得整数规划最优 解。否则，增加线性约束条件（称为割平面 方程），将原问题的可行域切割掉一部分， 被切割掉的都是非整数解，再用单纯形法求 解新的线性规划问题，依次进行下去，直到 使问题的最优解恰好在可行域的某个具有整 数坐标的顶点上得到。
0.5 + 0.4 x4 + 0.4 x5≥ 1
-
35
2. 借助单纯形表法
对求解整数规划问题的松弛问题（LP问题）得到
最优单纯形表，设xi=bi 是最优解中取分数值（分数 部分最大）的基变量，则有

数学规划模型 2

与送水方案无关！ 与送水方案无关！ 450×160=72,000(元)与送水方案无关！ 与送水方案无关！ 与送水方案无关
引水管理费+ 引水管理费+其他费用
其他费用: 元 千吨 其他费用:450元/千吨
确定送水方案使利润最大 确定送水方案使利润最大
使引水管理费最小ห้องสมุดไป่ตู้
模型建立
决策变量
确定3个水库向 个小区的供水量 确定 个水库向4个小区的供水量 个水库向 水库i 水库 向j 区的日供水量为 xij（x34=0） ）
求解
A(100) 100 30 B(120) 40 30 50 C(100) 50 甲(30;50) 乙(70;70) 丙(10;20) 丁(10;40)
Global optimal solution found. Objective value: Total solver iterations: Variable X11 X12 X13 X14 X21 X22 X23 X24 X31 X32 X33 Value 0.000000 100.0000 0.000000 0.000000 30.00000 40.00000 0.000000 50.00000 50.00000 0.000000 30.00000
货机装运
模型建立
x11 + x21 + x31 + x41 10 x12 + x22 + x32 + x42 = 16 x13 + x23 + x33 + x43 = 8
xij--第i 种货物装入第 个货舱的重量 --第 种货物装入第j 平衡 要求 约束 条件 货物 供应
10； ； 6800 16； ； 8700 8； ； 5300

第四章数学规划模型

1100吨, 分别供给 A地1700吨, B 地11吨, C 地200吨和 D
100吨, 已知每吨运费如表所示, 试建立一个使运费达到 最小的调拨计划.
销地
产地
A
B
C
D
甲
21
25
7
15
乙
51
51
37
15
单位路程运费表
分析 设从第 i个产地到第 j个销地的运输量为 xij , 运
输成本为cij ,则问题的目标函数为
⑶由于市场需求变化, 每公斤 A1的利润增加到30元,
应否改变生产计划?
解 设 x1, x2 表示这两种产品每天所消耗牛奶的数量 （单位：桶）. 则用于生产A1的牛奶可获利 3 24 x1, 用于生产A2 的牛奶可获利 4 16 x2 , 则目标函数为
z 72x1 64x2.
min 0.1* x2 0.2* x3 0.3* x4 0.8* x5; x1 2* x2 x4 100; 2* x3 2* x4 x5 100; 3* x1 x2 2* x3 3* x5 100;
End
运行后得到该问题的解为
X2 25.00000 X3 0.000000 X4 25.00000 X5 0.000000 X1 25.00000
非负性 xi 0,i 1, 2, ,5.
从分析中可以看出, 此问题的关键是确定每种方案下 的余料数.
设 xi i 1, 2, ,5 表示第i 种方案中使用的原料钢
筋数, 则余料数为
z 0.1x2 0.2x3 0.3x4 0.8x5.
而相应的限制条件为
故原问题的数学关系式为
x
x 该问题即是从 的每一个顶点, w12

第四章 数学规划问题(中文)


x1 + x 2 + L + x n = S
④假设在一个生长期内树木至多只能生长一个高度级。 假设在一个生长期内树木至多只能生长一个高度级。 n-1)是生长参数 即第i级的数目进入第i+1 是生长参数， 设gi (i=1, 2, …, n-1)是生长参数，即第i级的数目进入第i+1 级的比例数。 级的比例数。 （２）建模及计算 设向量Ｚ表示经过一个生长期后， 设向量Ｚ表示经过一个生长期后，森林中树木高度的 分布。 分布。则有
M = P2 g 1 x1 + ( P3 − P2 ) g 2 x 2 + L + ( Pn − Pn −1 ) g n −1 x n −1
max M = P2 g1 x1 + ( P3 − P2 ) g 2 x2 + L + ( Pn − Pn −1 ) g n −1 xn −1 s.t. x1 + x2 + L + xn = S g1 x1 ≥ g 2 x2 ≥ L ≥ g n −1 xn −1 ≥ 0 x ≥ 0 i = 1,2,L, n i
min W= 2πρDh(b 2 + h 2 )
1 2
1 2
π 2 E(D 2 + h 2 ) P (b 2 + H 2 ) ≤ πDhH 8(b 2 + H 2 ) 1 P (b 2 + H 2 ) 2 s.t. ≤σy πDhH D1 ≤ D ≤ D2 , H 1 ≤ H ≤ H 2
-
+ 6
+ 3
+ 4
+ 5
2
∑ ∑ ∑ ∑ ∑ ∑
§6 .2 动态规划模型
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

1
min W= 2 Dh(b2 h2 ) 2




s.t.






1
P(b2 H 2 ) 2 2 E(D 2 h 2 )
DhH
8(b2 H 2 )
1
P(b 2 H 2 ) 2
DhH
y
D1 D D2 , H1 H H 2
• 非线性规划问题求解比较复杂： • ① 用线性规划、二次规划来逐步逼近
设 xij 表示设备Ai 安在B j 处的台数， yi 表示购 置 Ai 的台数，Z 表示总的经济效益。
max
mn
Z
Cij xij
i1 j 1
∑n
xij ≤ yi + ai
j=1
i = 1,2, ,m
∑m
xij ≤b j
s.t. i=1
j = 1,2, , n
∑m
Pi yi ≤ M
非线性规划的方法；②随机试验法等； • ③ 可行方向法、凸单纯形法等； • ④ SUMT外点法、SUMT内点法、乘子法等。
4．整数规划模型
实例四 某工厂需要 m 种设备A1 ，A2 ，…，Am ，其中Ai 的单价P为i 元，该厂 已有第 i 种设备ai 台（i=1，2，…，m）。今有资金 M 元可用于购置这些设备， 该厂有 n 处可安装这些设备，B j 处最多可安装 bj 台，一台设备Ai 安B在j 处， 经济效益为 Cij 元，问应如何购置和安装这些设备，才有使总经济效益最高。
第四章 数学规划
线性规划模型 实例一 合理伐木
森林中的每年都要有一批被砍伐出售，为了使这片森 林不被耗尽而且年年都能有收获，每砍伐一棵时，应该就 地补种一棵幼苗，使森林树木的总数保持不变。被出售的 树木，其价值取决于树木的高度，我们希望能够找到一个 方案，在维持收获的前提下，如何砍伐树木，才能获得最 大的经济价值？
… [hn-1, ∞)
②假设树木经过一个生长期后被砍伐，再就地补种幼 苗，其状态和初始状态相同。 ③设树木总和为Ｓ。设X=(x1, x2, …, xn)T为初始树木向 量，因此有
x1 x2 xn S
④假设在一个生长期内树木至多只能生长一个高度级。 设gi (i=1, 2, …, n-1)是生长参数，即第i级的数目进入第i+1 级的比例数。
假设 ①因为出售的树木，价值与树木的高度有关，所以 我们把树木生长情况用高度区间来表示，即高度用h1, h2, …, hn, …表示。这样就可用下表表示各确定高度区间 与价格之间的关系。
级别 1(幼苗)
2 3
…
n
价格
P1=0 P2 P3 …
Pn
高度区间
[0, h1) [h1, h2) [h2, h3)
i=1
xij , yi ≥0, 且xij , yi : 整数
i = 1,2, , m; j = 1,2, , n
所有的变量都是整数的规划，称整数规划问题为纯 整数规划问题。解此类问题的方法有：①分枝定界算法； ②割平面法；③分解方法；④松弛方法；⑤群论方法； ⑥动态规划法等。
２．多目标规划模型
i=1,2,3
xi 0
y1 4.2x1 2.4x2 2.2x3 min
y2 x1 x2 x3 max
多目标规划：含有多个目标 求解多目标规划问题的方法有约束法、分层
（２）建模及计算 设向量Ｚ表示经过一个生长期后，森林中树木高度的
分布。则有
Z ((1 g1 )x1,g1x1 (1 g2 )x2 ,g2x2 (1 g3 )x3 ,, gn2xn2 (1 gn1 )xn1,gn1xn1 xn )T
Ｙ=(y1, y2, …, yn)T为收获向量。故 y１+y２+…+yn
M P2g1x1 (P3 P2 )g2x2 (Pn Pn1)gn1xn1max M P2 g1x源自 (P3 P2 )g2 x2
(Pn Pn1)gn1xn1
s.t.

x1 g1
x1
x2
xn g2 x2
就是收获的总数，从而补种向量为 Ｒ＝（y１+y２+…+yn, 0, …, 0)T
依据维持每年收获的原则，有 生长期未状态－收获＋新的幼苗替换＝生长期状态
即 Ｚ－Ｙ＋Ｒ＝Ｘ
y2 y3 yn g1x1

y2

g1x1

g 2 x2
y3 g2x2 g3x3
S g n 1 xn 1

0
xi 0 i 1,2,, n
线性规划问题：若干个等式或不等式约束下的优化问题。 求解：单纯形法
§2. 非线性规划
实例一 元件是在 A 点铰支的钢管。在 A 点，结构受到垂直 负荷载 2P。设已选定管壁厚度为 h，跨度为 2b。试选择钢管 的平均直径 D 与架高度 H，使杆件既不屈服又不失平稳，而 且架的总重量最轻。

yn1

gn2 xn2

gn1xn1
yn gn1xn1
因为yi≥0，i=1, 2, …, n。可推出
g1x1 g2x2 gn1xn1 0
设收获的总价值为Ｍ，则有
M P2 y2 P3 y3 Pn yn
利用前面的方程组及上式，我们得到
• 在许多客观实际问题中，要达到的目标往往 不止一个。例如，设计导弹时既要使其射程最远 有要燃料最省，还要精度最高。这类含有多个目 标的优化问题称为多目标规划问题。
实例 设市场上有香蕉、苹果、葡萄三种水果， 其单价分别为 4.2 元/千克，2.4 元/千克，2.2 元/千 克。现在某单位要筹办一次节日茶话会，要求买水 果的重量不少于 10 千克，香蕉、苹果的总和不少 于 6 千克，现共有 30 元钱，问如何确定最好的购 买方案。
设x1 ,x2 ,x3 分别为购买香蕉、苹果、葡萄三种水果 的重量。用于买水果的总钱数为y1 ,所买的水果的总量 为 y2 ，自然，我们希望 y1 取最小值，y2 取最大值。
约束条件为 s.t.
并使
4.2x1 2.4x2 2.2x3 30

x1 x2 x3 10 x1 x2 6