线性规划与单纯形法

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 某厂生产三种药物， 这些药物可以从四种不同的 原料中提取。下表给出了单 位原料可提取的药物量

产，已知生产单位产品所需的设备台时及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

1 3 第一章线性规划与单纯形法运筹学习题集第一章线性规划与单纯形13第一章线性规划与单纯形法运筹学习题集第一章线性规划与单纯形法复习思考题1. 试述线性规划数学模型的结构及各要素的特征。

2. 求解线性规划问题时可能出现哪几种结果?哪些结果反映建模时有错误?3. 什么是线性规划问题的标准形式?如何将一个非标准型的线性规划问题转化为标准形式?4. 试述线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。

5. 试述单纯形法的计算步骤，如何在单纯形表上判别问题是具有唯一最优解、无穷多最优解、无界解或无可行解?6. 如果线性规划的标准型变换为求目标函数的极小化min z，则用单纯形法计算时如何判别问题已得到最优解?7. 在确定初始可行基时，什么情况下要在约束条件中增添人工变量?在目标函数中人工变量前的系数为(-M)的经济意义是什么?8. 什么是单纯形法计算的两阶段法?为什么要将计算分成两个阶段进行,如何根据第一阶段的计算结果来判定第二阶段的计算是否需要继续进行?9. 简述退化的含义及处理退化的勃兰特规则。

10. 举例说明生产和生活中应用线性规划的可能案例，并对如何应用进行必要描述。

11. 判断下列说法是否正确:(a) 图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的;(b) 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大;(c) 线性规划问题的每一个基解对应可行域的一个顶点;(d) 如线性规划问题存在可行域，则可行域一定包含坐标的原点;(e) 对取值无约束的变量xj，通常令xj=x′j-x″j，其中x′j?0，x″j?0，在用单纯形法求得的最优解中有可能同时出现x′j,0，x″j,0;(f) 用单纯形法求解标准型的线性规划问题时，与σj,0对应的变量都可以被选作换入变量; (g) 单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负;(h) 单纯形法计算中，选取最大正检验数σk对应的变量xk作为换入变量，将使目标函数值得到最快的增长;(i) 一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果;(j) 线性规划问题的任一可行解都可以用全部基可行解的线性组合表示; (k)若X1，X2分别是某一线性规划问题的最优解，则X=λ1X1+λ2X2也是该线性规划问题的最优解，其中λ1、λ2可以为任意正的实数;(l) 线性规划用两阶段法求解时，第一阶段的目标函数通常写为minz=?ixai(xai为人工变量)，但也可写为min z=?ikixai,只要所有ki均为大于零的常数;(m)对一个有n个变量、m个约束的标准型的线性规划问题，其可行域的顶点恰好为Cmn个; (n) 单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解; (o) 线性规划问题的可行解如为最优解，则该可行解一定是基可行解; (p) 若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解;(q) 线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值，则该顶点处的目标函数值达到最优;(r) 将线性规划约束条件的“?”号及“?”号变换成“=”号，将使问题的最优目标函数值得到改善;(s) 线性规划目标函数中系数最大的变量在最优解中总是取正的值;(t) 一个企业利用3种资源生产4种产品，建立线性规划模型求解得到的最优解中，最多只含有3种产品的组合;(u) 若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解; (v) 一个线性规划问题求解时的迭代工作量主要取决于变量数的多少，与约束条件的数量关系相对较小。

的系数矩阵，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个，即