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

《研究生运筹学考试题及其考试答案.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一、解：二、（10分）证明：若、分别是原问题和对偶问题的可行解。那么,当且仅当、为最优解。证明：将原问题目标函数中的系数向量C用C=YA-YS代替后，得到z=(YA−YS)X=YAX−YSX将对偶问题的目标函数中系数列向量b，用b=AX+XS代替后，得到w=Y(AX+XS)=YAX+YXS三、1）（5分）写出下列线性规划问题的对偶问题解：2）（5分）试写出下述非线性规划的Kuhn-Tucker条件并求解解：先将该非线性规划问题写成以下形式写出其目标函数和约束函数的梯度：对第一个和第二个约束条件分别引入广义拉格朗日乘子，设K-T点为X*，则可

2、以得到该问题的K-T条件。该问题的K-T条件为：为解上述方程组，考虑以下几种情形：(1)令，无解。(2)令，解之，得，不是K-T点。(3)令，解之，得，不是K-T点。(4)令，解之，得此为K-T点，其目标函数值由于该非线性规划问题为凸规划，故就是其全局极小点。该点是可行域的内点，它也可直接由梯度等于零的条件求出。四、（10分）试用对偶单纯形求解下列线性规划问题解：先将此问题化成下列形式，以便得到对偶问题的初始可行基cj→-1-1-100CBXBbx1x2x3x4x500x4x5-1-2-31-1[-4]-1-11001cj-zj-1-1-1

3、00cj→-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五、（10分）用两阶段法求解下列线性规划问题，并指出属于哪一类解：解：第一阶段cj→0000011θiCBXBbx1x2x3x4x5x6x71X621-1【6】-10101/31X71

4、1120-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=0进行第二阶段的计算cj→502100θiCBXBbx1x2x3x4x5210X3X23/81/41/4【1/2】0110-1/81/4-1/8-3/43/21/2c

5、j-zj-1/40021/821/8215X3X11/41/201-1/2210-1/41/21/4-3/2cj-zj01/2011/49/4有唯一解六、解：未被覆盖的最小元素为1，打行减1，列加1=16+15+22+18+16=87七、解：故为极小值点。八、解：构造障碍函数求偏导数得令解得如此得最优解九、解：设为甲和乙的生产量，并赋予这三个目标为三个优先因子该模型为