运筹学基础及应用(第一二章习题解答)程序.docVIP

运筹学基础及应用 习题解答 习题一 P46 1.1 (a) 该问题有无穷多最优解，即满足的所有，此时目标函数值。 (b) 用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。 1.2 约束方程组的系数矩阵 基 基解 是否基可行解 目标函数值 否 是 10 是 3 否 否 是 3 否 是 0 否 最优解。 约束方程组的系数矩阵 基 基解 是否基可行解 目标函数值 否 是 否 是 5 否 是 5 最优解。 1.3 (a) (1) 图解法 最优解即为的解，最大值 (2)单纯形法 首先在各约束条件上添加松弛变量，将问题转化为标准形式 则组成一个基。令 得基可行解，由此列出初始单纯形表 基 。 基 ， 新的单纯形表为 基 ，表明已找到问题最优解。最大值 (b) (1) 图解法 最优解即为的解，最大值 (2) 单纯形法 首先在各约束条件上添加松弛变量，将问题转化为标准形式 则，，组成一个基。令 得基可行解，由此列出初始单纯形表 2 1 0 0 0 基 0 15 0 24 0 5 0 5 1 0 0 [6] 2 0 1 0 1 1 0 0 1 2 1 0 0 0 。 2 1 0 0 0 基 0 15 2 4 0 1 0 5 1 0 0 1 0 0 0 0 1 0 0 0 ， 新的单纯形表为 2 1 0 0 0 基 0 2 0 0 0 1 1 0 0 0 1 0 0 0 0 ，表明已找到问题最优解，，，，。最大值 1.6 (a) 在约束条件中添加松弛变量或剩余变量，且令， 该问题转化为 其约束系数矩阵为 在中人为地添加两列单位向量 令 得初始单纯形表 基 (b) 在约束条件中添加松弛变量或剩余变量，且令， 该问题转化为 其约束系数矩阵为 在中人为地添加两列单位向量 令 得初始单纯形表 基 1.7 (a)解1：大M法 在上述线性规划问题中分别减去剩余变量再加上人工变量得 其中M是一个任意大的正数。据此可列出单纯形表 由单纯形表计算结果可以看出，且，所以该线性规划问题有无界解 解2：两阶段法。 现在上述线性规划问题的约束条件中分别减去剩余变量再加上人工变量得第一阶段的数学模型 据此可列出单纯形表 第一阶段求得的最优解,目标函数的最优值。 因人工变量，所以是原线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。 由表中计算结果可以看出，且，所以原线性规划问题有无界解。 (b)解1：大M法 在上述线性规划问题中分别减去剩余变量再加上人工变量得 其中M是一个任意大的正数。据此可列出单纯形表 由单纯形表计算结果可以看出，最优解，目标函数的最优解值X存在非基变量检验数，故该线性规划问题有无穷多最优解。 解2：两阶段法。 现在上述线性规划问题的约束条件中分别减去剩余变量再加上人工变量得第一阶段的数学模型 据此可列出单纯形表 第一阶段求得的最优解,目标函数的最优值。 因人工变量，所以是原线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。