簡(jiǎn)單線性規(guī)劃(整點(diǎn)解問題)

1、懷化鐵路第一中學(xué)7.47.4簡(jiǎn)單的線型規(guī)劃簡(jiǎn)單的線型規(guī)劃(3)(3)整點(diǎn)解問題整點(diǎn)解問題懷化鐵路第一中學(xué)一、朝花夕拾一、朝花夕拾 圖解法解簡(jiǎn)單線性規(guī)劃問題的步驟圖解法解簡(jiǎn)單線性規(guī)劃問題的步驟(1)畫可行域；畫可行域；(2)比較斜率，畫目標(biāo)直線比較斜率，畫目標(biāo)直線l；(3)平移平移l，找最優(yōu)解；，找最優(yōu)解；(4) 求交算出最優(yōu)解，并求最值求交算出最優(yōu)解，并求最值解簡(jiǎn)單線性規(guī)劃應(yīng)用題的步驟解簡(jiǎn)單線性規(guī)劃應(yīng)用題的步驟(列列)設(shè)設(shè)寫寫作作移移定定答答懷化鐵路第一中學(xué)已知已知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顯然，當(dāng)顯然，當(dāng)l過點(diǎn)過點(diǎn)A時(shí)，時(shí)，z最小最小zx+y=z由由2x+y = 15x+3y =2734(3, 7)55A得得故當(dāng)故當(dāng)x=335，y=475時(shí)，時(shí)，zmin=2305懷化鐵路第一中學(xué) 要將兩種大小不同的鋼板截成要將兩種大小不同的鋼板截成A A、B B、C C三種規(guī)格，每三種規(guī)格，每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如下表所示：張鋼板可同時(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塊。塊。問各截這兩種鋼板多少?gòu)埧傻盟枞N規(guī)格成品，且使所問各截這兩種鋼板多少?gòu)埧傻盟枞N規(guī)格成品，且使所用鋼板張數(shù)最少。用鋼板張數(shù)最少。問題問題二、探索研究二、探索研究懷化鐵路第一中學(xué)（1） (列列)（2）設(shè)：設(shè)：所需截第一種鋼板所需截第一種鋼板x張，第二種鋼板張，第二種鋼板y張，兩種鋼張，兩種鋼板共板共z張張.（3）寫：寫：線性約束條件線性約束條件目標(biāo)函數(shù)：目標(biāo)函數(shù)：yxz規(guī)格類型規(guī)格類型鋼板類型鋼板類型第一種鋼板第一種鋼板第二種鋼板第

4、二種鋼板A 規(guī)格規(guī)格B 規(guī)格規(guī)格C 規(guī)格規(guī)格211123各規(guī)格成品數(shù)各規(guī)格成品數(shù)151827152yx 182yx273yx0 x0yxxxxyyyy幾何畫板演示幾何畫板演示懷化鐵路第一中學(xué)（6）定定:平移找解法平移找解法:打網(wǎng)格打網(wǎng)格,描整點(diǎn)描整點(diǎn),平移目標(biāo)函數(shù)線平移目標(biāo)函數(shù)線, 確定首確定首先經(jīng)過的整點(diǎn)先經(jīng)過的整點(diǎn). 要求作圖準(zhǔn)確，易要求作圖準(zhǔn)確，易出現(xiàn)模糊點(diǎn)，可操作出現(xiàn)模糊點(diǎn)，可操作性不強(qiáng)！性不強(qiáng)！懷化鐵路第一中學(xué)優(yōu)值調(diào)整法優(yōu)值調(diào)整法: 當(dāng)當(dāng)直線直線x+y=z 移至移至A(3.6,7.8)時(shí)時(shí), 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ù)解，應(yīng)繼續(xù)調(diào)整，直到找到為止仍無整數(shù)解，應(yīng)繼續(xù)調(diào)整，直到找到為止. 懷化鐵路第一中學(xué)y=8第第一一變：變：已知已知2x+y 15x+2y 18x+3y 27xNyN求求z=2x+3y的最小值的最小值解：解：如圖，作出可行域如圖，作出可行域并作出直線并作出直線l：2

6、x+3y=z 顯然，當(dāng)顯然，當(dāng)l移至過移至過A(3.6,7.8)時(shí)時(shí), 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或或(舍舍)即當(dāng)即當(dāng)x=4，y=8時(shí)時(shí)zmin=32懷化鐵路第一中學(xué)第第二二變：變：已知已知2x+y 15x+2y 1

7、8x+3y 27xNyN求求z=10 x+10y的最小值的最小值解：解：如圖，作出可行域如圖，作出可行域并作出直線并作出直線l：10 x+10y=z 顯然，當(dāng)顯然，當(dāng)l移至過移至過A(3.6,7.8)時(shí)時(shí), 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或或即當(dāng)即當(dāng)x=3，y=9，或當(dāng)或當(dāng)x=4，y=8時(shí)時(shí)zmin=120懷化鐵路第一中學(xué) 某公司承攬了一項(xiàng)業(yè)務(wù)某公司承攬了一項(xiàng)業(yè)務(wù), 需做文字標(biāo)牌需做文字標(biāo)牌

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

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