数学建模
第一章 线性规划
§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 应满足
（目标函数）
2134m ax 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 线性规划的Matlab 标准形式
线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性规划的标准形式为
b Ax x
c x
T ≤ that such min
其中c 和x 为n 维列向量，b 为m 维列向量，A 为n m ?矩阵。
例如线性规划
b Ax x
c x
T ≥ that such max
的Matlab 标准型为
b Ax x
c x
T -≤-- that such min
1.3 线性规划问题的解的概念
一般线性规划问题的标准型为
∑==n
j j
j x c z 1min
(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.4 线性规划的图解法
图解法简单直观，有助于了解线性规划问题求解的基本原理。我们先应用图解法来求解例1。如上图所示，阴影区域即为LP问题的可行域R。对于每一固定的值z，使目标函数值等于z的点构成的直线称为目标函数等位线，当z变动时，我们得到一族平行直线。让等位线沿目标函数值减小的方向移动，直到等位线与可行域有交点的最后位置，此时的交点（一个或多个）即为LP的最优解。
对于例1，显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为T
*=，最优目标值
x)6,2(
26
z。
*=
从上面的图解过程可以看出并不难证明以下断言：
（1）可行域R可能会出现多种情况。R可能是空集也可能是非空集合，当R非空时，它必定是若干个半平面的交集（除非遇到空间维数的退化）。R既可能是有界区域，也可能是无界区域。
（2）在R非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其目标函数值无界）。
（3）R非空且LP有有限最优解时，最优解可以唯一或有无穷多个。
（4）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R 的“顶点”。
上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的n 维空间中，满足一线性等式∑==n
i i i b x a 1的点集
被称为一个超平面，而满足一线性不等式∑=≤n i i i b x a 1
（或∑=≥n
i i i b x a 1
）
的点集被称为一个半空间（其中),,(1n a a Λ为一n 维行向量，b 为一实数）。有限个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。易见，线性规划的可行域必为多胞形（为统一起见，空集Φ也被视为多胞形）。
在一般n 维空间中，要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点可以看成为边界直线的交点，但这一几何概念的推广在一般n 维空间中的几何意义并不十分直观。为此，我们将采用另一途径来定义它。
定义1 称n 维空间中的区域R 为一凸集，若R x x ∈?21,及)1,0(∈?λ，有R x x ∈-+21)1(λλ。
定义2 设R 为n 维空间中的一个凸集，R 中的点x 被称为R 的一个极点，若不存在R x x ∈21、及)1,0(∈λ，使得21)1(x x x λλ-+=。
定义1 说明凸集中任意两点的连线必在此凸集中；而定义2 说明，若x 是凸集R 的一个极点，则x 不能位于R 中任意两点的连线上。不难证明，多胞形必为凸集。同样也不难证明，二维空间中可行域R 的顶点均为R 的极点（R 也没有其它的极点）。
1.5 求解线性规划的Matlab 解法
单纯形法是求解线性规划问题的最常用、最有效的算法之一。单纯形法是首先由
George Dantzig 于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个
极点。基于此，单纯形法的基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。这里我们不再详细介绍单纯形法，有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的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,X 0,OPTIONS) 这里fval 返回目标函数的值，Aeq 和beq 对应等式约束beq x Aeq =*，
LB 和UB 分别是变量x 的下界和上界，0x 是x 的初始值，OPTIONS
是控制参数。
例2 求解下列线性规划问题 321532m ax 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即可得所求结果。 例3 求解线性规划问题 32132 m in x x x z ++=
?????≥≥+≥++0,,6238243
2121321x x x x x x x x 解 编写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 问题为
b
Ax x x x n ≤+++ t.s.|
|||||min 21Λ
其中T n x x x ][1Λ=，A 和b 为相应维数的矩阵和向量。
要把上面的问题变换成线性规划问题，只要注意到事实：对任意的i x ，存在0,>i i v u 满足
i i i v u x -=，i i i v u x +=|| 事实上，我们只要取2||i i i x x u +=
，2
||i
i i x x v -=就可以满足上面的条件。
这样，记T n u u u ][1Λ=，T n v v v ][1Λ=，从而我们可以把上面的问题变成
∑=+n
i i i
v u
1
)(min
??
?≥≤-0
,)( t.s.v u b
v u A
§2 运输问题(产销平衡)
例5 某商品有m 个产地、n 个销地，各产地的产量分别为m a 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 1
11111 其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习
惯上称为表上作业法（由康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）。
表上作业法是单纯形法在求解运输问题时的一种简化方法，其求解工作在运输表上进行逐步迭代如下：先按某一规则找出一个初始解（初始调运方案）；再对现行解作最优性判断；若这个解不是最优的，就在运输表上对它进行调整改进，得一新解；再判断，再改进，直到得到最优解。
§3 指派问题（又称分配问题Assignment Problem ）
3.1 指派问题的数学模型
例6 拟分配n 人去干n 项工作，每人干且仅干一项工作，若分配第i 人去干第j 项工作，需花费ij c 单位时间，问应如何分配工作才能使工人花费的总时间最少？
容易看出，要给出一个指派问题的实例，只需给出矩阵
)(ij c C =，C 被称为指派问题的系数矩阵。
引入变量ij x ，若分配i 干j 工作，则取1=ij x ，否则取0=ij x 。上述指派问题的数学模型为
∑∑==n i n
j 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，故约束10或=ij x 可改写为0≥ij x 而不改变其解。此时，指派问题被转化为一个特殊的运输问题，其中n m =，1==j i b a 。
3.2 求解指派问题的匈牙利算法
由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig 提出的更为简便的解法—匈牙利算法。算法主要依据以下事实：如果系数矩阵)(ij c C =一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵)(ij b B = ，则以C 或B 为系数矩阵的指派问题具有相同的最优指派。
利用上述性质，可将原系数阵C 变换为含零元素较多的新系数阵B ，而最优解不变。若能在B 中找出n 个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为零，则所得该解是以B 为系数阵的指派问题的最优解，从而也
是原问题的最优解。
由C 到B 的转换可通过先让矩阵C 的每行元素均减去其所在行的最小元素得矩阵D ，D 的每列元素再减去其所在列的最小元素得以实现。
下面通过一例子来说明该算法。 例7 求解指派问题，其系数矩阵为
?
?
??
?
????
???=16221917
1718222418192117
22191516C
解 将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得
?
?
??
?
????
???=0631
01571240
74011B 再将第3列元素各减去1，得
?????
???????=**
**20531005711407301B 以2B 为系数矩阵的指派问题有最优指派
???
?
??43124321 由等价性，它也是例7的最优指派。
有时问题会稍复杂一些。
例8 求解系数矩阵C 的指派问题
?????
??
?????????=61071041066141512141217766698979712C
解：先作等价变换如下
∨
∨
∨????????
?????
???→????????????????----- 2636040*08957510*00*0032202*05610710410661415121412177666989797124
6767 容易看出，从变换后的矩阵中只能选出四个位于不同行不同
列的零元素，但5=n ，最优指派还无法看出。此时等价变换还可进行下去。步骤如下：
(1) 对未选出0元素的行打∨； (2) 对∨行中0元素所在列打∨；
(3) 对∨列中选中的0元素所在行打∨； 重复（2）、（3）直到无法再打∨为止。 可以证明，若用直线划没有打∨的行与打∨的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令∨行元素减去此数，∨列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例5变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得
???
??
?
?
?
????????04140
400811353800003420207
现在已可看出，最优指派为???
?
??5314254321。
§4 对偶理论与灵敏度分析
4.1 原始问题和对偶问题
考虑下列一对线性规划模型： x c T max s.t. 0,≥≤x b Ax
(P) 和
y
b T min
s.t.
0,≥≥y c y A T
(D)
称（P ）为原始问题，（D ）为它的对偶问题。
不太严谨地说，对偶问题可被看作是原始问题的“行列转置”： （1） 原始问题约束条件中的第j 列系数与其对偶问题约束条
件中的第j 行的系数相同； （2） 原始目标函数的系数行与其对偶问题右侧的常数列相
同； （3） 原始问题右侧的常数列与其对偶目标函数的系数行相
同； （4） 在这一对问题中，除非负约束外的约束不等式方向和优
化方向相反。 考虑线性规划：
0,s.t.
m in
≥=x b Ax x
c T
把其中的等式约束变成不等式约束，可得 0, s.t. min ≥??
?
???-≥??????-x b b x A A x c T 它的对偶问题是
[]
[
]
c y y A A y y b b
T T
T T
≤??
????-?
?
?
???-2121 s.t.max
其中1y 和2y 分别表示对应于约束b Ax ≥和b Ax -≥-的对偶变量组。令21y y y -=，则上式又可写成
c y A y b T T ≤ s.t. m ax
原问题和对偶的对偶问题约束之间的关系：
min max
???
??≤≥无限制变量
00 ??
???=≥≤行约束 ???
??=≤≥行约束
??
?
??≤≥无限制变量00 4.2 对偶问题的基本性质
1o 对称性：对偶问题的对偶是原问题。
2o 弱对偶性：若x 是原问题的可行解，y 是对偶问题的可行解。则恒有：y b x c T T ≤。
3o 无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。
4o 可行解是最优解时的性质：设x
?是原问题的可行解，y ?是对偶问题的可行解，当y b x
c T T ??=时，y x ?,?是最优解。 5o 对偶定理：若原问题有有限最优解，那么对偶问题也有最优解；且目标函数值相同。
6o 互补松弛性：若y x
?,?分别是原问题和对偶问题的最优解，则
0)?(?,0)?(?=-=-c y A x b x A y
T T T 由上述性质可知，对任一LP 问题(P)，若它的对偶问题(D)可能的话，我们总可以通过求解（D ）来讨论原问题（P ）：若(D)无界，则(P)无可行解；若(D)有有限最优解*w ，最优值b w *，则利用互补松弛性可求得(P)的所有最优解，且(P)的最优值为b w *。例如对只有两个行约束的LP ，其对偶问题只有两个变量，总可用图解法来求解。
例9 已知线性规划问题
5432132532m in x x x x x ++++=ω 432..54321≥++++x x x x x t s 33254321≥+++-x x x x x 5,,2,1,0Λ=≥j x j
已知其对偶问题的最优解为5
3,54
*
2*1==y y ，最优值为5*=z 。试用
对偶理论找出原问题的最优解。
解 先写出它的对偶问题
2134m ax y y z += s.t. 2221≤+y y
①
321≤-y y
②
53231≤+y y ③
221≤+y y ④ 3321≤+y y
⑤
0,21≥y y 将*
2*1,y y 的值代入约束条件，得②，③，④为严格不等式；设原问
题的最优解为),,(*5
*1*x x x Λ=，由互补松弛性得0*4*3*2===x x x 。因 0,*2*1>y y ；原问题的两个约束条件应取等式，故有
43*5*1=+x x 32*5*1=+x x 求解后得到1,1*
5
*1==x x ；故原问题的最优解为 ]'10001[*=X ；最优值为5*=w 。
4.3 灵敏度分析
灵敏度分析是指对系统或周围事物因周围条件变化显示出来的敏感程度的分析。
在以前讨论线性规划问题时，假定j i ij c b a ,,都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，j c 值就会变化；ij a 往往是因工艺条件的改变而改变；i b 是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：当这
些参数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；或者这些参数在什么范围内变化时，线性规划问题的最优解不变。这里我们就不讨论了。
4.4 参数线性规划
参数线性规划是研究j i ij c b a ,,这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这参变量的线性函数，含这参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形法进行分析参数线性规划问题。
习 题 一
1. 某厂生产三种产品I ，II ，III 。每种产品要经过B A ,两道工序加工。设该厂有两种规格的设备能完成A 工序，它们以21,A A 表示；有三种规格的设备能完成B 工序，它们以321,,B B B 表示。产品I 可在B A ,任何一种规格设备上加工。产品II 可在任何规格的A 设备上加工，但完成B 工序时，只能在1B 设备上加工；产品III 只能在2A 与2B 设备上加工。已知在各种机床设备的单件工时，原材料费，产品销售价格，各种设备有效台时以及满负荷操作时机床设备的费用如下表，要求安排最优的生产计划，使该厂利润最大。
2. 有四个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表：
问指派哪个人去完成哪项工作，可使总的消耗时间为最小？
3. 某战略轰炸机群奉命摧毁敌人军事目标。已知该目标有四个要害部位，只要摧毁其中之一即可达到目的。为完成此项任务的汽油消耗量限制为48000升、重型炸弹48枚、轻型炸弹32枚。飞机携带重型炸弹时每升汽油可飞行2千米，带轻型炸弹时每升汽油可飞行3千米。又知每架飞机每次只能装载一枚炸弹，每出发轰炸一次除来回路程汽油消耗（空载时每升汽油可飞行4千米）外，起飞和降落每次各消耗100升。有关数据如表所示。
方案，要求建立这个问题的线性规划模型。
课题： 3.3.2简单的线性规划（2） 班级：组名：姓名：设计人：赵帅军审核人：魏帅举领导审批： 一．：自主学习，明确目标 1．知识与技能：掌握线性规划问题的图解法，并能应用它解决一些简单的实 际问题； 2．过程与方法：经历从实际情境中抽象出简单的线性规划问题的过程，提高 数学建模能力； 教学重点：利用图解法求得线性规划问题的最优解 教学难点：把实际问题转化成线性规划问题，并给出解答，解决难点的关键 是根据实际问题中的已知条件，找出约束条件和目标函数，利用图解法求得 最优解。 教学方法：经历从实际情境中抽象出简单的线性规划问题的过程，提高数学 建模能力 二．研讨互动，问题生成 1、二元一次不等式Ax+By+C＞0在平面直角坐标系中表示直线Ax+By+C=0 某一侧所有点组成的平面区域（虚线表示区域不包括边界直线） 2、目标函数, 线性目标函数，线性规划问题,可行解，可行域, 最优解: 三．合作探究，问题解决 线性规划在实际中的应用： 线性规划的理论和方法主要在两类问题中得到应用，一是在人力、物力、 资金等资源一定的条件下，如何使用它们来完成最多的任务；二是给定一项 任务，如何合理安排和规划，能以最少的人力、物力、资金等资源来完成该 项任务 下面我们就来看看线性规划在实际中的一些 [范例讲解] 例5 营养学家指出，成人良好的日常 饮食应该至少提供0.075kg的碳 水化合物，0.06kg的蛋白质， 0.06kg的脂肪，1kg食物A含有 0.105kg碳水化合物，0.07kg蛋 白质，0.14kg脂肪，花费28元； 而1kg食物B含有0.105kg碳水 化合物，0.14kg蛋白质，0.07kg脂肪，花费21元。为了满足营养 专家指出的日常饮食要求，同时使花费最低，需要同时食用食物A 和食物B多少kg？
3.3.2简单的线性规划问题导学案（1） 班级 姓名 【学习目标】 1、了解线性规划的意义及线性约束条件、线性目标函数、可行解、可行域、最 优解等概念； 2、能根据条件，建立线性目标函数； 3、了解线性规划问题的图解法，并会用图解法求线性目标函数的最大（小）值。 【学习过程】 一、自主学习 (1)目标函数: (2)线性目标函数: (3)线性规划问题: (4)可行解: (5)可行域: (6) 最优解: 二、合作探究 在约束条件???????≥≥≤+≥+0 0221y x y x y x 下所表示的平面区域内， 探索：目标函数2P x y =+的最值？ （1）约束条件所表示的平面区域称为 （2）猜想在可行域内哪个点的坐标00(,)x y 能使P 取到最大(小)值？ （3）目标函数2P x y =+可变形为y= ，p 的几何意义： （4）直线2y x p =-+与直线2y x =-的位置关系 （5）直线2y x p =-+平移到什么位置时，在y 轴上的截距P 最大？ （6）直线2y x p =-+平移到什么位置时，在y 轴上的截距P 最小？ 三、交流展示 1、已知变量,x y 满足约束条件?? ???≥≤+-≤-1255334x y x y x ，求2t x y =-的最值。
规律总结：用图解法解决简单的线性规划问题的基本步骤？ 四、达标检测 A 组：1.下列目标函数中，Z 表示在y 轴上截距的是（ ） A.y x z -= B.y x z -=2 C.y x z += D.y x z 2+= 2.不等式组 x –y+5≥0 x + y ≥0 x ≤3表示的平面区域的面积等于（ ） A 、32 B 、1214 C 、1154 D 、632 3.若?? ???≤+≥≥100y x y x ，则y x z -=的最大值为（ ） A.－1 B.1 C.2 D.－2 4.已知x ，y 满足约束条件5003x y x y x -+??+??? ≥≥≤，则24z x y =+的最小值为（ ） A ．5 B ．6- C ．10 D ．10- 5．若?? ???≥≤+≤--0101x y x y x ，则目标函数y x z +=10的最优解为（ ） A ．（0，1），（1，0） B.（0，1），（0，－1） C.（0，－1），（0，0） D.（0，－1），（1，0） 6. 若222x y x y ????+? ≤≤≥，则目标函数2z x y =+的取值范围是（ ） A ．[26]， B ．[25]， C ．[36]， D ．[35]， 7.若A(x, y)是不等式组 –1＜x ＜2 –1＜y ＜2)表示的平面区域内的点，则2x –y 的取值范围是（ ） A 、（–4, 4） B 、（–4, –3） C 、（–4, 5） D 、（–3, 5） B 组：1.在不等式组 x ＞0 y ＞0 x+y –3＜0表示的区域内，整数点的坐标是 。 2．若y x ,都是非负整数,则满足5≤+y x 的点共有________个。
数学建模线性规划模型 数学建模教案,线性规划模型 一、问题的提出 在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。 例1 若需在长为4000mm的圆钢上，截出长为698mm和518mm两种毛坯，问怎样截取才能使残料最少, 初步分析可以先考虑两种“极端”的情况: (1)全部截出长为698mm的甲件，一共可截出 EQ F(4000,698) ?5件，残料长为510mm。 (2)全部截出长为518mm的乙件，一共可截出 EQ F(4000,518) ?7件，残料长为374mm。由此可以想到，若将 x个甲件和y 个乙件搭配起来下料，是否可能使残料减少,把截取条件数学化地表示出来就是: 698 x + 518y ? 4000 x ，y都是非负整数 目标是使:z = EQ F(698x + 518y,4000) (材料利用率)尽可能地接近或等于1。(尽可能地大) 该问题可用数学模型表示为: 目标函数 : max z = EQ F(698x + 518y,4000) 满足约束条件: 698 x + 518y ? 4000 ， (1) x ，y都是非负整数 . (2) 例2 某工厂在计划期内要安排生产I 、II两种产品，已知生产单位产品所需的设备台数及A、B两种原料的消耗，如下表所示。
I II 设备 1 2 8台数 原材料A 4 0 16kg 原材料B 0 4 12kg 该工厂每生产一件产品I可获利 2 元，每生产一件产品II可获利 3 元，问应如何安排生产计划使工厂获利最多, 这问题可以用以下的数学模型来描述:设 x, x分别表示在计划期内产品I、II 的产量。 1 2 因为设备的有效台数为8 ，这是一个限制产量的条件，所以在确定I 、II的产量时，要考虑不超过设备的有效台数，即可用不等式表示为: x + 2x ? 8 . 1 2同理，因原材料A 、B的限量，可以得到以下不等式: 4 x ? 16 1 4 x ? 12. 2 该工厂的目标是在不超过所有资源限量的条件下，如何确定产量x、x以得到最大 1 2的利润。若用 z 表示利润，这时z = 2x + 3 x。综上所述，该计划问题可用数学模型表 1 2 示为: 目标函数 : max z = 2x + 3 x 1 2 满足约束条件: x + 2x ? 8 1 2 4 x ? 16 1 4 x ? 12. 2
3.3.2简单的线性规划问题学案（一） 预习案（限时20分钟） 学习目标：1.了解线性规划的意义，了解线性规划的基本概念；2.掌握线性规划问题的图解法.3.能用线性规划的方法解决一些简单的实际问题，提高学生解决实际问题的能力. 学习重点，难点： 会画二元一次不等式（组）所表示的平面区域及理解数形结合思想,求目标函数的值。 预习指导：预习课本P87-91 1.如果两个变量y x ,满足一组一次不等式组，则称不等式组是变量y x ,的约束条件，这组约束条件都是关于y x ,的 次不等式，故又称 条件． 2.关于y x ,的一次式),(y x f z =是达到最大值或最小值所涉及的变量y x ,的解析式，叫线性目标函数． 3.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为 规划问题． 4.可行解、可行域和最优解：在线性规划问题中， ①满足线性约束条件的解(,)x y 叫 ；②由所有可行解组成的集合叫做 ； ③使目标函数取得最大或最小值的可行解叫线性规划问题的 解. 线性规划问题，就是求线性目标函数在线性约束条件下的最大值或最小值的问题. 预习检测 1.设变量y x ,满足约束条件?? ???≥+≤+≥-12102y x y x y x ，则目标函数y x z +=2的最大值为 ( ) A .。34 B .2 C .23 D .2 3- 2.若变量y x ,满足约束条件?? ???-≥≤+≤1,1y y x x y 且y x z +=2的最大值和最小值分别为m 和n ，则n m -＝( ) A ．5 B ． 6 C ． 7 D ． 8 3.若y x ,满足约束条件103030x y x y x -+≥??+-≥??-≤? ，则目标函数2z x y =-的最小值为__________ 4.求35z x y =+的最大值和最小值，使式中的y x ,满足约束条件5315153x y y x x y +≤??≤+??-≥? .
数学建模 第一章 线性规划 §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 应满足 （目标函数） 2134m ax 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 线性规划的Matlab 标准形式 线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性规划的标准形式为 b Ax x c x T ≤ that such min 其中c 和x 为n 维列向量，b 为m 维列向量，A 为n m ?矩阵。 例如线性规划 b Ax x c x T ≥ that such max 的Matlab 标准型为 b Ax x c x T -≤-- that such min 1.3 线性规划问题的解的概念 一般线性规划问题的标准型为 ∑==n j j j x c z 1min (3) ∑==≤n j i j ij m i b x a 1,,2,1 s.t.Λ (4) 可行解 满足约束条件（4）的解),,,(21n x x x x Λ=，称为线性规划问题的可行解，而使目标函数（3）达到最小值的可行解叫最优解。
高三数学第一轮复习讲义(47）2004。10.27 简单的线性规划 一．复习目标： 1．了解用二元一次不等式表示平面区域，了解线性规划的意义，并会简单的应用； 2．通过以线性规划为内容的研究课题与实习作业,提高解决实际问题的能力． 二．知识要点： 已知直线0Ax By C ++=，坐标平面内的点00(,)P x y ． 1．①若0B >，000Ax By C ++>，则点00(,)P x y 在直线的方； ②若0B >，000Ax By C ++<，则点00(,)P x y 在直线的方． 2．①若0B >，0Ax By C ++>表示直线0Ax By C ++=方的区域; ②若0B <，0Ax By C ++>表示直线0Ax By C ++=方的区域． 三．课前预习： 1．不等式240x y -->表示的平面区域在直线240x y --=的() ()A 左上方()B 右上方()C 左下方()D 右下方 2．表示图中阴影部分的二元一次不等式组是（）
()A 220102x y x y -+≤??-≥??≤?()B 21002x y x y -??-≥??≤≤?()C 1002x y -≤??≤≤?()D 10 02x y -≤??≤≤? 3．给出平面区域(包括边界）如图所示,若使目标函数(0)z ax y a =+> 取得最大值的最优解有无穷多个，则a 的值为(） () A 14() B 35() C 4() D 53 4．原点和点(1,1)在直线0x y a +-=的两侧， 则a 的取值范围是． 5.由|1|1y x ≥+-及||1y x ≤-+2)
四．例题分析: 例1．某人上午7时乘船出发,以匀速v 海里/时（420v ≤≤)从A 港到相距50海里的B 港去，然后乘汽车以ω千米/时（30100ω≤≤）自B 港到相距300千米的C 市去,计划在当天下午4至9时到达C 市.设乘船和汽车的时间分别为x 和y 小时,如果已知所要的经费（单位：元)1003(5)(8)P x y =+?-+-，那么v ，ω分别是多少时所需费用最少?此时需要花费多少元？ 小结： 例2．某运输公司有10辆载重量为6吨的A 型卡车与载重量为8吨的B 型卡车，有11名驾驶员。在建筑某段高速公路中，该公司承包了每天至少搬运480吨沥青的任务.已知每辆卡车每天往返的次数为A 型卡车8次，B 型卡车7次;每辆卡车每天的成本费A 型车350元，B 型车400元.问每天派出A 型车与B 型车各多少辆，公司所花的成本费最低，最低为多少? 小结：
线性规划 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
7．4 简单的线性规划第二课时学案 一、知识点： 1、二元一次方程表示平面区域： 2、目标函数、可行域、可行解、最优解、线性规划问题： 3、解线性规划问题的基本步骤： 二、应用： 例1：(1)已知,x y满足不等式组 22 21 0,0 x y x y x y +≥ ? ? +≥ ? ?≥≥ ? ，求3 z x y =+的最小值. (2) 已知,x y满足不等式组 270 43120 230 x y x y x y -+≥ ? ? --≤ ? ?+-≥ ? ,求 ①43 z x y =-的最大值与最小值; ②22 z x y =+的最大值与最小值; ③y z x =的取值范围.
(3) 已知,x y 满足不等式组2040250x y x y x y -+≥??+-≥??--≤? , 求①23z x y =-的最值; ②22222z x y x y =++-+的最小值; ③12 y z x +=+的最大值; ④24z x y =+-的最大值. 例2:给出平面区域如图所示,若使目标函数()0z ax y a =+> 取到最大值的最优解有无穷多个,则a 的值为( ). A. 14 B. 35 C. 4 D.53 变式: 给出平面区域如图所示,若使目标函数()0z ax y a =+> 取到最大值的最优解只在C 处,则a 的范围为 . 例3：已知()2,f x ax c =-且()()411,125f f -≤≤--≤≤，求()3f 的取值范围.
7．4 简单的线性规划第三课时学案 一、知识点： 1、目标函数、可行域、可行解、最优解、线性规划问题： 2、实际问题： 3、整点问题： 二、应用： 例1：某工厂生产甲、乙两种产品.已知生产甲种产品1t需耗A种矿石10t、B种矿石5t、煤4t；生产乙种产品1t需耗A种矿石4t、B 种矿石4t、煤9t.每1t甲种产品的利润是600元, 每1t乙种产品的利润是1000元.工厂在生产这两种产品的计划中要求消耗A种矿石不超过300t、B种矿石不超过200t、煤不超过363t.问甲、乙两种产品应各生产多少，能使利润总额达到最大？
【自学】 对于题目：已知实数,x y 满足：12,x y ≤+≤11x y -≤-≤，求2x y +的取值范围. 有个同学的解法如下： 解：由已知，得不等式组：12(1) 11(2)x y x y ≤+≤ ?? -≤-≤ ? ， 两个同向不等式作加法，得： 原不等式组化为 两个同向不等式作加法，得023(4)y ≤≤ 即 0 1.5y ≤≤ (5). 两个同向不等式（3）和（5）作加法，得 从而2x y +的取值范围是[0,4.5]. 思考：上题合适的解法该是怎样的呢？？？ 【对话】 【精讲点拨】 例1、已知2z x y =+，其中实数,x y 满足：12 11 x y x y ≤+≤??-≤-≤?，求z 的最大值和最 小值. 小结：
1、线性规划中的几个相关概念： 2、解决简单线性规划的方法： 3.解简单线性规划问题的步骤：
【对话】 【合作探究与展示分享】 例2、设2z x y =+，式中变量,x y 满足条件4335251x y x y x -≤-?? +≤??≥? ，求z 的最大值和最小值. 变式1、在例2中将2z x y =+改为610z x y =+，求z 的最大值和最小值. 变式2、在例2中将2z x y =+改为2z x y =-，求z 的最大值和最小值. 例3、设变量,x y 满足条件1035371x y x y x -+≤?? +≤??≥? ， （1） 找出,x y 均为正整数的可行解； （2） 求出目标函数53z x y =+的最大值； （3） 若,x y 均为正整数，求目标函数53z x y =+的最大值.
【评价】 【自我评价】 1. 右图中阴影部分的点满足不等式组52600 x y x y x y +≤??+≤? ?≥??≥?在这些点中，使目标函数68z x y =+取得最大值的点的坐标是______________. 2. 求函数23z x y =+的最大值，式中的,x y 满足约束条件2324700 x y x y x y +-≤ ??-≤? ?≥??≥? *3、在例2中将2z x y =+改为y z x =，求z 的最大值和最小值. *4、在例2中将2z x y =+改为2 2 z x y =+，求z 的最大值和最小值. **5.已知变量,x y 满足约束条件14 22x y x y ≤+≤?? -≤-≤? ，若目标函数 (0)z ax y a =+>其中仅在点(3,1)处取得最大值，则a 的取值范围为____________.
-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)。由于上面的目标函数及约束条件均为线性
3.3.2 简单的线性规划问题(一) 学习目标了解线性规划的意义；会求简单的线性目标函数的最值及一些简单的非线性函数的最值． 预习篇 1．二元一次不等式组是一组对变量x 、y 的约束条件，这组约束条件都是关于x 、y 的 不等式， 所以又称为线性约束条件． 2．z ＝ax ＋by (a 、b 是实常数)是欲达到最大值或最小值所涉及的变量x 、y 的解析式，叫做 函 数．由于z ＝ax ＋by 又是x 、y 的一次解析式，所以又叫做 目标函数． 3．求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题．满足线性约 束条件的解(x ，y)叫做 ，由所有可行解组成的集合叫做 .分别使目标函数 z ＝ax ＋by 取得最大值或最小值的可行解叫做这个问题的最优解． 课堂篇 探究点一 线性目标函数的最值问题 问题 若x≥0，y≥0，且x ＋y≤1，则目标函数z ＝x ＋2y 的最大值是________． 探究点二 非线性目标函数的最值问题 问题 一些非线性目标函数的最值可以赋予几何意义，利用数形结合的思想加以解决，例如： ①z ＝x 2＋y 2表示可行域中的点(x ，y) _______； ②z ＝(x －a)2＋(y －b)2表示可行域中的点(x ，y) _____________； ③z ＝y －b x －a 表示可行域内的点(x ，y) _______； ④z ＝ay ＋b cx ＋d (ac≠0)，可以先变形为z ＝a c ·y －????－b a x －??? ?－d c ，可知z 表示可行域内的点(x ，y) ； ⑤z ＝|ax ＋by ＋c| (a 2＋b 2≠0)，可以化为z ＝a 2＋b 2·|ax ＋by ＋c|a 2＋b 2的形式，可知z 表示可行域内的点(x ，y)__________________________________． 典型例题 例1 已知1≤x ＋y≤5，－1≤x －y≤3，求2x －3y 的取值范围． 跟踪训练1 设变量x ，y 满足约束条件????? x ＋y≥3，x －y≥－1， 2x －y≤3， 则目标函数z ＝2x ＋3y 的最小值为( ) A ．6 B ．7 C ．8 D ．23
《简单的线性规划问题》（第一课时）教学设计 一、内容与内容解析 本节课是《普通高中课程标准实验教科书数学》人教A版必修5第三章《不等式》中3.3.2《简单的线性规划问题》的第一课时. 主要内容是线性规划的相关概念和简单的线性规划问题的解法． 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法，广泛地应用于军事作战、经济分析、经营管理和工程技术等方面．简单的线性规划指的是目标函数含两个自变量的线性规划，其最优解可以用数形结合方法求出。简单的线性规划关心的是两类问题：一是在人力、物力、资金等资源一定的条件下，如何使用它们来完成最多的任务；二是给定一项任务，如何合理规划，能以最少的人力、物力、资金等资源来完成. 教科书利用生产安排的具体实例，介绍了线性规划问题的图解法，引出线性规划等概念，最后举例说明了简单的二元线性规划在饮食营养搭配中的应用. 本节内容蕴含了丰富的数学思想方法，突出体现了优化思想、数形结合思想和化归思想. 本节教学重点：线性规划问题的图解法；寻求有实际背景的线性规划问题的最优解. 二、目标和目标解析 （一）教学目标 1.了解约束条件、目标函数、可行解、可行域、最优解等基本概念. 2. 会用图解法求线性目标函数的最大值、最小值. 3.培养学生观察、联想、作图和理解实际问题的能力，渗透化归、数形结合的数学思想. 4.结合教学内容培养学生学习数学的兴趣和“用数学”的意识. （二）教学目标解析 1. 了解线性规划模型的特征：一组决策变量(,) x y表示一个方案；约束条件是一次不等式组；目标函数是线性的，求目标函数的最大值或最小值．熟悉线性
某银行经理计划用一笔资金进行有价证券的投资，可供购进的证券以及其信用等级、到期年限、收益如下表所示．按照规定，市政证券的收益可以免税，其他证券的收益需按50%的税率纳税．此 表四 问：（1）若该经理有1000万元资金，应如何投资？ （2）如果能够以2.75%的利率借到不超过100万元资金，该经理应如何操作？ （3）在1000万元资金情况下，若证券A 的税前收益增加为4.5%，投资应否改变？若证券C 的税前收益减少为4.8%，投资应否改变？ 解：设利润函数为M(x),投资A 、B 、C 、D 、E 五种类型的证券资金分别为12345,,,,x x x x x 万元，则由题设条件可知
12345123452341234512345123451234512345()0.0430.0270.0250.0220.0451000400 225 1.4()9154325(),,,,0 M x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x =++++++++≤++≥++++≤++++++++≤++++≥ 利用MATLAB 求解最优解，代码如下： c=[-0.043 -0.027 -0.025 -0.022 -0.045]; A=[1 1 1 1 1;0 -1 -1 -1 0;0.6 0.6 -0.4 -0.4 3.6;4 10 -1 -2 -3]; b=[1000;-400;0;0]; Aeq=[]; beq=[]; vlb=[0;0;0;0;0]; vub=[]; [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub) 运行结果如下：
《简单的线性规划》教学设计（二） 【教学目标】 巩固二元一次不等式和二元一次不等式组所表示的平面区域,能用此来求目标函数的最值． 【重点难点】 理解二元一次不等式表示平面区域是教学重点． 如何扰实际问题转化为线性规划问题,并给出解答是教学难点． 【教学步骤】 一、新课引入 我们知道,二元一次不等式和二元一次不等式组都表示平面区域,在这里开始,教学又翻开了新的一页,在今后的学习中,我们可以逐步看到它的运用． 线性规划 先讨论下面的问题 设2z x y =+,式中变量x 、y 满足下列条件 4335251x y x y x -≤-??+≤??≥? ① 求z 的最大值和最小值． 我们先画出不等式组①表示的平面区域,如图中 ABC ?内部且包括边界．点(0,0)不在这个三角形区域内,当0,0x y == 时,20z x y =+=,点(0,0)在直线0:20l x y +=上．作一组和0l 平等的直线:2,l x y t t R +=∈ 可知,当l 在0l 的右上方时,直线l 上的点(,)x y 满足20x y +>． 即0t >,而且l 往右平移时,t 随之增大,在经过不等式组①表示的三角形区域内的点且平行于l 的直线中,以经过点(5,2)A 的直线l ,所对应的t 最大,以经过点(1,1)B 的直线1l ,所对应的t 最小,所以 max 25212z =?+=min 2113z =?+= 在上述问题中,不等式组①是一组对变量x 、y 的约束条件,这组约束条件都是关于x 、y 的一次不等式,所以又称线性约束条件． 2x y +是欲达到最大值或最小值所涉及的变量x 、y 的解析式,叫做目标函数,由于2z x y =+又是x 、y 的解析式,所以又叫线性目标函数,上述问题就是求线性目标函数2z x y =+在 =0
运筹学模型（一） 本章重点： 线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题 复习要求： 1.进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵. 2.进一步理解数学模型的作用与特点. 本章复习重点是线性规划基础模型、运输问题模型和目标规划模型.具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单.运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单.你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求.目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型.另外，关于图论模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型.这之前恐怕要善于将一个实际问题转化为图论模型.还有一个最小数的问题，该如何把一个网络中的最小数找到.另外在个别场合可能会涉及一笔划问题. 1.营养配餐问题的数学模型 n n x C x C x C Z ++=211m i n ????? ?? ??=≥≥+++≥+++≥+++??) ,,2,1(0, ,, 22112222212111212111n j x b x a x a x a b x a x a x a b x a x a x a t s j m n mn m m n n n n 或更简洁地表为 ∑== n j j j x C Z 1 m i n ??? ??? ?==≥≥??∑=),,2,1,,2,1(01 n j m i x b x a t s j n j i j ij 其中的常数C j 表示第j 种食品的市场价格，a ij 表示第j 种食品含第i 种营养的数量，b i 表示人或动物对第i 种营养的最低需求量. 2.合理配料问题的数学模型 有m 种资源B 1，B 2，…，B m ，可用于生产n 种代号为A 1，A 2，…，A n 的产品.单位产品A j 需用资源B i 的数量为a ij ，获利为C j 单位，第i 种资源可供给总量为b i 个单位.问如何安排生产，使总利润达到最大？ 设生产第j 种产品x j 个单位（j =1，2，…，n ），则有 n n x C x C x C Z +++= 2211m a x
第十三章线性规划与数学建模简介 【授课对象】理工类专业学生 【授课时数】6学时 【授课方法】课堂讲授与提问相结合 【基本要求】1、了解数学模型的基本概念、方法、步骤； 2、了解线性规划问题及其数学模型； 3、了解线性规划问题解的性质及图解法. 【本章重点】线性规划问题. 【本章难点】线性规划问题、线性规划问题解的性质、图解法. 【授课内容】 本章简要介绍数学建模的基本概念、方法、步骤，并以几个典型线性规划问题为例，介绍构建数学模型的方法及其解的性质。 §1 数学建模概述 一、数学建模 数学建模是构造刻划客观事物原型的数学模型并用以分析、研究和解决实际问题的一种科学方法。运用这种科学方法，必须从实际问题出发，遵循从实践到认识再实践的认识规律，围绕建模的目的，运用观察力、想象力的抽象概括能力，对实际问题进行抽象、简化，反复探索，逐步完善，直到构造出一个能够用于分析、研究和解决实际问题的数学模型。因此，数学建模是一种定量解决实际问题的创新过程。 二、数学模型的概念 模型是人们对所研究的客观事物有关属性的模拟。例如在力学中描述力、 量和加速度之间关系的牛顿第二定律F＝ma就是一个典型的（数学）模型。一般地，可以给数学模型下这样的定义：数学模型是磁于以部分现实世界为一定目的而做的抽象、简化的数学结构。 通俗而言，数学模型是为了一定目的对原型所作的一种抽象模拟，它用数学 式子，数学符号以及程序、图表等描述客观事物的本质特征与内在联系。 三建立数学模型的方法和步骤 建立数学模型没有固定模式。下面介绍一下建立模型的大体过程： 1.建模准备 建模准备是确立建模课题的过程。这类课题是人们在生产和科研中为了使 认识和实践过一步发展必须解决的问题。因此，我们首先要发现这类需要解决的实际问题。其次要弄清所解决问题的目的要求并着手收集数据。进行建模筹划，组织必要的人力、物力等，确立建模课题。 2．模型假设 作为建模课题的实际问题都是错综复杂的、具体的。如果不对这些实际问题进行抽象简化，人们就无法准确把握它的本质属性，而模型假设就是根据建模的目的对原型进行抽象、简化，抓住反映问题本质属性的主要因素，简化掉那些非本质的
课题：3.3.2简单的线性规划（1） 班级： 组名 一．：自主学习，明确目标 1．知识与技能：使学生了解二元一次不等式表示平面区域；了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念；了解线性规划问题的图 解法，并能应用它解决一些简单的实际问题； 2．过程与方法：经历从实际情境中抽象出简单的线性规划问题的过程，提高数学建模能力； 教学重点：用图解法解决简单的线性规划问题 教学难点：准确求得线性规划问题的最优解 教学方法：经历从实际情境中抽象出简单的线性规划问题的过程，提高数学建模能力； 二．研讨互动，问题生成 1、二元一次不等式0>++C By Ax 在平面直角坐标系中表示什么图形？ 2、怎样画二元一次不等式（组）所表示的平面区域？应注意哪些事项？ 3、熟记“直线定界、特殊点定域”方法的内涵。 三．合作探究，问题解决 在现实生产、生活中，经常会遇到资源利用、人力调配、生产安排等问题。 1、下面我们就来看有关与生产安排的一个问题： 引例：某工厂有A 、B 两种配件生产甲、乙两种产品，每生产一件甲产品使用4个A 配件耗时1h,每生产一件乙产品使用4个B 配件耗时2h ，该厂每天最多可从配件厂获得16个A 配件和12个B 配件，按每天8h 计算，该厂所有可能的日生产安排是什么？ （1）用不等式组表示问题中的限制条件： 设甲、乙两种产品分别生产x 、y 件，又已知条件可得二元一次不等式组： 2841641200 x y x y x y +≤??≤?? ≤??≥?≥?? ……………………………………………………………….（1） （2）画出不等式组所表示的平面区域： 如图，图中的阴影部分的整点（坐标为整数的点）就代表所有可能的日生产安排。 （3）提出新问题： 进一步，若生产一件甲产品获利2万元，生产一件乙产品获利3万元，采用哪种生产安排利润最大？ （4）尝试解答： 设生产甲产品x 件，乙产品y 件时，工厂获得的利润为z ,则z=2x+3y . 这样，上述问
3.5.1二元一次不等式（组）与简单的线性规划问题 学案 1. 二兀 次不等式 Ax + By + C>0,当B>0时，表示直线 Ax + By + C = 0 边的区域；: 当B<0 时，表示直线 Ax + By + C = 0 边的区域. 2. 二兀一次不等式 Ax + By + C<0, 当B>0时，表示直线 Ax + By + C = 0 边的区域：: 当 B<0 时，表示直线 Ax + By + C = 0 边的区域. 3. 二兀一次不等式 Ax + By + C>0, 当A>0时，表示直线 Ax + By + C = 0 边的区域：: 当A<0 时，表示直线 Ax + By + C = 0 边的区域. 4. 二兀一次不等式 Ax + By + C<0, 当A>0时，表示直线 Ax + By + C = 0 边的区域：: 当A<0 时，表示直线 Ax + By + C = 0 边的区域. 【课前达标】 1?点（2，3），（1，2）在直线 y=2x + 1 的 （填“同侧”、 “异侧”） 【预习达标】 ) m 的取值范围是（ .-5 < me 10 2?若点(1, 3)和(—4,— 2)在直线2x+y+m=0的两侧，则 A. m<-5 或 m>10 B . m=-5 或 m=10 C . -5
3．3.2 简单的线性规划问题(二) 课时目标 1．准确利用线性规划知识求解目标函数的最值． 2．掌握线性规划实际问题中的两种常见类型． 1．用图解法解线性规划问题的步骤： (1)分析并将已知数据列出表格； (2)确定线性约束条件； (3)确定线性目标函数； (4)画出可行域； (5)利用线性目标函数(直线)求出最优解； 根据实际问题的需要，适当调整最优解(如整数解等)． 2．在线性规划的实际问题中，主要掌握两种类型：一是给定一定数量的人力、物力资源，问怎样运用这些资源能使完成的任务量最大，收到的效益最大；二是给定一项任务，问怎样统筹安排，能使完成的这项任务耗费的人力、物力资源最小． 一、选择题 1．某厂生产甲产品每千克需用原料A 和原料B 分别为a 1、b 1千克，生产乙产品每千克需用原料A 和原料B 分别为a 2、b 2千克，甲、乙产品每千克可获利润分别为d 1、d 2元．月初一次性购进本月用的原料A 、B 各c 1、c 2千克，要计划本月生产甲产品和乙产品各多少千克才能使月利润总额达到最大．在这个问题中，设全月生产甲、乙两种产品分别为x 千克、y 千克，月利润总额为z 元，那么，用于求使总利润z ＝d 1x ＋d 2y 最大的数学模型中，约束条件为( ) A.????? a 1x ＋a 2y ≥c 1， b 1 x ＋b 2 y ≥c 2 ，x ≥0，y ≥0 B.????? a 1x ＋ b 1y ≤ c 1， a 2 x ＋b 2 y ≤c 2 ， x ≥0， y ≥0
C.????? a 1x ＋a 2y ≤c 1， b 1 x ＋b 2 y ≤c 2 ，x ≥0，y ≥0 D.????? a 1x ＋a 2y ＝c 1， b 1 x ＋b 2 y ＝c 2 ， x ≥0， y ≥0 答案 C 解析 比较选项可知C 正确． 2. 如图所示的坐标平面的可行域内(阴影部分且包括边界)，若使目标函数z ＝ax ＋y (a >0)取得最大值的最优解有无穷多个，则a 的值为( ) A.14 B.35 C ．4 D.53 答案 B 解析 由y ＝－ax ＋z 知当－a ＝k AC 时，最优解有无穷多个．∵k AC ＝－35，∴a ＝35 . 3．某公司有60万元资金，计划投资甲、乙两个项目，按要求对 项目甲的投资不小于对项目乙投资的2 3 倍，且对每个项目的投资不能 低于5万元，对项目甲每投资1万元可获得0.4万元的利润，对项目乙每投资1万元可获得0.6万元的利润，该公司正确规划投资后，在这两个项目上共可获得的最大利润为( ) A ．36万元 B ．31.2万元 C ．30.4万元 D ．24万元 答案 B 解析 设投资甲项目x 万元，投资乙项目y 万元，