第一章线性规划

第1章线性规划制作：数理学院赵建强

§1.4初始基本可行解的确定

4§1.1线性规划问题及其数学模型

1§1.2线性规划问题的解

2§1.3单纯形法

3本章的教学目的和要求：

1、掌握线性规划数学模型的基本特征和标准形式，以及线性规划问题数学模型的建立方法，学会用图解法求解简单的线性规划问题。2、理解线性规划问题的解的概念，了解线性规划的基本理论。3、了解单纯形表的构成，熟练掌握运用单纯形法求解线性规划问题。4、掌握人工变量法（包括大Ｍ法和两阶段法）的计算步骤。5、本章将安排4学时的上机实验，练习如何建立线性规划模型解决相关的实际问题，并会用相关的数学软件求解该线性规划模型。教学重点：线性规划的标准形式、图解法、单纯形法。教学难点：单纯形法、人工变量法。§1.1线性规划问题及其数学模型教学目的和要求：使学生了解常见的几种线性规划实例；掌握线性规划的一般形式、标准形式、向量形式、矩阵形式等；会将线性规划的一般形式标准化。教学重点：线性规划的一般形式、标准形式；线性规划的标准化。教学难点：线性规划的标准化。教学过程：

在经济活动及工程技术中会遇到各种各样的实际问题，描述实际问题共性的抽象的数学形式称为该问题的数学模型．通常建立线性规划问题数学模型要遵循以下步骤：(1)明确问题中有待确定的未知量(称为决策变量)，并用数学符号表示；(2)明确问题中所有的限制条件(称为约束条件)，并用决策变量的一组线性方程或线性不等式表示；(3)明确问题的目标，并用决策变量的一个线性函数(称为目标函数)表示，按问题的不同取最大值或最小值．1.1.1线性规划问题的几个实例下面结合几个实际例子来介绍线性规划问题的特点，并按上面给出的三个步骤来建立它们的数学模型.例1.1-1生产计划问题假设某厂计划生产甲、乙两种产品，这两种产品都要分别在A，B，C三种不同设备上加工．按工艺资料规定：生产每件甲产品需占用设备的小时数分别为2，l，4；生产每件乙产品需占用设备的小时数分别为2，2，0.已知各设备计划期内用于生产这两种产品的能力(小时数)分别为12，8，16；又知每生产一件甲产品，该厂会获得利润2元，每生产一件乙产品，该厂能获利润3元，问该厂应安排生产两种产品各多少件才能使总的利润收入为最大?解(1)明确决策变量工厂需要确定的是甲、乙两种产品的计划生产量，设x1,x2分别为甲、乙两种产品的计划生产量，总的利润为z．

(2)明确约束条件因设备A在计划期内有效时间为12小时，不允许超过．故有对设备B，C也可列出类似的不等式此外产品的产量

只能取非负值，即

≥0≥0这种限制称为变量的非负约束条件．(3)明确目标工厂的目标是在各种设备能力允许的条件下，使总利润收入

为最大．

综合起来，该问题的数学模型为：求一组变量

的值在满足约束条件

的情况下，

为最大．

使利润例1.1-2运输问题设有三个地方

生产某种物资

简称为产地)

(四个地方

需要该种物资

（简称为销地)

产地的产量和销地的销量以及产地到销地的单位运价表见表1.1—1，问如何组织物资的运输，才能在满足供需的条件下使总的运费最少．表1.1—1产销运输表例1.1-3合理下料问题某工厂生产某一种型号的机床，每台机床上需要2.9m，2.1m,1.5m的轴分别为一根、二根、一根，这些轴需用同一种圆钢制作，圆钢的长度为7.4m，如果要生产100台机床，问应如何安排下料，才能使用料最省?1.1.2线性规划问题的数学模型一、线性规划模型的一般形式上述各例具有下列共同特征：

1、存在一组变量

，称为决策变量，通常要求这些变量的取值是非负的．2、存在若干个约束条件，可以用一组线性等式或线性不等式来描述．

3、存在一个目标函数，它是决策变量的线性函数，按实际问题求最大值或最小值．

根据以上特征，可以将线性规划问题抽象为一般的数学表达式，

即线性规划问题数学模型（简称线性规划模型）的一般形式为：

式中max表示求最大值，min表示求最小值，

是由实际问题所确定的常数.

为利润系数或成本系数；

称为限定系数或常数项；

称为结构系数或消耗系数；

为决策变量；每一个约束条件只有

一种符号

．

二、线性规划模型的标准形式线性规划模型的具体形式是多种多样的．为了讨论和计算方便，

我们要在这众多的形式中规定一种形式，将其称为

线性规划模型的标准形式．

通常线性规划模型的标准形式为

上述形式的特点是：

线性规划模型的标准形式可以写成简缩形式：

线性规划模型的标准形式有时用矩阵或向量描述往往更为方便．

用向量表示线性规划模型的标准形式为其中

向量

是变量

对应的约束条件中的系数列向量.

用矩阵表示线性规划的标准形式为

其中其它同前．我们称A为约束方程的系数矩阵（m×n），

一般m<n，m、n为正整数．

三、线性规划模型的标准化我们对线性规划问题的研究是基于标准形式进行的，因此对于给定的非标准形式线性规划问题的数学模型，则需要将其化为标准形式．一般地，对于不同形式的线性规划模型，可以采用以下一些方法将其化为标准形式．对于目标函数是求最小值的线性规划问题，只要将目标函数的系数反号，即可化为等价的最大值问题．2．约束条件为“≤”（“≥”）类型的线性规划问题，

可在不等式左边加上（或减去）一个非负的新变量，

即可化为等式．这个新增的非负变量称为松弛变量（或剩余变量），也可统称为松弛变量．在目标函数中一般认为新增的松弛变量的系数为零．3．如果在一个线性规划问题中，决策变量

的符号没有限制，我们可用两个非负的新变量和

之差来代替，即将变量

写成

且有

通常将这样的

称为自由变量．如果Xk<=0,则令Xk/=-Xk

4．当常数项

为负值时，可在该约束条件的两边

分别乘以-1．

例1.1-4将下列线性规划模型化成标准形式解通过以下四个步骤：（1）目标函数两边乘上-1化为求最大值；（2）以

代入目标函数和所有的约束条件中，

其中

（3）在第一个约束条件的左边加上松弛变量

（4）在第二个约束条件的左边减去剩余变量

于是得到该线性规划模型的标准形式：练习：化标准型p361.3(4),(5),1.9(3)作业：p341.1（1）（4）（5）、1.2§1.2线性规划问题的解教学目的和要求：掌握线性规划问题的基本概念；掌握线性规划图解法；了解线性规划问题的解的特殊情况；掌握线性规划解的基本性质。教学重点：线性规划问题的基本概念、基本性质、图解法。教学难点：线性规划的基本性质。教学过程：1.２.１线性规划问题的基本概念设有线性规划问题

一、可行解满足线性规划约束条件（1.2-2）和(1.2-3)的解

称为线性规划问题的可行解．

所有可行解的集合称为可行域或可行解集．二、最优解使线性规划的目标函数（1.2-1）式达到最大的可行解称为线性规划的最优解．

三、基本解设A是约束方程组(1.2-2)的（m×n）阶的系数矩阵（m<n）,其秩为m，则A中任意m个线性无关的列向量构成的m×m阶子矩阵

称为线性规划的一个基矩阵或简称为一个基，记为B．显然，

B为非奇异矩阵，即|B|≠0．

基矩阵的m个列向量称为基向量，其余n-m个向量称为非基向量；与m个基向量相对应的m个变量称为基变量，其余的n-m个变量则称为非基变量．显然，基变量随着基的变化而变化，当基被确定以后，基变量和非基变量也随之确定了．

若令约束方程组(1.2-2)中的n-m个非基变量为零，再对余下的m个基变量求解，所得到的约束方程组的解称为基本解．基本解的个数总是小于

等于

的．

如设

为线性规划的一个基，于是

为基变量，

就为非基变量．

现令非基变量

，方程组(1.2-2)就变为此时方程组有m个方程，m个未知数，

可唯一地解出

则向量就是对应于基B的基本解．

四、基本可行解

满足非负条件（1.2-3）的基本解称为基本可行解；对应于基本可行解的基称为可行基．

显然，基本可行解既是基本解，又是可行解．一般，基本可行解的数目要少于基本解的数目，最多两者相等．当基本可行解的非零分量个数恰为m时，称此解是非退化的解；如果有的基变量也取零值，即基本可行解的非零分量个数小于m时，称此解是退化解．例1.2-1求下列线性规划问题的所有基本解，并指出哪些是基本可行解．解将已知模型化为标准形式系数矩阵

则易知均为线性规划问题的基矩阵．对应基

，基变量为

，非基变量为

．令

得

.从而

为线性规划问题的一个基本解．

因

均大于零，故

为线性规划问题的一个基本可行解．

对应于其他基

的基本解列表见表1.2-1．

表1.2-1对应于其他基的基本解

2.线性规划的图解法线性规划的图解法(解的几何表示)：对于只有两个决策变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。图解法求解线性规划问题的步骤如下：2.线性规划的图解法(1)建立直角坐标系：分别取决策变量x1,x2

为坐标向量。

2.线性规划的图解法（2）绘制可行域：对每个约束（包括非负约束）条件，作出其约束半平面（不等式）或约束直线（等式）。各半平面与直线交出来的区域若存在，其中的点为此线性规划的可行解。称这个区域为可行集或可行域。然后进行下步。否则若交为空，那么该线性规划问题无可行解。

2.线性规划的图解法

（3）绘制目标函数等值线，并移动求解：目标函数随着取值不同，为一族相互平行的直线。首先，任意给定目标函数一个值，可作出一条目标函数的等值线（直线）；然后，确定该直线平移使函数值增加的方向；最后，依照目标的要求平移此直线。2.线性规划的图解法结果若目标函数等值线能够移动到既与可行域有交点又达到最优的位置，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。否则，目标函数等值线与可行域将交于无穷远处，此时称无有限最优解。

2.线性规划的图解法

Max

z=1500x1

+2500x2

s.t.3x1+2x2

≤65(A)

2x1+x2

≤40(B)

3x2

≤75(C)

x1,x2

≥0(D,E)2.线性规划的图解法例题作图（1）按照图解法的步骤：（1）以决策变量x1

，x2

为坐标向量作平面直角坐标系；

2.线性规划的图解法（2）对每个约束（包括非负约束）条件作出直线（A、B、C、D、E），并通过判断确定不等式所决定的半平面。各约束半平面交出来的区域即可行集或可行域如下图阴影所示。

2.线性规划的图解法例题作图（2）第2步图示(1)分别作出各约束半平面X2≥0x1

≥03x2

≤753x1+2x2

≤65

2x1+x2

≤40

2.线性规划的图解法例题作图（3）第2步图示(2)各约束半平面的交－可行域2.线性规划的图解法（3）任意给定目标函数一个值（例如37500）作一条目标函数的等值线，并确定该等值线平移后值增加的方向（向上移动函数值增大），平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置，得到交点(5,25)T，即最优解。此目标函数的值为70000。2.线性规划的图解法例题作图（4）第3步图示作出目标函数等值线函数值增大2.线性规划的图解法例题作图（5）第3步图示(2)求出最优解1

2.线性规划的图解法根据上面的过程我们得到这个线性规划的最优解x1=5、x2=25，最优值z=70000即最优方案为生产甲产品5件、乙产品25件，可获得最大利润为70000元。2.线性规划的图解法线性规划的解有如下几种情况：

1、存在有限最优解：惟一最优解；无穷多个最优解

2、无有限最优解（无界解）

3、无可行解（可行域空）

2.线性规划的图解法例2.5：在例2.4的线性规划模型中，如果目标函数变为：

Maxz=1500x1

+1000x2

那么，最优情况下目标函数的等值线与直线（A）重合。这时，最优解有无穷多个，是从点(5,25)T到点(15,10)T线段上的所有点，最优值为32500。如下图所示：

2.线性规划的图解法

无穷多解的情况(15,10)T

2.线性规划的图解法

例2.6：在例2.4的线性规划模型中,如果约束条件（A）、（C）变为：

3x1

+2x2

≥65(A’）

3x2

≥75(C’）并且去掉（D、E）的非负限制。那么，可行域成为一个上无界的区域。这时，没有有限最优解，如下图所示：

2.线性规划的图解法

无有限解的情况

2、线性规划的图解法例2.7：在例2.4的线性规划模型中，如果增加约束条件（F）为：

x1

+x2≥40

（F）那么，可行域成为空的区域。这时，没有可行解，显然线性规划问题无解。如下图所示：

2.线性规划的图解法

无可行解的情况

根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况

1.可行域为封闭的有界区域

(a)有唯一的最优解；

(b)有无穷多个最优解；

2.可行域为封闭的无界区域

(c)有唯一的最优解；

2.线性规划的图解法

(d)有无穷多个最优解；

(e)目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少)，因而没有有限最优解。

3.可行域为空集

(f)没有可行解，原问题无最优解

2.线性规划的图解法图1.2—5无界解图1.2—6无可行解可行域解空集有界集无界集无可行解唯一最优解无穷多最优解无界解.2.4线性规划问题解的基本性质

根据线性规划解的基本概念，并从图解法中直观地看到线性规划

问题的解具有以下一些基本性质．（有关性质的证明略）

定理1线性规划的可行解集是一个凸集．

凸集的几何意义是：若以集合中任意两点为端点的线段仍在该集合中，则称该集合为凸集．

定理2若一个线性规划有可行解，则它必有基本可行解．

定理3设线性规划的可行解集为D，则D的顶点（极点）就是线性规划的基本可行解．

定理4若线性规划问题有最优解，则一定存在一个基本可行解

是它的最优解．即：最优解一定可以在D的顶点（极点）上达到．

定理5若线性规划存在两个相异的基本可行解

和

为最优解，则以

线段上的一切点

为端点的也都是线性规划的最优解．

上述性质告诉我们，求解线性规划问题，只需在基本可行解（凸多边形的顶点）中寻找就行了．由于凸多边形的顶点是有限的，因而基可行解的个数也是有限的，这就保证了线性规划若有最优解，一定可以在有限步内得到最优解．作业：1.4线性规划模型

作如表1.3－1形式的表格称为单纯形表．§1.3单纯形法

单纯形法是求解线性规划问题的常用算法，它是1947年由丹塞格(Geofe·Dantzig)提出的．下面通过典式介绍其求解原理表1.3－1下面我们讨论单纯形表与线性规划模型间的对应关系。对于线性规划模型若将其系数矩阵A用分块矩阵来表示，即为研究方便起见，不妨设为一个基，再令则有相应地可有即以

和

分别表示基变量和非基变量．

同样有

其中

为目标函数中基变量的系数，

为非基变量的系数，

于是对约束条件有设B为基，即B的行列式不等于零，则

B-1存在，故由

可得到

（1.3-11）

（1.3-12）即

同样对目标数有将（1.3-12）式代入上式，得（1.3-13）

显然，若令非基变量

XN=0，由（1.3-12）式得

如果使

，便可得到一个基本可行解：当B=I（单位矩阵）时，则有我们把由（1.3-11）和(1.3-13)式结合成(1.3-14),(1.3-15),(1.3-16)式称为线性规划对应于基的典式．表1.3-1的单纯形表排列的就是典式的一系列数据，实际上它是把约束条件中的基变量用非基变量表示，同时把目标函数中基变量也用非基变量来表示，所形成的一种利于在表格上运算的一种形式．

为目标函数中非基变量的系数向量，其中第

个分量

为非基变量

这就是检验数即：

如果初始基矩阵B=I，则基变量的值为右端项

而由（1.3-14）式得

同时可以看出

的系数．回顾典式：对于线性规划模型对于选定的基1.3-10两端乘以B-1将它化为典式下面以例1.3-1，结合典式与定理六，介绍单纯形法求解过程．例1.3-1求解例1.1-1所示的线性规划问题．解：

引进松弛变量

将例1.1-1的数学模型化为标准形式

则(1.3-2)的系数矩阵

(1.3-1)(1.3-2)首先，我们找出一个初始基本可行解，在

中

是线性无关的，故

为(1.3－2)的一个基，对应的基变量为

,非基变量为

若令

，可得

．显然，

可作为本问题的一个初始基本可行解．

可作为本问题的一个初始基本可行解．

讨论求解初始基本可行解的一般方法．）

（我们将在本章1.4中当前基本可行解的实际意义是不生产任何产品，目标函数（利润）为0，即

必须寻找新的基本可行解，

这肯定不是最优解．下一步我们且使目标函数值增加．

由目标函数(1.3-1)式可看出，由于

前面的系数均为正数，所以当

由现在的非基变量（即取0值）变为基变量

（取非零值），可使目标函数值增加．又因为

的系数比

的系数大（利润增加快），故选

作为新的基本可行解中

的基变量，称其为进基变量．

为保证基变量个数不变（等于系数矩阵A的秩m），还需要

确定原来的基变量

哪一个被换出来作为非基变量

（称为出基变量）．为此，我们进行下面的分析．由约束方程

(1.3-2)的前三式可得当

进基以后，令

，而

仍为非基变量，即

．同时还必须保证所有的变量满足非负约束条件

（1.3-3）（即(2.3-2)式的最后一式成立），于是有或写为生产产品乙必须同时兼顾三种设备台时，因此产品乙最多不得超过4件，否则，第二种设备台时就不够用了．但由式(1.3-4)可得这说明生产4件乙产品,A设备台时还剩4，而B设备能力已用尽．

因此出基变量的选择原则应该是由最薄弱的资源来决定．即选取

（1.3-5）

正好体现了兼顾各种限制条件的思想，又称最小比值法则．

为了简便地得到一个新的基本可行解，可以通过对约束方程组

(1.3-2)的前三式进行变换，即将(1.3-2)式的第二式

,第一、三式

x2的系数变成1x2的系数变成都是0．于是我们得到方程组其变换过程为用

乘(1.3-2)式的第二式得(1.3-7)式；

用-1乘(1.3-2)式的第二式加到第一式得(1.3-6)式；

若非基变量

等于零，基变量

值就可以从右边常数项直接得到．

所以得新的基本可得解

相应地我们把目标函数用非基变量表示成

(1.3-8)而当

时，

．显然

上述结果表明，生产产品乙4件，可获得利润12元．

从（1.3-8）式可见，非基变量

x1的系数仍是正数，这说明

x1进基，仍可使目标函数值增大，即

不是最优解．重复上述步骤，

确定进基变量（

）和出基变量（

），经过迭代

得到另一个基本可行解

表示，（1.3-8）式变成而目标函数用非基变量（1.3-9）

由于目标函数(1.3-9)的非基变量的系数均小于零，即当

增加时，目标函数只会减少，因此，

就是最优解．

此结果表明，工厂应生产产品甲4件，产品乙2件，可获得

最大利润14元．从上述代数解法可以看到，求最优解的过程

是一种迭代选优的过程，即从一个基本可行解到另一个基本可行解，且使目标函数值一次比一次好，在几何上，则是从可行域的一个顶点迭代到

另一个顶点．

1.３.２线性规划的典式和单纯形表单纯形法就是将上述的代数解法表格化，即将运算过程中

相关数据之间的关系完全在表格上反映出来．723.单纯形法计算流程初始基本可行解是否最优解或无限最优解?结束沿边界找新的基本可行解NY73单纯形法的基本步骤可描述如下：

（1）寻找一个初始的可行基和相应基本可行解（极点），确定基变量、非基变量以及基变量、非基变量（全部等于0）和目标函数的值，并将目标函数和基变量分别用非基变量表示；

3.单纯形法74

（2）在用非基变量表示的目标函数表达式（2-12）中，我们称非基变量xj的系数（或其负值）为检验数记为j

。若j>0，那么相应的非基变量xj，它的值从当前值0开始增加时，目标函数值随之增加。这个选定的非基变量xj称为“进基变量”，转（3）。如果任何一个非基变量的值增加都不能使目标函数值增加，即所有j

非正，则当前的基本可行解就是最优解，计算结束；3.单纯形法75

（3）在用非基变量表示的基变量的表达式（2-11）中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到0的变量xr

，满足，=minb’i/a’ij

a’ij>0=b’r

/a’rj这个基变量xr称为“出基变量”。当进基变量的值增加到

时，出基变量xr的值降为0时，可行解就移动到了相邻的基本可行解（极点），转（4）。3.单纯形法76如果进基变量的值增加时，所有基变量的值都不减少，即所有a’ij

非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束；（4）将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复（1）。3.单纯形法3、单纯形法例2.10Maxz=1500x1+2500x2

s.t.3x1+2x2≤652x1+x2≤403x2≤75

x1,x2≥0

化标准形式：

Maxz=1500x1+2500x2

s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x5

0单纯形法过程(1)152001-1/3153010-2/32500x22501001/3-62500

1500000-2500/3

单纯形法过程(2)-700000

0-5000-500

2501001/3500-2/311/91500x15101/30-2/93、单纯形法单纯形表81注意：单纯形法中，

1.每一步运算只能用矩阵初等行变换；

2.表中第3列的数总应保持非负（≥0）；

3.当所有检验数均非正（≤0）时，得到最优单纯形表。3.线性规划

多解情况

线性规划问题可能存在无穷多解的情况，这时，利用单纯形表亦可求出。例

Max

z=x1+5x2

+4x3

-x5

-2x6

s.t.

x1+2x2

+3x3

+x5

=152x1

+x2

+5x3

+x6=20

x1

+2x2+4x3

+x4

=26

x1,x2,x3,x4,x5,x6

≥0用单纯形法求解得到解为

x’＝(0,15/7,25/7,52/7,0,0)T由于x1的检验数为零，可继续迭代，继续求解另一解为x”＝(25/3,0,0,11,10/3,0)T于是x’，x”线段上的任一点均为最优解。此线性规划的最优解可表示为：

x=

x’+(1-)x”，其中[01]无有限最优解的情况

线性规划问题可能存在无有限最优解（目标函数取向+）的情况。这时，利用单纯形表亦可得出此结论。例

Max

z=15x1+18x2

－2x3

+5x5

s.t.

-3x1-12x2

+x3

=-81-2x1

-(22/3)x2

+x4=-137/3-6x2

+x5=-30

x1,x2,x3,x4,x5

≥0用单纯形法求解得到

表中x3的检验数大于零，而其对应的约束矩阵元素均非正，说明此线性规划无有限最优解。

注意：单纯形法中1、每一步运算只能用矩阵初等行变换；

2、表中第3列(b列)的数总应保持非负（≥0）；

3、当所有检验数均非正（≤0）时，得到最优单纯形表。

4、当最优单纯形表存在非基变量对应的检验数为零时，可能存在无穷多解；Maxz=c1x1+c2x2+…+cnxn

s.t.

a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn

=b2...

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn

≥0§1.4初始基本可行解的确定大M法：引入人工变量xn+i

≥0（i=1,…,m）及充分大正数M

。得到：Max

z=c1x1+c2x2+…+cnxn-Mxn+1-…-Mxn+m

s.t.

a11x1+a12x2+…+a1nxn

+xn+1

=b1a21x1+a22x2+…+a2nxn+xn+2=b2...am1x1+am2x2+…+amnxn+xn+m=bm

x1，x2，…，xn

，xn+1，…，xn+m

≥0

Maxz=5x1+2x2+3x3-x4-Mx5-Mx6

s.t.

x1+2x2+3x3+x5

=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4

=26

x1,x2,x3,x4,x5,x6

≥0大M法问题(LP-M）大M法

（LP-M）得到最优解：(25/3，10/3，0，11)T

最优目标值：112/3显然，xj

=0j=1,…,n;

xn+i=bi

i=1,…,m

是基本可行解。对应的基是单位矩阵。结论：若得到的最优解满足

xn+i=0

i=1,…,m

则是原问题的最优解；否则，原问题无可行解。两阶段法：

引入人工变量xn+i

≥0，i=1,…,m；构造:Maxz=-xn+1

-xn+2

-…-xn+m

s.t.

a11x1+a12x2+…+a1nxn+xn+1

=b1

a21x1+a22x2+…+a2nxn+xn+2

=b2...

am1x1+am2x2+…+amnxn+xn+m

=bmx1,x2...

xn,xn+1,…,xn+m

≥0第一阶段求解上述问题：显然，xj=0j=1,…,n;

xn+i=bi

i=1,…,m

是基本可行解,它对应的基是单位矩阵。

Maxz=5x1+2x2+3x3-x4-Mx5-Mx6

s.t.

x1+2x2+3x3+x5

=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4

=26

x1,x2,x3,x4,x5,x6

≥0两阶段法：第一阶段问题（LP-1）

Max

z=-x5

-x6

s.t.

x1+2x2

+3x3

+x5

=152x1

+x2

+5x3

+x6=20

x1

+2x2+4x3

+x4

=26

x1,x2,x3,x4,x5,x6

≥0第一阶段(LP-1）

得到原问题的基本可行解:(0，15/7，25/7，52/7)T第二阶段把基本可行解填入表中

得到原问题的最优解:(25/3，10/3，0，11)T最优目标值：112/3合理利用线材问题：如何下料使用材最少。配料问题：在原料供应量的限制下如何获取最大利润。投资问题：从投资项目中选取方案，使投资回报最大。5.线性规划应用(选学)建模一、线性规划---产品生产计划：合理利用人力、物力、财力等，使获利最大。劳动力安排：用最少的劳动力来满足工作的需要。运输问题：如何制定调运方案，使总运费最小。

数学规划的建模有许多共同点，要遵循下列原则：

(1)容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。

(2)容易查找模型中的错误。这个原则的目的显然与(1)相关。常出现的错误有：书写错误和公式错误。

(3)容易求解。对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑。建立线性规划模型的过程可以分为四个步骤：

(1)设立决策变量；

(2)明确约束条件并用决策变量的线性等式或不等式表示；

(3)用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）；

(4)根据决策变量的物理性质研究变量是否有非负性。例2.12：某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：

人力资源分配的问题设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?解：设xi

表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6

约束条件：s.t.

x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0人力资源分配的问题例2.13:某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？套裁下料问题解:考虑下列各种下料方案（按一种逻辑顺序给出）把各种下料方案按剩余料头从小到大顺序列出假设x1,x2,x3,x4,x5

分别为上面前5种方案下料的原材料根数。我们建立如下的数学模型。目标函数：

Min

x1+x2+x3+x4+x5

约束条件：

s.t.

x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0套裁下料问题

例2.14:明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？生产计划的问题解：设x1,x2,x3

分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5

分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。生产计划的问题

求xi

的利润:利润=售价-各成本之和可得到

xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。这样我们建立如下数学模型：目标函数:

Max15x1+10x2+7x3+13x4+9x5

约束条件：

s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0生产计划的问题

例2.15:永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B

两道工序加工。假设有两种规格的设备A1、A2能完成A

工序；有三种规格的设备B1、B2、B3能完成B

工序。Ⅰ可在A、B的任何规格的设备上加工；Ⅱ可在任意规格的A设备上加工，但对B工序,只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？

生产计划的问题解：设xijk

表示第i

种产品，在第j

种工序上的第k

种设备上加工的数量.利润=[（销售单价-原料单价）×产品件数]之和-（每台时的设备费用×设备实际使用的总台时数）之和。

生产计划的问题这样我们建立如下的数学模型:Max

0.75x111+0.7753x112+1.15x211+1.3611x212

+1.9148x312-0.375x121-0.5x221-0.4475x122

-1.2304x322-0.35x123

s.t

5x111+10x211≤6000

（设备A1

）

7x112+9x212+12x312≤10000（设备A2

）

6x121+8x221≤4000(设备B1

）

4x122+11x322≤700(设备B2

）

7x123≤4000

（设备B3

）生产计划的问题x111+x112-x121-x122-x123=0(Ⅰ产品在A、B工序加工的数量相等）x211+x212-x221=0

(Ⅱ产品在A、B工序加工的数量相等）x312-x322=0(Ⅲ产品在A、B工序加工的数量相等）xijk≥0,i=1,2,3;j=1,2;k=1,2,3

生产计划的问题例2.14:某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？配料问题配料问题

解：设xij

表示第i

种（甲、乙、丙）产品中原料j的含量。这样我们建立数学模型时，要考虑：

对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，x32，x33；对于原料1：x11，x21，x31；对于原料2：x12，x22，x32；对于原料3：x13，x23，x33；目标函数：

利润最大，利润=收入-原料支出

约束条件：规格要求4个；

供应量限制3个。

Max

z=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

配料问题s.t.0.5x11-0.5x12-0.5x13≥0

（原材料1不少于50%）

-0.25x11+0.75x12-0.25x13≤0

（原材料2不超过25%）

0.75x21-0.25x22-0.25x23≥0

（原材料1不少于25%）

-0.5x21+0.5x22-0.5x23≤0

（原材料2不超过50%）

x11+x21+x31≤100(供应量限制）

x12+x22+x32≤100(供应量限制）

x13+x23+x33≤60(供应量限制）

xij≥0,i=1,2,3;j=1,2,3配料问题

投资