生產(chǎn)網(wǎng)絡(luò)流最小費(fèi)用問(wèn)題.pdf

1、網(wǎng)絡(luò)流模型在實(shí)際生產(chǎn)中有及其廣泛的應(yīng)用，但普通的網(wǎng)絡(luò)流模型在描述更加復(fù)雜的生產(chǎn)過(guò)程時(shí)有其局限性，比如由幾種不同的原料生產(chǎn)出一種產(chǎn)品或由一種原料提煉出幾種不同的產(chǎn)品．因此，F(xiàn)ang Shu—Cherng和Qi Liqun提出了稱為生產(chǎn)網(wǎng)絡(luò)流(簡(jiǎn)稱MNF)的廣義網(wǎng)絡(luò)流模型．在這個(gè)模型中，多種原料通過(guò)合成或提煉過(guò)程可以生產(chǎn)出多種產(chǎn)品．為了更恰當(dāng)?shù)孛枋龈鞣N生產(chǎn)過(guò)程，在生產(chǎn)網(wǎng)絡(luò)流模型中引入了六種不同結(jié)點(diǎn)：用來(lái)轉(zhuǎn)運(yùn)的普通點(diǎn)，用來(lái)提供原料的原點(diǎn)，用來(lái)

2、收集成品的終點(diǎn)，用來(lái)存儲(chǔ)加工中的原料或半成品的存貨點(diǎn)，用來(lái)進(jìn)行分配或提煉操作的分配點(diǎn)，用來(lái)進(jìn)行裝配或合成操作的裝配點(diǎn)．廣義生產(chǎn)網(wǎng)絡(luò)流的最優(yōu)化問(wèn)題包括最大流問(wèn)題和最小費(fèi)用流問(wèn)題．最小費(fèi)用流問(wèn)題是找一可行流使原料總費(fèi)用最小，其中給出每種產(chǎn)品的市場(chǎng)需求，以及每種原料的單位費(fèi)用．這兩類問(wèn)題都是帶有一般網(wǎng)絡(luò)流結(jié)構(gòu)的線性規(guī)劃問(wèn)題，但比經(jīng)典的網(wǎng)絡(luò)流問(wèn)題復(fù)雜得多．由于生產(chǎn)網(wǎng)絡(luò)的復(fù)雜性，F(xiàn)ang Shu-Cherng和Qi Liqun提出了兩種簡(jiǎn)化的模型

3、，即分配網(wǎng)絡(luò)流模型和裝配網(wǎng)絡(luò)流模型，并著重研究了分配網(wǎng)絡(luò)流中的最小費(fèi)用問(wèn)題，在討論其基本結(jié)構(gòu)和對(duì)偶性質(zhì)的基礎(chǔ)上，概述了該問(wèn)題的網(wǎng)絡(luò)單純形法． 本文綜合了分配網(wǎng)絡(luò)流模型和裝配網(wǎng)絡(luò)流模型的特點(diǎn)，給出了生產(chǎn)網(wǎng)絡(luò)流模型，在這個(gè)模型中包括了分配點(diǎn)和裝配點(diǎn)．我們主要研究生產(chǎn)網(wǎng)絡(luò)最小費(fèi)用問(wèn)題．一個(gè)制造商把在源點(diǎn)獲得原料進(jìn)行分配和組裝，在終點(diǎn)得到成品．在這個(gè)過(guò)程中所用的費(fèi)用最?。畬?duì)于這個(gè)問(wèn)題，可以在研究該問(wèn)題的基本結(jié)構(gòu)及其對(duì)偶性質(zhì)的基礎(chǔ)上，給出

4、解決該問(wèn)題的網(wǎng)絡(luò)單純形法．在本論文中，介紹了生產(chǎn)網(wǎng)絡(luò)中涉及的六種點(diǎn)和它的基本模型及其線性規(guī)劃描述．其中限制C一點(diǎn)的流只能來(lái)源于普通點(diǎn)或D-點(diǎn)的一個(gè)分支，而D-點(diǎn)的流只能來(lái)源于普通點(diǎn)或D-點(diǎn)．介紹了生產(chǎn)網(wǎng)絡(luò)最小費(fèi)用問(wèn)題的基本可行圖．并說(shuō)明一個(gè)連通的生產(chǎn)網(wǎng)絡(luò)，其對(duì)應(yīng)于基本可行解的子圖也是連通的，這個(gè)子圖叫做基本可行圖．提出了計(jì)算原問(wèn)題基本可行解和對(duì)偶問(wèn)題基本解的算法．這兩個(gè)算法同普通網(wǎng)絡(luò)流問(wèn)題對(duì)應(yīng)的算法一樣有效．根據(jù)這兩個(gè)算法及一些最優(yōu)條件