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

阳光穿透心脏的1/2处 2023-09-24 17:30 70阅读 0赞

整数规划是一类要求问题的解中的全部或一部分变量为整数的数学规划，应用范围极其广泛。不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性和经济分析等方面也有新的应用。

通过前面的学习，我们已经掌握了整数规划的数学模型、割平面法、分支定价法、0-1整数规划和指派问题，了解了求解目标规划的MATLAB以及Python相关代码。

**一、整数规划问题**

例题1

**问题描述**

一汽车厂生产小、中、大三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、劳动时间的现有量如下表所示，试制定月生产计划，使工厂的利润最大。

进一步讨论：由于各种条件限制，如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变。

![70f60b39638de5dc433ea5e4ee2a0f9e.jpeg][]

**问题解析**

![14f7eaa7a7624a1a5bade607b96f1744.png][]

**计算结果**

原问题：运用本公众号所介绍的MATLAB和Python相关代码或用Lingo直接求解得每月生产小、中、大型汽车的数量分别为64，168，0，工厂最大利润为632万元。

进一步讨论：解得每月生产小、中、大型汽车的数量分别为80，150，0，工厂最大利润为610万元。

**二、0-1整数规划问题**

固定成本问题

**问题描述**

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

![74d78ae0fc0edfa8b14c2d80afbc8a14.jpeg][]

**问题解析**

![4e9b9c479b0413e5c76664041a23d632.png][]

**计算结果**

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

分布系统设计问题

**问题描述**

![aa6be91abe303c9e4258ca270fffc69f.png][]

![22b3cf0bf9afc699fa3a12c86e150720.jpeg][]

**问题解析**

![494421f0836be576b07094131f56656a.png][]

**计算结果**

![d2b9b1a3191feb51878d38cbd198cefc.png][]

选址问题

**问题描述**

![01bc0fb6bc2018a4662c762f49197fc6.png][]

![ac0b002baa72a2dddb8edfaa802d0800.jpeg][]

**问题解析**

![cc61f70be23c88193bea39b7d8a037bb.png][]

**计算结果**

![883b61155a2dc23d75005139561853fa.png][]

投资问题

**问题描述**

某公司在今后五年内考虑给以下的项目投资。已知项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限；

项目B：第三年初需要投资，到第五年末回收本利128%，但规定最低投资金额为3万元，最高金额为5万元；

项目C：第二年初需要投资，到第五年末回收本利140%，但规定其投资额或为2万元或为4万元，或为6万元或为8万元；

项目D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。

该部门现有资金10万元，问应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大？

**问题解析**

![a1ed853710f7b339f3cbdb3ac900a4fd.png][]

![aa0989c08f96c19a91aef1e0b5aca2a5.jpeg][]

![438ccac751c38cd3d98f8856b2a8be12.png][]

**计算结果**

![96d42a5d95283e51d487ac669b45b241.png][]

含有复杂约束的生产问题

**问题描述**

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

![cecc3cf3617e807d5211d0c8421ea3ef.jpeg][]

**问题解析**

![db2e3a13470a0db745d8d0d460a5261e.png][]

**计算结果**

![0d237b6cc4a38da616b3f4a4d6b6acec.png][]

**三、指派问题**

例题7

**问题描述**

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

![36363f7bb765bcfc5c51af57b054a4b4.jpeg][]

**问题解析**

![173c873c1fdb64f78d6d8b65d86a4816.png][]

![c82f4e510a97a3b19b40077cd73b1b5f.jpeg][]

![10ae81a654cae2300ce7fb98c3350343.png][]

**计算结果**

![6e878ccad9a3d148ce89d82d5b7612d7.png][]

**\#2**

**资源使用问题**

\#1

**问题描述**

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

<table style=""> 
 <tbody> 
 <tr> 
 <td style="width:222px;vertical-align:top;height:52px;">资源</td> 
 <td style="width:92px;vertical-align:top;height:52px;">甲</td> 
 <td style="width:81px;vertical-align:top;height:52px;">乙</td> 
 <td style="width:113px;vertical-align:top;height:52px;">最大供应量</td> 
 </tr> 
 <tr> 
 <td style="width:222px;vertical-align:top;height:52px;">设备（台时/件）</td> 
 <td style="width:92px;vertical-align:top;height:52px;">2</td> 
 <td style="width:81px;vertical-align:top;height:52px;">6</td> 
 <td style="width:113px;vertical-align:top;height:52px;">90</td> 
 </tr> 
 <tr> 
 <td style="width:222px;vertical-align:top;height:52px;">原料（公斤/件）</td> 
 <td style="width:92px;vertical-align:top;height:52px;">4</td> 
 <td style="width:81px;vertical-align:top;height:52px;">2</td> 
 <td style="width:113px;vertical-align:top;height:52px;">80</td> 
 </tr> 
 <tr> 
 <td style="width:222px;vertical-align:top;height:52px;">燃料（公斤/件）</td> 
 <td style="width:92px;vertical-align:top;height:52px;">1/10</td> 
 <td style="width:81px;vertical-align:top;height:52px;">1/5</td> 
 <td style="width:113px;vertical-align:top;height:52px;">45</td> 
 </tr> 
 <tr> 
 <td style="width:222px;vertical-align:top;height:52px;">利润（元/件）</td> 
 <td style="width:92px;vertical-align:top;height:52px;">5</td> 
 <td style="width:81px;vertical-align:top;height:52px;">4</td> 
 <td style="width:113px;vertical-align:top;height:52px;"></td> 
 </tr> 
 </tbody> 
</table>

试问该公司每天应生产甲乙两种产品各多少件时，才能使盈利最多？

如果公司打算通过联合转产或者对外加工来提高经济效益，该公司在何种价格下所获得的盈利不少于最大利润？

\#2

**模型求解**

设每天生产甲产品*x*1件，乙产品*x*2件，公司获利Z元；设*y*1，*y*2，*y*3分别表示设备、原料和燃料的每单位的估价，转产后的总效益为*G*元。

![34dedf8dbff37300b9597c7915ff48d9.png][]

\#3

**问题解析**

“影子价格”是线性规划对偶问题的最优解。这就是说，设备的影子价格为0.3元，原料的影子价格为1.1元，燃料的影子价格为零。当设备增加每个台时所获得的利润等于或大于0.3元，原料增加每公斤所获得的利润等于或大于1.1元时，可以转产或对外加工，否则不考虑转产或对外加工。燃料的影子价格为零，说明增加燃料的供应量并不能提高总的经济效益。

公司的决策者可以根据“影子价格”的高低来决定是否联合转产或对外加工。

**\#3**

**资源配置问题**

\#1

**问题描述**

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

<table style=""> 
 <tbody> 
 <tr> 
 <td style="width:224px;vertical-align:top;height:52px;">资源</td> 
 <td style="width:91px;vertical-align:top;height:52px;">甲</td> 
 <td style="width:99px;vertical-align:top;height:52px;">乙</td> 
 <td style="width:130px;vertical-align:top;height:52px;">最大供应量</td> 
 </tr> 
 <tr> 
 <td style="width:224px;vertical-align:top;height:52px;">设备（台时/件）</td> 
 <td style="width:91px;vertical-align:top;height:52px;">2</td> 
 <td style="width:99px;vertical-align:top;height:52px;">6</td> 
 <td style="width:130px;vertical-align:top;height:52px;">90</td> 
 </tr> 
 <tr> 
 <td style="width:224px;vertical-align:top;height:52px;">原料（公斤/件）</td> 
 <td style="width:91px;vertical-align:top;height:52px;">4</td> 
 <td style="width:99px;vertical-align:top;height:52px;">2</td> 
 <td style="width:130px;vertical-align:top;height:52px;">80</td> 
 </tr> 
 <tr> 
 <td style="width:224px;vertical-align:top;height:52px;">燃料（公斤/件）</td> 
 <td style="width:91px;vertical-align:top;height:52px;">1/10</td> 
 <td style="width:99px;vertical-align:top;height:52px;">1/5</td> 
 <td style="width:130px;vertical-align:top;height:52px;">45</td> 
 </tr> 
 <tr> 
 <td style="width:224px;vertical-align:top;height:52px;">利润（元/件）</td> 
 <td style="width:91px;vertical-align:top;height:52px;">5</td> 
 <td style="width:99px;vertical-align:top;height:52px;">4</td> 
 <td style="width:130px;vertical-align:top;height:52px;"></td> 
 </tr> 
 </tbody> 
</table>

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

\#2

**模型求解**

设生产*x*1件甲产品，*x*2件乙产品。建立如下数学模型。

![b01b4e4cf52198259a2ff162eac32cb0.png][]

求解结果为：*x*1=15，*x*2= 10， *Z*=115

由结果可知，在现有设备、原料和燃料的供应条件下，公司每天要生产15件甲产品，10件乙产品，可获得的最大盈利为115元。

\#3

**问题解析**

当设备从90台时增加到91台时的时候，通过公式

![0bee7ae77d9f1917177c29ef16b895d2.png][]

得公司总的经济效益为115.3。这就是说企业总的经济效益从115元增加到115.3元，这个增加数值0.3元，正是此种资源的影子价格。

同理，当燃料从45公斤增加到46公斤时，企业总的经济效益不增加，即影子价格为零，表明此种资源在现有的条件下有剩余，增加燃料不能提高效益。

原料增加一个单位时，即从80公斤增加到81公斤时，总的经济效益增加的数值也正是它的影子价格，即0.1。

因此企业应优先配置设备，其次是燃料。

综上可得，影子价格大于零，表明此种资源稀缺；影子价格越大，表明此种资源越稀缺，增加此种资源所带来的经济效益就越大；这就是说企业的管理者可以根据影子价格的大小，确定优先配置的资源种类，抓住重点突破影响企业利润增长的瓶颈。

**配料问题**

**问题描述**

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

<table style=""> 
 <tbody> 
 <tr> 
 <td style="width:185px;vertical-align:top;height:52px;">产品名称</td> 
 <td style="width:375px;vertical-align:top;height:52px;">每天最多供应量</td> 
 <td style="width:142px;vertical-align:top;height:52px;">单价(元/kg)</td> 
 </tr> 
 <tr> 
 <td style="width:185px;vertical-align:top;height:52px;">甲</td> 
 <td style="width:375px;vertical-align:top;height:52px;">原材料1不少于50%，原材料2不超过25%</td> 
 <td style="width:142px;vertical-align:top;height:52px;">50</td> 
 </tr> 
 <tr> 
 <td style="width:185px;vertical-align:top;height:52px;">乙</td> 
 <td style="width:375px;vertical-align:top;height:52px;">原材料1不少于25%，原材料2不超过50%</td> 
 <td style="width:142px;vertical-align:top;height:52px;">35</td> 
 </tr> 
 <tr> 
 <td style="width:185px;vertical-align:top;height:52px;">丙</td> 
 <td style="width:375px;vertical-align:top;height:52px;">不限</td> 
 <td style="width:142px;vertical-align:top;height:52px;">25</td> 
 </tr> 
 </tbody> 
</table>

<table style=""> 
 <tbody> 
 <tr> 
 <td style="width:244px;vertical-align:top;height:52px;">原材料名称</td> 
 <td style="width:244px;vertical-align:top;height:52px;">规格要求</td> 
 <td style="width:244px;vertical-align:top;height:52px;">单价(元/kg)</td> 
 </tr> 
 <tr> 
 <td style="width:244px;vertical-align:top;height:52px;">1</td> 
 <td style="width:244px;vertical-align:top;height:52px;">100</td> 
 <td style="width:244px;vertical-align:top;height:52px;">65</td> 
 </tr> 
 <tr> 
 <td style="width:244px;vertical-align:top;height:52px;">2</td> 
 <td style="width:244px;vertical-align:top;height:52px;">100</td> 
 <td style="width:244px;vertical-align:top;height:52px;">25</td> 
 </tr> 
 <tr> 
 <td style="width:244px;vertical-align:top;height:52px;">3</td> 
 <td style="width:244px;vertical-align:top;height:52px;">60</td> 
 <td style="width:244px;vertical-align:top;height:52px;">35</td> 
 </tr> 
 </tbody> 
</table>

![376294cec37441fd77657998b5da4c77.jpeg][]

**套裁下料问题**

**问题描述**

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

![d7d8167caf347acc3cbcba5a6cc139c7.jpeg][]

**生产计划问题**

**问题描述**

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

![55302dbd0cf0625da744fe5c2656f400.jpeg][]

![c524508ff5197b07284ed0ecc37e0591.jpeg][]

**投资问题**

**问题描述**

北方印染公司需要的技术工人分为初级，中级和高级三个层次。统计资料显示：培养出来的每个初级工每年可为公司增加产值1万元，每个中级工每年可为公司增加产值4万元，每个高级工每年可为公司增加产值5.5万元。公司计划在今后的三年中对招聘的高中生和本公司的技工进行培训，预计拨出150万元作为职工培训费，其中，第一年投资55万元，第二年投资45万元，第三年投资50万元。每个等级的技术工人培训费用和时间如下表所示。

![b44235f11eee9b4b658c0511c961ab6a.jpeg][]

目前公司共有初级工226人，中级工560人，高级工496人。由于公司目前师资力量不足，教学环境有限，每年可培养的职工人数受到一定限制。根据目前的情况，每年在培的初级工不超过90人，在培的中级工不超过80人，在培的高级工不超过80人。制定培训方案，使企业增加的产值最多。

![00c7e732708ddb9360bc1dda90b6aa35.jpeg][]

[70f60b39638de5dc433ea5e4ee2a0f9e.jpeg]: https://img-blog.csdnimg.cn/img_convert/70f60b39638de5dc433ea5e4ee2a0f9e.jpeg
[14f7eaa7a7624a1a5bade607b96f1744.png]: https://img-blog.csdnimg.cn/img_convert/14f7eaa7a7624a1a5bade607b96f1744.png
[74d78ae0fc0edfa8b14c2d80afbc8a14.jpeg]: https://img-blog.csdnimg.cn/img_convert/74d78ae0fc0edfa8b14c2d80afbc8a14.jpeg
[4e9b9c479b0413e5c76664041a23d632.png]: https://img-blog.csdnimg.cn/img_convert/4e9b9c479b0413e5c76664041a23d632.png
[aa6be91abe303c9e4258ca270fffc69f.png]: https://img-blog.csdnimg.cn/img_convert/aa6be91abe303c9e4258ca270fffc69f.png
[22b3cf0bf9afc699fa3a12c86e150720.jpeg]: https://img-blog.csdnimg.cn/img_convert/22b3cf0bf9afc699fa3a12c86e150720.jpeg
[494421f0836be576b07094131f56656a.png]: https://img-blog.csdnimg.cn/img_convert/494421f0836be576b07094131f56656a.png
[d2b9b1a3191feb51878d38cbd198cefc.png]: https://img-blog.csdnimg.cn/img_convert/d2b9b1a3191feb51878d38cbd198cefc.png
[01bc0fb6bc2018a4662c762f49197fc6.png]: https://img-blog.csdnimg.cn/img_convert/01bc0fb6bc2018a4662c762f49197fc6.png
[ac0b002baa72a2dddb8edfaa802d0800.jpeg]: https://img-blog.csdnimg.cn/img_convert/ac0b002baa72a2dddb8edfaa802d0800.jpeg
[cc61f70be23c88193bea39b7d8a037bb.png]: https://img-blog.csdnimg.cn/img_convert/cc61f70be23c88193bea39b7d8a037bb.png
[883b61155a2dc23d75005139561853fa.png]: https://img-blog.csdnimg.cn/img_convert/883b61155a2dc23d75005139561853fa.png
[a1ed853710f7b339f3cbdb3ac900a4fd.png]: https://img-blog.csdnimg.cn/img_convert/a1ed853710f7b339f3cbdb3ac900a4fd.png
[aa0989c08f96c19a91aef1e0b5aca2a5.jpeg]: https://img-blog.csdnimg.cn/img_convert/aa0989c08f96c19a91aef1e0b5aca2a5.jpeg
[438ccac751c38cd3d98f8856b2a8be12.png]: https://img-blog.csdnimg.cn/img_convert/438ccac751c38cd3d98f8856b2a8be12.png
[96d42a5d95283e51d487ac669b45b241.png]: https://img-blog.csdnimg.cn/img_convert/96d42a5d95283e51d487ac669b45b241.png
[cecc3cf3617e807d5211d0c8421ea3ef.jpeg]: https://img-blog.csdnimg.cn/img_convert/cecc3cf3617e807d5211d0c8421ea3ef.jpeg
[db2e3a13470a0db745d8d0d460a5261e.png]: https://img-blog.csdnimg.cn/img_convert/db2e3a13470a0db745d8d0d460a5261e.png
[0d237b6cc4a38da616b3f4a4d6b6acec.png]: https://img-blog.csdnimg.cn/img_convert/0d237b6cc4a38da616b3f4a4d6b6acec.png
[36363f7bb765bcfc5c51af57b054a4b4.jpeg]: https://img-blog.csdnimg.cn/img_convert/36363f7bb765bcfc5c51af57b054a4b4.jpeg
[173c873c1fdb64f78d6d8b65d86a4816.png]: https://img-blog.csdnimg.cn/img_convert/173c873c1fdb64f78d6d8b65d86a4816.png
[c82f4e510a97a3b19b40077cd73b1b5f.jpeg]: https://img-blog.csdnimg.cn/img_convert/c82f4e510a97a3b19b40077cd73b1b5f.jpeg
[10ae81a654cae2300ce7fb98c3350343.png]: https://img-blog.csdnimg.cn/img_convert/10ae81a654cae2300ce7fb98c3350343.png
[6e878ccad9a3d148ce89d82d5b7612d7.png]: https://img-blog.csdnimg.cn/img_convert/6e878ccad9a3d148ce89d82d5b7612d7.png
[34dedf8dbff37300b9597c7915ff48d9.png]: https://img-blog.csdnimg.cn/img_convert/34dedf8dbff37300b9597c7915ff48d9.png
[b01b4e4cf52198259a2ff162eac32cb0.png]: https://img-blog.csdnimg.cn/img_convert/b01b4e4cf52198259a2ff162eac32cb0.png
[0bee7ae77d9f1917177c29ef16b895d2.png]: https://img-blog.csdnimg.cn/img_convert/0bee7ae77d9f1917177c29ef16b895d2.png
[376294cec37441fd77657998b5da4c77.jpeg]: https://img-blog.csdnimg.cn/img_convert/376294cec37441fd77657998b5da4c77.jpeg
[d7d8167caf347acc3cbcba5a6cc139c7.jpeg]: https://img-blog.csdnimg.cn/img_convert/d7d8167caf347acc3cbcba5a6cc139c7.jpeg
[55302dbd0cf0625da744fe5c2656f400.jpeg]: https://img-blog.csdnimg.cn/img_convert/55302dbd0cf0625da744fe5c2656f400.jpeg
[c524508ff5197b07284ed0ecc37e0591.jpeg]: https://img-blog.csdnimg.cn/img_convert/c524508ff5197b07284ed0ecc37e0591.jpeg
[b44235f11eee9b4b658c0511c961ab6a.jpeg]: https://img-blog.csdnimg.cn/img_convert/b44235f11eee9b4b658c0511c961ab6a.jpeg
[00c7e732708ddb9360bc1dda90b6aa35.jpeg]: https://img-blog.csdnimg.cn/img_convert/00c7e732708ddb9360bc1dda90b6aa35.jpeg