關于一個求解線性規劃問題的程序(有源代碼)

    這是一個老師布置的作業程序,我是用C++ Builder 4.0寫的. 如果學過<線性規劃>的話,這個程序要干什么大家都知道,就是求解線性規劃問題,即在一組線性不等式或等式組的約束條件下求某個線性函數的最值問題.關于線性規劃問題應用的重要性應該不是在這里說的,不過據說現代計算機的60%的計算能力都花在了求解線性規劃問題上.下面只是舉一道具體的題目給大家看看:

線性函數為:     min(z) = -20*x1 - 10*x2 - 3*x3
約束條件為:   3*x1 - 3*x2 + 5*x3      <= 50
              x1          + x3        <= 10
              x1   - x2   + 4*x3 + x4  = 20 
              x1>=0,x2>=0,x3>=0,x4>=0

    由于最值肯定是在約束條件所確定范圍的邊界上達到的,所以拉格朗日求最值的方法在這里是不適用的.而我們的一門課<線性規劃>講的就是怎么來解這一類問題(特別是用計算機求解,具體應用通常的變量有150個左右).
    由于我們都上過課,算法大家都會,即單純型法,而且同學們都做過不少作業還考了試我想對算法都是爛熟于胸的.所以我覺得評價這個程序時,算法反而不應占很大的比重,也就是說每個同學的程序能達到的功能別人也是可以達到的(除非能創造性地修改單存型表的算法).比如說有化規范型、能求最大值和最小值、可有自由變量、能輸出任何中間的結果、遇到不能整除時有很高的精確度等等。我覺得重要的是怎么把算法實現，以及實現了多少. 以上列舉的功能看起來簡單誰都會，但是真正實現其中的任何一項也不是一件很容易的事情。我想單純型法本身想起來也不會難吧，同學們都實現了它，感覺怎么樣，不是很容易吧？為了能寫的更好一點，反正我自己感覺是不是一件簡單的事情，起碼是有點煩的事情。


    每次寫程序的時候,大概是想一寫就寫得完美一些,于是看上去一些很簡單的程序,大部分時間往往都是在想如何設計才能得到比較好的結構(特別是在比較多用到數據結構和算法的程序),才能比較容易看懂、容易維護、方便重用，才能有比較快的執行速度，而這些都是面向對象程序設計的特點和要求。即使整體結構和算法都設計好了，或者說根本不用多少算法，但還是要為了界面的美觀友好方便而仔細修飾。有時為了這些簡直想爆頭了或者說煩死了。一個程序想要真正能拿出來見人和寫著玩是相差很遠的，雖然看上去不怎么樣，不信你寫一個象樣的程序給大家看看試試。所以每次寫程序都要花上不少的時間和精力，而有時還有其他事比如是要考試的時候,不免會因沒有去讀書或者說沒有心思讀書而內疚。有些程序就因此而不得不宣布放棄了(比如前一段時間寫過一個“五子棋”的小游戲，用的是有界深度優先a-b剪枝算法,就是因為花多了一點時間而暫時放棄了)。只能等到“有時間”的時候再繼續寫吧。

    寫這個程序的時候也是這樣，為了使結構自然一點，常常仔細斟酌代碼的好壞，而且把程序寫得越來越大。現在回想起來，我想我當時應該是這樣想的：
   1.考慮到程序會涉及到不少矩陣運算，首先想到的是要寫一個矩陣類TMatrix，從而又引出了一個向量類TCVector(至于矩陣要做什么運算就不用多說了吧)。而且也為了用分數作為矩陣的元素預留了空間。為了加快速度，避免取元素時的地址乘法運算，還采用了一維數組來存儲矩陣。而且想到向量也就是一種特殊的矩陣，于是就從矩陣繼承了下來。結果發現這樣用起來不是很好，有些地方挺別扭的。現在想來最好還是把矩陣和向量分開來寫。
   2.因為修正單純型表本身有自己的屬性(逆陣U,基解正分量Bx,最優值z0,對偶問題的解y)和方法(確定樞行樞列樞元素，換基，取得基解、最優值等)，而且要保存中間結果時會重復用到，所以寫了一個修正單純型表類(TxzDcx)。
   3.對每一個具體的線性規劃問題，如一般型、規范型、輔助問題，也有自己的屬性(系數矩陣、條件向量、費用向量等)和方法(化成規范型，求輔助問題，重置維數等)。而且考慮到構造初始基可行解的時候要傳原問題的許多參數，于是就寫了一個線性規劃問題類(TDcxQuestion)。
   4.為了統一第一階段和第二階段的算法，也為了使結構清晰，使算法和輸入輸出界面分離，于是寫了一個單純型表算法通道(TxzDcxChannel)。使得只要傳進規范型線性規劃問題(包括了初始基可行解)就可以取得結果數據。為了更自然方便，其中考慮了許多怎么傳數據和怎么拿數據的方式。對于這個通道也是考慮的最多的，其實現在看來做的還不是很好。
   5.為了保存每一次換基的中間結果，用了一個模板鏈表類(KTList),鏈表節點存的是修正單純型表的指針(TxzDcx*)。這樣就可以用它方便地拿到任一次換基的中間結果。
   6.最后，為了運算的精確性，還寫了一個分數類(TValue)作為矩陣類(TMatrix)的元素。當然其中也考慮到了分數和字符串、整數等的運算。  
   7.剩下的就是做輸入輸出界面了。所有程序運行看得到的東西都是在這一步才開始做的。
   
   結果寫出的程序現在重新看來整個結構還是比較滿意的。現在如果要進行擴充和修改功能的話都比較方便，比較好地實現了代碼的可理解性、可重用性、可擴充性。 算法和輸入輸出界面分離的比較好，以至還用相同的“內核”做出了一個dos下的界面，而且也一樣把算法用的很方便。
   
   但是，不知道是不是對c的指針的好奇還是以為c的指針靈活效率高或者是受CBuilder本身的影響(CBuilder本身幾乎所有的變量都是用指針定義的)的原因，程序中大量使用了指針(有的地方還用了指針的指針)，現在看來簡直有點泛濫的感覺(大家看一看程序就知道了)。這樣一來，往往就會出現意想不到的而且又異常關鍵的錯誤，比如內存釋放和指錯對象的錯誤，大大增加了調試程序的困難。而且有些地方用起來沒有起到清晰自然靈活的效果，反而會有點別扭。比如矩陣的指針的使用。所以如果程序要改的話我想我會改少用一點指針。
    對很多變量，特別是指針變量的定義我一直也有一個問題。就是當變量有多個窗口用到的時候，這個變量究竟放到哪里定義才比較好一點，在哪里初始化比較好一點，把它當作窗口的成員變量時初始化和傳遞數據都比較麻煩，而把它當作全局變量時又怕和別的全局變量沖突，而且數據不安全、聯系緊密。比如說各種線性規劃問題和算法通道的變量的定義。當時我是把它們以指針變量的形式當成主窗口的成員變量。現在想來可能還是把它們放到全局變量區把它們而且不以指針變量的形式定義比較好一點。
    還有一點就是我擔心由于太注重結構而會忽略了執行速度。因為這個程序對速度要求還是挺高的，實際上通常的一個問題都要用一臺計算機連續求解兩三天。比如使用分數，每進行一次操作運算都要多調用n個函數。對于矩陣等其他的類也是，執行速度可能沒有基本的二維數組快。有一點點懷疑我當時想的那么多有關結構的東西是否必要。


    我只有一部舊的電腦.有時不得不在這部機上寫windows下程序的時候,真可以說的上是奮斗。特別是用CBuilder4,每次編譯鏈接一個只有四五個文件的小小的程序都要花上半天的時間,如果只是一兩分鐘還是可以忍受的(通常的應該是幾秒到十幾秒吧),可是如果每一次,即使是小小改動看看有沒有語法錯誤的編譯都要花上三四分鐘的話,我想也是比較難以忍受的吧。所以現在盡管程序中還有問題，但也實在失去了調試的興致。(其中的一次256.28秒的編譯,讓我禁不住寫了這段話。)

   
    每次寫完一個程序，我都會有比較多的東西想寫出來。每當這個時候，我就會覺得自己曾經苦想的一個一個問題如今大都得到了比較好的解決，那種對問題的把握感和融會貫通的感覺還是挺不錯的。


    又一次覺得寫一個好的程序其實要明白許多東西的。比如說：
    1.要明白程序運行的操作系統幫你干了哪些事情，也就是要明白操作系統提供的程序一級的接口。比如說在windows下，構造一個窗口或者控鍵通常是讓操作系統幫你Create的,因為操作系統幫你Create的窗口或者控鍵有很多自己默認的功能，比如說接收鼠標鍵盤消息、拖動窗口、改變窗口大小、控鍵外觀、處理消息的默認方式(edit框可以輸入文字，下拉框可以下拉選擇等)等等。除了界面之外操作系統往往還有一些其他的比如說網絡通訊的接口、讀寫一些硬件(如內存、磁盤、顯卡)的接口。如果寫windows下的程序不借助windows的話，當然也是可以的，但那就根本說不上是windows下的程序了。可能有些同學只會用Turboc而還沒學windows下的編程,可能轉向windows下編程時就會感到很不適應。其實這也就是不明白windows提供的程序一級的接口而導致的，而在dos下還可以不用多少dos操作系統提供的接口。
    2.要明白編譯鏈接程序干了些什么事情。說來也是簡單，編譯鏈接程序就是把你的源代碼轉換成在某個操作系統下的可執行文件代碼。所以不論用什么語言，所產生的可執行文件代碼的格式肯定是一樣的，即都是操作系統能讀懂的。如果能明白自己所寫的某一個變量的名字、類型、位置和某一行語句最終會變成怎么樣的二進制數字，我想會能明白更多東西，比如說某種編程語言(如c、pascal)的很多機制，而且容易明白所有語言都是共通的。如果學過匯編語言和編譯原理的話，我想是有比較大的幫助的。
    3.要明白編程工具和軟件包幫你干了哪些事情。在windows下寫程序，往往會用到一些編程工具，比如Visual C++,Visual Basic,Delphi,C++Builder等，有時可以說學編程就是學這些工具。學怎么用它們，它們干了哪些事情。其實編程工具真是干了不少事情，包括幫你調用操作系統的接口，編譯鏈接程序。但最主要的我想還是里面提供的類庫，如VC的MFC,Delphi的VCL,熟悉了這些類庫，也就熟悉了編寫程序。
    4.寫一個程序或者代碼(如函數、類庫)還要明白用戶想要干什么事情、應該干什么事情。我想這會隨著程序的擴大而顯得越來越重要而且與越來越難理清。程序做得好不好就看用戶用的舒不舒服了。其實對于很多程序，真正花時間精力的都是花在這方面，至于算法和代碼反而沒有那么重要了。而且有很多時候用戶也不明白自己需要什么東西，這就需要程序設計人員盡可能地為用戶多想點東西了。如果不首先弄清楚你寫的東西是為了什么，那我想會寫不出什么好程序的。
    5.明白了以上幾點以后，剩下的就應該能明白自己究竟要干什么了吧。明白了自己要干的事情，我想肯定會寫得順手很多。當然如果多人合作的話，就更要明白自己的職責了。


    這個程序<線性規劃>的老師還評了獎,結果這個程序拿了全班第一名.反正當時開始做的時候就想好好做,也有拿第一名的愿望.


                                                          kk.h
                                                      2001-5-23