系统工程第二章系统工程的基础理论与方法论

第二章系统工程的基础理论与方法论系统最优化理论控制理论基础信息论基础系统工程方法论第2.1节系统最优化理论系统工程是一门交叉学科，其最基础的理论涉及系统最优化、系统控制与系统的信息处理三个方面。系统工程，其核心目标之一是使系统运行在最优状态，因此，系统最优化技术是其最重要的理论支撑。第2.1节系统最优化理论系统优化理论主要包括线性规划、非线性规化、整数规划、动态规划等内容，如果考虑到最优化技术在不同应用领域中的拓展，还应包括排队论、对策论、决策论等，这些都属于运筹学的研究范畴。第2.1节系统最优化理论2.1.1线性规划线性规划是系统优化理论体系中产生较早、应用广泛的一个分支，其中的内容是求取线性函数在线性等式或不等式约束下达到最小或最大值的问题。首先讨论两个例子。2.1系统最优化理论例2-1某工厂有三种原料B1、B2和B3，储量分别为170千克、100千克和150千克。现用此三种原料生产两种产品A1和A2。已知每生产1千克A1需要原料5千克B1、2千克B2和1千克B3。每生产1千克A2需要原料2千克B1、3千克B2和5千克B3。又知每千克A1产品利润为10元，每千克A2产品利润为18元。问在工厂现有资源条件下，应如何安排生产，才使工厂获得最大利润。2.1系统最优化理论解设安排A1、A2产品的产量分别为1x千克和2x千克，则产品的总利润为121018xx元。然而，产量1x和2x不能无限制扩大，要考虑到仓库中原料存量的限制。就原料B1来说，生产1x千克A1要消耗15x千克B1，生产2x千克A2要消耗22x千克B1，因此共消耗B1为1252xx千克。同样，当生产A1为1x千克，A2为2x千克时，共消耗B2为1223xx千克，共消耗B3为125xx千克。按原料B1、B2、B3的存储量限制，各原料总消耗量应不高于存储量，即1252170xx（千克），1223100xx（千克），125150xx（千克）。最后，考虑到1x和2x为产品的产量，因此不能为负数，120,0xx。这样，该问题的数学模型为：2.1系统最优化理论12max1018xx(2-1)12..52170stxx1223100xx(2-2)125150xx120,0xx这是一个典型的线性规划问题，其中“s.t”为“subjectto”的缩写，意为“受限于”。2.1系统最优化理论例2-2某企业共有m个生产基地生产同一种产品，产量分别为12,,maaa。该产品主要销售地n个，销量分别为12,,nbbb。将产品从第i个产地运到第j个销地的单位运输成本为ijc，对应的运输量为,1,2,,1,2,ijximjn。问在产量与销量持平的前提下，如何设计运输方案使运费最低？2.1系统最优化理论解首先，在假设运输量为ijx的条件下其总的运费为11mnijijijcx。其次，要考虑到从任意产地运出的量要等于该产地的产量，即1,1,2,nijijxaim。第三，还要考虑到运到任意销地的量要等于该销地能销出的量，即1,1,2,mijiixbjn。最后，也要考虑到ijx的产品数量属性，即0,1,2,,1,2,ijximjn，因此，该运输方案可由以下模型求解得到：2.1系统最优化理论11minmnijijijcx（2-3）11..,1,2,,1,2,0,1,2,,1,2,nijijmijjiijstxaimxbjnximjn(2-4)将上述方程约束条件部分的第一式两边i求和，第二式两边对j求和，有：1111mmnniijjiijjaxb（2-5）即意味着产量与销量持平（或称为产销平衡）。该问题又称为运输规划问题。2.1系统最优化理论上述两个例子表明，线性规划模型由三个基本要素构成：（1）决策变量，如例2-1中的1x和2x，例2-2中的,1,2,,1,2,ijximjn。决策变量是问题中要确定的未知量，决策者通过调控决策变量来选取不同的方案、设计、措施以达到最优目的。（2）目标函数，如例2-1中的12max1018xx,例2-2中的11minmnijijijcx。目标函数通常是决策变量的函数，表达了“何为最优”的准则和目标，规定了优化问题的实际意义。2.1系统最优化理论（3）约束条件，如例2-1和例2-2中由“s.t”规定的部分。约束条件指决策变量取值时受到的各种资源和条件的限制，表达了一种“有条件优化”的概念，通常为决策变量的等式或不等式方程。如果决策变量的取值是连续的，且目标函数和约束条件都是决策变量的线性函数，则称为线性规划问题。如果决策变量的取值为整数点，则称为整数规划问题；如果部分决策变量取值连续而其余取值为整数，则称为混合整数规划问题；如果目标函数和约束条件中存在任何的非线性因子，则称为非线性规划问题。2.1系统最优化理论根据实际求解问题的不同，线性规划模型往往有多种表达形式。为便于讨论和制定统一求解方法，人们规定了线性规划问题的标准方程形式：1122minnncxcxcx（2-6）1111221121122222112212..,,,0nnnnmmmnnmnstaxaxaxbaxaxaxbaxaxaxbxxx(2-7)2.1系统最优化理论其中，ix为决策变量，,,iijjcab为实常数且0,1,2,,1,2,jbimjn。利用向量和矩阵符号可以将上述标准形式简写为minTCX(2-8)..0stAXbX(2-9)2.1系统最优化理论其中，A为矩阵，b、C、X均为向量：111212122212121212nnmmmnTmTnTnaaaaaaAaaabbbbCcccXxxx式中上脚标T为转置。2.1系统最优化理论线性规划问题的分析讨论能采用标准形式的前提是任何线性规划模型均能等价地化为标准形式，这可以通过如下的形式变换实现。（1）对于minTCX(2-10)..0stAXbX(2-11)引进松弛变量12,,TmYyyy,可得等价的minTmCXOY..,0stAXYbXY2.1系统最优化理论对应于标准型的矩阵为mAI,对应于目标函数的系数向量为mCO，决策变量为mn个，即：1minTCZ（2-12）1..0stAZbZ（2-13）式中，1mCCO，XZY，1mAAI，mI为m维单位矩阵，mO为m维零向量。2.1系统最优化理论2）若约束条件为AXb且其余不变，则有AXYb(3)对于目标函数求极大的情况maxTCX..0stAXbX则化为等价的minTCX..0stAXbX2.1系统最优化理论（4）如果在某个实际的线性规划问题中，对一部分变量不要求非负约束，例如x1可取-到+间的任意值，则对此变量1x，可引入两个只取正值的虚拟变量11,0uv,令111xuv,并在相应的目标函数和约束条件中均以11uv代替1x,则非负约束成为112,,,,0nuvxx，变量个数为n+1。2.1系统最优化理论例2-3将下列线性规划模型转化为标准形式123min23xxx（2-14）12312312312..72325,0stxxxxxxxxxxx(2-15)2.1系统最优化理论解对约束条件的前面两个方程分别引入松弛变量670,0xx，且规定670cc；对约束条件的第三个方程两端同乘以－1；再令345xxx并增加条件45,0xx。这样，上述线性规划模型化为标准形式：1245min233xxxx（2-16）12456124571245124567..723225,,,,,0stxxxxxxxxxxxxxxxxxxxx(2-17)2.1系统最优化理论目前，线性规划问题的求解基本采用两种方法：低维线性规划（如两个决策变量）问题的图解求法和高维线性规划（三个决策变量以上）问题的单纯形求法，并且随着计算机软件技术的迅速发展，已有许多性能优良的商品化单纯形算法软件。一般，不论是线性规划还是下面将要讨论的整数规划、非线性规划，满足约束条件的决策变量向量12,,TnXxxx在n维空间中构成的点的集合称为解的可行域，而可行域中使目标函数达到最优的解点称为最优解，相应于最优解的目标函数值称为最优值。对线性规划问题来说，如果仅含有两个决策变量，则其可行域可以在平面上画出，最优解可由图解法确定。2.1系统最优化理论用图解法求解线性规划问题时不必将线性规划模型化为标准形式，其求解过程一般经历以下几步：以两个决策变量为轴在平面上建立直角坐标系；图示由线性等式和不等式构成的约束条件，标出可行域；图示并移动目标函数，寻找最优解。2.1系统最优化理论例2-4用图解法解下列线性规划12min4xx（2-18）121212..42,0stxxxxxx(2-19)2.1系统最优化理论解（1）以12,xx为坐标轴画出直角坐标系；（2）分别画出124xx，122xx，10x，20x四条直线，则该问题的可行域为这四条直线包围的内部区域s,如图2-1阴影部分所示。（3）目标函数的等值线方程为124xxz。因为要找的最优解在可行域内使目标函数具有最小值，所以让等值线124xxz沿z减小的方向在可行域内尽量平行移动，直到图中121,3xx的位置，如果再移动就移出了可行域s。于是，点（1，3）即为问题的最优解，目标函数的最优值为－13。2.1系统最优化理论1x2x124,13xxzz124,0xxzzo(1,3)(4,0)(0,2)S122xx124xxz减少方向图2-1图解法求解线性规划2.1系统最优化理论2.1.2整数规划许多实际问题的求解中，都要求部分甚至全部决策变量取整数值，如一台设备、五个人等，这类数学规划问题称为整数规划，其中，要求全部决策变量都必须取整数值的称为纯整数规划；部分决策变量取整数值的称为混合整数规划。有时，要求决策变量为只能取0或1的逻辑变量，则称为0－1规划。2.1系统最优化理论例2-5某厂生产A1和A2两种产品，需要经过B1、B2、B3三道工序加工。单件工时和利润以及各工序每周工时定额见表2-1。问工厂应如何安排生产才能使总利润最大？表2-1工厂加工条件与利润B1B2B3利润（元/件）A10.30.20.325A20.70.10.540工时定额（小时/周）2501001502.1系统最优化理论解设工厂每周生产A1产品1x件，A2产品2x件。则按工时定额要求，对B1工序来说，有120.30.7250xx同理，对于B2工序和B3工序，有120.20.1100xx和120.20.5150xx另外，由于1x为A1的件数，因此10x且只能取整数；同样，20x且只能取整数。2.1系统最优化理论按表2-1的最后一栏的利润系数，生产1x件A1和2x件A2所能获取的总利润为122540xx,因此，该问题的数学模型为：12max2540xx(2-20)12..0.30.7250stxx120.20.1100xx120.20.5150xx(2-21)10x，20x且取整数这是一个纯整数规划问题。2.1系统最优化理论例2-6背包问题：一个经典的0-1规划问题一个背包的总容积为V，现要在n种物品中选装。设物品j的重量为jw，体积为,1,2,jvjn。问如何装包，使得既不超过背包的容积，又使装的总重量最大。这一问题有广泛的应用背景，如装集装箱、装船、装车等。2.1系统最优化理论解设针对于物品j，变量01jx未装入背包物品被装入背包物品jjj=1,2,……n则所有被选装物品的总体积为1njjjvx，总重量为1njjjwx，该问题的数学模型为：1maxnjjjwx（2-22）1..0,1,1,2,nj