供应链系统优化方法

1、LP的数学模型的数学模型图解法图解法 LP模型的应用模型的应用Page 31. 规划问题规划问题生产和经营管理中经常提出如何合理安排，使人力、生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。这就是规划问题。（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源最少的资源 （如资金、设备、原标材料、人工、时间等）（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标去完成确定的任务或目标. .（2 2）在一定的资源条件限制下，如

2、何组织安排生产获得最）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多好的经济效益（如产品量最多 、利润最大）、利润最大）. .Page 4例例1.1 某企业计划生产甲、乙两种产品。这些产品分某企业计划生产甲、乙两种产品。这些产品分别要在别要在A、B、C、D、四种不同的设备上加工。按工、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？企业总的利润最大？ 设设 备备产产 品品 A B C D利润

3、（元）利润（元） 甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12Page 5解：设解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：分别为甲、乙两种产品的产量，则数学模型为：Page 6Page 700 )( )( (min) max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z(min)max 11nxmbxaxcjnjijijnjjj简写为：简写为：Page 8一般而言，一个经济、管理问题凡是满足以一般而言，一个经济、管理问题凡是满足以下条件

4、时，才能建立线性规划模型。下条件时，才能建立线性规划模型。 要求解问题的目标函数能用数值指标来反映，且要求解问题的目标函数能用数值指标来反映，且为线性函数为线性函数 存在着多种方案存在着多种方案 要求达到的目标是在一定条件下实现的，这些约要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述束可用线性等式或不等式描述Page 9 人力资源分配问题人力资源分配问题例例1.2 某昼夜服务的公交线路每天各时间段内所某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：需司机和乘务人员人数如下表所示：班次班次时间时间所需人员所需人员16:0010:0060210:0014:

5、0070314:0018:0060418:0022:0050522:002:002062:006:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少足工作需要，又使配备司机和乘务人员的人数减少?Page 10解：设解：设xi表示第表示第i班次时开始上班的司机和乘务人员人数。班次时开始上班的司机和乘务人员人数。 0,302050607060.min6543216554433221616543

6、21xxxxxxxxxxxxxxxxxxtsxxxxxx此问题最优解：此问题最优解：x150， x220， x350， x40， x520， x610，一共需要司机和乘务员，一共需要司机和乘务员150人。人。Page 11生产计划问题生产计划问题例例1.3 某厂生产某厂生产、三种产品，都分别经三种产品，都分别经A、B两道工序加工。设两道工序加工。设A工序可分别在设备工序可分别在设备A1和和A2上完成，有上完成，有B1、B2、B3三种设备可用于完成三种设备可用于完成B工序。工序。已知产品已知产品可在可在A、B任何一种设备上加工；产品任何一种设备上加工；产品可在任何规格的可在任何规格的A设备上加工

7、，但完成设备上加工，但完成B工序时，只工序时，只能在能在B1设备上加工；产品设备上加工；产品只能在只能在A2与与B2设备上加设备上加工。加工单位产品所需工序时间及其他各项数据如工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。下表，试安排最优生产计划，使该厂获利最大。Page 12设备设备产品产品设备有效设备有效台时台时设备加工费设备加工费（元（元/小时）小时）27910 000321B168124000250B247000783B37114000200原料费（万元原料费（万元/每件）每件）0.250.350.5售价（万元售价（万元

8、/每件）每件）1.252.002.8Page 13解：设解：设xijk表示产品表示产品i在工序在工序j的设备的设备k上加工的数量。约束条上加工的数量。约束条件有：件有：）（上加工的数量相等）上加工的数量相等），在工序在工序（产品（产品上加工的数量相等）上加工的数量相等），在工序在工序（产品（产品上加工的数量相等）上加工的数量相等），在工序在工序（产品（产品设备设备设备设备）（设备（设备）（设备（设备设备设备3 , 2 , 1; 2 , 1; 3 , 2 , 10BAIIIBAIIBAI)3B(40007)2B(70001141B4000862A100001297)1A(600010532231

9、2221212211123122121112111123322122221121312212112211111 kjixxxxxxxxxxxxxxxxxxxxxijkPage 14目标是利润最大化，即利润的计算公式如下：目标是利润最大化，即利润的计算公式如下： 5131)()(ii该该设设备备实实际际使使用用台台时时每每台台时时的的设设备备费费用用该该产产品品件件数数销销售售单单价价原原料料单单价价利利润润带入数据整理得到：带入数据整理得到：12332212222112131221221111211135. 023. 1448. 05 . 0375. 0915. 136. 115. 1775.

10、 075. 0maxxxxxxxxxxx Page 15因此该规划问题的模型为：因此该规划问题的模型为： ）（3,2,1;2,1;3,2,104000770001144000861000012976000105.35.023.1448.05.0375.09775.075.0max322312221212211123122121112111123322122221121312212112211111123322122221121312212211112111kjixxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxijkPage 16Page 17Page

11、18实际问题中的线性规划模型实际问题中的线性规划模型大型煤炭企业生产和供给问题大型煤炭企业生产和供给问题（Peng Hong-jun, Zhou Mei-hua. A Dynamic Optimization Model of an integrated Coal Supply Chain System and Its Application，Mining Science and Technology, 2009，19(6):842-846. (EI检索检索) ) 供应链供应链是一种新的企业组织形态和运营方式是一种新的企业组织形态和运营方式, ,包括从客户包括从客户需求开始经过原材料供应、生产

12、批发零售等环节需求开始经过原材料供应、生产批发零售等环节, ,到最后把产到最后把产品送到最终用户的各项制造和商业活动。机电等供应物流运输品送到最终用户的各项制造和商业活动。机电等供应物流运输客户市场原煤开配采洗选加工、配煤煤炭销售大型煤炭企业内客户市场原煤开配采洗选加工、配煤煤炭销售大型煤炭企业内部供应链物流部供应链物流/ /供应信息流资金流供应信息流资金流/ /需求信息流图需求信息流图1 1大型煤炭企大型煤炭企业供应链框架业供应链框架Page 19煤炭供应链中物流从上游向下游流动煤炭供应链中物流从上游向下游流动, 资金流从下游向资金流从下游向上游流动上游流动, 而信息流的流动则是双向的。以上

13、游供应企业作而信息流的流动则是双向的。以上游供应企业作为大型煤炭企业原料供应商为大型煤炭企业原料供应商, 以煤炭企业作为原煤及精煤生以煤炭企业作为原煤及精煤生产商产商, 再通过运输环节到达用户再通过运输环节到达用户, 形成以物流为主线形成以物流为主线, 包括信包括信息流及资金流的输入输出关系的煤炭供应链框架息流及资金流的输入输出关系的煤炭供应链框架, 如图如图1所所示。图中包含原煤开配采、煤炭洗选加工、煤炭销售等节示。图中包含原煤开配采、煤炭洗选加工、煤炭销售等节点并用实线框起来，为大型煤炭企业供给系统内部供应链。点并用实线框起来，为大型煤炭企业供给系统内部供应链。大型煤炭企业的原煤开采、煤炭

14、洗选加工和客户均为多点。大型煤炭企业的原煤开采、煤炭洗选加工和客户均为多点。Page 20供应商供应商物流运输物流运输客户市场客户市场原煤开配采原煤开配采洗选加工洗选加工煤炭销售煤炭销售复杂煤炭企业内部供应链复杂煤炭企业内部供应链物流物流/供应信息流供应信息流资金流资金流/需求信息流需求信息流图图1 复杂煤炭企业多层供应链框架复杂煤炭企业多层供应链框架外购煤外购煤Page 21 徐州矿务集团共徐州矿务集团共11个矿井，其中个矿井，其中9个矿井建有洗煤厂，各个矿井建有洗煤厂，各矿井生产情况如表矿井生产情况如表1, 该企业有该企业有5个主要客户，各客户需求情个主要客户，各客户需求情况见表况见表2。

15、 煤炭企业除了追求整理利润外，还应该考虑客户满意度因煤炭企业除了追求整理利润外，还应该考虑客户满意度因素，特别是要尽量提高一些长期重要客户的满意度，以保素，特别是要尽量提高一些长期重要客户的满意度，以保证企业的可持续发展。影响煤炭企业客户满意度的因素主证企业的可持续发展。影响煤炭企业客户满意度的因素主要有商品煤数量订单满足率、企业供给客户的商品煤质量要有商品煤数量订单满足率、企业供给客户的商品煤质量等。请建立同时考虑利润和客户满意度的煤炭企业生产和等。请建立同时考虑利润和客户满意度的煤炭企业生产和供给的一般模型，并用模型对所给煤炭企业进行生产和供供给的一般模型，并用模型对所给煤炭企业进行生产和

16、供给决策。给决策。Page 22表 徐州矿务集团各矿井生产情况表矿井名称矿井名称原煤能力原煤能力（吨）（吨）原煤成本原煤成本（元（元/ /吨）吨）洗煤能力洗煤能力（吨）（吨）洗煤成本洗煤成本（元（元/ /吨）吨）洗煤产品洗煤产品宅城宅城85000850003043040 0-夹河夹河11000011000034534596000960002525冶炼精煤、混煤冶炼精煤、混煤庞庄庞庄2250002250003103101100001100002222冶炼精煤、混煤冶炼精煤、混煤韩桥韩桥65000650003083080 0-三河尖三河尖560005600029829830000300003838

17、冶炼精煤、混煤冶炼精煤、混煤卧牛山卧牛山180001800031631616000160003030其他类炼焦精煤、混煤其他类炼焦精煤、混煤张双楼张双楼11800011800030730718000180002323其他类炼焦精煤、混煤其他类炼焦精煤、混煤权台权台16600016600028928950000500001717其他类炼焦精煤、混煤其他类炼焦精煤、混煤旗山旗山14800014800029329390000900001818其他类炼焦精煤、混煤其他类炼焦精煤、混煤义安义安330003300036936930000300002828其他类炼焦精煤、混煤其他类炼焦精煤、混煤张集张集87

18、0008700039339335000350003232其他类炼焦精煤、混煤其他类炼焦精煤、混煤合计合计11110001111000-475000475000-其他类炼焦精煤、混煤其他类炼焦精煤、混煤Page 23 表 徐州矿务集团客户需求情况序号序号原煤原煤冶炼精煤冶炼精煤其他精煤其他精煤混煤混煤最低订单最低订单满足率满足率需求量需求量价格价格需求量需求量价格价格需求量需求量价格价格需求量需求量价格价格1 12500002500004504500 0-0 0-1000001000005205200.80.82 20 0-80000800006506500 0-8000080000530530

19、0.60.63 30 0-600006000067067080000800007007000 0-0.60.64 41000001000004604600 0-600006000072072060000600005455450.50.55 560000600004704700 0-300003000075075040000400005605600 0合计合计410000410000140000140000170000170000280000280000Page 24令令i为矿井序号为矿井序号,i=1,2,I; j 为选煤厂序号，为选煤厂序号，j=1,2,J; k 为客户为客户序号，序号，k=1

20、,2,K;n为商品煤序号为商品煤序号;n=1,2, ,N，不妨设主要洗，不妨设主要洗选产品（精煤）序号为选产品（精煤）序号为1，原煤序号为，原煤序号为N.iXHiAiXiiAX 复杂煤炭供应链系统矿井节点分析复杂煤炭供应链系统矿井节点分析输入变量：输入变量： (%)(%)为矿井为矿井i i的原煤灰分的原煤灰分, ,( (吨吨) ) 为矿井为矿井i i原煤生产能力。原煤生产能力。决策变量：决策变量：( (吨吨) )为矿井为矿井i i原煤产量原煤产量. .原煤生产能力约束：原煤生产能力约束：Page 25jnHjBjYHjYjnLjjBY ),()1(321NjjjjjLLLYHfL复杂煤炭供应链

21、系统洗煤厂节点分析复杂煤炭供应链系统洗煤厂节点分析输入变量：输入变量： （% %）为洗煤厂）为洗煤厂j j生产的生产的n n种商品煤的灰分；种商品煤的灰分； ( (吨吨) ) 为选煤厂为选煤厂j j洗配能力；洗配能力； (%) (%) 为选煤厂为选煤厂j j入洗原煤灰分。入洗原煤灰分。决策变量：决策变量： （吨）选煤厂（吨）选煤厂j j入洗原煤量；入洗原煤量；（% %）为矿洗煤厂）为矿洗煤厂j j对对n n种商品煤的产率。种商品煤的产率。洗煤厂洗选能力约束：洗煤厂洗选能力约束：煤厂主要洗选产品产率与入洗原煤灰分和其他洗选产品产率有负煤厂主要洗选产品产率与入洗原煤灰分和其他洗选产品产率有负相关关

22、系，可以通过洗煤厂历史洗煤数据，用多元线性回归法建立各相关关系，可以通过洗煤厂历史洗煤数据，用多元线性回归法建立各洗煤厂主要洗选产品产出率模型，则：洗煤厂主要洗选产品产出率模型，则：Page 26复杂煤炭供应链系统客户端需求分析复杂煤炭供应链系统客户端需求分析用户对煤炭的需求，不仅是煤炭品种和数量的要求，而用户对煤炭的需求，不仅是煤炭品种和数量的要求，而且还有煤炭产品质量的要求，随着煤炭行业市场竞争态势的变且还有煤炭产品质量的要求，随着煤炭行业市场竞争态势的变化和客户导向意识的增强，煤炭企业需要关注和满足煤炭用户化和客户导向意识的增强，煤炭企业需要关注和满足煤炭用户多方面的需求。多方面的需求。

23、knEknPknDknF输入变量：输入变量： ( (吨吨) ) 为客户为客户k k对对n n种商品煤需求量；种商品煤需求量； ( (元元/ /吨吨) ) 为客户为客户k k购买购买n n种商品煤协议价格；种商品煤协议价格； (%) (%) 为煤炭企业确定的对客户为煤炭企业确定的对客户k k的的n n种商品煤最低的订种商品煤最低的订单满足率；单满足率； （% %）为煤炭企业向客户）为煤炭企业向客户k k销售的销售的n n种商品煤灰分标准种商品煤灰分标准. . Page 27nH0ijXikNZjknZnWknW0kWknQ复杂煤炭供应链系统物流分析复杂煤炭供应链系统物流分析输入变量：输入变量：

24、（%)%)表示外购的表示外购的l l种商品煤的灰分种商品煤的灰分, ,( (吨吨) )为煤矿企业供应链系统对外运输能力为煤矿企业供应链系统对外运输能力. . ( (吨吨) ) 为矿井为矿井i i运往选煤厂运往选煤厂 j j的待洗原煤量的待洗原煤量, , ( (吨吨) ) 为矿井为矿井i i运往客户运往客户k k的原煤量的原煤量, , （吨）为洗煤厂（吨）为洗煤厂j j运往客户运往客户k k的的n n商品煤数量，商品煤数量，n=1,2,N-1n=1,2,N-1, , ( (吨吨) )为外购为外购n n种商品煤数量种商品煤数量, , ( (吨吨) ) 为外购为外购n n种商品煤运往客户种商品煤运往

25、客户k k的数量的数量, , 为运往客户为运往客户k k的外购煤数量的外购煤数量, , ( (吨吨) )企业销售给客户企业销售给客户k k 的的n n种商品煤数量种商品煤数量. .决策变量：决策变量：Page 28矿井原煤生产量公式：矿井原煤生产量公式：kikNjijiZXX 洗煤厂原煤入洗量公式：洗煤厂原煤入洗量公式：iijjXY 煤炭销售公式：煤炭销售公式：1, 2 , 1,NnWZQknjjknkn kNiikNkNWZQkknnWWnknkWW0外购煤公式：外购煤公式：, 运输能力约束：运输能力约束：ikikNjkNnjknZZ11 Page 29客户需求数量约束：客户需求数量约束：1

26、, 2 , 1,NnEWZEDknknjjknknkn kNkNiikNkNkNEWZED客户需求质量约束（灰分）：客户需求质量约束（灰分）：1, 2 , 1,0NnFQHWHZknknnknjjnjkn kNkNNkNiiikNFQHWXHZ0Page 30ijSikVjkRnP0kT0iC1 jC 复杂煤炭供应链资金流分析复杂煤炭供应链资金流分析 ( (元元/ /吨吨) ) 矿井矿井i i到选煤厂到选煤厂j j单位重量运输成本单位重量运输成本, , ( (元元/ /吨吨) )矿井矿井i i到客户到客户k k单位重量运输成本单位重量运输成本, , ( (元元/ /吨吨) ) 选煤厂选煤厂j

27、j到客户到客户k k单位重量运输成本单位重量运输成本, , ( (元元/ /吨吨) ) 为外购为外购n n种商品煤报价种商品煤报价, , ( (元元/ /吨吨) )外购煤到客户外购煤到客户k k的单位重量运输成本的单位重量运输成本, , ( (元元/ /吨吨) ) 为矿井为矿井i i生产单位原煤成本生产单位原煤成本, , ( (元元/ /吨吨) ) 为选煤厂为选煤厂j j选洗单位原煤成本选洗单位原煤成本. .输入变量：输入变量：Page 31生产成本：生产成本： jjjiiiCYCX10 运输成本：运输成本：knkknijijijikikikNjknjkjknTWSXVZRZ 外购煤成本：外购

28、煤成本：nnnPW0 煤炭销售收入：煤炭销售收入：knknknPQ 煤炭企业供应链系统资金流净值煤炭企业供应链系统资金流净值利润利润: :nnnknkknijijijikikikNjknjkjknjjjiiiknknknPWTWSXVZRZCYCXPQU010)(Page 32客户端是煤炭供应链系统信息流的来源，是煤炭企业客户端是煤炭供应链系统信息流的来源，是煤炭企业供应链系统的决策的依据。煤炭企业决策目标除了系统经济供应链系统的决策的依据。煤炭企业决策目标除了系统经济利润最大化外利润最大化外,还要考虑客户满意度目标还要考虑客户满意度目标,利于企业可持续发利于企业可持续发展展.论文通过确定不同

29、客户相应的最低订单满足率和最低质量论文通过确定不同客户相应的最低订单满足率和最低质量保证的方法保证的方法, 建立煤炭供应链系统建立煤炭供应链系统线性规划决策模型线性规划决策模型：Page 33nnnknkknijijijikikikNjknjkjknjjjiiiknknknPWTWSXVZRZCYCXPQU010)(max kNkNNkNiiikNknknnknjjnjknikikNjkNnjknkNkNiikNkNkNknknjjknknknknknkknnkNiikNkNknjjknknkiijjikNjijiNjjjjjjjiFQHWXHZNnFQHWHZZZEWZEDNnEWZEDWW

30、WWWZQNnWZQXYZXXLLLYHfLBYAX00110)1(3211,2, 1,1,2, 1,1,2, 1,),(,Page 34根据该企业供应链原煤生产根据该企业供应链原煤生产,洗选加工洗选加工,运输情况以及客户需运输情况以及客户需求等信息求等信息,建立该企业的供应链系统的动态优化模型建立该企业的供应链系统的动态优化模型,其中决其中决策变量策变量300余个余个.LINGO软件是用来求解线性和非线性优化问题的简易工具软件是用来求解线性和非线性优化问题的简易工具.用用LINGO软件求解该模型软件求解该模型,得出企业原煤生产、洗煤加工、得出企业原煤生产、洗煤加工、运输和销售等系列决策，表中

31、列出了该矿务集团内部供应链运输和销售等系列决策，表中列出了该矿务集团内部供应链原煤生产和洗选生产等优化决策方案：原煤生产和洗选生产等优化决策方案：Page 35表 徐州矿务集团内部供应链系统优化决策矿井名称矿井名称原煤产量原煤产量入洗原煤量入洗原煤量商品原煤量商品原煤量冶炼精煤量冶炼精煤量其他精煤量其他精煤量混煤产量混煤产量宅城宅城8500085000-8500085000-夹河夹河960009600096000960000 05781457814-21392139庞庄庞庄2250002250001100001100001150001150000 0-8575085750韩桥韩桥1700017

32、000-1700017000-0 0三河尖三河尖4700047000300003000047000470002618626186-0 0卧牛山卧牛山180001800016000160001800018000-12523125230 0张双楼张双楼180001800018000180000 00权台权台1660001660005000050000116000116000-41243412430 0旗山旗山14800014800090000900005800058000-58770587700 0义安义安300003000030000300000 0-0 0282412

33、8241张集张集350003500035000350000 0-26260262600 0合计合计8850008850004750004750004100004100008400084000153994153994116130116130Page 36表 徐州矿务集团销售优化决策客户序号客户序号原煤销售量原煤销售量冶炼精煤销售量冶炼精煤销售量其他精煤销售量其他精煤销售量洗混煤销售量洗混煤销售量1 1250000250000-80000800002 2-4800048000-48000480003 3-36000360006399463994-4 4100000100000-6000060000

34、30000300005 56000060000-30000300000 0合计合计4100004100008400084000153994153994158000158000运输规划问题的数学模型运输规划问题的数学模型运输问题的应用运输问题的应用 Page 38例例2.1 某公司从两个产地某公司从两个产地A1、A2将物品运往三个销地将物品运往三个销地B1, B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最物品的运费如下表所示，问：应如何调运可使总运输费用最小？小？B1B2B3产量

35、产量A1646200A2655300销量销量150150200Page 39解：产销平衡问题：总产量解：产销平衡问题：总产量 = 总销量总销量500 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列运输量的运输量，得到下列运输量表：表：B1B2B3产量产量A1x11x12x13200A2x21x22x23300销量销量150150200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 1

36、50 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）Page 40运输问题的一般形式：产销平衡运输问题的一般形式：产销平衡A1、 A2、 Am 表示某物资的表示某物资的m个产地；个产地； B1、B2、Bn 表示表示某物质的某物质的n个销地；个销地；ai 表示产地表示产地Ai的产量；的产量； bj 表示销地表示销地Bj 的销量；的销量； cij 表示把物资从产地表示把物资从产地Ai运往销地运往销地Bj的单位运价。设的单位运价。设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列一般运输量问题的模型：的运输量，得到下列一般运输量问题的模型：

37、minjijijxcz11min njmixnjbxmiaxtsijjmiijnjiij, 1;, 1, 0, 1, 1.11Page 41变化：变化： 1）有时目标函数求最大。如求利润最大或营业额最大等；）有时目标函数求最大。如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，在模型中直接加入）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束约束条件（等式或不等式约束)； 3）产销不平衡时，可加入假想的产地（销大于产时）或销）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。地（产大于销时）。定理定理: 设有设有m个产地个产地n个销地且

38、产销平衡的运输问题，则基变个销地且产销平衡的运输问题，则基变量数为量数为m+n-1。Page 42目标函数求利润最大或营业额最大等问题。目标函数求利润最大或营业额最大等问题。 minjijijxCZ11max njmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 10, 2 , 1, 2 , 111，Page 43例例2.2 下列矩阵下列矩阵C是是Ai（I=1，2，3）到）到Bj的吨公里利润的吨公里利润,运输运输部门如何安排运输方案使总利润最大部门如何安排运输方案使总利润最大. 销地销地产地产地B1B2B3产量产量A1A2A3销量销量Page 44当总产量与总销量不相等

39、时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这这类运输问题在实际中常常碰到。类运输问题在实际中常常碰到。 当产大于销时，即：当产大于销时，即： minjjiba11数学模型为：数学模型为： minjijijxcZ11min njmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 10, 2 , 1, 2 , 111，Page 45由于总产量大于总销量，必有部分产地的产量不能全部运送完，由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟

40、销地销地Bn+1， bn+1作为一个虚设销地作为一个虚设销地Bn+1的销量的销量(即库存量即库存量)。各产地。各产地Ai到到Bn+1的运价为零，即的运价为零，即Ci,n+1=0,（i=1，m）。则平衡问题的）。则平衡问题的数学模型为：数学模型为： minjijijxcZ11min , 2 , 1, 2 , 1, 01, 2 , 1, 2 , 1111jmixnjbxmiaxijmijijnjiij；具体求解时具体求解时, ,只在只在运价表右端增加运价表右端增加一列一列B Bn n+1+1，运价，运价为零为零, ,销量为销量为b bn n+1+1即可即可Page 46 当销大于产时，即：当销大于

41、产时，即： minjjiba11 minjijijxCZ11min , 2 , 1;, 2 , 1, 0, 2 , 1, 2 , 111jmixnjbxmiaxijmijijnjiij数学模型为：数学模型为：由于总销量大于总产由于总销量大于总产量量,故一定有些需求地故一定有些需求地不完全满足不完全满足,这时虚设这时虚设一个产地一个产地Am+1，产量，产量为：为： miinjjab11Page 47销大于产化为平衡问题的数学模型为销大于产化为平衡问题的数学模型为 ： minjijijxcZ11min njmixnjbxmiaxijmijijnjiji, 2 , 11, 2 , 1, 0, 2 ,

42、 11, 2 , 1111；具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。产，运价为零。产量为量为am+1即可。即可。 Page 48例例2.3 求下列表中极小化运输问题的最优解。求下列表中极小化运输问题的最优解。 B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20603545180160 4141160180ijjiba因为有：因为有：Page 49所以是一个产大于销的运输问题。表中所以是一个产大于销的运输问题。表中A2不可达不可达B1，用一个，用一个很大的正数很大的正数M表示运价表示运价C21。虚设一个

43、销量为。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列，表的右边增添一列 ，得到新的运价表。，得到新的运价表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180Page 50下表为计算结果。可看出：产地下表为计算结果。可看出：产地A4还有还有20个单位没有运出。个单位没有运出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180Page 513. 生产与储存问题生产与储存问题例例2.4 某厂按合同规定须于当

44、年每个季度末分别提供某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用每积压一个季度需储存、维护等费用0.15万元。试求在完成合同万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。的情况下，使该厂全年生产总费用为最小的决策方案。季度季度生产能力生产能力/台台单位成本单位成本/万元万元2510.83511.130111

45、011.3Page 52解：解： 设设 xij为第为第 i 季度生产的第季度生产的第 j 季度交货的柴油机数目，那季度交货的柴油机数目，那么应满足：么应满足：交货：交货： x11 = 10 生产：生产：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10目标：目标：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x

46、23+11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 把第把第 i 季度生产的柴油机数目看作第季度生产的柴油机数目看作第 i 个生产厂的产量；把第个生产厂的产量；把第 j 季度季度交货的柴油机数目看作第交货的柴油机数目看作第 j 个销售点的销量。构造下列产销平衡问题：个销售点的销量。构造下列产销平衡问题：Page 53 ji产量产量10.810.9511.111.2525M11.1011.2511.4035MM11.0011.1530MMM11.3010销量销量10152520 10070由于产大于销，加上一个虚拟的销地由于产大于销，加上一个虚拟的销地D，化为平

47、衡问题，化为平衡问题，即可应用表上作业法求解。即可应用表上作业法求解。Page 54该问题的运输平衡表：该问题的运输平衡表： jiD产量产量10.810.9511.111.25025M11.1011.2511.40035MM11.0011.15030MMM11.30010销量销量1015252030 100100Page 55 jiD产量产量1015025053035255301010销量销量1015252030 100100最优生产决策如下表，最小费用最优生产决策如下表，最小费用z773万元。万元。Page 56下面给出一些例题，可作为建模的练习：下面给出一些例题，可作为建模的练习：例例2.

48、5 石家庄北方研究院有一、二、三，三个区。每年分别需石家庄北方研究院有一、二、三，三个区。每年分别需要用煤要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价如下表。由于需大于供，经院研究决定一区供应量吨，运价如下表。由于需大于供，经院研究决定一区供应量可减少可减少0-400吨，二区必须满足需求量，三区供应量不少于吨，二区必须满足需求量，三区供应量不少于1700吨，试求总费用为最低的调运方案。吨，试求总费用为最低的调运方案。一区二区三区产量山西

49、盂县1.651.701.754000河北临城1.601.651.701500需要量300010002000Page 57解：解： 根据题意，作出产销平衡与运价表，根据题意，作出产销平衡与运价表， 取取 M 代表一个很代表一个很大的正数，其作用是强迫相应的大的正数，其作用是强迫相应的 x31、 x33、 x34取值为取值为0。Page 58Page 59整数规划的特点及应用整数规划的特点及应用Page 61要求一部分或全部决策变量取整数值的规划问题称为要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件整数规划。不考虑整数条件，由余下的目标函数和约束

50、条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。问题是一个线性规划，则称该整数规划为整数线性规划。整数线性规划数学模型的一般形式：整数线性规划数学模型的一般形式： 且且部部分分或或全全部部为为整整数数或或 n)1.2(j 0)2 . 1( )min(max11jnjijijnjjjxmibxaxcZZPage 62 纯整数线性规划：指全部决策变量都必须取整数值的整数纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。线性规划。 混合整数线性规划：决策变量中有一部分必须取整数值，

51、混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。另一部分可以不取整数值的整数线性规划。 0-1型整数线性规划：决策变量只能取值型整数线性规划：决策变量只能取值0或或1的整数线性规的整数线性规划。划。Page 63如如1. 变量是人数、机器设备台数或产品件数等都要求是整数变量是人数、机器设备台数或产品件数等都要求是整数2. 对某一个项目要不要投资的决策问题，可选用一个逻辑变对某一个项目要不要投资的决策问题，可选用一个逻辑变量量 x，当，当x=1表示投资，表示投资，x=0表示不投资；表示不投资；3. 人员的合理安排问题，当变量人员的合理安排问题，当变量xij

52、=1表示安排第表示安排第i人去做人去做j工作，工作，xij=0表示不安排第表示不安排第i人去做人去做j工作。逻辑变量也是只允许取整数工作。逻辑变量也是只允许取整数值的一类变量。值的一类变量。Page 64例例3.1 工厂工厂A1和和A2生产某种物资。由于该种物资供不应求，故需要生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有再建一家工厂。相应的建厂方案有A3和和A4两个。这种物资的需求地两个。这种物资的需求地有有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费需求地的单位物资运费cij

53、，见下表：，见下表：B1B2B3B4年生产能力年生产能力A12934400A28357600A37612200A44525200年需求量年需求量350400300150工厂工厂A3或或A4开工后，每年的生产费用估计分别为开工后，每年的生产费用估计分别为1200万或万或1500万万元。现要决定应该建设工厂元。现要决定应该建设工厂A3还是还是A4，才能使今后每年的总费用，才能使今后每年的总费用最少。最少。Page 65解：这是一个物资运输问题，特点是事先不能确定应该建解：这是一个物资运输问题，特点是事先不能确定应该建A3还是还是A4中哪一个，因而不知道新厂投产后的实际生产物资。中哪一个，因而不知道

54、新厂投产后的实际生产物资。为此，引入为此，引入0-1变量：变量：)2 , 1(01 iyi若不建工厂若不建工厂若建工厂若建工厂再设再设xij为由为由Ai运往运往Bj的物资数量，单位为千吨；的物资数量，单位为千吨；z表示总费用，表示总费用，单位万元。单位万元。则该规划问题的数学模型可以表示为：则该规划问题的数学模型可以表示为：Page 66 )2 , 1(1 , 0)4 , 3 , 2 , 1,(0200200600400150300400350.15001200min2444342411343332312423222114131211443424144333231342322212413121

55、11414121iyjixyxxxxyxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsyyxcziijijijij混合整数规划问题混合整数规划问题Page 67例例3.2 现有资金总额为现有资金总额为B。可供选择的投资项目有。可供选择的投资项目有n个，项目个，项目j所需投资额和预期收益分别为所需投资额和预期收益分别为aj和和cj（j1,2,.,n），此外由），此外由于种种原因，有三个附加条件：于种种原因，有三个附加条件：n若选择项目若选择项目1，就必须同时选择项目，就必须同时选择项目2。反之不一定。反之不一定n项目项目3和和4中至少选择一个；中至少选择一个；n项目项目5,6,7中恰

56、好选择中恰好选择2个。个。应该怎样选择投资项目，才能使总预期收益最大。应该怎样选择投资项目，才能使总预期收益最大。Page 68解：对每个投资项目都有被选择和不被选择两种可能，因此解：对每个投资项目都有被选择和不被选择两种可能，因此分别用分别用0和和1表示，令表示，令xj表示第表示第j个项目的决策选择，记为：个项目的决策选择，记为：),.,2 , 1(01njjjxj 不投资不投资对项目对项目投资投资对项目对项目投资问题可以表示为：投资问题可以表示为： ）（或或者者nxxxxxxxxBxatsxczjnjjjnjjj, 2 , 1j1021.max765431211Page 69例例3.3 3

57、.3 指派问题或分配问题。人事部门欲安排四人到四个不指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。绩（百分制）如表所示，如何安排他们的工作使总成绩最好。 工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088Page 70设设 工工作作时时人人做做不不分分配配第第工工作作时时人人做做分分配配第第jijixij01数学模型如下：数学模型如下：4443424134333231242322211

58、413121188809086907983829578879590739285maxxxxxxxxxxxxxxxxxZ 要求每人做一项工作，约束条件为：要求每人做一项工作，约束条件为： 111144434241343332312423222114131211xxxxxxxxxxxxxxxxPage 71每项工作只能安排一人，约束条件为：每项工作只能安排一人，约束条件为： 111144342414433323134232221241312111xxxxxxxxxxxxxxxx变量约束：变量约束：4 ,3 ,2 , 110 jixij、，或或Page 72Page 73Page 74Page 75

59、【例【例3.4】某人有一背包可以装】某人有一背包可以装10公斤重、公斤重、0.025m3的物品。他准的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表备用来装甲、乙两种物品，每件物品的重量、体积和价值如表4-1所示。问两种物品各装多少件，所装物品的总价值最大？所示。问两种物品各装多少件，所装物品的总价值最大？表表4-1【解】设甲、乙两种物品各装【解】设甲、乙两种物品各装x1、x2件，则数学模型为：件，则数学模型为：且均取整数, 0,255 . 22108 . 02 . 134max21212121xxxxxxxxZ(4.1)物品物品重量重量（公斤（公斤/每件）每件）体积体积（m

60、3/每件）每件）价值价值(元元/每件每件)甲甲乙乙020.002543Page 76【例【例3.5】在例】在例4.10中，假设此人还有一只旅行箱，最大载重量中，假设此人还有一只旅行箱，最大载重量为为12公斤，其体积是公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。立下列几种情形的数学模型，使所装物品价值最大。（1）所装物品不变；）所装物品不变；（2）如果选择旅行箱，则只能装载丙和丁两种物品，价值分）如果选择旅行箱，则只能装载丙和丁两种物品，价值分别是别是4和和3，载重量和体积的约束为，载重量和