当前位置：文档之家 › 第一章 线性规划及单纯形法(7)

第一章 线性规划及单纯形法(7)

  • 格式：ppt
  • 大小：272.00 KB
  • 文档页数：17

下载文档原格式

  / 17

合集下载

第1讲线性规划及单纯形法

第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

运 筹 学 课 件

运 筹 学 课 件

12/3 4
z
1 2
x4
x5 42
x3
2 3
x4
1 3
x5
4
新典式
主元化 为1，主 元所在
x2
1 2
x4
6
列的其 余元素
x1
2 3
x4
1 3
x5
4
化为0
观察最后一个典式，所有检验数均为非负， 故其对应的基本可行解为最优解，即
X * 4,6,6,0,0T z* 42
去掉引入变量，得原问题的最优解为：
运筹学课件
目录
运筹学概论 第一章 线性规划基础 第二章 单纯形法 第三章 LP对偶理论 第四章 灵敏度分析 第五章 运输问题 第六章 整数规划 第七章 动态规划 第八章 网络分析
第二章 单纯形法
(SM-Simplex Method)
1947年，美国运筹学家Dantzig提出，原理是 代数迭代。
单纯形法中的单纯形的这个术语，与该方法毫 无关系，它源于求解方法的早期阶段所研究的一 个特殊问题，并延用下来。
CB B1b B1b
z
CB B1N CN X N X B B1NX N
CB B1b B1b
上述方程组的矩阵形式为
10
0 I
CB
B1N B1N
CN
z XB XN
CB B1b B1b
上式的系数增广阵称为对应于基B的单纯形表：
T(B)
CB B1b B1b
0 I
CB
B1N B1N
CN
形式的LP问题，必须解决三个问题： ⑴初始基本可行解的确定； ⑵解的最优性检验； ⑶基本可行解的转移规则。 这里先放一下⑴，研究⑵和⑶，为此，

第一章_线性规划

第一章_线性规划

第 一 节 线性规划问题及其数学模型
一、线性规划问题的数学模型
线性规划问题主要解决以下两类问题： 1、任务确定后，如何统筹安排，做到应用尽量少的人 力和物力资源来完成任务； 2、在一定量的人力、物力资源的条件下，如何安排、 使用他们，使完成的任务最多。
在生产管理和经济活动中，经常会遇到线性规划问 题，如何利用线性规划的方法来进行分析，下面举例 来加以说明。
表1－2
成分
产品来源
分析：很明显，该厂可以有多种不同的方案从A，B 两处采购原油，但最优方案应是使购买成本最小的一 个，即在满足供应合同单位的前提下，使成本最小的 一个采购方案。
解：设分别表示从A，B两处采购的原油量（单位：万 吨），建立的数学模型为：
m in S 200 x1 290 x2
3. 若存在无非负要求的变量。即有某一个变 量 xj 取正值或负值都可以。这时为了满足标准型 对变量的非负要求，可令 xj = xjˊ- xj〞, 其中： xjˊ、 xj〞 0 ，由于xjˊ可能大于也可能小于xj〞，故 xj 可以为正也可以为负。
上述的标准型具有如下特点： （1）目标函数求最大值； （2）所求的变量都要求是非负的； （3）所有的约束条件都是等式； （4）常数项非负。 综合以上的讨论可以说明任何形式的线
max Z x1 2x2 3x4 3x5 0x6 0x7
x1 x2 x4 x5 x6 7
x13x1x2
x4 x2
x5 2x4
x7 2 2x5 5
x1, x2, x4, , x7 0
第二节 线性规划问题的图解法及几何意义
例1－1：（计划安排问题）某工厂在计划期内安排 生产Ⅰ、Ⅱ两种产品，已知生产单位产品所占用的 设备A、B的台时、原材料的消耗及两种产品每件 可获利润见表所示：

第一章 线性规划及单纯形法

第一章 线性规划及单纯形法
37
线性规划问题的标准形式： 线性规划问题的标准形式：
max f = ∑ c j x
j =1 j n
n ∑ aij x j = bi , i = 1,2,L , m j =1 x j ≥ 0, j = 1,2,L , n
日产量（ 日产量（吨） 9 5 7 21
11
）（模型 例2（运输问题）（模型） （运输问题）（模型）
minf = 2 x11 + 9 x12 + 10 x13 + 7 x14 + x21 + 3 x22 + 4 x23 + 2 x24 + 8 x31 + 4 x32 + 2 x33 + 5 x34 x11 + x12 + x13 + x14 = 9 x +x +x +x =5 23 24 21 22 x31 + x32 + x33 + x34 = 7 x11 + x21 + x31 = 3 s.t. x12 + x22 + x32 = 8 x13 + x23 + x33 = 4 x14 + x24 + x34 = 6 xij ≥ 0(i = 1,2,3; j = 1,2,3,4)
18
3、（线性规划）数学模型的三要素 、（线性规划） 、（线性规划 变量/决策变量 决策变量； ①变量 决策变量； 目标函数（ ②目标函数（max/min）； ）； 约束条件。 ③约束条件。
19
决策变量： ①变量/决策变量：指决策者为实现规划目标采 变量 决策变量 取的方案、措施，是问题中要确定的未知量； 取的方案、措施，是问题中要确定的未知量；

运筹学

运筹学

11
目录
（三）LP问题的标准型
1.为了讨论LP问题解的概念和解的性质以及对LP问题求 解方便，必须把LP问题的一般形式化为统一的标准型：
minz=c1x1+c2x2+…+cnxn
j =1 a11 x2 + a12 x2 + + a1n xn = b1 a x + a x + + a x = b n 2n n 2 21 2 22 2 简 aij x j = bi (i = 1,2, L , m) s.t 化 j =1 x j ≥ 0( j = 1,2,L , n) am1 x2 + am 2 x2 + + amn xn = bm x1 , x2 , , xn ≥ 0
A ( 0 ,3 ) 10 15 , ) B( 7 7 5 C ( ,0 ) 2
max
Z = 5 x1 + 4 x 2
3 x 1 + 5 x 2 ≤ 15 2 x1 + x 2 ≤ 5 2 x 1 + 2 x 2 ≤ 11 x1 , x 2 ≥ 0
Z=
110 7
2x1+2x2=11
C 2.5
5x1+4x2=0 红线为目标函数的等值线 等值线. 红线为目标函数的等值线
j i= 1
j
(1.4) (1.5) (1.6)
ì n a ij x j = s .t . j = 1 í 1.从代数的角度看： x j 0 1.
b
i
可行解（Feasible Solution)： 满足约束条件(1.5)和(1.6)的 解X=(x1,x2,…,xn)T称为可行解。所有可行解构成可行解集， 即可行域。 最优解(Optimal Solution): 而使目标函数达到最大值的可 行解称为最优解，对应的目标函数值称为最优值。 求解LP问题就是求其最优解和最优值，但从代数的角 17 度去求是困难的。 目录

运筹学复习题

运筹学复习题
5、制造某机床需要A、B、C三种轴，其规格、需要量如下表所示。各种轴都用长7.4米的圆钢来截毛坯。如果制造100台机车，问最少要用多少根圆钢？试建立该问题的线性规划模型，并写出其对偶规划。
轴件
规格：长度（米）
每台机床所需轴件数量
A
B
C
2.9
2.1
1.5
1
1
1
6、试用单纯形法求解下列线性规划问题
2、某工厂生产A、B、C三种产品，现根据订货合同以及生产状况制定生产计划。
已知甲合同为：A产品1000件，单价600元，违约金为120元/件；
B产品700件，单价500元，违约金为100元/件。
乙合同为：B产品900件，单价550元，违约金为110元/件；
C产品800件，单价450元，违约金为90元/件。
有关各产品生产过程所需工时以及原材料的情况见下表。试以利润最大为目标，建立该工厂的生产计划线性规划模型（不求解）。
（1）应如何指派，使总的翻译效率最高？
（2）若甲不懂德文，乙不懂日文，其他数字不变，则应如何指派？
第五章图与网络分析
一复习思考题
1．通常用G(V，E)来表示一个图，试述符号V，E及这个表达式的涵义。
2．解释下列各组名词，并说明相互间的联系和区别：(a)端点，相邻，关联边；(b)环，多重边，简单图；(c)链，初等链；(d)圈，初等圈，简单圈；(e)回路，初等路；(f)节点的次，悬挂点，孤立点；(g)连通图，支撑子图；(h)有向图，赋权图。
2、用分技定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数是该问题目标函数值的下界；
3、用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取其中一个作为下界值，再进行比较剪枝；

运筹学第1章：线性规划问题及单纯型解法

运筹学第1章：线性规划问题及单纯型解法

原料甲 原料乙 最低含量 VA 0.5 0.5 2 VB1 1.0 0.3 3 VB2 0.2 0.6 1.2 VD 0.5 0.2 2 0.3 0.5 单价
分别代表每粒胶丸中甲, 设 x1, x2分别代表每粒胶丸中甲, 乙两种原料的用量
5
例3,合理下料问题 , 分别代表采用切割方案1~8的套数, 的套数, 设 xj 分别代表采用切割方案 的套数
19
( f(x
)= 3
6
1.2.2 单纯型法的基本思路
确定初试基础可行解
检查是否为 最优解? 最优解?
是
求最优解的目标函数值
否 确定改善方向
求新的基础可行解
20
1.2.3 单纯型表及其格式
IV CB III XB II x1 b c1 a11 a21 c1′′= cn+1 xn+1 b1 c2′′= cn+2 xn+2 b2 x2 … xn c2 … cn a12 … a1n a22 … a2n I xn+1 cn+1 1 0 0 zn+1 xn+2 cn+2 0 1 0 zn+2 … … … … … … xn+m cn+m 0 0 1 zn+m
OBJ : max f ( x) = 6x1 + 4x2 2x1 + x2 ≤ 10 铜资源约束 x1 + x2 ≤ 8 铅资源约束 s.t. x2 ≤ 7 产量约束 x1, x2 ≥ 0 产量不允许为负值 最优解: x1 = 2, x2 = 6, max f ( x) = 36.
4
例2,配料问题(min, ≥) ,配料问题(
2 max 1 O 1 2 3 4 D 5 6 7 H 8

第1章 线性规划

第1章 线性规划

第1章线性规划本章介绍了什么是线性规划，线性规划数学模型的概念及其建立数学模型方法；阐述了线性规划的图解法、解的概念及解的形式；详细介绍了普通单纯形法、人工变量单纯形法及单纯形法计算公式。

1．考核知识点（1） 基本概念：数学模型、决策变量、目标函数、约束条件、标准型、图解法、基矩阵、基变量、非基变量、可行解、基解、基可行解、最优解、基最优解、唯一解、多重解、无界解、无可行解、单纯形法、最小比值、入基变量、出基变量、解的判断、大M法、两阶段法、改进单纯形法。

（2） 建立简单的线性规划数学模型。

（3） 求解线性规划的图解法。

（4） 基、可行基及最优基的定义。

（5） 可行解、基本解、基可行解、最优解、基本最优解的定义及其相互关系。

（6） 有唯一解、有无穷多解、无界解、无可行解的判断。

（7） 求解线性规划的单纯形法。

（8） 求解线性规划的人工变量法。

（9） 单纯形法中的5个计算公式。

2．学习要求（1） 深刻领会线性规划的各种基与解的基本概念，它们之间的相互关系。

（2）掌握图解法的计算步骤，注意怎样将目标函数表达成一条直线，这条直线如何平移使得目标函数值上升或下降。

（3） 熟练掌握单纯形法计算的全过程，特别应注意如何列出单纯形表，如何由一个基可行解换到另一个基可行解，基可行解是最优解、无界解或多重解的判断准则。

（4） 理解在什么情况下加入人工变量，人工变量起何作用，用大M法计算时目标函数的变化，两阶段法计算时目标函数的构成，掌握这两种计算方法的全过程，在什么情形下线性规划无可行解。

（5） 理解用矩阵形式代替单纯形表，并用矩阵公式求解线性规划。

3．重点建立线性规划数学模型，有关线性规划解的概念、解的形式，单纯形法计算、大M法、两阶段法。

4．难点解析（1）建立线性规划数学模型建立数学模型是学习线性规划的第一步也是关键的一步。

建立正确的数学模型要掌握3个要素：研究的问题是求什么，即设置决策变量；问题要达到的目标是什么即建立目标函数，目标函数一定是决策变量的线性函数并且求最大值或求最小值；限制达到目标的条件是什么，即建立约束条件。

运筹学第一章

运筹学第一章
OR1
30
1.1.3解的概念
概念： 1、可行解：满足所有约束条件的解。 2、可行域：即可行解的集合。所有约束条件的交 集，也就是各半平面的公共部分。满足所有约 束条件的解的集合，称为可行域。 3、凸集：集合内任意两点的连线上的点均属于这 个集合。如：实心球、三角形。线性规划的可 行域是凸集。
OR1
OR1
27
线性规划图解法例题
（无界解）
max z x 2 y x y 1 2 x 4 y 3 x 0, y 0
OR1
28
线性规划图解法例题
（无解）
min z x 2 y x y 2 2 x 4 y 3 x 0, y 0
请问该 医院至 少需要 多少名 护士？
5
例题2建模
目标函数：min Z=x1+x2+x3+x4+x5+x6 约束条件： x1+x2 ≥70
x2+x3 ≥60 x3+x4 ≥ 50 x4+x5 ≥20 x5+x6 ≥30 非负性约束：xj ≥0,j=1,2,…6
OR1
6
例题3：运输问题
三个加工棉花的加工厂，并且有三个仓库供应棉花，各 供应点到各工厂的单位运费以及各点的供应量与需求量 分别如下表所示：问如何运输才能使总的运费最小？
OR1
14
总
结
从以上 5 个例子可以看出，它们都属于优化问题，它们 的共同特征： 1 、每个问题都用一组决策变量表示某一方案；这组决 策变量的值就代表一个具体方案，一般这些变量取值是 非负的。 2 、存在一定的约束条件，这些约束条件可以用一组线 性等式或线性不等式来表示。 3 、都有一个要求达到的目标，它可用决策变量的线性 函数（称为目标函数）来表示。按问题的不同，要求目 标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划的数学模型。

第一章线性规划及单纯形法

第一章线性规划及单纯形法

第一章线性规划及单纯形法6.6单纯形法小结Drawingontheexampl,thetwoaxisinterceptsareplotted.2、求初始基可行解并进行最优性检验Cj比值CBXBb 检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000令非基变量x1=0，x2=0，找到一个初始基可行解：x1=0，x2=0，x3=8，x4=12，x5=36，σj＞0，此解不是最优（因为z=3x1+5x2+0x3+0x4+0x5)即X0=(0,0,8,12,36)T，此时利润Z=03、寻找另一基可行解Cj比值CBXBb检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9主元首先确定入基变量再确定出基变量检验数?j81010060101/2012300-21x3x2x5050-30300-5/20Cj比值CBXBb检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9令x1=0，x4=0，得x2=6，x3=8，x5=12，即得基可行解X1=(0,6,8,0,12)T此时Z＝30σ1=3＞0，此解不是最优迭代4、寻找下一基可行解Cj比值CBXBb检验数?jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数?j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1令x4=0，x5=0，得x1=4，x2=6，x3=4，即X0=(4,6,4,0,0)T?j＜0最优解:X=(4,6,4,0,0)T最优值:Z=42小结：单纯形表格法的计算步骤①将线性规划问题化成标准型。

②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。

运筹学第一章

运筹学第一章

产品Ⅱ生产x2件。
4x1
≤ 16
这里z为利润函数，
4x2 ≤ 12
max z:表示求z的最大值。
x1，x2 ≥ 0
1
[eg.2]污水处理问题
环保要求河水含污低于2‰，河水可自身净化20%。 问：化工厂1、2每天各处理多少污水，使总费用最少？
分析：
500万m3
化工厂1
2万m3 1000元/万m3 化工厂2
(2)不等式(≤，≥) 对于“≤”情况：在“≤”左边加上一个松弛变量（非
负），变为等式； 对于“≥”情况：在“≥”左边减去一个剩余变量（非
负），变为等式。 注意：松弛变量、剩余变量在目标函数中的价值系数为0。
(3)无约束变量 令xk = xk’ - xk”，xk’,xk” ≥ 0，代入即可。
13
[eg.7]将下述问题化为标准型
22
3、人工基
[eg.10]max z = x1 + 2x2 + 3x3
x1 + 3x2 + 2x3 = 3 2x1 + x2 + x3 = 4 x1,x2,x3 ≥ 0 分析： A= 1 3 2 211 ∵ 找不到单位矩阵基 ∴ 引入人工变量为初始基变量（2个）
23
3.2 最优性的检验与解的判别
min z = -x1+2x2-3x3 x1+ x2+ x3 ≤ 7 ① x1- x2+ x3 ≥ 2 ②
-3x1+ x2+2x3 = 5 ③ x1,x2 ≥ 0，x3无约束
解：令x3 = x3’-x3”，x3’,x3” ≥ 0；
①式加上一个松弛变量x4；②式减去一个剩余变量x5； 令z’ = -z

运筹学第一章

运筹学第一章
max z = - x1’ +2x2 +3（ x3’ - x3” ） - x1’ +x2 – ( x3’ - x3” )-x4 = 9 st. 3x1’ +2x2 -4 ( x3’ - x3” )-x5= 7 x1’ +2x2 - 3 ( x3’ - x3” ) = 6 x1’ ≥ 0, x2 ≥ 0, x3’ ≥0 x3” ≥0
3.线性规划问题的标准形式 线性规划问题的标准形式 max z =- x1-2x2 -3x3 2 x1’+x2 +(x3’ - x3” )+ x4 = 9 3 x1’ +x2 +2 (x3’ - x3” ) –x5 = 4 st. -4 x1’ +2x2 +3 (x3’ - x3” ) =6 x1’ ≥ 0, x2 ≥0, x3’ ≥0 x3” ≥0
例1-1-2 ---1 min z = x1+2x2 +3x3 ﹣2 x1+x2 +x3 ≤9 st. ﹣3 x1+x2 +2x3 ≥ 4
4 x1－2x2 － 3x3 =﹣6
x1 ≤0, x2 ≥0, x3 无约束。 （1）min z = x1+2x2 +3x3 令Z=-Z’ min Z=min（-z ’）=max z ’
第一章 讲解内容
第一节： 第一节：线性规划问题及其数学模型 第二节： 第二节：线性规划问题的几何意义 第三节：单纯形法 第三节： 第四节： 第四节：单纯形法的计算过程 第五节： 第五节：单纯形法的进一步讨论 第六节： 第六节：应用案例
第一章 线性规划问题及其数学模型 1. 问题的提出 2.图解法（重点） 3. 线性规划问题的标准形式 4.线性规划问题的解的概念（重点、难点）

运筹学基础及应用第五版胡运权第一章

运筹学基础及应用第五版胡运权第一章
问题的提出 某企业计划生产Ⅰ、Ⅱ两种产品。这两种产品都要分别在A、B、C、D四种不同设备上加工。生产每件产品Ⅰ需占用各设备分别为2、1、4、0h，生产每件产品Ⅱ，需占用各设备分别为2、2、0、4h。已知各设备计划期内用于生产这两种产品的能力分别为12、8、16、12h，又知每生产一件产品Ⅰ企业能获得2元利润，每生产一件产品Ⅱ企业能获得3元利润，问企业应安排生产两种产品各多少件，使总的利润收入为最大。
xi 0
aij
aLj
xL 0
i
∴ P1 , P2,······,PL-1, PL+1,······ Pm, Pj 线性无关。
∴ X1 也为基本可行解。
四、最优性检验和解的判别
令
，其中 随基的改变而改变
X1 = (x1 0- a1j ,x2 0- a2j ,···,xm 0- amj ,0,···,,···,0)T
必要性：X非基本可行解 X非凸集顶点 不失一般性，设X=(x1,x2,······,xm,0,0,······,0)T，为非基本可行解， ∵ X为可行解，
证：等价于 X非基本可行解X非凸集顶点
又 X是非基本可行解， ∴ P1,P2,······,Pm线性相关，即有 1P1+2P2+······+mPm=0， 其中1，2，······，m不全为0，两端同乘≠0，得 1P1+2P2+······+mPm=0，······（2）
∵ >0, 1->0 ，当xj=0， 必有yj=zj=0
∴
pjyj =
j=1
n
pjyj=b ······(1)
j=1
r
pjzj =
j=1
n
pjzj=b ······(2)

运筹学第一章

运筹学第一章

第一章、 线性规划和单纯形法1.1 线性规划的概念一、线性规划问题的导出1．(引例) 配比问题——用浓度为45%和92%的硫酸配置100t 浓度为80%的硫酸。

取45%和92%的硫酸分别为x1和x2t,则有： 求解二元一次方程组得解。

目的相同，但有5种不同浓度的硫酸可选（30%，45%，73%，85%，92%）会出现什么情况？设取这5种硫酸分别为 x1、x2、x3、x4、x5 t, 则有： ⎩⎨⎧⨯=++++=++++1008.092.085.073.045.03.01005432154321x x x x x x x x x x 请问有多少种配比方案？为什么？哪一种方案最好？假设5种硫酸价格分别为：400，700，1400，1900，2500元/t ，则有：2.生产计划问题如何制定生产计划，使三种产品总利润最大？考虑问题：⎩⎨⎧⨯=+=+1008.092.045.01002121x x x x ⎪⎩⎪⎨⎧=≥⨯=++++=++++++++=5,,2,1,01008.092.085.073.045.03.0100..250019001400700400543215432154321 j x x x x x x x x x x x t s x x x x x MinZ j（1）何为生产计划？（2）总利润如何描述？（3）还要考虑什么因素？（4）有什么需要注意的地方（技巧）？（5）最终得到的数学模型是什么？二、线性规划的定义和数学描述（模型）1．定义：对于求取一组变量xj (j =1,2,......,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。

2.配比问题和生产计划问题的线性规划模型的特点：用一组未知变量表示要求的方案，这组未知变量称为决策变量；存在一定的限制条件，且为线性表达式；有一个目标要求（最大化，当然也可以是最小化），目标表示为未知变量的线性表达式，称之为目标函数； 对决策变量有非负要求。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第一章 线性规划及单纯形法 6
项目的资金数， 解：用 xij 表示第 i 年初投放到 j 项目的资金数， 则可投资的变量表如下
第一章 线性规划及单纯形法
7
由于第三年末收回的本利只包含第三年初项目一的投资、 由于第三年末收回的本利只包含第三年初项目一的投资、 第二年初项目三的投资和第三年初项目四的投资， 第二年初项目三的投资和第三年初项目四的投资，因此目标函 数为： 数为： max z = 1.2 x + 1.6 x + 1.4 x
31 23 34
第一年初投资总额为30万 因此有： 第一年初投资总额为 万，因此有：
x11 + x12 = 30
第二年初的投资额与第一年末收回的本利总额相同： 第二年初的投资额与第一年末收回的本利总额相同：
x21 + x23 = 1.2 x11
第三年初投资额与第二年末收回的本利总额相同： 第三年初投资额与第二年末收回的本利总额相同：
方案 毛坯 2.9 2.1 1.5 合计 剩余料头 方案1 方案2 方案3 方案4 方案5 2 0 1 7.3 0.1 1 2 0 7.1 0.3 1 1 1 6.5 0.9 1 0 3 7.4 0 0 3 0 6.3 1.1 方案6 0 2 2 7.2 0.2 方案7 方案8 0 1 3 6.6 0.8 0 0 4 6.0 1.4
设xj（j=1，2，…，8）分别表示第j种方案下料的原材料根数。 该问题的LP模型如下：
第一章 线性规划及单纯形法 3
（Ⅰ）
（Ⅱ）
思考：如何求解（Ⅰ） 、（Ⅱ）？ （ 、（Ⅱ
第一章 线性规划及单纯形法 4
模型（ 法求解，得到： 模型（Ⅰ）利用大 M 法求解，得到：
x = (10,50, 0,30, 0, 0, 0, 0 )
第一章 线性规划及单纯形法
10
解：用 i = 1 , 2 , 3 分别代表原料A、B、C，用 j = 1, 2, 3 分别 代表甲、乙、丙三种糖果。设 xij 为生产第 j 种糖果使用的第 i 种原料的数量，则问题的数学模型可归结为：
目标函数: 目标函数
第一章 线性规划及单纯形法
11
约束条件: 约束条件
第一章 线性规划及单纯形法
12
作业：P.36
第一章习题： 2
第一章 线性规划及单纯形法
13
补充： 应用LINDO求解 问题 求解LP问题 补充： 应用 求解
• LINDO可以从下面的网址下载： • LINDO由美国芝加哥大学开发，可求解线性规划 和线性整数规划等。其可按自然格式输入模型， 使用方便。 例如: 例如
第一章 线性规划及单纯形法
14
第一章 线性规划及单纯形法
15
例：应用LINDO求解下面LP问题：
第一章 线性规划及单纯形法
16
第一章 线性规划及单纯形法
17
x31 + x34 = 1.2 x21 + 1.5 x12
第一章 线性规划及单纯形法 8
再考虑各项目的投资限额，得到该问题的线性规划模型如下： 再考虑各项目的投资限额，得到该问题的线性规划模型如下：
第一章 线性规划及单纯形法
9
练习： 、C 加工成三种不同牌号的糖果甲、 乙、丙。已知各种牌号糖果中A、B、C 含量，原料成本，各种 原料的每月限制用量，三种牌号糖果的单位加工费及售价如下 表，问该厂每月生产这三种牌号糖果各多少千克，使该厂获利 最大，试建立该问题的线性规划数学模型。
§7 线性规划应用举例
一般情况下，一个经济管理问题满足以下条件时才能 建立线性规划（LP）模型. (1)目标函数能用线性函数的形式，用数值指标反映； (2)该问题有多中可行方案； (3)要求达到的目标是在一定的约束条件下实现的，这些约 束条件能用线性等式或不等式表示。
第一章 线性规划及单纯形法
1
§7 线性规划应用举例
*
T
z = 90
*
此时剩余料头16 m
第一章 线性规划及单纯形法 5
多阶段投资问题
兴安公司有一笔 30 万元的资金，考虑今后三年内用于下列 项目的投资： 1. 三年内的每年年初均可投入，每年获利为投资额的 20%， 其本利可一起用于下一年的投资； 2. 只允许第一年初投入，于第二年年末收回，本利合计为 投资额的150%，但此类投资限额15万以内； 3. 允许于第二年初投入，于第三年末收回，本利合计为投 资额的160%，但限额投资20万元以内； 4. 允许于第三年初投入，年末收回，可获利40%，但限额 为10万元以内； 试为该公司确定一个使第三年末本利总和为最大的投资组 合方案。
• • • • • • 例1.13 生产计划问题（P.27） 例1.14 合理下料问题（P.29） 例1.15 多阶段投资问题（P.30） 例1.16 场地租借问题（P.32） 例1.17 分配问题（P.33） 例1.18 选址问题（P.34）
第一章 线性规划及单纯形法
2
合理下料问题
要制作100套钢筋架子，每套有长2.9m、2.1m和1.5m的钢筋 各一根。已知原料长7.4m，应如何切割，使用原料最节省。 考察如下方案的综合使用： 考察如下方案的综合使用：