線性規(guī)劃應用題 蘇教版

本文格式為Word版，下載可任意編輯——線性規(guī)劃應用題蘇教版

例1、某木器廠生產圓桌和衣柜兩種產品，現有兩種木料，第一種有72m3，其次種有56m3，假設生產每種產品都需要用兩種木料，生產一只圓桌和一個衣柜分別所需木料如下表所示.每生產一只圓桌可獲利6元,生產一個衣柜可獲利10元.木器廠在現有木料條件下,圓桌和衣柜各生產多少,才使獲得利潤最多?

產品圓桌衣柜木料(單位m3)第一種0.180.09第二種0.080.28?0.18x?0.09y?72?0.08x?0.28y?56?解：設生產圓桌x只,生產衣柜y個,利潤總額為z元,那么?而z=6x+10y.

x?0???y?0

如上圖所示,作出以上不等式組所表示的平面區(qū)域,即可行域.

作直線l:6x+10y=0,即l:3x+5y=0,把直線l向右上方平移至l1的位置時,直線經過可行域上點M,且與原點距離最大,此時z=6x+10y取最大值解方程組??0.18x?0.09y?72,得M點坐標(350,100).答:應生產圓桌350只,生產衣柜100個,能使利潤總額達到最大.

0.08x?0.28y?56?1.5指出:資源數量一定,如何安排使用它們,使得效益最好,這是線性規(guī)劃中常見的問題之一

例2、某養(yǎng)雞場有1萬只雞,用動物飼料和谷物飼料混合喂養(yǎng).每天每只雞平均吃混合飼料0.5kg,其中動物飼料不能少于谷物飼料的動物飼料每千克0.9元,谷物飼料每千克0.28元,飼料公司每周僅保證供應谷物飼料50000kg,問飼料怎樣混合,才使成本最低.

解:設每周需用谷物飼料xkg,動物飼料ykg,每周總的飼料費用為z元,那么

?x?y?35000?1??y?x,而z=0.28x+0.9y5??0?x?50000???y?0y?1x5如下圖所示,作出以上不等式組所表示的平面區(qū)域,即可行域.

作一組平行直線0.28x+0.9y=t,其中經過可行域內的點且和原點最近的直線,經過直線x+y=35000和直線

的交點

A(87500175008750017500,),即x?,y?3333時,飼料費用最低.

所以,谷物飼料和動物飼料應按5:1的比例混合,此時成本最低.

指出:要完成一項確定的任務,如何統(tǒng)籌安排,盡量做到用最少的資源去完成它,這是線性規(guī)劃中最常見的問題之一.

1

(例3圖)(例4圖)

例3、下表給出甲、乙、丙三種食物的維生素A、B的含量及成本:

維生素A(單位/千克)維生素B(單位/千克)成本(元/千克)甲4008007乙6002006丙4004005營養(yǎng)師想購這三種食物共10千克,使之所含維生素A不少于4400單位,維生素B不少于4800單位,問三種食物各購多少時,成本最低?最低成本是多少?

解:設所購甲、乙兩種食物分別為x千克、y千克,則丙種食物為(10?x?y)千克.x、y應滿足線性條件為

?400x?600y?400(10?x?y)?4400?y?2,化簡得???800x?200y?400(10?x?y)?4800?2x?y?4作出可行域如上圖中陰影部分

目標函數為z=7x+6y+5(10?x?y)=2x+y+50,令m=2x+y,作直線l:2x+y=0,則直線2x+y=m經過可行域中A(3,2)時,m最小,即mmin=2?3+2=8，∴zmin=mmin+50=58答:甲、乙、丙三種食物各購3千克、2千克、5千克時成本最低,最低成本為58元.

指出:此題可以不用圖解法來解,譬如,由??y?2得

?2x?y?4z=2x+y+50=(2x?y)+2y+50?4+2?2+50=58,當且僅當y=2,x=3時取等號總結：(1)設出決策變量,找出線性規(guī)劃的約束條件和線性目標函數;

(2)利用圖象,在線性約束條件下找出決策變量,使線性目標函數達到最大(或最小).

?a11x1?a12x2???a1mxm?b1?ax?ax???ax?b?2112222mm22.線性規(guī)劃問題的一般數學模型是:已知??????an1x1?an2x2???anmxm?bn(j=1,2,?,m)是常量.

(這n個式子中的“?〞也可以是“?〞或“=〞號)

其中aij(i=1,2,?,n,j=1,2,?,m),bi(i=1,2,?,n)都是常量,xj(j=1,2,?,m)是非負變量,求z=c1x1+c2x2+?+cmxm的最大值或最小值,這里cj(3)線性規(guī)劃的理論和方法主要在以下兩類問題中得到應用:一是在人力、物力資金等資源一定的條件下,如何使用它們來完成最多的任務；二是給一項任務,如何合理安排和規(guī)劃,能以最少的人力、物力、資金等資源來完成該項任務.

線性規(guī)劃中整點最優(yōu)解的求解策略

在工程設計、經營管理等活動中，經常會碰見最優(yōu)化決策的實際問題，而解決此類問題一般以線性規(guī)劃為其重要的理論基礎。然而在實際問題中，最優(yōu)解(x,y)尋常要滿足x,y∈N，這種最優(yōu)解稱為整點最優(yōu)解，下面通過具體例子談談如何求整點最優(yōu)解.

1．平移找解法

作出可行域后，先打網格，描出整點，然后平移直線l，直線l最先經過或最終經過的那個整點便是整點最優(yōu)解.

例1、某木器廠生產圓桌和衣柜兩種產品，現有兩種木料，第一種有72m3，其次種有56m3，假設生產每種產品都需要用兩種木料，生產一只圓桌和一個衣柜分別所需木料如下表所示.每生產一只圓桌可獲利6元,生產一個衣柜可獲利10元.木器廠在現有木料條件下,圓桌和衣柜各生產多少,才使獲得利潤最多?產品2

木料(單位m3)第一種圓桌衣柜0.180.09第二種0.080.28?0.18x?0.09y?72?0.08x?0.28y?56?解：設生產圓桌x只,生產衣柜y個,利潤總額為z元,那么?而z=6x+10y.如下圖,作出以上不等式組所

?x?0??y?0表示的平面區(qū)域,即可行域.

作直線l:6x+10y=0,即l:3x+5y=0,把直線l向右上方平移至l1的位置時,直線經過可行域上點M,且與原點距離最大,此時z=6x+10y取最大值。解方程組??0.18x?0.09y?72,得M點坐標(350,100).答：應生產圓桌350只,生產衣柜100個,能使利潤總額達到最

?0.08x?0.28y?561配套，怎樣截最合理？3大.點評：此題的最優(yōu)點恰為直線0.18x+0.09y=72和0.08x+0.28y=56的交點M。

例2有一批鋼管，長度都是4000mm，要截成500mm和600mm兩種毛坯，且這兩種毛坯按數量比不小于解：設截500mm的鋼管x根，600mm的y根，總數

為z根。根據題意，得為

，

作出如下圖的可行域內的整點，

，目標函數

作一組平行直線x+y=t，經過可行域內的點且和原點距離最遠的直線為過B（8，0）的直線，這時x+y=8.由于x,y為正整數，知（8，0）不是最優(yōu)解。顯然要往下平移該直線，在可行域內找整點，使x+y=7，可知點（2，5），（3，4），（4，3），（5，2），（6，1）均為最優(yōu)解．答：略．

點評：此題與上題的不同之處在于，直線x+y=t經過可行域內且和原點距離最遠的點B（8，0）并不符合題意，此時必需往下平移該直線，在可行域內找整點，譬如使x+y=7，從而求得最優(yōu)解。

從這兩例也可看到，平移找解法一般適用于其可行域是有限區(qū)域且整點個數又較少，但作圖要求較高。二、整點調整法

先按“平移找解法〞求出非整點最優(yōu)解及最優(yōu)值，再借助不定方程的知識調整最優(yōu)值，最終篩選出整點最優(yōu)解．

?2x?y?3?0?例3．已知x,y滿足不等式組?2x?3y?6?0，求使x?y取最大值的整數x,y．

?3x?5y?15?0?解：不等式組的解集為三直線l1：2x?y

l1

A

l3

C

O

xl2

y?3?0，l2：2x?3y?6?0，l3：

B

3x?5y?15?0所圍成的三角形內部（不含邊界），設l1與l2，l1與l3，l2與l3交點分別為

A,B,C，則A,B,C坐標分別為A(作一組平行線l：x?3

1537512,)，B(0,?3)，C(,?)，841919y?t平行于l0：x?y?0，當l往l0右上方移動時，t隨之增大，

∴當l過C點時x?當xy最大為

6375，但不是整數解，又由0?x?知x可取1,2,3，

1919?1時，代入原不等式組得y??2，∴x?y??1；當x?2時，得y?0或?1，∴x?y?2或1；

當x?x?2?x?3?3時，y??1，∴x?y?2，故x?y的最大整數解為?或?．

?y?0?y??13.逐一檢驗法

由于作圖有時有誤差，有時僅有圖象不一定就能確鑿而迅速地找到最優(yōu)解，此時可將若干個可能解逐一校驗即可見分曉．例4一批長4000mm的條形鋼材，需要將其截成長分別為518mm與698mm的甲、乙兩種毛坯，求鋼材的最大利用率．

解：設甲種毛坯截x根，乙種毛坯截y根，鋼材的利用率為P，則

②，線性約束條件①表示的可行域是圖中陰

影部分的整點．②表示與直線518x+698y=4000平行的直線系。所以使P取得最大值的最優(yōu)解是陰影內最靠近直線518x+698y=4000的整點坐標．如圖看到(0，5)，(1，4)，(2，4)，(3，3)，(4，2)，(5，2)，(6，1)，(7，0)都有可能是最優(yōu)解，將它們的坐標逐一代入②進行校驗，可知當x=5,y=2時，

．

①，目標函數為

答：當甲種毛坯截5根，乙種毛坯截2根，鋼材的利用率最大，為99.65%．解線性規(guī)劃問題的關鍵步驟是在圖（可行域）上完成的，所以作圖時應盡可能確切，圖上操作盡可能規(guī)范，但考慮到作圖時必然會有誤差，

假使圖上的最優(yōu)點并不十明顯顯易辨時，不妨將幾個有可能是最優(yōu)點的坐標都求出來，然后逐一進行校驗，以確定整點最優(yōu)解.

線性規(guī)劃的實際應用習題精選

1．某家俱公司生產甲、乙兩種型號的組合柜，每種柜的制造白坯時間、油漆時間及有關數據如下：

問該公司如何安排這兩種產品的生產，才能獲得最大的利潤．最大利潤是多少？

2．要將兩種大小不同的鋼板截成A、B、C三種規(guī)格，每張鋼板可同時截得三種規(guī)格小鋼板的塊數如下：

每張鋼板的面積，第一種為1m，其次種為2m，今需要A、B、C三種規(guī)格的成品各12，15，17塊，問各截這兩種鋼板多少張，可得所需三種規(guī)格成品，且使所用鋼板面積最?。?

2

2

3．某人承攬一項業(yè)務，需做文字標牌2個，繪畫標牌3個，現有兩種規(guī)格的原料，甲種規(guī)格每張3m，可做文字標牌1個，繪畫標牌2個，乙種規(guī)格每張2m，可做文字標牌2個，繪畫標牌1個，求兩種規(guī)格的原料各用多少張，才能使總的用料面積最?。?．某蔬菜收購點租用車輛，將100噸新鮮黃瓜運往某市銷售，可供租用的大卡車和農用車分別為10輛和20輛，若每輛卡車載重8噸，運費960元，每輛農用車載重2.5噸，運費360元，問兩種車各租多少輛時，可全部運完黃瓜，且動費最低．并求出最低運費．5．某木器廠生產圓桌和衣柜兩種產品，現有兩種木料，第一種有72立方米，其次種有56立方米，假設生產每種產品都需要兩種木料．生產一只圓桌需用第一種木料0.18立方米，其次種木料0.08立方米，可獲利潤60元，生產一個衣柜需用第一種木料0.09立方米，其次種0.28立方米，可獲利潤100元，木器廠在現有木料狀況下，圓桌和衣柜應各生產多少，才能使所獲利潤最多．2