运筹学通论实验课ppt对于一个标准形式的线性规划,利用单纯 形法把它

m
n
m
z cibi (cj ciaij)xj
i1
jm 1
i1
约束条件右端常数 变量 xj 所对应的约束条件系数
第24页
m
n
m
z cibi (cj ciaij)xj
第12页
可引入人工变量凑出初始可行基：
maxz c1x1 c2 x2 cn xn Mxn1 Mxnm
a11x1 a12x2 ... a1n xn xn1
b1
s.t
.am1
x1
am2
x2
... ...
amn
xn
xnm bm
x1, ..., xn, xn1 ,..., xnm 0
第4页
max z c1 x 1 c 2 x 2 c n x n
a 11 x 1 a 12 x 2 ... a 1 n x n b1
s
.
t
.
a
m
1
x
1
am 2 x2
... ...
a mn
xn
bm
x 1 , ... , x n 0
第5页
maxz c1 x1 c2 x2 cn xn
... xmam,m1xm1 ...amnxn bm
xj 0, j1,..n .,
第19页
m
n
Mazx cixi cjxj
i1
jm1
s.t.
n
xi aijxj bi,i1,..m ., jm 1
xj 0,j1,..n .,
第20页
m
n
Mazx cixi cjxj
i1
jm1
（1）
s.t.
n
xi bi aijxj,i1,..m .,（2） jm 1

划问题化成如下的标准型：
max Z x1 2x2 3x4 3x5 0x6 0x7
x1 x2 x4 x5 x6 7 x1 x2 x4 x5 x7 2 3x1 x2 2x4 2x5 5 x1, x2, x4, , x7 0
第二节 线性规划问题的图解法及几何意义
一、线性规划问题的解的概念
(1.4)
标准型具有如下特点： （1）目标函数求最大值； （2）所求的变量都要求是非负的； （3）所有的约束条件都是等式； （4）常数项非负。 综合以上的讨论可以说明任何形式的线 性规划问题都可以通过上述手段把非标准 型的线性规划问题化成标准型。现举例如 下：
例1－4 试将如下线性规划问题化成标准型
多样性给讨论问题带来了不便。为了便于今后讨论，我 们规定线性规划问题的标准型为：
max Z c1x1 c2x2 cnxn
a11x1 a12x2 a21x1 a22x2
a1nxn b1 a2nxn b2
am1x1 am2x2 amnxn bm
x1, x2 , , xn 0
例1－1：（计划安排问题）某工厂在计划期内安排
生产Ⅰ、Ⅱ两种产品，已知生产单位产品所占用的
设备A、B的台时、原材料的消耗及两种产品每件可
获利润见表所示：
I
II 资源总量
设备A(h)
0
3
15
设备B(h)
4
0
12
原材料(公斤)
2
2
14
利润(元)
2
3
问如何安排计划使该工厂获利最多？
解: 假设 x1、x2分别表示在计划期内生产
二、线性规划问题的图解法
对于简单的线性规划问题(只有两个决策变量的
线性规划问题)，我们可以通过图解法对它进行求解

Max Z = 50 x1 + 30 x2
第3步 --表示约束条件
4x1+3x2 120（木工工时限制） 2x1+x2 50 （油漆工工时限制）
x1，x2≥0 （变量取非负值限制）
该计划的数学模型
max Z=50x1+30x2 4x1+3x2 120
s.t.
2x1+ x2 50 x1, x2 0
问如何组织生产才能使每月的销售收入最大？
• 第1步 -确定决策变量
是问题中要确定的未知量
xx •设
1 ——桌子的产量 2 ——椅子的产量
，表明规划中的用数量表 示的方案、措施，可由决 策者决定和控制。
z ——利润
x1
x2
第2步 --定义目标函数
Max Z = 50 x1 + 30 x2
第2步 --定义目标函数
线性规模解决的问题
• 给定一定数量的人力、物力、财力等资源， 研究如何充分利用，以发挥其最大效果
• 已给定计划任务，研究如何统筹安排，用最 少的人力、物力、财力去完成
2、线性规划问题的数学模型
线性规划数学模型三要素：
决策变量、目标函数、约束条件
➢ 每一个线性规划问题都有一组决策变量 (x1, x2, ……, xn) , 这组决策变量的值就代表 一个具体方案。
1、问题的提出
例1.1 生产计划问题（资源利用问题） 某家具厂生产桌子和椅子两种家具。 桌子售价50元/个，椅子销售价格30元/个。 需要木工和油漆工两种工种。 生产一个桌子需要木工4小时，油漆工2小时。 生产一个椅子需要木工3小时，油漆工1小时。 该厂每个月可用木工工时为120小时， 油漆工工时为50小时。
第1工厂投污水的水质要求 ：(2 x1) 2 500 1000

为变量xj关于基B的判别数，j=1,2, -------, n。
7 2020/11/2
五、 单纯形方法
2、判别向量与判别数： （的b）判λ别N=向CN量-C，BB其-1中N为任对一应分基量Bλ的j=c所j-C有BB非-1基Aj变量XN 为-非---基-, 变n。量xj关于基B的判别数，j=m+1,m+2, ----（c）所有基变量的判别向量是零向量，所有基变
（一）人工变量消除法——M法 2、M法的辅助线性规划问题：
原问题：
Max z=c1x1+c2x2+……+cnxn s.t. a11x1+a12x2+……+a1nxn=b1 a21 x1+ a22x2+…… +a2nxn =b2
……
am1x1+am2x2+……+amnxn=bm x1,x2, ……,xn ≥ 0
函数值Z/ >0，则原问题无解。 [证明]（请同学们自己做一做）。 （3）辅助问题在最优基B下目标函数的值Z/=0，此时有 两种情况：第一种情况，若辅助问题的最优基B对应的 基变量中无人工变量，则该最优基也是原问题的可行 基，这时候只要在单纯形表中去掉人工变量所在的列 和最后一行，即可得到原问题的初始可行单纯形表。
9 2020/11/2
五、 单纯形方法
（三）单纯形方法：表上作业法
1、单纯形表的构造
方法1：C-CBB-1A=(CB,CN)-CBB-1(B,N) =(0,CN-CBB-1N)
两边同乘上X得：
（C-CBB-1A）X= (0,CN-CBB-1N)X，化简得： Z=CBB-1b+(CN-CBB-1N) XN
3 X2 1.5 0.5 1 0.25 0

x1 ，x2 ，… ，xn ≥ 0
2.基本过程:
1）加入人工变量;
2）通过单纯形法的迭带,将虚拟的人 工变量从原来的基变量中替换出去, 变成非基变量,使每一个人工变量都 等于0.反之,如果不能都变为非基变 量,表明原问题无可行解.
(一)、大M法：
2.4 单纯形法补遗
2.4.1 进基变量的相持及其突破
Y
结束
N
沿边界找新
的基本可行解
2.1 单纯形法的基本思想
单纯形法的三种形式：1）方程组形式； 2）表格形式；3）矩阵形式。
2.1.1 方程组形式的单纯形法
maxZ=3X1 +5X2
X1
+X3
=8
2X2 +X4 =12
3X1+4X2
+X5 =36
X1 … X5 0
解：(1)、确定初始可行解
B=(a3 a4 a5)=I Z -3X1-5X2 =0 X3 =8- X1 X4=12-2X2
此时可以确定X5为离基变量
Z
+1/2X4 +X5 =42
X3 +2/3X4 -1/3X5 =4
X2 +1/2X4 =6
X1 -2/3X4+1/3X5=4
令X4 =X5 =0
X =(4, 6, 4, 0, 0)T Z =42
。此时4=1/2, 5=1, Z值不
再增大了,X值是最优基本解
即:X*=(4,6)T,Z*=42
X6
X7
CB XB -36 M -M -6 -M -4 0
0
M
0
0
0
X3 100
2
3
1
00
0

x1
L2
x1
x1
32 2020-5-31
def3：满足LP中所有约束条件（不等式或等式 约束）的点必在这些约束条件所对应区域所围 成的公共区域D内，则称此公共区域D为LP的 可行域。
例1
400 2x1+x2=400
300
B(50,250)
x2=250
C(100,200)
200
D
100
x1+x2=300
a11 a12
A
a21
谢谢阅读am1
a22 am 2
a1n a2n
amn
n
max z
cjxj
j 1
s.t
n
aij x j bi
x
j
j 1
0,
j 1~ n
bi 0, i 1 ~ m
max z CX
s.t AX b
X
0
n：决策变量个数 m：约束方程个数 25
2020-5-31
Hale Waihona Puke 产品 产品Ⅰ资源设备(台时)
1
产品Ⅱ 1
资源限制 300台时
原材料A(千克)
2
1
400千克
原材料B(千克)
0
单位产品利润(元) 50
谢谢阅读
1 100
250千克
16 2020-5-31
可以用x1和x2的线性函数形式来表示工 厂所要求的最大利润的目标：
max z=50x1+100x2 其中max为最大化的符号（最小化符号为
0
100
200
300
谢谢阅读
33 2020-5-31
当目标函数z取z1，z2，z3……时，

初始基本可行解
X [0,0,1600 ,2500 ,400 ]

T
目标函数与最优性检验
z 4x1 3x2 0x3 0x4 0x5
第一次迭代
确定入基变量，应当是 x1 ，它的系数是4。 确定出基变量，方法如下，得

x1
x2
x3
x4 0 1 0
x5
b

x5
2 2 1 5 2.5 0 1 0 0
j c j z j 1600
x2 x3 x4 x5
2 1 2.5 0 0 0
3 0

0 -2 400 1 -5 200 0 1
0 -4
0
第二次迭代
cj
4 3
0 1 0
0
0
0
0
cB xB b x1 0 x3 400 0 3 x2 200 0 4 x1 400 1
j c j z j 2200
确定新基和求解新的基本可行解

新基
0 B4 0 1
2 2 .5 0
2 5 1
x5 , x2 , x1 新的基变量： 新的基本可行解 x1 x2 x3 x4 x5
bຫໍສະໝຸດ 0 0 0.5 0.4 1 200 0 1 1.0 0.4 0 600 1 0 0.5 0.4 0 200
第三节 线性规划问题的单纯形解法
线性规划问题解的基本概念 单纯形解法 解的最优性检验 表解形式的单纯形法 单纯形解法的一些问题及其处理方法

一、线性规划问题解的基本概念
可行解 最优解 基及基本解 可行基及基本可行解 代数解与几何解的关系 单纯形法的要点

• 当第一阶段中目标函数的最优值＝0，即人工变量＝0， 则转入第二阶段；若第一阶段中目标函数的最优值不等于 0，即人工变量不等于0，则判断原问题为无解。
• 第二阶段：将第一阶段计算所得的单纯形表划去人工变量 所在的列，并将目标函数换为原问题的目标函数作为第二 阶段的初始单纯形表，进行进一步的求解。
14
s.t.
32x1x133xx2 22
x3 x3
100 120

x1, x2 , x3 0
cj
40 45 25 0 0
CB XB bi x1 x2 x3 x4 x5 θ
0 x4 100 2 [ 3 ] 1
1
0
100/3
0 x5 120 3 3 2 0 1
40
σj
40 45 25
两阶段法的算法流程图
MaxZ=-3x1+x3 x1+ x2+ x3≤4
-2x1+ x2- x3≥1 3x2+x3=9
xi ≥0,j=1,2,3
求解辅助问题，得到辅助 问题的最优解
引进人工变量x6，x7，构造辅助 问题，辅助问题的目标函数为
所有人工变量之和的极小化
Max W= -x6 - x7
x1+ x2+ x3+x4
取值
xj无约束 令xj = xj′- xj″
xj ≤ 0 令 xj′= - xj
xj′ ≥0 xj″ ≥0
右端项
bi < 0
约束条 件两端 同乘以
-1
等式或不等式
≤
=
≥
加松 弛变 量xs
加入 人工 变量
xa
减去 剩余 变量xs
加入 人工 变量xa

§1.3 单纯形法原理

理论方法 算法步骤 单纯形表



算例
第1页
一、基本概念
考虑线性规划标准形式 max z CX s .t . AX b X 0 ：
其中A为m×n阶矩阵
可行解：满足AX=b,且X≥0的解称为可行解。 可行域：全部可行解的集合称为可行域。 最优解：使目标函数达到最大值的可行解称为最 优解。 基：设B是系数矩阵A的一个m×n阶的满秩子矩阵， 称B是(LP)的一个基。
－5 0 0
2.5 0 4 4 0 3
1.5 17.5 22 19
－3 0 0 0
问：基解中零的个数至少有多少个？ 至少n-m个
例3
x1=0, x3=0 x2=3, x4=-2 是基解，但不 是可行解
D
max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0
max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40
第12页
三、几个基本定理
引理 线性规划问题的可行解为基可行解的充要条件 是它的正分量所对应的系数列向量线性无关。
证： （2）充分性
若向量 P1 , P2 , , Pk 线性无关，
则必有 k m
T
当 k m 时， P1 , P2 , , Pm 构成基
从而 X ( x1 , , x m , 0 , , 0 ) 为相应的基可行解
若X
(X
(0)
(0)
证。
(0)
不是基可行解
(0)
,由定理 2 知 X
到通过 X
) CX ) CX

aij x j bi
aij x j xni bi
xni 0 称为剩余变量
常量 bi＜0 的变换:约束方程两边乘以（－1）
线性规划问题的数学模型
例1.6 将下列线性规划问题化为标准形式
min Z 2 x1 x2 3 x3
5 x1 x2 x3 7
x1 x2 4 x3 2 3 x1 x2 2 x3 5
36 36 72 27
货运量 （千吨）
25 20 40 20
船只种类 拖轮 A型驳船 B型驳船
船只数 30 34 52
航线号 1 2
合同货运量 200 400
问：应如何编队，才能既完成合同任务，又使总货运成本为最小？
线性规划问题的数学模型
解： 设：xj为第j号类型船队的队数（j = 1，2，3，4），
Chapter1 线性规划
(Linear Programming)
本章主要内容：
LP的数学模型 图解法
单纯形法的进一步讨论－人工变量法 LP模型的应用
线性规划问题的数学模型
1. 规划问题 生产和经营管理中经常提出如何合理安排，使人力、 物力等各种资源得到充分利用，获得最大的效益， 这就是规划问题。
AX ( ) B
X
0
其中： C (c1 c2 cn )
a11 a1n
A
am1 amn
x1
X
xn
b1
B
bm
线性规划问题的数学模型
6. 线性规划问题的标准形式
n
max Z cj xj j 1
s.t
n
aij x j
j 1
bi
i 1, 2, , m
即 max z z c j x j