簡(jiǎn)單的線(xiàn)性規(guī)劃問(wèn)題(用)

1、 某工廠用某工廠用A A、B B兩種配件生產(chǎn)甲、乙兩種產(chǎn)品兩種配件生產(chǎn)甲、乙兩種產(chǎn)品, ,每生產(chǎn)一件每生產(chǎn)一件甲產(chǎn)品使用甲產(chǎn)品使用4 4個(gè)個(gè)A A配件耗時(shí)配件耗時(shí)1h, 1h, 每生產(chǎn)一件乙產(chǎn)品使用每生產(chǎn)一件乙產(chǎn)品使用4 4個(gè)個(gè)B B配配件耗時(shí)件耗時(shí)2h,2h,該廠每天最多可從配件廠獲得該廠每天最多可從配件廠獲得1616個(gè)個(gè)A A配件和配件和1212個(gè)個(gè)B B配配件件, ,按每天工作按每天工作8 8小時(shí)計(jì)算小時(shí)計(jì)算, ,該廠所有可能的日生產(chǎn)安排是什么該廠所有可能的日生產(chǎn)安排是什么? ?把有關(guān)數(shù)據(jù)列表表示如下把有關(guān)數(shù)據(jù)列表表示如下: :821所需時(shí)間所需時(shí)間1240B種配件種配件1604A種配件

2、種配件資源限額資源限額 乙產(chǎn)品乙產(chǎn)品 (1件件)甲產(chǎn)品甲產(chǎn)品 (1件件)資資 源源消消 耗耗 量量產(chǎn)品產(chǎn)品設(shè)甲、乙兩種產(chǎn)品分別生產(chǎn)設(shè)甲、乙兩種產(chǎn)品分別生產(chǎn)x x、y y件件. .oxy246824280 xy 4x 3y 28,416,412,0,0.xyxyxy 設(shè)甲、乙兩種產(chǎn)品分別生產(chǎn)設(shè)甲、乙兩種產(chǎn)品分別生產(chǎn)x x、y y件件, ,由己知由己知條件可得二元一次不等式組：條件可得二元一次不等式組：oxy24682428,416,412,0,0.xyxyxy 設(shè)甲、乙兩種產(chǎn)品分別生產(chǎn)設(shè)甲、乙兩種產(chǎn)品分別生產(chǎn)x x、y y件件, ,由己知由己知條件可得二元一次不等式組：條件可得二元一次不等式組：

3、280 xy 4x 3y oxy246824280 xy 4x 3y 若生產(chǎn)一件甲產(chǎn)品獲利若生產(chǎn)一件甲產(chǎn)品獲利2 2萬(wàn)元萬(wàn)元, ,生產(chǎn)一件乙產(chǎn)品生產(chǎn)一件乙產(chǎn)品獲利獲利3 3萬(wàn)元萬(wàn)元, ,采用哪種生產(chǎn)安排利潤(rùn)最大采用哪種生產(chǎn)安排利潤(rùn)最大? ? 設(shè)生產(chǎn)甲產(chǎn)品設(shè)生產(chǎn)甲產(chǎn)品 件，乙產(chǎn)品件，乙產(chǎn)品 件時(shí)，工廠獲得件時(shí)，工廠獲得的利潤(rùn)為的利潤(rùn)為 ，則，則 .xyz23zxy230 xy MABN線(xiàn)性約線(xiàn)性約束條件束條件線(xiàn)性目線(xiàn)性目標(biāo)函數(shù)標(biāo)函數(shù)28,416,412,0,0.xyxyxy 23zxy 在線(xiàn)性約束條件下求線(xiàn)性目標(biāo)函數(shù)的最大值或最小值問(wèn)題在線(xiàn)性約束條件下求線(xiàn)性目標(biāo)函數(shù)的最大值或最小值問(wèn)題, ,統(tǒng)稱(chēng)

4、為統(tǒng)稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題線(xiàn)性規(guī)劃問(wèn)題. . 不等組（不等組（1 1）是一組對(duì)變量）是一組對(duì)變量 的約束條件，這組約束條的約束條件，這組約束條件都是關(guān)于件都是關(guān)于 的一次不等式，的一次不等式，所以又稱(chēng)為所以又稱(chēng)為線(xiàn)性約束條件線(xiàn)性約束條件. .、x y、x y 函數(shù)函數(shù) 稱(chēng)為目標(biāo)函稱(chēng)為目標(biāo)函數(shù)數(shù), ,又因這里的又因這里的 是是關(guān)于變量關(guān)于變量 的一次解析式的一次解析式, ,所以又稱(chēng)為所以又稱(chēng)為線(xiàn)性目標(biāo)函數(shù)線(xiàn)性目標(biāo)函數(shù). .23zxy 23zxy 、x y可行域可行域可行解可行解最優(yōu)解最優(yōu)解oxy246824280 xy 4x 3y 230 xy M 由所有可行解組由所有可行解組成的集合叫做成的集合叫做

5、可行域可行域. . 使目標(biāo)函數(shù)取得使目標(biāo)函數(shù)取得最大值或最小值的可最大值或最小值的可行解叫做線(xiàn)性規(guī)劃問(wèn)行解叫做線(xiàn)性規(guī)劃問(wèn)題的題的最優(yōu)解最優(yōu)解. . 滿(mǎn)足線(xiàn)性約束條滿(mǎn)足線(xiàn)性約束條件的解件的解 叫做叫做可行解可行解. .( ,)x y解決線(xiàn)性規(guī)劃問(wèn)題的步驟解決線(xiàn)性規(guī)劃問(wèn)題的步驟：第一步：畫(huà)根據(jù)約束條件畫(huà)出可行域；第二步：作過(guò)原點(diǎn)作目標(biāo)函數(shù)直線(xiàn)的平行直線(xiàn)L0第三步：移平移直線(xiàn)L0，找出與可行域有公共 點(diǎn)且縱截距最大或最小的直線(xiàn)，確定可行 域內(nèi)最優(yōu)解。第四步：求解有關(guān)方程組，求出最優(yōu)解，將最 優(yōu)解代入目標(biāo)函數(shù)求最值。280 xy 4x 3y Moxy246824N28 ,41 6 ,41 2 ,0 ,

6、0 .xyxyxy 在線(xiàn)性約束條件在線(xiàn)性約束條件 下，下，求（求（1 1）目標(biāo)函數(shù)）目標(biāo)函數(shù) 的最大值；的最大值； （2 2）目標(biāo)函數(shù)）目標(biāo)函數(shù) 的最大值和最小值的最大值和最小值. .2zxy zxy20 xy0 xyAB 求求z=2x-yz=2x-y最大值與最小值最大值與最小值 。設(shè)設(shè)x,y滿(mǎn)足約束條件：滿(mǎn)足約束條件：作可行域（如圖）因此z在A（2，-1）處取得最大值，即Zmax=22+1=5；在B（-1，-1）處取得最小值，即Zmin=2（-1）-（-1）=-1。由z=2x-y得y=2x-z,因此平行移動(dòng)直線(xiàn)y=2x，若直線(xiàn)截距-z取得最大值，則z取得最小值；截距-z取得最小值，則z取得最

7、大值.綜上,z最大值為5；z最小值為-1.舉一反三舉一反三x-y0 x+y-1 0y -1解：y=-1x-y=0 x+y=1(-1,-1)xy011A AB BC（2，-1）y=2x 求求z=-x-yz=-x-y最大值與最小值最大值與最小值 。設(shè)設(shè)x,y滿(mǎn)足約束條件：滿(mǎn)足約束條件：作可行域（如圖）因此z在B（-1，-1）處截距-z取得最小值，z取得最大值即Zmax=2；在邊界AC處取得截距-z最大值，z取得最小值即Zmin=-2-（-1）=-1。由z=-x-y得y=-x-z,因此平行移動(dòng)直線(xiàn)y=-x，若直線(xiàn)截距-z取得最大值，則z取得最小值；截距-z取得最小值，則z取得最大值.變式演練變式演練

8、x-y0 x+y-1 0y -1解：y=-1x-y=0 x+y=1(-1,-1)xy011A AB BC（2，-1）y=-x例例1.1.營(yíng)養(yǎng)學(xué)家指出營(yíng)養(yǎng)學(xué)家指出, ,成人良好的日常飲食應(yīng)該至少提供成人良好的日常飲食應(yīng)該至少提供0.075kg0.075kg的碳水化合物的碳水化合物,0.06kg,0.06kg的蛋白質(zhì)的蛋白質(zhì),0.06kg,0.06kg的脂肪的脂肪.1kg.1kg食物食物A A含有含有0.105kg0.105kg碳水化合物碳水化合物,0.07 kg,0.07 kg的蛋白質(zhì)的蛋白質(zhì), 0.14kg, 0.14kg的脂肪的脂肪, ,花費(fèi)花費(fèi)2828元元; ;而而1kg1kg食物食物B

9、B含有含有0.105kg0.105kg碳水化合物碳水化合物,0.14 kg,0.14 kg的蛋白質(zhì)的蛋白質(zhì), , 0.07kg0.07kg的脂肪的脂肪, ,花費(fèi)花費(fèi)2121元元. .為了滿(mǎn)足營(yíng)養(yǎng)學(xué)家指出的日常飲食要為了滿(mǎn)足營(yíng)養(yǎng)學(xué)家指出的日常飲食要求求, ,同時(shí)使同時(shí)使花費(fèi)花費(fèi)最低最低, ,需要同時(shí)食用需要同時(shí)食用食物食物A A和食物和食物B B多少多少kgkg? ?分析分析: :將已知數(shù)據(jù)列成下表將已知數(shù)據(jù)列成下表0.070.140.1050.140.070.105BA脂肪脂肪/kg蛋白質(zhì)蛋白質(zhì)/kg碳水化合物碳水化合物/kg食物食物/kg解解:設(shè)每天食用設(shè)每天食用xkg食物食物A, ykg食

10、物食物B, 總成本為總成本為z元元. 那么那么x,y滿(mǎn)足的約束條件是滿(mǎn)足的約束條件是:0 1050 1050 0750 070 140 060 140 070 06 00.x.y.,.x.y.,.x.y.,x,y.目標(biāo)函數(shù)為目標(biāo)函數(shù)為z=28x+21y . 0, 0 , 6714, 6147, 577yxyxyxyx二元一次不等式組二元一次不等式組等價(jià)于等價(jià)于作出二元一次不等式組作出二元一次不等式組所所表示的平面區(qū)域，即可行域表示的平面區(qū)域，即可行域. . 775xy1476xy7146xy42821321zzxyyx 可化為34 這是斜率為這是斜率為 、在、在y軸上的截距為軸上的截距為 的一

11、組平行直線(xiàn)的一組平行直線(xiàn). .21zxyo737475761737576由圖知由圖知,當(dāng)直線(xiàn)當(dāng)直線(xiàn)經(jīng)過(guò)可行域上點(diǎn)經(jīng)過(guò)可行域上點(diǎn)M時(shí)時(shí),截距截距21z最小最小, 即即z最小最小.解方程組解方程組7751476xy,xy, 得得M的坐標(biāo)為的坐標(biāo)為14()77,.所以所以zmin=28x+21y=16.答：每天食用食物答：每天食用食物A約為約為143g，食物，食物B約約571g，能夠滿(mǎn)足日，能夠滿(mǎn)足日常飲食要求，又使花費(fèi)最低，最低成本為常飲食要求，又使花費(fèi)最低，最低成本為16元元.4321zyx 775xy1476xy7146xyxyo737475761737576M線(xiàn)性目標(biāo)函數(shù)的最線(xiàn)性目標(biāo)函數(shù)的最

12、大（小）值一般在大（?。┲狄话阍诳尚杏虻捻旤c(diǎn)處取可行域的頂點(diǎn)處取得，也可能在邊界得，也可能在邊界處取得處取得.解線(xiàn)性規(guī)劃應(yīng)用問(wèn)題的步驟：解線(xiàn)性規(guī)劃應(yīng)用問(wèn)題的步驟： （3）移移：在線(xiàn)性目標(biāo)函數(shù)所表示的一組平行線(xiàn)中，：在線(xiàn)性目標(biāo)函數(shù)所表示的一組平行線(xiàn)中，利用平移的方法找出與可行域有公共點(diǎn)且縱截距最大利用平移的方法找出與可行域有公共點(diǎn)且縱截距最大或最小的直線(xiàn)；或最小的直線(xiàn)； （4）求求：通過(guò)解方程組求出最優(yōu)解；：通過(guò)解方程組求出最優(yōu)解； （5）答答：作出答案。：作出答案。 （1）列列：設(shè)出未知數(shù)：設(shè)出未知數(shù),列出約束條件列出約束條件,確定目標(biāo)函數(shù)；確定目標(biāo)函數(shù)；（2）畫(huà)畫(huà)：畫(huà)出線(xiàn)性約束條件所表示的可

13、行域；：畫(huà)出線(xiàn)性約束條件所表示的可行域；注：注：1.線(xiàn)性目標(biāo)函數(shù)的最大（?。┲狄话阍诳尚杏虻捻斁€(xiàn)性目標(biāo)函數(shù)的最大（?。┲狄话阍诳尚杏虻捻旤c(diǎn)處取得，也可能在邊界處取得。點(diǎn)處取得，也可能在邊界處取得。2.求線(xiàn)性目標(biāo)函數(shù)的最優(yōu)解，要注意分析線(xiàn)性目標(biāo)函數(shù)求線(xiàn)性目標(biāo)函數(shù)的最優(yōu)解，要注意分析線(xiàn)性目標(biāo)函數(shù)所表示的幾何意義所表示的幾何意義 在在 y 軸上的截距或其相反數(shù)。軸上的截距或其相反數(shù)。小結(jié)小結(jié)例例2.要將兩種大小不同的鋼板截成要將兩種大小不同的鋼板截成A、B、C三種規(guī)格，每三種規(guī)格，每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如下表所示張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如下表所示321第二種鋼板第二種

14、鋼板112第一種鋼板第一種鋼板C規(guī)格規(guī)格B規(guī)格規(guī)格A規(guī)格規(guī)格鋼板類(lèi)型鋼板類(lèi)型規(guī)格類(lèi)型規(guī)格類(lèi)型今需今需A、B、C三種規(guī)格的成品分別三種規(guī)格的成品分別15，18，27塊，則使用塊，則使用鋼板張數(shù)最少為多少？鋼板張數(shù)最少為多少？21521832700 xyxyxyxy解：解：設(shè)需截第一種鋼板設(shè)需截第一種鋼板x張，第二種鋼板張，第二種鋼板y張，共需要張，共需要z張，張，則目標(biāo)函數(shù)為：則目標(biāo)函數(shù)為：z=x+y，且，且( ,)x yZ2x+y=15x+2y=18x+3y=27xyO4812162048121620242830作出可行域，如下圖，作出可行域，如下圖，把把z=x+y化為化為y=-x+z，這是斜

15、率為這是斜率為-1，在，在y軸上的截距為軸上的截距為z的一組平行直線(xiàn)，的一組平行直線(xiàn)，y=-xM如圖可知，當(dāng)直線(xiàn)如圖可知，當(dāng)直線(xiàn)y=-x+z經(jīng)過(guò)可行域上的整點(diǎn)經(jīng)過(guò)可行域上的整點(diǎn)A(4，8)，B(3，9)時(shí)，直線(xiàn)在時(shí)，直線(xiàn)在y軸上的截距軸上的截距z最小最小zmin=12答：略。答：略。B(3,9)A(4,8)在可行域內(nèi)找出最優(yōu)解、線(xiàn)性規(guī)劃整數(shù)解問(wèn)題的一般在可行域內(nèi)找出最優(yōu)解、線(xiàn)性規(guī)劃整數(shù)解問(wèn)題的一般方法是：方法是：1.若區(qū)域若區(qū)域“頂點(diǎn)頂點(diǎn)”處恰好為整點(diǎn)，那么它就是最優(yōu)解；處恰好為整點(diǎn)，那么它就是最優(yōu)解；（在包括邊界的情況下）（在包括邊界的情況下）2.若區(qū)域若區(qū)域“頂點(diǎn)頂點(diǎn)”不是整點(diǎn)或不包括邊界

16、時(shí)，應(yīng)先求出不是整點(diǎn)或不包括邊界時(shí)，應(yīng)先求出該點(diǎn)坐標(biāo)，并計(jì)算目標(biāo)函數(shù)值該點(diǎn)坐標(biāo)，并計(jì)算目標(biāo)函數(shù)值Z，然后在可行域內(nèi)，然后在可行域內(nèi)適適當(dāng)放縮目標(biāo)函數(shù)值，使它為整數(shù)，且與當(dāng)放縮目標(biāo)函數(shù)值，使它為整數(shù)，且與Z最接近，最接近，在在這條對(duì)應(yīng)的直線(xiàn)中，取可行域內(nèi)整點(diǎn)，如果沒(méi)有整點(diǎn)這條對(duì)應(yīng)的直線(xiàn)中，取可行域內(nèi)整點(diǎn)，如果沒(méi)有整點(diǎn)，繼續(xù)放縮，直至取到整點(diǎn)為止。，繼續(xù)放縮，直至取到整點(diǎn)為止。3.在可行域內(nèi)找整數(shù)解，一般采用平移找解法，即在可行域內(nèi)找整數(shù)解，一般采用平移找解法，即打網(wǎng)打網(wǎng)格、找整點(diǎn)、平移直線(xiàn)、找出整數(shù)最優(yōu)解格、找整點(diǎn)、平移直線(xiàn)、找出整數(shù)最優(yōu)解不等式組不等式組 表示的平面區(qū)域內(nèi)的表示的平面區(qū)域內(nèi)的整數(shù)點(diǎn)整數(shù)點(diǎn)共有共有（ ）個(gè)）個(gè)123400yxyx鞏固練習(xí)鞏