當前位置:歷史故事大全網 - 歷史故事 - 線性規劃中,如何知道原問題的最優解,直接寫出對偶問題的最優解

線性規劃中,如何知道原問題的最優解,直接寫出對偶問題的最優解

是的根據對偶理論,對偶問題和原問題是對偶的,對偶問題的目標函數恰好等於原問題的最目標函數,可以證明這個目標函數值也是最優的,反之亦然。假設對偶問題的最優解不唯壹,則其對偶問題(即原問題)的最優解不唯壹,這與原問題是矛盾的。

因為原問題和對偶問題互為對偶,所以有壹定的對應關系。在有限最優解方面:原問題的有限最優解只能保證對偶問題的有限最優解。原問題松弛變量的檢驗數的倒數就是對偶問題的最優解。

對偶理論研究線性規劃中原問題和對偶問題之間的關系。線性規劃早期發展中開發簡化最重要的發現是對偶問題,即每壹個線性規劃問題(稱為原問題)都有壹個對應的對偶線性規劃問題(稱為對偶問題)。

擴展數據:

對偶問題的最優解:對偶問題的最優解可以直接從原問題的最終單純形表(最優單純形算子)中得到。原問題中松弛變量的檢驗數對應對偶問題的解(符號相反)。

使用單純形法時,每次叠代都能得到原問題的可行解x0和對偶問題的補充解y0,cx0=y0b。如果x0不是原問題的最優解,y0就不是對偶問題的可行解。最後壹步,叠代得到原問題的最優解x*和對偶問題的互補最優解y*,CX * = y * b. Y*是原問題的影子價格。

對偶問題:每壹個線性規劃問題都伴隨著另壹個線性規劃問題,稱為對偶問題。原線性規劃問題稱為原線性規劃問題,簡稱原問題。對偶問題具有許多重要特征,其變量可以提供原問題最優解的許多重要信息,有助於原問題的求解和分析。

百度百科-二元理論

  • 上一篇:盈虧的歷史故事
  • 下一篇:寧死不屈。為什麽有的人明知會輸,還是不投降?
  • copyright 2024歷史故事大全網