運(yùn)籌學(xué)第一次課

1第一章線性規(guī)劃問(wèn)題及單純型解法1.1一般線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型

1.1.1線性規(guī)劃問(wèn)題舉例

1.1.2線性規(guī)劃數(shù)學(xué)模型

1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式(重點(diǎn)）

1.1.4標(biāo)準(zhǔn)型解的若干基本概念（難點(diǎn)）21.1線性規(guī)劃問(wèn)題及其一般數(shù)學(xué)模型1.1.1線性規(guī)劃問(wèn)題舉例例1、多產(chǎn)品生產(chǎn)問(wèn)題:某工廠計(jì)劃用現(xiàn)有的銅、鉛兩種資源生產(chǎn)甲、乙兩種電纜，已知甲、乙兩種電纜的單位售價(jià)分別為6萬(wàn)元和4萬(wàn)元，生產(chǎn)產(chǎn)品甲乙電纜對(duì)銅鉛的消耗量及可利用的銅鉛數(shù)量如右表，另外市場(chǎng)對(duì)乙電纜最大需求為7單位，對(duì)甲電纜需求無(wú)限制，問(wèn)工廠應(yīng)如何安排生產(chǎn)才能使收益最大？甲電纜乙電纜資源量銅2110鉛118價(jià)格643例2、配料問(wèn)題（min,

)設(shè)x1,x2分別代表每粒膠丸中甲、乙兩種原料的用量4三個(gè)要素：決策變量目標(biāo)函數(shù)約束條件1.1.2線性規(guī)劃數(shù)學(xué)模型5一般表示方式61.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式（重點(diǎn)）為了使線性規(guī)劃問(wèn)題的解法標(biāo)準(zhǔn)，就要把一般形式化為標(biāo)準(zhǔn)形式7

變換的方法：1目標(biāo)函數(shù)為min型，價(jià)值系數(shù)一律反號(hào)。令f

(x)=-f(x)=-CX,有minf(x)=-max[-

f(x)]=-maxf(x)2第i個(gè)約束的bi

為負(fù)值，則該行左右兩端系數(shù)同時(shí)反號(hào)，同時(shí)不等號(hào)也要反向3第i個(gè)約束為型，在不等式左邊增加一個(gè)非負(fù)的變量xn+i

，稱為松弛變量；同時(shí)令cn+i

=04第i個(gè)約束為型，在不等式左邊減去一個(gè)非負(fù)的變量xn+i

，稱為剩余變量；同時(shí)令cn+i

=05若xj0，令

xj=-xj

，代入非標(biāo)準(zhǔn)型，則有xj

06若xj

不限，令

xj=xj

-

xj

，xj

0，xj

0，代入非標(biāo)準(zhǔn)型例381.1.4標(biāo)準(zhǔn)型解的若干基本概念（難點(diǎn)）：基:在約束方程中線性無(wú)關(guān)的m列，構(gòu)成該標(biāo)準(zhǔn)型的一個(gè)基，即B=(P1

,P2

,…,Pm)，|B|0

P1

,P2

,…,Pm

稱為基向量與基向量對(duì)應(yīng)的變量稱為基變量，記為XB=(x1

,x2

,…,xm

)T，其余的變量稱為非基變量，記為XN=(xm+1

,xm+2

,…,xm+N

)T

，最多有個(gè)基2基本解令非基變量XN=0，求得基變量XB的值稱為基本解（又稱基解），即XB=B

1

b93可行解與非可行解滿足約束條件和非負(fù)條件的解X稱為可行解，滿足約束條件但不滿足非負(fù)條件的解X稱為非可行解全部可行解的集合稱為可行域。4基本可行解基本解XB的非零分量都

0時(shí)，稱為基本可行解，否