運(yùn)輸問(wèn)題和指派問(wèn)題

運(yùn)輸問(wèn)題和指派問(wèn)題第1頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第一節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型運(yùn)輸問(wèn)題的一般描述：某種物質(zhì)（糧食、棉花、煤等）有若干個(gè)產(chǎn)地和銷(xiāo)地，現(xiàn)在需要把物質(zhì)從各個(gè)產(chǎn)地運(yùn)往各個(gè)銷(xiāo)地，產(chǎn)量總數(shù)等于銷(xiāo)量總數(shù)，調(diào)運(yùn)方案很多。若已知各產(chǎn)地的產(chǎn)量、各銷(xiāo)地的銷(xiāo)量以及各產(chǎn)地到銷(xiāo)地的單位運(yùn)價(jià)（或運(yùn)輸距離）。又假定運(yùn)費(fèi)和運(yùn)輸量成正比，問(wèn)如何調(diào)運(yùn)，才能使總運(yùn)費(fèi)最??？第2頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第一節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型

設(shè)Xij為第i個(gè)產(chǎn)地運(yùn)往第j個(gè)銷(xiāo)地的數(shù)量這是m×n個(gè)變量，約束條件為m+n個(gè)的線性規(guī)劃問(wèn)題。MinZ=CijXijxij

=ai

（i=1，2，…，m）

xij

=bj

（j=1，2，…，n）

xij≥0（i=1，2，…，m；j=1，2，…，n）第3頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第一節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型一、運(yùn)輸問(wèn)題約束條件系數(shù)矩陣A=11…1111…1……………………11…111…1111……………………111（m+n）×（mn）第4頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第一節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型二、運(yùn)輸問(wèn)題的基變量共有m+n-1個(gè)三、m+n-1個(gè)變量構(gòu)成基變量的充要條件是它們不構(gòu)成閉合回路第5頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第二節(jié)表上作業(yè)法表上作業(yè)法求解運(yùn)輸問(wèn)題的思路和單純形法完全類(lèi)似。建立作業(yè)表①確定初始調(diào)運(yùn)方案②現(xiàn)行方案的最優(yōu)性檢驗(yàn)③現(xiàn)行方案的調(diào)整第6頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第二節(jié)表上作業(yè)法一、初始方案的確定：1.西北角法（左上角法）從表的左上角開(kāi)始，保證產(chǎn)銷(xiāo)平衡，每填上一個(gè)數(shù)劃去一行或一列，直到有m+n-1行或列劃去即可。填上數(shù)字為基變量，從而保證其個(gè)數(shù)為m+n-1個(gè)又不構(gòu)成閉合回路。第7頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第二節(jié)表上作業(yè)法一、初始方案的確定：2.最小元素法采用“就近供應(yīng)”的思想。從運(yùn)輸表的運(yùn)費(fèi)最小的元素開(kāi)始，保證產(chǎn)銷(xiāo)平衡，每填上一個(gè)數(shù)劃去一行或一列，直到有m+n-1行或列劃去即可。填上數(shù)字為基變量，從而保證其個(gè)數(shù)為m+n-1個(gè)又不構(gòu)成閉合回路。第8頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第二節(jié)表上作業(yè)法一、初始方案的確定：3.元素差額法（Vogel近似法）是在最小元素法基礎(chǔ)上的改進(jìn)。①求每行和每列的行罰數(shù)和列罰數(shù)從行罰數(shù)和列罰數(shù)最大的行或列的運(yùn)費(fèi)最小的元素開(kāi)始，保證產(chǎn)銷(xiāo)平衡，每填上一個(gè)數(shù)劃去一行或一列。③重復(fù)①和②直到有m+n-1行或列劃去即可。填上數(shù)字為基變量，從而保證其個(gè)數(shù)為m+n-1個(gè)又不構(gòu)成閉合回路。第9頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第二節(jié)表上作業(yè)法二、最優(yōu)性檢驗(yàn)1.閉合回路法：2.位勢(shì)法：三、調(diào)整第10頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月表上作業(yè)法的幾點(diǎn)說(shuō)明：1.若運(yùn)輸問(wèn)題的某一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)為負(fù)時(shí)，在迭代時(shí)可取它們中任一非基變量進(jìn)基均可使目標(biāo)函數(shù)值得到改善，但通常取最小者對(duì)應(yīng)的非基變量進(jìn)基。2.當(dāng)?shù)阶顑?yōu)解時(shí)，有某非基變量的檢驗(yàn)數(shù)為0時(shí)，則問(wèn)題有無(wú)窮多最優(yōu)解。3.當(dāng)在表上作業(yè)時(shí)，同時(shí)劃去了一行和一列運(yùn)輸價(jià)格時(shí)，就出現(xiàn)了退化，此時(shí)必須在當(dāng)前劃去的運(yùn)價(jià)中某一空格填入一個(gè)0，表示該格中的變量是取值為0的基變量。第11頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第三節(jié)產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題一、產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題虛設(shè)銷(xiāo)地，其需要量為∑ai-∑bj,相應(yīng)的運(yùn)費(fèi)為0，化成產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題。MinZ=CijXijxij

≤ai

（i=1，2，…，m）

xij

=bj

（j=1，2，…，n）

xij≥0（i=1，2，…，m；j=1，2，…，n）第12頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第三節(jié)產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題一、銷(xiāo)大于產(chǎn)的運(yùn)輸問(wèn)題虛設(shè)產(chǎn)地，其產(chǎn)量為∑bj-∑ai,相應(yīng)的運(yùn)費(fèi)為0，化成產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題。MinZ=CijXijxij

=

ai

（i=1，2，…，m）

xij

≤

bj

（j=1，2，…，n）

xij≥0（i=1，2，…，m；j=1，2，…，n）第13頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第四節(jié)指派問(wèn)題指派問(wèn)題的標(biāo)準(zhǔn)形式（以人和事為例）是：有n個(gè)人和n件事，已知第i人做第j事的費(fèi)用為Cij（i，j=1，2，…，n），要求確定人和事之間的一一對(duì)應(yīng)的指派方案，使完成這件事的總費(fèi)用最少。如任務(wù)人員ABCD甲乙丙丁210971541481314161141513914第14頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第四節(jié)指派問(wèn)題一、指派問(wèn)題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型令

1當(dāng)指派第i人完成第j項(xiàng)任務(wù)

0當(dāng)不指派第i人完成第j項(xiàng)任務(wù)xij=minz=∑∑cijxij∑xij=1，j=1，2，…，n∑xij=1，i=1，2，…，nxij=1或015第15頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第四節(jié)指派問(wèn)題二、指派問(wèn)題的匈牙利解法標(biāo)準(zhǔn)的指派問(wèn)題是一類(lèi)特殊的0-1整數(shù)規(guī)劃問(wèn)題，可以用多種相應(yīng)的解法來(lái)求解。但是，這些方法都沒(méi)有充分利用指派問(wèn)題的特殊性質(zhì)來(lái)有效減少計(jì)算量。1955年，庫(kù)恩（W.W.Kuhn）利用匈牙利數(shù)學(xué)家康尼格（D.K?nig）的關(guān)于矩陣中獨(dú)立零元素的定理，提出了指派問(wèn)題的一種解法，由此，習(xí)慣上稱(chēng)之為匈牙利解法。16第16頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第四節(jié)指派問(wèn)題二、指派問(wèn)題的匈牙利解法

匈牙利解法的關(guān)鍵是利用了指派問(wèn)題最優(yōu)解的如下性質(zhì)：若從指派問(wèn)題的系數(shù)矩陣C=（cij

）n×n的某行（或某列）各元素分別減去一個(gè)常數(shù)k

，得到一個(gè)新的系數(shù)矩陣C’=（c’ij

）則以C和C’為系數(shù)矩陣的兩個(gè)指派問(wèn)題有相同的最優(yōu)解。17第17頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月匈牙利解法的一般步驟步驟一：變換系數(shù)矩陣。使其每行及每列至少有一個(gè)零元素，同時(shí)不出現(xiàn)負(fù)元素。步驟二：進(jìn)行試指派，即確定獨(dú)立零元素。步驟三：繼續(xù)變換系數(shù)矩陣，然后返回步驟二。第18頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第四節(jié)指派問(wèn)題指派問(wèn)題（assignmentproblem）匈牙利解法的一般步驟對(duì)沒(méi)有加圈零元素的行打√號(hào)；對(duì)所有打√號(hào)行的所有含零元素的列打√號(hào)；再對(duì)已打√號(hào)的列中含零元素的行打√號(hào)；重復(fù)2）和3），直到再也不能找到可以打√號(hào)行或列為止；對(duì)沒(méi)有打√號(hào)的行畫(huà)一橫線，對(duì)打√號(hào)的列畫(huà)一豎線，這樣就得到能覆蓋所有零元素的最少直線數(shù)目的直線集合。19第19頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月指派問(wèn)題（assignmentproblem）匈牙利解法的一般步驟以上例說(shuō)明步驟

2151341041415914161378119

013112601011057401422497min（cij

）=20第20頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月指派問(wèn)題（assignmentproblem）匈牙利解法的一般步驟以上例說(shuō)明步驟

01311260101104740142

0042min

01370606905320100=（c’ij

）21第21頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月指派問(wèn)題（assignmentproblem）匈牙利解法的一般步驟以上例說(shuō)明步驟

01370606905320100此時(shí)加圈0元素的個(gè)數(shù)m=n=4，所以得到最優(yōu)解22第22頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月指派問(wèn)題（assignmentproblem）匈牙利解法的一般步驟以上例說(shuō)明步驟

00010100

10000010（xij

）=23第23頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月指派問(wèn)題（assignmentproblem）匈牙利解法的一般步驟例任務(wù)人員ABCDE甲乙丙丁戊128715479171410961267761461096910924第24頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月指派問(wèn)題（assignmentproblem）匈牙利解法的一般步驟

127979896667171214915146610410710976764

5020223000010572980040636525第25頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月指派問(wèn)題（assi