線性規(guī)劃的對(duì)偶理論課件

線性規(guī)劃的對(duì)偶理論對(duì)偶問題的提出

原問題與對(duì)偶問題的關(guān)系

對(duì)偶單純形法

一、對(duì)偶問題的提出

對(duì)于上節(jié)中所介紹的資源利用問題考慮資源擁有者為了實(shí)現(xiàn)一定的收入目標(biāo)，將其所擁有的資源出售，則需給每一種資源定價(jià)。

表示出售單位數(shù)量的第i種資源的價(jià)格，若將所有資源出售，則得到的總收入為

在做出決策時(shí)，考慮出售資源的收入不應(yīng)該低于生產(chǎn)所獲得的收入，則

資源擁有者出售每一種資源的最低估價(jià)，可通過求解線性規(guī)劃問題而得到

這表明，從不同角度考慮同一問題可得到相互聯(lián)系的線性規(guī)劃模型，這就是線性規(guī)劃的對(duì)偶問題。

一般地，稱線性規(guī)劃問題（I)

和(Ⅱ)互為對(duì)偶問題的標(biāo)準(zhǔn)形式。（I)(Ⅱ)

①對(duì)偶問題的變換關(guān)系為對(duì)稱關(guān)系時(shí)，根據(jù)原問題的系數(shù)矩陣就能容易地寫出對(duì)偶問題。如表5.2.1。表5.2.1yj

x1

x2

…

xn，

原關(guān)系

minW對(duì)偶關(guān)系

maxZ

②當(dāng)原問題的約束條件中含有等式約束方程時(shí)，即變換關(guān)系為非對(duì)稱形式，可按以下步驟求對(duì)偶問題：

首先將每一個(gè)等式約束方程都用兩個(gè)不等式約束方程代替，所有約束方程都變?yōu)橥?hào)不等式約束。

按對(duì)稱形式變換關(guān)系（表5.2.1）寫出它的對(duì)偶問題。

例：對(duì)于線性規(guī)劃問題

可以按下述步驟求出其對(duì)偶問題：第1步：將等式約束分解為不等式約束，變?yōu)?/p>

第2步，設(shè)和分別代表對(duì)應(yīng)的對(duì)偶變量，按對(duì)稱形式變換關(guān)系寫出它的對(duì)偶問題

上述線性規(guī)劃問題的各式，經(jīng)過整理后得到

令，由于，可見不受正、負(fù)限制，將代入，可得到原線性規(guī)劃問題的對(duì)偶問題。

二、原問題與對(duì)偶問題的關(guān)系

線性規(guī)劃原問題與對(duì)偶問題之間的形式變換關(guān)系可以由表5.2.2予以概述。原問題（或?qū)ε紗栴}）

對(duì)偶問題（或原問題）

目標(biāo)函數(shù)

目標(biāo)函數(shù)

變

量

個(gè)數(shù)n≥0≤0無約束

約束方程

個(gè)數(shù)n≥≤=約束方程

個(gè)數(shù)m≤≥=變量

個(gè)數(shù)m≥0≤0無約束

約束方程右端項(xiàng)

目標(biāo)函數(shù)中變量的系數(shù)

目標(biāo)函數(shù)中變量的系數(shù)

約束方程右端項(xiàng)

表5.2.2

利用表5.2.2所描述的變換關(guān)系，可寫出任何一個(gè)線性規(guī)劃問題的對(duì)偶問題。譬如，對(duì)于線性規(guī)劃問題其對(duì)偶問題為

對(duì)偶問題的基本性質(zhì)

①對(duì)稱性：即對(duì)偶問題的對(duì)偶是原問題。

②弱對(duì)偶性：即若是原問題的可行解，是對(duì)偶問題的可行解，則存在關(guān)系：。

③無界性：若原問題（對(duì)偶問題）為無界解，則其對(duì)偶問題（原問題）無可行解。

④對(duì)偶定理：若原問題有最優(yōu)解，那么對(duì)偶問題也有最優(yōu)解，而且它們的最優(yōu)目標(biāo)值相等。

⑤松緊定理：若和分別為原問題與對(duì)偶問題的可行解，則它們?yōu)樽顑?yōu)解的充要條件為

⑥設(shè)原問題是

其對(duì)偶問題是

⑦互補(bǔ)松弛性：若和分別是原問題和對(duì)偶問題的可行解。那么，和，當(dāng)且僅當(dāng)和為最優(yōu)解。

則原問題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問題的一個(gè)基解，其對(duì)應(yīng)關(guān)系如表5.2.3。

0表5.2.3

三、對(duì)偶單純形法

基本思想若保持對(duì)偶問題的解是基可行解，而原問題在非可行解的基礎(chǔ)上，通過逐步迭代達(dá)到基可行解，這樣也就得到了最優(yōu)解。這種方法的優(yōu)點(diǎn)是原問題的初始解不一定是基可行解，可從非基可行解開始迭代。

基本原理對(duì)于原問題

設(shè)B是一個(gè)基，不失一般性,令，它對(duì)應(yīng)的基變量為。當(dāng)非基變量都為零時(shí)，可以得到。若在中至少有一個(gè)負(fù)分量，設(shè)，并且在單純形表的檢驗(yàn)數(shù)行中的檢驗(yàn)數(shù)都非正，即對(duì)偶問題保持可行解，它的各分量是:①對(duì)應(yīng)基變量的檢驗(yàn)數(shù)是

②對(duì)應(yīng)非基變量的檢驗(yàn)數(shù)是

每次迭代是將基變量中的負(fù)分量取出，去替換非基變量中的，經(jīng)過基變換，所有檢驗(yàn)數(shù)仍保持非正。從原問題來看，經(jīng)過每次迭代，原問題由非可行解往可行解靠近，當(dāng)原問題得到可行解時(shí)，便得到了最優(yōu)解。計(jì)算步驟

①列出初始單純形表，檢查b列中的各分量，若都為非負(fù)，且檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解。若b列中至少有一個(gè)負(fù)分量，檢驗(yàn)數(shù)保持非正，進(jìn)行以下計(jì)算。

②確定換出變量。按照法則

確定對(duì)應(yīng)的基變量為換出變量。

③確定換入變量。

若xj所在行有負(fù)系數(shù)，計(jì)算所對(duì)應(yīng)的非基變量xk為換入變量。

④以為主元素，按原單純形法迭代運(yùn)算，得新單純形表。

⑤重復(fù)①～④的步驟，直至求得最優(yōu)解。

例1：試用對(duì)偶單純形法求解如下線性規(guī)劃問題

首先將該問題化為-2-3-400CBXBbX1X2X3X4X500X4X5-3-4-1[-2]-21-131001-2-3-400初始單純形表，如表5.2.4所示表5.2.4b列各行為負(fù)，進(jìn)行迭代計(jì)算，確定換出變量故X3為換出變量。

故X1為換入變量。換入、換出變量所在列、行的交叉處“2”為主元項(xiàng)。進(jìn)行迭代運(yùn)算，得表5.2.5。

-2-3-400CBXBbX1X2X3X4X50-2X4X1-1201[-5/2]-1/21/23/210-1/2-1/20-4-10-1表5.2.5

從表5.2.5可看出，b列中仍有負(fù)分量，繼續(xù)迭代計(jì)算，重復(fù)上述步驟，得表5.2.6。

表5.2.6

-2-3-400CBXBbX1X2X3X4X5-3-2X2X1-2/511/50110-1/5