《《运筹学》教学案卷》由会员分享，可在线阅读，更多相关《《运筹学》教学案卷（30页珍藏版）》请在金锄头文库上搜索。
1、运筹学运筹学教学案卷教学案卷对象：交通运输、农业工程、环境工程对象：交通运输、农业工程、环境工程 时间：时间：2010/08-2011/01沈阳农业大学沈阳农业大学 工程学院工程学院赵赵 秀秀 荣荣7/23/2024Associate Prof Xiurong Zhao,Shenyang Agriculture University,China2008级级本本科科适适用用Operations Research第五章目标规划第五章目标规划（讲课（讲课3学时）学时）n5-1 目标规划数学模型目标规划数学模型n5-2 目标规划的图解法目标规划的图解法n5-3 解目标规划的单纯形法解目标规划的单纯形法
2、7/23/20242008级级本本科科适适用用Operations Research本章重点本章重点n n n n掌握目标规划的数学模型掌握目标规划的数学模型7/23/20242008级级本本科科适适用用Operations Research绪：绪：n 前面讨论的线性规划问题，都涉及一前面讨论的线性规划问题，都涉及一个目标函数，称单目标数学规划。个目标函数，称单目标数学规划。n在实际中，所遇到的问题，往往难以用一在实际中，所遇到的问题，往往难以用一个目标来衡量。个目标来衡量。n将具有两个或两个以上目标函数的规划问将具有两个或两个以上目标函数的规划问题叫做多目标规划。题叫做多目标规划。n 7/2
3、3/20242008级级本本科科适适用用Operations Research绪：绪：n 多目标问题在经济中、科学研究和工程设计多目标问题在经济中、科学研究和工程设计上经常遇到。上经常遇到。n例如，设计导弹，既要射程远，又要省燃料，还例如，设计导弹，既要射程远，又要省燃料，还必须要精度高；必须要精度高；n确定一个新橡胶配方，往往同时考察八、九个指确定一个新橡胶配方，往往同时考察八、九个指标，如强力、硬度、变形、伸长等；标，如强力、硬度、变形、伸长等；n再如选一个新厂址，除考虑运输费用、造价、燃再如选一个新厂址，除考虑运输费用、造价、燃料等费用外，还要考虑环境污染等社会因素。料等费用外，还要考虑
4、环境污染等社会因素。7/23/20242008级级本本科科适适用用Operations Research 5-1 目标规划数学模型目标规划数学模型 n 为了使同学们更好理解和掌握目标规划，为了使同学们更好理解和掌握目标规划，n下面通过例子来介绍其有关概念及数学模型。下面通过例子来介绍其有关概念及数学模型。n例例1：某工厂生产甲、乙两种产品，已知有关数：某工厂生产甲、乙两种产品，已知有关数据如表据如表5-1。试求该工厂获利最大的生产方案。试求该工厂获利最大的生产方案。7/23/20242008级级本本科科适适用用Operations Research5-1 目标规划数学模型目标规划数学模型 产品
5、品原料原料甲甲乙乙资源源拥有有量量原材料（原材料（kg）2111设备（hr）1210利利润（元（元/件）件）810根据根据LP问题所学知识，可列出其线性规划数学模型如下：问题所学知识，可列出其线性规划数学模型如下： 解解：可得最优解可得最优解：7/23/20242008级级本本科科适适用用Operations Research5-1 目标规划数学模型目标规划数学模型 如果实际上工厂在决策时，要考虑市场等一系列条件，如：如果实际上工厂在决策时，要考虑市场等一系列条件，如：n（1）根据市场信息，产品甲的销量有下降趋势，故考虑产）根据市场信息，产品甲的销量有下降趋势，故考虑产品甲的产量不大于产品乙；
6、品甲的产量不大于产品乙；n（2）超过计划供应的原材料时，需用高价采购，这就使成）超过计划供应的原材料时，需用高价采购，这就使成本增加；本增加；n（3）应尽可能充分利用设备台时，但不希望加班）应尽可能充分利用设备台时，但不希望加班n（4）应尽可能达到并超过计划利润指标）应尽可能达到并超过计划利润指标56元。元。n 在考虑上述问题决策时，便是多目标决策问题。在考虑上述问题决策时，便是多目标决策问题。n目标规划方法是解决这类决策问题的方法之一。目标规划方法是解决这类决策问题的方法之一。n 下面介绍有关概念：下面介绍有关概念：7/23/20242008级级本本科科适适用用Operations Rese
7、arch5-1 目标规划数学模型目标规划数学模型n（1）偏差变量偏差变量n设 为决策变量，此外引入正负偏差变量 。n 表示决策值超过目标的部分；n 表示决策值未达到目标值的部分。n因为决策值不可能既超过目标值，同时又未达到目标值，即 7/23/20242008级级本本科科适适用用Operations Research5-1 目标规划数学模型目标规划数学模型n（2）绝对约束绝对约束和目标约束目标约束n 绝对约束绝对约束是指必须严格满足的等式约束和不等式约束；n如线性规划问题的所有约束条件。不能满足这些约束条件的解称为非可行解，所以这些约束就是硬约束。n 目标约束目标约束是目标规划特有的，可以把约
8、束右端项看作要追求的目标值。在达到此目标值时发生正或负的偏差，因此在这些约束中加入正或负偏差变量，则这些约束是软约束。7/23/20242008级级本本科科适适用用Operations Research5-1 目标规划数学模型目标规划数学模型n（3）优先因子优先因子n 一个规划问题通常有多个目标，但决策者在一个规划问题通常有多个目标，但决策者在要达到这些目标时，有主次和轻重缓急之分；要达到这些目标时，有主次和轻重缓急之分；n凡要求第一位的目标赋予优先因子凡要求第一位的目标赋予优先因子 ；n第二位赋予优先因子第二位赋予优先因子 ；以此类推，；以此类推，n令 注意：优先因子不代表具体数，只代表目标
9、的注意：优先因子不代表具体数，只代表目标的优先次序优先次序。 7/23/20242008级级本本科科适适用用Operations Research5-1 目标规划数学模型目标规划数学模型n（4）目标规划的目标函数目标规划的目标函数n 目标规划的目标函数是按各目标约束的正负目标规划的目标函数是按各目标约束的正负偏差变量和赋予相应的优先因子而构成的。偏差变量和赋予相应的优先因子而构成的。n当每一目标值确定后，决策者的要求是尽可能缩当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是小偏离目标值。因此目标规划的目标函数只能是n n 其基本形式有三种：其基本形式有三种：
10、 7/23/20242008级级本本科科适适用用Operations Research5-1 目标规划数学模型目标规划数学模型n（1）要求恰好达到目标值，即正负偏差）要求恰好达到目标值，即正负偏差变量都要极可能的小。这时变量都要极可能的小。这时n（2）要求不超过目标值，即允许达不到）要求不超过目标值，即允许达不到目标值，正偏差的变量要尽可能小。这时目标值，正偏差的变量要尽可能小。这时 n（3）要求超过目标值，即超过量不限，）要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能的小。这时但必须是负偏差变量要尽可能的小。这时 7/23/20242008级级本本科科适适用用Operations
11、Research5-1 目标规划数学模型目标规划数学模型n 对于每一个目标规划问题，其对于每一个目标规划问题，其目标函数是根据决策者的要求和规目标函数是根据决策者的要求和规定的优先因子来构造的。定的优先因子来构造的。7/23/20242008级级本本科科适适用用Operations Research5-1 目标规划数学模型目标规划数学模型n例例2：例例1中中，决策者，决策者在原料供应受价格限在原料供应受价格限制基础上考虑：制基础上考虑：n首先首先是乙的是乙的产量不低产量不低于于产品甲的产量；产品甲的产量；n其次其次是充分利用设备是充分利用设备有效台时，有效台时，不加班不加班；n再次再次是利润额
12、不小于是利润额不小于56元，求元，求决策方案决策方案。G P那么该目标规划的目标函数是什么呢？那么该目标规划的目标函数是什么呢？要考虑的目标有三个，分别赋优先因子要考虑的目标有三个，分别赋优先因子：P1，P2，P3L P台时台时原材料原材料首先要确定该目标规划的约束条件首先要确定该目标规划的约束条件最先要考虑有无硬约束？请大家分析最先要考虑有无硬约束？请大家分析原材料约束即为硬约束，即原材料约束即为硬约束，即考虑所有硬约束以后，开始考虑目标约束，按照目标先后，则有考虑所有硬约束以后，开始考虑目标约束，按照目标先后，则有按照第一个目标要求（现不考虑其下级目标）按照第一个目标要求（现不考虑其下级目
13、标）应该符合？应该符合？再按照第二个目标要求（不考虑其上、下级目标）再按照第二个目标要求（不考虑其上、下级目标）最后按照第三个目标要求（不考虑其上级目标）最后按照第三个目标要求（不考虑其上级目标）应该符合？应该符合？把三个应满足的目标合成一个目标函数即为该问题目标函数把三个应满足的目标合成一个目标函数即为该问题目标函数7/23/20242008级级本本科科适适用用Operations Research5-1 目标规划数学模型目标规划数学模型n解：解：按决策者所要求的，分别赋予这三个目标、优先因子，则其数学模型为： 7/23/20242008级级本本科科适适用用Operations Resear
14、ch5-1 目标规划数学模型目标规划数学模型n解：解：按决策者所要求的，分别赋予这三个目标、优先因子，则其数学模型为： 7/23/20242008级级本本科科适适用用Operations Research5-1 目标规划数学模型目标规划数学模型n目标规划的一般数学模型为：目标规划的一般数学模型为： 7/23/20242008级级本本科科适适用用Operations Research5-2 目标规划的图解法目标规划的图解法n 对只具有两个决策变量的目标规划的对只具有两个决策变量的目标规划的数学模型，可以用图解法来分析求解。数学模型，可以用图解法来分析求解。n首先在平面直角坐标系中作约束条件直线首
15、先在平面直角坐标系中作约束条件直线n注意不包含注意不包含n 作目标约束时，限令作目标约束时，限令n作相应的直线，然后在该直线旁，标上作相应的直线，然后在该直线旁，标上n 如下个幻灯图，这表明目标约如下个幻灯图，这表明目标约束可以沿二者所示的方向平移。束可以沿二者所示的方向平移。 7/23/20242008级级本本科科适适用用Operations Research5-2 目标规划的图解法目标规划的图解法BCDEFGO首先在平面直角坐标系中作约束条件直线，不含首先在平面直角坐标系中作约束条件直线，不含步骤如下：步骤如下：在所做直线旁，标上在所做直线旁，标上表明目标约束可以沿二者所示的方向平移表明目
16、标约束可以沿二者所示的方向平移分析分析d+，d-的方向？的方向？作目标约束时，限令作目标约束时，限令先考虑满足所有硬约束后，考虑满足第一目标，即先考虑满足所有硬约束后，考虑满足第一目标，即要使要使 d1+=0 （这时只能在（这时只能在OBC范围内取值）范围内取值）接着考虑第二优先因子目标的实现。在目标函数中接着考虑第二优先因子目标的实现。在目标函数中要求实现要求实现则只有在则只有在ED线段上的点才符合线段上的点才符合最后考虑具有第三优先因子的目标的实现，在目标函最后考虑具有第三优先因子的目标的实现，在目标函数中要求实现数中要求实现则把最优解定在了？则把最优解定在了？GD上上n可求得可求得G的坐
17、标值为（的坐标值为（2，4）、）、D（10/3，10/3），），G、D的凸线性组合都是该目标规划问题的解。的凸线性组合都是该目标规划问题的解。7/23/20242008级级本本科科适适用用Operations Research5-2 目标规划的图解法目标规划的图解法n 注意目标规划问题求解时，把绝对约束作为注意目标规划问题求解时，把绝对约束作为最高的优先级考虑。最高的优先级考虑。n在前例中能以先后次序都得到了满足，即n 因而因而n但在大多问题中并非如此，还可能出现非可行解，但在大多问题中并非如此，还可能出现非可行解，故将目标规划问题的最优解称为满意解。故将目标规划问题的最优解称为满意解。7/2
18、3/20242008级级本本科科适适用用Operations Research5-3 解目标规划的单纯形法解目标规划的单纯形法n目标规划的数学模型结构与线性规划数学模型结目标规划的数学模型结构与线性规划数学模型结构没有本质区别，所以可用单纯形法求解。构没有本质区别，所以可用单纯形法求解。n但要考虑目标规划的数学模型的一些特点作以下但要考虑目标规划的数学模型的一些特点作以下规定规定：n（1）因目标规划问题的目标函数都是求最小，）因目标规划问题的目标函数都是求最小，n所以所以 ，以，以 为最优判断的准则。为最优判断的准则。7/23/20242008级级本本科科适适用用Operations Rese
19、arch5-3 解目标规划的单纯形法解目标规划的单纯形法n（2）非基变量的检验数中含有不同级别的）非基变量的检验数中含有不同级别的优先因子，须按优先因子先后依次判断；优先因子，须按优先因子先后依次判断；n对下级进行判断迭代时，以不破坏上一级以对下级进行判断迭代时，以不破坏上一级以及其以前各级的达成值为标准。及其以前各级的达成值为标准。n解目标规划问题单纯形法的计算步骤：解目标规划问题单纯形法的计算步骤：n第一步：建立初始单纯形表，在表中将检验第一步：建立初始单纯形表，在表中将检验数行按照优先因子的个数分别排成数行按照优先因子的个数分别排成k行，含行，含k=1。7/23/20242008级级本本
20、科科适适用用Operations Research5-3 解目标规划的单纯形法解目标规划的单纯形法n第二步：检查第二步：检查k=1行中是否存在负数，且对应行中是否存在负数，且对应的前的前k-1行的系数是零。行的系数是零。n若有负数，取其中最小者对应的变量为换入变量若有负数，取其中最小者对应的变量为换入变量转第三步；若无负数，则转第五步。转第三步；若无负数，则转第五步。n第三步：按最小比值规定确定换出变量，第三步：按最小比值规定确定换出变量，n当存在两个或两个以上相同最小比值时，选取具当存在两个或两个以上相同最小比值时，选取具有有较高优先级别的变量较高优先级别的变量为换出变量。为换出变量。7/2
21、3/20242008级级本本科科适适用用Operations Research5-3 解目标规划的单纯形法解目标规划的单纯形法n第四步：按单纯形法进行迭代换算，建立第四步：按单纯形法进行迭代换算，建立新的计算表，返第二步。新的计算表，返第二步。n第五步第五步:当所有当所有k行都判断完毕后，表中的行都判断完毕后，表中的解即为满意解。解即为满意解。7/23/20242008级级本本科科适适用用Operations Research5-3 解目标规划的单纯形法解目标规划的单纯形法n例例3：试用单纯形法来求解例：试用单纯形法来求解例2： 7/23/20242008级级本本科科适适用用Operation
22、s Research5-3 解目标规划的单纯形法解目标规划的单纯形法因为所有检验数都大于或等于零，故已满足第一优先因为所有检验数都大于或等于零，故已满足第一优先指标，应往下进行，即判断第二优先指标指标，应往下进行，即判断第二优先指标将主元化为将主元化为1，主元所在列其它元素化为零。注意不包含下，主元所在列其它元素化为零。注意不包含下级指标，同时不破坏上级已达成指标。结果见下幻灯片。级指标，同时不破坏上级已达成指标。结果见下幻灯片。7/23/20242008级级本本科科适适用用Operations Research5-3 解目标规划的单纯形法解目标规划的单纯形法因为第一、第二行所有检验数都大于或
23、等于零，故均因为第一、第二行所有检验数都大于或等于零，故均已满足，应往下进行，即判断第三优先指标已满足，应往下进行，即判断第三优先指标如果选择该列，则会影响前面的二级指标，所以不选择该列。如果选择该列，则会影响前面的二级指标，所以不选择该列。试试看其它列，如第一列试试看其它列，如第一列“-3”，其前面两行检验数均为零，故，其前面两行检验数均为零，故不会影响上级指标达成值。不会影响上级指标达成值。将主元化为将主元化为1，主元所在列其它元素化为零。进行单纯，主元所在列其它元素化为零。进行单纯形迭代。结果见下个幻灯片。形迭代。结果见下个幻灯片。7/23/20242008级级本本科科适适用用Opera
24、tions Research5-3 解目标规划的单纯形法解目标规划的单纯形法因为所有检验数都大于或等于零，故三级指标均已满因为所有检验数都大于或等于零，故三级指标均已满足。取得了目标规划的满意解。足。取得了目标规划的满意解。该目标规划的满意解为该目标规划的满意解为x*=(2 2，4 4，3 3，2 2，0 0，0 0，0 0，0 0，0 0)T 如果我们以最后一列为关键列，第二行为关键行，会得到另一如果我们以最后一列为关键列，第二行为关键行，会得到另一个满意解见下个幻灯片个满意解见下个幻灯片 7/23/20242008级级本本科科适适用用Operations Research5-3 解目标规划的单纯形法解目标规划的单纯形法此解相当于图此解相当于图5-1的的G、D两点的凸线性组合，都是满意解。两点的凸线性组合，都是满意解。 7/23/2024
