簡單線性規(guī)劃問題2課件

簡單線性規(guī)劃（2）【教學(xué)目標(biāo)】1．進(jìn)一步理解二元一次不等式表示平面區(qū)域2.進(jìn)一步理解線性規(guī)劃的意義以及約束條件、目標(biāo)函數(shù)、可行解、可行域、最優(yōu)解等基本概念；3.進(jìn)一步理解線性規(guī)劃問題的圖解法，并能應(yīng)用它解決一些簡單的實(shí)際問題；4.會(huì)求線性規(guī)劃的整點(diǎn)最優(yōu)解?！窘虒W(xué)重點(diǎn)】用圖解法解決簡單的線性規(guī)劃問題【教學(xué)難點(diǎn)】準(zhǔn)確求得線性規(guī)劃問題的最優(yōu)解例1某工廠用A、B兩種配件生產(chǎn)甲、乙兩種產(chǎn)品，每生產(chǎn)一件甲產(chǎn)品使用4個(gè)A配件耗時(shí)1h，每生產(chǎn)一件乙產(chǎn)品使用4個(gè)B配件耗時(shí)2h，該廠每天最多可從配件廠獲得16個(gè)A配件和12個(gè)B配件，按每天工作8h計(jì)算，該廠所有可能的日生產(chǎn)安排是什么？按甲、乙兩種產(chǎn)品分別生產(chǎn)x、y件，由已知條件可得二元一次不等式組例2

要將兩種大小不同規(guī)格的鋼板截成A、B、C三種規(guī)格，每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如下表所示

：解：設(shè)需截第一種鋼板x張，第一種鋼板y張，則

規(guī)格類型鋼板類型第一種鋼板第二種鋼板A規(guī)格B規(guī)格C規(guī)格2121312x+y≥15,{x+2y≥18,x+3y≥27,x≥0y≥0

作出可行域（如圖）目標(biāo)函數(shù)為z=x+y今需要A,B,C三種規(guī)格的成品分別為15，18，27塊，問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所用鋼板張數(shù)最少。X張y張x0y2x+y=15x+3y=27x+2y=18x+y=02x+y≥15,{x+2y≥18,x+3y≥27,x≥0,x∈Ny≥0y∈N直線x+y=12經(jīng)過的整點(diǎn)是B(3,9)和C(4,8)，它們是最優(yōu)解.

作出一組平行直線z=x+y，目標(biāo)函數(shù)z=

x+yB(3,9)C(4,8)A(18/5,39/5)當(dāng)直線經(jīng)過點(diǎn)A時(shí)z=x+y=11.4,x+y=12解得交點(diǎn)B,C的坐標(biāo)B(3,9)和C(4,8)調(diào)整優(yōu)值法246181282724681015但它不是最優(yōu)整數(shù)解.作直線x+y=12答（略）x0y2x+y=15x+3y=27x+2y=18x+y=02x+y≥15,{x+2y≥18,x+3y≥27,x≥0,x∈N*y≥0y∈N*經(jīng)過可行域內(nèi)的整點(diǎn)B(3,9)和C(4,8)時(shí)，t=x+y=12是最優(yōu)解.答:(略)作出一組平行直線t=x+y，目標(biāo)函數(shù)t

=

x+yB(3,9)C(4,8)A(18/5,39/5)打網(wǎng)格線法在可行域內(nèi)打出網(wǎng)格線，當(dāng)直線經(jīng)過點(diǎn)A時(shí)t=x+y=11.4,但它不是最優(yōu)整數(shù)解，將直線x+y=11.4繼續(xù)向上平移，1212182715978練習(xí)某工廠家具車間造型兩類桌子，每張桌子需木工和漆工兩道工序完成．已知木工做一張型桌子分別需要1小時(shí)和2小時(shí)，漆工油漆一張型桌子分別需要3小時(shí)和1小時(shí)；又知木工、漆工每天工作分別不得超過8小時(shí)和9小時(shí)，而兩類型桌子分別獲利潤2千元和3千元，試問工廠每天應(yīng)生產(chǎn)兩類型桌子各多少張，才能獲利潤最大？目標(biāo)函數(shù)為

.獲利潤為千元，則設(shè)每天生產(chǎn)型桌子張，型桌子張，每天所解：答：每天應(yīng)生產(chǎn)型桌子2張，型桌子3張才能解方程組

得

.獲最大利潤．

以實(shí)際問題為背景的線性規(guī)劃問題其求解的格式與步驟:(1)尋找線性約束條件,線性目標(biāo)函