当前位置：文档之家 › 第二章线性规划

第二章线性规划

  • 格式：ppt
  • 大小：444.00 KB
  • 文档页数：26

下载文档原格式

  / 26

合集下载

管理运筹学第二章 线性规划的图解法

管理运筹学第二章 线性规划的图解法


B、约束条件不是等式的问题：
若约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量si ，使它等于约束右 边与左边之差 si=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，si 也具有非负约束，即si≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+si = bi
第二章 线性规划 的图解法
一、线性规划的概念 二、线性规划问题的提出 三、线性规划的数学模型 四、线性规划的图解法 五、线性规划解的情况 六、LP图解法的灵敏度分析
一、线性规划的概念
线性规划Linear Programming 简称LP，是一 种解决在线性约束条件下追求最大或最小的 线性目标函数的方法。 线性规划的目标和约束条件都可以表示成线 性的式子。
max z 3 x1 2 x2
2 x1 x2 ≤ 10 设备B台时占用 s.t. x1 x2 ≤ 8 x , x ≥ 0 产量非负 1 2
决策变量 （decision variable） 目标函数 （objective function） 约束条件 （subject to）

-ai1
x1-ai2 x2- … -ain xn = -bi 。
例1.3：将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 ≤15.7 4.1 x1 + 3.3 x3 ≥8.9 x1 + x2 + x3 = 38 x 1 , x 2 , x3 ≥ 0
第二章线性规划

第二章线性规划




线性规划要研究的两类问题中都包含有约束条件和目 标函数。用数学的方式描述，规划的目的就是在给定 的限制条件（或称约束条件）下，求目标函数的极值 问题（包括极小值和极大值）。
2
线性规划的数学模型
3
解： 设产品 的产量为：1 , 产品 的产量为：x2 x
4
5
6
7

配料问题：由若干种不同价格、不同成分含量的原料，用 不同的配比混合调配出一些不同规格的产品，在原料的供 应量限制和保证产品成分含量的前提下，如何进行配料来 获取最大利润或使总成本最低。
15
2.2.3 线性规划求解的可能结局
1、有唯一的最优解
2、有无穷多个最优解 （将目标函数改为 z=4x1+3x2 ）
x2
max z 4 x1 3 x2 x1 2 x2 5 2 x x 4 1 2 s.t. 4 x1 3 x2 9 x1 , x2 0
3x1 2 x2 4 x3 3
3x1 2 x2 4 x3 xs 3
剩余变量
变量xs实际上是原式左端减去右端的差，即 ：
xs 3x1 2 x2 4 x3 3
当约束条件是“ ”型的不等式时，只要将该约 束条件左端减去一个非负的剩余变量即可化为等式。 无论是松弛变量还是剩余变量在决策中都不产生实际价 值，因此它们在目标函数中的系数都应该为零。有时也将松 29 弛变量和剩余变量统称为松弛变量。
2x1+x2=4 D C
x1+2x2=5 B 4x1+3x2=9 O A x1
16
3、无界解
指线性规划问题有可行解，但是 在可行域，目标函数值是无界的， 因而达不到有限最优值。因此线 性规划问题不存在最优解。
第二章线性规划

第二章线性规划


解：设产品 A、B 的产量分别为x , y 。则，数学模型为：
m inZ 2 x 3 y x 125 x y 350 2 x y 600 x, y 0
例3 营养问题
某公司饲养试验用的动物以供出售。已知这些动物的生长 对饲料中的三种营养元素特别敏感，分别称为营养元素A 、B、C。已求出这些动物每天至少需要700克营养元素 A,30克营养元素B，而营养元素C每天恰好为200克。现有 五种饲料可供选择，各种饲料的营养元素及单价如下表22所示，为了避免过多使用某种饲料，规定混合饲料中各 种饲料的最高含量分别为：50、60、50、70、40克。求满 足动物需要且费用最低的饲料配方。
最优解必定可在可行域的某个顶点上 取得。
QM软件求解两个变量的LP问 题的方法。（演示）
Step1 Step2 Step3 Step4
1 A B C 价 格 3 1 0.5 2
2 2 0.5 1 7
3 1 0.2 0.2 4
4 6 2 2 9
5 18 0.5 0.8 5
需 求 700 30 200
解：设 x j
j 1,2 ,3,4 ,5 为每天混合饲料内包含的
第 j 种饲料的数量 （克） 则营养问题的数学模型为： 。
m inZ 2 x1 7 x 2 4 x3 9 x 4 5 x5 3x1 2 x 2 x3 6 x 4 18x5 700 x 0.5 x 0.2 x 2 x 0.5 x 30 2 3 4 5 1 0.5 x1 x 2 0.2 x3 2 x 4 0.8 x5 200 x 50, x 60, x 50, x 70, x 40 2 3 4 5 1 x j 0, j 1,2,3,4,5,
第2章 线性规划

第2章 线性规划


目标函数下降
MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20
X2=4
B A
目标函数上升
C
X2 0
E
D
X1 X1=6
4X1-3X2=0
X1=1
对解的讨论： .唯一解 .无穷解 .无解： 可行域空集 可行域无界
X2 X1+2X2=10 X2=4
X1 0
a11 a12 a1n 约束方程组 A P1 , P2 , Pn 系数矩阵 a m1 a m 2 a mn
A为m ×n矩阵（ m为约束方程个数，n为变量个数）
a11 a12 a1n A P1 , P2 , Pn a m1 a m 2 a mn
消除负的右端常数项
MAXZ=-X1-3(X3-X4) S.T. 6X1+7(X3-X4)8 X1-3(X3-X4) ≥6 X1-(X3-X4)=3 X1、X3、X4 0
约束方程还不是等式约束
人为添加变量，成为等式约束
对于“≤”约束，添加松弛变量 对于“≥”约束，添加剩余变量
6X1=5X1+3X2 S.T. 3X1+5X215
max Z 5 x1 3 x 2 3 x1 5 x 2 x 3 15 5 x1 3 x 2 x 4 10 x1 , x 2 , x 3 , x 4 0
5X1+2X210
X1,X20
2、给出基本可行解
• 6．基本可行解：满足非负条件
对于D1 ，基变量为X4、X5，X1、X2、X3为非基变量，令 X1、X2、X3=0， X4 = 8、X5 = 1 对于D2 ，基变量为X1、X2，X3、X4、X5为非基变量，令 X3、X4、X5 =0， X1 = -13/4 、X2=15/4
管理运筹学第二章线性规划的图解法

管理运筹学第二章线性规划的图解法


02
图解法的基本原理
图解法的概念
图解法是一种通过图形来直观展示线性规划问题解的方法。它通过在坐标系中绘 制可行域和目标函数，帮助我们理解问题的结构和最优解的位置。
图解法适用于线性规划问题中变量和约束条件较少的情况，能够直观地展示出最 优解的几何意义。
图解法的步骤
确定决策变量和目标函数
明确问题的决策变量和目标函数，以便在图 形中表示。
目标函数是要求最小化或最大化的函数，通常表示为 $f(x) = c_1x_1 + c_2x_2 + ldots + c_nx_n$。
04
约束条件是限制决策变量取值的条件，通常表示为 $a_1x_1 + a_2x_2 + ldots + a_nx_n leq b$或 $a_1x_1 + a_2x_2 + ldots + a_nx_n = b$。
LINDO是一款开源的线性规划求解器，用 户可以免费使用。
软件工具的使用方法
Excel
用户需要先在Excel中设置好线性规划模型，然后使 用“数据”菜单中的“规划求解”功能进行求解。
Gurobi/CPLEX/LINDO
这些软件通常需要用户先在软件界面中输入线性规划 模型，然后通过点击“求解”按钮进行求解。
实例三：分配问题
总结词
分配问题是指如何根据一定的分配原则 或目标，将有限的资源分配给不同的需 求方，以最大化整体效益。
VS
详细描述
分配问题在实际生活中广泛存在，如物资 分配、任务分配等。通过图解法，可以将 分配问题转化为线性规划模型，并利用图 形直观地展示最优解的资源分配方案。在 分配问题中，通常需要考虑不同需求方的 重要性和优先级，以及资源的有限性等因 素，以实现整体效益的最大化。
最优化方法：第2章 线性规划

最优化方法：第2章 线性规划


Z=CBB-1b+(σm+1,
σm+k ,
xm+1
σn
)
CB B-1b+σ m+k
xn
因为 m+k 0，故当λ→+∞时，Z→+∞。
用初等变换求改进了的基本可行解
假设Ｂ是线性规划 maxZ=CX,AX=b,X 0的可行基，则
AX=b
(BN)
XB XN
b
(I,B-1 N)
➢ 若在化标准形式前，m个约束方程都是“≤”的形式， 那么在化标准形时只需在一个约束不等式左端都加上一个松弛变 量xn+i (i=12…m)。
➢ 若在化标准形式前，约束方程中有“≥”不等式， 那么在化标准形时除了在方程式左端减去剩余变量使不等式变 成等式以外，还必须在左端再加上一个非负新变量，称为 人工变量．
单纯形法简介
考虑到如下线性规划问题 maxZ=CX AX=b X 0
其中Ａ一个m×n矩阵，且秩为m，ｂ总可以被调整为一 个m维非负列向量，Ｃ为n维行向量，Ｘ为n维列向量。
根据线性规划基本定理： 如果可行域Ｄ={ Ｘ∈Ｒn / ＡＸ=ｂ，Ｘ≥0}非空有界， 则Ｄ上的最优目标函数值Ｚ=ＣＸ一定可以在Ｄ的一个顶 点上达到。 这个重要的定理启发了Dantzig的单纯形法， 即将寻优的目标集中在D的各个顶点上。
非基变量所对应的价值系数子向量。
要判定 Z=CBB-1b 是否已经达到最大值，只需将
XB =B-1b-B-1NX N 代入目标函数，使目标函数用非基变量
表示，即：
Z=CX=(CBCN
)
XB XN
=CBXB +CNXN =CB (B-1b-B-1NXN )+CNXN
第二章线性规划及单纯形法总结

第二章线性规划及单纯形法总结


第一章
工厂需要的原棉存放在三个仓库中，现将原棉运往工 厂以满足工厂生产的需求。已知原棉运到各个工厂的单位 运费如表所示。问使总运费最小的运输方案？
仓库\工厂
1 2 3 需求
1
2 2 3 40
2
1 2 4 15
3
3 4 2 35
库存
50 30 10
2．线性规划数学模型
解：设xij为i 仓库运到 j工厂的原棉数量(i =1,2,3
1．线性规划介绍
第一章
线性规划研究的主要问题： 有一定的人力、财力、资源条件下，如何 合理安排使用，效益最高?
某项任务确定后，如何安排人、财、物， 使之最省?
2．线性规划数学模型
第一章
例1 美佳公司计划制造I，II两种家电产品。已知各 制造一件时分别占用的设备A、B的台时、调试时间及A、 B设备和调试工序每天可用于这两种家电的能力、各售出 一件时的获利情况如表I—l所示。问该公司应制造A、B两 种家电各多少件，使获取的利润为最大？
第一章
j =1,2,3)
minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33 x11 +x12+x13 x21+x22+x23 x31+x32+x33 50 30 10 40
st.
x11 +x21+x31 =
x12 +x22+x32 =
x13 +x23+x33 = xij 0
15
35
2．线性规划数学模型
第一章
练习4 连续投资10万元 A：从第1年到第4年每年初投资，次年末回收本利1.15； B：第3年初投资，到第5年末回收本利1.25，最大投资4万元； C：第2年初投资，到第5年末回收本利1.40，最大投资3万元； D：每年初投资，每年末回收本利1.11。 求：使5年末总资本最大的投资方案。 分析： A 1 x1A 2 x2A x2C x1D x2D x3D x4D x5D 3 x3A 4 x4A 5
第二章线性规划的图解法

第二章线性规划的图解法


➢ 答案：
X2 ➢ 最优解为： x1 ＝15 ，x2＝10 40 ➢ 最优值为：z*＝2500×15+1500×10
➢
30
＝52500
3x2＝75
20
（15，10）
10
O
10
20
30
40
50 X1
3x1+2x2＝65
2x1+x2＝40
五、线性规划问题解的情况
➢ 例1.5的最优解只有一个，这是线性规划问题 最一般的解的情况，但线性规划问题解的情 况还存在其它特殊的可能：无穷多最优解、 无界解或无可行解。
... am1x1+am2x2 +…+amnxn≤( =, ≥ )bm x1 ，x2 ，… ，xn ≥ ( ≤) 0 或无约束
xj为待定的决策变量； cj为目标函数系数，或价值系数、费用系数； aij为技术系数； bj为资源常数，简称右端项； 其中i＝1，2，…m； j＝1，2，…n
可以看出，一般LP模型的特点： A、决策变量x1，x2，x3，……xn表示要寻求
O
100 200 300
X1
3、无界解的情况
➢若将例1.5的线性规划模型中约束条件1、2的 不等式符号改变，则线性规划模型变为：
➢ 目标函数：Max z= 50x1+100 x2 约束条件：x1+x2 ≥ 300 2x1+x2 ≥ 400 x2≤250 x1 ≥0， x2 ≥0
B、定义决策变量；
C、用决策变量的线性函数形式写出所要追求 的目标，即目标函数；
D、用一组决策变量的等式或不等式来表示在 解决问题过程中所必须遵循的约束条件。
三、线性规划的数学模型
1、LP模型的一般形式 目标函数：
第二章 线性规划

第二章 线性规划

第二章线性规划一.线性规划所研究的问题可以归结为两方面：1）在现有的资源条件下，如何充分利用资源，使目标完成的最好。

（求极大问题）.2)在给定的目标和任务下，以最少的资源消耗或代价，去实现目标。

（求极小化问题）。

二.线性规划的标准型：1.标准型： max z=c1x1+c2x2+…+c n x ns.t. a11x1+a12x2+…a1n x1n=b1a21x1+a22x2+…+a2n x2=b2…a m1x1+a m2x2+…a mn x n=b mx1,x2,…,x n≥02.线性规划变换方法：1）min转换为max 目标函数乘以(-1);2）对于≤引进松弛变量，将其变成取等号。

对于≥引进剩余变量，将其变成取等号。

3）将变量中的非正限制或无限制转化为非负限制。

3.二维线性规划的图解法：1）正法向量：由目标函数系数组成的与等值线垂直的向量，称正法向量。

2）等值线：使目标函数取相等值的所有点的集合，称等值线。

4.二维线性规划解的形式：1）唯一最优解 2)无穷多个最优解 3)有可行解但无最优解 4）无可行解5.线性规划解的概念：1）解：满足约束方程条件的点。

2）可行解：满足所有约束条件的点。

（非负性约束）3）最优解：使目标函数得到极值的可行解。

4）基：由最大的线性无关的列向量所构成的子矩阵。

（基向量/非基向量）5）基变量：与基向量对应的变量称为基变量。

同理（非基变量）6）基本解：X=（B-1b）（ 0 ）7）基本可行解：对于基本解，同时又满足非负性要求称基本可行解。

（可行解与基本解之间相交的部分）有图。

8）可行基：基本可行解对应的基。

9）基本最优解：满足目标函数要求的基本解。

10）退化基本可行解：基本可行解中存在取值为零的基变量。

6.线性规划的基本定理：1）如果一个线性规划问题存在可行解，则一定有基本可行解。

2）若线性规划问题存在最优解，则一定存在最优基本可行解。

三 线性规划的求解1.单纯形方法（消去发）：1）标准化处理。

第二章线性规划

第二章线性规划

l j b l k 1
akl 0
关
b bk akl
j akj akl akj
k akl akj bk

i ail aij bi
bk i 0 aij ail bi ail akl akl
B 1b b [b1 , b2 , , bm ]T
（2.28）
记记
1
，
j 1, 2,, n ，
B a j a j [a1 j , a2 j , , amj ]T ,
则（2.28）可写成
x1 x2 a2 m1 xm1 a2l xl a2 n xn b2 xm amm1 xm 1 aml xl amn xn bm . a1m1 xm1 a1l xl a1n xn b1
,
x 中只有 xl bk 0 ，其余分量皆为 0。于是，由 N
（2.26）式得
z z l xl z l bk . （2.37）
z z
特别当 bk 0 时，只要 l 0 ，必有
z z
结论是： 引入判别数为正的变量， 将保证 B 的基本容许解的目标函数值不大于 B 的基本容 许解的目标函数值。
令 N
T T 1 T c B B N c N ，于是
故
因为 xN 0 ，因此，只要 N 0 ，必有 z z 。
由此得到判断基本容许解是最优解的一个充分 条件。
T z z N xN ， （2.26） T z z N xN .
有最优点
解无界
Dantzig 单纯形法的思想涉及以下三个具 体问题： 一、初始基本容许解的产生； 二、最优性准则； 三、基本容许解的改进。
第2章 线性规划(对偶问题)

第2章 线性规划(对偶问题)


对偶问题（或原问题）
目标函数为 Min W
n个
约束条件
＝
m个
变量
0 0 无约束
约束条件右端项cj 价值系数bi 约束条件的系数矩阵AT
例：
• 写出下面线性规划问 题的对偶问题：
• 1.
max Z 2x1 x2 3x3 x4
x1 x2 x3 x4 5
s.t.
2x1 x2 3x3
原问题（对偶问题）
目标函数 限定向量 价值向量 技术系数 约束条件 变量数目 约束条件个数 变量正负
对偶问题（原问题）
目标函数 价值向量 限定向量 技术系数 对偶变量 约束条件个数 对偶变量数目 约束条件
非对称形式的对偶问题
• 在原线性规划问题为Max型，且变量非负 的前提下：
1. 原问题约束条件是“”型
x1
x3
x4
1
4
x1, x3 0, x2 , x4无约束
• 解：根据上述对偶关 系，可以写出原问题 的对偶问题：
min W 5 y1 4 y2 y3
y1 2 y2 y3 2
s.t.
y1 y1
y2 1 3y2 y3
3
y1
y3
1
y1 0, yLeabharlann 0, y2无约束例：y1
0,
y3
0,
y2无约束
对偶的基本性质
• 原问题： Max Z=CTX
• 对偶问题： Min W=bTY
s.t. AXb X0
s.t. ATY C Y0
• ①对称性：对偶问题的对偶是原问题； • ②弱对偶性：若X是原问题的可行解，Y是
对偶问题的可行解，则CTX bTY
• 弱对偶性的证明： AX’ b X’TAT bT X’TATY’ bTY’

第二章 线性规划的图解法

x2
AB
z
C
D
z=0=50x1+100x2
E
x1
图2-2
12
❖ 目标函数：Maxz = 50 x1 + 100 x2
❖ 约束条件：s.t. x1 + x2 ≤ 300
❖
2 x1 + x2 ≤ 400
❖
x2 ≤ 250
❖
x1 , x2 ≥ 0
❖最优解： x1 =50 x2 = 250
❖例2：某工厂在计划期内要安排生产Ⅰ、Ⅱ 两种产品，已知生产单位产品所需的设备台
- (c1 / c2 ) ， 当 -1 - (c1 / c2 ) 0 （*） 时，原最优解仍是最优解。
❖假设产品Ⅱ的利润100元不变，即 c2 = 100，代到式（*）并整理得 0 c1 100
❖假设产品Ⅰ的利润 50 元不变，即 c1 = 50 ，代到式（*）并整理得 50 c2 +
▪ 4.无可行解。若在例1的数学模型中 再增加一个约束条件4x1+3x2≥1200， 则可行域为空域，不存在满足约束条 件的解，当然也就不存在最优解了。
例3.某公司由于生产需要，共需要A，B两种原料至 少350吨（A，B两种材料有一定替代性），其中A原 料至少购进125吨。但由于A，B两种原料的规格不同 ，各自所需的加工时间也是不同的，加工每吨A原料 需要2个小时，加工每吨B原料需要1小时，而公司总 共有600个加工小时。又知道每吨A原料的价格为2万 元，每吨B原料的价格为3万元，试问在满足生产需 要的前提下，在公司加工能力的范围内，如何购买A ，B两种原料，使得购进成本最低？
❖-ai1 x1-ai2 x2- … -ain xn = -bi。

第二章 线性规划

第二章 线性规划本章内容重点： 线性规划模型 解的主要概念 线性规划应用——建模一. 线性规划模型引例：（1）用一块边长为a 的正方形铁皮做一容器，应如何裁剪，使做成的容器的容积最大？（2）某企业计划生产甲、乙两种产品。

这两种产品都要分别在A 、B 、C 、D 四种不同设备上加工。

按工艺资料规定，生产每件产品甲需占用设备分别为2、1、4、0小时，生产每件产品乙需占用设备分别为2、2、0、4小时。

已知各设备计划期内用于生产这两种产品的能力分别为12、8、16、12小时，又已知每生产一件产品甲企业能获得2元利润，每生产一件产品乙企业能获得3元利润，问该企业应如何安排生产，使总的利润收入最大？讨论：（1）可用微积分的方法解决； （2）复杂一些目标： 最大2132x x z +=例2.1:某工厂拥有A 、B 、C 三种类型的设备，生产甲、乙两种产品。

每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：问题：工厂应如何安排生产可获得最大的总利润？解：设变量xi 为第i 种（甲、乙）产品的生产件数（i ＝1，2）。

根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。

对设备A ，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1 + 2 x2 ≤ 65； 对设备B ，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1 + x2 ≤ 40；对设备C ，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x 2 ≤75 ；另外，产品数不可能为负，即 x 1 ,x 2 ≥0。

同时，我们有一个追求目标，即获取最大利润。

于是可写出目标函数z 为相应的生产计划可以获得的总利润：z =1500x 1+2500x 2 。

综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤≤≤+≤+0,12416482122221212121x x x x x x x x目标函数 Max z =1500x1+2500x2约束条件 s.t. 3x1+2x2≤ 652x1+x2≤ 403x2≤ 75x 1 ,x2≥0这是一个典型的利润最大化的生产计划问题。

第2章线性规划(对偶问题)


• 解：根据上述对偶关 系，可以写出原问题 的对偶问题：
m in W 5 y 1 4 y 2 y 3 y1 y1 s .t . y 1 y 1 y1 2 y2 y3 2 y2 1 3 y2 y3 3 y3 1 0 , y3 0 , y 2无 约 束
• 令y4=y2-y3 ，得：
• Min W=y1+2y4 S.t. y1+2y4 1 2y1-3y4 2 5y1-4y4 -3 y1 0, y4无符号约束
原问题与对偶问题的对应关系
原问题（或对偶问题） 目标函数为 Max Z 变量 n个 0 0 无约束 对偶问题（或原问题） 目标函数为 Min W n个 ＝ 约束条件
– 设X*是原问题的可行解，Y*是对偶问题的可行
解，当CTX*=bTY*时，X*，Y*是最优解。
– 证明：由弱对偶性，可知原问题的所有可行解
X’均满足 CT X’ bTY*
又因为CTX* = bTY* ，所以CT X’ CTX* ，即： X*是使目标函数取值最大的可行解。因而是最 优解。 同理可证Y*也是最优解。
m个 ＝ 价值系数cj 约束条件右端项bi 约束条件的系数矩阵A 约束 条件
m个 变量 0 0 无约束 约束条件右端项cj 价值系数bi 约束条件的系数矩阵AT
例：
• 写出下面线性规划问 题的对偶问题： • 1.
m a x Z 2 x1 x 2 3 x 3 x 4 x1 x 2 x 3 x 4 5 2 x x 3x 4 1 2 3 s .t . x1 x 3 x 4 1 x1 , x 3 0 , x 2 , x 4 无 约 束
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

以下讨论在 w 0 下进行。分两种情形： （1）在最优表中人工变量已全部退出基变量 （表现为 D 中不存在基向量） 。
这时，与 Ax b 等价的 Ax b 中有了标准基，即
表明（2.54）有了初始基本容许解，这时可以 开始求解（2.54） （见下面的 4.（1）。 ）
T 其中 e 1,1, ,1 。
显然（2.55）不可能无解。
设（2.55）的最优值为 w ，显然 w 0 。设 最优表对应的 G-J 方程组为 Du Ax b . （2.56）
注意： Ax b 与 Ax b 等价。
（2.54）与（2.55）的关系：若 w 0 ，则 （2.54）无解；若 w 0 ，则由（2.56）可得到 （2.54）的一个初始基本容许解。
么关于 B 的信息全部反映在以下两个式子（线 性规划的两个关键数学式）中， 1 1 IxB B NxN B b T N xN z z
(2.43) (2.44)
称之为关于基 B 的增广 G-J 方程组。
增广 G-J 方程组其实可由线性规划（2.21） 的原始数据经初等行变换得到。原有 BxB NxN b (2.45) T T (2.46) z cB xB cN xN 0,
称为线性规划的准备表。
类似前面的推导，由准备表容易导出单纯形表
B c T B I 0 1 1 N b I B N B b T T T cB c N cN 0 0 1 1 B N B b I B 1 N T 1 T T 1 T T cB B N c N cB B b 0 N
（1）求解线性规划
（2）求解线性规划
T min c x s.t. Ax b x 0.
T min c x s.t. Ax b x 0. 总结：一般来说，解线性规划主要分为两 大步：
第一步，化标准形（有时不需要） ；
B1 即得（2.43）式， （2.45）式左乘 （2.43）式
T 再左乘 cB 加到（2.46）式上便得（2.44）式。
þ ¥ ö ã Ò È Ô ¹ G-J ·³ ×Ö µ ±Á º ½ Ì é Ð Ä ä ¿ Í Ä µ ý ò ¿ ¬ « ä à ý Ý Ð É í µ Ï Ê Ï Á £ ½ Æ Ó Ê ¾ Á ³ ±
例 2.9 求解线性规划
s.t. x1 2 x1
min x1 x2 2 x3 5 x4 2 x3 x4 1 4 4 x3 2 x4 2 x1 x2 x3 x1 , x2 , x3 , x4 0.
例 2.10 求解线性规划
min x1 2 x2 3 x3 s.t. x1 2 x2 4 x3 4 4x1 9 x2 3 x3 16 x1 , x2 , x3 0.
z
I B N T （2.51） T 0 N 称为关于基 B 的单纯形表。若 B 是最优基，则
1 1
B b ， z
称为最优表。 单纯形表是增广 G-J 方程组的简单表示。 表 B N b c T c T 0 （2.52） N B
这里介绍一种最简单的避免循环的规则 ——Bland 规则。 Bland 规则 设在单纯形法的迭代过程中，当
B [at1 , at2 ,, atm ] ，关于 B 的基容许解 前容许基是
不是最优解，则主元列标和行标分别由如下两 个规则确定： ⅰ）Bland 进基规则 采用正判别数最小下标进基规则，即主元 列标是 l min{ j | j 0},
ⅱ）若 ak1 , ak 2 , , akn 至少有一个不为 0 ，不
妨设 akl 0 。以 akl 为主元在最优表上进行换基运
算，人工变量 u k 就会从基变量中消失。
重复以上步骤，直到人工变量全部从基变 量中消失，最终的 G-J 方程组为
Du Ax b
然后就可以启动单纯形法。
例 2.8 求解线性规划 P66
min x1 2 x2 x3 3x4 s.t. x1 x2 3x3 x4 6 2 x2 x3 x4 3 x2 6 x3 x4 4 x1 , x2 , x3 , x4 0.
3. 初始基本容许解的产生 对于标准线性规划
0 ， k 是用公式（2.36）确
定的一个行标；
ⅳ）用 al 替换 B 中的 ak ，而其余基向量不
变，构成矩阵 B 。
那么， B 是容许基，且关于 B 的基本容许解的 目标函数值小于关于 B 的基本容许解的目标函 数值。 定理 2.12 在标准线性规划（2.21）中， 假设： ⅰ） B [a1 , a2 ,, am ] 是容许基；
B0 at1 , at2 , , atm 是标准容许基。
x j 0,
j 1, 2, , n.
典范线性规划含有标准容许基，它的准备表既 是单纯形表，因此单纯形法可以直接启动。
算法 2.1（单纯形法） P65 单纯形法本质上是求解典范线性规划的算 法。
定理 2.13 在使用单纯形法 （算法 2.1） 求 解典范线性规划时，若各次迭代出的基本容许 解皆是非退化的，则算法在有限步终止。
引理 2.10 定理 2.11（单纯形法基本定理） 在标准 线性规划（2.21）中，假设： ⅰ） B [a1 , a2 ,, am ] 是容许基，关于 B 的
1 基本容许解是非退化的，即 b B b 0 ；
1 ⅲ） al B al
ⅱ）非基变量 xl 的判别数 l 0 ；
由此确定 al 进基。
1 j n
ⅱ）Bland 退基规则 1 al B al [a1l , a2l ,, aml ]T 假定
0 。设
又设
bi min{ ail 0}, 1i m a il bi I i , ail 0, i 1, 2, , m ail
k
（2.58）
以下分两种情形： ⅰ）若 ak1 ak 2 akn 0 ，则（2.58）表 示 0 0 。这表明 Ax b 的第 k 个方程是多余方
程， 从而 Ax b 的第 k
个方程也多余。 划去第 k 个
方程，人工变量 u k 将彻底消失。
则主元行标 k 由式
tk min ti ti是基向量下标
iI
atk 退基。换句话说，在所有可 确定，由此确定
2.4 退化的处理
在非退化假定下，单纯形法（算法 2.1）具 有有限终止性（定理 2.13） 。取消非退化假定， 情况会是怎么样？第一，算法 2.1 可能发生无 限循环，求不到最优解；第二，适当修改选主 元的规则，则可以保证单纯形法仍具有有限步 终止性。
1. 选主元规则
单纯形法的核心是换基运算，而换基运算的 首要步骤是选主元。
选取主元列标的规则称为进基规则；选取主行 标的规则称为退基规则。进基规则和退基规则 合称选主元规则。选主元规则有多种多样，常 用的进基规则有以下两种：
ⅰ）最大正判别数进基规则
选取最大判别数的下标作为主元的列标。 若同时有多个等值的最大正判别数，则选取其 中最小的下标为主元的列标；
ⅱ）正判别数最小下标进基规则 选取正判别数中最小的下标作为主元的列 标。算法 2.2 和算法 2.3 就采用这种进基规则。
（2） 在最优表中至少还有一个人工变量是基变 量（表现为 D 中有基向量） 。
假设第 k 个人工变量 u k 仍是基变量，那么它的 取值为 bk 。因为 w 0且w ui ，所以 bk 0 。考虑 i 1 （2.56）的第 k 个方程
n
a
j 1
n
k jBiblioteka x j b 这时与 Ax b 等价的 Ax b 中也有了标准基， 从
而（2.54）也有了初始基本容许解，于是可以 开始求解（2.54） （见下面的 4.（2）。 ）
4. 标准线性规划的解法
按 3.求出（2.54）的初始基本容许解之后，接 下来求解（2.54） ，与 3.中的（1）（2）对应， 、 分别为
B b . z
1
至此，含有标准基的线性规划问题的求解 彻底解决。归纳见（3） 。
例 2.7 求解例 2.5 中的线性规划。P64-55
（3）典范线性规划的解法 考虑典范线性规划
min c1 x1 c2 x2 cn xn s.t. x1a1 x2 a2 xn an b
最大正判别数进基规则与最小行标退基规则合 称 Dantzig 规则。算法 2.1 采用的就是这种规 则。计算实践表明，在各种选主元规则中， Dantzig 规则效果较好， 在求解同一线性规划问 题时，迭代次数相对较少。它的缺点是，在求 解退化问题时，算法可能产生无限循环，求不 到最优解。
2. 避免循环的规则
£ Ã Ä Ë ù æ ò Ç î ¡ ³ Ó µ Í » ¹ Ô Ê ×Ð Ð ± Í » ¹ Ô ¡ ê Ë ù æ ò £ Ú ¹ à « ½ ¨ Ô Ê Ó ¹ Ê £ 2.36£ È ¶ Ö Ô Ð ± k £ È © ·¨÷ª ê ¬ ô î ¡ È µ Ú à × Ð ±Ö Ô ¶ Ð É È µ £ Ô ´ Ö Ñ È × Ï ¡ à ¬ ò Ó Ð ¡ ¡ î ¡ Ä Ð µ Ð ±×Î Ö Ô µ Ð ±¡ ê ÷ª ÷ª Ä ê £
推论 2.14 典范线性规划或者存在最优基 本容许解，或者解无界。 对于如下形式的线性规划
T min c x s.t. Ax b x 0, 其中 b 0 。先引入非负变量 u 将其化为典范形