建模培訓(xùn)之線性規(guī)劃

線性規(guī)劃(LinearProgramming)線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題的求解方法線性規(guī)劃的圖解法線性規(guī)劃的單純形法單純形法的進一步討論線性規(guī)劃模型的應(yīng)用目前一頁\總數(shù)一百零三頁\編于十四點

為了完成一項任務(wù)或達到一定的目的，怎樣用最少的人力、物力去完成或者用最少的資源去完成較多的任務(wù)或達到一定的目的，這個過程就是規(guī)劃。例一、有一正方形鐵皮，如何截取x使容積為最大？xa此為無約束極值問題一、線性規(guī)劃問題及其數(shù)學(xué)模型（一）、問題的提出目前二頁\總數(shù)一百零三頁\編于十四點

設(shè)備產(chǎn)品ABCD利潤（元）

Ⅰ21402

Ⅱ22043有效臺時1281612

例二、已知資料如下表所示，問如何安排生產(chǎn)才能使利潤最大？或如何考慮利潤大，產(chǎn)品好銷。模型maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12此為帶約束的極值問題目前三頁\總數(shù)一百零三頁\編于十四點問題中總有未知的變量，需要我們?nèi)ソ鉀Q。

要求：有目標(biāo)函數(shù)及約束條件，一般有非負(fù)條件存在，由此組成規(guī)劃數(shù)學(xué)模型。

如果在規(guī)劃問題的數(shù)學(xué)模型中，變量是連續(xù)的（數(shù)值取實數(shù)）其目標(biāo)函數(shù)是有關(guān)線性函數(shù)（一次方），約束條件是有關(guān)變量的線性等式或不等式，這樣，規(guī)劃問題的數(shù)學(xué)模型是線性的。反之，就是非線性的規(guī)劃問題（其中一個條件符合即可）。（二）、數(shù)學(xué)模型

1、目前四頁\總數(shù)一百零三頁\編于十四點目標(biāo)函數(shù)：約束條件：①②③2、線性規(guī)劃數(shù)學(xué)模型的一般形式目前五頁\總數(shù)一百零三頁\編于十四點也可以記為如下形式：目標(biāo)函數(shù)：約束條件：目前六頁\總數(shù)一百零三頁\編于十四點如將上例用表格表示如下：設(shè)變量

產(chǎn)品j

設(shè)備i

有效臺時

利潤

目前七頁\總數(shù)一百零三頁\編于十四點向量形式：目前八頁\總數(shù)一百零三頁\編于十四點矩陣形式：目前九頁\總數(shù)一百零三頁\編于十四點規(guī)劃確定型隨機型靜態(tài)規(guī)劃動態(tài)規(guī)劃線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃非整數(shù)規(guī)劃整數(shù)規(guī)劃非整數(shù)規(guī)劃3、規(guī)劃類型目前十頁\總數(shù)一百零三頁\編于十四點一般有兩種方法圖解法單純形法兩個變量、直角坐標(biāo)三個變量、立體坐標(biāo)適用于任意變量、但需將一般形式變成標(biāo)準(zhǔn)形式二、線性規(guī)劃問題的求解方法

（一）、求解方法目前十一頁\總數(shù)一百零三頁\編于十四點1、解的概念⑴可行解：滿足約束條件②、③的解為可行解。所有解的集合為可行解的集或可行域。⑵最優(yōu)解：使目標(biāo)函數(shù)達到最大值的可行解。⑶基：B是矩陣A中m×n階非奇異子矩陣（∣B∣≠0），則B是一個基。則稱Pj(j=12……m)為基向量?！郮j為基變量，否則為非基變量。（二）、線性規(guī)劃問題的解目前十二頁\總數(shù)一百零三頁\編于十四點

⑷基本解：滿足條件②，但不滿足條件③的所有解，最多為個。

⑸基本可行解：滿足非負(fù)約束條件的基本解，簡稱基可行解。

⑹可行基：對應(yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解目前十三頁\總數(shù)一百零三頁\編于十四點Maxz=2x1+3x2st.x1+x2≤3 x1+2x2≤4 x1,x2≥0Maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4≥0A=x1x2x3x411101201可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T等。設(shè)B=1001，令，則|B|=1≠0,令x1=x2=0，則x3=3,x4=4，X=(0,0,3,4)T例：x3x4——基變量令B=1110x1x3

，則令x2=x4=0，則x3=-1,x1=4，X=(4,0,-1,0)T|B|=-1≠0,——非基本可行解——基本可行解標(biāo)準(zhǔn)化目前十四頁\總數(shù)一百零三頁\編于十四點例2.2某地區(qū)有三個礦山A1，A2，A3，生產(chǎn)同一種礦物。另外有四個這種礦物消費地（鐵廠）B1，B2，B3，B4。各礦山產(chǎn)量及鐵廠的需要量和礦山將礦物運到鐵廠的單位運價如表2-2。問應(yīng)如何調(diào)運，才使總運費最??？（一）運輸問題的數(shù)學(xué)模型目前十五頁\總數(shù)一百零三頁\編于十四點解：該題有兩個限制條件：一個是產(chǎn)量，一個是需量。目標(biāo)是總運費最省。設(shè)：xij表示從第i個礦山運往第j個鐵廠的礦物運量。這樣得到以下兩組線性方程組：（1）各礦山礦物的生產(chǎn)量與運出量平衡方程：目前十六頁\總數(shù)一百零三頁\編于十四點（2）各鐵廠礦物供應(yīng)量與需要量平衡方程（3）礦物的運輸量應(yīng)非負(fù)

目前十七頁\總數(shù)一百零三頁\編于十四點（4）目標(biāo)函數(shù)目前十八頁\總數(shù)一百零三頁\編于十四點（二）資源最優(yōu)利用的數(shù)學(xué)模型例2.3某廠生產(chǎn)A、B產(chǎn)品1kg需用資源數(shù)見表2-3，已知生產(chǎn)A1kg價值7千元，B1kg12千元。應(yīng)該生產(chǎn)A和B產(chǎn)品各多少才能使總價值最大。目前十九頁\總數(shù)一百零三頁\編于十四點解：設(shè)A、B兩產(chǎn)品的計劃產(chǎn)量為x1、x2則數(shù)學(xué)模型為：

目前二十頁\總數(shù)一百零三頁\編于十四點（三）機床負(fù)荷問題的數(shù)學(xué)模型例2.4設(shè)某車間需加工甲、乙兩種零件。這兩種零件可以在三種不同機床——銑床、六角車床、自動機床上進行加工。機床數(shù)及生產(chǎn)效率如表2-4。目前二十一頁\總數(shù)一百零三頁\編于十四點（三）機床負(fù)荷問題的數(shù)學(xué)模型

此表說明，在一臺銑床上一個工作日可以加工15件甲零件或20件乙零件，余類同。該車間共有3臺銑床，3臺六角車床，1臺自動機床。問如何合理安排機床的加工任務(wù)，使得在產(chǎn)品配套比例條件下（設(shè)甲、乙零件1:1配套），使成套產(chǎn)品的數(shù)量達到最大。目前二十二頁\總數(shù)一百零三頁\編于十四點

解：設(shè)xij表示第i種機床用來生產(chǎn)第j種產(chǎn)品的臺數(shù)，則數(shù)學(xué)模型為：（1）加工甲、乙產(chǎn)品機床臺數(shù)平衡方程：

（2）甲、乙零件配套比例平衡方程：

目前二十三頁\總數(shù)一百零三頁\編于十四點（3）變量非負(fù)：（4）目標(biāo)函數(shù)求成套產(chǎn)品數(shù)量最大：

目前二十四頁\總數(shù)一百零三頁\編于十四點（四）人員分配的數(shù)學(xué)模型

例2.5有四件工作，分配給四人，每人能力不同，工作效率也不同如表2-5，規(guī)定每項工作由一個人擔(dān)任和每個工人只分配一項工作。問應(yīng)分配哪個人去完成哪項工作可使總效率達到最大。目前二十五頁\總數(shù)一百零三頁\編于十四點解：設(shè)xij表示i個工人分配擔(dān)任第j項工作的情況，并xij取1和0兩個值，

xij=1，表示第i個工人分配擔(dān)任第j項工作；

xij=0，表示i個工人不擔(dān)任第j項工作。

數(shù)學(xué)模型：（1）每個工人只擔(dān)任一項工作目前二十六頁\總數(shù)一百零三頁\編于十四點（2）每項工作必由一個工人擔(dān)任（3）變量取值：

（4）目標(biāo)函數(shù)求總效率最大：

目前二十七頁\總數(shù)一百零三頁\編于十四點（五）合理配料問題的數(shù)學(xué)模型

例2.6某人每日需服A、B兩種維生素，A最少服9個單位，B最少服19個單位，現(xiàn)有六種營養(yǎng)物每克含A、B維生素的單位數(shù)和每克價格如表2-6。問此人每天要服用這六種營養(yǎng)物各多少克，才既能獲得每日最少所需維生素又使花費最省。目前二十八頁\總數(shù)一百零三頁\編于十四點（五）合理配料問題的數(shù)學(xué)模型

設(shè)：六種營養(yǎng)物分別各服用x1g，x2g，x3g，x4g，x5g，x6g。則數(shù)學(xué)模型：

目前二十九頁\總數(shù)一百零三頁\編于十四點（六）合理下料問題的數(shù)學(xué)模型例2.7某車間有一批長度為180cm的鋼管，為著制造零件的需要，要將其截成三種不同長度的管料：70cm、52cm、35cm。規(guī)定這三種管料的需要量分別不少于100根、150根和100根。問題是應(yīng)如何下料能使消耗的鋼管數(shù)量最少？解：設(shè)在180cm長的鋼管上能夠下出U個70cm的零件，V個52cm的零件和W個35cm的零件，則U、V、W個零件必須符合:70U+52V+35W≤180目前三十頁\總數(shù)一百零三頁\編于十四點（六）合理下料問題的數(shù)學(xué)模型經(jīng)過試算，可得8種下料方式，見表：目前三十一頁\總數(shù)一百零三頁\編于十四點設(shè)：x1、x2、x3、x4、x5、x6、x7、x8分別表示這八種下料方式鋼管消耗的總根數(shù)，則數(shù)學(xué)模型：目前三十二頁\總數(shù)一百零三頁\編于十四點2、解的基本定理⑴線性規(guī)劃問題的可行域是凸集（凸多邊形）。凸集凸集不是凸集頂點⑵最優(yōu)解一定是在凸集的某一頂點實現(xiàn)（頂點數(shù)目不超過個）目前三十三頁\總數(shù)一百零三頁\編于十四點⑶先找一個基本可行解，與周圍頂點比較，如不是最大，繼續(xù)比較，直到找出最大為止。3、解的情況唯一解無窮解無界解無可行解有最優(yōu)解無最優(yōu)解目前三十四頁\總數(shù)一百零三頁\編于十四點

建立直角坐標(biāo)，圖中陰影部分及邊界上的點均為其解，是由約束條件來反映的。例一、⑴⑵⑶⑷三、圖解法目前三十五頁\總數(shù)一百零三頁\編于十四點012345678123456⑴⑵⑶⑷作圖∴最優(yōu)解：x1=4x2=2有唯一最優(yōu)解，Z=14x2

x1(42)⑴⑵⑶⑷目前三十六頁\總數(shù)一百零三頁\編于十四點例二、例三、⑴⑵⑶無窮多最優(yōu)解⑴⑵無界解x1x1x2

x2

目前三十七頁\總數(shù)一百零三頁\編于十四點⑴⑵x1x2

無可行解例四、練習(xí)1目前三十八頁\總數(shù)一百零三頁\編于十四點效產(chǎn)品機床率AB機床臺數(shù)

Ⅰ304040

Ⅱ553040Ⅲ233720

2、

某車間用三種不同型號的機床Ⅰ、Ⅱ、Ⅲ，加工A、B兩種零件，機床臺數(shù)、生產(chǎn)效率如表所示。問如何合理安排機床的加工任務(wù)，才能使生產(chǎn)的零件總數(shù)最多？1、某工廠生產(chǎn)A1、A2兩種產(chǎn)品，每件可獲利潤15、20元。每個產(chǎn)品都經(jīng)過三道工序，資料如表所示。工廠應(yīng)如何安排生產(chǎn)計劃使獲得的總利潤最多？試寫出此問題的數(shù)學(xué)模型。工產(chǎn)品工序時A1A2可用工時

Ⅰ32800

Ⅱ23800Ⅲ11350習(xí)題1目前三十九頁\總數(shù)一百零三頁\編于十四點3、用圖解法求解下面的線性規(guī)劃問題：目前四十頁\總數(shù)一百零三頁\編于十四點x1x2

123(2)x1x2

123(1)目前四十一頁\總數(shù)一百零三頁\編于十四點（一）、基本思想將模型的一般形式變成標(biāo)準(zhǔn)形式，再根據(jù)標(biāo)準(zhǔn)型模型，從可行域中找一個基本可行解，并判斷是否是最優(yōu)。如果是，獲得最優(yōu)解；如果不是，轉(zhuǎn)換到另一個基本可行解，當(dāng)目標(biāo)函數(shù)達到最大時，得到最優(yōu)解。（二）、線性規(guī)劃模型的標(biāo)準(zhǔn)形式1、標(biāo)準(zhǔn)形式四、單純形法目前四十二頁\總數(shù)一百零三頁\編于十四點2、特征：⑴.目標(biāo)函數(shù)為求極大值，也可以用求極小值；⑵.所有約束條件（非負(fù)條件除外）都是等式，右端常數(shù)項為非負(fù)；⑶.變量為非負(fù)。3、轉(zhuǎn)換方式：⑴.目標(biāo)函數(shù)的轉(zhuǎn)換如果是求極小值即，則可將目標(biāo)函數(shù)乘以（－1），可化為求極大值問題。也就是：令，可得到上式。即目前四十三頁\總數(shù)一百零三頁\編于十四點⑵.約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量目前四十四頁\總數(shù)一百零三頁\編于十四點⑶.變量的變換若存在取值無約束的變量，可令其中：例一、將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式為無約束（無非負(fù)限制）目前四十五頁\總數(shù)一百零三頁\編于十四點

解:用替換，且，將第3個約束方程兩邊乘以（－1）將極小值問題反號，變?yōu)榍髽O大值標(biāo)準(zhǔn)形式如下：引入變量目前四十六頁\總數(shù)一百零三頁\編于十四點例二、將線性規(guī)劃問題化為標(biāo)準(zhǔn)型為無約束解：目前四十七頁\總數(shù)一百零三頁\編于十四點（三）、單純形法例一、變成標(biāo)準(zhǔn)型目前四十八頁\總數(shù)一百零三頁\編于十四點約束方程的系數(shù)矩陣為基變量為非基變量I為單位矩陣且線性獨立目前四十九頁\總數(shù)一百零三頁\編于十四點Maxz=2x1+3x2st.x1+x2≤3 x1+2x2≤4 x1,x2≥0Maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4≥0A=x1x2x3x411101201可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T等。設(shè)B=1001，令，則|B|=1≠0,令x1=x2=0，則x3=3,x4=4，X=(0,0,3,4)T回顧：x3x4——基變量令B=1110x1x3

，則令x2=x4=0，則x3=-1,x1=4，X=(4,0,-1,0)T|B|=-1≠0,——非基本可行解——基本可行解標(biāo)準(zhǔn)化目前五十頁\總數(shù)一百零三頁\編于十四點令：則：∴基本可行解為（001281612）

此時，Z=0然后，找另一個基本可行解。即將非基變量換入基變量中，但保證其余的非負(fù)。如此循環(huán)下去，直到找到最優(yōu)解為止。注意：為盡快找到最優(yōu)解，在換入變量時有一定的要求。如將目標(biāo)系數(shù)大的先換入等。目前五十一頁\總數(shù)一百零三頁\編于十四點找出一個初始可行解是否最優(yōu)轉(zhuǎn)移到另一個目標(biāo)函數(shù)（找更大的基本可行解）最優(yōu)解是否循環(huán)直到找出為止，核心是：變量迭代結(jié)束其步驟總結(jié)如下：目前五十二頁\總數(shù)一百零三頁\編于十四點當(dāng)時，為換入變量確定換出變量為換出變量接下來有下式：目前五十三頁\總數(shù)一百零三頁\編于十四點用高斯法，將的系數(shù)列向量換為單位列向量，其步驟是：結(jié)果是：目前五十四頁\總數(shù)一百零三頁\編于十四點代入目標(biāo)函數(shù)：有正系數(shù)表明：還有潛力可挖，沒有達到最大值；此時：令得到另一個基本可行解

（0，3，6，2，16，0）有負(fù)系數(shù)表明：若要剩余資源發(fā)揮作用，就必須支付附加費用。當(dāng)時，即不再利用這些資源。如此循環(huán)進行，直到找到最優(yōu)為止。本例最優(yōu)解為：（4，2，0，0，0，4）目前五十五頁\總數(shù)一百零三頁\編于十四點（四）、單純形表目前五十六頁\總數(shù)一百零三頁\編于十四點判定標(biāo)準(zhǔn)：若求

或例題：目前五十七頁\總數(shù)一百零三頁\編于十四點cj230000cBxBb

x1x2x3x4x5x60000x3x4x5x61281612221000120100400010040001-Z0

23000012/28/2－12/4cj230000cBxBbx1x2x3x4x5x6000x3x4x516

400010

-Z3x23010001/42620100-1/2100100-1/2目前五十八頁\總數(shù)一百零三頁\編于十四點cj230000cBxBbx1x2x3x4x5x60003x3x4x5x262163

20100-1/210010-1/2400010010001/4-Z-9

20000-3/46/2216/4－cj230000cBxBbx1x2x3x4x5x60203x3x1x5x22283001-201/210010-1/2000-412010001/44－412-Z-13000-201/4目前五十九頁\總數(shù)一百零三頁\編于十四點cj230000cBxBbx1x2x3x4x5x60203x6x1x5x2

4402

002-401101-10000-441001-1/2100-Z-1400-1/2-100000-201/4-13-Z4－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cj目前六十頁\總數(shù)一百零三頁\編于十四點cj230000cBxBbx1x2x3x4x5x60203x3x1x6x2

0442001-1-1/4010001/40

000-21/210101/2-1/80-Z-14000-3/2-1/80000-201/4-13-Z4－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cj目前六十一頁\總數(shù)一百零三頁\編于十四點練習(xí)00-1/12-7/24-33/4-Z

x2x112x1x2x3x4bxBcB2100cj15/43/4011/4-1/810-1/125/24目前六十二頁\總數(shù)一百零三頁\編于十四點（一）、模型情況

變量：xj≥0xj≤0xj無約束結(jié)1、組成約束條件：≥=≤b目標(biāo)函數(shù)：maxmin果2、變量xj≤0令xj′=-xj，xj′≥0

xj≥0不處理

xj無約束令xj=xj′－xj″,xj′≥0,xj″≥0唯一最優(yōu)無窮最優(yōu)無界解無可行解五、單純形法的進一步討論

目前六十三頁\總數(shù)一百零三頁\編于十四點3、約束條件：加入松弛變量加入人工變量先減去再加上例：目前六十四頁\總數(shù)一百零三頁\編于十四點目前六十五頁\總數(shù)一百零三頁\編于十四點加入人工變量后，目的是找到一個單位向量，叫人工基。其目標(biāo)價值系數(shù)要確定，但不能影響目標(biāo)函數(shù)的取值。一般可采用兩種方法處理：大M法和兩階段法。即假定人工變量在目標(biāo)函數(shù)中的系數(shù)為M（任意大正數(shù)），如果是求極大值，需加-M；如果是求極小值，需加M。如基變量中還存在M，就不能實現(xiàn)極值。⑴.大M法：目前六十六頁\總數(shù)一百零三頁\編于十四點cj-31100MMcBxBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011-Z-3+6M1-M1-3M0M00cBxBbx1x2x3x4x5x6x70x4103-20100-1－Mx610100-11-211x31-2010001－-Z-11-M00M03M-1目前六十七頁\總數(shù)一百零三頁\編于十四點cj-31100MMcBxBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2－1x31-2010001－-Z-2-10001M-1M+1cBxBbx1x2x3x4x5x6x7-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3-Z20001/31/3M-1/3M-2/3∴最優(yōu)解為（4190000），Z=－2目前六十八頁\總數(shù)一百零三頁\編于十四點用計算機處理數(shù)據(jù)時，只能用很大的數(shù)代替M,可能造成計算機上的錯誤，故多采用兩階段法。

第一階段：在原線性規(guī)劃問題中加入人工變量，構(gòu)造如下模型：⑵.兩階段法：目前六十九頁\總數(shù)一百零三頁\編于十四點對上述模型求解（單純形法），若W=0,說明問題存在基本可行解，可以進行第二個階段；否則，原問題無可行解，停止運算。第二階段：在第一階段的最終表中，去掉人工變量，將目標(biāo)函數(shù)的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，作為第二階段計算的初始表（用單純形法計算）。例：第一階段目前七十頁\總數(shù)一百零三頁\編于十四點cj0000011cBxBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-20100011-Z46-1-301000x4103-20100-1－1x610100-11-210x31-2010001－-Z10-1001030x4123001-22-50x210100-11-20x31-2010000-Z00000011目前七十一頁\總數(shù)一百零三頁\編于十四點cj-31100cBxBbx1x2x3x4x50x4123001-241x210100-1－1x31-20100－-Z-2-10001-3x141001/3-2/31x210100-11x390012/3-4/3-Z20001/31/3第二階段∴最優(yōu)解為（41900），目標(biāo)函數(shù)Z=-2目前七十二頁\總數(shù)一百零三頁\編于十四點1、目標(biāo)函數(shù)：max,min設(shè)規(guī)劃模型約束條件為，需加入人工變量，而得到一個m×m的單位矩陣，即基變量組合。因人工變量為虛擬變量，且存在于初始基本可行解中，需要將它們從基變量中替換出來。若基變量中不含有非零的人工變量，表示原問題有解。若當(dāng)，而還有人工變量（非零）時，則表示原問題無可行解。目前七十三頁\總數(shù)一百零三頁\編于十四點3、無可行解的判斷：運算到檢驗數(shù)全負(fù)為止，仍含有人工變量，無可行解。目前七十四頁\總數(shù)一百零三頁\編于十四點

5、退化：即計算出的θ（用于確定換出變量）存在有兩個以上相同的最小比值，會造成下一次迭代中由一個或幾個基變量等于零，這就是退化（會產(chǎn)生退化解）。雖任意換出變量，目標(biāo)函數(shù)值不變，但此時不同的基卻表示為同一頂點，其特例是永遠達不到最優(yōu)解。需作如下處理：⑴.當(dāng)中出現(xiàn)兩個以上最大值時，選下標(biāo)最小的非基變量為換入變量；⑵.當(dāng)θ中出現(xiàn)兩個以上最小值時，選下標(biāo)最小的基變量為換出變量。目前七十五頁\總數(shù)一百零三頁\編于十四點建立模型個數(shù)取值右端項等式或不等式極大或極小新加變量系數(shù)兩個三個以上xj≥0xj無約束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa求解圖解法、單純形法單純形法不處理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj=-xj不處理約束條件兩端同乘以-1加松弛變量xs加入人工變量xa減去xs加入xa不處理令z′=-ZminZ=－maxz′0-M根據(jù)上表列出初始單純形表A（二）、線性規(guī)劃小結(jié)目前七十六頁\總數(shù)一百零三頁\編于十四點A目前七十七頁\總數(shù)一百零三頁\編于十四點練習(xí)目前七十八頁\總數(shù)一百零三頁\編于十四點-M+1/7-1/7-M-16/7-50/700-102/7-Z1/7-1/75/76/70145/7x12-1/71/72/71/7104/7x23x6x5x4x3x2x1bxBcB-M0-M-532cj0-M0-5+2M3-4M2+3M-Z51-101-5210x6-M70011117X4-Mx6x5x4x3x2x1bxBcB-M0-M-532cj目前七十九頁\總數(shù)一百零三頁\編于十四點作業(yè)目前八十頁\總數(shù)一百零三頁\編于十四點目前八十一頁\總數(shù)一百零三頁\編于十四點0100x2-4-2/35/3-10/3x1300-Z-1/3-1/300-2/32/3-1/32/3x2-44010-1/31/3105/3-5/310/340/310/3x804-1/31/301-1/31/3-5/34/3x7-Mx10x9x8x7x6x5x3bxBcB-M00-M5-52cj4M-4311x2-43-6M-21-4x130-M005-3M3M-52-3M-Z2/31-100-22-12x10-M14\400101-1314\4x8020001-11-22x7-Mx10x9x8x7x6x5x3bxBcB-M00-M5-52cj目前八十二頁\總數(shù)一百零三頁\編于十四點0100x2-4-31/2-3/25/2-15/2x13-M0-1/2-M+9/200-17/22\7-Z001/21/2001/28\3x2-4001/2-1/21-1[5/2]6\1x65-111/25/200-5/210\5x90x10x9x8x7x6x5x3bxBcB-M00-M5-52cj0100x2-4-13-45-10x13-M00-M+41-1-68-Z-0001-11-22x2-46001-12-2512\2x80--1103-11-54x90x10x9x8x7x6x5x3bxBcB-M00-M5-52cj目前八十三頁\總數(shù)一百零三頁\編于十四點一般而言，一個經(jīng)濟、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。⑴.要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)；⑵.存在著多種方案；⑶.要求達到的目標(biāo)是在一定條件下實現(xiàn)的，這些約束可用線性等式或不等式描述。六、線性規(guī)劃模型的應(yīng)用目前八十四頁\總數(shù)一百零三頁\編于十四點（一）、資源的合理利用一般提法：某廠計劃在下一生產(chǎn)周期內(nèi)生產(chǎn)B1,B2,…Bn種產(chǎn)品，要消耗A1,A2,…Am種資源，已知每件產(chǎn)品所消耗的資源數(shù)、每種資源的數(shù)量限制以及每件產(chǎn)品可獲得的利潤如表所示，問如何安排生產(chǎn)計劃，才能充分利用現(xiàn)有的資源，使獲得的總利潤最大？單件產(chǎn)消耗品資源資源限制單件利潤目前八十五頁\總數(shù)一百零三頁\編于十四點（二）、生產(chǎn)組織與計劃問題

一般提法：某工廠用機床A1,A2,…Am加工B1,B2,…Bn種零件。在一個周期內(nèi)，各機床可能工作的機時（臺時），工廠必須完成各種零件的數(shù)量、各機床加工每個零件的時間（機時/個）和加工每個零件的成本（元/個）如表所示，問如何安排各機床的生產(chǎn)任務(wù)，才能完成加工任務(wù)，又使總成本最低？加工零時間件機床機時限制必須零件數(shù)加工