第2章-线性规划原理与解法

第二章线性规划原理与解法§2-1线性规划求解原理§2-2单纯形方法§2-3人工变量及其处理§2-1线性规划求解原理1、举例说明2、一般线性规划问题单纯形法求解基础单纯形法的思路：从问题的某个基可行解开始，转换到另一个基可行解，直到找到使目标函数最大的基可行解。82321xxx16441xx12452xx0,,,,54321xxxxx5432100032maxxxxxxz例2-1100400100400121),,,,(A54321PPPPP步骤1寻找初始基可行解100010001),,(B543PPPTBxxxX),,(543从约束条件的系数矩阵中可以容易地找到一个基：将上述约束条件变换形式为一、举例说明,83x令非基变量为0，则TX)12,16,8,0,0()0(即：为基可行解21328xxx14416xx25412xx（式2-1）,164x,125x0z对应的为:BX步骤2判断是否为最优解一、举例说明选择作为换入变量，2x1x2x可以将或换入基变量中。同时还要找出一个换出变量。82321xxx16441xx12452xx0,,,,54321xxxxx5432100032maxxxxxxz例2-112345121212121223000230*820*16400*1204230zxxxxxxxxxxxxxxx将（式2-1）带入目标函数为（式2-2）21328xxx14416xx25412xx（式2-1）计算非基变量检验数步骤3基变换（由一个基转向另一个基）一、举例说明基变换过程中的要求：02823xx0164x041225xx（式2-3）（1）所有变量均为非负；1x因为仍为非基变量，所以01x由式（2-1）和要求（1）知21328xxx14416xx25412xx（式2-1）4282x34122x必须有3)412,,28min(2x为了保证式（2-3）满足基变换要求，此时，05x将式（2-1）进行如下基变换用替换，5x2x12382xxx14416xx52124xx（式2-4）（2）所有非基变量为0。最小规则步骤3基变换一、举例说明利用高斯消去法将式（2-4）左边变换为单位矩阵（即出现基）513212xxx14416xx52413xx（式2-5）基可行解为TX)0,16,2,3,0()1(9z12382xxx14416xx52124xx（式2-4）目标函数值之间的联系？将式（2-5）代入目标函数0439251xxz514329xx1234511515155max230001233041022016400zxxxxxxxxxxxxx得:重复步骤2判断是否为最优解513212xxx14416xx52413xx（式2-5）一、举例说明步骤4重复步骤2、3，直到目标函数中非基变量的系数均为负，无改进可能，即找到最优解本例依次向下迭代得到的基可行解分别为：13)0,8,0,3,2()2(zXT14)4,0,0,2,4()3(zXT于是最优解为:14)4,0,0,2,4(**zXT一、举例说明与图解法之间的对应关系TX)0,16,2,3,0()1(TX)0,8,0,3,2()2(TX)4,0,0,2,4()3(9zTX)12,16,8,0,0()0(0z13z14z2134567812340Q1Q2Q3Q4①③②1x2x例2－1BCBXb54321xxxxx3x4x5xijc23000816121210004001400104－300008161220420[4]§2-1单纯形法23000382321xxx16441xx12452xx0,,,,54321xxxxx5432100032maxxxxxxz230000812100401640010－0120[4]001323000BCBXb54321xxxxx3x4x5xijc03x4x2x90031x4x2x1x5x2x20300-3/2-1/801400-201/413200-3/40103001/4164001001210-1/224－3216014[1]101000-410100－412283-1/221/41/4[2]20311/2-200401/400140-1/81/21022283283-1/221/4-1/221/4TX)4,0,0,2,4(*14*z最优解为：本例题中，X5先出基，又进基一、举例说明由以上分析可以得出单纯形法的步骤:1、建立实际问题的线性规划数学模型；2、把一般的线性规划问题化为标准形式；3、确定初始基可行解；4、检验所得到的基可行解是否最优;5、迭代，求得新的基可行解（主要确定换入变量和换出变量）；下面将主要针对3、4、5来进行讨论二、一般线性规划问题的求解基础1、确定初始基可行解※对于已经是标准型的线性规划问题：※对于所有约束条件都是“≤”型的不等式：※对于所有约束条件都是“≥”型的不等式及等式约束情况：找到初始可行基后，将所有基变量列于等式左边，非基变量和常数列于等式右边，则可得初始可行解TmTmbbbxxxX)0,,0,,,,()0,,0,,,,(2121),,,(21mPPPB不失一般性，令初始可行基为，则（式2-6）一般可以直接观察得到一个初始可行基；对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对等式约束直接加上一个非负的人工变量。21328xxx14416xx25412xx（式2-1）通过化标准型——加上松弛变量，可以得到一个初始可行基。nmjjnnmmxabxaxabx111,111,111nmjjnnmmxabxaxabx122,211,222nmjmjmnnmmmmmmxabxaxabx1,11,二、一般线性规划问题的求解基础2、最优性检验与解的判别由式（2-6）知,nmjijxa1基变量＝常数－其中常数和ija都是经过变换之后的，与最初的不同，用（式1-7）表示经过迭代之后的基变量的值。nmjiixabxij1''将式1-7代入目标函数jnmjjimiijnjjxcxcxcz111得minmjnmjjjjijiiiminmjnmjjjjijiixcxacbcxcxabcz111''111'')()(jmiijijminmjiixaccbc)(1'11'nmjjjjxzcz10)(nmjjjxz10j称为检验数检验数实际上就是将决策变量代入目标函数后，各变量在目标函数中的系数二、一般线性规划问题的求解基础2、最优性检验与解的判别（1）最优解的判定定理：（3）无穷多最优解：（4）无界解判定定理：（以下判定定理针对标准型而言）0j对于一个基可行解，如果其所有非基变量的检验数，则该解称为最优解。同时它对应的系数列向量所有的，0,kmia则该线性规划问题具有无界解。02823xx0164x041225xx82321xxx16441xx12452xx0,,,,54321xxxxx5432100032maxxxxxxz已经是最优解，有某个非基变量的检验数=00km对于一个基可行解，其非基变量中有某个，（2）唯一最优解：所有非基变量的检验数都0二、一般线性规划问题的求解基础3、基变换当初始可行解不是最优解时，要从中确定一个换入变量，一个换出变量，得到一个新的基可行解。（1）确定换入变量0j当存在多个时，kxkjj)0(max一般选，即为换入变量，为使目标函数增长较快，但不是必须。例如：按上述原则，本节例子必须经过三步迭代才能得到最优解。TX)0,16,2,3,0()1(9zTX)12,16,8,0,0()0(0zTX)0,8,0,3,2()2(13zTX)4,0,0,2,4()3(14z2134567812340Q1Q2Q3Q4①③②1x2x二、一般线性规划问题的求解基础3、基变换（2）换出变量的确定为了确保所有的变量均为非负，需确定换入变量的值为：''''')0(minlklikikiikabaabx为了与书上后面的单纯形法统一，令式（2－8）等于θ则,05x确定5x为换出变量。由上例可知为了求得新的基可行解，除保证和外，还必须通过高斯消去法得到新的可行基和基可行解。kx0lx82321xxx16441xx12452xx0,,,,54321xxxxx5432100032maxxxxxxz即''''')0(minlklikikiiabaab称为最小θ规则3)412,,28min(2x上例由无界解判定定理可知为什么0'ika换出变量为：lx式（2－8）•进基变量的选择•出基变量的选择•判优原则若目标函数最小化？总结主要掌握的内容：1、确定初始可行解2、解的最优性的判断3、基变换（换入和换出变量的确定）线性代数中求逆矩阵的一种方法为：（B|I）----（I|B-1）………经过行变换单纯形表间的对应关系CBCBCN0b表头XBXNXSBNIb初始表…………CBIB-1NB-1B-1b当前表CB-CBICN-CBB-1N0-CBB-1检验数单纯形表的矩阵表述BX1NXsX11NB1BbB1111NBCCBN1BCBbBCB1I03x4x2x980031x4x2x1x5x2x20300-3/2-1/801400-201/413200-3/40103001/4164001001210-1/224－101000-410100－41223-1/221/420311/2-200401/400140-1/81/2102230000812100401640010－01204001323000BCBXb54321xxxxx3x4x5xijc0XBXSB-1B-1B-1B-1§2-3人工变量及其处理一、大M法二、两阶段法三、线性规划问题的各种情况讨论一、大M法当约束条件出现“≥”或“＝”时，不能直接找到单位矩阵，如下例例2－2：3213minxxxz112321xxx324321xxx1231xx0,,321xxx54321'003maxxxxxxz1124321xxxx3245321xxxx1231xx0,,,,54321xxxxx构造单位矩阵※约束条件为“≥”时：减去剩余变量再加上人工变量※约束条件为“＝”时：直接加上人工变量※目标函数中，剩余变量系数为0，人工变量系数：求max时，为－M，求min时，为＋M。？？？7654321'003maxMxMxxxxxxz1124321xxxx32465321xxxxx12731xxx0,,,,,,7654321xxxxxxx4x6x7xBCBXb7654321xxxxxxxijc7654321'003maxMxMxxxxxxz1124321xxxx32465321xxxxx12731xxx0,,,,,,7654321xxxxxxx1-2110001131-4120-110-20100013-1-100-M-M113/210-M-M1131121一、大M法12[1]3－6M-1+M-1+3M0-M00-1+3M3-1