- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2018/11/17 14
3、模型：min z=cX s.t. AX b Aeq X beq VLB≤X≤VUB
命令：[1] x=linprog（c，A，b，Aeq,beq, VLB，VUB） [2] x=linprog（c，A，b，Aeq,beq, VLB，VUB, X0） 注意：[1] 若没有等式约束: Aeq X beq , 则令Aeq=[ ], beq=[ ]. [2]其中X0表示初始点 4、命令：[x,fval]=linprog(…) 返回最优解ｘ及ｘ处的目标函数值fval.
一、引言
我们从2005年“高教社杯”全国大学生数模
竞 赛的B题“DVD在线租赁”问题的第二问和第三问 谈起.
其中第二个问题是一个如何来分配有限资源， 从而达到人们期望目标的优化分配数学模型. 它 在数学建模中处于中心的地位. 这类问题一般可 以归结为 数学规划模型.
规划模型的应用极其广泛，其作用已为越来 越多的人所重视. 随着计算机的逐渐普及，它越
上述食谱问题就是一个典型的线性规划问题， 它是指在一组线性的等式或不等式的约束条件下，
寻求以线性函数的最大（小）值为目标的数学模
型.
线性规划的数学模型
• max z =
c1 x1 c2 x2 cn xn
S.T
a11 x1 a12 x 2 a1 j x j a1n x n b1 ai1 x1 ai 2 x 2 aij x j ain x n bi a m1 x1 a m 2 x 2 a mj x j a mn x n bm x1 , x 2 ,, x n 0
来越急速地渗透于工农业生产、商业活动、军事
行为核科学研究的各个方面，为社会节省的财富、 创造的价值无法估量. 在数模竞赛过程中，规划模型是最常见的一 类数学模型. 从92-08年全国大学生数模竞赛试题 的解题方法统计结果来看，规划模型共出现了16 次，占到了近50%，也就是说每两道竞赛题中就有
一道涉及到利用规划理论来分析、求解.
min
f=
c x
x≥0
T
s.t
Ax ≥b,
其中f被称作目标函数，目标函数下的等式或不等 式被称作约束条件， T 1 2 n
( x , x ,, x )
(c1 , c2 ,, cn )T
A=
a11 a 21 a m1
a12 a 22 am2
a1n a2n a mn
用MATLAB优化工具箱解线性规划
1、模型： min z=cX s.t. AX b 命令：x=linprog（c，A，b）
2、模型：min z=cX s.t. AX b Aபைடு நூலகம்q X beq
命令：x=linprog（c，A，b，Aeq,beq）
AX b 存在，则令A=[ ]，b=[ ]. 注意：若没有不等式：
MATLAB中有关求解线性规划问题的指令
• • • • • X=linprog(f,A,b,Aeq,beq) X=linprog(f,A,b,Aeq,beq,lb,ub) X=linprog(f,A,b,Aeq,beq,lb,ub,x0) X=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) [x,fval,exitflag,output]= linprog(…)
b1 b 2 ,b= b m
一组满足约束条件的变量 x1 , x2 ,, xn 可行解。
的值称为一组
可行解的集合称为可行解域，或可行解空间。
线性规划问题也就是在可行解域上寻找使目标函数取得 极小（或极大）值的可行解，称之为最优解。
2.2 线性规划模型的求解 针对标准形式的线性规划问题，其解的理论 分析已经很完备，在此基础上也提出了很好的算 法——单纯形方法及其相应的变化形式（两阶段 法，对偶单纯形法等）. 单纯形方法是线性规划问题的最为基础、也 是最核心的算法。它是一个迭代算法，先从一个 特殊的可行解（极点）出发，通过判别条件去判
线性规划、线性规划的可行解，最优解的概念 线性规划一般可写作 min(or max) f= 1 1 s.t.
c x c2 x2 cn xn
ai1 x1 ai 2 x2 ain xn bi ,
x j 0, j 1,2,, n
i 1,2,, m
线性规划问题还可以用矩阵表示
解 首先根据食物数量及价格可写出食谱费用为 c1 x1 c2 x2 cn xn ,
其次食谱中第 i 种营养素的含量为 ai1 x1 ai 2 x2 ain xn .
因此上述问题可表述为： min c1 x1 c2 x2 cn xn
a11 x1 a12 x2 a1n xn b1 a x a x a x b 21 1 22 2 2n n 2 s .t . a x a x a x b m2 2 mn n m m1 1 x1 0, x2 0, xn 0
二、线性规划模型
线性规划模型是所有规划模型中最基本、最 简单的一种. 2.1 线性规划模型的基本形式
例1.（食谱问题）设有 n 种食物，各含 m 种营养
素，第 j 种食物中第 i 种营养素的含量为 aij , n 种 食物价格分别为c1, c2, …, cn，请确定食谱中n 种食 物的数量x1, x2, …, xn，要求在食谱中 m 种营养素 的含量分别不低于b1, b2, …, bm 的情况下，使得总 总的费用最低.
断该可行解是否为最优解（或问题无界），若不
是最优解，则根据相应规则，迭代到下一个更好
的可行解（极点），直到最优解（或问题无界）.
关于线性规划问题解的理论和单纯形法具体的求
解过程可参见相关文献. 然而在实际应用中，特别是数学建模过程中，
遇到线性规划问题的求解，我们一般都是利用现 有的软件进行求解，此时通常并不要求线性规划 问题是标准形式. 比较常用的求解线性规划模型 的软件包有LINGO、LINDO和MATLAB。
