运筹学基础 课件 第3章.pptx

第3章线性规划;

3.1约束目标标准型;

;

若记

则其一般形式可以表示为;

3.1.2线性规划的标准形式

定义3-2线性规划的标准形式为

则标准形式可以记为;

定理3-1线性规划的一般形式可以转换为等价的标准形式。

对于目标函数,可以通过将系数向量取负,将最大化和最小化目标函数进行互化。对于约束条件来讲,不等式可以通过增加辅助决策变量的方法进行转换,遵循以下转换规则:

(1)对于小于不等式,在左侧加上一个辅助决策变量。

(2)对于大于不等式,在左侧减去一个辅助决策变量。;

例3-1对于如下线性规划模型的一般形式,将其转换为标准形式。

先通过将系数向量取负,将目标函数转换为最小化,然后增加一个辅助决策变量将约束条件不等式转换为等式,得到如下标准形式;

3.1.3-整数线性规划

定义3-3-如果线性规划的所有决策变量都必须是整数,那么这个问题称为整数规划问题。

例3-2有三种物品A、B、C,单位物品的重量分别为1、2、3,单位物品的价值分别为15、33、50,背包的最大载重为4,请问可装入背包的物品的最大价值是多少?;

设装入背包的三种物品的数量分别为x1,x2,x3,则可以建立一般形式的线性规划模型

其中目标函数代表最大化装入背包中物品的价值,第一个约束条件代表装入背包中的物品总重量不能超过背包的最大载重4,第二个约束条件代表装入背包中物品的数量不能为负,第三个约束条件代表装入背包中物品的数量为整数;

定义3-4如果线性规划的所有决策变量只能取0或者1,则称之为0-1整数规划。;

;

3.2从无穷到有限之基解;

首先,线性规划标准形式约束条件的主体是一个线性方程组,另外加一个非负条件。;

若先不考虑非负条件,这个线性方程组可变为

与线性规划问题的可行域有如图3-1所示对应关系。;

;

定理3-2线性规划标准形式的可行域等于其约束条件组成的线性方程组的非负解集。

根据线性方程组解的理论,线性方程组的解有以下几种情况:

(1)无解,R(A)R(A,b)。

(2)唯一最优解,R(A)=R(A,b)=n。

3)无穷多最优解,R(A)=R(A,b)n。其中,A=[aij];b=[bi];i=1,…,m;j=1,…,n;R(·)代表矩阵的秩。;

因此,根据定理3-2,可以有以下结论:

(1)若线性规划标准形式约束条件构成的线性方程组无解,则线性规划问题无解。

(2)若此线性方程组有唯一非负解,则这个解是线性规划问题可行解也是最优解;若此线性方程组有唯一解,但是负数,则线性规划问题无解。

(3)若此线性方程组有无穷多非负解,则线性规划问题有可能有无穷多可行解,这种情况是线性规划研究的重点。;

3.2.2基解

在这种情况下,根据生成测试范例的朴素优化思想,我们可以往可解的方向碰碰运气。如果令任意n-m个变量取特定值(如取0),把它们看作常量,移动到等式的右边,得

这样方程组就可解了。;

定义3-6如果将n-m个变量取值为0,对线性规划标准形式约束条件构成的线性方程组求解,若能得到唯一解,则称此解为线性规划问题的基解,如果基解满足非负条件,则称为基可行解,取值为0的n-m个决策变量称为非基变量,等式左边的m个决策变量称为基变量,基变量对应的系数矩阵的列称为基向量,基向量组成的矩阵称为线性规划问题的基。;

例如,对于线性方程组(3-1),若有唯一解,则其所对应的线性规划问题的基为

其中,Pi为基向量,与基向量Pi相应的变量xi为基变量,否则称为非基变量。;

3.2.3-基解三定理

定理3-3-若线性规划问题存在可行域,则一定是凸集。;;

定理3-4若线性规划问题的可行域有界,则一定可在此凸集的顶点上达到最优。;

定理3-5线性规划的可行域的顶点与基可行解一一对应;;;

(2)若X不是基可行解,则X一定不是可行域的顶点。;

3.2.4基解的枚举

这样,由于最优解一定是基解,基解的数量是有限的,因此可以使用枚举法求解线性规划标准形式,步骤为:

步骤1:在n个决策变量中,选择m个决策变量作为基变量,其他变量取0,求线性规划标准形式隐含的线性规划方程组,若得到唯一解,则此唯一解就是基解,若非负,则是基可行解。

步骤2:循环执行步骤1直到找出所有的基可行解,对比其目标函数,使目标函数达到最优的即为最优解。;

例3-4对如下的线性规划一般形式的模型:

(1)将其可行域在二维坐标系中表示出来。