王沙沙

【摘要】自動態(tài)規(guī)劃開始研究之后，在城市規(guī)劃、金融管理、生產(chǎn)車間調(diào)度和最優(yōu)化等方面有很廣闊的應(yīng)用前景。例如最短路徑、資源分配、生產(chǎn)庫存等問題，用動態(tài)規(guī)劃的方法解決更加方便。

【關(guān)鍵詞】動態(tài)規(guī)劃 最優(yōu)化 服裝搭配

動態(tài)規(guī)劃隸屬于運籌學(xué)的研究范圍，是用于求解決策過程最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家貝爾曼等人在研究多階段決策優(yōu)化問題的過程中提出了著名的最優(yōu)化原理，把多階段的過程問題轉(zhuǎn)化為一系列的單階段問題，逐個求解，創(chuàng)立了解決此類過程優(yōu)化問題的新方法—動態(tài)規(guī)劃。

一、動態(tài)規(guī)劃的基本概念

最優(yōu)化原理：作為整個過程的最優(yōu)策略，它滿足：相對于前面的決策所形成的狀態(tài)，余下的子策略必然構(gòu)成“最優(yōu)子策略”。

狀態(tài)轉(zhuǎn)移：動態(tài)規(guī)劃中本階段狀態(tài)往往是上一階段狀態(tài)和上一階段決策的結(jié)果，由第k段的狀態(tài)sk和本階段決策uk確定第k+1段的狀態(tài)sk+1的過程叫狀態(tài)轉(zhuǎn)移。狀態(tài)轉(zhuǎn)移規(guī)律的形式化表示

■

稱為狀態(tài)轉(zhuǎn)移方程。狀態(tài)轉(zhuǎn)移是決策目的，決策是狀態(tài)轉(zhuǎn)移的路徑，各階段決策確定以后，整個問題的決策序列就構(gòu)成了一個策略。

規(guī)劃方程的一般求法是從一個目標(biāo)狀態(tài)出發(fā)的遞推公式：

■

■某個初始值，稱為邊界條件。

二、搭配衣服問題

通過對動態(tài)規(guī)劃的學(xué)習(xí)以及對動態(tài)規(guī)劃應(yīng)用的研究與分析，我發(fā)現(xiàn)現(xiàn)實生活中的“搭配衣服問題”也可以用動態(tài)規(guī)劃方法實現(xiàn)。例如：

假設(shè)你剛開了一家服裝店，你想雇來一些模特，通過她們最完美的服裝展示吸引顧客?，F(xiàn)在有模特數(shù)量m，同時也有至少同樣數(shù)量的衣服被按順序擺成一行。這些衣服固定于衣架上，衣架不可移動，并從1至n序編號，從左至右排列，則最左邊的是衣服1，最右邊的是衣服n，并且可以移動，每位模特用1至m的整數(shù)唯一標(biāo)識。標(biāo)識模特的整數(shù)決定了模特所穿的衣服的順序，如果i

例如，假設(shè)一共雇來5位模特，第一位模特標(biāo)識數(shù)為1，第二位模特的標(biāo)識數(shù)為2，第三位模特標(biāo)識數(shù)為3，第四位模特標(biāo)識數(shù)為4，第五位模特標(biāo)識數(shù)為5，所有的模特穿上衣服時必須保持其標(biāo)識數(shù)的順序，即模特的順序不變。如果衣服的數(shù)量大于模特的數(shù)量。則多余的衣服必須空置，且一位模特只能穿一件衣服。

由于每一位模特的身高、體型各不同。所以，當(dāng)不同的模特穿不同的衣服，會產(chǎn)生不同的視覺效果，并以美學(xué)值（一個整數(shù)）來表示，定義空置衣服的美學(xué)值為零。在上述例子中，衣服與模特的不同搭配所具有的美學(xué)值，如表3.1所示。

表3.1 衣服與模特的不同搭配所具有的美學(xué)值

■

從表中不難看出模特1搭配衣服6會很好看，然而搭配衣服7就會遜色很多；模特2搭配搭配衣服7很好看，然而搭配衣服4會遜色很多；模特3搭配衣服2會很好看，然而搭配衣服1就會遜色很多；模特4配搭配衣服6會很好看，然而搭配衣服5就會遜色很多；模特5配衣服4會很好看，然而搭配衣服1就會遜色很多。

用動態(tài)規(guī)劃的方法解決這個問題的步驟：

第一，以模特的人數(shù)來劃分階段。在這里，階段變量k表示的就是要布置的模特人數(shù)（前k位模特），狀態(tài)變量sk表示第k位模特所穿的衣服。而對于每一個狀態(tài)sk，決策就是第k-l位模特應(yīng)該穿哪件衣服，用uk表示。最優(yōu)指標(biāo)函數(shù)fk（sk）表示前k位模特，其中第k位模特穿第sk件衣服，所能取得的最大美學(xué)值。

第二，狀態(tài)轉(zhuǎn)移方程：■。

第三，規(guī)劃方程：■■。

第四，邊界條件：■■（V是衣服總數(shù)）。

解：以模特人數(shù)來劃分階段，不難看出可劃分為5個階段。

方法1 逆向遞推法

由于此時模特2穿的是7號衣服，要保證模特的順序保持不變是實現(xiàn)不了的，故考慮要想使得模特的順序不變，模特1 的選擇只有衣服1、2、3，模特5的最優(yōu)選擇是衣服7，此時從后向前考慮，可得模特4選擇衣服6，此時模特3的最優(yōu)選擇時衣服3，故模特2選擇衣服2，模特1選擇衣服1。

k=1時，■；

k=2時，■；

k=3時；■；

k=4時，■；

k=5時，■。

方法2 正向遞推法

要保證模特的順序保持不變是實現(xiàn)不了的，故考慮要想使得模特的順序不變，模特1的選擇只有衣服1、2、3，模特5的最優(yōu)選擇是衣服7。

當(dāng)模特1選擇衣服3時，其余模特的選擇只有一種，即模特2選擇衣服4，模特3選擇衣服5，模特4選擇衣服6，模特5選擇衣服7；當(dāng)模特1選擇衣服2時，模特2只能在衣服3、4中選擇，由于5<18，故模特2應(yīng)當(dāng)選擇衣服3；模特3同樣有兩種選擇，即衣服4、5，由于8>2，則模特3選擇衣服5時，■；當(dāng)模特3選擇衣服4時，■，由于14>-3，則模特4選擇衣服6時，■；當(dāng)模特4選擇衣服5時，■；故模特5衣服7；當(dāng)模特1選則衣服1時，■；由于6<18，模特2有2種選擇，即衣服2或衣服3，從以上結(jié)果可知模特2選擇衣服3之后的有三種結(jié)果，由于6=5+1，故得到的三個順序分別為：1-3-5-6-7，1-3-4-6-7，1-3-4-5-7。

當(dāng)模特2選則衣服2時，■，由于10>2，則模特3有三種選擇，當(dāng)選擇衣服5時，■，當(dāng)模特3選擇衣服4時，■，由于16=14+2，則■；當(dāng)模特3選擇衣服3時，■，由于27>-3，則當(dāng)模特4選擇衣服6時，■，當(dāng)模特4選擇衣服5時，■，模特5選擇衣服7，■；當(dāng)模特4選擇衣服4時，■，模特5選擇衣服7，■。故可以得到下表：

■

由此得出一個最優(yōu)方案為：1-2-3-6-7。

三、總結(jié)

動態(tài)規(guī)劃是求解最優(yōu)化問題的一種途徑、一種方法，往往針對一種最優(yōu)化問題。動態(tài)規(guī)劃的設(shè)計方法對不同的問題，有各具特色的解題方法。本文介紹了動態(tài)規(guī)劃服裝搭配方面的實際應(yīng)用。通過求解，總結(jié)出了動態(tài)規(guī)劃方法的便利性和高效性。

參考文獻

[1]劉鳳鳴.動態(tài)規(guī)劃的應(yīng)用[J].Science Technology Vision，2013，13（7）：40-43.

[2]趙娟，樊超.動態(tài)規(guī)劃方法的應(yīng)用研究[J].Computer Ero，2014，7（2）：28-30.

[3]厲洋峰.動態(tài)規(guī)劃及其在數(shù)學(xué)模型中的應(yīng)用[J].China New Technologies and Products，2009，16（8）：224-225.