水庫標的線性規劃問題與其對偶問題之解法

Abstract

本文以案例及圖表說明水庫標的線性規劃模式、對偶模式與原、偶二模式的關係。一個兼具蓄洪、供水與貯水三類服務功能的水庫，必須有足夠的容量，才能滿足各項預定需求，並假定各時期各功能服務的成本是供應量的片段線性函數。標的模式的對偶模式是提供替代服務的水庫同業訂定服務價格的問題：在水庫接受的條件下，如何決定價格參數使它提供的收益最高。 文中利用單純形法處理原始問題，用對偶單純形法求解水庫之對偶問題，原本求演算過程中的單位淨成本是針對切割各枝對其他弦的替換關係，在此轉而利用原、偶題間互補鬆弛條件的方法求得，經過比較更能增加演算效率。

A reservoir goal linear programming model, its dual model and the relations among the two are introduced with simple examples. 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 the minimum demands for each service item in each period. The profit for each service is a piecewise linear of the supply and their total profit from all service items is to be maximized or minimized. First, potential network simplex was offered to solve reservoir problem. Then, flow network dual simplex was used to solve the dual problem. The key concepts of the two models and their simplex network algorithms are itemized in tables and compared for the duality.