最優解的證明
最優解的含義：在滿足約束條件的情況下，可使目標函式取極（大或小）值的可行解。貪心解是可行解，故只需證明：貪心解可使目標函式取得極值。
1）最優解證明思路：
● 比較貪心解x與任一最優解y
● 若x與y不等，則尋找第乙個不同元素的位置，假設為xi
● 替換最優解y的元素yi為xi，得到新的最優解z
● 證明: z與y相比，目標函式值沒有變化
● 反覆以上這種代換，直到新產生的最優解與貪心解x相等，即貪心解即最優解
2）定理3.1及其證明
定理3.1 如果p1/w1≥ p2/w2≥…≥ pn/wn,則演算法greedy-knapsack對於給定的揹包問題例項生成乙個最優解。
證明：設x=(x1, x2, …, xn)是grdddy-knapsack所生成的貪心解。
1 如果x1 = x2 = … = xn = 1，則顯然為最優解，得證。
2 否則，則存在y=(y1, y2, …, yn)是揹包問題的最優解，且有：
= mstep 1 找到x與y第乙個不等的元素所在的位置k，並將yk 替換為 xk
xi = yi = zi (istep 2 計算z的效益值，需要證明z的效益值大於等於y的效益值
= z1p1 + … + zk-1pk-1 +
zkpk + zk+1pk+1 + …+znpn
= y1p1 + … + yk-1pk-1 +
zkpk+zk+1pk+1+…+znpn
= y1p1 + … + ynpn –(ykpk + … + ynpn)+
zkpk+zk+1pk+1+…+znpn
= + pk(zk-yk) –
[pk+1(yk+1-zk+1)+...+ pn(yn-zn)]
= + wk (zk-yk) (pk/wk) –
[wk+1 (yk+1-zk+1) (pk+1/wk+1)+...+
wn (yn-zn) (pn/wn)]
(pk/wk >= pk+1/wk+1 >=…>= pn/wn)
>= + wk (zk-yk) (pk/wk) –
[wk+1 (yk+1-zk+1) (pk/wk)+...+
wn (yn-zn) (pk/wk)]
pk/wk)[wk (zk-yk) –]
step3 分析上式：如果能證明zk>yk，則yk增加到zk，那麼必須從（yk+1，…，yn）中減去同樣多的量，保證總容量仍然是m。從而有wk (zk-yk) =，即wk (zk-yk) –=0
step4證明zk>yk，即：xk>yk
由貪心解演算法，x的序列形式如下：j是使得xj <> 1的最小下標，0<=xj<1
y1、y2、y3分別為j和k相對位置不同的三種情況：
1) kyk，0<=yk<=1因此 xk>yk得證。
2) k=j；
m=w1x1+…+wj-1xj-1+wjxj
m=w1x1+…+wj-1xj-1+wjyj+…+wnyn
如果xj只有xj>yj成立
3) k>j；則xk=0，yk>=0，yk<>xk，因此，yk>xk
m=w1x1+…+wj-1xj-1+wjxj
m=w1x1+…+wj-1xj-1+wjxj+…wkyk+…+wnxn
同樣》m，不成立，因此得證。
step5 >=得證
step6 將x與z比較，如果不等，則找到第乙個不等的元素，繼續代換，直到x與最優解相等為止。
求整數最優解的方法
例題要將兩種大小不同的鋼板截成a b c三種規格，每張鋼板可同時截得三種規格的小鋼板的塊數如下表所示 今需要a b c三種規格的成品分別為15 18 27塊，問各截這兩種鋼板多少張可得所需三種規格成品，且使用鋼板張數最少。解 設需截第一種鋼板x張，第二種鋼板y張，則約束條件為 可行域為 目標函式為z...
最優化方法的matlab實現
在生活和工作中，人們對於同乙個問題往往會提出多個解決方案，並通過各方面的論證從中提取最佳方案。最優化方法就是專門研究如何從多個方案中科學合理地提取出最佳方案的科學。由於優化問題無所不在，目前最優化方法的應用和研究已經深入到了生產和科研的各個領域，如土木工程 機械工程 化學工程 運輸排程 生產控制 經...
引數估計最優統計性質的證明
一 引數估計與是y的線性函式 僅說明是y的線性函式，的情況類似可以得到。由的估計式，即由隨機變數y線性表出，從這一關係式還可理解到的隨機性是由y帶來的。引數估計線性性質的重要性，是可以基於y的統計分布建立引數估計和統計分布，這對利用和對真實引數和的統計推斷帶來了極大的方便。對於有如下一些性質，1 2...