QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 4965|回复: 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)是数学规划的一个分支。


    1 a! G) U+ z" R+ o5 K! c& O& u" x
    ; A6 H6 r, w" u) Ox1,x2为决策变量,约束条件记为s.t.(subject to)。
    3 q: h1 V# J+ ]4 j5 T6 A8 o* K' R

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

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

    7 B# @/ e. y: @& e
    7 O" \; f6 E* q/ P1 B1 y6 ?/ t7 M
    其中c和x均为n维列向量,A、Aeq为适当维数(列数与x维数相同,行数与约束条件数相同),b、beq为适当维数的列向量(维数与约束条件数相同)。7 O. W/ H8 F* v* N/ u8 b

    " r/ ~; ~0 |; b例如:
    2 u$ [; m& k' U2 p, Y' ]/ }0 V1 Imax  cTx  s.t.   Ax≥b max  cTx  s.t.   Ax≥b
    % y% T' w3 R5 q9 Pmatlab中为:
    ; u1 @0 ^  U: dmin  −cTx  s.t.   −Ax≤b min  −cTx  s.t.   −Ax≤b
    5 T8 J1 \' `5 z* O- a3.线性规划中解的概念& |2 M$ T: [7 S# E& S

    , H  L; _# E& W可行解:满足约束条件的 解x = (x1,x2…xn),称为线性规划问题的可行解,从而使目标函数达到最大值或者最小值的可行解称为最优解。
    : n$ K( J3 a% b' t$ p7 N可行域:所有可行解构成的集合称为问题的可行域,记为R。
    + |$ z3 e. q  K8 G$ n
    3 [- o3 ]0 Y5 s( B! a/ I4.一般的线性规划问题
    5 y8 r0 R5 a8 V% f4 L! S. ~: ]& B/ h+ _
    在一般的n维空间中,满足 ∑ni=1aixi = b∑i=1naixi = b 的点集称为一个超平面,而满足 ∑ni=1aixi ≥ b∑i=1naixi ≥ b (或者∑ni=1aixi ≤ b∑i=1naixi ≤ b )的点集称为一个半平面,若干个半平面的交集称为多胞形,有界的多胞形称为多面体。因此线性规划的可行域必定为多胞形(空集也视为多胞形)。若该区域R为凸集,则凸集中的任意两点的连线必然在该凸集中,若x为区域R的极点,则x不能位于R中的任意两点的连线上。
    ! X( G+ O2 `" n/ W0 s$ X. ~2 F" q6 O  K: c3 u
    5.matlab中线性规划求解过程" A7 e$ a3 }1 b4 q! E2 N
    3 T3 ^$ `5 @  m9 S, t
    ① 利用linprog函数返回最小值解向量。
    4 f5 l9 t6 C$ e- h② value = c’ * x求最小值。
    " j& g9 n$ m2 ]. M' a
    - B0 D' Q- a: m4 Z8 Q/ G基本函数形式是 linprog(c,A,b) , c用于确定等值线(列向量),返回值为向量x。 2 e8 B! s$ `3 n" [9 A7 y4 O  @
    其他的函数形式:
    - z! g7 d' ?$ @' {- ]/ q$ W[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,x0,OPTIONS) - i* U/ B( A& U7 ~8 L/ p# o
    x0为向量x的初始值,一般使用zeros()函数 初始化,LB和UB分别是向量x的下界向量和上界向量。返回值为fval(目标函数c’ * x的值)。
    5 p9 @* `% f4 m/ l4 ~# U$ [, e; B0 Z! Y- g# [# \9 u
    6.常见技巧/ X% e8 d' W, I$ u( R

    : W, r. v4 {  j" }问题为:
    $ |, P, q7 h1 d+ d, ~5 I
    2 L0 y3 Y2 k+ ~5 J+ m# r7 {, n) Jmin|x1|+|x2|+…+|xn|  s.t.  Ax≤b min|x1|+|x2|+…+|xn|  s.t.  Ax≤b  
    ' g5 ^7 i& o. Y+ y事实上,对于任意的xixi,存在ui,viui,vi满足: * \: [! V: U5 o/ N% s, r. X# u: _
    xi=ui−vi  ,  |xi|=ui+vixi=ui−vi  ,  |xi|=ui+vi
    7 U. b( v$ [2 j/ t- s8 ?令 ui=(xi+|xi|2),vi=(|xi|−xi2)ui=(xi+|xi|2),vi=(|xi|−xi2)即可满足。* x7 e! {* L6 K5 E( n$ T( N1 [5 u3 U2 @
    4 S, v. z9 F" _9 e
    转换为:
    * g0 C+ H: R  x6 T+ t! gmin  ∑ni=1(ui+vi)min  ∑i=1n(ui+vi)
    $ l; ^1 X4 l: ]s.t.{A(ui−vi)≤b,u,v≥0,s.t.{A(ui−vi)≤b,u,v≥0," A) z7 a% R  V; h6 g# g
    7.运输问题(产销平衡)
    0 v) N6 N0 ^& j6 y6 q/ x8 z: M( q* ?5 m9 V

    5 n$ E! A8 @* u

    8.指派问题

    1.数学模型
    ) v1 M3 J' d' _/ K" ~6 `

    ! m+ k1 L- p& Y9 }7 z

    $ _" T! r( m2 t# M' T% v2.利用匈牙利算法 * D# k" I& ^1 P- V
    算法主要思想:如果系数矩阵中C=(cijcij)一行(或一列)中每一个元素都加上或减去同一个数,得到新矩阵B,则以B或C为系数矩阵的指派问题具有相同的最优指派。
    7 |& e4 G3 h: B- R6 n5 O最优指派的结果是一个2行n列的行列式,第一行为第i人,第二行为被指派的地点。 2 x, `: F+ P0 _, w( b% ~$ Z( Q
    求解中心:变换出n个不同行不同列的零元素。
    8 @! f, F6 X; Q; M1 Y( m4 G
    8 @1 g( \6 s3 `0 T) A; o) S3 @0 _( F" m) N% z, ^

    ; u* x& k5 _: J$ i4 W! a
    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 03:29 , Processed in 0.376748 second(s), 50 queries .

    回顶部