经济数学基础(顾静相)teaching_09_08.ppt

《经济数学基础(顾静相)teaching_09_08.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、9.8.4约束方程有“≥”“＝”约束的情况举例9.8.1引例9.8.2单纯形表9.8.3约束方程均是“≤”约束的情况举例9.8单纯形方法9.7节中例1的标准形式，为，，，其中松驰变量　、　分别表示甲、乙两种原料的剩余量．，9.8.1引例返回1/87下一页下一页上一页上一页如果取标准形式的约束方程组中的变量、的系数列向量　　、　组成一个基　,那么．9.8.1引例返回2/87上一页上一页下一页下一页对应于基　的基变量为　、　，非基变量为、　、　．那么,用非基变量表示基变量，得9.8.1引例，．代入目标函数，得．返回3/87上一页上一页下一页下一

2、页如果把　也看作一个变量，那么上述式子可以写成：，，．(9.8,1)9.8.1引例返回4/87上一页上一页下一页下一页(9.8.1)式就是方程组，，．的一般解．9.8.1引例返回5/87上一页上一页下一页下一页当　　　　　　时，目标函数和基变量的取值为：，，．9.8.1引例由此得到线性规划问题的第一个基本可行解：．返回6/87上一页上一页下一页下一页这个基本可行解　表示工厂没有安排生产Ⅰ、Ⅱ、Ⅲ型三种产品，因此，甲、乙两种原料都没有被使用，工厂的利润也为　　．9.8.1引例返回7/87上一页上一页下一页下一页由于(9.8.1)式的第一行

3、中变量　、　、　的系数都是正数，如果将它们中的某一个换成基变量(换入者称为“进基”变量，换出者称为“出基”变量．)，则目标函数值有可能增大．为使利润增加多些，我们对第一行中　、　、　的系数作如下选择9.8.1引例返回8/87上一页上一页下一页下一页．“5”是变量　的系数，由此可以确定应让非基变量“进基”．有了进基变量，就必须从原基变量中换一个“出基”．9.8.1引例返回9/87上一页上一页下一页下一页当　进基时，　、　仍是非基变量，所以，由(9.8.1)式得，，．9.8.1引例返回10/87上一页上一页下一页下一页解上式中的两个不等式，得，

4、．只有选择．(9.8.3)9.8.1引例返回11/87上一页上一页下一页下一页说明：称(9.8.3)式为最小比值原则，它是用进基变量的约束方程系数列向量(或称进基列)中大于0的元素作除数,对应的常数作被除数，得到的商并取其中最小比值．当　　　时，原基变量　变为非基变量，取为　　　，由此确定了出基变量为　．9.8.1引例返回12/87上一页上一页下一页下一页为了获得以　、　为基变量的一个基本可行解，只须对方程组(9.8.2)的增广矩阵施行初等行变换,使新基变量　所对应的系数列向量变为原基变量　所对应的单位列向量,即初等行变换9.8.1引例返回13

5、/87上一页上一页下一页下一页②变换后的增广矩阵所表示的方程组的一般解为：9.8.1引例(9.8.4)，，，返回14/87上一页上一页下一页下一页其中　、　、是非基变量.当　　　　　，得　　　,并且得到另一个基本可行解　　，9.8.1引例．获得的新基是由原约束方程组中变量　、的系数列向量组成．返回15/87上一页上一页下一页下一页从(9.8.4)式中的第一个方程看到,非基变量　的系数是正数，它表示目标函数值还能增加，　不是最优解.重复上述方法，可以确定非基变量　进基，再由(9.8.4)式的增广矩阵9.8.1引例返回16/87上一页上一页下一页下

6、一页中　所在列与常数列(第一行元素除外)用最小比值原则9.8.1引例返回17/87上一页上一页下一页下一页．确定了基变量　出基．9.8.1引例然后用初等行变换，进行换基迭代，获得由基变量　、　的系数列向量组成的新基，即返回18/87上一页上一页下一页下一页9.8.1引例返回19/87上一页上一页下一页下一页，，，(9.8.5)9.8.1引例它对应的一般解为返回20/87上一页上一页下一页下一页其中　、、是非基变量．当时，得　　　，获得另一个基本可行解：9.8.1引例．返回21/87上一页上一页下一页下一页在(9.8.5）式的第一行(目标函数)中

7、，非基变量　、　、　的系数都不是正数．这说明如果非基变量　、　、　中的某一个变量进基，都将会使目标函数值减少．所以，　　已经是最优解，对应的　　　就是最优值．这也就是说，该工厂把甲、乙两种原料全部用于生产Ⅰ型和Ⅱ型两种产品，基中Ⅰ型生产8吨，Ⅱ型生产26吨，才能获得最大利润154千元．9.8.1引例返回22/87上一页上一页下一页下一页设　阶矩阵　为线性规划问题，，(9.8.6)9.8.2单纯形表返回23/87上一页上一页下一页下一页9.8.2单纯形表返回24/87上一页上一页下一页下一页(其中)的一个基，　表示基变量在目标函数中的系数组成的行

8、矩阵，如果记，，，，．则对应于基　的单纯形表　　为9.8.2单纯形表返回25/87上一页上一页下一页下一页简记为:表中的第一行除最后一个分量外，其余