整數(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ī)劃問題

1

例題1

1

問題描述

一汽車廠生產(chǎn)小、中、大三種類型的汽車，已知各類型每輛車對(duì)鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)以及每月工廠鋼材、勞動(dòng)時(shí)間的現(xiàn)有量如下表所示，試制定月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大。

進(jìn)一步討論：由于各種條件限制，如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變。

2

問題解析

3

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

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

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

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

2

固定成本問題

1

問題描述

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

2

問題解析

3

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

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

3

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

1

問題描述

2

問題解析

3

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

4

選址問題

1

問題描述

2

問題解析

3

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

5

投資問題

1

問題描述

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

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

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

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

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

2

問題解析

3

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

6

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

1

問題描述

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

2

問題解析

3

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

三、指派問題

7

例題7

1

問題描述

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

2

問題解析

3

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

#2

資源使用問題

#1

問題描述

假設(shè)某公司生產(chǎn)甲乙兩種產(chǎn)品，這兩種產(chǎn)品都需要三種資源：設(shè)備、原料、燃料?，F(xiàn)在已知生產(chǎn)部門提供了如下的數(shù)據(jù)：

試問該公司每天應(yīng)生產(chǎn)甲乙兩種產(chǎn)品各多少件時(shí)，才能使盈利最多？

如果公司打算通過聯(lián)合轉(zhuǎn)產(chǎn)或者對(duì)外加工來提高經(jīng)濟(jì)效益，該公司在何種價(jià)格下所獲得的盈利不少于最大利潤(rùn)？

#2

模型求解

設(shè)每天生產(chǎn)甲產(chǎn)品x1件，乙產(chǎn)品x2件，公司獲利Z元；設(shè)y1，y2，y3分別表示設(shè)備、原料和燃料的每單位的估價(jià)，轉(zhuǎn)產(chǎn)后的總效益為G元。

#3

問題解析

“影子價(jià)格”是線性規(guī)劃對(duì)偶問題的最優(yōu)解。這就是說，設(shè)備的影子價(jià)格為0.3元，原料的影子價(jià)格為1.1元，燃料的影子價(jià)格為零。當(dāng)設(shè)備增加每個(gè)臺(tái)時(shí)所獲得的利潤(rùn)等于或大于0.3元，原料增加每公斤所獲得的利潤(rùn)等于或大于1.1元時(shí)，可以轉(zhuǎn)產(chǎn)或?qū)ν饧庸ぃ駝t不考慮轉(zhuǎn)產(chǎn)或?qū)ν饧庸?。燃料的影子價(jià)格為零，說明增加燃料的供應(yīng)量并不能提高總的經(jīng)濟(jì)效益。

公司的決策者可以根據(jù)“影子價(jià)格”的高低來決定是否聯(lián)合轉(zhuǎn)產(chǎn)或?qū)ν饧庸ぁ?/p>

#3

資源配置問題

#1

問題描述

假設(shè)某公司生產(chǎn)甲乙兩種產(chǎn)品，這兩種產(chǎn)品都需要三種資源：設(shè)備、原料、燃料。現(xiàn)在已知生產(chǎn)部門提供了如下的數(shù)據(jù)：

企業(yè)應(yīng)該優(yōu)先配置哪些資源，使得有限資源的情況下得到最大的效益。

#2

模型求解

設(shè)生產(chǎn)x1件甲產(chǎn)品，x2件乙產(chǎn)品。建立如下數(shù)學(xué)模型。

求解結(jié)果為：x1=15，x2= 10， Z=115

由結(jié)果可知，在現(xiàn)有設(shè)備、原料和燃料的供應(yīng)條件下，公司每天要生產(chǎn)15件甲產(chǎn)品，10件乙產(chǎn)品，可獲得的最大盈利為115元。

#3

問題解析

當(dāng)設(shè)備從90臺(tái)時(shí)增加到91臺(tái)時(shí)的時(shí)候，通過公式

得公司總的經(jīng)濟(jì)效益為115.3。這就是說企業(yè)總的經(jīng)濟(jì)效益從115元增加到115.3元，這個(gè)增加數(shù)值0.3元，正是此種資源的影子價(jià)格。

同理，當(dāng)燃料從45公斤增加到46公斤時(shí)，企業(yè)總的經(jīng)濟(jì)效益不增加，即影子價(jià)格為零，表明此種資源在現(xiàn)有的條件下有剩余，增加燃料不能提高效益。

原料增加一個(gè)單位時(shí)，即從80公斤增加到81公斤時(shí)，總的經(jīng)濟(jì)效益增加的數(shù)值也正是它的影子價(jià)格，即0.1。

因此企業(yè)應(yīng)優(yōu)先配置設(shè)備，其次是燃料。

綜上可得，影子價(jià)格大于零，表明此種資源稀缺；影子價(jià)格越大，表明此種資源越稀缺，增加此種資源所帶來的經(jīng)濟(jì)效益就越大；這就是說企業(yè)的管理者可以根據(jù)影子價(jià)格的大小，確定優(yōu)先配置的資源種類，抓住重點(diǎn)突破影響企業(yè)利潤(rùn)增長(zhǎng)的瓶頸。

配料問題

問題描述

某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如表所示。問:該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大?

套裁下料問題

問題描述

某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的需求切割后售出。從鋼管廠進(jìn)貨時(shí)得到原料鋼管都是19m長(zhǎng)?，F(xiàn)有一客戶需要50根4m長(zhǎng)，20根6m長(zhǎng)和15 根8m長(zhǎng)的鋼管，應(yīng)如何下料最節(jié)省?

生產(chǎn)計(jì)劃問題

問題描述

永久機(jī)械廠生產(chǎn)I、II、 II三種產(chǎn)品，均要經(jīng)過A、B兩道工序加工。設(shè)有兩種規(guī)格的設(shè)備A1、A2能完成A工序；有三種規(guī)格的設(shè)備B1、B2、 B3能完成B工序。I可A、B的任何規(guī)格的設(shè)備上加工，II 可在任意規(guī)格的A設(shè)備上加工，但對(duì)B工序，只能在B1設(shè)備上加工，1只能在A2與B2設(shè)備上加工。數(shù)據(jù)如表。問：為使該廠獲得最大利潤(rùn)，應(yīng)如何制定產(chǎn)品加工方案?

投資問題

問題描述

北方印染公司需要的技術(shù)工人分為初級(jí)，中級(jí)和高級(jí)三個(gè)層次。統(tǒng)計(jì)資料顯示：培養(yǎng)出來的每個(gè)初級(jí)工每年可為公司增加產(chǎn)值1萬(wàn)元，每個(gè)中級(jí)工每年可為公司增加產(chǎn)值4萬(wàn)元，每個(gè)高級(jí)工每年可為公司增加產(chǎn)值5.5萬(wàn)元。公司計(jì)劃在今后的三年中對(duì)招聘的高中生和本公司的技工進(jìn)行培訓(xùn)，預(yù)計(jì)撥出150萬(wàn)元作為職工培訓(xùn)費(fèi)，其中，第一年投資55萬(wàn)元，第二年投資45萬(wàn)元，第三年投資50萬(wàn)元。每個(gè)等級(jí)的技術(shù)工人培訓(xùn)費(fèi)用和時(shí)間如下表所示。

目前公司共有初級(jí)工226人，中級(jí)工560人，高級(jí)工496人。由于公司目前師資力量不足，教學(xué)環(huán)境有限，每年可培養(yǎng)的職工人數(shù)受到一定限制。根據(jù)目前的情況，每年在培的初級(jí)工不超過90人，在培的中級(jí)工不超過80人，在培的高級(jí)工不超過80人。制定培訓(xùn)方案，使企業(yè)增加的產(chǎn)值最多。文章來源地址http://www.zghlxwxcb.cn/news/detail-744553.html