工程优化与智能优化-课本.doc

第一章 最优化概论 本章概括地论述最优化的基本概念，使初学者对最优化技术有一个初步的认识内容包括什么是最优化? 最优化问题的数学模型如何建立? 有哪些基本类型? 最优化在工程中有何典型应用等对于最优化的基本理论和基本技术将在后三章中详细叙述 1 最优化问题的数学模型物质世界的每一种活动都可称作是一个系统任何一个系统，无论是复杂系统(如自动控制系统)，还是简单系统(如螺旋线圈)，无论是具体的物理系统(如发电厂)还是抽象的理论实体(如经济模型)，都是由许多相互联系的要素结合而成，具有特定功能的有机整体。从事任何工程项目，不管是设计新系统还是改造已有系统，一般总存在各种不同的候选方案，我们总是希望按照一定的标准设法从中选出最好的方案，从而使系统运行在最佳状态，以达到满意的效果，这就是工程最优化问题 大自然中最优化的例子很多，如光行进的路线是以最短时间为依据的，水往低处流是因为低处的势能最小。最优化又是人们追求的目标和实际的行动例如走路时人们总爱选最短距离的路线。两点之间的最短路径凭直观就知道是直线。但是，如果两点无直路，只有多条曲折路径，凭直观确定最短路径就会有困难。 最优化技术就是运用数学手段帮助决策者进行最优决策的一门学科，所以又叫数学规划技术。它主要研究和解决两大问题：1) 建模：建立最优化问题的数学模型2) 解模：运用最优化方法求出模型的最优解。1-1建立数学模型的三要素 1) 决策变量(设计变量) 组成系统的要素叫做参数，某些参数可事先取固定的常数值，叫预知参数，其它参数的值由最优化确定，叫做决策变量，或者设计变量。前者往往是一些不失重要的，或者受外界条件制约的参数，后者则是对系统性质有本质影响的关键参数。例如电路设计中一些与设计要求关系不大的元件可取固定的参数值，另一些与电路性质有直接影响的元件参数选作设计变量，这样既不会对电路的性质有大的影响，又能减小问题的规模不过，决策变量的数目与最优化模型的精确度和计算的复杂度有着密切关系，应该权衡考虑。设问题有个决策变量则可以表示成维决策向量。2) 约束条件 系统的各个要素是相互联系，相互制约的。因此，决策变量必须满足相应的约束条件。 1) 系统的物理特征约束：这些约束包括系统外形，尺寸的限制，物理参数的取值范围等。例如电路元倬的参数、电力系统母线电压、马达转子直径等的上下界。 其中分别为变量的下界和上界。2) 系统的性能约束(隐约束)：这些约束包括系统必须遵循的基本定理和性能要求，如电路中的基尔霍夫定律，电力系统中的功率平衡方程，产品设计中的技术条件等。这种约束以决策变量的函数形式表示，因此叫隐约束，有不等式和等式之分： 满足所有约束条件的就是可行决策方案3) 目标函数系统都是具有特定功能的，评价一个方案的优劣，除了考虑系统的各项性能指标外，经济性也是必须考虑的一项重要指标。从这些指标中选出一个或多个指标作为可行决策方案的最优性判断，称其为目标函数，用表示。1) 极大化目标函数(效果函数)：如利润、产值、增益、效益、生产率、可靠性、精确度等。2) 极小化目标函数(成本函数)：如费用、时间、人力、材料、损耗、重量、误差等.1-2. 数学模型最优化问题的一般提法：在满足=0和的条件下求使尽可能优的。于是，极小化问题的数学模型是： (1-1)三、几何解释和概念说明1可行解：满足所有约束条件的。2可行域：可行解的集合，用表示，如图11中所示的阴影区 (1-2)3最优解：中使取最优值的点，用表示，既满足下面条件的为极小点： (1-3)4. 最优值: 。5等高线： 测绘人员常把具有相同海拔高度的地点连成一条等高线，不同的海拔高度有不同的等高线。将这些线画在地图上，可使人一目了然地从地图上看出某个地区曲地形：哪里是山峰，峰有多高；哪里是山谷，底有多深。类似地，在最优化的研究中，常把目标函数的值的大小看作地形海拔的高低，并把具有相同目标函数值的自变量的点连成一条曲线，称为等值线(等高线)，即(常数)的点的轨迹。目标函数取不同的常数值，就得到不同的等高线。二维问题的几何解释如图所示。图1-1本教材以极小化问题为讨论对象，极大化问题可寓于极小化问题之中一并解决。因为问题可以用等效地分析和分解。事实上，若令为极大化问题的最优解，则按照最优解的定义有，或者，所以也是极小化问题的最优解。 2 最优化问题的分类根据建模三要素的性质和问题的物理结构可以将最优化问题适当分类，不同类型的问题有不同的求解方法。2-1 按照决策变量进行分类 1 连续最优化问题：所有决策变量允许取任何实数值2 离散最优化问题：基些决策变量限制只取离散值。1) 整数规划问题：某些决策变量只允许取整数值 全整数规划问题：所有决策变量只允许取整数值 混合整数规划问题：部分决策变量只允许取整数值 0-1规划问题：决策变量只限取0或l值2) 网络最优化问题：工程中有许多系统，如交通系统、运输系统、电力系统、控制系统，都具有网络结构。交通系统中的人流、运输系统中的货物流、电力系统中的电力流、控制系统中的信号流等，都可以看成是网络流。这些系统的线性整数规划模型中的约数函数相当于对应的网络图的节点关联矩阵。网络最优化就是应用图论来研究网络中的最短路径、最小生成树、最大流和最小成本流等问题，进而解决实际系统中的最优化问题。3) 组合最优化问题：组合最优化是研究离散物体的最佳排列、定序、分组、选择等它们虽可定式为0-1规划，但无可行算法，其中有一类所谓的“NP-完全问题”，至今未发现有效算法，计算法的复杂性以问题规模(如决策变量的个数）的多项式函数为界的算法。目前只能采用多项式界的近似运算法求出组合优化问题的良好近似解。2-2 按照约束方程进行分类1.有约束最优化问题:带有约束条件的最优化问题称为约束最优化问题，(1-1)是约束极小化的一般形式。下面是两类常见的约束最优化问题。1）等式约束问题： ， (1-4)其中。该函数又称为函数的条件极值问题。2）不等式约束问题： (1-5)2.无约束最优化问题：标函数为非线性函数，但没有约束条件的最优化问题，称为无约束最优化问题，一般形式为：。如果存在极值，无约束最优化问题就是目标函数的极值问题.2-3按照目标函数进行分类1单目标最优化问题：以上所述的最优化问题只涉及到一个目标函数，称为单目标最优化问题但实际问题中常常期望几个指标都达到最优。2. 多目标最优化问题：如果最优化问题的目标函数不止一个，则称为多目标最优化问题，或者向量最优化问题，一般形式为：， (1-6)式中为k个分目标函数。一般来说，各分目标函数的优劣是互相矛盾的，同时使各分目标函数达其最优值的“最优解”几乎不存在，只能找到所谓的“非劣解”（折衷解）。非劣解都有共同的性质：在非劣解点上进一步使任何一个分目标函数优化必然导致其他分目标函数中至少有一个分目标函数劣化。2-4 按约束方程和目标函数的线性与非线性划分l线性规划问题：目标函数和约束函数均为线性函数的最优化问题称为线性规划问题该问题的一般形式为： (1-7)式中为常数。2. 非线性规划问题：如果最优化问题中的目标函数和约束函数至少有一个使非线性函数，则称为非线性规划问题。公式(1-1)为非线性规划问题的一般形式非线性规划问题有几种特殊类型：1）二次规划问题：目标函数是二次函数，约束函数是线性函数，数学模型为： ， (1-8)式中为常数。2) 几何规划问题：目标函数和约束函数均为X的正项式(polynomial)，数学模型为： (1-9)式中为正数，为实数. 正项式是一个和式，每一项都是系数为正的决策变量的幂函数乘积。工程设计问题中的目标函数(如总成本)常常具有这种和式。 3 现代最优化技术 近年来，最优化技术进入了蓬勃发展的时期这主要是由于近代科学技术和生产的迅速发展，提出了许多用经典最优化技术无法解决的最优化问题然而，为了取得重大的经济和军事效果又必须解决这些问跫，这种客观需要极大地推动了最优化的研究与应用.另一方面，由于电子计算机的出现和发展，为最优化技未提供了有效手段许多大型复杂的计算问题，过去只能定性地，粗略地在理论进行分析,如今已经可以精确的定量研究并用于实际了。 最优化的发展首先表现在线性规划方面二次大战期间在美国空军部门工作的丹茨格(Dantzig)受命进行数学和有关技术应用于军事规赳问题的可行性研究于是，他便把一个大的机掬的各种活动问的相互关系看成是一个线性规划模型，并通过极小化一个线性目标函数来确定最优规划模型来确定最优规划。1947年丹茨格提出了一般线性规划问题的数学定式和系统解法单纯形法这是最优化技术发展的一个重大突破，为线性规划问题提供了完整的理论和有效解法.另一个重大突破是在非线性规划理论方面1951年库恩一图克(Kuhn-Tucker)发表论文阐述一般非线性规划问题(包括不等式约束)最优解的必要条件，称为库恩一图克条件，它是等式约束问题的一阶必要条件(拉格朗日乘子法)在不等式约束问题中直接推广，具有类似的表达形式。然而它的问世竟然相隔近三百年! 库恩和图克时开创性工作为以后许多非线性规划方面的研究打下了基础 第三个重大发展是动态规划技术l957年贝尔曼(Bellman)阐述了一条最优性原理，它联系到不同的时间点、不同的空间点和不同的水准上进行序贯决策问题(多级决策问题)，包括动态最优化问题(例如最优控制问题)和可以定式表示成多级决策的静态最优化问题(例如最短路径问题)。根据这一最优性原理，一个多级决策问题的最优化可以定义为动态规划问题，即一序列的单极决策问题动态规划技术在最优控制、组合最优化等方面有广泛的应用 在最优化理论的研究基础上，最优化方法在开发方面也取得了全面的发展重点列举如下在无约束最优化方面有l959年戴维顿(Davidon)首先提出，J963年经弗莱彻(Fletcher)和鲍威尔(Powell)改进的DFP即法；1962年斯潘德利(Spendley)等提出， 1965年经内尔德(Nelder)和米德(Mead)改进的单纯形搜索法。在约束最优化方面有1943年柯兰特(Courant)首先使用，1964年经菲阿科(Fiacco)和梦考密克(McComick)发展的惩罚函数法；博克斯(Box)的复合形法。在二次规划方面有1965年莱姆克(Lamke)的互补主元法在几何规划方面有1967年达芬（Duffin）的几何规划法在整数规划方面有l958年高莫里(Gomory)的割平面法；l965年巴勒斯(Balas)的隐枚举0-1规划法。在网络规划方面有l956年克鲁斯卡尔(Kruskal)的最小生成树法；l957年戴杰斯特拉(Dijkstra)的最短路径法；在多目标规划方面有1961年查内斯(Charnes)和库柏(Cooper)的线性目标规划法。在随机规划方面有l955年丹茨格的两阶段随机线性规划法；1957年查内斯和库柏的随机约束规划法等。 七十年代中期数学规划开始与图论和组合学产生所谓的组合最优化，它是一个研究内容丰富，应用范围广泛，因而也最吸弓l人的最优化领域。组合最优化的另一个重大进展是应用神经网络模拟和求解组合最优化问题。1984年霍普菲尔德提出了一个神经网络模型模型。这种神经网络所代表的系统可用状态空间的运动方程来描述，而能量函数就是此系统的李雅普洛夫函数。也就是说，当系统从某个初始值动作，其收敛的稳态乎衡点印为能量函数的局部极小点，它就是最优化问题的近似解特别一提的是近年来发展起来的智能优化技术。 智能计算也称之为软计算，是人们受自然界或生物界规律的启发，根据自然界或生物界的原理，模仿其规律而设计的求解问题的算法。自然界的许多自适应优化现象不断给人类以启示。近几十年来，一些与经典的数学规划原理截然不同的试图通过模拟自然生态系统机制以求解复杂优化问题的仿生智能优化算法相继被提出和研究。这方面的内容非常丰富，典型地如遗传算法，模糊规划，人工神经网络技术，人工免疫算法和群智能算法等。 这些算法大大丰富了现代优化技术，也为那些传统优化技术难以处理的优化问题提供了切实可行的解决方案。练习1. 说明线性与非线性规划单目标与多目标规划硬优化与软优化的区别.2. 举例说明智能优化方法的内容与特点. 第二章 线性最优化 线性最优化包括线性规划和线性整数规划它们的共同特点是目标函数和约束函数均为决策变量的线性函数不过线性整数规划的部分或全部变量被限制为整数线性规划技术比较成熟，在军事、经济、工业和社会问题中得到广泛的应用但是，线性整数规划问题的求解却要困难得多本章首先讨论线性规划问题的最优解原理，然后描述线性规划的基本解法和对偶性，最后介绍求解线性整数规划的一般技巧。 2.1线性规划问题的图解法和性质 由于线性规划问题的“线性”，其解也具有独特的性质。这种性质是建立线性规划的基本解法单纯形法的基础。下面从“几何学”和“代数学”两个方面分析这种性质。一二维图解法和解的几何性质 只有两个决策变量的线性规划问题属于简单的情况，可以用图解法求解。图解法除了可以求出解，还可以看出线性规划问题的一些几何特征。例2-1 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表2-1所示。表2-1数学模型为: 例2-2 简化的环境保护问题 靠近某河流有两个化工厂(见图)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。 第一 化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工厂每天排放这种工业污水1.4万立方米。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万立方米第二 化工厂处理工业污水的成本是800元/万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。数学模型为上述模型的共同特征: 1）每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的；2) 要有各种资源和使用有关资源的技术数据，创造新价值的数据； ；3) 存在可以量化的 约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;4) 要有一个达到目标的要求，它可用决策变量的线性函数(称为 目标函数)来表示。按问题的不同，要求目标函数实现最大化或最小化。表格2-2它们的对应关系可用表格2-2表示：线性规划的一般模型形式: (2-1)二线性规划的图解法例2-3 是二维空间（平面）线性规划问题，可用作图法直观地来表述它的求解。 因存在，可行域必须在直角坐标的第1象限内作图(图2.1a)，求解。目标函数 图2.1(a) 可行域 图2.1(b) 目标函数极值 从图2.1b可以看出，目标值在(4，2)点达到最大值14。 图解法基本步骤：1) 在平面上画出由约束条件限定的可行域（如图2.1(a)中阴影区) 2) 选择一个便于作图的目标函数值，作一条穿过可行域的等高线(图中右上方虚线)3) 将此等高线沿值减小(对最大化问题为增大)方向平移，直到等高线至少与可行域的一个顶点相迭4) 步骤3)中最后得到的交迭点就是线性规划的最优解，通过交叠点的等高线为最优等高线，其目标函数值称为最优解，用表示。三线性规划问题的解的几种可能情况(如图2.2(a)-(d)所示)1) 唯一最优解：最优等高线与可行域D的个顶点交迭，此顶点为唯一最优解。2) 多重最优解：最优等高线与可行域D的一条边界重合，这条边界上的任何点均可取作最优解，它们具有同一个目标函数值3) 无界最优解：若在目标函数减小(对max问题为增大)方向，可行域不闭合，此时有可行解，但是最优值。对于一个实际问题来说，由于从有限的资源中是不可能取得无限的收益的，所以不应该存在这种不可思义的解。如果在解一个实际问题时出现了这种情况，通常是由于忽略了一个或几个约束条件所造成的。这时需重新研究数学模型：4) 无可行解：可行域不存在，这是由于约束条件互不相容所致，需重新建模. 从二维图解法中我们可以看到，线性规划的解具有以下重要的几何性质:1) 可行域为凸集，即中任意两点连线仍在内凸集与非凸集如图2.3所示2) 最优解(如果有界的话)，一定出现在可行域的顶点。凡凸集中不位于该集中的其它两点的连线上的点称为顶点。例如，圆周上的所有点以及多边形的角点都是顶点。四、线性规划问题的标准形式和基可行解1. 线性规划问题的标准形式 因数值求解的需要，线性规划应表示为标准形式。以矩阵和向量表示的标准形式是 (2-2) _约束矩阵(常数)式中 _决策向量(变量)； _成本向量(变量)； _要求向量(变量)线性规划问题的标准形式具有以下特征: 1) 决策变量非负，即要求向量X非负; 2) 除非负条件外，所有的约束为等式，因此可行域是一组方程的公共解；3) 目标函数为极大化类型。 各种求解线性规划问题的方法往往要求问题用标准形式表示，但并不是所有线性规划问题的原始数学模型都以标准形式出现，所以，求解的第一步就是将非标准形式的数学模型化成标准形式。步骤如下：1) 将不满足非负条件的决策变量化为非负变量：若某个决策变量，不满足非负要求，则可采用以下两种方式来进行处理：第一种方法：引入松弛变量。例如：若则可引入松弛变量作变换，将此变换代入原问题，就消去了负变量：若置无符号限制，则可以引入两个松弛变量，作变换。将此变换代入原问题，就消去了自由变量本方法比较常用，本书中所有例子都采用该方法进行处理第二种方法：先将不等式约束变为等式约束，然后从某个等式约束中将不满足非负条件的决策变量解出，再将已解出的表达式代入到其余各等式中，这样就消去了不满足非负条件的决策变量2) 将约束条件的右端化为非负：若第个约束条件的右端则可在该约束的左右两端同时乘以-1，就可将其右端化为非负需要注意的是，如果该约束为不等式约束，则在该过程中一定要改变不等式的方向 3) 将不等式约束条件化为等式约束条件：若第个约束条件为不等式约束条件，则可在该不等式的左侧引入一个新的变量，就可以将其化为等式约束条件。为了将新引入的变量与原有的决策变量相区别，该变量称为松弛变量。4) 将最大值问题化为最小值问题: 若原问题为极大化问题，则可引入新目标函数，约束条件不变，这样原问题就变成了等价的标准形式。例2-4 将例2-1的数学模型化为标准型解：把例2-1的数学模型加松驰变量后得例2-5 将下述线性规划问题化为标准型求解步骤如下:(1) 用-替换，其中；(2) 在第一个约束不等式号的左端加入松弛变量；(3) 在第二个约束不等式号的左端减去剩余变量；(4) 令z= -z，把求min z 改为求max z，即可得到该问题的标准型：2线性规划问题的基可行解 1) 基解：在标准形式的约束方程中，置个变量(称为非基变量)为零，有方程式解出其余个变量(称为基变量)，这样构成的一组解称为基解。显然基解的个数至多为个。2) 基可行解: 满足非负条件的基解称为基可行解。显然基可行解的个数也不会超过个。这些概念的关系如图所示。求基可行解的经典方法为高斯-约当消去法其基本原理是通过初等行运算将标准形式的约束方程式化为等效的正则形式，即约束方程式中可以找到个变量，其系数能够组成一个一个单位矩阵假设这个变量中的前个变量为则约束方程式的正则形式如下： (2-3)从上式可以看出，这些变量在某个方程中的系数为l，而在其它的方程中系数为0这些变量叫做基变量或相关变量，余下的个变量叫做非基变量或独立变量。正则形式的优点在于可以简单的令个非基变量的值为零后，立即可得出基变量的值，从而求出一个基解。例如公式(2-3)的一个基解为若则该基解是基可行解。求出这种正则形式的优点是，只要选取不同的非基变量，解出基变量的正则方程组，就可求出约束方程的多组解可以用两种基本的行运算求出正则形式：行运算 1：对方程组的任一方程乘以一个非零常数； 行运算 2：对方程组中任一方程加或减其它方程的常数倍。例2-6 用消元法求下面线性规划问题的全部基可行解。目标函数: 约束条件: 解：在上面的约束方程和中，若选和为基变量，令则，得解(基可行解)；若选和为基变量，进行消元运算，用得； 再用减去的2倍，得令0，则得解(基可行解)；类似的消元运算可得(基可行解)，(基可行解)，(不可行基解)，(不可行基解)因为所以基解已全部求出，其中只有4个基可行解3基可行解与可行域顶点的关系如果把例2-6中的变量看成松弛变量，则例2-6实际上就是下面二维规划问题的标准形式：；，这个二维问题的可行域D及其顶点如图2-4所示，顶点的坐标就是相应的可行解。图2-4可行域顶点与基可行解的关系一般地，有以下结论：1) 线性规划的基可行解与可行域顶点一一对应。2) 线性规划的最优解可以由基可行解求出，因为基可行解的个数不超过，因此一条非常自然的求解线性规划的途径是，通过正则变换产生所有基可行解，其中给出最优化目标函数值的基可行解就是最优解然而，当和很大时，基可行解数也随之增加；例如当时，有个基解；而当时，有184756个基解，这已经是一个相当可观的数目因此，我们希望有一种计算方法，它只需要计算一小部分基可行解便可以找出最优解。单纯形法就是这样的一种方法只考察大约(n3m)个基可行解，便可以找到最优解，因此是非常有效的思考题：1. 已知线性规划问题：；;1) 化为标准形式；2) 化为以和为基变量的正则形式；3) 求出所有基解、基可行解和最优解；4) 用图解法求解2. 已知线性规划问题:,; 找出满足约束条件的所有基解。指出哪些是基可行解，并 2-2 线性规划的单纯形法 单纯形法(Simplex Method)是一种迭代方法，它是从所有基可行解中的一个较小部分里，通过迭代过程选出最优解的有效方法其名字来源于线性规划问题的解的性质可行域为n维空间的多面体(几何上称这种凸多面体为广义单纯形)；其原理出自线性规划问题的代数性质最优解存在于基可行解之中 单纯形法的基本观点是：从可行解的凸集某个顶点(初始解)出发，向相邻顶点运动，以使其目标函数值至少比前一个顶点更好由于可行域的顶点数是有限的，并且最优解一定在顶点上，所以迭代过程是有限的。事实上几何上从一个顶点到另一个顶点的有限次迭代，在代数上即为从一个基可行解到另一个基可行解的迭代前面已经指出，它需要进行数倍于约束个数的迭代，便可以求得最优解。因此，它目前求解线性规划问题的最基本和最通用的方法。四十多年来的计算实践已经证明它是实用有效的。一、单纯形法的基本原理 单纯形法是从产生初始基可行解开始的，如果最优性检验表明当前基可行解不是最优解，将继续寻找目标函数值更优的基可行解，这一过程重复进行，直到找到最优解下面首先通过一个算例来说明单纯型法的基本步骤。例2-7 试以例2-2来讨论如何用单纯形法求解。例2-2的标准型为：约束方程的系数矩阵为从上式中可以看到x3, x4, x5的系数列向量线性无关构成一个基按照基向量得 把x3, x4, x5的上述表达式代入目标函数得令非基变量x1, x2,为零得。这时得到一个基可行解X(0)，X(0)=(0,0,8,16,12)T。 这个基可行解表示工厂没有安排生产产品、；资源都没有被利用，所以工厂的利润指标z=0。 从分析目标函数的表达式可以看到，非基变量x1, x2 (即没有安排生产产品，)的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品或，就可以使工厂的利润指标增加。所以只要在目标函数的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。如何确定换入，换出变量? 一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中去. 而确定基变量中有一个要换出来成为非基变量(换出变量)，可按以下方法: 当将x2定为换入变量后，必须从x3, x4, x5中确定一个换出变量，并保证其余的都是非负，即x3, x4, x50。 x2取何值时，才能满足非负要求？从上式中可以看出，只有选择x2= min(8/2,-,12/4)=3时，才能使上式成立。因当x2=3时，基变量x5=0，这就决定用x2去替换x5。以上数学描述说明了每生产一件产品，需要用掉各种资源数为(2，0，4)。由这些资源中的薄弱环节，就确定了产品的产量。这里就是由原材料B的数量确定了产品的产量x2=12/4=3件。 为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将x2的位置与x5的位置对换，得 用高斯消去法将上式中x2的系数列向量变换为单位列向量。其运算步骤是:=/4；=-2;=,并将结果仍按原顺序排列有： 再将该式代入目标函数式得到, 令非基变量得到另一个基可行解，且，从目标函数的表达式中可以看到，非基变量x1的系数是正的，说明目标函数值还可以增大，X(1)还不是最优解。于是再用上述方法，确定换入、换出变量，继续迭代，再得到另一个基可行解X(2)，X(2)=(2,3,0,8,0)T，再经过一次迭代，再得到一个基可行解X(3)，X(3)=(4,2,0,0,4)T而这时得到目标函数的表达式是： z=14-1.5x3-0.125x4 再检查上式，可见到所有非基变量x3,x4的系数都是负数。所以当x3=x4=0时，目标函数达到最大值, X(3)是最优解。即当产品生产4件，产品生产2件，工厂才能得到最大利润。 通过上例，可以了解利用单纯形法求解线性规划问题的思路。现将每步迭代得到的结果与图解法做一对比，其几何意义就很清楚了。原例1的线性规划问题是二维的，即两个变量x1, x2；当加入松弛变量x3, x4, x5后，变换为高维的。这时可以想象，满足所有约束条件的可行域是高维空间的凸多面体(凸集)。这凸多面体上的顶点，就是基可行解。一般地，一个线性规划问题用单纯性法求解必须研究三个方面的问题:1初始基可行解的产生为了确定初始基可行解，要首先找出初始可行基，其方法如下。 (1)直接观察 (2)加松弛变量 (3)加非负的人工变量(1) 直接观察: 给定线性规划问题 (2-7)从Pj(j=1,2,n)中一般能直接观察到存在一个初始可行基。如其中一组单位向量。(2) 加松弛变量 x1,x2,xm , 对所有约束条件是“”形式的不等式，可以利用化为标准型的方法，在每个约束条件的左端加上一个松弛变量。经过整理，重新对xj及aij (i=1,2,m; j=1,2,n)进行编号，则得下列方程组 (2-8)于是含有mm单位矩阵，以B 作为可行基,如下式所示。 令xm+1=xm+2=xn=0，所以得xi=bi(i=1,2,m)，得到一个初始基可行解。又因bi0，所以得到一个初始基可行解 X=(x1,x2,xm,0,0)T =(b1,b2,bm,0，0)T (3) 加非负的人工变量 对所有约束条件是“”形式的不等式及等式约束情况，若不存在单位矩阵时，就采用人造基方法。 即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量； 对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。二最优性检验与解的判别对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况。为此需要建立对解的判别准则。一般情况下，经过迭代后(2-3)式变成 (2-9)将该式代入线性规划的目标函数整理后得令，得 设 (2-10)若为对应于基B的一个基可行解，且对于一切j=m+1,n，有j0，则X(0)为最优解。称j为检验数。 最优解的判别定理1）当所有非基变量的j0时，由（2-12）式可知已不存在任一可换入的非基变量，使目标函数继续增大。所以以j0，为最优解的判别准则。2）若为一个基可行解，对于一切j=m+1，,n，有j0，又存在某个非基变量的检验数m+k=0，则线性规划问题有无穷多最优解。3）若为一基可行解，有一个m+k0，并且对i=1,2,，m，有存在。 那么该线性规划问题具有无界解(或称无最优解) (证明略)。 当求目标函数极小化时，将其化为标准型。如果不化为标准型，只需在上述1，2点中把j0改为j 0，第3点中将m+k0改写为m+k0即可。2.4 基变换若初始基可行解X(0)不是最优解及不能判别无界时，需要找一个新的基可行解。具体做法是从原可行解基中换一个列向量(当然要保证线性独立)，得到一个新的可行基，这称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解。1) 换入变量的确定为了使目标函数值增加得快，从直观上一般选j0中的大者，即则对应的xk为换入变量。但也可以任选。2) 换出变量的确定.重复换入与换的过程称为旋转迭代变换。即经过基变换得到的解是基可行解。 实际上，从一个基可行解到另一个基可行解的变换，就是进行一次基变换。从几何意义上讲，就是从可行域的一个顶点转向另一个顶点。现考虑以下形式的约束方程组 (2-11)一般线性规划问题的约束方程组中加入松弛变量或人工变量后，很容易得到上述形式。设x1,x2,xm为基变量，对应的系数矩阵是mm单位阵I，它是可行基。令非基变量xm+1,xm+2,xn为零，即可得到一个基可行解。 若它不是最优解，则要另找一个使目标函数值增大的基可行解。这时从非基变量中确定xk为换入变量。显然这时为在迭代过程中可表示为其中是经过迭代后对应于的元素值。按规则确定xl为换出变量，xk, xl的系数列向量分别为 为了使xk与xl进行对换，须把Pk变为单位向量，这可以通过(2-11)式系数矩阵的增广矩阵进行初等变换来实现 (2-12)变换的步骤是：(1) 将增广矩阵(2-12)式中的第l行除以al k，得到 (2-13)(2) 将(2-12)中xk列的各元素，除变换为1以外，其他都应变换为零。其他行的变换是将(2-13)式乘以)后，从(2-12)式的第i行减去，得到新的第i行。由此可得到变换后系数矩阵各元素的变换关系式：是变换后的新元素。 (3) 经过初等变换后的新增广矩阵是 (2-14)(4) 由(2-14)式中可以看到x1,x2,xk,，xm的系数列向量构成mm单位矩阵;它是可行基.当非基变量xm+1,，xl,xn为零时，就得到一个基可行解X(1)。 在上述系数矩阵的变换中，元素al k称为主元素，它所在列称为主元列，它所在行称为主元行。元素al k位置变换后为1。 例2-8 试用上述方法计算例2-1的两个基变换。解 例2-1的约束方程组的系数矩阵写成增广矩阵 当以x3,x4,x5为基变量，x1, x2为非基变量，令x1, x2=0可得一个基可行解X(0)=(0,0,8,16,12)T现用x2去替换x5，于是将x3，x4, x2的系数矩阵变换为单位矩阵，经变换后为令非基变量x1, x5=0，得到新的基可行解X(1)=(0,3,2,16,0)T。四 单纯型表单纯形法的各个计算步骤可以在一张表格上施行，称其为单纯形表将线性规划的约束方程与目标函数组成n+1个变量， m+1个方程的下面方程组:将上述方程组写成增广矩阵形式1) 将z看作不参与基变换的基变量，它与x1, x2, , xm的系数构成一个基，2) 采用行初等变换将c1, c2,cm变换为零，使其对应的系数矩阵为单位矩阵。得到可根据上述增广矩阵设计以下计算表格。 表2-2表格的说明： XB列中填入基变量，这里是x1，x2,，xm； CB列中填入基变量的价值系数，这里是c1,c2,cm；它们是与基变量相对应的； b列中填入约束方程组右端的常数； cj行中填入基变量的价值系数c1,c2,cn； i列的数字是在确定换入变量后，按规则计算后填入； 最后一行称为检验数行，对应各非基变量xj的检验数是单纯行法的计算步骤如下：表2-2称为初始单纯形表， 每迭代一步构造一个新单纯形表。(1) 按数学模型确定初始可行基和初始基可行解，建立初始单纯形表。(2) 计算各非基变量xj的检验数， 检查检验数，若所有检验数，则已得到最优解，可停止计算。否则转入下一步。 (3) 在中，若有某个对应的系数列向量0，则此问题是无界，停止计算。否则，转入下一步。(4) 根据，确定为换入变量，按规则计算换出变量：(5) 以为主元素进行迭代(即用高斯消去法或称为旋转运算)，把所对应的列向量将XB列中的xl换为xk，得到新的单纯形表。重复(2)(5)直到终止。现用例2-1的标准型来说明上述计算步骤。 (1) 取松弛变量x3, x4, x5为基变量，它对应的单位矩阵为基。这就得到初始基可行解X(0)=(0,0,8,16,12)T将有关数字填入表中，得到初始单纯形表，见表2-3。表中左上角的cj是表示目标函数中各变量的价值系数。在CB列填入初始基变量的价值系数，它们都为零。 表2-3cj23000CBXBbx 1x 2x 3x 4x 50x 38121008/2=40x 41640010-0x 5120400112/4=3 -z 0230002. 计算，由它确定为换出变量。各非基变量的检验数为1=c1-z1=2-(01+04+00)=2； 2=c2-z2=3-(02+00+04)=3填入表2-3的底行对应非基变量处。(2) 因检验数都大于零，且P1，P2有正分量存在， 转入下一步；(3) max(1,2)=max(2,3)=3，对应的变量x2为换入变量， 计算它所在行对应的x5为换出变量，x2所在列和x5所在行的交叉处4称为主元素或枢元素(4) 以4为主元素进行旋转运算或迭代运算，即初等行变换，使P2变换为（0,0,1）T, 在XB 列中将x2 替换x5 ,于是得到新表2-4. 表2-4cj23000CBXBbx1x2x3x4x50x321010-1/220x4164001043x2301001/4- -z -92000-3/4(5) 检查表2-4的所有cj-zj, 这时有c1-z1=2；说明x1应为换入变量。重复(2)(4)的计算步骤，得表2-5。表2-5cj23000CBXBbx1x2x3x4x52x121010-1/2-0x4800-41243x2301001/412 -z -1300-201/4还存在检验数大于0，继续进行。(6) 表2-6最后一行的所有检验数都已为负或零。这表示目标函数值已不可能再增大，于是得到最优解。表2-6cj23000 CBXBbx1x2x3X4x52x141011/400x5400-21/2 13x22011/2-1/80 -z -1400-3/2-1/80最优解X*=X(3)=(4,2,0,0,4)T，目标函数的最大值:z*=14 2-3 单纯形法的进一步讨论以下介绍单纯性法设计的几个相关问题: 人工变量法；退化；检验数的几种表示形式。1) 大M法 假定人工变量在目标函数中的系数为(-M)(M为任意大的正数)，因此，要实现最大化时，必须把人工变量从基变量换出。否则目标函数不可能实现最大化。 例2-10 现有线性规划问题，试用大M法求解。解 在上述问题的约束条件中加入松弛变量x4，剩余变量x5，人工变量x6, x7，得到这里M是一个任意大的正数。 因本例的目标函数是要求min，所以用所有cj-zj0来判别目标函数是否实现了最小化.用单纯形法进行计算时，见表2-8。表2-8cj-31100MMiCBXBbx1x2x3x4x5x6x70MMx4x6x711311-4-2-2101211000-10010001113/2 1 cj-zj-3+6M1-M1-3M0M00在表2-8的最终计算结果表中，表明已得到最优解是：x1=4,x2=1,x3=9，x4=x5=x6=x7=0；目标函数z=-2cj-31100MMiCBXBbx1x2x3x4x5x6x70M1x4x6x3101130-2-2100011000-10010-1-211 cj-zj-11-M1-3M0M03M-1011x4x2x3121130-2010001100-2-10210-5-214 cj-zj-10001M-1M+1-311x1x2x34191000100011/302/3-2/3-1-4/32/314/3-5/3-2-7/3 cj-zj 20001/31/3M-1/3M-2/32.两阶段法 第一阶段求解： 不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。如第一阶段求解:用单纯形法求解上述模型，若得到=0，这说明原问题存在基可行解，可以进行第二段计算。 否则原问题无可行解，应停止计算。第二阶段求解：将