線性規(guī)劃與單純形法詳解演示文稿

線性規(guī)劃與單純形法詳解演示文稿目前一頁\總數(shù)一百零五頁\編于八點（優(yōu)選）線性規(guī)劃與單純形法目前二頁\總數(shù)一百零五頁\編于八點例1.1生產(chǎn)計劃問題（資源利用問題）某家具廠生產(chǎn)桌子和椅子兩種家具。

桌子售價50元/個，椅子銷售價格30元/個。需要木工和油漆工兩種工種。生產(chǎn)一個桌子需要木工4小時，油漆工2小時。生產(chǎn)一個椅子需要木工3小時，油漆工1小時。該廠每個月可用木工工時為120小時，油漆工工時為50小時。

問如何組織生產(chǎn)才能使每月的銷售收入最大？1、問題的提出目前三頁\總數(shù)一百零五頁\編于八點是問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。第1步-確定決策變量設(shè)——桌子的產(chǎn)量

——椅子的產(chǎn)量

——利潤目前四頁\總數(shù)一百零五頁\編于八點第2步--定義目標(biāo)函數(shù)決策變量

MaxZ=50x1+30x2目前五頁\總數(shù)一百零五頁\編于八點價值系數(shù)第2步--定義目標(biāo)函數(shù)

MaxZ=50x1+30x2目前六頁\總數(shù)一百零五頁\編于八點第3步--表示約束條件4x1+3x2

120（木工工時限制）

2x1+x2

50（油漆工工時限制）

x1，x2≥0（變量取非負值限制）目前七頁\總數(shù)一百零五頁\編于八點

該計劃的數(shù)學(xué)模型

maxZ=50x1+30x24x1+3x2

1202x1+x250

x1,x20s.t.線性函數(shù)線性等式線性不等式線性規(guī)劃+目前八頁\總數(shù)一百零五頁\編于八點例1.2簡化的環(huán)境保護問題

靠近某河流有兩個化工廠(見下圖)，流經(jīng)第一化工廠的河流流量為每天500萬立方米，在兩個工廠之間有一條流量為每天200萬立方米的支流。

目前九頁\總數(shù)一百零五頁\編于八點第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水2萬立方米，第二化工廠每天排放這種工業(yè)污水1.4萬立方米。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2%。這兩個工廠都需各自處理一部分工業(yè)污水。第一化工廠處理工業(yè)污水的成本是1000元/萬立方米。第二化工廠處理工業(yè)污水的成本是800元/萬立方米?，F(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個工廠總的處理工業(yè)污水費用最小。目前十頁\總數(shù)一百零五頁\編于八點

建模型之前的分析和計算

設(shè)：第一化工廠每天處理工業(yè)污水量為x1萬立方米，第二化工廠每天處理工業(yè)污水量為x2萬立方米目前十一頁\總數(shù)一百零五頁\編于八點數(shù)學(xué)模型目前十二頁\總數(shù)一百零五頁\編于八點線性規(guī)模解決的問題給定一定數(shù)量的人力、物力、財力等資源，研究如何充分利用，以發(fā)揮其最大效果已給定計劃任務(wù)，研究如何統(tǒng)籌安排，用最少的人力、物力、財力去完成目前十三頁\總數(shù)一百零五頁\編于八點線性規(guī)劃數(shù)學(xué)模型三要素：

決策變量、目標(biāo)函數(shù)、約束條件

每一個線性規(guī)劃問題都有一組決策變量

(x1,x2,……,xn),這組決策變量的值就代表一個具體方案。

有使用各種資源的約束條件，用等式或不等式表示。

有一個要達到的目標(biāo)，是決策變量的線性函數(shù)，實現(xiàn)最大化或最小化。2、線性規(guī)劃問題的數(shù)學(xué)模型目前十四頁\總數(shù)一百零五頁\編于八點

一般形式線性規(guī)劃模型的表示形式

矩陣形式

標(biāo)準(zhǔn)形式

將一般線性規(guī)劃化成標(biāo)準(zhǔn)形

簡寫形式目前十五頁\總數(shù)一百零五頁\編于八點max(min)Z=c1x1+c2x2+…..+cnxna11x1+a12x2+….+a1nxn(=,)b1

a21x1+a22x2+….+a2nxn(=,)b2

….

am1x1+am2x2+….+amnxn(=,)bm

x1,

x2,….,xn0s.t.線性規(guī)劃問題的一般形式目前十六頁\總數(shù)一百零五頁\編于八點

線性規(guī)劃問題的簡寫形式目前十七頁\總數(shù)一百零五頁\編于八點

max

Z=CTX

s.t.AX=b

X

0C—價值向量b—資源向量X—決策變量向量線性規(guī)劃的矩陣形式目前十八頁\總數(shù)一百零五頁\編于八點

a11

a12….a1nb1A=a21

a22….a2n

b

=

b2…….

am1

am2….amnbm

c1

x10

c2

x20C=X=0=……...

cn

xn0目前十九頁\總數(shù)一百零五頁\編于八點線性規(guī)劃問題的標(biāo)準(zhǔn)形式max

Z=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn

=b1

a21x1+a22x2+….+a2nxn=

b2

….

am1x1+am2x2+….+amnxn=

bm

x1,

x2,….,xn0其中：bi

0,i=1,2,….,m.目前二十頁\總數(shù)一百零五頁\編于八點四點要求:將一般線性規(guī)劃化成標(biāo)準(zhǔn)型

求max

等式約束

bi0

xi0目前二十一頁\總數(shù)一百零五頁\編于八點(1)若目標(biāo)函數(shù)是求最小值:

min

Z=CTX

令Z’=Z,則化成max

Z’=CTX注意:

因為min

Z=max(Z)

所以變換后的最優(yōu)解不變，最優(yōu)值變號。目前二十二頁\總數(shù)一百零五頁\編于八點(2)若約束條件是不等式1)若約束條件是“”不等式，則不等式左邊“加上”非負的松馳變量；如：2X1+2X2≤12令X3=12-2X1-2X2

則有2X1+2X2+X3=12

2)若約束條件是“”不等式，則不等式左邊“減去”非負的松馳變量。如：10X1+12X2≥18令X4=10X1+12X2-18則有10X1+12X2-X4=18

為了使添加松馳變量不影響原來的目標(biāo)，添加松馳變量在目標(biāo)函數(shù)中的系數(shù)為0。目前二十三頁\總數(shù)一百零五頁\編于八點(3)若約束條件右面的某一常數(shù)項bi<0,

這時只要在bi相對應(yīng)的約束方程兩邊乘1。(4)若變量xj無非負限制引進兩個非負變量xj’

xj”0

令xj=

xj’

xj”

（可正可負）任何形式的線性規(guī)劃總可以化成標(biāo)準(zhǔn)型目前二十四頁\總數(shù)一百零五頁\編于八點例1.3將下列問題化成標(biāo)準(zhǔn)型:

min

Z=

x1+2x23x3

s.t.x1+x2+x37

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3無限制目前二十五頁\總數(shù)一百零五頁\編于八點例1.3將下列問題化成標(biāo)準(zhǔn)型:

min

Z=

x1+2x23x3

s.t.x1+x2+x37

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3無限制minx3

無限制目前二十六頁\總數(shù)一百零五頁\編于八點例1.3將下列問題化成標(biāo)準(zhǔn)型:

max

Z’=

x1

2x2+3x3

s.t.x1+x2+x37

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3無限制目前二十七頁\總數(shù)一百零五頁\編于八點例將下列問題化成標(biāo)準(zhǔn)型:

max

Z’=

x1

2x2+3x3+0x4

s.t.x1+x2+x3+x4=7

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3無限制，x4

0目前二十八頁\總數(shù)一百零五頁\編于八點例將下列問題化成標(biāo)準(zhǔn)型:

maxZ’=

x1

2x2+3x3+0x4+0x5

s.t.x1+x2+x3+x4=7

x1

x2+x3

x5=2

3x1+x2+2x3=5

x10,x20,x3無限制，x4

0，x5

0目前二十九頁\總數(shù)一百零五頁\編于八點max

Z’=

x1

2x2+3x3’

3x3’’+0x4+0x5

s.t.x1+x2+x3’

x3’’

+x4=7

x1

x2+x3’

x3’’

x5=2

3x1+x2+2x3’

2x3’’

=5

x10,x20,x3’0,

x3’’0，x4

0，x5

0令x3=

x3’

x3’’目前三十頁\總數(shù)一百零五頁\編于八點例將下列一般形式劃為標(biāo)準(zhǔn)形式：目前三十一頁\總數(shù)一百零五頁\編于八點目前三十二頁\總數(shù)一百零五頁\編于八點標(biāo)準(zhǔn)型習(xí)題P55-2.2（1）劃為標(biāo)準(zhǔn)形式目前三十三頁\總數(shù)一百零五頁\編于八點二、LP問題的圖解法max

Z=50x1+30x2s.t.4x1+3x21202x1+x2

50

x1,x2

01.例目前三十四頁\總數(shù)一百零五頁\編于八點x240302010102030x1

由4x1+3x2120

x10,x20

圍成的區(qū)域50

由2x1+x250

x10,x20

圍成的區(qū)域目前三十五頁\總數(shù)一百零五頁\編于八點x240302010102030x1

由4x1+3x21202x1+x250

x10,x20

圍成的區(qū)域

(可行域)50可行域滿足約束條件的解稱為可行解，全部可行解的集合稱為可行域。目前三十六頁\總數(shù)一百零五頁\編于八點x240302010102030x1

該問題的可行域是由

Q1，Q2，Q3，Q4

作為頂點的凸多邊形50可行域Q1(0,0)Q2(25,0)Q4(0,40)Q3(15,20)目前三十七頁\總數(shù)一百零五頁\編于八點x240302010102030x1

目標(biāo)函數(shù)

Z=50x1+30x2

是一組平行線50可行域目前三十八頁\總數(shù)一百零五頁\編于八點x240302010102030x1

此組平行線沿其法線方向(50,30)右上方函數(shù)值Z

增加50可行域目前三十九頁\總數(shù)一百零五頁\編于八點x240302010102030x1當(dāng)該直線移到Q3(15,20)點時，Z值達到最大：

max

Z=5015+3020=1350此時最優(yōu)解X*=（15，20）50Q3(15,20)目前四十頁\總數(shù)一百零五頁\編于八點二個重要結(jié)論：可行域是一個凸多邊形。最優(yōu)解必定能在某一個頂點上取得。目前四十一頁\總數(shù)一百零五頁\編于八點2.LP問題的解

可行解：滿足約束條件（包括非負條件）的一組變量值，稱可行解。

可行域：可行解的全體。

最優(yōu)解：使目標(biāo)函數(shù)達到最大的可行解。

最優(yōu)值：將最優(yōu)解代入目標(biāo)函數(shù)得到的值。目前四十二頁\總數(shù)一百零五頁\編于八點

可行域為空集無可行解

可行域非空，則有三種情況：(1)有唯一解(頂點)(2)有無窮多個解(兩個頂點間的連線)(3)無最優(yōu)解(無界解)無最優(yōu)解目前四十三頁\總數(shù)一百零五頁\編于八點⑴⑵x1x2

無可行解目前四十四頁\總數(shù)一百零五頁\編于八點x240302010102030x1

當(dāng)目標(biāo)函數(shù)由

max

Z=50x1+30x2

變成

max

Z=40x1+30x2

目標(biāo)函數(shù)是同約束條件

4x1+3x2120

平行的直線

Q2與Q3之間都是最優(yōu)解50Q3(15,20)Q2(25,0)目前四十五頁\總數(shù)一百零五頁\編于八點⑴⑵無界解x1x2

目前四十六頁\總數(shù)一百零五頁\編于八點無界解：若可行域無界，且目標(biāo)函數(shù)值可增加(減少)到正無窮(負無窮)，稱這種無最優(yōu)解的情況為無界解。注意：

可行域無界，不一定無最優(yōu)解；可行域非空有界，則必定有最優(yōu)解。目前四十七頁\總數(shù)一百零五頁\編于八點LP問題解的類型習(xí)題P55-2.1目前四十八頁\總數(shù)一百零五頁\編于八點三、單純形法的基本思路和原理（一）單純形法的基本思路

從可行域中某一個頂點開始，判斷此頂點是否是最優(yōu)，如不是，則再找另一個使得其目標(biāo)函數(shù)值更優(yōu)的頂點，稱之為迭代，再判斷此點是否是最優(yōu)解，直到找到一個頂點為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。目前四十九頁\總數(shù)一百零五頁\編于八點找出一個初始可行解是否最優(yōu)轉(zhuǎn)移到另一個目標(biāo)函數(shù)（找更大的基本可行解）最優(yōu)解是否循環(huán)直到找出為止，核心是：變量迭代結(jié)束目前五十頁\總數(shù)一百零五頁\編于八點

例

max

Z=2x1+3x2s.t.x1+2x244x1

84x2

6

x1,x2

01.基本概念目前五十一頁\總數(shù)一百零五頁\編于八點劃為標(biāo)準(zhǔn)型：

max

Z=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=44x1+x4=84x2+x5=6

x1,x2,x3,x4,x5

0目前五十二頁\總數(shù)一百零五頁\編于八點約束方程的系數(shù)矩陣A=P1P2P3P4P5單位矩陣A中存在一個不為零的三階子式，A的秩為3目前五十三頁\總數(shù)一百零五頁\編于八點A是約束條件的m×n階系數(shù)矩陣，設(shè)r(A)=m,且B是A的m

階非奇異的子矩陣（det(B)0),則稱矩陣B為線性規(guī)劃問題的一個基(陣)。（1）基(陣)B=或目前五十四頁\總數(shù)一百零五頁\編于八點(mn)

r(A)=m，至少有一個m階子式不為0。a11

…a1m

a1m+1

…a1na21

…

a2m

a2m+1

…

a2n………am1

…

amm

amm+1

…

amnp1

…

pm

pm+1

…

pnBN目前五十五頁\總數(shù)一百零五頁\編于八點基B中的一列即稱為一個基向量，基B中共有m個基向量。（2）基向量與非基向量B=P3P4P5基向量A=(p1

…

pm

pm+1

…

pn)=(B,N)

基向量

非基向量目前五十六頁\總數(shù)一百零五頁\編于八點（3）基變量與非基變量設(shè)A=(p1,p2,……,pn)，若B=(pi1,pi2,……,pim)為A的基陣，則稱x1,x2,……,xn中的xi1,xi2,……,xim為對應(yīng)于B的基變量，其余的稱為非基變量。目前五十七頁\總數(shù)一百零五頁\編于八點B=P3P4P5x3,x4,x5是基變量x1,x2,是非基變量基向量X=(x1

…

xm

xm+1

…

xn

)T=(XBXN)T

基變量

非基變量A=(p1

…

pm

pm+1

…

pn)=(B,N)

基向量

非基向量目前五十八頁\總數(shù)一百零五頁\編于八點（4）基(本)解令非基變量取值為零,則基變量的取值可從AX=b中唯一解得。如此的一組解稱為對應(yīng)于B的一個基（本）解。目前五十九頁\總數(shù)一百零五頁\編于八點（5）基可行解若X0是一個基解，而且又是一個可行解，則稱X0是一個基可行解。基可行解對應(yīng)于可行域的頂點。目前六十頁\總數(shù)一百零五頁\編于八點退化的基可行解問題:

在基可行解中,非基變量的取值必定為零,基變量的取值是否必定大于零?若X0是一個基可行解,其基變量的取值全部大于零，則稱X0是非退化的;否則稱為退化的。目前六十一頁\總數(shù)一百零五頁\編于八點解的關(guān)系可行解基解基可行解最優(yōu)解目前六十二頁\總數(shù)一百零五頁\編于八點代數(shù)概念幾何概念滿足一個等式約束的解滿足一個不等式約束的解滿足一組不等式約束的解基解基可行解目標(biāo)函數(shù)值等于一個常數(shù)的解組約束直線約束半平面約束半平面的交集：凸多邊形約束直線的交點可行域頂點目標(biāo)函數(shù)等值線：一組平行線目前六十三頁\總數(shù)一百零五頁\編于八點舉例目前六十四頁\總數(shù)一百零五頁\編于八點化為標(biāo)準(zhǔn)型目前六十五頁\總數(shù)一百零五頁\編于八點可行解、基解和基可行解舉例目前六十六頁\總數(shù)一百零五頁\編于八點2.最優(yōu)解的判斷檢驗數(shù)公式或最優(yōu)解檢驗的依據(jù)是計算檢驗數(shù)目前六十七頁\總數(shù)一百零五頁\編于八點檢驗數(shù)的判別規(guī)則(max)若所有的，則基B所對應(yīng)的基可行解就是最優(yōu)解。若所有的，而非基變量的檢驗數(shù)滿足條件，則該線性規(guī)劃問題有唯一最優(yōu)解。若所有的

，又有某個非基變量的檢驗數(shù)，則該線性規(guī)劃問題有無窮多最優(yōu)解。若存在某個，又其對應(yīng)的向量的所有分量，則該線性規(guī)劃問題存在無界解。目前六十八頁\總數(shù)一百零五頁\編于八點3.單純形表目前六十九頁\總數(shù)一百零五頁\編于八點（二）單純形法的內(nèi)容1.初始基可行解的確定（假定基陣B為單位陣）2.最優(yōu)解的判斷3.換基可行解的方法目前七十頁\總數(shù)一百零五頁\編于八點例

max

Z=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=44x1+x4=84x2+x5=6

x1,x2,x3,x4,x5

0目前七十一頁\總數(shù)一百零五頁\編于八點

cj23000x1x2x3x4x5121004001004001cBxBbx3x4x5000486

max

Z=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=44x1+x4=84x2+x5=6

x1,x2,x3,x4,x5

0目前七十二頁\總數(shù)一百零五頁\編于八點cj23000cBxBb

x1x2x3x4x5000x3x4x54861210040010040010

230004/26/4－cj23000cBxBbx1x2x3x4x500x3x4840010

9/23x23/2010011010-1/21/420-20-3/41/1–8/4目前七十三頁\總數(shù)一百零五頁\編于八點cj23000cBxBbx1x2x3x4x520x1x4400-412

13/23x23/2010011010-1/21/400-201/4–64/2cj23000cBxBbx1x2x3x4x520x1x5200-21/21

73x21011/2-1/821001/40000-3/2-1/40目前七十四頁\總數(shù)一百零五頁\編于八點例目前七十五頁\總數(shù)一百零五頁\編于八點cj230000cBxBb

x1x2x3x4x5x60000x3x4x5x612816122210001201004000100400010

23000012/28/2－12/4000x3x4x516

400010

3x23010001/42620100-1/2100100-1/2目前七十六頁\總數(shù)一百零五頁\編于八點cj230000cBxBbx1x2x3x4x5x60003x3x4x5x262163

20100-1/210010-1/2400010010001/49

20000-3/46/2216/4－0203x3x1x5x22283001-201/210010-1/2000-412010001/44－41213000-201/4目前七十七頁\總數(shù)一百零五頁\編于八點0203x6x1x5x2

4402

002-401101-10000-441001-1/21001400-1/2-100000-201/4134－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cj目前七十八頁\總數(shù)一百零五頁\編于八點0203x3x1x6x2

0442001-1-1/4010001/40000-21/210101/2-1/8014000-3/2-1/80000-201/4134－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cj目前七十九頁\總數(shù)一百零五頁\編于八點例

求線性規(guī)劃問題

目前八十頁\總數(shù)一百零五頁\編于八點00-1/12-7/2433/4

x2x112x1x2x3x4bxBcB2100cj15/43/4011/4-1/810-1/125/24目前八十一頁\總數(shù)一百零五頁\編于八點單純形法解線性規(guī)劃問題習(xí)題P55-2.2目前八十二頁\總數(shù)一百零五頁\編于八點1.無法給出初始基可行解四、大M法2.添加人工變量3.修改目標(biāo)函數(shù)目前八十三頁\總數(shù)一百零五頁\編于八點例先減去再加上加入松弛變量加入人工變量目前八十四頁\總數(shù)一百零五頁\編于八點

加入人工變量后，目的是找到一個單位向量。其目標(biāo)價值系數(shù)要確定，但不能影響目標(biāo)函數(shù)的取值。一般可采用兩種方法處理：大M法和兩階段法。

即假定人工變量在目標(biāo)函數(shù)中的系數(shù)為-M（任意大正數(shù)。如基變量中還存在M，就不能實現(xiàn)極值。大M法：目前八十五頁\總數(shù)一百零五頁\編于八點目前八十六頁\總數(shù)一百零五頁\編于八點0-M0-5+2M3-4M2+3M-17M51-101-5210x6-M70011117X4-Mx6x5x4x3x2x1bxBcB-M0-M-532cj-M+1/7-1/7-M-16/7-50/700102/71/7-1/75/76/70145/7x12-1/71/72/71/7104/7x23x6x5x4x3x2x1bxBcB-M0-M-532cj目前八十七頁\總數(shù)一百零五頁\編于八點一般而言，一個經(jīng)濟、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)；存在著多種方案；要求達到的目標(biāo)是在一定條件下實現(xiàn)的，這些約束可用線性等式或不等式描述。五、線性規(guī)劃在工商管理中的應(yīng)用目前八十八頁\總數(shù)一百零五頁\編于八點1.人力資源分配的問題；2.生產(chǎn)計劃的問題；3.套裁下料問題；4.配料問題；5.投資問題。應(yīng)用舉例目前八十九頁\總數(shù)一百零五頁\編于八點1.人力資源分配的問題

例1：某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下：

設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員?目前九十頁\總數(shù)一百零五頁\編于八點分析：不同上班班次時段的司機和乘務(wù)人員數(shù)設(shè)xi

表示第i班次時開始上班的司機和乘務(wù)人員數(shù)目前九十一頁\總數(shù)一百零五頁\編于八點例2：一家中型的百貨商場，它對售貨員的需求經(jīng)過統(tǒng)計分析如下表所示。為了保證售貨人員充分休息，售貨人員每周工作5天，休息兩天，并要求休息的兩天是連續(xù)的。問應(yīng)該如何安排售貨人員的作息，既滿足工作需要，又使配備的售貨人員的人數(shù)最少？目前九十二頁\總數(shù)一百零五頁\編于八點設(shè)xi

(i=1,2,…,7)表示星期一至日開始工作的人數(shù)。目前九十三頁\總數(shù)一百零五頁\編于八點2.生產(chǎn)計劃的問題例3：某公司面臨一個是外包協(xié)作還是自行生產(chǎn)的問題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？目前九十四頁\總數(shù)一百零五頁\編于八點解：設(shè)x1，x2，x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4，x5

分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。求xi的利潤：利潤=售價-各成本之和產(chǎn)品甲全部自制的利潤=23-(3+2+3)=15

產(chǎn)品甲鑄造外協(xié)，其余自制的利潤=23-(5+2+3)=13

產(chǎn)品乙全部自制的利潤=18-(5+1+2)=10

產(chǎn)品乙鑄造外協(xié)，其余自制的利潤=18-(6+1+2)=9

產(chǎn)品丙的利潤=16-(4+3+2)=7可得到xi

（i=1,2,3,4,5）的利潤分別為15、10、7、13、9元。目前九十五頁\總數(shù)一百零五頁\編于八點通過以上分析,可建立如下的數(shù)學(xué)模型:目標(biāo)函數(shù)：Max15x1+10x2+7x3+13x4+9x5

約束條件：5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0目前九十六頁\總數(shù)一百零五頁\編于八點例5：現(xiàn)有一批某種型號的圓鋼長8米，需要截取2.5米長的毛坯100根，長1.3米的毛坯200根。問如何才能既滿足需要，又能使總的用料最少？100200321002462.5米1.3米需要根數(shù)

一二三四下料下料毛件數(shù)方式坯型號設(shè)變量為第j種方法的所有原料件數(shù)3.套裁下料問題目前九十七頁\總數(shù)一百零五頁\編于八點

例6：某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長7.4m，問：應(yīng)如何下料，可使所用原料最??？解：共可設(shè)計下列5種下料方案，見下表

設(shè)x1,x2,x3,x4,x5分別為上面5種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5

約束條件：s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0目前九十八頁\總數(shù)一百零五頁\編于八點用軟件計算得出最優(yōu)下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=30;x2=10；

x3=0；

x4=50；

x5=0；只需90