QQ登录

只需要一步,快速开始

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

【数学建模】线性规划

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

100

主题

17

听众

7546

积分

升级  50.92%

  • TA的每日心情
    开心
    2018-6-4 15:01
  • 签到天数: 7 天

    [LV.3]偶尔看看II

    群组2018年大象老师国赛优

    群组高考备战

    群组2018中小学数学建模冬

    跳转到指定楼层
    1#
    发表于 2018-10-30 10:06 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta

    1.线性规划简介

    线性规划(LP)是数学规划的一个分支。


    # P  \. v" z& q1 i. Y! M" g9 V
    x1,x2为决策变量,约束条件记为s.t.(subject to)。
    7 N" k0 W1 G( {% g) \6 ]

    2.线性规划的matlab标准形式

    线性规划的目标函数可以求最大值也可以求最小值,约束条件的不等号可以是小于号也可以是大于号,因此在matlab中给出了统一形式

    . X( z6 h0 H5 a+ O8 V. f
    4 c+ Q# |/ E. q  r- c% L# q
    其中c和x均为n维列向量,A、Aeq为适当维数(列数与x维数相同,行数与约束条件数相同),b、beq为适当维数的列向量(维数与约束条件数相同)。
    1 W$ V( z$ s# e" ?9 |) P( |
    - @# q" ~/ y/ x( a! [$ r. `( O1 d例如:
    1 x2 N# i+ @1 V! u7 Bmax  cTx  s.t.   Ax≥b max  cTx  s.t.   Ax≥b & |8 y4 I7 L" t6 Z! b
    matlab中为:
    , c1 D7 Q8 C- D% Z' `min  −cTx  s.t.   −Ax≤b min  −cTx  s.t.   −Ax≤b
    0 m* R, h' O1 s* l$ Z3.线性规划中解的概念
    ; u2 d5 e8 [: ]9 f7 C" S5 j
    9 d, M; c) U+ W/ A5 S8 ^可行解:满足约束条件的 解x = (x1,x2…xn),称为线性规划问题的可行解,从而使目标函数达到最大值或者最小值的可行解称为最优解。
    # |6 l/ {: J  l# z( F9 g可行域:所有可行解构成的集合称为问题的可行域,记为R。7 b1 A! c( P4 X2 c& J2 B
    % B* u* _1 n- z7 R8 ~1 s
    4.一般的线性规划问题! [1 j7 W5 S3 \5 R1 [5 ^- z5 c

    & P1 f2 X2 w5 ?7 W; l在一般的n维空间中,满足 ∑ni=1aixi = b∑i=1naixi = b 的点集称为一个超平面,而满足 ∑ni=1aixi ≥ b∑i=1naixi ≥ b (或者∑ni=1aixi ≤ b∑i=1naixi ≤ b )的点集称为一个半平面,若干个半平面的交集称为多胞形,有界的多胞形称为多面体。因此线性规划的可行域必定为多胞形(空集也视为多胞形)。若该区域R为凸集,则凸集中的任意两点的连线必然在该凸集中,若x为区域R的极点,则x不能位于R中的任意两点的连线上。
    / l8 C* ?& ]9 G' h' m3 p! C* K9 b. ^
    5.matlab中线性规划求解过程
    5 H8 y# o& Q% P& q2 }7 K2 O5 Z9 ?$ C, b3 i% f* c
    ① 利用linprog函数返回最小值解向量。
    * w, Z5 S6 _5 }! a4 i5 Q② value = c’ * x求最小值。$ _5 ?; b; }& L9 q& ~& ?* f$ M
    / l" ~3 K- {) D6 \& O5 c$ Y2 _  ~
    基本函数形式是 linprog(c,A,b) , c用于确定等值线(列向量),返回值为向量x。 ) ^: g' g* z8 D
    其他的函数形式:
    ) s5 G% w4 i  G6 O! E  w* o) n[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,x0,OPTIONS)
    + r8 j' d: E( u/ N( lx0为向量x的初始值,一般使用zeros()函数 初始化,LB和UB分别是向量x的下界向量和上界向量。返回值为fval(目标函数c’ * x的值)。
    7 \3 ?2 x& I0 y  a  {) v
    1 G. P) G7 \& R4 B3 r6.常见技巧2 I- N' h( I( L6 n" ~4 z, V

    * d  S! c, Z/ j  u0 F: V8 t* L0 @问题为:
    . r4 {  x% t% J( d- A1 y
    3 ?8 X$ y& j5 N+ u' fmin|x1|+|x2|+…+|xn|  s.t.  Ax≤b min|x1|+|x2|+…+|xn|  s.t.  Ax≤b  ( y0 U4 }8 @! M) r
    事实上,对于任意的xixi,存在ui,viui,vi满足:
    / b, _3 Y, m# _xi=ui−vi  ,  |xi|=ui+vixi=ui−vi  ,  |xi|=ui+vi
    4 G" m0 [. x/ q6 ^. T5 b令 ui=(xi+|xi|2),vi=(|xi|−xi2)ui=(xi+|xi|2),vi=(|xi|−xi2)即可满足。
    1 w  B+ U( ?3 H5 V& p6 V+ F% }0 p3 l' W+ [* Z+ w
    转换为:
    * I/ d  T" n- U+ M8 u$ v7 @min  ∑ni=1(ui+vi)min  ∑i=1n(ui+vi)
    ( K: l2 r8 \# k& f% Ps.t.{A(ui−vi)≤b,u,v≥0,s.t.{A(ui−vi)≤b,u,v≥0,* {6 W! B* k3 |' R: h, z
    7.运输问题(产销平衡). F/ n+ g" T" {; H9 w4 V) q0 W
    0 b- N6 v7 ]. |/ X) f' U8 g

    ; E( |; f2 c0 [

    8.指派问题

    1.数学模型 ) W1 D1 T1 w5 @+ a4 S. q; x5 f

    ) _: Z5 E* n9 v# A. o9 [: W
    # [, p. l) j. a" r2 m
    2.利用匈牙利算法
    ; H" P; a7 H* G3 h算法主要思想:如果系数矩阵中C=(cijcij)一行(或一列)中每一个元素都加上或减去同一个数,得到新矩阵B,则以B或C为系数矩阵的指派问题具有相同的最优指派。 ; d3 h& O. P7 s0 R; e* {8 I9 P
    最优指派的结果是一个2行n列的行列式,第一行为第i人,第二行为被指派的地点。
    , i9 Y  i+ G0 |$ B求解中心:变换出n个不同行不同列的零元素。& A- U- I  A& ~; V6 u; {
    5 N6 ]( X  F. S! L0 F

    # F7 a1 d9 v+ o+ V) A. X# m) G" A+ F* \  N' f. G
    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-6-14 07:08 , Processed in 0.553758 second(s), 49 queries .

    回顶部