在上一期的學習中，我們對目標規(guī)劃的相關概念和模型進行了講解，本期我們進行運籌學之目標規(guī)劃算法的講解。我們將對目標規(guī)劃的基礎知識進行一個簡單的回顧，并介紹求解目標規(guī)劃的Excel方法、LINGO、MATLAB以及Python相關代碼，以幫助大家利用工具快速求解目標規(guī)劃問題，做到事半功倍。話不多說，我們一起來看看吧！

??

一、基礎知識

1、目標規(guī)劃問題的數(shù)學模型

★線性規(guī)劃與目標規(guī)劃的異同

?

★目標規(guī)劃數(shù)學模型的一般形式

?

模型中，gk為第k個目標約束的預期目標值，W_lk^-和W_lk^+為Pl優(yōu)先因子對應各目標的權系數(shù)。

2、目標規(guī)劃問題的求解

★目標規(guī)劃問題的建模步驟

（1）根據(jù)要研究的問題所提出的各目標與條件，列出絕對約束；

（2）可根據(jù)決策者的需要,將某些或全部絕對約束轉(zhuǎn)化為目標約束。這時只需要給絕對約束加上負偏差變量和減去正偏差變量即可；

（3）給各目標賦予相應的優(yōu)先因子Pk (k=1，2…，K)；

（4）對同一優(yōu)先等級中的各偏差變量,若需要可按其重要程度的不同賦予相應的權系數(shù)；

（5）根據(jù)決策者的要求，構造一個由優(yōu)先因子和權系數(shù)相對應的偏差變量組成的要求實現(xiàn)極小化的目標函數(shù)。

★目標規(guī)劃問題的求解方法

（1）單純形法

目標規(guī)劃的數(shù)學模型實際上是最小化型的線性規(guī)劃，可以用單純形法求解。

在用單純形法解目標規(guī)劃時，檢驗數(shù)是各優(yōu)先因子的線性組合。因此，在判別各檢驗數(shù)的正負及大小時，必須注意P1?P2?P3?…。當所有檢驗數(shù)都已滿足最優(yōu)性條件（cj-zj≥0）時，從最終單純形表上就可以得到目標規(guī)劃的解。具體流程圖如下所示。后續(xù)算法實現(xiàn)部分用Excel方法以及Python平臺求解目標規(guī)劃問題采用的就是此方法。

?

（2）序貫式解法

序貫式解法是按照目標函數(shù)中各目標的優(yōu)先級別，順序?qū)⒛繕艘?guī)劃分解為一系列單目標的線性規(guī)劃，用單純形法逐一求解。在求解過程中確定出基變量、進基變量以及迭代的原則與線性規(guī)劃的單純形法相同。不同的是要以不影響較高級目標的最優(yōu)值為前提求解較低級目標的最優(yōu)值。如此反復進行迭代，直到最低級目標的目標函數(shù)達到最優(yōu)為止。后續(xù)算法實現(xiàn)部分用LINGO求解目標規(guī)劃問題采用的就是此方法。

?

二、算法實現(xiàn)

1、例題介紹?

某工廠生產(chǎn)兩種產(chǎn)品，受到原材料和設備工時的限制。單件利潤等有關數(shù)據(jù)已知，具體數(shù)據(jù)如下表：

?

計劃人員被要求考慮如下的意見：

（1）由于產(chǎn)品Ⅱ銷售疲軟，故希望產(chǎn)品Ⅱ的產(chǎn)量不超過產(chǎn)品Ⅰ的一半；

（2）原材料嚴重短缺，生產(chǎn)過程中應避免過量消耗；

（3）最好能節(jié)約4h設備工時；

（4）計劃利潤不少于48元。

面對這些意見，計劃人員需要會同有關各方做進一步的協(xié)調(diào)，最后達成了一致意見：原材料使用限額不得突破；產(chǎn)品Ⅱ產(chǎn)量要求必須優(yōu)先考慮；設備工時問題其次考慮，最后考慮計劃利潤的要求。

上述例題的數(shù)學模型如下：

?

2、平臺實現(xiàn)

此次我們以上述例題為例，借助Excel、LINGO及MATLAB、Python這4個平臺分別介紹實現(xiàn)求解目標規(guī)劃的相關代碼。由于篇幅有限，小編接下來只展示部分代碼，小伙伴們可以關注“運籌學”公眾號→后臺回復“目標規(guī)劃之LINGO”及“目標規(guī)劃之MATLAB”、“目標規(guī)劃之Python”分別獲取對應的完整代碼。

（1）Excel

★準備工作

依次在相應的單元格內(nèi)輸入數(shù)據(jù)和公式如下，優(yōu)先因子間的關系可以自行定義，這里我們令P1=100，P2=50，P3=1，表示P1?P2?P3。

?

★求解流程

設置規(guī)劃求解參數(shù)如圖所示，本題我們求解目標函數(shù)的最小值，設定好相應的約束條件，在“使無約束變量為非負數(shù)”前的方框里打?qū)︺^，選擇求解方法處選擇“單純線性規(guī)劃”，點擊求解即可返回運算結果。

?

點擊“求解”后，出現(xiàn)“規(guī)劃求解結果”對話框，我們可以看到，規(guī)劃求解找到一解，在報告位置還可以選擇生成運算結果報告。

?

★運行結果

可以看到，x1=4.8，x2=2.4，d1+=0，d1-=0，d2+=0，d2-=7.2，d3+=0，d3-=0，因此，可獲得在上述約束條件下的滿意解，并求得最優(yōu)利潤為48元。

??

?

（2）LINGO

★平臺介紹

LINGO可以用于求解非線性規(guī)劃，也可以用于一些線性和非線性方程組的求解等，功能十分強大，是求解優(yōu)化模型的最佳選擇。其特色在于內(nèi)置建模語言，提供十幾個內(nèi)部函數(shù)，可以允許決策變量是整數(shù)（即整數(shù)規(guī)劃，包括0-1整數(shù)規(guī)劃），方便靈活，而且執(zhí)行速度非?？?，能方便與Excel、數(shù)據(jù)庫等其他軟件交換數(shù)據(jù)。

??

★代碼展示

??

?

小伙伴們可以關注“運籌學”公眾號→后臺回復“目標規(guī)劃之LINGO”獲取完整代碼。

★代碼調(diào)用及運行結果

當程序運行時，會出現(xiàn)一個對話框，由于該目標規(guī)劃共有3個優(yōu)先因子P1、P2、P3，因此我們需要做三次運算。

在做第一級目標計算時，ctr輸入1，goal(1)和goal(2)輸入兩個較大的值，表明這兩項約束不起作用。求得第一級的最優(yōu)偏差為0，進行第二級目標計算；

在第二級目標的運算中，ctr輸入2。由于第一級的偏差為0，因此goal(1)的輸入值為0，goal(2)輸入一個較大的值。求得第二級的最優(yōu)偏差仍為0，進行第三級計算；

在第三級的計算中，ctr輸入3。由于第一級、第二級的偏差均是0，因此，goal(1)和goal(2)的輸入值也均是0，第三級的最優(yōu)偏差為0。

最終運行結果展示如下：

?

分析計算結果，x1=8，x2=0，d1+=8，d1-=0，d2+=0，d2-=4，d3+=0，d3-=0，因此，可獲得在上述約束條件下的滿意解為生產(chǎn)產(chǎn)品Ⅰ 8 件，不生產(chǎn)產(chǎn)品Ⅱ，最優(yōu)利潤48元。

（2）MATLAB

MATLAB平臺有多種求解目標規(guī)劃問題的方法，現(xiàn)在介紹兩種：fgoalattain函數(shù)和gamultiobj。

（2.1）fgoalattain

★函數(shù)介紹

fgoalattain函數(shù)常用來求解多個決策函數(shù)的規(guī)劃問題。

語法為：[x,fval] = fgoalattain(fun, x0, goal, A, b, Aeq, beq, lb, ub)。?

其中，x為最終解，fval為最終的目標函數(shù)值。fun 是定義的決策函數(shù)，通常通過M文件或者匿名函數(shù)進行定義；x0 為初始值；goal 為欲達到的目標；weight為權重；A和b用于定義不等式約束A*x ≤ b；Aeq和beq用于定義等式約束Aeq*x=beq；lb和ub表示解的范圍。? ??

★代碼展示

★運行結果

運行之后，得出如下結果，即當x1=6，x2=3時，求得在權重weight=[10,2,1]情況下目標規(guī)劃的滿意解，即生產(chǎn)產(chǎn)品I 6件，產(chǎn)品Ⅱ3件，最優(yōu)利潤為60元。

?

（2.2）gamultiobj

★函數(shù)介紹

gamultiobj是Optimization Toolbox中使用遺傳算法來解多目標問題的一個函數(shù)，其使用方法同fgoalattain類似。與fgoalattain不同的是，gamultiobj直接返回多個滿足條件的解，如何選擇看決策者實際要求。

本文中用到的語法為：[x,fval] = gamultiobj (fun, 2, goal, A, b, Aeq, beq, lb, ub)。

其中，x為最終解，fval為最終的目標函數(shù)值。fun 是定義的決策函數(shù)，通常通過M文件或者匿名函數(shù)進行定義；goal 為欲達到的目標；A和b用于定義不等式約束A*x ≤ b；Aeq和beq用于定義等式約束Aeq*x=beq；lb和ub表示解的范圍。

★代碼展示

?

★運行結果

運行之后，得到如下結果，其中x的每一行都代表了一組滿意解，fx中第三列的相反數(shù)代表的就是相應的滿意解所對應的目標函數(shù)值。

??

?

（4）Python

通過查閱相關資料，小編發(fā)現(xiàn)目前使用Python算法求解目標規(guī)劃問題的資料甚少，因此，為進一步鍛煉小編的編程能力同時也為方便大家對于運籌學算法相關知識的學習，小編根據(jù)單純形法求解原理，自行編寫了求解目標規(guī)劃問題的Goal programming文件。

★準備工作

在運行代碼之前，我們首先要將初始單純形表寫入“模型輸入表”中，書寫格式如下圖所示。為方便代碼運行，單純形表中的所有信息均采用數(shù)字表示，各個變量均有相應的數(shù)字代號。此外，表格中A1:C1為無用單元格，為保證代碼正常運行，將其賦值為0.1。同時我們令P1=100，P2=50，P3=1，表示P1?P2?P3。

?

?

★代碼展示

Goal programming文件包含從“模型輸入表”中讀取數(shù)據(jù)、確定換入變量、確定換出變量、更新相關數(shù)據(jù)（包括單純形表中的約束系數(shù)矩陣、XB、CB以及b）、將更新后的單純形表寫入“結果輸出表”以及在Python界面輸出此時的檢驗數(shù)六大部分。部分代碼如下圖所示，小伙伴們可以關注“運籌學”公眾號→后臺回復“目標規(guī)劃之Python”獲取完整代碼。

? ??

★運行結果

首先我們需要將初始單純形表按照“準備工作”中提到的格式要求寫入“模型輸入表”中。

?

然后運行Goal programming文件，我們可以得到“結果輸出表”，該表記錄了新生成的單純形表，同時我們可以得知當前最小的檢驗數(shù)為-20。

?

?

由于我們目標函數(shù)求最小，因此不應存在檢驗數(shù)為負的情況，所以我們需要將“結果輸出表”中的數(shù)據(jù)復制到“模型輸入表”，再次運行Goal programming文件，發(fā)現(xiàn)運行完成后生成的單純形表最小的檢驗數(shù)為0。

?

此時我們便求得該目標規(guī)劃問題的一個滿意解，通過查看新生成的“結果輸出表”及“準備工作”中提到的變量和代號之間的關系，我們可以知道，此時的滿意解為：x1=4.8,x2=2.4。

?

3、算法總結?

線性規(guī)劃立足于求滿足所有約束條件的最優(yōu)解，而在實際問題中，可能存在相互矛盾的約束條件。這些相互矛盾的約束條件以及優(yōu)先因子的存在決定了目標規(guī)劃的找到的只能是滿意解。

上面我們給出了Excel、Lingo、MATLAB、Python求解目標規(guī)劃的四種方法，四種算法的優(yōu)缺點總結如下，小伙伴們可以根據(jù)實際需要自行選擇哦！

?

三、注意事項

運行MATLAB中的目標規(guī)劃函數(shù)fgoalattain時，由于fgoalattain解的是極小化問題，因此當?shù)趇個目標fun(i)為最大時，fun(i)和goal(i)的系數(shù)需變?yōu)樨摗?/p>

四、參考資料

【Excel實現(xiàn)】利用“規(guī)劃求解”求解目標規(guī)劃問題

https://wenku.baidu.com/view/a26c306c7e21af45b307a82a.html?qq-pf-to=pcqq.c2c?

【LINGO實現(xiàn)】利用序貫式算法求解目標規(guī)劃問題

https://blog.csdn.net/qq_29831163/article/details/89488932?

【MATLAB實現(xiàn)】利用目標規(guī)劃函數(shù)求解目標規(guī)劃問題

https://blog.csdn.net/m0_54690727/article/details/119730584?

本期的內(nèi)容就介紹到這里，想要進一步了解運籌學，關注本公眾號，快快學起來吧！

作者 |尹萌娟 曹貴玲??

責編 | 何洋洋

審核 | 徐小峰