OR1 1
OPERATIONS RESEARCH
运筹学 Ⅰ
—— 怎样把事情做到最好郝英奇
OR1 2
第一章 绪论
1.1题解
Operations 汉语翻译工作、操作、行动、手术、运算
Operations Research
日本 —— 运用学 港台 —— 作业研究中国大陆 —— 运筹学
Operational Research原来名称，意为军事行动研究 —— 历史渊源
OR1 3
绪论
1.2 运筹学的历史早期运筹思想：田忌赛马丁渭修宫沈括运粮
Erlang 1917 排队论
Harris 1920 存储论
Levinson 1930 零售贸易康脱洛维奇 1939 LP
OR1 4
绪论
1.2运筹学的历史军事运筹学阶段德军空袭 防空系统 Blackett
运输船编队空袭逃避深水炸弹轰炸机编队
OR1 5
绪论
1.2运筹学的历史管理运筹学阶段战后人员三分,军队、大学、企业大学：课程、专业、硕士、博士企业：美国钢铁联合公司英国国家煤炭局运筹学在中国,50年代中期引入华罗庚推广 优选法、统筹法中国邮递员问题、运输问题
OR1 6
1.3学科性质
应用学科
Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。
Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。
中国定义：运筹学是应用分析、试验、量化的方法，
对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。
OR1 7
1.4定性与定量
例：店主进货
两者都是常用的决策方法
定性是基础，定量是工具，定量为定性服务。
定性有主观性也有有效性，定量有科学性也有局限性。管理科学的发展，定量越来越多。但定量不可替代定性。
OR1 8
1.5运筹学的模型
模型：真实事物的模仿，主要因素、相互关系、系统结构。
形象模型：如地球仪、沙盘、风洞
模拟模型：建港口，模拟船只到达。学生模拟企业管理系统运行。
数学模型：用符号或数学工具描述现实系统。 V=F（ xi,yj,uk) G(xi,yj,uk)≥0
OR1 9
1.6运筹学的学科体系
规划论：线性规划、非线性规划 |、整数规划、目标规划、动态规划
图论与网络
存储论
排队论
决策论
对策论
计算机仿真
OR1 10
1.7运筹学的工作步骤
确定问题
搜集数据建立模型
检验模型
求解模型
结果分析
结果实施
OR1 11
1.8运筹学与计算机
计算机为运筹学提供解题工具。
本书有现成的程序可以利用
要学会解题的思路与方法，建立模型很重要。
OR1 12
第二章 线性规划与单纯形法
2.1 LP(linear programming)的基本概念
LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。
LP有一组有待决策的变量，
一个线性的目标函数，
一组线性的约束条件 。
OR1 13
2.1.1 LP的数学模型例题 1— 生产计划问题
某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：
产品 A 产品 B 资源限量劳动力设 备原材料
9
4
3
4
5
10
360
200
300
利润 元 /kg 70 120
OR1 14
例题 1建模
问题：如何安排生产计划，使得获利最多？
步骤：
1、确定决策变量：设生产 A产品 x1kg,B产品 x2kg
2、确定目标函数,maxZ=70X1+120X2
3、确定约束条件：人力约束 9X1+4X2≤360
设备约束 4X1+5X2 ≤200
原材料约束 3X1+10X2 ≤300
非负性约束 X1≥0 X2≥0
OR1 15
例题 2—— 配方问题
养海狸鼠 饲料中营养要求,VA每天至少 700克,VB每天至少 30克,VC每天刚好 200克。现有五种饲料，搭配使用，饲料成分如下表：
饲料 Va Vb Vc 价格元 /KG
I
II
III
IV
V
3
2
1
6
18
1
0.5
0.2
2
0.5
0.5
1
0.2
2
0.8
2
7
4
9
5
营养要求 700 30 200
OR1 16
例题 2建模
设抓取饲料 I x1kg;饲料 II x2kg;饲料 III x3kg……
目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5
约束条件,3x2+2x2+x3+6x4+18x5 ≥700
营养要求,x1+0.5x2+0.2x3+2x4+0.5x5 ≥30
0.5x1+x2+0.2x3+2x4+0.8x5 =200
用量要求,x1 ≤50,x2 ≤60,x3 ≤50,x4 ≤70,x5 ≤40
非负性要求,x1 ≥0,x2 ≥0,x3 ≥0,x4 ≥0,x5 ≥0
OR1 17
例题 3：人员安排问题
医院护士 24小时值班，每次值班 8小时。
不同时段需要的护士人数不等。据统计：
序号 时段 最少人数 安排人数
1 06— 10 60 X1
2 10— 14 70 X2
3 14— 18 60 X3
4 18— 22 50 X4
5 22— 02 20 X5
6 02— 06 30 x6
OR1 18
例题 3建模
目标函数,min Z=x1+x2+x3+x4+x5+x6
约束条件,x1+x2 ≥70
x2+x3 ≥60
x3+x4 ≥ 50
x4+x5 ≥20
x5+x6 ≥30
非负性约束,xj ≥0,j=1,2,…6
OR1 19
归纳：线性规划的一般模式
目标函数,max(min)Z=c1x1+c2x2+c3x3+…+c nxn
约束条件,a11x1+a12x2+a13x3+…+a 1nxn ≤(= ≥)b1
a21x1+a22x2+a23x3+…+a 2nxn ≤(= ≥)b2
… … … …
am1x1+am2x2+am3x3+…+a mnxn ≤(= ≥)bn
非负性约束,x1 ≥0,x2 ≥0,…,x n ≥0
OR1 20
2.1.2线性规划图解法
由中学知识可知,y=ax+b是一条直线，同理,Z=70x1+120x2→x 2=70/120x1-Z/120也是一条直线，以 Z为参数的一族等值线。
9x1+4x2 ≤360 → x 1 ≤360/9-4/9x2
是直线 x1=360/9-4/9x2 下方的半平面。
所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。
OR1 21
例 1图示
.
90
80
60
40
20
0 20 40 60 80 100
x1
x2
9x1+4x2≤ 360
4x1+5x2≤200
3x1+10x2≤300
A
B
C
D E F
G
H I
Z=70x1+120x2
OR1 22
概念
概念：
1、可行解：满足所有约束条件的解。
2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。
3、基解：约束条件的交点称为基解（直观）
4、基可行解：基解当中的可行解。
5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形
OR1 23
结论
可行域是个凸集
可行域有有限个顶点
最优值在可行域的顶点上达到
无穷多解的情形
无界解情形
无解情形
OR1 24
2.1.3线性规划的标准型
代数式 maxZ=c1x1+c2x2+…+c nxn
a11x1+a12x2+…+a 1nxn=b1
a21x1+a22x2+…+a 2nxn=b2
… … …
am1x1+am2x2+…+a mnxn=bm
xj≥0 j=1,2,…,n
OR1 25
线性规划的标准型
和式,maxZ=∑cjxj
∑aijxj=bi i=1,2,…,m
xj ≥0 j=1,2,…,n
j=1
n
n
j=1
OR1 26
线性规划的标准型
向量式,maxZ=CX
∑pjxj=bi i=1,2,…,m
xj ≥0 j=1,2,…,n
C=(c1,c2,c3,…,c n)
X=(X1,X2,X3,…,X n) T
n
j=1
OR1 27
线性规划的标准型
矩阵式,maxZ=CX AX=b X ≥0
其中,b=(b1,b2,…,b m)T
a11 a12 …,a1n
A= a21 a22 … a2n
… … …
am1 am2 … amn
OR1 28
标准型的特征
目标函数极大化
约束条件为等式
决策变量非负
OR1 29
非标准型转化为标准型
目标函数极小化转为极大化：
minZ=－ max(－ Z),一个数的极小化等价于其相反数的极大化。
不等式约束的转化,∑aijxj≤bi 加入松弛变量
∑aijxj≥bi 减去剩余变量
非正变量：即 xk ≤0 则令 x’k =－ xk
自由变量：即 xk无约束，令 xk= x’k－ x”k
OR1 30
非标准型转化举例 之一
maxZ=70X1+120X2 maxZ=70X1+120X2
9X1+4X2≤360 9X1+4X2+X3=360
4X1+5X2 ≤200 4X1+5X2 +x4=200
3X1+10X2 ≤300 3X1+10X2+x5 =300
X1≥0 X2≥0 Xj≥0 j=1,2,…,5
OR1 31
非标准型转化举例 之二
minZ=x1+2x2-3x3 maxZ’=x’1－ 2x2+3(x’3－ x”3)
x1+x2+x3 ≤9 － x’1+x2+x’3－ x”3 + x4=9
-x1-2x2+x3 ≥2 x’1－ 2x2+x’3 － x”3 - x5= 2
3x1+x2-3x3=5 － 3x’1+x2－ 3(x’3 － x”3 )=5
x1 ≤0 x2 ≥0 x3无约束 x’1 ≥ 0 x2 ≥0 x’3 ≥0
x”3 ≥0 x4≥0 x5≥0
OR1 32
2.1.4基可行解
基的概念,如前所述 LP标准型和式,maxZ= ∑cjxj ∑aijxj=bi xj ≥0 j=1,2,…,n
矩阵式,maxZ=CX AX=b X ≥0
约束方程的系数矩阵 A的秩为 m，且 m<n。设
A=B+N,B是 A中 m?m阶非奇异子矩阵，则称
B是 LP的一个 基,即,B是 A中 m个线性无关向量组。
n
j=1
n
j=1
OR1 33
基解的概念不失一般性,设 B是 A的前 m列,即
B=(p1,p2,…,p m）,其相对应的变量
XB=(x1,x2,…,x m)T,称为基变量；其余变量
XN=(Xm+1,…,Xn)T称为非基变量。令所有非基变量等于零,则 X=（ x1,x2,… xm,0,…,0)T
称为基解 。
OR1 34
基可行解的概念
基可行解,基解可正可负，负则不可行
（违背非负性约束条件），称满足所有约束条件的基解为 基可行解。
退化的基可行解,若某个基变量取值为零，
则称之为退化的基可行解。
基解的数目：最多 Cmn=n!/m!(n-m)!
OR1 35
例题 6 基可行解说明
maxZ=70X1+120X2 P1 P2 P3 P4 P5
9X1+4X2+X3=360 9 4 1 0 0
4X1+5X2 +x4=200 A= 4 5 0 1 0
3X1+10X2+x5 =300 3 10 0 0 1
Xj≥0 j=1,2,…,5
这里 m=3,n=5。 Cmn=10
OR1 36
例题 6 基可行解说明
基（ p3,p4,p5）,令非基变量 x1,x2=0，则基变量 x3=360,x4=200,x5=300,可行解
基（ p2,p4,p5）,令非基变量 x1=0,x3=0基变量
x2=90,x4=－ 250,x5=－ 600,非可行解
基（ p2,p3,p4 ），令非基变量 x1,x5=0，则基变量 x2=30,x3=240,x4=50,可行解 （ P21图）
OR1 37
2.2单纯形法
2.2.1初始基可行解的确定从系数矩阵中找到一个可行基 B，不妨设 B由 A
的前 m列组成，即 B=(P1,P2,……Pm) 。进行等价变换－－约束方程两端分别左乘 B－ 1 得
X1+ +a’1m+1xm+1+…+ a’1nxn=b’1
x2+ +a’2m+1xm+1+…+ a’2nxn=b’2
…………………………….,
xm+a’mm+1xm+1+…+ a’mnxn=b’m
令非基变量为 0，得基可行解
X(0)=(b1’,b2’,……b m,0,……0 ） T z0=∑cibi’
OR1 38
2.2单纯形法
2.2.2最优性检验,LP经过若干步迭代，成为如下形式：
X1+ +a’1m+1xm+1+…+ a’1nxn=b’1 x1=b’1- ∑a’1jxj
x2+ +a’2m+1xm+1+…+ a’2nxn=b’2 x2=b’2- ∑a’2jxj
…………………………….,……………..
xm+a’mm+1xm+1+…+ a’mnxn=b’m xm=b’m- ∑a’mjxj
OR1 39
单纯形法一般性表示,xi=b’i- ∑a’ijxj i=1,2,…m 将 xi代入目标函数得,Z= ∑ cjxj
= ∑ cixi+ ∑ cjxj
= ∑ci（ b’i- ∑a’ijxj ） + ∑ cjxj
= ∑cibi’+∑(cj- ∑ cia’ij)xj
令,σj= cj- ∑ cia’ij z0=∑cibi’ 则 Z=z0+ ∑ σj xj
σj判别准则,σj ≤0时,达到最优解
OR1 40
单纯形法
2.2.2基变换若存在 σj ≥ 0，则取 max{σj } = σK,相应之非基变量 XK若取非零，将使 Z增加,故令 XK 进基。
令 XK≠0,其余非基变量保持为零。 XK 原是非基变量，取零值,若 XK ≠0 将迫使某个原基变量为零，当 XK取值超过任意 b’i / a’ik 时,将破坏非负性条件,于是令 θ = min {b’i / a’ik a’ik >0 } =b’L/ a’Lk 。
这时原基变量 XL=0，由基变量变成非基变量，
a’Lk处在变量转换的交叉点上，称之为枢轴元素
σj ≥ 0
OR1 41
单纯形法解题举例单纯形表的格式：
Cj C1 C2 … C n
θiCB XB b x1 x2 …,xn
C1
C2
…
Cm
x1
x2
…
xm
b 1
b2
…
bm
a11 a12 … a 1n
a21 a22 … a 2n
… … …
am1 am2… a mn
θ1
θ2
…
θm
σj σ1 σ2 … σ n
OR1 42
Cj C1 C2 … C n
CB XB b X1 X2 X3 X4 X5 θj
0
0
0
X3
X4
X5
360
200
300
9 4 1 0 0
4 5 0 1 0
3 10 0 0 1
90
40
30
σj 0 70 120 0 0 0
0
0
120
X3
X4
X2
240
50
30
7.8 0 1 0 -0.4
2.5 0 0 1 -0.5
0.3 1 0 0 0.1
30.76
20
100
σj 3600 34 0 0 0 -12
70
120
0
X3
X1
X2
84
20
24
0 0 1 -3.12 1.16
1 0 0 0.4 -0.2
0 1 0 -0.12 0.16
σj 4280 0 0 0 -13.6 -5.2
OR1 43
2.2.3单纯形法的计算步骤
找到初始可行基，建立单纯形表
计算检验数，若所有 σj ≤0则得最优解，结束。否则转下步
若某 σK ≥ 0而 P’K ≤0,则最优解无界，结束。否则转下步
根据 max {σj } =σK 原则确定 XK 进基变量；根据 θ
规则,θ = min {b’i / a’ik a’ik >0} = b’L/ a’Lk 确定 XL为出基变量
以 a’Lk 为枢轴元素进行迭代，回到第二步
OR1 44
2.3单纯形法的进一步探讨
2.3.1极小化问题直接求解：检验数的判别由所有 σj ≤0即为最优，变为所有 σj≥ 0则为最优。
人工变量法之一：大 M法 人工变量价值系数 M
例
人工变量法之二：构造目标函数，分阶段求解例
2.3.2无穷多最优解情形：非基变量检验数 σj= 0
2.3.3退化解的情形：有两个以上 θ值相等
OR1 45
2.3.4单纯形法的计算机求解
程序说明
应用举例例题 1
例题 2
OR1 46
2.5LP应用举例之一
例 13合理下料问题料长 7.4米，截成 2.9,2.1,1.5米各 200根。
如何截取余料最少？关键：设变量。
方案料型
1 2 3 4 5 6 7 8
2.9米
2.1米
1.5米
1 2 0 1 0 1 0 0
0 0 2 2 1 1 3 0
3 1 2 0 3 1 0 4
合计残料
7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0
0 0.1 0.2 0.3 0.8 0.9 1.1 1.4
OR1 47
应用举例之二
例 14混合配方问题
A,B,C,D四种原料配制三种产品，三类约束：技术要求、原料限量、市场容量。
已知产品价格和原料价格，求利润最大的配方。关键：设变量。
OR1 48
应用举例之三
例 15.滚动投资问题兹有 100万元闲钱，投资方向有四：
第四年第一年 第二年 第三年
A项目 110%
B项目 135%
C项目 125%
D项目 104%
第五年各年投资什么项目，使第五年末资本总额为最大？
OR1 49
应用举例之四
例 16动态生产计划问题工厂做 n个月的生产计划，第 j月需求量 dj、
正常生产能力 aj、加班生产能力 bj、正常生产成本 cj、加班生产成本 ej、库存能力为 I、库存费用
hj，设期初、期末库存为零。求费用最小的生产计划。
设第月正常生产 xj件，加班生产件 yj，存储 zj
件。则：
本期生产 +上期库存 -本期库存 =本期需求
OR1 50
第三章 对偶问题与灵敏度分析
要求：
了解 LP对偶问题的实际背景了解对偶问题的建立规则与基本性质掌握对偶最优解的计算及其经济解释掌握 LP的灵敏度分析理解计算机输出的影子价格与灵敏度分析的内容
OR1 51
3.1 对偶问题
3.1.1 对偶问题的提出回顾例题 1,现在 A,B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？
产品 A 产品 B 资源限制劳动力设备原材料
9
4
3
4
5
10
360
200
300
单位利润 70 120
OR1 52
对偶模型
设每个工时收费 Y1元，设备台时费用 Y2
元，原材料附加费 Y3元。
出租收入不低于生产收入：
9y1+4y2+3y3 ≥70
4y1+5y2+10y3 ≥120
目标,ω=360y1+200y2+300y3
出租收入越多越好？至少不低于某数
OR1 53
原问题与对偶问题之比较原问题,对偶问题：
maxZ=70X1+120X2 minω=360y1+200y2+300y3
9X1+4X2≤360 9y1+4y2+3y3 ≥70
4X1+5X2≤200 (3.1) 4y1+5y2+10y3 ≥120 (3.2)
3X1+10X2≤300 y1 ≥0,y2 ≥0,y3 ≥0
X1≥0 X2≥0
OR1 54
3.1.2对偶规则原问题一般模型,对偶问题一般模型：
maxZ=CX min ω=Yb
AX ≤b YA ≥C
X ≥0 Y ≥0
OR1 55
对偶规则
原问题有 m个约束条件，对偶问题有 m个变量
原问题有 n个变量，对偶问题有 n个约束条件
原问题的价值系数对应对偶问题的右端项
原问题的右端项对应对偶问题的价值系数
原问题的技术系数矩阵转置后为对偶问题系数矩阵
原问题的约束条件与对偶问题方向相反
原问题与对偶问题优化方向相反
OR1 56
对偶规则
.
原问题 对偶问题目标函数 max min 目标函数约束条件 ≤
≥
=
≥ 变量
≤
无约束
≥
变量符号 ≤
无约束
≥
≤ 约束条件
=
OR1 57
对偶规则简捷记法
原问题标准则对偶问题标准
原问题不标准则对偶问题不标准
例题 2 max ω=7y1+4y2-2y3
minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 ≤3
2x1+x2-4x3+x4+3x5 ≥7 y1 +3y3 ≤2
x1+ 2x3 -x4 ≤4 -4y1+ 2y2 ≤-6
-x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 ≥ 0
x1,x2,x3 ≥0; 3y1 +y3=1
x4 ≤0;x5无限制 y1 ≥ 0y2 ≤ 0y3 无约束
OR1 58
3.1.3对偶问题的基本性质
对称性：对偶问题的对偶问题是原问题
弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值 (鞍型图 )
无界性：原问题无界，对偶问题无可行解
对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为 B，则其对偶问题最优解 Y*=CBB-1
OR1 59
3.1.4对偶最优解的经济解释 — 影子价格
Z= ω=CX=Yb?Z/? b=(Yb)’=Y
Z=Yb= ∑yibi的意义,Y是检验数的反数。在 Y确定的前提下，每增加一个单位的 i种资源，对目标函数的贡献。
结合例题 1讲解影子价格,y1=0:第一种资源过剩
y2=13.6：设备台时最紧张，每增加一个台时,利润增加
13.6元。 y3=5.2…
影子价格所含有的信息,1、资源紧缺状况
2、确定资源转让基价参见,P40 3、取得紧缺资源的代价
OR1 60
3.2灵敏度分析
为什么进行灵敏度分析？
灵敏度分析的两把尺子：
σj =Cj-CBB-1pj≤ 0；? xB= B-1b ≥0
3.2.1 价值系数的灵敏度分析
Cj变化到什么程度可以保持最优基不变？用?
（参看 P96）
例题 4,87.5 ≤ C2 ≤ 233.33； 36 ≤ C1 ≤ 96
OR1 61
灵敏度分析
右端项的灵敏度分析：
bi变化到什么程度可以保持最优基不变？用尺度?
xB= B-1b ≥0
例题 5,1 -3.12 1.16 360
B-1b= 0 0.4 -0.2 200 ≥0
0 -0.12 0.16 b3
b3的变化范围,227.586 ≤ b3 ≤ 400
OR1 62
其它形式的灵敏度分析新产品的分析：
在资源结构没有变化的条件下，是否生产这种新产品，就看它的竞争力如何。
例题 6：新增一种 C产品，单位利润 110元，使用劳动力 6工时，设备 5台时，原材料 7公斤，问要否调整产品结构？
先算检验数 σj =Cj-CBB-1pj
σ6=C6-YP6=110-（ 0,13.6,5.2）（ 6,5,7） T
= 110-104.4=5.6 大于零，有利可图，将 P6左乘 B-1，
加入到末表之中，继续迭代，直到求得最优解。
OR1 63
3.3用计算机进行灵敏度分析
例题 7 参见 P102
OR1 64
习题课：
P78—— 2.10
（ 1）唯一最优解,H3 ≤ 0,H5≤ 0,H1 ≥0
（ 2）无穷多最优解,H3=0,H1 ≥0,H5? 0,H2>0
或 H5=0,H1 ≥0,H3? 0,H4>0
（ 3）无界解,H5≥0,H4? 0,H1 ≥0,H3? 0
（ 4）退化 最优 解,H1=0,H3? 0,H5? 0
（ 5）非最优解,X1进基,X2出基：
H1 ≥0,H3>0,H2>0,5H
2
< H17
OR1 65
习题课：
P79—— 2.11
1、对 2、错，可能有最优解 3、对
4、对 5、错 6、错 7、错在“可行”
8、对 9、错
OR1 66
习题课：
P81—— 2.16
设白天电视广告 X1个，黄金时间电视广告 X2个，
广播广告 X3个，杂志广告 X4个
maxZ=40X1+90X2+50X3+2X4
8X1+15X2+6X3+3X4≤16
30X1+40X2+20X3+X4≥200
8X1+15X2 ≤10
X1 ≥3 X2 ≥2
X3 ≥5 X3 ≤10
X4 ≥5 X4 ≤10 X j≥0 j=1,2,3,4
OR1 67
习题课：
P81—— 2.17
设 A产品生产 X1单位,B产品生产 X2单位，
C产品销毁 X3单位
maxZ=5X1+10X2+3（ 2X2-X3） -1X3
2X1+3X2≤200
3X1+4X2≤240
2X2-X3≤10 X1,X2,X3 ≥0
OR1 68
习题课：
P107—— 3.2
1、对，根据若对偶性
2、对，同上
3、对，同上
4、对，因为影子价格是每增加一个单位的某种资源，对目标函数的贡献程度
5、对，根据强对偶定理
OR1 69
习题课
P107—— 3.5 注：目标函数为最大化
1、这是线性规划的逆运算
对偶问题最优解,
Y1=4,Y2=2,Y3=0,Y4=4,Y5=0
OR1 70
习题课
P109—— 3.8
1、原问题的最优解,X1=6,X5=10，其余为零 ;对偶问题最优解,Y1=2,Y2=0
C1的变化范围：以 C1代入末表,C1 ≥1
右端项变化范围,xB= B-1b ≥0
b1 ≥-6,?b2≥-10
OPERATIONS RESEARCH
运筹学 Ⅰ
—— 怎样把事情做到最好郝英奇
OR1 2
第一章 绪论
1.1题解
Operations 汉语翻译工作、操作、行动、手术、运算
Operations Research
日本 —— 运用学 港台 —— 作业研究中国大陆 —— 运筹学
Operational Research原来名称，意为军事行动研究 —— 历史渊源
OR1 3
绪论
1.2 运筹学的历史早期运筹思想：田忌赛马丁渭修宫沈括运粮
Erlang 1917 排队论
Harris 1920 存储论
Levinson 1930 零售贸易康脱洛维奇 1939 LP
OR1 4
绪论
1.2运筹学的历史军事运筹学阶段德军空袭 防空系统 Blackett
运输船编队空袭逃避深水炸弹轰炸机编队
OR1 5
绪论
1.2运筹学的历史管理运筹学阶段战后人员三分,军队、大学、企业大学：课程、专业、硕士、博士企业：美国钢铁联合公司英国国家煤炭局运筹学在中国,50年代中期引入华罗庚推广 优选法、统筹法中国邮递员问题、运输问题
OR1 6
1.3学科性质
应用学科
Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。
Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。
中国定义：运筹学是应用分析、试验、量化的方法，
对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。
OR1 7
1.4定性与定量
例：店主进货
两者都是常用的决策方法
定性是基础，定量是工具，定量为定性服务。
定性有主观性也有有效性，定量有科学性也有局限性。管理科学的发展，定量越来越多。但定量不可替代定性。
OR1 8
1.5运筹学的模型
模型：真实事物的模仿，主要因素、相互关系、系统结构。
形象模型：如地球仪、沙盘、风洞
模拟模型：建港口，模拟船只到达。学生模拟企业管理系统运行。
数学模型：用符号或数学工具描述现实系统。 V=F（ xi,yj,uk) G(xi,yj,uk)≥0
OR1 9
1.6运筹学的学科体系
规划论：线性规划、非线性规划 |、整数规划、目标规划、动态规划
图论与网络
存储论
排队论
决策论
对策论
计算机仿真
OR1 10
1.7运筹学的工作步骤
确定问题
搜集数据建立模型
检验模型
求解模型
结果分析
结果实施
OR1 11
1.8运筹学与计算机
计算机为运筹学提供解题工具。
本书有现成的程序可以利用
要学会解题的思路与方法，建立模型很重要。
OR1 12
第二章 线性规划与单纯形法
2.1 LP(linear programming)的基本概念
LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。
LP有一组有待决策的变量，
一个线性的目标函数，
一组线性的约束条件 。
OR1 13
2.1.1 LP的数学模型例题 1— 生产计划问题
某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：
产品 A 产品 B 资源限量劳动力设 备原材料
9
4
3
4
5
10
360
200
300
利润 元 /kg 70 120
OR1 14
例题 1建模
问题：如何安排生产计划，使得获利最多？
步骤：
1、确定决策变量：设生产 A产品 x1kg,B产品 x2kg
2、确定目标函数,maxZ=70X1+120X2
3、确定约束条件：人力约束 9X1+4X2≤360
设备约束 4X1+5X2 ≤200
原材料约束 3X1+10X2 ≤300
非负性约束 X1≥0 X2≥0
OR1 15
例题 2—— 配方问题
养海狸鼠 饲料中营养要求,VA每天至少 700克,VB每天至少 30克,VC每天刚好 200克。现有五种饲料，搭配使用，饲料成分如下表：
饲料 Va Vb Vc 价格元 /KG
I
II
III
IV
V
3
2
1
6
18
1
0.5
0.2
2
0.5
0.5
1
0.2
2
0.8
2
7
4
9
5
营养要求 700 30 200
OR1 16
例题 2建模
设抓取饲料 I x1kg;饲料 II x2kg;饲料 III x3kg……
目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5
约束条件,3x2+2x2+x3+6x4+18x5 ≥700
营养要求,x1+0.5x2+0.2x3+2x4+0.5x5 ≥30
0.5x1+x2+0.2x3+2x4+0.8x5 =200
用量要求,x1 ≤50,x2 ≤60,x3 ≤50,x4 ≤70,x5 ≤40
非负性要求,x1 ≥0,x2 ≥0,x3 ≥0,x4 ≥0,x5 ≥0
OR1 17
例题 3：人员安排问题
医院护士 24小时值班，每次值班 8小时。
不同时段需要的护士人数不等。据统计：
序号 时段 最少人数 安排人数
1 06— 10 60 X1
2 10— 14 70 X2
3 14— 18 60 X3
4 18— 22 50 X4
5 22— 02 20 X5
6 02— 06 30 x6
OR1 18
例题 3建模
目标函数,min Z=x1+x2+x3+x4+x5+x6
约束条件,x1+x2 ≥70
x2+x3 ≥60
x3+x4 ≥ 50
x4+x5 ≥20
x5+x6 ≥30
非负性约束,xj ≥0,j=1,2,…6
OR1 19
归纳：线性规划的一般模式
目标函数,max(min)Z=c1x1+c2x2+c3x3+…+c nxn
约束条件,a11x1+a12x2+a13x3+…+a 1nxn ≤(= ≥)b1
a21x1+a22x2+a23x3+…+a 2nxn ≤(= ≥)b2
… … … …
am1x1+am2x2+am3x3+…+a mnxn ≤(= ≥)bn
非负性约束,x1 ≥0,x2 ≥0,…,x n ≥0
OR1 20
2.1.2线性规划图解法
由中学知识可知,y=ax+b是一条直线，同理,Z=70x1+120x2→x 2=70/120x1-Z/120也是一条直线，以 Z为参数的一族等值线。
9x1+4x2 ≤360 → x 1 ≤360/9-4/9x2
是直线 x1=360/9-4/9x2 下方的半平面。
所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。
OR1 21
例 1图示
.
90
80
60
40
20
0 20 40 60 80 100
x1
x2
9x1+4x2≤ 360
4x1+5x2≤200
3x1+10x2≤300
A
B
C
D E F
G
H I
Z=70x1+120x2
OR1 22
概念
概念：
1、可行解：满足所有约束条件的解。
2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。
3、基解：约束条件的交点称为基解（直观）
4、基可行解：基解当中的可行解。
5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形
OR1 23
结论
可行域是个凸集
可行域有有限个顶点
最优值在可行域的顶点上达到
无穷多解的情形
无界解情形
无解情形
OR1 24
2.1.3线性规划的标准型
代数式 maxZ=c1x1+c2x2+…+c nxn
a11x1+a12x2+…+a 1nxn=b1
a21x1+a22x2+…+a 2nxn=b2
… … …
am1x1+am2x2+…+a mnxn=bm
xj≥0 j=1,2,…,n
OR1 25
线性规划的标准型
和式,maxZ=∑cjxj
∑aijxj=bi i=1,2,…,m
xj ≥0 j=1,2,…,n
j=1
n
n
j=1
OR1 26
线性规划的标准型
向量式,maxZ=CX
∑pjxj=bi i=1,2,…,m
xj ≥0 j=1,2,…,n
C=(c1,c2,c3,…,c n)
X=(X1,X2,X3,…,X n) T
n
j=1
OR1 27
线性规划的标准型
矩阵式,maxZ=CX AX=b X ≥0
其中,b=(b1,b2,…,b m)T
a11 a12 …,a1n
A= a21 a22 … a2n
… … …
am1 am2 … amn
OR1 28
标准型的特征
目标函数极大化
约束条件为等式
决策变量非负
OR1 29
非标准型转化为标准型
目标函数极小化转为极大化：
minZ=－ max(－ Z),一个数的极小化等价于其相反数的极大化。
不等式约束的转化,∑aijxj≤bi 加入松弛变量
∑aijxj≥bi 减去剩余变量
非正变量：即 xk ≤0 则令 x’k =－ xk
自由变量：即 xk无约束，令 xk= x’k－ x”k
OR1 30
非标准型转化举例 之一
maxZ=70X1+120X2 maxZ=70X1+120X2
9X1+4X2≤360 9X1+4X2+X3=360
4X1+5X2 ≤200 4X1+5X2 +x4=200
3X1+10X2 ≤300 3X1+10X2+x5 =300
X1≥0 X2≥0 Xj≥0 j=1,2,…,5
OR1 31
非标准型转化举例 之二
minZ=x1+2x2-3x3 maxZ’=x’1－ 2x2+3(x’3－ x”3)
x1+x2+x3 ≤9 － x’1+x2+x’3－ x”3 + x4=9
-x1-2x2+x3 ≥2 x’1－ 2x2+x’3 － x”3 - x5= 2
3x1+x2-3x3=5 － 3x’1+x2－ 3(x’3 － x”3 )=5
x1 ≤0 x2 ≥0 x3无约束 x’1 ≥ 0 x2 ≥0 x’3 ≥0
x”3 ≥0 x4≥0 x5≥0
OR1 32
2.1.4基可行解
基的概念,如前所述 LP标准型和式,maxZ= ∑cjxj ∑aijxj=bi xj ≥0 j=1,2,…,n
矩阵式,maxZ=CX AX=b X ≥0
约束方程的系数矩阵 A的秩为 m，且 m<n。设
A=B+N,B是 A中 m?m阶非奇异子矩阵，则称
B是 LP的一个 基,即,B是 A中 m个线性无关向量组。
n
j=1
n
j=1
OR1 33
基解的概念不失一般性,设 B是 A的前 m列,即
B=(p1,p2,…,p m）,其相对应的变量
XB=(x1,x2,…,x m)T,称为基变量；其余变量
XN=(Xm+1,…,Xn)T称为非基变量。令所有非基变量等于零,则 X=（ x1,x2,… xm,0,…,0)T
称为基解 。
OR1 34
基可行解的概念
基可行解,基解可正可负，负则不可行
（违背非负性约束条件），称满足所有约束条件的基解为 基可行解。
退化的基可行解,若某个基变量取值为零，
则称之为退化的基可行解。
基解的数目：最多 Cmn=n!/m!(n-m)!
OR1 35
例题 6 基可行解说明
maxZ=70X1+120X2 P1 P2 P3 P4 P5
9X1+4X2+X3=360 9 4 1 0 0
4X1+5X2 +x4=200 A= 4 5 0 1 0
3X1+10X2+x5 =300 3 10 0 0 1
Xj≥0 j=1,2,…,5
这里 m=3,n=5。 Cmn=10
OR1 36
例题 6 基可行解说明
基（ p3,p4,p5）,令非基变量 x1,x2=0，则基变量 x3=360,x4=200,x5=300,可行解
基（ p2,p4,p5）,令非基变量 x1=0,x3=0基变量
x2=90,x4=－ 250,x5=－ 600,非可行解
基（ p2,p3,p4 ），令非基变量 x1,x5=0，则基变量 x2=30,x3=240,x4=50,可行解 （ P21图）
OR1 37
2.2单纯形法
2.2.1初始基可行解的确定从系数矩阵中找到一个可行基 B，不妨设 B由 A
的前 m列组成，即 B=(P1,P2,……Pm) 。进行等价变换－－约束方程两端分别左乘 B－ 1 得
X1+ +a’1m+1xm+1+…+ a’1nxn=b’1
x2+ +a’2m+1xm+1+…+ a’2nxn=b’2
…………………………….,
xm+a’mm+1xm+1+…+ a’mnxn=b’m
令非基变量为 0，得基可行解
X(0)=(b1’,b2’,……b m,0,……0 ） T z0=∑cibi’
OR1 38
2.2单纯形法
2.2.2最优性检验,LP经过若干步迭代，成为如下形式：
X1+ +a’1m+1xm+1+…+ a’1nxn=b’1 x1=b’1- ∑a’1jxj
x2+ +a’2m+1xm+1+…+ a’2nxn=b’2 x2=b’2- ∑a’2jxj
…………………………….,……………..
xm+a’mm+1xm+1+…+ a’mnxn=b’m xm=b’m- ∑a’mjxj
OR1 39
单纯形法一般性表示,xi=b’i- ∑a’ijxj i=1,2,…m 将 xi代入目标函数得,Z= ∑ cjxj
= ∑ cixi+ ∑ cjxj
= ∑ci（ b’i- ∑a’ijxj ） + ∑ cjxj
= ∑cibi’+∑(cj- ∑ cia’ij)xj
令,σj= cj- ∑ cia’ij z0=∑cibi’ 则 Z=z0+ ∑ σj xj
σj判别准则,σj ≤0时,达到最优解
OR1 40
单纯形法
2.2.2基变换若存在 σj ≥ 0，则取 max{σj } = σK,相应之非基变量 XK若取非零，将使 Z增加,故令 XK 进基。
令 XK≠0,其余非基变量保持为零。 XK 原是非基变量，取零值,若 XK ≠0 将迫使某个原基变量为零，当 XK取值超过任意 b’i / a’ik 时,将破坏非负性条件,于是令 θ = min {b’i / a’ik a’ik >0 } =b’L/ a’Lk 。
这时原基变量 XL=0，由基变量变成非基变量，
a’Lk处在变量转换的交叉点上，称之为枢轴元素
σj ≥ 0
OR1 41
单纯形法解题举例单纯形表的格式：
Cj C1 C2 … C n
θiCB XB b x1 x2 …,xn
C1
C2
…
Cm
x1
x2
…
xm
b 1
b2
…
bm
a11 a12 … a 1n
a21 a22 … a 2n
… … …
am1 am2… a mn
θ1
θ2
…
θm
σj σ1 σ2 … σ n
OR1 42
Cj C1 C2 … C n
CB XB b X1 X2 X3 X4 X5 θj
0
0
0
X3
X4
X5
360
200
300
9 4 1 0 0
4 5 0 1 0
3 10 0 0 1
90
40
30
σj 0 70 120 0 0 0
0
0
120
X3
X4
X2
240
50
30
7.8 0 1 0 -0.4
2.5 0 0 1 -0.5
0.3 1 0 0 0.1
30.76
20
100
σj 3600 34 0 0 0 -12
70
120
0
X3
X1
X2
84
20
24
0 0 1 -3.12 1.16
1 0 0 0.4 -0.2
0 1 0 -0.12 0.16
σj 4280 0 0 0 -13.6 -5.2
OR1 43
2.2.3单纯形法的计算步骤
找到初始可行基，建立单纯形表
计算检验数，若所有 σj ≤0则得最优解，结束。否则转下步
若某 σK ≥ 0而 P’K ≤0,则最优解无界，结束。否则转下步
根据 max {σj } =σK 原则确定 XK 进基变量；根据 θ
规则,θ = min {b’i / a’ik a’ik >0} = b’L/ a’Lk 确定 XL为出基变量
以 a’Lk 为枢轴元素进行迭代，回到第二步
OR1 44
2.3单纯形法的进一步探讨
2.3.1极小化问题直接求解：检验数的判别由所有 σj ≤0即为最优，变为所有 σj≥ 0则为最优。
人工变量法之一：大 M法 人工变量价值系数 M
例
人工变量法之二：构造目标函数，分阶段求解例
2.3.2无穷多最优解情形：非基变量检验数 σj= 0
2.3.3退化解的情形：有两个以上 θ值相等
OR1 45
2.3.4单纯形法的计算机求解
程序说明
应用举例例题 1
例题 2
OR1 46
2.5LP应用举例之一
例 13合理下料问题料长 7.4米，截成 2.9,2.1,1.5米各 200根。
如何截取余料最少？关键：设变量。
方案料型
1 2 3 4 5 6 7 8
2.9米
2.1米
1.5米
1 2 0 1 0 1 0 0
0 0 2 2 1 1 3 0
3 1 2 0 3 1 0 4
合计残料
7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0
0 0.1 0.2 0.3 0.8 0.9 1.1 1.4
OR1 47
应用举例之二
例 14混合配方问题
A,B,C,D四种原料配制三种产品，三类约束：技术要求、原料限量、市场容量。
已知产品价格和原料价格，求利润最大的配方。关键：设变量。
OR1 48
应用举例之三
例 15.滚动投资问题兹有 100万元闲钱，投资方向有四：
第四年第一年 第二年 第三年
A项目 110%
B项目 135%
C项目 125%
D项目 104%
第五年各年投资什么项目，使第五年末资本总额为最大？
OR1 49
应用举例之四
例 16动态生产计划问题工厂做 n个月的生产计划，第 j月需求量 dj、
正常生产能力 aj、加班生产能力 bj、正常生产成本 cj、加班生产成本 ej、库存能力为 I、库存费用
hj，设期初、期末库存为零。求费用最小的生产计划。
设第月正常生产 xj件，加班生产件 yj，存储 zj
件。则：
本期生产 +上期库存 -本期库存 =本期需求
OR1 50
第三章 对偶问题与灵敏度分析
要求：
了解 LP对偶问题的实际背景了解对偶问题的建立规则与基本性质掌握对偶最优解的计算及其经济解释掌握 LP的灵敏度分析理解计算机输出的影子价格与灵敏度分析的内容
OR1 51
3.1 对偶问题
3.1.1 对偶问题的提出回顾例题 1,现在 A,B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？
产品 A 产品 B 资源限制劳动力设备原材料
9
4
3
4
5
10
360
200
300
单位利润 70 120
OR1 52
对偶模型
设每个工时收费 Y1元，设备台时费用 Y2
元，原材料附加费 Y3元。
出租收入不低于生产收入：
9y1+4y2+3y3 ≥70
4y1+5y2+10y3 ≥120
目标,ω=360y1+200y2+300y3
出租收入越多越好？至少不低于某数
OR1 53
原问题与对偶问题之比较原问题,对偶问题：
maxZ=70X1+120X2 minω=360y1+200y2+300y3
9X1+4X2≤360 9y1+4y2+3y3 ≥70
4X1+5X2≤200 (3.1) 4y1+5y2+10y3 ≥120 (3.2)
3X1+10X2≤300 y1 ≥0,y2 ≥0,y3 ≥0
X1≥0 X2≥0
OR1 54
3.1.2对偶规则原问题一般模型,对偶问题一般模型：
maxZ=CX min ω=Yb
AX ≤b YA ≥C
X ≥0 Y ≥0
OR1 55
对偶规则
原问题有 m个约束条件，对偶问题有 m个变量
原问题有 n个变量，对偶问题有 n个约束条件
原问题的价值系数对应对偶问题的右端项
原问题的右端项对应对偶问题的价值系数
原问题的技术系数矩阵转置后为对偶问题系数矩阵
原问题的约束条件与对偶问题方向相反
原问题与对偶问题优化方向相反
OR1 56
对偶规则
.
原问题 对偶问题目标函数 max min 目标函数约束条件 ≤
≥
=
≥ 变量
≤
无约束
≥
变量符号 ≤
无约束
≥
≤ 约束条件
=
OR1 57
对偶规则简捷记法
原问题标准则对偶问题标准
原问题不标准则对偶问题不标准
例题 2 max ω=7y1+4y2-2y3
minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 ≤3
2x1+x2-4x3+x4+3x5 ≥7 y1 +3y3 ≤2
x1+ 2x3 -x4 ≤4 -4y1+ 2y2 ≤-6
-x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 ≥ 0
x1,x2,x3 ≥0; 3y1 +y3=1
x4 ≤0;x5无限制 y1 ≥ 0y2 ≤ 0y3 无约束
OR1 58
3.1.3对偶问题的基本性质
对称性：对偶问题的对偶问题是原问题
弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值 (鞍型图 )
无界性：原问题无界，对偶问题无可行解
对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为 B，则其对偶问题最优解 Y*=CBB-1
OR1 59
3.1.4对偶最优解的经济解释 — 影子价格
Z= ω=CX=Yb?Z/? b=(Yb)’=Y
Z=Yb= ∑yibi的意义,Y是检验数的反数。在 Y确定的前提下，每增加一个单位的 i种资源，对目标函数的贡献。
结合例题 1讲解影子价格,y1=0:第一种资源过剩
y2=13.6：设备台时最紧张，每增加一个台时,利润增加
13.6元。 y3=5.2…
影子价格所含有的信息,1、资源紧缺状况
2、确定资源转让基价参见,P40 3、取得紧缺资源的代价
OR1 60
3.2灵敏度分析
为什么进行灵敏度分析？
灵敏度分析的两把尺子：
σj =Cj-CBB-1pj≤ 0；? xB= B-1b ≥0
3.2.1 价值系数的灵敏度分析
Cj变化到什么程度可以保持最优基不变？用?
（参看 P96）
例题 4,87.5 ≤ C2 ≤ 233.33； 36 ≤ C1 ≤ 96
OR1 61
灵敏度分析
右端项的灵敏度分析：
bi变化到什么程度可以保持最优基不变？用尺度?
xB= B-1b ≥0
例题 5,1 -3.12 1.16 360
B-1b= 0 0.4 -0.2 200 ≥0
0 -0.12 0.16 b3
b3的变化范围,227.586 ≤ b3 ≤ 400
OR1 62
其它形式的灵敏度分析新产品的分析：
在资源结构没有变化的条件下，是否生产这种新产品，就看它的竞争力如何。
例题 6：新增一种 C产品，单位利润 110元，使用劳动力 6工时，设备 5台时，原材料 7公斤，问要否调整产品结构？
先算检验数 σj =Cj-CBB-1pj
σ6=C6-YP6=110-（ 0,13.6,5.2）（ 6,5,7） T
= 110-104.4=5.6 大于零，有利可图，将 P6左乘 B-1，
加入到末表之中，继续迭代，直到求得最优解。
OR1 63
3.3用计算机进行灵敏度分析
例题 7 参见 P102
OR1 64
习题课：
P78—— 2.10
（ 1）唯一最优解,H3 ≤ 0,H5≤ 0,H1 ≥0
（ 2）无穷多最优解,H3=0,H1 ≥0,H5? 0,H2>0
或 H5=0,H1 ≥0,H3? 0,H4>0
（ 3）无界解,H5≥0,H4? 0,H1 ≥0,H3? 0
（ 4）退化 最优 解,H1=0,H3? 0,H5? 0
（ 5）非最优解,X1进基,X2出基：
H1 ≥0,H3>0,H2>0,5H
2
< H17
OR1 65
习题课：
P79—— 2.11
1、对 2、错，可能有最优解 3、对
4、对 5、错 6、错 7、错在“可行”
8、对 9、错
OR1 66
习题课：
P81—— 2.16
设白天电视广告 X1个，黄金时间电视广告 X2个，
广播广告 X3个，杂志广告 X4个
maxZ=40X1+90X2+50X3+2X4
8X1+15X2+6X3+3X4≤16
30X1+40X2+20X3+X4≥200
8X1+15X2 ≤10
X1 ≥3 X2 ≥2
X3 ≥5 X3 ≤10
X4 ≥5 X4 ≤10 X j≥0 j=1,2,3,4
OR1 67
习题课：
P81—— 2.17
设 A产品生产 X1单位,B产品生产 X2单位，
C产品销毁 X3单位
maxZ=5X1+10X2+3（ 2X2-X3） -1X3
2X1+3X2≤200
3X1+4X2≤240
2X2-X3≤10 X1,X2,X3 ≥0
OR1 68
习题课：
P107—— 3.2
1、对，根据若对偶性
2、对，同上
3、对，同上
4、对，因为影子价格是每增加一个单位的某种资源，对目标函数的贡献程度
5、对，根据强对偶定理
OR1 69
习题课
P107—— 3.5 注：目标函数为最大化
1、这是线性规划的逆运算
对偶问题最优解,
Y1=4,Y2=2,Y3=0,Y4=4,Y5=0
OR1 70
习题课
P109—— 3.8
1、原问题的最优解,X1=6,X5=10，其余为零 ;对偶问题最优解,Y1=2,Y2=0
C1的变化范围：以 C1代入末表,C1 ≥1
右端项变化范围,xB= B-1b ≥0
b1 ≥-6,?b2≥-10
