基于M/M/S排队论的病床安排模型
（获２００９年大学生数学建模赛全国二等奖）
数学与计算科学学院雷蕾
信息科学与计算学院黄缨宁
信息科学与计算学院丁炜杰
指导老师：王其如教授
摘要
就医排队是一种我们非常熟悉的现象。在眼科医院的病床安排中，主要从医院高效工作和患者满意度两方面来考虑安排方法。本文通过确定两方面的权重，确立评价标准。
针对问题二，本文确定了从医院和患者两方面综合考虑的目标函数，医院各种诊疗规则的限制下进行线性规划，使得目标函数值（背离度）最小，得到问题二的解决方案。用问题一的标准评价，确实优于医院的FCFS模型。
问题三中对每一类病人术后恢复时间做统计，由计算机按照概率给出术后恢复的时间，运用第二问模型的选择方式，对近一段时间内的出入院人数作出合理预测，并根据M的排序确定患者入院的时间区间。
对于问题四，先确立白内障双眼手术的方案（调查支持可以任意不同两天手术），按照问题二的算法，先算出周二四做白内障手术的最小M值及入院前等待时间和术前等待时间。用计算机模拟出在手术时间可调整情况下M可能的最小值，得到周三五为最佳手术时间。尤其术前人均等待时间的优化减少使医院病床的有效使用率增加。模型改进率达到18.11%。
问题五要求确定病床固定分配使人均等待时间最短。病床的分配使整个排队系统变成了五个M/M/N模型，N为各类病床的数量。根据排队论中M/M/1模型的条件演化得到服务强度小于1及病床数固定不变。采取整数规划，在此限制条件下使得平均等待时间最小。从而算出各类病床的分配比例。
关键词：M/M/S模型泊松（Poisson）分布非线性规划优化模型病人满意度病床有效利用率
一．问题的重述
有某医院眼科门诊每天开放，住院部有病床79张。眼科手术主要分四大类：白内障、视网膜疾病、青光眼和外伤。
白内障手术较简单且没有急症。目前只在周一、三做白内障手术，此类病人的术前准备时间只需1、2天。如果要做双眼是周一先做一只，周三再做另一只。
外伤疾病通常属于急症，病床有空时立即安排住院，第二天便会安排手术。
其他眼科疾病情况不同，住院后2-3天就可接受手术，但术后观察时间较长。这类疾病手术时间可根据需要安排，一般不安排在周一、周三。
医院眼科手术条件较充分，可不考虑手术条件的限制，但考虑到医生的安排问题，通常情况下白内障手术与其他眼科手术（急症除外）不安排在同一天做。当前该住院部对全体非急症病人是按照FCFS规则安排住院，但等待病人越来越多。故要优化其模型
问题一：试分析确定合理的评价指标体系，用以评价该问题的病床安排模型的优劣。
问题二：试就该住院部当前的情况，建立合理的病床安排模型，以根据已知的第二天拟出院病人数来确定第二天应该安排哪些病人住院。并对你们的模型利用问题一中的指标体系做出评价。
问题三：作为病人，自然希望尽早知道自己何时能住院。能否根据当时住院病人及等待住院病人的统计情况，在病人门诊时即告知其大致入住时间区间。
问题四：若该住院部周六、周日不安排手术，请你们重新回答问题二，医院的手术时间安排是否应做出相应调整?
问题五：有人从便于管理的角度提出建议，在一般情形下，医院病床安排可采取使各类病人占用病床的比例大致固定的方案，试就此方案，建立使得所有病人在系统内的平均逗留时间（含等待入院及住院时间）最短的病床比例分配模型。
二．模型条件的假设
1.假设如有空床位，优先安排外伤病人；
2.设有一患者当天出院，则立即可以安排另外的人入院；
3.设定做白内障手术的两天不做其他手术；
4.假设除了外伤无其他急症；
5.白内障病人手术准备时间是1-2天的任意值，不是因人而异，青光眼和视网
膜疾病手术准备时间是2-3天的任意值。
三．符号的定义及说明
1.B
i
：各类患者从入院到手术所花费的平均时间（手术准备时间）；
2.θ
1θ
2
θ
3
：分别为M
1
M
2
M
3
的权值；
3.K
1i K
2i
：分别表示第i个病人在第一阶段的等待时间和该病人在术前住院时
间；
4.S：某一天出院的病人数；
5.W：等待病床的总人数；
6.W
1W
2
W
3
W
4
：分别等待病床的人中白双、白单、青光眼和视网膜疾病、外伤的
人数；
7.P (i,j)：第i类第j号的人；
8.M(i,j)：第i类第j号人的M；
9.P
k
：泊松分布中k个病人到达的概率；
10.λ
1λ
2
λ
3
λ
4
λ
5
λ
6
：分别表示白双、白单、青光眼、视网膜疾病，外伤以及
出院人数的平均到达率；
11.P
n
(t)：时间t内有n个患者在排队的概率；
12.ρ
i
：各类病床系统的服务强度；
13.μ
i
：各类患者的平均服务率；
14.n1 n2 n3 n4 n5：五类病人各应该分配的病床数；
15.D1，D2：选择两天做白内障手术的星期数;
16.x1 x2 x3 x4 x5 x6 a1 a2 a3 a4 a5 a6:各种病情的等待人数及其系数
四．模型的分析及求解
问题一：
1.确定评价指标：
从病人和医院两方面对模型进行分析，病人方面以花费时间，住院费用和公平性作为满意程度的指标，医院方面以病床利用率和病床有效利用率为作为评价指标。同时还有一些客观条件有可能影响到评价指标，如所有病者是否一致对待还是有优先考虑。
花费时间是指从门诊到出院的时间，费用则根据入院到出院的时间计算，公平性是根据是否先门诊先入院来进行评判，床位利用率是指住有病人的床位与所有床位的比，有效的床位利用是指床位上所住病人属于必须住院日期与所住的所有日期的比，如白内障术前准备时间2-3天，术后恢复时间3-4天，超过此时间则属于床位的无效利用，需要避免。
将患者就医分为三个过程：门诊到入院为第一阶段，入院到进行手术为第二阶段，手术完毕到出院为第三阶段。得出如下评价指标可能的构成因素：
1.第一阶段等待时间
1.花费时间
2.第二阶段等待时间
3.第三阶段的住院时间
患者（满意度） 1第二阶段准备时期费用
2.住院的费用 2 第三阶段住院费用
3手术费用
可能构成因素
3.公平性
医院（效率） 1.床位利用率
2.床位有效利用率
客观条件：1.病者类别
整数规划的数学模型及解的特点 整数规划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）分布非线性规划优化模型病人满意度病床有效利用率
第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/1f16870162.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 即为该整数。
通常，非线性整数规划是一个具有指数复杂度的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 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 %
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 中的向量点。
非线性整数规划的遗传算法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);
非线性规划模型 在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。 一、非线性规划的分类 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）若ε
非线性规划与多目标规划模型及其求解 一、实验目的及意义 [1] 学习非线性规划模型的标准形式和建模方法； [2] 掌握建立非线性规划模型的基本要素和求解方法； [3] 熟悉MATLAB 软件求解非线性规划模型的基本命令； [4] 通过范例学习，了解建立非线性规划模型的全过程，与线性规划比较其难点何在。 通过该实验的学习，使学生掌握最优化技术，认识面对什么样的实际问题，提出假设和建立优化模型，并且使学生学会使用MATLAB 软件进行非线性规划模型求解的基本命令，并进行灵敏度分析。解决现实生活中的最优化问题是本科生学习阶段中一门重要的课程，因此，本实验对学生的学习尤为重要。 二、实验内容 1．建立非线性规划模型的基本要素和步骤； 2．熟悉使用MATLAB 命令对非线性规划模型进行计算与灵敏度分析； 3．学会计算无约束优化问题和有约束优化问题的技巧。 三、实验步骤 1．开启MATLAB 软件平台，开启MATLAB 编辑窗口； 2．根据问题，建立非线性规划模型，并编写求解规划模型的M 文件； 3．保存文件并运行； 4．观察运行结果(数值或图形)，并不断地改变参数设置观察运行结果； 5．根据观察到的结果和体会，写出实验报告。 四、实验要求与任务 根据实验内容和步骤，完成以下实验，要求写出实验报告（实验目的→问题→数学模型→算法与编程→计算结果→分析、检验和结论） 基础实验 1求解无约束优化 1) 画出该曲面图形, 直观地判断该函数的最优解; 2) 使用fminunc 命令求解, 能否求到全局最优解 ? 120.5(cos(2)cos(2))12min (,)2022.713 ..55,1,2 x x i f x x e e s t x i ππ-+=--+-≤≤=