数学建模线性规划.docx

-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小时，问该厂应生产甲、乙机床各
几台，才干使总利润最大？
上述问题的数学模型：设该厂生产1x台甲机床和2x乙机床时总利润最大，则12x,x
应满足
（目的函数）12maxz=4x+3x(1)
s.t.（约束条件）
⎪⎪
⎩
⎪⎪
⎨
⎧
≥
≤
+≤
+≤
,0
7
8
210
12
2
12
12
xx
x
xx
xx
（2）
这里变量12x,x称之为决策变量，（1）式被称为问题的目的函数，（2）中的几个不等式
是问题的约束条件，记为s.t.(即subjectto)。由于上面的目的函数及约束条件均为线性
函数，故被称为线性规划问题。
总之，线性规划问题是在一组线性约束条件的限制下，求一线性目的函数最大或最
小的问题。
在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往
也是困难的一步，模型建立得是否恰当，直接影响到求解。而选适当的决策变量，是我
们建立有效模型的关键之一。
1.2线性规划的Matlab标准形式
线性规划的目的函数可以是求最大值，也可以是求最小值，约束条件的不等号可以
是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab中规定线性
规划的标准形式为
cx
x
minT
s.t.
⎪⎩
⎪⎨
⎧
≤≤
⋅=
≤
lbxub
Aeqxbeq
Axb
其中c和x为n维列向量，A、Aeq为适当维数的矩阵，b、beq为适当维数的列向
量。
-2-
例如线性规划
cxAxb
x
maxTs.t.≥
的Matlab标准型为
cxAxb
x
min−Ts.t.−≤−
1.3线性规划问题的解的概念
一般线性规划问题的（数学）标准型为
Σ=
=
n
j
jjzcx
1
max(3)
s.t.
⎪⎩
⎪⎨
⎧
≥=
==Σ=
xjn
axbim
j
n
j
ijji
01,2,,
1,2,,
1
L
L
(4)
可行解满足约束条件（4）的解(,,,)12nx=xxLx，称为线性规划问题的可行解，
而使目的函数（3）达成最大值的可行解叫最优解。
可行域所有可行解构成的集合称为问题的可行域，记为R。
1.4线性规划的图解法
0246810
0
1
2
3
4
5
6
7
8
9
10
x2=7
2x1+x2=10
x1+x2=8
z=12
(2,6)
图1线性规划的图解示意图
图解法简朴直观，有助于了解线性规划问题求解的基本原理。我们先应用图解法来
求解例1。对于每一固定的值z，使目的函数值等于z的点构成的直线称为目的函数等
位线，当z变动时，我们得到一族平行直线。对于例1，显然等位线越趋于右上方，其
上的点具有越大的目的函数值。不难看出，本例的最优解为x*=(2,6)T，最优目的值
z*=26。
从上面的图解过程可以看出并不难证明以下断言：
（1）可行域R也许会出现多种情况。R也许是空集也也许是非空集合，当R非空
时，它必然是若干个半平面的交集（除非碰到空间维数的退化）。R既也许是有界区域，
也也许是无界区域。
（2）在R非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其
目的函数值无界）。
-3-
（3）若线性规划存在有限最优解，则必可找到具有最优目的函数值的可行域R的
“顶点”。
上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的n维
空间中，满足一线性等式Σ=
=
n
i
iiaxb
1
的点集被称为一个超平面，而满足一线性不等式
Σ=
≤
n
i
iiaxb
1
（或Σ=
≥
n
i
iiaxb
1
）的点集被称为一个半空间（其中(,,)1naLa为一n维行
向量，b为一实数）。若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面
体。易见，线性规划的可行域必为多胞形（为统一起见，空集Φ也被视为多胞形）。
在一般n维空间中，要直接得出多胞形“顶点”概念尚有一些困难。二维空间中的顶点
可以当作为边界直线的交点，但这一几何概念的推广在一般n维空间中的几何意义并不
十分直观。为此，我们将采用另一途径来定义它。
定义1称n维空间中的区域R为一凸集，若∀x1,x2∈R及∀λ∈(0,1)，有
λx1+(1−λ)x2∈R。
定义2设R为n维空间中的一个凸集，R中的点x被称为R的一个极点，若不
存在x1、x2∈R及λ∈(0,1)，使得x=λx1+(1−λ)x2。
定义1说明凸集中任意两点的连线必在此凸集中；而定义2说明，若x是凸集R
的一个极点，则x不能位于R中任意两点的连线上。不难证明，多胞形必为凸集。同
样也不难证明，二维空间中可行域R的顶点均为R的极点（R也没有其它的极点）。
1.5求解线性规划的Matlab解法
单纯形法是求解线性规划问题的最常用、最有效的算法之一。这里我们就不介绍
单纯形法，有爱好的读者可以参看其它线性规划书籍。下面我们介绍线性规划的Matlab
解法。
Matlab中线性规划的标准型为
cx
x
minT
s.t.
⎪⎩
⎪⎨
⎧
≤≤
⋅=
≤
lbxub
Aeqxbeq
Axb
基本函数形式为linprog(c,A,b)，它的返回值是向量x的值。尚有其它的一些函数调用形
式（在Matlab指令窗运营helplinprog可以看到所有的函数调用形式），如：
[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)
这里fval返回目的函数的值，LB和UB分别是变量x的下界和上界，0x是x的初始值，
OPTIONS是控制参数。
例2求解下列线性规划问题
123maxz=2x+3x−5x
s.t.7123x+x+x=
2510123x−x+x≥
312123x+x+x≤
,,0123xxx≥
-4-
解（i）编写M文献
c=[2;3;-5];
a=[-2,5,-1;1,3,1];b=[-10;12];
aeq=[1,1,1];
beq=7;
x=linprog(-c,a,b,aeq,beq,zeros(3,1))
value=c'*x
（ii）将M文献存盘，并命名为example1.m。
（iii）在Matlab指令窗运营example1即可得所求结果。
例3求解线性规划问题
123minz=2x+3x+x
⎪⎩
⎪⎨
⎧
≥
+≥
++≥
,,0
326
428
123
12
123
xxx
xx
xxx
解编写Matlab程序如下：
c=[2;3;1];
a=[1,4,2;3,2,0];
b=[8;6];
[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))
1.6可以转化为线性规划的问题
很多看起来不是线性规划的问题也可以通过变换变成线性规划的问题来解决。如：
例4规划问题为
Axb
xxxn
≤
+++
s.t.
min||||||12L
其中T
nx[xx]=1L，A和b为相应维数的矩阵和向量。
要把上面的问题变换成线性规划问题，只要注意到事实：对任意的ix，存在
,>0iiuv满足
iiix=u−v，iii|x|=u+v
事实上，我们只要取
2
||ii
i
uxx
+
=，
2
||ii
i
vxx
−
=就可以满足上面的条件。
这样，记T
nu[uu]=1L，T
nv[vv]=1L，从而我们可以把上面的问题
变成
Σ=
+
n
i
iiuv
1
min()
⎩⎨⎧
≥
−≤
,0
()
s.t.
uv
Auvb
例5min{max||}xyiii
ε
其中iiiε=x−y。
对于这个问题，假如我们取max||0yii
x=ε，这样，上面的问题就变换成
-5-
0minx
1100s.t.xyx,,xyxnn−≤L−≤
此即我们通常的线性规划问题。
§2运送问题(产销平衡)
例6某商品有m个产地、n个销地，各产地的产量分别为ma,,a1L，各销地的
需求量分别为nb,,b1L。若该商品由i产地运到j销地的单位运价为ijc，问应当如何调
运才干使总运费最省？
解：引入变量ijx，其取值为由i产地运往j销地的该商品数量，数学模型为
ΣΣ
==
m
i
n
j
ijijcx
11
min
s.t.
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
≥
==
==
Σ
Σ
=
=
0
,1,2,,
,1,,
1
1
ij
m
i
ijj
n
j
iji
x
xbjn
xaim
L
L
显然是一个线性规划问题，当然可以用单纯形法求解。
对产销平衡的运送问题，由于有以下关系式存在：
ΣΣΣΣΣΣ
======
=⎟⎠
⎞
⎜⎝
⎛
=⎟
⎟⎠
⎞
⎜⎜⎝
⎛
=
m
i
i
n
j
n
j
m
i
ij
m
i
n
j
jijbxxa
111111
其约束条件的系数矩阵相称特殊，可用比较简朴的计算方法，习惯上称为表上作业法（由
康托洛维奇和希罕柯克两人独立地提出，简称康—希表上作业法）。
§3指派问题
3.1指派问题的数学模型
例7拟分派n人去干n项工作，每人干且仅干一项工作，若分派第i人去干第j
项工作，需花费ijc单位时间，问应如何分派工作才干使工人花费的总时间最少？
容易看出，要给出一个指派问题的实例，只需给出矩阵()ijC=c，C被称为指派
问题的系数矩阵。
引入变量ijx，若分派i干j工作，则取=1ijx，否则取=0ijx。上述指派问题的
数学模型为
ΣΣ
==
n
i
n
j
ijijcx
11
min
s.t.Σ=
=
n
j
ijx
1
1
-6-
Σ=
=
n
i
ijx
1
1
=0或1ijx
上述指派问题的可行解可以用一个矩阵表达，其每行每列均有且只有一个元素为
1，其余元素均为0；可以用1,L,n中的一个置换表达。
问题中的变量只能取0或1，从而是一个0-1规划问题。一般的0-1规划问题求解
极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模
矩阵，其各阶非零子式均为±1），其非负可行解的分量只能取0或1，故约束=0或1ijx
可改写为≥0ijx而不改变其解。此时，指派问题被转化为一个特殊的运送问题，其中
m=n，==1ijab。
3.2求解指派问题的匈牙利算法
由于指派问题的特殊性，又存在着由匈牙利数学家Konig提出的更为简便的解法
—匈牙利算法。算法重要依据以下事实：假如系数矩阵()ijC=c一行（或一列）中每
一元素都加上或减去同一个数，得到一个新矩阵()ijB=b，则以C或B为系数矩阵的
指派问题具有相同的最优指派。
例8求解指派问题，其系数矩阵为
⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢
⎣
⎡
=
17192216
24221817
17211918
16151922
C
解将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行
元素减去17，最后一行的元素减去16，得
⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢
⎣
⎡
=
1360
7510
0421
1047
1B
再将第3列元素各减去1，得
⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢
⎣
⎡
=
*
*
*
*
2
1350
7500
0411
1037
B
以2B为系数矩阵的指派问题有最优指派
⎟⎟⎠
⎞
⎜⎜⎝
⎛
2134
1234
由等价性，它也是例7的最优指派。
有时问题会稍复杂一些。
例9求解系数矩阵C的指派问题
-7-
⎥⎥⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢⎢⎢
⎣
⎡
=
4107106
15146610

89666
127979
C
解：先作等价变换如下
∨
∨
∨
⎥⎥⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢⎢⎢
⎣
⎡
→
⎥⎥⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢⎢⎢
⎣
⎡
−
−
−
−
−
06362
980*04
0*10575
2300*0
50*202
4107106
15146610

89666
127979
4
6
7
6
7
容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但n=5，
最优指派还无法看出。此时等价变换还可进行下去。环节如下：
(1)对未选出0元素的行打∨；
(2)对∨行中0元素所在列打∨；
(3)对∨列中选中的0元素所在行打∨；
反复（2）、（3）直到无法再打∨为止。
可以证明，若用直线划没有打∨的行与打∨的列，就得到了可以覆盖住矩阵中所
有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令∨行元素减去此
数，∨列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转
变为0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选取出足
够的0元素为止。例如，对例5变换后的矩阵再变换，第三行、第五行元素减去2，第
一列元素加上2，得
⎥⎥⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢⎢⎢
⎣
⎡
04140
118004
08353
43000
70202
现在已可看出，最优指派为⎟
⎟⎠⎞
⎜⎜⎝
⎛
24135
12345
。
§4对偶理论与灵敏度分析
4.1原始问题和对偶问题
考虑下列一对线性规划模型：
maxcTxs.t.Ax≤b,x≥0(P)
和
minbTys.t.ATy≥c,y≥0(D)
-8-
称（P）为原始问题，（D）为它的对偶问题。
不太严谨地说，对偶问题可被看作是原始问题的“行列转置”：
（1）原始问题中的第j列系数与其对偶问题中的第j行的系数相同；
（2）原始目的函数的各个系数行与其对偶问题右侧的各常数列相同；
（3）原始问题右侧的各常数列与其对偶目的函数的各个系数行相同；
（4）在这一对问题中，不等式方向和优化方向相反。
考虑线性规划：
mincTxs.t.Ax=b,x≥0
把其中的等式约束变成不等式约束，可得
0,s.t.min≥⎥⎦
⎤
⎢⎣
⎡
−
≥⎥⎦
⎤
⎢⎣
⎡
−
x
b
b
x
A
A
cTx
它的对偶问题是
[][]c
y
y
AA
y
y
bbTTTT≤⎥⎦
⎤
⎢⎣
⎡
−⎥⎦
⎤
⎢⎣
⎡
−
2
1
2
max1s.t.
其中1y和2y分别表达相应于约束Ax≥b和−Ax≥−b的对偶变量组。令12y=y−y，
则上式又可写成
maxbTys.t.ATy≤c
原问题和对偶的对偶约束之间的关系：
minmax
⎪⎩
⎪⎨
⎧
≤
≥
无限制
变量0
0
⎪⎩
⎪⎨
⎧
=
≥
≤
0
0
0
行约束
⎪⎩
⎪⎨
⎧
=
≤
≥
0
0
0
行约束
⎪⎩
⎪⎨
⎧
≤
≥
无限制
变量0
0
4.2对偶问题的基本性质
1o对称性：对偶问题的对偶是原问题。
2o弱对偶性：若x是原问题的可行解，y是对偶问题的可行解。则存在
cTx≤bTy。
3o无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。
4o可行解是最优解时的性质：设xˆ是原问题的可行解，yˆ是对偶问题的可行解，
当cTxˆ=bTyˆ时，xˆ,yˆ是最优解。
5o对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目的函数值相同。
6o互补松弛性：若xˆ,yˆ分别是原问题和对偶问题的最优解，则
yˆT(Axˆ−b)=0,xˆT(ATyˆ−c)=0
例10已知线性规划问题
12345minω=2x+3x+5x+2x+3x
s.t.23412345x+x+x+x+x≥
-9-
23312345x−x+x+x+x≥
x≥0,j=1,2,L,5j
已知其对偶问题的最优解为;5
5
,3
5
4*
2
*
1y=y=z=。试用对偶理论找出原问题的最优
解。
解先写出它的对偶问题
12maxz=4y+3y
2212y+y≤①
312y−y≤②
23513y+y≤③
212y+y≤④
3312y+y≤⑤
,012yy≥
将*
2
*
1y,y的值代入约束条件，得②，③，④为严格不等式；由互补松弛性得
*0
4
*
3
*
2x=x=x=。因,*0
2
*
1yy>；原问题的两个约束条件应取等式，故有
3*4
5
*
1x+x=
2*3
5
*
1x+x=
求解后得到1,*1
5
*
1x=x=；故原问题的最优解为
X*=[10001]';ω*=5。
4.3灵敏度分析
在以前讨论线性规划问题时，假定ijija,b,c都是常数。但事实上这些系数往往是估
计值和预测值。如市场条件一变，jc值就会变化；ija往往是因工艺条件的改变而改变；
ib是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：当这
些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；或者
这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。这里我们就不讨
论了。
4.4参数线性规划
参数线性规划是研究ijija,b,c这些参数中某一参数连续变化时，使最优解发生变化
的各临界点的值。即把某一参数作为参变量，而目的函数在某区间内是这参变量的线性
函数，含这参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形
法进行分析参数线性规划问题。
§5投资的收益和风险
5.1问题提出
市场上有n种资产is（i=1,2,L,n）可以选择，现用数额为M的相称大的资金
作一个时期的投资。这n种资产在这一时期内购买is的平均收益率为ir，风险损失率为
iq，投资越分散，总的风险越少，总体风险可用投资的is中最大的一个风险来度量。
-10-
购买is时要付交易费，（费率ip），当购买额不超过给定值iu时，交易费按购买iu
计算。此外，假定同期银行存款利率是r0，既无交易费又无风险。（5%0r=）
已知n=4时相关数据如表1。
表1
isir(%)iqip(%)iu(元)
1s282.51103
2s211.52198
3s235.54.552
4s252.66.540
试给该公司设计一种投资组合方案，即用给定资金M，有选择地购买若干种资产
或存银行生息，使净收益尽也许大，使总体风险尽也许小。
5.2符号规定和基本假设
符号规定：
is：第i种投资项目，如股票，债券
iiir,p,q：分别为is的平均收益率，交易费率，风险损失率
iu：is的交易定额
0r：同期银行利率
ix：投资项目is的资金
a：投资风险度
Q：总体收益
基本假设：
1．投资数额M相称大，为了便于计算，假设M=1；
2．投资越分散，总的风险越小；
3．总体风险用投资项目is中最大的一个风险来度量；
4．n种资产is之间是互相独立的；
5．在投资的这一时期内，iiir,p,q，0r为定值，不受意外因素影响；
6．净收益和总体风险只受iiir,p,q影响，不受其它因素干扰。
5.3模型的分析与建立
1．总体风险用所投资的is中最大的一个风险来衡量，即
max{qx|i1,2,,n}ii=L
2．购买is所付交易费是一个分段函数，即
交易费
⎩⎨⎧
≤
>
=
iiii
iiii
puxu
pxxu
,
,
而题目所给定的定值iu（单位：元）相对总投资M很少，iipu更小，可以忽略不
计，这样购买is的净收益为iii(r−p)x。
3．要使净收益尽也许大，总体风险尽也许小，这是一个多目的规划模型：
-11-
目的函数为
⎪⎩
⎪⎨
⎧
−Σ=
minmax{}
max()
0
ii
n
i
iii
qx
rpx
约束条件为
⎪⎩
⎪⎨
⎧
≥=
=+Σ=
xin
pxM
i
n
i
ii
0,0,1,,
(1)
0
L
4．模型简化
a)在实际投资中，投资者承受风险的限度不同样，若给定风险一个界线a，使最
大的一个风险a
M
qxii≤，可找到相应的投资方案。这样把多目的规划变成一个目的的线
性规划。
模型一固定风险水平，优化收益
Σ=
−
n
i
iiirpx
0
max()
s.t.
⎪⎪⎩
⎪⎪⎨
⎧
+=≥=
≤
Σ=
n
i
iii
ii
pxMxin
a
M
qx
0
(1),0,0,1,L,
b)若投资者希望总赚钱至少达成水平k以上，在风险最小的情况下寻求相应的投
资组合。
模型二固定赚钱水平，极小化风险
min{max{}}iiqx
s.t.
⎪⎪
⎩
⎪⎪
⎨
⎧
+=≥=
−≥
Σ
Σ
=
=
n
i
iii
n
i
iii
pxMxin
rpxk
0
0
(1),0,0,1,,
()
L
c)投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资
组合。因此对风险、收益分别赋予权重s（0<s≤1）和(1−s)，s称为投资偏好系数。
模型三Σ=
−−−
n
i
iiiiisqxsrpx
0
min{max{}}(1)()
s.t.Σ=
+=≥=
n
i
iiipxMxin
0
(1),0,0,1,2,L,
5.4模型一的求解
模型一为：
minf(0.05,0.27,0.19,0.185,0.185)(x,x,x,x,x)T01234=−−−−−
-12-
s.t.
⎪⎪⎪⎪
⎩
⎪⎪⎪⎪
⎨
⎧
≥=
≤
≤
≤
≤
++++=
0(0,1,,4)
0.026
0.055
0.015
0.025
1.011.021.0451.0651
4
3
2
1
01234
xiL
xa
xa
xa
xa
xxxxx
i
由于a是任意给定的风险度，到底如何没有一个准则，不同的投资者有不同的风险
度。我们从a=0开始，以步长Δa=0.001进行循环搜索，编制程序如下：
clc,clear
a=0;
holdon
whilea<0.05
c=[-0.05,-0.27,-0.19,-0.185,-0.185];
A=[zeros(4,1),diag([0.025,0.015,0.055,0.026])];
b=a*ones(4,1);
Aeq=[1,1.01,1.02,1.045,1.065];
beq=1;
LB=zeros(5,1);
[x,Q]=linprog(c,A,b,Aeq,beq,LB);
Q=-Q;
plot(a,Q,'*r');
a=a+0.001;
end
xlabel('a'),ylabel('Q')
5.5结果分析
1.风险大，收益也大。
2．当投资越分散时，投资者承担的风险越小，这与题意一致。即：
冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。
3．在a=0.006附近有一个转折点，在这一点左边，风险增长很少时，利润增长
不久。在这一点右边，风险增长很大时，利润增长很缓慢，所以对于风险和收益没有特
殊偏好的投资者来说，应当选择曲线的拐点作为最优投资组合，大约是a=0.6%，
Q=20%，所相应投资方案为：
风险度a=0.006，收益Q=0.2023，00x=，0.241x=，0.42x=，0.10913x=，
0.22124x=。
习题一
1．试将下述问题改写成线性规划问题：
⎭⎬⎫
⎩⎨⎧
⎟⎠
⎞
⎜⎝
⎛ΣΣΣ
===
m
i
ini
m
i
ii
m
i
xii
axaxax
i11
2
1
1maxmin,,L,
⎩⎨⎧
≥=
+++=
xim
xxx
i
m
0,1,,
1
st.12
L
L
2．试将下列问题改写成线性规划问题：
-13-
Σ=
=
n
j
jjzcx
1
max||
⎪⎩
⎪⎨
⎧
==Σ=
j取值无约束
n
j
ijji
x
axbim
1
(1,2,,)
st.
L
3．线性回归是一种常用的数理记录方法，这个方法规定对图上的一系列点
(,),(,),,(,)1122nnxyxyLxy选配一条合适的直线拟合。方法通常是先定直线方程为
y=a+bx，然后按某种准则求定a,b。通常这个准则为最小二乘法，但也可用其他准
则。试根据以下准则建立这个问题的线性规划模型：
Σ=
−+
n
i
iiyabx
1
min|()|
4．某厂生产三种产品I，II，III。每种产品要通过A,B两道工序加工。设该厂有
两种规格的设备能完毕A工序，它们以12A,A表达；有三种规格的设备能完毕B工序，
它们以123B,B,B表达。产品I可在A,B任何一种规格设备上加工。产品II可在任何规
格的A设备上加工，但完毕B工序时，只能在1B设备上加工；产品III只能在2A与2B
设备上加工。已知在各种机床设备的单件工时，原材料费，产品销售价格，各种设备有
效台时以及满负荷操作时机床设备的费用如表2，求安排最优的生产计划，使该厂利润
最大。
表2
产品
设备
IIIIII
设备有效台时
满负荷时的
设备费用(元)
1A
2A
1B
2B
3B
5
7
6
4
7
10
9
8
12
11
6000
10000
4000
7000
4000
300
321
250
783
200
原料费(元/件)
单价(元/件)
0.25
1.25
0.35
2.00
0.50
2.80
5．有四个工人，要指派他们分别完毕4项工作，每人做各项工作所消耗的时间如
表3。
表3
工作
工人ABCD
甲15182124
乙19232218
丙26171619
丁19212317
问指派哪个人去完毕哪项工作，可使总的消耗时间为最小？
-14-
6．某战略轰炸机群奉命摧毁敌人军事目的。已知该目的有四个要害部位，只要摧
毁其中之一即可达成目的。为完毕此项任务的汽油消耗量限制为48000升、重型炸弹
48枚、轻型炸弹32枚。飞机携带重型炸弹时每升汽油可飞行2千米，带轻型炸弹时每
升汽油可飞行3千米。又知每架飞机每次只能装载一枚炸弹，每出发轰炸一次除来回路
程汽油消耗（空载时每升汽油可飞行4千米）外，起飞和降落每次各消耗100升。有关
数据如表4所示。
表4
摧毁也许性
要害部位
离机场距离
（千米）每枚重型弹每枚轻型弹
1
2
3
4
450
480
540
600
0.10
0.20
0.15
0.25
0.08
0.16
0.12
0.20
为了使摧毁敌方军事目的的也许性最大，应如何拟定飞机轰炸的方案，规定建立这个问
题的线性规划模型。
7．用Matlab求解下列线性规划问题：
123maxz=3x−x−x
s.t.
⎪⎪
⎩
⎪⎪
⎨
⎧
≥
−+=
−++≥
−+≤
,,0
21
423
211
123
13
123
123
xxx
xx
xxx
xxx
8．用Matlab求解下列规划问题：
min||2||3||4||1234z=x+x+x+x
s.t.01234x−x−x+x=
311234x−x+x−x=
2
2311234x−x−x+x=−
9．一架货机有三个货舱：前舱、中仓和后舱。三个货舱所能装载的货品的最大重
量和体积有限制如表5所示。并且为了飞机的平衡，三个货舱装载的货品重量必须与其
最大的允许量成比例。
表5货舱数据
前舱中仓后舱
重量限制（吨）10168
体积限制（立方米）
现有四类货品用该货机进行装运，货品的规格以及装运后获得的利润如表6。
表6货品规格及利润表
重量（吨）空间（立方米/吨）利润（元/吨）
货品
货品
货品
货品
-15-
假设：
（1）每种货品可以无限细分；
（2）每种货品可以分布在一个或者多个货舱内；
（3）不同的货品可以放在同一个货舱内，并且可以保证不留空隙。
问应如何装运，使货机飞行利润最大？__