运筹学(A)解答.doc

数学规划试题(A)解答一、是否题:(填()或(),每小题1分,共12分),则最优解一定对应可行域边界上的一个点。(),与对应的变量都可以被选作换入变量。(),选取最大正检验数对应的变量作为换入变量,将使目标函数值得到最快的增长。()、都是某一线性规划问题的最优解,则也是该线性规划问题的最优解,其中。()。(),某非基变量的检验数,且所在列的元素全部小于或等于零,则可以判断该线性规划问题为无界解。(),所以可能会出现无界解、无可行解等情况。()。()(或伏格尔法)给出的初始基可行解,从每一个空格出发可以找出唯一的闭回路。(),负偏差变量取负值。()-1规划的隐枚举法是分枝定界法的特例。()。()二、(10分)将线性规划问题变换成标准型,并列出初始单纯形表:解:令,,化为标准型:所求的初始单纯形表为:71-111-110008-2-3-5000100110-22-200-112-M-3M-13-7M2M+1-2M-100-M0三、(15分)已知线性规划问题:(a)写出其对偶问题;(b)用图解法求对偶问题的解;(c)利用(b)的结果及对偶性质求原问题解。解:(a)线性规划问题的对偶问题为:(b)用图解法得到,对偶问题的最优解为:(c)利用(b)的结果及由和对偶性质——互补松弛性,得到:,且得到原问题解:21028623514243631232251四、(12分)在下图中,用Dijkstra算法求顶点到其余各个顶点的最短有向路的长度及其路径。解:V1V2V3V4V5V6V7V8V9V10V11102268358124712675787681097101098101013912最短路:V1V2;长度:2;最短路:V1V2V3;长度:5;最短路:V1V2V3V4;长度:7;最短路:V1V2V3V6V5;长度:8;最短路:V1V2V3V6;长度:6;最短路:V1V2V3V7;长度:7;最短路:V1V2V3V6V5V8;长度:10;最短路:V1V2V3V7V9;长度:10;最短路:V1V2V3V7V10;长度:9;最短路:V1V2V3V7V9V11;长度:12;五、(12分)对如下的工程网络图,标号求出各工序的最早开工时间、最迟完工时间,以及关键路径。21028623514243631232251解:各工序的最早开工时间、最迟完工时间,以及关键路径如下图所示:1612212123210286235142436312322516171711726260608814142218六、(12分)在如下图所示的有向网络中(边上的数字