QQ登录

只需要一步,快速开始

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

[课件资源] 0-1规划

[复制链接]
字体大小: 正常 放大
137368108 实名认证    中国数模人才认证   

4

主题

4

听众

2306

积分

升级  10.2%

  • TA的每日心情
    开心
    2015-7-3 16:05
  • 签到天数: 689 天

    [LV.9]以坛为家II

    社区QQ达人

    群组: 2013年数学建模国赛备

    群组: 中南民族大学

    群组: 学术交流A

    群组: 数学建摸协会

    群组: 第三届数模基础实训

    跳转到指定楼层
    1#
    发表于 2011-8-20 15:54 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    0-1规划
    0 ?, p) z. f6 A# C: z0-1规划是决策变量仅取值0或1的一类特殊的整数规划。在处理经济管理中某些规划问题时,若决策变量采用 0-1变量即逻辑变量,可把本来需要分别各种情况加以讨论的问题统一在一个问题中讨论。" F/ J- z7 b* ]* C, `
      0-1规划 5 n% V# {6 s7 f( p- Z
    0-1 Programming2 g9 v6 H* v8 T' x  r
    一种特殊形式的整数规划 。这种规划的决策变量仅取值0或1,故称为0-1变量或二进制变量 ,因为一个非负整数都可以用二进制记数法用若干个0-1变量表示 。0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件 ,因此0-1规划非常适合描述和解决如线路设计 、工厂选址 、生产计划安排、旅行购物、背包问题、人员安排、代码选取、可靠性等人们所关心的多种问题。实际上,凡是有界变量的整数规划都可以转化为0-1规划来处理 。由于0-1规划具有深刻的背景和广泛的应用,几十年来一直受到人们的重视。! C% T( M  J: y
    求解0-1规划的方法主要是隐枚举法(如分枝定界法)。对一些特殊问题还有一些更加有效的方法,例如对指派问题,用D.柯尼希发明的匈牙利法求解更显方便有效。* N/ u9 O4 b* `7 Z* t: l
    应用范围
    ' A% z/ c& P$ C* d4 Z0 e0-1规划主要用于求解互斥的计划问题、约束条件互斥问题、固定费用问题和分派问题等方面。
    , R7 f5 @  T) ?& h) m+ J3 I1 x互斥计划问题
    6 m. E0 Y" _6 I. `. L. ]如确定投资项目,选定投资场所,决定投产产品等。设有几种产品,各产品投产后获得的利润为 ,投资限额为 ,规定决策变量 的取值为
    . u4 `* V+ ?7 c$ G% h" V % v3 Q6 R. m- d1 P  r
    则此0-1规划的数学模型为 ! z% A  ]2 P9 t1 }2 ?$ Q8 v8 ~6 w3 }* Z

    8 \. Z9 d  l- U% f式中 表示求极大值; 表示“受约束于”; 是目标函数; 是各种产品的投资额。 ( s. E7 E0 L* m( M" D4 W
    约束条件互斥问题
    : t  p$ P; A  V6 s/ S$ g% s设有 个互相排斥的约束条件(≤型)  (i=1,2,…,m)为了保证这m个约束条件中只有一个起作用,引入m个0-1变量yi和一个足够大的常数M,构造m+1个约束条件
    % ~5 R1 @$ t. f/ W. c5 q% Gai1x1+ai2x2+…+ainxn≤bi+yiM
    ' U1 @; w5 K) a( t* My1+y2+…+ym=m-18 `" J) y! n9 }9 o
    因为m个yi中只有一个能取0值,所以只有一个约束条件能起作用。! {, V4 K  Z2 Q1 ?  X+ p
    如运送两种货物,其数量分别为 x1和x2,车运时货物体积不得超过b1,船运时货物重量不得超过b2,即
    6 W6 u6 q; w2 V" \( L4 L+ J2 Ua11x1+a12x2≤b1 (车运),0 k- s& l* |! z" G; K
    a21x1+a22x2≤b2 (船运)。  S5 P7 J) a( g  x! n
    若只能采用一种运送方式,这两个约束条件是互相排斥的。为了统一在一个问题中,引用0-1变量yi,设) Q! d, Z5 i  U8 f2 W
       $ B  R+ E. U6 p$ ^" g  E
       ) t5 b, O: _9 e0 g1 N
    把上述约束条件改造成为下面一组约束条件: 6 W! H, \  `; F$ _. u! L/ F" _7 N
    a11x1+a12x2≤b1+y1M
    - B& {3 [2 _) I2 z% n8 v- V  s2 J) xa21x1+a22x2≤b2+y2M% O9 _* y' v+ |, P
    y1+y2=2-1
    5 y* W9 k( W6 a( e: `) q. f7 B式中M是足够大的数,采用车运时y1=0,由第1式即得到车运约束条件,采用船运时y2=0,由第2式即得到船运约束条件。因此上述互相排斥的约束条件被一组联立约束条件所代替。! {. ], ^4 V. w+ _0 F: Y
    固定费用问题3 |1 s5 F' d* A! r7 `, K! Y  D
    采用一般线性规划不能解决固定费用问题,需要用0-1规划。设有n种生产方式可供选择,xi为采用第i种方式时的产量,ci为采用第i种方式时每件产品的变动成本,ki为采用第 i种方式时的固定成本,采用各种生产方式的总成本分别为! X4 S/ [$ G3 S: r" s( n& F$ N3 a
       
    & f" T6 w6 n! D( b5 v  k, u(i=1,2,…,n) 7 K9 Q% V/ S" k; y7 a3 J
    在构成目标函数时,为了统一在一个问题中讨论,引入0-1变量yi,即
      S( X; ^$ Y- i1 p- \2 x9 s5 k+ y- c4 S5 e则此0-1规划的数学模型为
      k; G8 m9 x$ Z% H   0 ~* h& F7 `- [) L7 ?" Y) Y
       # R) |1 P% C3 I: C! s, x8 r+ o. a
    式中min表示求极小值,M是充分大的常数。
    5 f  @8 ]3 v- w& G7 D4 f' p; m9 L; U分派问题3 I, X" p, C: t' |
    由几个人去完成几项任务,但由于任务性质和各人专长不同,应分派哪个人去完成哪项任务,以使总效率最高或耗费的总时间最小,这类问题称为分派问题,又称指派问题。
    % {, j; n3 i& P, A+ F7 Y9 H" Z分派问题必须给出系数矩阵(又称效率矩阵),矩阵的元素 cij(>0)(i,j=1,2,…,n)表示派第i人去完成第j项任务时的效率(或时间、成本等)。引用0-1变量xij,设
    * I6 z& C' ?2 t) O9 k   
    9 l4 P& {9 s4 f# M分派问题的数学模型为
    " q* m" A# o2 U. l! w* {# |: e   
    " q6 }, Y+ y# D2 Q3 X& y; K   
    7 ~  K2 v& \: O8 E( K; H第1个约束条件说明第j项任务只能由1人去完成,第2个约束条件说明第i人只能完成1项任务。分派问题的解可写成矩阵形式(xij),其各行各列的元素之和都是1。
    ) H; Q. b; j3 |3 ~隐枚举法& i) a9 E- B3 {8 b6 u& K" ?
    0-1规划问题一般有三种解法,即变换法、穷举法和隐枚举法。上述方法即为变换法,用于解特殊的0-1规划问题。穷举法就是检查变量取值为0或 1的每一种组合,比较目标函数值来求最优解,这就需要检查变量取值的2n个组合。对于n>10的情况,这几乎是办不到的。因此常设计一些方法,只检查变量取值组合的一部分,就能得到问题的最优解。这样的方法称为隐枚举法。
    1 j* Q0 X$ Z& l采用隐枚举法解 0-1规划问题时要根据目标函数的性质增加一个相应的不等式作为附加约束条件,称为过滤条件,以减少运算次数。一般还要按目标函数中xi的系数递增的顺序,重新排列目标函数和约束条件中xi的次序,以简化计算。
    " o7 R& h. B. ]* }$ x
    ' ~2 f; Y: ^7 W) t- B3 r
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持1 反对反对0 微信微信

    24

    主题

    9

    听众

    4478

    积分

  • TA的每日心情
    衰
    2012-9-19 16:55
  • 签到天数: 27 天

    [LV.4]偶尔看看III

    邮箱绑定达人 新人进步奖 最具活力勋章 发帖功臣

    群组: Matlab讨论组

    群组: 全国大学生数学建模竞

    群组: 数学建摸协会

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    fastpost qq
    收缩
    • 电话咨询

    • 04714969085

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

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

    蒙公网安备 15010502000194号

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

    GMT+8, 2026-11-23 05:23 , Processed in 0.351258 second(s), 59 queries .

    回顶部