CAJ | 학술논문

最小费用流问题在网络流问题中增加了费用方面的指标,从而使网络流问题扩展到在费用、容量网络中求最佳的流量配置,使总流量达到预定值（或最大值）条件下总费用最低,这在现实生活中起着重要的作用。在求解最小费用流问题时,通过研究流分解性质、最短路问题的最优条件、对偶线性规划的互补松弛性等,给出三种不同但等价的最优条件：负圈最优条件、减少费用最优条件和互补松弛最优条件,由这三种最优条件分别给出三种对应的算法。将这三个算法分别应用于一个煤矿应急物资储备运输问题,说明三种最优条件在解决专项问题时可以根据实际情况选用构造最合适的算法求解问题。
최소비용류문제재망락류문제중증가료비용방면적지표,종이사망락류문제확전도재비용、용량망락중구최가적류량배치,사총류량체도예정치（혹최대치）조건하총비용최저,저재현실생활중기착중요적작용。재구해최소비용류문제시,통과연구류분해성질、최단로문제적최우조건、대우선성규화적호보송이성등,급출삼충불동단등개적최우조건：부권최우조건、감소비용최우조건화호보송이최우조건,유저삼충최우조건분별급출삼충대응적산법。장저삼개산법분별응용우일개매광응급물자저비운수문제,설명삼충최우조건재해결전항문제시가이근거실제정황선용구조최합괄적산법구해문제。
The minimum cost flow problem adds the index of cost to expand the network flow problem to new field,where both of cost and capacity are researched,and both of fixed flow and minimum cost are desired.Thus,the minimum cost flow problem plays an important role in real life.When we solve this problem,nature of flow decomposition,optimality condition of shortest path problem and complementary slackness of dual linear programming will be researched.And,there are three different but equivalent optimal conditions,such as negative cycle optimality condition,reduced cost optimality condition and complementary slackness optimality condition.Also they can obtain three different but equivalent algorithms.At last,there is a case which is about coal mines emergency reserve transportation,and illuminates that how to use these optimality conditions after minimum cost flow problem reduction.In a word,the three optimality conditions can be used to build suitable algorithms to solve special problems according to the actual situation.