演算法直到

『壹』 演算法步驟

上述演算法的流程如圖4-1所示。

演算法從尋找初始可行解開始。通常的做法是，它對應於從鬆弛變數列形成的基底。如果沒有初始可行解存在，則演算法在第二步停止。

圖4-1 菲力浦的多目標單純形法計算框圖

如果存在一個可行基底。便置計數器b和c分別為1和0。計數器b標識各個基底，計數器c標識對應於非劣勢解的基底，在第三步中計算與初始基底對應的解。在第四步中，通過解非劣勢性子問題來檢查可行解的非劣勢性。

演算法在第四、五、六步中進行循環，直到發現一個非劣勢解。發現後，把這個非劣勢解在第七步中列印出來。

為了檢查另外的非劣勢解，在第八步中求解方向子問題。如果沒有合適的（s_k）_min=0，那麼，不存在別的非劣勢解，演算法停止。但是，如果第九步確定了一個（s_k）_min=0，且第十步指出對應的x_k將引導到一個未探索過的基底，則對應的x_k進入基底，轉到第七步去列印出這個另外的非劣勢解。演算法將繼續在第七、八、九、十、十一、七步之間進行循環，直到出現沒有對應的x_k導致未探索基底時為止。

為了進一步理解菲力浦的多目標單純形法求解的有關步驟，我們考慮上一節中的例子並添加鬆弛變數來產生初始多目標單純形表。

極大優勢

華北煤田排水供水環保結合優化管理

其中，

華北煤田排水供水環保結合優化管理

滿足於約束條件

華北煤田排水供水環保結合優化管理

初始基本可行解在表4-2中列出，初始基底是根據與鬆弛變數x₃、x₄、x₅相關的列來形成的。從而，演算法的第一、二、三步是滿足的。

表4-2 初始基本可行解表

接下來，演算法確定x₁=x₂=0是否為非劣勢解點。這由解非劣勢性子問題來進行。要解這個非劣勢性子問題，需要確定（u^T+e^T）D。矩陣D對應於目標函數行中的非基本列，就是

華北煤田排水供水環保結合優化管理

對於x₁=x₂=0要是非劣勢的，必須存在一個權數集w_i=u_i+1，使得

華北煤田排水供水環保結合優化管理

或

華北煤田排水供水環保結合優化管理

或

華北煤田排水供水環保結合優化管理

減去剩餘變數s₁，s₂，添加人工變數y₁，y₂，產生所需要的第一演算階段單純形問題：

華北煤田排水供水環保結合優化管理

滿足於約束條件

華北煤田排水供水環保結合優化管理

對此非劣勢性子問題的初始表如表4-3所示。

表4-3 非劣勢性子問題的初始表

把第三行加到第一行上，產生初始可行解，如表4-4所示。

表4-4 初始可行解

根據單純形法則，u₂進入基底，旋轉主元是第三行框起來的數2。變換後得表4-5。

表4-5 非劣勢解表

此時y_min=0，s₁=7/2，u₂=1/2，u₁=s₂=y₁=y₂=0，於是點x₁=x₂=0是非劣勢解。

我們也注意到，表4-5表明存在正的權數w₁=u₁+1=1，w₂=u₂+1=3/2，解x₁=x₂=0也是下面問題的最優解。這個問題是：

華北煤田排水供水環保結合優化管理

滿足於

華北煤田排水供水環保結合優化管理

因此，可以這樣說，菲力浦演算法允許我們「朝後」應用加權方法：對於一個非劣勢解x，確定出一組權數w，它們是在加權方法中用來得出這個非劣勢解x所需要的權數。

接下來求解方向子問題，以確定是否存在另外的非劣勢解。從表4-5，我們能夠看到，有s₂=0。於是，如果引入x₂將導致一個未探索過的基底，則存在另一個非劣勢解點。從表4-2，對x₂的旋轉主元是第五行中的數字5，這表明新的基底將是x₂、x₃和x₄，它還沒有被探索過。

顯然沒有必要，因為已經確定了將導致另一個非劣勢解的x_k，但我們現在也能夠確定引入x₁是否會導致一個非劣勢解。這可以通過解下面的方向子問題來進行。這個方向子問題是：

華北煤田排水供水環保結合優化管理

滿足於

華北煤田排水供水環保結合優化管理

在第一演算階段以後（表4-5），得到如下的方向子問題，表4-6所示。

表4-6 方向子問題表

把第2行加到第一行上，產生了表4-7。

表4-7 最優解表

表4-7是最優的，它指出s₁=7/2＞0，因此引入x₁將導致一個有劣勢解。

我們現在引入x₂。以表4-2第五行的元素為主元進行旋轉，得到主問題的第二個表，如表4-8所示，從而，x₁=0，x₂=72/5是一個非劣勢解，把它列印出來。

表4-8 主問題二表

為了檢查是否存在別的非劣勢解，現在必須重新求解方向子問題。要這樣做，必須又一次計算（u^T+e^T）D，其中的矩陣D此時為

華北煤田排水供水環保結合優化管理

於是，

華北煤田排水供水環保結合優化管理

由此，方向子問題的合適的約束集為

華北煤田排水供水環保結合優化管理

關於目標函數，可以為s₁和s₅。然而，在前面我們是用x₂驅趕x₅而得到目前的非劣勢解點，因此，易知有s₅=0，且把x₅帶入基底會產生出前面的非劣勢解點。從而，僅需對s₁檢查方向子問題，就是，

華北煤田排水供水環保結合優化管理

滿足於

華北煤田排水供水環保結合優化管理

用表的形式，見表4-9。

表4-9 方向子問題表

把表4-9的第2行加到第1行上，得表4-10。對表4-10以第2行第二列元素為主元進行旋轉，得到最優的表4-11。從表4-11可以看出，s₁=0，這表示此時把x₁引入基底將產生另一個非劣勢解點。從表4-3可明顯看出，旋轉主元是4/25，將把x₄驅趕出基底。這導致又一個未探索過的基底（x₁，x₂和x₃）和第三個非劣勢解點。以4/25為主元旋轉，得到下面表4-12中的解：非劣勢點x₁=7，x₂=13。

表4-10 方向子問題過渡表

表4-11 最優解表

表4-12 非劣勢解表

繼續與前面同樣的過程，即求解與表4-12相關的方向子問題，得到s₄=0和s₅=9/2。引入s₄將把x₁從基底中驅趕出去並返回到先前的非劣勢解。引入x₅將把x₂從基底中驅趕出去將得到一個有劣勢解。這樣，演算法停止^［134］。

『貳』 有N個人圍成一環形圈，第一個人從1開始報數，報道M的人出列，直到最後一個同學，請寫出演算法。

經典的約瑟夫環問題
設n個人圍成一圈，標號為0..n-1，從第一個人開始依次從1到k循環報數，當報到k的
時候此人出圈。設J(n,
k,
i)表示第i個出圈的人的標號。
定理一:
J(n,
k,
1)
=
(k-1)
MOD
n,
(n>=1,
k>=1)
…………
(1)
證明：由定義直接得證。
定理二：
J(n+1,
k,
i+1)
=
(k
+
J(n,
k,
i))
MOD
(n+1),
(n>=1,
k>=1,
1<=i<=n)
………
…
(2)
證明：
設g
=
J(n,
k,
i)，因此如果有n個人，從0開始報號，第隱世i個出圈的標號為g。現在考
慮J(n+1,
k,
i+1)，灶清肢因為J(n+1,
k,
1)
=
(k-1)
MOD
(n+1)，即第一步的時候刪除數
字(k-1)
MOD
(n+1)，第二步的時候從數字k開始數起。因而問題變為了找到剩下的n
個數字中從k開始數起被刪除的第i個數字(注意這時(k-1)
MOD
(n+1)已經被刪除了)
，而這恰好就正咐是(g+k)
MOD
(n+1)，(2)成立。
根據(2)，很容易求得n個數裡面第i個出圈的數。
就根據這個定理遞推計算吧！

『叄』 設計一個計算10個數的平均數的演算法 （用直到型和當型）

演算法可以這樣描述：
S1：S=0；
S2：I=1；
S3：輸入一個數G；
S4：使S+G,其和仍放S中；
S5：使I的值增加1；
S6：如果I＞10,退出循環,如果I≤10重復S3；
S7：將平均數S/10存放在A中；
S8：輸出A.
按著演算法就可以畫程序框圖了

『肆』 利用兩種循環寫出1+2+3+…+100的演算法，並畫出各自的流程圖

直到型循環演算法：

第一步：S←0；

第二步：I←1；

第三步：S←S+I；

第四步：I←I+1；

第五步：如果I不大於100，轉第三步；否則，輸出S。相應的流程圖如圖甲所示．當型循環演算法如

下：S1令i←1，S←0S2 。

當型循環演算法如下：

S1 令i←1,S←0

S2 若i≤100成立，則執行S3；否則，輸出S，結束演算法

S3 S←S+i

S4 i←i+1，返回S2

相應的流程圖如圖乙所示。

(4)演算法直到擴展閱讀

從1開始遞增依次與從100開始遞減、將兩個數進行相加配對、有50組為101的數。

1+100=101，2+99=101······50+51=101。從1加到100有50組這樣的數，所以50X101=5050。

等差數列求和公式：（1+100）*100/2=5050