QQ登录

只需要一步,快速开始

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

数学建模算法与应用第二章:整数规划

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2020-3-13 17:02 |只看该作者 |正序浏览
    |招呼Ta 关注Ta
    数学建模算法与应用第二章:整数规划4 z$ n/ L% Q5 H& B: b% @4 k( a
    0 |7 r2 [  p9 W9 S
    2.1 基本概念
    3 y! L) s4 s7 @& n& d; u$ R
    4 O. F9 f6 c6 Z( u& d整数规划:数学规划中的变量(部分或全部)限制为整数
    $ k: x8 p# N/ B7 {目前只能求解整数线性规划
    $ s1 c, m* i' Y* e% l$ K整数规划的解有如下三种情况:" t/ G# g$ O6 q/ |
    # m5 o; w; y9 q, V7 A9 _9 l1 x& h
    没有可行解(最优解不是整数): m& n' e0 M7 W1 P  _! Q% T# i
    存在最优解(最优解为整数)
    ) g0 A0 q$ |6 ^5 x有可行解(最优解值变差)
    7 C( E% c0 h  F) R7 @2.2 0-1整数规划
    ) r  j- l; C+ S% H8 b4 i' N" S
    ( ^* Q" u; J% P3 c' E/ w定义:变量x仅取值0或1,即0-1变量
    2 I% q' K/ x5 z  m* E& Q/ ~" e4 p2 t0 A- Z% P
    2.2.1 相互排斥的约束条件
    & D) ~; \  v5 u+ J" O; ~& c/ P
    + z6 w: w& R  y0 k9 y  K) g$ C引进一个充分大的数,削弱取一种情况时另一种情况下的约束条件
    ' Z$ d1 F3 X/ b+ _改为普通的约束条件(不常用)
    , _+ c9 \" t- `; B: j若有m个互相排斥的约束条件3 b6 f4 [+ g6 Z- o
    1.png
    ' {+ N" f; C9 l9 i: X* k) R5 O- h1 w; e7 ~3 [" ?: z% H2 r
    需保证只有一个起作用,则引进m个0-1变量:* F+ u. n+ u& s% F( B. `0 ^# ~
    2.png . O  C, V3 I% N7 k; g0 `( b2 `

    7 p1 E( f. ~4 V; _, u- T# j, U和一个充分大的常数M,则有:4 E5 ^5 j( _, J" l2 n
    3.png ' ^3 k4 l& d$ w/ U& V4 v" L
    2.2.2 混合整数规划(固定费用)

    定义:变量部分限制为整数* r9 O) M; T: A
    可用约束条件:

    4 u3 _0 s+ l$ @* `& r! I
    4.png
    . q- s2 t# u$ U8 E0 Oy为引入的0-1变量,ε \varepsilonε为充分小的正常数,M为充分大的正常数% h$ [2 n; a- Z* A0 h! J; k2 }
    上式即代替了该分段函数:) ~8 T; s4 o) u9 ^' d

    ) |8 L& n2 J  ~0 A 5.png 7 m( f1 X/ `2 X9 f& r, T& m

    . s, y( Y9 q  X5 I6 ]7 K2.2.3 指派问题

    关键:给出系数矩阵C' Q1 G  @3 U! J( C% {7 B/ ]: I
    规划模型为:(x为引入的0-1变量)

    7 Z+ w2 x# C' X/ j
    6.png ' v& D& o4 b& ]4 x" e
    * C  y! A/ ~" D1 G/ k
    2.3 蒙特卡洛法(随机取样法)

    目的:求解非线性整数规划5 P+ H* P8 H+ U/ H" g
    matlab程序如下:" ~* w$ ^: {  G  _. w, y) R
      定义目标函数 f 和约束向量函数 g

    7.png ) p  N9 f" Q$ u' o- B! ]9 I

    3 j8 Z( c6 p( K1 _5 u2 L4 _求解问题
    ) u) M$ r* e/ x: Z# W8 f6 e 8.png
    9 ~& l& O) h. w9 O
    $ A( c( ?* y1 J6 L2.4 整数线性规划的计算机求解

    matlab求解混合整数线性规划,用intlinprog函数,但必须把所有的决策变量化成一维决策变量,即需要做变量替换。
    6 s7 r& j0 j/ o; E- C4 H  j  标准形式为:

    ' l7 h6 s4 L' S0 k7 i1 ^) K! K8 `
    9.png 1 Z* p5 D. S! k' H4 j# S
    10.png
    8 z3 \" s3 ^+ R; g( s
    - x- o$ @  m0 p, N
    ) z4 F2 d  R- g* N1 K6 a————————————————/ |8 X; W+ j9 D, b! R
      R1 d0 p  b, y6 q* R4 C1 U, d" s
    版权声明:本文为CSDN博主「victor_cs_bit」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
    " V7 G# J& [3 y0 S4 W  V$ }原文链接:https://blog.csdn.net/qq_41000485/article/details/96478231" Z. r* @8 b* r

    0 Y; P( `8 Z' N  Q
    # e" K- [4 W: W# {8 {& i  K————————————————
    8 s8 @( x, j  J6 K2 d7 r6 C9 l原文链接:https://blog.csdn.net/qq_41000485/article/details/96478231
    + Z+ Z4 O% u$ n# K  ~) ^0 _6 U  C& T# s2 d3 |) l$ ^" ~

    - y* f$ ~; h- n8 }1 B  w
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

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

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

    蒙公网安备 15010502000194号

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

    GMT+8, 2026-4-21 00:36 , Processed in 0.355764 second(s), 54 queries .

    回顶部