一、 简答题 1.答：（1）把一般线形规划模型转换成标准型；（2）确定初始基可行解；（3）利用检验数?j对初始基可行解进行最优性检验，若?j?0 ，则求得最优解，否则，进行基变换；（4）基变换找新的可行基，通过确定入基变量和出基变量，求得新的基本可行解；（5）重复步骤（3）、（4）直至?j?0，求得最优解为止。 2.答：分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。 3.答：（1）最优解不一定在顶点上达到；（2）最优解不一定是松弛问题最优解的三、计算题 1.解：（1）加入人工变量x4,x6 ，减去剩余变量x5 得到该线形规划问题的标准型 maxz?2x1?3x2?5x3?Mx4?Mx6 ?x1?x2?x3?x4?7??2x1?5x2?x3?x5?x6?10 ?x,x,x,x,x,x?0?123456邻近整数解；（3）整数可行解远多余于顶点，枚举法不可取；（4）整数规划的最大函数值小于或等于相应的线性规划的最大目标函数值；（5）整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。 （2）利用单纯形表逐步迭代 Cj 2 3 CB XB b x1 x2 -M x4 7 1 1 -M x6 10 [2] -5 3M+2 3-4M ? j-5 x3 1 1 1 0 2M-5 0 1/2 1/2 1 0 -M x4 0 x5 0 -1 -M 1/2 -1/2 0 1 0 -M x6 比值 7 5 4/7 - -M 2 x4 x1 2 5 0 1 0 [7/2] -5/2 -1/2 1/2 ?j 3 2 x2 x1 4/7 0 45/7 1 3M/2+8 M/2-6 1 0 1/7 6/7 0 0 2/7 5/7 M/2+1 -3M/2-1 1/7 -1/7 -1/7 -1/7 1/7 -M+1/7 ?j 0 -50/7 -M-16/7 最优解X*?(45/7,4/7,0,0,0)T,z*?102/7 2.解：用逆序算法。设 （1）阶段：每个研究小组为一个阶段，该问题分3个阶段： 阶段 1 2 3 小组 （2）决策变量Pn(1 2 3 xn：分配给第n小组的高级科学家数目，相应的失败概率为xn)； s第 页 共 页 （3）状态变量n：在阶段n时可分配于阶段n，n-1，…，1的高级科学家人数。 递推关系：
相关推荐：
loading