《运筹学》课程综合复习资料
一、判断题
1.用单纯形法求解单纯形表时,若选定入基变量xk(检验数>0), 但该列的aikLP问题无解。
2.对偶单纯形法中,若选定出基变量xi(xi<0),但xi所在行的元素(系数矩阵中)全部大于或等于0,则此问题无解。
3.当你自己建立的LP模型无解时,极有可能是模型中存在矛盾的约束条件。 4.运输问题是一种特殊的LP问题,总有可行解存在。
5.应用表上作业法的最小元素法确定运输问题的初始调运方案时,遇有退化基本可行解时,一定注意补0,否则,初始调运方案的实格数不满足:实格数=m+n-1。
6.运输问题是一种特殊形式的LP问题,因而其求解结果也可能会有唯一的最优解或多个最优解。 7.动态规划实质是阶段上枚举,过程上寻优。 8.动态规划中,允许决策集合是状态变量的函数。
?0 i=1,2...m,则该
二、图解计算题
1.
Maxz?10x1?5x2
s.t.3x1?4x2?95x1?2x2?8x1x2?0
2.
Minz?2x1?3x2
s.t.4x1?6x2?62x1?2x2?4x1x2?0
3.
?Minz?p1d1??p2d2?p3d3?s.t.
5x1?10x2?60x1?2x2?d1??d1??04x1?4x2?d?d?366x1?8x2?d3??d3??48变量非负运筹学 第1页 共8页
?2?2
三、写出下面线性规划的对偶规划;并将该线性规划模型化成标准形式。
Minz??3x1?4x2?2x3?5x4s.t.4x1?x2?2x3?x4??2
x1?x2?x3?2x4?14?2x1?3x2?x3?x4?2x1x2?0x3?0x4无约束
四、建立模型
1. 在蔬菜价格上涨的情况下,某疗养院要求定出一周的菜谱,以保证修养员在对各种营养正常需要的条件下,节约伙食开支。当时当地可供采购的蔬菜有6种,每种菜的成本及所含营养的数据如下表;为满足胃口变化的要求,规定洋白菜的供应一周不多于2次,其余蔬菜不多于4次,一周内每人每天供应蔬菜2份,共14份,试建立整数规划模型。
蔬菜种类 每份菜所含营养素的量 铁(Mg) 青豆 胡萝卜 菜花 洋白菜 苔菜 土豆 每周要求达到的最低营养素的量 2. 某采油区已建有n个计量站B1,B2…Bn,各站目前尚未被利用的能力为b1,b2…bn(吨液量/日)。为适应油田开发的需要,规划在该油区打m口调整井A1,A2…Am,且这些井的位置已经确定。根据预测,调整井的产量分别为a1,a2…am(吨液量/日)。考虑到原有计量站富余的能力,决定不另建新站,而用原有老站分工管辖调整井。按规划要求,每口井只能属于一个计量站。假定Ai到Bj的距离dij已知,试确定各调整井与计量站的关系,使新建集输管线总长度最短。(设定变量,写出模型)
0.45 0.45 1.05 0.40 0.50 0.50 6.0 磷(Mg) 10 28 50 25 22 75 325 维A(Mg) 415 9065 2550 75 15 235 17500 维C(Mg) 8 3 53 27 5 8 245 每份菜烟酸成本 (Mg) 0.3 0.35 0.6 0.15 0.25 0.8 5.0 (元) 0.5 0.5 0.8 0.2 0.6 0.3
运筹学 第2页 共8页
五、问答题
1. 某工厂使用一台设备,其在不同使用役龄下的维修费、残值及该设备不同年份的购置费如下表,试制定一个使总支出最少的5年更新计划。
项目 购买费 机器役龄 维修费 残值
2. 设有LP模型如下:
第1年 11 0-1 5 4 第2年 12 1-2 6 3 第3年 13 2-3 8 2 第4年 14 3-4 11 1 第5年 14 4-5 18 0 Maxz?CXs.t.AX?IXs?b
X?0Xs?0试用矩阵语言,描述其最优性检验条件为:
3. 已知某线性规划问题的初始单纯形表和用单纯形法迭代得到最优解时的表如下,求括弧中未知数a…l的值。
X4 X5 cj-zj X1 X5 cj-zj
4. 石油公司所属某仪器厂按合同向勘探单位提供地震勘探仪器,在计划年度内各季度的合同交货量、该厂的生产能力、生产成本及成品库中的维护与保管成本数据如下表,试:
①建立总成本最低的生产计划模型; ②并用表上作业法求解一步。 季度 合同交货(台) 1 2 3 4
运筹学 第3页 共8页
C?CBB?1A?0?CBB?1?0
X1 (b) -1 (a) (g) (h) 0 X2 (c) 3 -1 2 (i) -7 X3 (d) (e) 2 -1 1 (j) X4 1 0 0 1/2 1/2 (k) X5 0 1 0 0 1 (l) b 6 1 (f) 4 生产能力(台) 25 35 30 10 生产成本(千元/台) 保管成本(千元/台季) 103 111 110 113 1.5 1.5 1.5 1.5 10 15 25 20