运筹学II

《运筹学》 (II)

一、填空题

1．表1为用单纯形法计算时某一步的表格，已知该线性规划的目标函数为maxz5x13x2，约束形式为，x3，x4为松弛变量，表中解代入目标函数后得z＝10。

表1 x1 c d b x2 0 e -1 x3 1 0 f x4 1/5 1 g x3 2 x1 a cjzj （1）a＝______，b＝______，c＝______，d＝______，e＝______，f＝______，g＝______； （2）表中给出的解为___________（提示：最优解，满意解，可行解……）。 2．影子价格是一种____________，它相当于在资源得到最优利用的生产条件下，bi每增加一个单位时目标函数z的增量。

3．若原问题及其对偶问题均具有可行解，则两者均具有__________，且它们最优解的目标函数值_________。

4．动态规划中的状态必须具备____________。

二、判断题

1. 线性规划问题的每一个基解对应可行域的一个顶点。（ ） 2. 对偶问题的对偶问题一定是原问题。（ ）

3. 表上作业法实质上就是求解运输问题的单纯形法。（ ）

4. 对一个动态规划问题，应用顺推法或逆推法可能会得到不同的最优解。（ ）

5. 求图的最小支撑树以及求图中一点至另一点的最短路问题，都可以归结为求解整数规划问题。（ ）

三、简答题

1. 简述动态规划方法的基本思想。 ） 2. 简述不确定型决策方法中的乐观准则。 四、计算题

1.用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解或无可行解。

maxz4x18x22x12x210 st.x1x28x,x012第1页 共3页

2.已知线性规划问题：

minz2x1x22x3x1x2x34 st.x1x2kx36x0,x0,x无约束231（1）写出其对偶问题，并求对偶问题的最优解；

（2）求k的值。

3. 已知运输问题的产销地、产销量及各产销地间的单位运价如下表所示，试据此列出其数学模型。

表2 产地 销地 1 2 3 销量 甲 10 14 22 12 乙 16 22 24 8 丙 32 40 34 20 产量 15 7 16 4.用隐枚举法求解下列0－1规划问题： minz2x15x23x34x44x1x2x3x402x4x2x4x4 1234st.x1x2x3x41xi0或1(i1,,4)5.用匈牙利法求解下述指派问题，已知效率矩阵为：

38689

8210372974275

4235106910

五、建模题

某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C的含量、原料成本、各种原料每月的用量，三种牌号糖果的单位加工费及售价如表3所示：

表3 A B C 加工费（元/kg） 售价（元/kg） 甲 乙 丙 原料成本（元/kg） 每月用量（kg） 2.00 1.50 1.00 2000 2500 1200 60% 15% 20% 0.50 3.40 60% 0.40 2.85 50% 0.30 2.25 若该糖果厂建立生产计划的目标优先级为： p1：达到利润目标；

p2：甲、乙、丙三种糖果的原材料比例上应满足配方要求； p3：充分利用又不超出规定的原材料供应量。

第2页 共3页

根据上述要求，对此问题建立目标规划的数学模型。

第3页 共3页