第7讲 线性规划模型.

x , x , x ≤8, x ≤6, x ≤7, x ≤3, x ≤4,
1 2 7 2 4 5 6
x
i
∈ N , i = 1,2,...7.
+
模型求解

求解结果：843.0000
线性规划模型
主讲人
组员
线性代数模型背景

线性规划模型是数学规划模型中最简单、最基本 的数学模型。线性规划模型主要解决如何使用有 限的劳动力，设备等资源安排生产以取得最大的 经济效益以及为达到一定的目标应如何组织生产， 或合理安排工艺流程或调整产品的成分以使生产 所消耗的各类资源最少等问题。

有些复杂问题，往往给人们以变幻莫测的感觉， 难以掌握其中的奥妙。当我们把思维扩展到线性 空间，利用线性代数的基本知识建立模型，就可 以掌握事物的内在规律，预测其发展趋势。

确定目标函数：目标应该是使得总价值最大，即
max z = 40 x1+ 37 x2 + 58 x3 + 36 x4 + 35 x5 + 45 x6 + 50 x7
55 x1+ 58 x2 + 62.4 x3+ 49 x4 + 40.6 x5 + 53.3 x6 + 66 x7 ≤ 1000,
0.5 x1+1.7 x2 + 3 x3 + 2.2 x4 + 3 x5 + x6 + 4 x7 ≤ 40
在实际运用中，特别是数学建模过程中，遇到线 性规划模型的求解，一般都是利用现有的软件进 行求解。比较常用的求解线性规划模型的软件有 Lingo和Matlab等

建立线性规划模型基本步骤来自找出待定的未知变量（又称为决策变量-决策者 自己可以控制的变量），并且用符号表示；

cj(j1,2, ,n)称为价值系数或目标函数系数
bi(i1,2, ,m) 称为资源常数或约束右端常数
a ij 0 (i= 1 ,..,m ;j= 1 ,..,n ) 称为技术系数或约束系数
概 念 和 模 型
紧缩形式：
n
max（或min） Z c j x j j 1 n max z cj xj j 1
24
x1 , x 2 0
(1.1a) (1.1b) (1.1c) (1.1d)
运用图解法，以求出最优生产计划 （最优解）。
图
由于线性规划模型中只有两个决策 变量，因此只需建立平面直角坐标系就
解
可以进行图解了。
法
1.建立平面直角坐标系，标出坐标原点, 坐标轴的指向和单位长度。
2.对约束条件加以图解，找出可行域。
定理 如果向量 的第 k 个分量k 0 ，而向量 B 1 Ak 0 ， 则原问题无界。
定理 对于非退化的基本可行解 x ，若向量 的第 k 个分量 k 0 ，而向量 B 1 Ak . 至少有一个正分量，则可以找到一个新的 基本可行解 xˆ 使得 c xˆ c x 。
给定一个非退化的基可行解 x ，对应的可行基为 B ，则等式约束变为：
解 的 概 念
线性规划问题
可行解：
n
max z c j x j j 1
s.t.
n j 1
aij x j
bi
(i 1,.., m)
x
j
0
（j 1,2, , n）
变量满足所有约束条件的一组值
可行解集：
所有可行解构成的集合
可行域：
可行解集构成n维空间的区域
AX b
x
0
D {x|Ab xx ,0 }

j 1
i 1
将目标函数和约束条件放在一起，即得指派问题的数学模型.
第i人花费在第j项工作的时间用cijxij表示，在所有的工作中，第i人干仅干一项工作，
若第i人被分配去干第j0项工作，则当j0≠j时，cijxij=0，所以花费的总时间为T

nn
cij xij
.
i1 j 1
n
n
对于第i人，应有 xij 1 ；对于第j项工作，应有 xij 1 .
cT x
Ax b

A
eq
x beq
l b x u b
Matlab中求解线性规划的命令为：
[x，fval]=linprog(c，A，b，Aeq，beg，lb，ub)
其中，x返回的决策变量x的取值，fvla返回的是目标函数的最优值.
注：若没有某种约束，则相应的系数矩阵赋值为空矩阵，如没有等式约束，则令Aeq=[]， beq=[].
（7）模型的分析与评价
在建立线性模型是，总是假定aij，bi，cj都是常数，但实际上这些系数往往是估计值 和预测值，如市场条件一变，aij值就会变化；bi往往因工艺条件的改变而改变；cj是根据 资源投入后的经济效果决定的一种决策选择.因此，这些参数在什么范围内变化时，线 性规划问题的最优解不变.
2.整数规划模型
3. 0-1整数模型
在部分规划问题中，每个需要做的决策只有两种时，可以使用0-1整数规划建模，它的 变量xi仅取值0或1.此类模型可用Lingo和Matlab求解.Matlab中规定0-1整数规划模型中的标准形 式为：
min cT x Ax b
s.t. Aeq x beq
Matlab中求解0-1规划的命令为： [x，fval]=bintprog(c，A，b，Aeq，beq)

第六年所掌握的资金最多。
解：设x1为第一年的投资; x2为 第一年的保留资金
x1+ x2 第二年： x3为=第10二0 年新的投资； x4：第二年的保 留资金；
2021年5月22日星期六
( x1 2
x3 )
x4
x2
第14页/共21页
第三年：x5为新的投资；x6：第三年的保留资金；
(
x3 2
x5 )
2021年5月22日星期六
第3页/共21页
线性规划的数学模型由
决策变量 Decision variables 目标函数Objective function 及约束条件Constraints
构成。称为三个要素。
怎样辨别一个模型是线性规划模型？ 其特征是：
1．解决问题的目标函数是多个决策变量的
线性函数，通常是求最大值或 最小值；
x7
x j 0, j
2 x 8 2 x9 1,2,,9
0
用单纯形法解得：X＝（22.64，72.36，58.54，0， 26.02， 0，104.06，0，0）’。Z＝208.12。
2021年5月22日星期六
第16页/共21页
即：第一年投资22.64元; 第二年新投资58.54元; 第三年新投资26.02元; 第四年新投资104.06元; 第六年末有资金208.12万元。
第18页/共21页
为了书写方便，上式也可写成
n
max(min) Z c j x j j 1
n j 1
aij
x
j
(或
,)bix j 0 j 1,2,, ni 1,2,, m
在实际中一般xj≥0,但有时xj≤0或xj无符号限制。
2021年5月22日星期六