研究生运筹学考试题及其考试答案

一、解：121284xxx1242xx*243214Z1212233xxxx123212xx*33192224Z二、（10分）证明：若ˆX、ˆY分别是原问题和对偶问题的可行解。那么ˆˆ0ssYXYX,当且仅当ˆX、ˆY为最优解。证明：min,0,0SSSSmaxzCXYbAXXbYAYCXXYY设原问题和对偶问题的标准关系是原问题对偶问题将原问题目标函数中的系数向量C用C=YA-YS代替后，得到z=(YA−YS)X=YAX−YSX将对偶问题的目标函数中系数列向量b，用b=AX+XS代替后，得到w=Y(AX+XS)=YAX+YXSˆˆˆˆˆˆˆˆ;,4,4ˆˆ2152160,0SSSSYX0,YX0YbYAXCXXYCXYAXYbYXYX若则由性质（），可知是最优解。又若分别是原问题和对偶问题的最优解，根据性质（），则有由（），（）式可知，必有三、1）（5分）写出下列线性规划问题的对偶问题123123123123123Minzxx2x2x3x5x23xx7x3s.tx4x6x5x,x,x0解：123123123123123Maxw2y3y5y2y3yy13yy4y1s.t5y7y6y2y0,y,y02）（5分）试写出下述非线性规划的Kuhn-Tucker条件并求解2()(4)15Minfxxx解：先将该非线性规划问题写成以下形式212min()(4)()10()50fxxgxxgxx写出其目标函数和约束函数的梯度：12()2(4),()1,()1fxxgxgx对第一个和第二个约束条件分别引入广义拉格朗日乘子，设K-T点为X*，则可以得到该问题的K-T条件。该问题的K-T条件为：**12*1*2**122(4)0(1)0(5)0,0xxx为解上述方程组，考虑以下几种情形：(1)令**120,0，无解。(2)令**120,0，解之，得*11,6x，不是K-T点。(3)令**120,0，解之，得*25,4x，不是K-T点。(4)令**120，解之，得4x此为K-T点，其目标函数值()0fx由于该非线性规划问题为凸规划，故*4x就是其全局极小点。该点是可行域的内点，它也可直接由梯度等于零的条件求出。四、（10分）试用对偶单纯形求解下列线性规划问题12312312312331420Minzxxxxxxxxxx,x,x解：先将此问题化成下列形式，以便得到对偶问题的初始可行基12312341235123453142,,0Maxzxxxxxxxxxxxx,x,xxxcj→-1-1-100CBXBbx1x2x3x4x500x4x5-1-2-31-1[-4]-1-11001cj-zj-1-1-100cj→-1-1-100CBXBbx1x2x3x4x50-1x4X2-1/21/2-11/41/401-5/4-1/4101/4-1/4cj-zj-10-10-1/4cj→-1-1-100CBXBbx1x2x3x4x5-1-1X1X22/115/1110015/11-4/11-4/111/11-1/11-3/11cj-zj00-10/11-3/11-4/11*(211,511)TX五、（10分）用两阶段法求解下列线性规划问题，并指出属于哪一类解：131234123552162210,1,,5iMinzxxxxxxxxxxxi解：第一阶段6712346123571234567min6221,,,,,,0xxxxxxxxxxxxxxxxxxx目标函数约束条件cj→0000011θiCBXBbx1x2x3x4x5x6x71X621-1【6】-10101/31X711120-1011/2cj-zj-208110001X3X71/31/31/62/3-1/6【4/3】10-1/61/30-11/6-1/3011/4cj-zj-2/3-4/30-1/314/3000X2X31/43/81/21/410011/4-1/8-3/4-1/8-1/41/83/41/8cj-zj0000011X2=1/4X3=3/8X1=X4=X5=X6=X7=0W*1131521244z*W=0进行第二阶段的计算cj→502100θiCBXBbx1x2x3x4x5210X3X23/81/41/4【1/2】0110-1/81/4-1/8-3/43/21/2cj-zj-1/40021/821/8215X3X11/41/201-1/2210-1/41/21/4-3/2cj-zj01/2011/49/4*1100024Tx*1131521244z有唯一解六、解：18221620242319171526292527242218172028192216232615min1615221715260488420173520103112718110160487420163520003112618110ⓞⓞⓞⓞⓞ1648742116352311261811未被覆盖的最小元素为1，打行减1，列加1164974212524131135710ⓞⓞⓞⓞⓞⓞ0010000010000011000001000ijxminz=16+15+22+18+16=87七、解：122122()(224,42)24TfxxxxxA(0)(0)(0)(0)300()(624,46)()122Txfxpfx(0)(0)0(0)(0)0022()1220402242TTfxppAp(1)(0)(0)0330131242xxp(1)1()634660Tfx(1)(1)0(0)(0)1100()()10()()4022TTfxfxfxfx(1)(1)(0)00101()10242pfxp(1)(1)1(1)(1)1101()211221112242TTfxppAp(2)(1)(1)131433222xxp(2)0()844880Tfx(2)2||()||0fx故(*)(2)42xx为极小值点。八、解：构造障碍函数212112(,)2lnlnxxxpxrxxrr求偏导数得12112121xrprxxxx22122prxxx令120ppxx解得111618rx212411632rrx如此得最优解min01161124116(,)(0,0)832limTTrrrrx九、解：设12,xx为甲和乙的生产量，并赋予这三个目标123,,ppp为三个优先因子该模型为1211122212331268480106580801008000,0;,0;0(1,2,3)iiiixxddxxddxxddxxddddi