系统工程第3章最优化技术

IntroductiontoSystemsEngineering

石英

武汉理工大学自动化学院E-mail:

a_laly@163.com系统工程概论教学内容第一章

绪论

（1学时）

第二章系统分析与系统建模（3学时）

第三章最优化技术（24学时）

第四章

系统优化（2学时）

第五章

决策分析（2学时）

系统工程概论第三章最优化技术§3-1最优化技术的基本概念

§3-2线性规划§3-3整数规划§3-4非线性规划§3-5动态规划§3-6图与网络

E-mail:a_laly@163.com

武汉理工大学自动化学院石英§3-1最优化技术的基本概念BasicConceptoftheOptimizationTechnology1.数学模型的建立

TheCreationoftheMathematicalModel2.最优化问题的分类

TheSortoftheOptimizationProblem3.最优化问题的解决方法

TheSolutionoftheOptimizationProblem系统工程概论分类建模解决方法E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念最优化技术是研究和解决最优化问题的一门科学，它研究和解决如何从一切可能的方案中寻找最优的方案。也就是说，最优化技术是研究和解决如何将最优化问题表示为数学模型以及如何根据数学模型尽快求出其最优解的两大问题。一般而言，用最优化方法解决实际工程问题可分为三步进行：

(1)

根据所提出的最优化问题，建立最优化问题的数学模型，确定变量，列出约束条件和目标函数(指标函数或性能指标);

(2)

对所建立的模型进行具体分析和研究，选择适当的最优化求解方法;

(3)

根据最优化方法的算法列出程序框图和编写语言程序，用计算机求出最优解，并对算法的收敛性、通用性、简便性、计算效率及误差等作出评价。

最优化方法是采用计算机进行寻优的方法。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念分类建模解决方法所谓最优化问题，就是寻找一个最优化控制方案或最优化控制规律，使所研究的对象(或系统)能最优地达到预期的目标。例如，在恒温的自动控制过程中，如果出现干扰而产生偏差，则用什么办法最快地消除偏差致使系统恢复原来的平衡状态?再如，在雷达高炮随动系统中，当发现敌机后，如何以最快的速度跟踪目标而将敌机击落?又如，在控制发射N级火箭时，如何规划各级火箭的质量致使火箭的总质量为最小?总之，最优化问题的中心课题，就是依据各种不同的研究对象以及人们预期要达到的目的，寻找出一个最优控制规律或设计出一个最优控制方案或最优控制系统。

系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念分类建模解决方法一、数学模型的建立

用最优化方法解决实际工程问题的第一步，就是要建立表达最优化问题的数学模型，其中包括了确定变量、列出约束条件和建立目标函数等三个主要内容。

例[3-1]人造卫星姿势控制问题

人造卫星姿势控制的示意图如3-1-1。图中，用A和B表示的两组斜对称配置的小喷嘴对成对工作，小喷嘴喷出燃料时产生的反作用力可以使卫星旋转并进入要求的姿态。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念分类建模解决方法系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念分类建模解决方法llAABBF/2F/2质心基准θ图3-1-1人造卫星姿态控制示意图t0时刻，卫星偏离要求的基准姿态θ(t0)角度，且正以角度继续偏离。从t0时刻起加上控制力u(t)，使卫星在最短时间里回复到所要求的姿态。以tf表示终端时刻，则要求有θ(tf)=0和且tf

－t0为最小。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念分类建模解决方法作用在卫星体上的力矩表达式为：2×F/2×l=Fl在力矩的作用下，卫星体产生的角速度为：Jm为卫星体绕质心的转动惯量。令控制力选择状态变量x1(t)=θ(t),，则有

系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念分类建模解决方法写成向量形式：系统初始状态为：系统终端状态为：系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念分类建模解决方法由于小喷嘴可以产生的最大反作用力是有限的，所以控制力u(t)有限，其绝对值不大于某个数值，即：式中，Um为某个正数。根据题意

J＝tf

－t0应为最小。目标函数约束条件(1)

要求在姿势控制过程中所消耗的燃料为最少，

J=∫tft0|u(t)|dt

(2)

要求在姿势控制过程中不但所消耗的燃料为最少，而且还要兼顾到所需要的时间为最短，

J=∫tft0[ρ+|u(t)|]dt

ρ为权系数，它的大小表示了燃料和时间的相对重要性。若要求动作快、时间短，则要加大ρ;若强调节省燃料，则要减小ρ。

人造卫星姿势控制的最优化问题，就是如何选择满足的容许控制，使所建立的目标函数取极小值。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念分类建模解决方法最优化问题的数学描述，应包括以下几方面的内容:

(1)

受控制动态系统的数学模型，即满足系统动力学特性的系统状态方程；

(2)

动态系统的初态和终态，即状态方程的边界条件；

(3)

目标函数(又称性能指标或性能函数或目标泛函等)，它是一个衡量“控制作用”效果的性能指标；

(4)

容许控制的集合。每一个实际的控制问题，控制向量u(t)都有一个规定的取值范围。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念分类建模解决方法二、最优化问题的分类

(1)

无约束与有约束最优化问题

如果控制变量的取值范围不受限制，则为无约束的最优化问题，求无约束函数的极值时，问题的最优解即为目标函数的极值。约束条件可分为等式约束条件和不等式约束条件。等式约束条件上各点称为可行解，等式约束曲线表示可行解域。满足不等式约束条件的区域范围称为解的可行域，在该域内的解称为可行解，而可行解的数目会有无限多个，其中必有一个为最优解。系统工程概论分类建模解决方法E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念(2)

确定性和随机性最优化问题

在确定性最优问题中，每个变量的取值是确定的，可知的。在随机性最优问题中，某些变量的取值是不确定的，但可根据大量的实验统计，知道变量取某值服从一定的概率分布规律，这称为随机规划。

(3)

线性和非线性最优化问题

如果目标函数和所有的约束条件式均为线性，则称为线行最优化问题或线性规划问题。如果目标函数或约束式(即使只是部分约束式)中任一个是变量的非线性函数，则称为非线性最优化问题或非线性规划问题。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念分类建模解决方法(4)

静态和动态最优化问题

如果最优化问题的解不随时间t的变化而变化，则称为静态最优化(参数最优化)问题。如果最优化问题的解随时间t的变化而变化，即变量是时间t的函数，则称为动态最优化(最优控制)问题，解决静态最优化问题可以采用线性规划和非线性规划方法，而解决动态最优化问题则采用动态规划或最大值原理。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念分类建模解决方法三、最优化问题的求解方法

最有化问题的求解方法大致可分成四类:

(1)

间接法(又称解析法)

对于目标函数及约束条件性具有简单而明确的数学解析表达式的最优化问题，通常可采用间接法(解析法)来解决，其求解方法是先按照函数极值的必要条件，用数学分析方法(一般用求导数方法或变分方法)求出其解析解，然后按照充分条件或问题的实际物理意义间接地确定最优解。系统工程概论分类建模解决方法E-mail:a_laly@163.com

武汉理工大学自动化学院石英最优化技术的基本概念(2)

直接法(数值解法)

直接法的基本思想，就是用直接搜索方法经过一系列的迭代以产生点的序列(简称点列)，使之逐步接近到最优点。直接法常常是根据经验或试验而得到的。

(3)

以解析法为基础的数值解法

以梯度法为基础的一种直接法，它是一种解析与数值计算结合的方法。

(4)

图与网络方法

这种方法是以网络作为数学模型，用图论方法进行搜索的寻优方法。

系统工程概论最优化技术的基本概念分类建模解决方法TheEndofOptimizationTechnology系统工程概论第三章最优化技术§3-1最优化技术的基本概念

§3-2线性规划§3-3整数规划§3-4非线性规划§3-5动态规划§3-6图与网络

E-mail:a_laly@163.com

武汉理工大学自动化学院石英§3-2线性规划LinearProgramming1.LP的数学模型

MathematicalModelofLP2.图解法

GraphicalMethod3.标准型

NormalizedFormofLP4.单纯形法

SimplexMethod5.人工变量法

ArtificialVariableMethod6.附录：LP常用词汇线性规划（LinearProgramming缩写为LP）是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。

线性规划通常解决下列两类问题

（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；

（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法§3-2-1LP的数学模型产品设备甲乙丙设备能力（小时）A31220B22415C40116D03512利润（元/件）435【例3.2.1】某企业计划生产甲、乙、丙三种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如表1-1所示，已知各设备在计划期内的能力分别为20、15、16、12小时；每生产一件甲、乙、丙三种产品，企业可获得利润分别为4、3、5元。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法【解】设x1、x2、x3

分别为甲、乙、丙三种产品的产量数学模型为：系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法线性规划的数学模型由决策变量Decisionvariables

目标函数Objectivefunction及约束条件Constraints构成。称为三个要素。其特征是：1．解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；2．解决问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型？系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj,j=1,2…,n，目标函数的变量系数用cj表示,

cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示,

bi称为资源限量。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法线性规划数学模型的一般表达式可写成：系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法在实际中一般xj≥0,但有时xj≤0或xj无符号限制。为了书写方便，上式也可写成系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划目标函数约束条件LP的数学模型标准型图解法单纯形法人工变量法系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法1.什么是线性规划?2.线性规划数学模型的组成及其特征。3.线性规划数学模型的一般表达式。图解法的步骤：1.求可行解集合。分别求出满足每个约束包括变量非负要求的区域，其交集就是可行解集合，或称为可行域；2.绘制目标函数图形。先过原点作一条矢量指向点（C1,C2)，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法§3-2-2图解法3.求最优解。依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是最优解。一般地，将目标函数直线放在可行域中，求最大时直线沿着矢量方向移动，求最小时沿着矢量的反方向移动。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法x1x2O1020304010203040(3,4)(15,10)最优解X=(15,10)最优值Z=85maxZ=3x1+4x2例3.2.2动画演示246x1x2246最优解X=(3,1)最优值Z=5(3,1)min

Z=x1+2x2例3.2.3动画演示246x1x2246有无穷多个最优解即具有多重解,通解为X（2）＝（3,1）X（1）＝（1,3）0≤α≤1当α=0.5时Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)minZ=5x1+5x2例3.2.4动画演示246x1x2246无界解(无最优解)maxZ=x1+2x2例3.2.5动画演示x1x2O10203040102030405050无可行解即无最优解maxZ=3x1+4x2例3.2.6动画演示由以上例题可知，线性规划的解有4种形式：1.有唯一最优解(例3.2.2例3.2.3)2.有多重解(例3.2.4)3.有无界解(例3.2.5)4.无可行解(例3.2.6)

1、2情形为有最优解，3、4情形为无最优解1.通过图解法了解线性规划有几种解的形式2.作图的关键有三点(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动作业：P79T1,4系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。线性规划问题的标准型为1．目标函数求最大值；2．约束条件都为等式方程；3．变量xj为非负；4．常数bi都大于或等于零。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法§3-2-3线性规划的标准型maxZ=c1x1+c2x2+…+cnxn系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法或用矩阵形式:或写成下列形式：系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法其中:通常X记为：

。称Ａ为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况m≤n，且r(Ａ)＝m。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法【例3.2.7】将下列线性规划化为标准型【解】(1)因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以令系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法(2)第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4，x4≥0，化为等式；(3)第二个约束条件是“≥”号，在“≥”号左端减去剩余变量（也称松驰变量）x5，x5≥0。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法(4)第三个约束条件是≤号且常数项为负数，因此在≤左边加入松驰变量x6，x6≥0，同时两边乘以－1。(5)目标函数是最小值，为了化为求最大值，令Z′=－Z,得到maxZ′=－Z，即当Z达到最小值时Z′达到最大值，反之亦然。

系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法综合起来得到下列标准型:系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法当某个变量xj≤0时,令x‘j=－xj.当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束

将其化为两个不等式

再加入松驰变量化为等式。

系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法1.如何化标准形式？可以对照四条标准逐一判断！标准形式是人为定义的，目标函数可以是求最小值。2.图解法时不必化为标准型。3.单纯形法求解时一定要化为标准型。作业：P793系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法单纯形算法的基本思路是:根据问题的标准型,从可行域中某个基可行解(顶点)开始,转换到另一个基可行解(顶点),并使得每次的转换,目标函数值均有所改善,最终达到最大值时就得到最优解。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法§3-2-4单纯形法单纯形计算方法(SimplexMethod)是先求出一个初始基可行解并判断它是否最优，若不是最优，再换一个基可行解并判断，直到得出最优解或无最优解。它是一种逐步逼近最优解的迭代方法。当系数矩阵A中可以观察得到一个可行基时（通常是一个单位矩阵或m个线性无关的单位向量组成的矩阵），可以通过解线性方程组求得基本可行解。【例3.2.8】用单纯形法求下列线性规划的最优解系统工程概论线性规划LP的数学模型标准型图解法单纯形法人工变量法E-mail:a_laly@163.com

武汉理工大学自动化学院石英【解】化为标准型，加入松驰变量x3、x4则标准型为系数矩阵r（B1）=2，B1是一个初始基,x3、x4为基变量，x1、x2为非基变量，令x1=0、x2=0由约束方程知x3=40、x4=30得到初始基本可行解X(1)=(0,0,40,30)T

系统工程概论线性规划LP的数学模型标准型图解法单纯形法人工变量法E-mail:a_laly@163.com

武汉理工大学自动化学院石英以上得到的一组基可行解是不是最优解，可以从目标函数中的系数看出。目标函数Z=3x1+4x2中x1的系数大于零，如果x1为一正数，则Z的值就会增大，同样若x2不为零为一正数，也能使Z的值增大；因此只要目标函数中非基变量的系数大于零，那么目标函数就没有达到最大值，即没有找到最优解，判别线性规划问题是否达到最优解的数称为检验数，记作λj,j=1,2…,n。本例中λ1=3,λ2=4,λ3=0,λ4=0.参看表3-1（a）。

最优解判断标准当所有检验数λj≤0（j=1，…，n）时，基本可行解为最优解。当目标函数中有基变量xi时，利用约束条件将目标函数中的xi消去即可求出检验数。系统工程概论线性规划LP的数学模型标准型图解法单纯形法人工变量法E-mail:a_laly@163.com

武汉理工大学自动化学院石英进基列出基行bi/ai2，ai2>0θi表3-1(a)XBx1x2x3x4bx3211040x4130130λj3400

(b)x3x4λj

(c)x1

x2

λj

基变量11018001/301/3105/31－1/330405/30－4/330103/5－1/51801－1/52/5400－1－1将3化为1乘以1/3后得到LP的数学模型标准型图解法单纯形法人工变量法动画演示单纯形法全过程的计算，可以用列表的方法计算更为简洁，这种表格称为单纯形表（表3-1）。计算说明：1.求初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零；2.判断：（a）若λj≤０（j＝１，２，…，n）得到最优解；（b）某个λk>0且aik≤０（i=1，2,…,m）则线性规划具有无界解。（c）若存在λk>0且aik(i=1,…,m)不全非正，则进行换基；系统工程概论线性规划LP的数学模型标准型图解法单纯形法人工变量法E-mail:a_laly@163.com

武汉理工大学自动化学院石英3.换基：（a）设λk>0,xk为进基变量，求最小比值：第Ｌ个比值最小，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个。aLk为主元素；(b）求新的基可行解：用初等行变换方法将aik

化为1,k列其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。系统工程概论线性规划LP的数学模型标准型图解法单纯形法人工变量法E-mail:a_laly@163.com

武汉理工大学自动化学院石英【例3.2.9】用单纯形法求解【解】将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，单纯法计算结果如表3-2所示。系统工程概论线性规划LP的数学模型标准型图解法单纯形法人工变量法E-mail:a_laly@163.com

武汉理工大学自动化学院石英表3-2Cj12100bθCBXBx1x2x3x4x50x42－3210150x51/3150120λj12100

0x42x2λj

1x1

2x2

λj

1/3150120301713751/30－90－2－2025601017/31/31250128/9－1/92/335/300－98/9－1/9－7/3线性规划LP的数学模型标准型图解法单纯形法人工变量法动画演示

前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法§3-2-5人工变量法【例3.2.10】用大M法解下列线性规划系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法【解】首先将数学模型化为标准形式式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量，x6、，x7，目标函数中加入―Mx6―Mx7一项，得到人工变量单纯形法数学模型再用前面介绍的单纯形法求解，见下表。

系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法线性规划

Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M

0－Mx6x5x7－4123－1－2121－1000101000014101→λj3－2M2+M－1+2M↑－M000

－M0－1x6x5x3－6－3253－2001－100010001

3→81λj5－6M5M↑0－M00

20－1x2x5x3－6/53/5－2/5100001－1/53/5－2/5010

3/531/5→11/5λj5↑0000

23－1x2x1x301010000111025/32/3

1331/319/3λj000－5－25/3

系统工程概论LP的数学模型标准型图解法单纯形法人工变量法（1）初始表中的检验数有两种算法，第一种算法是利用第一、三约束将x6、x7的表达式代入目标涵数消去x6和x7，得到用非基变量表达的目标函数，其系数就是检验数；第二种算法是利用公式计算，如（2）M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法（3）在第二张中x7已出基，故没有计算第七列的数值，同理，第三、四张表中x6、x7都已出基，故第六、七列没有计算；（4）第三、四张表中的基变量没有人工变量x6、x7，因而检验数中不含M；（5）可以看出，人工变量是帮助我们寻求原问题的可行基，第三张表就找到了原问题的一组基变量x2、x5、x3，此时人工变量就可以从模型中退出，也说明原规划有可行解，但不能肯定有最优解。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法【例3.2.11】求解线性规划

【解】加入松驰变量x3、x4化为标准型系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法在第二个方程中加入人工变量x5，目标函数中加上Mx5一项，得到系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法用单纯形法计算如下表所示。Cj5－800MbCBXBx1x2x3x4x50Mx3x53※11－2100－1016→4λj5－M↑－8+2M0M0

5MX1x5101/3－7/31/3－1/30－10122λj0－29/3+7/3M－5/3+1/3MM0

表中λj≥0，j=1，2，…，5，从而得到最优解X=（2，0，0，0，2），Z=10+2M。但最优解中含有人工变量x5≠0说明这个解是伪最优解，是不可行的，因此原问题无可行解。系统工程概论LP的数学模型标准型图解法单纯形法人工变量法解的判断唯一最优解的判断：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。多重最优解的判断:最优表中存在非基变量的检验数为零,则线性规划具有多重最优解。无界解的判断:某个λk>0且aik≤０（i=1，2,…,m）则线性规划具有无界解。无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri>0时，则表明原线性规划无可行解。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英LP的数学模型标准型图解法单纯形法人工变量法线性规划线性规划常用词汇线性规划Linearprogramming数学模型Mathematicalmodel决策变量Decisionvariable约束条件Constraint目标函数Objectivefunction图解法graphicalmethod可行域feasibleregion可行解feasiblesolution最优解optimalsolution非可行解infeasiblesolution斜率slopeofaline系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英线性规划LP的数学模型标准型图解法单纯形法人工变量法取...最大值,最大化maximize最小化minimize变量variable基basis基变量basisvariable松弛变量slackvariable人工变量artificialvariable进基变量enteringvariable出基变量leavingvariable无界解unboundsolution机会成本Opportunitycost系数coefficient迭代iteration系统工程概论线性规划LP的数学模型标准型图解法单纯形法人工变量法线性规划常用词汇TheEndofLP系统工程概论第三章最优化技术§3-1最优化技术的基本概念

§3-2线性规划§3-3整数规划§3-4非线性规划§3-5动态规划§3-6图与网络

E-mail:a_laly@163.com

武汉理工大学自动化学院石英1.整数规划数学模型MathematicalModelof

IP2.分枝定界法BranchandBoundMethod3.0－1规划

BinaryIntegerProgramming4.指派问题

AssignmentProblem§3-3整数规划IntegerProgramming一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划。当要求全部变量取整数值的，称为纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。如果模型是线性的，称为整数线性规划。本章只讨论整数线性规划。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划§3-3-1整数规划的数学模型IP的数学模型分枝定界法0-1规划指派问题很多实际规划问题都属于整数规划问题.例如1.变量是人数、机器设备台数或产品件数等都要求是整数2.对某一个项目要不要投资的决策问题，可选用一个逻辑变量x，当x=1表示投资，x=0表示不投资；3.人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题【例3.3.1】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表3-3-1-所示。问两种物品各装多少件，所装物品的总价值最大？表3-3-1物品重量（公斤/每件）体积（m3/每件）价值(元/每件)甲乙1.20.80.0020.002543系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题【解】设甲、乙两种物品各装x1、x2件，则数学模型为：(3.3.1)系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划如果不考虑x1、x2取整数的约束（称为（3.3.1）的松弛问题），线性规划的可行域如图3-3-1中的阴影部分所示。IP的数学模型分枝定界法0-1规划指派问题图3-3-1系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题用图解法求得点B为最优解：X＝(3.57，7.14)，Z＝35.7。由于x1，x2必须取整数值，实际上整数规划问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）虽属可行解，但代入目标函数得Z=33,并非最优。实际上问题的最优解是（5，5），Z=35。即两种物品各装5件，总价值35元。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题由图3-3-1知，点（5，5）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题【例3.3.2】在例3.3.1中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。（1）

所装物品不变；（2）如果选择旅行箱，载重量和体积的约束为系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题解：此问题可以建立两个整数规划模型，但用一个模型描述更简单。引入0－1变量（或称逻辑变量）yi，令i=1,2分别是采用背包及旅行箱装载。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题(1)由于所装物品不变，式(3.3.1)约束左边不变，整数规划数学模型为(2)由于不同载体所装物品不一样，数学模型为系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题旅行箱y2，重量背包y1，重量背包y1，体积旅行箱y2，体积式中M为充分大的正数。从上式可知，当使用背包时(y1=1，y2=0)，式(b)和(d)是多余的；当使用旅行箱时(y1=0，y2=1)，式(a)和(c)是多余的。上式也可以令：同样可以讨论对于有m个条件互相排斥、有m（≤m、≥m）个条件起作用的情形。系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划如果问题的所有变量取0或1，此问题称为0－1整数规划问题，简称0－1规划。IP的数学模型分枝定界法0-1规划指派问题系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划【例3.3.3】指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表3-3-2所示，如何安排他们的工作使总成绩最好。表3-3-2工作人员ABCD甲85927390乙95877895丙82837990丁86908088IP的数学模型分枝定界法0-1规划指派问题系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划【解】此工作分配问题可以采用枚举法求解，即将所有分配方案求出，总分最大的方案就是最优解。本例的方案有4！＝4×3×2×1＝24种，当人数和工作数较多时，方案数是人数的阶乘，计算量非常大。用0－1规划模型求解此类分配问题显得非常简单。设IP的数学模型分枝定界法0-1规划指派问题系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划数学模型如下：目标函数为要求每人做一项工作，约束条件为IP的数学模型分枝定界法0-1规划指派问题每项工作只能安排一人，约束条件为变量约束：

系统工程概论E-mail:a_laly@163.com

武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题1.线性整数规划模型的特征2.什么是纯（混合）整数规划3.0－1规划模型的应用4.指派模型的特征及其应用系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题分枝定界法的步骤：

1.求整数规划的松弛问题最优解；2.

若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；3.任意选一个非整数解的变量xi，在松弛问题中加上约束xi≤[xi]及xi≥[xi]+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界；系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划§3-3-2分枝定界法IP的数学模型分枝定界法0-1规划指派问题分枝定界法的步骤：4.

检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题【例3.3.4】用分枝定界法求解例3.3.1【解】先求对应的松弛问题（记为LP0）：用图解法得到最优解X＝（3.57,7.14）,Z0=35.7,如下图所示。系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题1010松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7x1x2oABC1010x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5①②动画演示1010x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336①②动画演示1010x1x2oACLP1346①②LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP3动画演示尽管LP1的解中x1不为整数，但Z5>Z因此LP5的最优解就是原整数规划的最优解。上述分枝过程可用下图表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP3:X=(4.33,6)Z3=35.33x2≤6LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x1≤4x1≥5无可行解x2≥7动画演示1.理解分枝与定界的含义2.选择合适的“枝”生“枝”3.掌握何时停止生“枝”4.掌握混合整数规划的分枝定界法求解整数规划的方法还有割平面法。作业：教材P134T5.2系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题什么是0-1规划？以一个工程项目投资分配问题为例。有n个工程，每项工程建成后的经济效益为cj，各项工程的投资、资源都是有限的，如何确定哪些项目应该建设，以使总的经济效益最大。数学模型如下：系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题§3-3-30-1规划求解0－1整数规划的隐枚举法(ImplicitEnumerationMethod)隐枚举法的步骤：1.找出任意一可行解，目标函数值为Z0；2.

原问题求最大值时，则增加一个约束当求最小值时，上式改为小于等于约束；(*)系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题列出所有可能解，对每个可能解先检验式（*），若满足再检验其它约束，若不满足式（*），则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值；目标函数值最大（最小）的解就是最优解。系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题【例3.3.5】用隐枚举法求下列0－1整数规划的最优解【解】容易求得X＝(1,0,0)是一可行解，Z0＝6。加一个约束(0)由于3个变量每个变量取0或1，共有8种组合，用列表的方法检验每种组合解是否可行解，满足约束打上记号“√”，不满足约束打上记号“×”，计算如表3-3-3所示。系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型0-1规划指派问题分枝定界法表3-3-3变量组合约束(0)约束(1)约束(2)约束(3)Z（0，0，0）

（0，0，1）

（0，1，0）

（0，1，1）

（1，0，0）（1，0，1）（1，1，0）

（1，1，1）

由表3-3-3知，X＝（1，0，1）是最优解，最优值Z＝9。××××√√√√6√√√√9√√××√E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题动画演示系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题§3-3-4指派问题指派问题，顾名思义，就是将“任务”指派给“人”。假定每个人只能分担一个任务，每个任务只能分给一个人，这就是指派问题。1.指派问题的数学模型系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题可见，指派问题是0-1规划的一种特例。2.指派问题的求解方法：匈牙利算法匈牙利算法是匈牙利数学家克尼格（Konig）证明了下面两个基本定理，为计算分配问题奠定了基础。因此，基于这两个定理基础上建立起来的解分配问题的计算方法被称为匈牙利法。假设问题求最小值，m个人恰好做m项工作，第i个人做第j项工作的效率为cij，效率矩阵为[cij]。系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题【定理3.1】如果从分配问题效率矩阵[cij]的每一行元素中分别减去（或加上）一个常数ui（被称为该行的位势），从每一列分别减去（或加上）一个常数vj（称为该列的位势），得到一个新的效率矩阵[bij]，若其中bij=cij－ui－vj,则[bij]的最优解等价于[cij]的最优解。这里cij、bij均非负。【定理3.2】若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素（称为独立元素）的最大个数。系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题如果最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，得到最优解。定理3.1告诉我们如何将效率表中的元素转换为有零元素，定理3.2告诉我们效率表中有多少个独立的“0”元素。【例3.3.6】已知四人分别完成四项工作所需时间如下表，求最优分配方案。系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题【解】最优分配方案是怎样安排四人的工作，使得完成工作总时间最少，是求最小值问题。第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有Min3408第二步：找出矩阵每列的最小元素，再分别从每列中减去，有Min系统工程概论IP的数学模型分枝定界法0-1规划指派问题第三步：用最少的直线覆盖所有“0”，得第四步：这里直线数等于3（等于4时停止运算），要进行下一轮计算。（1）从矩阵未被直线覆盖的数字中找出一个最小的数k，表中k＝3。(2)直线相交处的元素加上k，未被直线覆盖的元素减去k，被直线覆盖而没有相交的元素不变，得到下列矩阵系统工程概论IP的数学模型分枝定界法0-1规划指派问题整数规划可以分解为两个步骤：在1、2、4行（未被直线覆盖）减3，然后在3、4列（被直线覆盖）加3，根据定理1，与原矩阵等价。或者1、2列减3，第3行加3。回到第三步:用最少的直线覆盖所有“0”，得未被直线覆盖元素中最小元素k=2,直线相交处的元素加上2，未被直线覆盖的元素减去2，被直线覆盖而没有相交的元素不变，得到下列矩阵系统工程概论IP的数学模型分枝定界法0-1规划指派问题画线，最少直线数等于4。第五步：最优分配最优解：最优值Z＝73＋87＋82＋88＝330×××系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题独立元素0代表了最优指派。它们应该尽量分散，覆盖所有行或者所有列3.求最大值的指派问题匈牙利法的条件是：模型求最小值、效率cij≥0令则与的最优解相同。设C=(cij)m×m

对应的模型是求最大值将其变换为求最小值系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题【例】某人事部门拟招聘4人任职4项工作，对他们综合考评的得分如下表(满分100分)，如何安排工作使总分最多。【解】M＝95，令系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模型分枝定界法0-1规划指派问题用匈牙利法求解：最优解：即甲安排做第二项工作、乙做第一项、丙做第四项、丁做第三项。总分为：Z＝92＋95＋90＋80＝357系统工程概论E-mail:a_laly@163.com武汉理工大学自动化学院石英整数规划IP的数学模