簡單的線性規(guī)劃第一課時.ppt

簡單線性規(guī)劃 第一節(jié)復習回顧 平面區(qū)域的表示 例1 畫出不等式2x y 6 0表示的平面區(qū)域 3 6 2x y 6 0 2x y 6 0 練習1 畫出下列不等式表示的平面區(qū)域 1 x y 2 x y 1 2 例2 畫出不等式組表示的平面區(qū)域 x y 0 x 3 x y 5 0 注 不等式組表示的平面區(qū)域是各不等式所表示平面區(qū)域的公共部分 5 5 解 0 0 5 0 1 0 0 4 2 3 3 2 練習2畫出下列不等式組表示的平面區(qū)域 2 二元一次不等式Ax By C 0在平面直角坐標系中表示直線Ax By C 0某一側所有點組成的平面區(qū)域 確定步驟 直線定界 特殊點定域 若C 0 則直線定界 原點定域 小結 則用不等式可表示為 解 此平面區(qū)域在x y 0的右下方 x y 0 它又在x 2y 4 0的左下方 x 2y 4 0 它還在y 2 0的上方 y 2 0 y o x 4 2 x y 0 y 2 0 x 2y 4 0 2 2 求由三直線x y 0 x 2y 4 0及y 2 0所圍成的平面區(qū)域所表示的不等式 3 在同一坐標系上作出下列直線 2x y 0 2x y 1 2x y 3 2x y 4 2x y 7 x y o 2x y 0 2x y 1 2x y 4 2x y 7 2x y 3 直線的方程 直線的傾斜角與斜率 4 判斷下列直線斜率的大小關系 5 求下列直線的交點 兩直線無交點 平行 二 簡單的線性規(guī)劃問題 畫出不等式組表示的平面區(qū)域 3x 5y 25 x 4y 3 x 1 3x 5y 25 x 4y 3 x 1 問題 有無最大 小 值 x y o 問題 2 有無最大 小 值 二 提出問題 把上面兩個問題綜合起來 設z 2x y 求滿足 時 求z的最大值和最小值 A B C A 直線l越往右平移 t隨之增大 以經過點A 5 2 的直線所對應的t值最大 經過點B 1 1 的直線所對應的t值最小 最優(yōu)解 使目標函數(shù)達到最大值或最小值的可行解 線性約束條件 約束條件中均為關于x y的一次不等式或方程 有關概念 約束條件 由 的不等式 方程 構成的不等式組 目標函數(shù) 欲求最值的關于x y的一次解析式 線性目標函數(shù) 欲求最值的解析式是關于x y的一次解析式 線性規(guī)劃 求線性目標函數(shù)在線性約束條件下的最大值或最小值 可行解 滿足線性約束條件的解 x y 可行域 所有可行解組成的集合 設z 2x y 求滿足 時 z的最大值和最小值 線性目標函數(shù) 線性約束條件 線性規(guī)劃問題 任何一個滿足不等式組的 x y 可行解 可行域 所有的 最優(yōu)解 x y o x 4y 3 x 1 C 設z 2 式中變量 滿足下列條件 求 的最大值和最小值 B 3x 5y 25 問題1 將z 2 變形 問題2 z幾何意義是 斜率為 2的直線在y軸上的截距 則直線l 2 z是一簇與l0平行的直線 故直線l可通過平移直線l0而得 當直線往右上方平移時z逐漸增大 當l過點B 1 1 時 z最小 即zmin 3當l過點A 5 2 時 最大 即zmax 2 5 2 12 析 作直線l0 2 0 例1 設z 2x y 式中變量x y滿足下列條件求 的最大值和最小值 解 作出可行域如圖 當 0時 設直線l0 2x y 0 當l0經過可行域上點A時 z最小 即 最大 當l0經過可行域上點C時 最大 即 最小 zmax 2 5 2 8zmin 2 1 4 4 2 4 5 2 1 4 4 平移l0 平移l0 2x y 0 解線性規(guī)劃問題的步驟 2 在線性目標函數(shù)所表示的一組平行線中 用平移的方法找出與可行域有公共點且縱截距最大或最小的直線 3 通過解方程組求出最優(yōu)解 4 作出答案 1 畫出線性約束條件所表示的可行域 畫 移 求 答 已知滿足 2 求的最大值和最小值 1 求的最大值和最小值 三 課堂練習 解 1 根據(jù)線性約束條件作出可行域 2 作直線 3 平移直線 4 當直線過點時 5 當直線過點時 解 1 根據(jù)線性約束條件作出可行域 2 作直線 3 平移直線 5 當直線過點時 4 當直線過點時 3x 5y 25 例2 已知x y滿足 設z ax y a 0 若 取得最大值時 對應點有無數(shù)個 求a的值 x y o x 4y 3 x 1 C B 解 當直線l y ax z與直線重合時 有無數(shù)個點 使函數(shù)值取得最大值 此時有 kl kAC kAC kl a a a 例3 滿足線性約束條件的可行域中共有多少個整數(shù)解 1 2 2 3 3 1 4 4 5 5 x y 0 解 由題意得可行域如圖 由圖知滿足約束條件的可行域中的整點為 1 1 1 2 2 1 2 2 故有四個整點可行解 幾個結論 1 線性目標函數(shù)的最大 小 值一般在可行域的頂點處取得 也可能在邊界處取得 2 求線性目標函數(shù)的最優(yōu)解 要注意分析線性目標函數(shù)所表示的幾何意義 在y軸上的截距或其相反數(shù) a b o 5 當直線3a 2b 0過點A 4 1 時 3a 2b取最大值10 當直線3a 2b 0過點B 0 1 時 3a 2b取最大值 2 四 應用 某工廠生產甲 乙兩種產品 生產1t甲種產品需要A種原料4t B種原料12t 產生的利潤為2萬元 生產1t乙種產品需要A種原料1t B種原料9t 產生的利潤為1萬元 現(xiàn)有庫存A種原料10t B種原料60t 如何安排