--
§2.7 非线性规划模型
在现实问题中，大量的问题是非线性的。因此，除线性规划外，应用更多的是非线性规划。本节简单介绍非线性规划的有关概念。
一. 引例
例1． 如图2-68，预建一猪舍，
围墙与隔墙的总长不能超过40米，问长、宽各多少时，面积最大？
设长、宽分别是1x 米、2x 米时，问题即为下述优化问题：求
???≥≤+0,4052max 2
1212
1x x x x st
x x 易知，本问题的最优解是.4,1021
==x x
例2．
某企业生产一种产品，其生产要素（可以是某种原材料，也可以是劳
力、资本等）编号为n ,,2,1 . 已知该产品的生产函数为),,,(21n x x x g (第i 种生产要素的投入量为i x 时的产品产出量)一般为非线性函数,设给定产品的总产量为a ,第
i 种生产要素的单位生产费用为i c ,问如何安排生产成本最低?
数学模型为:
???≥=∑0),,,(min 21i
n i
i x a x x x g st
x c 例3．
最优国民经济计划模型
国民经济由n 个部门所组成, 编号为n ,,2,1 ,各部门间直接消耗的系数矩阵为
()n j i ij
a A 1,==,ij a 为第i 个部门生产价值一个单位的产品直接消耗j 部门产品的价值
11
x
2x ??
?
????图2-68
--
单位,
j 部门的生产函数),(i i i i K L f x =其中i x 为第i 部门总产品的价值.i K 为投入
i 部门的资金数i L 为投入i 部门的劳力数.问在总劳动力L ,资金K 给定的前提下,如何
安排各部门的资金数及劳力投入,可使国民收入最大?
设i y 表示第i 部门最终产品的总价值,则数学模型为
????
???≥=≤≤+=∑∑∑∑0,,,),(max
i
i i i i i i i i i i j ij i i
K L y x L K f x K
K L L y x a x st
y 例4． 确定经验公式－非线性回归分析
设(i t , i y ) (n i ,,2,1 =)为实际问题中的一组数据,且i y 与i t 有关系
ct be a y -+=,现求系数c b a ,,使得ct be a y -+=与数据组“最接近”。化为数学问题,
即求
,,)(min
2
1
>+--=∑c b a be a y i
ct
k
i i
一般地，称
min ),,(1n x x f
s.t. m i x x g n i ， ,1,0),,(1=≥ l j x x h n j ,,1,0),,(1 ==
为规划问题(或称为条件极值问题)。
特别1. 当j i h g ,为线性函数，f 为二次函数，称上述问题为二次规划；
2. 当f h g j i ,,均为线性函数，称上述问题为线性规划。
--
0,0=≥j i h g 称为约束条件，f 称为目标函数。
二. 二变量非线性规划问题的图解法 考虑规划问题
min ),(21x x f s.t. 0),(21≥x x g i
0),(21=x x h j
可以用图解法求出. 先给出若干概念.
1. 约束集合
首先我们知道,在平面上,一个不等式可确定一个区域。如：02<-y x ，表示2x y =上方部分；12
2≤+y x ，表示12
2=+y x 内部部分等.
一个等式可确定一条曲线。
将所有不等式、等式确定的区域的公共部分称为约束集合。
2. 等高线
对于目标函数),(21x x f ，),(21x x f =z 取定值时，确定平面上一条曲线，而),(21x x f z =，z 取不同值为平面上一条曲线。对应于该曲线上的点，其函数值相同，称这些曲线为等高线。
例5. 2
22
121),(x x x x f z +==的等高线为一族以原点为圆心的同心圆，c z =时，这些同心圆半径为c 。随着圆的半径增大，圆上的函数值增大（如图2-69）。
图2-69
图2-70
--
例6. 2
2
21211
),(x x x x f z +=
=的等高线也为一族以原点为圆心的同心圆，半径为
c
1
。随着圆的半径扩大，圆上的函数值变小。（见图2-70）。
3. 几何意义及图解法 例7. 非线性规划问题
min 2
22
1)2()2(+++x x
122
21
≤+
x x st
0≥i x
的可行域（约束集合）如图2-71阴影部分，最优解为（0，0）.
解“猪舍问题”（例1）
4052..max 212
1≥≤+i x x x t s x x
可行域即图2-72阴影部分，做出等高线c x x =21，取30,40,50,60=c ，易知最优解为4021=x x 与
405221=+x x 的交点).4,10(
三. 函数的梯度及最速下降法
约束问题转化为无约束问题(如Lagrange 乘数法)后可用最速下降法求解。
1. 求解无约束极值－多元函数极值
min ),,()(1n x x f x f =
图2-72
图2-71
--
经典数学方法：令n i f i x ,,2,1,0' == ，解得驻点，是否极值点？看矩阵)(''j i x x f 的正定性即可，从
0))()
((),,(0
10110
01x n
n n n f x x x x x x x x f f ??-++??-+= )())()
((2
20
10110∑?+??-++??-+i x n
n n x o f x x x x x x
)
(
))()(,,(),,(2
00110
0011001∑?+?????
??--''--+=?i n n
n n x x n n n x o x x x x x f x x x x x x f j i
当矩阵n n x x x f j i ?))((0
'
'正定时，)(x f 在0x 取极小； 当矩阵n n x x x
f j i ?))((0
''负定时，)(x f 在0x 取极大。
这种做法的困难是○
1要解方程组；○2判定正定性。 2. 规划方法
首先回顾梯度的性质：
○1)(x f 在给定点0x 的负梯度即))(,,,()(0
021x f f f x f n
x x x x '''-=- 是函数)(x f 在0
x 点下降最快的方向；
○
22=n 时，梯度方向为曲线),
(),(020
121x x f
x x f =在?
??
? ??020
1x x 的法向。 最速下降法：
我们假设稳定点又是最优点。给定初始点T n x x x ),,(0010 =，若0)(0
=x f x ，则
0x 即为最优点；
否则，0)(01≠x f x ，则按梯度意义，)(0
x f x -为f 下降最快的方向，沿
--
)(00x f z x -=方向，求0λ，使)()(min 0
00000
z x f z x f λλλ+=+≥（其中)(00z x f λ+是
λ的一元函数）
。 令0001z x x λ+=，则)()(0
1x f x f <
（)()(,000000z x f z x f λλλ+≤+≥? ，特别取0=λ，有)()(0
1x f x f <）
从1
x 依次迭代即可得到最优解。
步骤：
1. 取初始点0,0
>εx ； 2. 若ε≤+++=
-222)()()()(21k x k x k x k x x f x f x f x f n ，止；
3. 计算ε>-)(k x x f ，求极值)()(min k
k k k k z x f z x f λλ+=+；
4. 令k k k k z x x
λ+=+1
，1:+=k k ，转2。
例9. 求无约束问题
2221)1(4)1(min -+-x x 。
解：1. 取4)(10)
0,1(020
===-x f x T
ε；
2. )8,0()1(8),1(2021'
=--=-x x x x f ； 3. ε>=8'
x f ；
4. 8/1,)18(4))8,1((m in ))8.0((m in 2
=-==+λλλλf x f ；
5.
ε<=-=+=0)(,)1,1()8,0(81
1'01x f x x x T T 。
故
T x f )1,1(,0*min ==。
四. 罚函数法
考虑非线性规划问题
--
)(min x f
st ???=≥0)(0)(x h x g j
i
引入函数
{}???<≥=-==0
,
0,
0)2(
),0(min )(22
2t t t t t t t ?
{}t t t t ,0min 20
,
20,0=??
?<≥='?
用)(t ?构造函数
{}
∑∑∑∑++=?
?
????++===2
2112
))(())](,0([min )())(())(()(),(x h x g M x f x h x g M x f M x T j i m i l j j i ? 其中M 是一个很大的数。 由
?的定义，及约束条件的集合为{}
0)(,0)(=≥=x h x g x R j i ，故
??
??>∈=R
x x f R x x f M x T ),
(),
(),(，
由于R x ?时，
0))(())](,0[min(2
2>+=?∑∑x h x g j i
及M 为很大的正数，故?M 也是一个很大的正数。于是，当R x ?时，
?+=M x f M x T )(),(也是很大的数。
我们称函数),(M x T 为罚函数，?称为罚款项，M 称为罚因子。
对于固定的M ，),(M x T 为x 的函数。下面求无条件约束问题的最优解。（可用最
图2-73
--
速下降法）
设其最优解为x ?。由于),(M x T 为很大的数，故无约束问题),(min M x T 的最优解x
?应满足条件R x ??。 可以证明：
),(min M x T 的最优解x
?为规划问题 ??
?=≥0
)(0)()(min x h x g st x f j i
的最优解。
这里M 取多大合适，我们事先不知道。但从上述结论，若对1M M =，
),(m in 1M x T 的最优解R x ∈'，则x '为原规划问题的最优解。
否则，R x ?'，则说明1M 不够大。从而取1210M M M ==，再求解
),(m in 2M x T 。
依次下去，若求得),(min k M x T 的最优解R x k ∈，则k
x 为原问题的最优解。
或k x 与R 足够接近，如：εε≤-≥)(,)(k j k
i x h x g ，迭代停止。否则， 令k k M M M 101==+，继续上述步骤。 这个方法称为罚函数方法。 罚函数方法的实际意义：
考虑我们购买n ,,2,1 中货物，对每种货物的采购量分别为n x x ,,1 ，则我
们把目标函数
),,()(1n x x f x f =
看成采购量分别为n x x ,,1 时，所需总钱数。
约束集合，理解为某种“规定”。因此，非线性规划问题
--
??
?=≥0
)(0)()(min x h x g st x f j i 的经济意义为：在“规定”的范围内购物，使花钱最少。
对于罚函数，),(k M x T 的意义是：
相对“规定”制定一种“罚款”政策。若符合规定（即R x ∈），则罚款为0。若违反规定，则需交纳一笔正罚款（即罚款项）
2
1
2
1
))(())]
(,0([min ∑∑==+l
j j k m
i i
k k
x h M x g M
于是，罚函数),(k M x T 即为采购的总代价。
不难理解，当k M 很大时，相当于对违反“规定”的采购规定了苛刻的罚款，这当然不合算。于是迫使我们在考虑总代价为最小时，要符合规定。
在数学上表现为：当k M 很大时，无约束极值问题的最优解k
x 应满足约束条件，即R x k
∈。
例10. 利用罚函数法求解
{}
0min ≥x st x
解： ))),0(((min ),(2
x M x M x T +=
2)2
(
x x M x ++=
???
≤+≥=0
,
210,1),(2
x x M x M x T k k x
若x 为极值，则0),(=k x M x T 。故无约束问题的最优解满足021=+x M k ，即
--
k
M x 21
=
。 当∞→k 时，得021
lim
==k
M x 。 例11. 解非线性规划问题
{}
01min 3212
3
2221=-++++x x x st x x x
解： 23212
32
22
1)1(),(-+++++=x x x M x x x M x T k
0)1(22)1(22)1(22),(321332123211=?
??
?
? ??-+++-+++-+++=x x x M x x x x M x x x x M x M x T k k k k x
得
???
??=-+++=-+++=-+++0
)1(220)1(220
)1(223213
32123211x x x M x x x x M x x x x M x k k k 解得
03)(3)(321321=-+++++k k M x x x M x x x
得
k
k
M M x x x 313321+=
++
∴k
k
k k k M M M M M x x x 31))1313(
(321+=-+-===
∞→k M ，有3/1321===x x x 。
整数规划的数学模型及解的特点 整数规划IP (integer programming)：在许多规划问题中，如果要求一部分或全部决策变量必须取整数。例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP 。 松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。 若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。 一、整数线性规划数学模型的一般形式 ∑==n j j j x c Z 1 min)max(或 中部分或全部取整数n j n j i j ij x x x m j n i x b x a t s ,...,,...2,1,...,2,10 ),(.211 ==≥=≥≤∑= 整数线性规划问题可以分为以下几种类型 1、纯整数线性规划(pure integer linear programming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。
2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。 3、0—1型整数线性规划(zero —one integer liner programming)：指决策变量只能取值0或1的整数线性规划。 1 解整数规划问题 0—1型整数规划 0—1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的 ???? ? ????≥≤+≥+≤-+=且为整数0,5210453233max 2121212121x x x x x x x x x x z
控制系统仿真课程设计 题目：基于NCD优化的非线性优化 PID控制 学生姓名： 学号： 专业： 班级： 指导教师：
目录 基于NCD优化的非线性优化PID控制 (4) 摘要 (4) 第一章绪论 (6) 1.1 课程设计的目的 (6) 1.2 课程设计的题目要求 (6) 第二章MA TLAB概述 (7) 2.1 MA TLAB简介 (7) 2.2 MA TLAB工作环境 (7) 2.3 MA TLAB操作界面简介 (8) 2.4 MA TLAB 语言 (8) 2.5 SIMULINK仿真集成环境简介 (8) 2.5.1 SIMILINK模块库介绍 (9) 第三章非线性控制系统及优化原理 (13) 第四章非线性控制系统的优化 (14) 4.1 非线性控制系统的设计 (14) 4.1.1 MATLAB/SIMULINK模型的建立 (14) 4.1.2 系统参数设定 (14) 4.2 非线性系统参数优化 (16) 4.2.1 Signal Constraint阶跃响应特性参数设定 (16) 4.2.2 设置优化参数 (17) 4.2.3 设置不确定参数范围 (18) 4.2.4 控制参数优化计算 (18)
第五章课程设计总结 (20)
基于NCD优化的非线性优化PID控制 摘要 PID控制是工业过程控制中应用最广的策略之一。因此PID控制器参数的优化设计成为人们关注的问题,它直接影响控制效果的好坏。目前PID参数的优化方法很多,如间接寻优法、专家整定法、单纯形法等。虽然,这些方法都具有良好的寻优特性,但却存在着一些弊端。（1）中仅仅将单纯形法应用于系统,仍然存在局部最小问题,容易陷入局部最优化解,造成寻优失败。（2）而且当系统的非线性较强时,传统的基于线性化模型的线性系统设计方法难以获得好的控制效果。为了设计与分析非线性控制系统，提出了利用MATLAB优化控制工具箱与优化函数相结合对非线性系统PID控制器进行优化设计的方法,同时建立了基于MA TLAB/SIMULINK的非线性系统仿真图。通过MATLAB/SIMULINK非线性模块Signal Constraint进行仿真试验,验证了该参数优化设计方法不仅方便快捷,而且使系统具有较好的控制精度和稳定性,可使系统的性能有所提高。关键词：非线性控制系统MATLAB/SIMULINK Signal Constraint模块PID 非线性模块
基于M/M/S排队论的病床安排模型 （获２００９年大学生数学建模赛全国二等奖） 数学与计算科学学院雷蕾 信息科学与计算学院黄缨宁 信息科学与计算学院丁炜杰 指导老师：王其如教授 摘要 就医排队是一种我们非常熟悉的现象。在眼科医院的病床安排中，主要从医院高效工作和患者满意度两方面来考虑安排方法。本文通过确定两方面的权重，确立评价标准。 针对问题二，本文确定了从医院和患者两方面综合考虑的目标函数，医院各种诊疗规则的限制下进行线性规划，使得目标函数值（背离度）最小，得到问题二的解决方案。用问题一的标准评价，确实优于医院的FCFS模型。 问题三中对每一类病人术后恢复时间做统计，由计算机按照概率给出术后恢复的时间，运用第二问模型的选择方式，对近一段时间内的出入院人数作出合理预测，并根据M的排序确定患者入院的时间区间。 对于问题四，先确立白内障双眼手术的方案（调查支持可以任意不同两天手术），按照问题二的算法，先算出周二四做白内障手术的最小M值及入院前等待时间和术前等待时间。用计算机模拟出在手术时间可调整情况下M可能的最小值，得到周三五为最佳手术时间。尤其术前人均等待时间的优化减少使医院病床的有效使用率增加。模型改进率达到18.11%。 问题五要求确定病床固定分配使人均等待时间最短。病床的分配使整个排队系统变成了五个M/M/N模型，N为各类病床的数量。根据排队论中M/M/1模型的条件演化得到服务强度小于1及病床数固定不变。采取整数规划，在此限制条件下使得平均等待时间最小。从而算出各类病床的分配比例。 关键词：M/M/S模型泊松（Poisson）分布非线性规划优化模型病人满意度病床有效利用率
整数规划模型
实际问题中 x x x x f z Max Min T n "),(),()(1==或的优化模型 m i x g t s i ",2,1,0)(..=≤x ~决策变量f (x )~目标函数g i (x )≤0~约束条件 多元函数决策变量个数n 和数 线性规划条件极值约束条件个数m 较大最优解在可行域学 规 非线性规划解 的边界上取得划 整数规划
Programming +Integer 所有变量都取整数，称为纯整数规划；有一部分取整数，称为混合整数规划；限制取0，1称为0‐1型整数规划。 型整数规划
+整数线性规划 max(min) n z c x =1j j j n =∑1 s.t. (,) 1,2,,ij j i j a x b i m =≤=≥=∑"12 ,,,0 () n x x x ≥"且为整数 或部分为整数
+例：假设有m 种不同的物品要装入航天飞机，它们的重量和体积分别为价值为w j 和v j ，价值为c j ，航天飞机的载重量和体积限制分别为W 和V ，如何装载使价值最大化？ m 1?1 max j j j c y =∑ 1 0j j y =?被装载 s.t. m j j v y V ≤∑0 j ?没被装载1 j m =1 j j j w y W =≤∑ 0 or 1 1,2,,j y j m =="
(Chicago)大学的Linus Schrage教授于1980年美国芝加哥(Chi)Li S h 前后开发, 后来成立LINDO系统公司（LINDO Systems Inc.），网址：https://www.doczj.com/doc/9d15825569.html, I）网址htt//li d LINDO: Interactive and Discrete Optimizer (V6.1) Linear(V61) LINGO: Linear Interactive General Optimizer (V8.0) LINDO——解决线性规划LP—Linear Programming，整数规划IP—Integer Programming问题。 LINGO——解决线性规划LP—Linear Programming，非线性规划NLP—Nonlinear Programming，整数规划IP—Integer Programming g g整划g g g 问题。
1 整数规划的MATLAB 求解方法 （一） 用MATLAB 求解一般混合整数规划问题 由于MATLAB 优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif 和Tawfik 在MATLAB Central 上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog ，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。intprog 函数的调用格式如下： [x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 该函数解决的整数规划问题为： ????? ??????∈=≥≤≤=≤=） 取整数（M j x n i x ub x lb b x A b Ax t s x c f j i eq eq T ),,2,1(0..min 在上述标准问题中，假设x 为n 维设计变量，且问题具有不等式约束1m 个，等式约束2m 个，那么：c 、x 均为n 维列向量，b 为1m 维列向量，eq b 为2m 维列向量，A 为n m ?1维矩阵，eq A 为n m ?2维矩阵。 在该函数中，输入参数有c,A,b,A eq ,b eq ,lb,ub,M 和TolXInteger 。其中c 为目标函数所对应设计变量的系数，A 为不等式约束条件方程组构成的系数矩阵，b 为不等式约束条件方程组右边的值构成的向量。Aeq 为等式约束方程组构成的系数矩阵，b eq 为等式约束条件方程组右边的值构成的向量。lb 和ub 为设计变量对应的上界和下界。M 为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为621,,,x x x ，要求32,x x 和6x 为整数，则M=[2;3;6]；若要求全为整数，则M=1:6，或者M=[1;2;3;4;5;6]。TolXInteger 为判定整数的误差限，即若某数x 和最邻近整数相差小于该误差限，则认为x 即为该整数。
1 整数规划的MATLAB 求解方法 （一） 用MATLAB 求解一般混合整数规划问题 由于MATLAB 优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif 和Tawfik 在MATLAB Central 上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog ，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。intprog 函数的调用格式如下： [x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 该函数解决的整数规划问题为： ????? ??????∈=≥≤≤=≤=） 取整数（M j x n i x ub x lb b x A b Ax t s x c f j i eq eq T ),,2,1(0..min Λ 在上述标准问题中，假设x 为n 维设计变量，且问题具有不等式约束1m 个，等式约束2m 个，那么：c 、x 均为n 维列向量，b 为1m 维列向量，eq b 为2m 维列向量，A 为n m ?1维矩阵，eq A 为n m ?2维矩阵。 在该函数中，输入参数有c,A,b,A eq ,b eq ,lb,ub,M 和TolXInteger 。其中c 为目标函数所对应设计变量的系数，A 为不等式约束条件方程组构成的系数矩阵，b 为不等式约束条件方程组右边的值构成的向量。Aeq 为等式约束方程组构成的系数矩阵，b eq 为等式约束条件方程组右边的值构成的向量。lb 和ub 为设计变量对应的上界和下界。M 为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为621,,,x x x Λ，要求32,x x 和6x 为整数，则M=[2;3;6]；若要求全为整数，则M=1:6，或者M=[1;2;3;4;5;6]。TolXInteger 为判定整数的误差限，即若某数x 和最邻近整数相差小于该误差限，则认为x 即为该整数。
线性规划模型在生活中的实际应用 一、线性规划的基本概念 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题.满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域.决策变量、约束条件、目标函数是线性规划的三要素. 二、线性规划模型在实际问题中的应用 （1）线性规划在企业管理中的应用范围 线性规划在企业管理中的应用广泛，主要有以下八种形式： 1.产品生产计划：合理利用人力、物力、财力等，是获利最大. 2.劳动力安排：用最少的劳动力来满足工作的需要. 3.运输问题：如何制定运输方案，使总运费最少. 4.合理利用线材问题：如何下料，使用料最少. 5.配料问题：在原料供应的限制下如何获得最大利润. 6.投资问题：从投资项目中选取方案，是投资回报最大. 7.库存问题：在市场需求和生产实际之间，如何控制库存量从而获得更高利益.
8.最有经济计划问题：在投资和生产计划中如何是风险最小 . （2）如何实现线性规划在企业管理中的应用 在线性规划应用前要建立经济与金融体系的评价标准及企业的计量体系，摸清企业的资源.首先通过建网、建库、查询、数据采集、文件转换等，把整个系统的各有关部分的特征进行量化，建立数学模型，即把组成系统的有关因素与系统目标的关系，用数学关系和逻辑关系描述出来，然后白较好的数学模型编制成计算机语言，输入数据，进行计算，不同参数获取的不同结果与实际进行分析对比，进行定量，定性分析，最终作出决策. 3.3 线性规划在运输问题中的应用 运输是物流活动的核心环节，线性规划是运输问题的常用数学模型，利用数学知识可以得到优化的运输方案. 运输问题的提出源于如何物流活动中的运输路线或配送方案是最经济或最低成本的.运输问题解决的是已知产地的供应量，销地的需求量及运输单价，如何寻找总配送成本最低的方案；运输问题包含产销平衡运输问题和产销不平衡运输问题；通常将产销不平衡问题转化为产销平衡问题来处理；运输问题的条件包括需求假设和成本假设.需求假设指每一个产地都有一个固定的供应量所有的供应量都必须配送到目的地.与之类似，每一个目的地都有一个固定的需求量，整个需求量都必须有出发地满足；成本假设指从任何一个产地到任何一个销地的配送成本和所配送的数量的线性比例关系.产销平衡运输问题的一般提法是： 假设某物资有m个产地a1，a2，?，am;各地产量分别为b1，b2，?，bn，物资从产地Ai运往销地Bj的单位运价为cij,满足：
线性规划模型在实际生活中的应用 【摘要】线性规划在实际生活中扮演着很重要的角色，研究对象是计划管理工作中有关安排和估值的问题,其广泛应用于经济等领域，是实际生活中进行管理决策的最有效的方法之一。解决的主要问题是在给定条件下,按某一衡量指标来寻找安排的最优方案。本文通过对例题利用线性规划分析，如何合理的分配利用，最终找到最优解使企业利润最大，说明了线性规划在实际生活中的应用，而且对线性规划问题模型的建立，模型的解进行了分析，运用图解法和单纯形法解决问题。 【关键词】线性规划、建模、实际生活、图解法、单纯形法 前言：线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。 在实际生活中，经常会遇到一定的人力、物力、财力等资源条件下，如何精打细算巧安排，用最少的资源取得最大的效益的问题，而这正是线性规划研究的基本容，它在实际生活中有着非常广泛的应用．任何一个组织的管理者都必须对如何向不同的活动分配资源的问题做出决策，即如何有效地利用人力、物力完成更多的任务，或在预定的任务目标下如何耗用最少的人力、物力去实现目标。在许多情况下，大量不同的资源必须同时进行分配，需要这些资源的活动可以是不同的生产活动，营销活动，金融活动或者其他一些活动。随着计算技术的不断发展，使成千上万个约束条件和决策变量的线性规划问题能迅速地求解，更为线性规划在经济等各领域的广泛应用创造了极其有利的条件。线性规划已经成为现代化管理的一种重要的手段。本文运用常用的图解法和单纯形法解决利润最大化决策问题，贴近生活，很好的吧线性规划应用到生活实践中。 1、简单线性问题步骤简单介绍 建模是解决线性规划问题极为重要的环节，一个正确的数学模型的建立要求建模者熟悉线性规划的具体实际容，要明确目标函数和约束条件，通过表格的形式把问题中的已知
整数线性规划理论 §1 概论 1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型整数线性规划。目前所流行的求解整数规划的方法，往 1.2 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.3 整数规划特点 （i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1 原线性规划为 21min x x z += 0,0,5422121≥≥=+x x x x 其最优实数解为：4 5min ,4 5,021===z x x 。LINGO1.lg4 LINGO11.lg4 ③有可行解（当然就存在最优解），但最优解值变差。 例2 原线性规划为 21m i n x x z += 0,0,6422121≥≥=+x x x x 其最优实数解为：2 3min ,23,021===z x x 。 若限制整数得：2min ,1,121===z x x 。LINGO2.lg4 LINGO21.lg4 （ii ） 整数规划最优解不能按照实数最优解简单取整而获得。 1.4 求解方法分类： （i ）分枝定界法—可求纯或混合整数线性规划。 （ii ）割平面法—可求纯或混合整数线性规划。 （iii ）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。 （iv ）匈牙利法—解决指派问题（“0-1”规划特殊情形）。 （v ）蒙特卡洛法—求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 §2 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行
第三章 整数线性规划 本章, 我们介绍三种解决整数线性规划问题的软件: 第一种: MATLAB 中的optimization toolbox 中的若干程序; 第二种: LINDO 软件; 第二种: LINGO 软件. 1. MATLAB 程序说明 程序名: intprogram, L01p_e, L01p_ie, transdetobi, biprogram intprogram 是利用分支定界法解决整数规划问题, 是全部的整数规划问题; L01p_e 是利用枚举法解决0-1规划问题, 变量要求全部为0或者1; L01p_ie 是利用隐枚举法解决0-1规划问题, 变量要求全部为0或者1; Transdetobi 是枚举法和隐枚举法中利用到的将十进制数转化为二进制数的函数; Biprogram 是MATLAB6.5以上版本中有的求解0-1规划的函数的程序. intprogram 执行实例1： 12 121212max 2010s.t.5424 2513 ,0, f x x x x x x x x =++≤+≤≥ 且为整数 在命令窗口的程序执行过程和结果如下: >> c=[-20,-10]; %将最大转化为最小; >> a=[5,4;2,5]; >> b=[24;13]; >> [x,f]=intprogram(c,a,b,[0;0],[inf;inf],[],0,0.0001) % c,a,b 之后[0;0] is the value of low bound;[inf;inf] is the value of up bound;[] is the initialization;0 is the number of the equation constraints; 0.0001 is the concise rate. x = 4.0000 1.0000 f = -90 intprogram 执行实例2: 书中例题3.3.1 在命令窗口的程序执行过程和结果如下: >> c=[-1,-1]; >> a=[-4,2;4,2;0,-2]; >> b=[-1;11;-1];
通常，非线性整数规划是一个具有指数复杂度的NP问题，如果约束较为复杂，Matlab优 化工具箱和一些优化软件比如lingo等，常常无法应用，即使能应用也不能给出一个较为令 人满意的解。这时就需要针对问题设计专门的优化算法。下面举一个遗传算法应用于非线性整数规划的编程实例，供大家参考! 模型的形式和适应度函数定义如下: nun ￡ =迟叼匸［（1_冏）督 i-1 /-I J=K乙员-??严丿=12 M…严 ▼ 0 或1* 适应度函数为3 Fi tn叱O）=》〔?巾1口｛＞?（卡（￡）一/；0?门））转幷亠 Z j'-i 50 4 S0 其中比=2、即士￡ = ￡ =瓦％■，口（1-务），马；j^ = s = ■ x v' y- to.8,02）., /-I i-L i-1 E 这是一个具有200个01决策变量的多目标非线性整数规划，编写优化的目标函数如下，其 中将多目标转化为单目标采用简单的加权处理。 fun ctio n Fit ness=FITNESS(x,FARM,e,q,w) %%适应度函数 %输入参数列表 % x 决策变量构成的 4X50的0-1矩阵 % FARM 细胞结构存储的当前种群，它包含了个体x
% e 4 X50的系数矩阵 % q 4 X50的系数矩阵 % w 1 X50的系数矩阵 %% gamma=0.98; N=length(FARM);% 种群规模 F1=zeros(1,N); F2=zeros(1,N); for i=1:N xx=FARM{i}; ppp=(1-xx)+(1-q).*xx; F1(i)=sum(w.*prod(ppp)); F2(i)=sum(sum(e.*xx)); end ppp=(1-x)+(1-q).*x; f1=sum(w.*prod(ppp)); f2=sum(sum(e.*x)); Fitness=gamma*sum(min([sign(f1-F1);zeros(1,N)]))+(1-gamma)*sum(min([sign(f2- F2);zeros(1,N)])); 针对问题设计的遗传算法如下，其中对模型约束的处理是重点考虑的地方 function [Xp,LC1,LC2,LC3,LC4]=MYGA(M,N,Pm) %% 求解 01 整数规划的遗传算法 %% 输入参数列表
整数线性规划 【数学模型】 m in T x f x st. A x b ?≤ A eq x b eq ?= lb x ub ≤≤ i x 取值为整数 其中f , x , b , beq , lb 和ub 为向量，A 和Aeq 为矩阵。 【函数】 intprog 【说明】 在Matlab 中无求解整数线性规划的现成函数，利用Matlab 的线性规划函数linprog 来编写整数线性规划函数，输入与输出与linprog 类似，采用分枝定界法来实现。 Matlab 主程序intprog 如下： function [x,fval,status] = intprog(f,A,B,I,Aeq,Beq,lb,ub,e) %整数规划求解函数 intprog() % 其中 f 为目标函数向量 % A 和B 为不等式约束 Aeq 与Beq 为等式约束 % I 为整数约束 % lb 与ub 分别为变量下界与上界 % x 为最优解，fval 为最优值 % 控制输入参数 if nargin < 9, e = 0.00001; if nargin < 8, ub = []; if nargin < 7, lb = []; if nargin < 6, Beq = []; if nargin < 5, Aeq = []; if nargin < 4, I = [1:length(f)]; end , end , end , end , end , end %求解整数规划对应的线性规划,判断是否有解 options = optimset('display','off'); [x0,fval0,exitflag] = linprog(f,A,B,Aeq,Beq,lb,ub,[],options); if exitflag < 0 disp('没有合适整数解'); x = x0; fval = fval0; status = exitflag; return ; else %采用分支定界法求解
非线性规划模型 在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。 一、非线性规划的分类 1无约束的非线性规划 当问题没有约束条件时，即求多元函数的极值问题，一般模型为 ()min 0 x R f X X ∈??? ≥?? 此类问题即为无约束的非线性规划问题 1.1无约束非线性规划的解法 1.1.1一般迭代法 即为可行方向法。对于问题()min 0x R f X X ∈??? ≥?? 给出)(x f 的极小点的初始值)0(X ，按某种规律计算出一系列的),2,1()(Λ=k X k ，希望点阵}{)(k X 的极限*X 就是)(x f 的一个极小点。 由一个解向量) (k X 求出另一个新的解向量)1(+k X 向量是由方向和长度确定的，所以),2,1()1(Λ=+=+k P X X k k k k λ 即求解k λ和k P ，选择k λ和k P 的原则是使目标函数在点阵上的值逐步减小，即
.)()()(10ΛΛ≥≥≥≥k X f X f X f 检验}{)(k X 是否收敛与最优解，及对于给定的精度0>ε，是否ε≤?+||)(||1k X f 。 1.1.2一维搜索法 当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有： （1）试探法（“成功—失败”，斐波那契法，0.618法等）； （2）插值法（抛物线插值法，三次插值法等）； （3）微积分中的求根法（切线法，二分法等）。 考虑一维极小化问题 )(min t f b t a ≤≤ 若)(t f 是],[b a 区间上的下单峰函数，我们介绍通过不断地缩短],[b a 的长度，来搜索得)(min t f b t a ≤≤的近似最优解的两个方法。通过缩短区间],[b a ，逐步搜索得 )(min t f b t a ≤≤的最优解*t 的近似值 2.1.3梯度法 选择一个使函数值下降速度最快的的方向。把)(x f 在) (k X 点的方向导数最小的方向 作为搜索方向，即令)(k k X f P -?=. 计算步骤： （1）选定初始点0 X 和给定的要求0>ε，0=k ； （2）若ε
-- §2.7 非线性规划模型 在现实问题中，大量的问题是非线性的。因此，除线性规划外，应用更多的是非线性规划。本节简单介绍非线性规划的有关概念。 一. 引例 例1． 如图2-68，预建一猪舍， 围墙与隔墙的总长不能超过40米，问长、宽各多少时，面积最大？ 设长、宽分别是1x 米、2x 米时，问题即为下述优化问题：求 ???≥≤+0,4052max 2 1212 1x x x x st x x 易知，本问题的最优解是.4,1021 ==x x 例2． 某企业生产一种产品，其生产要素（可以是某种原材料，也可以是劳 力、资本等）编号为n ,,2,1 . 已知该产品的生产函数为),,,(21n x x x g (第i 种生产要素的投入量为i x 时的产品产出量)一般为非线性函数,设给定产品的总产量为a ,第 i 种生产要素的单位生产费用为i c ,问如何安排生产成本最低? 数学模型为: ???≥=∑0),,,(min 21i n i i x a x x x g st x c 例3． 最优国民经济计划模型 国民经济由n 个部门所组成, 编号为n ,,2,1 ,各部门间直接消耗的系数矩阵为 ()n j i ij a A 1,==,ij a 为第i 个部门生产价值一个单位的产品直接消耗j 部门产品的价值 11 x 2x ?? ? ????图2-68
-- 单位, j 部门的生产函数),(i i i i K L f x =其中i x 为第i 部门总产品的价值.i K 为投入 i 部门的资金数i L 为投入i 部门的劳力数.问在总劳动力L ,资金K 给定的前提下,如何 安排各部门的资金数及劳力投入,可使国民收入最大? 设i y 表示第i 部门最终产品的总价值,则数学模型为 ???? ???≥=≤≤+=∑∑∑∑0,,,),(max i i i i i i i i i i i j ij i i K L y x L K f x K K L L y x a x st y 例4． 确定经验公式－非线性回归分析 设(i t , i y ) (n i ,,2,1 =)为实际问题中的一组数据,且i y 与i t 有关系 ct be a y -+=,现求系数c b a ,,使得ct be a y -+=与数据组“最接近”。化为数学问题, 即求 ,,)(min 2 1 >+--=∑c b a be a y i ct k i i 一般地，称 min ),,(1n x x f s.t. m i x x g n i ， ,1,0),,(1=≥ l j x x h n j ,,1,0),,(1 == 为规划问题(或称为条件极值问题)。 特别1. 当j i h g ,为线性函数，f 为二次函数，称上述问题为二次规划； 2. 当f h g j i ,,均为线性函数，称上述问题为线性规划。
非线性整数规划的遗传算法Matlab程序（附图） 通常，非线性整数规划是一个具有指数复杂度的NP问题，如果约束较为复杂，Matlab优化工具箱和一些优化软件比如lingo等，常常无法应用，即使能应用也不能给出一个较为令人满意的解。这时就需要针对问题设计专门的优化算法。下面举一个遗传算法应用于非线性整数规划的编程实例，供大家参考！ 模型的形式和适应度函数定义如下： 这是一个具有200个01决策变量的多目标非线性整数规划，编写优化的目标函数如下，其中将多目标转化为单目标采用简单的加权处理。 function Fitness=FITNESS(x,FARM,e,q,w) %% 适应度函数 % 输入参数列表 % x 决策变量构成的4×50的0-1矩阵 % FARM 细胞结构存储的当前种群，它包含了个体x % e 4×50的系数矩阵 % q 4×50的系数矩阵 % w 1×50的系数矩阵 %% gamma=0.98; N=length(FARM);%种群规模 F1=zeros(1,N); F2=zeros(1,N); for i=1:N xx=FARM{i}; ppp=(1-xx)+(1-q).*xx; F1(i)=sum(w.*prod(ppp));
F2(i)=sum(sum(e.*xx)); end ppp=(1-x)+(1-q).*x; f1=sum(w.*prod(ppp)); f2=sum(sum(e.*x)); Fitness=gamma*sum(min([sign(f1-F1);zeros(1,N)]))+(1-gamma)*sum(min([sign(f2-F2);zeros(1, N)])); 针对问题设计的遗传算法如下，其中对模型约束的处理是重点考虑的地方 function [Xp,LC1,LC2,LC3,LC4]=MYGA(M,N,Pm) %% 求解01整数规划的遗传算法 %% 输入参数列表 % M 遗传进化迭代次数 % N 种群规模 % Pm 变异概率 %% 输出参数列表 % Xp 最优个体 % LC1 子目标1的收敛曲线 % LC2 子目标2的收敛曲线 % LC3 平均适应度函数的收敛曲线 % LC4 最优适应度函数的收敛曲线 %% 参考调用格式[Xp,LC1,LC2,LC3,LC4]=MYGA(50,40,0.3) %% 第一步：载入数据和变量初始化 load eqw;%载入三个系数矩阵e,q,w %输出变量初始化 Xp=zeros(4,50); LC1=zeros(1,M); LC2=zeros(1,M); LC3=zeros(1,M); LC4=zeros(1,M); Best=inf; %% 第二步：随机产生初始种群 farm=cell(1,N);%用于存储种群的细胞结构 k=0; while k %以下是一个合法个体的产生过程 x=zeros(4,50);%x每一列的1的个数随机决定 for i=1:50 R=rand; Col=zeros(4,1); if R<0.7 RP=randperm(4);%1的位置也是随机的 Col(RP(1))=1; elseif R>0.9 RP=randperm(4);
0-1型整数线性规划模型理论 (1) 0-1型整数线性规划 0-1型整数线性规划是一类特殊的整数规划,它的变量仅取值0或1.其模型如下: T min ..01(1,2, ,)j f s t x j n =??=?c x Ax =b 取或 其中()T 12,,,,n c c c =c ()T 12,,,,n x x x =x (),ij m n a ?=A ()T 12,,,.m b b b =b 称此时的决策变量为0-1变量,或称二进制变量.在实际问题中,如果引进0-1变量,就可以把各种需要分别讨论的线性(或非线性)规划问题统一在一个问题中讨论了. (2) 求解0-1型整数线性规划的分支界定法Matlab 指令 x = bintprog(f,A,b): 求解0-1型整数线性规划,用法类似于linprog. x = bintprog(f,A,b,Aeq,beq): 求解下述线性规划问题: T min ,z =f x ≤Ax b ,≤Ax b ,?≤Aeq x beq ,x 分量取0或1. x = bintprog(f,A,b,Aeq,beq,x0): 指迭代初值x0,如果没有不等式约束,可用[]代替A,b 表示默认,如果没有等式约束,可用[]代替Aeq 和beq 表示默认;用[x,fval]代替上述各命令行中左边的x,则可得到最优解处的函数值fval. 例如：求解0-1型整数线性规划模型: 1min n i i Z x ==∑ ()()() 123453568946791234712567 5812923 2200..20 0020 01(1,2,,9)j x x x x x x x x x x x x x x x x x x x s t x x x x x x x x x x x j ?-++++≤-?-++++≤-??-+++≤-??--+≤?-≤??--+≤??-≤?-+≤??--+≤??==? 或 用Matlab 软件编程可解得1236791x x x x x x ======,其他变量为0,共六门课,满足