欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

淺談Python數(shù)學(xué)建模之線性規(guī)劃

 更新時(shí)間:2021年06月22日 17:19:23   作者:youcans  
線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支,它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法。研究線性約束條件下線性目標(biāo)函數(shù)的極值問題的數(shù)學(xué)理論和方法

一、求解方法、算法和編程方案

線性規(guī)劃 (Linear Programming,LP) 是很多數(shù)模培訓(xùn)講的第一個(gè)算法,算法很簡單,思想很深刻。

線性規(guī)劃問題是中學(xué)數(shù)學(xué)的內(nèi)容,雞兔同籠就是一個(gè)線性規(guī)劃問題。數(shù)學(xué)規(guī)劃的題目在高考中也經(jīng)常出現(xiàn),有直接給出線性約束條件求線性目標(biāo)函數(shù)極值,有間接給出約束條件求線性目標(biāo)函數(shù)極值,還有已知約束條件求非線性目標(biāo)函數(shù)極值問題。

因此,線性規(guī)劃在數(shù)學(xué)建模各類問題和算法中確實(shí)是比較簡單的問題。下面我們通過這個(gè)比較簡單、也比較熟悉的問題,分析一下數(shù)學(xué)模型問題的方法、算法和學(xué)習(xí)方案。探討這些容易混淆的概念,也便于大家理解本系列教程的初衷和特色。

1.1、線性規(guī)劃問題的求解方法

解決線性規(guī)劃問題有很多數(shù)學(xué)方法,例如:

  • 圖解法, 用幾何作圖的方法并求出其最優(yōu)解,中學(xué)就講過這種方法,在經(jīng)濟(jì)學(xué)研究中十分常用;
  • 矩陣法, 引進(jìn)松弛變量將線性規(guī)劃問題轉(zhuǎn)換成增廣矩陣形式后逐次求解, 是單純性法之前的典型方法;
  • 單純性法, 利用多面體在可行域內(nèi)逐步構(gòu)造新的頂點(diǎn)來不斷逼近最優(yōu)解,是線性規(guī)劃研究的里程碑,至今仍然是最重要的方法之一;
  • 內(nèi)點(diǎn)法,通過選取可行域內(nèi)部點(diǎn)沿下降方向不斷迭代來達(dá)到最優(yōu)解,是目前理論上最好的線性規(guī)劃問題求解方法;
  • 啟發(fā)式方法,依靠經(jīng)驗(yàn)準(zhǔn)則不斷迭代改進(jìn)來搜索最優(yōu)解 ,如貪心法、模擬退火、遺傳算法、神經(jīng)網(wǎng)絡(luò)。

雖然不同的求解方法都是面對(duì)線性規(guī)劃問題,也就必然會(huì)殊途同歸,但它們?cè)谒枷肷暇痛嬖谥举|(zhì)區(qū)別,在求解方法和步驟上也就完全不同。

不夸張地說,對(duì)于很多小白,學(xué)沒學(xué)過單純性法,對(duì)于學(xué)習(xí)啟發(fā)式方法可能完全沒有區(qū)別。

這意味著什么呢?這就是說,對(duì)于非數(shù)學(xué)專業(yè)的同學(xué),對(duì)于學(xué)習(xí)數(shù)學(xué)建模的同學(xué),針對(duì)每一類問題,完全沒必要學(xué)習(xí)各種解決方法。即便是數(shù)學(xué)專業(yè)的同學(xué),也不可能在數(shù)模學(xué)習(xí)期間把各種方法都學(xué)會(huì)。

對(duì)于小白,本文推薦選擇較為通用、相對(duì)簡單(思路簡單、程序簡單)的方法來進(jìn)行學(xué)習(xí),沒必要貪多求新。

1.2、線性規(guī)劃的最快算法

算法,跟方法有什么不同呢?

算法的定義是“解題方案的準(zhǔn)確而完整的描述”,是一系列解決問題的清晰指令,算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。

我對(duì)“方法”的理解是思想方法,是求解問題總體框架,而“算法”是具體和明確的實(shí)現(xiàn)步驟,在計(jì)算機(jī)編程中相當(dāng)于詳細(xì)的流程圖。

在每一種方法的基本思想和方案提出后,往往都會(huì)有很多變形、改進(jìn)和發(fā)展的算法。極少的改進(jìn)算法具有實(shí)質(zhì)貢獻(xiàn)而成為主流的經(jīng)典算法,即便如此往往也只是性能、效率上的提升,對(duì)于求解數(shù)模競賽中的問題基本沒有影響。

而絕大多數(shù)改進(jìn)算法只是針對(duì)某些特殊情況、特殊問題(自稱)有效,常用于大量的灌水論文。對(duì)于數(shù)學(xué)建模來說,學(xué)習(xí)基本算法或者目前的經(jīng)典算法就足夠了,不需要聽信改進(jìn)算法中自稱的優(yōu)點(diǎn),那都是莆田系的廣告。

有一種例外情況,就是一些算法是有適用范圍和限制條件的。舉個(gè)例子,內(nèi)點(diǎn)法的基本算法不能處理等式約束,最短路徑問題中 Dijkstar算法不能處理負(fù)權(quán)邊。這種情況下如果選錯(cuò)算法,問題是無法求解的。所以對(duì)我們來說,搞清楚算法的適用范圍,比理解算法本身更重要。

回到本節(jié)的標(biāo)題,對(duì)于線性規(guī)劃問題,什么算法是最快的呢?答案是:猜。不是讓你猜,而是說求解線性規(guī)劃問題,猜起來比較快。不是開玩笑,我是認(rèn)真的。

佐治亞理工學(xué)院彭泱教授在 2021年計(jì)算機(jī)理論頂會(huì) SODA2021 獲得最佳論文(Best paper award at ACM-SIAM symposium on discrete algorithms 2021),正是研究線性規(guī)劃問題的求解——“Solving sparse linear systems faster than matrix multiplication”,所用的全新思路是:猜,反復(fù)猜,迭代猜。

當(dāng)然,猜起來比較快只是在某些特殊條件下才有效的,至于在什么條件下猜,怎么猜,這不是我們所要關(guān)心,所能理解的問題了。只是以此說明,簡單的問題也有復(fù)雜的情況,每個(gè)問題都有很多求解的思路、方法和算法。

1.3、選擇適合自己的編程方案

編程方案是我杜撰的術(shù)語。我所要表達(dá)意思是,在選擇了求解方法和算法以后,是自己按照算法步驟一步步編程實(shí)現(xiàn),或者找到例程調(diào)試使用,還是調(diào)用第三方工具包/庫函數(shù)來完成呢?

首先,對(duì)于學(xué)習(xí)數(shù)學(xué)建模、參加數(shù)模競賽,不建議自己按照算法步驟去編程。我們?cè)凇?1.新手必讀》中討論過這個(gè)問題,對(duì)于數(shù)學(xué)小白兼計(jì)算機(jī)小白,這樣做既不可行也沒必要;即使你愿意挑戰(zhàn)自我去試試,那其實(shí)已經(jīng)是走在學(xué)習(xí)另一門計(jì)算機(jī)或算法課程的路上了。

其次,要不要找到例程自己調(diào)試、使用?很多數(shù)模培訓(xùn)就是這么說,這么做的,而且把這些收集的例程當(dāng)作核心機(jī)密吸引同學(xué)。我不反對(duì)這樣做,這種學(xué)習(xí)方法對(duì)于理解算法、提高編程能力很有幫助;但是并不推薦這樣做,原因是:

(1)我認(rèn)為學(xué)習(xí)數(shù)學(xué)建模、參加數(shù)模競賽,重點(diǎn)應(yīng)該放在識(shí)別問題、分析問題、解決問題,能使用算法和編程就足夠了;

(2)第三方庫與例程沒有本質(zhì)區(qū)別,第三方庫就是經(jīng)典的、規(guī)范的、標(biāo)準(zhǔn)化的例程,既然選擇例程為什么不選擇優(yōu)秀的例程——第三方庫呢?

(3)大部分例程都存在很多問題,即使調(diào)試通過仍然有很多坑,而且新手難以識(shí)別。

所以我是明確推薦優(yōu)選直接使用第三方庫來解決問題,這也是 Python 語言“不要重復(fù)造輪子”的思想。

進(jìn)一步地,很多工具包/庫函數(shù)都能實(shí)現(xiàn)常用的算法,應(yīng)該如何選擇呢?

如果你對(duì)某個(gè)工具包已經(jīng)很熟悉,又能實(shí)現(xiàn)所要的算法,這當(dāng)然是理想的選擇。如果你是小白,就跟著我走吧。

本系列選擇第三方工具包的原則是:

(1)優(yōu)選常用的工具包;

(2)優(yōu)選通用功能的工具包和函數(shù)(例如,最好既能實(shí)現(xiàn)線性規(guī)劃,又能實(shí)現(xiàn)整數(shù)規(guī)劃、非線性規(guī)劃);

(3)優(yōu)選安裝簡單、使用簡單、配置靈活的工具包;

(4)優(yōu)選兼模型檢驗(yàn)、圖形繪制的工具包。

二、PuLP庫求解線性規(guī)劃問題

2.1、線性規(guī)劃問題的描述

線性規(guī)劃是研究線性等式或不等式約束條件下求解線性目標(biāo)函數(shù)的極值問題,常用于解決資源分配、生產(chǎn)調(diào)度和混合問題。

一般線性規(guī)劃問題的標(biāo)準(zhǔn)形式為:

滿足所有約束條件的解,稱為線性規(guī)劃問題的可行解;所有可行解構(gòu)成的集合,稱為可行域。

使目標(biāo)函數(shù)達(dá)到最小值的解,稱為最優(yōu)解。

線性規(guī)劃問題的建模和求解,通常按照以下步驟進(jìn)行:

  • 問題定義,確定決策變量、目標(biāo)函數(shù)和約束條件;
  • 模型構(gòu)建,由問題描述建立數(shù)學(xué)方程,并轉(zhuǎn)化為標(biāo)準(zhǔn)形式的數(shù)學(xué)模型;
  • 模型求解,用標(biāo)準(zhǔn)模型的優(yōu)化算法對(duì)模型求解,得到優(yōu)化結(jié)果。

很多 Python 的第三方包,都提供求解線性規(guī)劃問題的算法,有的工具包還提供整數(shù)規(guī)劃、非線性規(guī)劃的算法。例如:

  • Scipy 庫提供了解簡單線性或非線性規(guī)劃問題,但是不能求解如背包問題的0-1規(guī)劃問題,或整數(shù)規(guī)劃問題,混合整數(shù)規(guī)劃問題。
  • PuLP 可以求解線性規(guī)劃、整數(shù)規(guī)劃、0-1規(guī)劃、混合整數(shù)規(guī)劃問題,提供多種針對(duì)不同類型問題的求解器。
  • Cvxpy 是一種凸優(yōu)化工具包,可以求解線性規(guī)劃、整數(shù)規(guī)劃、0-1規(guī)劃、混合整數(shù)規(guī)劃、二次規(guī)劃和幾何規(guī)劃問題。

此外,SKlearn、DOcplex、Pymprog 等很多第三方工具包也都能求解線性規(guī)劃問題。

2.2、PuLP 求解線性規(guī)劃問題的步驟

例題 1:

下面以該題為例講解 PuLP 求解線性規(guī)劃問題的步驟:

(0)導(dǎo)入 PuLP庫函數(shù)

import pulp

(1)定義一個(gè)規(guī)劃問題

MyProbLP = pulp.LpProblem("LPProbDemo1", sense=pulp.LpMaximize)

pulp.LpProblem 是定義問題的構(gòu)造函數(shù)。

"LPProbDemo1"是用戶定義的問題名(用于輸出信息)。

參數(shù) sense 用來指定求最小值/最大值問題,可選參數(shù)值:LpMinimize、LpMaximize 。本例 “sense=pulp.LpMaximize” 表示求目標(biāo)函數(shù)的最大值。

(2)定義決策變量

x1 = pulp.LpVariable('x1', lowBound=0, upBound=7, cat='Continuous') 
x2 = pulp.LpVariable('x2', lowBound=0, upBound=7, cat='Continuous')
x3 = pulp.LpVariable('x3', lowBound=0, upBound=7, cat='Continuous') 

pulp.LpVariable 是定義決策變量的函數(shù)。
'x1' 是用戶定義的變量名。

參數(shù) lowBound、upBound 用來設(shè)定決策變量的下界、上界;可以不定義下界/上界,默認(rèn)的下界/上界是負(fù)無窮/正無窮。本例中 x1,x2,x3 的取值區(qū)間為 [0,7]。

參數(shù) cat 用來設(shè)定變量類型,可選參數(shù)值:'Continuous' 表示連續(xù)變量(默認(rèn)值)、' Integer ' 表示離散變量(用于整數(shù)規(guī)劃問題)、' Binary ' 表示0/1變量(用于0/1規(guī)劃問題)。

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

MyProbLP += 2*x1 + 3*x2 - 5*x3  	# 設(shè)置目標(biāo)函數(shù)

添加目標(biāo)函數(shù)使用 "問題名 += 目標(biāo)函數(shù)式" 格式。

(4)添加約束條件

MyProbLP += (2*x1 - 5*x2 + x3 >= 10)  # 不等式約束
MyProbLP += (x1 + 3*x2 + x3 <= 12)  # 不等式約束
MyProbLP += (x1 + x2 + x3 == 7)  # 等式約束

添加約束條件使用 "問題名 += 約束條件表達(dá)式" 格式。

約束條件可以是等式約束或不等式約束,不等式約束可以是 小于等于 或 大于等于,分別使用關(guān)鍵字">="、"<="和"=="。

(5)求解

MyProbLP.solve()
print("Status:", pulp.LpStatus[MyProbLP.status]) # 輸出求解狀態(tài)
for v in MyProbLP.variables():
    print(v.name, "=", v.varValue)  # 輸出每個(gè)變量的最優(yōu)值
print("F(x) = ", pulp.value(MyProbLP.objective))  #輸出最優(yōu)解的目標(biāo)函數(shù)值   

solve() 是求解函數(shù)。PuLP默認(rèn)采用 CBC 求解器來求解優(yōu)化問題,也可以調(diào)用其它的優(yōu)化器來求解,如:GLPK,COIN CLP/CBC,CPLEX,和GUROBI,但需要另外安裝?!?/p>

2.3、Python例程:線性規(guī)劃問題

例程 1:求解線性規(guī)劃問題

import pulp
MyProbLP = pulp.LpProblem("LPProbDemo1", sense=pulp.LpMaximize)  # 求最大值
x1 = pulp.LpVariable('x1', lowBound=0, upBound=7, cat='Continuous') 
x2 = pulp.LpVariable('x2', lowBound=0, upBound=7, cat='Continuous') 
x3 = pulp.LpVariable('x3', lowBound=0, upBound=7, cat='Continuous') 
MyProbLP += 2*x1 + 3*x2 - 5*x3  	# 設(shè)置目標(biāo)函數(shù)
MyProbLP += (2*x1 - 5*x2 + x3 >= 10)  # 不等式約束
MyProbLP += (x1 + 3*x2 + x3 <= 12)  # 不等式約束
MyProbLP += (x1 + x2 + x3 == 7)  # 等式約束
MyProbLP.solve()  # youcans@xupt
print("Status:", pulp.LpStatus[MyProbLP.status]) # 輸出求解狀態(tài)
for v in MyProbLP.variables():  # youcans
    print(v.name, "=", v.varValue)  # 輸出每個(gè)變量的最優(yōu)值
print("Max F(x) = ", pulp.value(MyProbLP.objective))  #輸出最優(yōu)解的目標(biāo)函數(shù)值

例程 1 運(yùn)行結(jié)果:

Welcome to the CBC MILP Solver 

Version: 2.9.0 

Build Date: Feb 12 2015 

Status: Optimal

x1 = 6.4285714

x2 = 0.57142857

x3 = 0.0

Max F(x) =  14.57142851

例程01 程序說明:

  • 用 PuLP 庫求解線性規(guī)劃問題,可以選擇求最大值或最小值,可以按照問題的數(shù)學(xué)描述,直接輸入目標(biāo)函數(shù)、等式約束和不等式約束,不等式約束可以選擇 <= 或 >=,不需要進(jìn)行轉(zhuǎn)換。這中方式簡單直觀,非常適合初學(xué)者掌握。
  • 對(duì)于較大規(guī)模線性規(guī)劃問題, PuLP 庫支持用字典類型(dict)建立多個(gè)變量,設(shè)置目標(biāo)函數(shù)和約束條件。

三、小結(jié)

求解線性規(guī)劃問題的方法非常簡單,本文實(shí)際上并未講解具體的算法。

希望通過對(duì)求解方法、算法和編程方案的講解,闡明作者對(duì)于數(shù)學(xué)建模學(xué)什么、怎么學(xué)的理解,也使讀者能了解本系列教程的特點(diǎn):本教程不打算詳細(xì)講解各種算法的具體方法,重點(diǎn)介紹如何使用第三方包實(shí)現(xiàn)算法、解決問題。

以上就是淺談Python數(shù)學(xué)建模之線性規(guī)劃的詳細(xì)內(nèi)容,更多關(guān)于Python 線性規(guī)劃的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • 利用python計(jì)算均值、方差和標(biāo)準(zhǔn)差(Numpy和Pandas)

    利用python計(jì)算均值、方差和標(biāo)準(zhǔn)差(Numpy和Pandas)

    這篇文章主要給大家介紹了關(guān)于利用python計(jì)算均值、方差和標(biāo)準(zhǔn)差的相關(guān)資料,Numpy在Python中是一個(gè)通用的數(shù)組處理包,它提供了一個(gè)高性能的多維數(shù)組對(duì)象和用于處理這些數(shù)組的工具,它是使用Python進(jìn)行科學(xué)計(jì)算的基礎(chǔ)包,需要的朋友可以參考下
    2023-11-11
  • 模型訓(xùn)練時(shí)GPU利用率太低的原因及解決

    模型訓(xùn)練時(shí)GPU利用率太低的原因及解決

    這篇文章主要介紹了模型訓(xùn)練時(shí)GPU利用率太低的原因及解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-02-02
  • Python實(shí)現(xiàn)在不同坐標(biāo)系中繪制曲線

    Python實(shí)現(xiàn)在不同坐標(biāo)系中繪制曲線

    這篇文章主要為大家學(xué)習(xí)介紹了Python如何實(shí)現(xiàn)在不同坐標(biāo)系中繪制曲線,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起了解一下
    2023-07-07
  • Python入門(六)Python數(shù)據(jù)類型

    Python入門(六)Python數(shù)據(jù)類型

    這篇文章主要介紹了Python入門(六)Python數(shù)據(jù)類型,Python是一門非常強(qiáng)大好用的語言,也有著易上手的特性,本文為入門教程,需要的朋友可以參考下
    2023-04-04
  • Python 通過xpath屬性爬取豆瓣熱映的電影信息

    Python 通過xpath屬性爬取豆瓣熱映的電影信息

    我喜歡看電影,可以說大部分熱門電影我都看過。處理愛好的目的,我看了看豆瓣熱映的電影列表。于是我寫了這個(gè)爬蟲把豆瓣熱映的電影都爬了下來。對(duì)頁面的處理主要是需要點(diǎn)擊顯示全部電影,然后爬取影片屬性,最后輸出文本。采用的還是scrapy框架。順便聊聊我的實(shí)現(xiàn)過程吧
    2021-11-11
  • 利用python獲取當(dāng)前日期前后N天或N月日期的方法示例

    利用python獲取當(dāng)前日期前后N天或N月日期的方法示例

    最近在工作中遇到一個(gè)需求,查找資料發(fā)現(xiàn)了一個(gè)很好的時(shí)間組件,所以下面這篇文章主要給大家介紹了關(guān)于利用python獲取當(dāng)前日期前后N天或N月日期的方法示例,需要的朋友們可以參考借鑒,下面來一起看看吧。
    2017-07-07
  • python使用paramiko實(shí)現(xiàn)遠(yuǎn)程拷貝文件的方法

    python使用paramiko實(shí)現(xiàn)遠(yuǎn)程拷貝文件的方法

    這篇文章主要介紹了python使用paramiko實(shí)現(xiàn)遠(yuǎn)程拷貝文件的方法,分析了paramiko庫的安裝以及遠(yuǎn)程下載文件的實(shí)現(xiàn)技巧,需要的朋友可以參考下
    2016-04-04
  • 教你用python編寫腳本實(shí)現(xiàn)自動(dòng)簽到

    教你用python編寫腳本實(shí)現(xiàn)自動(dòng)簽到

    這篇文章主要介紹了教你怎樣用python編寫腳本實(shí)現(xiàn)自動(dòng)簽到,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-08-08
  • 淺析Python函數(shù)式編程

    淺析Python函數(shù)式編程

    在本篇文章中我們給大家分享了關(guān)于Python函數(shù)式編程的相關(guān)知識(shí)點(diǎn)內(nèi)容,有興趣的朋友參考下。
    2018-10-10
  • python讀寫json文件的簡單實(shí)現(xiàn)

    python讀寫json文件的簡單實(shí)現(xiàn)

    這篇文章主要介紹了python讀寫json文件的簡單實(shí)現(xiàn),實(shí)例分析了各種讀寫json的方法和技巧,有興趣的可以了解一下
    2017-04-04

最新評(píng)論