运筹学课程设计

1、 课程设计 学院：理学院 班级：数学与应用数学1101班 姓名：邹荣 学号：运筹学课程设计摘要随着经济的不断发展及运筹学自身的渐趋完善，运筹学模型再经济领域中得到了越来越多广泛的应用，在现代经济管理中起着重要的作用。资源是人们进行生产活动从事生产经营的基础，然而资源总是具有经济性和稀缺性的，这就决定了资源的合理利用、科学分配有着极其重要的现实意义。因此，在生产和经营等管理工作中，就需要经常进行计划和规划。本文通过建立线性规划模型解决了企业在有限资源的条件下使预期目标达到最优的问题。线性规划问题是运筹学一个重要的分支，广泛应用于军事作战、经营管理、经济分析和工程技术等方面，为合理的利用有限的人力

2、、物力和财力提供了科学的依据，有效地解决了如何利用现有的有限的资源，最大限度的发挥资源的能力，产生最优的效果这一问题。本论文主要以公司制造商品的有限资源为约束条件，以公司获取最大利润为目标函数，建立了线性规划模型，由单纯形法求解，并通过C语言编程求出最优解。关键词：线性规划 目标最优 C语言 约束条件 单纯形法一、问题的提出 在生产过程、科学实验以及日常生活中，人们总希望用最少的人力、物力、财力和时间去办更多的事，活得最大的效益，在管理学中被看作是生产者的利润最大化和消费者的效用最大化，如果从数学的角度来看就被看作是“最优化问题”。在最优化的研究生教学中我们所说的最优化问题一般是在某些特定的“

3、约束条件”下寻找某个“目标函数”的最大(或最小)值，其解法称为最优化方法。线性规划方法是最优化方法中的一个重要部分。美佳公司计划制造甲、乙两种家电产品。已知各制造一件时分别占用设备A、设备B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如下表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。项目甲乙 每天可用能力设备A/h0515设备B/h6224调试工序/h115利润/元21二、问题分析 根据题意可知该问题是典型的最优化问题，题中以公司两种设备以及调试工序每天的可用能力为限制，要求在此限制下使公司获得最大的利润，故我们可以以限制条件为约束条件，以最大利润为

4、目标函数建立线性规划模型对该问题进行求解。三、符号说明：生产家电甲的件数：生产家电乙的件数 ：公司所获得的利润四、模型的建立 1目标函数的建立已知生产甲、乙两种家电每件公司所获得的利润分别为2元、1元，那么生产甲、乙产品各、，公司所获得最大利润为 2约束条件的建立（1）、设备A分别用于甲、乙两产品每天可用能力的限制 （2）、设备B分别用于甲、乙两产品每天可用能力的限制 （3）调试工序每天用于甲、乙两产品的每天可用能力的限制 而且由于实际条件的限制，有，那么综上所述，可得线性规划模型为：s.t 五、模型的求解1、该线性规划问题可利用单纯形法求解，已知单纯形算法的基本步骤如下： Step1.首先将

5、一般形式的线性规划问题化为标准形式（这里是目标函数求极小）的线性规划问题，即形如 Step2. 求初始基可行解，列出初始单纯形表。Step3. 设初始基为B,然后执行如下步骤： (1).解,求得，令 ，计算目标函数值,(2).计算单纯形乘子W, ,得到,对于非基变量，计算判别数,可直接计算令 ,R为非基变量集合若判别数,则得到一个最优基本可行解，运算结束；否则，转到下一步(3).解,得到；若,即的每个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤(4).确定下标r,使为换出变量，为换入变量，用代替得到新的基矩阵B，返回步骤（1）.2.将问题中的线性规划模型转化为如上所示的标准形

6、式： s.t 3.对于上述标准线性规划问题利用单纯形算法，用C语言编程求解，（主要程序见附录）程序运行结果具体如下：六、结论与改进 由以上结果可知当生产产品甲3.5件，产品乙1.5件时公司获得利润最大为8.5元。通过对该问题的求解，不仅锻炼了自己的编程能力，也让我对单纯形算法有了更进一步的认识。我们发现单纯形法要求已知一个基本可行解，且线性规划需为标准形式，而在一般情况下，线性规划并无明显的可行解，如用两阶段法获得可行解，必须增加人工变量，从而增加了计算量。所以针对这一问题，我们还可以尝试新的改进的单纯形法，用简单的计算求出基可行解，并剔除多余的约束，判断问题是否有解，同时将线性规划的约束方程

7、化为标准型，以达到减少比较次数，简单易行，容易在计算机上实现的目的。七、参考文献1胡运权，等.运筹学教程.第4版.北京：清华大学出版社，2012.112刘焕彬，库在强，廖小勇等.数学模型与实验【M】.北京：科学出版社，20083韩中庚.实用运筹学【M】.北京：清华大学出版社，20074朱德通.最优化模型与实验【M】.上海：同济大学出版社，2003附录：#include #include #define m 3 /*定义约束条件方程组的个数*/#define n 5 /*定义未知量的个数*/ float M=.0; float Amn; /*用于记录方程组的数目和系数;*/ float Cn;

8、/*用于存储目标函数中各个变量的系数*/ float bm; /*用于存储常约束条件中的常数*/ float CBm; /*用于存储基变量的系数*/ float setam; /*存放出基与入基的变化情况*/ float deltan; /*存储检验数矩阵*/ float xn; int numm; /*用于存放出基与进基变量的情况*/ float ZB=0; /*记录目标函数值*/ void input(); void print(); int danchunxing1(); int danchunxing2(int a); void danchunxing3(int a,int b); i

9、nt danchunxing1() int i,k=0; int flag=0; float min=0; for(i=0;i=0) flag=1; else flag=0;break; if(flag=1) return -1; for(i=0;ideltai) min=deltai;k=i; return k; int danchunxing2(int a) int i,k,j; int flag=0; float min; k=a; for(i=0;im;i+) if(Aik=0) flag=1; else flag=0;break; if(flag=1) printf(n该线性规划无最

10、优解!n); return -1; for(i=0;i0) setai=bi/Aik; else setai=M; min=M; for(i=0;i=setai) min=setai;j=i; numj=k+1; CBj=Ck; return j; void danchunxing3(int p,int q) int i,j,c,l; float temp1,temp2,temp3; c=p; /*行号*/ l=q; /*列号*/ temp1=Acl; bc=bc/temp1; for(j=0;jn;j+) Acj=Acj/temp1; for(i=0;im;i+) if(i!=c) if(A

11、il!=0) temp2=Ail; bi=bi-bc*temp2; for(j=0;jn;j+) Aij=Aij-Acj*temp2; temp3=deltal; for(i=0;in;i+) deltai=deltai-Aci*temp3; void print() int i,j=0; printf(n-n); for(i=0;im;i+) printf(%8.2ftX(%d) %8.2f ,CBi,numi,bi); for(j=0;jn;j+) printf(%8.2f ,Aij); printf(n); printf(n-n); printf(ttt); for(i=0;in;i+)

12、 printf( %8.2f,deltai); printf(n-n); void input() int i,j; /*循环变量*/ int k; printf(请输入方程组的系数矩阵A(%d行%d列):n,m,n); for(i=0;im;i+) for(j=0;jn;j+) scanf(%f,&Aij); printf(n请输入初始基变量的数字代码num矩阵:n); for(i=0;im;i+) scanf(%d,&numi); printf(n请输入方程组右边的值矩阵b:n); for(i=0;im;i+) scanf(%f,&bi); printf(n请输入目标函数各个变量的系数所构

13、成的系数阵C:n); for(i=0;in;i+) scanf(%f,&Ci); for(i=0;in;i+) deltai=Ci; for(i=0;im;i+) k=numi-1; CBi=Ck; void main() int i,j=0; int p,q,temp; input(); printf(n-n); printf( tCBtXBtbt); for(i=0;in;i+) printf( X(%d)t,i+1); for(i=0;in;i+) xi=0; printf(n); while(1) q=danchunxing1(); if(q=-1) print(); printf(n所得解已经是最优解!n); printf(n最优解为n);