第二章 线性规划
主要内容：1、线性规划问题及数学模型 2、线性规划问题的解及其性质
3、图解法
4、单纯形法
5、大M 法和两阶段法
重点与难点：线性规划数学模型的建立：一般形成转化为标准型的方法：单纯形法的求
解步骤。
要 求：理解本章内容，掌握本章重点与难点问题；深刻理解线性规划问题的基本概
念、基本性质，熟练掌握其求解技巧；培养解决实际问题的能力。
§1 线性规划的数学模型及解的性质
一、数学模型（一般形式）
例 1 已知某市有三种不同体系的建筑应予修建，其耗用资源数量及可用的资源限量如
解：设三种体系的建筑面积依次为1x ,2x ,3x 万平方米，则目标函数为
321m a x x x x z ++=
约束条件为 ??
??
???????=≥≤++≤≤++≤++≤++3,2,104005.335.41470021015000180190110200025301211000
1221371053211321321321j x x x x x x x x
x x x x x x j
例2 某工厂要安排生产甲、乙两种产品。已知：
解：设
21,x x 分别为甲、乙两种产品的生产量： 则目标函数为 21127max x x z +=
约束条件为???
???
?=≥≤+≤+≤+2,1,03001032005436049112121j x x x x x x x j
从以上两例可以看出，它们都属于一类优化问题。它们的共同特征：
①每一个问题都有一组决策变量（n x x x 21,）表示某一方案；这组决策变量的值就代表
一个具体方案。一般这些变量的取值是非负的。
②存在一定的约束条件，这些约束条件可以用一组线性等式或不等式来表示。 ③都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示；按问题的不同，要求目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为线性规划的数学模型。其一般形式为：
目标函数 n n x c x c x c z +++= 2211m a x (m i n )
约束条件 ()()()?????
????=≥=≥≤+++=≥≤+++=≥≤+++n
j x b
x a x a x a b x a x a x a b x a x a x a j m
n mn m m n n n n ,,2,1,0,,,2211222221211
1212111
可行解：满足约束条件的一组决策变量，称为可行解。
最优解：使目标函数取得最大（小）值的可行解，称为最优解。 最优值：目标函数的最大（小）值，称为最优值。
二、标准型
（一）问题的标准形式：
n n x c x c x c z +++= 2211m a x
?????
??
??=≥=+++=+++=+++n j x b
x a x a x a b x a x a x a b x a x a x a j m
n mn m m n n n n ,,2,1,02211222221211
1212111
其中 n m m i b i <=≥,,2,10
注意：任何一个一般型都可转化为一个标准型。
（二）标准型的表示方法：
1、和式形式：
∑==n
j j
j x c z 1
max
()()
?????
=≥==∑=n j x m i b x a j
n
j i j ij ,,2,10,,2,11
2、矩阵形式：
CX
z =max
?
?
?≥=0X b AX 其中
[]n c c c C ,,,21 =-------价格系数向量
??
???
???????=
m b b b b 21-------资源向量（限定系数向量） ?????
???????=
mn m m n n a a a a a a a a a A ,,,,,,,,,212222111211 -----------约束条件系数矩阵 []
T
n x x x X ,,,21 =--------决策变量
3、向量形式：
n n x c x c x c z +++= 2211max
?
??≥=++02211j n n x b P x P x P x 其中
??????
????????=j n j j j a a a P ,,2,1 为约束条件系数矩阵A 的第j 列。
（三）一般型化为标准型的方法 1、
CX z =min
引进新的目标函数Z Z -=', 则可化为CX
Z -='max
2、不等式约束
①i n in i i b x a x a a ≤+++ 221
引进新的非负决策变量, 使得1+n x
i n n in i i b x x a x a x a =+++++12211
1+n x 称为松弛变量，在目标函数中，其价格系数为0。
②
i n in i i b x a x a x a ≥+++ 2211
引进新的非负决策变量1+n x ,使得
i n n in i i b x x a x a x a =-++++12211
1+n x 称为剩余变量，在目标函数中，其价格系数为0。
3、若
0
可变为
02211>-=----i n in i i b x a x a x a
4、若某个变量j x 无非负限制，称为自由变量。
令
00
≥''≥''
'-'=j j j j j x x x x x
例3 将下列问题化为标准型
21127max x x z +=
??????
?≥≥≤+≤+≤+0
,0300103200543604921212121x x x x x x x x 解：标准型为
54321000127max x x x x x z ++++=
5
,4,3,2,10300
1032005436049521421321=≥=++=++=++???
????j x x x x x x x x x x j
例4 将下列问题化为标准型
32173min x x x z -+-=
??????
?≥=++-≥+-≤+-无约束
3213213213210,64542732x x x x x x x x x x x x 解：令
z z -=' ，标准型为：
543210073max x x x x x z +++-='
??????
?≥=++-=-+-=++-无约束
35421321532143210,,,64542732x x x x x x x x x x x x x x x x 令
33
3x x x ''-'=
则标准型为：
5433
2100773x z max x x x x x ++''-'+-='
三、线性规划问题的解
标准型
CX
z =max
??
?≥=0
X b
AX ??
????
?≥'''=''-'++-=-''-'+-=+''-'+-0,,,,,64454273325433
21312153321433
21x x x x x x x x x x x x x x x x x x x x
]
,,,[212
1
2222111211n n
m mn m m n n P P P a a a a a a a a a A =?
?
?
???
??????=?
记
n P P P
2
1
秩
()n m m
A rank <=
im i i P P P ,,,21 []im i i P P P B ,,,21 =
1、基阵：若列向量是线性无关的，则称为LP 问题的一个基阵。基矩阵中每个列向量称为基向量。
由非基向量组成的矩阵称为非基矩阵，记为
()m n m N -?
例如：
5
31001030105400149??????
?????=A
取[]??????????==100010001,,5431P P P B 线性无关，则??
??
?
?????=10354491N []??????????==003104019,,4312P P P B 线性无关，则??
??
?
?????=11005042N 2、基变量：基矩阵中各列向量对应的变量称为基变量，记为[]T
im i i B x x x X ,,,21 =。
如[]5431,,P P P B =, 则基变量为543,,x x x 。
对应于非基向量的变量称为非基变量，记为 []
T
in m i n x x X ,,)1( += 3、基本解：设基矩阵为[]m 21P ,,, P P B =，则非基矩阵[]n m P P N ,,1 +=
∴[]N B A = ??
????=N B X X X
那么，约束方程 []b X X N B N B =??
?
??? 即b NX BX N B =+ --------有无穷解 令0=N X 则b B X b BX B B 1-==
那么，约束方程组的解 ??
????=-01b B X ，将其称为LP 问题的基本解。
注意：基本解不一定是可行解，若01
≥-b B ,则称??
?
???=-01b B X 为LP 问题的基本可行解，
对应于基本可行解的基矩阵，称为可行基。
4、最优解：对应于某一可行基，使目标函数获得最优值的基本可行解，称为最优解。最优解所对应的基矩阵称为最优基。
举例说明： 54321000127max x x x x x z ++++=
???????≥=++=++=++0
,,,,30010320054360495432152142
13
21x x x x x x x x x x x x x x
约束矩阵
????
?
?????=1001030105400149A
若取基矩阵
[]????
?
?????==100010001,,5431P P P B
则非基矩阵??
??
??????=10354491N
基变量????
?
?????=5431
x x x X B ,非基变量?
?????=211x x X N
??
??
?
?????===-3002003601
1b Ib b B
∴基本解为
()
T
X 300,200,360,0,0= 是基本可行解
若取基矩阵()??
??
?
?????==1030540491,,2132P P P B 则
????
?
?????=1001002N
()
T
B x x x X 213,,2=
??????=542
x x X N
??
????????=-2420841
2b B
()
T
X 0,0,84,24,20=∴ -----基本可行解
注意：基本可行解与可行域的顶点坐标是一一对应的。
§2 图解法---主要解决二维线性规划问题
一、按约束条件，绘出解的可行域图形
21127max x x z +=
???
???
?≥≤+≤+≤+0,300103200543604921212121x x x x x x x x
可行域：可行解的全体称为可行域。
将等值线
1212712Z
x x +-=沿法线方向向上平移至（20，24）点时截距最大，那么
最优解为（20，24）T 。
二、解的情况
最优解有以下几种情况：
（1）有唯一的最优解。
（2）有多个最优解。如上例中，若
2154max x x z +=，就有无穷多解。
1
1
（3）有无界解：若有可行解，但无有限最优解，则称其为有无界解(这种情况在约束条件考虑不周全时出现)。 如： 21m a x x x z +=
???
??≥≥≤-≤+-0
,024
221
2121x x x x x x
(4)无可行解（约束条件有矛盾） 如：212max x x z +=
???
??≥≥-≤+0,2212
12121x
x x x x x
结论：
①约束集合一定是凸条边形（二维）；
②若有最优解，则一定可在多边形顶点获得。
§3单纯形法
单纯形法的基本思路是：根据问题的标准，从可行域中某个基本可行解（一个顶点）开始，转换到另一个基本可行解（顶点）；并且使目标函数达到最大值时，问题就得到了最优解。即
2
2=1
初始顶点0X (可行域一顶点)????→?寻找较好的顶点1X ????→?寻找更好的顶点2X ?→?…?→?)(最优解＊X
0Z ≤ 1Z ≤ 2X ≤ ≤ ＊Z
一、单纯形法的求解步骤
（1）寻找初始可行基0B ,并计算初始基本可行解；??
?
???=????????=-010000b B X X X N B
（2）检验基本可行解是否最优；
（3）寻找更好的可得基； （4）重复（2），（3）。
1、初始可行基的确定
i)若A 中含有m 阶单位矩阵I ,则取I B =0。此时，0100≥==-b b B X B
0B ∴是可行基
ii)若A 中不含有m 阶单位矩阵，就采用人造基的方法。即增加人工变量把原问题化为含有I 的等价问题。（下一节重点讲）
例：???
??≥=++=+020325833
2132121x x x x x x x x
因为系数数阵A 中不含有单位矩阵，需增加人工变量
5
4,x x 化为
??
?
??=≥=+++=++5,,2,10203258
353
21421 j x x x x x x x x j 则
??
?
???=1032501013A
()??
?
???==1001,540P P B 注意：松驰变量、剩余变量的价值系数取为0，而人工变量的价值系数取值为大M 。
2、检验
基本可行解
??
????=-01b B X
对应的目标函数值???
?
????==-01b B C CX Z
[]b
B C b B C C B N B 11
0--=?
???=
对任意可行解??????=N B X X X 变化b AX =为 []b X X N B N B =??
?
???
即b NX BX N B =+
N B N B NX B b B X NX b BX 11---=?-= 将其代入目标函数得：
[]N N B B N B N B X C X C X X C C CX Z +=???
???==
()
N N N B X C NX B b B C +-=--11 ()
N B N B X N B C C b B C 11---+=
0≥N X ∴当01≤--N B C C B N 时，Z 的最大值是b B C B 1-
即??
?
???=-01b B X 为最优解。
这里，我们称每个j B j j P B C c 1--=σ为检验数。
当I B =时，基本可行解???
???=0b X
检验数∑=--=-=m
i ij i j j B j j a c C P B C c 11
σ
第i 个基变量的价格系数 第j 个非基变量的价格系数
如果???
???=0b X 为最优解，则最优值为b C X B =*
判断定理：（对标准型maxZ 来讲）
（1）若所有
0≤j
σ，则??
?
???=-01b B X 为最优解。
（2）若所有
0≤j σ,且有某个0=k σ，则LP 问题有无穷多个最优解。
（3）若有某个
0>k
σ，则??
?
???=-01b B X 不是最优解。
（4）当
I
B =时，若有一个
0>k σ，且对一切m i ,,2,1 =都有
0≤ik a ,则有无界解(或无最优解)。
3、基变换：确定新的基矩阵的过程
（1）换入变量的确定 选择
>j σ中的最大者所对应的变量
k
x 作为换入变量，即
{}
k j j σσσ=>0max
（2）换出变量的确定：用最小比值规则（θ规则）
设
()()
()
()()
l
k l i
k i
k i
P B b B P B P B b B 1
1
1
110min -----=??????>=θ
则取
l x 为换出变量
当
I
B =时，
lk
l
ik ik i a b a a b =??????>=0min θ
则取
l x 为换出变量，lk a 称为主元素
（3）新基矩阵的确定
k
n
l l x x x x x x
11
2
1
+-
?????
?
?
?????=+-+-+-mk
mn ml ml m m k n l l k n l l a a a a a a a a a a a a a a a a a a B 112122121222211111111211如：
54321000127max x x x x x z ++++=
???
????=≥=+=++=++5,,2,1,030010320054360495214213
21 j x x x x x x x x x x j 解：????
??????=1001030105400149A
取初始基矩阵()??
??
?
?????==100010001,,5430P P P B
那么
()
T
B x x x X 543,,0=
()
T
N x x X 21,0=
基可行解
()T
b b B X 300,200,360
,0,0001=??
????=??????=-
检验数：
∑=-=m i ij i j j a c c 1
σ ()70731521411311=-=++-=a c a c a c c σ
()1201232522412322=-=++-=a c a c a c c σ
,21>σσ
X
∴不是最优解，换入变量为
()122σσ> x
lk
l
ik ik ik a b a a b =
??????>=0min θ
323
1030010300,5200,4
360min a b ==??? ??= ∴
换出变量为
5x （基变量中的第3个变量），主元素为32a
增
广
矩
阵
变
换
：
????
??????3001001032000105436000149??
??
?
????????→?301.00013.0200010543600014910
3行除第
24
3301
.00013.0505.01005.22404.00108.7x x x ??????????--?→?
∴
新的基矩阵()
2431,100010001P P P B =????
??????=
新基可行解()
T
X 0,50,240,30,0=
检验数：
()31221411311a c a c a c c ++-=σ
4.33.0127=?-=
()35225415355a c a c a c c ++-=σ
2.11.0120-=?-=
X
∴不是最优解。
二、单纯形表：（将上述过程列成表格,便于理解）
对每一个可行基，作一个单纯形表，包括①基可行解②检验数j σ③θ和主元素。
B X 列中填入基变量，这里是;,,,21m x x x
B C 列中填入基变量的价值系数，与基变量一一对应，这里是;,,,21m C C C
b 列中填入约束方程组右端的常数；
线性规划模型及其举例 摘要：在日常生活中，我们常常对一个问题有诸多解决办法，如何寻找最优方案，成为关键，本文提出了线性规划数学模型及其举例，在一定约束条件下寻求最优解的过程，目的是想说明线性规划模型在生产中的巨大应用。 关键词：资源规划；约束条件；优化模型；最优解 在工农业生产与经营过程中，人们总想用有限的资源投入，获得尽可能多的使用价值或经济利益。如：当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多，利润最大）。 一.背景介绍 如果产出量与投入量存在（或近似存在）比例关系，则可以写出投入产品的线性函数式： 1()n i ij j j f x a x ==∑，1,2,,,1i m m =+ (1) 若将（1）式中第（1m +）个线性方程作为待求的目标函数，其余m 个线性方程作为资源投入的限制条件（或约束条件），则（1）式变为： OPT. 1()n j j j f x c x ==∑ ST. 1 n ij j j a x =∑> ( =, < )i b , 1,2,,i m = (2) 0,j x ≥ 1,2,,j n =… （2）式特点是有n 个待求的变量j x （1,2,,j n =…）；有1个待求的线性目标函数()f x ，有m 个线性约束等式或不等式，其中i b （1,2,,i m =…）为有限的资源投入常量。将客观实际问题经过系统分析后，构建线性规划模型，有决策变量，目标函数和约束条件等构成。 1．决策变量（Decision Variable,DV ）在约束条件范围内变化且能影响（或限定）目标函数大小的变量。决策变量表示一种活动，变量的一组数据代表一个解决方案，通常这些变量取非负值。 2．约束条件（Subject To,ST ）在资源有限与竞争激烈的环境中进行有目的性的一切活动，都
线性规划 1.简介： 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源. 线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.规划问题。一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。 (x)都是线性函数，则该模型称为在优化模型中，如果目标函数f(x)和约束条件中的g i 线性规划。 2.线性规划的3个基本要素 （1）决策变量 （2）目标函数f(x) (x)≤0称为约束条件） （3）约束条件（g i 3.建立线性规划的模型 （1）找出待定的未知变量（决策变量），并用袋鼠符号表示他们。 （2）找出问题中所有的限制或者约束，写出未知变量的线性方程或线性不等式。
（3）找到模型的目标或判据，写成决策变量的线性函数，以便求出其最大值或最小值。以下题为例，来了解一下如何将线性规划用与实际的解题与生活中。 生产计划问题 某工厂生产甲乙两种产品，每单位产品消耗和获得的利润如表 试拟订生产计划，使该厂获得利润最大 解答：根据解题的三个基本步骤 （1）找出未知变量，用符号表示： 设甲乙两种产品的生产量分别为x 1与x 2 吨，利润为z万元。 （2）确定约束条件： 在这道题目当中约束条件都分别为：钢材，电力，工作日以及生产量不能为负的限制 钢材：9x 1+5 x 2 ≤360， 电力：4x 1+5 x 2 ≤200， 工作日：3x 1+10 x 2 ≤300， x 1≥0 ，x 2 ≥0， （3）确定目标函数： Z=7x 1+12 x 2
11（2），12,14,18 习题 2-1 判断下列说法是否正确： （1） 任何线性规划问题存在并具有惟一的对偶问题； T （2） 对偶问题的对偶问题一定是原问题；T （3） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之， 当对偶问题无可行解时，其原问题具有无界解；F （4） 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优 解； （5） 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出 现原问题与对偶问题均为非可行解的情况； （6） 应用对偶单纯形法计算时，若单纯形表中某一基变量x i <0，又x i 所在行的元素全 部大于或等于零，则可以判断其对偶问题具有无界解。 （7） 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加 5个单位时，相应的目标函数值将增大5k ； （8） 已知y i 为线性规划的对偶问题的最优解，若y i >0，说明在最优生产计划中第 i 种资源已经完全耗尽；若y i =0，说明在最优生产计划中的第i 种资源一定有剩余。 2-2将下述线性规划问题化成标准形式。 ????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43 214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z 2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基 可行解对应图解法中可行()?????≥≤≤-+-=++-+-=无约束 321 3213213 21,0,06 24 .322min 2x x x x x x x x x st x x x z 域的哪一顶点。 ()??? ??≥≤+≤++=0,8259 43.510max 12 1212121x x x x x x st x x z ()??? ??≥≤+≤++=0,242615 53.2max 22 121212 1x x x x x x st x x z 2-4已知线性规划问题，写出其对偶问题： 5 43212520202410max x x x x x z ++++=
-1- 第一章线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济 效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947 年G. B. Dantzig 提出 求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性 规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000 元与3000 元。 生产甲机床需用A、B机器加工，加工时间分别为每台2 小时和1 小时；生产乙机床 需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时 数分别为A 机器10 小时、B 机器8 小时和C 机器7 小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1 x 台甲机床和2 x 乙机床时总利润最大，则1 2 x , x 应满足 （目标函数）1 2 max z = 4x + 3x (1) s.t.（约束条件） ?? ? ?? ? ? ≥ ≤ + ≤ + ≤ , 0 7 8 2 10 1 2 2 1 2 1 2 x x x x x x x （2） 这里变量1 2 x , x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。由于上面的目标函数及约束条件均为线性
习题一 1.1 用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。 (1) min z ＝6x1＋4x2(2) max z ＝4x1＋8x2 st. 2x1＋x2≥1 st. 2x1＋2x2≤10 3x1＋4x2≥1.5 －x1＋x2≥8 x1, x2≥0 x1, x2≥0 (3) max z ＝x1＋x2(4) max z ＝3x1－2x2 st. 8x1＋6x2≥24 st. x1＋x2≤1 4x1＋6x2≥－12 2x1＋2x2≥4 2x2≥4 x1, x2≥0 x1, x2≥0 (5) max z ＝3x1＋9x2(6) max z ＝3x1＋4x2 st. x1＋3x2≤22 st. －x1＋2x2≤8 －x1＋x2≤4 x1＋2x2≤12 x2≤6 2x1＋x2≤16 2x1－5x2≤0 x1, x2≥0 x1, x2≥0 1.2. 在下列线性规划问题中，找出所有基本解，指出哪些是基本可行解并分别代入目标函数，比较找出最优解。 (1) max z ＝3x1＋5x2(2) min z ＝4x1＋12x2＋18x3 st. x1＋x3＝4 st. x1＋3x3－x4＝3 2x2＋x4＝12 2x2＋2x3－x5＝5 3x1＋2x2＋x5＝18 x j≥0 （j＝1, (5) x j≥0 （j＝1, (5) 1.3. 分别用图解法和单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。 (1) max z ＝10x1＋5x2 st. 3x1＋4x2≤9 5x1＋2x2≤8 x1, x2≥0 (2) max z ＝100x1＋200x2 st. x1＋x2≤500 x1≤200 2x1＋6x2≤1200 x1, x2≥0 ９
习题七7.1计算如图所示的从A 到E 的最短路线及其长度（单位：km ）： （1） 用逆推解法；2用标号法。 7.2 用动态规划方法求解下列问题 （1） max z ＝x 12x 2 x 33 x 1＋x 2＋x 3 ≤6 x j ≥0 （j ＝1,2,3） （2）min z ＝ 3x 12＋4x 22 ＋x 32 x 1x 2 x 3 ≥ 9 x j ≥0 （j ＝1,2,3） 7.3 利用动态规划方法证明平均值不等式： n n n x x x n x x x 12121)()( ≥+++ 设x i ≥0，i ＝1，2，…，n 。 7.4 考虑一个有m 个产地和n 个销地的运输问题。设a i （i ＝1，2，…，m ）为产地i 可发运的物资数，b j （j ＝1，2，…，n ）为销地j 所需要的物资数。又从产地i 到销地j 发运x ij 单位物资所需的费用为h ij （x ij ），试将此问题建立动态规划的模型。 7.5 某公司在今后三年的每一年的开头将资金投入A 或B 项工程，年末的回收及其概率如下表所示。每年至多做一项投资，每次只能投入1000万元。求出三年后所拥有的期望金额达到最大的投资方案。 投 资 回 收 概 率 A 0 0.4 2000 0.6 B 1000 0.9 2000 0.1 7.6 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。现公司有资金5千万元，问应如何分配投资使公司的总收益最大?
7.7 某厂准备连续3个月生产A种产品，每月初开始生产。A的生产成本费用为x2，其中x是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1＝100，d2＝110，d3＝120。现设开始时第一个月月初存货s0＝0，第三个月的月末存货s3＝0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。 7.8 设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如下表所示。 货物代号重量（吨）容积（立方米）价值（千元） 1 2 2 3 2 3 2 4 3 4 2 5 4 5 3 6 若该卡车的最大载重为15吨，最大允许装载容积为10立方米，在许可的条件下，每车装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。 7.9 某警卫部门有12支巡逻队负责4个仓库的巡逻。按规定对每个仓库可分别派2－4支队伍巡逻。由于所派队伍数量上的差别，各仓库一年内预期发生事故的次数如下表所示。试应用动态规划的方法确定派往各仓库的巡逻队数，使预期事故的总次数为最少。 巡逻队数预期事故次数仓库 1 2 3 4 2 18 38 14 34 3 16 36 12 31 4 12 30 11 25 7.10 （生产计划问题）根据合同，某厂明年每个季度末应向销售公司提供产品，有关信息见下表。若产品过多，季末有积压，则一个季度每积压一吨产品需支付存贮费0.2万元。现需找出明年的最优生产方案，使该厂能在完成合同的情况下使全年的生产费用最低。 季度j生产能力a j（吨）生产成本d j（万元/吨）需求量b j（吨） 1 30 15.6 20 2 40 14.0 25 3 25 15.3 30 4 10 14.8 15 （1）请建立此问题的线性规划模型。（提示：设第j季度工厂生产产品x j吨，第j季度初存贮的产品为y j吨，显然y1＝0）（2）请建立此问题的动态规划模型。（均不用求解）
LP （Linear Programming）
Alex 有一个家庭农场。除了农场上的农作物以外，他还饲养了一些猪拿到市场上出售，猪可获得的饲料及其所含成分如下表：Alex如何喂养猪更好？ 成分/每公斤 玉米槽料苜蓿每日最小需求量碳水化合物 蛋白质 维他命 成本(美分)903010842080207240606060200180150 问题1：科学养猪线性规划建模（猪饲料的配方）饲养成本最小
--- 每天玉米、槽料、苜蓿各喂多少公斤？ --- 必须满足要求12--- 追求成本最低 Min. 84x 1+ 72x 2+ 60x 3 3x 1x 2x 3 知识点 建模三要素 决策变量约 束目标 90x 1+ 20x 2+ 40x 3 ≥ 20030x 1+ 80x 2+ 60x 3 ≥ 18010x 1+ 20x 2+ 60x 3 ≥ 150 x i ≥0 , i =1，2，3 成分/每公 斤 玉米槽料苜蓿每日最小需求量碳水化合物 蛋白质 维他命 成本(美分)903010842080207240606060200180150
s.t. 90x 1+ 20x 2+ 40x 3 ≥ 200 30x 1 + 80x 2+ 60x 3 ≥ 180 10x 1+ 20x 2+ 60x 3 ≥ 150 x i ≥0 , i =1,2,3 Min . 84x 1+ 72x 2+ 60x 3 目标函数约束函数符号中必含等号符号的右侧为常数线性--变量均为1次方 Max. 或 Min.线性--所有变量均为1次方常规约束：变量非负！知识点 模型表示
？线性规划模型能求解出来吗？ 能！--- 万能的单纯形法 结合软件 QSB应用
第三章 线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用B A 、机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用C B A 、、三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A 机器10小时、B 机器8小时和C 机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1x 台甲机床和2x 乙机床时总利润最大，则21,x x 应满足 （目标函数）2134max x x z += (1) s.t.（约束条件）???????≥≤≤+≤+0 ,781022122 121x x x x x x x （2） 这里变量21,x x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式 是问题的约束条件，记为s.t.(即subject to)。上述即为一规划问题数学模型的三个要素。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。 总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。 在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选取适当的决策变量，是我们建立有效模型的关键之一。 1.2 线性规划问题的解的概念 一般线性规划问题的标准型为 ∑==n j j j x c z 1 min (3) ∑==≤n j i j ij m i b x a 1 ,,2,1 s.t. (4) 可行解 满足约束条件（4）的解),,,(21n x x x x =，称为线性规划问题的可行解，而使目标函数（3）达到最小值的可行解叫最优解。 可行域 所有可行解构成的集合称为问题的可行域，记为R 。 1.3 线性规划的图解法
第二章 线性规划的对偶理论与灵敏度分析习题 1. 写出下列线性规划问题的对偶问题。 (1)????? ? ?≥=++≤++≥++++=无约束 3213213213213 21,0,5343 32243422min x x x x x x x x x x x x x x x z (2) ????? ? ?≤≥≤++≥-+-=++++=0 ,0,8374355 22365max 3213213213213 21x x x x x x x x x x x x x x x z 无约束 (3)?? ??? ??? ???==≥=====∑∑∑∑====) ,,1;,,1(0) ,,1(),,1(min 1 111n j m i x n j b x m i a x x c z ij m i j ij n j i ij m i ij n j ij (4)???????????=≥++==<=<=∑∑∑===),,,,1(0),,2,1() ,,1(min 1 211111n n j x m m m i b x a m m i b x a x c z j n j i j ij n j i j ij n j j j 无约束 2. 判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； (2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解； ( 3)在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值； (4)任何线性规划问题具有唯一的对偶问题。 3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。
第三章线性规划对偶理论与灵敏度分析习题 一、思考题 1．对偶问题和对偶变量的经济意义是什么？ 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？ 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？ 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？ 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么？ 7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+k n σ（标准形为 求最小值），其经济意义是什么？ 8．将i j j i b c a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量0>* i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量0=* i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于i j j i b c a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量0第三章 非线性规划
第三章 非线性规划 §1 非线性规划 1.1 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。 下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念。 例1 （投资决策问题）某企业有n 个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金A 元，投资于第),,1(n i i 个项目需花资金i a 元，并预计可收益i b 元。试选择最佳投资方案。 解 设投资决策变量为 个项目 决定不投资第，个项目 决定投资第i i x i 0, 1，n i ,,1 ， 则投资总额为 n i i i x a 1 ，投资总收益为 n i i i x b 1 。因为该公司至少要对一个项目投资，并 且总的投资金额不能超过总资金A ，故有限制条件 n i i i A x a 1 另外，由于),,1(n i x i 只取值0或1，所以还有 .,,1,0)1(n i x x i i 最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为： n i i i n i i i x a x b Q 11max s.t. n i i i A x a 1 .,,1,0)1(n i x x i i 上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中目标函数或约束条件中至少有一个非线性函数，这类问题称之为非线性规划问题，简记为（NP ）。可概括为一般形式 )(min x f q j x h j ,,1, 0)(s.t. (NP) p i x g i ,,1, 0)(
线性规划建模问题 1、招聘问题 新机电器始创于1989年，是高低压电器元件、成套装置附件、高压电控电器配套件的专业生产制造商，是国家的高、低压电器开关行业协会理事单位，在业内享有很高声誉。新机电器已发展成为拥有八家子公司，在永嘉、温州、厦门、青田、陕西均有设厂。 工种：普车车工、数控车工、装配工、检验员、计算机绘图员各1名。 要求：具有良好的工作心态，吃苦耐劳，虚心好学，积极进取，有团队协作精神以及良好的沟通能力。 面试须知： 岗位安排方案完成后，新机为前往厂内实习的人员，提供了往返车费，总共是46元。获悉该厂又分新、旧两个厂区，要求每区至少去一名同学，且去旧厂区面试的同学比新厂区至少多一名。 已知前往新厂区每位同学的往返车费是4元，该厂区为每人提供的考虑岗位数为5个；旧厂区每位同学的往返车费是6元，而为每人可供考虑的岗位数为3个。 建模分析： 分析：以两组为基本单位，共同出谋划策，怎样合理地安排分别前往新、旧两区的人数，并能使面试时可选择的空缺岗位数达到最多，这样每人实习录用的机会就增多。请问岗位最多是多少？ 假设： 问题解答： 解：设前往新、旧厂区的 人数分别为y x ,，设岗位数为z ，则根据题意得， y x z 35+=， 且 1,1 4646 x y y x x y ≥≥?? ≥+??+≤? 在坐标系中将各不等式区域表示如下： 我们发现当5,4==y x 时，不等式所夹的区域最大，因此，前往新、旧厂区的人数 y=1
分别为4、5时，可供选择的岗位数最大，为35个。 2、已知高翔工业区内的新机厂区并不是真正的加工厂，实际上只完成装配工作，所需配件由青田与陕西两个厂区供应，而这两个厂生产出的零部件毛利价格不同。 拿“JN15-12-31.5型户内高压接地开关”为例，扭簧为其中的配件之一，而青田与陕西产的扭簧可获利润不同，毛利价格现列表如下： 要求：每日由青田与陕西厂区供应的货品总和需保持在500—1000件之间，而且青田厂区的产品数至少要比陕西的多100件，下面请你给出一项合理的方案，将货源如何进行调配，才能使我厂每日的毛利最多？最多为多少？方案的好坏，以及策划的速度快慢都直接影响到你在实习期间以及今后工作岗位的调动及职务与薪酬。 问题解决： 解：设每日青田与陕西厂区所提供的货品数分别为y x,，设每日扭簧的毛利为z元，则根 据题意得：y x z20 15+ =，且 0,0 5001000 100 x y x y x y ≥≥ ? ? ≤+≤ ? ?≥+ ? ，在坐标系中将各不等式的区域表示如 下： 最大 y=0 x=0 因此，当450 , 550= =y x时，也就是青田供货550件，陕西供货450件时，毛利最 大，为17250元。
ERP的核心线性规划模型 1982年，以美国布鲁克海文国家试验室与德国玉立希核研究中心牵头的多国能源系统协作项目大功告成，它为西方国家制定能源政策、化解由于石油价格暴涨所产生的能源危机做出了不可估量的奉献。该项目的目的是评判能源新工艺在以后国家级能源系统中的作用。毫无疑咨询，如此的评判需要建立一个通用的运算机化的模型。经认真考虑和多方比较，他们一致选择了多周期的线性规划模型。 15年过去了，我们对线性规划在治理、决策及ERP中作用的认识仍旧不够。从1996年到今年8月，《运算机世界》所发表的30多篇有关M RP或ERP的文章中，除两篇文章各有一处提到"优化"一词外，其余皆未提及。至于线性规划，则全未触及，看起来毫无关系。 优化：企业效益的源泉 从60年代初期的MRP到MRPⅡ再到90年代初的ERP，前后整整经历了30年的时刻，为时不短。就MRP与ERP的字面看，其差不仅仅是优化的资源种类由少变多、由局部变全部罢了。但有一个字没有变，那确实是"PLANNING"。什么是PLANNING？按字面讲是"做打算"、"做规划"或"打算"、"规划"。对企业而言，做打算并不是什么困难的情况，困难的是做一个好的，经得起推敲与论证同时又能给企业带来较大效益的打算。有鉴于此，我们宁可将"PLANNING"译为"做规划"或"规划"，因为由此才会联系到线性规划、非线性规划及动态规划，才会联系到目标与优化。事实上，MRP到MRPⅡ再到ERP的进展历程正是企业的线性规划模型与优化的范畴由小到大、由局部到全局的过程。企业的效益依靠于资源配置的优化，即依靠于线性规划模型的优化。优化的范畴越大，成效也就越好。如若不然，我们什么缘故还要将MRP扩大到MRPⅡ再扩大到ERP呢？ 清仓查库、摸清资源、建立良好的会计系统与审计系统、机构重组、鼓舞机制及企业文化等亦可提升企业的效益。但这与ERP及模型的优化不是一个概念。前者是体会、艺术，是事务处理；而后者是揭示企业运作规律、猎取更大效益的科学与技术。随着时刻的推移，这类科技在企业治理中的
第二章 线性规划 本章内容重点： 线性规划模型 解的主要概念 线性规划应用——建模 一. 线性规划模型 引例： （1）用一块边长为a 的正方形铁皮做一容器，应如何裁剪，使做成的容器的容积最大？ （2）某企业计划生产甲、乙两种产品。这两种产品都要分别在A 、B 、C 、D 四种不同设备上加工。按工艺资料规定，生产每件产品甲需占用设备分别为2、1、4、0小时，生产每件产品乙需占用设备分别为2、2、0、4小时。已知各设备计划期内用于生产这两种产品的能力分别为12、8、16、12小时，又已知每生产一件产品甲企业能获得2元利润，每生产一件产品乙企业能获得3元利润，问该企业应如何安排生产，使总的利润收入最大？ 讨论：（1）可用微积分的方法解决； （2）复杂一些 目标： 最大 2 132x x z +=
例2.1:某工厂拥有A 、B 、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 问题：工厂应如何安排生产可获得最大的总利润？ 解：设变量xi 为第i 种（甲、乙）产品的生产件数（i ＝1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A ，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1 + 2 x2 ≤ 65； 对设备B ，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1 + x2 ≤ 40； 对设备C ，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x 2 ≤75 ；另外，产品数不可能为负，即 x 1 ,x 2 ≥0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z 为相应的生产计划可以获得的总利润：z =1500x 1+2500x 2 。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模 ????? ????≥≤≤≤+≤+0 ,1241648212222121 2121x x x x x x x x