数学建模中线性规划与目标规划的比较文档

数学建模中线性规划与目标规划的比较【摘要】Theconcepts,characteristics,modelingofthestructureandmethodstosolvethemodelaboutlinearprogrammingandgoalprogramminghavebeendiscussedandcomparedinthepaper.Thefrontmodelingmethodsalsohavebeendemonstrated.%对数学建模中的线性规划与目标规划模型的概念、特点、模型的结构以及解模的方法进行了比较．展示了较前沿的建模与解模方向。【关键词】数学模型;线性规划;目标规划;解模数学建模是指从现实对象的信息中提出数学问题，选择合适的数学方法、识别常量、自变量和因变量，引入适当的符号并采用适当的单位制，提出合理的简化假设，推导变量和常量应满足的数量关系式，表述成数学模型。笔者就数学建模中的两类规划模型：线性规划模型与目标规划模型进行分析与比较。

数学规划是运筹学学科中发展较快，应用范围广泛的数学模型，主要分为两类：一是确定某个项目任务后，研究怎样以最少的资源去完成这项任务；二是在已有资源有限的条件下，研究如何优化配置现有资源，从而获得最大利润或效益。数学规划问题可叙述为构建一个含有n个变量的目标函数z＝f（x1，x2，⋯，xn），提出关于这n个变量相关的约束性实值函数：hi（x1，x2，⋯，xn）＝0，i＝1，2，⋯，m；gi（x1，x2，⋯，xn）≤0，i＝1，2，⋯，n从而使得问题转化为求解目标函数f的极大（或极小）值问题。1.1线性规划模型的可行解和最优解定义1设线性规划模型的一般为：约束条件满足约束条件（2）的一组数（x1，x2，⋯，xn），称为该线性规划模型的可行解。上述表达式中，未知数xj称为决策变量，目标函数中xj的系数cj称为价值系数（如产品单价、单位产品成本），约束条件中xj的系数aij称为工艺技术系数（如工时、工艺转换系数），约束条件右端的常数bi称为资源限量。满足目标函数，即使得目标函数达到最大值或最小值的可行解，称为该线性规划模型的最优解。把最优解代入目标函数所得到的目标函数的最大值或最小值称为最优值。线性规划模型的全体可行解组成的集合，称为该线性规划模型的可行解域。1.2线性规划模型的标准型为讨论方便，一般要求将所构建的线性规划模型化为标准型。线性规划模型的标准型为：约束条件（s.t.）在线性规划模型的标准型中，约束条件是一组线性等式，称为约束方程组。线性规划的标准型应具有的特点是：目标函数是求最大值；约束条件为线性方程组；

未知变量x1，x2，⋯，xn都有非负限制。线性规划模型的非标准型，可以通过以下三种方法化为标准型：（1）目标函数是求最小值minZ。设minZ＝c1x1＋c2x2＋⋯＋cnxn，可设Z′＝-Z，则求最小值问题转化为求最大值问题，即将求minZ转化为求maxZ′，且maxZ′＝-c1x1＋c2x2＋⋯＋cnxn。（2）约束条件为不等式。如果约束条件为不等式，则可增加一个或减去一个非负变量，使约束条件变为等式，增加或减去的这个非负变量称为松弛变量。例如：ai1x1＋ai2x2＋⋯＋ainxn≤bi，加一个非负变量xn＋1，使不等式变为等式：ai1x1＋ai2x2＋⋯＋ainxn＋xn＋1＝bi如果约束为ai1x1＋ai2x2＋⋯＋ainxn≥bi，则减去一个非负变量xn＋1，使不等式变为等式：ai1x1＋ai2x2＋⋯＋ainxn-xn＋1＝bi（3）模型中的某些变量没有非负限制。若某个变量xj取值可正可负，这时可设两个非负变量xj′和xj″，令xj＝xj′-xj″，这样就可以满足标准型的要求。1.3求解线性规划模型的方法1.3.1图解法图解法是求解两个变量线性规划问题的一种简单直观的方法。两个变量线性规划模型的一般形式为：该线性规划模型的可行解域是所有满足约束条件的数组（x1，x2）。约束条件是一组线性等式或不等式。在几何上，两个变量的线性等式是平面上的直线。线性不等式a1x1＋a2x2≤（≥）b是半平面。可行解域就是由直线或半平面相交而成的平面区域，而每个可行解即为该平面区域上的一个点。若线性规划存在唯一最优解，则一定是可行解域的某个顶点。若两个顶点都是最优解，则这两个顶点连线上的任一点都是最优解，若可行解区域无界，则可能不存在最优解。

1.3.2单纯形法单纯形方法是1947年由G.B.Dantzig提出的一种较有效的求解线性规划问题的方法。设线性规划问题的矩阵形式为：其中，系数矩阵A的秩为m，设A中任意一个m×m非奇异子矩阵B是此线性规划问题的一个基，N是非基p2，⋯，pm），N＝（pm＋1，pm＋2，⋯，pn），相应地把X记做X＝（x1，x2，⋯，xm，xm＋1，⋯，xn）T，X中基为XB，记XB＝（x1，x2，⋯，xm）T，非基变量N＝（pm＋1，pm＋2，⋯，pn）对应的变量XN，记XN＝（xm＋1，xm＋2，⋯，xn）T，于是，则A＝（B，N），写成向量形式得B＝（p1，B＝（p1，p2，⋯，pm）对应的变量≥，因而约束条件AX＝b可写成（B，N）≥＝b，即BXB＋NXN＝b，两边同时左乘B-1，得XB＋B-1NXN＝B-1b。因此，XB＝B-1b-B-1NXN，就是用非基变量xm＋1，xm＋2，⋯，xn表示基变量x1，x2，⋯，xm的形式，相应地，也把目标函数中的C写成C＝（CB，CN），其中CB＝（c1，c2，⋯，cm），CN＝（cm＋1，cm＋2，⋯，cn），于是目标函数maxZ＝CX可写成maxZ＝（CB，CN）≥，略去符号max，并将XB代入上式，得当XN＝0时，XB＝B-1b，称为对应于基B的基础解，此时Z＝CBB-1b就是基B的目标函数值。如果B-1b≥0，即XB≥0，称XB＝B-1b，XN＝0为基B进一步满足CBB-1N-CN≥0，则对一切可行解，有Z＝CX≤CBB-1b。即表明，对应于基B的基础可行解，B为可行基。如果一个可行基础可行解，能使目标函数达到最大值，即最优解。但又因所以，CBB-1N-CN≥0与CBB-1A-C≥0等价。

因而可得以下法则：对于基B，若B-1b≥0，且CBB-1AC≥0，则对应于基B的基础解是最优解，又叫基础最优解，B为最优基。由（7）式得Z＋（CBB-1N-CN）XN＝CBB-1b，即Z＋（0，CBB-1A-C）X＝CBB-1b又由AX＝b得，B-1AX＝B-1b，把上面两式写成矩阵形式，得称T（B）为对应于基B的单纯形表，b0j（j＝1，2，⋯，n）称为检验数。定理1（最优解的判定）若T（B）中所有检验数b0j≥0（j＝1，2，⋯，n），则XB＝B-1b-B-1NXN是最优解。定理2（无最优解的判定）若T（B）中有某一个检验数b0，m＋s＜0，且在该列中的bi，m＋s≤0（i＝1，2，⋯，m），则线性规划问题无最优解。1.3.3计算软件求解法目前，求解线性规划常用的软件有LINDO和MATLAB。LINDO是“Linearinteractiveanddiscreteoptimizer”的缩写，它是解决线性规划，整数规划等规划问题的有力工具，在大型计算机上，它可用于解决50000个约束条件，200000个变量的线性规划问题。MATLAB是MatrixLaboratory（矩阵实验室）的缩写。它早期是线性代数课的教学软件，后来逐步应用于实际工程问题的计算，目前已成为工程界和应用数学人员常用的数学软件。1991年，查恩斯（A.Charnes）和库柏（W.W.Cooper）提出目标规划（goalprogramming），得到广泛重视和较快发展。目标规划在处理实际决策问题时，承认各项决策要求（即使是冲突的）的存在有其合理性；在作最终决策时，不强调其绝对意义上的最优性。由于目标规划在一定程度上弥补了线性规划的上述局限性，因此，目标规划被认为是一种较之线性规划更接近于实际决策过程的决策工具。目标规划数学模型涉及下述基本概念：

（1）偏差变量。对每一个决策目标，引入正、负偏差变量d＋和d-，分别表示决策值超过或不足目值的部分。按定义应有d＋≥0，d-≥0，d＋·d-＝0。（2）绝对约束和目标约束。绝对约束是指必须严格满足的约束条件，如线性规划中的约束条件都是绝对约束。绝对约束是硬约束，对它的满足与否，决定了解的可行性。目标约束是目标规划特有的概念，是一种软约束，目标约束中决策值的目标值之间的差异用偏差变量表示。（3）优先因子和权系数。不同目标的主次轻重有两种差别。一种差别是绝对的，可用优先因子p1来表示。只有在高级优先因子对应的目标已满足的基础上，才能考虑较低级优先因子对应的目标；在考虑低级优先因子对应的目标时，绝不允许违背已满足的高级优先因子对应的目标。优先因子间的关系为P1＞＞Pl＋1，即P1对应的目标比Pl＋1对应的目标有绝对的优先级。另一种差别是相对的，这些目标具有相同的优先因子，它们的重要程度可用权系数的不同来表示。（4）目标规划的目标函数。目标规划的目标函数（又称为准则函数或达成函数）由目标约束的偏差变量及相应的优先因子和权系数构成。由于目标规划追求的是尽可能接近各既定目标值，也就是使各有关偏差变量尽可能小，所以其目标函数只能是极小化。应用时，有三种基不希望的，因此有min｛f（d＋＋d-）｝。二是要过目标值，但允许不足目标值。这时，不希望决策值超过目标值，因此有min｛f本表达式：一是要求恰好达到目标值。这时，决策值超过或不足目标值都是求不超（d＋）｝。三是要求不低于目标值，但允许超过目标值。这时，不希望决策值低于目标值，因此有min｛f（d-）｝。除以上三种基本表达式外，目标规划的目标函数还可以有其他表达min｛f（d--d＋）｝和min｛f（d＋-d-）｝，但很少使用。2.1目标规划的一般形式目标规划数学模型的一般形式为：

模型中gk为第k个目标约束的预期目标值，Wlk-和Wlk＋为Pl优先因子对应各目标的权系数。在建立目标规划数学模型时，需要确定预期目标值、优先值和权系数等，应当综合运用各种决策技术，尽可能地减少主观片面性。2.2求解目标规划的方法对于只有两个决策变量的目标规划问题，可以用图解方法来求解。在用图解法解目标规划时，首先必须满足所有绝对约束。在此基础上，再按照优先级从高到低的顺序，逐个地考虑各个目标约束。一般地，若优先因子Pj对应的解空间为Rj，则优先因子Pj＋1对应的解空间只能在Rj中考虑，即Rj＋1哿Rj。若Rj非空，而Rj＋1为空集，则Rj中的解为目标规划的满意解，它只能保证满足P1，P2，⋯，Rj级目标，而不保证满足其后的各级目标。对于多个变量的目标规划问题，目标规划的数学模型实际上是最小化形的线性规划，可以用单纯形法求解。在用单纯形法解目标规划时，检验数是各优先因子的线性组合。因此，在判别各检验数的正负及大小时，必须注意P1＞＞P2＞＞P3⋯。当所有的检验数已满足最优性条件（cj-zj≥0）时，从最终单纯形表上就可以得到目标规划的解。由于目标规划多级多任务变量的迭代过程更繁琐，目前求解目标规划总是借助于功能更强大的MATLAB软件完成。线性规划与目标规划属于运筹学的数学模型，它们均以规划的最优解存在为前提，从规划思想上看，线性规划注重于经济问题的投入产出最大化问题，而目标规划除了要求满足投入产出模型最大化外，由于目标的高出，超出约束条件的现值，可能造成可行解的不存在，最终造成最优解的不存在。因而目标规划模型采取一些变通的办法，或者调整目标，或者放宽约束条件，以求得目标规划存在可行域的最优解。从规划的数学模型结构上看，线性规划模型显得既规范又紧致，而目标规划显得松弛与宽泛。从规划的求解方法上看，虽然线性规划与目标规划的求解都可以归结为单纯形的迭

代方法寻求最优解，但决策变量的维数较大时，造成迭代的次数增多，加大了计算的复杂程度，这对应用的计算机数学软件MATLAB提出了更高的要求，因此Karmarkav的内点算法对于求解线性规划的数学模型更具有应用型和高效性。Abstract：Theconcepts，characteristics，modelingofthestructureandmethodstosolvethemodelaboutlinearprogrammingandgoalprog