1、單純形表法第1頁(yè)，共17頁(yè)，2022年，5月20日，3點(diǎn)19分，星期二（1）當(dāng)存在多個(gè) 時(shí)，始終選取下標(biāo)值為最小的變量作為換入變量；（2）當(dāng)計(jì)算值出現(xiàn)兩個(gè)以上相同的最小比值時(shí)，始終選取下標(biāo)值為最小的變量作為換出變量。3.無(wú)可行解的判別 本章第四節(jié)單純形法迭代原理中，講述了用單純形法求解時(shí)如何判別問題結(jié)局屬唯一最優(yōu)解、無(wú)窮多最優(yōu)解和無(wú)界解。當(dāng)線性規(guī)劃問題中添加人工變量后，無(wú)論用大M法或兩階段法，初始單純形表中的解因含非零人工變量，故實(shí)質(zhì)上是非可行解。當(dāng)求解結(jié)果出現(xiàn)所有時(shí)，如基變量中仍含有非零的人工變量（兩階段法求解時(shí)第一階段目標(biāo)函數(shù)值不等于零），表明問題無(wú)可行解。 第2頁(yè)，共17頁(yè)，2022年，

2、5月20日，3點(diǎn)19分，星期二例1-11 用單純形法求解線性規(guī)劃問題 解 用圖解法可看出本例無(wú)可行解。現(xiàn)用單純形法求解，在添加松馳變量和人工變量后，模型可寫成第3頁(yè)，共17頁(yè)，2022年，5月20日，3點(diǎn)19分，星期二以 為基變量列出初始單純形表，進(jìn)行迭代計(jì)算，過程見表1-11。表中當(dāng)所有 時(shí)，基變量中仍含有非零的人工變量， 故例1-12的線性規(guī)劃問題無(wú)可行解。 2 1 0 0 -M 基 0 2-M 61 1 1 0 02 2 0 -1 1 2+2M 1+2M 0 -M 0 2 2-M 21 1 1 0 00 0 -2 -1 1 0 -1 -2-2M -M 0第4頁(yè)，共17頁(yè)，2022年，5月

3、20日，3點(diǎn)19分，星期二二、單純形法小結(jié) 1. 對(duì)給定的線性規(guī)劃問題應(yīng)首先化為標(biāo)準(zhǔn)形式，選取或構(gòu)造一個(gè)單位矩陣作為基，求出初始基可行解并列出初始單純形表。對(duì)各種類型線性規(guī)劃問題如何化為標(biāo)準(zhǔn)形式及如何選取初始基變量可參見page35表1-14。 2 . 單純形法計(jì)算步驟的框圖見page35圖1-第5頁(yè)，共17頁(yè)，2022年，5月20日，3點(diǎn)19分，星期二一、修正單純形法的基本思想 運(yùn)用單純形法時(shí)，如果知道可行基的逆 就能利用 原始數(shù)據(jù)計(jì)算基變量的取值及檢驗(yàn)數(shù)，從而能夠確定一個(gè)基本可行解，并判斷它是否為最優(yōu)解。因此在整個(gè)計(jì)算過程中，只要保存原始數(shù)據(jù)和現(xiàn)行的逆即可。修正單純刑法的基本思想就是給定初

4、始基本可行基后，通過修改新基的逆 進(jìn)而完成其他運(yùn)算。在整個(gè)計(jì)算過程中，始終保持先行基的逆 。1-8修正單純形法第6頁(yè)，共17頁(yè)，2022年，5月20日，3點(diǎn)19分，星期二二、修正單純形發(fā)的步驟（1）求一個(gè)初始基B并求出它的逆 ，寫出基底描述J。（2）求單純形乘子 。（3）求 及 得到最優(yōu)解，停止；否則，記為k主元列，轉(zhuǎn)入（4）。（4）計(jì)算 得無(wú)界解，停止：否則轉(zhuǎn)入（5）。（5）求 第7頁(yè)，共17頁(yè)，2022年，5月20日，3點(diǎn)19分，星期二并記l為主元行。（6）構(gòu)造矩陣 用 左乘 得到新基的逆陣，將J中的第L個(gè)數(shù)改為k ，轉(zhuǎn)入（2）。第8頁(yè)，共17頁(yè)，2022年，5月20日，3點(diǎn)19分，星期二

5、 解 最簡(jiǎn)單做法是，在每一根原材料上截取2.9m，2.1m和1.5m的元鋼各一根組成一套，每根原材料省下料頭0.9m。為了做100套鋼架，需用原材料100根，有90米料頭,若改為用套裁，這可以節(jié)約原材料。下面有幾種套裁方案，都可以考慮采用，見表1-13。 1-9.單純形法應(yīng)用實(shí)例例1-12 合理利用線材問題現(xiàn)要做100套鋼架，每套用長(zhǎng)為2.9m，2.1m和1.5m的元鋼各一根，已知原料長(zhǎng)7.4m，問應(yīng)如何下料，使用的原材料最省。第9頁(yè)，共17頁(yè)，2022年，5月20日，3點(diǎn)19分，星期二 方案下料數(shù)(根)長(zhǎng)度m 2.9 2.1 1.5 1 321221213合計(jì)料頭7.407.30.17.20

6、.27.10.36.60.8為了得到100套鋼架，需要混合使用各種下料方案。設(shè)按方案下料的原材料要數(shù)為，方案為，方案為，方案為，方案為。根據(jù)表1-13的方案，可列出以下數(shù)學(xué)模型：第10頁(yè)，共17頁(yè)，2022年，5月20日，3點(diǎn)19分，星期二計(jì)算得到最優(yōu)下料方案是：按 方案下料30根；方案下料10根；方案下料50根。即需90根原材料才能制造100套鋼架。第11頁(yè)，共17頁(yè)，2022年，5月20日，3點(diǎn)19分，星期二例1-13 配料問題某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、C。已知產(chǎn)品的規(guī)格要求，產(chǎn)品單價(jià)，每天能供應(yīng)的原材料數(shù)量及原材料單價(jià)，分別見表1-14和表1-15

7、，該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？產(chǎn)品名稱 規(guī)格要求單價(jià)(元/kg)A原材料C不少于50%原材料P不少于25%50 B原材料C不少于25% 原材料P不少于50% 35 D 不限 25第12頁(yè)，共17頁(yè)，2022年，5月20日，3點(diǎn)19分，星期二原材料名稱每天最多供應(yīng)量(kg)單價(jià)(元/kg)CPH10010060652535解 如以 表示產(chǎn)品A中C的成分， 表示產(chǎn)品A中P的成分，依次類推。有(1-36) 這里 (1-37) (1-36)將（1-36）逐個(gè)代入(1-37)并整理得到第13頁(yè)，共17頁(yè)，2022年，5月20日，3點(diǎn)19分，星期二 表1-15表明這些原材料供應(yīng)數(shù)量的限額,加入到產(chǎn)品A、B、D的原材料C總量每天不超過100kg，P的總量不超過100kg，H總量不超過60kg。由此 第14頁(yè)，共17頁(yè)，2022年，5月20日，3點(diǎn)19分，星期二在約束條件中共有9個(gè)變量，為計(jì)算和敘述方便， 分別用表示令 由此約束條件可表示為： 第15頁(yè)，共17頁(yè)，2022年，5月20日，3點(diǎn)19分，星期二 我們的目的是使利潤(rùn)最大，即產(chǎn)品價(jià)格減去原材料的價(jià)格為最大。產(chǎn)品價(jià)格為: 原材料價(jià)格為： 原材料H產(chǎn)品A產(chǎn)品B產(chǎn)品D原材料C原材料P目標(biāo)函數(shù)為： 為了得到初始解，在約束條件中加入松馳變量 ，得到數(shù)學(xué)模型： 第16頁(yè)，