文件列表:

linearprogram_src (0, 2007-10-31)
linearprogram_src\About.cpp (3389, 2001-05-24)
linearprogram_src\About.dfm (7923, 2001-05-24)
linearprogram_src\About.h (1866, 2001-05-24)
linearprogram_src\common.ini (410, 2001-05-22)
linearprogram_src\demo.ini (436, 2001-05-23)
linearprogram_src\free.ini (368, 2001-05-24)
linearprogram_src\global.cpp (3260, 2001-05-07)
linearprogram_src\global.h (856, 2001-05-05)
linearprogram_src\help.txt (2345, 2001-05-27)
linearprogram_src\lp_doc.txt (8549, 2005-03-14)
linearprogram_src\Main.cpp (12463, 2001-05-24)
linearprogram_src\Main.dfm (16222, 2001-05-22)
linearprogram_src\Main.h (3583, 2001-05-22)
linearprogram_src\Matrix.cpp (220, 2001-04-30)
linearprogram_src\Matrix.h (13715, 2001-05-22)
linearprogram_src\MatrixOp.cpp (8532, 2001-05-05)
linearprogram_src\MatrixOp.dfm (2970, 2001-05-08)
linearprogram_src\MatrixOp.h (1985, 2001-05-05)
linearprogram_src\MatrixOp_Assign.cpp (1625, 2001-05-05)
linearprogram_src\MatrixOp_Assign.dfm (5284, 2001-05-08)
linearprogram_src\MatrixOp_Assign.h (1093, 2001-05-03)
linearprogram_src\MatrixOp_Tranfer.cpp (3112, 2001-05-05)
linearprogram_src\MatrixOp_Tranfer.dfm (8278, 2001-05-08)
linearprogram_src\MatrixOp_Tranfer.h (1733, 2001-05-04)
linearprogram_src\reset.cpp (1856, 2001-05-03)
linearprogram_src\reset.dfm (4880, 2001-05-08)
linearprogram_src\reset.h (1093, 2001-05-03)
linearprogram_src\rule.ini (296, 2001-05-22)
linearprogram_src\solve_mGD.cpp (544, 2001-05-03)
linearprogram_src\solve_mGD.dfm (3719, 2001-05-05)
linearprogram_src\solve_mGD.h (1315, 2001-05-04)
linearprogram_src\TDcxQ.cpp (246, 2001-05-22)
linearprogram_src\TDcxQ.h (8304, 2001-05-24)
linearprogram_src\TList.cpp (520, 2001-05-06)
linearprogram_src\TList.h (10364, 2001-05-08)
linearprogram_src\TValue.cpp (247, 2001-05-07)
linearprogram_src\TValue.h (3928, 2001-05-07)
linearprogram_src\Vector.cpp (220, 2001-05-01)
... ...

关于一个求解线性规划问题的程序(有源代码) 这是一个老师布置的作业程序,我是用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

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：