【正文】 一、 分配問(wèn)題 二、匈牙利方法 分配問(wèn)題 設(shè)：????否則項(xiàng)任務(wù)個(gè)人員去完成第表示分配第01 jix ij m in z = ? ?? ?ninjijij xa1 1 s . t . ??niijx1= 1 ， j = 1, 2 , . . . , n ??njijx1= 1 ， i = 1, 2 , . . . , n x i j = 1 或 0 分配問(wèn)題 基 本 概 念 解矩陣 系數(shù)矩陣 匹配 獨(dú)立 0元素 系數(shù)矩陣的定義與性質(zhì) 某游泳隊(duì)擬選用甲、乙、丙、丁四名游泳運(yùn)動(dòng)員組成一個(gè) 4 ? 10 0 米混合接力隊(duì)，參加今年的錦標(biāo)賽。他們的 100 米自由泳、蛙泳、蝶泳、仰泳的成績(jī)?nèi)绫硭?。本?shū)主要介紹最常用的前兩種方法。各產(chǎn)品占用資源數(shù)據(jù)，資源擁有數(shù)及產(chǎn)品利潤(rùn)（見(jiàn)表 1. 54 ）。 影子價(jià)格（ 2） 例 某工廠生產(chǎn) A , B , C 三種產(chǎn)品，每種產(chǎn)品都同時(shí)需要兩種原料，數(shù)據(jù)見(jiàn)表 1 . 53 表 1 . 53 原料 產(chǎn)品 A 產(chǎn)品 B 產(chǎn)品 C 現(xiàn)有原料（噸） 原料甲 2 1 2 7 原料乙 1 3 2 11 利潤(rùn)（萬(wàn)元） 2 3 1 解：設(shè) x1, x2, x3分別表示計(jì)劃生產(chǎn) A , B , C 產(chǎn)品的產(chǎn)量（噸） 數(shù)學(xué)模型為 ???????????????0,1123722..32m a x321321321321xxxxxxxxxtsxxxs 引進(jìn)松弛變量 x4, x5化成標(biāo)準(zhǔn)型： ?????????????????0,1123722..32m a x5432153214321321xxxxxxxxxxxxxtsxxxs 影子價(jià)格（ 3） 該問(wèn)題的最優(yōu)基對(duì)應(yīng)的單純形表見(jiàn)表 x B x 1 x 2 x 3 x 4 x 5 b x 1 1 0 4/ 5 3/ 5 1/ 5 2 x 2 0 1 2/ 5 1/ 5 2/ 5 3 C 0 0 9/ 5 3/ 5 4/ 5 13 影子價(jià)格（ 4） 例 9 某廠在下一個(gè)計(jì)劃期內(nèi)要安排生產(chǎn) I ， I I 兩種產(chǎn)品，現(xiàn)有生產(chǎn)每種產(chǎn)品一件要消耗的鋼材，煤和機(jī)械加工時(shí)間數(shù)；資源數(shù)及每件產(chǎn)品可獲得的利潤(rùn)如表所示（見(jiàn)表 1. 55 ） 試制訂一個(gè)最優(yōu)生產(chǎn)計(jì)劃。由于企業(yè)生產(chǎn)任務(wù)，產(chǎn)品的結(jié)構(gòu)及其知識(shí)的含量等情況的變化，資源的影子價(jià)格也隨之改變。 影子價(jià)格的經(jīng)濟(jì)意義： （一）第 i 種資源的影子價(jià)格 y i * 是一個(gè)邊際函數(shù)。已知甲，乙，丙，丁四種復(fù)合肥每公斤的價(jià)格及含氮，磷，鉀的數(shù)量，如表 1 . 5 。又知每一調(diào)度人員在任 1 時(shí)段開(kāi)始上班后，要連續(xù)工作 8 小時(shí)（包括輪流吃飯時(shí)間）才能滿足調(diào)度值班工作需要。運(yùn)籌學(xué)模型（ 1） [ 生產(chǎn)計(jì)劃模型 ] 國(guó)內(nèi)某手機(jī)產(chǎn)商考慮生產(chǎn)甲、乙、丙、丁型號(hào)的四款手機(jī)，每款手機(jī)都需要依次經(jīng)過(guò) A 、 B 、 C 三個(gè)車(chē)間加工完成。 B C A D 運(yùn)籌學(xué)模型（ 3） 【合理下料問(wèn)題】 某工地要求做 100 套鋼筋，每套為 3 根，它們的長(zhǎng)度分別 為 米， 米和 米；原材料長(zhǎng)為 米，為應(yīng)當(dāng)怎樣截割鋼筋，才能使所需的原材料根數(shù)為最少？ 提示 1：如果只需要截 100根，如何下料？ 提示 2：如果需要截 100根，又如何下料？ 有八種方法截取 ? 1 2 3 4 5 6 7 8 2 1 1 1 0 0 0 0 0 2 1 0 3 2 1 0 0 0 1 3 0 1 3 4 x1 x2 x3 x4 x5 x6 x7 x8 ? Mf=x1+x2+x3+x4+x5+x6+x7+x8 ? 2x1+x2+x3+x4=100 ? 2x2+3x3 +3x5+2x6+x7=100 ? x3+3x4 +x6+3x7+x8=100 ? Xj=0且為整數(shù) j=1,2,3,……8 運(yùn)籌學(xué)模型（ 4） 【排班問(wèn)題】 某工廠的中心調(diào)度室，每晝夜 24 小時(shí)都要有人員值班，已知每個(gè)時(shí)間段（每 4 小時(shí)為一個(gè)時(shí)間段）所需要的值班人員如表 1 . 6 。已知每件產(chǎn)品在每道工序上加工所需的機(jī)時(shí)及生產(chǎn)每件產(chǎn)品可以獲得的利潤(rùn)如下表，如何安排生產(chǎn)，才能使總利潤(rùn)最大？ 甲 乙 可用機(jī)時(shí) 工序 A 2 4 80 工序 B 3 2 60 單位利潤(rùn) 60 50 單純型法（二） 80. . 6 0012121212ma x f = 6 0 x +5 0 x2 x +4 xs t 3 x +2 xx 0 , x?????? ???（ 0， 20） C B（ 10， 15） （ 0， 0） O A （ 20， 0） 2x1x單純型法（三） 3480. . 6 01 2 3 41121212ma x f = 6 0 x +50 x2 x +4x xs t 3 x +2x xx 0 , j? ??????? ??? ， ， ，（ 0， 20） C B（ 10， 15） （ 0， 0） O A （ 20， 0） 2x單純型法（四） 3480. . 6 01 2 3 41121212ma x f = 6 0 x +50 x2 x +4x xs t 3 x +2x xx 0 , j? ??????? ??? ， ， ，???????????????????432102031324032382022120042143242,j,xxxxxxx.xxfma xj????????????????????43210302123402425151 5 0 042143141,j,xxxxxxx.xxfm a xj??????????????????432104021260234321432,j,xxxxxxx.fma xj??????????????????4,3,2,1,020212204121..225351000m a x43132131jxxxxxxxtsxxfj???????????????????4,3,2,1,0154183102141..2354151350m a x43243143jxxxxxxxtsxxfj單純型法（五） 基變量 ————“非自由變量”，記號(hào) xB 非基變量 ————“自由變量”，記號(hào) 基 —— 所有基變量下標(biāo)的集合，記號(hào) B 典式 —— 約束等式是基變量由非基變量表示； 目標(biāo)函數(shù)中不含有基變量 單純形表 ——基可行解典式的表格化 ? 檢驗(yàn)數(shù) ? 入基變量 ? 出基變量 ? 轉(zhuǎn)軸點(diǎn) Bx單純型法（六） ?????????????)2,1(08234..52m a x212121jxxxxxtsxxfj解：引進(jìn)松弛變量 x3 , x4 , x5，把線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形 ??????????????????)51(08234..52m a x521423121?jxxxxxxxxtsxxfj單純型法（七） 基變量 XB=(x3 , x4 , x5)，可以得到對(duì)應(yīng)的單純形表如下： CxB x1 x2 x3 x4 x5 x3 1 0 1 0 0 4 x4 0 1 0 1 0 3 x5 1 2 0 0 1 8 ? 2 5 0 0 0 0 b[1] 單純型法（八） 單純表矩陣計(jì)算公式： X b XB 1?BAA 1?BAb c － CT＋ C BT 1?BAA CBT1?BAb ???????????????32,10112..32m a x3121321jxxxxxxtsxxxfj x1 x2 x3 b x1 1 0 1 1 x2 0 1 2 1 c 0 0 2 3 單純型法（九） 例 ????????????????2,10644..m a x21212121jxxxxxxxtsxxfj解：化成標(biāo)準(zhǔn)形 ???????????????????5,4,3,2,10644..m a x52142132121jxxxxxxxxxxtsxxfj單純型法（十） 例 解：化成標(biāo)準(zhǔn)形 ??????????????2,1010525..2m a x212121jxxxxxtsxxfj????????????????4,3,2,1010525..2m a x42132121jxxxxxxxtsxxsj單純型法（十一） 例 x1 x2 x3 x4 b x3 1 1 1 0 5 x4 2 5 0 1 10 c 2 1 0 0 0 兩階段法（ 1） 例 ??????????????????5, . . . ,2,101226..215m a x5321432131jxxxxxxxxxtsxxfj解：引入人工變量 x6, x7構(gòu)造輔助問(wèn)題 ????????