【正文】 供 1 2 20臺同一規(guī)格的柴油機。 生產(chǎn)能力（臺） 單位成本（萬元） 一季度 25 1 0 . 8 二季度 35 1 1 . 1 三季度 30 1 1 . 0 四季度 10 1 1 . 3 產(chǎn)地 銷地 第一季度 第二季度 第三季度 第四季度 第一季度 第二季度 第三季度 第四季度 產(chǎn)量 銷量 25 35 30 10 10 15 25 20 M M M M M M 分析： 本問題可轉(zhuǎn)化為一運輸問題 第一季度 第二季度 第三季度 第四季度 產(chǎn)量 第一季度 10 15 0 25 第二季度 5 35 第三季度 20 10 30 第四季度 10 10 銷量 10 15 25 20 最優(yōu)方案為： 。如果生產(chǎn)出來的柴油機當(dāng)季不交貨，每臺每積壓一個季度需儲存、維護等費用 。問攜帶哪些物品可使總價值最大？ 解： 模型為： 54321 36957 xxxxxZM a x ??????????. 1151946573554 54321 ????? xxxxx),51,i(10 ??? 或ix4. 消防隊問題 某城市的消防總部將全市劃分為 11個防火區(qū)，設(shè)有 4個消防救火站。 （ 2） 選擇了 S3或 S4就不能選擇 S5，反 過來也一樣 。39。 4 運輸問題 第一章 線性規(guī)劃 （ Linear Programming，簡稱 LP） 167。運 籌 學(xué) Operational Research 天津大學(xué)管理學(xué)院 郭均鵬 教師簡介： 郭均鵬：博士，副教授， 碩士生導(dǎo)師。 3 整數(shù)規(guī)劃 167。 = CX （ 2）約束條件 例如： 9 x1 +4x2≤360 9 x1 +4x2+ x3=360 松弛變量 ? ―≤‖型約束，加松弛變量； ? ―≥‖型約束，減松弛變量； 例、將如下問題化為標(biāo)準型 ??????????????????????0,52327..32321321321321321xxxxxxxxxxxxtsxxxzM i n解 ：令 第二個約束減松弛變量 x6， 得標(biāo)準型： )( 39。 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 [例 ] 人力資源分配的問題 某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下： 設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員 ? 班次 時間 所需人數(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 解：設(shè) xi 表示第 i班次時開始上班的司機和乘務(wù)人員數(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ū)設(shè)立商業(yè)網(wǎng)點，備選位置有A1~A7共 7個，如果選 Ai，估計投資為 bi元，利潤為 ci元，要求總投資不超過 B元，規(guī)定 東區(qū)： A A A3中至多選 2個 西區(qū)： A A5中至少選一個 南區(qū)： A A7中至少選一個 問如何設(shè)點使總利潤最大？ 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 ?????. 課堂練習(xí) 1: 某鉆井隊要從 S1~S10共 10個井位中確定五個鉆井探油，如果選 Si，估計鉆探費用為 ci元，并且井位選擇上要滿足下列條件： （ 1） 或選擇 S1和 S7，或選擇 S8 。他最多能帶 115kg的物品，現(xiàn)有 5件物品，分別重 5 35 4 19kg，其價值依次為 3。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如右表