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

關(guān)于線性規(guī)劃與單純形法第1頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第二章線性規(guī)劃與單純形法第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型第2節(jié)圖解法第3節(jié)解第4節(jié)單純形法原理及其計(jì)算步驟第5節(jié)人工變量法第6節(jié)小結(jié)第2頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型一、規(guī)劃如何合理地利用有限的人力、物力、財(cái)力等資源，以便得到最好的經(jīng)濟(jì)效果。第3頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例1：用一塊邊長(zhǎng)為a的正方形鐵皮做一個(gè)容器，應(yīng)該如何裁剪，使做成的容器的容積最大（如下圖所示）。ax第4頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例1：解：設(shè)在鐵皮四個(gè)角上剪去四個(gè)邊長(zhǎng)各為x的正方形

V=(a-2x)·(a-2x)·x→max

滿足x≤a/2x≥0第5頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例2：某企業(yè)計(jì)劃生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，都要分別在A，B，C，D四種不同設(shè)備上加工。按工藝資料規(guī)定，生產(chǎn)每件產(chǎn)品Ⅰ需占用各設(shè)備分別為2，1，4，0（小時(shí)），生產(chǎn)每件產(chǎn)品Ⅱ需占用各設(shè)備分別為2，2，0，4（小時(shí)）。已知各設(shè)備計(jì)劃期內(nèi)用于生產(chǎn)這兩種產(chǎn)品的能力分別為12，8，16，12（小時(shí)），又知每生產(chǎn)一件產(chǎn)品Ⅰ，企業(yè)能獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ，企業(yè)能獲利3元。問：該企業(yè)應(yīng)如何安排生產(chǎn)兩種產(chǎn)品各多少件，使企業(yè)的利潤(rùn)收入最大。第6頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例2：解：設(shè)Ⅰ、Ⅱ兩種產(chǎn)品在計(jì)劃期內(nèi)的產(chǎn)量分別為x1、x2z=2x1+3x2→max2x1+2x2≤12x1+2x2≤8滿足4x1≤164x2≤12x1，x2≥0表示形式第7頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型二、數(shù)學(xué)規(guī)劃研究在一些給定的條件下，求所考察函數(shù)在某種意義下的極值問題。第8頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型特征（1）決策變量（2）約束條件（3）目標(biāo)函數(shù)第9頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型三、線性規(guī)劃問題特征（三要素）（1）決策變量：?jiǎn)栴}中的未知量（2）目標(biāo)函數(shù)：?jiǎn)栴}要達(dá)到的目標(biāo)（最大或最?。硎緸闆Q策變量的線性函數(shù)（3）約束條件：表示為含決策變量的一組互不矛盾的線性等式或線性不等式的函數(shù)約束和決策變量的非負(fù)約束第10頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型V=(a-2x)·(a-2x)·x→maxx≤a/2x≥0z=2x1+3x2→max2x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1，x2≥0第11頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題數(shù)學(xué)模型的形式（1）一般形式第12頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型（2）簡(jiǎn)寫形式（3）向量形式（4）矩陣形式第13頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例3：寫出例2數(shù)學(xué)模型的一般形式和矩陣形式。一般形式矩陣形式

maxz=2x1+3x22x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1，x2≥0解第14頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型四、線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)形式（標(biāo)準(zhǔn)型）目標(biāo)函數(shù)求最大值函數(shù)約束條件全為等式?jīng)Q策變量全為非負(fù)函數(shù)約束條件右端項(xiàng)全為非負(fù)第15頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型五、線性規(guī)劃的非標(biāo)準(zhǔn)型如何轉(zhuǎn)化為標(biāo)準(zhǔn)型目標(biāo)函數(shù)求最小值：令z′＝-z函數(shù)約束條件為不等式：‘≤’：在函數(shù)約束條件左端加非負(fù)的松弛變量‘≥’：在函數(shù)約束條件左端減非負(fù)的松弛變量松弛變量在目標(biāo)函數(shù)中的系數(shù)全為‘0’決策變量為負(fù)值：令xj′＝-xj，xj′≥0決策變量取值無約束：令xj

＝xj′-xj〞，xj′≥0，xj〞≥0函數(shù)約束條件右端項(xiàng)（bi）為負(fù)值：函數(shù)約束條件兩端同乘‘-1’第16頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型要求：將下列線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)型。例4：minz=x1+2x2+3x3-2x1+x2+x3≤9-3x1+x2+2x3≥43x1-2x2-3x3=-6x1≤0，x2≥0，x3取值無約束第17頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例4：解：令

maxz′=x1′-2x2-3x3′+3x3〞+0x4+0x52x1′+x2+x3′-x3〞+x4=93x1′+x2+2x3′-2x3〞-x5=43x1′+2x2+3x3′-3x3〞=6x1′，x2，x3′，x3〞，x4，x5≥0第18頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例5：minz=-x1+2x2-3x3x1+x2+x3≤7x1-x2+x3≥2-3x1+x2+2x3=5x1，x2≥0，x3無約束第19頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例5：解：令

maxz′=x1-2x2-3x3′+3x3〞x1+x2+x3′-x3〞+x4=7x1-x2+x3′-x3〞-x5=2-3x1+x2+2x3′-2x3〞=5x1，x2，x3′，x3〞，x4，x5≥0第20頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例6：maxz=2x1+3x2+5x3x1+x2-x3≥-5-6x1+7x2-9x3=16∣19x1-7x2＋5x3∣≤13x1，x2≥0，x3無約束第21頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型例6：解：令

maxz=2x1+3x2+5x3′-5x3〞-x1-x2+x3′-x3〞+x4=5-6x1+7x2-9x3′+9x3〞=1619x1-7x2+5x3′-5x3〞+x5=13-19x1+7x2-5x3′+5x3〞+x6=13x1，x2，x3′，x3〞，x4，x5，x6≥0第22頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五作業(yè)2-1作業(yè)2-1：將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)型。1、minz=5x1-2x2+4x3-3x4-x1+2x2-x3+4x4=-2-x1+3x2+x3+x4≤142x1-x2+3x3-x4≥2x1無約束，x2≤0，x3，x4≥02、minz=x1+2x2+4x32x1+x2+3x3＝20∣3x1+x2+4x3∣≤25x1，x2≥0，x3≤0第23頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第2節(jié)解線性規(guī)劃問題數(shù)學(xué)模型的標(biāo)準(zhǔn)型（以’一般形式’表示）第24頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第2節(jié)解一、線性規(guī)劃問題解的概念可行解：滿足函數(shù)約束條件和非負(fù)約束條件的解，全部可行解的集合稱為可行域最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解，對(duì)應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值第25頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第2節(jié)解基：設(shè)A是約束方程組的m×n階系數(shù)矩陣，B是矩陣A中m×m階非奇異子矩陣，稱B是線性規(guī)劃問題的一個(gè)基基向量：基B中每一個(gè)列向量Pj非基向量：A中其余列向量Pj（不在B中）基變量：與基向量Pj對(duì)應(yīng)的決策變量xj非基變量：與非基向量對(duì)應(yīng)的決策變量基解基可行解：滿足非負(fù)約束條件的基解可行基：對(duì)應(yīng)于基可行解的基克萊姆法則非奇異矩陣解的關(guān)系第26頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第2節(jié)解非奇異矩陣：行列式不等于0的矩陣。克萊姆法則：如果線性方程組

a11x1+a12x2+‥‥+a1mxm=b1a21x1+a22x2+‥‥+a2mxm=b2‥‥am1x1+am2x2+‥‥+ammxm=bm

的系數(shù)行列式不等于0，則方程組有唯一解。第27頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第2節(jié)解二、線性規(guī)劃問題解的關(guān)系最優(yōu)解第28頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第2節(jié)解例7：寫出例2的標(biāo)準(zhǔn)型，并指出基、基變量、基解、基可行解和可行基。第29頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第2節(jié)解例7：標(biāo)準(zhǔn)型maxz=2x1+3x22x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1，x2≥0maxz=2x1+3x22x1+2x2+x3=12x1+2x2+x4=84x1+x5=164x2+x6=12x1-6≥0圖解法第30頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第2節(jié)解例8：求下述線性規(guī)劃的所有基解、基可行解及最優(yōu)解。

maxz=3x1+x2+3x3x1+x2+x3＝2x1+2x2+4x3＝6x1，x2，x3≥0第31頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五作業(yè)2-2作業(yè)2-2：求下列線性規(guī)劃的所有基解、基可行解及最優(yōu)解。1、maxz=2x1+3x2+4x3+7x4

2x1+3x2-x3-4x4＝8-x1+2x2-6x3+7x4＝3x1，x2，x3，x4≥02、maxz=-5x1+2x2-3x3+6x4x1+2x2+3x3+4x4＝72x1+x2+x3+2x4＝3x1，x2，x3，x4≥0第32頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法一、圖解法適用條件：適用于求解只有兩個(gè)決策變量的線性規(guī)劃問題特點(diǎn)（1）不必將線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)型（2）直觀性強(qiáng)，計(jì)算方便第33頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法例9：用圖解法求解下述線性規(guī)劃問題。

maxz=2x1+3x2x1+2x2≤84x1≤164x2≤12x1，x2≥0第34頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法例9：標(biāo)出約束條件(0,0)(0,3)(2,3)(4,2)(4,0)第35頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法例9：標(biāo)出目標(biāo)函數(shù)目標(biāo)函數(shù)z唯一最優(yōu)解第36頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法二、圖解法的求解步驟建立二維坐標(biāo)系將約束條件表示在坐標(biāo)系中，以確立可行域ⅰ畫出每個(gè)函數(shù)約束的約束邊界，用原點(diǎn)判斷直線的哪一邊是約束條件所允許的ⅱ找出所有約束條件都同時(shí)滿足的區(qū)域，即可行域?qū)⒛繕?biāo)函數(shù)繪制在坐標(biāo)系中，并標(biāo)出變化的方向ⅰ給定目標(biāo)函數(shù)一個(gè)特定的值k，畫出目標(biāo)函數(shù)特定線，當(dāng)k變化時(shí)，目標(biāo)函數(shù)特定線將平行移動(dòng)ⅱ對(duì)于目標(biāo)函數(shù)最大（小）化的問題，找出目標(biāo)函數(shù)增加（減少）的方向，目標(biāo)函數(shù)最后離開可行域的點(diǎn)是最優(yōu)解確定最優(yōu)解第37頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法三、圖解法解的類型唯一最優(yōu)解：僅有一點(diǎn)使目標(biāo)函數(shù)值取得最大（小）值無窮多（多重）最優(yōu)解：線段（射線）上任意一點(diǎn)都使目標(biāo)函數(shù)值取得相同的最大（?。┲禑o界解：可行域無界，目標(biāo)函數(shù)值可以增大到無窮大無可行解：可行域?yàn)榭占療o界解和無可行解統(tǒng)稱為無最優(yōu)解第38頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法要求：用圖解法求解下列線性規(guī)劃問題。例10：maxz=2x1+4x2x1+2x2≤84x1≤164x2≤12x1，x2≥0第39頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法例10：目標(biāo)函數(shù)maxz=2x1+4x2

z多重最優(yōu)解第40頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法例11：maxz=2x1+3x24x1≤16x1，x2≥0無界解第41頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法例12：maxz=2x1+3x22x1+2x2≤12x1+2x2≥14x1，x2≥0無可行解第42頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法四、圖解法解的特點(diǎn)當(dāng)可行域非空集時(shí)，可行域必是有界或無界凸多邊形。（凸集：集合C中任意兩個(gè)點(diǎn)a和b，其連線上所有點(diǎn)也必為集合C中的點(diǎn)。）若可行域有界，則目標(biāo)函數(shù)一定可以在可行域的頂點(diǎn)上達(dá)到最優(yōu)；若可行域無界，則可能無最優(yōu)解，也可能有最優(yōu)解，若有也必定在某頂點(diǎn)上達(dá)到。第43頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法線性規(guī)劃問題的每個(gè)基可行解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn)。線性規(guī)劃問題的最優(yōu)解在頂點(diǎn)上達(dá)到，則一定存在一個(gè)基可行解是最優(yōu)解。若有唯一最優(yōu)解，則一定在可行域的某個(gè)頂點(diǎn)處得到；若有兩個(gè)頂點(diǎn)同時(shí)達(dá)到最優(yōu)解，則兩個(gè)頂點(diǎn)之間線段上的任意一點(diǎn)都是最優(yōu)解，既有無窮多最優(yōu)解。線性規(guī)劃問題有最優(yōu)解，則解題思路：找出可行域的頂點(diǎn)，計(jì)算頂點(diǎn)處的目標(biāo)函數(shù)值，比較各頂點(diǎn)的目標(biāo)函數(shù)值，值最大（?。┑捻旤c(diǎn)為最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一。第44頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法例13：下列哪一個(gè)圖是凸集？ABCD凸多邊形第45頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法例9圖解：目標(biāo)函數(shù)z第46頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法例10圖解：目標(biāo)函數(shù)maxz=2x1+4x2

z頂點(diǎn)最優(yōu)第47頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法要求：用圖解法求解下列線性規(guī)劃問題。例14：minz=2x1-x2-2x1+x2≤2x1-2x2≤1x1，x2≥0無界可行域第48頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法例15：1、maxz=x1+x2-2x1+x2≤4x1-x2≤2x1，x2≥02、maxz=x1+2x2x1+2x2≤84x1≤164x2≤12x1，x2≥0第49頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第3節(jié)圖解法例15：2、(0,0)(0,3)(2,3)(4,2)(4,0)第50頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五作業(yè)2-3作業(yè)2-3：用圖解法求解下列線性規(guī)劃問題。1、maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1，x2≥02、maxz=4x1+8x22x1+2x2≤10-x1+x2≥8x1，x2≥03、maxz=3x1+9x2x1+3x2≤22-x1+x2≤4x2≤62x1-5x2≤0x1，x2≥04、maxz=2x1+2x2x1-x2≥

-1-0.5x1+x2≤2x1，x2≥0第51頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟例16：求解下述線性規(guī)劃問題。

maxz=2x1+3x2x1+2x2≤84x1≤164x2≤12x1，x2≥0第52頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟例16：解：方法一：圖解法z*=2x1+3x2=14(0,3)(2,3)(4,0)(0,0)Q4Q3Q1→X*第53頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟例16：解：方法二：確定所有基解、基可行解及最優(yōu)解轉(zhuǎn)化為標(biāo)準(zhǔn)型

maxz=2x1+3x2x1+2x2+x3=84x1+x4=164x2+x5=12x1-5≥0第54頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟例16：解：方法三：確定部分基可行解及最優(yōu)解轉(zhuǎn)化為標(biāo)準(zhǔn)型

maxz=2x1+3x2x1+2x2+x3=84x1+x4=164x2+x5=12x1-5≥0第55頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟一、單純形法的解題思路從某一基可行解開始，轉(zhuǎn)化到另一個(gè)相鄰的基可行解，并且使相應(yīng)的目標(biāo)函數(shù)值有改進(jìn)。即從可行域的一個(gè)頂點(diǎn)沿約束邊界轉(zhuǎn)換到可行域的另一個(gè)相鄰的且使目標(biāo)函數(shù)值有改進(jìn)的頂點(diǎn)，直到目標(biāo)函數(shù)值到達(dá)最優(yōu)時(shí)的頂點(diǎn)為止。第56頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟兩個(gè)基可行解相鄰：在基變量集合中，除了一個(gè)基變量以外，其他基變量全是相同的，只是數(shù)值可能不相同而已。第57頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟二、單純形法的含義單純形法是一種迭代算法，首先找到一個(gè)初始基可行解，然后判斷它是否為最優(yōu)解，如果是就停止迭代，否則，按照一定的法則，再找到一個(gè)更好且與當(dāng)前基可行解相鄰的基可行解，再進(jìn)行判斷，直到找不到更好的基可行解或判斷問題無解為止。第58頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟三、單純形法的解題步驟1、找出初始可行基，確定初始基可行解，建立初始單純形表。第59頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟例：線性規(guī)劃問題數(shù)學(xué)模型的某種標(biāo)準(zhǔn)形式第60頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟初始單純形表c1…cmcm+1…cncBxBbx1…xmxm+1…xnc1x1b11…0a1,m+1

…a1,nc2x2b20…0a2,m+1…a2,n………………………cmxmbm0…1am,m+1…am,n0…0…第61頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟2、檢驗(yàn)各非基變量xj（j=m+1，m+2，…，n）的檢驗(yàn)數(shù)δj，若δj≤0，則已得最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入3。3、在δj＞0（j=m+1，m+2，…，n）中，若有某個(gè)δk對(duì)應(yīng)的xk的系數(shù)列向量Pk≤0，則此線性規(guī)劃問題存在無界解，停止計(jì)算，否則轉(zhuǎn)入4。4、根據(jù)，確定xk為換入變量，通過，計(jì)算確定xl為換出變量，轉(zhuǎn)入5。第62頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟5、以alk為主元素進(jìn)行迭代（高斯消去法），把xk所對(duì)應(yīng)的列向量

將xB列中xl的換為xk，得到新的單純形表，重復(fù)2～5，直至終止。變換為單純形法求解例16第63頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟高斯消去法的基本代數(shù)運(yùn)算：一行乘以一個(gè)數(shù)一行乘上一個(gè)數(shù)加到另外一行中去第64頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟例16：解：方法四：?jiǎn)渭冃畏ㄞD(zhuǎn)化為標(biāo)準(zhǔn)型

maxz=2x1+3x2x1+2x2+x3=84x1+x4=164x2+x5=12x1-5≥0第65頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟例17：用單純形法求解下述線性規(guī)劃問題。

maxz=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1，x2≥0第66頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第4節(jié)單純形法原理及其計(jì)算步驟例17：解：轉(zhuǎn)化為標(biāo)準(zhǔn)型

maxz=2x1+x25x2+x3=156x1+2x2+x4=24x1+x2+x5=5x1，x2，x3，x4，x5≥0第67頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五作業(yè)2-4作業(yè)2-4：用單純形法求解下列線性規(guī)劃問題。1、maxz=5x1+2x2+3x3-x4+x5x1+2x2+2x3+x4=83x1+4x2+x3+x5=7x1，x2，x3，x4，x5≥02、minz=-5x1-4x2x1+2x2≤62x1-x2≤45x1+3x2≤15x1，x2≥0第68頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第5節(jié)人工變量法例18：求解下述線性規(guī)劃問題。

maxz=-3x1+x3x1+x2+x3≤4-2x1+x2-x3≥13x2+x3=9x1，x2，x3≥0第69頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第5節(jié)人工變量法例18：解：標(biāo)準(zhǔn)型第70頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第5節(jié)人工變量法標(biāo)準(zhǔn)型人為構(gòu)造單位矩陣第71頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第5節(jié)人工變量法例18：線性規(guī)劃問題的最后形式第72頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第5節(jié)人工變量法一、人工變量法的解題思路線性規(guī)劃問題中不存在現(xiàn)成的可行基，為了求一個(gè)初始可行基和初始基可行解，在每個(gè)約束方程中人為地加上一個(gè)變量（人工變量），使約束方程組的系數(shù)矩陣中產(chǎn)生初始基。第73頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第5節(jié)人工變量法二、人工變量法的含義為了確保引入人工變量以后新的線性規(guī)劃問題與原線性規(guī)劃問題求解的一致性：在最優(yōu)解中人工變量取值必須為零；令人工變量的系數(shù)為-M（M>0，表示充分大的數(shù)），“-M”稱為“罰因子”，表示只要人工變量取值大于零，目標(biāo)函數(shù)就不可能達(dá)到最大值。第74頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第5節(jié)人工變量法三、人工變量法的解題步驟將原問題轉(zhuǎn)化為標(biāo)準(zhǔn)型對(duì)‘＝’或‘≥’的約束條件添加人工變量，直至構(gòu)造出單位矩陣，且人工變量在目標(biāo)函數(shù)中的系數(shù)為‘-M’，建立初始單純形表按照‘單純形法’的解題步驟2～5求解人工變量法求解例18第75頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第5節(jié)人工變量法例18：解：第76頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第5節(jié)人工變量法例19：用人工變量法求解下述線性規(guī)劃問題。

maxz=2x1+x2x1+x2≤22x1+2x2≥6x1，x2≥0第77頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第5節(jié)人工變量法例19：解：標(biāo)準(zhǔn)型并添加人工變量

maxz=2x1+x2-Mx5x1+x2+x3=22x1+2x2-x4+x5=6x1，x2，x3，x4，x5≥0第78頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第5節(jié)人工變量法小結(jié)（1）將線性規(guī)劃化為標(biāo)準(zhǔn)型后，對(duì)‘＝’或‘≥’的約束條件添加人工變量（若約束條件系數(shù)矩陣A中已有k個(gè)單位列向量，只要引入m-k個(gè)人工變量，使它們與原來的k個(gè)單位列向量合成單位矩陣）（2）在最優(yōu)解中，若人工變量大于0，則原問題無可行解第79頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五作業(yè)2-5作業(yè)2-5：用人工變量法求解下列線性規(guī)劃問題。1、maxz=3x1-x2-x3x1-2x2+x3≤11-4x1+x2+2x3≥32x1-x3=-1x1，x2，x3≥02、minz=-x1-3x2+x3x1+x2+2x3+x4=4-x1+x3-x5=4x3-x6=3x1，x2，x3，x4，x5，x6≥0第80頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)第81頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)二、單純形表中解的表示形式1、唯一最優(yōu)解：最終單純形表中，所有非基變量檢驗(yàn)數(shù)δj＜02、無窮多最優(yōu)解：最終單純形表中，某非基變量檢驗(yàn)數(shù)δj＝03、無界解：某檢驗(yàn)數(shù)δj＞0對(duì)應(yīng)變量的系數(shù)列向量Pk≤04、無可行解：線性規(guī)劃問題中添加人工變量后，最終單純形表中，基變量中含有非零的人工變量（＞0）第82頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)5、退化現(xiàn)象：用θ規(guī)則確定換出變量時(shí)，出現(xiàn)兩個(gè)以上相同的最小比值，使下一個(gè)單純形表中出現(xiàn)一個(gè)或多個(gè)基變量等于零。退化基可行解：一個(gè)或幾個(gè)基變量取值‘＝0’的基可行解退化基可行解出現(xiàn)的原因：模型中存在多余的約束，使多個(gè)基可行解對(duì)應(yīng)同一頂點(diǎn)第83頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)退化基可行解的處理規(guī)則：出現(xiàn)退化基可行解，可能導(dǎo)致從某個(gè)基開始，經(jīng)過若干次迭代后又回到原來的基，即單純形法出現(xiàn)了循環(huán)，永遠(yuǎn)達(dá)不到最優(yōu)解，導(dǎo)致計(jì)算失敗。為避免出現(xiàn)死循環(huán)，法則如下：選擇換入變量時(shí)，若有幾個(gè)正的檢驗(yàn)數(shù)具有相同的最大值，則選擇下標(biāo)最小的對(duì)應(yīng)的非基變量作為換入變量選擇換出變量時(shí)，若按θ規(guī)則計(jì)算，有幾個(gè)比值同時(shí)達(dá)到最小，則選擇下標(biāo)最小的對(duì)應(yīng)的基變量作為換出變量第84頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)例20：下列表格是求線性規(guī)劃問題的單純形表，試說明解的情況。1、最終表23000CBxBbx1x2x3x4x5203x1x5x24421001/4000-21/21011/2-1/8000-3/2-1/80第85頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)2、最終表32-1000CBxBbx1x2x3x4x5x6023x4x2x129/56/521/500-11-1/58/501101/5-3/510001/52/500-30-10第86頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)3、中間表（最終表）4

5

0

0

0CBxBbx1x2x3x4x5000x3x4x57234-1100-1-50107

-300145000第87頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)4、中間表（最終表）4

3

0

0

0CBxBbx1x2x3x4x5000x3x4x57234-1100-1-50107

-300143000第88頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)5、最初表33200CBxBbx1x2x3x4x500x4x512-13-1102-110133200第89頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)6、中間表230000CBxBbx1x2x3x4x5x60203x3x1x5x22283001-201/210010-1/2000-412010001/4000-201/4第90頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)三、單純形法對(duì)給定的線性規(guī)劃問題，首先化為標(biāo)準(zhǔn)型，選取或構(gòu)造一個(gè)單位矩陣作為基矩陣，求出初始基可行解并列出初始單純形表。（若線性規(guī)劃問題的標(biāo)準(zhǔn)型為目標(biāo)函數(shù)最小化，則最優(yōu)解判別規(guī)則為：所有檢驗(yàn)數(shù)δj≥0）第91頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五單純形法計(jì)算步驟框圖第92頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)例21：用單純形法求解下述線性規(guī)劃問題，并說明解的情況。

maxz=2.5x1+x23x1+5x2≤155x1+2x2≤10x1，x2≥0第93頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)例21：解：maxz=2.5x1+x23x1+5x2+x3=155x1+2x2+x4=10x1，x2，x3，x4≥0第94頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五作業(yè)2-6作業(yè)2-6：求解下列線性規(guī)劃問題，并說明解的情況。1、maxz=6x1+4x2-x1+2x2≤43x1+2x2≤142x1-x2≤4x1，x2≥02、maxz=2x1-x2+2x3x1+x2+x3≥6-2x1+x3≥22x2-x3≥0x1，x2，x3≥0第95頁(yè)，共101頁(yè)，2022年，5月20日，18點(diǎn)43分，星期五第6節(jié)小結(jié)例22：下表為求某最大化線性規(guī)劃問題的最終單純形表，其中x4，x5為松弛變量，試寫出該問題的最優(yōu)解。bx1x2x3x4x5240-11311-1