第1章 线性规划及单纯形法复习及举例

21
解：目标函数： Min 约束条件：
f = 2x1 + 3 x2
s.t.
x1 + x2 ≥ 350
x1 ≥ 125
2 x1 + x2 ≤ 600
x1 , x2 ≥ 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。
x2
x1 =125
600
500
2x1+3x2 =1200
400
2x1+x2 =600
26
凸集
定义 2.2.1：设 S Rn 是 n 维欧氏空间的点集，若对任意 x S, y S 的和任意 [0,1] 都有 x (1 ) y S 就称 S 是一个凸集。
定理 2.2.1 线性规划的可行域 D { x Ax b, x 0} 是凸集 定理 2.2.2 任意多个凸集 Si 的交还是凸集
例1 目标函数： max 50x1+100x2 约束条件：x1+x2+s1=300，
2x1+x2+s2=400， x2+s3=250.
xj≥0 （j=1，2）,sj≥0 （j=1，2,3）
30
它的系数矩阵 ,
1 1 1 0 0
A(p1,p2,p3,p4,p5)2 1 0 1 0
0 1 0 0 1
其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变
a i1 x 1 a i 2 x 2 a in x n s i b i , s i 0
或
a i1 x 1 a i 2 x 2 a in x n b i
松弛变量
a i1 x 1 a i 2 x 2 a in x n s i b i , s i 0

2.目标函数：设总利润为z，则 有： max z = 2 x1 + x2
3.约束条件：
2x1 + 2x2 ≤ 12
x1 + 2x2 ≤ 8
4x1
≤ 16
4x2 ≤ 12 x1 ≥ 0 , x2 ≥ 0
线性规划问题的数学模型
例1.4 某厂生产三种药物， 这些药物可以从四种不同的 原料中提取。下表给出了单 位原料可提取的药物量
线性规划问题的数学模型
3. 建模条件
(1) 优化条件：问题所要达到的目标能用线型函数描述，且 能够用极值（max 或 min）来表示；
(2) 限定条件：达到目标受到一定的限制，且这些限制能够 用决策变量的线性等式或线性不等式表示；
(3) 选择条件：有多种可选择的方案供决策者选择，以便找 出最优方案。
2x1
+4 x3 +2 x4 ＝200
3x1 ＋x2 +x3 +2 x4 ≤180
x1、x2 、x3 、x4 ≥0
线性规划问题的数学模型
例1.5 某航运局现有船只种类、数量以及计划期内各条航 线的货运量、货运成本如下表所示：
航线号
船队 类型
1 1
2
3 2
4
拖轮
1 1 2 1
编队形式 A型 驳船 2 — 2 —
目标函数： 约束条件：
max (min) z c1 x1 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 c j xj j1
线性规划问题的数学模型
例1.1 如图所示，如何截取x使铁皮所围成的容积最 大？

上页 下页 返回
重点与难点
7、*单纯形法的其它问题
1）最优性的判断 唯一最优解判断 无穷多最优解判断 无界解判断 2）检验数的公式法 3）最小化问题的最优性判 断与换基 所有检验数都非负为最优 解 最小的检验数对应的变量 进基 4）人工变量法求基可行解 两阶段法 大M法
上页 下页 返回
例某工厂生产A、B两种产品，有关资料如下表所示：
工序 产品
A 2 3 4
B 3 4 10
C 销售 — — 3 报废 — — －2
工序 1 工序 2
单位利润 （百元）
工时限 制 12 24
注：每生产单位产品 B 可得到 2 单位副产品 C，据 预测，市场上产品 C 的最大销量为 5 单位，若产 品 C 销售不出去，则报废。
上页 下页 返回
线性规划(运筹学)主要解决两类问题
企业利润=收入-成本 收入由提供产品或服务获得 成本由消耗的资源承担 1、资源有限（获成本），要求生 产的产品获得的收入（或利润）最 多。1 2、任务（或产品收入）一定，要 求消耗的资源（或成本）最少。2
上页 下页 返回
线性规划中的两类数学模型1
1）决策变量 2）目标函数 3）约束条件 4）符号约束
上页
下页
返回
重点与难点
3、两个自变量的线性规划的图解法 4、线性规划数学模型的标准形式 5、*一般线性规划的单纯形法基础
1）线性规划解的基本概念 可行解 最优解 基 基解 基可行解 可行基
上页
下页
返回
重点与难点
2）线性规划的几何意义 凸集 k个点的凸组合 凸集的顶点 线性规划可行域是凸集 3）基可行解的特征 可行解是基可行解的充分必要条件是其非零分 量的系数列向量线性无关 基可行解对应于可行域的顶点

ai1 x1+ai2 x2+ … +ain xn+s = bi 11
1.线性规划的概念
当约束条件为
ai1 x1+ai2 x2+ … +ain xn ≥ bi
时，类似地令
s=(ai1 x1+ai2 x2+ … +ain xn)- bi 显然，s 也具有非负约束，即s≥0，
这时新的约束条件成为
ai1 x1+ai2 x2+ … +ain xn-s = bi
生产所占用的机时数不能超过65，于是我
们可以得到不等式：3 x1 + 2 x2 ≤ 65； 对设备B，两种产品生产所占用的机
时数不能超过40，于是我们可以得到不等
式：2 x1 + x2 ≤ 40； 3
1.线性规划的概念
对设备C，两种产品生产所占用的
机时数不能超过75，于是我们可以得到
不等式：3x2 ≤75 ；另外，产品数不可 能为负，即 x1 ,x2 ≥0。同时，我们有
4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0
20
2.线性规划的图解法
线性规划的图解法(解的几何 表示)对于只有两个变量的线性规 划问题，可以二维直角坐标平面 上作图表示线性规划问题的有关 概念，并求解。图解法求解线性 规划问题的步骤如下：
x2=25，最优值z
划 =
的 最 优 解 x1=5 、
70000。即最优方
案为生产甲产品5件、乙产品25件，
可获得最大利润为70000元。