规划模型(运筹学)课件

1、运筹学（运筹学（Operations ResearchOperations Research）是用数学方法研究各种系统的最）是用数学方法研究各种系统的最优化问题，运筹学强调发挥现有系统的效能，应用数学模型求得合理利优化问题，运筹学强调发挥现有系统的效能，应用数学模型求得合理利用各种资源的最佳方案，为决策者提供科学决策的依据。用各种资源的最佳方案，为决策者提供科学决策的依据。 运筹学的内容有数学规划，运输问题，图与网络分析，排队论，存运筹学的内容有数学规划，运输问题，图与网络分析，排队论，存储论，决策论和对策论等，其中数学规划又包括线性规划，整数规划，储论，决策论和对策论等，其中数学规划又包括线

2、性规划，整数规划，非线性规划，目标规划和动态规划等，非线性规划，目标规划和动态规划等，虽然运筹学包括的内容较多，但是它们有两个共同的特点：一是以虽然运筹学包括的内容较多，但是它们有两个共同的特点：一是以全局最优作为问题的基本出发点；二是通过建立数学模型，运用优化技全局最优作为问题的基本出发点；二是通过建立数学模型，运用优化技术求得系统最合理的运营方案。由于各种系统的运营机制和性能不尽相术求得系统最合理的运营方案。由于各种系统的运营机制和性能不尽相同，它们的数学模型也各不相同，从而形成了运筹学的不同分支。同，它们的数学模型也各不相同，从而形成了运筹学的不同分支。学习内容：线性规划、整数规划学习内

3、容：线性规划、整数规划要求：建立模型、软件求解（要求：建立模型、软件求解（Matlab）运筹学（运筹学（Operations ResearchOperations Research）是用数学方法研究各种系统的最）是用数学方法研究各种系统的最优化问题，运筹学强调发挥现有系统的效能，应用数学模型求得合理利优化问题，运筹学强调发挥现有系统的效能，应用数学模型求得合理利用各种资源的最佳方案，为决策者提供科学决策的依据。用各种资源的最佳方案，为决策者提供科学决策的依据。 运筹学的内容有数学规划，运输问题，图与网络分析，排队论，存运筹学的内容有数学规划，运输问题，图与网络分析，排队论，存储论，决策论和对策

4、论等，其中数学规划又包括线性规划，整数规划，储论，决策论和对策论等，其中数学规划又包括线性规划，整数规划，非线性规划，目标规划和动态规划等，非线性规划，目标规划和动态规划等，虽然运筹学包括的内容较多，但是它们有两个共同的特点：一是以虽然运筹学包括的内容较多，但是它们有两个共同的特点：一是以全局最优作为问题的基本出发点；二是通过建立数学模型，运用优化技全局最优作为问题的基本出发点；二是通过建立数学模型，运用优化技术求得系统最合理的运营方案。由于各种系统的运营机制和性能不尽相术求得系统最合理的运营方案。由于各种系统的运营机制和性能不尽相同，它们的数学模型也各不相同，从而形成了运筹学的不同分支。同，

5、它们的数学模型也各不相同，从而形成了运筹学的不同分支。 所以可对运筹学做如下概括：所以可对运筹学做如下概括：，运筹学的研究对象是各种系统，运筹学的研究对象是各种系统，运筹学的研究目的是实现系统的最优化，求得合理利用各种资源，运筹学的研究目的是实现系统的最优化，求得合理利用各种资源的最优方案，的最优方案，运筹学的研究方法是运用数学语言来描述实际系统，通过建立数，运筹学的研究方法是运用数学语言来描述实际系统，通过建立数学模型和优化技术求得系统运营的最优解。学模型和优化技术求得系统运营的最优解。，运筹学的研究动机是，运筹学的研究动机是为决策者提供科学决策的依据。为决策者提供科学决策的依据。 运筹学在

6、工业，农业，商业，物流，经济计划，人力资源，军事运筹学在工业，农业，商业，物流，经济计划，人力资源，军事等行业都有着非常广泛的应用。有人曾对世界上等行业都有着非常广泛的应用。有人曾对世界上500500家著名的企业集家著名的企业集团或跨国公司进行过调查，发现其中团或跨国公司进行过调查，发现其中95%95%曾使用过线性规划，曾使用过线性规划，75%75%使用使用过运输模型，过运输模型，90%90%使用过网络计划技术，使用过网络计划技术，90%90%使用过存储模型，使用过存储模型，43%43%使使用过动态规划。用过动态规划。 由此可见运筹学一门应用性很强的学科。特别是随着计算机技术由此可见运筹学一门

7、应用性很强的学科。特别是随着计算机技术的不断发展，计算机成为运筹学最强有力的运算工具，运筹学越来越的不断发展，计算机成为运筹学最强有力的运算工具，运筹学越来越显示出其广泛的使用价值。显示出其广泛的使用价值。 运筹学这一名词最早出现于运筹学这一名词最早出现于19381938年。当时英，美等国盟军在与德年。当时英，美等国盟军在与德国的战争中遇到了许多错综复杂的战略和战术问题难以解决，比如国的战争中遇到了许多错综复杂的战略和战术问题难以解决，比如，防空雷达的布置问题：英美等国为了对付德国的空袭配备了先进，防空雷达的布置问题：英美等国为了对付德国的空袭配备了先进的雷达作为防空系统的一部分，但是由于雷达

8、系统的布置不甚合理，的雷达作为防空系统的一部分，但是由于雷达系统的布置不甚合理，通过防空演习发现实际效果并不理想，通过防空演习发现实际效果并不理想，护航舰队的编队问题：英美等国需要对本国的商船队配备护航舰，护航舰队的编队问题：英美等国需要对本国的商船队配备护航舰队，以防止德国潜艇的攻击，这里有一个如何合理编队才能使商船队队，以防止德国潜艇的攻击，这里有一个如何合理编队才能使商船队一旦遭受德国潜艇攻击时损失最少的问题。一旦遭受德国潜艇攻击时损失最少的问题。 为了应付上述各种复杂问题，英美等国逐批召集不同专业背景的为了应付上述各种复杂问题，英美等国逐批召集不同专业背景的科学家，在三军组织了各种研究

9、小组，研究的问题都是军事性质的，科学家，在三军组织了各种研究小组，研究的问题都是军事性质的，在英国称为在英国称为“Operational ResearchOperational Research”，其他英语国家称为，其他英语国家称为“Operations ResearchOperations Research”，意思是军事行动研究。这些研究小组运用，意思是军事行动研究。这些研究小组运用系统优化的思想，应用数学技术分析军事问题，取得了非常理想的效系统优化的思想，应用数学技术分析军事问题，取得了非常理想的效果。果。二次大战以后，在军事运筹小组中工作过的一部分科学家开始转二次大战以后，在军事运筹小组

10、中工作过的一部分科学家开始转入民用部门，他们把对军事系统最优化的研究成果拓展到各种民用系入民用部门，他们把对军事系统最优化的研究成果拓展到各种民用系统的研究上。统的研究上。 19471947年美国数学家年美国数学家G.B.DantzigG.B.Dantzig在研究美国空军资源配置时在研究美国空军资源配置时, ,提提出了求解线性规划的有效方法出了求解线性规划的有效方法单纯形法。二十世纪五十年代初，应单纯形法。二十世纪五十年代初，应用计算机求解线性规划获得成功。用计算机求解线性规划获得成功。 至五十年代末，一些工业先进国家的大型企业已经较普遍地使用至五十年代末，一些工业先进国家的大型企业已经较普遍

11、地使用运筹学方法解决在生产经营管理中遇到的实际问题，并取得了良好的运筹学方法解决在生产经营管理中遇到的实际问题，并取得了良好的效果，至六十年代中期，运筹学开始应用于一些服务性行业和公用事效果，至六十年代中期，运筹学开始应用于一些服务性行业和公用事业。业。 同时同时很多国家成立了运筹学研究学会，很多国家成立了运筹学研究学会，一些大学的相关专业也陆一些大学的相关专业也陆续设置了运筹学的有关课程。专门发表运筹学研究论文的刊物开始出续设置了运筹学的有关课程。专门发表运筹学研究论文的刊物开始出版，运筹学的理论研究日趋成熟，在实际应用上则日趋广泛。版，运筹学的理论研究日趋成熟，在实际应用上则日趋广泛。 问

12、题的提出：问题的提出： 在生产管理的经营活动中，通常需要对在生产管理的经营活动中，通常需要对“有限的资源有限的资源”寻求寻求“最佳最佳”的利用或分配方式。的利用或分配方式。l有限资源：劳动力、原材料、设备或资金等有限资源：劳动力、原材料、设备或资金等 l最佳：有一个标准或目标，使利润达到最大或成本达到最小。最佳：有一个标准或目标，使利润达到最大或成本达到最小。 有限资源的合理配置有两类问题有限资源的合理配置有两类问题l如何合理的使用有限的资源，使生产经营的效益达到最大；如何合理的使用有限的资源，使生产经营的效益达到最大；l在生产或经营的任务确定的条件下，合理的组织生产，安排经在生产或经营的任务

13、确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少。营活动，使所消耗的资源数最少。 线性规划问题及其数学模型线性规划问题及其数学模型 与规划问题有关的数学模型总有两部分组成：与规划问题有关的数学模型总有两部分组成：l约束条件：反映了有限资源对生产经营活动的种种约束，约束条件：反映了有限资源对生产经营活动的种种约束，或者生产经营必须完成的任务；或者生产经营必须完成的任务；l目标函数：反映生产经营者在有限资源条件下希望达到目标函数：反映生产经营者在有限资源条件下希望达到的生产或经营的目标。的生产或经营的目标。例，例，某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生某制药厂生产

14、甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：周可提供的资源总量如下表所示：每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤） 30302020160160设备（台班）设备（台班） 5 51 11515已知该厂生产每吨甲、乙药品的利润分别为已知该厂生产每吨甲、乙药品的利润分别为5 5万元和万元和2 2万元。但根据万元。但根据市场需求调查的结果，甲药品每周的产量不应超过市场需求调查的结果，甲药品每周的产量

15、不应超过4 4吨。问该厂应如何安吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？排两种药品的产量才能使每周获得的利润最大？ 定义定义x x1 1为生产甲种药品的计划产量数，为生产甲种药品的计划产量数，x x2 2为生产乙种药品的计划产量数。为生产乙种药品的计划产量数。目标：目标： 使总利润使总利润 Z=5xZ=5x1 1+2x+2x2 2 极大化极大化 约束：约束： 每周资源总量的限制，每周资源总量的限制， 30 x30 x1 1+20 x+20 x2 2160160 5x5x1 1+ x+ x2 2 1515甲种药品每周产量不应超过甲种药品每周产量不应超过4 4吨的限制吨的限制

16、x x1 144计划生产数不可能是负数，计划生产数不可能是负数， x x1 10 x0 x2 200每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤） 30302020160160设备（台班）设备（台班） 5 51 11515单位利润（万元）单位利润（万元） 5 5 数学模型为数学模型为 s.t.s.t. （subject to)subject to) (such that) (such that) 这是一个如何合理的使用有限的资源，使生产经营的效益达到最大这是一个如何合理的使用有限的资源，使生产经营的效益达到最大的数学规划问题。的数学规划问题。 在满

17、足一组约束条件的限制下，寻求决策变量在满足一组约束条件的限制下，寻求决策变量x x1 1，x x2 2的决策值，使目的决策值，使目标函数达到最大值。标函数达到最大值。121212112maxZ=5x +2x30 x20 x1605xx15x4x0,x0每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤） 30302020160160设备（台班）设备（台班） 5 51 11515单位利润（万元）单位利润（万元） 5 5例：例：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品。

18、已知甲、乙两种原料都含有混合配制而成的特种产品。已知甲、乙两种原料都含有A A、B B、C C三种三种化学成分，两种原料分别所含三种化学成分的百分比含量，以及按合化学成分，两种原料分别所含三种化学成分的百分比含量，以及按合同规定的产品中三种化学成分的最低含量如下表所示：同规定的产品中三种化学成分的最低含量如下表所示： 已知甲、乙两种原料的成本分别是每公斤已知甲、乙两种原料的成本分别是每公斤3 3元和元和2 2元，厂方希望元，厂方希望总成本达到最小，问如何配置该产品？总成本达到最小，问如何配置该产品？ 原料原料化学成分含量（化学成分含量（% %） 产品中化学成分的最低含量产品中化学成分的最低含量

19、（% %） 甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5化学成分化学成分定义定义x x1 1，x x2 2分别为每公斤产品中甲，乙两种原料的数量，分别为每公斤产品中甲，乙两种原料的数量，目标：使总成本目标：使总成本 Z=3xZ=3x1 1+2x+2x2 2 极小化极小化 约束：配料平衡条件，约束：配料平衡条件， x x1 1+x+x2 2=1=1产品中产品中A A、B B、C C三种化学成分的最低含量三种化学成分的最低含量 12x12x1 1+3x+3x2 244 2x2x1 1+3x+3x2 222 3x3x1 1+15x+15x2 255非负性条件非

20、负性条件 x x1 10,x0,x2 200 原料原料化学成分含量（化学成分含量（% %） 产品中化学成分的最低含量产品中化学成分的最低含量（% %） 甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5单位成本（元）单位成本（元）化学成分化学成分 数学模型：数学模型： s.t.s.t. 这是一个原料配制问题，是在生产任务确定的条件下，合理的组织这是一个原料配制问题，是在生产任务确定的条件下，合理的组织 生产，使所消耗的资源数最少的数学规划问题。生产，使所消耗的资源数最少的数学规划问题。 满足一组约束条件的同时，寻求变量满足一组约束条件的同时，寻求变量x x1

21、1和和x x2 2的值使目标函数取得最小的值使目标函数取得最小 值。值。 原料原料化学成分含量（化学成分含量（% %） 产品中化学成分的最低含量（产品中化学成分的最低含量（% %） 甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5单位成本（元）单位成本（元）化学成分化学成分121212121212minZ=3x +2xxx112x3x42x3x23x15x0 x0,x0例，例，某铁器加工厂要制作某铁器加工厂要制作100100套钢架，每套要用长为套钢架，每套要用长为2.92.9米，米，2.12.1米米和和1.51.5米的圆钢各一根。已知原料长为米的圆钢各一根。

22、已知原料长为7.47.4米，问应如何下料，可使材米，问应如何下料，可使材料最省？料最省？分析：在长度确定的原料上截取三种不同规格的圆钢，可以归纳分析：在长度确定的原料上截取三种不同规格的圆钢，可以归纳出出8 8种不同的下料方案：种不同的下料方案：圆钢（米）圆钢（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 30 01 15 53 31 12 20 03 31 10 04 4料头（米）料头（米）0 00.10.10.20.20.30.30.80.80.90.91.1.1.41.4 问题归纳为如何混合使用这问题归纳为如何混合使用

23、这8 8种不同的下料方案，来制造种不同的下料方案，来制造100100套钢架，且要使剩余的料头总长为最短。套钢架，且要使剩余的料头总长为最短。 设设x xj j表示用第表示用第j j种下料方案下料的原料根数，种下料方案下料的原料根数，j=1,2j=1,28,8,目标：使料头总长度目标：使料头总长度Z=0.1xZ=0.1x2 2+0.2x+0.2x3 3+0.3x+0.3x4 4+0.8x+0.8x5 5+0.9x+0.9x6 6+1.1x+1.1x7 7+1.4x+1.4x8 8极小化极小化约束：三种规格圆钢根数约束：三种规格圆钢根数 x x1 1+2x+2x2 2+ x+ x4 4+ x+ x

24、6 6 =100 =100 2x2x3 3+2x+2x4 4+x+x5 5+ x+ x6 6+3x+3x7 7=100=100 3x 3x1 1+x+x2 2+2x+2x3 3+3x+3x5 5+x+x6 6+4x+4x8 8=100=100非负取整条件非负取整条件 x xj j0 (j=1,20 (j=1,28)8)且取整数且取整数圆钢（米）圆钢（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 30 01 15 53 31 12 20 03 31 10 04 4料头（米）料头（米）0 00.10.10.20.20.30.30

25、.80.80.90.91.1.1.41.4 数学模型数学模型 s.t.s.t. 这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，这是一个下料问题，是在生产任务确定的条件下，合理的组织生产， 使所消耗的资源数最少的数学规划问题。使所消耗的资源数最少的数学规划问题。 满足一组约束条件的同时，寻求变量满足一组约束条件的同时，寻求变量x x1 1至至x x8 8的值的值, ,使目标函数取得最使目标函数取得最 小值。小值。 2345678124634567 123568jminZ=0.1x +0.2x +0.3x +0.8x +0.9x +1.1x +1.4xx2x x x 100 2x2x

26、x x3x 1003xx2x 3x x 4x 100 x0 j1,2，8 ,圆钢（米）圆钢（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 30 01 15 53 31 12 20 03 31 10 04 4料头（米）料头（米）0 00.10.10.20.20.30.30.80.80.90.91.11.11.41.4且为整数且为整数n 线性规划的一般数学模型线性规划的一般数学模型 线性规划模型的特征：线性规划模型的特征：（1 1）用一组决策变量）用一组决策变量x x1 1，x x2 2，x xn n表示某一方案，且在一般情况下

27、，表示某一方案，且在一般情况下，变量的取值是非负的。变量的取值是非负的。（2 2）有一个目标函数，这个目标函数可表示为这组变量的线性函数。）有一个目标函数，这个目标函数可表示为这组变量的线性函数。（3 3）存在若干个约束条件，约束条件用决策变量的线性等式或线）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式来表达。性不等式来表达。（4 4）要求目标函数实现极大化（）要求目标函数实现极大化（maxmax）或极小化（）或极小化（minmin）。）。满足上述满足上述4 4个特征的规划问题称为线性规划问题个特征的规划问题称为线性规划问题 线性规划的模型的一般形式线性规划的模型的一般形式:

28、: 目标函数目标函数 满足约束条件满足约束条件 通常称通常称 为决策变量，为决策变量， 为价值系数，为价值系数， 为消耗系数为消耗系数, , 为资源限制系数。为资源限制系数。 1122nnmax(min)Z=c x +c x +c x1111221nn12112222nn2m11m22mnnm12n a xa xa x(,)b a xa xa x(,)b axaxax(,)b x ,x ,x0 12nx ,x ,x12nc ,c ,c1112mna ,a ,a12mb ,b ,b线性规划的图解法线性规划的图解法 适用于求解两个变量的线性规划问题适用于求解两个变量的线性规划问题n 图解法的基本步

29、骤图解法的基本步骤例例4,4,利用例利用例1 1说明图解法的主要步骤，说明图解法的主要步骤， 例例1 1的数学模型为的数学模型为 s.t. 121212112maxZ5x2x30 x2 0 x160 5xx15 x4x0, x0O51015x1x1=4x25101AB( 2, 5)CZ5x1+x2=1530 x1+20 x2=1605x1+2x2=5121212112maxZ5x2x30 x2 0 x160 5xx15 x4x0, x012ZZZ=5 2xx，（ ，） 线性规划图解法的基本步骤：线性规划图解法的基本步骤：（1 1）建立以）建立以x x1 1,x,x2 2为坐标轴的直角坐标系，画

30、出线性规划为坐标轴的直角坐标系，画出线性规划 问题的可行域问题的可行域, ,（2 2）求目标函数）求目标函数 Z=CZ=C1 1x x1 1+C+C2 2x x2 2 的梯度的梯度Z =Z =（c c1 1,c,c2 2）, ,（3 3）任取等值线）任取等值线 C C1 1x x1 1+C+C2 2x x2 2=Z=Z0 0, , 沿梯度沿梯度Z Z正方向平移正方向平移, , （若是极小化问题，则沿负梯度方向（若是极小化问题，则沿负梯度方向- -Z Z平移），平移）， 求等直线将离未离可行域时与可行域的交点。求等直线将离未离可行域时与可行域的交点。（4 4）若交点存在，则该点坐标就是最优解）若

31、交点存在，则该点坐标就是最优解 。*Xn 图解法的几种可能结果图解法的几种可能结果 (1(1）有唯一最优解，如例）有唯一最优解，如例1 1。（2 2）有无穷多最优解）有无穷多最优解 如例如例1 1中的目标函数设为中的目标函数设为 maxZ=10 xmaxZ=10 x1 1+2x+2x2 2 则目标函数等值线则目标函数等值线10 x10 x1 1+2x+2x2 2=Z =Z 与第二约束与第二约束 5x5x1 1+x+x2 21515 的边界线平行。将等值线沿梯度的边界线平行。将等值线沿梯度Z =Z =（1010，2 2）正方向平移）正方向平移 至至B B点时与可行域点时与可行域OABCOABC的

32、整条边界线的整条边界线ABAB重合。重合。 这表明线段这表明线段ABAB上的每一点都使目标函数取得同样的最大值，上的每一点都使目标函数取得同样的最大值， 因而都是最优解。因而都是最优解。O51015x1x1=4x25101AB（2，5）CZ5x1+x2=1530 x1+20 x2=16010 x1+2x2=5212xx10maxZ12ZZZ=2xx，（10，）例例5 5，试用图解法求解下列线性规划问题试用图解法求解下列线性规划问题 st.（3 3） 无界解（或称无最优解）无界解（或称无最优解） 无界解是指线性规划问题的最优解无界。无界解是指线性规划问题的最优解无界。若是极大化问题，则可使目标函

33、数值若是极大化问题，则可使目标函数值Z+,Z+, 极小化问题极小化问题 则可使目标函数值则可使目标函数值Z-Z-， 有无界解的线性规划问题的可行域通常是无界区域，但反之有无界解的线性规划问题的可行域通常是无界区域，但反之则不必然。则不必然。12121212minZ3x2x-2xx2 x -3x3 x0,x0 -1 O24x1x224-Z=(3,2)-2x1+x2=2x1-3x2=3-1 O3312121212minZ3x2x-2xx2 x -3x3 x0,x012ZZZ=2xx，（-3,- ）（4 4）无可行解）无可行解 某些线性规划问题的可行域是空集，既不存在满足所有约束条某些线性规划问题的

34、可行域是空集，既不存在满足所有约束条件的点，这时问题无可行解，当然更谈不上最优解了。件的点，这时问题无可行解，当然更谈不上最优解了。 在实际中出现这种情况可以认为资源条件无法满足人们的要求，在实际中出现这种情况可以认为资源条件无法满足人们的要求，既不存在可行方案。既不存在可行方案。 标准线性规划模型标准线性规划模型 线性规划问题的标准形式：线性规划问题的标准形式： s.t s.t 其中其中(1.1)(1.1)为目标函数，为目标函数，(1.2)(1.2)为约束条件，为约束条件，(1.3)(1.3)为非负条件，为非负条件， 为称呼方便，有时将为称呼方便，有时将(1.3)(1.3)也称为约束条件。也

35、称为约束条件。（1.21.2） （1.31.3）线性规划的标准形式线性规划的标准形式（1.11.1）1122nn1111221nn12112222nn2 m11m22mnnm 12nmaxZ=c x +c x +c xa x +a x +a x =ba x +a x +a x =bax +ax +ax =b x ,x ,x0（一）、整数规划问题实例（一）、整数规划问题实例 例一、合理下料问题例一、合理下料问题设用某型号的圆钢下零件设用某型号的圆钢下零件A1, A2,Am 的毛坯。在一根圆钢的毛坯。在一根圆钢上下料的方式有上下料的方式有B1,B2, Bn 种，每种下料方式可以得到各种，每种下料方

36、式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？样安排下料方式，使得即满足需要，所用的原材料又最少？零件 方 个数 式零件零 件毛坯数nBB 1mAA 1mbb 1mnmnaaaa 1111二、整数规划的模型二、整数规划的模型 设：设：xj 表示用表示用Bj (j=1.2n) 种方式下料根数种方式下料根数 模型：模型：且且为为整整数数n)1.2(j 0)2 . 1( min11jnjijijnjjxmibxaxZ例二、例二、某公司计划在某公司计划在m个地点建厂，可供选择的地点个地

37、点建厂，可供选择的地点有有A1,A2Am ，他们的生产能力分别是他们的生产能力分别是a1,a2,am（假设（假设生产同一产品）。第生产同一产品）。第i i个工厂的建设费用为个工厂的建设费用为fi (i=1.2m),又有又有n个地点个地点B1,B2, Bn 需要销售这种产品，需要销售这种产品，其销量分别为其销量分别为b1.b2bn 。从工厂运往销地的单位运费。从工厂运往销地的单位运费为为Cij。试决定应在哪些地方建厂，即满足各地需要，。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？又使总建设费用和总运输费用最省？单 销地厂址 价生产能力建设费用销量nmmmnmmmnnb

38、bbfacccAfacccAfacccABnBB 2121222222121111211121 设：设： xij 表示从工厂运往销地的运量表示从工厂运往销地的运量( (i=1.2m、j=1.2n), 1 ), 1 在在Ai建厂建厂 又设又设 Yi （i=1.2m） 0 0 不在不在Ai建厂建厂 模型：模型：n)1.2jm1.2(i 1 0, 0n)1.2(j )2 . 1( min111、或或iijmijijnjiiijmiiiijijyxbxmiyaxyfxcZ（二）、整数规划的数学模型（二）、整数规划的数学模型一般形式一般形式且且部部分分或或全全部部为为整整数数或或 n)1.2(j 0)2

39、 . 1( )min(max11jnjijijnjjjxmibxaxcZZ 依照决策变量取整要求的不同，整数规划可分为纯整依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、数规划、全整数规划、混合整数规划、0 01 1整数规划。整数规划。 纯整数规划：纯整数规划：所有决策变量要求取非负整所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要数（这时引进的松弛变量和剩余变量可以不要求取整数）。求取整数）。 全整数规划：全整数规划：除了所有决策变量要求取非负除了所有决策变量要求取非负整数外，系数整数外，系数aij和常数和常数bi也要求取整数（这时引也要求取整数（这