第一章線性規(guī)劃與單純形法

1第一章

線性規(guī)劃與單純形法2第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型1.1問題的提出例1

某工廠在計(jì)劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗以及資源的限制，如下表：?jiǎn)栴}：如何安排生產(chǎn)才能使工廠獲利最多？3線性規(guī)劃模型三個(gè)要素決策變量

目標(biāo)函數(shù)約束條件4例2

靠近某河流有兩個(gè)化工廠，流經(jīng)第一化工廠的河流流量為每天500萬立方米，在兩個(gè)工廠之間有一條流量為每天200萬立方米的支流。第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水2萬立方米，第二化工廠每天排放這種工業(yè)污水1.4萬立方米。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20％可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2％。這兩個(gè)工廠都需各自處理一部分工業(yè)污水。第一化工廠處理工業(yè)污水的成本是1000元/萬立方米，第二化工廠處理工業(yè)污水的成本是800元/萬立方米?，F(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個(gè)工廠總的處理工業(yè)污水費(fèi)用最小。工廠1工廠2500萬立方米200萬立方米5例3：下料問題

某工廠要做100套鋼架，每套有長2.9米、2.1米和1.5米的圓鋼組成，已知原料長7.4米，問應(yīng)如何下料使需用的原材料最省。方案1方案2方案3方案4方案5方案6方案7方案82.9m120101002.1m002211301.5m31203104合計(jì)7.47.37.27.16.66.56.36.0剩余料頭00.10.20.30.80.91.11.46線性規(guī)劃的一般模型技術(shù)系數(shù)價(jià)值系數(shù)資源系數(shù)例1

某工廠在計(jì)劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗以及資源的限制，如下表：?jiǎn)栴}：如何安排生產(chǎn)才能使工廠獲利最多？7價(jià)值系數(shù)技術(shù)系數(shù)資源系數(shù)34840x2x1A1.2線性規(guī)劃的圖解法1.畫可行域2.畫等值線3.找最優(yōu)解步驟惟一最優(yōu)解34840x2x1AB無窮多最優(yōu)解（多重最優(yōu)解）34840x2x1-2無可行解x1x2024無界解解的情況總結(jié)12有最優(yōu)解無最優(yōu)解惟一最優(yōu)解無窮多最優(yōu)解無可行解無界解圖解法的局限與啟示局限：只能求解兩個(gè)變量的線性規(guī)劃問題啟示:通過圖解法，能夠直觀的看到，如果線性規(guī)劃問題有最優(yōu)解，一定能夠在其頂點(diǎn)上達(dá)到最優(yōu)。131434840x2x1A惟一最優(yōu)解1534840x2x1AB無窮多最優(yōu)解（多重最優(yōu)解）16171.3線性規(guī)劃問題的標(biāo)準(zhǔn)形式我們規(guī)定的標(biāo)準(zhǔn)形式要求：目標(biāo)函數(shù)求極大值所有約束為等式約束條件右端項(xiàng)都大于等于零所有變量都大于等于零18練習(xí)19一般形式簡(jiǎn)寫形式向量形式矩陣形式201.4線性規(guī)劃問題解的概念可行解：滿足所有約束條件的解，稱為線性規(guī)劃問題的可行解。最優(yōu)解：使目標(biāo)函數(shù)值達(dá)到最優(yōu)的可行解?；涸O(shè)A是約束方程組的m×n維系數(shù)矩陣，其秩為m。B是矩陣中m階非奇異子矩陣，則稱B是線性規(guī)劃問題的一個(gè)基?；兞浚号c基向量對(duì)應(yīng)的變量。非基變量：與非基向量對(duì)應(yīng)的變量?；猓毫罘腔兞繛榱?，求解方程組,得到一個(gè)基解?；尚薪猓簼M足非負(fù)條件的基解?？尚谢簩?duì)應(yīng)于基可行解的基，為可行基。21例題思考非基變量取值是否為零？取值為零的變量是否一定為非基變量？大于零的變量是否是基變量？基變量的系數(shù)列向量是否一定線性無關(guān)？22解之間的關(guān)系23可行解基解非可行解基可行解例題2425第二節(jié)線性規(guī)劃問題的幾何意義2.1基本概念凸集：設(shè)K是n維歐式空間的一點(diǎn)集，若任意兩點(diǎn)的連線上的一切點(diǎn)都屬于K；則稱K為凸集。凸集凸集不是凸集極點(diǎn)26兩點(diǎn)連線上的點(diǎn)的數(shù)學(xué)表示方法27282.2幾個(gè)定理例題2930特殊情況有時(shí)目標(biāo)函數(shù)可能在多個(gè)頂點(diǎn)處達(dá)到最大值。這時(shí)在這些頂點(diǎn)的凸組合上也達(dá)到最大值。稱這種線性規(guī)劃問題有無限多個(gè)（無窮多個(gè)）最優(yōu)解。若可行域無界，則可能無最優(yōu)解，也可能有最優(yōu)解，若有也必定在某頂點(diǎn)上得到。31結(jié)論

線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，也可能為無界域，它們有有限個(gè)頂點(diǎn)，線性規(guī)劃問題的每個(gè)基可行解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn)；若線性規(guī)劃問題有最優(yōu)解，必在某頂點(diǎn)上得到。33第三節(jié)單純形法

單純形法的基本思路：根據(jù)問題的標(biāo)準(zhǔn)，從可行域中某個(gè)基可行解（一個(gè)頂點(diǎn)）開始，轉(zhuǎn)換到另一個(gè)基可行解（頂點(diǎn)），并且使目標(biāo)函數(shù)值達(dá)到最優(yōu)時(shí)，問題就得到了最優(yōu)解。343.1舉例35(1)(2)36幾何意義分析

37(1)38幾何意義分析

無窮多最優(yōu)解舉例39無界解舉例40入基，由方程組可知，可以無限增加，所以目標(biāo)函數(shù)可以趨向于無窮大，此時(shí)為無界解。413.2初始可行基的確定1.直接觀察2.對(duì)所有約束條件是“≤”的不等式，可在每個(gè)不等式左端引入一個(gè)松弛變量，變成標(biāo)準(zhǔn)型，從而得到一個(gè)初始基可行解。3.不存在單位陣時(shí)，采用人造基方法。423.3最優(yōu)性檢驗(yàn)與解的判別

（目標(biāo)函數(shù)求極大）最優(yōu)解判別定理：若非基變量的系數(shù)（檢驗(yàn)數(shù)）都小于等于零，則為最優(yōu)解。無窮多最優(yōu)解判別準(zhǔn)則：若非基變量的檢驗(yàn)數(shù)都小于等于零，且其中至少有一個(gè)為零，則線性規(guī)劃問題有無窮多個(gè)最優(yōu)解。無界解（無最優(yōu)解）判別定理：對(duì)于一個(gè)基可行解，若有一個(gè)檢驗(yàn)數(shù)大于零，且該檢驗(yàn)數(shù)對(duì)應(yīng)的所有系數(shù)都小于等于零，則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。433.4基變換（一個(gè)頂點(diǎn)變換到另一個(gè)頂點(diǎn)）換入變量確定：一般選擇絕對(duì)值最大的，但也可以任選或按最小號(hào)碼選。換出變量確定：最小比值原則。其原理是保證所有變量都為非負(fù)。443.5迭代（旋轉(zhuǎn)運(yùn)算）

利用系數(shù)的增廣矩陣進(jìn)行初等變換來實(shí)現(xiàn)。將主元素變?yōu)?。將入基變量所對(duì)應(yīng)的列向量變?yōu)閱挝幌蛄俊?5第四節(jié)單純形法的計(jì)算步驟4.1單純形表若線性規(guī)劃問題目標(biāo)函數(shù)為：約束條件為：增廣矩陣為：46根據(jù)增廣矩陣設(shè)計(jì)計(jì)算表473.1舉例484.2計(jì)算步驟49例題50單純形法的求解步驟目標(biāo)函數(shù)求極大初始可行基（單位陣）解的判別所有非基變量檢驗(yàn)數(shù)都小于零，得惟一最優(yōu)解所有非基變量檢驗(yàn)數(shù)都小于等于零，且至少有一個(gè)為零，得無窮多最優(yōu)解。如果有一個(gè)非基變量的檢驗(yàn)數(shù)大于零，而其在方程組中的系數(shù)都小于等于零，為無界解。迭代入基變量：檢驗(yàn)數(shù)大于零出基變量：最小比值原則方程組求解（矩陣初等行變換）目標(biāo)函數(shù)求極小初始可行基（單位陣）解的判別所有非基變量檢驗(yàn)數(shù)都大于零，得惟一最優(yōu)解所有非基變量檢驗(yàn)數(shù)都大于等于零，且至少有一個(gè)為零，得無窮多最優(yōu)解。如果有一個(gè)非基變量的檢驗(yàn)數(shù)小于零，而其在方程組中的系數(shù)都小于等于零，為無界解。迭代入基變量：檢驗(yàn)數(shù)小于零出基變量：最小比值原則方程組求解（矩陣初等行變換）5152例8第五節(jié)單純形法的進(jìn)一步討論531.大M法在一個(gè)線性規(guī)劃問題的約束條件中加入人工變量后，要求人工變量對(duì)目標(biāo)函數(shù)取值沒有影響，為此假定人工變量在目標(biāo)函數(shù)中的系數(shù)為（-M）（M為任意大的數(shù)），（若目標(biāo)函數(shù)值為求最小值，則人工變量在目標(biāo)函數(shù)中的系數(shù)為M）。這樣目標(biāo)函數(shù)要實(shí)現(xiàn)最大化時(shí)，必須把人工變量從基變量換出，否則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最大化。54例8原問題新問題552.兩階段法第一階段：不考慮原問題是否存在基可行解，給原線性規(guī)劃問題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)，要求其實(shí)現(xiàn)最小化。用單純形法求解此模型，若目標(biāo)函數(shù)值等于零，說明原問題有基可行解，可以進(jìn)行第二階段計(jì)算，否則原問題無可行解，應(yīng)停止計(jì)算。第二階段：將第一階段得到的最終表，除去人工變量，將目標(biāo)函數(shù)行的系數(shù)，換原問題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的初始表。

實(shí)質(zhì)是：第一階段為原問題找出了一個(gè)基可行解。56例9第一階段原問題1.6第一階段605.2退化

單純形法計(jì)算中，用最小比值原則確定出基變量時(shí)，有時(shí)存在兩個(gè)以上相同的最小比值，這樣在下一次迭代中就有一個(gè)或幾個(gè)基變量等于零，這就出現(xiàn)退化解。當(dāng)出現(xiàn)退化時(shí)，有時(shí)會(huì)出現(xiàn)計(jì)算過程的循環(huán)，永遠(yuǎn)達(dá)不到最優(yōu)解?？捎刹m特規(guī)則求解。迭代六次后，出現(xiàn)循環(huán)615.3檢驗(yàn)數(shù)的幾種表示形式62第六節(jié)應(yīng)用舉例63某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、D，數(shù)據(jù)如下表。問：該廠應(yīng)如何安排生產(chǎn)，使利潤收入為最大？例11：配料問題64

某部門在今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第四年每年年初需要投資，