单纯形法C语言程序.doc

单纯形法C语言程序 单纯形法是一种常用的线性规划算法，用于解决线性规划问题。该算法的主要思想是通过不断迭代，找到一个可行解，直到达到最优解。 在本实验中，我们使用C语言编写单纯形法计算程序，解决标准线性规划问题。该程序的主要步骤如下： 1. 求解一般标准线性规划问题的单纯形算法（修正）步骤 给定一个初始基本可行解，设初始基为B，然后执行如下步骤： （1）解，求得； （2）计算单纯形乘子w，得到，对于非基变量，计算判别数， 可直接计算令，R为非基变量集合若判别数，则得到一个最优基本可行解，运算结束；否则，转到下一步 （3）解，得到；若，即的每个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤（4） （4）确定下标r，使 2. 计算框图 开始 初始可行基 B 否 得到最优解否 不存在有限最优解确定下标 r，使得 2是是 3. 计算程序（Matlab） A=input('A=');b=input('b=');c=input('c=');format rat %可以让结果用分数输出 [m,n]=size(A);E=1:m;E=E'; F=n-m+1:n;F=F';D=[E,F]; %创建一个一一映射，为了结果能够标准输出 X=zeros(1,n); %初始化X if(n<m) %判断是否为标准型 fprintf('不符合要求需引入松弛变量') flag=0; else flag=1; B=A(:,n-m+1:n); %找基矩阵 cB=c(n-m+1:n); %基矩阵对应目标值的c while flag w=cB/B; %计算单纯形乘子，cB/B=cB*inv(B)，用cB/B的目的是，为了提高运行速度。 panbieshu=w*A-c %计算判别数，后面没有加分号，就是为了计算后能够显示出来。 [z,k]=max(panbieshu); % k 作为进基变量下标。 fprintf('b''./(B\\A(:,%d))为',k); b'./(B\A(:,k)) if(z<0.000000001) flag=0; %所有判别数都小于0时达到最优解。 fprintf(' 已找到最优解!\n'); xB=(B\b')'; f=cB*xB'; for i=1:n mark=0; for j=1:m if (D(j,2)==i) mark=1; X(i)=xB(D(j,1)); %利用D找出xB与X之间的关系。 end end if mark==0 X(i)=0; %如果D中没有X(i)，则X(i)为非基变量，所以X(i)＝0。 end end fprintf('基向量为:'); X fprintf('目标函数值为:') ; f else if(B\A(:,k)<=0) % 如果B\A(;,k)中的每一个分量都小于零。 flag=0; fprintf(' \n 此问题') end end end end 该程序的主要功能是使用单纯形法解决标准线性规划问题，通过迭代计算，找到一个可行解，直到达到最优解。同时，该程序也可以判断问题是否存在有限最优解。 单纯形法的优点是，该算法可以解决大规模线性规划问题，且具有高效的计算速度和良好的稳定性。但是，该算法也存在一些缺点，例如，需要大量的计算资源和存储空间，且在某些情况下，可能会出现迭代不收敛的情况。 本实验的单纯形法C语言程序可以作为解决标准线性规划问题的一种有效方法，具有良好的计算性能和稳定性。但是，在实际应用中，需要根据具体情况选择合适的算法和编程语言。