运筹学作业-王程130404026

《运筹学作业-王程130404026》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学作业王程信管1302130404026目录运筹学作业1第一章线性规划及单纯形法3第二章线性规划的对偶理论与灵敏度分析24第三章运输问题53第四章目标规划63第五章整数规划72第六章非线性规划84第七章动态规划93第八章图与网络分析96第九章网络计划98第一章线性规划及单纯形法1.1分别用图解法和单纯形法求下列线性规划问题，⑴指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解；⑵当具有限最优解时，指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。解：⑴图解法：当经过点时，最小，且有无穷多个最优解。⑵图解法：该问题无可

2、行解。⑶图解法：当经过点时，取得唯一最优解。单纯形法：在上述问题的约束条件中分别加入松弛变量，化为标准型：由线性规划问题的标准型可列出单纯初始形表逐步迭代，计算结果如下表所示：⑷图解法：当经过点时，取得唯一最优解。1.2将下述线性规划问题化成标准形式。1.3对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。解：（1）该线性规划问题的全部基解见下表中的①～⑧，打√者为基可行解，注*者为最优解，z*=36。（2）该线性规划问题的标准形式为：其全部基解见下表中的①～⑥，打√者为基可行解，注*者为最优解，z*=5。1.4题1

3、.1（3）中，若目标函数变为，讨论的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。解：由目标函数可得：，其中。⑴当时，可行域的顶点A使目标函数达到最优；⑵当时，可行域的顶点B使目标函数达到最优；⑶当时，可行域的顶点C使目标函数达到最优；⑷当或时，最优解为O点。1.6分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪一类解。其中M是一个任意大的正数，据此可列出初始单纯形表如下：cj23100MMθiCBXBbx1x2x3x4x5x6x7MMx6x78613[4]220-100-1100123cj-zj2-

4、4M3-6M1-2MMM003Mx2x7221/4[5/2]101/2-1-1/41/20-11/4-1/20184/5cj-zj32x2x19/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5cj-zj0001/21/2M-1/2M-1/2由单纯形表的计算结果得：最优解,目标函数最优值X存在非基变量检验数，故该线性规划问题有无穷多最优解。据此可列出单纯初始形表如下：cj0000011θiCBXBbx1x2x3x4x5x6x711x6x78613[4]220-100-1100123cj-

5、zj-4-6-2110001x2x7221/4[5/2]101/2-1-1/41/20-11/4-1/20184/5cj-zj00x2x19/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5cj-zj0000011第一阶段求得的最优解，目标函数的最优值，因人工变量，所以是原线性规划问题的基可行解。于是可以进行第二阶段计算，将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，如下表：cj23100θiCBXBbx1x2x3x4x532x2x19/54/501103/5-2/5

6、-3/101/51/10-2/5cj-zj0001/21/2由表中计算可知，原线性规划问题的最优解，目标函数的最优值，由于存在非基变量检验数，故该线性规划问题有无穷多最优解。其中M是一个任意大的正数，据此可列出单纯形表如下：cj101512000-MθiCBXBbx1x2x3x4x5x6x700-Mx4x5x79155[5]-52361115110001000-10019/5-5/2cj-zj10+2M15+M12+M00-M0100-Mx1x5x79/5247/51003/59-1/51/5[16]3/51/51-2/501000

7、-100193/27/3cj-zj1012-Mx1x3x73/23/21/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001cj-zj0由单纯性表的最终表可以看出，所有非基变量检验数，且存在人工变量，故原线性规划问题无可行解。据此可列出单纯初始形表如下：cj0000001θiCBXBbx1x2x3x4x5x6x7001x4x5x79155[5]-52361115110001000-10019/5-5/2cj-zj-2-1-100101001x1x5x79/5247/510

8、03/59-1/51/5[16]3/51/51-2/501000-100193/27/3cj-zj-1/53/5-2/51001x1x3x73/23/21/210039/809/16-43/800103/161/16-7/16-1/8