線性規劃問題是討論乙個給定的線性目標函式在一組線性約束條件下的最大值或最小值問題。對於乙個實際問題,管理科學者根據管理層決策目標的要求,首先確定乙個目標函式以衡量不同決策的優劣,且根據實際問題中的資源、資金和環境等因素對決策的限制提出相應的約束條件以建立線性規劃模型;然後用計算機軟體求出最優方案並作靈敏度分析以供管理層決策之用。而在一些問題中,決策目標往往不只乙個,且模型中有可能存在一些互相矛盾的約束條件的情況,用已有的線性規劃的理論和方法無法解決這些問題。
因此,2023年美國學者查恩斯(a.charnes)和庫柏(提出了目標規劃的概念與數學模型,以解決經濟管理中的多目標決策問題。
我們將通過幾個例子來說明在實際應用中線性規劃存在一系列的侷限性。
例1 某廠生產a、b兩種產品每件所需的勞動力分別為4個人工和6個人工,所需裝置的單位台時均為1。已知該廠有10個單位機器台時提供製造這兩種產品,並且至少能提供70個人工。又,a、b產品的利潤,每件分別為300元和500元。
試問:該廠各應生產多少件a、b產品,才能使其利潤值最大?
解設該廠能生產a、b產品的數量分別為件,則有
**法求解如下:
由上圖可得,滿足約束條件的可行解集為,即機時約束和人工約束之間產生矛盾,因而該問題無解。但在實際中,該廠要增加利潤,不可能不生產a、b兩種產品,而由線性規劃模型無法為其找到乙個合適的方案。
例2 某廠為進行生產需採購a、b兩種原材料,單價分別為70元/公斤和50元/公斤。現要求購買資金不超過5000元,總購買量不少於80公斤,而a原材料不少於20公斤。問如何確定最好的採購方案(即花掉的資金最少,購買的總量最大)?
解這是乙個含有兩個目標的數學規劃問題。設分別為購買兩種原材料的公斤數,為花掉的資金,為購買的總量。建立該問題的數學模型形式如下:
對於這樣的多目標問題,線性規劃很難為其找到最優方案。極可能的結果是,第乙個方案使第一目標的結果值優於第二方案,同時第二方案使第二目標的結果值優於第一方案。也就是說很難找到乙個最優方案,使兩個目標的函式值同時達到最優。
另外,對於多目標問題,還存在有多個目標存在有不同重要程度的因素,而這也是線性規劃所無法解決的。
**性規劃的基礎上,建立了一種新的數學規劃方法——目標規劃法,用於彌補線性規劃的上述侷限性。總的來說,目標規劃和線性規劃的不同之處可以從以下幾點反映出來:
1、線性規劃只能處理乙個目標,而現實問題往往存在多個目標。目標規劃能統籌兼顧地處理多個目標的關係,求得切合實際需求的解。
2、線性規劃是求滿足所有約束條件的最優解。而在實際問題中,可能存在相互矛盾的約束條件而導致無可行解,但此時生產還得繼續進行。即使存在可行解,實際問題中也未必一定需要求出最優解。
目標規劃是要找乙個滿意解,即使在相互矛盾的約束條件下也找到盡量滿足約束的滿意解,即滿意方案。
3、線性規劃的約束條件是不分主次地等同對待,這也並不都符合實際情況。而目標規劃可根據實際需要給予輕重緩急的考慮。
§2.1 基本概念
在這一小節裡介紹與目標規劃有關的基本概念。
1.偏差變數
對於例1,造成無解的關鍵在於約束條件太死板。設想把約束條件「放鬆」,比如占用的人力可以少於70人的話,機時約束和人工約束就可以不再發生矛盾。在此基礎上,引入了正負偏差的概念,來表示決策值與目標值之間的差異。
——正偏差變數,表示決策值超出目標值的部分,目標規劃裡規定;
——負偏差變數,表示決策值未達到目標值的部分,目標規劃裡規定。
實際操作中,當目標值(也就是計畫的利潤值)確定時,所作的決策可能出現以下三種情況之一:
(1)決策值超過了目標值(即完成或超額完成計畫利潤值),表示為,;
(2)決策值未達到目標值(即未完成計畫利潤值),表示為,;
(3)決策值恰好等於目標值(即恰好完成計畫利潤指標),表示為,。
以上三種情況,無論哪種情況發生,均有=0。
2.絕對約束與目標約束
絕對約束也稱系統約束,是指必須嚴格滿足的等式約束和不等式約束,它對應於線性規劃模型中的約束條件。
目標約束是目標規劃所特有的。當確定了目標值,進行決策時,允許與目標值存在正或負的偏差。因而目標約束中加入了正、負偏差變數。
如,例1中假定該企業計畫利潤值為5000元,那麼對於目標函式
,可變換為
。該式表示決策值與目標值5000之間可能存在正或負的偏差(請讀者分別按照上面所講的三種情況來理解)。
絕對約束也可根據問題的需要變換為目標約束。此時將約束右端項看作所追求的目標值。如,例1中絕對約束,可變換為目標約束。
3.目標規劃的目標函式
對於滿足絕對約束與目標約束的所有解,從決策者的角度來看,判斷其優劣的依據是決策值與目標值的偏差越小越好。因此目標規劃的目標函式是與正、負偏差變數密切相關的函式,我們表示為。它有如下三種基本形式:
(1)要求恰好達到目標值,即正、負偏差變數都盡可能地小。此時,構造目標函式為:
(2)要求不超過目標值,即允許達不到目標值,正偏差變數盡可能地小。此時構造目標函式為:
(3)求超過目標值,即超過量不限,負偏差變數盡可能地小。此時構造目標函式為:
4.優先次序係數與權係數
乙個規劃問題往往有多個目標。決策者在實現這些目標時,存在有主次與輕重緩急的不同。對於有級目標的問題,按照優先次序分別賦予不同大小的大係數:
,,,。,,,為無窮大的正數,並且, (「」符號表示「遠大於」),這樣,只有當某一級目標實現以後(即目標值為0) ,才能忽略大的影響,否則目標偏離量會因為大的原因而無窮放大。並且由於,所以只有先考慮忽略影響(實現第級目標)後,才能考慮第級目標。
實際上這裡的大是對偏離目標值的懲罰係數,優先級別越高,懲罰係數越大。
權係數用來區別具有相同優先順序別的若干目標。在同一優先級別中,可能包含有兩個或多個目標,它們的正負偏差變數的重要程度有差別,此時可以給正負偏差變數賦予不同的權係數和。
各級目標的優先次序及權係數的確定由決策者按具體情況給出。
§2.2 目標規劃的數學模型
綜上所述,目標規劃模型由目標函式、目標約束、絕對約束以及變數非負約束等幾部分構成。目標規劃的一般數學模型為:
目標函式
目標約束
絕對約束
非負約束
例3 在例1中,假定目標利潤不少於15000元,為第一目標;占用的人力可以少於70人,為第二目標。求決策方案。
解按決策者的要求分別賦予兩個目標大係數。列出模型如下:
例4 某紡織廠生產a、b兩種布料,平均生產能力均為1千公尺/小時,工廠正常生產能力是80小時/周。又a布料每千公尺獲利2500元,b布料每千公尺獲利1500元。已知a、b兩種布料每週的市場需求量分別是70千公尺和45千公尺。
現該廠確定一周內的目標為:
第一優先順序:避免生產開工不足;
第二優先順序:加班時間不超過10小時;
第三優先順序:根據市場需求達到最大銷售量;
第四優先順序:盡可能減少加班時間。
試求該問題的最優方案。
解設分別為生產甲、乙布料的小時數。對於第三優先順序目標,根據a、b布料利潤的比值,取二者達到最大銷量的權係數分別為5和3。該問題的目標規劃模型為:
綜上所述,目標規劃建立模型的步驟為:
1、 根據問題所提出的各目標與條件,確定目標值,列出目標約束與絕對約束;
2、根據決策者的需要將某些或全部絕對約束轉換為目標約束,方法是絕對約束的左式加上負偏差變數和減去正偏差變數;
3、給各級目標賦予相應的懲罰係數(),為無窮大的正數,且;
4、對同一優先順序的各目標,再按其重要程度不同,賦予相應的權係數;
5、根據決策者的要求,各目標按三種情況取值:①恰好達到目標值,取②允許超過目標值,取③不允許超過目標值,取;然後構造乙個由懲罰係數、權係數和偏差變數組成的、要求實現極小化的目標函式。
3.1 **法
只有兩個決策變數的目標規劃數學模型,可以使用簡單直觀的**法求解。其方法與線性規劃**法類似,先在平面直角座標系第一象限內作出各約束等式或不等式的圖象,然後由絕對約束確定了可行域,由目標約束和目標函式確定最優解或滿意解。
對於絕對約束,與線性規劃中的約束條件畫法完全相同。對於目標約束方程,除作出直線外,還要在直線上要標出正負偏差變數的方向,其可行域方向取決於目標函式中對應目標。另外,目標規劃是在前一級目標滿足的情況下再來考慮下一級目標,很有可能盡可能滿足目標的解不是可行解(即非可行解),而是權衡以後得出的最優解——滿意解。
因而在目標規劃裡稱求得的解為滿意解。
注意在求解的時候,把絕對約束作最高端別考慮。
例5 用**法求解目標規劃問題
解在平面直角座標系第一象限內作出各約束條件的影象,目標約束要在直線旁標上和di+。
首先,絕對約束確定了可行解範圍在三角形oef內;
根據第一級目標,要求實現(恰好),因而可行解範圍縮小到線段oc上;
根據第二級目標,要求實現(不少於),**段oc上,取的點a,此時可行解範圍縮小到線段ac上;
根據第**目標,要求實現,**段ac上,取的點b,此時解的範圍縮小到線段ab上。
所以,線段ab上的所有點為滿意解。可求得a(15/8,15/8),b(24/7,24/7)。
例6 用**法求解例4的目標規劃模型。
解在平面直角座標系第一象限內作出各約束條件對應的圖象,並在目標約束直線旁標上和。
根據第一級目標,目標函式要求實現,解的範圍是線段ac的右上方區域;
根據第二級目標,目標函式要求實現,解的範圍縮小到四邊形abdc內的區域;
7運籌學之目標規劃胡運權版
線性規劃問題是討論乙個給定的線性目標函式在一組線性約束條件下的最大值或最小值問題。對於乙個實際問題,管理科學者根據管理層決策目標的要求,首先確定乙個目標函式以衡量不同決策的優劣,且根據實際問題中的資源 資金和環境等因素對決策的限制提出相應的約束條件以建立線性規劃模型 然後用計算機軟體求出最優方案並作...
衛生管理運籌學目標規劃
第四章目標規劃 前面的線性規劃問題,研究的都是只有乙個目標函式,若干個約束條件的最優決策問題 然而現實生活中,衡量乙個方案的好壞標準往往不止乙個,而且這些標準之間往往不協調,甚至是相互衝突的,標準的度量單位也常常各不相同 例如,在資源的最優利用問題中,除了考慮所得的利潤最大,還要考慮使生產的產品 勞...
運籌學 線性規劃
數學與計算科學學院 實驗報告 實驗專案名稱線性規劃 所屬課程名稱運籌學b 實驗型別綜合實驗 實驗日期 班級成績 附錄1 源程式 附錄2 實驗報告填寫說明 1 實驗專案名稱 要求與實驗教學大綱一致.2 實驗目的 目的要明確,要抓住重點,符合實驗教學大綱要求.3 實驗原理 簡要說明本實驗專案所涉及的理論...