运筹学第二章作业的参考答案.doc

《运筹学第二章作业的参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章作业的参考答案4、将下面的线性规划问题化成标准形式解：将max化为min，用代替，则令，则将线性不等式化成线性等式，则可得原问题的标准形式205、用图解法求解下列线性规划问题：等值线20128X2oX1法线方向图2.1（1）解：图2.1的阴影部分为此问题的可行区域。将目标函数的等值线（为常数）沿它的负法线方向移动到可行区域的边界上。于是交点就是该问题的最优解，其最优值为36。注：用图解法求解线性规划问题的步骤①比较准确地画出可行区域；②确定等值线及其法线方向；③由max或min确定等值线的移动方向，并将其移动到可行区域

2、的边界上；④得出结论。2012、对于下面的线性规划问题，以为基写出对应的典式。解：先将方程组中基变量的系数向量化成单位向量利用线性方程组的典式，把用表示，再带入目标函数，则可得原问题相应于基的典式2016、用单纯形法求解下列线性规划问题：注（零行元素的获得）：先将目标函数化成求最小值的形式，再把所有变量移到等式左边，常数移到等式右边。则变量前的系数为零行对应的元素。(1)解：将此问题化成标准形式以为基变量，可得第一张单纯形表为RHS21-10000311100601-120101011-100120注意单纯形表的格式！注：要

3、用记号把转轴元标出来以为进基变量，为离基变量旋转得20RHS03-50-20-2004-51-30301-120101002-30-1110注：要记住在单纯形表的左边，用进基变量代替离基变量以为进基变量，为离基变量旋转得RHS000-350011-1-210100150105所以最优解为，最优值为-35。注：用单纯形法求解线性规划问题的步骤Ⅰ、将问题化成标准形式；Ⅱ、找出初始解；Ⅲ、写出第一张单纯形表，并化成典式；Ⅳ、判定和迭代。①判定：<1>最优解（检验数向量）；<2>问题无界（某个非基变量的检验数，且在典式中的系数向量）

4、②迭代步骤：<1>确定进基变量（检验数向量中最大的正分量）；<2>确定转轴元（进基变量所在的这一列中的正分量与右端向量中对应元素比值最小的）；<3>确定离基变量（转轴元所在的这一行对应的基变量）；20<4>迭代计算（利用初等行变换，将转轴元变为1，转轴元所在的这一列其它元素全部变为0）；<5>用进基变量代替离基变量。（3）解：在第三个等式两端同乘以-1，并以为基变量可得其单纯形表为RHS-11-10-110000301106012-10001010000-10000100116注：必须先将线性方程组和目标函数化成典式，再用单

5、纯形方法开始判定、迭代！将第0行的元素化为检验数可得20RHS0001010-400301106012-10001010000-10000100116由于的检验数，并且在典式中的系数向量，所以问题无界。17、用两阶段法求解下列线性规划问题：（2）解：将此问题化为标准形式添加人工变量得到辅助问题20以为基变量，可得辅助问题的单纯形表为RHS-2-4000000000-1-102-3-10102-110-1013把所在的这一行的元素化成检验数RHS-2-4000001-2-1-10052-3-10102-110-1013注：必须

6、先将线性方程组和目标函数化成典式，才可以开始判定、迭代！以为进基变量，为离基变量旋转得20RHS0-7-101020-10410010-114所以，辅助问题的最优解为，其最优值为。因此，原问题没有可行解。（4）解：将此问题化成标准形式添加人工变量得到辅助问题20以为基变量，可得辅助问题的单纯形表为RHS2-45-60000000-1-1014-28102-1234011把所在的这一行的元素化成检验数RHS2-45-60000611200314-28102-1234011以为进基变量，为离基变量旋转得20RHS-1000400

7、01004010以为进基变量，为离基变量旋转得RHS-1000000-1-10010100所以，辅助问题的最优解为，其最优值为。因此，原问题的初始解为，其第一张单纯形表为RHS-100010100以为进基变量，为离基变量旋转得20RHS0-660-130-311160328061123因此，原问题的最优解为，最优值为31。18、写出下列线性规划问题的对偶规划：解：先将此问题化成一般形式注：要先将问题化成一般形式，再按规则写出它的对偶问题。要记住判定对偶变量是自由变量还是非负变量所以，其对偶规划为2020、给定线性规划问题记为

8、（P）（1）用单纯形算法解P;（2）写出P的对偶问题D;（3）写出P的互补松紧条件,并利用它们解对偶D;解：(1)把问题（P）化为标准形式以为基变量，可得到其单纯形表为:RHS-10-100120150103把第0行化成检验行，得20RHS0018120150103以为进基变量，为离基变量