【正文】 請安排服務(wù)員的工作時間，使服務(wù)員總數(shù)最少 . 82 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 三、項(xiàng)目投資選擇 有 600萬元投資 5個項(xiàng)目，收益如表，求利潤最大的方案？ 項(xiàng)目 投資額 項(xiàng)目收益 約束條件 I 2 10 1 60 II 3 00 2 10 I II 1 50 60 IV 1 30 80 V 2 60 1 80 項(xiàng)目 I 、 II 、 I II 中選 1 項(xiàng) 項(xiàng)目 I II 、 IV 之中選 1 項(xiàng) 選項(xiàng)目 V 必先選項(xiàng)目 I ???? 個項(xiàng)目投資選中第不 個項(xiàng)目投資選中第 jjx j 01 ??????????????????????????10,116002601301503002101808060210160m a x5432115433215432154321或xxxxxxxxxxxxxxxxxxxxxxZ83 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 四、互斥約束問題 ? 例如關(guān)于煤資源的限制，其約束條件為： ? 企業(yè)也可以考慮采用天然氣進(jìn)行加熱處理： ? 這兩個條件是互相排斥的。 解：設(shè) x1為甲產(chǎn)品的臺數(shù)， x2為乙產(chǎn)品的臺數(shù)。于是有 2y1+0y2+3y3≥ 3 ? 同理，對乙產(chǎn)品而言，則有 0y1+2y2+4y3≥ 5 ? 設(shè)備臺時出讓的收益（希望出讓的收益最少值） min? 16y1+10y2+32y3 ? 顯然還有 y1， y2， y3≥0 65 OR:SM 第一節(jié) 對偶規(guī)劃的數(shù)學(xué)模型 一、對偶問題的提出 例 1的對偶問題的數(shù)學(xué)模型 ? 對偶問題的最優(yōu)解： y1=0， y2=1/2， y3=1， W* =37 ? 兩個問題的目標(biāo)函數(shù)值相等并非偶然 ? 前者稱為線性規(guī)劃原問題，則后者為對偶問題，反之亦然。 53 OR:SM 第一節(jié) 目標(biāo)函數(shù)的描述技巧 三、計(jì)時工資 ? 目標(biāo)函數(shù)為 1 2 3m a x 108 138 105 110 00Z x x x? ? ? ?? 經(jīng) Lindo軟件求解，得到最優(yōu)解為 Z=5800,x1=40,x2=60,x3=40。 ???????????100010001B? 基變量是 x3, x4, x5 ? 非基變量是 x1, x2 ? 令非基變量 x1=x2=0，得到一個基解 x3=16， x4=10， x5=32 44 OR:SM 二、線性規(guī)劃之解的概念 第二節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃解之關(guān)系 可行解 ： 滿足約束條件 AX=b, X≥0 的解。 maxZ= 3x1 +5 x2 2 x1 ≤16 2x2 ≤10 3x1 +4 x2 ≤32 x1 ≥0, x2 ≥0 2x1 =16 2x2 =10 3x1 +4 x2 =32 0 A B C D 36 OR:SM 2x1 =16 2x2 =10 3x1 +4 x2 =32 0 A B C D 四、線性規(guī)劃的圖解方法 第一節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃的最優(yōu)解 目標(biāo)函數(shù) Z= 3x1 +5 x2 代表以 Z 為參數(shù)的一族平行線。 據(jù)市場分析，單位甲乙產(chǎn)品的銷售價(jià)格分別為 73和 75元，試確定獲利最大的產(chǎn)品生產(chǎn)計(jì)劃。管理運(yùn)籌學(xué) 管理科學(xué)方法 謝家平 博士 教授 博士生導(dǎo)師 研究領(lǐng)域： 管理科學(xué)、運(yùn)營管理、供應(yīng)鏈管理 講授課程： 管理運(yùn)籌學(xué) 管理科學(xué)方法、管理系統(tǒng)工程、 運(yùn)營管理、 供應(yīng)鏈管理、 ERP、國際物流、 企業(yè)物流管理、管理決策模型與方法 單 位： 上海財(cái)經(jīng)大學(xué)工商學(xué)院 物流管理系 Email： 1 OR:SM 教材與參考書籍 ? 教材： ? 謝家平編著 .管理運(yùn)籌學(xué)：管理科學(xué)方法， 中國人民大學(xué)出版社， 2023 ? 參考書： ? David et al. 數(shù)據(jù)、模型與決策，機(jī)械工業(yè)出版社， 2023 ? 費(fèi)雷德里克 . 數(shù)據(jù)、模型與決策，中國財(cái)政經(jīng)濟(jì)出版社， 2023 ? James et al. 數(shù)據(jù)、模型與決策，中國人民大學(xué)出版社， 2023 2 OR:SM 32課時講授提綱 ? 緒 論 ? 第一章 線性規(guī)劃 ? 第二章 線性規(guī)劃討論 ? 第三章 對偶規(guī)劃 靜態(tài)規(guī)劃 ? 第四章 整數(shù)規(guī)劃 ? 第五章 目標(biāo)規(guī)劃 ? 第六章 動態(tài)規(guī)劃 動態(tài)優(yōu)化 ? 第七章 網(wǎng)絡(luò)分析 ? 第八章 網(wǎng)絡(luò)計(jì)劃 ? 第九章 決策分析 ? 第十章 方案排序 ? 第十一章 庫存控制 ? 第十二章 排隊(duì)理論 離散優(yōu)化 隨機(jī)優(yōu)化 淡化數(shù)學(xué)算法 LINDO求解 3 OR:SM 考核方式 ? 結(jié)課考試： ? 筆試（開卷 or 閉卷？） 每章一題 80% ? 案例研究： ? 選擇合適方法結(jié)合企業(yè)實(shí)際進(jìn)行應(yīng)用 20% 4 OR:SM 管理運(yùn)籌學(xué)的稱謂 ? 管理運(yùn)籌學(xué)是一門研究如何最優(yōu)安排的學(xué)科。 產(chǎn)品 設(shè)備 工時消耗 甲 乙 工時成本 元 /h 生產(chǎn)能力 h A B C 2 0 0 2 3 4 20 15 10 16 10 32 28 OR:SM 第一節(jié) 線性規(guī)劃的一般模型 (1)決策變量 ： 設(shè) x1為甲產(chǎn)品的產(chǎn)量 ， x2為乙產(chǎn)品的產(chǎn)量 。 Z=30 Z=37 Z=15 37 OR:SM 四、線性規(guī)劃的圖解方法 第一節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃解的特性 a b c d ? 由線性不等式組成的可行域是凸多邊形 (凸多邊形是凸集 ) ?凸集定義：集合內(nèi)部任意兩點(diǎn)連線上的點(diǎn)都屬于這個集合 ? 可行域有有限個頂點(diǎn)。 可行基 ： 可行解對應(yīng)的基矩陣。 1 2 30 30 15 240 0x x x? ? ?1 2 310 20 0 240 0x x x? ? ?1 2 331 21 21 480 0x? ?313 24 480 0x x x? ?設(shè)備 E： 設(shè)備 F： 設(shè)備 G： 設(shè)備 H： 1 40x ?2 803 40x ?產(chǎn)品甲： 產(chǎn)品乙： 產(chǎn)品丙： ? 市場需求約束 ? 設(shè)備能力約束 54 OR:SM 第二節(jié) 線性規(guī)劃的適用層次 計(jì)劃鏈的層次 粗能力計(jì)劃 定單 可行 不可行 CRP 主生產(chǎn)計(jì)劃 MPS 物料需求計(jì)劃 MRP 能力需求計(jì)劃 車間作業(yè)計(jì)劃 銷售計(jì)劃 可行否 作業(yè)統(tǒng)計(jì)與控制 物料清單 庫存管理 外購計(jì)劃 供應(yīng)商 成品、在制品信息 生產(chǎn)計(jì)劃大綱 預(yù)測 當(dāng)前條件 經(jīng)營計(jì)劃 ? 產(chǎn)值計(jì)劃 或 利潤計(jì)劃 ? 絕對數(shù)量 或 增長幅度 ? 期限 :年度 單位 :萬元 ? 大類產(chǎn)品銷售收入 或 臺套 ? 產(chǎn)品品種 和 數(shù)量 如何確定 ? 期限 :年度 單位 :萬臺 ? 具體產(chǎn)品在具體 時段的出產(chǎn)計(jì)劃 ? 合同訂單和預(yù)測 轉(zhuǎn)換為生產(chǎn)任務(wù) ? 將產(chǎn)品出產(chǎn)計(jì)劃轉(zhuǎn)換成物料需求表 ? 大類產(chǎn)品年度生產(chǎn)計(jì)劃 ? 確定產(chǎn)品的品種 和 數(shù)量 ? 期限 :年度 單位 :萬臺 55 OR:SM 第三節(jié) 線性規(guī)劃的典型案例 ? 配送中心選擇 例： 某企業(yè)存在兩個供貨源（產(chǎn)地），已知原有供貨源每月的供貨能力是 5萬臺產(chǎn)品，新增供貨源的生產(chǎn)能力可以滿足產(chǎn)品的需求，且兩個貨源的價(jià)格相同。 ? 對偶問題的最優(yōu)解對應(yīng)于原問題最優(yōu)單純型法表中，初始基變量的檢驗(yàn)數(shù)的負(fù)值。 maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1, x2 ≥0 x1, x2 取整數(shù) 74 OR:SM 第一節(jié) 整數(shù)規(guī)劃問題 二、 01規(guī)劃 登山隊(duì)員可攜帶最大重量為 25公斤。引入 0—1變量 y，令 ? 互斥問題可由下述的條件來代替，其中 M是充分大的數(shù)。 ???????????????????????????????????????????皆為整數(shù)54321543215545435432432132121154321,0,35813119810..m i nxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxZ按規(guī)定，服務(wù)員連續(xù)工作 8小時(4個時段 )為一班。 ? 全部決策變量的取值都為整數(shù)，則稱為全整數(shù)規(guī)劃 (All IP) ? 僅要求部分決策變量的取值為整數(shù)，則稱為混合整數(shù)規(guī)劃(Mixed IP) ? 要求決策變量只取 0或 1值，則稱 01規(guī)劃 (01 Programming) 73 OR:SM 第一節(jié) 整數(shù)規(guī)劃問題 一、純整數(shù)規(guī)劃 產(chǎn)品 資源 甲 乙 現(xiàn)有量 A 2 1 9 B 5 7 35 單臺利潤 6 5 例：某企業(yè)利用材料和設(shè)備生產(chǎn)甲乙產(chǎn)品，其工藝消耗系數(shù)和單臺產(chǎn)品的獲利能力如下表所示： 問如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使利潤為最大。 64 OR:SM 第一節(jié) 對偶規(guī)劃的數(shù)學(xué)模型 一、對偶問題的提出 出讓定價(jià) ? 假設(shè)出讓 A、 B、 C設(shè)備所得利潤分別為 y y y3 ? 原本用于生產(chǎn)甲產(chǎn)品的設(shè)備臺時，如若出讓，不應(yīng)低于自行生產(chǎn)帶來的利潤，否則寧愿自己生產(chǎn)。 ? 總收入 =173x1+233x2+170x3， 原料成本 =65x1+95x2+65x3，營運(yùn)費(fèi)用 =11000， 則目標(biāo)函數(shù)為 maxZ= 108x1+138x2+105x311000 ? 崗位工資制薪酬體系下，工作時間也不會完全受每天 8小時工作時間約束，但有產(chǎn)品市場需求約束，如下： 產(chǎn)品甲： 產(chǎn)品乙： 產(chǎn)品丙： 非負(fù)性約束 1 40?2 80x3 40?1 2 3, , 0x x x ?? 經(jīng) Lindo軟件求解，得到最優(yōu)解為 Z=8560,x1=40,x2=80,x3=40。 基變量： ? 與基向量 Pj 相對應(yīng)的 m個變量 xj稱為基變量 ? 其余的 n m個變量為非基變量 線性規(guī)劃解之關(guān)系 基解： 令所有非基變量等于零，得出基變量的唯一解 。 1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 212m a x( m in) Z( , )( , ) . ( , ), , 0nnnnnnm m m n n mnc x c x c xa x a x a x ba x a x a x ba x a x a x bx x x? ? ? ?? ? ? ? ? ???? ? ? ? ? ?????? ? ? ? ? ?????35 OR:SM 四、線性規(guī)劃的圖解方法 第一節(jié) 線性規(guī)劃的一般模型 線性規(guī)劃的可行域 可行域： 滿足所有約束條件的解的集合， 即所有約束條件共同圍城的區(qū)域。應(yīng)如何制定生產(chǎn)計(jì)劃，使總利潤為最大。 ? Operations Research ? 日本譯作 “ 運(yùn)用學(xué) ” ? 香港 、 臺灣譯為 “ 作業(yè)研