运筹学(二)

预付成本（ B ）

A. 随销售量而波动 B.与销售量无关 C.大于计划成本 D.小于计划成本

从带连数长度的连通图中生成的最小支撑树，叙述不正确的是（C）

A.任一连通图生成的各个最小支撑树总长度必相等

B.任一连通图生成的各个最小支撑树连线数必相等

C.任一连通图中具有最短长度的连线必包含在生成的最小支撑树中

D.最小支撑树中可能包括连通图中的最长连线

所谓确定条件下的决策，是指在这种条件下，只存在（A ）

A.一种自然状态 B.两种自然状态

C.三种或三种以上自然状态 D.无穷多种自然状态

对于第一类存储模型——进货能力无限，不允许缺货，下列哪项不属于起假设前提条件（ A ）

A. 假设每种物品的短缺费忽略不计 B.假设需求是连续，均匀的 C.假设当存储降至0时，可以立即得到补充 D.假设全部定货量一次供应

连续型动态规划常用求解方法是（B）

A.表格方式

B.公式递推

C.决策树

D.多阶段决策

（B）表示当过程处于某阶段的某个确定状态时，可以作出的选择或决定

A.状态

B.决策

C.状态转移

D.指标函数

设F为固定成本，V为可变成本，V′为单件可变成本，Q为产品产量，C为总成本，则A

A.C=F+QV′ B.C=F+V′ C.C=F+V+QV′ D.C=F+QV

关于最大流量问题，叙述正确的是（A）

A.一个流量图的最大流量能力是唯一确定

B.达到最大流量的方案是唯一的

C.一个流量图的最大流量能力不是唯一的

D.n条线路中的最大流量等于这n条线路的流量能力之和

在实际工作中，企业为了保证生产的连续性和均衡性，需要存储一定数量的物资，对于存储方案，下列说法正确的是( C )

A.应尽可能多的存储物资，以零风险保证生产的连续性 B.应尽可能少的存储物资，以降低库存造成的浪费 C.应从多方面考虑，制定最优的存储方案 D.以上说法都错误

前一阶段的状态和决策决定了下一阶段的状态，他们之间的关系称为（C）

第1页共5页 一、 实验内容及步骤（包含简要的实验步骤流程）

问题：大学生值班问题

东方大学计算机实验室聘用4名大学生（代号1、2、3、4）和2名研究生（代号5、6）值班答疑。已知每人从周一至周五每天最多可安排的值班时间及每人每h值班报酬如下表所示：

表

学生代号 报酬

（元/h） 每人最多可安排的值班时间

周一 周二 周三 周四 周五

1 10.0 6 0 6 0 7

2 10.0 0 6 0 6 0

3 9.9 4 8 3 0 5

4 9.8 5 5 6 0 4

5 10.8 3 0 4 8 0

6 11.3 0 6 0 6 3

该实验室开放时间为上午8：00至晚上10：00，开放时间内须有且仅须有一名学生值班。规定大学生每周值班不少于8h，研究生每周值班不少于7h，每名学生每周值班不超过3次，每次值班不少于2h，每天安排值班的学生不超过3人，且其中必须有一名研究生。施为该实验室安排一张人员值班表，使总支付的报酬为最少。

模型建立：

解：设错误！未找到引用源。为学生i在周j的值班时间，

10ijy，安排学生i在周j值班，否则

用错误！未找到引用源。代表学生i在周j最对可安排的值班时间，错误！未找到引用源。为学生i的每h的报酬，则本题的数学模型为：

6511miniijijzcx

第2页共5页 51516151615621,6;j1,581,4875,67141,514..31,6331,5311,5ijijijijijjijjijiijjijijjyxayixihxihxjhstyiyjyyj不超过可安排时间大学生每周值班不少于研究生每周值班不少于每天实验室开放每名学生一周值班不超过次每天值班不超过人每天0,01i16j15ijijxy有一名研究生值班或；

第 1 页 共 29 页 《运筹学》复习参考资料

资料加工、整理人——杨峰（函授总站高级讲师）

要求掌握的各部分知识点

第一部分 线性规划问题的求解（相当于教材的第一章）

——重要算法：单纯形迭代、大M法单纯形迭代、表上作业法、匈牙利法

第二部分 动态规划问题的求解（相当于教材的第三章）

——重要算法：图上标号法

第三部分 网络分析问题的求解（相当于教材的第四章）

——重要算法：破圈法、TP标号法、寻求网络最大流的标号法

第四部分 存储论简介（相当于教材的第七章）

※杨老师关于学习方法的提示：《运筹学》属于应用数学的范畴，本门课程在管理类本科生层次开设时，又称“管理运筹学”，是现代数学理论和计算机技术应用于管理科学的新兴学科。非应用数学系（专业）学生学习本门课程之前务必先具备“高数Ⅱ”（线性代数、概率论与数理统计）的知识基础。学员同志们通过学习，必须领会数学建模的思想、系统工程的思想。

非全日制学生学习时，只要求知道若干典型数学模型及其算法的操作，即只须明白“怎样做”，而不必去过问“为什么”要这样做。 第 2 页 共 29 页 第一部分 线性规划问题的求解

一、两个变量的线性规划问题的图解法：

㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。

定义：达到目标的可行解为最优解。

㈡图解法：

图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出；

2、确定可行解域；

3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；

注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。

4、确定最优解及目标函数值。

㈢参考例题：（只要求下面这些有唯一最优解的类型）

例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：

运筹学2对偶问题

运筹学教程

运筹学Operations Research Chapter 2 对偶问题Dual

Problem

1. 线性规划的对偶模型 Dual Model of LP 2.对偶性质 对偶性质 3.对偶单纯形法 对偶单纯形法 4.灵敏度分析 灵敏度分析

Dual property Dual Simplex Method Sensitivity Analysis

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual

model of LP

Ch2 Dual Problem2022年11月26日星期五 Page 2 of 19

在线性规划问题中，存在一个有趣的问题，即每一个线性规

划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。

【例2.1】 某企业用四种资源生产三种产品，工艺系数、 例

资源限量及价值系数如下表：产品 资源 Ⅰ Ⅱ Ⅲ Ⅳ 每件产品利润 9 5 8 7 100 8 4 3 6 80 6 7 2 4 70 500 450 300 550 A B C 资源限量

建立总收益最大的数学模型。

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2022年11月26日星期五 Page 3 of 19

设x1,x2,x3分别为产品A,B,C的产量，则线性规划数学模 解

型为： m Z = 100x + 80x + 70x ax1 2 3

9x1 + 8x2 + 6x3 ≤ 500 5x + 4x + 7x ≤ 450 2 3 1 8x1 + 3x2

+ 2x3 ≤ 300 7x + 6x + 4x ≤ 550 2 3 1 x1, x2, x3 ≥ 0 现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产 品，而将现有的资源转让或出租给其它企业，那么资源的转让价格