? ? ???整數(shù)規(guī)劃是一類要求問題的解中的全部或一部分變量為整數(shù)的數(shù)學(xué)規(guī)劃，應(yīng)用范圍極其廣泛。不僅在工業(yè)和工程設(shè)計(jì)和科學(xué)研究方面有許多應(yīng)用，而且在計(jì)算機(jī)設(shè)計(jì)、系統(tǒng)可靠性、編碼和經(jīng)濟(jì)分析等方面也有新的應(yīng)用。

? ? ???通過前面的學(xué)習(xí)，我們已經(jīng)掌握了整數(shù)規(guī)劃的數(shù)學(xué)模型、割平面法、分支定價(jià)法、0-1整數(shù)規(guī)劃和指派問題，了解了求解目標(biāo)規(guī)劃的MATLAB以及Python相關(guān)代碼。

? ? ? ?本期，小編選取三類共七道整數(shù)規(guī)劃的經(jīng)典例題，包括含有一般整數(shù)變量的整數(shù)規(guī)劃問題、0-1整數(shù)規(guī)劃問題和指派問題進(jìn)行詳細(xì)講解。其中，針對0-1整數(shù)變量在構(gòu)建模型中的一些特殊作用，小編整理出五道0-1整數(shù)規(guī)劃的細(xì)分問題，包括固定成本問題、分布系統(tǒng)設(shè)計(jì)問題、選址問題、投資問題和含有復(fù)雜約束的生產(chǎn)問題，以供大家學(xué)習(xí)。

一、一般整數(shù)規(guī)劃問題

1.例題1

問題描述：

一汽車廠生產(chǎn)小、中、大三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤以及每月工廠鋼材、勞動時間的現(xiàn)有量如下表所示，試制定月生產(chǎn)計(jì)劃，使工廠的利潤最大。進(jìn)一步討論：由于各種條件限制，如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變。

問題解析：

計(jì)算結(jié)果：

原問題：運(yùn)用MATLAB或Python相關(guān)代碼或用Lingo直接求解得每月生產(chǎn)小、中、大型汽車的數(shù)量分別為64，168，0，工廠最大利潤為632萬元。

進(jìn)一步討論：解得每月生產(chǎn)小、中、大型汽車的數(shù)量分別為80，150，0，工廠最大利潤為610萬元。

二、0-1整數(shù)規(guī)劃問題

2.固定成本問題

問題描述：

高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機(jī)器設(shè)備，制造一個容器所需的各種資源數(shù)量如下表。不考慮固定費(fèi)用，每種容器單位利潤分別為4萬元、5萬元、6萬元，可使用的金屬板500噸，勞動力300人/月，機(jī)器100臺/月，此外只要生產(chǎn)，需支付固定費(fèi)用：小號是100萬元，中號為150萬元，大號為200萬元。試制定一個生產(chǎn)計(jì)劃，使獲利最大。

問題解析：

計(jì)算結(jié)果：

經(jīng)軟件計(jì)算：小號、中號和大號容器的生產(chǎn)數(shù)量分別為100，0，0，最大目標(biāo)函數(shù)值為300，即獲利最多為300萬元。

3.分布系統(tǒng)設(shè)計(jì)問題

問題描述：

問題解析：

計(jì)算結(jié)果：

4.選址問題

問題描述：

問題解析：

計(jì)算結(jié)果：

5.投資問題

問題描述：

某公司在今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知項(xiàng)目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%，但要求第一年投資最低金額為4萬元，第二、三、四年不限；

項(xiàng)目B：第三年初需要投資，到第五年末回收本利128%，但規(guī)定最低投資金額為3萬元，最高金額為5萬元；

項(xiàng)目C：第二年初需要投資，到第五年末回收本利140%，但規(guī)定其投資額或?yàn)?萬元或?yàn)?萬元，或?yàn)?萬元或?yàn)?萬元；

項(xiàng)目D：五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息6%，此項(xiàng)投資金額不限。

該部門現(xiàn)有資金10萬元，問應(yīng)如何確定給這些項(xiàng)目的每年投資額，使到第五年末擁有的資金本利總額為最大？

問題解析：

計(jì)算結(jié)果：

6.含有復(fù)雜約束的生產(chǎn)問題

因?yàn)橘Y金和管理水平的限制，某公司想以相同的價(jià)格和不同的租期（工時）租賃另一公司甲、乙、丙丁四個車間中的兩個，來生產(chǎn)五種新開發(fā)的產(chǎn)品（命名為：A、B、C、D、E）中的最多三種。每種產(chǎn)品在生產(chǎn)過程中要分解成生產(chǎn)難度相似的兩個階段（對于某個車間來說，生產(chǎn)任一階段所用的工時都是相同的），要求在不同的車間生產(chǎn)，所以一件產(chǎn)品需要兩個車間的合作才能完成。由于兩個車間的機(jī)床和工人的經(jīng)驗(yàn)不同，生產(chǎn)不同產(chǎn)品的效率也不同，導(dǎo)致不同的產(chǎn)品（任一階段）在不同的車間生產(chǎn)所用的工時數(shù)不同（數(shù)據(jù)見下表）。另外，根據(jù)公司市場部的預(yù)測，每種產(chǎn)品的單位利潤和在租期內(nèi)最大的銷售量以及各車間在租期內(nèi)的總工時數(shù)等數(shù)據(jù)也列在下表中。公司管理層應(yīng)如何選擇車間和產(chǎn)品，才能使租期內(nèi)所獲得的利潤最大？

問題解析：

計(jì)算結(jié)果：

三、指派問題

7.例題7

問題描述：

分配甲、乙、丙、丁去完成A、B、C、D、E五項(xiàng)任務(wù)。由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一個人可兼完成兩項(xiàng)任務(wù)，其余三人每人完成一項(xiàng)。每人做各項(xiàng)工作所消耗的時間如下表，試確定總花費(fèi)時間最少的指派方案。

問題解析：

計(jì)算結(jié)果：

? ? ? ?以上就是本期整數(shù)規(guī)劃精品案例的全部內(nèi)容啦，通過對這一期的學(xué)習(xí)，相信大家一定能夠加深對整數(shù)規(guī)劃的理解，尤其是對于不同形式的0-1規(guī)劃問題，一定有了更為全面的認(rèn)識。希望大家能多發(fā)現(xiàn)多思考，在生活實(shí)踐中學(xué)會應(yīng)用！

作者 | 裴傳濤 陳志昂 林鑫

責(zé)編 | 劉文志

審核 | 徐小峰