算法設(shè)計(jì)與分析 課件 第八章 線性規(guī)劃

計(jì)算機(jī)算法設(shè)計(jì)與分析第八章

線性規(guī)劃學(xué)習(xí)目標(biāo)掌握線性規(guī)劃的一般形式、標(biāo)準(zhǔn)形式掌握求解線性規(guī)劃問題的單純性法掌握求解線性規(guī)劃問題的對(duì)偶單純性法

8.1線性規(guī)劃模型例8.1生產(chǎn)計(jì)劃問題。某工廠生產(chǎn)甲、乙兩種產(chǎn)品，銷售后的利潤(rùn)分別為4千元/件與3千元/件。生產(chǎn)甲產(chǎn)品每件需要A、B兩種原材料均為1噸；生產(chǎn)乙產(chǎn)品每件需要A、C兩種原材料分別為2噸和1噸。若工廠A、B、C三種原材料分別有6噸，4噸和2噸，問該廠應(yīng)如何安排生產(chǎn)，才能使總利潤(rùn)最大？解：建立數(shù)學(xué)模型。設(shè)該廠生產(chǎn)件甲產(chǎn)品和件乙產(chǎn)品時(shí)總利潤(rùn)z最大，則x1，x2應(yīng)滿足：

8.1線性規(guī)劃模型從以上的例子可以看出：目標(biāo)函數(shù)和約束條件都是線性形式。下面給出線性規(guī)劃問題的一般形式：

8.2線性規(guī)劃標(biāo)準(zhǔn)形

8.2線性規(guī)劃標(biāo)準(zhǔn)形

8.2線性規(guī)劃標(biāo)準(zhǔn)形

8.3.4單純形表1.單純形法基本步驟單純形法的求解線性規(guī)劃問題的基本步驟如下：（1）確定初始的基可行解；（2）檢查當(dāng)前的基可行解，判斷若是最優(yōu)解或無最優(yōu)解，計(jì)算終止；否則做基變換，找一個(gè)非基變量換入，一個(gè)基變量換出，得到新的可行基和對(duì)應(yīng)的基可行解，且要求目標(biāo)函數(shù)的值減少（至少不能增加）；（3）重復(fù)步驟（2）。

8.3.4單純形表

8.3.4單純形表2.例8.8用單純性法求解下列線性規(guī)劃問題。解：列單純性表如下：所有檢驗(yàn)數(shù)均≥0，停止計(jì)算。最優(yōu)解為=(4,1,0,0,1)T，最優(yōu)值為-19。

8.3.4單純形表

8.4人工變量和兩階段法

8.4人工變量和兩階段法

8.4人工變量和兩階段法

8.4人工變量和兩階段法

8.4人工變量和兩階段法所有檢驗(yàn)數(shù)均≥0，停止計(jì)算。最優(yōu)解為(4,1,9,0,0)T，最優(yōu)值為-2。

8.6.3對(duì)偶單純形法

2.例8.12用對(duì)偶單純形法求解。解：將模型轉(zhuǎn)化為：列對(duì)偶單純形表如下：

8.6.3對(duì)偶單純形法

8.6.3對(duì)偶單純形法最終b列均為非負(fù)，檢驗(yàn)數(shù)也均為非負(fù)，迭代終止，問題的最優(yōu)解為(11/5,2/5,0,0,0)T,最優(yōu)值為28/5。

8.7整數(shù)線性規(guī)劃在線性規(guī)劃的實(shí)際問題中，有時(shí)要求最優(yōu)解是整數(shù)情況，例如要求的解是機(jī)器的臺(tái)數(shù)，人員的人數(shù)，物品的件數(shù)等。此時(shí)，如果僅僅是將所求的進(jìn)行最優(yōu)解四舍五入，這樣可能不是可行解，或者是可行解但不是最優(yōu)解。因此，對(duì)這樣的問題要進(jìn)一步的探討。這類問題，稱之為整數(shù)線性規(guī)劃（IntegerLinearProgramming，ILP）。在整數(shù)規(guī)劃中，要求所有的變量都限制為非負(fù)整數(shù)，就稱為純整數(shù)規(guī)劃或全整數(shù)規(guī)劃。如果僅一部分變量限制為非負(fù)整數(shù)，則稱為混合整數(shù)規(guī)劃。整數(shù)規(guī)劃中還有一種最特殊的情況，就是限定變量只能取0或1，就稱為0-1規(guī)劃。下面主要討論全整數(shù)規(guī)