线性规划-精品课件

《线性规划-精品课件》由会员分享，可在线阅读，更多相关《线性规划-精品课件（65页珍藏版）》请在金锄头文库上搜索。

1、线性规划 引言 什么是线性规划 如果最优化问题三要素中的目标函数和约束条件都是线性的，则该最优化问题称为线性规划问题 线性规划的应用和发展 线性规划（ Linear Programming，简写成 LP）是最优化理论和方法中的重要领域之一。其理论上的完整性、方法上的有效性以及应用上的广泛性，较其他分支都成熟的多，同时很多实际问题都可以转化为线性规划来解决 线性规划的要点就是在满足线性约束条件的前提下，使预定的线性目标函数达到最优。现在线性规划已不仅仅是一种数学方法，在理论上，它启发了诸如对偶、凸性等最优化理论的核心概念，在实际中更是大量被运用于经济学和管理学领域，成为科学决策的一个有效手段 乔

2、治 丹齐格（ G. B. Dantzig）被认为是线性规划之父。自从 1947年他提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在应用上也日益深入，成为科学与工程领域广泛应用的数学模型。特别是在计算机能处理海量约束条件和设计变量的线性规划问题之后，线性规划就更加受到青睐 线性规划的典型实例 运输问题 设有两个建材厂 C1和 C2，每年沙石的产量分别为 35万吨和 55万吨，这些沙石需要供应到 W1、 W2和 W3三个建筑工地，每个建筑工地对沙石的需求量分别为 26万吨、 38万吨和 26万吨，各建材厂到建筑工地之间的运费（万元 /万吨）如表所示，问题是应当怎么调运才能使得总运费最

3、少？ 运费 工地 建材厂 W1 W2 W3 C1 10 12 9 C2 8 11 13 线性规划的典型实例 运输问题 问题分析 假设 xij代表建材厂 Ci运往建筑工地 Wj的数量（万吨），则各建材厂和工地之间的运量可以用下表来表示 目标函数即为总运费 建材厂 C1、 C2的输出量应分别为建材厂 C1、 C2的产量 各工地的沙石需求量应当为从各建材厂接收到沙石的总量 运输量 xij为一非负值 分配量 工地 （万吨） 建材厂 W1 W2 W3 输出总 量 C1 x11 x12 x13 35 C2 x21 x22 x23 55 接收总量 26 38 26 90 1 1 1 2 1 3 2 1 2

4、2 2 31 0 1 2 9 8 1 1 1 3f x x x x x x1 1 1 2 1 32 1 2 2 2 33555x x xx x x1 1 2 11 2 2 21 3 2 3263826xxxxxx0ijx线性规划的典型实例 运输问题 数学模型 线性规划问题的特征 均可以用一组设计变量来表示一种实施方案 每个问题都有一定的约束条件，这些条件可以用一组线性等式或者线性不等式表达 在上述前提下，一般都有一个目标函数，该函数用于衡量方案的优劣，可以表达为设计变量的一个线性函数，我们的目的一般为使得目标函数达到最大值或者最小值 11 12 13 21 22 2311 12 1321 22

5、 2311 2112 2213 2310 12 9 8 11 13m in35s .t .552638260 ( 1 , 2 ; 1 , 2 , 3 )ijf x x x x x xx x xx x xxxxxxxx i j线性规划问题的标准型 线性规划问题的一般标准型 根据线性规划的定义，线性规划问题即求取设计变量 x=x1, x2, xnT的值，在线性约束条件下使得线性目标函数达到最大，线性规划问题的一般标准型为： 其中， ci 、 aij 、 bi 为给定的常数 线性规划问题的标准型的特点 目标函数为设计变量的线性函数，且需要极大化； 约束条件为设计变量的一组线性等式，也称为约束方程组；

6、 设计变量 x1, x2, xn都有非负限制。 1 1 2 21 1 1 1 2 2 1 12 1 1 2 2 2 2 21 1 2 2m axs .t .0 1 , 2 ,nnnnnnm m m n n mjf c x c x c xa x a x a x ba x a x a x ba x a x a x bx j n线性规划问题的标准型 线性规划问题的矩阵标准型 利用向量或矩阵符号，线性规划问题的标准型还可以用矩阵形式表达： 其中 为 n维行向量 为 m n维矩阵 为 m维列向量 为 n维列向量 是指其各分量 m axs.t.0f cxA x bx 12 nc c cc1 1 1 2 1

7、2 1 2 2 212nnm m m na a aa a aa a aA 12 Tnb b bb 12 Tnx x xx x0 12, , 0nx x x线性规划问题的标准型 不同类型的非标准型化为标准型的方法 问题为极小化目标函数 设原有线性规划问题为极小化目标函数 则可设 将极小化目标函数问题转化为极大化目标函数问题 约束条件为不等式 如果原有线性规划问题的约束条件为不等式，则可增加一个或减去一个非负变量，使约束条件变为等式，增加或减去的这个非负变量称为松弛变量。例如，假如约束为 则可以在不等式的左边增加一个非负变量 xn+1，使不等式变为等式 如果约束为 则可在不等式的左边减去一个非负变

8、量 xn+1， 使不等式变为等式 模型中的某些变量没有非负限制 若对某个变量 xj并无限制，取值可正可负，这时可设两个非负变量 和 ，令 注意到，因为对原设计变量进行了代换，还需要将代换式代入目标函数和其他约束条件做相应的代换，这样就可以满足线性规划标准型对变量非负的要求 1 1 2 2m in nnf c x c x c xff1 1 2 2m a x nnf c x c x c x1 1 2 2i i in n ia x a x a x b1 1 2 2 1i i in n n ia x a x a x x b1 1 2 2i i in n ia x a x a x b1 1 2 2 1i

9、 i in n n ia x a x a x x bjx jx j j jx x x线性规划问题的标准型 例子 将线性规划模型标准化 将目标函数两边乘上 -1转化为求极大值 原问题的约束条件中的前两个条件均为不等式，在第一个不等式的左边加上一个松弛变量 x4，在第二个不等式的左边减去一个松弛变量 x5，将两者转化为等式约束 原问题对设计变量 x3没有非负限制，故在此引入非负变量 和 ，令 经过上述步骤整理后的标准型为 1 2 31 2 31 2 31 2 3122m in3s.t.212 3 400f x x xx x xx x xx x xxx1 2 3m a x 2f x x x1 2 3

10、 41 2 3 5321x x x xx x x x13x 23x 123 3 3x x x121 2 3 3121 2 3 3 4121 2 3 3 5121 2 3 3121 2 3 3 4 52m a x3s .t.2 2 12 3 3 4, , , , , 0f x x x xx x x x xx x x x xx x x xx x x x x x线性规划问题中解的概念 概述 为了帮助分析线性规划求解过程，先介绍线性规划解的概念。仍然考虑式 (4-2)中的线性规划的矩阵标准型： 求解上述线性规划问题实际上就是要求出向量 x=x1,x2, xnT使其满足 Ax=b和x 0，且目标函数 f

11、达到最大值，这个向量称为 线性规划问题的解 。 当求解 Ax=b时，假设独立方程的个数为 m个，设计变量的维数为 n，根据线性代数的知识，如果 m=n，则方程有唯一解，无优化的自由度；如果 mn，方程个数大于未知数的个数，则有些约束可能不能被满足，上述两类问题不在我们探讨的范围之列，也就是我们 仅讨论 mm)，则基本解的数量小于或等于 基本解 不是线性规划问题的解 ，而是仅满足约束方程组的解 BNxB N bx10BNx BbxxmnC线性规划问题中解的概念 可行解、可行域 上面的分析仅考虑了约束方程组 Ax=b，下面进一步考虑线性规划问题的非负约束。我们称既满足约束方程组 Ax=b，又满足非

12、负约束 x 0的解为线性规划问题的可行解，即可行解满足线性规划问题的所有约束。可行解的集合称为可行域，记作： 基本可行解 特别的，若线性规划问题的基本解能够满足线性规划问题中的非负约束，即： 则称该解 xB为基本可行解，简称基可行解，称 B为可行基。基可行解的数量不会超过 个。显然，基本可行解一定是可行解，基可行解是可行域中一种特殊的解 最优解 能使得线性规划问题的目标函数值达到最大的可行解称为最优解。线性规划问题中的最优解，一定可以在基可行解中找到，而基可行解的数量是有限的，因而这就在理论上保证了可以在有限的步骤之内求出线性规划问题的最优解。 | , 0D x A x b x1 0Bx B

13、bmnC线性规划问题中解的概念 实例 线性规划标准型为 于是 取矩阵 A的线性无关列 P1和 P2构成 2阶非奇异子矩阵 ， B1是线性规划问题的一个 基矩阵，与其对应的基变量为 x1和 x2，即 ，相应的非基矩阵和非基变量分别为 令非基变量 x3=0，可以求出对应基矩阵 B1的基本解为 ，基矩阵 B1解向量的各分量均为非负，故是线性规划问题的基本可行解。如果这个解可以使得目标函数取得最大值则该解为最优解。是否最优解的判断方法将在后续的章节中探讨。 若取矩阵 A的后两个线性无关列 P2和 P3，构成线性规划的另一个基矩阵 用相同的方法进行分析，可知，此时的基变量为 x2和 x3，非基变量为 x

14、1，于是令 x1=0，可以得到对应基矩阵 B2的一组基本解为： ，由于对应基矩阵 B2解向量的第二个分量即 x3为负，故该解不是线性规划问题的基本可行解 由理论分析可知，该线性规划问题基本解的个数为 3个，也就是还可以选取 P1和 P3构成基矩阵 B3，求取该问题的第三个基本解，只要有一个基矩阵，就可以求出一个对应的基本解，至于该基本解是否基本可行解和最优解则需要进一步判断。 1 2 31 2 31 2 31 2 32m a x3s .t.21, , 0f x x xx x xx x xx x x1 2 31 1 1112A P P P1 1 2 1111B P P1 12TB xxx1312NP 1 3N xx1 2 1 0Bx2 2 31112B P P2 0 7 4Bx线性规划问题的图解法 用图解法求解如下二维线性规划问题 分析可行域 引入平面直角坐标系，以 x1作为横轴，以 x2作为纵轴，由于线性规划问题满足非负条件 x1, x2 0，故问题的探讨局限在平面直角坐标系的第一象限 分析 x1-2x2 4，取直线