自對偶參數法在水庫標的線性規劃問題之應用

Abstract

本文考慮一個簡單的水庫標的線性規劃問題，這個水庫問題可以表示成一個位勢網絡的問題，另外水庫的對偶問題也可以用一個流量網絡問題來表達。標的模式考慮水庫的蓄洪、供水與貯水三類服務功能，並假定各時期各項服務功能的成本（收益）是供應量的片段線性函數。接著本文利用自對偶參數法，來處理具有網絡問題特性的原水庫問題及對偶問題。 文中採用網絡單純形法、對偶網絡單純形法及互補定理，來處理水庫問題及對偶問題。先利用自對偶參數法、網絡單純形法與對偶網絡單純形法，來處理原水庫問題。再利用互補定理，來處理水庫的對偶問題。

A reservoir goal linear programming model was formulated for a simple reservoir in this thesis. It can be treated as a potential network model. The dual model of potential network is a network flow problem. The three functional services of the reservoir considered are: reserved space for flood control, water supply, and pooling of water. The reservoir is to be operated to meet minimum demands for each service item in each period. The profit for each service item is a piecewise linear function of supply and the total profit is to be maximized. In this thesis, self-dual parametric algorithm were presented for solving the reservoir and its dual problems. The network simplex, network dual simplex, and complimentary theorem were used to solve reservoir and its dual problems. First, self-dual parametric algorithm, network simplex, and network dual simplex were offered to solve reservoir problem. Then, complimentary theorem were used to solve the dual problem.