线性规划-运筹学

1、1第一章第一章 线性规划线性规划 ( Linear Programming)1 1 线性规划问题及其数学模型线性规划问题及其数学模型本节重点：本节重点： 线性规划模型结构及特点（了解）线性规划模型结构及特点（了解） 线性规划解的存在情况（理解）线性规划解的存在情况（理解） 线性规划标准模型（掌握）线性规划标准模型（掌握） 线性规划解的基本概念（掌握）线性规划解的基本概念（掌握）21.1 1.1 问题的提出问题的提出 例例1某工厂计划期内要安排生产某工厂计划期内要安排生产、两种产品，两种产品，已知生产单位产品所需的设备台时和已知生产单位产品所需的设备台时和 A、B 两种原材两种原材料的消耗，以及

2、可获利润如表所示，问应如何安排计料的消耗，以及可获利润如表所示，问应如何安排计划使该工厂获利最多？划使该工厂获利最多？x1x2可利用资源可利用资源设备设备原材料原材料A原材料原材料润利润23？元？元3 设设 x1、x2 分别表示计划期内产品分别表示计划期内产品、的产量，的产量，建立数学模型：建立数学模型：约束条件约束条件（Subject to）目标函数目标函数0, 012416482. .32max21212121xxxxxxtsxxZ4 例例 2靠近某河流有两个化工厂（见图），流经靠近某河流有两个化工厂（见图），流经第一化工厂的河流流量为每天第一化工厂的河流流量为每

3、天 500 万万m3，在两个工厂，在两个工厂之间有一条流量为每天之间有一条流量为每天 200 万万m3 的支流。第一化工厂的支流。第一化工厂每天排放含有某种有害物质的工业污水每天排放含有某种有害物质的工业污水 2 万万m3，第二，第二化工厂每天排放这种工业污水化工厂每天排放这种工业污水 1.4 万万m3。从第一化工。从第一化工厂排出的工业污水流到第二化工厂以前，有厂排出的工业污水流到第二化工厂以前，有 20% 可以可以自然净化。根据环保要求，河流中工业污水的含量不自然净化。根据环保要求，河流中工业污水的含量不应大于应大于0.2%。这两个工厂都需各自处理一部分工业污。这两个工厂都需各自处理一部分

4、工业污水。第一化工厂处理工业污水的成本是水。第一化工厂处理工业污水的成本是1000元元/万万m3，第二化工厂处理工业污水的成本是第二化工厂处理工业污水的成本是 800 元元/万万m3。现在。现在要问在满足环保要求的条件下，每厂各应处理多少工要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。业污水，使这两个工厂总的处理工业污水费用最小。5 设设 x1、x2 分别为第一、第二化工厂每天分别为第一、第二化工厂每天处理的工业污水量。处理的工业污水量。 第一化工厂到第二化工厂之间的污水含量第一化工厂到第二化工厂之间的污水含量要不大于要不大于0.2%(2 -(2

5、- x1)/ 50 0 2 / 1000 流经第二化工厂后，河流中的污水含量仍流经第二化工厂后，河流中的污水含量仍不大于不大于0.2%60.8(2 -8(2 - x1) + ( (1. .4-4- x2) / 700 2 / 1000污水处理量限制污水处理量限制x1 2，x2 1. .4 4，x1 0，x2 0目标函数：目标函数：要求两厂用于处理工业污水的费用最小要求两厂用于处理工业污水的费用最小min Z = 1000 x1+800 x2整理得数学模型：整理得数学模型：7 x1 1s.t. 0. .8 8 x1 + x2 1.6.6 x1 2 x2 1.4.4 x1 0，x2 0min Z

6、= 1000 = 1000 x1 + 800 x2 问题：某种物资问题：某种物资,有有m个产地个产地 Ai，i =1，2，m， 可供应量为可供应量为 ai，i =1，2，m，有，有 n 个销地个销地 Bj，j =1，2，n，需要量分别为，需要量分别为 bj，j=1，2，n，从，从 Ai 到到 Bj 运输单位物资运输单位物资的运价为的运价为 cij。求总运费最小的调运方案。求总运费最小的调运方案。例例3 3 运输问题运输问题8 min Z= i=1m j=1ncijxij s.t. j=1nxij ai (i =1,2, ,m)i=1mxij bj (j =1,2, ,n) xij 0 (i =

7、1,2, ,m; j =1,2, ,n) 设设 xij 表示从产地表示从产地 Ai 发往销地发往销地 Bj 的运量，的运量，数学模型为：数学模型为：91. 建模步骤：建模步骤： 明确有待决定的未知变量（决策变量明确有待决定的未知变量（决策变量decision variables） 一般可设变量一般可设变量 表示系统中待确表示系统中待确定的某些量。定的某些量。TnxxxX),(21 明确问题中所有的限制条件（约束条件明确问题中所有的限制条件（约束条件constraints），并用决策变量的关系式来表示。），并用决策变量的关系式来表示。 设置的变量应能够明确完整地描述系统的问题。设置的变量应能够明

8、确完整地描述系统的问题。也可能需要在模型的建立过程中随着分析的进一步深也可能需要在模型的建立过程中随着分析的进一步深入而进行调整。入而进行调整。小结：小结：10 明确目标明确目标(objective function)，用决策变量的关系，用决策变量的关系式表示。式表示。 变量取值限制：变量取值限制：一般变量不能为负数。一般变量不能为负数。2. 线性规划问题的假定线性规划问题的假定(1) 比例性假定比例性假定(proportionality assumption)： 每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。(2) 可加性假定可加性假定(additivity assump

9、tion) 每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。11(3) 连续性假定连续性假定(divisibility assumption) 决策变量取连续值。3. 线性规划问题的共同特征线性规划问题的共同特征(4) 确定性假定确定性假定(certainty assumption) 所有参数都是确定的参数，不包含随机因素。 一组非负决策变量一组非负决策变量（x1，x2，xn）表示某一方）表示某一方案；案； 一组线性等式或线性不等式一组线性等式或线性不等式表示约束条件；表示约束条件； 一个线性函数一个线性函数（称为目标函数）表示要达到的目

10、标。（称为目标函数）表示要达到的目标。根据具体问题，要求根据具体问题，要求目标函数目标函数实现最大化或最小化。实现最大化或最小化。124.4.线性规划模型的一般形式线性规划模型的一般形式 max(min) Z = c1x1 + c2x2 + cnxn (1.1) a11x1 + a12x2 + a1nxn ( = , ) b1 a21x1 + a22x2 + a2nxn ( = , ) b2 s.t. (1 (1.2)2) am1x1 + am2x2 + amnxn ( = , ) bm x1，x2，xn 0 (1.3)131.3 线性规划问题的标准形式线性规划问题的标准形式其中其中bi 0，

11、（，（i =1，2，m） 一般一般 m 0)4 . 1 (0,. .max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz14（1）用求和符号表示）用求和符号表示njxmibxatsxczjinjjijnjjj, 2 , 10, 2 , 1. .max111.3.1标准型的简写形式标准型的简写形式: :15其中：其中：C=（c1，c2，cn）njxbxPtsCXzjnjjj, 2 , 10. .max1nxxxX21mbbbb21mjjjjaaaP21（2）用向量表示）用向量表示16 称称 A 为约

12、束条件的为约束条件的 m n 阶阶系数矩阵，一般系数矩阵，一般 A 的的秩为秩为 m。（3）用矩阵描述为）用矩阵描述为0. .maxXbAXtsCXz其中其中),(212212222111211nnmmnnPPPaaaaaaaaaA000017例例4 将下列线性规划模型化为标准型。将下列线性规划模型化为标准型。1.3.2 将一般形式化为标准形式将一般形式化为标准形式 min Z= x1 +2x2 3x3 x1 + x2 + x3 7 s.t. x1 x2 + x3 2 3 x1 + x2 + 2 x3 = 5 x1 0，x2 0，x3为无符号约束为无符号约束(1)18LP问题模型标准化方法：问

13、题模型标准化方法：（1）目标函数最小化）目标函数最小化最大化最大化CXz minZZCXz其中,max（2）不等式约束）不等式约束等式约束等式约束injjijbxa101iniinnjjijxbxxa松弛变量松弛变量injjijbxa101iniinnjjijxbxxa剩余变量剩余变量19（3）变量为负约束、无符号约束）变量为负约束、无符号约束0jx0jjjxxxxj无符号约束无符号约束 0, 0 jjjjjxxxxx （4）某个右端常数）某个右端常数 bk 0将该等式两边均乘以（将该等式两边均乘以（-1），使右端常数项），使右端常数项 b k = - bk 020 解：令解：令x2=-y，x

14、3=u-v，并引入松弛变量，并引入松弛变量s1和和s2，标准型为：标准型为：0,0,0,0,0,005303320552.443max211121111ssvuyxyxsvuyxsvuyxtsvuyxZ0,0053032052.43min2121321321321xxxxxxxxxxtsxxxZ（2）21 可行解可行解1.4 线性规划问题解的概念线性规划问题解的概念满足约满足约束条件束条件（1.5)(1.6)的解的解 X=( x1，x2，xn)T)6 . 1 (0)5 . 1 (. .)4 . 1 (maxXbAXtsCXz线性规划标准型线性规划标准型22如例如例1 1，max Z = 2 =

15、 2x1 1 + 3 + 3x x2 2 s.t. . x1 + 2 x2 + x3 = 84 x1 + x4 = 16 4 x2 +x5 = 12 x1，x2，x3，x4，x5 0 x1x2O4 Q2(4,2)Q1Q3Q43A23 最优解最优解使目标函数（使目标函数（1.4）达到最大值的可行解；）达到最大值的可行解；x1x2O4 Q2(4,2)Q1Q3Q43A24 基基 基向量基向量 基变量基变量XB 非基变量非基变量XN Am n，R(A)=m， A中的中的 m m 阶非奇异子矩阵阶非奇异子矩阵 B ，称为线性规划问题的一个基。，称为线性规划问题的一个基。（|B | 0，B 的各列线性无关

16、）的各列线性无关） x1 + 2 x2 + x3 = 84 x1 + x4 = 16 4 x2 +x5 = 12 B=（p3，p4，p5）XB=(x3, x4, x5)TXN=(x1, x2)T 若若Amn，m n，则至多有则至多有Cnm个基。个基。25 基本解基本解基基BX1=（0, 0, 8, 16, 12）TB1 =（p3，p4，p5），），令所有非基变量为零令所有非基变量为零约束方程组的解约束方程组的解 x1 + 2 x2 + x3 = 84 x1 + x4 = 16 4 x2 +x5 = 12 B2=（p2，p4，p5），），X2=（0, 4, 0, 16, -4）T 基可行解基可行

17、解满足非负条件的基本解。满足非负条件的基本解。 26 至多有至多有 Cnm 个基解，基解的非零分量至多个基解，基解的非零分量至多 m 个，非零分量个数小于个，非零分量个数小于 m 的基解为的基解为退化解退化解。 至多有至多有 Cnm个基可行解，基可行解至多有个基可行解，基可行解至多有m个个正分量。正分量。 可行基可行基 基最优解基最优解 最优基最优基B1 =（p3，p4，p5）X1=(0，0，8，16，12)TB2=( (P P1 1、P P2 2、P P5 5) ) X2=(4，2，0，0，4)T基变量基变量27 上述解的概念中上述解的概念中基解基解和和基可行解基可行解最为重要，各种最为重要

18、，各种解的关系粗略地可用下图表示：解的关系粗略地可用下图表示： 非可行解可行解 基解基可行解最优解282 线性规划问题的几何意义线性规划问题的几何意义本节重点：本节重点： 凸组合的概念（理解）凸组合的概念（理解） 凸集的概念（理解）凸集的概念（理解） 线性规划基本定理（掌握）线性规划基本定理（掌握）292.1 基本概念基本概念凸凸组组合合 设设 X 1，Xk En，若若存存在在1 1，k k，0 0i i1 1，且且i=1ki =1 1，使使 X X= =1 1 X 1+k k X k则则称称X X为为 X 1，X k的的凸凸组组合合。)(X)(XX10121 两 点 连 线两 点 连 线上的

19、任何一点上的任何一点都是这两点的都是这两点的凸组合。凸组合。X1X2X30 设设 K En，若若任任意意两两点点 X1 K，X2 K 的的凸凸组组合合属属于于 K，即即 X = X1+（1- ）X2 K（0 1） 则则称称 K 为为凸凸集集。 凸集凸集任何两个凸集任何两个凸集的交集是凸集的交集是凸集(e)(c)(a)(d)(b)凸集凸集不是凸集不是凸集31 顶点（极点）顶点（极点） 设设 K 是凸集，是凸集，X K，若，若 X 不能用不能用 K 的其它两点的其它两点的凸组合表示，即不存在的凸组合表示，即不存在 X1 K，X2 K ( X1 X2 )，能使能使 X = X1+（1- ）X2 K（

20、0 1）则称则称 X为为 K 的一个顶点。的一个顶点。(a)(b)(c) 32 引理引理1 线性规划问题的可行解线性规划问题的可行解 X = (x1，x2，xn)T 为基可行解的充分必要条件是为基可行解的充分必要条件是X的正分量所对应的的正分量所对应的系数列向量是线性无关的。系数列向量是线性无关的。 定理定理1 若线性规划问题存在可行解，则所有可行解的若线性规划问题存在可行解，则所有可行解的集合集合可行域可行域D = X| AX= b，X 0 是凸集。是凸集。2.2 基本定理基本定理线性规划问题的可行解集是凸集。线性规划问题的可行解集是凸集。33 定理定理2 线性规划问题的基可行解线性规划问题

21、的基可行解 X 对应于可行域对应于可行域 D 的顶点。的顶点。 引理引理2 若若K是有界凸集，则任何一点是有界凸集，则任何一点X K可表示为可表示为K的顶点的凸组合。的顶点的凸组合。图中，图中， X = X 4 + ( 1 ) X 2 (0 1) X 4 = X 1 + ( 1 ) X 3 (0 0(m+1 j n)，则有xj 0，其它非基变量仍为零的可行解，其目标函数值这说明当前解不是最优解。最优性判别定理：最优性判别定理： 对极大化的LP问题，若基可行解对应的检验数 j 0 ( j =1, 2, , n)，则此解是最优解，否则不是最优解。检验数检验数47注意： xj 的检验数是在线性规划模

22、型表示为典式时目标函数中 xj 的系数。 基变量的检验数为零。3.5基变换基变换 求一个改进的、“相邻”的可行基，一个基变量将变成非基变量，一个非基变量将变成基变量。 一般，若 k = maxj |j 0，则取对应的 xk 作为进基变量。 1、进基变量的确定最优解一定在可行域的最优解一定在可行域的顶点（基可行解）得到顶点（基可行解）得到48 2.出基变量的确定xj = 0 ( m+1 j n，j k )，若令 xk 0 ，且要保持基变量 xi 0 ( i =1，2， m )，即000222111kmkmmkkkkxabxxabxxabxkmkmkkkkxabxabxab2211 若所有 aik

23、 0，只要 xk 0即可，问题无界 若存在 aik 049则。比值法量。这种方法称为最小对应的基变量为换出变个约束，第一般，计算labaablklikiki0min 新的基可行解中xk 的取值于是，取 bl 对应的 xl 作为出基变量。新基为 B (1) = ( P1，, Pl-1， Pk ，Pl+1，, Pm )出基变量确定方法出基变量确定方法:)1 (0minmlabaabxlklikikik50 x2= 3 x5 =0012416482. .32max521524132121xxxxxxxxxxtsxxZ，要使 x3 =8 2x2 0 x4 =16 0 x5 =12 4x2 0初始基可行

24、解 X (0) =(0,0,8,16,12)T，x2为进基变量。故第 3 个约束中的 x5 是换出变量。例：新的基 B (1) = (P3, P4, P2)新的解 X (1)=(0, 3, 2, 16, 0)Tx2的系数的系数10040251 3.6 单纯形表单纯形表 将典式的系数和常数项按照一定的规则列在一张表上，并称这种表为线性规划问题的对应于基 B 的单纯形表，简称单纯形表。c1c2clcmcm+1ckcnCBXBbx1x2xlxmxm+1xkxnc1x1b11a1m+1a1k a1nc2x2b21a2m+1a2k a2nclxlbl1alm+1alkalncmxmbm1amm+1amk

25、 amn-Z0000m+1kniibc从此表中可读出的信息？523.7 旋转变换旋转变换 利用矩阵的初等变换将xk的系数向量变为单位向量 （0，0 ， ，1， ，0）T 这种变换称为以 alk 为主元素的旋转变换。第l 行、第 k 列 旋转变换后可得新的单纯形表，由此形式很容易知新的基可行解和非基变量的检验数。 重复以上步骤，直至某X(k)对应的检验数均小于等于零，X(k)就是最优解。53例例5 用单纯形法计算以下线性规划模型。用单纯形法计算以下线性规划模型。0,50212034.3050max21212121xxxxxxtsxxz解：引入松弛变量，化标准型为：解：引入松弛变量，化标准型为：0

26、,50212034.3050max432142132121xxxxxxxxxxtsxxz54cj503000CBXBbx1x2x3x4x3x4120504310210100-Z0503000建立单纯形表格并计算如下：建立单纯形表格并计算如下：*x3x125 11/201/220 011-2-1250050-25*x2x120 011-215 10-1/2 3/2-135000-5-15 检验数全部检验数全部 0，本问题达到最优，本问题达到最优，最优解为：最优解为：x1=15, x2=20z=135055练习：练习：012416482. .32max521524132121xxxxxxxxxxt

27、sxxZ，cj23000CBXBbx1x2x3x4x5x3x4x581612121004001004001000-Z02300056cj23000CBXBbx1x2x3x4x50 x38121000 x416400100 x51204001-Z023000-Z*x3x4x2003301001/421010-1/21640010-92000-3/457cj23000CBXBbx1x2x3x4x50 x321010-1/20 x416400103x2301001/4-Z-92000-3/4-Z*x1x4x220321010-1/2800-412301001/4-1300-201/458cj2300

28、0CBXBbx1x2x3x4x52x121010-1/20 x4800-4123x2301001/4-Z -1300-201/4-Z*x1x5x2203400-21/2141001/402011/8-1/80-1400-3/2-1/80无j 0，故 X*=(4, 2, 0, 4, 0)T Z* =1459小结：小结：单纯形法的计算步骤单纯形法的计算步骤 （1） 找出初始可行基，确定初始基可行解，建立初始单纯形表。 （2） 检验各非基变量 xj 的检验数，若 j 0，j = m+1，n；则已得到最优解，可停止计算，否则，转入下一步。 （4）根据 max j |j 0 = k，确定 xk 为换入变

29、量，按 规则计算 （3）在 j0，j = m+1，n 中，若有某个k 对应 xk 的系数列向量 Pk 0，则此问题是无界解，停止计算。否则，转入下一步。60可确定第 l 行的基变量 xl 为换出变量。转入下一步。lklikikiabaab0min （5）以 alk 为主元素进行迭代（即用高斯消去法或称为旋转变换），把 xk 所对应的列向量变换为 （0，0，1，0）T，将XB 中的第l 个基变量换为 xk，得到新的单纯形表，返回（2）。614 单纯形法的进一步讨论单纯形法的进一步讨论0,12324112.3minLP632131321321321xxxxxxxxxxxtsxxxZ问题用单纯形法求

30、：例引入松弛变量x4，剩余变量x5化为标准型：如何求初始可行基？62 其中第2、3个约束方程中无明显基变量，分别加上人工变量 x6 , x7，得到如下方程组0,12324112. .3max543213153214321321xxxxxxxxxxxxxxxtsxxxZ为构造初始可行基0,123241127654321731653214321xxxxxxxxxxxxxxxxxxx人造基：B =（p4，p6，p7）X(0) = (0，0，0，11，0，3，1)T630,123241123max7654321731653214321321xxxxxxxxxxxxxxxxxxxxxxZ4.1 大大 M

31、 法法在目标函数中加上惩罚项其中 M 为充分大的正数。x6 x7 若加了人工变量的问题，最优解中仍有人工变量不为零，意味着什么？-M -M说明原问题无可行解。说明原问题无可行解。64本例 的典式为：单纯形法迭代过程如下：0,12324112. .)31()1()63 (4max76543217316532143215321xxxxxxxxxxxxxxxxxxxt sMxxMxMxMMZ65cjCBCBbx1x2x3x4x5x6x7 x4x6x70-M-M11311-211000-4120-110-20100013-1-100-M-M4M3-6M -1+M -1+3M0-M00 x4x6x30-

32、M-1103-2010010100-111-2010001+M1-1+M00-M066cj3-1-100-M-MCBCBbx1x2x3x4x5x6x70 x4103-20100-Mx610100-11-1x31-2010001+M1-1+M00-M0 0-1-1x4x2x3123001-210100-11-2010021000-167cj3-1-100-M-MCBCBbx1x2x3x4x5x6x70 x4123001-2-1x210100-1-1x31-2010021000-1 3-1-1x1x2x341001/3-2/310100-190012/3-4/3-2000-1/3-1/3X * =

33、 (4，1，9，0，0)， Z * = -268思考：若目标函数为极小值型时，引入人工变量的目标函数系数应如何设定？4.2 两阶段法两阶段法该最小化问题的最优目标函数值W原问题无可行解，停止计算。原问题有可行解，解得的最优解 ，对应原问题的一个基可行解。= 00以人工变量之和最小化为目标函数，与原约束条件构成线性规划模型 ，运用单纯形法求解（不考虑原问题是否存在基可行解） 。 第一阶段：第一阶段：69以第一阶段的最优解（不含人工变量）为初始解，原目标函数为目标函数，应用单纯形法继续迭代，求原问题的最优解。第二阶段：第二阶段：例：试用两阶段法求解上例。0,12324112. .3min32131

34、321321321xxxxxxxxxxxtsxxxZ70解：在上述线性规划问题的约束方程2，3中加入人工变量，第一阶段的数学模型为：0,12324112min765432173165321432176xxxxxxxxxxxxxxxxxxxxxW化标准型，并用单纯形法求解如下：710,12324112max765432173165321432176xxxxxxxxxxxxxxxxxxxxxWcj00000-1-1CBXBbx1x2x3x4x5x6x70-1-1x4x6x711311-4-2-2101211000-10010001-Z4-6130-100 72cj00000-1-1CBXBbx1x

35、2x3x4x5x6x70-1-1x4x6x711311-4-2-2101211000-10010001-Z4-6130-1000-10 x4 x6x3101130-2-2100011000-10010-1-21-Z10100-10-3x4 x2x3121130-2010001100-2-10210-5-21000000-1-1 X*=（0,1,1,12,0,0,0）T , W = 0(0,1,1,12,0)T是原线性规划问题的基可行解。 73第二阶段运算:cj-31100CBCBbx1x2x3x4x50 x4123001-21x210100-11x31-20100-2-100010 x4410

36、01/3-2/31x210100-11x390012/3-4/320001/31/3 744.3 线性规划问题解的讨论线性规划问题解的讨论x1x2max Z = 2x1+ 4x2 x1 +x2 10 s.t. 2x1 +x2 40 x1 , x2 01、无可行解75人工变量不能从基底换出，此时原线性规划无可行解。-M-2-2M2-M-20+20M0-M04+M2+2M40M001-1-2-112201040 x1x5x3x50102-M-M0042x5x4x3x2x1bXBCBcj110762、退化问题 有基可行解的正分量个数小于约束条件个数 m 的问题。0,060

37、240.43max2121212121xxxxxxxxtsxxZ例：x1x2304060402x1 + x2 60 x1 - x2 = 0 x1 + x2 4077cj3400-MCBXBbx1x2x3x4x50 x340111000 x46021010-Mx501-100103+M4-M0000 x3400210-10 x4600301-23x101-100100700-3-M4x220011/200 x4000-3/213x120101/20-14000-7/20右侧常数中有零时，初始解就是退化解。 单纯形法计算中，计算 值时，有两个以上比值同为最小，这样在下一次迭代中就会出现零值的基变量

38、，出现退化解。 78cj3400-MCBXBbx1x2x3x4x50 x3400210-10 x4600301-23x101-100100700-3-M0 x30001-2/34x2200101/33x1201001/3-140000-7/3最优值同上3、有无穷多最优解的情况、有无穷多最优解的情况最优解中有非基变量的检验数等于零的情况 。 790,1122521553.53max2121212121xxxxxxxxtsxxZ例：x1x2cj35000CBXBbx1x2x3x4x50 x315351000 x45210100 x511220010350005x233/5 11/5000 x427

39、/5 0-1/5100 x554/5 0-2/501-1500-100X(1) = (0, 3, 0, 2, 5)T80X(2)=(10/7, 15/7, 0, 0, 27/7)T全部的最优解：X= X(1)+(1- )X(2) (0 1)cj35000CBXBbx1x2x3x4x55x233/511/5000 x427/50-1/5100 x554/50-2/501-1500-1005x215/7012/7-3/703x110/710-1/75/700 x527/7002/7-4/71-1500-1004、无界解（或无有界解）无界解（或无有界解）x1x2 81若存在某检验数 k 而对应系数列

40、中元素 aik （即无法找到换出变量），则原问题有无界解。0,33242.max2121212121xxxxxxxxtsxxZ 根据实际问题给出数学模型，进行标准化，根据情况引入松弛变量、剩余变量或人工变量。 线性规划处理问题思路小结：线性规划处理问题思路小结：练习：用单纯形法求解，分析检验数与系数关系并画图验证。82变量xj0 xj 0 xj无约束不需要处理令xj= -xj; xj0令xj= xj-xj;xj, xj0 约束条件b0 b 0 计 算计 算i i=bi/aik令令l= =minmin i i 第第l个基变量个基变量为换出变为换出变量，量，alk为主元素为主元素 迭代运算迭代运算

41、.用非基变量用非基变量xk替换换出变量替换换出变量 .对主元素行对主元素行(第第l行行) 令令 bl/alkbl;alj/alkajl对主元素列对主元素列(第第k列列)令令1alk;0;0其它元其它元素，表中其它行列元素素，表中其它行列元素令令 aij-ali/alkaikaij b bi i- -b bl l/ /a alklka aikikb bi i j- alj/alk k j否是 对目标函数求 max 型线性规划问题，单纯形法计算步骤的框图如下：845 单纯形法的矩阵描述单纯形法的矩阵描述5.1 典式的矩阵形式典式的矩阵形式对于非标准型的线性规划问题对于非标准型的线性规划问题0. .

42、maxXbAXtsCXZ标准型为：标准型为：0. .maxssXXbXAXtsCXZ，松弛变量松弛变量85C=(CB，CN，CS)（A，I）=(B，N，I )设设 B 为可行基，为可行基， SNBXXXXZ = CX目标函数：目标函数：约束条件：约束条件：因为因为B-1 存在，故上式可化为存在，故上式可化为AX+XS=(B, N, I) SNBXXX=BXB+NXN+IXS=bXB +B-1NXN +B-1XS =B-1b=CBXB+CNXN+CSXS86将上式代入目标函数可得将上式代入目标函数可得 XB =B-1b- -B-1NXN - -B-1XSZ=CBXB+CNXN+CSXS =CBB

43、-1b + (CN-CBB-1N)XN + (-CBB-1)XS= CB (B-1b-B-1NXN -B-1XS）+CNXN+CSXSCS=0则线性规划模型可表示为：则线性规划模型可表示为：87Z =CBB-1b + (CN-CBB-1N)XN + (-CBB-1)XS s.t. XB +B-1NXN +B-1XS =B-1b X 0 令非基变量令非基变量 XN = 0， XS = 0，得到一个基本可行得到一个基本可行解，解，Z（0）=CBB-1b 001()bBX单纯形表的相应各部分可表示为：单纯形表的相应各部分可表示为：88 可知，初始单位阵的位置总对应可知，初始单位阵的位置总对应B -1

44、 ；已知；已知 B-1 就能求出整个表。就能求出整个表。XXBXNXSXBB-1bIB-1NB-1-CBB-1b0CN-CBB-1N-CBB-1C-CBB-1AB-1A89如例10,12416482. .32max54321524132121xxxxxxxxxxxxtsxxZ040104021),(421pppB若取基12168b2144/ 1002/ 101 1B则C =(2, 3, 0, 0, 0) 90832121682144/1002/1011bB相应的基可行解中基变量的值相应的基可行解中基变量的值NBCCBNN11000012144/1002/101)0 , 3 , 2()0 , 0

45、(TNxxX),(53)41,2( j =cj -CBB-1pj单纯形乘子向量单纯形乘子向量910104022144/1002/1012p21pB单纯形迭代中的第三张表单纯形迭代中的第三张表CBXBbx1x2x3x4x52x121010-1/20 x4800-4123x2301001/4-1300-201/4B-1B-1b926 线性规划的对偶理论线性规划的对偶理论6.1 对偶问题的提出对偶问题的提出例例7：假如有一个企业家有一批待加工的订单，有：假如有一个企业家有一批待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产意利用该家具厂的木工和油漆工资源来加工他的产品。因此他要与家具厂谈

46、判付给该厂每个工时的价品。因此他要与家具厂谈判付给该厂每个工时的价格。假定该企业家对家具厂的经营状况有详细了解，格。假定该企业家对家具厂的经营状况有详细了解，具体数据同练习具体数据同练习1 。该企业家应如何定价？。该企业家应如何定价？93 设付给每个木工工时和油漆工工时的租金为设付给每个木工工时和油漆工工时的租金为 y1、y2。该企业家的目标是所付的租金最少。模型为。该企业家的目标是所付的租金最少。模型为此问题就称为原问题的对偶问题。此问题就称为原问题的对偶问题。0,3035024. .50120min21212121yyyyyytsyyW0, 050212034. .3050max21212

47、121xxxxxxtsxxZ对比一下这两个模型对比一下这两个模型木工木工油漆工油漆工注意对比各系数、变量之间的关注意对比各系数、变量之间的关系系94对对称称的的对对偶偶问问题题主问题（即原问题）主问题（即原问题）Prime problemDual problem的对偶问题是问题的对偶问题是问题0. .maxXbAXtsCXZ0.minYCYAtsYbW( P )( D ) 一般，一般， 原问题有原问题有 m 个约束个约束 n 个变量，对偶问题个变量，对偶问题有有 m 个变量个变量 n 个约束，对偶问题的一个变量对应原问个约束，对偶问题的一个变量对应原问题的一个约束，反之亦然。题的一个约束，反之

48、亦然。6.2 对偶问题的定义对偶问题的定义95非对称的对偶问题非对称的对偶问题无符号约束的对偶问题是：证明例YCYAtsYbWXbAXtsCXZ. . min 0. . max 8证：证： AX=b 由定义，对偶问题的约束条件为：由定义，对偶问题的约束条件为： 对应对应 Y 对应对应Y AX b- -AX - -b96令令 Y=Y -Y ，得，得(P )的对偶问题为的对偶问题为:0,0 YYCAYAY无约束YCYAtsYbW.minv 掌握对偶问题与原问题的对应关系：掌握对偶问题与原问题的对应关系：教材教材p56，表，表2-497例例9 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶

49、问题 解：由约束条件知有对偶变量解：由约束条件知有对偶变量y1，y2，y3，对偶问对偶问题为：题为：分析：对偶变量的个数、符号，约束条件的个分析：对偶变量的个数、符号，约束条件的个 数、不等号方向，系数的对应关系数、不等号方向，系数的对应关系0, 0852353410. .342max21321321321321xxxxxxxxxxxtsxxxz98无约束432143243143214321, 0, 0642253. . 532min ) 1 (xxxxxxxxxxxxxxtsxxxxz0, 035342423. .8510min31321321321321yyyyyyyyyyytsyyyw练

50、习：写出下列问题的对偶问题练习：写出下列问题的对偶问题0, 01553232. . 23min (2) 3132121321321xxxxxxxxxxtsxxxW990. .maxXbAXtsCXZ6.3 对偶问题的基本性质对偶问题的基本性质1.对称性对称性对偶问题的对偶问题是原问题。对偶问题的对偶问题是原问题。 原问题和对偶问题的概念是相对的。原问题和对偶问题的概念是相对的。（P）（D）0.minYCYAtsYbW2.弱对偶性弱对偶性。，有解的任一可行和的任一可行解对于bYXCYDXP )()( （D）（P）以对称的对偶以对称的对偶问题为前提问题为前提100无界矛盾。与，则由弱对偶性，解有可

51、行无界。若为无界解，意味着)(,Y)()( PbYXCDXCP证：证：0XCAY，由于XCXAY有，又bXAbYXAY所以bYXC即3. 无界性无界性若若( P )为无界解，则为无界解，则( D )无可行解。无可行解。证证:注意：注意：(D)无可行解，无可行解，(P)不一定为无界解。不一定为无界解。(P)有可行解，有可行解，(D)不一定有可行解。不一定有可行解。101是最优解。，时，的可行解，当是的可行解，时设)()( YXbYXCDYPX证：证：都有的所有可行解由弱对偶性，对于XP)(XCbYXC得最优解。是达到这个上界，故如今)(PXXC得最优解。是同理可知，)(DY5. 主对偶定理主对偶

52、定理4. 可行解是最优解时的性质可行解是最优解时的性质若互为对偶的线性规划问题都有可行解，则它们都有最优解，且目标函数最优值相等。 102 首先，当两者都有可行解时，对 Yb 的最小值有一个下界，对 CX 的最大值有一个上界，所以两者必定有最优解。 证：证： 再证它们有相同的最优值。，这时必有矩阵是的最优解，它对应的基是设BPX)( 01ABCCBbBCXCZB1,1BCYB设, 0,YCAY则的可行解。是说明)(DY1XCbBCbYB由于的最优解。是，根据性质)(4DY103 6. ( (P ) )的单纯形表的检验数行对应的单纯形表的检验数行对应( (D ) )的一个基解，的一个基解，其对应

53、关系是其对应关系是可得出的结论：可得出的结论：XBXNXS-Y-YS2YS10CN-CBB-1N-CBB-1（P）、（）、（D）同时）同时达到最优达到最优原问题与对偶问题原问题与对偶问题同时可行同时可行1047.互补松弛定理互补松弛定理 设设X 、Y 分分别别为为(P)和和(D)的的可可行行解解，则则它它们们为为(P)和和(D)的的最最优优解解的的充充分分必必要要条条件件是是： Y Xs = 0 和和 Ys X =0 其其中中，XS，YS为为(P)、(D)标标准准型型问问题题中中的的松松弛弛变变量量和和剩剩余余变变量量。 证：证：设设(P)和和(D)的标准型是：的标准型是：Z=(YA-Ys)X

54、=YAX-YsX W=Y(AX+Xs)=YAX+YXs maxZ=CX (P) AX+Xs=b X, Xs 0 min W=Yb(D) YA-Ys=C Y,Ys 0105若若 YsX =0，Y Xs=0，则则 充分性：充分性：由由性性质质4可可知知 X ，Y 是是最最优优解解。 XAYbYXC若若X 、Y 分分别别是是(P)和和(D)的的最最优优解解，CX =Y b必要性：必要性： 于于是是 Y AX -YsX =Y AX +Y Xs 又又由由于于 Ys，X ，Y ，Xs 0， 所所以以必必有有 Ys X =0，Y Xs =0106其含义为当该约束条件的右端常数增加一个单位其含义为当该约束条件

55、的右端常数增加一个单位时（假设原问题的最优基不变），原问题目标函数最时（假设原问题的最优基不变），原问题目标函数最优值增加的数量。优值增加的数量。6.4 对偶问题的经济解释对偶问题的经济解释影子价格影子价格对偶变量对偶变量 yi的的最优值最优值（i =1，2，m）表示原）表示原问题的第问题的第 i 个约束条件的影子价格。个约束条件的影子价格。Z* = CX* =Y*bb1 b2 bm =（y1*，y2*， ，ym*）= y1*b1+ y2*b2+ +ym*bm?*, 1Zbbkk若1071、指明企业内部挖潜的方向、指明企业内部挖潜的方向2、指导企业间的分工与协作、指导企业间的分工与协作3、新产

56、品的开发决策、新产品的开发决策4、资源购销决策、资源购销决策5、分析产品价格变动对资源紧缺情况的影响、分析产品价格变动对资源紧缺情况的影响影子价格的作用：影子价格的作用：6.5 对偶单纯形法对偶单纯形法1. 1. 对偶单纯形法的基本原理对偶单纯形法的基本原理)1 (0. . max )(XbAXtsCXZP)2(. . min )(无符号约束YCYAtsYbWD108 设设 B为问题为问题( (1) )的一个基，则的一个基，则01)0(bBX为问题为问题( (1) )的一个基本解。的一个基本解。 =C-CBB-1A 0 （4）原始最优性条件原始最优性条件则则X(0)为问题为问题（1）的最优解。

57、的最优解。 若满足条件若满足条件原始可行性条件原始可行性条件B-1b 0 （3）X(0)为一个基可行解，若进一步满足为一个基可行解，若进一步满足 令令Y=CBB-1，代入式代入式（4） =C-CBB-1A 0，得，得YA C （5）对偶可行性条件对偶可行性条件109 若基若基 B 为原问题的最优基，则为原问题的最优基，则 Y=CBB-1 就是对就是对偶问题的最优解。偶问题的最优解。定义定义1 凡满足原始最优性条件的基凡满足原始最优性条件的基 B 称为对偶可行基。称为对偶可行基。基基原始可行原始可行对偶可行对偶可行最优基最优基对偶单纯形法的思路：对偶单纯形法的思路：初始基本解初始基本解满足原始最

58、优性条件满足原始最优性条件不满足原始可行性条件不满足原始可行性条件110按一定规则寻找按一定规则寻找保持最优性保持最优性满足可行性满足可行性基最优解基最优解定义定义2 如果原问题（如果原问题（1）的一个基本解）的一个基本解X(0)对应的检验数对应的检验数向量满原始最优性条件（向量满原始最优性条件（4），则称此基本解为问题），则称此基本解为问题（1）的一个）的一个正则解，正则解，相应的基为正则基。相应的基为正则基。2. 对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：（1）找一个正则基）找一个正则基B，列初始单纯形表。，列初始单纯形表。 （2）若）若 b =B-1b 0，则迭代停止，已找到原问题

59、，则迭代停止，已找到原问题的最优解；否则，转入下一步。的最优解；否则，转入下一步。111 （4）若）若 alj 0（j=1，2，n），则停止迭代，原），则停止迭代，原问题无解；否则，转入下一步。问题无解；否则，转入下一步。 （5）计算）计算则取相应的则取相应的 xk 为进基变量，转入下一步。为进基变量，转入下一步。 若若 bl = min bi | bi 0 ，则取相应的变量，则取相应的变量 xl 为出基为出基变量。变量。lkkljljjaaa 0min （6）以）以 alk为主元进行旋转变换，得新的正则解，返为主元进行旋转变换，得新的正则解，返回（回（2）。）。（3）确定出基变量：）确定出基

60、变量：112例例10 用对偶单纯形法求解用对偶单纯形法求解LP问题：问题： 解：用（解：用（-1）乘不等式约束的两边。再引入松弛）乘不等式约束的两边。再引入松弛变量变量x5， x6，将原问题化为，将原问题化为)4 , 3 , 2 , 1(023233. .34max43214321321jxxxxxxxxxtsxxxzj)4, 3, 2, 1(024233. .34max6432154321421jxxxxxxxxxxxtsxxxZj113列对偶单纯形表进行迭代（见下表）列对偶单纯形表进行迭代（见下表）cjCBXBbx1x2x3x4x5x6x5x600-3- 2-1 2-2 11 -4 - 1