第1章 线性规划及其扩展1.2.pptVIP

定理1.2.4 如果线性规划问题（1.1.16）存在最优解，则一定存在基础最优解。即：线性规划问题的最优解一定可以在可行解集的极点上达到。 通过以上定理，可以得到以下结论： （1）线性规划问题的可行解集是一个凸集，可行解集可能有界也可能无界，但其极点（顶点）的个数是有限个； （2）线性规划问题的每个基本可行解对应于可行解集的极点； （3）若线性规划问题有最优解，则其最优解必可在可行解集的某个（或多个）极点上达到。 这就提供了寻求线性规划问题最优解的途径：在基本可行解中寻求最优解,而基本可行解的个数有限，不会超过基本解的个数，而基本解的个数不会超过 ，其中m,n分别为线性规划问题（1.1.16）中系数矩阵A的行数和列数，但穷举法仍然低效率的。 * 例1.2.1 用图解法求解例1.1.2。 解 例1.1.2的数学模型为（1.1.4）式，即 等值线 最优解 图解法求解两个变量的线性规划问题的步骤： (1)作出线性规划问题的可行解区域。本例是满足5个不等式的公共部分OABCD（见图1.2.1）。 (2)作出目标函数的等值线，并标出等值线的值增加的方向,本题作出目标函数的等值线2x1+3x2=6，并可以看出将该等值线向右上方平行移动其值是增加的（见图1.2.1）。 (3)根据目标函数求最大、最小值，求出问题的最优解。由于本题是求目标函数的最大值，将目标函数的等值线向右上方平行移动，当移动到B点使得目标函数达到最大。 等值线 最优解 例1.2.2 如果例1.1.2中产品B的单位利润不是3元而为4元，那么最优计划如何安排？最大利润是多少？ 解: 与例1.1.2建立线性规划问题数学模型（1.1.3）类似，则该线性规划问题的数学模型是： 线段BC上的点都是最优解 有无穷多最优解 线段BC上的点都是最优解 有无穷多最优解 例1.2.3 用图解法求解线性规划问题 最大值不存在 目标函数的最小值 最大值不存在 目标函数的最小值 例1.2.4 用图解法求解线性规划问题 最大值不存在 目标函数的最小值 例1.2.5 用图解法求解线性规划问题 解： 满足四个约束条件的公共部 分不存在（如图1.2.4），因此， 本题无可行解，当然亦无最优解。 （3）线性规划的解有以下情况： （1）线性规划问题的可行解区域都是凸多边形（凸集）； （2）线性规划问题如果有最优解，则一定在可行解区域的顶点上达到； 通过例1.2.1—1.2.5，我们可以看出两个变量线性规划问题的解具有以下特点： 1.2.2 线性规划问题的基本概念 对于线性规划问题（1.1.16） 定义1.2.1 例1.2.6 对于线性规划问题 （1.2.4） 可以表示成矩阵形式： 图1.2.5 基本解 基可行解 可行解 1.2.3 凸集及其性质 定义1.2.3 如实心圆（球）或实心椭圆（球）、长方形（体）或多边形（体）等都是凸集，圆环等不是凸集。如图1.2.6中的(a)、(b)和(c)都是凸集，(d)和(e)都不是凸集。 (a) (b) (c) (d) (e) 图1.2.6 例1.2.6 证明：线性规划问题（1.1.16）的可行解集是凸集。 定义1.2.4 (1.2.5) 定义1.2.5 的一个严格凸组合，则称 1.2.4 线性规划问题解的性质 定理1.2.1 线性规划问题(1.1.16)的可行解集 定理的结论已由例1.2.6所证明。 定理1.2.2 线性规划问题(1.1.16)的可行解 证明 必要性：若线性规划问题（1.1.17）的可行解 定理1.2.3 （1.2.8） * 安徽大学十一五规划教材