線性規劃標準型和整數線性規劃最優解的兩個注記

孟香惠,施保昌,胡新生

(1.深圳廣播電視大學學習中心,廣東 深圳518001;2.華中科技大學數學與統計學院,湖北 武漢430074;3.深圳廣播電視大學教育技術中心,廣東 深圳518001)

1.引言

線性規劃是運籌學、決策科學和管理科學最重要的基礎,現已成為人們合理利用、調配有限資源做出最佳決策的有力工具[1?3].除了生產計劃安排和運輸問題等經典的應用領域,因其算法簡單、高效,適于處理大規?？茖W與工程問題,線性規劃還在現今的機器學習等熱點研究領域發揮著重要作用[4?5].線性規劃的基本算法: 單純形法可以被看成是線性方程組的消去法的變形或推廣形式,它以其簡單、通用及應用廣泛等特性而著稱于世.在線性規劃的實際應用中,如生產計劃安排、物資運輸與調度、工作指派等對應的線性規劃問題中,其所涉及的全部或部分決策變量往往有整數性的要求,這就得到了所謂整數線性規劃問題[6?7].整數性要求使得常用的解析方法不便用于整數規劃問題,因而整數規劃的分析和求解更為困難[6].結合松弛法的思想,單純形法和對偶單純形法等線性規劃算法可以用于變量有整數性要求的整數線性規劃問題,從而進一步擴展了線性規劃的應用范圍.

我們知道,單純形法是基于線性規劃標準型的.通常,在有關線性規劃的教科書和參考文獻里介紹標準型時,都會“不失一般性”地對其作些假設,如“約束系數矩陣行滿秩”.另外,談到整數線性規劃時,又……