用于線性規劃的診斷與決策可視化

韋東鑫

（四川大學計算機學院，成都610065）

0 引言

線性規劃是在各種約束條件下構建線性規劃模型并從中挑選出最合適的計算方法，進而求解出最佳結果。線性規劃目前被廣泛應用于現有數學計算方法中并能夠解決工作生活中的各種實際問題，但要想將現實問題抽象為線性規劃模型存在著諸多困難，例如，分析人員需要足夠的先驗知識才能很好地在各種約束條件下完成對現實問題的抽象，線性規模模型中的參數難以預先確定。此外，大規模復雜的線性規劃求解結果難以讓用戶進行分析且難以理解。

人眼的感知能力是目前已知的最強生物感知系統，人眼對圖片的識別能力要遠遠超出對數字與文字的識別?？梢暬萌搜鄣膹姼兄芰祿D換為可交互的可視化圖像，能夠增強數據識別效率，傳遞有效信息。將可視化運用于線性規劃，可在數據層面為復雜的線性規劃問題提供解釋與診斷，通過可視化技術，基于統計圖表的隱喻方法設計視圖并增加多種交互方法，能夠幫助理解復雜的決策變量與約束關系。

本文結合線性規劃與可視化兩種方法，圍繞如何在控制飼養成本的前提下保證寵物貓的營養攝入問題進行研究，設計并實現了多種可視化視圖，并利用視圖對線性規劃求解結果進行展示，幫助用戶快速理解線性規劃的優化結果，對決策變量的數據流向進行追蹤從而對約束的邏輯含義進行解釋，且可以輔助觀察者對約束進行調整。此外，本文使用的可視化視圖能夠幫助觀察者理解決策變量之間的數值關系和邏輯關系，采用探索式的方法進一步挖掘數據中的信息。

1 數據描述與線性規劃求解

1.1 數據獲取與處理

本文采集的所有數據可分為三類：①寵物貓的各類營養物質需求量；寵物貓所需的營養物質總體可概括為7 種：蛋白質、碳水化合物、鈣元素、脂肪、磷元素、維生素E 和鋅元素。②各類食材的出售價格；本文從在線生鮮平臺上采集了各類食材的出售價格，由于食材的種類繁多且價格不一，因此統一以銷量最高的食材所對應的價格為準。③各類食材所含的營養成分信息；本文從美國農業部公開的USDA 數據庫中獲取到了常見的各類食材中所含的上述7 種營養成分信息。在采集到足量的數據后，本文對數據集進行了臟值與錯值去除、數據結構化以及存儲等處理工作。

1.2 線性規劃求解

本文所研究的問題為如何在控制飼養成本的前提下保證寵物貓的營養提供，將這一實際問題抽象為線性規劃模型可得到如式（1）所示的數學模型，其中i，j分別對應不同食材的編號與不同營養物質的編號，xi，ci分別表示每種食材的數量以及寵物貓對該種食材的最低需求量，ni，N 分別表示第i 種食材所含的營養成分與寵物貓所需的營養最低值，pricei表示單種食材的價格。

由此可知該線性規劃模型實際上可視為最小成本函數，對上述實際問題的求解也就是對該最小成本函數求最優解。本文使用Python 語言下開放的IBM Cplex API 對線性規劃模型進行求解，在后續中將重點描述如何在不斷調整參數并求解時，使用可視化方法來對線性規劃求解結果進行展示，從而輔助得到最優解。

2 可視化模型構建與視圖設計

2.1 可視化模型描述

在現實生產生活中，線性規劃中的約束提取往往依賴于分析人員對問題的理解，也即約束式通常具有實際的現實含義。在設計線性規劃優化方案時，由于實際問題或約束引入了諸多不確定性，因此難以對約束邏輯和參數進行控制，要在這樣的條件下引入數學模型來解決管理優化問題變得異常困難。通過可視化的方法可以逐步探索、驗證與分析數據信息，且對模型理解具有重要意義。本文結合數據與實際問題，提出了如圖1 所示的可視化模型，并依據該模型使用多種方法對1.2 小節中的最小成本函數進行分析，解釋模型中各類約束與決策變量間的關聯關系并最終實現對函數的最優求解。

圖1 可視化模型

2.2 可視化任務抽象

為了更好地理解線性規劃問題中的約束與決策變量，本文結合可視化模型與寵物貓營養供給實際問題，對涉及到的可視化任務進行分類，提出了如表1 所示的可視化任務與對應的現實問題。針對不同類別的可視化任務設計并實現了多種可視化方法，使用可視化方法對求解后的線性規劃模型各類參數、約束條件進行展示，發現決策變量間的取值與關聯關系并呈現該決策變量對約束的貢獻，嘗試找出可相互替代的決策變量。

表1 可視化任務

2.3 可視化方法

本文設計了如圖2 所示的?；晥D，在視圖中不同的色塊表示不同的決策變量，以顏色區分決策變量的類別，色塊的寬度表示單個決策變量對目標函數的貢獻，色塊間的連接表示決策變量之間的層次關系。該視圖中的數據分組由用戶自行定義，可以按照食材所屬動物物種或食材所屬部位進行分類，允許用戶在不同的角度對線性規劃模型求解結果進行打包分析，且利用分組與層次關系減少認知負擔，發現不同分組間的比較關系。從視圖中可發現經過線性規劃求解后，第一次求解結果中只有雞心、蛋黃、肝臟、鯖魚和鵪鶉五種食材，其中雞肉類即紅色色塊最多。

圖2 用于線性規劃分析的?；鶊D

本文對嵌套餅圖與分組柱圖進行組合，得到如圖3所示的可視化視圖。該視圖中以面積表示單個決策變量對約束的貢獻，也即單個決策變量對約束的貢獻占比，此外，嵌套餅圖中的嵌套關系用于表示層次關系，不同層級的約束相互嵌套。因為嵌套餅圖的大小是固定的所以當模型求解結果超出約束條件越多則嵌套的圓越大。分組柱圖可以直觀地展示不同決策變量在滿足同一個約束上的貢獻差別，因兩個視圖采用了相同的顏色映射方式，所以用戶只需對顏色進行觀察追蹤便能夠在不同組之間進行同一變量在滿足不同約束時貢獻高低的比較。

從繪制的?；鶊D和嵌套餅圖-條形圖組中可以發現：雞對目標成本貢獻值最高。進一步從嵌套餅圖-條形圖組分析，很明顯看出貓攝入的脂肪含量遠遠超過脂肪的最低攝入量，這樣的營養配比明顯不太合理，應再進一步關注其他營養成分情況。

圖3 嵌套餅圖-分組柱圖

從圖4 中可以明顯發現：鈣元素、鋅元素、維生素E 和碳水化合物中的營養大部分來自蛋黃。這里的蛋黃（每個30 克）每周提供1.5 千克，如果要達到首次計算出的配方，那么需要每周為貓提供高達50 個的蛋黃數量，明顯是不太切合實際情況的。所以就需要考慮決策變量的變更，因為鈣和維生素E 的主要來源都是蛋黃，所以加入鈣粉和維生素E 進入決策變量，再次計算并可視化。

圖4 多種營養成分分析

本文在和弦圖的基礎上進行改進，得到了邊緣變形的和弦圖。該視圖使用徑向圓弧的弧長表示單個決策變量的大小，圓弧的寬度表示對應決策變量被替換而引入的額外支出。圓弧之間的弦表示可被替代的關系，同樣地，以顏色區分不同的類別。此視圖以紅色的圓弧為主，可以看出紅色圓弧所代表的決策變量可以被綠色、藏藍、粉色弦所連接的圓弧對應的決策變量替代。如圖4 所示，蛋黃可以被雞肝、鯖魚、雞心和鵪鶉替代，但是蛋黃自身一部分無法被替代，也就是說在此種組合策略下寵物貓必須攝入一定量的蛋黃。圖中綠色弦與紅色圓弧連接處出現了明顯的邊緣凸起，表明若使用鯖魚替代蛋黃會增加額外的成本，邊緣凸起的高度越大表示決策變量替換后線性規劃模型的值越大。

3 結語

本文針對線性規劃診斷和決策問題進行了可視化方法的研究，具體工作主要分為幾個方面：首先根據實際生活中存在的問題提出了可視化分析任務，建立了可視分析模型。然后，針對可視化任務提出了三種可視化方法，分別為?；鶊D可視化方法、嵌套餅圖-條形圖組可視化方法、邊緣變形的弦圖可視化方法。最后以寵物貓營養供給為例進行分析，分析結果驗證了可視化方法的有效性。