高分求 matlab 对偶单纯形法 程序 ，

刚好我也做了这个，给你参考哈

function x=lindual(c,A,b)

[n1,n2]=size(A);

A=[A,eye(n1)];c=[-c,zeros(1,n1)];

x1=[zeros(1,n2),b'];lk=[n2+1:n1+n2];

while(1)

x=x1(1:n2);

s1=[lk',b,A]

c

x1

cc=[];ci=[];

for i=1:n1

if b(i)<0

cc=[cc,b(i)];

ci=[ci,i];

end

end

nc=length(cc);

if nc==0

fprintf('达到最优解');

break

end

cliu=cc(1);

cl=ci(1);

for j=1:nc

if abs(cc(j))>abs(cliu)

cliu=cc(j);

cl=j;

end

end

cc1=[];ci1=[];

for i=1:n1+n2

if A(cl,i)<0

cc1=[cc1,A(cl,i)];

ci1=[ci1,i];

end

end

nc1=length(cc1);

if nc1==0

fprintf('无可行解');

break

end

cliu=c(ci1(1))/cc1(1);

cl1=ci1(1);

for j=1:nc1

if c(ci1(j))/cc1(j)<cliu

cliu=c(ci1(j))/cc1(j);

cl1=ci1(j);

end

end

b(cl)=b(cl)/A(cl,cl1);

A(cl,:)=A(cl,:)/A(cl,cl1);

for k=1:n1

if k~=cl

b(k)=b(k)-b(cl)A(k,cl1);

A(k,:)=A(k,:)-A(cl,:)A(k,cl1);

end

end

c=c-c(cl1)A(cl,:);

x1(lk(cl))=0;

lk(cl)=cl1;

for kk=1:n1

x1(lk(kk))=b(kk);

end

x=x1(1:n2);

end

验证p62运筹学

min ω=2x1+3x2+4x3

x1+2x2+x3≥3

2x1-x2+3x3≥4

x1，x2，x3≥0

检验

format rat

c=[2 3 4];A=[-1 -2 -1;-2 1 -3];b=[-3;-4];

x=lindual(c,A,b)

单纯形法

simplex method

求解线性规划问题的通用方法。单纯形是美国数学家GB丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。

最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。

单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。

改进单纯形法

原单纯形法不是很经济的算法。1953年美国数学家GB丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。

对偶单纯形法

1954年美国数学家C莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。

数学优化中，由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现（1965年），这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。

这二者都使用了单纯形的概念，它是N维中的N + 1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。

Cb就是目标方程中的相对应得c,如70是maxZ中X1前面的系数，30是maxZ中X2的系数．B-1是对应的可行基B的逆矩阵．aj就是对应约束方程中的系数。

单纯形法是求解线性规划问题最常用、最有效的算法之一。单纯形法最早由George Dantzig于1947年提出，近70年来，虽有许多变形体已经开发，但却保持着同样的基本观念。如果线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。

基于此，单纯形法的基本思路是：先找出可行域的一个顶点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如此下去，直到找到某最优解为止。

基本单纯形法：

单纯形法的基本想法是从线性规划可行集的某一个顶点出发，沿着使目标函数值下降的方向寻求下一个顶点，面顶点个数是有限的，所以，只要这个线性规划有最优解，那么通过有限步迭代后，必可求出最优解。

为了用迭代法求出线性规划的最优解，需要解决以下三个问题：

1最优解判别准则，即迭代终止的判别标准。

2换基运算，即从一个基可行解迭代出另一个基可行解的方法。

3进基列的选择，即选择合适的列以进行换基运算，可以使目标函数值有较大下降。

这个用到库的问题(是matlab库)

开头:

#include mexh/这个matlab自己的也是必须的/

库函数(4个参数)//名字忘了太长了

{

//自己的程序;

}

解释:

matiab 的核心有pascal 到c

有了了很大的改进;不仅支持c /java等

我只用着2个;其他没有用过;c++也支持;

自己查查函数手册;旧知道了

增加以下:哪个函数为MexFuction(4参数)

{

//自己的代码

}

%单纯形法matlab程序-ssimplex

% 求解标准型线性规划:min c'x; st Ax=b; x>=0

%本函数中的A是单纯初始表，包括:最后一行是初始的检验数，最后一列是资源向量b

% N是初始的基变量的下标

% 输出变量minx是最优解, 其中松弛变量（或剩余变量）可能不为0

% 输出变量minf是最优目标值，k是迭代次数

function [minx,minf,k]=ssimplex(A,N)

[mA,nA]=size(A);

k=0; % 迭代次数

flag=1;

while flag

k=k+1;

if A(mA,:)>=0 % 已找到最优解

flag=0;

minx=zeros(1,nA-1);

for i=1:mA-1

minx(N(i))=A(i,nA);

end

minf=-A(mA,nA);

else

for i=1:nA-1

if A(mA,i)>0&A(1:mA-1,i)<=0 % 问题有无界解

disp('have infinite solution!');

flag=0;

break;

end

end

if flag % 还不是最优表，进行转轴运算

temp=0;

for i=1:nA-1

if A(mA,i)<temp

temp=A(mA,i);

inb=i; % 进基变量的下标

end

end

sita=zeros(1,mA-1);

for i=1:mA-1

if A(i,inb)>0

sita(i)=A(i,nA)/A(i,inb);

end

end

temp=inf;

for i=1:mA-1

if sita(i)>0&sita(i)<temp

temp=sita(i);

outb=i; % 出基变量下标

end

end

% 以下更新N

for i=1:mA-1

if i==outb

N(i)=inb;

end

end

% 以下进行转轴运算

A(outb,:)=A(outb,:)/A(outb,inb);

for i=1:mA

if i~=outb

A(i,:)=A(i,:)-A(outb,:)A(i,inb);

end

end

end

end

end

以上就是关于高分求 matlab 对偶单纯形法 程序 ，全部的内容，包括:高分求 matlab 对偶单纯形法 程序 ，、单纯形法的基本求法和思想、单纯形法cb是啥等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！