- 在线时间
- 5 小时
- 最后登录
- 2016-8-1
- 注册时间
- 2016-7-12
- 听众数
- 12
- 收听数
- 0
- 能力
- 0 分
- 体力
- 37 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 21
- 相册
- 0
- 日志
- 1
- 记录
- 0
- 帖子
- 3
- 主题
- 6
- 精华
- 0
- 分享
- 0
- 好友
- 2
升级   16.84% TA的每日心情 | 开心 2016-8-1 18:38 |
|---|
签到天数: 2 天 [LV.1]初来乍到
 |
三、线性规划、整数规划、多元规划、二次规划
: j* ?1 k5 S, O9 z5 D' t# }' {+ ]4 ](1)线性规划
3 ]2 i- d( {( r, h1、含义的理解6 Z9 Y7 ?; C: t$ l: s; E
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.研究线性约束条件下线性目标函数的极值问题的数学理论和方法,英文缩写LP。它是运筹学的一个重要分支。& H ]7 T8 J* i
在经济管理、交通运输、工农业生产等经济活动中,提高经济效果是人们不可缺少的要求,而提高经济效果一般通过两种途径:一是技术方面的改进,例如改善生产工艺,使用新设备和新型原材料.二是生产组织与计划的改进,即合理安排人力物力资源.线性规划所研究的是:在一定条件下,合理安排人力物力等资源,使经济效果达到最好.一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题。满足线性约束条件的解叫做可行解,由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。
7 }+ Q- ?* G8 ]* T3 ^/ ?2、线性规划问题的数学模型的一般形式和模型建立' \% ~) W4 y% N* ?6 J, D
(1)列出约束条件及目标函数 (2)画出约束条件所表示的可行域 (3)在可行域内求目标函数的最优解及最优值(实际问题中建立数学模型一般有以下三个步骤:根据影响所要达到目的的因素找到决策变量;2.由决策变量和所在达到目的之间的函数关系确定目标函数;3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。)0 j9 X0 V4 w9 z. v: ^5 i! U
所建立的数学模型具有以下特点:
3 s1 e T: G7 j [0 } {(1)、每个模型都有若干个决策变量(x1,x2,x3……,xn),其中n为决策变量个数。决策变量的一组值表示一种方案,同时决策变量一般是非负的。
3 x3 \- N* C5 a5 G5 m(2)、目标函数是决策变量的线性函数,根据具体问题可以是最大化(max)或最小化(min),二者统称为最优化(opt)。7 n2 w: c+ P/ N. ~0 J
(3)、约束条件也是决策变量的线性函数。当我们得到的数学模型的目标函数为线性函数,约束条件为线性等式或不等式时称此数学模型为线性规划模型。+ F; A" m( o* e, M
3、实例
; R l+ y2 n% N P) l生产计划问题
1 O: y: o$ r$ A3 C8 l4 Q问题:4 e6 l: k9 D. e0 P( m
某企业要在计划期内安排生产甲、乙两种产品,这个企业现有的生产资料是:设备18台时,原材料A :4吨,原材料 B: 12吨;已知单位产品所需消耗生产资料及利润如下表。问应如何确定生产计划使企业获利最多?
( R3 ]. m+ \( l! R6 Q7 s: H9 Y 产品
2 X* }) A' o) c* Z" s1 [/ z资源 甲 乙 资源量
( [- O: G) V/ f( V' e设备/台时 3 2 18
- X- h$ S6 C- k5 _原料A/吨 1 0 4
: S; K7 R8 F/ K& l& c原料B/吨 0 2 12
6 }+ H) b; G: w* R6 j @8 W: A+ D- A2 B单位赢利/万元 3 5
" h9 u+ s8 B" e G. f2 q设x1为甲产品分配的设备台数,x2为乙产品分配的台数。则
0 T g+ z6 [. l* L9 b% l8 R( O条件限制为:
, V4 H9 d; R! \4 B, ~3*x1+2*x2 18
. ?8 n) T- @( Z* K+ U( _1*x1+0*x2 4
& L7 X( K6 c& R x5 |% }0*x1+2*x2 12# M. ^7 Q/ A. k; i/ V6 p
x1 0,x2 09 e6 X' H$ W9 F: C+ L+ r
求max z=3*x1+5*x2
: i% A) s1 l2 V9 {* \, B6 g用lingo编程,程序如下:
* N/ @# F0 O& ~& fmax=3*x1+5*x2;5 ]! S, D" u- U& A3 U7 D
3*x1+2*x2<=18;
& _: s* B& R- o; Lx1<=4;, q* T% c, _+ z m! o. k
x2<=6;" ^) a8 G* \$ i5 b
x1>=0;
8 \" Y' F% R( p" h! Q/ F5 Zx2>=0;& a% P0 S) q2 Q, g- C8 @( G) M, \
结果为:
: w8 Q2 l8 i3 N4 J. eGlobal optimal solution found. u" Y( G& R; @' k* e+ _9 e( e
Objective value: 36.00000( E* H3 F3 O: z% f! ^
Total solver iterations: 1
/ S! }3 n! J( |0 Y Variable Value Reduced Cost
4 \' }# k: g6 Q' L% N9 B9 o X1 2.000000 0.000000& k2 D, P4 V# c3 x' ?
X2 6.000000 0.000000. u4 `. w( h4 H
9 h9 t! y \( z; e
Row Slack or Surplus Dual Price
* [0 ]. w1 g9 ~! s& \; `! z; A) C1 X 1 36.00000 1.0000005 i/ t [" V$ `) L$ t- [ R
2 0.000000 1.0000009 J- Q% K$ z7 m( A5 w: R
3 2.000000 0.000000
4 C" S6 ?& a8 F5 R 4 0.000000 3.000000( g( @: t; D+ T; y
5 2.000000 0.000000
! S' q" ^. ?6 j$ t" ~* w. n" g 6 6.000000 0.0000006 }$ e% z* N( o. _6 B9 E, Z- g! H0 m# f
即在x1=2,x2=6时,企业获利最多,为36万元。
9 s7 y3 v2 q, x3 M6 c3 B4、线性规划的应用
+ Y7 c b( g3 [: m. R* L+ J在企业的各项管理活动中,例如计划、生产、运输、技术等问题,线性规划是指从各种限制条件的组合中,选择出最为合理的计算方法,建立线性规划模型从而求得最佳结果. 广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策,提供科学的依据。) F0 Q1 f; u' R% ]5 [
(2)整数规划 ~5 x0 e9 j7 R6 H4 |! `
一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性,二次和非线性的整数规划。 在线性规划问题中,有些最优解可能是分数或小数,但对于某些具体问题,常要求某些变量的解必须是整数。例如,当变量代表的是机器的台数,工作的人数或装货的车数等。为了满足整数的要求,初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解,所以应该有特殊的方法来求解整数规划。在整数规划中,如果所有变量都限制为整数,则称为纯整数规划;如果仅一部分变量限制为整数,则称为混合整数规划。整数规划的一种特殊情形是0-1规划,它的变数仅限于0或1。不同于线性规划问题,整数和0-1规划问题至今尚未找到一般的多项式解法。- j+ R8 ?( c8 [9 Q' `, Y5 E. f& G
组合最优化通常都可表述为整数规划问题。两者都是在有限个可供选择的方案中,寻找满足一定约束的最好方案。有许多典型的问题反映整数规划的广泛背景。例如,背袋(或装载)问题、固定费用问题、和睦探险队问题(组合学的对集问题)、有效探险队问题(组合学的覆盖问题)、旅行推销员问题, 车辆路径问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用,而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。, k& n7 }3 {% R/ Q) p
整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的 。解整数规划最典型的做法是逐步生成一个相关的问题,称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题(衍生问题称为松弛问题的源问题)。通过松弛问题的解来确定它的源问题的归宿,即源问题应被舍弃,还是再生成一个或多个它本身的衍生问题来替代它。随即再选择一个尚未被舍弃的或替代的原问题的衍生问题,重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法,它们都是在上述框架下形成的。+ q. X. O0 a2 l* w0 @6 M/ ^% f
0-1规划在整数规划中占有重要地位,一方面因为许多实际问题,例如指派问题、选地问题、送货问题都可归结为此类规划,另一方面任何有界变量的整数规划都与0-1规划等价,用0-1规划方法还可以把多种非线性规划问题表示成整数规划问题,所以不少人致力于这个方向的研究。求解0-1规划的常用方法是分枝定界法,对各种特殊问题还有一些特殊方法,例如求解指派问题用匈牙利方法就比较方便。1 E7 Y/ V* C4 I5 m! r; j% m
(4)二次规划( W' ^2 F# W: B/ I( L
二次规划是非线形规划中一类特殊的数学规划问题,它的解是可以通过求解得到的。通常通过解其库恩—塔克条件(KT条件),获取一个KT条件的解称为KT对,其中与原问题的变量对应的部分称为KT点。
% H- C2 q1 [# C二次规划分为凸二次规划与非凸二次规划,前者的KT点便是其全局极小值点,而后者的KT点可能连局部极小值点都不是。若它的目标函数是二次函数,则约束条件是线性的。由于求解二次规划的方法很多,所以较为复杂;其较简便易行的是沃尔夫法,它是依据库恩-塔克条件,在线性规划单纯形法的基础上加以修正而成的。此外还有莱姆基法、毕尔法、凯勒法等。
: \3 q$ t7 _% W0 C9 f8 _ O2 P# a# a" L
* [! O9 j! x: @# E3 h
1 ]- X% X3 j8 R y+ p
|
zan
|