线性规划与计算复杂性简介

《线性规划与计算复杂性简介》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划与计算复杂性简介浙江大学数学建模实践基地1§5.1线性规划问题一、线性规划的实例与定义二、线性规划的标准形式三、线性规划的图解法四、基本可行解与极点的等价定理五、求解线性规划的单纯形法六、初始可行解的求法——两段单纯形法§5.2运输问题一、运输问题的数学模型三、最优性判别二、初始可行解的选取§5.3指派问题一、指派问题的数学模型二、求解指派问题的匈牙利算法§5.4计算复杂性问题的提出一、P类与NP类，NP完全性二、有关离散问题模型及其算法的几点附加说明2§5.1线性规划问题在人们的生产实践中，经

2、常会遇到如何利用现有资源来安排生产以取得最大经济效益的问题，此类问题构成了运筹学的一个重要分支——数学规划，而线性规划（LinearProgramming,简记LP）则是数学规划的一个重要部分。自从1947年G·B·Dantzig提出求解线性规划的单纯形方法以来，线性规划在理论上日趋成熟，在应用上日趋广泛，已成为现代管理中经常采用的基本方法之一。3一.线性规划的实例与定义例5.1某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用A、B机器加工，加工时间分别为每台2小

3、时和1小时；生产乙机床需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各多少台，才能使总利润最大？4例1的数学模型：设该厂生产x1台甲机床和x2台乙机床时总利润最大，则x1、x2应满足max4x1+3x2s.t2x1+x2≤10x1+x2≤8(5.1)x2≤7x1,x2≥0（5.1）式中4x1+3x2表示生产x1台甲机床和x2台乙机床的总利润，被称为问题的目标函数，当希望使目标函数最大时，记为max；反

4、之，当希望使目标函数最小时，记为min。（5.1）中的几个不等式是问题的约束条件，记为S.t（即Subjectto）。由于（5.1）式中的目标函数及约束条件均为线性函数，故被称为线性规划问题。总之，线性规划问题是在一组线性约束条件的限止下，求一线性目标函数最大或最小的问题。5二、线性规划的标准形式例5.2minS.ti=1,…,mxj≥0,j=1,…,n线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件可以是不等式也可以是等式，变量可以有非负要求也可以没有非负要求（称这样的变量为自由变量）。为

5、了避免这种由于形式多样性而带来的不便，规定线性规划的标准形式为利用矩阵与向量记为minz=CTxS.tAx=bx≥0（5.3）其中C和x为n维列向量，b为m维列向量，b≥0，A为m×n矩阵,m

6、i≥0。若第i个约束为ai1x1+…+ainxn≥bi，可引入剩余量yi，将不等式化为ai1x1+…+ainxn－yi=bi，且yi≥0。（3）若xi为自变量，则可令,其中、≥0例如例5.1并非标准形式，其标准形式为min―4x1―3x2s.t2x1+x2+x3=10x1+x2+x4=8x2+x5=7x1,x2,x3,x4,x5≥07图5.1对于例5.1，显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为x*=(2,6)T，最优目标值z*=26。三、线性规划的图解法为了了解线

7、性规划问题的特征并导出求解它的单纯形法，我们先应用图解法来求解例5.1。满足线性规划所有约束条件的点称为问题的可行点（或可行解），所有可行点构成的集合称为问题的可行域，记为R。对于每一固定的值z，使目标函数值等于z的点构成的直线称为目标函数等位线，当z变动时，我们得到一族平行直线（图5.1）。8上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的n维空间中，满足一线性等式aix=bi的点集被称为一个超平面，而满足一线性不等式aix≤bi（或aix≥bi）的点集被称为一个半空间（其中ai为

8、一n维行向量，bi为一实数）。若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。易见，线性规划的可行域R必为多胞形（为统一起见，空集Φ也被视为多胞形）。（1）可行域R可能会出现多种情况。R可能是空集也可能是非空集合，当R非空时，它必定是若干个半平面的交集（除非遇到空间维数的退化）。R既可能是有界区域，也可能是无界区域。（2）在R非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其目标函数值无界）。（3）若线性规划存在有