《线性规划课程设计》由会员分享，可在线阅读，更多相关《线性规划课程设计（15页珍藏版）》请在金锄头文库上搜索。
1、摘要摘要线性规划为运筹学一个重要分支,是辅助人们进行科学管理的一种数学方法。旨在解决经济管理、交通运输、工农业生产等经济活动中有关最优问题。即在一定条件下，通过合理安排人力物力等资源，使经济效益达到最好。基本概念有：可行解（满足线性约束条件的解） 、可行域（由所有可行解组成的集合） 、决策变量、约束条件、目标函数。线性规划最早是由法国数学家 J.- B.- J.傅里叶和 C.瓦莱普森分别于 1832 和1911 年独立地提出线性规划的想法，在 1947 年美国数学家 G.B.丹齐克提出线性规划的一般数学模型和求解线性规划 问题的通用方法单纯形法，为这门学科奠定了基础。其后许多学者对线性规划进行
2、大量的理论研究，伴随着计算机的出现，众多新的算法得以大量普及应用 。指派问题是一类重要的整数规划问题，从而也是线性规划问题的一个分支。关键词：最优化、线性规划、整数规划、指派问题AbstractLinear programming operations research an important branch of supporting people, a mathematical method of scientific management. Designed to solve the optimization problem in economic management, transpo
3、rtation, industrial and agricultural production and other economic activities. Under certain conditions, by reasonable arrangements for human and material resources so that economic benefits reach the best. The basic concept: a feasible solution (satisfying the conditions for the solution of linear
4、constraints), the feasible region (the collection of all feasible solutions), decision variables, constraints and objective function.Linear programming was first in 1832 and 1911 respectively by the French mathematician J. - B. - J. Fourier and C. Valle - Simpson made independently of the linear pro
5、gramming idea, in 1947, American mathematician GB Danzig proposed a general mathematical model of linear programming and general method for solving linear programming problems simplex method, and laid the foundation for this discipline. Subsequently many scholars on the linear programming theory, al
6、ong with the emergence of computer, many new algorithms can be a large number of popular applications.Assignment problem is an important class of integer programming problem, and thus is also a branch of linear programming problem.Keywords:Keywords: Optimization, linear programming, integer programm
7、ing, assignment problem. 线性规划课程设计1目录目录第一章第一章 问题描述问题描述21.1 指派问题概述21.2 指派问题的数学模型2第二章第二章 求解算法求解算法42.1 匈牙利算法的基本原理42.2 匈牙利算法的步骤52.3 举例7第三章第三章 数值实验数值实验93.1 基于 Matlab 的数值实验103.2 基于 Lingo 的数值实验10总结总结参考文献参考文献线性规划课程设计2第一章 问题描述1.1 指派问题概述指派问题（assignment problem）:又称分配问题，是一种特殊的整数规划问题。描述如下：假定有 n 项不同的工作或任务，需要 n 个人去
8、完成（每人只完成一项任务） ，由于每人的能力、知识、经验等的不同，所以每人完成不同任务需要的时间或其他资源是不同的，问应如何分配使得总的效率为最高或消耗的资源为最少？1.2 指派问题的数学模型数学模型：设个 01 变量：2nijx，用表示第 i 个人完成第 j1,ij0ijijx 表示指派第个人虔诚第项任务，表示不指派第个人去完成第项工作ijc项工作所用的资源，称其为效率系数或价值系数，。因此有指派问题的数学模型;ijc表示指派问题的效率矩阵nnij i=1 j=111minZ=c;.(1)1,1,2., .1,1,2,.,01, ,1,2., ;.(4)ijnij jnij iijxxins
9、txjnxi jn ；（2）；. . . . . . (3)或(1)式表示完成全部 n 项工作所消耗的总资源最少，为目标函数式。线性规划课程设计3（2）式表示第 i 个人只能且必须完成一项工作， （3）式第 j 项工作指派一人去完成， （4）是决策变量只取 0 或 1 两个整数值。指派问题的实质是线性规划问题，是一类特殊的运输问题（决策变量的取值只取 0 或 1，离散型） ，可以用解运输问题的表上作业法求解指派问题，但通常用更有效的匈牙利法求解。解指派问题的匈牙利法是从这样一个明显事实出发的：如果效率矩阵的所有元素，而其中存在一组位于不同行不同列的 0 元素，则只要令对应ijc 0于这些 0
10、元素的位置的=1，其余的=0，则就是问题ijxijxnnij i=1 j=1Z=cijx的最有解。如效率矩阵：，令，即将第一项工作分配给01493 920023 23038 012140 112332441,1,1,1xxxx甲，第二项给丙，第三项给乙，第四项给丁。这时完成总工作用时最少。但问题是如何产生并寻找这组位于不同行不同列的 0 元素。匈牙利数学家 Konig 证明了其中的两个基本定理为上述问题奠定了基础。线性规划课程设计4第二章 求解算法2.1 匈牙利算法的基本原理定理 1：如果从指派问题的效率矩阵的每一行元素中分别ijc减去（或加上）一个常数，从每一列分别减去（或加上）一个常iu数
11、，得到一个新的效率矩阵，若其中，则的jvijbijijijbcuvijb最优解等价于的最优解。ijc证明：将从中得到的解代入指派问题数学模型的目标函ijb数式（1） ，有nnnnnnnnijijij i=1 j=1i=1 j=1i=1 j=11111i=1 j=111ccnnnnnnijijijijijiijjijijij ijjiijZb xcuv xxuxvxxuv 第一项是的解的目标函数值 Z，后面两项是常数，因而当达到最ijc小值时，相应的也达到最小值。nnij i=1 j=1Z=cijx定理 2：若效率矩阵 C 的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于
12、不同行不同列的“0”元素的最大个数。证明：已知矩阵中有若干 0 元素，设覆盖全部 0 元素最少需m 条直线，又设位于不同行不同列的 0 有 M 个。因覆盖 M 中的每一个 0 至少用一条直线，故有：mM。下证 Mm。假定覆盖所有 0 元素的 m 条直线有 r 行（用表示）c 列（用表示） ，m=r+c。显然每一行上至少存在一1,.rii1,.cjj线性规划课程设计5个不在列上的 0（否则就不要在此行上划线这与直线有 r 行矛1,.cjj盾） ，设某一行上这些不在列上的 0 元素下标集合1,.cjj，对行分别有集合。从这些集合10,.iilcSl cljj1,.rii12,.iiirSSS中任意
13、取 k 个（kr）其集合中的不同元素个数必不小于 k，否则这 k 行的直线可用少于 k 条列线代替，与 m 是覆盖 0 元素最少直线数的假定矛盾。由此在 r 条行线上存在不少于 r 个位于不同列的0，且这些 0 不位于列上。同理可证在 c 列上存在不少于 c 个1,.cjj位于不同行的 0，且这些 0 不位于行上。1,.rii若上述两部分 0 的个数总和为 S，则 Sm，又显然 SM，故有 Mm。综上的 M=m。2.2 匈牙利算法的步骤：1：变换效率矩阵，把各行元素分别减去本行元素的最小值,然后在此基础上,再把每列元素减去本列中的最小值.2： 用圈 0 法求出变换后矩阵中的独立 0 元素。(1
14、)进行行检验:对变换后矩阵进行逐行检查，对每行只有一个未标记的 0 元素时用记号将该 0 元素圈起，然后将被圈起的 0 元素所在列的其他未标记的 0 元素用记号划去。重复行检验，直到每一行都没有未被标记的 0 元素或至少有两个未被标记的 0 元素为止。(2)进行列检验:线性规划课程设计6与进行逐行检查类似，对进行了行检验的矩阵逐列进行检验，对每列只有一个未标记的 0 元素时用记号将该 0 元素圈起，然后将被圈起的 0 元素所在行的其他未标记的 0 元素用记号 X 划去。重复列检验，直到每一列都没有未被标记的 0 元素或至少有两个未被标记的 0 元素为止。这时可能出现 3 中情形：每一行均有圈 0 出现，圈 0 的个数 m 恰好等于 n。存在未被标记过的 0 元素，但它们所在的行和列中，为被标记过的 0 元素均至少有 2 个。不存在未被标记的 0 元素，但圈 0 的个数 mn。(3)进行试指派；若情况出现，则可进行行指派：令圈 0 位置的决策变量取值ijx为 1，其他的取值为 0，得到一个最优指派方案，结束。若情况出现，则再对每行、每列中有两个未被标记的 0 元素任选一个，加上标记。然后给同列、同行的其他未被标记的 0 元素加标记。然后再进行行、列检验，可能出现情况或，出现则按上述得到一最优指派方案，结束。若情况出现，进入第四步。（4）作最少直线覆
