容量 10 8 2 7
流量 7 4 0 7
边 3——2 3——4 4——5
中国石油大学（华东）
容量 5 10 4
流量 0 4 4
(3)计划利润不少于 48 元。
试建立符合要求的目标规划模型。
三、 计算及回答
某公司计划制造Ⅰ、Ⅱ两种家电产品，已知各制造一件时分别占用的设备 A、B 的台时、调试时间
及每天可用的设备能力和单件产品的获利情况如下表：
设备 A（小时） 设备 B（小时） 调试工序（小时） 利润（元）
产品Ⅰ 0 6 1 2
连接而成的线路是关键线路
5、 LP 问题的可行域是凸集。
6、 LP 问题的基本可行解对应可行域的顶点。
7、 LP 问题的最优解一定是可行域的顶点,可行域的顶点也一定是最优解。
8、 若 LP 问题有两个最优解,则它一定有无穷多个最优解.
9、求解 LP 问题时,对取值无约束的自由变量，通常令 x j x j x j,其中∶ x j 单纯形法求得的最优解中,不可能同时出现 x j x j 0 .
季度 合同交货（台）
1
10
2
15
3
25
4
20
生产能力（台） 25 35 30 10
生产成本（千元/台） 保管成本（千元/台季）
103
1.5
111
1.5
110
1.5
113
1.5
答案
一、略
中国石油大学（华东）
二、
1.设 xij 表示 i 井是否连到 j 站
mn
Min z
dij xij
i1 j1
2
5 1
3
4
边 1——2 1——3 2——4 2——5
容量 10 8 2 7
边 3——2 3——4 4——5
容量 5 10 4
2、石油公司所属某仪器厂按合同向勘探单位提供地震勘探仪器，在计划年度内各季度的合同交货
量、该厂的生产能力、生产成本及成品库中的维护与保管成本数据如下表，试建立总成本最低的生
产计划模型并用表上作业法求解一步。
（3）求解（10 分）
2. 某运输问题的运价及各产地、销地的数据如下表: B1 B2 B3 B4 供应
A1 3 11 4 5 7 A2 7 7 3 8 4 A3 1 2 10 6 9
中国石油大学（华东）
需求 3 6 5 6 20 试确定总运费最低的运输方案。（注意：本题存在退化的基本可行解） 五、 1、下图为一运输网络，各边的容量如下表，试安排其流量为 11 的一个可行流。
54 14
15 23 1 2 4 1，故产品Ⅲ值得生产。
0 1 4 3 2 2
四、
1. （1）设状态变量 sk 表示 k 阶段开始时，可供分配的机器台数；决策变量 xk 表示 k 阶段分配给 k 工
厂机器台数，则状态转移方程为： sk1 sk xk
x j 0 ,在用
10、当用两阶段法求解带有大 M 的 LP 模型时，若第一阶段的最优目标函数值为零，则可断言原
LP 模型一定有最优解。
二、建立模型
1.某采油区已建有 n 个计量站 B1，B2…Bn，各站目前尚未被利用的能力为 b1，b2…bn（吨液量/日）。 为适应油田开发的需要，规划在该油区打 m 口调整井 A1，A2…Am，且这些井的位置已经确定。根 据预测，调整井的产量分别为 a1，a2…am（吨液量/日）。考虑到原有计量站富余的能力，决定不另 建新站，而用原有老站分工管辖调整井。按规划要求，每口井只能属于一个计量站。假定 Ai 到 Bj 的距离 dij 已知，试确定各调整井与计量站的关系，使新建集输管线总长度最短。(设定变量，写出 模型)
产品Ⅱ 5 2 1 1
每天可用能力 15 24 5
①建立获利最大的线性规划模型并求解（不考虑整数要求，10 分）
②对获利最大的线性规划模型①，建立其对偶规划模型，并回答其最优解和说明该公司的短缺资源
是哪些？（5 分）
③如该公司新研制的产品Ⅲ对三种资源的单位产品消耗是（3 4 2 )T ，预期盈利为 3 元∕件，试判断
d
2
36
d
2

0
6x1
8x2

d
3

d
3

48
d
3
0
5x1 10x2 60
all var iables positive
三、
1.
x1

7 2
x2

3 2
z 17 2
2. y1 0
y2

1 4
y3

1 2
，短缺资源为设备
B
与调试工序。
3. x3 3 0 2 110
中国石油大学（华东）
《运筹学》综合复习资料
一、是非判断
1、动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策。 2、对于同一个动态规划问题，逆序法与顺序法的解不一样。 3、PERT 计算中，总时差是线路上的时差，可以串用，但单时差是工序的时差，不能串用
4、在 PERT 计算中，将最早节点时刻等于最迟节点时刻、且满足 tL ( j) t(i, j) tE (i) 0 节点
f4 (s4 ) 0
（2）
fk
(sk
)

max
0xk sk
vk sk , xk f k1 sk1 k 3,2,1
sk 1 sk xk
（3） x1 0 x2 2 x3 1 f13 14
2.略 五、
1.
2.略
边 1——2 1——3 2——4 2——5
n
s.t. xij 1 i 1m j 1
m
ai xij b j j 1n
i 1
var iable positive
2.
Min
z

p1 d1

p2
d
2

p3d
3
s.t.
x1 2x2 d1 d1 0 d1 0
4x1
4x2

d
2

2. 某工厂生产两种产品，其原材料供应、设备工时及单件利润等有关数据如下表。
产品
Ⅰ
Ⅱ
限量
原材料（kg/件）
5
设备工时（h/件） 4
利润（元/件）
6Байду номын сангаас
10
60
4
40
8
计划人员要求考虑如下的意见（以先后为序）： (1)由于产品Ⅱ销售疲软，故希望产品Ⅱ的产量不超过产品 I 的一半；
中国石油大学（华东）
(2)最好能节约 4 小时设备工时；
且仅判断产品Ⅲ是否值得生产？（10 分）
四、
1.某公司有某种高效率设备 3 台，拟分配给所属甲、乙、丙工厂，各工厂得到设备后，获利情况如
下表，试建立最优分配方案
工厂
获利
甲
乙
丙
设备台数
0
0
0
0
1
3
5
4
2
7
10
6
3
9
11
11
（1）正确设定状态变量、决策变量并写出状态转移方程（2 分）
（2）写出规范的（形式）基本方程(3 分)