关于线性规划在实际应用中的一些问题

这是最近在做新enigma机的项目时候遇到的一点问题。

主要研究对象的实质是线性规划。

因为线性规划存在在可数学函数化前提下的固定解法,所以这一问题本身可以认为是基本上存在最优解。但在实际应用中出现的问题在于,在面对极大线性规划的时候,一般采用的单纯型算法的理论时间是指数级,即不可解,而在此时只能用内点法来进行尝试,理论上内点法可以在多项式时间内可解,但涉及具体问题的时候容易成为NP型,也就是说实际上是一个LP问题,即是否能在强多项式时间内可解。这也就是这个问题的核心数学问题。当然这一问题目前没有解决。

但涉及实际问题的时候存在另外的问题,即在最优化的过程中花掉的时间(利益)多于达到最优化而产生的利益的时,这个优化则没有实际意义。即使是在强多项式时间内可解。而对于一个量“利益”的判断是涉及社会性的量,这个量没有没有固定的定理来判断,于是总体原则上来说实际性的极大线性规划的实际考量是不存在理论上的特定最优解。

当然必须考量到涉及实际性的时候极大的实际大小定义,即模型中顶点的数量问题。这个在目前的工作中已经有遇到。另外这其中涉及到实际问题与函数模型的转换的复杂度问题,这又是一个需要论证的方面。但总体可以这样说,在一个比较复杂的实际问题且其以线性规划为基本模型的前提下,实际中不存在理论上的最优解。

Advertisements

10 responses

  1. welcome join us!! 臺灣寶貝-休閒地帶 http://www.nice777.info

  2. 閣下妳好
    在下由HKG得知而來
    看了些閣下文章 程序+德國 引起在下些興趣 不知是否能藉機請教些?

    在下想請教的是 此文所述線性規劃的實際應用:enigma机
    enigma机 查了些資料 可說其間接指向密碼學(?) 密碼學牽涉到編解碼
    因此由編解碼 關聯到線性規劃? 可能表達的不是很好 換個說法
    文中提到的enigma机 其實際是代表什麼?
    因如果以歷史來看 是個戰爭使用一個器具 聯想不到線性規劃

    且 曾接觸一說法 實際存在最優解 這最優解來自於經驗(統計)
    因探討演算法的基礎上是實現 實現方法在於程序
    考慮程序誤差累積 則有最大效益之處 -不知文中第二段 是否也已涵蓋這情況

    見識淺拙 如有錯誤 煩請見諒

    1. 難得見到有人對這個話題感興趣www

      enigma是我的一個項目的名稱,裏面有些地方用到了線性規劃,這個項目本身和這文關係不大。

      至於你說的情況是有考慮到的,這就是實際問題在實際中的體現,因為你也看到你所說的最優解是來源於統計,統計是要求實例的,所以他在理論上還是不適用的。為什麼呢,因為你不是在 設計 上就找出了理論最優解,而是實踐找到一個近似最優解,注意,他依然不是最優解,因為你無法實驗所有的可能性,也不能保證你的實驗數據足夠,所以他依然只是一個近似最優解。更何況還有我文裡提到的問題,你要花多少 代價 在實驗和數據收集上?你付出的代價會不會大於收益?特別在一個足夠複雜的實例中。所以我這文的觀點在這個情況下依然是適用的。而你接觸的那個說法我個人覺得是還不夠周全的。

  3. 閣下所指 “統計是要求實例” 這應有兩種情況
    一是實例來於實驗 也因此牽涉到了實驗代價的問題
    二是實例來於實行 即已不在於設計階段 而是在於成品階段

    閣下所述所慮之層面 是否在於 針對一已知或部分已知(因無法了解全部可能)的問題 進行”設計”解決問題的方法(找尋實際最優解的方法) 設計完畢後 在實現於成品上 如此為上述第一點情況

    上述第二點情況 則不同
    不在於設計上尋求最優解之方法 而在於給予”成品”具有找尋最優解的能力
    如此 將無過大的實驗代價與理論上不可行的最優解 問題
    其中給予成品具有尋找最優解能力 情況是與第一點實驗相似 即需要相當的資訊(>數據&資料)

    上述第二點情況的概念 一般似稱為 人工智慧/類神經網路(具有學習能力)

    如此 是程式乃至於演算法概念之轉變 已實現最優解
    其實在於第一點情況中考慮的最優解情況 是將最優解視為絕對性
    應該視為相對性才較適當 因為即使能夠克服實際情況而實現絕對性的最優解
    在時間的推演下 也會喪失絕對性而成為相對性最優解

    1. 沒錯啊,因為 設計 的話,純在數學層面上來說,自然是可能有最優解確定和產生的,而實際中 設計 是達不到最優解的,這就是這文的觀點所在,你所說的情況叫做 改進 是對原有設計,在實例的基礎上得到更優解,這是更符合現實做法的方式。所以和你說的也差不多,設計上的 最優 不代表什麼,即使因為情況簡單而有數學模型的最優解,不代表實際中他依然是最優解,因為執行力等問題。 另外你說的相對性就是我上一篇回答你的時候說到的近似最優解問題,也就是說實際中你只能無限接近最優解,而不能達到最優解。

  4. 閣下說 在下所述情況是改進
    以商業層面來說 投入一實品 會定一某種程度的投入成本(時間人力)
    即基於這成本下 需完成成品 這成本暫稱最初成本

    前面討論中的實驗代價 即歸於最初成本 且會莫大增加這最初成本
    也因是商業層面而受限在某種程度的投入成本 可付出的實驗代價勢必不大
    (除非近學術)
    如此 考慮實際問題如最優解 將會是以這程度的投入成本 尋求能獲得較佳結果的處理方法 即一種實際問題或一實品所包含的所有問題 勢必有基於最初成本下而獲得一解決方法

    此時 就有了改進動作(隨時間推移下) 但這改進動作亦須付出成本(時間人力)
    除非最初成本以包含到這情況 否則將視為一個額外付出的成本 且付出幾次是無法得知(即使最初成本包含這改進成本 也無法預知這改進成本的程度 因時間推移)

    故 在下前面所說情況 確實是改進動作 但在該情況下是能減少改進動作所要付出的成本程度(雖然兩者情況的最初成本是不一定相同)

  5. 所以在現代設計,特別是計算機領域來說,算法或者說設計經常出現的是,並不是最好的,但是 當 前 最實用的,而靠後期,用一個專業術語的話,Refactoring,來實現不斷的優化,以使其接近最優化。

    但同樣有一個生命週期的問題,也就是這文裡面的另一個觀點,你必須加上成本的函數,來對比設計或者改進中帶來的效益,如果前者大於了後者,那麼追求理論上的後者最優化是沒有意義的。

    另外還有一直強調的一個問題,現實中的很多問題是無法轉換成為單純的數學模型的,所以 社會性 的事物,可以簡單的認為沒有最優解,永遠只能接近最優解。

    現實中,用數學術語來說的話,最優解 – 現實可實現解 = e > 0, 但當 e < E,E 為足夠小的量的時候,我們在現實中就認為是最優解了

  6. 謝謝閣下不厭其煩的解說與遷就在下用字=w=
    在下大學所讀電機 所以對計算機領域根本談不上專業 很粗淺的有聽聞些而已
    故能與閣下請益 在下自是相當感謝

    如果一現實問題轉換數學模型是相當複雜 則這情況帶來的是:執行上的困難度增加 如執行成本過高?進而是否簡化以減少成本? 前句前提是基於只要可執行(有解)下 而不是追求最優或近似最優 如此 且是否還會造成其它問題?

    對問題情況了解後(如上面討論的各類情況)與實際設計前的進行效益評估
    實際上是用什麼樣的方法來評估”效益” 即實際上是否對”效益”數據化(量化)以進行比較?

    1. 打個比方的話,兩點間的最短距離這種就是簡單的情況,可以用簡單的線性規劃來解決;但比如背包問題,就相對複雜很多,這屬於動態規劃的範疇。或者說線性規劃其實就是動態規劃的一個分支。

      以背包問題為例,他肯定有解,而在理論上一个最優解卻無法在多項式時間內找到最準確的解。(即它是個NP問題)
      這個其實就符合你說的情況。對這個問題的解法就是動態規劃,動態規劃的理念就是追求近似最優解。但其實他降低的也只是理論上的時間成本,但沒有更好的方法之前,這種方法就可以被認為是減少了這個問題的成本,不管這套算法要花多少時間。因為这个算法所花費的代價还是可以計算的。

      所以現實中往往需要追求 成本可接受 的解法,當然追求一個特定的解也可以,不過 運行成本 就會很高。所以實際中還是需要不斷改進,如果 運行成本 過高的話。

      效益要說也很簡單,即 收益 – 成本 = 效益,比如 我改進一個尋路算法,改進後的效果 – 改進前的效果 = 收益,成本 = 花在改進這個尋路算法上的成本。你可以看到純數學的話,這個算式是無法進行的,因為他們的單位就不同,所以現實中往往需要換算成一些別的更純數學的東西來計算。
      例如,我改進後找一條路的時間 – 改進前找一條路的時間 = 改進收益(時間) 成本 = 比如,花了多少人的多少時間在這上面,就會有一個效益值,以這個值來和 運行成本 (比如這裡就是我一天要用這個算法多少次,花費多少時間這種簡單的換算)的改善來對比就能算出效益是多少,只要效益是正的,那麼這個改進就是值得的。

      這裡值得注意的一點就是我文裡提到的,如果過於複雜,這個就不那麼好計算了,或者說換算成數學的東西。比如一個國家改用歐元的收益有多少,這個就根本無法函數化來計算。

  7. 回覆晚了 請見諒

    線性規劃屬動態規劃的分支之一,即動態規劃為上位概念,線性規劃為下位概念。則是否動態規劃亦屬於下位概念,而還有上位概念存在?

    代價問題
    以上面背包與國家改用歐元的收益多少,這兩情況來討論。
    一個複雜問題,但只要轉換成數學的東西(模型),即能計算出代價多少?
    即問題間接由可實行與實際必行手段的數學轉換中,計算代價多少?
    也因此如上面所說,當一個問題過於複雜,以致不易轉換成數學的東西或無法轉換時,其問題解法的代價就無法比較精確的計算出來?
    因為無法轉換成數學?

    上面考慮的出發點在於;對於一個問題進而設計解法,這第一次設計,是否就能評估這第一次設計所要付出的代價?
    因此,對於問題在勢必解決的前提下,分有代價可計算與不可計算兩種情況?

    因為這關聯到,藉由(解決方法的)代價計算而比較二個以上的解決方法,
    選擇較小或較優代價的解決方法,進而實行。
    如果是遇到代價不可計算的情況,這便意味著無法比較兩個以上的解決方法?

    上面討論的東西,簡短的說就是代價是否可預測?不可預測代價時,需如何應對?

    效益問題
    如此的話,這改進方法的效益,將間接被改進人或團體所影響。因此實際在改進程序時,是否會有另一(批)人來做客觀立場的存在?
    例如字幕的翻譯人員翻好後,再由校對、後期人員看稿等這樣行為。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: