[其他]用于有效地分配資源的方法和設備

無效

• 申請號: 86101057
• 申請日: 1986-02-06
• 公開（公告）號: CN86101057A
• 公開（公告）日: 1986-11-12
• 發明（設計）人: 卡馬卡·納德·克爾施納
• 申請（專利權）人: 美國電話電報公司
• 主分類號: H04Q3/64
• 分類號: H04Q3/64
• 代理公司: 中國國際貿易促進委員會專利代理部
• 代理人: 李勇

本發明涉及在多個資源用戶當中進行資源分配的系統，更具體地說，是關于有效地對技術和工業資源進行最佳分配以便使這種分配的成本最低或效益最高的設備和方法。

在廣泛的技術和工業領域中都需要作出資源分配決策，例如在電話傳輸系統中對傳輸設備的分配，對工廠中產品調配的控制，工業設備的布署，以及庫存量的控制等等。在本文中，“資源分配”的一般含義是：為產生特定的技術或工業成果所需要的對技術或工業資源的具體布署。

資源分配決策一般都要遵從對這類分配方案的各種約束條件。資源總是限定在總體可利用性范圍之內，而且某一具體資源在某種具體應用之中的可用性也是有限度的。例如，提供給遠程通信系統的總通信量是有限的，在通信系統中每個鏈路的信號傳送能力也是有限的。對于某一資源的每個具體分配方案都能與一個“收益”相聯系，即與這種分配方案的成本或分配效益（例如利潤）相聯系。于是，問題歸結為對所有資源進行分配，使之滿足全部約束條件，同時使收益達到最大值，即是使成本最低或使效益提高。

表述分配決策問題的一種方法稱之為線性規劃模型（linear????programming????model）。這種模型由若干個線性表達式組成。這些線性表達式代表了各種可能的分配方案、它們的約束條件、以及它們的成本或效益之間的定量關系。如果所有的關系式都是常系數與未知分配值乘積之和（這些值等于某個常數，或者大于或等于某個常數，或者小于或等于某個常數），則這組關系被認為是線性的。當然，許多資源分配問題不能表示成這類線性關系，而是在關系式中涉及到未知量的高次方冪或其他非線性關系，因此，對這些問題不宜采用線性規劃方法。

應當指出的是，上面討論的資源分配問題是在實際物理系統中產生的實際物理問題。的確，這個物理問題的各個主要定量方面能夠由線性規劃模型來表述，而這一模型的目的是提供一組最佳值，然后用這組最佳值去構成或運行一個物理系統。以往應用這種數學模型來表示物理系統的典型的實例是利用方程組構成無線電天線或控制橡膠模壓生產過程。

在一段時間里，如上所述的許多資源分配問題是由人們運用自己的直覺與經驗來解決的。近年來，已經有了若干定量的手段協助人們進行這類決策活動，例如統計學、模型法、圖形法、以及線性規劃等等。應用這類定量手段的一個實例是制造廠應用線性規劃模型控制生產步驟和庫存量，使之既滿足銷售需要又能最大限度減少生產和存貨費用。與此類似的例子是一個通信系統利用線性規劃模型在一個傳輸設備網絡中開通電話通信路線，使得滿足全部通信量的要求，沒有任何一個鏈路超負荷，而且傳輸費用最低。

早期的作為線性規劃模型來解決分配問題的最著名的方法稱作單純形法（simplex????method），它是由喬治B.丹基格（George????B.Danzig）于1947年發明的，在1963年由新澤西州普林斯頓大學出版社出版的《線性規劃與擴展》（Linear????Programming????and????Extensions）一書中，喬治B.丹基格描述了這一方法。依照單純形法，第一步是選取一個初始的可行的分配方案作為起點，這可能是利用另一種線性規劃模型（它是原始模型的一個變體）得到的。這里，一個可行的分配方案是指它滿足全部約束條件但不知是否是最佳方案。然后依次識別出那些能改進被優化函數（稱為目標函數）的新分配方案。這一過程是迭代式重復過程，選擇出新的試驗方案，它們總是更加接近于最佳分配方案。當本次迭代的試驗分配方案不能得到進一步改進時，迭代過程即告終止。

通過分析由圖1給出的一個線性規劃模型的簡化圖示，可以更好地理解單純型法。圖1中給出一個凸多面體10的三維圖形，它有多個小面，例如小面11便是其中之一。多面體10的每個小面都用圖形表示出形式線性規劃模型中的一個約束關系的一部分。就是說，每個線性約束在多面體10的空間中定義一個平面，而這個平面的一部分即構成了多面體10的一個小面。說多面體10是凸多面體，這是指連接多面體10表面上任何兩點直線均在該多面體之中。

應該指出的是，將多面體10表示成三維多邊形僅僅是為了表示方便。事實上，一個線性規劃模型的多面體表示是包含于一個超空間中的。這個超空間具有的維數等于未知分配方案值（如圖1所見的情況），或者準確地說，等于不相等約束關系的數目減去相等約束關系的數目。的確，該多面體將這個超空間分成兩部分：由多面體10構成的可行區域和在多面體10外部的不可行區域。