散文網(wǎng) » 生活 »日常 » 運(yùn)籌說(shuō) 第62期 | 算法介紹之整數(shù)規(guī)劃（二）

運(yùn)籌說(shuō) 第62期 | 算法介紹之整數(shù)規(guī)劃（二）

2022-05-24 17:15 作者:運(yùn)籌說(shuō) 0人讀過(guò) | 我要投稿

?

????本期我們繼續(xù)進(jìn)行運(yùn)籌學(xué)之整數(shù)規(guī)劃算法的講解，我們將對(duì)整數(shù)規(guī)劃的基礎(chǔ)知識(shí)進(jìn)行一個(gè)簡(jiǎn)單的回顧，并介紹求解隱枚舉法和指派問(wèn)題的MATLAB和Python相關(guān)代碼，以幫助大家利用工具快速求解整數(shù)規(guī)劃問(wèn)題，做到事半功倍。由于篇幅有限，小編接下來(lái)只展示部分代碼，小伙伴們可以關(guān)注“運(yùn)籌說(shuō)”公眾號(hào)→后臺(tái)回復(fù)“隱枚舉法之MATLAB”、“隱枚舉之Python”、“指派問(wèn)題之MATLAB”、“指派問(wèn)題之Python”分別獲取對(duì)應(yīng)的完整代碼。話不多說(shuō)，我們一起來(lái)看看吧！

一、基礎(chǔ)知識(shí)

1、隱枚舉法

★?0-1型整數(shù)規(guī)劃

????0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃的一種特殊形式，它的變量? $x_%7Bj%7D$ 僅取值?0 或 1。這種只能取?0?或1 的變量稱(chēng)為0-1變量或二進(jìn)制變量。例如：

????當(dāng)問(wèn)題含有多項(xiàng)限制要素 $E_%7B1%7D%2CE%7B2%7D%2C...%2CE_%7Bn%7D$ ，其中每項(xiàng)都有兩種選擇時(shí)，可令

????0-1型整數(shù)規(guī)劃是一種特殊的整數(shù)規(guī)劃,若含有 n?個(gè)變量,則可以產(chǎn)生 $2%5E%7Bn%7D$ 個(gè)可能的變量組合。當(dāng) n?較大時(shí),采用完全枚舉法解題幾乎是不可能的。已有的求解0-1型整數(shù)規(guī)劃的方法一般都屬于隱枚舉法。

★?基本思路

????求解0-1規(guī)劃的隱枚舉法的基本思路是從所有變量等于零出發(fā)，依次指定一些變量為?1，直至得到一個(gè)可行解，并將它作為最好的可行解。此后，依次檢查變量等于 0 或 1?的變量組合，每當(dāng)發(fā)現(xiàn)比原來(lái)更好的可行解，則進(jìn)行改進(jìn)，最終獲得最優(yōu)解。

????隱枚舉法不同于窮舉法，它不需要將所有可行的變量一一列舉，它通過(guò)分析、判斷排除了許多變量組合作為最優(yōu)解的可能性。

★?求解流程?

2、匈牙利法

★?指派問(wèn)題的標(biāo)準(zhǔn)形式

????指派問(wèn)題的標(biāo)準(zhǔn)形式是：有?n?項(xiàng)任務(wù)，恰好n個(gè)人承擔(dān)，第?i?人完成第?j?項(xiàng)任務(wù)的花費(fèi)(時(shí)間或費(fèi)用等)為? $c_%7Bij%7D$ ，要求確定人和事之間的一一對(duì)應(yīng)的指派方案，使總花費(fèi)最省。

???指派問(wèn)題的系數(shù)矩陣如下：

為建立標(biāo)準(zhǔn)指派問(wèn)題的數(shù)學(xué)模型，引入n?×?n個(gè)0-1變量：

指派問(wèn)題的數(shù)學(xué)模型可寫(xiě)成如下形式：

????其中，約束條件（a）表示每件事必有且只有一個(gè)人做，約束條件（b）表示每個(gè)人必做且只做一件事。指派問(wèn)題有 $n!$ 個(gè)可行解。求解指派問(wèn)題的方法是匈牙利法。

★?基本思路

????匈牙利法的關(guān)鍵是利用了指派問(wèn)題最優(yōu)解的一個(gè)性質(zhì)：若從系數(shù)矩陣的行(列)各元素中分別減去該行(列)的最小元素,得到新矩陣，那么以新矩陣為系數(shù)矩陣求得的最優(yōu)解和用原矩陣求得的最優(yōu)解相同。利用這個(gè)性質(zhì),可使原系數(shù)矩陣變換為含有很多0元素的新矩陣，而最優(yōu)解保持不變。

★?求解流程

?

二、算法實(shí)現(xiàn)

1、隱枚舉法

（1）例題介紹

求解0-1整數(shù)規(guī)劃：

?

（2）平臺(tái)實(shí)現(xiàn)

我們以上述例題為例，借助MATLAB和Python介紹實(shí)現(xiàn)求解“0-1”規(guī)劃的相關(guān)代碼。

①?MATLAB

★?代碼展示

★?代碼調(diào)用

代碼調(diào)用及最終結(jié)果展示如下，最優(yōu)解 $(x_%7B1%7D%2Cx_%7B2%7D%2Cx_%7B3%7D)%5E%7BT%7D%3D(1%2C0%2C1)%5E%7BT%7D%2Cmax%5C%3Bz%3D8$ 。

?

★?注意事項(xiàng)

????MATLAB只能求解目標(biāo)函數(shù)的最小值，而例題要求目標(biāo)函數(shù)最大值，所以對(duì)目標(biāo)函數(shù)進(jìn)行了乘以-1處理，最后的結(jié)果也要乘以-1才是目標(biāo)函數(shù)所求。

②?Python

★?代碼展示

??

★?代碼調(diào)用

代碼運(yùn)行及最終結(jié)果展示如下，最優(yōu)解 $(x_%7B1%7D%2Cx_%7B2%7D%2Cx_%7B3%7D)%5E%7BT%7D%3D(1%2C0%2C1)%5E%7BT%7D%2Cmax%5C%3Bz%3D8$ 。

?

2、指派問(wèn)題

（1）例題介紹

????某商業(yè)公司計(jì)劃開(kāi)辦5家新商店，決定由5家建筑公司分別承建。已知建筑公司 $A_%7Bi%7D$ （i=1,2,…,5）對(duì)新商店 $B_%7Bj%7D$ （j=1,2,…,5）的建造費(fèi)用的報(bào)價(jià)（萬(wàn)元）? $c_%7Bij%7D$ （i,j=1,2,…,5），如下表。商業(yè)公司應(yīng)當(dāng)對(duì)5家建筑公司怎樣分配建造任務(wù)，才能使總的建造費(fèi)用最少？?

若設(shè)0-1變量：

?

則問(wèn)題的數(shù)學(xué)模型為：

?

（2）平臺(tái)實(shí)現(xiàn)

我們以上述例題為例，借助MATLAB和Python介紹實(shí)現(xiàn)求解指派問(wèn)題的相關(guān)代碼。

①?MATLAB

★?代碼展示

★?代碼調(diào)用

代碼運(yùn)行及最終結(jié)果展示如下，最優(yōu)指派方案是讓 $A_%7B1%7D$ 承建 $B_%7B3%7D$ ， $A_%7B2%7D$ 承建 $B_%7B2%7D$ ， $A_%7B3%7D$ 承建 $B_%7B1%7D$ ， $A_%7B4%7D$ 承建 $B_%7B4%7D$ ， $A_%7B5%7D$ 承建 $B_%7B5%7D$ ，這樣安排能使得總的建造費(fèi)用最少，為7+9+6+6+6=34（萬(wàn)元）。

?

②Python

★?代碼展示

★?代碼調(diào)用

代碼運(yùn)行及最終結(jié)果展示如下，最優(yōu)指派方案是讓 $A_%7B1%7D$ 承建 $B_%7B3%7D$ ， $A_%7B2%7D$ 承建 $B_%7B2%7D$ ， $A_%7B3%7D$ ?承建 $B_%7B1%7D$ ， $A_%7B4%7D$ 承建? $B_%7B4%7D$ ， $A_%7B5%7D$ 承建 $B_%7B5%7D$ ，這樣安排能使得總的建造費(fèi)用最少，為7+9+6+6+6=34（萬(wàn)元）。

?

三、參考資料

【隱枚舉法MATLAB實(shí)現(xiàn)】

https://www.jianshu.com/p/37aba460930b

【隱枚舉法Python實(shí)現(xiàn)】

https://blog.csdn.net/youcans/article/details/117463682

【指派問(wèn)題MATLAB實(shí)現(xiàn)】

https://blog.csdn.net/hyc6668378/article/details/52403354

【指派問(wèn)題Python實(shí)現(xiàn)】

https://blog.csdn.net/weixin_39088580/article/details/82685981

本期的內(nèi)容就介紹到這里，想要進(jìn)一步了解運(yùn)籌學(xué)，關(guān)注本公眾號(hào)，快快學(xué)起來(lái)吧！

作者?|?曹貴玲?尹萌娟?陳夢(mèng)?宋偉

責(zé)編?|?劉文志

審核?|?徐小峰

標(biāo)簽：