第1章 线性规划.doc

第1章 线性规划1.数学模型(Mathematic Model)：为了解决实际问题，将问题的目标以及全部的约束条件表示的数学表达式。2.线性规划模型(Linear program Model)：由决策变量、目标函数、约束条件三要素构成的一种数学模型。要求目标函数是决策变量的线性函数、约束条件是决策变量的线性不等式组、所有变量非负。3.决策变量(Decision Variable)：数学模型中的待定未知的可控因素。4.目标函数(Objective Function)：表示目标的决策变量的函数，通常求最大值或最小值。5.约束条件(Constraint) ：用变量表示的限制、修饰数学模型的等式或不等式。6.标准型(Standard Form)：满足下列4个条件的线性规划模型：（1）目标函数求最大值；（2）约束条件为等式方程；（3）决策变量非负（4）资源限量非负。7.图解法(Graphical Method)：在平面直角坐标系中作图解线性规划的方法。8.基（Basis）：设线性规划的标准型为 式中A是mn矩阵，mn并且r（A）=m，显然A中至少有一个mm子矩阵B，使得r（B）=m。系数矩阵A中m阶方阵B满足r（B）=m，则称B是线性规划的一个基（或基矩阵）。9.基向量(Basic Vector)：基矩阵中的列向量。10.非基向量（NonBasic Vector）：系数矩阵A中除基向量外其它列向量。11.基变量(Basic Variable)：基向量对应的变量。12.非基变量(Nonbasic Variable)：非基向量对应的变量。13.可行解(Feasible Solution)：满足线性规划所有约束条件的解。14.可行域(Feasible Region)：全部可行解的集合。 15.基本解(Basic Solution)：一确定的基B，令非基变量等于零，利用式（1.2）解出基变量，则这组解称为基的基本解。16.基本可行解(Basic Feasible Solution)：若基本解是可行解则称为是基本可行解（也称基可行解或基解）。17.最优解(Optimal Solution) ：式（1.1）的可行解称为最优解，即使得目标函数达到最大值的可行解就是最优解。18.基本最优解(Basic Optimal Solution)：最优解是基本解。19.唯一最优解(Unique Optimal Solution)：线性规划只有一个最优解。判断方法：最优表中所有非基变量的检验数非零,则线规划具有唯一最优解。20.多重最优解 (Alternative Optimal Solutions)：线性规划存在多于一个解使得目标函数取得最优值。判断方法：最优表中存在非基变量的检验数为零,则线性规划具有多重最优解。21.无界解(Unbound Solution)：对于求最大值（最小值）问题，解的值可以无限扩大（缩小）时仍然满足约束条件的解。判断方法：某个k0且aik（i=1，2,m）则线性规划具有无界解。22.无可行解(Infeasible Solution)：没有满足全部约束条件的解。判断方法：（1）当用大M单纯形法计算得到最优解并且存在人工变量大于0时，则表明原线性规划无可性解；（2）当第一阶段的最优目标值W0时，则原问题无可行解。23单纯形法（Simplex Method）：先求出一个初始基可行解并判断它是否最优，若不是最优，再一个基可行解并判断，直到得出最优解或无最优解。它是一种不断逼近最优解的迭代方法，普通单纯形法、大M单纯形法、两阶段单纯形法、对偶单纯形法统称为单纯形法。24.最小比值(Minimal Proportion)：常数向量与进基变量的列向量系数的正数的最小比值。最小比值对应行的变量出基，即用于选出基变量。25.进基变量(Entering Variable)：选一个k0的非基变量xk换成基变量，称为进基变量。26.出基变量(Leaving Variable)：选一个能使所有变量非负的基变量xl换成非基变量，称为出基变量。出基变量由最小比值确定。27.松弛变量(Slack Variable):加到小于等于形式的约束条件左边，使其两边相等的变量。28.剩余变量(Surplus Variable): 在大于等于形式的约束条件左边减去，使其两边相等的变量。29.人工变量（Artificial Variable）：为建立一个初始基本可行解人为加入的一个变量，对原线性规划问题没有实际意义。30.大M法(Big M Method)：约束条件加入人工变量后，为了使人工变量出基，求极大值时，将目标函数变为式中M为很大的正数，因而MRi为很小的负数，在迭代过程中，Z要达到极大化，Ri就会很快出基求极小值时，将目标函数变为同理，在迭代过程中，Z要达到极小化，Ri就会迅速出基31.两阶段法(TwoStage Method)：将人工变量从基变量中换出，以求出原问题的初始基本可行解。将原问题分成两个阶段求解，第一阶段的目标函数是约束条件是加入人工变量后的约束方程，当第一阶段的最优解中没有人工变量作基变量时，得到原线性规划的一个基本可行解，第二阶段就以此为基础对原目标函数求最优解 32.退化(Degeneracy)：有一个或多个基变量等于零。33.凸集(Convex