《运筹学》课件 第5、6章 整数规划、目标规划

第五章整数规划线性规划的扩展整数规划IntegerProgrammingIP模糊线性规划fuzzylinearprogramming非线性规划NonlinearProgrammingNP组合优化Combinatorialoptimization图论参数规划多目标规划随机过程stochasticprogramming线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。要求全部或部分决策变量的取值为整数的线性规划问题，称为整数线性规划，简称整数规划(IntegerProgramming)。全部决策变量的取值都为整数，则称为全整数规划(AllIP)；仅要求部分决策变量的取值为整数，则称为混合整数规划(MixedIP)；要求决策变量只能取0或1值，则称为0-1规划(0-1Programming)。第5章内容提要5.1整数规划问题5.2分支定界法5.3指派问题5.40-1规划建模应用5.1整数规划问题为了满足整数要求，似乎可以把线性规划的小数最优解进行“舍入化整”以得到与最优解相近的整数解。“舍入化整”一般是不可行的：化整后的解有可能成为非可行解；虽是可行解，却不是最优解。例如一、问题的提出

产品资源甲乙现有量A219B5735单台利润65

问如何安排甲、乙两产品的产量，使利润为最大。解：设x1为甲产品的台数，x2为乙产品的台数。maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整数不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题。不考虑整数约束的最优解：x1*=28/9，x2*=25/9，Z*=293/9舍入化整x1=3，x2=3，Z=33，不满足约束条件5x1+7x2≤35，非可行解；x1=3，x2=2，Z=28，满足约束条件，是可行解，但不是最优解；x1=4，x2=1，Z=29，满足约束条件，才是最优解。步骤：在线性规划的可行域内列出所有决策变量可能取的整数值，求出这些变量所有可行的整数解，比较它们相应的目标函数值，最优的目标函数值所对应的解就是整数规划的最优解。实用性：只有两个决策变量，可行的整数解较少。

5x1+7x2=352x1+x2=9•(3,3)••••••••••二、整数规划的图解法

x1x21231253445.2分枝定界法分枝定界法(BranchandBoundMethod)基本思想：先求出整数规划相应的LP(即不考虑整数限制)的最优解，若求得的最优解符合整数要求，则是原LP的最优解；若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。然后，再在缩小的可行域中求解新构造的线性规划的最优解，这样通过求解一系列线性规划问题，最终得到原整数规划的最优解。定界的含义：整数规划是在相应的线性规划的基础上增加变量为整数的约束条件，整数规划的最优解不会优于相应线性规划的最优解。对极大化问题来说，相应线性规划的目标函数最优值是原整数规划函数值的上界；对极小化问题来说，相应线性规划的目标函数的最优值是原整数规划目标函数值的下界。例maxZ=

6x1+5x2

2x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整数第一步,不考虑变量的整数约束,求相应LP(问题1)的最优解：

x1=28/9，x2=25/9，Z1=293/9第二步,定界过程这个解不满足整数约束，这时目标函值Z1是整数规划的目标上界；因为x1=x2=0是整数规划问题的可行解，所以下界为0。第三步,分枝过程将不满足整数约束的变量x1进行分枝，x1称为分枝变量，构造两个新的约束条件：

x1≤[28/9]=3，x1≥[28/9]+1=4这样就把相应的线性规划的可行域分成两个部分，如图所示。••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=3x1=4问题2：maxZ=

6x1+5x2问题3：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≥4x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数求解相应的线性规划的最优解问题2相应的线性规划的最优解：x1=3，x2=20/7，Z2=226/7问题3相应的线性规划的最优解：x1=4，x2=1，Z3=29第四步，定界过程LP3的解满足整数约束，不必再分枝，它的目标函数值是29，大于原有下界0，则新的下界为29；现有上界为未分枝子问题中目标函数最大值，即为226/7。LP2的解仍不满足整数约束的要求，它的目标函数值226/7大于现有下界，则应继续分枝。第五步，分枝过程将不满足整数约束的变量x2进行分枝，构造两个新的约束条件：

x2≤[20/7]=2，x2≥[20/7]+1=3

••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3问题4：maxZ=

6x1+5x2问题5：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≤2x2≥3x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数x2=2

x2=3求解相应的线性规划的最优解问题4相应的线性规划的最优解：

x1=3，x2=2，Z4=28问题5相应的线性规划的最优解：x1=14/5，x2=3，Z5=159/5第六步，定界过程LP4的解满足整数约束，不必再分枝，它的目标函数值是28，小于原有下界29，则下界仍为29；现有上界为未分枝子问题中目标函数最大值，即为159/5。LP5的解仍不满足整数约束的要求，它的目标函数值159/5大于现有下界29，则应继续分枝。第七步，分枝过程将不满足整数约束的变量x1进行分枝，构造两个新的约束条件：

x1≤[14/5]=2，x1≥[14/5]+1=3

问题6：maxZ=

6x1+5x2问题7：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≥3x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数x2=2

x2=3••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x1=2求解相应的线性规划的最优解：问题6相应的线性规划的最优解：

x1=2，x2=25/7，Z6=209/7问题7相应的线性规划的最优解：无最优解第八步，定界过程LP7的无最优解，不必再分枝，下界仍为29；现有上界为未分枝子问题中目标函数最大值，即为209/7。LP6的解仍不满足整数约束的要求，它的目标函数值209/7大于现有下界29，则应继续分枝。第九步，分枝过程将不满足整数约束的变量x2进行分枝，构造两个新的约束条件：

x2≤3，x2≥4

问题8：maxZ=

6x1+5x2问题9：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≤2x2≤3x2≥4x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x2=3x1=2x2=2

x2=4求解相应的线性规划的最优解问题8相应的线性规划的最优解：

x1=2，x2=3，Z8=27问题9相应的线性规划的最优解：x1=7/5，x2=4，Z9=142/5第十步，定界过程LP8的最优解，满足整数约束，不必再分枝，下界仍为29；现有上界为未分枝子问题中目标函数最大值，即为29。虽然LP9的解仍不满足整数约束的要求，它的目标函数值142/5小于现有下界29，则不再继续分枝。上界=下界，得整数规划问题的最优解：x1=4，x2=1，Z=29分枝定界过程x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3x2≤3x2≥4割平面法（P109)..X1X2一、指派问题及其标准形式指派问题的标准形式（以人和事为例）：设有个人和件事已知第人做第事的费用为，要求一个人和事之间一一对应的指派方案，使完成这件事的总费用最少。一般称矩阵

为指派问题的系数矩阵（coefficientmatrix）。5.3指派问题为了建立标准指派问题的数学模型，引入个0-1变量

问题的数学模型可写成

二、0－1整数规划应用－－指派问题英日德俄

甲乙丙丁2151341041415914161378119注意到：1从人来看，如果乙不作日语，损失特别大62从事来看，如果英语不分配给甲，损失特别大5英日德俄

甲乙丙丁21513410414159141613781190－1整数规划应用－－指派问题原理：从人的角度思考……..考虑人最适合的工作从工作的角度思考…….考虑工作最适合的人英日德俄

甲乙丙丁

2151341041415914161378119各行都减去这一行的最小值，得到的0表示这个0所在的行对应的人最适合的工作是这个0所在的列对应的事这一列有三个0，表示这一列的事有三个人适合作行最小值英日德俄

甲乙丙丁

01311260101105740142指派问题第一步:{各行元素}—{该行行最小}{各列元素}—{该列列最小}

本题有n个独立的0元素则已得最优解

各列都减去这一列的最小值，得到的0表示这个0所在的列行对应的事最适合的人是这个0所在的行对应的人甲俄乙日丙英丁德英日德俄

甲乙丙丁

0131126010110574014

2英日德俄

甲乙丙丁

0137

060690532010

0列最小值有三个人适合英文为什么确定丙英指派问题的匈牙利法：第一步:{各行元素}—{该行行最小}，{各列元素}—{该列列最小}

若有n个独立的0元素则已得最优解，本题有n个独立的0元素减去行列最小后矩阵英日德俄甲01370第4步行仅1零乙60第2步列仅1零69丙0第1步行仅1零532丁010第3步列仅1零0列仅一个零表示这个工作只适合一个人行仅一个零表示这个人只适合一个工作甲俄乙日丙英丁德颜色表示“确定”三、指派问题的匈牙利法第一步:{各行元素}—{该行行最小}，{各列元素}—{该列列最小}

若有n个独立的0元素则已得最优解，否则转第二步第二步:1，从只有一个0元素的行（列）开始，把0元素记为

，表示“确定”，然后划去所在行（列）的其他0元素，记为0表示“不考虑”

2.划去行（列）的新矩阵再回到:1

3.若仍有没划圈的0元素，且同行（列）至少有两个0元素，则从0元素最少的行（列）开始，试探若

“确定”的数目m等于矩阵的阶n，则最优解得到第三步1对没有

的行打（对应的人没找到合适的工作）

2对已打的行中的所含0的列打（没找到工作的人最适合的工作）

3

对打的列中的所含0的行打（没有工作的人所适合的工作分给谁了），重复2

3

对没有打的行划线（所有找到合适工作的人）对打的列划线（没找到合适工作的人最适合的工）如直线数<任务数，转第四步,如直线数=任务数,

的数<任务数，回到第三步第四步:没有被直线覆盖的行找“最小元素”打的各行—{最小元素},打的列+{最小元素}得到的新矩阵有更多的0元素，若得到n个独立元素则求的最优解，否则回到第三步克尼格定理

:

如果从分配问题效率矩阵(cij)的每一行元素中分别减去(或加上)一个常数ui，从每一列中分别减去(或加上)一个常数vj，得到一个新的效率矩阵(bij)，其中bij=aij-ui-vj,则以(bij)为效率矩阵的分配问题与以(cij)为效率矩阵的分配问题具有相同的最优解。

任务人员ABCD甲67112乙4598丙31104丁5982例:华东交通大学工业工程与物流管理系

运筹学第一步，变换系数矩阵：－5第二步，试指派：◎◎◎ØØ

找到3个独立零元素但m=3<n=

4

第三步，作最少的直线覆盖所有0元素：

◎◎◎ØØ√√√独立零元素的个数m等于最少直线数l，即l＝m=3<n=4；

第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派：000000得到4个独立零元素，所以最优解矩阵为：

◎◎◎ØØ√√√◎◎◎ØØ◎◎◎ØØ◎练习：115764戊69637丁96458丙9117129乙118957甲EDCBA费工作用人员-1-2◎Ø◎◎◎ØØ◎Ø◎◎◎ØØ√√√l=m=4<n=5◎Ø◎◎◎ØØ◎Ø◎Ø◎Ø◎Ø√√√√√√√◎Ø◎Ø◎Ø◎Ø√√√√√√√l=m=4<n=5◎Ø◎Ø◎Ø◎Ø√√√√√√√◎ØØ◎ØØ◎Ø◎Ø◎此问题有多个最优解28◎ØØ◎ØØ◎Ø◎Ø◎◎ØØ◎ØØ◎Ø◎Ø◎打破僵局时选择不当的结果：结果仅出现3个标记()，但却划出4条线，说明什么？！

四、不平衡的指派问题当人数m大于工作数n时，加上m－n项工作，例如当人数m小于工作数n时，加上n－m个人，例如求最大值的指派问题匈牙利法的条件是：模型求最小值、效率cij≥0令则与的最优解相同。设C对应的模型是求最大值将其变换为求最小值。例某人事部门拟招聘4人任职4项工作，对他们综合考评的得分如下表（满分100分），如何安排工作使总分最多。解M＝95，令用匈牙利法求解：最优解：一个人可做几件事的指派问题若某人可做几件事，则将该人化作相同的几个“人”来接受指派，且费用系数取值相同。例如：丙可以同时任职A和C工作，求最优指派方案。某事一定不能由某人做的指派问题将该人做此事的效率系数取做足够大的数，可用M表示。例分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务。每个人完成各项任务的时间如表所示。由于任务数多于人数，考虑任务E必须完成，其他4项中可任选3项完成。试确定最优分配方案，使完成任务的总时间最少。

任务人员ABCDE甲2529314237乙3938262033丙3427284032丁2442362345解:1)这是不平衡的指派问题，首先转换为标准型，再用匈牙利法求解。2)由于任务数多于人数，所以假定一名虚拟人，设为戊。因为工作E必须完成，故设戊完成E的时间为M（M为非常大的数），其余效率系数为0，则标准型的效率矩阵表示为：

任务人员ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊0000M用匈牙利法求出最优指派方案为：即甲－B，乙－D，丙－E，丁－A,任务C放弃。最少时间为105。例

混合泳接力队队员的选拔问题

赵钱张王周仰泳37.732.938.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1解：这是一个最小化指派问题，人数与事数不等。每行/列减去最小数字添加虚拟事情，利用匈牙利算法求解独立零元素个数等于矩阵维数，得到最优解分配矩阵仰泳——周蛙泳——王蝶泳——钱自由泳——赵例：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由3家建筑公司分别承建。已知第Ai(i=1,2,3)个建筑公司对第Bj(j=1,2,3,4,5)家新商店的建造费用的报价如下表，为保证工程进度，每家建筑公司最多只能承建两个商店，且由于某种原因，第B3家商店不能由第A1个建筑公司承办，求使总费用最少的指派方案商店建筑公司报价B1B2B3B4B5A1A2A3487151279171410691287B1B2B3B4B5A11A12A21A22A31A32每家公司最多可承建两家商店：人数≠工作数：B1B2B3B4B5B6A11A12A21A22A31A32B3不能由A1承办：MM√√√√√√√√√√√B1B2B3B4B5B6A11A12A21A22A31A32由A1承建B1、B2指派方案：，由A2承建B5由A3承建B3、B4总费用=42作业：6个人应聘4份工作，由于个人的技术专长不同，他们承担各项工作所获得的收益如下表，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总收益最大的指派方案。工作人收益1234123456354567688981010109111211101213121113分派方案：第3个人第2项工作第4个人第3项工作第5个人第1项工作第6个人第4项工作第1、2个人没工作1、引入0-1变量的实际问题①相互排斥的计划②相互排斥的约束条件③关于固定费用的问题5.40-1规划建模应用①相互排斥的计划

解：设决策变量为建立0－1规划模型如下：在东区，在A1，A2，A3三个点中至多选两个；2)在西区，A4，A5两个点中至少选一个；3)在南区，A6，A7两个点为互斥点;

4)选A2点必选A5点。②相互排斥的约束条件③关于固定费用的问题

在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决.例某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。所以必须全面考虑。第六章目标规划线性规划的局限性只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题。实际决策中，衡量方案优劣考虑多个目标生产计划决策中，通常要考虑产值、利润、满足市场需求、降低消耗、提高质量、提高劳动生产率等；生产布局决策中，除了要考虑运输费用、投资、原料供应、产品需求量等经济指标外，还要考虑到污染和其它社会因素等。这些目标中，有主要的，也有次要的；有最大的，也有最小的；有定量的，也有定性的；有互相补充的，也有互相对立的，LP则无能为力。目标规划（GoalProgramming）在LP的基础上发展起来的解决多目标规划问题的最有效的方法之一。美国经济学家查恩斯(A.Charnes)和库柏(W.W.Cooper)在1961年出版的《管理模型及线性规划的工业应用》一书中，首先提出的。

处理多种目标的关系，求得更切合实际要求的解只能处理一个目标目标规划线性规划可以在相互矛盾的约束条件下找到满意解满足所有约束条件的可行解找到的最优解是指尽可能地达到或接近一个或若干个已给定的指标值约束条件同等重要可根据实际需要给予轻重缓急或主次之分的考虑第6章内容提要6.1多目标线性规划6.2目标规划的数学模型6.3线形规划的解法6.4目标规划的应用6.1多目标线性规划

多目标线性规划含有多个优化目标的线性规划。线性规划模型只能有一个目标函数，可称为单目标线性规划。多目标线性规划模型具有两个或两个以上的目标函数。例1某工厂计划生产甲、乙两种产品，现有的设备资源、每种产品的技术消耗定额及单位产品的利润如表所示。试确定计划期内的生产计划，使获得的利润最大。

一、问题的提出产品资源甲乙现有资源

设备4324单位产品利润

54解：设x1、x2分别表示甲、乙两种产品的产量，则可建立线规划模型如下：

maxZ=5x1+4x2

4x1+3x2≤24x1，x2≥0假设：该工厂根据市场需求或合同规定，希望尽量扩大甲产品的生产；减少乙产品的产量。这时又增加了二个目标，则可建立如下的模型：

maxZ1=5x1+4x2

maxZ2=x1minZ3=x24x1+3x2≤24x1，x2≥0

这些目标之间相互矛盾，一般的线性规划方法不能求解

加权系数法为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确定合理的权系数，以反映不同目标之间的重要程度。

优先等级法将各目标按其重要程度分成不同的优先等级，转化为单目标模型。

有效解法寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。二、求解思路加权系数法和优先等级法的结合对每个目标函数确定一个希望达到的期望值(目标值或理想值)；由于各种条件的限制，这些目标值往往不可能全部都达到；对每一个目标函数引入正的或负的偏差变量，分别表示超过或未达到目标值的情况；为区别各目标的重要程度，引入目标的优先等级和加权系数；对所有的目标函数建立约束方程，并入原来的约束条件中，组成新的约束条件；从这组新的约束条件，寻找使组合偏差最小的方案。三、目标规划法

例2某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。在未来的一计划期内，可利用总工时为2000，原材料2500公斤（每件产品耗原料2公斤），产品需求量为800件。要求制订一生产计划，使其尽可能达到以下三项指标：（1）满足需要量；（2）质量水平达到98%；（3）7000元的工时成本。正常生产加班生产转包合同临时工所需工时/件222.53成本费用元/工时101588质量水平99%98%95%90%生产条件约束:

欲达到的目标：

总工时限制：2000个；原材料限制：2500kg。满足需求800件；达到质量水平合格率98%；工时成本7000元。1）分析例2某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。在未来的一计划期内，可利用总工时为2000，原材料2500公斤（每件产品耗原料2公斤），产品需求量为800件。要求制订一生产计划，使其尽可能达到以下三项指标：（1）满足需要量；（2）质量水平达到98%；（3）7000元的工时成本。2）组建约束确定决策变量：假设正常生产、加班生产、转包合同和雇临时工生产的量分别为x1，x2，x3和x4。确定约束：工时限制：2x1+2x2+2.5x3+3x4≤2000；原材料限制：2（x1+x2+x3+x4

）≤2500；非负限制：xi≥0（i=1，2，3，4）正常生产加班生产转包合同临时工所需工时/件222.53成本费用元/工时101588质量水平99%98%95%90%需要达到的目标：（1）满足需求量800件；（2）产品质量水平98%；（3）工时成本7000元。3）分析目标需求

三个目标要求，如何得到集中体现？是否需要建立三个目标函数？传统线性规划一般只建立一个目标函数，而有多个约束。→是否可以将三个目标以约束的形式表现出来，这样可解决多目标的问题？3）目标需求分析与目标向约束的转化需要达到的目标：→实际也变成了约束情况（1）满足需求量800件：在实际生产中，可能会出现两种情况，生产量不够800件或超过800件，则会产生不同的情况：0.98（x1+x2+x3+x4

）≤800；或0.98（x1+x2+x3+x4

）≥800；（2）产品质量水平98%：出现两种可能99%x1+98%x2+95%x3+90%x4≤98%（x1+x2+x3+x4

）；或

99%x1+98%x2+95%x3+90%x4

≥98%（x1+x2+x3+x4

）；

（3）工时成本7000元：可能出现两种可能：20x1+30x2+20x3+24x4≤7000；或20x1+30x2+20x3+24x4

≥7000。（1）满足需求量800件：两种情况不可能同时出现，化为标准型约束。0.98（x1+x2+x3+x4

）≤800；→0.98（x1+x2+x3+x4

）+S1=8000.98（x1+x2+x3+x4

）≥800；→0.98（x1+x2+x3+x4

）-S2=800（松弛变量S1和剩余变量S2中只可能出现一个）（2）产品质量水平98%：99%x1+98%x2+95%x3+90%x4≤98%（x1+x2+x3+x4）；→99%x1+98%x2+95%x3+90%x4+S3=98%（x1+x2+x3+x4）

99%x1+98%x2+95%x3+90%x4≥98%（x1+x2+x3+x4）；→99%x1+98%x2+95%x3+90%x4–S4=98%（x1+x2+x3+x4）（S3和S4中只可能出现一个）（3）工时成本7000元：20x1+30x2+20x3+24x4≤7000；→20x1+30x2+20x3+24x4+S5=700020x1+30x2+20x3+24x4≥7000。→20x1+30x2+20x3+24x4–S6=7000（S5和S6中只可能出现一个）如何综合考虑目标要求中可能会出现的两种情况？√√√√√√（1）满足需求量800件：归一化处理0.98（x1+x2+x3+x4

）+S1-S2=800（S1和S2中只可能出现一个，即其中至少有一个为零）（2）产品质量水平98%：99%x1+98%x2+95%x3+90%x4+S3–S4=98%（x1+x2+x3+x4

）（S3和S4中只可能出现一个，至少有一个为零）（3）工时成本7000元：

20x1+30x2+20x3+24x4+S5–S6=7000（S5和S6中只可能出现一个，至少有一个为零）如何综合考虑目标要求中可能会出现的两种情况？这里就在目标中引入了偏差量的概念，使多个目标要求转变成了约束→目标约束。S奇松弛变量，称为负偏差量（≥0）S偶剩余变量，称为正偏差量（≥0）目标要求转换成约束后的情形（1）满足需求量800件：归一化处理（2）产品质量水平98%（3）工时成本7000元

0.98（x1+x2+x3+x4

）+S1-S2=80099%x1+98%x2+95%x3+90%x4+S3–S4=98%（x1+x2+x3+x4

）

20x1+30x2+20x3+24x4+S5–S6=70000.98（x1+x2+x3+x4

）+d1-

-

d1+=8001%x1-3%x3-8%x4+d2-–d2+=020x1+30x2+20x3+24x4+d3-–d3+=7000di-，负偏差量di+，正偏差量目标约束4）相关概念引入

d+：正偏差量，可能实现值高于目标指标值的部分；

d-：负偏差量，可能实现值低于目标指标值的部分。实现目标的三种情况：（1）超过目标值

ｄk＋

>0，ｄk--＝0（2）达不到目标值ｄk＋

=0，ｄk-->0（3）刚好达到目标值

ｄk＋

=0，ｄk--＝0(d+*d—＝0)①

正、负偏差变量②

目标规划的约束形式

（1）绝对约束：也叫客观条件约束，为必须严格满足的约束。（2）目标约束：目标规划特有的约束，也叫软约束。（3）非负约束：要求所有决策变量和偏差量均≥0。如例2中的目标约束为：(1)满足需求800件；(2)达到质量水平合格率98%；(3)工时成本7000元；

(4)绝对约束

（5）非负约束:5）如何确定最终的目标方程？

设想：希望能尽量同时满足三个目标需求，即刚好达到800件产量，质量合格率刚好为98%，工时成本刚好为7000元。此时，所有的正偏差和负偏差量应均为0。但是，实际情况下，正偏差或负偏差量很难同时为0，即实际中不可能刚好同时达到目标要求。但是，应该尽力靠近目标要求，则需实际可能值应尽可能与目标要求值靠近，即使得所有目标约束的偏差量最小。由此，可建立新的目标函数：

原有目标变成了约束（目标约束），如何寻找新的目标方程？数学模型6.2目标规划的数学模型

目标函数的期望值每一个目标函数希望达到的期望值(或目标值、理想值)。根据历史资料、市场需求或上级部门的布置等来确定。偏差变量每个目标函数的期望值确定之后，目标的实际值和它的期望值之间就有正的或负的偏差。正偏差变量dk+表示第k个目标超过期望值的数值；负偏差变量dk-表示第k个目标未达到期望值的数值。同一目标，它的取值不可能在超过期望值的同时，又没有达到期望值，所以在dk+和dk-中至少有一个必须为零。一、目标规划的基本概念

目标约束引入正、负偏差变量后，对各个目标建立的目标函数方程。原来的目标函数变成了约束条件的一部分，即目标约束(软约束)原来的约束条件称为系统约束(硬约束)。例1中，管理部门提出新要求：第一个目标是实现利润最大，计划部门规定利润目标是20；第二个目标是充分利用设备台时，但尽量少加班；第三个目标做如下规定，甲产品产量希望不少于3单位，乙产品产量比甲产品多2单位。对各目标函数引入正、负偏差变量：

5x1+4x2+d1--d1+=204x1+3x2+d2--d2+=24x1

+d3--d3+=3-x1+x2+d4--d4+=2目标达成函数

各个目标函数引入正、负偏差变量，而被列入了目标约束条件。如何使各目标的实际值最接近于各自的期望值，构造一个新的目标函数以求得有关偏差变量的最小值。这个新的目标函数反映了各目标函数的期望值达到或实现的情况，故把这个新的目标函数称为目标达成函数。若要求尽可能达到规定的目标值，则正、负偏差变量dk+、dk-都尽可能最小，将dk+和dk-都列入目标函数中，即minSk=dk++dk-；若希望尽可能不低于期望值(允许超过)，则负偏差变量dk-尽可能的小，而不关心超出量dk+

，故只需将dk-列入目标函数，minSk=

dk-；若允许某个目标低于期望值，但希望不得超过期望值，则正偏差变量dk+

尽可能地小，而不关心低于量dk-，故只需将dk+列入目标函数，minSk=

dk+。优先等级和权数

目标的重要程度不同，用优先等级因子Pk来表示第k等级目标。优先等级因子Pk是正的常数，Pk>>Pk+1。同一优先等级下的目标的相对重要性，赋以不同的加权系数w。例如第一个目标是实现利润最大，其优先级为P1

；第二个目标是充分利用设备台时，但尽量少加班，其优先级为P2

；第三个目标：甲的产量不少于3，乙的产量比甲多2，优先级为P3

。假设：甲产品产量希望不少于3单位的权数为3，乙产品产量比甲产品多2单位的权数为5。

minZ=P1d1-+P2(d2-+d2+

)+P3(3d3-+5d4-

)5x1+4x2+d1--d1+=204x1+3x2+d2--d2+=24x1

+d3--d3+=3-x1+x2+d4--d4+=2x1,x2,dk-,dk+≥0二、目标规划的数学模型

例某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。该厂经营目标如下：（1）利润指标为每月16000元，争取超额完成；（2）充分利用现有生产能力；（3）可以适当加班，但加班时间不得超过24小时；（4）产量以预计销售量为准。试建立目标规划模型。

小结线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,

xs

xa

xi

xs

xa

d约束条件绝对约束目标约束、绝对约束解最优最满意6.3目标规划的解法

只含有两个决策变量的目标规划模型

线性规划是在可行域中寻找一点，使单个目标极大或极小；目标规划则是寻找一个区域，这个区域提供了相互矛盾的目标集的折衷方案。目标规划的图解法的思路首先是在可行域内寻找一个使P1级各目标均满足的区域R1；然后再在R1中寻找一个使P2级各目标均满足的区域R2(R2

R1)；接着再在R2中寻找一个满足P3级各目标的区域R3(R3

R2

R1)；如此继续，直到寻找到一个区域RK(RK

RK-1

…

R3

R2

R1)，满足PK级各目标，这时RK即为这个目标规划的最优解空间，其中的任一点均为这个目标规划的满意解。

一、目标规划的图解法

目标规划的图解法的步骤首先，按照绝对约束画出可行域，其次，不考虑正负偏差变量，画出目标约束的边界线，最后。按优先级别和权重依次分析各级目标。minZ=P1d1-+P2(d2-+d2+)+P3(3d3-+5d4-)5x1+4x2+d1--d1+=20①4x1+3x2+d2--d2+=24②x1

+d3--d3+=3③-x1+x2+d4--d4+=2④x1,x2,dk-,dk+≥0⑤x1x2①d1+d1-②d2+d2-③d3+d3-④d4-d4+DABC满意解：x1=3,x2=15/4

Minz=P1d1++P2(d2-+d2+)+P3d3-

subjectto 2x1+x2≤11(1)硬约束

x1-x2+d1--d1+=0(2)

x1+2x2+d2--d2+=10(3) 8x1+10x2+d3--d3+=56(4)

x1,x2,di--di+>=0,i=1,2,3(5)例:线性规划模型为024A6810可行域x2非可行域12

B10

86

4

2x1满意解线段数学模型归结为：Minz=P1d1++P2(d2-+d2+)+P3d3-

subjectto 2x1+x2≤11(1)硬约束

x1-x2+d1--d1+=0(2)

x1+2x2+d2--d2+=10(3) 8x1+10x2+d3--d3+=56(4)

x1,x2,di--di+>=0,i=1,2,3ECDGd1-d1+d2+d3+d3-d2-D(10/3,10/3)G(2,4)P2(d2-+d2+)

P1d1+P3d3-

102用图解法求解下列目标规划问题103(a)(b)(c)(d)x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+满意解(3,3)046834622目标规划与线性规划的数学模型的结构相似可用前述单纯形算法求解目标规划模型：将优先等级Pk视为正常数(大Ｍ法

)正负偏差变量dk+、dk-视为松弛变量以负偏差变量dk-为初始基变量，建立初始单纯形表检验数的计算与LP单纯形表检验数的计算完全相同，即

j=cj-CBiPj最优性判别准则类似于LP的单纯形算法：检验数一般是各优先等级因子的代数和判断检验数的正负和大小二、目标规划的单纯形法

minZ=P1d1-+P2(d2-+d2+)+P3(3d3-+5d4-)5x1+4x2+d1--d1+=204x1+3x2+d2--d2+=24x1

+d3--d3+=3-x1+x2+d4--d4+=2x1,x2,dk-,dk+≥0划为标准型

maxZ=-P1d1--P2(d2-+d2+)-P3(3d3-+5d4-)5x1+4x2+d1--d1+=204x1+3x2+d2--d2+=24x1

+d3--d3+=3-x1+x2+d4--d4+=2x1,x2,dk-,dk+≥0cj

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数

j00-P10-P2-P2-3P20-5P2020541-10000002443001-1000031000001-1002-110000001-1d1-d2-d3-d4--P1-P2-3P3-5P3+5P1+4P2-2P3+4P1+3P2+5P30-P10-2P20-3P30-5P3463-检验数

jd1-d2-x1d4--P1-P20-5P331000001-1005041-100-55001203001-1-440050100001-11-10+4P1+3P2+5P30-P10-2P2-5P1-4P2+2P3+5P1+4P2-5P30-5P313--cj00-P10-P2-P2-3P20-5P20

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数

jd3+d2-x1d4-0-P20-5P3104/51/5-1/500-110080-1/5-4/54/51-10000414/51/5-1/5000000609/51/5-1/500001-10-P1000-1/5P2-4/5P2+4/5P2-2P2+9P3+P3-P3-3P3-5P3-10--检验数

jd3+d1+x1d4-000-5P3100-1/4-115/4-5/40000303/4001/4-1/4-1100613/4001/4-1/40000807/4001/4-1/4001-10-P1000-P2-P235/4P3+5/4P3-5/4P3-3P3-5P34-832/7cj00-P10-P2-P2-3P20-5P20

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数

jx2d1+x1d4-000-5P3401001/3-1/3-4/34/3001100-114/3-4/3-1/31/3003100000-110010000-1/31/37/3-7/31-100-P100-P2-P2-5/3P3+5/3P326/3P3-35/3P3-5P3---3检验数

jx2d1+x1d3-000-3P33/70000-1/71/71-13/7-3/732/701001/7-1/7004/7-4/778/700-119/7-9/7001/7-1/718/710001/7-1/700-3/73/700-P1000-P2-P2-3/7P3+3/7P3-3P3-26/7P3-9/7P36.4目标规划的应用经营目标P1：总利润不低于40，P2：充分利用设备能力，且尽量不超过140如何安排生产？minZ=P1d1-+P2(d2-+