第2章-线性规划(第1节)

线性规划问题

线性规划模型

线性规划解的基本概念

线性规划的图解

利用EXCEL求解线性规划模型行解

单纯形法

第二章线性规划（第1节）

某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表2-1所示。该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排计划使该工厂获利最多？资源

产品ⅠⅡ

拥有量

设备12

8台时原材料A

40

16kg原材料B04

12kg§1线性规划问题—例1如何用数学关系式描述这问题，必须考虑：设分别表示计划生产产品Ⅰ、Ⅱ的数量，称它为决策变量；(确定决策变量阶段)生产数量的多少受资源拥有量的限制，这是约

束条件；

(确定约束条件阶段)如何安排生产，使利润最大，这是目标。(确定目

标函数阶段)§1线性规划问题—例1

数学模型§1线性规划问题—例1

目标函数：约束条件：靠近某河流有两个化工厂(见图2-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。

§1线性规划问题—例2图2-1§1线性规划问题—例2第一化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工厂每天排放这种工业污水1.4万立方米。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万立方米。第二化工厂处理工业污水的成本是800元/万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。

建模型之前的分析和计算

设：第一化工厂每天处理工业污水量为x1万立方米，第二化工厂每天处理工业污水量为x2万立方米

§1线性规划问题—例2数学模型§1线性规划问题—例2

目标函数：约束条件：§1线性规划问题—例3

WyndorGlass公司生产高质量的玻璃产品，包括窗和玻璃门，拥有3个工厂。铝框架和硬件在工厂1制造，木质框架在工厂2生产，玻璃生产和产品组装在工厂3完成。现有两种产品：8英尺玻璃门（产品1），4*6英尺框架（产品2）。产品1需要工厂1和工厂3的生产能力，分别是1小时和3小时，而不需要工厂2的生产能力;产品2需要工厂2和工厂3的生产能力，分别是2小时和2小时，而不需要工厂1的生产能力.工厂1每周可用生产时间为4小时,工厂2每周可用生产时间为12小时，工厂3每周可用生产时间为18小时，每批产品1的利润为3（千）美元，每批产品2的利润为5（千）美元.试确定该如何安排产品的生产？建模过程如下：§1线性规划问题—例3

1、确定决策变量。设分别为每周计划生产产品1、2的数量。

2、确定目标函数。公司要求利润最大，设Z表示企业的利润，

则有

3、确定约束条件。该问题有有三个工厂的生产能力限制，据此

可建立三种资源约束如下：

工厂1：

工厂2：

工厂3：

可得上述问题的数学模型为：§1线性规划问题—例3§2线性规划模型

线性规划模型的一般形式目标函数：约束条件：

线性规划模型的标准形式目标函数：约束条件：§2线性规划解的基本概念—1

可行解。凡是满足所有约束条件的所有解成为可行解。所有的可行解构成可行解域，简称可行域。基本解。所有约束条件直线的交点对应的解称为基本解。基本可行解。位于可行解域边界上的约束条件直线的交点对应的解。最优解。凡使得目标函数值达到最优（最大或最小）的可行解成为最优解。

这里介绍一下线性规划解的几个基本概念：最优解可行域目标函数线460x1x2§3线性规划解的基本概念—29基可行解本解基本解线性规划的可行域是凸集线性规划的最优解在极点上凸集凸集不是凸集极点

可行域的性质：最优解可行域目标函数线460x1x2§4线性规划的图解法9基可行解本解基本解§5利用EXCEL求解线性规划模型这里以线性规划模型3为例，来讲解利用EXCEL求解的一般过程和方法。其规划模型如下：

§5利用EXCEL求解线性规划模型（练习1）练1：明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间，已知生产单位产品需要各车间的工作时间及各车间的资源限制如下表2-2所示。另外，该工厂每生产一件产品甲可获利23元，每生产一件产品乙可获利25元，每生产一件产品丙可获利22元，问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？数学模型

目标函数：约束条件：§5利用EXCEL求解线性规划模型（练习1）§5利用EXCEL求解线性规划模型（练习2）练2：某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省件？数学模型

目标函数：约束条件：§5利用EXCEL求解线性规划模型（练习2）6.1单纯形法的求解思路6.2单纯形法求解过程的应用举例6.3单纯形表6.4单纯形的经济信息§6单纯形法(重点、难点)一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。这样问题就得到了最优解，先举一例来说明。§6.1单纯形法求解线性规划的思路

以例1来讨论如何用单纯形法求解。通过引入松弛变量将例1的数模化为标准型：§6.1单纯形法求解线过程的应用例

需要注意的是，如果数模的目标函数是Min型，则要转化为Max型。如目标函数由于，令则原目标函数化为Max型为：

约束方程(2-2)式的系数矩阵从(2-2)式中可以看到x3,x4,x5的系数列向量

P3,P4,P5是线性独立的，这些向量构成一个基

对应于B的变量x3,x4,x5为基变量.

从(2-2)式中可以得到（2-3）式

将(2-3)式代入目标函数(2-1)

得到当令非基变量x1=x2=0，便得到z=0。这时得到一个基可行解X(0)X(0)=(0,0,8,16,12)T

这个基可行解表示：工厂没有安排生产产品Ⅰ、Ⅱ；资源都没有被利用，所以工厂的利润指标z=0。

第一步：确定初始基本可行解从分析目标函数的表达式(2-4)可以看到非基变量x1,x2(即没有安排生产产品Ⅰ，Ⅱ)的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品Ⅰ或Ⅱ，就可以使工厂的利润指标增加。所以只要在目标函数(2-4)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。

如何确定换入，换出变量一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。现分析(2-3)式，当将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的都是非负，即x3,x4,x5≥0。第二步：确定入基变量与出基变量

当x1=0,由(2-3)式得到

x2取何值时，才能满足非负要求？

从(2-5)式中可以看出，只有选择x2=min(8/2,-,12/4)=3时，才能使(2-5)式成立。因当x2=3时，基变量x5=0，这就决定用x2去替换x5。

以上数学描述说明了每生产一件产品Ⅱ，需要用掉各种资源数为(2，0，4)。由这些资源中的薄弱环节，就能确定产品Ⅱ的产量。这里就是由原材料B的数量确定了产品Ⅱ的产量x2=12/4=3件。

为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将(2-3)中x2的位置与x5的位置对换。得到

用高斯消去法将(2-6)式中x2的系数列向量变换为单位列向量。其运算步骤是：③′=③/4；①′=①-2×③′;②′=②,并将结果仍按原顺序排列有：

再将(2-7)式代入目标函数(2-1)式得到

第三步：确定新解从目标函数的表达式(2-8)中可以看到，非基变量x1的系数是正的，说明目标函数值还可以增大，X(1)还不是最优解。于是再用上述方法，确定换入、换出变量，继续迭代，再得到另一个基可行解X(2)X(2)=(2,3,0,8,0)T再经过一次迭代，再得到一个基可行解X(3)X(3)=(4,2,0,0,4)T而这时得到目标函数的表达式是：z=14-1.5x3-0.125x4(2-9)第四步：迭代再检查(2-9)式，可见到所有非基变量x3,x4的系数都是负数。这说明若要用剩余资源x3,x4，就必须支付附加费用。所以当x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以X(3)是最优解。即当产品Ⅰ生产4件，产品Ⅱ生产2件，工厂才能得到最大利润。

第五步：确定最优解通过上例，可以了解利用单纯形法求解线性规划问题的思路。现将每步迭代得到的结果与图解法做一对比，其几何意义就很清楚了。原例1的线性规划问题是二维的，即两个变量x1,x2；当加入松弛变量x3,x4,x5后，变换为高维的。这时可以想象，满足所有约束条件的可行域是高维空间的凸多面体(凸集)。这凸多面体上的顶点，就是基可行解。初始基可行解X(0)=(0,0,8,16,12)T就相当于图2-2中的原点(0，0)，X(1)=(0,3,2,16,0)T相当于对应图解法中的Q4点(0，3)；X(2)=(2，3，0，8，0)T相当于图解法中的Q3点(2，3)；最优解X(3)=(4，2，0，0，4)T相当于图解法中的Q2点(4，2)。从初始基可行解X(0)开始迭代，依次得到X(1)，X(2)，X(3)。这相当于图解法中的目标函数平移时，从0点开始，首先碰到Q4，然后碰到Q3，最后达到Q2。下面讨论一般线性规划问题的求解。

为了便于理解计算关系，现设计一种计算表，称为单纯形表。下面用例1的来