第三章数学规划模型
- 格式：pdf
- 大小：327.79 KB
- 文档页数：16
第三章数学规划模型
第三章 数学规划模型
数学规划论起始20世纪30年代末，50年代与60年代发展成为⼀个完整的分⽀并受
到数学界和社会各界的重视。七⼋⼗年代是数学规划飞速发展时期，⽆论是从理论上还是算法⽅⾯都得到了进⼀步完善。时⾄今⽇数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有近1/4的问题可⽤数学规划进⾏求解。
数学规划模型的⼀般表达式：),,(..),,(min(max)≤βαβαx g t s x f
f 为⽬标函数，
g 为约束函数，x 为可控变量，α为已知参数， β为随机参数。
本章主要介绍线性规划、整数规划、⾮线性规划的基本概念与基本原理、⽆约束问题的最优化⽅法、约束问题的最优化⽅法、动态规划。3.1线性规划
线性规划模型是运筹学的重要分⽀，是20世纪三四⼗年代初兴起的⼀门学科。1947年美国数学家丹齐格G.B.Dantzig 及其同事提出的求解线性规划的单纯形法及有关理论具有划时代的意义。他们的⼯作为线性规划这⼀学科的建⽴奠定了理论基础。随着1979年前苏联数学家哈奇扬的椭球算法和1984年美籍印度数学家卡玛卡尔H.Karmarkar 算法的相继问世，线性规划的理论更加完备成熟，实⽤领域更加宽⼴。线性规划研究的实际问题多种多样，如⽣产计划问题、物资运输问题、合理下料问题、库存问题、劳动⼒问题、最优设计问题等。
就模型⽽⾔，线形规划模型类似于⾼等数学中的条件极值问题，只是其⽬标函数和约束条件都限定为线性函数。线性规划模型的求解⽅法⽬前仍以单纯形法为主要⽅法。本节介绍的主要内容有：线性规划模型的建⽴以及求解，线性规划的matlab 解法，线性规划问题的建模实例。3.1.1 线性规划模型的建⽴以及求解
⼀、线性规划模型的建⽴
例1、某机床⼚⽣产甲、⼄两种机床，每台销售后的利润分别为4000元与3000元。⽣产甲机床需⽤B A 、机器加⼯，加⼯时间分别为每台2⼩时和1⼩时；⽣产⼄机床需⽤C B A 、、三种机器加⼯，加⼯时间为每台各⼀⼩时。若每天可⽤于加⼯的机器时数分别为
A 机器10⼩时、
B 机器8⼩时和
C 机器7⼩时，问该⼚应⽣产甲、⼄机床各⼏台，才能使总利润最⼤？
建⽴上述问题的数学模型：设该⼚⽣产1x 台甲机床和2x ⼄机床时总利润最⼤，则21,x x 应满⾜：
（⽬标函数）2134maxx x z += (1)
s.t.（约束条件）
≥≤≤+≤+0
,7810
22122121x x x x x x x （2）
这⾥变量21,x x 称之为决策变量，（1）式被称为问题的⽬标函数，（2）中的⼏个不等式是问题的约束条件，记为s.t.(即subjectto)。上⾯的⽬标函数及约束条件均为线性函数，故被称为线性规划问题。 ⼀般线性规划问题的标准型为
∑==n
j jj 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.图解法
图解法简单直观，有助于了解线性规划问题求解的基本原理。我们先应⽤图解法来求解例1。如上图所⽰，阴影区域即为LP 问题的可⾏域R 。对于每⼀固定的值z ，使⽬标函数值等于z 的点构成的直线称为⽬标函数等位线，当z 变动时，我们得到⼀族平⾏直线。让等位线沿⽬标函数值减⼩的⽅向移动，直到等位线与可⾏域有交点的最后位置，此时的交点（⼀个或多个）即为LP 的最优解。
对于例1，显然等位线越趋于右上⽅，其上的点具有越⼤的⽬标函数值。不难看出，本例
的最优解为Tx )6,2(*=，最优⽬标值26*=z 。
2. 单纯形法
单纯形法是求解线性规划问题的最常⽤、最有效的算法之⼀。单纯形法是⾸先由George Dantzig 于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论：若线性规划问题有有限最优解，则⼀定有某个最优解是可⾏区域的⼀个极点。基于此，单纯形法的基本思路是：先找出可⾏域的⼀个极点，据⼀定规则判断其是否最优；若否，则转换到与之相邻的另⼀极点，并使⽬标函数值更优；如此下去，直到找到某⼀最优解为⽌。
三、典型的线性规划问题 1.运输问题(产销平衡)
例2 某商品有m 个产地、n 个销地，各产地的产量分别为ma a ,,1 ，各销地的需求量
分别为n
b b ,,1 。若该商品由i 产地运到j 销地的单位运价为ij c，问应该如何调运才能使总
运费最省？
解：引⼊变量ij
x ，其取值为由i 产地运往j 销地的该商品数量，数学模型为
∑∑==m i n
j ij
ij x
c 11
min
s.t. ?
≥====∑∑==0,,2,1,,,1,1
1ij m
i j ij n
j i ij x n j b x m i a x
显然是⼀个线性规划问题，当然可以⽤单纯形法求解。 对产销平衡的运输问题，由于有以下关系式存在：∑∑∑∑∑∑=======??? ??=???? ??=m
i i
n
j n j m i ij m
i n j ij j a x x b 111111
其约束条件的系数矩阵相当特殊，可⽤⽐较简单的计算⽅法，习惯上称为表上作业法（由康托洛维奇和希奇柯克两⼈独⽴地提出，简称康—希表上作业法）。
表上作业法是单纯形法在求解运输问题时的⼀种简化⽅法，其求解⼯作在运输表上进⾏逐步迭代如下：先按某⼀规则找出⼀个初始解（初始调运⽅案）；再对现⾏解作最优性判断；若这个解不是最优的，就在运输表上对它进⾏调整改进，得⼀新解；再判断，再改进，直到得到最优解。2.指派问题（⼜称分配问题Assignment Problem ） 2.1指派问题模型建⽴
例3 拟分配n ⼈去⼲n 项⼯作，每⼈⼲且仅⼲⼀项⼯作，若分配第i ⼈去⼲第j 项⼯作，需花费ij
c 单位时间，问应如何分配⼯作才能使⼯⼈花费的总时间最少？
容易看出，要给出⼀个指派问题的实例，只需给出矩阵)(ij c C =，C 被称为指派问题的系
数矩阵。
引⼊变量ijx ，若分配i ⼲j ⼯作，则取1=ij x ，否则取0
=ij x 。上述指派问题的数学模
型为∑∑==n i nj ij
ij x
c 11
min
s.t.
n ,1,2,j i,, 1 0,,2,1,1,,2,1,11
1
======∑∑== 或ij n
i ij n
j ij x n
j x n i x (5)
(5)的可⾏解既可以⽤⼀个矩阵(称为解矩阵)表⽰，其每⾏每列均有且只有⼀个元素为1，其余元素均为0，也可以⽤n ,,1 中的⼀个置换表⽰。(5)的变量只能取0或1，从⽽是⼀个0-1规划问题。⼀般的0-1规划问题求解极为困难。但指派问题并不难解，其约束⽅程组的系数矩阵⼗分特殊（被称为全单位模矩阵，其各阶⾮零⼦式均为1±），其⾮负可⾏解的分量只能取0或1，故约束1
0或=ij x 可改写为
≥ij x ⽽不改变其解。此时，指派问题被转化为⼀个特殊的运输问题，其中n m =，
1
==j i b a 。
2.2 求解指派问题的匈⽛利算法
由于指派问题的特殊性，⼜存在着由匈⽛利数学家D.Konig 提出的更为简便的解法—匈⽛利算法。算法主要依据以下事实：如果系数矩阵)(ij c C =⼀⾏（或⼀列）中每⼀元素
都加上或减去同⼀个数，得到⼀个新矩阵)(ij b B = ，则以C 或B 为系数矩阵的指派问题具
有相同的最优指派。
利⽤上述性质，可将原系数阵C 变换为含零元素较多的新系数阵B ，⽽最优解不变。若能在B 中找出n 个位于不同⾏不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为零，则所得该解是以B 为系数阵的指派问题的最优解，从⽽也是原问题的最优解。
由C 到B 的转换可通过先让矩阵C 的每⾏元素均减去其所在⾏的最⼩元素得矩阵D ，D 的每列元素再减去其所在列的最⼩元素得以实现。 下⾯通过⼀例⼦来说明该算法。
例4 求解系数矩阵C 的指派问题
=61071041066141512141217766698979712C 解：先作等价变换如下
∨∨
∨
→----- 26360
40*08957
510*00*
0032202
*056107104106614151214121776669897971246767
容易看出，从变换后的矩阵中只能选出四个位于不同⾏不同列的零元素，但5=n ，最优指派还⽆法看出。此时等价变换还可进⾏下去。步骤如下： 对未选出0元素的⾏打∨； 对∨⾏中0元素所在列打∨； 对∨列中选中的0元素所在⾏打∨； 重复（2）、（3）直到⽆法再打∨为⽌。3.1.2求解线性规划的Matlab 解法
⼀、求解线性规划的Matlab 解法 Matlab5.3中线性规划的标准型为b
Ax x c T x
≤ such that min
基本函数形式为linprog(c,A,b)，它的返回值是向量x 的值。还有其它的⼀些函数调⽤形式（在 Matlab 指令窗运⾏ help linprog 可以看到所有的函数调⽤形式），如： [x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)
这⾥fval 返回⽬标函数的值，Aeq 和beq 对应等式约束beq x Aeq =*，LB 和UB 分别是变量x 的下界和上界，x 是x 的初始值，OPTIONS 是控制参数。
例1 求解下列线性规划问题3
21532max x x x z -+=
≥≥+-=++0,,105273
21321321x x x x x x x x x
解 （i ）编写M ⽂件 c=[2;3;-5];a=[-2,5,-1]; b=-10; 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即可得所求结果。
⼆、可以转化为线性规划的问题
很多看起来不是线性规划的问题也可以通过变换变成线性规划问题来解决。如： 例2 问题为b
Ax x x x n ≤+++ t.s.|
|||||min
21
其中T
n x x x ][1 =，A 和b 为相应维数的矩阵和向量。
要把上⾯的问题变换成线性规划问题，只要注意到事实：对任意的ix ，存在
