运筹学作业解答(1-2).ppt

运筹学作业 一 题1 1 总结线性规划模型的特征 判断下列数学模型是否为线性规划模型 模型a b c为常数 q为可取某常数值的参变量 x y为变量 题1 将下列线性规划模型转化为标准型题1 试给出下列线性规划问题的对偶问题的线性规划模型 题1 用图解法求解下列线性规划问题 并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点 maxz 10 x1 5x2st 3x1 4x2 95x1 2x2 8x1 x2 0 题1 5 某工厂需要在一定时间内生产700单位的产品 单位的产品B 单位的产品C 生产这些产品需要五个部门来完成 各部门每个员工在该时间内能完成的各产品量 单位 和工资见下表 试确定各部门用人数量 只建立线性规划数学模型 解 用xj j 1 5 分别代表五个部门的用人数量 题1 6 某农场有100公顷土地和15000元资金 农场劳动力在秋冬季节3500人 在春夏季节4000人 劳动力在空闲时可外出干活 秋冬季节收入为1 8元 人 春夏季节2 1元 人 农场种植三种作物 大豆 玉米 小麦 并饲养奶牛和鸡 种作物不需专门投入 而饲养动物时每头奶牛 元 每只鸡 元 养奶牛每头需 公顷土地种草 并占用人工在秋冬季节 人 春夏季节 人 养奶牛每年净收入 元 头 养鸡时不占用土地 但需人工在秋冬季节 人 只 秋冬季节 人 每只鸡 年净收入 元 只 农场只允许最多养鸡 只 奶牛 头 三种植物每年需要的人工及收入见下表 试决定农场的经营方案从而使年收入最高 只建立现行规划数学模型 解 用x1 x2 x3分别代表大豆 玉米 麦子的种植数 x4 x5分别代表奶牛和鸡的饲养数 x6 x7分别代表秋冬和春夏季节多余的劳动力数目 题1 问答题 线性规划问题中 所说的基 是几阶矩阵 答 m阶 基 都是可行基吗 答 不一定 基本解与基本可行解有何区别 答 基本可行解是满足变量非负条件的基本解 题1 8 写出下列线性规划问题的对偶问题 maxz 10 x1 x2 2x3st x1 x2 2x3 104x1 x2 x3 20 xj 0 j 1 2 3 minz 5x1 6x2 7x3st x1 5x2 3x3 15 5x1 6x2 10 x3 20 x1 x2 x3 5x1 0 x2 0 x3无约束 3 minz 3x1 2x2 x3st x1 2x2 12x2 x3 22x1 x3 3x1 2x2 3x3 4x1 x2 0 x3无非负限制对偶问题 maxs y1 2y2 3y3 4y4s t y1 2y3 y4 32y1 2y2 2y4 2y2 y3 3y4 1y2 y3 y4 0 y1无非负约束 题1 9 填空题 在用图解法求线性规划问题时 目标函数 ClX1 C2X2 则直线ClX1 C2X2 10是 的一条平行线 而当可行域非空有界时最优解必定能在可行域的顶点上达到 线性规划数学模型三要素 决策变量 目标函数 约束条件 线性规划中 任何基对应的决策变量称为基变量 若某线性规划问题存在唯一最优解 从几何上讲 它必定在可行解域的某个顶点处达到 从代数上讲 它也一定是某个基变量组的基可行解 设P是线性规划问题 D是其对偶问题 则 不正确 A P有最优解 D不一定有最优解B 若P和D都有最优解 则二者最优值肯定相等C 若P无可行解 则D无有界最优解D D的对偶问题为P 在求minZ的线性规划问题中 正确A 最优解只能在可行基解中才有B 最优解只能在基解中才有C 基变量的检验数只能为零D 有可行解必有最优解 有关线性规划 B 是错误的 A 当最优解多于一个时 最优解必有无穷多个B 当有可行解时必有最优解C 当有最优解时必有在可行集顶点达到的最优解D 当有可行解时必有可行基解 线性规划中 B 不正确 A 有可行解必有可行基解B 有可行解必有最优解C 若存在最优解 则最优基解的个数不超过2D 可行域无界时也可能得到最优解 题 判断题 运筹学作业 二 2 1某钻井队要从以下10个可供选择的井位中确定5个钻井探油 使总的钻探费用为最小 若10个井位的代号为s1 s2 s10 相应的钻探费用为c1 c2 c10 并且井位选择上要满足下列限制条件 或选择s1和s7 或选择钻探s8 选择了s3或s4就不能选s5 或反过来也一样 在s5 s6 s7 s8中最多只能选两个 试建立此问题的整数规划模型解 xj 1表示选择钻探sj井位 否则xj 0 2 2用隐枚举法求解0 1整数规划问题maxZ 3x1 2x2 5x3 2x4 3x5st x1 x2 x3 2x4 x5 47x1 3x3 4x4 3x5 811x1 6x2 3x4 3x5 3xj 0或1 j 1 5 解 最优解x1 x2 1 x3 x4 x5 0 Z 5 2 3试述用最小元素法确定运输问题的初始基可行解的基本思路和基本步骤 答 最小元素法的基本思想是就近供应 即从单位运价表中最小的运价开始确定供销关系 然后次小 一直到给出初始基可行解为止2 4试述用闭回路法计算检验数的原理和经济意义 如何从任一空格出发去寻找一条闭回路 答 闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数 当所有检验数都非负时 该基可行解即为最优解 从经济意义而言 闭回路法检验数表示 空格运量从0增加一个单位导致的总运费的改变量 在初始调运方案表中 从任意空格出发 沿着纵向或横向行进 遇到适当填有数据的方格90度转弯 继续行进 总能回到原来空格 这个封闭的曲线称为闭回路 2 5一般线性规划问题应具备什么特征才可以转化并列出运输问题的数学模型 从而用表上作业法求解 答 一般线性规划问题不能够转化为运输问题数学模型 除非所有变量都是双下标 且第1 第2下标个数整齐 所有约束的系数为1或0 再加上其他条件才可能 2 6解 表中最小元素是C32 令x32 min a3 b2 min 5 3 3 同时将第二列划去 现在 最小元素为C23 C31 任意选取其一 这里选C31 令x31 min 5 3 5 2 同时将第三行划去 依次进行下去 直到得到结果 2 7 针对某一产销平衡运输问题 当前解如下表所示 写出a b c d e的值判断当前解是否为最优解如果当前解不是最优解 求出最优解 或最优运输方案 A3到B1的单位运费满足什么条件时 表中当前解为最优方案解 所以当前解不是最优解 所有检验数为非负数 所以当前解是最优解 以检验数为