线型规划与单纯形法

2.目标函数：设总成本为z
min z = 5 x1 + 6 x2 + 7 x3 + 8 x4 3.约束条件：
x1 + 2x2 + x3 + x4 ≥160
要求：生产A种药物至少160 单位；B种药物恰好200单位， C种药物不超过180单位，且 使原料总成本最小。
2x1
+4 x3 +2 x4 ＝200
线性规划问题的数学模型
5. 线性规划数学模型的一般形式
目标函数：
max (min) z c1x1 c2 x2
cn xn
a11 x1 a12 x2
a1n xn ( ) b1
约束条件：
am1 x1 am2 x2
amn xn ( ) bm
x1 0
xn 0
n
简写为： max(min)Z cj xj
j1
n
aij xj ( ) bi
j1
xj 0
(i 1 2m) (j 1 2n)
线性规划问题的数学模型
向量形式： max(min)z CX
pj xj ( ) b
X 0
其中： C(c1 c2 cn)
x1
X
x n
P
j
a
1
j
a mj
b1
b
b m
线性规划问题的数学模型
3.约束条件：
2x1 + 2x2 ≤ 12
x1 + 2x2 ≤ 8
4x1
≤ 16
4x2 ≤ 12 x1 ≥ 0 , x2 ≥ 0
线性规划问题的数学模型
例1.4 某厂生产三种药物， 这些药物可以从四种不同的 原料中提取。下表给出了单 位原料可提取的药物量

状态值，各条弧代表了可行的方案选择。 • 正确。
整理课件
59
• （4）动态规划的基本方程是将一个多阶段的决策问题转化为一系列具 有递推关系的单阶段决策问题。
• 正确。 • （5）建立动态规划模型时，阶段的划分是最关键和最重要的一步。 • 错误。 • （6）动态规划是用于求解多阶段优化决策的模型和方法，这里多阶段
• 错误。
• 唯一最优解时，最优解是可行域顶点，对应基本可行解；无穷多最优 解时，除了其中的可行域顶点对应基本可行解外，其余最优解不是可 行域的顶点。
• （12）若线性规划问题具有可行解，且其可行域有界，则该线性规划 问题最多具有有限个数的最优解。
• 错误。
• 如果在不止一个可行解上达到最优，它们的凸组合仍然是最优解，
结束时间不允许有任何延迟。 • 正确。 • （10）网络关键路线上的所有作业，其总时差和自由时差均为零。 • 正确。 • （11）任何非关键路线上的作业，其总时差和自由时差均不为零。 • 错误。
整理课件
57
• （12）若一项作业的总时差为零，则其自由时差一定为零。 • 正确。 • （13）若一项作业的自由时差为零，则其总时差比为零。 • 错误。 • （14）当作业时间用a,m,b三点估计时，m等于完成该项作业的期
既可以是时间顺序的自然分段，也可以是根据问题性质人为地将决策 过程划分成先后顺序的阶段。
• 正确。
整理课件
60
•
整理课件
61
此课件下载可自行编辑修改，供参考！ 感谢您的支持，我们努力做得更好！
整理课件
62
5 3 6 -6 0
0
801001
5
14 1 2 0 0 0
-6
4 0 1 -1 1 0

产，已知生产单位产品所需的设备台时及A、B两种 原材料的消耗，以及资源的限制如下表所示：
甲 乙 设备 1 1 原料A 2 1 原料B 0 1 单件利润 50（元/件） 100（元/件）
Байду номын сангаас
资源限制 300台时 400千克 250千克
问:工厂应分别生产多少个产品甲、乙才能使工厂获利最多？
设生产甲产品x1个，生产乙产品x2个
j 1
n
n aij x j (或 ， ）bi (i 1, 2, , m) s.t. j 1 x 0( j 1, 2, , n) j
n j 1 n p j x j (或 ， ）b s.t. j 1 x 0( j 1, 2, , n) j
x2 B
C z=27500=50x1+100x2 z=20000=50x1+100x2 D z=0=50x1+100x2 E
A
z=10000=50x1+100x2
x1
图2-2
解的几种可能结果
唯一最优解解 无穷多个最优解 无界解(可行域无界，常为模型遗漏了某些 必要的约束条件) 无可行解（可行域为空集，约束条件自相矛 盾,资源满足不了人们的需求）
(2) MinZ Max(Z ) 3 y1 5 x2 y2 y3
(3) 3 y1 2 x2 y2 y3 6
3 y1 2 x2 y2 y3 6
(4)在第一、第三约束左端加上松弛变量 x4,x6≥0 ，在第二约束左端减去剩余变量 x5≥0
解:
2x1+x2=400 x2=250
100
100 200 300
x2≤250

的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般 情况m≤n，且r(Ａ)＝m。
一般形式线性规划模型的标准化准则: （前提 bi ≥0 ）
Z cx 1 . min Z cx max
2. aij xj b i
j 1
n
n
n aij x j x n i bi j 1 x n i 0
(4)第三个约束条件是“≤”号且常数项为负数，因此在 “≤”左边加入松驰变量x6，x6≥0，同时两边乘以－1。
2.3 线性规划的标准型 Standard form of LP
(5)目标函数是最小值，为了化为求最大值，令Z′=－Z,
得到 max Z′=－Z，即当Z达到最小值时Z′达到最大值。
2.3 线性规划的标准型 Standard form of LP
2.4 线性规划的有关概念
Basic Concepts of LP
2.4 基本概念 Basic Concepts
设线性规划的标准型
max Z=CX
AX=b X ≥0
(2.1)
(2.2) (2.3)
式中 A 是 m×n矩阵， m≤n 并且 r(A)=m，显然 A中至少 有一个m×m子矩阵B，使得r(B)=m。 基 (basis)：A中 m×m子矩阵 B 并且有r(B)=m，则称B 是线性规划的一个基(或基矩阵basis matrix )。
求所有基矩阵。 【解】约束方程的系数矩阵为2×5矩阵
11 0 5 1 A 106 2 0 1
11 0 5 1 A 106 2 0 1
容易看出r(A)=2，2阶子矩阵有C52=10个，其中第1列与 第3列构成的2阶矩阵不是一个基，基矩阵只有9个，即