Python小白的數學建模課-05.0-1規劃-有解無憂

0-1 規劃不僅是數模競賽中的常見題型，也具有重要的現實意義，

雙十一促銷中網購平臺要求二選一，就是互斥的決策問題，可以用 0-1規劃建模，

小白學習 0-1 規劃，首先要學會識別 0-1規劃，學習將問題轉化為數學模型，

『Python小白的數學建模課 @ Youcans』帶你從數模小白成為國賽達人，

1. 什么是 0-1 規劃？

0-1 整數規劃是一類特殊的整數規劃，變數的取值只能是 0 或 1，

0-1 變數可以描述開關、取舍、有無等邏輯關系、順序關系，可以處理背包問題、指派問題、選址問題、計劃安排、線路設計、人員安排等各種決策規劃問題，進而，任何整數都可以用二進制表達，整數變數就可以表示為多個 0-1 變數的組合，因此任何整數規劃都可以轉化為 0-1 規劃問題來處理，0-1 規劃問題與運籌學中的很多經典問題也都有緊密聯系，

在數學建模學習中，0-1 規劃主要用于求解互斥的決策問題、互斥的約束條件問題、固定費用問題和分派問題，0-1 規劃是數模競賽的常見題型，國賽 B題經常有 0-1規劃問題或可以轉化為 0-1 規劃問題，

0-1 規劃的演算法都比較復雜，大規模問題一般沒有精確解法，本文仍然使用 PuLP 工具包求解 0-1 規劃問題，該工具包的使用比較簡單，建議本文讀者重點關注 0-1 規劃問題的分類及建模方法，把握哪些問題是 0-1 規劃問題，是哪一類的 0-1 規劃問題，如何對這些典型問題進行建模，在此基礎上，才能呼叫 PuLP 函式進行求解，

歡迎關注『Python小白的數學建模課 @ Youcans』，每周更新數模筆記
Python小白的數學建模課-01.新手必讀
Python小白的數學建模課-02.資料匯入
Python小白的數學建模課-03.線性規劃
Python小白的數學建模課-04.整數規劃
Python小白的數學建模課-05.0-1規劃
Python數模筆記-PuLP庫
Python數模筆記-StatsModels統計回歸
Python數模筆記-Sklearn
Python數模筆記-NetworkX
Python數模筆記-模擬退火演算法

2. 0-1 規劃的分類及建模方法

規劃問題的數學模型包括決策變數、約束條件和目標函式，圍繞這三個要素都可能存在互斥的情況，從而匯出不同型別的0-1規劃問題，其建模方法也有差別，

2.1 互斥的決策問題

互斥的決策問題，是指決策方案、計劃互斥，如決定投資專案、確定投資場所、選擇投產產品等，

例如，雙十一的促銷活動，淘寶、京東、拼多多要求店鋪二選一，最多只能選擇參加一家平臺，否則可能會被封殺，這是典型的互斥決策問題，

背包問題就是經典的互斥決策問題，給定一組 n 個物品，每種物品 i 的價值為 v_i、重量/體積為 w_i，背包所能容納的總重量/總容量為（B），如何選擇其中若干種物品（每種物品選 0 個或 1 個），使得物品的總價值最高？

背包問題的建模方法如下：

定義決策變數為：

\[x_i = \begin{cases} 0，不選擇第\;i\;個物品\\ 1，選擇第\;i\;個物品 \end{cases} \]

定義目標函式為：

\[max\;f(x) = \sum_{i=1}^n v_i x_i\\ s.t.:\begin{cases} \sum_{i=i}^n w_i x_i \leq B, \\ x_i = 0,1 \end{cases} \]

很多應用問題都可以用上述的背包問題數學模型來表達，例如：

有 n個專案，每個專案所需投資額為 w_i，投產后的利潤為 v_i，投資總限額為 B，求利潤最大的投資方案；
處理器能力有限，任務很多，如何選擇使處理器的效用最大；

2.2 互斥的約束問題

互斥的約束問題，是指具有多個互斥的約束條件，這些約束條件只有一個起作用，

例如，貨物運輸有車運或者船運兩種運輸方式可供選擇，已知采用車運的約束條件和船運的約束條件，必須且只能選擇其中一種運輸方式，這兩個約束條件互斥，有且只有一個起作用，這是可以引入一個 0-1變數來處理，

一般地，設有 m 個互斥的約束條件：

\[a_{i1}x_1 + ...a_{in}x_n \leq b_i，i=1,...m \]

該類問題的建模方法，為了保證只有一個約束條件起作用，可以引入一個充分大的常數 M 和 m 個 0-1 變數表示約束是否起作用：

\[y_i = \begin{cases} 0，第 i 個約束不起作用\\ 1，第 i 個約束起作用 \end{cases} \]

于是可以構造新的 m+1 個約束條件：

\[s.t.:\begin{cases} a_{i1}x_1 + ...a_{in}x_n \leq b_i + (1-y_i)M，i=1,...m\\ y_1 + ... + y_m = 1\\ y_i = 0,1 \end{cases} \]

由于 M 足夠大，新的約束條件就能保證只有 y_i=1 的約束條件起作用，而其它約束條件都不起作用，

2.3 固定費用問題（Fixed cost problem）

固定費用問題，是指求解生產成本最小問題時，總成本包括固定成本和變動成本，而選擇不同生產方式會有不同的固定成本，因此總成本與選擇的生產方式有關，

固定費用問題，實際上是互斥的目標函式問題，對于不同的生產方式具有多個互斥的目標函式，但只有一個起作用，固定費用問題不能用一般的線性規劃模型求解，

一般地，設有 m 種生產方式可供選擇，采用第 j 種方式時的固定成本為 K_j、變動成本為 c_j、產量為 x_j，則采用各種生產方式的總成本分別為：

\[min\;P_j = \begin{cases} k_j + c_j x_j，&x_j \geq 0\\ 0，&x_j = 0, j=1,...m \end{cases} \]

該類問題的建模方法，為了構造統一的目標函式，可以引入 m 個 0-1 變數 y_j 表示是否采用第 j 種生產方式：

\[y_j = \begin{cases} 0，不采用第\;j\;種生產方式\\ 1，采用第\;j\; 種生產方式 \end{cases} \]

于是可以構造新的目標函式和約束條件：

\[min\;f(x) = \sum_{j=1} ^m (k_j y_j + c_j x_j)\\ s.t.:\;x_j \leq y_j M，j=1,...m \]

M 是一個充分大的常數，

2.4 指派問題

分配 n 個人去做 n 件作業，每人只做一件作業，每件作業只有一個人做，已知每個人做每件事的用時為c_ij，如何安排才能使花費的總時間最少，

引入 0-1 變數 x_ij：

\[x_{i,j} = \begin{cases} 0，第\;i\;人不做第\;j\;件作業\\ 1，第\;i\;人做第\;j\;件作業，i,j=1,...,n \end{cases} \]

指派問題的數學模型就可以描述為：

\[min\;f(x) = \sum_{i=1} ^n \sum_{j=1} ^n (c_{ij} x_{ij})\\ s.t.:\;\begin{cases} \sum_{j=1} ^n x_{ij} = 1，i=1,...,n\\ \sum_{i=1} ^n x_{ij} = 1，j=1,...,n\\ x_{ij} = 0,1，i,j=1,...,n \end{cases} \]

在此基礎上，還可以衍生出新的問題：

分配 m 個人去做 n 件作業，已知每個人做每件事的用時，當 m<n（不限定每人作業的件數）、m>n（不限定每件作業的參與人數）時，如何安排使花費的總時間最少，
分配 m 個人去做 n 件作業，已知每個人做每件事的用時，如果允許某人完成自己的作業后去幫助別人，如何安排使花費的總時間最少，

3. 0-1 規劃的求解方法

目前 0-1 規劃問題并沒有通用、高效、精確的求解方法，常用的方法或是針對特殊問題，或是近似方法，

需要特別指出的是，我們在數學建模的學習中會遇到越來越多的問題都沒有通用、高效、精確的求解方法，而是借助于計算機演算法和程式來得到近似解，

3.1 隱列舉法（Implicit enumeration）

求解 0-1 規劃問題的思路，首先是窮舉法，遍歷決策變數的所有的組合，求出目標函式的最優值，隨著問題規模的增大，變數的組合成指數增長，窮舉法就不可能實作了，

隱列舉法是通過反復構造過濾條件，不斷洗掉比當前解差的解集，并把優于當前最優解的結果作為新的最優解，再以新的最優解構造新的過濾條件，如此反復直到求出最優解，

隱列舉法通過過濾條件對窮舉法進行改進，可以較快地求出最優解，分支定界法也是一種隱列舉法，

3.2 蒙特卡洛法（Monte Carlo）

既然對較大規模問題無法窮舉，無法獲得數學意義上的最優解，那么另一個思路就是隨機搜索，于是大名鼎鼎、無所不能的蒙特卡洛法出場了，

蒙特卡洛法是一類隨機方法的統稱，也稱隨機取樣法，顧名思義，蒙特卡洛法就是大量地對決策變數隨機取值——如果能在滿足約束條件的前提下隨機取值就更好了，通過比較其目標函式值來不斷獲得更好的解，最后就能得到近似的最優解，

蒙特卡洛法的特點是，可以在隨機采樣上計算得到近似結果，采樣越多，越近似最優解，但無法保證得到的結果是不是全域最優解，可以證明，在一定的計算量的情況下，蒙特卡洛法可以獲得較好的滿意解，

蒙特卡洛法的思想很簡單，看起來演算法也很簡單，但實際上也涉及了深刻的數學理論，演算法理論與實踐也都在不斷的發展，

蒙特卡洛法不僅可以處理幾乎所有的決策問題、優化問題，而且在各種學科領域都得到了廣泛的應用，這樣的方法我們當然不能錯過，后文將專題進行討論，

3.3 啟發式演算法（Heuristic algorithms）

設計高效的啟發式演算法解決實際問題，是解決 0-1 規劃問題的另一個思路，

啟發式演算法通常是以問題為導向的，沒有一個通用的框架，根據具體問題的特殊結構來識別啟發性資訊，構造啟發式優化程序來高效地尋找近似最優解，

啟發式演算法獲得的近似最優解，通常是區域最優解，而且，啟發式演算法的解需要借助其他方法來評估其質量，并且在實際應用中不能保證為各種算例穩定地生成接近全域最優的可行解，

3.4 近似演算法（Approximation algorithms）

本來不想在這里談近似演算法的，只是為了說明啟發式演算法并不是近似演算法，

近似演算法與啟發式演算法是不同的，近似演算法往往通過巧妙的設計，得到的解是在全域最優解的某個鄰域范圍之內，或一定比例范圍內，近似演算法的解可以用嚴格的數學證明是“比較好”的，因而被認為是有保證的，

3.5 0-1 規劃問題的編程方案

總結 0-1 規劃的求解方法，就是沒有通用、高效、精確的求解方法，

對于小白來說，其實這樣更簡單，不要操心學習哪種演算法了，我們還是用 PuLP 工具包來求解，

4. PuLP 求解 0-1 規劃問題

不僅繼續用 PuLP 工具包，而且解題程序和編程步驟也與求解線性規劃問題完全一致，

下面我們以一個簡單的數學模型練習，來講解整個解題程序，而不僅給出例程，

4.1 案例問題描述

例題 1：
公司有 5 個專案被列入投資計劃，各專案的投資額和預期投資收益如下表所示（萬元）：

專案	A	B	C	D	E
投資額	210	300	100	130	260
投資收益	150	210	60	80	180

公司只有 600萬元資金可用于投資，綜合考慮各方面因素，需要保證：

（1）專案 A、B、C 中必須且只能有一項被選中；
（2）專案 C、D 中最多只能選中一項；
（3）選擇專案 E 的前提是專案 A被選中，

如何在上述條件下，進行投資決策，使收益最大，

4.2 建模程序分析

定義決策變數為：

\[x_i = \begin{cases} 0，不選擇第\;i\;個專案\\ 1，選擇第\;i\;個專案 \end{cases} \]

定義目標函式為：

\[max\;f(x) = 150x_1+210x_2+60x_3+80x_4+180x_5\\ s.t.:\begin{cases} 210x_1+300x_2+100x_3+130x_4+260x_5 \leq 600\\ x_1 + x_2 + x_3 = 1\\ x_3 + x_4 \leq 1\\ x_5 \leq x_1\\ x_i = 0,1，i=1,...5 \end{cases} \]

4.3 模型求解的編程

模型求解，用標準模型的優化演算法對模型求解，得到優化結果，模型求解的編程步驟如下：

（0）匯入 PuLP庫函式

    import pulp

（1）定義一個規劃問題

     InvestLP = pulp.LpProblem("Invest decision problem", sense=pulp.LpMaximize)

pulp.LpProblem 用來定義問題的建構式，"InvestLP"是用戶定義的問題名，
引數 sense 指定問題求目標函式的最小值/最大值，本例求最大值，選擇 “pulp.LpMaximize” ，

（2）定義決策變數
對于問題 1：

    x1 = pulp.LpVariable('A', cat='Binary')  # 定義 x1，A 專案
    x2 = pulp.LpVariable('B', cat='Binary')  # 定義 x2，B 專案
    x3 = pulp.LpVariable('C', cat='Binary')  # 定義 x3，C 專案
    x4 = pulp.LpVariable('D', cat='Binary')  # 定義 x4，D 專案
    x5 = pulp.LpVariable('E', cat='Binary')  # 定義 x5，E 專案

pulp.LpVariable 用來定義決策變數的函式，'x1'~'x5' 是用戶定義的變數名，
引數 cat 用來設定變數型別，' Binary ' 表示0/1變數（用于0/1規劃問題），

（3）添加目標函式

    InvestLP += (150*x1 + 210*x2 + 60*x3 + 80*x4 + 180*x5)  # 設定目標函式 f(x)

（4）添加約束條件

    InvestLP += (210*x1 + 300*x2 + 100*x3 + 130*x4 + 260*x5 <= 600)  # 不等式約束
    InvestLP += (x1 + x2 + x3 == 1)  # 等式約束
    InvestLP += (x3 + x4 <= 1)  # 不等式約束
    InvestLP += (x5 - x1 <= 0)  # 不等式約束

　　添加約束條件使用 "問題名 += 約束條件運算式" 格式，
　　約束條件可以是等式約束或不等式約束，不等式約束可以是小于等于或大于等于，分別使用關鍵字">="、"<="和"=="，

（5）求解

    InvestLP.solve()
    print(InvestLP.name)  # 輸出求解狀態
    print("Status youcans:", pulp.LpStatus[InvestLP.status])  # 輸出求解狀態
    for v in InvestLP.variables():
        print(v.name, "=", v.varValue)  # 輸出每個變數的最優值
    print("Max f(x) =", pulp.value(InvestLP.objective))  # 輸出最優解的目標函式值

solve() 是求解函式，可以對求解器、求解精度進行設定，

4.4 Python 例程

# mathmodel06_v1.py
# Demo05 of mathematical modeling algorithm
# Solving 0-1 binary programming with PuLP.
# Copyright 2021 Youcans, XUPT
# Crated：2021-06-02
# Python小白的數學建模課 @ Youcans

import pulp      # 匯入 pulp 庫

# 主程式
def main():
    # 投資決策問題：
    # 公司現有 5個擬投資專案，根據投資額、投資收益和限制條件，問如何決策使收益最大，
    """
    問題建模：
        決策變數：
            x1～x5：0/1 變數，1 表示選擇第 i 個專案， 0 表示不選擇第 i 個專案
        目標函式：
            max fx = 150*x1 + 210*x2 + 60*x3 + 80*x4 + 180*x5
        約束條件：
            210*x1 + 300*x2 + 100*x3 + 130*x4 + 260*x5 <= 600
            x1 + x2 + x3 = 1
            x3 + x4 <= 1
            x5 <= x1
            x1,...,x5 = 0, 1
    """
    InvestLP = pulp.LpProblem("Invest decision problem", sense=pulp.LpMaximize)  # 定義問題，求最大值
    x1 = pulp.LpVariable('A', cat='Binary')  # 定義 x1，A 專案
    x2 = pulp.LpVariable('B', cat='Binary')  # 定義 x2，B 專案
    x3 = pulp.LpVariable('C', cat='Binary')  # 定義 x3，C 專案
    x4 = pulp.LpVariable('D', cat='Binary')  # 定義 x4，D 專案
    x5 = pulp.LpVariable('E', cat='Binary')  # 定義 x5，E 專案
    InvestLP += (150*x1 + 210*x2 + 60*x3 + 80*x4 + 180*x5)  # 設定目標函式 f(x)
    InvestLP += (210*x1 + 300*x2 + 100*x3 + 130*x4 + 260*x5 <= 600)  # 不等式約束
    InvestLP += (x1 + x2 + x3 == 1)  # 等式約束
    InvestLP += (x3 + x4 <= 1)  # 不等式約束
    InvestLP += (x5 - x1 <= 0)  # 不等式約束
    InvestLP.solve()  # youcans
    print(InvestLP.name)  # 輸出求解狀態
    print("Status youcans:", pulp.LpStatus[InvestLP.status])  # 輸出求解狀態
    for v in InvestLP.variables():
        print(v.name, "=", v.varValue)  # 輸出每個變數的最優值
    print("Max f(x) =", pulp.value(InvestLP.objective))  # 輸出最優解的目標函式值

    return

if __name__ == '__main__':  # Copyright 2021 YouCans, XUPT
    main()  # Python小白的數學建模課 @ Youcans

4.5 Python 例程運行結果

Welcome to the CBC MILP Solver 
Version: 2.9.0 
Build Date: Feb 12 2015 

Result - Optimal solution found

Invest_decision_problem
Status youcans: Optimal
A = 1.0
B = 0.0
C = 0.0
D = 1.0
E = 1.0
Max f(x) = 410.0

從 0-1 規劃模型的結果可知，選擇 A、C、E 專案進行投資，可以滿足限定條件并獲得最大收益 410萬元，

5. 小結

對于小白學數模，能識別哪些問題是 0-1 規劃問題，是哪種 0-1規劃問題，才能將問題描述轉化為數學模型的表達形式，這是數模學習中最重要的內容，
至于模型的求解，對于演算法能了解一些最好，不求甚解也沒關系，先學會用工具包解決問題就可以了，
從線性規劃、整數規劃到本文的 0-1 規劃，我們都選擇了 PuLP 工具包，雖然這些問題的型別不同，求解演算法差別非常大，但是 PuLp 工具包使用了一致的處理步驟：定義問題、定義變數、定義目標函式和約束條件，呼叫求解器求解，
所以我們在求解不同問題時的編程方法和步驟如出一轍，完全感受不到不同型別問題之間的巨大差異，這就是為什么在線性規劃問題時不選擇 Scipy 的原因，這就是本系列課程的特點，讓小白能快速入門求解問題，
對于更為復雜的問題，PuLP 還提供了快捷方式，可以結合 Python語言的回圈和容器，使用字典來創建問題，我們下節再講，

【本節完】

著作權宣告：

歡迎關注『Python小白的數學建模課 @ Youcans』原創作品

原創作品，轉載必須標注原文鏈接：，

Crated：2021-06-02

歡迎關注『Python小白的數學建模課 @ Youcans』，每周更新數模筆記
Python小白的數學建模課-01.新手必讀
Python小白的數學建模課-02.資料匯入
Python小白的數學建模課-03.線性規劃
Python小白的數學建模課-04.整數規劃
Python小白的數學建模課-05.0-1規劃
Python小白的數學建模課-A1.國賽賽題型別分析
Python小白的數學建模課-A2.2021年數維杯C題探討
Python數模筆記-PuLP庫
Python數模筆記-StatsModels統計回歸
Python數模筆記-Sklearn
Python數模筆記-NetworkX
Python數模筆記-模擬退火演算法

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/285586.html

標籤：Python

上一篇：Python爬蟲基礎講解（二十）：多行程——multiprocessing模塊的使用

下一篇：pandas（11）:資料合并