圖論和網(wǎng)絡(luò)分析算法及Matlab實(shí)現(xiàn)PPT課件

1、2021-10-29涉及網(wǎng)絡(luò)優(yōu)化的數(shù)學(xué)建模問題涉及網(wǎng)絡(luò)優(yōu)化的數(shù)學(xué)建模問題1、最短路問題貨柜車貨柜車司機(jī)司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱縱橫交錯(cuò)橫交錯(cuò)，因此有多種行車路線，這名司機(jī)應(yīng)，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問題相當(dāng)于需要找到一條恒定的，那么這一問題相當(dāng)于需要找到一條從甲地到乙地的從甲地到乙地的最短路最短路。 第1頁(yè)/共74頁(yè)2021-10-292 2、最小支撐樹問題最小支撐樹問題某一地區(qū)有若干個(gè)主

2、要城市，現(xiàn)準(zhǔn)備修建高速公某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些路把這些城市連接城市連接起來(lái)，使得從其中任何一個(gè)城起來(lái)，使得從其中任何一個(gè)城市都可以經(jīng)高速公路市都可以經(jīng)高速公路直接或間接直接或間接到達(dá)另一個(gè)城市到達(dá)另一個(gè)城市。假定已經(jīng)知道了任意兩個(gè)城市之間修建。假定已經(jīng)知道了任意兩個(gè)城市之間修建高速公高速公路成本路成本，那么應(yīng)如何決定在哪些城市間修建高速，那么應(yīng)如何決定在哪些城市間修建高速公路，使得公路，使得總成本最小總成本最小？第2頁(yè)/共74頁(yè)2021-10-293 3、 指派問題指派問題Assignment problemAssignment problem 一家公司經(jīng)理一家公司

3、經(jīng)理安排安排N N名員工去完成名員工去完成N N項(xiàng)任務(wù)，每項(xiàng)任務(wù)，每人一項(xiàng)。由于各員工的人一項(xiàng)。由于各員工的特點(diǎn)不同特點(diǎn)不同，不同的員工，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)不同回報(bào)不同。如何。如何分配工作方案可以使總分配工作方案可以使總回報(bào)最大回報(bào)最大？ 第3頁(yè)/共74頁(yè)2021-10-294 4、中國(guó)郵遞員問題、中國(guó)郵遞員問題Chinese postman problemChinese postman problem一名一名郵遞員郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為他（她）設(shè)計(jì)一條最短的他（她）設(shè)計(jì)一條最短的投遞路線投遞路線（從郵

4、局出（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次街道至少一次，最后返，最后返回郵局）？回郵局）？我國(guó)管梅谷教授我國(guó)管梅谷教授1960年首先提出，年首先提出，國(guó)際上稱之為中國(guó)郵遞員問題。國(guó)際上稱之為中國(guó)郵遞員問題。 第4頁(yè)/共74頁(yè)2021-10-295 5 、旅行商問題、旅行商問題Traveling salesman problemTraveling salesman problem一名一名推銷員推銷員準(zhǔn)備前往若干準(zhǔn)備前往若干城市城市推銷產(chǎn)推銷產(chǎn)品。如何為他設(shè)計(jì)一條品。如何為他設(shè)計(jì)一條最短最短的旅行的旅行路線？路線？ （從駐地出發(fā)，經(jīng)過每個(gè)城（從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次

5、，最后返回駐地）市恰好一次，最后返回駐地）第5頁(yè)/共74頁(yè)2021-10-296 6、運(yùn)輸問題、運(yùn)輸問題Transportation problemTransportation problem 某種原材料有某種原材料有 M M個(gè)產(chǎn)地個(gè)產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往地運(yùn)往 N N個(gè)使用這些原材料的工廠。假定個(gè)使用這些原材料的工廠。假定 M M個(gè)產(chǎn)個(gè)產(chǎn)地的產(chǎn)量和地的產(chǎn)量和 N N家工廠家工廠的需要量已知，單位產(chǎn)品從的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么如何安排任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸方案可以使總運(yùn)輸成本運(yùn)輸成本最低？

6、最低？第6頁(yè)/共74頁(yè)2021-10-29問題的兩個(gè)共同特點(diǎn)問題的兩個(gè)共同特點(diǎn)（1 1）目的都是從若干可能的安排或方案中尋求）目的都是從若干可能的安排或方案中尋求 某種意義下的某種意義下的最優(yōu)安排最優(yōu)安排或方案，數(shù)學(xué)問題稱或方案，數(shù)學(xué)問題稱 為最優(yōu)化或?yàn)樽顑?yōu)化或優(yōu)化問題優(yōu)化問題。（2 2）它們都可用）它們都可用圖形圖形形式直觀描述，數(shù)學(xué)上把這形式直觀描述，數(shù)學(xué)上把這 種與圖相關(guān)的結(jié)構(gòu)稱為種與圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡(luò)網(wǎng)絡(luò)。圖和網(wǎng)絡(luò)相關(guān)圖和網(wǎng)絡(luò)相關(guān) 的最優(yōu)化問題就是的最優(yōu)化問題就是網(wǎng)絡(luò)最優(yōu)化網(wǎng)絡(luò)最優(yōu)化。 網(wǎng)絡(luò)優(yōu)化問題是以網(wǎng)絡(luò)流為研究的對(duì)象，常網(wǎng)絡(luò)優(yōu)化問題是以網(wǎng)絡(luò)流為研究的對(duì)象，常 常被稱為網(wǎng)絡(luò)流或常被

7、稱為網(wǎng)絡(luò)流或網(wǎng)絡(luò)流規(guī)劃網(wǎng)絡(luò)流規(guī)劃等。等。 第7頁(yè)/共74頁(yè) 一、圖論的基本概念1 . 圖與子圖11( ,),nmGV EVvvEee，其中為，圖頂點(diǎn)集為邊集。11111( ,),GV EVV EE其中子圖。e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如 G：簡(jiǎn)單圖：無(wú)自環(huán)、無(wú)重邊的圖。第8頁(yè)/共74頁(yè)2021-10-29 |V|=n表示圖G中節(jié)點(diǎn)個(gè)數(shù)為n，此節(jié)點(diǎn)個(gè)數(shù)n也稱為圖G的階 |E|=m表示圖G中邊的個(gè)數(shù)為m 任一頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目稱為該頂點(diǎn)的度 完全圖：任意兩點(diǎn)有邊相連，用 表示 完全圖的邊，和每點(diǎn)的度是多少？nK第9頁(yè)/共74頁(yè)2 . 關(guān)聯(lián)

8、與相鄰121212, ,()ev vev vvve（邊與點(diǎn)關(guān)系）：若 是二點(diǎn)間的邊，記稱或聯(lián)與關(guān)關(guān)聯(lián)。12121212 vvvveeee（邊與邊、點(diǎn)與點(diǎn)）：點(diǎn) 與 有公共邊，稱 與 相鄰； 邊 與 有公共點(diǎn)，稱 與鄰接相鄰。n1110100110001000110100001101： 關(guān)聯(lián)矩陣： *m或者是m*n圖在計(jì)算機(jī)中的表示第10頁(yè)/共74頁(yè)n0111101011011011鄰接矩陣： *n鄰接矩陣為對(duì)稱陣，簡(jiǎn)單圖對(duì)角線元素為0第11頁(yè)/共74頁(yè)3 . 鏈與圈1 1 2 211 , MatlabkkiiiGv ev eevev vG:由 中的某些點(diǎn)與邊相間構(gòu)成的序列，若滿足則稱此邊點(diǎn)序鏈

9、列為 中的一條鏈。 鏈在中的存儲(chǔ)：只儲(chǔ)存頂點(diǎn)標(biāo)號(hào)圈：封閉的鏈。G：圖 中任二點(diǎn)間至少存連通圖在一條鏈。第12頁(yè)/共74頁(yè)4. 有向圖與無(wú)向圖 ( ,),(, , ). ,),kijijijGV EGvv vv vGGv v無(wú)向圖也可記若點(diǎn)對(duì)無(wú)序，稱 為；否則稱 為。為區(qū)別起見，稱有向圖圖有向圖弧的邊為，記（在圖上用箭線表示。），路有向圖：?。?，鏈無(wú)向圖：邊,，圈，回路比較：第13頁(yè)/共74頁(yè)1ijijavv 有向圖的存儲(chǔ)：行為起點(diǎn)，列為終點(diǎn)存在弧賦權(quán)圖：邊有長(zhǎng)度v1v2v3v5v4834217第14頁(yè)/共74頁(yè) W= .41 .99 .51 .32 .15 .45 .38 .32 .36 .2

10、9 .21 ;DG=sparse6 1 2 2 3 4 4 5 5 6 1 , 2 6 3 5 4 1 6 3 4 3 5 ,Wview(biograph(DG,ShowWeights,on)UG tril DG DGview(biograph(UG,ShowWeights,on)；賦權(quán)圖在Matlab中的存儲(chǔ)：第15頁(yè)/共74頁(yè)5. 樹 例1 已知有5個(gè)城市，要在它們之間架設(shè)電話線網(wǎng)，要求任2城市都可通話（允許通過其它城市），并且電話線的根數(shù)最少。v1v2v3v5v4 特點(diǎn)：連通、無(wú)圈。樹無(wú)圈的連通圖，記為T。第16頁(yè)/共74頁(yè)v1v2v3v5v4樹的性質(zhì)：（1）樹的任2點(diǎn)間有且僅有1鏈；

11、（2）在樹中任去掉1邊，則不連通； （3）在樹中不相鄰2點(diǎn)間添1邊，恰成1圈； （4）若樹T有n個(gè)頂點(diǎn)，則T有n-1條邊。第17頁(yè)/共74頁(yè)6.圖的支撐樹 若圖G=（V，E）的子圖T=（V，E）是樹，則稱T為G的支撐樹。特點(diǎn)邊少、點(diǎn)不少。性質(zhì)：G連通，則G必有支撐樹。證：破圈、保連通。第18頁(yè)/共74頁(yè)二、網(wǎng)絡(luò)分析二、網(wǎng)絡(luò)分析網(wǎng)絡(luò)賦權(quán)圖，記D=（V，E，C），其中C=c1，cn， ci為邊ei上的權(quán)（設(shè)ci ）。網(wǎng)絡(luò)分析主要內(nèi)容: 最小支撐樹 最短路 最大流。0第19頁(yè)/共74頁(yè)一. 最小支撐樹問題問題：求網(wǎng)絡(luò)D的支撐樹，使其權(quán)和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，

12、1975)。例 2 求如圖網(wǎng)絡(luò)的最小支撐樹。v5v1v3v6v4v2v7255233575711Kruskal, J.B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society 7, 48-50. 第20頁(yè)/共74頁(yè)避圈法是一種選邊的過程，其步驟如下：1. 從網(wǎng)絡(luò)D中任選一點(diǎn)vi，找出與vi相關(guān)聯(lián)的 權(quán)最小的邊vi，vj，得第二個(gè)頂點(diǎn)vj；2. 把頂點(diǎn)集V分為互補(bǔ)的兩部分V1,

13、 1 ，其中V集；不與已選邊相關(guān)聯(lián)的點(diǎn)，與已選邊相關(guān)聯(lián)的點(diǎn)集， 11VV其中權(quán)最小的；挑選其中考慮所有這樣的邊 , 3.11svsvvvjiji。即，直至全部頂點(diǎn)屬于重復(fù))(3 4.11ss第21頁(yè)/共74頁(yè)2021-10-29對(duì)G中各邊按權(quán)大小順序排列，不妨設(shè)為W1 W2 Wm填寫Wj對(duì)應(yīng)的各邊aj S= ，i = 0，j=1aj S構(gòu)成回路？|S| = n-1= n-1ei+1=aj S=ei+1 Si=i +1 j=j+1j=j+1T*=S打印T*ENDYYNN第22頁(yè)/共74頁(yè)用避圈法解例2v5v1v3v6v4v2v7255233575711最小部分樹如圖上紅線所示；最小權(quán)和為14。思

14、考：破圈法是怎樣做的呢？見圈就破，去掉其中權(quán)最大的。第23頁(yè)/共74頁(yè)最小支撐樹問題的應(yīng)用例子 已知有A、B、C、D、E、F六個(gè)城鎮(zhèn)間的道路網(wǎng)絡(luò) 如圖，現(xiàn)要在六個(gè)城鎮(zhèn)間架設(shè)通訊網(wǎng)絡(luò)（均沿道路架設(shè)），每段道路上的架設(shè)費(fèi)用如圖。求能保證各城鎮(zhèn)均能通話且總架設(shè)費(fèi)用最少的架設(shè)方案。6EACBFD5109353978284第24頁(yè)/共74頁(yè)二. 最短路問題1. 問題：求網(wǎng)絡(luò)D中一定點(diǎn)v1到其它點(diǎn)的最短路。 例3 求如圖網(wǎng)絡(luò)中v1至v7的最短路，圖中數(shù)字為兩點(diǎn)間距離。v5v1v3v6v4v2v7255233575711第25頁(yè)/共74頁(yè)2021-10-29 2. 方法：Dijkstra算法（Dijkstr

15、a，1959） Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269271. 原理： Bellman最優(yōu)化原理 若P是網(wǎng)絡(luò)G中從Vs到Vt的一條最短路，Vl是P中除Vs與Vt外的任何一個(gè)中間點(diǎn)，則沿P從Vs到Vl的一條路P1亦必是Vs到Vl的最短路。 證明（反證）： 若P1不是從Vs到Vl的最短路，則存在另一條 Vs到Vl的路P2使W(P2)W(P1)，若記路P中從Vl到Vt的路為P3。則有W(P2)+W(P3) 300 300米米) ) 對(duì)坡度對(duì)

16、坡度的限制的限制 0.125= 0 0.100 第61頁(yè)/共74頁(yè)2021-10-29模型計(jì)算方法模型計(jì)算方法 (1) (1) 對(duì)地圖網(wǎng)格加密，形成圖。對(duì)地圖網(wǎng)格加密，形成圖。 (2) (2) 計(jì)算網(wǎng)格的距離，用費(fèi)用作為權(quán)值。計(jì)算網(wǎng)格的距離，用費(fèi)用作為權(quán)值。 (3) (3) 求賦權(quán)圖兩點(diǎn)間的最短距離。求賦權(quán)圖兩點(diǎn)間的最短距離。 第62頁(yè)/共74頁(yè)2021-10-29參考答案參考答案第63頁(yè)/共74頁(yè)2021-10-29 災(zāi)情巡視路線，下圖為某縣的鄉(xiāng)（鎮(zhèn)）、災(zāi)情巡視路線，下圖為某縣的鄉(xiāng)（鎮(zhèn)）、村公路網(wǎng)示意圖，公路邊的數(shù)字為該路段村公路網(wǎng)示意圖，公路邊的數(shù)字為該路段的公里數(shù)。今年夏天該縣遭受水災(zāi)。

17、為考的公里數(shù)。今年夏天該縣遭受水災(zāi)。為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。路線。第64頁(yè)/共74頁(yè)2021-10-291. 若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線。能均衡的巡視路線。 2. 假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2T=2小時(shí)

18、，在各小時(shí)，在各村停留時(shí)間村停留時(shí)間t=1t=1小時(shí)，汽車行駛速度小時(shí)，汽車行駛速度V=35V=35公里公里/ /小時(shí)。小時(shí)。要在要在2424小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下你認(rèn)為最佳的巡視路線。組下你認(rèn)為最佳的巡視路線。3. 若巡視組數(shù)已定若巡視組數(shù)已定(如三組如三組)，要求盡快完成巡視，討論，要求盡快完成巡視，討論T，t和和V改變對(duì)最佳巡視路線的影響。改變對(duì)最佳巡視路線的影響。 4. 上述關(guān)于上述關(guān)于T , t和和V的假定下，如果巡視人員足夠多，的假定下，如果巡視人員足夠多，完成巡視的最短時(shí)間是多少；給出在這種最短時(shí)間完完成巡視的最短時(shí)間

19、是多少；給出在這種最短時(shí)間完成巡視的要求下，你認(rèn)為最佳的巡視路線。成巡視的要求下，你認(rèn)為最佳的巡視路線。第65頁(yè)/共74頁(yè)2021-10-29鄉(xiāng)村分布圖鄉(xiāng)村分布圖第66頁(yè)/共74頁(yè)2021-10-29點(diǎn)的行遍性問題點(diǎn)的行遍性問題1 1、圖論、圖論-哈密爾頓問題（是否存在經(jīng)過所有點(diǎn)一次的圈）哈密爾頓問題（是否存在經(jīng)過所有點(diǎn)一次的圈）2 2、組合優(yōu)化、組合優(yōu)化-旅行商問題（賦權(quán)圖經(jīng)過所有頂點(diǎn)至少一次）旅行商問題（賦權(quán)圖經(jīng)過所有頂點(diǎn)至少一次） 非完全圖的多旅行商問題非完全圖的多旅行商問題v 兩點(diǎn)間的最短路長(zhǎng)度作為兩點(diǎn)間的權(quán)，構(gòu)造完全圖。兩點(diǎn)間的最短路長(zhǎng)度作為兩點(diǎn)間的權(quán)，構(gòu)造完全圖。v 兩邊權(quán)之和不小

20、于第三邊的權(quán)兩邊權(quán)之和不小于第三邊的權(quán)=v 完全圖的最優(yōu)哈密爾頓圈完全圖的最優(yōu)哈密爾頓圈=原圖的最優(yōu)旅行商問題。原圖的最優(yōu)旅行商問題。v 完全圖完全圖-增廣完全圖增廣完全圖=求最優(yōu)哈密爾頓圈求最優(yōu)哈密爾頓圈v 近似算法或分組后直接搜索近似算法或分組后直接搜索v 注意（1 1） 兩點(diǎn)間的最短路長(zhǎng)度可用DijkstraDijkstra算法（2 2） 多旅行商問題=最優(yōu)哈密爾頓圈第67頁(yè)/共74頁(yè)2021-10-29線性規(guī)劃模型線性規(guī)劃模型第68頁(yè)/共74頁(yè)2021-10-29問題解答：?jiǎn)栴}解答：1 1、分三組（路）巡視，試設(shè)計(jì)總路程最短且分三組（路）巡視，試設(shè)計(jì)總路程最短且 各組盡可能均衡的巡視路

21、線。各組盡可能均衡的巡視路線。 目標(biāo)函數(shù)：目標(biāo)函數(shù)： min(C1+C2+C3)min(C1+C2+C3) 限制條件：限制條件：min(C3 - C1)min(C3 - C1) 或或 者者 ：min(C1)min(C1)2、假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2T=2小時(shí)小時(shí)，在各村停留時(shí)間，在各村停留時(shí)間t=1t=1小時(shí)，汽車行駛速度小時(shí)，汽車行駛速度V=35V=35公里公里/ /小時(shí)。要在小時(shí)。要在2424小時(shí)內(nèi)完成巡視，至少應(yīng)分小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下最佳的巡視路線幾組；給出這種分組下最佳的巡視路線。第69頁(yè)/共74頁(yè)2021-10-2

22、9 目標(biāo)函數(shù)：目標(biāo)函數(shù)： min(H1+H2+H3)min(H1+H2+H3) 花費(fèi)時(shí)間：花費(fèi)時(shí)間：Hi=2mi+ni+Ci/VHi=2mi+ni+Ci/V 限制條件：限制條件：min(max(Hi)min(max(Hi)總時(shí)間總時(shí)間6969小時(shí)小時(shí)=至少至少4 4組，組，4 4組的路線可以找到。組的路線可以找到。3 3、在上述關(guān)于在上述關(guān)于T , tT , t和和V V的假定下，如果巡視人員足夠多，完成的假定下，如果巡視人員足夠多，完成巡視的最短時(shí)間是多少；給出在這種最短時(shí)間完成巡視的要求巡視的最短時(shí)間是多少；給出在這種最短時(shí)間完成巡視的要求下，你認(rèn)為最佳的巡視路線。下，你認(rèn)為最佳的巡視路線

23、。 單獨(dú)巡視的最短時(shí)間單獨(dú)巡視的最短時(shí)間= =最遠(yuǎn)距離最遠(yuǎn)距離 （1）每組時(shí)間不超過最遠(yuǎn)距離時(shí)間）每組時(shí)間不超過最遠(yuǎn)距離時(shí)間 （2）巡視組足夠少，）巡視組足夠少，2222組組4 4、 若巡視組數(shù)已定若巡視組數(shù)已定( (如三組如三組) )，要求盡快完成巡視，討論，要求盡快完成巡視，討論T T，t t和和 V V改變對(duì)最佳巡視路線的影響。改變對(duì)最佳巡視路線的影響。 討論花費(fèi)時(shí)間函數(shù)：討論花費(fèi)時(shí)間函數(shù)：Hi=2mi+ni+Ci/VHi=2mi+ni+Ci/V注意：多旅行商問題注意：多旅行商問題=單旅行商問題（單旅行商問題（LING2LING2）第70頁(yè)/共74頁(yè)2021-10-29DVD在線租賃在線

24、租賃 隨著信息時(shí)代的到來(lái)，網(wǎng)絡(luò)成為人們生活中越來(lái)越不可或缺的元素之一。許多網(wǎng)站利用其強(qiáng)大隨著信息時(shí)代的到來(lái)，網(wǎng)絡(luò)成為人們生活中越來(lái)越不可或缺的元素之一。許多網(wǎng)站利用其強(qiáng)大的資源和知名度，面向其會(huì)員群提供日益專業(yè)化和便捷化的服務(wù)。例如，音像制品的在線租賃的資源和知名度，面向其會(huì)員群提供日益專業(yè)化和便捷化的服務(wù)。例如，音像制品的在線租賃就是一種可行的服務(wù)。這項(xiàng)服務(wù)充分發(fā)揮了網(wǎng)絡(luò)的諸多優(yōu)勢(shì)，包括傳播范圍廣泛、直達(dá)核心消就是一種可行的服務(wù)。這項(xiàng)服務(wù)充分發(fā)揮了網(wǎng)絡(luò)的諸多優(yōu)勢(shì)，包括傳播范圍廣泛、直達(dá)核心消費(fèi)群、強(qiáng)烈的互動(dòng)性、感官性強(qiáng)、成本相對(duì)低廉等，為顧客提供更為周到的服務(wù)。費(fèi)群、強(qiáng)烈的互動(dòng)性、感官性強(qiáng)、

25、成本相對(duì)低廉等，為顧客提供更為周到的服務(wù)。 考慮如下的在線考慮如下的在線DVD租賃問題。顧客繳納一定數(shù)量的月費(fèi)成為會(huì)員，訂購(gòu)租賃問題。顧客繳納一定數(shù)量的月費(fèi)成為會(huì)員，訂購(gòu)DVD租賃服務(wù)。會(huì)員租賃服務(wù)。會(huì)員對(duì)哪些對(duì)哪些DVD有興趣，只要在線提交訂單，網(wǎng)站就會(huì)通過快遞的方式盡可能滿足要求。會(huì)員提交有興趣，只要在線提交訂單，網(wǎng)站就會(huì)通過快遞的方式盡可能滿足要求。會(huì)員提交的訂單包括多張的訂單包括多張DVD，這些這些DVD是基于其偏愛程度排序的。網(wǎng)站會(huì)根據(jù)手頭現(xiàn)有的是基于其偏愛程度排序的。網(wǎng)站會(huì)根據(jù)手頭現(xiàn)有的DVD數(shù)量和數(shù)量和會(huì)員的訂單進(jìn)行分發(fā)。每個(gè)會(huì)員每個(gè)月租賃次數(shù)不得超過會(huì)員的訂單進(jìn)行分發(fā)。每個(gè)會(huì)員每個(gè)月租賃次數(shù)不得超過2次，每次獲得次，每次獲得3張張DVD。會(huì)員看完會(huì)員看完3張張DVD之后，只需要將之后，只需要將DVD放進(jìn)網(wǎng)站提供的信封里寄回（郵費(fèi)由網(wǎng)站承擔(dān)），就可以繼續(xù)下次租放進(jìn)網(wǎng)站提供的信封里寄回（郵費(fèi)由網(wǎng)站承擔(dān)），就可以繼續(xù)下次租賃。請(qǐng)考慮以下問題：賃。請(qǐng)考慮以下問題：第71頁(yè)/共74頁(yè)2021-10-291) 1) 網(wǎng)站正準(zhǔn)備購(gòu)買一些新的網(wǎng)站正準(zhǔn)備購(gòu)買一些新的DVD，通過問卷調(diào)查通過問卷調(diào)查1000個(gè)會(huì)員，得到了愿意觀個(gè)會(huì)員，得到了愿意觀看這些看這些DVD的人數(shù)（表的人數(shù)（表1給出了其