第六章 线性规划及其解的实现线性规划是目前应用最广泛的一种系统优化方法，它的理论和方法已十分成熟，可以应用于生产计划、物质调运、资源优化配置、地区经济规划等许多实际问题.线性规划最早由前苏联学者L V Kantorovich 于1939年提出，但他的工作当时并未为人所熟知.直到1947年，美国学者G B Danzing 提出求解线性规划最有效的算法-----单纯性算法后，才引起数学家、经济学家和计算机工作者的重视，并迅速发展成为一门完整的学科而得到广泛的应用.利用线性规划建立数学模型也是中国大学生数学建模竞赛中最常用的方法之一.优化模型的一般形式为T n Xx x x X X f z ),,,(),(min 21 == (1)m i X g t s i ,,2,1,0)(.. =≤ (2)其中)(x f 称为目标函数，)(X g i 称为约束条件.只满足式(2)的X 称为可行解；同时满足式(1)、式(2)两式的解*X X =称为最优解.由式(1)、式(2)组成的模型属于约束优化，若只有式(1)就是无约束优化.一般情况下，优化问题都是有约束的，但是如果最优解不是在可行域的边界上，而是在可行域的内部，那么就可以用无约束优化作比较简单的处理.若f ，i g 均为线性函数，优化模型式(1)、式(2)称为线性规划，否则称为非线性规划. 本章主要对线性规划问题及其解的实现作简要介绍.§6.1 线性规划模型形式及其性质线性规划是运筹学的一个重要分支，应用很广.线性规划问题可以描述为求一组非负变量，这些非负变量在一定线性约束的条件下，使一个线性目标函数取得极小(或极大)值的问题.1、线性规划的标准形式目标函数 n n x c x c x c z +++= 2211m in约束条件 ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=+++=+++=+++0,,,2122112222212111212111n mn mn m m n n n n x x x bx a x a x a b x a x a x a b x a x a x a这里n x x x ,,,21 是变量，i ij i b a c ,,都是已知常数，且0≥i b ，约束条件常用..t s 表示.线性规划用矩阵表示就是T n x x x X cX z ),,,(,min 21 ==T n n m ij b b b b n m a A x b AX t s ),,,(),()(,0,..21 =≤=≥=⨯.2、线性规划的一般形式 目标函数 n n x c x c x c z +++= 2211m in约束条件 ⎪⎪⎩⎪⎪⎨⎧+++++++++mn mn m m n n n n b x a x a x a b x a x a x a b x a x a x a )()()(22112222212*********式中的( )可以是关系符号：≤≥=<>,,,,中的任意一个.3、线性规划化为标准形的方法 把线性规划化为标准形：(1)目标函数一律化为求极小(如果是求极大，则利用)m in(m ax z z -⇔化为求极小).(2)对约束条件中b Ax ≤的不等式，利用加入松弛变量的方法化为等式.如果原约束条件中有""b ≥形式的约束，可以在不等式两边同时加负号化为""b -≤的形式.(3)标准形中一般要求0≥i x .如果某个i x 无此约束，可以引入两个新变量''',i i x x ，令'''i i i x x x -=，0,'''≥i i x x ；如果原来的约束为i i l x ≥，可以令i i i l x x -='，0'≥i x .4、线性规划的基本性质 线性规划有以下基本性质：1）若存在可行域，可行域必为凸集； 2）基可行解对应于可行域的顶点；3）若有最优解，必在可行域的顶点取得.§6.2 线性规划问题的数学模型及其解的基本概念1、线性规划问题的数学模型例1 (生产计划问题)某工厂生产甲、乙两种产品，甲产品每生产一件需耗黄铜2kg 、3个工作日、两个外协件，每件可获利润60元；乙产品每生产一件需耗黄铜4kg 、1个工作日、不需外协件，每件可获利润30元，该厂每月可供生产用的黄铜320kg ，总工作日180个，外协件100个.问应怎样安排生产才能使工厂的利润最高？分析问题，建立数学模型.问题：怎样安排生产，即甲、乙两种产品各生产多少才能使工厂的利润最高？用1x ，2x 分别表示甲、乙两种产品生产的件数，该厂追求的目标是获取最高利润，用数学表达式表示为：213060m axx x f +=.由于生产甲、乙产品的件数要受到生产能力的约束，即 黄铜约束：3204221≤+x x ，工作日约束：180321≤+x x ， 外协件约束：10021≤x ， 非负约束：0,21≥x x .这样，该厂生产计划问题就归结为如下数学模型：⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤++=.0,,1002,1803,32042..,3060max 211212121x x x x x x x t s x x f例2 (运输问题)计划由三个粮站1A ，2A ，3A 运输某种粮食至三个加工厂1B ，2B ，3B ，三个粮站的供应量和三个加工厂的需求量以及各供应地至需求地的单位运输价(元/t)如表1所示，试作出运费最省的调运计划方案.表 1问题：如何调运，才能使运费最省？设ij x 表示第i 个粮站到第j 个加工厂的粮食数量(单位：3,2,1,,=j i t )，则总运费3332312322211312112050603040709080120x x x x x x x x x f ++++++++=.从各粮站运出的粮食数量不能超过供应量，20131211=++x x x ，30232221=++x x x ，50333231=++x x x ，同时还要保证各加工厂的需要，25312111=++x x x ，50322212=++x x x ，25332313=++x x x ，而运输量应满足0≥ij x .则上述运输问题的数学模型为⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥=++=++=++=++=++=++++++++++=.0255025503020..2050603040709080120min 332313322212312111333231232221131211333231232221131211ij x x x x x x x x x x x x x x x x x x x t s x x x x x x x x x f从上述两个例子可以看出，虽然两个问题的具体内容和性质不同，但它们都属于优化问题，它们的数学模型都有相同的数学形式，即在一定的线性等式或不等式的条件下，使某一线性函数达到最大(或最小).所谓线性规划问题的数学模型是将实际问题转化为一组线性不等式获等式约束下求线性目标函数的最小(大)值问题.2、解的基本概念对于线性规划问题的标准形式..min ≥==x b Ax t s cx z 其中系数矩阵A 是行满秩的，即)()(n m m A R ≤=，并引入列向量),,2,1(n j P j =表示系数矩阵的列向量.满秩约束条件的解称为线性规划问题的可行解，可行解的全体}0,|{≥==x b Ax x D 称为线性规划问题的可行域.满足目标函数的可行解称为线性规划问题的最优解.系数矩阵A 的任意一个m 阶的可逆方阵B 称为线性规划问题的一个基.显然，A 最多有mn C 个基.基B 中的任意一列向量j P 称为基向量.系数矩阵A 中除基B 外的其余m n -个列向量称为非基向量.显然，选择的基不同，与基对应的非基向量也不尽相同.与基向量j P 对应的变量j x 称为基变量.与非基向量j P 对应的变量j x 称为非基变量.为叙述方便，不妨假设基B 是阵A 的前m 列构成的，即),,,(21m P P P B =，如若不然，则可通过调整变量顺序达到此目的.按上述定义，),,2,1(m j x j =为基变量，),,2,1(n m m j x j ++=为非基变量，记T m B x x x X ),,,(21 =，T n m m N x x x X ),,,(21 ++=，),,,(21n m m P P P N ++=那么约束条件可用分块矩阵表示为b X X N B N B =⎪⎪⎭⎫ ⎝⎛),(令0=N X ，由b BX B =得b B X B 1-= (3) 称⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫ ⎝⎛=-01b B X X X N B为对应于基B 的基解.很显然，由于m B R =)(，即0||≠B ，所以式(3)的解是惟一的.即对应于某个基的基解是惟一的，从而一个线性规划问题最多有mn C 个基解.若基解满足0≥x ，则称基解为基可行解。
