运筹学规划习题答案.doc

《运筹学规划习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、附录四：习题参考答案第一章线性规划及单纯形法1.1（1）解：第一，求可行解集合。令两个约束条件为等式，得到两条直线，在第一象限划出满足两个不等式的区域，其交集就是可行集或称为可行域，如图1-1所示，交集为（1/2,0）。第二，绘制目标函数图形。将目标函数的系数组成一个坐标点（6，4），过原点O作一条矢量指向点（6，4），矢量的长度不限，矢量的斜率保持4比6，再作一条与矢量垂直的直线，这条直线就是目标函数图形，目标函数图形的位置任意，如果通过原点则目标函数值Z=0，如图1-2所示。第三，求最优解。图1-2的

2、矢量方向是目标函数增加的方向或称梯度方向，在求最小值时将目标函数图形沿梯度方向的反方向平行移动，（在求最大值时将目标函数图形沿梯度方向平行移动）直到可行域的边界，停止移动，其交点对应的坐标就是最优解，如图1-3所示。最优解x=（1/2,0）,目标函数的最小值Z=3。X22x1+x2≥13x1+4x2≤1.5O1/2X1图1.1-1X22x1+x2≥13x1+4x2≤1.5(6,4)O1/2X1图1.1-2X22x1+x2≥13x1+4x2≤1.5(6,4)O1/2X1图1.1-3（2）无可行解；[求解方法

3、与（1）类似]（3）无界解；（4）无可行解；（5）无穷多最优解z*=66（6）唯一最优解z*=92/3,x1=20/3,x2=3/81.2（1）解：由题目可知，其系数矩阵为因线性独立，故有令非基变量得→得到一个基可行解，。线性独立，故有令非基变量得→得到一个基本解，但非可行解，。同理可以求出，得基本可行解。，得基本可行解。，得基本可行解。，得基本可行解。，得基本非可行解。，得基本非可行解。（1）、（2）答案如下表所示，其中打三角符号的是基本可行解，打星号的为最优解：x1x2x3x4x5zx1x2x3x4x

4、5△00412180000-3-5△400126123000-560-2120180010-3△4306027-9/205/200△064063005/20-30*△262003603/2100△*4600-64235/2000△094-6045005/29/20△1.3(1)解：单纯形法首先，将问题化为标准型。加松弛变量x3，x4，得其次，列出初始单纯形表，计算最优值。CBXB10500BX1X2X3X40X3341090X452018σj105000X3014/51-3/521/510X112/501

5、/58/5σj010-25X2115/14-3/143/210X100-1/72/71σj00-5/14-25/14（表一）由单纯形表一得最优解为图解法：X245X1+2X2≤8第一步：相当于原点（0,0）3X1+4X2≤99/4(1,3/2)O8/53x1图1.3-1X245X1+2X2≤8第二步：相当于点（8/5,0）3X1+4X2≤99/4(1,3/2)O8/53x1图1.3-2X245X1+2X2≤8第三步：相当于点（1,3/2）3X1+4X2≤99/4(1,3/2)O8/53x1图1.3-3（2

6、）略1.4(1)解：大M法首先将数学模型化为标准形式式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束分别加入人工变量x6x7，目标函数中加入-Mx6-Mx7一项，得到大M单纯形法数学模型由单纯形表计算：CBXB45100-M-MBX1X2X3X4X5X6X7-MX6321-1010180X521001004-MX711-100015σj4+4M5+3M1-M000-MX6-101-1-210105X221001004-MX7-10-100011σj4-2M01-M-2M001X3-101-1-

7、20100X22100104-MX7-200-1-2111σj5-2M001-M2-2M0表1.4-1.1在迭代过程中，人工变量一旦出基后不会在进基，所以当人工变量X6出基后，对应第六列的系数可以不再计算，以减少计算量。当用大M单纯形法计算得到最优解并且存在人工变量大于零时，则表明原线性规划无可行解。两阶段单纯形法首先，化标准形同大M法，第一、三约束分别加入人工变量x6x7后，构造第一阶段问题用单纯形法求解，得到第一阶段问题的计算表1.4-1.2，CBXB0000011BX1X2X3X4X5X6X71X6

8、321-1010180X5210010041X711-100015σj-4-3010001X601/21-1-3/210120X111/2001/20021X701/2-10-1/2013σj0-1012001X6-101-1-210100X2210020041X7-10-10-1011σj2001300表1.4-1.2在第一阶段的最优解中人工变量不为零，则原问题无可行解。注：在第二阶段计算时，初始表中的检验数不能引用第一阶段