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

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

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

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

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