簡單的線性規(guī)劃問題(用)

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

2、種配件資源限額資源限額 乙產(chǎn)品乙產(chǎn)品 (1件件)甲產(chǎn)品甲產(chǎn)品 (1件件)資資 源源消消 耗耗 量量產(chǎn)品產(chǎn)品設甲、乙兩種產(chǎn)品分別生產(chǎn)設甲、乙兩種產(chǎn)品分別生產(chǎn)x x、y y件件. .oxy246824280 xy 4x 3y 28,416,412,0,0.xyxyxy 設甲、乙兩種產(chǎn)品分別生產(chǎn)設甲、乙兩種產(chǎn)品分別生產(chǎn)x x、y y件件, ,由己知由己知條件可得二元一次不等式組：條件可得二元一次不等式組：oxy24682428,416,412,0,0.xyxyxy 設甲、乙兩種產(chǎn)品分別生產(chǎn)設甲、乙兩種產(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萬元萬元, ,生產(chǎn)一件乙產(chǎn)品生產(chǎn)一件乙產(chǎn)品獲利獲利3 3萬元萬元, ,采用哪種生產(chǎn)安排利潤最大采用哪種生產(chǎn)安排利潤最大? ? 設生產(chǎn)甲產(chǎn)品設生產(chǎn)甲產(chǎn)品 件，乙產(chǎn)品件，乙產(chǎn)品 件時，工廠獲得件時，工廠獲得的利潤為的利潤為 ，則，則 .xyz23zxy230 xy MABN線性約線性約束條件束條件線性目線性目標函數(shù)標函數(shù)28,416,412,0,0.xyxyxy 23zxy 在線性約束條件下求線性目標函數(shù)的最大值或最小值問題在線性約束條件下求線性目標函數(shù)的最大值或最小值問題, ,統(tǒng)稱

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

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

6、0 .xyxyxy 在線性約束條件在線性約束條件 下，下，求（求（1 1）目標函數(shù)）目標函數(shù) 的最大值；的最大值； （2 2）目標函數(shù)）目標函數(shù) 的最大值和最小值的最大值和最小值. .2zxy zxy20 xy0 xyAB 求求z=2x-yz=2x-y最大值與最小值最大值與最小值 。設設x,y滿足約束條件：滿足約束條件：作可行域（如圖）因此z在A（2，-1）處取得最大值，即Zmax=22+1=5；在B（-1，-1）處取得最小值，即Zmin=2（-1）-（-1）=-1。由z=2x-y得y=2x-z,因此平行移動直線y=2x，若直線截距-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最大值與最小值最大值與最小值 。設設x,y滿足約束條件：滿足約束條件：作可行域（如圖）因此z在B（-1，-1）處截距-z取得最小值，z取得最大值即Zmax=2；在邊界AC處取得截距-z最大值，z取得最小值即Zmin=-2-（-1）=-1。由z=-x-y得y=-x-z,因此平行移動直線y=-x，若直線截距-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)學家指出, ,成人良好的日常飲食應該至少提供成人良好的日常飲食應該至少提供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的脂肪的脂肪, ,花費花費2828元元; ;而而1kg1kg食物食物B

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

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

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

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

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

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

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

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