运筹学 北京邮电大学.ch2-1

北京邮电大学 运筹学
§3.1 运输问题的数学模型 Mathematical Model of T P
Ch3 Transportation Problem
2020/1/28
Page 4 of 11
需求假设（The Requirements Assumption）： 每一个出发地都有一个固定的供应量，所有的供应 量都必须配送到目的地。与之相类似，每一个目的 地都有一个固定的需求量，整个需求量都必须由出 发地满足，即
如何制定一个运输方案，使总的运输费用最小。这样的问题称为运 输问题。
北京邮电大学 运筹学
§3.1 运输问题的数学模型 Mathematical Model of T P
Ch3 Transportation Problem
2020/1/28
Page 3 of 11
运输问题的特征 Characteristics of Transportation Problems
钢铁厂
矿山
B1
A1
3
A2
5
A3
4
需要量
5
表3－1
B2
B3
2
6
3
8
1
2
7 8 北京邮电大学 运筹学
运价表（元/吨）
B4
产量
3
10
2
8
9
5
3
23
§3.1 运输问题的数学模型 Mathematical Model of T P
Ch3 Transportation Problem
2020/1/28
Page 7 of 11

x12 x22

x13 x14 x23 x24
10 8

北邮运筹学试题及答案一、单项选择题（每题 2 分，共 20 分）1. 运筹学中，线性规划问题的基本解是指：A. 可行域中的任意一点B. 可行域的顶点C. 可行域的内部点D. 可行域的边界点答案：B2. 单纯形法中，如果一个变量的系数在目标函数中为正，在所有约束条件中为负，则该变量：A. 可以取任意值B. 必须取零C. 可以取正值D. 可以取负值答案：B3. 在整数规划问题中，目标函数的最优解一定是：A. 整数解B. 非整数解C. 可行域中的任意解D. 可行域的顶点解答案：A4. 动态规划中，状态转移方程的作用是：A. 描述系统状态的演变B. 描述系统状态的稳定性C. 描述系统状态的最优性D. 描述系统状态的随机性答案：A5. 网络流问题中，流量守恒定律指的是：A. 每个节点的流量总和为零B. 每个节点的流量总和为一C. 每个节点的流量总和为负D. 每个节点的流量总和为正答案：A6. 在排队论中，M/M/1队列的特点是：A. 到达率为常数，服务率为常数，一个服务台B. 到达率为常数，服务率为常数，两个服务台C. 到达率为常数，服务率为变量，一个服务台D. 到达率为变量，服务率为常数，一个服务台答案：A7. 决策树中，期望值的计算是基于：A. 概率B. 成本C. 时间D. 收益答案：A8. 敏感性分析在运筹学中的作用是：A. 确定最优解B. 确定可行域C. 确定目标函数的稳定性D. 确定约束条件的最优性答案：C9. 非线性规划问题中，拉格朗日乘数法用于：A. 求解无约束问题B. 求解有约束问题C. 求解线性问题D. 求解整数问题答案：B10. 博弈论中，纳什均衡是指：A. 双方都没有动机单方面改变策略B. 双方都没有动机同时改变策略C. 至少一方有动机单方面改变策略D. 至少一方有动机同时改变策略答案：A二、多项选择题（每题 2 分，共 20 分）11. 线性规划问题中，可行解必须满足的条件包括：A. 满足所有约束条件B. 满足目标函数C. 满足非负约束D. 满足所有变量的取值范围答案：ACD12. 单纯形法中，基本可行解的特征是：A. 所有非基变量的值为零B. 所有基变量的值非负C. 所有变量的值非负D. 所有基变量的值不为零答案：ABD13. 动态规划问题中，最优子结构性质指的是：A. 问题的最优解包含子问题的最优解B. 问题的最优解不包含子问题的最优解C. 子问题的最优解可以组合成原问题的最优解D. 子问题的最优解不能组合成原问题的最优解答案：AC14. 网络流问题中，最大流最小割定理指出：A. 最大流等于最小割B. 最大流小于最小割C. 最大流大于最小割D. 最大流与最小割无关答案：A15. 排队论中，M/M/1队列的稳态概率分布是：A. 几何分布B. 泊松分布C. 指数分布D. 正态分布答案：A16. 决策树中，期望值的计算需要考虑的因素包括：A. 概率B. 成本C. 时间D. 收益答案：ABD17. 敏感性分析中，可以分析的因素包括：A. 目标函数系数的变化B. 约束条件的变化C. 变量的取值范围的变化D. 算法的效率答案：ABC18. 非线性规划问题中，拉格朗日乘数法可以用于：A. 求解无约束问题B. 求解有约束问题C. 求解线性问题D. 求解整数问题答案：B19. 博弈论中，纳什均衡的特点包括：A. 双方都没有动机单方面改变策略B. 双方都没有动机同时改变策略C. 至少一方有动机单方面改变策略D. 至少一方有动机同时改变策略答案：A20. 博弈论中，零和博弈与非零和博弈的区别在于：A. 零和博弈中，一方的收益等于另一方的损失B. 非零和博弈中，一方的收益不等于另一方的损失C. 零和博弈中，双方的收益总和为零D. 非零和博弈中，双方的收益总和不为零答案：ABCD三、判断题（每题 2 分，共 20 分）21. 线性规划问题中，如果目标函数的最优解在可行域的边界上，则该解一定是顶点解。

【性质5】互补松弛定理 设X°、Y°分别为（LP）与 （DP）的可行解，XS和YS是它的松弛变量的可行解，则 X°和Y°是最优解当且仅当
YSX°=0和Y°XS=0
【证】设X°和Y°是最优解，由性质3 ，C X°= Y°b，
由于XS和YS是松弛变量A X，°则＋有XS＝b
Y°A－YS=C 将第一式左乘Y°，第二式右乘X°得
§2.2对偶性质 Dual Property
Ch2 Dual Problem
2020年4月28日星期二 Page 1 of 23
设原问题是（记为LP）： 对偶问题是（记为DP）：
max Z CX
min w Yb
AX b X 0
YA C Y 0
这里A是m×n矩阵X是n×1列向量，Y是1×m行向量。假
【性质3】最优准则定理 设X°与Y°分别是（LP）与（DP） 的可行解，则当X°、Y°是（LP）与（DP）的最优解当且仅 当C X°= Y°b.
【 证 】 若 X° 、 Y° 为 最 优 解 ， B 为 （ LP ） 的 最 优 基 ， 则 有
Y°=CBB－1，并C且X 0 CB B1b Y 0b
设Xs与Ys分别是（LP）与（DP）的松驰变量。
【性质1】 对称性 对偶问题的对偶是原问题。 【证】设原问题是
max Z CX , AX b, X 0
§2.2对偶性质 Dual Property
由表2－1知，它的对偶问题是
Ch2 Dual Problem
2020年4月28日星期二 Page 2 of 23
2020年4月28日星期二 Page 5 of 23
max w 2 y1 2 y2
y1 y2 1
1
y12, yy21

2018年北京邮电大学数学考研招生专业目录、研究方向、考试科目、考试大纲一、招生信息招生院系：理学院招生人数：48招生专业：070100数学二、研究方向01(全日制)代数与密码学02(全日制)符号计算在新型光纤通信等领域中的应用03(全日制)应用微分方程04(全日制)非线性系统理论与应用05(全日制)二维纳米光电器件与超快光学06(全日制)信息安全中的数学模型与算法07(全日制)拓扑学理论及其在智能信息处理中的应用08(全日制)复分析和复动力系统09(全日制)概率统计（因果模型及数据分析）10(全日制)概率论与数理统计（金融数学）11(全日制)运筹学（排队论，库存管理）12(全日制)复杂网络、链路预测和推荐系统中的大数据分析13(全日制)概率论与随机过程14(全日制)应用偏微分方程15(全日制)微分方程中的变分法研究16(全日制)微分方程及其在智能科学中的应用17(全日制)智能信息处理与最优化方法18(全日制)优化理论与方法19(全日制)自适性、有限元及其工程应用20(全日制)运筹学在通信中的应用21(全日制)群体智能及其应用22(全日制)组合优化及其在通信网络中的应用22(全日制)组合优化及其在通信网络中的应用23(全日制)数值代数，数据挖掘24(全日制)调和分析及其在偏微分方程中的应用25(全日制)应用信息学三、考试科目①101思想政治理论②201英语一③601数学分析④811概率论⑤816高等代数④⑤选一四、专业课考试大纲参考书目：811概率论：《概率论》，科学出版社（第二版），杨振明《概率论引论》，北京大学出版社（2004年2月版），汪仁官《概率论·数理统计·随机过程》，北京邮电大学出版社（2006年出版），胡细宝孙洪祥王丽霞816高等代数：《高等代数》，高教出版社（第三版），北京大学数学系几何与代数教研室前代数小组编王萼芳石生明修订（1）601数学分析一、考试目的要求考生比较系统地理解和掌握数学分析的基本概念、基本理论和基本方法。