运筹学 《第一章 线性规划及单纯形法》

1、运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一章 线性规划及单纯形法n线性规划问题及其数学模型n图解法n单纯形法原理n单纯形法计算步骤n应用举例运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型例例1 1 美佳公司计划制造I,II两种家电产品.已知各制造一件时分别占用的设备A,B,C的台时, 每天可用于这两种家电的能力，各售出一件时的获利情况如下表所示.问该公司应制造两种家电各多少件,使获利最多。1.1 问题的提出产品I产品II每天可用能力设备A(h)0515设备B(h)6224设备C(h)1 15利润(h)2 1运筹学运筹学-线性规划及单纯形法线性规划

2、及单纯形法第一节 线性规划问题及其数学模型例例1 1 美佳公司计划制造I,II两种家电产品.已知各制造一件时分别占用的设备A,B,C的台时, 每天可用于这两种家电的能力，各售出一件时的获利情况如下表所示.问该公司应制造两种家电各多少件,使获利最多。分析产品I产品II每天可用能力设备A(h)0515设备B(h)6224设备C(h)1 15利润(h)2 1目标运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型例例1 1 美佳公司计划制造I,II两种家电产品.已知各制造一件时分别占用的设备A,B,C的台时, 每天可用于这两种家电的能力，各售出一件时的获利情况如下表所示

3、.问该公司应制造两种家电各多少件,使获利最多。分析产品I产品II每天可用能力设备A(h)0515设备B(h)6224设备C(h)1 15利润(h)2 1目标约束条件运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型例例1 1 美佳公司计划制造I,II两种家电产品.已知各制造一件时分别占用的设备A,B,C的台时, 每天可用于这两种家电的能力，各售出一件时的获利情况如下表所示.问该公司应制造两种家电各多少件,使获利最多。分析产品I产品II每天可用能力设备A(h)0515设备B(h)6224设备C(h)1 15利润(h)2 1目标约束条件如何体现目标?运筹学运筹学-线

4、性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型例例1 1 美佳公司计划制造I,II两种家电产品.已知各制造一件时分别占用的设备A,B,C的台时, 每天可用于这两种家电的能力，各售出一件时的获利情况如下表所示.问该公司应制造两种家电各多少件,使获利最多。分析产品I产品II每天可用能力设备A(h)0515设备B(h)6224设备C(h)1 15利润(h)2 1目标约束条件如何体现目标?运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型例例1 1 美佳公司计划制造I,II两种家电产品.已知各制造一件时分别占用的设备A,B,C的台时, 每天可用于这两

5、种家电的能力，各售出一件时的获利情况如下表所示.问该公司应制造两种家电各多少件,使获利最多。分析产品I产品II每天可用能力设备A(h)0515设备B(h)6224设备C(h)1 15利润(h)2 1目标约束条件如何体现约束?运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型建模产品I产品II每天可用能力设备A(h)0515设备B(h)6224设备C(h)1 15利润(h)2 1解解: : 设该公司应制造产品设该公司应制造产品I,II分别为分别为x1 1, ,x2 2件件则则, ,目标函数目标函数 max z = 2 x1 + 1 x2 约束条件约束条件 0 x1

6、 + 5 x2 15 6 x1 + 2 x2 24 1 x1 + 1 x2 5 x1 0，x20运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型建模产品I产品II每天可用能力设备A(h)0515设备B(h)6224设备C(h)1 15利润(h)2 1解解: : 设该公司应制造产品设该公司应制造产品I,II分别为分别为x1 1, ,x2 2件件则则, ,目标函数目标函数 max z = 2 x1 + 1 x2 约束条件约束条件 0 x1 + 5 x2 15 6 x1 + 2 x2 24 1 x1 + 1 x2 5 x1 0，x20运筹学运筹学-线性规划及单纯形法

7、线性规划及单纯形法第一节 线性规划问题及其数学模型建模产品I产品II每天可用能力设备A(h)0515设备B(h)6224设备C(h)1 15利润(h)2 1解解: : 设该公司应制造产品设该公司应制造产品I,II分别为分别为x1 1, ,x2 2件件则则, ,目标函数目标函数 max z = 2 x1 + 1 x2 约束条件约束条件 0 x1 + 5 x2 15 6 x1 + 2 x2 24 1 x1 + 1 x2 5 x1 0，x20运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型建模产品I产品II每天可用能力设备A(h)0515设备B(h)6224设备C(

8、h)1 15利润(h)2 1解解: : 设该公司应制造产品设该公司应制造产品I,II分别为分别为x1 1, ,x2 2件件则则, ,目标函数目标函数 max z = 2 x1 + 1 x2 约束条件约束条件 0 x1 + 5 x2 15 6 x1 + 2 x2 24 1 x1 + 1 x2 5 x1 0，x20运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型建模产品I产品II每天可用能力设备A(h)0515设备B(h)6224设备C(h)1 15利润(h)2 1解解: : 设该公司应制造产品设该公司应制造产品I,II分别为分别为x1 1, ,x2 2件件则则,

9、 ,目标函数目标函数 max z = 2 x1 + 1 x2 约束条件约束条件 0 x1 + 5 x2 15 6 x1 + 2 x2 24 1 x1 + 1 x2 5 x1 0，x20非负性约束运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型例例2 2 靠近某河流有2个化工厂，流经第1化工厂的河流流量为500万立方米/天，两个工厂之间有一条流量为200万立方米/天的支流。第1化工厂每天排污2万立方米，第2化工厂每天排污1.4万立方米。从第1化工厂排出的污水流到第2化工厂前，有20%可自然净化。根据环保要求，河流中污水含量不能大于0.2%。这两个工厂污水处理成本

10、分别是1000元/万立方米和800元/万立方米，问在满足环保要求的前提下，每个工厂应处理多少污水使总的污水处理费用最小。运筹学运筹学-线性规划及单纯形法线性规划及单纯形法工厂1工厂2500万m3/天200万m3/天排污量2万m3/天治污成本：1000元/万m3排污量1.4万m3/天治污成本：800元/万m3污水含量不大于0.2%x1x2(2-x1)/500=0.2%0.8(2-x1)+(1.4-x2)/700=0.2%x1=2,x2=1.4Min z=1000 x1+800 x2运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型例例3 3 捷运公司拟在下一年度的

11、1-4月的4个月内需租用仓库堆放物资。已知各月所需仓库面积列于表1。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表2。租借仓库的合同每月初都可以办理，每份合同具体规定租用面积数和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，使所付租借费用最小。月份1234所需面积(100m2)15102012表2合同租借期限(月 )1234合同期内租金（元/100m2)2800450060007300表1运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型例例3

12、3 捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资。已知各月所需仓库面积列于表1。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表2。租借仓库的合同每月初都可以办理，每份合同具体规定租用面积数和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，使所付租借费用最小。分析目标约束租借费用最小租借费用由每月初制定的不同的租借合同决定租借合同即租期和租借面积每月的租借面积因此可以将决策变量设为每月初签订的合同类型运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问

13、题及其数学模型建模解解: : 设则设则xij表示该公司在第表示该公司在第i月初签订的期限为月初签订的期限为j个个月的月的租借面积合同。即租借面积合同。即x11 表示表示1月份签订的合同期限为月份签订的合同期限为1个月的租借面积个月的租借面积x12表示表示1月份签订的合同期限为月份签订的合同期限为2个月的租借面积个月的租借面积x13表示表示1月份签订的合同期限为月份签订的合同期限为3个月的租借面积个月的租借面积x14表示表示1月份签订的合同期限为月份签订的合同期限为4个月的租借面积个月的租借面积月份1234所需面积(100m2)15102012表2合同租借期限(月 )1234合同期内租金（元/1

14、00m2)2800450060007300表1运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型建模解解: : 设则设则xij表示该公司在第表示该公司在第i月初签订的期限为月初签订的期限为j个个月的月的租借面积合同。即租借面积合同。即x11 表示表示1月份签订的合同期限为月份签订的合同期限为1个月的租借面积个月的租借面积x12表示表示1月份签订的合同期限为月份签订的合同期限为2个月的租借面积个月的租借面积x13表示表示1月份签订的合同期限为月份签订的合同期限为3个月的租借面积个月的租借面积x14表示表示1月份签订的合同期限为月份签订的合同期限为4个月的租借面积个

15、月的租借面积x21 表示表示2月份签订的合同期限为月份签订的合同期限为1个月的租借面积个月的租借面积x22表示表示2月份签订的合同期限为月份签订的合同期限为2个月的租借面积个月的租借面积x23表示表示2月份签订的合同期限为月份签订的合同期限为3个月的租借面积个月的租借面积x31表示表示3月份签订的合同期限为月份签订的合同期限为1个月的租借面积个月的租借面积x32 表示表示3月份签订的合同期限为月份签订的合同期限为2个月的租借面积个月的租借面积x41表示表示4月份签订的合同期限为月份签订的合同期限为1个月的租借面积个月的租借面积运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问

16、题及其数学模型建模解解: : 设设xij表示该公司在第表示该公司在第i月初签订的期限为月初签订的期限为j个个月的租借面积合月的租借面积合同。则同。则目标函数：目标函数：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面积(100m2)

17、15102012表2合同租借期限(月 )1234合同期内租金（元/100m2)2800450060007300表1合同期为一个月的租金运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型建模解解: : 设设xij表示该公司在第表示该公司在第i月初签订的期限为月初签订的期限为j个个月的租借面积合月的租借面积合同。则同。则目标函数：目标函数：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+x13+x14+x21

18、+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面积(100m2)15102012表2合同租借期限(月 )1234合同期内租金（元/100m2)2800450060007300表1合同期为两个月的租金运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型建模解解: : 设设xij表示该公司在第表示该公司在第i月初签订的期限为月初签订的期限为j个个月的租借面积合月的租借面积合同。则同。则目标函数：目标函数：min z = 2800(x

19、11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面积(100m2)15102012表2合同租借期限(月 )1234合同期内租金（元/100m2)2800450060007300表1合同期为三个月的租金运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性

20、规划问题及其数学模型建模解解: : 设设xij表示该公司在第表示该公司在第i月初签订的期限为月初签订的期限为j个个月的租借面积合月的租借面积合同。则同。则目标函数：目标函数：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面积(100

21、m2)15102012表2合同租借期限(月 )1234合同期内租金（元/100m2)2800450060007300表1合同期为四个月的租金运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型建模解解: : 设设xij表示该公司在第表示该公司在第i月初签订的期限为月初签订的期限为j个个月的租借面积合月的租借面积合同。则同。则目标函数：目标函数：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+x13+x14+

22、x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面积(100m2)15102012表2合同租借期限(月 )1234合同期内租金（元/100m2)2800450060007300表1一月份的租借面积约束运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型建模解解: : 设设xij表示该公司在第表示该公司在第i月初签订的期限为月初签订的期限为j个个月的租借面积合月的租借面积合同。则同。则目标函数：目标函数：min z = 280

23、0(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面积(100m2)15102012表2合同租借期限(月 )1234合同期内租金（元/100m2)2800450060007300表1二月份的租借面积约束运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节

24、 线性规划问题及其数学模型建模解解: : 设设xij表示该公司在第表示该公司在第i月初签订的期限为月初签订的期限为j个个月的租借面积合月的租借面积合同。则同。则目标函数：目标函数：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面积(

25、100m2)15102012表2合同租借期限(月 )1234合同期内租金（元/100m2)2800450060007300表1三月份的租借面积约束运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型建模解解: : 设设xij表示该公司在第表示该公司在第i月初签订的期限为月初签订的期限为j个个月的租借面积合月的租借面积合同。则同。则目标函数：目标函数：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+x13+x

26、14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面积(100m2)15102012表2合同租借期限(月 )1234合同期内租金（元/100m2)2800450060007300表1四月份的租借面积约束运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型建模解解: : 设设xij表示该公司在第表示该公司在第i月初签订的期限为月初签订的期限为j个个月的租借面积合月的租借面积合同。则同。则目标函数：目标函数：min z =

27、2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面积(100m2)15102012表2合同租借期限(月 )1234合同期内租金（元/100m2)2800450060007300表1非负性约束运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线

28、性规划问题及其数学模型建模解解: : 设设xij表示该公司在第表示该公司在第i月初签订的期限为月初签订的期限为j个个月的租借面积合月的租借面积合同。则同。则目标函数：目标函数：min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)月份1234所需面积(10

29、0m2)15102012表2合同租借期限(月 )1234合同期内租金（元/100m2)2800450060007300表1说明：建模时我们所设的决策变量（ x11,x21,x31,x41）,(x12,x22,x32),(x13,x23), x14只是说明一月份我们只是说明一月份我们最多可以签署四份期限不同的合同最多可以签署四份期限不同的合同,二月份可以签署三份期限不二月份可以签署三份期限不同的合同同的合同,三月份可以签署两份期限不同的合同三月份可以签署两份期限不同的合同,四月份一份合同四月份一份合同.这只是一种可能范围这只是一种可能范围,并不代表最终最优解中一定是要在一月份并不代表最终最优解中

30、一定是要在一月份签署四份签署四份,二月份签三份等等二月份签三份等等.如该题目的最优解为如该题目的最优解为:x11=3x31=8x14=12运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型构成要素模型构成要素变量（决策变量）目标函数约束条件1.2 线性规划问题的数学模型决策者通过控制和决定决策变量来选择和确定不同的方案、措施min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+x13+x14+x21+x22

31、+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型构成要素模型构成要素变量（决策变量）目标函数约束条件1.2 线性规划问题的数学模型决策变量的线性函数，根据优化目标为max,minmin z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+x13+x14+

32、x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型构成要素模型构成要素变量（决策变量）目标函数约束条件1.2 线性规划问题的数学模型反映为实现目标所受到的资源的约束，为不等式或等式。min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+

33、x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型假设模型假设比例性（或固定规模报酬）可叠加性连续性1.2 线性规划问题的数学模型max z = 2 x1 + 1 x20 x1 + 5 x2 156 x1 + 2 x2 241 x1 + 1 x2 5x1 0，x20运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型假设模型假设比例性（或

34、固定规模报酬）可叠加性连续性1.2 线性规划问题的数学模型规模报酬递增：企业的生产规模扩大后，收益增加的幅度要大于规模扩大的幅度，或者说随着生产能力和产量的扩大，单位产品的成本会随之下降。比如：投资1000元获得利润150元，投资2000元可获得利润400元。 反之称规模报酬递减。max z = 2 x1 + 1 x20 x1 + 5 x2 156 x1 + 2 x2 241 x1 + 1 x2 5x1 0，x20运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型假设模型假设比例性（或固定规模报酬）可叠加性连续性1.2 线性规划问题的数学模型每个决策变量对目

35、标函数和约束方程的影响是独立于其它变量的，目标函数值是每个决策变量对目标函数的总和。 max z = 2 x1 + 1 x20 x1 + 5 x2 156 x1 + 2 x2 241 x1 + 1 x2 5x1 0，x20运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型假设模型假设比例性（或固定规模报酬）可叠加性连续性1.2 线性规划问题的数学模型决策变量取连续值。max z = 2 x1 + 1 x20 x1 + 5 x2 156 x1 + 2 x2 241 x1 + 1 x2 5x1 0，x20运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节

36、线性规划问题及其数学模型模型假设模型假设比例性（或固定规模报酬）可叠加性连续性确定性1.2 线性规划问题的数学模型所有参数都是确定的参数，不包含随机因素。max z = 2 x1 + 1 x20 x1 + 5 x2 156 x1 + 2 x2 241 x1 + 1 x2 5x1 0，x20运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型一般形式模型一般形式1.2 线性规划问题的数学模型max(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+

37、a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00min z = 2800(x11+x21+x31+x41)+4500(x12+x22+x32) + 6000(x13+x23)+7300 x14约束条件：约束条件：x11+x12+x13+x1415 x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x3

38、1+x32 20 x14+x23+x32+x41 12 xij 0(i=1,2,3,4;j=1,2,3,4)max z = 2 x1 + 1 x20 x1 + 5 x2 156 x1 + 2 x2 241 x1 + 1 x2 5x1 0，x20( (假定有假定有n n个决策变量个决策变量, ,m m个约束个约束) )运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型和式模型和式1.2 线性规划问题的数学模型),.,1(0),.,1()(min)max(11njxmibxaxczjinjjijnjjj，或或max(max(或或min)z=cmin)z=c1 1

39、x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型和式模型和式1.2 线性规划问题的数学模型),.,1(0),.,1()(min)ma

40、x(11njxmibxaxczjinjjijnjjj，或或max(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节

41、线性规划问题及其数学模型模型向量形式模型向量形式1.2 线性规划问题的数学模型0)(min)max(1XbxPCXznjjj，或或C=（c1,c2,cn)max(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1

42、 1,x,x2 2,x,xn n 00运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型向量形式模型向量形式1.2 线性规划问题的数学模型0)(min)max(1XbxPCXznjjj，或或x1x2.xnmax(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+

43、a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型向量形式模型向量形式1.2 线性规划问题的数学模型0)(min)max(1XbxPCXznjjj，或或mnmmnnnaaaaaaaaaPPP.),.,(21222211121121max(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，

44、）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型向量形式模型向量形式1.2 线性规划问题的数学模型0)(min)max(1XbxPCXznjjj，或或mbbb21max(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1

45、111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型向量形式模型向量形式1.2 线性规划问题的数学模型0)(min)max(1XbxPCXznjjj，或或nnnnxcxcxcxxxccc22112121max

46、(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx x1 1,x,x2 2,x,xn n 00运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型向量形式模型向量形式1.2 线性规划

47、问题的数学模型0)(min)max(1XbxPCXznjjj，或或mnmnnnmmbbbxaaaxaaaxaaa21212222121121111P2PnPbmax(max(或或min)z=cmin)z=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn na a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n（或，或，）b b1 1a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n（或，或，）b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n（或，或，）b bm mx

48、x1 1,x,x2 2,x,xn n 00运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型模型矩阵和向量形式模型矩阵和向量形式1.2 线性规划问题的数学模型0)(min)max(XbAXCXz，或或mnmnmmnnbbbxxxaaaaaaaaa2121212222111211),(或AXb运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式0maxXbAXCXz标准形式的特征?1 目标函数 最大化运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式0maxXbAXCXz

49、标准形式的特征?1 目标函数 最大化2 b0运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式0maxXbAXCXz标准形式的特征?1 目标函数 最大化2 b03 约束条件为等号运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式0maxXbAXCXz标准形式的特征?1 目标函数 最大化2 b03 约束条件为等号4 决策变量X 0运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式0maxXbAXCXz1 目标函数 min z化标准形式的方法化标准形式的方

50、法令z=-z则min z=CX 等价于max z= - CX)4 , 3 , 2 , 1(042634334min4213212121jxxxxxxxxxxxzj)4 , 3 , 2 , 1(042634334max4213212121jxxxxxxxxxxxzj令z=-z运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式0maxXbAXCXz1 目标函数 min z2 bi0化标准形式的方法化标准形式的方法第i个约束方程两边乘以(-1)-ai1-ai2-ain=-bi)4 , 3 , 2 , 1(042634334max4213212121jx

51、xxxxxxxxxxzj)4 , 3 , 2 , 1(042634334max4213212121jxxxxxxxxxxxzj运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式0maxXbAXCXz1 目标函数 min z2 bi03 约束条件或0化标准形式的方法化标准形式的方法若0，则加松弛变量若0，则减剩余变量（松弛变量，剩余变量均非负） 6x1+2x20标准化为6x1+2x2+x3=0 10 x1+12x20标准化为10 x1+12x2- x4 =0这里x3， x4 0运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及

52、其数学模型1.3 标准形式0maxXbAXCXz1 目标函数 min z2 bi03 约束条件或04 决策变量0或无约束 化标准形式的方法化标准形式的方法若xi0，则令xi=- xi若xi 无约束,则令xi= xi- xi xi, xi 0 6x1+2x2=0 X2无约束标准化为6x1+2x2- 2x2=0这里x2 ， x2 0运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式取值无约束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz例例3 3 将下述线性规划化为标准形式将下述线性规划化为标准

53、形式分析1 目标函数不标准运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式取值无约束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz例例3 3 将下述线性规划化为标准形式将下述线性规划化为标准形式分析1 目标函数不标准2 b不标准运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式取值无约束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz例例3 3 将下述线性规划化为标准形式将下述线性规划化为

54、标准形式分析1 目标函数不标准2 b不标准3 决策变量不标准运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式取值无约束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz例例3 3 将下述线性规划化为标准形式将下述线性规划化为标准形式分析1 目标函数不标准2 b不标准3 决策变量不标准4 不符合等式约束运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式求解求解解：令x1=-x1，x3-x3=x3，z=-z，约束加松弛变量x4,约束减去剩余变量x5,

55、约束两边乘以-1，则模型等价于取值无约束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz924 3321xxxxx42235 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054 3321xxxxxx 3321332maxxxxxz运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式求解求解解：令x1=-x1，x3-x3=x3，z=-z，约束加松弛变量x4,约束减去剩余变量x5,约束两边乘以-1，则模型等价于取值无约束321321321321321, 0, 0632

56、44239232minxxxxxxxxxxxxxxxz924 3321xxxxx42235 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054 3321xxxxxx 3321332maxxxxxz运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式求解求解解：令x1=-x1，x3-x3=x3，z=-z，约束加松弛变量x4,约束减去剩余变量x5,约束两边乘以-1，则模型等价于取值无约束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz924 3321xxxxx4223

57、5 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054 3321xxxxxx 3321332maxxxxxz运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式求解求解解：令x1=-x1，x3-x3=x3，z=-z，约束加松弛变量x4,约束减去剩余变量x5,约束两边乘以-1，则模型等价于取值无约束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz924 3321xxxxx42235 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054

58、3321xxxxxx 3321332maxxxxxz运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式求解求解解：令x1=-x1，x3-x3=x3，z=-z，约束加松弛变量x4,约束减去剩余变量x5,约束两边乘以-1，则模型等价于取值无约束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz924 3321xxxxx42235 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054 3321xxxxxx 3321332maxxxxxz运筹学运筹学-线性规划及单纯形法线性

59、规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式求解求解解：令x1=-x1，x3-x3=x3，z=-z，约束加松弛变量x4,约束减去剩余变量x5,约束两边乘以-1，则模型等价于取值无约束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz924 3321xxxxx42235 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054 3321xxxxxx 3321332maxxxxxz运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型1.3 标准形式求解求解解：令x1=-x1

60、，x3-x3=x3，z=-z，约束加松弛变量x4,约束减去剩余变量x5,约束两边乘以-1，则模型等价于取值无约束321321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz924 3321xxxxx42235 3321xxxxx63324 3321xxxx0, 0, 0, 0, 0, 054 3321xxxxxx 3321332maxxxxxz运筹学运筹学-线性规划及单纯形法线性规划及单纯形法第一节 线性规划问题及其数学模型练习1取值无约束43214321432143214321, 0,2321422245243minxxxxxxxxxxxxxxxxx