QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2107|回复: 3
打印 上一主题 下一主题

[课件资源] 规划问题

[复制链接]
字体大小: 正常 放大
Jessew        

6

主题

12

听众

21

积分

升级  16.84%

  • TA的每日心情
    开心
    2016-8-1 18:38
  • 签到天数: 2 天

    [LV.1]初来乍到

    社区QQ达人

    跳转到指定楼层
    1#
    发表于 2016-7-29 19:16 |只看该作者 |正序浏览
    |招呼Ta 关注Ta
    三、线性规划、整数规划、多元规划、二次规划6 A% E3 i  o2 z" J" ^8 Z1 K
    (1)线性规划$ C! |- C& A% X( r
    1、含义的理解5 G4 x7 F4 n" s
    线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.研究线性约束条件下线性目标函数的极值问题的数学理论和方法,英文缩写LP。它是运筹学的一个重要分支。/ u( O: [% f/ d# S4 k
    在经济管理、交通运输、工农业生产等经济活动中,提高经济效果是人们不可缺少的要求,而提高经济效果一般通过两种途径:一是技术方面的改进,例如改善生产工艺,使用新设备和新型原材料.二是生产组织与计划的改进,即合理安排人力物力资源.线性规划所研究的是:在一定条件下,合理安排人力物力等资源,使经济效果达到最好.一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题。满足线性约束条件的解叫做可行解,由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。5 F% L9 L. }- ]% u2 J+ I
    2、线性规划问题的数学模型的一般形式和模型建立
    ' ?0 b, V7 I; @/ r(1)列出约束条件及目标函数 (2)画出约束条件所表示的可行域 (3)在可行域内求目标函数的最优解及最优值(实际问题中建立数学模型一般有以下三个步骤:根据影响所要达到目的的因素找到决策变量;2.由决策变量和所在达到目的之间的函数关系确定目标函数;3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。)$ \% k: m1 A$ C( X! ]- G
    所建立的数学模型具有以下特点:
    % G- i1 X* C  ?# [. {(1)、每个模型都有若干个决策变量(x1,x2,x3……,xn),其中n为决策变量个数。决策变量的一组值表示一种方案,同时决策变量一般是非负的。
    5 Y# m6 O( Y% A$ v' Q(2)、目标函数是决策变量的线性函数,根据具体问题可以是最大化(max)或最小化(min),二者统称为最优化(opt)。
    % V2 n6 n5 _5 L+ E* y(3)、约束条件也是决策变量的线性函数。当我们得到的数学模型的目标函数为线性函数,约束条件为线性等式或不等式时称此数学模型为线性规划模型。
    1 |3 S) L  A( o# R; P3、实例
    9 Y  ]4 s8 r. i% {+ |% W+ k生产计划问题
    5 D7 G+ Y  r8 o$ a0 H  ?* A7 y+ _/ b问题:5 ]2 i: z6 J5 \1 J% B7 r
    某企业要在计划期内安排生产甲、乙两种产品,这个企业现有的生产资料是:设备18台时,原材料A :4吨,原材料 B: 12吨;已知单位产品所需消耗生产资料及利润如下表。问应如何确定生产计划使企业获利最多?
      v$ B2 O9 ?' q) n      产品: m3 ?9 ]0 n& ?4 O! n& G
    资源        甲        乙        资源量
    + t- k% \0 P$ O6 C8 K* C, c设备/台时        3        2        18
    ( i# r2 r5 \8 ^! B原料A/吨        1        0        48 ?# k/ ^1 I1 ]0 g  u; U# \
    原料B/吨        0        2        12# s& |( G; Q+ i6 ^3 U( U0 H, s) y
    单位赢利/万元        3        5         
    : C5 X7 z& n& p- `+ h$ B" I5 Q/ g( v设x1为甲产品分配的设备台数,x2为乙产品分配的台数。则
    5 l" E+ F9 u1 Z/ Q条件限制为:' G' k7 N( K8 i' s# D) H
    3*x1+2*x2 18# E7 s0 g6 I4 `. `4 _: B# W; b; ?1 M. ~
    1*x1+0*x2 4
    - a/ ~0 M: f$ b" x0*x1+2*x2 12
    / |8 }& z" D1 Z. k; S: m6 E8 W+ jx1 0,x2 05 o3 ]( I* ]' J4 a# G+ G
    求max z=3*x1+5*x2: d1 ]/ \5 J8 }+ ^) l% W9 ?
    用lingo编程,程序如下:
    & s: o: b/ v: n- u! s9 l1 ~max=3*x1+5*x2;! t& S- k& E+ r" {' k  p5 Y/ l
    3*x1+2*x2<=18;
    # Y: C% i  g5 nx1<=4;
    ' Q( O% m% l& I8 z1 {5 Sx2<=6;* N4 J" Q) o" ?4 Y
    x1>=0;
    - c% |3 E, j  q, Rx2>=0;# ]" G: F# ?; x6 O! I' U
    结果为:! B- t/ D- T% p2 w; m* q: m& {
    Global optimal solution found.6 s' n- F! n6 f3 T7 D  L: d  [: `
    Objective value:                              36.00000* k7 ~: d0 u& F' k9 ^. G
    Total solver iterations:                             18 q) ?- W; q' u2 C# U( I5 V
            Variable           Value        Reduced Cost
    7 G7 K( z% Y) G8 M                X1        2.000000            0.000000
    & `# P! q0 y6 g. b                X2        6.000000            0.0000008 }8 h8 T6 f- g- B- r+ p% ~
    ) S' R1 W8 \; p5 h9 @/ `8 [
            Row    Slack or Surplus      Dual Price1 D  A; T* K, P, U
             1        36.00000            1.0000003 t$ f/ m& H: u4 z2 t6 ?9 D. Q
              2        0.000000            1.000000
    5 u0 |" @. t# o  m& _          3        2.000000            0.000000
    ) n+ N% W# h5 O# |1 o2 j1 W9 @          4        0.000000            3.0000008 O1 M: o9 j9 d: t9 \
              5        2.000000            0.000000
    & d3 x( E" ^7 w" T/ N$ S3 P9 r          6        6.000000            0.000000
    ' f' f; W+ ]( i" ]0 k. W7 K2 E即在x1=2,x2=6时,企业获利最多,为36万元。; w' x! T: ^' _4 `- \
    4、线性规划的应用" t& A) A5 j* Z: q
    在企业的各项管理活动中,例如计划、生产、运输、技术等问题,线性规划是指从各种限制条件的组合中,选择出最为合理的计算方法,建立线性规划模型从而求得最佳结果. 广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策,提供科学的依据。
    " i  L# k; \1 l! L# ]# N7 e(2)整数规划
    $ W$ O, C% {! f# D1 r% c一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性,二次和非线性的整数规划。   在线性规划问题中,有些最优解可能是分数或小数,但对于某些具体问题,常要求某些变量的解必须是整数。例如,当变量代表的是机器的台数,工作的人数或装货的车数等。为了满足整数的要求,初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解,所以应该有特殊的方法来求解整数规划。在整数规划中,如果所有变量都限制为整数,则称为纯整数规划;如果仅一部分变量限制为整数,则称为混合整数规划。整数规划的一种特殊情形是0-1规划,它的变数仅限于0或1。不同于线性规划问题,整数和0-1规划问题至今尚未找到一般的多项式解法。0 @/ d" k/ [! t' S; Q
    组合最优化通常都可表述为整数规划问题。两者都是在有限个可供选择的方案中,寻找满足一定约束的最好方案。有许多典型的问题反映整数规划的广泛背景。例如,背袋(或装载)问题、固定费用问题、和睦探险队问题(组合学的对集问题)、有效探险队问题(组合学的覆盖问题)、旅行推销员问题, 车辆路径问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用,而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。7 E; J" ]( a8 y5 H
    整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的 。解整数规划最典型的做法是逐步生成一个相关的问题,称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题(衍生问题称为松弛问题的源问题)。通过松弛问题的解来确定它的源问题的归宿,即源问题应被舍弃,还是再生成一个或多个它本身的衍生问题来替代它。随即再选择一个尚未被舍弃的或替代的原问题的衍生问题,重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法,它们都是在上述框架下形成的。% m* O% H! f) O# k4 v, f) X  P+ K
    0-1规划在整数规划中占有重要地位,一方面因为许多实际问题,例如指派问题、选地问题、送货问题都可归结为此类规划,另一方面任何有界变量的整数规划都与0-1规划等价,用0-1规划方法还可以把多种非线性规划问题表示成整数规划问题,所以不少人致力于这个方向的研究。求解0-1规划的常用方法是分枝定界法,对各种特殊问题还有一些特殊方法,例如求解指派问题用匈牙利方法就比较方便。: k4 N, t& ]% u2 l
    (4)二次规划5 H) {& s  ^" h+ W
    二次规划是非线形规划中一类特殊的数学规划问题,它的解是可以通过求解得到的。通常通过解其库恩—塔克条件(KT条件),获取一个KT条件的解称为KT对,其中与原问题的变量对应的部分称为KT点。8 K5 o- S9 }: k* n6 Z; d
    二次规划分为凸二次规划与非凸二次规划,前者的KT点便是其全局极小值点,而后者的KT点可能连局部极小值点都不是。若它的目标函数是二次函数,则约束条件是线性的。由于求解二次规划的方法很多,所以较为复杂;其较简便易行的是沃尔夫法,它是依据库恩-塔克条件,在线性规划单纯形法的基础上加以修正而成的。此外还有莱姆基法、毕尔法、凯勒法等。" V# o2 Q" J: Q( G: D

    1 P/ G5 {& W. ^9 I- U3 f
    9 n, _1 Q' O! m9 _
    3 a- k3 w/ j+ N) A* W0 ~# Y
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    3#
    无效楼层,该帖已经被删除
    2#
    无效楼层,该帖已经被删除
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2025-7-27 10:42 , Processed in 0.420664 second(s), 60 queries .

    回顶部