332簡(jiǎn)單的線性規(guī)劃問(wèn)題(一)

1、3.3.2簡(jiǎn)單的線性規(guī)劃簡(jiǎn)單的線性規(guī)劃問(wèn)題問(wèn)題(一一) 1. 某工廠用某工廠用A、B兩種配件生產(chǎn)甲、乙兩種產(chǎn)品，每?jī)煞N配件生產(chǎn)甲、乙兩種產(chǎn)品，每生產(chǎn)一件甲產(chǎn)品使用生產(chǎn)一件甲產(chǎn)品使用4個(gè)個(gè)A配件耗時(shí)配件耗時(shí)1h，每生產(chǎn)一件，每生產(chǎn)一件乙產(chǎn)品使用乙產(chǎn)品使用4個(gè)個(gè)B配件耗時(shí)配件耗時(shí)2h，該廠最多可從配件廠，該廠最多可從配件廠獲得獲得16個(gè)個(gè)A配件和配件和12個(gè)個(gè)B配件，按每天工作配件，按每天工作8h計(jì)算，計(jì)算，該廠所有的日生產(chǎn)安排是什么？該廠所有的日生產(chǎn)安排是什么？AB時(shí)間時(shí)間甲甲401乙乙042xy(1) 設(shè)甲、乙兩種產(chǎn)品分別生產(chǎn)設(shè)甲、乙兩種產(chǎn)品分別生產(chǎn)x、y件，由已知件，由已知條件可得二元一次不

2、等式組：條件可得二元一次不等式組：分析：分析： .0,0,124,164,82 yxyxyx(3)若生產(chǎn)一件甲產(chǎn)品獲利若生產(chǎn)一件甲產(chǎn)品獲利2萬(wàn)元，生產(chǎn)一萬(wàn)元，生產(chǎn)一件乙產(chǎn)品獲利件乙產(chǎn)品獲利3萬(wàn)元，采用哪種生產(chǎn)安排萬(wàn)元，采用哪種生產(chǎn)安排利潤(rùn)最大？利潤(rùn)最大？(2)將上述不等式組表示成平面上的區(qū)域，將上述不等式組表示成平面上的區(qū)域，3y082yx4x4384Oxy(3)若生產(chǎn)一件甲產(chǎn)品獲利若生產(chǎn)一件甲產(chǎn)品獲利2萬(wàn)元，生產(chǎn)一萬(wàn)元，生產(chǎn)一件乙產(chǎn)品獲利件乙產(chǎn)品獲利3萬(wàn)元，采用哪種生產(chǎn)安排萬(wàn)元，采用哪種生產(chǎn)安排利潤(rùn)最大？利潤(rùn)最大？設(shè)生產(chǎn)甲產(chǎn)品設(shè)生產(chǎn)甲產(chǎn)品x乙產(chǎn)品乙產(chǎn)品y件時(shí)，工廠獲得的件時(shí)，工廠獲得的利潤(rùn)為

3、利潤(rùn)為z,則則z=2x+3y.上述問(wèn)題就轉(zhuǎn)化為：上述問(wèn)題就轉(zhuǎn)化為：當(dāng)當(dāng)x、y滿足上述不等式（組）并且為非負(fù)滿足上述不等式（組）并且為非負(fù)整數(shù)時(shí)，整數(shù)時(shí)，z的最大值是多少？的最大值是多少？1. 上述問(wèn)題中，不等式組是一組對(duì)變量上述問(wèn)題中，不等式組是一組對(duì)變量x、y的的約束條件約束條件， 這組約束條件都是關(guān)于這組約束條件都是關(guān)于x、y的一次不等式，所以又的一次不等式，所以又叫叫線性約束條件線性約束條件.線性約束條件除了用一次不等式表示外，有時(shí)也用線性約束條件除了用一次不等式表示外，有時(shí)也用一次方程表示一次方程表示.2. 欲求最大值或最小值的函數(shù)欲求最大值或最小值的函數(shù)z=2x+3y叫做叫做目標(biāo)函數(shù)

4、目標(biāo)函數(shù). 由于由于 z=2x+y又是又是x、y的一次解析式，所以又叫的一次解析式，所以又叫線性目標(biāo)函數(shù)線性目標(biāo)函數(shù). 5. 由所有可行解組成的集合叫做由所有可行解組成的集合叫做可行域可行域. 6. 使目標(biāo)函數(shù)取得最大值或最小值的可行解，它們都使目標(biāo)函數(shù)取得最大值或最小值的可行解，它們都叫做這個(gè)問(wèn)題的叫做這個(gè)問(wèn)題的最優(yōu)解最優(yōu)解.3. 一般地，求線性目標(biāo)函數(shù)在線性約束條件下的最大值或一般地，求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問(wèn)題，統(tǒng)稱為最小值的問(wèn)題，統(tǒng)稱為線性規(guī)劃問(wèn)題線性規(guī)劃問(wèn)題. 4. 滿足線性約束條件的解滿足線性約束條件的解(x,y)叫做叫做可行解可行解. 例題分析例題分析 例

5、例1. 設(shè)設(shè) z2xy，式中變量，式中變量x、 y滿足滿足下列條件：下列條件：求求z的最大值和最小值的最大值和最小值.)1( , 1,2553, 34 xyxyx42246OCAB02553 yx034 yx1x) 1 ( , 1,2553, 34 xyxyxyx 我們先畫(huà)出不等式組我們先畫(huà)出不等式組(1)表示的平面區(qū)表示的平面區(qū)域，如圖中域，如圖中ABC內(nèi)部且包括邊界，點(diǎn)內(nèi)部且包括邊界，點(diǎn)(0,0)不在這個(gè)三角形區(qū)域內(nèi)，不在這個(gè)三角形區(qū)域內(nèi)，方程方程2x+y=z表示斜率為表示斜率為-2的直線，的直線， y42246OCAB02553 yx034 yx1xyx當(dāng)當(dāng)z=0時(shí)，時(shí)，直線過(guò)原點(diǎn)，直線

6、過(guò)原點(diǎn)，隨著隨著z值得變化，值得變化，直線直線2x+y=z平行移動(dòng)平行移動(dòng)思考：在這里，思考：在這里，z表示的幾何意表示的幾何意義是什么？義是什么？如圖可知，如圖可知，當(dāng)當(dāng)l在在l0的右上方時(shí)，的右上方時(shí)，直線直線l上的點(diǎn)上的點(diǎn)(x,y)滿足滿足2x+y0. 即即z0，而且，而且l 往右往右平移時(shí)，平移時(shí)，z隨之增隨之增大，在經(jīng)過(guò)不等式大，在經(jīng)過(guò)不等式組組(1)表示的三角形表示的三角形區(qū)域內(nèi)的點(diǎn)且平行區(qū)域內(nèi)的點(diǎn)且平行于于l的直線中，我們發(fā)現(xiàn)：的直線中，我們發(fā)現(xiàn)：y42246OCAB02553 yx034 yx1xyx（2）經(jīng)過(guò)點(diǎn)）經(jīng)過(guò)點(diǎn)B(1,1)的直線的直線 l1 所對(duì)應(yīng)的所對(duì)應(yīng)的z最小最小

7、.y42246OCAB02553 yx034 yx1xyx）（ 2 , 5（1）經(jīng)過(guò)點(diǎn)）經(jīng)過(guò)點(diǎn)A(5,2)的直線的直線 l2 所對(duì)應(yīng)的所對(duì)應(yīng)的z最大，最大，）（ 1 , 1所以：所以：z的最大值為的最大值為1212 z z的最小值為的最小值為3 3練習(xí)練習(xí)1.解下列線性規(guī)劃問(wèn)題：求解下列線性規(guī)劃問(wèn)題：求z2xy的最大值和的最大值和最小值，使式中的最小值，使式中的x、y滿足滿足.11yyxxy約束條件約束條件解：先作出可行域，解：先作出可行域，xy yxOABC11見(jiàn)圖中見(jiàn)圖中ABC表示的區(qū)域表示的區(qū)域, 且求得且求得01 yx01y當(dāng)當(dāng)l0平行線平行線l2過(guò)過(guò)C點(diǎn)點(diǎn)時(shí)，可使時(shí)，可使z=2x+y

8、達(dá)達(dá)到最大值到最大值.解：先作出可行域，見(jiàn)圖中解：先作出可行域，見(jiàn)圖中ABC表示的表示的區(qū)域區(qū)域, 且求得且求得).1, 2( ) 1, 1( )21,21(CBA、)1, 1( Bxy yxOABC1101 yx01y作出直線作出直線l0:2x+y=0，再將直線平移，當(dāng)再將直線平移，當(dāng)l0平平行線行線l1過(guò)過(guò)B點(diǎn)時(shí)，可使點(diǎn)時(shí)，可使 z=2x+y達(dá)到最小值，達(dá)到最小值，zmin=2( 1)+( 1)= 3，zmax=22+( 1)=3.所以：xy yxOA1101 yx01y) 1, 1(B).1, 2( C解答線性規(guī)劃問(wèn)題的步驟：解答線性規(guī)劃問(wèn)題的步驟：u第一步：根據(jù)約束條件畫(huà)出可行域；第一

9、步：根據(jù)約束條件畫(huà)出可行域；u第二步：令第二步：令z0，畫(huà)直線，畫(huà)直線l0；u第三步：觀察，分析，平移直線第三步：觀察，分析，平移直線l0， 從而找到最優(yōu)解；從而找到最優(yōu)解；u第四步：求出目標(biāo)函數(shù)的最大值或最第四步：求出目標(biāo)函數(shù)的最大值或最 小值小值.例例2.求求zxy的取值范圍，使式中的的取值范圍，使式中的x、y滿足約束滿足約束條件：條件：0102022yxyx例例3.求求zx2y2的最大值和最小值，使式中的的最大值和最小值，使式中的x、y滿足約束條件：滿足約束條件：,. 03201234, 072yxyxyx引例：引例： 某工廠用某工廠用A、B兩種配件生產(chǎn)甲、乙兩種產(chǎn)品，兩種配件生產(chǎn)甲、乙

10、兩種產(chǎn)品，每生產(chǎn)一件甲產(chǎn)品使用每生產(chǎn)一件甲產(chǎn)品使用4個(gè)個(gè)A配件耗時(shí)配件耗時(shí)1h，每生產(chǎn)一，每生產(chǎn)一件乙產(chǎn)品使用件乙產(chǎn)品使用4個(gè)個(gè)B配件耗時(shí)配件耗時(shí)2h，該廠最多可從配件，該廠最多可從配件廠獲得廠獲得16個(gè)個(gè)A配件和配件和12個(gè)個(gè)B配件，按每天工作配件，按每天工作8h計(jì)算，計(jì)算，若生產(chǎn)一件甲產(chǎn)品獲利若生產(chǎn)一件甲產(chǎn)品獲利2萬(wàn)元，生產(chǎn)一件乙產(chǎn)品獲利萬(wàn)元，生產(chǎn)一件乙產(chǎn)品獲利3萬(wàn)元，采用哪種生產(chǎn)安排利潤(rùn)最大？萬(wàn)元，采用哪種生產(chǎn)安排利潤(rùn)最大？解：設(shè)甲、乙兩種產(chǎn)品分別生產(chǎn)解：設(shè)甲、乙兩種產(chǎn)品分別生產(chǎn)x、y件，由已知件，由已知條件可得二元一次不等式組：條件可得二元一次不等式組： . 0, 0,124,164,

11、 82 yxyxyx3y082yx4x4384Oxy將不等式組表示的將不等式組表示的平面區(qū)域畫(huà)出如圖平面區(qū)域畫(huà)出如圖所示：所示：設(shè)生產(chǎn)甲產(chǎn)品設(shè)生產(chǎn)甲產(chǎn)品x乙產(chǎn)品乙產(chǎn)品y件時(shí)，工廠獲得的利潤(rùn)為件時(shí)，工廠獲得的利潤(rùn)為z,則則z=2x+3y3y082yx4x4384Oxy）（ 2 , 4P14maxZ即：生產(chǎn)甲產(chǎn)品4件，乙產(chǎn)品2件時(shí)，利潤(rùn)最大為14萬(wàn)元解：設(shè)需截第一種鋼板x張，第二種鋼板y張，共需截這兩張鋼板z張，則目標(biāo)函數(shù)為：yxz00273182152yxyxyxyx畫(huà)出可行域，如圖0246810y121416181810 12 141620 222624648x228152yx182 yx273 yxMB(3,9)C(4,8)最小時(shí)，截距經(jīng)過(guò)可行域上點(diǎn)當(dāng)直線zMyxzzxyyxz），的坐標(biāo)為（得點(diǎn)解方程組539518152273Myxyx）不是最優(yōu)整數(shù)解，（點(diǎn)539518,MNyx128493minzCB），得，（）和，（經(jīng)調(diào)整得最優(yōu)解的最大值和最小值。，求滿足約束條件、已知例3051,4xyzxyxyxyx501 234671234598-1-2-3xy01 yxABC05yx）的連線的斜率與