《高级算法设计》课件 第1章 线性规划

高级算法设计与分析线性规划林海lin.hai@B站：foretmer基本概念基本概念基本概念线性规划的形式：线性规划：定义标准型和松弛型标准型和松弛型非标准型目标函数不是最大化，而是最小化约束条件是大于等于约束约束条件是等式约束;存在一些变量没有非负约束标准型和松弛型非标准型例子标准型和松弛型标准型和松弛型标准型和松弛型标准型：标准型和松弛型松弛型：在松弛型中，等式左边的变量x4,x5,x6被称为基本变量，等式右边的变量x1,x2,x3被称为非基本变量矩阵形式：标准型和松弛型图解法将可行域为：ABCDEF的边界和内部，A,

B,

C,

D,

E,

F称为极点图解法单纯形法如果我们能够将上述目标函数的所有变量的系数全部转换为负数单纯形法步骤松弛基本解为(x1,x2,x3,x4,x5,x6)=(0,0,13,10,5,2)单纯形法步骤基本解为(x1,x2,x3,x4,x5,x6)=(0,0,13,10,5,2)在此基本解下，目标函数的值为0通过增大x1或x2来使目标函数变大单纯形法步骤目标函数中x1的系数大于x2，选择增大x1约束条件4的约束最紧凑单纯形法步骤约束条件4变为用这个表达式替换目标函数和其他约束条件中的x1

单纯形法步骤目标函数的值为16单纯形法步骤用这个表达式替换目标函数和其他约束条件中的x2

单纯形法步骤单纯形表注意表格中的值是变量系数的值（取负），目标函数变量的系数同样取负单纯形表1.从目标函数中选择一个需要变大的变量（系数最小）x12.找出最紧凑约束最紧凑约束是b/(x1系数)最小的约束（第4行约束）3.x1变量替入为基变量，而原来的基变量x6替出为非基变量单纯形表1.从目标函数中选择一个需要变大的变量（系数最小）x12.找出最紧凑约束最紧凑约束是b/(x1系数)最小的约束（第4行约束）3.x1变量替入为基变量，而原来的基变量x6替出为非基变量单纯形表4.用x1的表达式替换目标函数和其他约束条件中的x1

高斯消元单纯形表4.用x1的表达式替换目标函数和其他约束条件中的x1

高斯消元重复上述步骤单纯形表重复上述步骤最紧凑约束为第一行约束，对第一行进行替入和替出操作单纯形表重复上述步骤用第一行约束对所有其他约束行和目标函数行进行x2高斯消元对偶对偶性是线性规划最重要的内容之一每个线性规划（LP1）必然有与之相伴而生的另一个线性规划问题（LP2），即任何一个求maxz的LP1都有一个求minw的LP2对偶对偶矩阵形式对偶例子对偶对偶规则（标准型）原问题的目标函数是最大化，对偶问题的目标函数是最小化，原问题的约束条件是小于等于，对偶问题的约束条件是大于等于原问题约束条件的个数(m)决定对偶问题变量的个数，且第一个约束条件对应第一个变量，第二个约束条件对应第二个变量，以此类推对偶对偶规则（标准型）原问题变量的个数(n)决定对偶问题约束条件的个数，且第一个变量对应第一个约束条件，第二个变量对应第二个约束条件，以此类推对偶问题的目标函数中每个变量的系数由其对应原问题中约束条件b值决定对偶问题约束条件的c值是其对应变量(原问题)在目标函数的系数，约束条件中各变量的系数是其对应变量(原问题)在约束条件中的系数对偶对偶：例子对偶：例子对偶是怎么来的设线性规划的原始问题：转化为优化问题的标准形式对偶是怎么来的对偶是怎么来的对偶是怎么来的对偶问题可以化为对偶是怎么来的如果对原问题按照“原问题和对偶问题的转换”表可得：等价对偶例子：矩阵博弈矩阵博弈：猜硬币，两个参与者分别同时从两个硬币(一元和两元)中选取一个让对方猜，如果都猜错或都猜对，继续玩，如果只有一方猜对，则猜对一方赢得此次双方的所有硬币对偶例子：矩阵博弈矩阵博弈：猜硬币，收益矩阵如下：行和列表示（player1和player2）的策略（选取的硬币和猜对方的硬币），如（1，2）表示选取硬币1元，猜对方选取的是2元；矩阵的值表示列player2的收益

对偶例子：矩阵博弈对偶例子：矩阵博弈对偶例子：矩阵博弈对偶例子：矩阵博弈对偶例子：矩阵博弈对偶例子：矩阵博弈即player2

LP问题C的对偶问题即为player1的LP问题R对偶性质线性规划标准式对偶性质可得：即：对偶性质：弱对偶性对偶性质：强对偶性和互补松驰性对偶性质：互补松驰性如果原问题和对偶问题得出的解满足互补松弛性，则为最优解互补松驰性例子互补松驰性例子原问题的对偶问题为互补松驰性例子互补松驰性例子原问题的对偶问题为互补松弛性可得互补松驰性例子整数规划当变量的取值从实数变为整数后，这个问题到底是变难了，还是变容易了?整数规划松弛整数规划：分支限界分支限界：例子对线性规划问题求解，得最优解为x1=2.5,x2=2.25，目标函数为21.5分支限界：例子此时，可以对x1进行分支，也可对x2进行分支。对x1进行分支，则分为x1≤2和x1≥3两部分。

分支限界：例子对左边分支(x1≤2)求解得x1=2,x2=2.5，目标函数为20对右边分支(x1≥3)求解得x1=3,x2=1.5，目标函数为21分支限界：例子接着搜索节点3，对x2进行分支，则分为x2≤1和x2≥2两部分分支限界：例子对左边分支(x2≤1)求解得x1=3.3,x2=1，目标函数为20.7而右边分支(x2≥2)无可行解。分支限界：例子接着搜索节点4，对x1进行分支，则分为x1≤3和x1≥4两部分分支限界：例子对左边分支(x1≤3)求解得x1=3,x2=1，目标函数为19，找到整数解，结束搜索而右边分支(x1≥4)无可行解分支限界：例子因为节点2的上限大于目前找到的最优值19，需要继续搜索，对x2进行分支，则分为x2≤2和x2≥3两部分分支限界：例子对左边分支(x2≤2)求解得x1=2,x2=2，目标函数为18而右边分支(x2≥3)无可行解最终的最优解为x1=3,x2=1，最优值为190-1整数规划整数规划的一个特列是0-1整数规划，也就是参数的取值只能是0或1。很多算法问题都可以建模成0-1整数规划问题，如0-1背包问题、任务分配、集合覆盖等问题。0-1整数规划：建模0-1背包问题中，设背包的承重为C，共n个物品，每个物品的重量和价值分别为wi和vi，则问题建模为0-1整数规划：建模在应用中，有时会遇到变量可以取多个整数值的问题。如果用0-1变量来表示，也可以用一组0-1变量来取代。

如x取0－9之间的任意整数时。

x=20x0+

21x1+

22x2+

23x3£90-1整数规划：建模含有相互排斥的约束条件的问题（1）两个约束中，只有一个起作用。例：a11x1+a12x2<B1a21x1+a22x2<B2

解：引入0-1变量Y1,Y2和足够大的正数M，则a11x1+a12x2<B1+M1Y1a21x1+a22x2<B2+M2Y2Y1+Y2=10-1整数规划：建模某企业生产产品的费用如下，建立0-1规划模型单耗量产品资源IIIIII资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价810120-1整数规划：建模解：设Xj是第j种产品的产量。Yj是0－1变量，表示是（Yj=1）否（Yj=0）生产第j种产品。maxZ=4X1+5X2+6X3–100Y1

–150Y2

–200Y32X1+4X2+8X3£5002X1+3X2+4X3£300X1+2X2+3X3£100X1£

M1Y1X2£

M2Y2X3

£

M3

Y3X1,

X2,

X3³0整数Y1,Y2,Y3为0－1变量。

s.t.0-1整数规划：隐枚举法0-1整数规划：隐枚举法0-1整数规划：隐枚举法0-1整数规划：隐枚举法原始-对偶算法通过对偶问题来求解原问题的最优解或者近似解，统称为原始-对偶算法对于0-1整数规划问题，是很难通过互补松弛性来求得最优解，但我们依然可以通过原问题(Primal)和对偶问题(Dual)的弱对偶性来求得一个近似解原始-对偶算法原始-对偶算法原始-对偶算法原始-对偶算法的应用：顶点覆盖顶点覆盖问题是指从图中选取最少的顶点，这些顶点能够覆盖图中所有的边(一个顶点覆盖一条边，指这个顶点和这条边相连)。数学模型。设G=(V,E)，节点个数为n，边的条数为m，令xv

为0-1变量，0代表不选取顶点v，1代表选取顶点v，则顶点覆盖的0-1整数规划模型:原始-对偶算法的应用：顶点覆盖顶点覆盖问题是指从图中选取最少的顶点，这些顶点能够覆盖图中所有的边(一个顶点覆盖一条边，指这个顶点和这条边相连)。对偶：图的最大匹