正文內容

運籌學線性規劃的對偶問題(編輯修改稿)

2026-06-19 22:15 本頁面

　

【文章內容簡介】）為對偶問題的最優解。綜上，一對對偶問題的解必然下列情況之一：原問題和對偶問題都有解，且目標函數值相等一個問題具有無界解，另一個問題無可行解一個問題無可行解 ,另一個問題或具有無界解或無可行解 6 .互補松弛定理若 X（ 0）和 Y（ 0）分別是原問題和對偶問題的可行解，則 X（ 0）和 Y（ 0）都是最優解的充要條件是 Y（ 0） Xs=0和 Ys X（ 0） =0。其中 Xs=(xs1,xs2,…,x sm)T， xs1,xs2,…,x sm 是原問題的松弛變量 . Ys=(ys1,ys2,…,y sn)T ， ys1,ys2,…,y sn是對偶問題的剩余變量。松弛的含義是如果有某個原始最優解 X(0)，使得對某個下標 j，滿足 X(0)j0(原問題是松的 )，那么與之對應的對偶約束在最優的情況下為等式，即 ysj=0(對偶問題是緊的 )；如果原始約束在最優情況下對某個下標 i滿足 x(0)si0(原問題是松的 )，那么，對偶最優解中與之對應的 y(0)i=0(對偶問題是緊的 )。證明 : 原問題對偶問題 max z =CX min ω =Yb AX+ Xs =b YAYs=C X, Xs ≥0 Y, Y s≥0 z =(YAYs)X=YAXYsX ω =Y(AX+Xs)=YAX+YXs 若 Y(0)Xs=0和 YsX(0) =0, 則 Y(0)b=Y(0)AX(0)=CX(0)，根據性質 4可知 X(0),Y(0)為最優解。反之 , X(0),Y(0)為最優解 , 則 CX(0)=Y(0)AX(0)= Y(0)b 可知必有 Y(0)Xs=0和 YsX(0) =0。證畢 7. 原問題的檢驗數對應對偶問題的一個基本解設 B是原問題的一個可行基 ,有 A=(B,N) max z=CBXB+CNXN min ω =Yb BXB+NXN+XS=b YBYs1=CB XB, XN， Xs≥0 YNYs2=CN Y, Ys1， Ys2≥0 YS=（ YS1， YS2）證明 : 原問題對偶問題 max z =CX min ω =Yb AX+ Xs =b YAYs=C X, Xs ≥0 Y, Y s≥0 當原問題有解 XB=B1b， XN=0時 ,檢驗數為： CNCBB1N， CBB1 令 Y=CBB1，代入對偶問題的約束條件得： Ys1=0， Ys2= CNCBB1N 則（ Y， Ys1， Ys2）為對偶問題的基本解證畢檢驗數性質：原問題檢驗數行對應其對偶問題的一個基解 , 關系如下 : XB XN Xs 0 CNCBB1N CBB1 Ys1 Ys2 Y 例 4 已知線性規劃問題 max z = x1 + x2 x1 + x2 + x3 ≤ 2 2x1 + x2 x3 ≤ 1 x1 , x2 , x3≥0 試用對偶理論證明上述線性規劃問題無最優解。證 : 首先看到該問題存在可行解，例如 X = (0,0,0) 而上述問題的對偶問題為 minω = 2y1 + y2 y1 2y2 ≥ 1 y1 + y2 ≥ 1 y1 y2 ≥ 0 y1 ,y2 ≥ 0 由第一約束條件可知對偶問題無可行解，因而無最優解。由此原問題也無最優解。例 5 已知線性規劃問題

點擊復制文檔內容

教學課件相關推薦

運籌學線性規劃的對偶問題(編輯修改稿)

[高等教育]4線性規劃的對偶問題-資料下載頁

運籌學對偶靈敏ppt課件-資料下載頁

運籌學胡運權-第4版-第二章--線性規劃的對偶理論及靈敏度分析-資料下載頁

運籌學第2章對偶理論-資料下載頁

[精選]生產運籌學--線性規劃及單純形法ppt66頁-資料下載頁

whut運籌學-7矩陣表示對偶問題理論影子價格-資料下載頁

運籌學課件第5章整數線性規劃-第1-4節-資料下載頁

運籌學——整數規劃與分配問題-資料下載頁

[理學]chapter02線性規劃的對偶理論-資料下載頁

線性規劃問題-資料下載頁

第二講1線性規劃及其對偶-資料下載頁

運籌學-動態規劃-資料下載頁

運籌學課件第1章線性規劃與單純形法-第6節-資料下載頁

運籌學課件第1章線性規劃與單純形法-第2節-資料下載頁

332簡單的線性規劃問題-資料下載頁

運籌學線性規劃的對偶問題(完整版)

運籌學線性規劃的對偶問題(更新版)

運籌學線性規劃的對偶問題(專業版)

運籌學線性規劃的對偶問題(留存版)