單純形表法課件

（1）當存在多個時，始終選取下標值為最小的變量作為換入變量；（2）當計算值出現(xiàn)兩個以上相同的最小比值時，始終選取下標值為最小的變量作為換出變量。3.無可行解的判別 本章第四節(jié)單純形法迭代原理中，講述了用單純形法求解時如何判別問題結局屬唯一最優(yōu)解、無窮多最優(yōu)解和無界解。當線性規(guī)劃問題中添加人工變量后，無論用大M法或兩階段法，初始單純形表中的解因含非零人工變量，故實質上是非可行解。當求解結果出現(xiàn)所有時，如基變量中仍含有非零的人工變量（兩階段法求解時第一階段目標函數(shù)值不等于零），表明問題無可行解。（1）當存在多個時，始終選取下標值為最小的變例1-11用單純形法求解線性規(guī)劃問題

解用圖解法可看出本例無可行解?，F(xiàn)用單純形法求解，在添加松馳變量和人工變量后，模型可寫成例1-11用單純形法求解線性規(guī)劃問題解用圖解法可看出以為基變量列出初始單純形表，進行迭代計算，過程見表1-11。表中當所有時，基變量中仍含有非零的人工變量，故例1-12的線性規(guī)劃問題無可行解。

2100-M

基

02-M6[1]1100220-11

2+2M1+2M0-M0

22-M21110000-2-11

0-1-2-2M-M0以為基變量列出初始單純形表，進行迭代二、單純形法小結

1.對給定的線性規(guī)劃問題應首先化為標準形式，選取或構造一個單位矩陣作為基，求出初始基可行解并列出初始單純形表。對各種類型線性規(guī)劃問題如何化為標準形式及如何選取初始基變量可參見page35表1-14。2.單純形法計算步驟的框圖見page35圖1-二、單純形法小結一、修正單純形法的基本思想

運用單純形法時，如果知道可行基的逆就能利用原始數(shù)據(jù)計算基變量的取值及檢驗數(shù)，從而能夠確定一個基本可行解，并判斷它是否為最優(yōu)解。因此在整個計算過程中，只要保存原始數(shù)據(jù)和現(xiàn)行的逆即可。修正單純刑法的基本思想就是給定初始基本可行基后，通過修改新基的逆進而完成其他運算。在整個計算過程中，始終保持先行基的逆?！?-8修正單純形法一、修正單純形法的基本思想§1-8修正單純形法二、修正單純形發(fā)的步驟（1）求一個初始基B并求出它的逆，寫出基底描述J。（2）求單純形乘子。（3）求及得到最優(yōu)解，停止；否則，記為k主元列，轉入（4）。（4）計算得無界解，停止：否則轉入（5）。（5）求二、修正單純形發(fā)的步驟并記l為主元行。（6）構造矩陣用左乘得到新基的逆陣，將J中的第L個數(shù)改為k，轉入（2）。并記l為主元行。

解

最簡單做法是，在每一根原材料上截取2.9m，2.1m和1.5m的元鋼各一根組成一套，每根原材料省下料頭0.9m。為了做100套鋼架，需用原材料100根，有90米料頭,若改為用套裁，這可以節(jié)約原材料。下面有幾種套裁方案，都可以考慮采用，見表1-13。

§1-9.單純形法應用實例例1-12合理利用線材問題現(xiàn)要做100套鋼架，每套用長為2.9m，2.1m和1.5m的元鋼各一根，已知原料長7.4m，問應如何下料，使用的原材料最省?！?-9.單純形法應用實例例1-12合理利用線材問題

方案下料數(shù)(根)長度m

Ⅰ

Ⅱ

ⅢⅢ

Ⅴ

2.92.11.51321221213合計料頭7.407.30.17.20.27.10.36.60.8為了得到100套鋼架，需要混合使用各種下料方案。設按Ⅰ方案下料的原材料要數(shù)為，Ⅱ方案為，Ⅲ方案為，Ⅳ方案為，Ⅴ方案為。根據(jù)表1-13的方案，可列出以下數(shù)學模型：方案下料數(shù)(根)

計算得到最優(yōu)下料方案是：按Ⅰ方案下料30根；Ⅱ方案下料10根；Ⅳ方案下料50根。即需90根原材料才能制造100套鋼架。計算得到最優(yōu)下料方案是：按Ⅰ方案下料30根；Ⅱ方案下料10例1-13配料問題某工廠要用三種原材料C、P、H混合調配出三種不同規(guī)格的產(chǎn)品A、B、C。已知產(chǎn)品的規(guī)格要求，產(chǎn)品單價，每天能供應的原材料數(shù)量及原材料單價，分別見表1-14和表1-15，該廠應如何安排生產(chǎn)，使利潤收入為最大？產(chǎn)品名稱

規(guī)格要求單價(元/kg)A原材料C不少于50%原材料P不少于25%50

B原材料C不少于25%原材料P不少于50%

35D

不限

25例1-13配料問題產(chǎn)品名稱規(guī)格要求單價(元/原材料名稱每天最多供應量(kg)單價(元/kg)CPH10010060652535解如以表示產(chǎn)品A中C的成分，表示產(chǎn)品A中P的成分，依次類推。有(1-36)這里(1-37)

(1-36)將（1-36）逐個代入(1-37)并整理得到原材料名稱每天最多供應量(kg)單價(元/kg)C10065

表1-15表明這些原材料供應數(shù)量的限額,加入到產(chǎn)品A、B、D的原材料C總量每天不超過100kg，P的總量不超過100kg，H總量不超過60kg。由此

表1-15表明這些原材料供應數(shù)量的限額,加入到產(chǎn)品A在約束條件中共有9個變量，為計算和敘述方便，分別用表示令

由此約束條件可表示為：

在約束條件中共有9個變量，為計算和敘述方便，

我們的目的是使利潤最大，即產(chǎn)品價格減去原材料的價格為最大。產(chǎn)品價格為: