簡(jiǎn)潔是智慧的靈魂，冗長(zhǎng)是膚淺的藻飾。——莎士比亞《哈姆雷特》

1.PuLP 庫(kù)的安裝

如果您使用的是 Anaconda的話（事實(shí)上我也更推薦這樣做），需要先激活你想要安裝的虛擬環(huán)境，之后在 Prompt 輸入

pip install pulp

不出意外的話等一會(huì)就安裝完畢。

2.線性規(guī)劃簡(jiǎn)介

想必大家能點(diǎn)開(kāi)這篇文章一定都知道線性規(guī)劃是什么意思吧……那么我用兩個(gè)例子再簡(jiǎn)單說(shuō)一下。

2.1 線性規(guī)劃

2.1.1 題目描述

若變量x,y 滿足約束條件：

求z=3x+y 的最大值。

2.1.2 基本概念

首先，我們要認(rèn)清在這道題中，x和y是可以變的，所以把它們叫做決策變量。三個(gè)不等式叫做約束條件，即x和y必須同時(shí)滿足這三個(gè)不等式。我們?nèi)舢?huà)出圖來(lái)：

其中不滿足約束條件的區(qū)域被我標(biāo)上了顏色，所以x,y 可以取得值只能在純白區(qū)域內(nèi)，這一片區(qū)域稱作可行域。

再看最后的我們的目標(biāo)：求z=x+3y 的最大值。

于是z=x+3y 就被稱作目標(biāo)函數(shù)，我們的工作就是求這個(gè)目標(biāo)函數(shù)的最大值。

整個(gè)問(wèn)題描述為：

然后怎么算？別急我們?cè)倏匆粋€(gè)例子。

2.2 整數(shù)規(guī)劃

2.2.1 題目描述

汽車廠生產(chǎn)小、中、大三種類型的汽車，已知各類型每輛車對(duì)鋼材、勞動(dòng)時(shí)間的需求以及利潤(rùn)如下表所示。要求每月的鋼材消耗不超過(guò) 600 t，總勞動(dòng)時(shí)間不超過(guò) 60 000 h。試指定生產(chǎn)計(jì)劃使得工廠每月的利潤(rùn)最大。

2.2.2 解題思路

首先，設(shè)三個(gè)決策變量，用x1,x2,x3 分別表示生產(chǎn)小型車、中型車、大型車的數(shù)量，但是注意要滿足：

• 車的數(shù)量只能是整數(shù)；
• 車的數(shù)量大于等于 0。

其他約束條件看題直接列：

最后寫(xiě)出目標(biāo)函數(shù)：

z=2x₁+3x₂+4x₃

綜合起來(lái)整個(gè)問(wèn)題描述為：

另外可以看出這個(gè)題由于涉及到三個(gè)決策變量，可行域是相當(dāng)抽象的，這里就不畫(huà)了 hhh~

3.求解過(guò)程

首先在最前面引入所需的pulp工具庫(kù)：

import pulp as pl

這句話是引入 pulp 庫(kù)并簡(jiǎn)寫(xiě)為 pl，一個(gè) python 庫(kù)只有在開(kāi)始 import 了之后才能在后面使用。這樣后面凡是用到 pulp 的功能都要寫(xiě)成 pl.xxx。

接下來(lái)是以下幾個(gè)步驟：

• 定義模型
• 定義決策變量
• 添加約束條件
• 添加目標(biāo)函數(shù)
• 模型求解
• 打印結(jié)果

3.1 定義模型

# Define the model
model = pl.LpProblem(name="My-Model", sense=pl.LpMaximize)

這個(gè)操作是使用 pl.LpProblem 創(chuàng)建了一個(gè)模型并賦值給變量 model，接收兩個(gè)參數(shù)：

• name：模型的名字，隨便起一個(gè)；
• sense：模型的類型，pl.LpMinimize是求目標(biāo)函數(shù)的最小值，pl.LpMaximize 是求最大值

3.2 定義決策變量

# Define the decision variables
x = pl.LpVariable(name='x')
y = pl.LpVariable(name='y')

如果你的變量比較少的話可以簡(jiǎn)單這么寫(xiě)。這個(gè)意思是定義了兩個(gè)浮點(diǎn)數(shù)變量，取值范圍是整個(gè)實(shí)數(shù)域。注意等號(hào)左邊的變量才是你在之后的計(jì)算式中使用的符號(hào)，而參數(shù) name 只有在最后打印結(jié)果的時(shí)候才會(huì)被打印出來(lái)。另外如果你對(duì)變量有其他要求的話可以添加以下參數(shù)：

• lowBound：變量的最小取值（不寫(xiě)的話默認(rèn)負(fù)無(wú)窮）；
• upBound：變量的最大取值（默認(rèn)正無(wú)窮）；
• cat：變量的類型，有 pl.Binary 邏輯變量、pl.Integer 整數(shù)、pl.Continuous 實(shí)數(shù)（默認(rèn)值）；

如果你的變量比較多而不得不用 1, 2, 3…… 來(lái)編號(hào)，可以采用類似這樣的寫(xiě)法：

# Define the decision variables
x = {i: pl.LpVariable(name=f"x{i}", lowBound=0, cat=pl.LpInteger) for i in range(1, 9)}

這是一次定義 8 個(gè)變量并保存在一個(gè)類似數(shù)組的結(jié)構(gòu)中，變量都是正整數(shù)，分別用 x[1],x[2], ..., x[8] 表示，依次命名為 x1, x2,..., x8。

注意 range(left, right) 表示的區(qū)間是左閉右開(kāi)。

3.3 添加約束條件

# Add constraints
model += (2 * x + 3 * y - 6 >= 0, "constrain_1")
model += (x + 3 * y - 3 == 0, "constrain_2")

沒(méi)錯(cuò)！如你所見(jiàn)就是這么簡(jiǎn)單，括號(hào)里第一個(gè)變量就是你的約束不等式或等式，第二個(gè)變量是你的自定義的約束名（可以起一個(gè)有意義的名字，當(dāng)然也可以省略）。

由于一些比較數(shù)學(xué)的原因，約束條件里是不能使用大于號(hào)“>”或小于號(hào)“<”的。

如果你像前面一樣把變量定義在了數(shù)組中，那么可以直接用方括號(hào)調(diào)用：

model += (2 * x[1] + 3 * x[2] - 6 >= 0)

3.4 添加目標(biāo)函數(shù)

# Set the objective
model += x + 3 * y

與前面添加約束條件不同，添加目標(biāo)函數(shù)這一步不用加最外層的括號(hào)。

3.5 模型求解

# Solve the optimization problem
status = model.solve()

就寫(xiě)這一句話，調(diào)用 model 的 solve() 方法，并把結(jié)果保存在 status 中。

3.6 打印結(jié)果

# Get the results
print(f"status: {model.status}, {pl.LpStatus[model.status]}")
print(f"objective: {model.objective.value()}")

for var in model.variables():
    print(f"{var.name}: {var.value()}")

for name, constraint in model.constraints.items():
    print(f"{name}: {constraint.value()}")

然后你就能看到模型求解的結(jié)果了。

4.示例代碼

4.1 高考題代碼

首先解決一下 3.1 的高考題：

import pulp as pl

# 定義一個(gè)模型，命名為 "Model_3.1"，求最大值
model = pl.LpProblem(name="Model_3.1", sense=pl.LpMaximize)

# 定義兩個(gè)決策變量，取值為整個(gè)實(shí)數(shù)域
x = pl.LpVariable(name='x')
y = pl.LpVariable(name='y')

# 添加三個(gè)約束條件
model += (2 * x + 3 * y - 6 >= 0)
model += (x + y - 3 <= 0)
model += (y - 2 <= 0)

# 目標(biāo)函數(shù)
model += x + 3 * y

# 求解
status = model.solve()

# 打印結(jié)果
print(f"status: {model.status}, {pl.LpStatus[model.status]}")
print(f"objective: {model.objective.value()}")

for var in model.variables():
    print(f"{var.name}: {var.value()}")

for name, constraint in model.constraints.items():
    print(f"{name}: {constraint.value()}")

查看結(jié)果的最后幾行：

status: 1, Optimal
objective: 7.0
x: 1.0
y: 2.0
_C1: 2.0
_C2: 0.0
_C3: 0.0

最大值是7.0，在x=1.0,y=2.0 時(shí)取到。

4.2 汽車廠代碼

import pulp as pl

# 定義一個(gè)模型，命名為 "Model_3.2"，求最大值
model = pl.LpProblem(name="Model_3.2", sense=pl.LpMaximize)

# 定義三個(gè)決策變量，取值正整數(shù)
x = {i: pl.LpVariable(name=f"x{i}", lowBound=0, cat=pl.LpInteger) for i in range(1, 4)}

# 添加約束條件
model += (1.5 * x[1] + 3 * x[2] + 5 * x[3] <= 600)
model += (280 * x[1] + 250 * x[2] + 400 * x[3] <= 60000)

# 目標(biāo)函數(shù)
model += 2 * x[1] + 3 * x[2] + 4 * x[3]

# 求解
status = model.solve()

# 打印結(jié)果
print(f"status: {model.status}, {pl.LpStatus[model.status]}")
print(f"objective: {model.objective.value()}")

for var in model.variables():
    print(f"{var.name}: {var.value()}")

for name, constraint in model.constraints.items():
    print(f"{name}: {constraint.value()}")

查看結(jié)果的最后幾行：

status: 1, Optimal
objective: 632.0
x1: 64.0
x2: 168.0
x3: 0.0
_C1: 0.0
_C2: -80.0

三種車的產(chǎn)量分別取 64、168、0，最大收益 632 萬(wàn)元。

到此這篇關(guān)于Python+PuLP實(shí)現(xiàn)線性規(guī)劃的求解的文章就介紹到這了,更多相關(guān)Python PuLP線性規(guī)劃內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論