(1.3.1)--2线性规划的标准型.pdf

《(1.3.1)--2线性规划的标准型.pdf》由会员分享，可在线阅读，更多相关《(1.3.1)--2线性规划的标准型.pdf（27页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、运运 筹筹 学学第二章第二章线性规划的标准型线性规划的标准型线性规划化的标准型2主 要 内 容1线性规划一般形式和特点3线性规划一般形式化标准型的方法一一、线性规划模型的一般形式和特点线性规划模型的一般形式和特点112211112211211222221122().()().()nnnnnnmmmnnmMax Minzc xc xc xa xa xa xba xa xa xbstaxaxa xb 每一个问题都有一组变量-称为决策变量，一般记为对决策变量每一组值：代表了一种决策方案。通常要求决策变量取值非负，即.,21nxxxTnxxx),()0()0(2)0(1).,2,1(,0nixi一一、

2、线性规划模型的一般形式和特点线性规划模型的一般形式和特点 每个问题中都有决策变量需满足的一组约束条件-线性的等式或不等式。一一、线性规划模型的一般形式和特点线性规划模型的一般形式和特点 都有一个关于决策变量的线性函数,在满足约束条件下实现最大化或最小化-称为目标函数。因此，我们将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linearprogramming)其数学模型为：一一、线性规划模型的一般形式和特点线性规划模型的一般形式和特点nnxcxcxcZ2211max(min),2,1(,0),(),(),(.221122222121112121

3、11njxbxaxaxabxaxaxabxaxaxatsjmnmnmmnnnn二、线性规划的标准型上述模型的简写形式为：njjjxcZ1max(min),2,1(0),2,1(),(.1njxmibxatsjnjijij二、线性规划的标准型若令);,(21ncccC;21nxxxX;21mbbbb),(21212222111211nmnmmnnPPPaaaaaaaaaA二、线性规划的标准型线性规划问题可记为矩阵和向量的形式：CXZ max(min)0),(.XbAXtsCXZ max(min)0),(.1XbxPtsnjjj用向量表示时，上述模型可写为：二、线性规划的标准型LP问题的数学模型的

4、标准形式为：nnxcxcxcZ2211max11112211211222221122.0,(1,2,)nnnnmmmnnmja xa xa xba xa xaxbstaxaxaxbxjn其中常数项,0ib),2,1(mi二、线性规划的标准型二、线性规划的标准型LPLP问题标准形式的特征：问题标准形式的特征：求目标函数的求目标函数的最大值最大值；约束条件中变量满足线性方程组与非约束条件中变量满足线性方程组与非负性两部分；负性两部分；方程组中右端方程组中右端常数项常数项皆皆非负非负。下面分析如何将LP问题标准化：1.若目标函数为nnxcxcxcZ2211min引进新的目标函数则Z的最小值即为的最大

5、值三、线性规划的一般形式化标准型方法ZZ maxmin目标函数变换为：nnxcxcxcZ2211maxZ,ZZ例1 将LP问题3212minxxxZ)2,1(0222.31321ixxxxxxtsi化为标准形。三、线性规划的一般形式化标准型方法解：引进新的目标函数,ZZ于是原LP问题化为标准形式：)2,1(0222.31321ixxxxxxtsi3212maxxxxZ三、线性规划的一般形式化标准型方法2.若约束方程为不等式三、线性规划的一般形式化标准型方法约束方程为“”不等式,则可在“”不等式的左端加入非负松弛变量，把原不等式变为等式。2.若约束方程为不等式三、线性规划的一般形式化标准型方法约

6、束方程为“”不等式，则可在“”不等式的左端减去非负剩余变量（也可称松弛变量），把原不等式变为等式约束条件。例2 将LP问题化为标准形。三、线性规划的一般形式化标准型方法052327.323,2,1321321321321xxxxxxxxxxxxtsxxxzMin解：步骤（1）在第一个约束不等式“”号的左端加入松弛变量（2）在第二个约束不等式“”号的左端减去剩余变量（3）把目标函数最小化改成最大化三、线性规划的一般形式化标准型方法于是原LP问题化为标准形式：三、线性规划的一般形式化标准型方法0,52327.0032543213215321432154321xxxxxxxxxxxxxxxxtsxx

7、xxxzMax3.若变量为无约束，右端常数项为负三、线性规划的一般形式化标准型方法可令0,0,kkkkxxxxxk不等式两端乘以-1.例3 将LP问题化为标准形。三、线性规划的一般形式化标准型方法无约束3,2,1321321321321,052327.32xxxxxxxxxxxxtsxxxzMin解：步骤（1）用x4-x5代替x3（2）在第一个约束不等式“”号的左端加入松弛变量（3）在第二个约束不等式“”号的左端减去剩余变量（4）把目标函数最小化改成最大化三、线性规划的一般形式化标准型方法于是原LP问题化为标准形式：三、线性规划的一般形式化标准型方法2145671245612457124512456723-)00-)7-)2.32-)5,0Max zxxx xxxxxx xxxxx xxstxxx xx x x x x x（1.线性规划一般形式和特点结结语语2.线性规划的标准型3.线性规划的一般形式化标准型的方法