第1章 线性规划和单纯形法

上课须知理论课每周4节，实践课每周上机；考查，五级分制：优、良、中、及格、不及格；课后及时复习与预习；独立自主作业，课代表在上课前收取，按学号整理；平时成绩=作业+课堂考查；听到下课铃声才能离开教室。参考教材第1章线性规划模型和单纯形法§1.1什么是线性规划§1.2线性规划的图解法§1.3单纯形法§1.4人工变量法第1章线性规划模型和单纯形法§1.1什么是线性规划线性的约束线性的目标函数例1：达能公司生产I、II两种饼干，需用A、B、C三种类型的设备。每吨饼干在生产中需要占用设备的工时数，每吨饼干可以获得的利润以及三种设备可利用的工时数如下表所示：

饼干I饼干II工时数设备A（搅拌机）3515设备B（成形机）215设备C（烘箱）2211利润（百元/吨）54

§1.1什么是线性规划

§1.1什么是线性规划

问题：公司应如何安排生产可获得最大的利润？解：设变量xi为第i种产品的每天的生产量（i＝1,2）。根据前面分析，可以建立如下的线性规划模型：

一般形式

目标函数：

约束条件：

§1.1什么是线性规划标准形式目标函数：

约束条件：§1.1什么是线性规划线性规划的标准形式有四个特点：§1.1

什么是线性规划目标最小化、等式约束、非负决策变量、非负右端项一般形式四类变换标准形式

§1.1什么是线性规划例1（续）将例1化为标准式。（怎样化为标准形？教材第14-16页有四点！）§1.1什么是线性规划例2：服装厂应如何安排生产可获得最大的总利润？

男式女式生产能力（小时）裁剪12/3900缝纫1/21/3300检验1/81/4100利润（元/件）58

解：（1）决策变量

§1.1什么是线性规划设变量x1

为男式童装的生产件数，变量x2

为女式童装的生产件数。（2）约束条件（3）目标函数

LP（LinearProgramming）模型§1.1什么是线性规划（标准化）Return

§1.1

什么是线性规划

§1.2线性规划的图解法

对于只有两个变量的线性规划问题，可以在二维直角坐标平面上用图解法求解。

用图解法求解时不必化成标准形。

§1.2线性规划的图解法

图解法求解步骤：

第(1)步以决策变量为坐标建立直角坐标系。

§1.2线性规划的图解法

第（2）步

确定每个约束条件决定的半平面，并绘出各约束半平面交集

(或=

）。若

存在（

称为可行集或可行域，点x

称为线性规划的可行解）转第（3）步；若不存在，该线性规划问题无可行解。

§1.2线性规划的图解法

第（3）步

作一条目标函数的等值线，确定目标值增加（或减少）的方向；平移等值线，达到既与

有交点又不可能使值再增加（或减少）的位置(或交于无穷远处，称无有限最优解）。若有交点时，此等值线与

的交点即最优解（一个或多个），目标函数的值即最优值。

§1.2线性规划的图解法目标函数等值线的确定例1（续）目标函数

的等值线用下列方法来确定：

在坐标平面上找出点方向OM是目标函数z增加的方向

OM的直线是目标函数z的等值线

§1.2

线性规划的图解法

对求最大的问题把等值线向目标函数增加的方向推；

对求最小的问题把等值线向目标函数减少的方向推。例1（续）

§1.2线性规划的图解法§1.2

线性规划的图解法最优解:§1.2

线性规划的图解法最优值:例2（续）

§1.2

线性规划的图解法§1.2

线性规划的图解法§1.2

线性规划的图解法最优解:最优值:

§1.2

线性规划的图解法例3

§1.2

线性规划的图解法

§1.2

线性规划的图解法例4

§1.2

线性规划的图解法

§1.2

线性规划的图解法例5

§1.2

线性规划的图解法

§1.2

线性规划的图解法例6

§1.2

线性规划的图解法多个最优解：在例6中，线段上的每一点都是最优解，最优解的全体可以表示为：

极点(端点)是和

最优值:§1.2

线性规划的图解法线性规划的可行域和最优解有以下几种情况：

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

有唯一的最优解；

有无穷多个最优解；

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

有唯一的最优解；

§1.2

线性规划的图解法

有无穷多个最优解；

无有限的最优解

（目标值无界）

3.可行域为空集

无可行解§1.2

线性规划的图解法§1.2

线性规划的图解法可行域和最优解

Return§1.3

单纯形法

例1（续）

变量x3

,x4,x5称为基本变量，基本变量的全体（用B表示）称为一个（组）基；其它的变量称为非基本变量（用N表示）。

（1）基本变量：x3=15,x4=5/2,x5=11/2

（2）非基本变量：x1=0,x2=0

目标值：z1=0§1.3

单纯形法

§1.3

单纯形法

例1（续）将例1化为标准式。§1.3

单纯形法

x1x2x3x4x5右端z1540000x33510015x4210105x52200111“单纯形表”

单纯形法步骤：（1）化为标准形；（2）找出一个基；（3）检验数（目标函数的系数）都是≤0时，已经得到最优解；（4）检验数有>0时，由最大的检验数计算比值；（5）由最小的比值换基，直到检验数都是≤0，从而得到最优解。§1.3

单纯形法

在计算比值时要注意两点：（1）检验数有

>0时，由最大的检验数计算比值时，只对正的系数计算；（2）如果最大的检验数相应的系数都是≤

0，那么不能计算比值。这时无最优解，即最优解不存在。这是对应图解法中“可行域无界——目标函数无界”的情况。§1.3

单纯形法

§1.3

单纯形法

x1x2x3x4x5右端比z1540000x3251001515/3=5x42101055/2x5220011111/2§1.3

单纯形法

x1x2x3x4x5右端比z103/20-5/20-25/2x307/21-3/2015/215/7x111/201/205/25x5010-1166基本变量:

非基本变量:

目标值:§1.3

单纯形法

§1.3

单纯形法

x1x2x3x4x5右端z100-3/7-13/70-110/7x2012/7-3/7015/7x110-1/75/7010/7x5001-2/7-4/7127/7最优解、最优值:原问题的最优解、最优值:

§1.3

单纯形法

例7用单纯形求下列线性规划。§1.3

单纯形法

转化为标准形

§1.3

单纯形法

§1.3

单纯形法

x1x2x3x4x5x6右端比z16-330000x421010084x5-4-2301014*x61-210011818§1.3

单纯形法

x1x2x3x4x5x6右端比z10-63-300-24x111/201/2004*x50032103010x60-5/21-1/2011414§1.3

单纯形法

x1x2x3x4x5x6右端z10-60-5-10-54x111/201/2004x30012/31/3010x60-5/20-7/6-1/314最优解、最优值:原问题的最优解、最优值:

§1.3

单纯形法

§1.3

单纯形法例8

某工厂有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。问：工厂应如何安排生产可获得最大的总利润？请用图解法和单纯形两种方法解这个问题。

产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500

解：x1-甲产品数量，x2-乙产品数量

§1.3

单纯形法

§1.3

单纯形法

转化为标准形：§1.3

单纯形法

§1.3

单纯形法

x1x2x3x4x5右端比z1150025000000x3321006565/2x4210104040/1x5030017575/3§1.3

单纯形法

x1x2x3x4x5右端比z11500000-2500/3-62500x33010-2/31515/3x42001-1/31515/2x201001/325*§1.3

单纯形法

x1x2x3x4x5右端z100-5000-500-70000x1101/30-2/95x400-2/311/95x201001/325最优解、最优值:原问题的最优解、最优值:

§1.3

单纯形法

可行解、可行域最优解、最优值基、基变量、非基变量注意复习下列概念：§1.3

单纯形法

两个习题：1.

均无符号限制

§1.3

单纯形法

参考答案：化标准形设z1=-zx1=y1-y2，

x2=y3-y4，x3=y5-y6

所以z1=-(y1-y2)-2(y3-y4)+(y5-y6)再加入三个松弛变量y7,y8,y9

§1.3

单纯形法

（标准形）

最优解：§1.3

单纯形法

2

§1.3

单纯形法

参考答案：（标准形）最优解：（0,0,1.5,0,8,0）

Return§1.3

单纯形法

人工变量法基本思想（见下例）例9§1.4

人工变量法

首先标准化§1.4

人工变量法

第一阶段:辅助问题

增加人工变量R1和R2

，用单纯形法求解。§1.4

人工变量法

辅助问题最优解及最优值:x1*=2,x2*=0,S2*=0,S3*=1R1*=0,R2*=0,f*=0

原来问题的可行解:

x1*=2,x2*=0,S2*=0,S3*=1§1.4

人工变量法第二阶段:把第一阶段最后的一张（最优）单纯形表的目标函数f-行换成原来的目标函数z-行，用单纯形法求解。§1.4

人工变量法例10§1.4

人工变量法解：标准形§1.4

人工变量法第一阶段:辅助问题增加人工变量R1和R3§1.4

人工变量法§1.4

人工变量法x1x2x3S1S2R1R3右端f00000-1-1015-3-101015S25-61001002011100015§1.4

人工变量法x1x2x3S1S2R1R3右端

比f2-2-100020R11-3-1010153S25-610010020*R311100015565§1.4

人工变量法x1x2x3S1S2R1R3右端

比f4/501/50-6/502x21/51-3/5-1/501/503*S231/5032/5-6/516/50385.9R34/501/50-1/5121.28/58/5§1.4

人工变量法x1x2x3S1S2R1R3右端

f00000-1-10x21/210-1/801/83/815/4S2300-212-430x31/2011/80-1/85/85/4最优解、最优值:原问题的最优解、最优值:

§1.4

人工变量法

辅助问题最优解:辅助问题最优值:

f*=0原来问题的可行解:x1=0,x2=15/4,x3=5/4,S1=0,S2=30§1.4

人工变量法第二阶段:把第一阶段最后的一张（最优）单纯形表的目标函数f-行换成原来的目标函数z-行。§1.4

人工变量法§1.4

人工变量法x1x2x3S1S2右端

z-23/200-1/80-125/4x21/210-1/8015/4S2300-2130x31/2011/805/4

最优解:

x1*=0,x2*=15/4,x3*=5/4

最优值:

z*=-125/4§1.4

人工变量法例11§1.4

人工变量法解：标准形§1.4

人工变量法第一阶段:辅助问题