整数规划、对偶理论、线性规划经典例题解说

整数规划是一类要求问题的解中的全部或一部分变量为整数的数学规划，应用范围极其广泛。不仅在工业和工程设计和科学研究方面有很多应用，而且在盘算机设计、系统可靠性和经济分析等方面也有新的应用。
  通过前面的学习，我们已经把握了整数规划的数学模子、割平面法、分支定价法、0-1整数规划和指派问题，相识了求解目标规划的MATLAB以及Python相关代码。
  一、整数规划问题
  

1

  例题1
  

1

  问题描述
  一汽车厂生产小、中、大三种范例的汽车，已知各范例每辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、劳动时间的现有量如下表所示，试订定月生产筹划，使工厂的利润最大。
  进一步讨论：由于各种条件限制，假如生产某一范例汽车，则至少要生产80辆，那么最优的生产筹划应作何改变。
              

           

2

  问题分析
              

           

3

  盘算结果
  原问题：运用本公众号所先容的MATLAB和Python相关代码或用Lingo直接求解得每月生产小、中、大型汽车的数目分别为64，168，0，工厂最大利润为632万元。
  进一步讨论：解得每月生产小、中、大型汽车的数目分别为80，150，0，工厂最大利润为610万元。
  二、0-1整数规划问题
  

2

  固定本钱问题
  

1

  问题描述
  高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和呆板装备，制造一个容器所需的各种资源数目如下表。不考虑固定费用，每种容器单位利润分别为4万元、5万元、6万元，可使用的金属板500吨，劳动力300人/月，呆板100台/月，此外只要生产，需支付固定费用：小号是100万元，中号为150万元，大号为200万元。试订定一个生产筹划，使获利最大。
              

           

2

  问题分析
              

           

3

  盘算结果
  经软件盘算：小号、中号和大号容器的生产数目分别为100，0，0，最大目标函数值为300，即获利最多为300万元。
  

3

  分布系统设计问题
  

1

  问题描述
              

                       

           

2

  问题分析
              

           

3

  盘算结果
              

           

4

  选址问题
  

1

  问题描述
              

                       

           

2

  问题分析
              

           

3

  盘算结果
              

           

5

  投资问题
  

1

  问题描述
  某公司在以后五年内考虑给以下的项目投资。已知项目A：从第一年到第四年每年年初需要投资，并于次年末接纳本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限；
  项目B：第三年初需要投资，到第五年末接纳本利128%，但规定最低投资金额为3万元，最高金额为5万元；
  项目C：第二年初需要投资，到第五年末接纳本利140%，但规定其投资额或为2万元或为4万元，或为6万元或为8万元；
  项目D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。
  该部分现有资金10万元，问应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大？
  

2

  问题分析
              

                       

                       

           

3

  盘算结果
              

           

6

  含有复杂约束的生产问题
  

1

  问题描述
  由于资金和管理水平的限制，某公司想以类似的价格和不同的租期（工时）租赁另一公司甲、乙、丙丁四个车间中的两个，来生产五种新开辟的产品（定名为：A、B、C、D、E）中的最多三种。每种产品在生产过程中要分解成生产难度相似的两个阶段（对于某个车间来说，生产任一阶段所用的工时都是类似的），要求在不同的车间生产，以是一件产品需要两个车间的合作才能完成。由于两个车间的机床和工人的经验不同，生产不同产品的效率也不同，导致不同的产品（任一阶段）在不同的车间生产所用的工时数不同（数据见下表）。另外，根据公司市场部的预测，每种产品的单位利润和在租期内最大的销售量以及各车间在租期内的总工时数等数据也列在下表中。公司管理层应如何选择车间和产品，才能使租期内所获得的利润最大？
              

           

2

  问题分析
              

           

3

  盘算结果
              

           三、指派问题
  

7

  例题7
  

1

  问题描述
  分配甲、乙、丙、丁去完成A、B、C、D、E五项任务。由于任务数多于人数，故规定此中有一个人可兼完成两项任务，其余三人每人完成一项。每人做各项工作所斲丧的时间如下表，试确定总耗费时间最少的指派方案。
              

           

2

  问题分析
              

                       

                       

           

3

  盘算结果
              

           

#2

  

资源使用问题

  
  

#1

  问题描述
  假设某公司生产甲乙两种产品，这两种产品都需要三种资源：装备、原料、燃料。现在已知生产部分提供了如下的数据：
     

资源	甲	乙	最大供应量
装备（台时/件）	2	6	90
原料（公斤/件）	4	2	80
燃料（公斤/件）	1/10	1/5	45
利润（元/件）	5	4

    试问该公司每天应生产甲乙两种产品各多少件时，才能使红利最多？
  假如公司打算通过联合转产或者对外加工来进步经济效益，该公司在何种价格下所获得的红利不少于最大利润？
  

#2

  模子求解
  设每天生产甲产品x1件，乙产品x2件，公司获利Z元；设y1，y2，y3分别体现装备、原料和燃料的每单位的估价，转产后的总效益为G元。
              

           

#3

  问题分析
  “影子价格”是线性规划对偶问题的最优解。这就是说，装备的影子价格为0.3元，原料的影子价格为1.1元，燃料的影子价格为零。当装备增加每个台时所获得的利润即是或大于0.3元，原料增加每公斤所获得的利润即是或大于1.1元时，可以转产或对外加工，否则不考虑转产或对外加工。燃料的影子价格为零，说明增加燃料的供应量并不能进步总的经济效益。
  公司的决策者可以根据“影子价格”的高低来决定是否联合转产或对外加工。
  

#3

  

资源配置问题

  
  

#1

  问题描述
  假设某公司生产甲乙两种产品，这两种产品都需要三种资源：装备、原料、燃料。现在已知生产部分提供了如下的数据：
     

资源	甲	乙	最大供应量
装备（台时/件）	2	6	90
原料（公斤/件）	4	2	80
燃料（公斤/件）	1/10	1/5	45
利润（元/件）	5	4

    企业应该优先配置哪些资源，使得有限资源的情况下得到最大的效益。
  

#2

  模子求解
  设生产x1件甲产品，x2件乙产品。创建如下数学模子。
              

           求解结果为：x1=15，x2= 10， Z=115
  由结果可知，在现有装备、原料和燃料的供应条件下，公司每天要生产15件甲产品，10件乙产品，可获得的最大红利为115元。
  

#3

  问题分析
  当装备从90台时增加到91台时的时间，通过公式
              

           得公司总的经济效益为115.3。这就是说企业总的经济效益从115元增加到115.3元，这个增加数值0.3元，正是此种资源的影子价格。
  同理，当燃料从45公斤增加到46公斤时，企业总的经济效益不增加，即影子价格为零，表明此种资源在现有的条件下有剩余，增加燃料不能进步效益。
  原料增加一个单位时，即从80公斤增加到81公斤时，总的经济效益增加的数值也正是它的影子价格，即0.1。
  因此企业应优先配置装备，其次是燃料。
  综上可得，影子价格大于零，表明此种资源稀缺；影子价格越大，表明此种资源越稀缺，增加此种资源所带来的经济效益就越大；这就是说企业的管理者可以根据影子价格的大小，确定优先配置的资源种类，捉住重点突破影响企业利润增长的瓶颈。
  

配料问题

  
  

问题描述

  某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如表所示。问:该厂应如何安排生产，使利润收入为最大?
     

产品名称	每天最多供应量	单价(元/kg)
甲	原材料1不少于50%，原材料2不凌驾25%	50
乙	原材料1不少于25%， 原材料2不凌驾50%	35
丙	不限	25

      

原材料名称	规格要求	单价(元/kg)
1	100	65
2	100	25
3	60	35

               

           

套裁下料问题

  
  

问题描述

  某钢管零售商从钢管厂进货，将钢管按照顾客的需求切割后售出。从钢管厂进货时得到原料钢管都是19m长。现有一客户需要50根4m长，20根6m长和15 根8m长的钢管，应如何下料最节省?
              

           

生产筹划问题

  
  

问题描述

  永久机械厂生产I、II、 II三种产品，均要颠末A、B两道工序加工。设有两种规格的装备A1、A2能完成A工序；有三种规格的装备B1、B2、 B3能完成B工序。I可A、B的任何规格的装备上加工，II 可在恣意规格的A装备上加工，但对B工序，只能在B1装备上加工，1只能在A2与B2装备上加工。数据如表。问：为使该厂获得最大利润，应如何订定产品加工方案?
              

           
              

           

投资问题

  
  

问题描述

  北方印染公司需要的技能工人分为低级，中级和高级三个条理。统计资料体现：作育出来的每个低级工每年可为公司增加产值1万元，每个中级工每年可为公司增加产值4万元，每个高级工每年可为公司增加产值5.5万元。公司筹划在以后的三年中对招聘的高中生和本公司的技工举行培训，预计拨出150万元作为职工培训费，此中，第一年投资55万元，第二年投资45万元，第三年投资50万元。每个品级的技能工人培训费用和时间如下表所示。
              

           
  现在公司共有低级工226人，中级工560人，高级工496人。由于公司现在师资气力不敷，教学情况有限，每年可作育的职工人数受到肯定限制。根据现在的情况，每年在培的低级工不凌驾90人，在培的中级工不凌驾80人，在培的高级工不凌驾80人。订定培训方案，使企业增加的产值最多。
  
              

           

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。