非线性规划模型

非线性规划模型

在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在

实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都

可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。

一、非线性规划的分类1无约束的非线性规划当问题没有约束条件时，即求多元函数

的极值问题，一般模型为

I r m i n f(X)

X 一0

此类问题即为无约束的非线性规划问题

1.1无约束非线性规划的解法

1.1.1 一般迭代法

即为可行方向法。对于问题J mnf(X)

[X X O

给出f (X)的极小点的初始值X(O),按某种规律计算出一系列的X(k)(k =1,2,…)，

希望点阵｛X (k)｝的极限X "就是f (X)的一个极小点。

由一个解向量X(k)求出另一个新的解向量X(kI)

向量是由方向和长度确定的，所以XZ I)=X k「k P k(k =12…)

即求解A和P k,选择'k和P k的原则是使目标函数在点阵上的值逐步减小，即

f (X0) 一f (X1) 一- f (X k) 一.

检验｛X(k)｝是否收敛与最优解，及对于给定的精度；7,是否IIlf(X k JlF ；

1.1.2 一维搜索法

当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有：

(1)试探法(“成功一失败”，斐波那契法，0.618法等)；

(2)插值法(抛物线插值法，三次插值法等)；

(3)微积分中的求根法(切线法，二分法等)。考虑一维极小化问题

a?f(t)

若f (t)是[a,b]区间上的下单峰函数，我们介绍通过不断地缩短[a,b]的长度，来

搜索得min f(t)的近似最优解的两个方法。通过缩短区间 [a,b],逐步搜索得 a 空 m t in f (t)的最优解t *的近似值

a

-≤ιb

2.1.3 梯度法

选择一个使函数值下降速度最快的的方向。

把f(x)在X (IO

点的方向导数最小的方向

作为搜索方向，即令 P k

——?

f (X k

).

计算步骤：

(1) 选定初始点 X 0

和给定的要求；?0，k=0 ；

(2) 若 |八 f(X k

)* ;,则停止计算，X^X k

,否则 P

(k)

=-V f(X k

)；

(3)

在X (k

)处沿方向P (I)

做一维搜索得x (

j

I)

=

X k

…k P k

,令k = kT ,返回 第二

步，直到求得最优解为止

.可以求得：

、_ Vf(X

(I)

)? V f (X (I)

) ^Vf(X (I)

)T

.H(X (I)

^V f(X (I)

).

2.1.4共轭梯度法

又称共轭斜量法，仅适用于正定二次函数的极小值问题：

1

min f(X) = X T

AX B T

X C

2

A 为n n 阶实对称正定阵 X,

B ? E n

,c 为常数

从任意初始点X (I)

和向量P

(I)

= -

f (X ⑴)出发，由

(f (X (I)

)

δχ

所(X

(I)

)…

))T

CX n

CX 2

「济(X (I)

) 商(X

(I)

)…

CF(X

(I)

)I

、 J

CX 1

ZV

J

% EX n Cf(X (I)

) 商(X (I)

)…

Gr(X (I)

)

cx 2^x 1

- CX 2CX 2 ,

≡

CX 2

C X n

-

Cf(X (I)

) 伊(X (I)

)… GF(X (I)

) CX n CX I

~!

CX^X 2

'

EXnEX n

H(X (I)

)二

If(X (I)

) =

(k “2 ,n -1)

可以得到一一能够证明向量一一是线性无关的，且关于 A 是两两共轭的。从而可得到

则 为 的极小点。 计算步骤:

(1)对任意初始点

X

(I)

?

E n

和向量P ⑴-f (X ⑴)，取k = 1;

(2)若I

f (X (I)

) =0,即得到最优解，停止计算，否则求

(k =1,2,…,n -1)

(3)令 k =k 1 ；返回(2)

2.1.5 牛顿法

对于问题：

1 min f(X) X T

AX B T

X C

2

由I f(X)=AX ?B=0,则由最优条件'f(X) =0,当A 为正定时，Ad 存在，于是有

X^ -A 4B 为最优解

2.1.6 拟牛顿法

对于一般的二阶可微函数f (X),在X (I)

点的局部有

f(X) ： f(X (I)

Γ If(X (I)

)T

(X _ X (I)

) ? 1(X _ X (I)

)TI 2

f(X (I)

)(^X (I)

)

2

当√f(X Ck)

)正定时，也可用上面的牛顿法，这就是拟牛顿法。

X (k D =X k k

P k k

= min f (x (k

)

k

P (k )

)=

Cf(X (k )))T p (k )

(P (

G )T AP (k)

和 P (k I)

-f (x (k I)

) —P (k

「k

Vf(X (k I)

) A (P (Io )T

(P (k))T

AP

(k)

X (k 1) = X k k

P k

, k

= min f(X (I) k

P (I)

)=

" f(X )) P (P (I))T

AP

(I)

P (

k D

一屮x (k1)

)「k P (k)

「k

U(X (II)

)A (P (I))T

(P (I))T

AP

(I)

计算步骤：

(1)任取 X(I)?E n，k =1;

(2)计算g1.八f(X(k)),若g k =0 ,则停止计算，否则计算H(X k)八2f(X(k))，

令 X(k I)=X k-(H(X k))S k ；

(3)令 k =k 1 ；返回(2)

2有约束的非线性规划

2.1非线性规划的最优性条件

… * *

若X是非线性问题中的极小点，且对点 X有效约束的梯度线性无关，

则必存在向量r =(丫；异；川I,Y m T使下述条件成立：

「m

H(X h—z Y浮gj(X"=0

Ag j X* =0, j =1,2

V* ≥0, j =1,2^∣,m

I

此条件为库恩-塔克条件(K-T条件)，满足K-T条件的点也称为K-T点。K-T条件

是非线性规划最重要的理论基础，是确定某点是否为最优解的必要条件，但不一

定是充要条件。对于凸规划它一定是充要条件。

2.2非线性规划的可行方向法

由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是整

个可行域上的全局最优解。非线性规划却不然，有时求出的某个解虽是一部分可

行域上的极值点，但并不一定是整个可行域上的全局最优解。

假设X k非线性规划问题中的一个可行解，但不是最优解，为了进一步

寻找最优解在它的可行下降方向中选取其中一个方向 D k,并确定最佳

步长,k,使得

[χ(k4τ)= χ(k)十打D(k)w R

,k=0,1,2,川.

f X k 1： f X k

反复进行这一过程，直到得到满足精度要求为止，这种方法称为可行方向法，也

称迭代法。

2.3有约束非线性规划的解法

2.3.1 外点法

(1)对于等式约束问题

p^min f (X), Jh(X)=O,i =1,2,…m,

做辅助函数

m

R(X,M) = f (X) +M W h f(X)

j4

如果最优解X ”满足或近似满足h i(X*) =0 (j =d,2,…,m),则X ”就是问题的

最优解或近似解

(2)对于不等式约束问题

做辅助函数

m

F2(X,M) = f(X) M' [min{0g(X)}]2

j^

求mjn P2(X,M ).

(3)对于一般问题

做辅助函数

P3(X,M) = f(X) MP(X)

m m

P(X)=M' ∣h j2(X) I2M^ [min{0g(X)}]2

j j m

求解min P3 (X, M)

X

2.3.2 内点法

内点法是在可行域内进行得，并一直保持在可行域内进行搜索，只适用于不等式约束的问题

辅助函数：

Q(X,r) = f(X) rB(X)

X趋于R的边界时，使B(X)趋向于正无穷，B(X)的常用形式

m

I

B(X)八一1

Ug j(X)

m

和B(X)-'I n[g j(X)]

j^

求解 min Q(X,r)

X巩

R0 ={X Ig j(X) 0, j =1,2, ,m}

(完整word版)整数规划的数学模型及解的特点

整数规划的数学模型及解的特点 整数规划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

非线性规划-优化模型

基于M/M/S排队论的病床安排模型 （获２００９年大学生数学建模赛全国二等奖） 数学与计算科学学院雷蕾 信息科学与计算学院黄缨宁 信息科学与计算学院丁炜杰 指导老师：王其如教授 摘要 就医排队是一种我们非常熟悉的现象。在眼科医院的病床安排中，主要从医院高效工作和患者满意度两方面来考虑安排方法。本文通过确定两方面的权重，确立评价标准。 针对问题二，本文确定了从医院和患者两方面综合考虑的目标函数，医院各种诊疗规则的限制下进行线性规划，使得目标函数值（背离度）最小，得到问题二的解决方案。用问题一的标准评价，确实优于医院的FCFS模型。 问题三中对每一类病人术后恢复时间做统计，由计算机按照概率给出术后恢复的时间，运用第二问模型的选择方式，对近一段时间内的出入院人数作出合理预测，并根据M的排序确定患者入院的时间区间。 对于问题四，先确立白内障双眼手术的方案（调查支持可以任意不同两天手术），按照问题二的算法，先算出周二四做白内障手术的最小M值及入院前等待时间和术前等待时间。用计算机模拟出在手术时间可调整情况下M可能的最小值，得到周三五为最佳手术时间。尤其术前人均等待时间的优化减少使医院病床的有效使用率增加。模型改进率达到18.11%。 问题五要求确定病床固定分配使人均等待时间最短。病床的分配使整个排队系统变成了五个M/M/N模型，N为各类病床的数量。根据排队论中M/M/1模型的条件演化得到服务强度小于1及病床数固定不变。采取整数规划，在此限制条件下使得平均等待时间最小。从而算出各类病床的分配比例。 关键词：M/M/S模型泊松（Poisson）分布非线性规划优化模型病人满意度病床有效利用率

数学建模线性规划与非线性规划

实验7：线性规划与非线性规划 班级：2015级电科班，学号：222015333210187，姓名：吴京宣，第1组 ====================================================================== 一、实验目的： 1. 了解线性规划的基本内容。 2. 直观了解非线性规划的基本内容。 3. 掌握用数学软件求解优化问题。 二、实验内容 1. 两个引例. 2. 用数学软件包MATLAB求解线性规划与非线性规划问题. 3. 用数学软件包LINDO、LINGO求解线性规划问题. 4. 建模案例：投资的收益与风险. 5. 非线性规划的基本理论 6. 钢管订购及运输优化模型． 三、实验步骤 对以下问题,编写M文件: 1.某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过800箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论: 1)若投资0.8万元可增加原料1千克,问应否作这项投资. 2)若每100箱甲饮料获利可增加1万元,问应否改变生产计划. 2.某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货40台、60 台、80台．每季度的生产费用为（单位:元）, 其中x 是该季度生产的台数．若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度c元．已知工厂每季度最大生产能力为100台，第一季度开始时无存货，设a=50、b=0.2、c=4，问:工厂应如何安排生产计划，才能既满足合同又使总费用最低．讨论a、b、c变化对计划的影响，并作出合理的解释．

第5讲 整数规划、非线性规划、多目标规划1

第5讲整数规划、非线性规划、多目标规划 一、整数规划 1、概念 数学规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。 整数规划的分类:如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：1）变量全限制为整数时，称纯（完全）整数规划。 2）变量部分限制为整数的，称混合整数规划。 2、整数规划特点 (i)原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。

例1原线性规划为 2 1min x x z +=s.t. ?? ?≥≥=+0 ,05422121x x x x 其最优实数解为：01=x ，4 52=x ， 4 5min = z ③有可行解（当然就存在最优解），但最优值变差。例2原线性规划为 2 1min x x Z +=s.t. ?? ?≥≥=+0 ,06422121x x x x 其最优实数解为：01=x ，2 32=x ，2 3min = z 若限制整数得：11=x ，12=x ， 2 min =z 。 （ii ）整数规划最优解不能按照实数最优解简单取整而获得。

3、0-1整数规划 0?1型整数规划是整数规划中的特殊情形，它的变量 j x 仅取值 0或1。这时 j x 称为 0?1变量，或 称二进制变量。j x 仅取值0或1这个条件可由下述约束条件： 1 0≤≤j x ，且为整数 所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入0?1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。 引入10-变量的实际问题： （1）投资场所的选定——相互排斥的计划 例3某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）)7,,2,1( =i A i 可供选择。规定 在东区：由321,,A A A 三个点中至多选两个；在西区：由54,A A 两个点中至少选一个；

数学建模(整数规划)

整数规划模型

实际问题中 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/308348254.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无约束的非线性规划 当问题没有约束条件时，即求多元函数的极值问题，一般模型为 ()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）插值法（抛物线插值法，三次插值法等）；

整数规划和多目标规划模型

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 即为该整数。

数学建模-非线性规划

-32- 第三章 非线性规划 §1 非线性规划 1.1 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。 下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念。 例1 （投资决策问题）某企业有n 个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金A 元，投资于第),,1(n i i L =个项目需花资金i a 元，并预计可收益i b 元。试选择最佳投资方案。 解 设投资决策变量为 ?? ?=个项目 决定不投资第，个项目 决定投资第i i x i 0,1，n i ,,1L =， 则投资总额为 ∑=n i i i x a 1，投资总收益为 ∑=n i i i x b 1 。因为该公司至少要对一个项目投资，并 且总的投资金额不能超过总资金A ，故有限制条件 ∑=≤< n i i i A x a 1 另外，由于),,1(n i x i L =只取值0或1，所以还有 .,,1,0)1(n i x x i i L ==? 最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为： ∑∑=== n i i i n i i i x a x b Q 11max s.t. ∑=≤< n i i i A x a 1 .,,1,0)1(n i x x i i L ==? 上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式 )(min x f q j x h j ,,1, 0)(s.t. L =≤ (NP) p i x g i ,,1, 0)(L ==

整数线性规划理论

整数线性规划理论 §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 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行

整数线性规划word版

第三章 整数线性规划 本章, 我们介绍三种解决整数线性规划问题的软件: 第一种: 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];

遗传算法解决非线性规划问题的Matlab程序

通常，非线性整数规划是一个具有指数复杂度的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 整数规划的遗传算法 %% 输入参数列表

多目标非线性规划程序Matlab完整版

多目标非线性规划程序 M a t l a b Document serial number【NL89WT-NY98YT-NC8CB-NNUUT-NUT108】

f u n c t i o n[e r r m s g,Z,X,t,c,f a i l]= BNB18(fun,x0,xstat,xl,xu,A,B,Aeq,Beq,nonlcon,setts,options1,options2,maxSQPit,varargin ); %·Dêy1￡Díóa·§¨μü′ú·¨￡úDê1ó￡DèOptimization toolbox §3 % Minimize F(x) %subject to: xlb <= x <=xub % A*x <= B % Aeq*x=Beq % C(x)<=0 % Ceq(x)=0 % % x(i)éaáD±á￡êy￡ò1ì¨μ % ê1óê %[errmsg,Z,X]=BNB18('fun',x0,xstat,xl,xu,A,B,Aeq,Beq,'nonlcon',setts) %fun￡o Mt￡±íê×Dˉ±êoˉêyf=fun(x) %x0: áDòá￡±íê±á3μ %xstat￡o áDòá￡xstat(i)=0±íêx(i)aáD±á￡1±íêêy￡2±íê1ì¨μ %xl￡o áDòá￡±íê±á %xu: áDòá￡±íê±áé %A: ó, ±íêD2μèêêμêy %B: áDòá, ±íêD2μèêêé %Aeq: ó, ±íêDμèêêμêy %Beg: áDòá, ±íêD2μèêêóòμ %nonlcon: Mt￡±íê·Dêoˉêy[C,Ceq]=nonlin(x),DC(x)a2μèêê, % Ceq(x)aμèêê %setts: ·¨éè %errmsq: ·μ′íóìáê %Z: ·μ±êoˉêy×Dμ %X: ·μ×óa % %àyìa % max x1*x2*x3 % -x1+2*x2+2*x3>=0 % x1+2*x2+2*x3<=72 % 10<=x2<=20 % x1-x2=10 % èD′ Moˉêy % function f=discfun(x) % f=-x(1)*x(2)*x(3); %óa % clear;x0=[25,15,10]';xstat=[1 1 1]'; % xl=[20 10 -10]';xu=[30 20 20]'; % A=[1 -2 -2;1 2 2];B=[0 72]';Aeq=[1 -1 0];Beq=10; % [err,Z,X]=BNB18('discfun',x0,xstat,xl,xu,A,B,Aeq,Beq); % XMAX=X',ZMAX=-Z %

整数线性规划

整数线性规划 【数学模型】 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 %采用分支定界法求解

多目标非线性规划程序(Matlab)

function [errmsg,Z,X,t,c,fail] = BNB18(fun,x0,xstat,xl,xu,A,B,Aeq,Beq,nonlcon,setts,options1,options2,ma xSQPit,varargin); %·???D???êy1????￡Dí?ó?a·??§?¨??μü′ú??·¨?￡?úMATLAB5.3?Dê1ó?￡?DèOptimizat ion toolbox 2.0?§3?? % Minimize F(x) %subject to: xlb <= x <=xub % A*x <= B % Aeq*x=Beq % C(x)<=0 % Ceq(x)=0 % % x(i)?é?aá?D?±?á?￡???êy￡??ò1ì?¨?μ % ê1ó???ê? %[errmsg,Z,X]=BNB18('fun',x0,xstat,xl,xu,A,B,Aeq,Beq,'nonlcon',setts) %fun￡o M???t??￡?±íê?×?D??ˉ??±êoˉêyf=fun(x) %x0: áD?òá?￡?±íê?±?á?3??μ %xstat￡o áD?òá?￡?xstat(i)=0±íê?x(i)?aá?D?±?á?￡?1±íê???êy￡?2±íê?1ì?¨?μ %xl￡o áD?òá?￡?±íê?±?á????? %xu: áD?òá?￡?±íê?±?á?é??? %A: ???ó, ±íê???D?2?μèê???ê??μêy %B: áD?òá?, ±íê???D?2?μèê???ê?é??? %Aeq: ???ó, ±íê???D?μèê???ê??μêy %Beg: áD?òá?, ±íê???D?2?μèê???ê?óò???μ %nonlcon: M???t??￡?±íê?·???D???ê?oˉêy[C,Ceq]=nonlin(x),???DC(x)?a2?μèê???ê?, % Ceq(x)?aμèê???ê? %setts: ??·¨éè?? %errmsq: ·μ??′í?óìáê? %Z: ·μ????±êoˉêy×?D??μ %X: ·μ??×?ó??a % %àyìa % max x1*x2*x3 % -x1+2*x2+2*x3>=0 % x1+2*x2+2*x3<=72 % 10<=x2<=20 % x1-x2=10 % ?èD′ Moˉêydiscfun.m % function f=discfun(x) % f=-x(1)*x(2)*x(3); %?ó?a % clear;x0=[25,15,10]';xstat=[1 1 1]'; % xl=[20 10 -10]';xu=[30 20 20]'; % A=[1 -2 -2;1 2 2];B=[0 72]';Aeq=[1 -1 0];Beq=10; % [err,Z,X]=BNB18('discfun',x0,xstat,xl,xu,A,B,Aeq,Beq); % XMAX=X',ZMAX=-Z % % BNB18 Finds the constrained minimum of a function of several possibly integer variables. % Usage: [errmsg,Z,X,t,c,fail] = % BNB18(fun,x0,xstatus,xlb,xub,A,B,Aeq,Beq,nonlcon,settings,options1,opti ons2,maxSQPiter,P1,P2,...) % % BNB solves problems of the form: % Minimize F(x) subject to: xlb <= x0 <=xub

一般非线性规划

一般非线性规划 标准型为： min F(X) s.t AX<=b b e q X A e q =? G(X)0≤ Ceq(X)=0 VLB ≤X ≤VUB 其中X 为n 维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab 求解上述问题，基本步骤分三步： 1. 首先建立M 文件fun.m,定义目标函数F （X ）: function f=fun(X); f=F(X); 2. 若约束条件中有非线性约束:G(X)0≤或Ceq(X)=0,则建立M 文件nonlcon.m 定义函数G(X)与Ceq(X): function [G,Ceq]=nonlcon(X) G=... Ceq=... 3. 建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下： (1) x=fmincon (‘fun’,X0,A,b) (2) x=fmincon (‘fun’,X0,A,b,Aeq,beq) (3) x=fmincon (‘fun’,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fmincon (‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’) (5)x=fmincon (‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’,options) (6) [x,fval]= fmincon(...) (7) [x,fval,exitflag]= fmincon(...) (8)[x,fval,exitflag,output]= fmincon(...) 注意： [1] fmincon 函数提供了大型优化算法和中型优化算法。默认时，若在

目标规划模型

§5.3 目标规划模型 1. 目标规划模型概述 1)引例 目标规划模型是有别于线性规划模型的一类多目标决策问题模型，通过下面的例子，我们可看出这两者的区别。 例1 某工厂的日生产能力为每天500小时，该厂生产A 、B 两种产品，每生产一件A 产品或B 产品均需一小时，由于市场需求有限，每天只有300件A 产品或400件B 产品可卖出去，每出售一件A 产品可获利10元，每出售一件B 产品可获利5元，厂长按重要性大小的顺序列出了下列目标，并要求按这样的目标进行相应的生产。 （1）尽量避免生产能力闲置； （2）尽可能多地卖出产品，但对于能否多卖出A 产品更感兴趣； （3）尽量减少加班时间。 显然，这样的多目标决策问题，是单目标决策的线性规划模型所难胜任的，对这类问题，须采用新的方法和手段来建立对应的模型。 2）相关的几个概念 （1）正、负偏差变量+ d 、- d 正偏差变量+ d 表示决策值 ) ,,2,1(n i x i =超过目标值的部分；负偏差变量 - d 表示决策值 ) ,,2,1(n i x i =未达到目标值的部分；一般而言，正负偏差变量 + d 、- d 的相互关系如下： 当决策值 ) ,,2,1(n i x i =超过规定的目标值时， ,0=>- + d d ；当决策值 ),,2,1(n i x i =未超过规定的目标值时，0 ,0>=- + d d ；当决策值 ) ,,2,1(n i x i =正好等于规定的目标值时， ,0==- + d d 。 （2）绝对约束和目标约束 绝对约束是必须严格满足的等式约束或不等式约束，前述线性规划中的约束

条件一般都是绝对约束；而目标约束是目标规划所特有的，在约束条件中允许目标值发生一定的正偏差或负偏差的一类约束，它通过在约束条件中引入正、负偏差变量+ d 、- d 来实现。 （3）优先因子（优先级）与权系数 目标规划问题常要求许多目标，在这些诸多目标中，凡决策者要求第一位达到的目标赋予优先因子1P ，要求第二位达到的目标赋予优先因子2P ，……，并规定1+>>k k P P ，即1+k P 级目标的讨论是在k P 级目标得以实现后才进行的（这里 n k ,,2,1 =）。若要考虑两个优先因子相同的目标的区别，则可通过赋予它们 不同的权系数 j w 来完成。 3）目标规划模型的目标函数 目标规划的目标函数是根据各目标约束的正、负偏差变量+ d 、- d 和其优先因子来构造的，一般而言，当每一目标值确定后，我们总要求尽可能地缩小与目标值的偏差，故目标规划的目标函数只能是 ) ,( min - +=d d f z 的形式。我们 可将其分为以下三种情形： （1）当决策值) ,,2,1(n i x i =要求恰好等于规定的目标值时，这时正、负 偏差变量+ d 、- d 都要尽可能小，即对应的目标函数为： ) ( min - + +=d d f z ； （2）当决策值) ,,2,1(n i x i =要求不超过规定的目标值时，这时正偏差变 量+ d 要尽可能小，即对应的目标函数为： ) ( min + =d f z ； （3）当决策值 ) ,,2,1(n i x i =要求超过规定的目标值时，这时负偏差变量 - d 要尽可能小，即对应的目标函数为： ) ( min - =d f z 。 目标规划数学模型的一般形式为： ∑∑=+ +-- =+= K k k lk k lk L l l d w d w P z 1 1 ) ( min

非线性规划模型-

-- §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 ,,均为线性函数，称上述问题为线性规划。

非线性规划(教案)

非线性规划 线性规划及其扩展问题的约束条件和目标函数都是关于决策变量的一次函数。虽然大量的实际问题可以简化为线性规划及其扩展问题来求解，但是还有相当多的问题很难用线性函数加以描述。如果目标函数或约束条件中包含有非线性函数，就称这样的规划问题为非线性规划问题。由于人们对实际问题解的精度要求越来越高，非线性规划自20世纪70年代以来得到了长足的发展；目前，已成为运筹学的一个重要分支，在管理科学、最优设计、系统控制等许多领域得到了广泛的应用。 一般来讲，非线性规划问题的求解要比线性规划问题的求解困难得多；而且也不象线性规划问题那样具有一种通用的求解方法（单纯形法）。非线性规划没有能够适应所有问题的一般求解方法，各种方法都只能在其特定的范围内发挥作用。 本章在简要介绍非线性规划基本概念和一维搜索的基础上，重点介绍无约束极值问题和约束极值问题的求解方法。 §1非线性规划的数学模型 1.1 非线性规划问题 [例1] 某商店经销A 、B 两种产品，售价分别为20和380元。据统计，售出一件A 产品的平均时间为0.5小时，而售出一件B 产品的平均时间与其销售的数量成正比，表达式为n 2.01+。若该商店总的营业时间为1000小时，试确定使其营业额最大的营业计划。 解：设1x 和2x 分别代表商店经销A 、B 两种产品的件数，于是有如下数学模型： 2138020)(m ax x x x f += 10002.05.02 221≤++x x x 0,021≥≥x x 1.2 非线性规划问题的数学模型 同线性规划问题的数学模型一样，非线性规划问题的数学模型可以具有不同的形式；但由于我们可以自由地实现不同形式之间的转换，因此我们可以用如下一般形式来加以描述： n E X X f ∈),(m in ),,2,1(,0)(m i X h i == ),,2,1(,0)(l j X g j =≥ 其中T n x x x X ),,,(21 =是n 维欧氏空间n E 中的向量点。