簡單線性規(guī)劃(整點解問題)

1、懷化鐵路第一中學7.47.4簡單的線型規(guī)劃簡單的線型規(guī)劃(3)(3)整點解問題整點解問題懷化鐵路第一中學一、朝花夕拾一、朝花夕拾 圖解法解簡單線性規(guī)劃問題的步驟圖解法解簡單線性規(guī)劃問題的步驟(1)畫可行域；畫可行域；(2)比較斜率，畫目標直線比較斜率，畫目標直線l；(3)平移平移l，找最優(yōu)解；，找最優(yōu)解；(4) 求交算出最優(yōu)解，并求最值求交算出最優(yōu)解，并求最值解簡單線性規(guī)劃應用題的步驟解簡單線性規(guī)劃應用題的步驟(列列)設設寫寫作作移移定定答答懷化鐵路第一中學已知已知2x+y 15x+2y 18x+3y 27x 0y0求求z=x+y的最小值的最小值xyO O3 6 9 1215182124273

2、6912152x+y=15x+2y=18x+3y=27A解：解：如圖，作出可行域如圖，作出可行域并作出直線并作出直線l：x+y=z顯然，當顯然，當l過點過點A時，時，z最小最小zx+y=z由由2x+y = 15x+3y =2734(3, 7)55A得得故當故當x=335，y=475時，時，zmin=2305懷化鐵路第一中學 要將兩種大小不同的鋼板截成要將兩種大小不同的鋼板截成A A、B B、C C三種規(guī)格，每三種規(guī)格，每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示：張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示：321第二種鋼板第二種鋼板112第一種鋼板第一種鋼板C C規(guī)格規(guī)格B B規(guī)格

3、規(guī)格A A規(guī)格規(guī)格規(guī)格類型規(guī)格類型鋼板類型鋼板類型 今需要今需要A A、B B、C C三種規(guī)格的成品分別為三種規(guī)格的成品分別為1515、1818、2727塊。塊。問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所用鋼板張數(shù)最少。用鋼板張數(shù)最少。問題問題二、探索研究二、探索研究懷化鐵路第一中學（1） (列列)（2）設：設：所需截第一種鋼板所需截第一種鋼板x張，第二種鋼板張，第二種鋼板y張，兩種鋼張，兩種鋼板共板共z張張.（3）寫：寫：線性約束條件線性約束條件目標函數(shù)：目標函數(shù)：yxz規(guī)格類型規(guī)格類型鋼板類型鋼板類型第一種鋼板第一種鋼板第二種鋼板第

4、二種鋼板A 規(guī)格規(guī)格B 規(guī)格規(guī)格C 規(guī)格規(guī)格211123各規(guī)格成品數(shù)各規(guī)格成品數(shù)151827152yx 182yx273yx0 x0yxxxxyyyy幾何畫板演示幾何畫板演示懷化鐵路第一中學（6）定定:平移找解法平移找解法:打網(wǎng)格打網(wǎng)格,描整點描整點,平移目標函數(shù)線平移目標函數(shù)線, 確定首確定首先經(jīng)過的整點先經(jīng)過的整點. 要求作圖準確，易要求作圖準確，易出現(xiàn)模糊點，可操作出現(xiàn)模糊點，可操作性不強！性不強！懷化鐵路第一中學優(yōu)值調(diào)整法優(yōu)值調(diào)整法: 當當直線直線x+y=z 移至移至A(3.6,7.8)時時, zmin=11.4, 由由x,y取整數(shù)知取整數(shù)知: z 必為整數(shù)必為整數(shù), 先先將將z調(diào)整調(diào)

5、整為為12, 即即x+y=12, y=12-x或或 x=12-y, 將將y=12-x代入約束條件得：代入約束條件得：,y,y,y,y00273182152xxxx,1,)(,)(,)(020271231812215122xxxxxxxx,1202963xxxxx543.x,43xx或或8493yyxx，或或若調(diào)整若調(diào)整z=12仍無整數(shù)解，應繼續(xù)調(diào)整，直到找到為止仍無整數(shù)解，應繼續(xù)調(diào)整，直到找到為止. 懷化鐵路第一中學y=8第第一一變：變：已知已知2x+y 15x+2y 18x+3y 27xNyN求求z=2x+3y的最小值的最小值解：解：如圖，作出可行域如圖，作出可行域并作出直線并作出直線l：2

6、x+3y=z 顯然，當顯然，當l移至過移至過A(3.6,7.8)時時, zmin=30.6 但由但由x,y N知知: z N 先先將將z調(diào)整調(diào)整為為31, 即即2x+3y=31, 得得y=(31-2x)/3, 代入線性約束條件代入線性約束條件整理得整理得 3.5x 4故故x=4， y=23/3不合題意不合題意再再將將z調(diào)整調(diào)整為為32, 即即2x+3y=32, 得得y=(32-2x)/3, 代入線性約束條件代入線性約束條件整理得整理得 3.25x 5故故x=4x=5y=22/3或或(舍舍)即當即當x=4，y=8時時zmin=32懷化鐵路第一中學第第二二變：變：已知已知2x+y 15x+2y 1

7、8x+3y 27xNyN求求z=10 x+10y的最小值的最小值解：解：如圖，作出可行域如圖，作出可行域并作出直線并作出直線l：10 x+10y=z 顯然，當顯然，當l移至過移至過A(3.6,7.8)時時, zmin=114 但由但由x,y N知知: z是是10的倍數(shù)的倍數(shù)先先將將z調(diào)整調(diào)整為為120, 得得y=12-x, 代入線性約束條件代入線性約束條件整理得整理得 3x 4.5即即10 x+10y=120, y=9故故x=3x=4y=8或或即當即當x=3，y=9，或當或當x=4，y=8時時zmin=120懷化鐵路第一中學 某公司承攬了一項業(yè)務某公司承攬了一項業(yè)務, 需做文字標牌需做文字標牌

8、2個個,繪畫繪畫標牌標牌3個個.現(xiàn)有兩種規(guī)格原料現(xiàn)有兩種規(guī)格原料,甲種規(guī)格每張甲種規(guī)格每張3m2,可做文可做文字標牌字標牌1個個,繪畫標牌繪畫標牌2個個;乙種規(guī)格每張乙種規(guī)格每張2m2,可做文字可做文字標牌標牌2個個,繪畫標牌繪畫標牌1個個,求兩種規(guī)格的原料各用多少張求兩種規(guī)格的原料各用多少張,才能使總的用料面積最小才能使總的用料面積最小?分析分析:列列標牌需求量標牌需求量乙規(guī)格乙規(guī)格甲規(guī)格甲規(guī)格面積面積 (m2 )繪畫標牌繪畫標牌文字標牌文字標牌標牌類型規(guī)格類型12321223三、練習反饋三、練習反饋 懷化鐵路第一中學約束條件為約束條件為:22yx32yx0 x0y解解:設用甲種規(guī)格原料設用

9、甲種規(guī)格原料x張張,乙種規(guī)格原料乙種規(guī)格原料y張張,所用總所用總面積為面積為 z m2.則目標函數(shù)為則目標函數(shù)為z=3x+2y,標牌需求量標牌需求量乙規(guī)格乙規(guī)格甲規(guī)格甲規(guī)格面積面積 (m2 )繪畫標牌繪畫標牌文字標牌文字標牌標牌類型標牌類型規(guī)格類型規(guī)格類型12321223懷化鐵路第一中學123456x1234y0作出可行域如圖作出可行域如圖:22 yx32 yx作直線作直線l0:3x+2y=0,平移平移l 00:320lxy用甲、乙兩種原料各為用甲、乙兩種原料各為1張時，可使總用料面積最小為張時，可使總用料面積最小為5m2.答：答：B(1,1)31,34(A22yx32yx0 x0y到經(jīng)過可行域內(nèi)點到經(jīng)過可行域內(nèi)點 時時, z有最小值，有最小值，可得經(jīng)過可行域內(nèi)整點可得經(jīng)過可行域內(nèi)整點B(1,1)時時, zmin=5(m2)z=3x+2y,),(3134A此時此時z=3x+2y,314調(diào)整調(diào)整z= 5，懷化鐵路第一中學其步驟是其步驟是尋找尋找“整點整點”最優(yōu)解的方法：最優(yōu)解的方法：四、本課小結(jié)四、本課小結(jié) 打網(wǎng)格，打網(wǎng)格，平移找解法平移找解法:優(yōu)值調(diào)整法優(yōu)值