运筹学课件(线性规划)

线性规划(LinearProgramming)线性规划问题及其数学模型线性规划问题的求解方法线性规划的图解法线性规划的单纯形法单纯形法的进一步讨论线性规划模型的应用一、线性规划问题及其数学模型（一）、问题的提出

为了完成一项任务或达到一定的目的，怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的，这个过程就是规划。例一、有一正方形铁皮，如何截取x使容积为最大？xa此为无约束极值问题

设备产品ABCD利润（元）

Ⅰ

2

1

4

0

2

Ⅱ

2

2

0

4

3有效台时12

81612

例二、已知资料如下表所示，问如何安排生产才能使利润最大？或如何考虑利润大，产品好销。模型maxZ=2x1+3x2

x1≥0,x2≥0s.t.

2x1+2x2≤12x1+2x2≤84x1≤164x2≤12此为带约束的极值问题（二）、数学模型1、问题中总有未知的变量，需要我们去解决。

要求：有目标函数及约束条件，一般有非负条件存在，由此组成规划数学模型。

如果在规划问题的数学模型中，变量是连续的（数值取实数）其目标函数是有关线性函数（一次方），约束条件是有关变量的线性等式或不等式，这样，规划问题的数学模型是线性的。反之，就是非线性的规划问题（其中一个条件符合即可）。2、线性规划数学模型的一般形式目标函数：约束条件：①②③12也可以记为如下形式：目标函数：约束条件：如将上例用表格表示如下：设变量

产品j设备i

有效台时

利润向量形式：矩阵形式：3、规划类型规划确定型随机型静态规划动态规划线性规划非线性规划整数规划非整数规划整数规划非整数规划二、线性规划问题的求解方法（一）、求解方法一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但需将一般形式变成标准形式（二）、线性规划问题的解1、解的概念

⑴可行解：满足约束条件②、③的解为可行解。所有解的集合为可行解的集或可行域。

⑵最优解：使目标函数达到最大值的可行解。

⑶基：B是矩阵A中m×n阶非奇异子矩阵（∣B∣≠0），则B是一个基。则称Pj

(j=12……m)为基向量。∴Xj

为基变量，否则为非基变量。5

⑷基本解：满足条件②，但不满足条件③的所有解，最多为个。

⑸基本可行解：满足非负约束条件的基本解，简称基可行解。

⑹可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解2、解的基本定理⑴线性规划问题的可行域是凸集（凸多边形）。凸集凸集不是凸集极点⑵最优解一定是在凸集的某一定点实现（顶点数目不超过个）⑶先找一个基本可行解，与周围顶点比较，如不是最大，继续比较，直到找出最大为止。3、解的情况唯一解无穷解无界解无可行解有最优解无最优解三、图解法

建立直角坐标，图中阴影部分及边界上的点均为其解，是由约束条件来反映的。例一、⑴⑵⑶⑷012345678123456⑴⑵⑶⑷作图∴最优解：x1=4x2=2有唯一最优解，Z=14x2

x1(42)例二、例三、⑴⑵⑶无穷多最优解⑴⑵无界解x1x1x2

x2

例三、⑴⑵x1x2

无可行解练习习题效产品机床率AB机床台数

Ⅰ3040

40

Ⅱ5530

40

Ⅲ2337

20

2、

某车间用三种不同型号的机床Ⅰ、Ⅱ、Ⅲ，加工A、B两种零件，机床台数、生产效率如表所示。问如何合理安排机床的加工任务，才能使生产的零件总数最多？1、某工厂生产A1、A2

两种产品，每件可获利润15、20元。每个产品都经过三道工序，资料如表所示。工厂应如何安排生产计划使获得的总利润最多？试写出此问题的数学模型。工产品工序时A1A2可用工时

Ⅰ

3

2

800

Ⅱ

2

3

800

Ⅲ

1

1

3503、用图解法求解下面的线性规划问题：四、单纯形法（一）、基本思想将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。（二）、线性规划模型的标准形式1、标准形式2、特征：

⑴.目标函数为求极大值，也可以用求极小值；

⑵.所有约束条件（非负条件除外）都是等式，右端常数项为非负；

⑶.变量为非负。3、转换方式：

⑴.目标函数的转换如果是求极小值即，则可将目标函数乘以（－1），可化为求极大值问题。也就是：令，可得到上式。即⑵.约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变量⑶.变量的变换若存在取值无约束的变量，可令其中：例一、将下列线性规划问题化为标准形式为无约束（无非负限制）

解:

用替换，且，引入变量将第3个约束方程两边乘以（－1）将极小值问题反号，变为求极大值标准形式如下：例二、将线性规划问题化为标准型为无约束解：（三）、单纯形法例一、变成标准型约束方程的系数矩阵为基变量为非基变量I为单位矩阵且线性独立令：则：∴基本可行解为（001281612）

此时，Z=0然后，找另一个基本可行解。即将非基变量换入基变量中，但保证其余的非负。如此循环下去，直到找到最优解为止。注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。其步骤总结如下：找出一个初始可行解是否最优转移到另一个目标函数（找更大的基本可行解）最优解是否循环直到找出为止，核心是：变量迭代当时，为换入变量确定换出变量为换出变量接下来有下式：用高斯法，将的系数列向量换为单位列向量，其步骤是：结果是：代入目标函数：有正系数表明：还有潜力可挖，没有达到最大值；有负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当时，即不再利用这些资源。此时：令得到另一个基本可行解

（0，3，6，2，16，0）如此循环进行，直到找到最优为止。本例最优解为：（4，2，0，0，0，4）（四）、单纯形表例题：判定标准：若求

或cj230000cBxBbx1x2x3x4x5x60000x3x4x5x61281612221000120100400010040001-Z0

23000012/28/2－12/4cj230000cBxBbx1x2x3x4x5x6000x3x4x516

400010

-Z3x23010001/42620100-1/2100100-1/2cj

230000cBxBbx1x2x3x4x5x60003x3x4x5x262163

20100-1/210010-1/2400010010001/4-Z-9

20000-3/46/2216/4－cj230000cBxBbx1x2x3x4x5x60203x3x1x5x22283001-201/210010-1/2000-412010001/44－412-Z-13000-201/4据摄动原理将下标大的换出cj230000cBxBbx1x2x3x4x5x60203x3x1x6

x2

0442000-1-1/401100

1/40

000-21/2

10411/2

-1/80-Z-14000-3/2-1/80cj230000cBxBbx1x2x3x4x5x60203x3x1x5x22283001-201/210010-1/2000-412010001/44－412-Z-13000-201/4据摄动原理将下标大的换出五、单纯形法的进一步讨论（一）、模型情况

变量：xj≥0xj≤0xj无约束结1、组成约束条件：≥=≤b

目标函数：maxmin果2、变量xj≤0令xj′=-xj，xj′≥0

xj≥0不处理

xj

无约束令xj=xj′－

xj″,xj′≥0,xj″≥0唯一最优无穷最优无界解无可行解3、约束条件：加入松弛变量加入人工变量先减去再加上例：4、目标函数：max,min

设规划模型约束条件为，需加入人工变量，而得到一个m×m的单位矩阵，即基变量组合。因人工变量为虚拟变量，且存在于初始基本可行解中，需要将它们从基变量中替换出来。若基变量中不含有非零的人工变量，表示原问题优解。若当，而还有人工变量（非零）时，则表示原问题无可行解。加入人工变量后，目的是找到一个单位向量，叫人工基。其目标价值系数要确定，但不能影响目标函数的取值。一般可采用两种方法处理：大M法和两阶段法。

⑴.大M法：即假定人工变量在目标函数中的系数为M（任意大正数），如果是求极大值，需加-M；如果是求极小值，需加M。如基变量中还存在M，就不能实现极值。cj-31100MMcBxBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011-Z-3-6M1-M1-3M0M00cBxBbx1x2x3x4x5x6x70x4103-20100-1－Mx610100-11-211x31-2010001－-Z-11-M00M03M-1cj-31100MMcBxBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2－1x31-2010001－-Z-2-10001M-1M+1cBxBbx1x2x3x4x5x6x7-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3-Z20001/31/3M-1/3M-2/3∴最优解为（4190000），Z=－2

⑵.两阶段法：用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。

第一阶段：在原线性规划问题中加入人工变量，构造如下模型：对上述模型求解（单纯形法），若W=0,说明问题存在基本可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。例：第一阶段cj0000011cBxBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-20100011-Z46-1-301000x4103-20100-1－1x610100-11-210x31-2010001－-Z10-1001030x4123001-22-50x210100-11-20x31-2010000-Z00000011cj-31100cBxBbx1x2x3x4x50x4123001-241x210100-1－1x31-20100－-Z-2-10001-3x141001/3-2/31x210100-11x390012/3-4/3-Z00001/31/3第二阶段∴最优解为（41900），目标函数Z=-26、无可行解的判断：运算到检验数全负为止，仍含有仍工变量，无可行解。

8、退化：即计算出的θ（用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量等于零，这就是退化（会产生退化解）。虽任意换出变量，目标函数值不变，但此时不同的基却表示为同一顶点，其特例是永远达不到最优解。需作如下处理：

⑴.选中下标最小的非基变量为换出变量；

⑵.当θ中出现两个以上最小值时，选下标最大的基变量为换出变量。（二）、线性规划小结建立模型个数取值右端项等式或不等式极大或极小新加变量系数两个三个以上xj≥0xj无约束xj

≤0

bi

≥0bi<0≤=≥maxZminZxs

xa求解图解法、单纯形法单纯形法不处理令xj

=

x′-x″

x′≥0x″≥0令

xj

=-xj不处理约束条件两端同乘以-1加松弛变量xs加入人工变量xa减去xa加入xs不处理令z′=-ZminZ=－maxz′0-M根据上表列出初始单纯形表AA六、线性规划模型的应用一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。

⑴.要求解问题的目标函数能用数值指标来反映，且为线性函数；

⑵.存在着多种方案；

⑶.要求达到的目标是