1线性规划的局限性
在我们解题过程中，大量运用线性规划建模，但是在很多情况下，线性规划具有不可避免的局限性：
（1）线性规划要求所解决的问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；
（2）线性规划只能处理单目标的优化问题，而对一些次目标只能转化为约束处理，而在实际问题中，目标和约束是可以相互转化的，处理时不一定要严格区分；
（３）线性规划在处理问题时，将各个约束（也可看做目标）的地位看成同等重要，而在实际问题中，各目标的重要性即有层次上的差别，也有在同一层次上不同权重的差别；
（４）线性规划寻找最优解，而许多实际问题只需要找到满意解就可以了。
２目标规划的基本概念
为了克服线性规划的局限性，目标规划采用如下手段。
1). 设置偏差变量
用偏差变量来表示实际值与目标值之间的差异，令d+为超出目标的差值，称为正偏差变量；d- 为未达到目标的差值，称为负偏差变量。其中d+ 与d- 至少有一个为0。当实际值超过目标值时，有d- =0，d+>0;当实际值未达到目标值时，有d+ =0，d- >0；当实际值与目标值一致时，有d+ =d- =0。
2）统一处理目标与约束
在目标规划中，约束有两类，一类是对资源有严格限制的，同线性规划的处理相同，用严格的等式或不等式约束来处理，成为刚性约束；
另一类约束是可以不严格控制的，连同原线性规划的目标，构成柔性约束。如果希望不等式保持大于等于，则极小化负偏差；如果希望不等式保持小于等于，则极小化正偏差；如果希望保持等式，则同时极小化正、负偏差。
3）目标的优先级与权系数
在目标规划模型中，目标的优先分为两个层次。第一个层次是目标分成不同的优先级，在计算目标规划时，必须先优化高优先级的目标，然后再优化低优先级的目标。通常以P1，P2，……表示不同的因子，并规定了优先等级。第二个层次是目标处于同一优先级，但两个目标的权重不一样，因此两目标同时优化，但用权系数的大小来表示目标重要性的差别。
３目标规划模型的建立
总的来讲，目标规划在建模中，除刚性约束必须严格满足外，对所有目标约束均允许有偏差。其求解过程要从高到低逐层优化，在不增加高层次目标的偏差值的情况下，逐次使低层次的偏差达到极小。
3.1例题：（生产安排问题）某企业生产甲、乙两种产品，需要用到A、B、C三种设备，关于产品的盈利与使用设备的工时及限制如表1-1所示。问：该企业应如何安排生产，使得在计划期内总利润最大？
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 即为该整数。
数学建模8-动态规划和目标规划 一、动态规划 1.动态规划是求解决策过程最优化的数学方法，主要用于求解以时间划分阶段的动态过程的 优化问题。但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 2.基本概念、基本方程： （1）阶段 （2）状态 （3）决策 （4）策略 （5）状态转移方程： （6）指标函数和最优值函数： （7）最优策略和最优轨线 （8）递归方程： 3．计算方法和逆序解法（此处较为抽象，理解较为困难，建议结合例子去看）
4．动态规划与静态规划的关系：一些静态规划只需要引入阶段变量、状态、决策等就可以用动态规划方法求解（详见书中例4） 5．若干典型问题的动态规划模型： （1）最短路线问题： （2）生产计划问题:状态定义为每阶段开始时的储存量x k，决策为每个阶段的产量，记每个阶段的需求量（已知量）为d k，则状态转移方程为 （3）资源分配问题：详见例5
状态转移方程： 最优值函数： 自有终端条件： （4）具体应用实例：详见例6、例7。 二、目标规划 1．实际问题中，衡量方案优劣要考虑多个目标，有主要的，有主要的，也有次要的；有最大值的，也有最小值的；有定量的，也有定性的；有相互补充的，也有相互对立的，这时可用目标规划解决。其求解思路有加权系数法、优先等级法、有效解法等。 2．基本概念： （1）正负偏差变量： （2）绝对（刚性）约束和目标约束 ，次位赋（3）优先因子（优先等级）与权系数：凡要求第一位达到的目标赋予优先因子P 1……以此类推。 予P 2 （4）目标规划的目标函数： （5）一般数学模型：
工厂资源规划问题 冉光明 2010070102019 信息与计算科学 指导老师：赵姣珍
目录 摘要 (1) 关键词 (1) 问题的提出 (2) 问题重述与分析 (3) 符号说明 (4) 模型假设 (4) 模型建立与求解 (5) 模型检验 (9) 模型推广 (10) 参考文献 (11) 附录 (12)
摘要：本问题是个优化问题。问题首先选择合适的决策变量即各种产品数，然后通过决策变量来表达约束条件和目标函数，再利用matlab或lingo编写程序，求得最优产品品种计划；最后通过优化模型对问题作以解释，得出当技术服务消耗33小时、劳动力消耗67小时、不消耗行政管理时，得到的是最优品种规划。 问题一回答：当技术服务消耗33小时、劳动力消耗67小时、不消耗行政管理时， 时，若使产品品产品III不值得生产。用matlab运算分析，当产品III的利润增加至25 3 种计划最优，此时需要消耗技术服务29h，劳动力消耗46h，行政管理消耗25h。 问题二回答：利用lingo得到当技术服务增加1h时，利润增加2.5元;劳动力增加1h，利润增加1元；行政管理的增减不会影响利润。 问题三回答：增加的决策变量，调整目标函数。当技术服务消耗33h，劳动力消耗17h，不消耗行政管理，新增量50h时，管理部门采取这样的决策得到最优的产品品种规划。 问题四回答：增加新的约束条件，此时当技术服务消耗32h，劳动力消耗58h，行政管理消耗10h时，得到最优产品品种规划。 本文对模型的求解给出在线性约束条件下的获利最多的产品品种规划。 关键词：线性规划；优化模型；最优品种规划
问题的提出 某工厂制造三种产品，生产这三种产品需要三种资源：技术服务、劳动力和行政管理。下表列出了三种单位产品对每种资源的需要量： 资源利润 技术服务劳动力行政管理 产品I 1 10 2 10 II 1 4 2 6 III 1 5 6 4 现有100h的技术服务、600h劳动力和300h的行政管理时间可使用，求最优产品品种规划。且回答下列问题： ⑴若产品III值得生产的话，它的利润是多少？假使将产品III的利润增加至25/3元，求获利最多的产品品种规划。 ⑵确定全部资源的影子价格。 ⑶制造部门提出建议，要生产一种新产品，该种产品需要技术服务1h、劳动力4h 和行政管理4h。销售部门预测这种产品售出时有8元的单位利润。管理部门应有怎样的决策？ ⑷假定该工厂至少生产10件产品III，试确定最优产品品种规划。
MATLAB 中文论坛讲义 多目标规划优化问题 Matlab 中常用于求解多目标达到问题的函数为fgoalattain.假设多目标函数问题的数学模型为： ub x lb beq x Aeq b x A x ceq x c goal weight x F t s y x ≤≤=≤=≤≤-**0 )(0 )(*)(..min ,γγ weight 为权值系数向量，用于控制对应的目标函数与用户定义的目标函数值的接近程度； goal 为用户设计的与目标函数相应的目标函数值向量； γ为一个松弛因子标量； F(x)为多目标规划中的目标函数向量。 综上，fgoalattain 的优化过程就是使得F 逼近goal; 工程应用中fgoalattain 函数调用格式如下： [x,fval]=fgoalattain (fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) x0表示初值； fun 表示要优化的目标函数； goal 表示函数fun 要逼近的目标值，是一个向量，它的维数大小等于目标函数fun 返回向量F 的维数大小； weight 表示给定的权值向量，用于控制目标逼近过程的步长； 例1. 程序（利用fgoalattain 函数求解） 23222 12 3222132min )3()2()1(min x x x x x x ++-+-+- 0,,6 ..321321≥=++x x x x x x t s ①建立M 文件. function f=myfun(x) f(1)= x(1)-1)^2+(x(2)-2)^2+(x(3)-3)^2; f(2)= x(1)^2+2*x(2)^2+3*x(3)^2; ②在命令窗口中输入. goal=[1,1]; weight=[1,1];
§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
优化与决策 ——多目标线性规划的若干解法及MATLAB 实现 摘要：求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划，本文介绍 了理想点法、线性加权和法、最大最小法、目标规划法，然后给出多目标线性规划的模糊数学解法，最后举例进行说明，并用Matlab 软件加以实现。 关键词：多目标线性规划 Matlab 模糊数学。 注：本文仅供参考，如有疑问，还望指正。 一．引言 多目标线性规划是多目标最优化理论的重要组成部分，由于多个目标之间的矛盾性和不可公度性,要求使所有目标均达到最优解是不可能的,因此多目标规划问题往往只是求其有效解(非劣解)。目前求解多目标线性规划问题有效解的方法,有理想点法、线性加权和法、最大最小法、目标规划法。本文也给出多目标线性规划的模糊数学解法。 二．多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函数,其数学模型表示为： 11111221221122221122max n n n n r r r rn n z c x c x c x z c x c x c x z c x c x c x =+++??=+++?? ??=+++? （1） 约束条件为： 1111221121122222112212,,,0 n n n n m m mn n m n a x a x a x b a x a x a x b a x a x a x b x x x +++≤??+++≤?? ??+++≤?≥?? （2） 若（1）式中只有一个1122i i i in n z c x c x c x =+++ ，则该问题为典型的单目标线性规划。我们记:()ij m n A a ?=,()ij r n C c ?=,12(,,,)T m b b b b = ,12(,,,)T n x x x x = ，
四类基本模型 1 优化模型 1.1 数学规划模型 线性规划、整数线性规划、非线性规划、多目标规划、动态规划。 1.2 微分方程组模型 阻滞增长模型、SARS 传播模型。 1.3 图论与网络优化问题 最短路径问题、网络最大流问题、最小费用最大流问题、最小生成树问题(MST)、旅行商问题(TSP)、图的着色问题。 1.4 概率模型 决策模型、随机存储模型、随机人口模型、报童问题、Markov 链模型。 1.5 组合优化经典问题 ● 多维背包问题(MKP) 背包问题：n 个物品，对物品i ，体积为i w ，背包容量为W 。如何将尽可能多的物品装入背包。 多维背包问题：n 个物品，对物品i ，价值为i p ，体积为i w ，背包容量为W 。如何选取物品装入背包，是背包中物品的总价值最大。 多维背包问题在实际中的应用有：资源分配、货物装载和存储分配等问题。该问题属于NP 难问题。 ● 二维指派问题(QAP) 工作指派问题：n 个工作可以由n 个工人分别完成。工人i 完成工作j 的时间为ij d 。如何安排使总工作时间最小。 二维指派问题（常以机器布局问题为例）：n 台机器要布置在n 个地方，机器i 与k 之间的物流量为ik f ，位置j 与l 之间的距离为jl d ，如何布置使费用最小。 二维指派问题在实际中的应用有：校园建筑物的布局、医院科室的安排、成组技术中加工中心的组成问题等。 ● 旅行商问题(TSP) 旅行商问题：有n 个城市，城市i 与j 之间的距离为ij d ，找一条经过n 个城市的巡回（每个城市经过且只经过一次，最后回到出发点），使得总路程最小。 ● 车辆路径问题(VRP) 车辆路径问题（也称车辆计划）：已知n 个客户的位置坐标和货物需求，在
多目标规划训练例题 某音像商店有5名全职熟练货员和4名兼职售货员，全职售货员每月工作160h,兼职售货员每月工作80h ，根据过去的工作纪录，全职售货员每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5元，兼职售货员每小时销售CD10张，平均工资每小时10元，加班工资每小时10元，现在预测下个月CD 销售量为27500张，商店每周开门营业6天，所以可能要加班，每出售一张CD 盈利1.5元， 商店经理认为，保持稳定的就业水平加上必要的加班，比不加班但就业水平不稳定要好，但全职售货员如果加班过多，就会因为疲劳过度而造成效益下降，因此，不允许每月加班超过100h,建立相应的目标规划模型，并应用Lingo 软件求解。 解：首先建立目标约束的优先级 1P ：下月的CD 销售量达到27500张 2P ：限制全职售货员加班时间不超过100h 3P ：保持全体售货员充分就业，因为充分工作是良好劳资关系的重要因素，但对全职售货 员要比兼职售货员加倍优先考虑 4P ：尽量减少加班时间，但对两种售货员区别对待，优先权因子由他们对利润的贡献而定。 第二，建立目标约束 （1）销售目标约束，设 1x ：全体售货员下月的工作时间； 2x ：全体兼职售货员下月的工作时间； - 1d ：达不到销售目标的偏差； +1d ：超过销售目标的偏差； 希望下月的销售超过27500张CD 片，因此销售目标为 ???=-+++ -- 27500 1025} min{11211d d x x d （2）正常工作时间约束，设 - 2d ：全体全职售货员下月的停工时间； + 2d ：全体全职售货员下月的加班时间； - 3d ：全体兼职售货员下月的停工时间； +3d ：全体兼职售货员下月的加班时间；
27. 多目标规划 一、线性规划的局限性 1. 线性规划要求所求解问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足； 2. 线性规划只能处理单目标的优化问题，从而对一些次目标只能转化为约束处理，而实际问题中，目标和约束是可以相互转化的，处理时不一定要严格区分； 3. 线性规划在处理问题时，将各个约束（也可看成目标）的地位看成同等重要，实际问题中，各个目标的重要性有层次上的差别，在同一层次也可能有不同权重； 4. 线性规划寻找最优解，而许多实际问题只要找到满意解就可以了。 例1 (线性规划——生产安排问题) 某企业生产甲、乙两种产品，需要用到A,B,C三种设备，每天产品盈利与设备使用工时及限制如下表： 问：该企业应如何安排生产，能使总利润最大？
解：设甲乙产品的产量分别为x 1, x 2，建立线性规划模型： 12 121212max 200300 s. t. 2212 416 515 ,0z x x x x x x x x =++≤≤≤≥ 用Lingo 可求得最优解：x 1=3, x 2=3, z *=1500. 但实际上，企业的经营目标不仅仅是利润，还需要考虑多个方面，比如：增加下列因素（目标） （1） 力求使利润不低于1500元； （2） 考虑市场需求，甲乙两种产品的产量比应尽量保持1:2； （3） 设备A 位贵重设备，严格禁止超时使用； （4）设备C 可以适当加班，但要控制，设备B 既要求充分利用，又尽可能不加班，在重要性上，设备B 是设备C 的3倍。 这就需要用目标规划。 二、目标规划的基本概念 1. 设置偏差变量 偏差变量——表示实际值与目标值之间的差异； d +——表示超出目标的差值，称为正偏差变量；当实际值超过目标值时，有d - = 0，d +> 0; d -——表示未达到目标的差值，称为负偏差变量；当实际值未达到目标值时，有d + = 0，d ->0. 注：若实际值与目标值一致，有d - = d += 0.