线性规划问题的基本解-完整版
- 格式：pdf
- 大小：1.54 MB
- 文档页数：16
下载文档原格式
合集下载
第二章 线性规划基本内容
x1 0, x2 0, x3符号无限制
，x3 x4 x5 ， 解： 令 z z ，x1 x1 其中 x4 , x5 0 ，
则标准化后有
2 x2 3 x4 3 x5 max z x1 x2 s.t. x1 x4 x5 2 x2 x1 x4 x5 x2 3 x4 3 x5 3 x1 , x2 , x4 , x5 , x6 , x7 0 x1
40 3x1 10x 2 300 (0,30) A x1 , x 2 0 4 x1 5 x 2 200
B(20,24)
3 x1 10 x 2 300
C(1000/29,360/29) 0 D E (40,0) (50,0) 100 x1
在 B 点获得最大值，z=4280
x2
凸集
定义 2.2.1： 设 S R n 是 n 维欧氏空间的点集， 若对任意 x S , y S 的 和 任 意 [0,1] 都 有 x (1 ) y S 就称 S 是一个凸集。
定义 2.2.2：设 S 为凸集 x S ，如果对任意 y, z S 和 0 1 ，都 有 x y (1 ) z ,则称 x 为 S 的顶点。 定理 2.2.1 线性规划的可行域 D { x Ax b, x 0} 是凸集 定理 2.2.2 任意多个凸集的交还是凸集
（1）若 x k 0 ，令 x k x k
（2）若 中
xk
为符号无限制变量，则 。
xk xk xk
，其
, xk 0 xk
例1
max z 70x1 120x 2 s.t. 9 x1 4 x 2 360 4 x1 5 x 2 200 3 x1 10x 2 300 x1 , x 2 0
线性规划的基本定理-最优化方法
j 1
j 1
现构造两个点X（1），X（2），使满足
X（1）=（x1+αλ1,…, xk+αλk ,0,…,0）T X（2）=（x1-αλ1,…, xk-αλk ,0,…,0）T
线性规划解的基本定理
定理2：设X是可行域D的极点，那么，X最多有m个 正分量。
证明：设X=(x1，···xk，0，···，0)T，若k>m，由
z=λx+(1-λ)y
这说明当0 ≤ λ ≤1 时，λx+(1λ)y 表示以x.y为端点的直线段上的所 有点，因而它代表以 x.y为端点的直线 段。
一般地，如果x.y是n维欧氏空间Rn中的两点，则 有如下定义：
如果 x=(x1…xn)T,y=(y1…yn)T是Rn中任意两点，定 义z=λx+(1-λ)y(0≤λ≤1),z=(z1…zn)T 的点 所构成的集合为以x,y为端点的线段，对应λ=0， λ=1的点 x, y叫做这线段的端点，而对应 0<λ<1的点叫做这线段的内点。
表明X不是D的极点，与已知条件矛盾，故k≤m。
线性规划解的基本定理
定理1.4：对标准形式的线性规划，基可行解与可行 域的极点一一对应。
证明：首先证明极点必是基可行解。设X是极点， 由定理1.3,可设X=(x1,…xk,0,…,0)T xj>0,k≤m 若X不是基可行解，由定理1.2，向P1,P2,…,Pk应 线性相关。仿照定理1.3的证明过程，可推导出X 不是极点，与已知条件矛盾。故可知X是基可行解。
其次证明充分性。设X的正分量为x1，x2,…,xk，其对 应的列向量P1,P2,…,Pk线性无关。显然k≤m。
若k=m，则P1,P2,…,Pk可用来构成一个基，所 以X是基本解。而已知X是可行解，故X又是基可行 解。
线性规划(图解法)
D
max Z
可行域
（7.6，2） ， ）
34.2 = 3X1+5.7X2
X1 + 1.9X2 = 3.8(≥) X1 - 1.9X2 = 3.8 (≤) L0： 0=3X1+5.7X2
oபைடு நூலகம்
x1
图解法
min Z=5X1+4X2 x2
X1 + 1.9X2 = 10.2 (≤)
Page 18
43=5X1+4X2 8=5X1+4X2 此点是唯一最优解 （0，2） ， ）
图解法
线性规划问题的求解方法 一般有 两种方法 图解法 单纯形法 两个变量、 两个变量、直角坐标 三个变量、 三个变量、立体坐标
Page 1
适用于任意变量、 适用于任意变量、但必需将 一般形式变成标准形式
下面我们分析一下简单的情况—— 下面我们分析一下简单的情况—— 只有两个决策 变量的线性规划问题， 变量的线性规划问题，这时可以通过图解的方法来 求解。图解法具有简单、直观、 求解。图解法具有简单、直观、便于初学者窥探线 性规划基本原理和几何意义等优点。 性规划基本原理和几何意义等优点。
• 有效与无效 紧与松)约束：与最优解相关的约束为有效 有效与无效(紧与松 约束 紧与松 约束： (紧)约束。 紧 约束 约束。 • 最优解：总是在可行域的边界上，一般由可行域的顶 最优解：总是在可行域的边界上， 点表示。 点表示。 • 可行域：由约束平面围起来的凸多边形区域，可行域 可行域：由约束平面围起来的凸多边形区域， 个可行解。 内的每一个点代表一 个可行解。
20
无可行解(即无最优解 无可行解 即无最优解) 即无最优解
10
O
10
最优化方法-线性规划的基本定理
其次证明充分性。设X的正分量为x1，x2,…,xk，其对 应的列向量P1,P2,…,Pk线性无关。显然k≤m。
若k=m，则P1,P2,…,Pk可用来构成一个基，所以X是基 本解。而已知X是可行解，故X又是基可行解。
若k<m，由于A的秩为m，比可从A中再挑出m-k个列向 量，与P1,P2,…,Pk ，一起构成一个线性无关极大组，即 为一个基，由此可知X是基可行解。
定义1.7：设集合S是n维欧式空间En中的闭凸 集，d是En中的非零向量。如果对于S的每 个点X，以及一切非负的数λ，都有
X+λd∈S，λ≥0
则称向量d是凸集S的一个方向。如果d1， d2是S的方向，且d1≠αd2， ∀ α>0，则d1， d2是两个不同的方向。
进一步，如果d是凸集S的一个方向，且 不能表示为S的另外两个不同的方向的正组 合，则称d是S的一个极方向。
约定A是行满秩的m行n列矩阵。
2、基、基向量、基变量、基本解、基本可 行解、可行基、最优解、最优基
基：矩阵A中一个m阶非奇异子矩阵 基向量：基的列向量 基变量：基向量对应的变量 基本解：非基变量全为零的解
基本可行解：非基变量为零，基变量都大 于等于零的解
可行基：基可行解对应的基 最优解：基本解中使目标函数最大的解 最优基：最优解对应的基
X=λX（1）+（1-λ）X（2）
上式的分量表达形式为 显然，当j>m时，有
x
j
xj
xj1 xj1x j2
1 0
xj2
,
j
1,
2,
,n
m
再由于X（1），X（2）均是可行点，故可推知 xjiPj b,i 1, 2
两式相减，得
若k=m，则P1,P2,…,Pk可用来构成一个基，所以X是基 本解。而已知X是可行解，故X又是基可行解。
若k<m，由于A的秩为m，比可从A中再挑出m-k个列向 量，与P1,P2,…,Pk ，一起构成一个线性无关极大组，即 为一个基，由此可知X是基可行解。
定义1.7：设集合S是n维欧式空间En中的闭凸 集，d是En中的非零向量。如果对于S的每 个点X，以及一切非负的数λ，都有
X+λd∈S，λ≥0
则称向量d是凸集S的一个方向。如果d1， d2是S的方向，且d1≠αd2， ∀ α>0，则d1， d2是两个不同的方向。
进一步，如果d是凸集S的一个方向，且 不能表示为S的另外两个不同的方向的正组 合，则称d是S的一个极方向。
约定A是行满秩的m行n列矩阵。
2、基、基向量、基变量、基本解、基本可 行解、可行基、最优解、最优基
基：矩阵A中一个m阶非奇异子矩阵 基向量：基的列向量 基变量：基向量对应的变量 基本解：非基变量全为零的解
基本可行解：非基变量为零，基变量都大 于等于零的解
可行基：基可行解对应的基 最优解：基本解中使目标函数最大的解 最优基：最优解对应的基
X=λX（1）+（1-λ）X（2）
上式的分量表达形式为 显然，当j>m时，有
x
j
xj
xj1 xj1x j2
1 0
xj2
,
j
1,
2,
,n
m
再由于X（1），X（2）均是可行点，故可推知 xjiPj b,i 1, 2
两式相减，得
线性规划常见题型及解法 均值不等式(含答案)
线性规划常见题型及解法一．基础知识：(一)二元一次不等式表示的区域二元一次不等式0>++C By Ax 表示直线0=++C By Ax 某一侧的所有点组成的区域，把直线画成虚线表示不包括边界， 0≥++C By Ax 所表示的区域应包括边界，故边界要画成实线.由于在直线0=++C By Ax 同一侧的所有点（x,y ）,把它的坐标（x,y ）代入C By Ax ++，所得的符号相同，所以只需在此直线的某一侧取一个特殊点（0,0y x ），从C By Ax ++00的正负即可判断0≥++C By Ax 表示直线哪一侧的平面区域。
通常代特殊点（0，0）。
（二）线性规划(1)不等式组是一组对变量x 、y 的约束条件，由于这组约束条件都是关于x 、y 的一次不等式，所以又可称其为线性约束条件.z =A x +B y 是欲达到最大值或最小值所涉及的变量x 、y 的解析式，我们把它称为目标函数.由于z =A x +B y 又是关于x 、y 的一次解析式，所以又可叫做线性目标函数.另外注意：线性约束条件除了用一次不等式表示外，也可用一次方程表示.(2)一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题.(3)那么，满足线性约束条件的解（x ,y ）叫做可行解，由所有可行解组成的集合叫做可行域.在上述问题中，可行域就是阴影部分表示的三角形区域.其中可行解（11,y x ）和（22,y x ）分别使目标函数取得最大值和最小值，它们都叫做这个问题的最优解.线性目标函数的最值常在可行域的顶点处取得;而求最优整数解必须首先要看它们是否在可行(4)用图解法解决简单的线性规划问题的基本步骤：1.首先，要根据线性约束条件画出可行域（即画出不等式组所表示的公共区域）.2.设z =0，画出直线l 0.3.观察、分析，平移直线l 0，从而找到最优解.4.最后求得目标函数的最大值及最小值. (5) 利用线性规划研究实际问题的解题思路：首先，应准确建立数学模型，即根据题意找出约束条件，确定线性目标函数.然后，用图解法求得数学模型的解，即画出可行域，在可行域内求得使目标函数取得最值的解. 最后，还要根据实际意义将数学模型的解转化为实际问题的解，即结合实际情况求得最优解.线性规划是新教材中新增的内容之一，由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下常见题型。
线性规划问题的基本解
am1
x1
am2 x2
L
amn xn
bm
x1 0, x2 0,L , xn 0
1.2 1.3
满足约束条件的X称为线性规划问题的可行解;
X x1, x2, , xn T
所有可行解的集合称为可行域 (feasible region),
使目标函数(1.1)达到最大值的可行解称为最优解(an optimal solution)。
A.基本可行解 B.非基本解
C.非可行解
D.最优解
4. X是线性规划的基本可行解，则有（ A. X中的基变量非零，非基变量为零 B. X不一定满足约束条件 C. X中的基变量非负，非基变量为零 D. X是最优解
）。
，P4
1
，P5
0
0
2
0
0
1
分别是变量 x1, x2 , x3, x4 , x5 的系数向量。
max z 3x1 5x2
3x1 2x2 x3
18
3 2 1 0 0
x1
x4 4
A 1 0 0 1 0
2x2
x5 12
0 2 0 0 1
x1, x2 , x3, x4 , x5 0
XB x j1 , x j2 ,L , x jm 表示基变量向量，
X N 表示非基变量向量。
现令所有的非基变量都等于0，即
XN 0
则约束方程(1.2)可化为：
Pj1 x j1 Pj 2 x j 2 L Pjm x jm b
BXB b
1.4
它是一个m个变量m个方程组成的线性方程组，B又是可逆
在上例1中，
对应于 B1 的基解为 X1 0, 0,18, 4,12T
线性规划问题的图解法
bm 0 1 am ,m 1 amn m
j
0 0 j c j c i a ij
bi 其中： i a kj 0 a kj
单纯形法的计算步骤
例1.8 用单纯形法求下列线性规划的最优解
max Z 3 x1 4 x 2 2 x1 x 2 40 x1 3 x 2 30 x , x 0 1 2
A
0
E
| 5
| 6
| 7
| 8
| 9
x1
图解法
9— 8—
目标函数 Max Z = 2x1 + 3x2
约束条件 x1 + 2x2 8
4x1 16 4x2 12 x1、 x2 0
x2
7—
6— 5—
4x1 16
C 4 x2 16
4 —B
3— 2— 1—
D
| 1 | 2 | 3 | 4
4—
3— 2— 1— 0
x1
图解法
9— 8—
目标函数 Max Z = 2x1 + 3x2
约束条件 x1 + 2x2 8
4x1 16 4x2 12 x1、 x2 0
x2
7—
6— 5—
4x1 16 4 x2 12 x1 + 2x2 8
4—
3— 2— 1— 0
可行域
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
x2
X1 + 1.9X2 = 11.4 (≤)
8=5X1+4X2 此点是唯一最优解 （ 0， 2）
D
43=5X1+4X2
可行域
j
0 0 j c j c i a ij
bi 其中： i a kj 0 a kj
单纯形法的计算步骤
例1.8 用单纯形法求下列线性规划的最优解
max Z 3 x1 4 x 2 2 x1 x 2 40 x1 3 x 2 30 x , x 0 1 2
A
0
E
| 5
| 6
| 7
| 8
| 9
x1
图解法
9— 8—
目标函数 Max Z = 2x1 + 3x2
约束条件 x1 + 2x2 8
4x1 16 4x2 12 x1、 x2 0
x2
7—
6— 5—
4x1 16
C 4 x2 16
4 —B
3— 2— 1—
D
| 1 | 2 | 3 | 4
4—
3— 2— 1— 0
x1
图解法
9— 8—
目标函数 Max Z = 2x1 + 3x2
约束条件 x1 + 2x2 8
4x1 16 4x2 12 x1、 x2 0
x2
7—
6— 5—
4x1 16 4 x2 12 x1 + 2x2 8
4—
3— 2— 1— 0
可行域
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
x2
X1 + 1.9X2 = 11.4 (≤)
8=5X1+4X2 此点是唯一最优解 （ 0， 2）
D
43=5X1+4X2
可行域
线性规划-讲义-3
4)、解的几种情况： 4)、解的几种情况： 唯一解 无穷多解－最优表中非基变量检验数有为0者。 无穷多解－最优表中非基变量检验数有为0 无界解 max, σ j > 0 但Pj ≤ 0 min, σ j < 0 但Pj ≤ 0 无可行解－最优表中人工变量在基中， 无可行解－最优表中人工变量在基中，且＝0。 建模有问题 5)、 5)、退化解问题
表2 -2
-1/3 -1/3
两阶段法步骤 n 原问题 max S=Σ Cj xj n j=1 Σ aij xj =bi ( i=1,2, …,m) xj ≥ 0 m 作辅助问题 min W=Σ yi n i=1 Σ aij xj + yi =bi ( i=1,2, …,m) Xj ， yi ≥ 0 阶段：解辅助问题， 第1阶段：解辅助问题，当进行到最优表时 ①、若W=0, 则得到原问题的一个基本可行 转入第2阶段 阶段。 解，转入第 阶段。 ②、若W>0, 则判定原问题无可行解 阶段： 第2阶段：用求出的初始基可行解求最优解。 阶段 用求出的初始基可行解求最优解。
人工变量： x6 , x7 人工变量：
cj
XB b*
0
x1
0
x2
0
x3
0
x4
0
x5
-1
x6
-1
x7
x4 11 3 x6 x7 1 - W’ 0
XB b*
1 -4 -2
0
x1
-2 1 0
0
x2
1 2 1
0
x3
1 0 0
0
x4
0 -1 0
0
x5
0 1 0
-1
x6
0 0 1
-1
x7
线性规划原理与解法
c1 b1 a1,m 1 xm 1 a1,m 2 xm 2 ... a1n xn
z c1b1 c2b ... cmbm
cm1 ci ai,m1
i 1
m
cm 1 c1a1, m 1 c2 a2, m 1 ... cm am , m 1 xm 1 c c a i i ,m 2 m 2
i 1
对增广矩阵 作初等行变换 将基变为单位阵
1 0 0
x2 0 ... 0 a1, m 1 ... a1n b : 1 1 ... 0 a2, m 1 ... a2 n b xm 2 ...... x : m 1 bm 0 ... 1 am, m 1 ... amn : x n
第一节 线性规划求解原理
5）若约束条件为“≥”，“≤”和“=”的混合性， 则综合应用以上方法，确定初始基。
max z 3 x1 4 x2 例： x1 2 x2 ≤8 4 x ≤16 1 s.t. 4 x2 ≤12 x1 , x2≥0 max z 3x1 4 x2 0 x3 0 x4 0 x5 =8 x1 2 x2 x3 4 x x4 =16 1 s.t. x5 12 4 x2 x1 , x2 , x3 , x4 , x5≥0
xi bi
j m 1
a x (i 1, 2,..., m)
ij j
n
x1 b1 a1,m1 xm1 a1,m2 xm2 ... a1n xn x2 b2 a2,m1 xm1 a2,m2 xm2 ... a2 n xn ...... xm bm am,m1 xm1 am,m 2 xm 2 ... amn xn
线性规划问题
以上约束方程组有无穷多个解，单纯形法就是 确定这些解的过程
.(1)初始单纯形表: X1 x2 x3 x4 x0
x3
x4
3
5
4
4
1
0
0
1
36
40
-32
-30
0
0
0
在初始单纯形表中，横线上以上部分即为约束方程组
的增广矩阵，而横线以下的这一行由目标函数的系数
组成（注意到目标函数中未出现 x3和x4 及常数项，
X1 X3 x1
0
0 1
x2
8 5 4 5
x3
1 0
x4
3 5 1 5
x0 12 8 256
22 5
0
32 5
对这张单纯形表，横线以上部分对应与原 约束方程组同解的方程组，此时等价地将 原规划问题变为如下问题：
22 32 min z 256 x2 x4 . 5 5
第二节:线性规划的解法 一、几个概念
对线性规划问题称满足全部约束条件的解为线 性规划问题的可行解，全部可行解的集合称为 可行域。使目标函数取最小值的可行解，称为 最优解，此时目标函数的最小值称为最优值。 一般讲,线性规划问题可行解有无穷多个,要从中 找出最优解也是很困难的。通常线性规划问题 的可行域的顶点只有有限多个,将这些点的的标 函数值全算出也是可以的.一般对于两个变量线 性规划问题进行图解法。
3x1 4 x 2 x3 36, 5x1 4 x 2 x 4 40;
以上可以得到问题的标准形 min z 32x 30x .
1 2
s.t.
3x1 4 x2 x3 36 5 x1 4 x2 x4 40 x 0 ( j 1,2,3,4) j
线性规划图解法
适用于任意变量、但必需将 一般形式变成标准形式
下面我们分析一下简单的情况—— 只有两个决策 变量的线性规划问题，这时可以通过图解的方法来 求解。图解法具有简单、直观、便于初学者窥探线 性规划基本原理和几何意义等优点。
精选课件
图解法
Page 2
一、线性规划的图解法（解的几何表示）
对于只有两个变量的线性规划问题，可以在二维直角坐标 平面上作图表示线性规划问题的有关概念，并求解。
X1 + 1.9X2 = 10.2 (≤)
8=5X1+4X2 此点是唯一最优解 （0，2）
D可行域
43=5X1+4X2
max Z
X1 + 1.9X2 = 3.8(≥)
min Z
o
L0： 0=5X1+4X2
精选课件
X1 - 1.9X2 = 3.8 (≤)
Page 18
x1
图解法
x2
6 3x1+x2=6(≥) 4
X = X1 + (1- ) X2 则必定有X = X1 = X2，则称X为S的一个顶点。
精选课件
图解法
Page 24
可以证明，线性规划的可行域以及最优解有以下 性质：
（1）、若线性规划的可行域非空，则可行域必定为一凸集；
（2）、线性规划问题的基本可行解对应于可行域的顶点；
（3）、若可行域有界，线性规划问题的目标函数一定可以在 其可行域的顶点上达到最优，或在可行域的某个顶点（唯一最 优解）或在某两个顶点及其连线上（无穷多最优解）得到。
2x1+ x2 50 z = 50x1+30x2= 1350
z = 50x1+30x2= 900
(15, 20)
下面我们分析一下简单的情况—— 只有两个决策 变量的线性规划问题，这时可以通过图解的方法来 求解。图解法具有简单、直观、便于初学者窥探线 性规划基本原理和几何意义等优点。
精选课件
图解法
Page 2
一、线性规划的图解法（解的几何表示）
对于只有两个变量的线性规划问题，可以在二维直角坐标 平面上作图表示线性规划问题的有关概念，并求解。
X1 + 1.9X2 = 10.2 (≤)
8=5X1+4X2 此点是唯一最优解 （0，2）
D可行域
43=5X1+4X2
max Z
X1 + 1.9X2 = 3.8(≥)
min Z
o
L0： 0=5X1+4X2
精选课件
X1 - 1.9X2 = 3.8 (≤)
Page 18
x1
图解法
x2
6 3x1+x2=6(≥) 4
X = X1 + (1- ) X2 则必定有X = X1 = X2，则称X为S的一个顶点。
精选课件
图解法
Page 24
可以证明，线性规划的可行域以及最优解有以下 性质：
（1）、若线性规划的可行域非空，则可行域必定为一凸集；
（2）、线性规划问题的基本可行解对应于可行域的顶点；
（3）、若可行域有界，线性规划问题的目标函数一定可以在 其可行域的顶点上达到最优，或在可行域的某个顶点（唯一最 优解）或在某两个顶点及其连线上（无穷多最优解）得到。
2x1+ x2 50 z = 50x1+30x2= 1350
z = 50x1+30x2= 900
(15, 20)
1.2线性规划的解
. ..
x2 .3 .
. x1 2x2 2 . . . . .
0
x1
解： （1）在直角坐标系上画出可行域
x1 4
x1 2x2 8
（2）做目标函数的等值线 x1 2x2 2
(3)最优值z* 8
求交点：
x1 x2
2x2 3
8
x1 x1
2x2 4
8
(x1, x2 ) (2,3)
(x1, x2 ) (4,2)
max z 7x1 x2
x1 2x2 6
s.t
x1 x2 1 x1 2
x1 , x2 0
其标准型为
max z 7x1 x2
x1 2x2 x3 6
s.t
x1 x2 x4 1 x1 x5 2
x1, x2 , x3 , x4 , x5 0
1 2 1 0 0
系数矩阵A
2x1 x2 3
可行域为空集
无可行解
该问题无最优解
图解法的基本步骤：
1、在直角坐标系x1ox2上做出可行域S的图形
（一般是一个凸多边形）
2、令目标函数值取一个给定的常数k,
做等值线Z c1x1 c2 x2 k 3、对max 问题，令目标函数值k由小变大, 即让等值线向上平移，
若它与可行域S最后交于一个点（一般是S的一个顶点）， 则该点就是所求的最优点， 若与S的一条边界重合，此时边界线上的点均是最优点
退化基本可行解：基本可行解中，存在取0值的基变量
对应的基称为退化基
非退化基本可行解：基本可行解中，基变量的取值均>0
对应的基称为非退化基
线性规划问题
退化的线性规划问题：存在退化基 非退化的线性规划问：题 所有基均非退化
第2章—线性规划
§5 利用EXCEL求解线性规划模型（练习2）
数学模型
目标函数 ：
max z = x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 s.t. x1 + 2x2 + x4 + x6 ≥ 100 2x3 + 2x4 + x5 + x6 + 3x7 ≥ 100 3x1 + x2 + 2x3 + 3x5 + x6 + 4x8 ≥ 100 x1 x8 ≥ 0
资源 设
产 品 备
Ⅰ 1 4 0
Ⅱ 2 0 4
拥有量 8台时 16 kg 12 kg
原材料 A 原材料 B
§1 线性规划问题—例1
如何用数学关系式描述这问题，必须考虑： 设 x1 , x2 分别表示计划生产产品Ⅰ、Ⅱ的数量，称它为 分别表示计划生产产品Ⅰ 决策变量；(确定决策变量阶段) 决策变量；(确定决策变量阶段) 生产 x1 , x2 数量的多少受资源拥有量的限制，这是约 束条件 x1 + 2 x2 ≤ 8; 4 x1 ≤ 16; 4 x2 ≤ 12；x1 , x2 ≥ 0 ； (确定 约束条件阶段) 约束条件阶段) 如何安排生产，使利润最大，这是目标 。(确定目 标函数阶段) 标函数阶段)
工厂1 工厂1： 工厂2 工厂2： 工厂3 工厂3：
x1 ≤ 4; 2 x2 ≤ 12； 3 x1 + 2 x2 ≤ 18
§1 线性规划问题—例3
可得上述问题的数学模型为：
max z = 3 x1 + 5 x2 x1 ≤ 4; 2 x ≤ 12； 2 s.t. 3 x1 + 2 x2 ≤ 18; x1 , x2 ≥ 0
线性规划及其解法
非基变量 σj 为0 是 无穷多最优解
否 存在aik>0 无界解
是
找出主元素，迭代
3.5 单纯形法的灵敏度分析 --目标函数中ck的灵敏度分析
当ck变成ck +△ck 原规划最优解不变的条件是： σj ‘≤0 • 在最终的单纯形表中，xk是非基变量时
σk ‘= ck+△ck- zk= △ck +σk ≤0 即： △ck ≤-σk 例
某单纯形表中，存在着一个大于零的检 验数，但该列中所有系数小于或等于零， 说明存在无界解。
max z x1 x2 x1 x2 1 s.t. 3x1 2 x2 6 x1 , x2 0
无穷多最优解：
对于某个最优的基本可行解，如果存在 某个非基变量的检验数为零，说明有无 穷多最优解。 最优解的线性组合仍是最优解，即 X=αX1+（1-α）X2， 0≤α ≤1 max z 50 x1 50 x2
cj cB x B b x5 2 2 x2 1 x1 4 Z
x1
2
x2
2
x3 x4 x5 x6
1 -1 2a
2 1 -1 1
-1 -2
-a+8
1、把表中缺少的项目填上适当的数或式子 2、要使上表成为最优表，a应满足什么条件 3、何时有唯一最优解 4、何时有无穷多最优解 5、何时以x3替换x1
• 2、2≤a ≤4 • 3、2<a<4 • 4、 2≤a ≤4 a=2或a=4 • 5、1<a<2 • 2/1>4/2a 0<a<2
• 系数矩阵A变化时 非基变量系数变化时，最优解不变 的条件是σk ‘≤0 基变量系数变化时，需重新计算
运筹学 第01章 线性规划问题
线性规划建模步骤
设定决策变量 明确约束条件并用决策变量的线性等式或 不等式表示 用变量的线性函数表示要达到的目标，并 确定是求极小还是求极大 根据变量的物理性质确定变量是否具有非 负性 注：其中最关键是设定决策变量这一步
生产计划问题(1)
某工厂用三种原料生产三种产品，已知的 条件如下表所示，试制订总利润最大的日 生产计划
线性规划问题解的有关概念(2)
基本解：令模型中所有非基变量的值等于零后，由 模型的约束方程组得到的一组解。 基本可行解：满足非负条件的基本解称为基本可行 解。 可行基：对应于基本可行解的基称为可行基。 退化解：基本可行解的非零分量个数小于m时，称 为退化解。 最优基：若对应于基B的基本可行解X是线性规划的 最优解，则称B为线性规划的最优基
人员安排问题(1)
医院护士24小时值班，不同时段需要的护 士人数不等（见下表）。每个护士每天连 续值班8小时，在各时段开始时上班。问最 少需要多少护士？
序号 1 2 3 4 时段 06—10 10—14 14—18 18—22 最少人数 60 70 60 50
5 6
22—02 02—06
20 30
人员安排问题(2)
设xj为第j时段开始值班的护士人数
目标函数为：使人数最少，则有
min f ( X ) x1 x2 x3 x4 x5 x6 x6 x1 60 x x 70 1 2 x2 x3 60 s.t. x3 x4 50 x x 20 5 4 x5 x6 30 x1 , x2 , x3 , x4 , x5 , x6 0且为整数
运筹学
第一章 线性规划问题
本章重点
线性规划建模 线性规划的图解法 线性规划的标准形式 单纯形法 两阶段法 大M法
线性规划探索线性规划的基本原理解决线性规划的相关问题
线性规划探索线性规划的基本原理解决线性规划的相关问题线性规划（Linear Programming）是一种常见的最优化方法，旨在找到一组变量的最佳取值，使得目标函数在满足一组线性约束条件的前提下取得最大或最小值。
它被广泛应用于经济学、管理学、工程学等领域，用于解决各类实际问题。
一、线性规划的基本模型及定义在介绍线性规划的原理之前，首先需要了解线性规划的基本模型和一些相关定义。
1. 目标函数（Objective Function）：线性规划的目标函数是需要进行最大化或最小化的变量，通常用线性函数表示。
以最大化为例，目标函数常用如下形式表示：```max Z = c₁x₁ + c₂x₂ + ... + cₙxₙ```其中，c₁、c₂、...、cₙ为常数，x₁、x₂、...、xₙ为决策变量。
2. 约束条件（Constraint）：线性规划的约束条件反映了问题的限制条件，通常为一组线性不等式或等式。
通常表示为：```a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙ```其中，a₁₁、a₁₂、...、aₙₙ为常数，x₁、x₂、...、xₙ为决策变量，b₁、b₂、...、bₙ为常数。
3. 决策变量（Decision Variable）：决策变量是需要确定取值的变量，它们的取值将会影响到目标函数和约束条件。
常用 x₁、x₂、 (x)表示。
基于以上定义，线性规划的一般形式可以表示为：```max Z = c₁x₁ + c₂x₂ + ... + cₙxₙs.t.a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙ```二、线性规划的解法线性规划问题的解法主要分为图形法、单纯形法和内点法等。