运筹学复习

运筹学复习1、线性规划的基本概念2、单纯形法和对偶单纯形法3、对偶线性规划4、运输问题5、目标规划6、整数规划7、网络最大流问题8、网络最短路径问题第一章线性规划模型和单纯形法线性规划问题一般模型目标函数：max，min约束条件：≥,=,≤变量符号：≥0,unr,≤0线性规划的标准形式目标函数：min约束条件：=变量符号：≥0unr,0)(Xb),(AX.t.sXCzmax(min)T0XbAX.t.sXCzminT非标准形式转化为标准形式极大化目标函数转化为极小化：目标函数系数变号约束条件是不等式转化为等式：“≤”约束加上松弛变量“≥”约束减去松弛变量变量没有符号限制转化为变量非负：没有符号限制的变量用两个非负变量的差表示例如:maxz=3x1+4x2-2x3+5x4s.t4x1-x2+2x3-x4=4x1+x2+3x3-x4≤14-2x1+3x2-x3+2x4≥3x1≥0,x2≥2,x3≤0,x4:unr线性规划的图解–画约束直线–确定满足约束条件的半平面–所有半平面的交集—凸多边形—线性规划的可行域–画两条目标函数等值线–确定目标函数优化的方向–平行移动目标函数等值线–得到线性规划的最优解线性规划问题的概念基：设标准形式的LP问题的约束方程组的秩为M，B是系数矩阵A中的M阶满秩子矩阵，则称B是该LP问题的一个基。基变量：B中的每一个列向量成为基向量，对应的变量为基变量，共有M个。非基变量：B以外的列向量称为非基向量，对应变量成为非基变量，共有N-M个。基础解：对应基B，令所有的非基变量为零，求解约束方程组AX=b，可惟一得出基变量的一组值，这样得到的N个变量的一组解成为一个“基础解”。基础可行解：如果一个基础解中的所有变量都大于或等于0，则称这个基础解为“基础可行解”。退化解：基解中的非零分量的个数小于M个时，即某个基变量为零时，此时为退化解。线性规划的基本定理线性规划的基础可行解就是可行域的极点。线性规划的基本概念minz=x1+2x2s.t.x1+x2≥4(1)-x1+x2≥2(2)x2≤5(3)x1,x2≥0OABCDEFG41234123x1x2x3=0x4=0x2=0x1=0x5=0引进松弛变量x3,x4,x5minz=x1+2x2s.t.x1+x2+x3=4-x1+x2-x4=2x2+x5=5x1,x2x3,x4,x5≥0基础解OABCDEFGBEF四边形BEFG基础可行解可行域目标函数等值线….最优解B5GA不是可行解，是由于变量（）0。C不是可行解，是由于变量（）0。满足x1，x2，x5≥0，x3,x4≤0的区域是（）。满足x1，x2，x4，x5≥0，x3≤0的区域是（）。A点对应的解，基变量为（），非基变量为（）。F点对应的解，基变量为（），非基变量为（）。G点对应的解，基变量为（），非基变量为（）。x1x4x5x2x3x4x1x2x3x2x3x1x5x4x5x4x3OABCBCEOABCDEFG41234123x1x2x3=0x4=0x2=0x1=0x5=0OABCDFGE41234123x1x2x3=0x4=0x2=0x1=0x5=0从O点到C点的单纯形叠代，进基变量为（），离基变量为（）。从C点到B点的单纯形叠代，进基变量为（），离基变量为（）。从B点到E点的单纯形叠代，进基变量为（），离基变量为（）。在B点上,对偶变量(w1,w2,w3,w4,w5)中大于零的变量是(),小于零的变量是(),等于零的变量()x2x4x1x3x4x1单纯形表单纯形表的结构基变量在目标函数中的系数等于0，基变量在约束条件中的系数是一个单位矩阵单纯形表的运算Step0获得一个初始的单纯形表，确定基变量和非基变量Step1检查基变量在目标函数中的系数是否等于0，在约束条件中的系数是否是一个单位矩阵Step2如果表中非基变量在目标函数中的系数全为负数，则已得到最优解。停止。否则选择系数为正数且绝对值最大的变量进基。Step3如果进基变量在约束条件中的系数全为负数或0，可行域开放，目标函数无界。停止。否则选取右边常数和正的系数的最小比值，对应的基变量离基。Step4确定进基变量的列和离基变量的行交叉的元素为“主元”，对单纯形表进行行变换，使主元变为1，主元所在列的其他元素变为0。将离基的基变量的位置用进基的非基变量代替。转Step1。单纯形法和对偶单纯形法单纯形法适用的问题约束条件全部为≤，右边常数全部为非负，对目标函数的系数没有要求。对偶单纯形法应用的条件约束条件中至少有一个是≥，相应的右边常数为非负，目标函数系数全部为非负。minz=3x1-2x2s.t.x1+2x2≤122x1+x2≤18x1,x2≥0minz=3x1+2x2s.t.x1+2x2≥122x1+x2≤18x1,x2≥0单纯形表minz=3x1-2x2s.t.x1+2x2≤122x1+x2≤18x1,x2≥0zx1x2x3x4RHSz1-32000x3012101212/2x4021011818/1x2进基，x3离基minz=3x1-2x2s.t.x1+2x2+x3=122x1+x2+x4=18x1,x2,x3,x4≥0最优解为：(x1,x2,x3,x4)=(0,6,0,12)，minz=-12zx1x2x3x4RHSz1-40-10-12x201/211/206x403/20-1/2112zx1x2x3x4RHSz1-32000x3012101212/2x4021011818/1minz=3x1+2x2s.t.x1+2x2-x3=122x2+x2-x4=18x1,x2,x3,x4≥0对偶单纯形法的例子minz=3x1+2x2s.t.x1+2x2≥122x1+x2≥18x1,x2≥09x4=061812x1x2最优解（x1,x2,x3,x4）=（8,2,0,0）x3=0x1=0x2=0zx1x2x3x4RHS1-3-2000x30-1-210-12x40-2-101-18zx1x2x3x4RHS1-3-2000x3012-1012x40210-118约束两边同乘以-1zx1x2x3x4RHS1-3-2000x30-1-210-12x40-2-101-18-3/-2-2/-1zx1x2x3x4RHS1-3-2000x30-1-210-12x1011/20-1/29x4离基，x1进基。第二个约束两边同除以-2，得到zx1x2x3x4RHS1-3-2000x30-1-210-12x1011/20-1/29zx1x2x3x4RHS10-1/20-3/227x300-3/21-1/2-3x1011/20-1/291/33/1x3离基，x2进基消去主元所在列的其他元素，得到zx1x2x3x4RHS10-1/20-3/227x200-3/21-1/2-3x1011/20-1/29zx1x2x3x4RHS10-1/20-3/227x2001/2-1/31/61x1011/20-1/29第一个约束两边同除以-3，得到zx1x2x3x4RHS10-1/20-3/227x2001/2-1/31/61x1011/20-1/29zx1x2x3x4RHS100-1/3-4/328x2001/2-1/31/61x10101/3-2/38消去主元所在列的其他元素，得到zx1x2x3x4RHS100-1/3-4/328x2001-2/31/32x10101/3-2/38zx1x2x3x4RHS100-1/3-4/328x2001/2-1/31/61x10101/3-2/38原始问题的最优解为(x1,x2,x3,x4)=(8,2,0,0)，minz=28对偶问题的最优解为(w1,w2,w3,w4)=(1/3,4/3,0,0)maxy=28将主元所在行乘以2，得到9061812x1x2单纯形叠代的过程如下图所示x3=0x4=0x1=0x2=0人工变量法如果约束条件全为“≤”，且右边常数全为非负，则引进的松弛变量就可以作为初始的基变量，得到一个初始的基础可行解。如果约束条件有“≥”，右边常数全为非负，则需要引进人工变量，建立辅助问题。大M法的步骤引进松弛变量，使约束条件全为等式。引进人工变量，令人工变量在目标函数中的系数为大M（任意大的正数）用单纯形法求解，得到原问题的最优解。两阶段法的步骤引进松弛变量，使约束条件全为等式。引进人工变量，建立辅助问题。辅助问题的目标函数为各人工变量之和（仅含人工变量）。用人工变量作为辅助问题的初始基变量，用单纯形法求解辅助问题，得到辅助问题的最优解和最优解的目标函数值。如果辅助问题最优解的目标函数值大于0，原问题可行域为空集，无可行解。如果辅助问题最优解的目标函数值等于0，辅助问题的最优解是原问题的一个可行解。将第一阶段得到的最终表除去人工变量，将目标函数行的系数换原问题的目标函数系数，作为第二阶段计算的初始表，用单纯形法求解，得到原问题的最优解。•Maxz=4x1+5x2+x3S.t3x1+2x2+x3≥182x1+x2≤4x1+x2-x3=5X1,x2,x3≥0线形规划问题的应用•某车间有一批长度为180cm的钢管,且数量充足.为制造零件的需要,要将其截成三种不同长度的管料,分别为72cm,52cm,35cm.生产任务规定这三种不同的需要量分别不少于100,150和100根.问如何下料才能使消耗的钢管数量最少?试建立此问题的线形规划模型.第二章对偶理论和灵敏度分析对偶的定义原始问题：目标函数极大化约束条件全为≤变量全为非负对偶问题：目标函数极小化约束条件全为≥变量全为非负对偶问题MinW=bTys.t.ATy≥Cy≥0原始问题Maxz=CTXs.t.AX≤bX≥0原始问题（prime)与对偶问题之间的关系•极小化问题（min)极大化问题（max)•变量Xj≥0约束∑aijwj≤bi•Xj:unr∑aijwj=bi•Xj≤0∑aijwj≥bi•约束∑aijxj≥bi变量wj≥0•∑aijxj=biwj:unr•∑aijxj≤biwj≤0对偶问题的形成minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40≤≥=≥unr≤≥≥=≤≥x1≥0x2≤0x3:unr原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质，用表示原始问题约束条件的性质影响对偶问题变量的性质，用表示minz=CTXs.t.AX≤bX≥0maxw=bTys.t.ATy≤Cy≤0其他形式问题的对偶minz=CTXs.t.AX≥bX≥0maxw=bTys.t.ATy≤Cy≥0minz=CTXs.t.AX=bX≥0maxw=bTys.t.ATy≤Cy：unr原始——对偶关系原始问题和对偶问题可行解目标函数之间的关系z=CTX≥yTAX≥bTy=w原始问题任何一个可行解的目标函数值不小于对偶问题任何一个可行解的目标函数值原始问题和对偶问题最优解的目标函数值之间的关系z=CTX＝yTAX＝bTy=w如果原始问题和对偶问题都有最优解，它们的目标函数值相等原始问题和对偶问题最优解之间的互补松弛关系向量形式：XTYs=0YTXs=0分量形式：xjym+j=0yixn+i=0原始问题第j个变量和对偶问题的第j个松弛变量中至少有一个是0；对偶问题的第i个变量和原始问题的第i个松弛变量之间至少有一个是0。y1yiymvm+1vm+jvn+mx1xjxnun+1un+iun+m对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjvm+j=0yiun+i=0(i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个