【正文】 ? 原問(wèn)題與對(duì)偶問(wèn)題優(yōu)化方向相反 對(duì)偶規(guī)則 原問(wèn)題 對(duì)偶問(wèn)題 目標(biāo)函數(shù) max min 目標(biāo)函數(shù) 約束條件 ≤ ≥ 變量 ≥ ≤ = 無(wú)約束 變量符號(hào) ≥ ≥ 約束條件 ≤ ≤ 無(wú)約束 = 對(duì)偶規(guī)則簡(jiǎn)捷記法 ? 原問(wèn)題標(biāo)準(zhǔn)則對(duì)偶問(wèn)題標(biāo)準(zhǔn) ? 原問(wèn)題不標(biāo)準(zhǔn)則對(duì)偶問(wèn)題不標(biāo)準(zhǔn) ? 例題 2 max ω=7y1+4y22y3 minZ=3x1+2x26x3+x5 2y1+ y2 y3 ≤3 2x1+x24x3+x4+3x5 ≥7 y1 +3y3 ≤2 x1+ 2x3 x4 ≤ 4 4y1+2y2 ≤6 x1+3x2 x4+ x5 =2 y1 y2 y3 ≥ 0 x1,x2， x3 ≥0。x2=20。如何規(guī)劃，使該廠利潤(rùn)最大。該廠應(yīng)如何安排生產(chǎn)才能使獲得的利潤(rùn)最大？ 產(chǎn)品 規(guī)格要求 最小需求 (公斤 ) 最大需求 (公斤 ) 1 含 A不少于 25%， C不多于 20% 1000 2500 2 含 A不少于 50%， D不多于 25% 100 不限 3 含 A和 B各不少于 25%，不含 C 不限 不限 應(yīng)用舉例之二 標(biāo)準(zhǔn)型的特征 ? 目標(biāo)函數(shù)極大化 ? 約束條件為等式 ? 決策變量非負(fù) 應(yīng)用舉例之三 ? 例 茲有 100萬(wàn)元閑錢(qián)，投資方向有四： 第四年 第一年 第二年 第三年 A項(xiàng)目 110% B項(xiàng)目 135% C項(xiàng)目 125% D項(xiàng)目 104% 第五年 各年投資什么項(xiàng)目，使第五年末資本總額為最大？ ?目標(biāo)函數(shù)極小化轉(zhuǎn)為極大化： 應(yīng)用舉例之三 項(xiàng)目 1 2 3 4 5 5年末 A X1A X2A X3A X4A B X2B C X3C D X1D X2D X3D X4D X5D 擁有的資金 100 + + + + ++ 例 1： (排產(chǎn)問(wèn)題 )某廠生產(chǎn) Ⅰ 、 Ⅱ 、 Ⅲ ，每種產(chǎn)品要經(jīng)過(guò) A、 B兩道工序加工， A工序可以在 A A2設(shè)備上完成； B工序可以在 BB B3上完成。 凸集：集合內(nèi)任意兩點(diǎn)的連線上的點(diǎn)均屬于這個(gè)集合。 可行域：所有約束條件的交集，即各半平面的公共部分，也就是滿(mǎn)足所有約束條件的解的集合，稱(chēng)為可行域。 時(shí)間 需要的總?cè)藬?shù) 全日制 1 全日制 2 需要兼職 方案 11~12 9 1 8 X1 12~1 9 1 8 X2 1~2 9 1 1 7 X3 2~3 3 1 1 1 X4 3~4 3 1 2 X5 4~5 3 1 1 1 X6 5~6 6 1 5 X7 6~7 12 1 1 10 X8 7~8 12 1 1 10 X9 8~9 7 1 6 X10 9~10 7 1 6 X11 設(shè)不同的時(shí)間段上班的人數(shù)分別為 X1， X2，X3， X4， X5， X6， X7， X7， X9， X10， X11 Obj：MinZ=X1+X2+X3+X4+X5+X6+x7+x8+x9+x10+x11 S． T． X1≥8 X1+ X2≥8 X1 +X2+ X3≥7 X1+ X2+ X3+ X4≥1 X2+ X3+ X4+ X5≥2 X3+ X4+ X5 +X6≥1 X4+ X5+ X6+ X7≥5 X5+ X6+ X7+ X8≥10 X6+ X7+ X8+ X9≥10 X7+ X8+ X9+X10≥6 X8+ X9+X10+X11≥6 X1， X2， X3， X4， X5， X6，X7， X8， X9， X10， X11≥0 ? 由中學(xué)知識(shí)可知： Y=Ax+b是一條直線，同理：Z=70x1+120x2→x 2=70/120x1Z/120也是一條直線，以 Z為參數(shù)的等值線。一個(gè)全日制工人從下午 1點(diǎn)上班，休息 1小時(shí)，再干 4小時(shí)。據(jù)統(tǒng)計(jì)： 序號(hào) 時(shí)段 最少人數(shù) 安排人數(shù) 1 06— 08 60 X1 2 08— 10 X2 3 10— 12 70 X3 4 12— 14 X4 5 14— 16 60 X5 6 16— 18 X6 7 18— 20 50 X7 8 20— 22 X8 9 22— 24 20 X9 10 24— 02 X10 11 02— 04 X11 12 02— 06 30 x12 ? 目標(biāo)函數(shù)： min Z=x1+x2+x3+x4+x5+x6 ? 約束條件： x10+x11+x12+x1≥70 ? x11+x12+x1+x2≥70 ? x12+x1+x2+x3≥70 ? x1+x2+x3+x4≥70 ? x2+x3+x4+x5≥70 ? x3+x4+x5+x6≥70 ? x4+x5+x6+x7≥70 ? x5+x6+x7+x8 ≥70 x6+x7+x8+x9 ≥60 x7+x8+x9+x10 ≥ 50 x8+x9+x10+x11 ≥20 x9+x10+x11+x12 ≥30 非負(fù)性約束： xj ≥0,j=1,2,…12 該公司進(jìn)一步分析還可以知道，每個(gè)時(shí)段的人數(shù)分別是 序號(hào) 時(shí)間段 所需人數(shù) 方案 具體的方案 1 方案 0 具體的方案 2 1 6~10 60 X1 60 40 60 2 10~14 70 X2 10 30 10 3 14~18 60 X3 50 30 50 4 18~22 50 X4 0 20 0 5 22~2 20 X5 20 0 30 6 2~6 30 X6 10 30 0 如果我們進(jìn)一步來(lái)分析，例如某快餐店從上午 11點(diǎn)到晚上 10點(diǎn)需要的人數(shù)不一樣，該公司全日制工人 2人，每天工作 8小時(shí)，其余為兼職人員，每天工作 4小時(shí)，每小時(shí) 4元錢(qián)。據(jù)統(tǒng)計(jì)： 序號(hào) 時(shí)段 最少人數(shù) 安排人數(shù) 1 06— 10 60 X1 2 10— 14 70 X2 3 14— 18 60 X3 4 18— 22 50 X4 5 22— 02 20 X5 6 02— 06 30 x6 例題 3建模 ? 目標(biāo)函數(shù)： min Z=x1+x2+x3+x4+x5+x6 ? 約束條件： x1+x2 ≥70 x2+x3 ≥60 x3+x4 ≥ 50 x4+x5 ≥20 x5+x6 ≥30 非負(fù)性約束： xj ≥0,j=1,2,…6 該公司進(jìn)一步分析還可以知道，每個(gè)時(shí)段的人數(shù)分別是 序號(hào) 時(shí)間段 所需人數(shù) 方案 具體的方案 1 方案 0 具體的方案 2 1 6~10 60 X1 60 40 60 2 10~14 70 X2 10 30 10 3 14~18 60 X3 50 30 50 4 18~22 50 X4 0 20 0 5 22~2 20 X5 20 0 30 6 2~6 30 X6 10 30 0 ? 醫(yī)院護(hù)士 24小時(shí)值班，每次值班 8小時(shí)。最少需要配備的人數(shù)是多少？ 序號(hào) 時(shí)間段 所需人數(shù) 方案 1 6:00~14:00 70 70 x1 2 14:00~22:00 60 60 x2 3 22:00~6:00 30 30 x3 例題 3：人員安排問(wèn)題 模型：設(shè)不同的時(shí)間段的排班人數(shù)分別為 X XX3 Obj： MinZ=X1+X2+X3 S． T． X1≥70 X2≥60 X3≥30 X X X3≥0 ? 醫(yī)院護(hù)士 24小時(shí)值班，每次值班 8小時(shí)。飼料 II x2kg。問(wèn)如何安排生產(chǎn)，使生產(chǎn)獲得的利潤(rùn)最大？ I II 資源 設(shè)備臺(tái)時(shí) 1 2 8 原料 A 4 0 16 原料 B 0 4 12 單位產(chǎn)品利潤(rùn) 2 3 解：設(shè)產(chǎn)品 I、 II分別生產(chǎn) X X2個(gè) Obj： MaxX=2X1+3X2 S． T． X1+2X2≤8 4X1 ≤16 4X2 ≤12 X1， X2≥0 解得： X1=4， X2=2， Z=14 專(zhuān)業(yè)軟件求解結(jié)果 產(chǎn)品 1生產(chǎn) 4件，產(chǎn)品 2生產(chǎn) 2件，總利潤(rùn)為 14 EXCEL輸入界面 例題 2—— 配方問(wèn)題 ? 養(yǎng)海貍鼠 飼料中營(yíng)養(yǎng)要求： Va每天至少 700克， Vb每天至少 30克， Vc每天剛好 30克。 ? 本書(shū)有現(xiàn)成的程序可以利用 ? 要學(xué)會(huì)解題的思路與方法，建立模型很重要。 ? 數(shù)學(xué)模型：用符號(hào)或數(shù)學(xué)工具描述現(xiàn)實(shí)系統(tǒng)。 ? 形象模型：如地球儀、沙盤(pán)、風(fēng)洞 ? 模擬模型：建港口，模擬船只到達(dá)。但定量不可替代定量。 運(yùn)籌學(xué) —— 怎樣把事情做到最好 緒論 ? Operations 漢語(yǔ)翻譯 工作、操作、行動(dòng)、手術(shù)、運(yùn)算 Operations Research 日本 —— 運(yùn)用學(xué) 港臺(tái) —— 作業(yè)研究 中國(guó)大陸 —— 運(yùn)籌學(xué) Operational Research原來(lái)名稱(chēng)，意為軍事行動(dòng)研究 —— 歷史淵源 緒論 ? 運(yùn)籌學(xué)的歷史 早期運(yùn)籌思想：田忌賽馬 丁渭修宮 沈括運(yùn)糧