[管理學]管理運籌學 第一章_線性規(guī)劃-預覽頁
【正文】 的一門 應用科學 。 3 整數(shù)規(guī)劃 167。有關數(shù)據如下表，現(xiàn)飼料可從市場上出售的 M、 N兩種飼料中選擇，試決定總花費最小的購買方案。 = CX （ 2）約束條件 例如： 9 x1 +4x2≤360 9 x1 +4x2+ x3=360 松弛變量 ? ―≤‖型約束，加松弛變量； ? ―≥‖型約束，減松弛變量； 例、將如下問題化為標準型 ??????????????????????0,52327..32321321321321321xxxxxxxxxxxxtsxxxzM i n解 ：令 第二個約束減松弛變量 x6， 得標準型： )( 39。 7x1+12x2=84 7x1+12x2=168 如：令 7 x1 +12x2=84 7 x1 +12x2=168 9x1+4x2=360 4x1+5x2=200 3x1+10x2=300 x1 x2 40 20 60 80 100 20 40 60 80 100 0 X*=（ 20， 24）， Z*=428 最優(yōu)解： x1 = 0， x2 = 1 最優(yōu)目標值 z = 6 課堂練習 圖解法求解線性規(guī)劃 ????????????????0,)3(22)2(22)1(432m i n2121212121xxxxxxxxstxxz0 1 2 3 4 1 2 3 4 x 1 x 2 O 1 2 (1) (2) (3) 2. LP 解的幾種情況 （ 1）唯一解 （ 2）多重最優(yōu)解 （ 3）無可行解 注：出現(xiàn)（ 3）、（ 4）情況時，建模有問題 （ 4）無有限最優(yōu)解 圖解法的結論： ● 線性規(guī)劃的可行域是凸集 ● 線性規(guī)劃的最優(yōu)解若存在，必在可行域的在極點獲得 ● 若在兩個極點同時獲得，則有無窮多最優(yōu)解 凸集 不是凸集 極點 167。 3 整數(shù)規(guī)劃 Integer Programming(簡稱 IP) 一、 整數(shù)規(guī)劃的一般模型 LP: max z=CX AX=b X≥0 ??????????IP: max z=CX AX=b X≥0 X為整數(shù) 整數(shù)規(guī)劃的解法：分枝定界法或割平面法 基本思想是把一個整數(shù)規(guī)劃問題化為一系列的線性規(guī)劃問題來求解 整數(shù)規(guī)劃的分類： ? 純整數(shù)規(guī)劃：所有變量都限制為整數(shù) ? 混合整數(shù)規(guī)劃：僅部分變量限制為整數(shù) ? 01整數(shù)規(guī)劃：變量的取值僅限于 0或 1 [例 ] 人力資源分配的問題 某晝夜服務的公交線路每天各時間段內所需司機和乘務人員數(shù)如下： 設司機和乘務人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務人員，既能滿足工作需要，又配備最少司機和乘務人員 ? 班次 時間 所需人數(shù) 1 6： 00 —— 10： 00 60 2 10： 00 —— 14： 00 70 3 14： 00 —— 18： 00 60 4 18： 00 —— 22： 00 50 5 22： 00 —— 2： 00 20 6 2： 00 —— 6： 00 30 解：設 xi 表示第 i班次時開始上班的司機和乘務人員數(shù) ,于是 LP模型為 : x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0 且為整數(shù) min z=x1 + x2 + x3 + x4 + x5 + x6 ?????班次 時間 所需人數(shù) 1 6 ： 00 —— 10 ： 00 60 2 10 ： 00 —— 14 ： 00 70 3 14 ： 00 —— 18 ： 00 60 4 18 ： 00 —— 22 ： 00 50 5 22 ： 00 —— 2 ： 00 20 6 2 ： 00 —— 6 ： 00 30 最優(yōu)解： X* =(60 ， 10， 50 ， 0 ， 30 ， 0）， Z*=150 二、 01整數(shù)規(guī)劃 ? 投資場所的選址問題 ? 指派問題 ? 背包問題 ? 消防隊問題 1. 投資場所的選址問題 某城市擬在東、西、南三區(qū)設立商業(yè)網點，備選位置有A1~A7共 7個，如果選 Ai，估計投資為 bi元，利潤為 ci元，要求總投資不超過 B元，規(guī)定 東區(qū)： A A A3中至多選 2個 西區(qū)： A A5中至少選一個 南區(qū)： A A7中至少選一個 問如何設點使總利潤最大？ 1， Ai被選中 0， Ai沒被選中 ?????解：令 xi= max z= ??71iiixcxi=0或 1， i=1, … ,7 ∑ bixi≤B i=1 7 x1+x2+x3≤2 x4+x5≥1 x6+x7≥1 ?????. 課堂練習 1: 某鉆井隊要從 S1~S10共 10個井位中確定五個鉆井探油，如果選 Si，估計鉆探費用為 ci元，并且井位選擇上要滿足下列條件： （ 1） 或選擇 S1和 S7，或選擇 S8 。 要求： 每人只能完成一項任務，每項任務只能由一人完成。他最多能帶 115kg的物品，現(xiàn)有 5件物品，分別重 5 35 4 19kg，其價值依次為 3。已知備選校址代號及其能覆蓋的居民小區(qū)編號如表所示，問為覆蓋所有小區(qū)至少應建多少所小學？ 備選校址代號 覆蓋的居民小區(qū)編號 ABCDEF 7 5 5 5 6 6 167。已知該廠各季度的生產能力及生產每臺柴油機的成本如右表。已知該廠各季度的生產能 力及生產每臺柴油機的成本如右表
教學課件相關推薦
鄂ICP備17016276號-1