线性规划讲稿.doc

第一章 线性规划的数学模型线性规划是研究在一些线性条件下，把一个线性函数极小化或极大化的问题一、安全生产问题例1:某个工厂利用三台设备，生产三种不同的产品。各种产品每生产一件在各台设备上需要的加工时间、各台设备每天的生产能力以及没见产品的单位利润表如下，问怎样安排生产，才能使每天获得的利润最大？设 备 每件产品的加工时间设备的生产能力211420302450212430利 润211.5二、运输问题例2:设有两个砖厂，其产量分别是23万块和27万块，他们生产的砖供应，三个工地，其需要量分别是17万块、18万块和15万块，而各自生产地到各工地的运价如下表，问应如何调运，才能使总运费最省。工地运价砖厂50607060110160三、下料问题例3：某厂有一批长度为300cm的钢管，要把它们截成长度为45cm,80cm,95cm的管料，并要求其根数比例为5：3：2，来配套生产某零件。问采用怎样的方案进行锯割，才能使得到的三种管料既能配套，又能使残料最少。截 法12345678910长度45cm644322110080cm010210321095cm0010120123残 料304025535201503015四、投资问题例4:一投资方欲向几个企业投入一定数量的资金，各个企业的获利情况。资金的周转周期个不相同。如何分配对各企业的投资量，使得若干年后获得的利润最高。.线性规划问题的数学模型的一般形式第二节 线性规划问题的标准形式一、线性规划的标准形式均为常数，此标准形式可以写成矩阵形式其中 二、怎样把现行规划的问题的非标准形式化成标准形式1、如果求最小值只需令2、如果第r个约束变量条件是则引入松弛变量变将上式变成，并不是决策变量他在目标函数中的系数是0.3、如果第r个条件是则引入剩余变量，上式变为，引入的也不是决策变量，他在目标函数中的系数也为0.4、如果，则5、如果某个决策变量没有非负的约束条件，则可以令且带入约束方程和目标函数，这样可以使得却不便利狼都为非负的限制。看两个例子第三节 线性规划问题的解及其集合性质 （2.3）定义1：满足（2.3）中条件的解成为线性规划问题的可行解。使目标函数达到最大值的可行解成为线性规划的最优解。定义2：令B是A中m个线性无关的列向量所构成的m阶满秩方阵，B称为线性规划问题的基阵，称X为B的列向量对应的分量为基变量，X的其余变量为非基变量。当所有的非基变量取零时，所得到的AX=b的解称为基阵B的基本解。当基本解又是可行解时我们称之为基本可行解，简称基可行解。例如：解:令，线性无关，线性无关，所以只有两个基阵， 对于来说，是基变量。令=0得到约束方程的解于是得到基本解，也是基本可行解。对于来说，是基变量，是非基变量令，得到约束方程的基本解因为是负数所以不是基本可行解。第二节 两个变量的线性规划问题的图解法例1：（有唯一最有解）约束条件例2：（有无数最优解），条件如上约束条件例3：（最优解不存在）约束条件例4: （没有最优解）无可行域 约束条件注：（2.3）的可行域R有界。那么它的目标函数一定可以在R的顶点达到最大值。第三章 单纯形法考虑一类特殊的线性规划问题均为常数，引入松弛变量使得均为常数，有如下特点：1、 有m阶单位方阵作为基阵。2、 目标函数中所有的基变量的系数都为03、 约束条件中的方程右边的常数皆为非负数。满足以上三点的线性规划问题称为典试。一般的线性规划的问题可以化为 (3.3)这里的.令（3.3）中非基变量等于0得到基本可行解以及与之对应的目标函数的判断及可行解是否是最优解的关键是（3. 3）目标数中非基变量的系数，所以非基变量的系数称为检验数。定理3.1：（最优解判别定理）若是（3.3）所对应的一个基可行解，且（3.3）中目标函数行的，则是最优解。定理3.2：（有无穷多个最优解判定定理）若是线性规划问题（3.3）所对应的一个基可行解，且（3.3）中的目标函数的，且存在一个检验数，则此线性规划问题就有无穷多个解。定理3.3：（无最优解判定定理）若是线性规划问题（3.3）所对应的一个基可行解，有某个个检验数，且所有的，则此线性规划问题的目标函数值无界，即无最优解。 第二节 基本可行解之间的转移例3.1： 引入松弛变量化为典式20510400151001450-80-45000得到一个基可行解由于两个检验数-80，-45，进行基迭代min-80，-45= -80，-80为的系数，让入基，由于所以选出基，这时20为主元。接着将20所在的列除20以外都化为0，把20变成1，得11/41/20020025/4-3/411500-25401600迭代后，新近基变量为，而非基变量为，令，得到新的基可行解为，由于检验数还有负数，则重复上面的工作，令-25多对应的非基变量入基，由于，所以选取25/4为主元，它所在的行的基变量出基。使25/4变为1，主元所在的列的其他元为0。102/25-1/251401-3/254/252400142200令，于是的为最优解，最优值为2200第二节 大M法和两阶段法均为常数，引入m个人工变量并在目标函数中增加，其中是一个任意大的正数，构造一个规划问题新的规划问题有一个m阶单位方阵为初始可行基，从此基出发通过迭代，让所有的人工变量出基，当所有的人工变量取0时，新的规划问题就是原规划问题了，新的规划问题的基可行解就是原问题的一个基可行解。例3.3解：引入人工变量转换典式为典式S的表达式中不能有得出单纯形表1-2-3-21051-1210110-2M-23M+3M+2M-100-15M所以检验数中-2M-20）,则令k=minj|=(,0并确定为出基，即在比值最小的的行中，选择行对应的的基变量出基。-3/4在最左边，选入基，1001/4-8-1900101/2-12-1/23000100101000-3/420-1/260出基，得到单纯形表4001-32-4360-210043/2-150001001013000-4-7/2330再选出基，入基-1280108-840-1/21/40013/8-15/400010010111000-2180如此重复得到001001011-1/23/40-2015/23/40211-2406103/25/402021/25/4最优解为，最优解为5/4第四章 对偶原理对偶问题的表达 与之对应的线性规划问题（P） （D） 矩阵形式为 上面互为对偶问题原规划问题对偶规划问题1、目标函数求目标函数求2、目标函数中的系数为约束条件中的常数为3、约束条件中的常数目标函数中的系数为4、约束条件的系数矩阵A约束条件中的系数矩阵A5、约束条件有m个方程对偶变量有m个6、决策变量有n个约束条件有n个方程7、每个约束条件为每个对偶为变量8、每个决策变量每个约束条件为 第二节 非对称形式对偶问题的表达对称形式的对偶问题，若求最大值，则约束条件为，如果求最小值，则约束条件的形式，除此之外都是非对称形式。定理4.1 如果规划问题（p）中第k个条件为等式，则其对偶问题中，第k个对偶变量无非负限制，反之，如果原规划问题第k个决策变量无非负限制，则其对偶问题的第k个约束条件应为等式。定理4.2 如果原规划问题是求最大值，且第k个约束条件为形式，则在其对偶问题中，第k个对偶变量；如果原规划问题求最大值，且第k个决策变量则在其对偶问题中，第k个约束约束条件为 形式。定理4.3 如果原规划问题中求最小值，且第k个约束条件为形式，则在其对偶问题中，第k个对偶变量；如果原规划问题求最小值，且第k个决策变量，则在其对偶问题中，第k个约束条件为形式。第三节对偶规划的基本性质性质：对偶规划的对偶规划是原规划。性质：原规划（P）和对偶规划（D）有最优解的充分必要条件是它们同时有可行解。性质：原规划有最优解则对偶规划也有最优解，而且目标函数的最优值相等。性质：原规划的检验数对应于对偶规划的一个基本解。第三节 对偶单纯形方法一、对偶单纯形法的思想原规划问题（P）对偶规划问题（D） 引入松弛变量，把（P）化为标准形式设B是（P）的可行基，则上述问题变为将目标函数放在约束条件里，则化为对应的单纯形表为表中为原规划的一个基本解，（0，）为原规划的检验数，又是对偶问题的一个基本解，而也是对偶问题的的检验数，若满足1、存在2、3、，则B为最优解。若B满足1、2，不满足3，那么可以用单纯形法求出最优解。若B满足1、3，不满足2，则B是对偶可行基，下面就介绍从对偶可行基出发，逐步使B满足2，求出最优解。例48 引入松弛变量令 对偶单纯形表基变量-3-1100-3-4-3010-6-1-3001-2320003、 确定出基变量：最后一列中-6最小，所以为出基变量，min|3/-4|,|2/-3 |,=|2/-3 |,所以为进基变量。4、 迭代以-3为主元，用和单纯形法相同的方法，利用初等变换进行换基迭代得到基变量-5/301-1/30-1-4/310-1/302-1/300-11-21/3002/30min|1/3/-5/3|,|2/3/-1/3|=|1/3/-5/3| 所以进基，出基。基变量10-3/51/503/5014/5-3/506/500-11111/5002/300所有检验数全部为非负，原规划和对偶规划全达到最优解步骤如下：1、将规划问题标准。（1）如果表中的常数列每个元都是非负，则初始基是一个可行基，用单纯形法求解。（2）如果表中常数列有一个为负数，且对于初始基的所有检验数全是非负，则初始基是对偶可行基，用对偶单纯形法求解。2、找出主元 （1）在常数列中找出最小的负元素所在的行，该行对应的基变量为出基变量。（2）在主行中都是元素非负，则此线性规划问题无可行解。若有负元素，则用所有的负元素去除对应的检验数，并在这些