北航最优化方法线性规划考试题.pdf

－ 学年 第 学期 “““最最最优优优化化化理理理论论论与与与算算算法法法－－－线线线性性性规规规划划划”””补补补充充充习习习题题题 年 月 日 刘红英 判断下列每个命题的正误，并说明理由 理由可以是行的解释或者反例；理由不正确的答案 不得分 线性规划标准形的可行集总是有界的 线性规划标准形问题一定有可行解 非基变量的既约费用系数总是严格正的 多面集上极小化一个凸的分段线性函数能表述为线性规划问题 如果所有非基变量的既约费用系数都是正数，则线性规划问题有唯一最优解 线性规划标准形问题一定有基本可行解 如果某个基本解的所有既约费用系数非负，则它是最优解 如果对偶问题是不可行的，则原始问题一定无界 两阶段法中，第 阶段的辅助问题的对偶问题有可能无界 在最小费用网络流问题中，弧上的费用是整数，但是需求和供给量是分数，则树解对应的 单纯形乘子都是整数 在最小费用网络流问题中，弧上的费用是分数，但是需求和供给量是整数，最优树解的每 个分量是分数 整数线性规划极小化松弛问题的最优值一定不大于原始问题的最优值 将整数线性规划极小化松弛问题的最优解四舍五入可以得到原问题的可行解 分假设用单纯形法求解标准形式的线性规划时得到如下单纯形表 x x x x x β γ δ r r 还假设矩阵 的后三列形成单位矩阵 给出由该表描述的当前基是最优的充分必要条件依照表中的系数 假设该基是最优的且r 找出另外一个最优基本可行解，其与该表所描述的不同 假定与当前表所联系的基是最优的假设将原问题中的b 替换为b ϵ给出使基保持最优 的ϵ的上下界。 某公司利用资源 和 生产四种产品 和 公司通过求解线性规划问题 z x x x x x x x x x x x x x .x x x x , x , x , x 确定产品组合 将该问题化成标准形后使用单纯形法求解，得到最优表格 . . . . . . 最优解和最优值各是多少？ 最优基 和其逆 各是多少？ 用一句话来描述最优策略