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

1第一章

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

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

目標函數約束條件4例2

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

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

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

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

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

37(1)38幾何意義分析

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

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

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

實質是：第一階段為原問題找出了一個基可行解。56例9第一階段原問題1.6第一階段605.2退化

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

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