线性规划单纯形法matlab解法
线性规划单纯形法matlab解法
%单纯形法matlab程序-ssimplex
% 求解标准型线性规划:max c*x; s.t. A*x=b; x>=0
% 本函数中的A是单纯初始表，包括:最后一行是初始的检验数，最后一列是资源向量b
% N是初始的基变量的下标
% 输出变量sol是最优解, 其中松弛变量（或剩余变量）可能不为0
% 输出变量val是最优目标值，kk是迭代次数
% 例：max 2*x1+3*x2
% s.t. x1+2*x2<=8
% 4*x1<=16
% 4*x2<=12
% x1,x2>=0
% 加入松驰变量，化为标准型，得到
% A=[1 2 1 0 0 8;
% 4 0 0 1 0 16;
% 0 4 0 0 1 12;
% 2 3 0 0 0 0];
% N=[3 4 5];
% [sol,val,kk]=ssimplex(A,N)
% 然后执行 [sol,val,kk]=ssimplex(A,N)就可以了。
function [sol,val,kk]=ssimplex(A,N)
[mA,nA]=size(A);
kk=0; % 迭代次数
flag=1;
while flag
kk=kk+1;
if A(mA,:)<=0 % 已找到最优解
flag=0;
sol=zeros(1,nA-1);
for i=1:mA-1
sol(N(i))=A(i,nA);
end
val=-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=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 循环语句的应用,提高编程的能力和技巧。 二、实验用仪器设备、器材或软件环境 Windows Xp 操作系统 ,Matlab6.5，计算机 三、算法 对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始 基本可行解。设初始基为B,然后执行如下步骤： (1).解B Bx b =,求得1 B x B b -=，0,N B B x f c x ==令计算目标函数值 1(1,2,...,)i m B b i -=i 以b 记的第个分量 (2).计算单纯形乘子w , B wB C =,得到1 B w C B -=,对于非基变量，计算判别数 1i i i B i i z c c B p c σ-=-=-,令 max{}k i i i R z c σ∈=-,R 为非基变量集合 若判别数0k σ≤ ,则得到一个最优基本可行解，运算结束；否则，转到下一步 (3).解k k By p =,得到 1 k k y B p -=；若0k y ≤,即k y 的每个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤(4). (4).确定下标r,使 { } :0 min ,0 t r rk tk tk b b tk y y t y y >=>且r B x 为离基变量。 k x 为进基变量，用k p 替换r B p ，得到新的基矩阵B ，返回步骤（1）。 对于极大化问题，可以给出完全类似的步骤，只是确定进基变量的准则不同。对于极大化问题，应令 min{}k k j j z c z c -=- 四、计算框图 是 否 是 否 开始 初始可行解B 令1,0,B N B B x B b b x f c x -==== 计算单纯形乘子1 B w c B -=，计算判别数,i j j wp c j R σ=-∈（非基变量） 令max{,}k j j R σσ=∈ 0?k σ≤ 得到最优解 解方程k k By p =，得到1k k y B p -=。 0?k y ≤ 不存在有限最优解 确定下标r ，是 { }:0 min ,0 t r rk tk tk b b tk y y t y y >=>且 k x 为进基变量，用 k p 替换r B p ，得到新的基矩阵B 数 学 软 件 与 实 验 数学与信息科学学院 信息与计算科学 单纯形法的Matlab程序如下：function [xx,fm]=myprgmh(m,n,A,b,c) B0=A(:,1:m); cb=c(:,1:m); xx=1:n; sgm=c-cb*B0^-1*A; h=-1; sta=ones(m,1); for i=m+1:n if sgm(i)>0 h=1; end end while h>0 [msg,mk]=max(sgm); for i=1:m sta(i)=b(i)/A(i,mk); end [mst,mr]=min(sta); zy=A(mr,mk); for i=1:m if i==mr for j=1:n A(i,j)=A(i,j)/zy; end b(i)=b(i)/zy; end end for i=1:m if i~=mr for j=1:n A(i,j)=A(i,j)-A(i,mk)*A(mr,j); end b(i)=b(i)-A(i,mk)*b(mr); end end B1=A(:,1:m); cb(mr)=c(mk); xx(mr)=mk; sgm=c-cb*B1*A; for i=m+1:n if sgm(i)>0 h=1; end end end fm=c*xx; 例题： 编写下列求解如下线性规划问题的单纯形法函数min f'x s.t ax<=b(其中b>=0) 函数形式function [x,fval,it,op]=singl(f,a,b) 输出中x为最优解 fval为最优值 it为迭代次数 无最优解op=0 有最优解op=1 编写程序如下： function [x,fval,it,op]=singl(f,a,b) [m,n]=size(a); c=[a eye(m) b;f' zeros(1,m+1)]; fval=0; x=zeros(m+n,1); op=1; it=0; e=zeros(1,m); lie=find(f<0); l=length(lie); while(l>0) for j=1:l d=find(c(:,lie(j))); %求解标准型线性规划:max c*x;s.t. A*x=b;x>=0 %本函数中的A是单纯初始表，包括:最后一行是初始的检验数，最后一列是资源向量b %N是初始的基变量的下标 %输出变量sol是最优解 %输出变量val是最优值，kk是迭代次数 function [sol,val,kk]=ssimplex(A,N) [mA,nA]=size(A); kk=0; %迭代次数 flag=1; while flag kk=kk+1; if A(mA,:)<=0 %已找到最优解 flag=0; sol=zeros(1,nA-1);%给每个变量赋初值0 for i=1:mA-1 sol(N(i))=A(i,nA);%给基变量赋新值(替换0) end %给出最优解 val=-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) 算法实现与分析 算法1.单纯形法 具体算例: 标准化后: 用单纯形法求解,程序如下: clear clc M=1000000; A=[3,2,-3,1,0;1,-2,1,0,1];%系数矩阵 C=[-3,1,2,M,M,0];%价值矩阵 B=[6;4]; Xt=[4 5]; for i=1:length(C)-1 D=0; for j=1:length(Xt) D=D+A(j,i)*C(Xt(j)); end xi(i)=C(i)-D; end s=[]; for i=1:length(xi) if xi(i)<0 s=[s,i]; end end f=length(s); h=1; while(f) for k=1:length(s) j=1; A x=[]; for i=1:length(Xt) if A(i,s(k))>0 x(j)=i; j=j+1; end end x if(length(x)+1==1) break; end y=1 x for i=1:length(x) if B(x(i))/A(x(i),s(k)) 运筹学教程（胡运权主编，清华第4版）部分习题答案（第一章）1.1 （1）无穷多解：α (6/5, 1/5) + (1- α) (3/2, 0)，α∈ [0,1]。 （2）无可行解； （3）x* = (10,6)，z* = 16； （4）最优解无界。 1.2 （1）max z’ = 3x1 - 4x2 + 2x3 - 5x’4 + 5x’’4 s.t. –4x1 + x2 – 2x3 + x’4– x’’4 = 2 x1 + x2 – x3 + 2x’4– 2x’’4 + x5 = 14 –2x1 + 3x2 + x3 – x’4+ x’’4– x6 = 2 x1, x2, x3, x’4, x’’4, x5, x6 ≥ 0 （2）max z’ = 2x’1 + 2x2 – 3x’3 + 3x’’3 s.t. x’1 + x2 + x’3 – x’’3 = 4 2x’1 + x2 – x’3 + x’’3 + x4 = 6 x’1, x2, x’3, x’’3, x4, ≥ 0 1.3 （1）基解：(0, 16/3, -7/6, 0, 0, 0)； (0, 10, 0, -7, 0, 0)； (0, 3, 0, 0, 7/2, 0)，是基可行解，z = 3，是最优解； (7/4, -4, 0, 0, 0, 21/4)； (0, 16/3, -7/6, 0, 0, 0)； (0, 0, -5/2, 8, 0, 0)； (1, 0, -1/2, 0, 0, 3)； (0, 0, 0, 3, 5, 0)，是基可行解，z = 0； (5/4, 0, 0, -2, 0, 15/4)； (3/4, 0, 0, 0, 2, 9/4)，是基可行解，z = 9/4； (0, 0, 3/2, 0, 8, 0)，是基可行解，z = 3，是最优解。 （2）基解：(-4, 11/2, 0, 0)； (2/5, 0, 11/5, 0)，是基可行解，z = 43/5； (-1/3, 0, 0, 11/6)； (0, 1/2, 2, 0)，是基可行解，z = 5，是最优解； 单纯形法（Matlab 程序） %%单纯形法( Matlab 程序) a=input('input the major matrix A '); b=input('input the matrix b '); n=input('input the judgement '); %%为计数器(确定循环次数) g=0; while g<40 %%确定非负 alength=max(size(n)); blength=max(size(b)); m=0; for i=1:alength if n(i)>=0 m=m+1; end end; if m==alength x=b; break end; %%找 K s=min(n); for i=1:alength if n(i)==s k=i; break end; end; %%a[i,k] 的非负性 m=0; for i=1:blength if a(i,k)<0 m=m+1; end; end; if m==blength disp('x does not exit'); judge=1; break end; %%找 L 确定主元 cc=100000; for i=1:blength if a(i,k)>0 if (b(i)/a(i,k))< cc cc=b(i)/a(i,k); end end end; for i=1:blength if a(i,k)~=0 if (b(i)/a(i,k))==cc l=i; break end end end; %%计算 ,a 标准化 zu=a(l,k); aa=a; for i=1:l-1 for j=1:alength aa(i,j)=a(i,j)- a(l,j)*a(i,k)/a(l,k); end end; for i=l+1:blength for j=1:alength aa(i,j)=a(i,j)- a(l,j)*a(i,k)/a(l,k); end end; for j=1:alength aa(l,j)=a(l,j)/zu; end; %%b勺判别 bb=b; bb(l)=b(l)/zu; for i=1:l-1 bb(i)=b(i)- b(l)*a(i,k)/a(l,k); end; for i=l+1:blength bb(i)=b(i)- b(l)*a(i,k)/a(l,k); end; b=bb; %%确定判别数 线性规划 线性规划是处理线性目标函数和线性约束的一种较为成熟的方法，目前已经广泛应用于军事、经济、工业、农业、教育、商业和社会科学等许多方面。 8.2.1 基本数学原理 线性规划问题的标准形式是： ????? ??????≥=+++=+++=++++++=0,,,min 21221122222121112 121112211n m n mn m m n n n n n n x x x b x a x a x a b x a x a x a b x a x a x a x c x c x c z 或 ???? ?????=≥===∑∑==n j x m i b x a x c z j n j i j ij n j j j ,,2,1,0,,2,1,min 1 1 写成矩阵形式为： ?? ???≥==O X b AX CX z min 线性规划的标准形式要求使目标函数最小化，约束条件取等式，变量b 非负。不符合这几个条件的线性模型可以转化成标准形式。 MATLAB 采用投影法求解线性规划问题，该方法是单纯形法的变种。 8.2.2 有关函数介绍 在MATLAB 工具箱中，可用linprog 函数求解线性规划问题。 linprog 函数的调用格式如下： ●x=linprog(f,A,b)：求解问题minf'*x ，约束条件为A*x<=b 。 ●x=linprog(f,A,b,Aeq,beq)：求解上面的问题，但增加等式约束，即Aeq*x=beq 。若没有不等式约束，则令A=[ ],b=[ ]。 ●x=linprog(f,A,b,Aeq,beq,lb,ub)：定义设计x 的下界lb 和上界ub ，使得x 始终在该范围内。若没有等式约束，令Aeq=[ ],beq=[ ]。 ●x=linprog(f,A,b,Aeq,beq,lb,ub,x0)：设置初值为x0。该选项只适用于中型问题，默认时大型算法将忽略初值。 ●x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)：用options 指定的优化参数进行最小化。 ●[x,fval]=linprog(…)：返回解x 处的目标函数值fval 。 ●[x,lambda,exitflag]=linprog(…)：返回exitflag 值，描述函数计算的退出条件。 ●[x,lambda,exitflag,output]=linprog(…)：返回包含优化信息的输出参数output 。 ●[x,fval,exitflag,output,lambda]=linprog(…)：将解x 处的拉格朗日乘子返回到lambda 参数中。 多目标线性规划的若干解法及MATLAB 实现 一．多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函 数,其数学模型表示为： 11111221221122221122max n n n n r r r rn n z c x c x c x z c x c x c x z c x c x c x =+++??=+++?? ??=+++? （1） 约束条件为： 1111221121122222112212,,,0 n n n n m m mn n m n a x a x a x b a x a x a x b a x a x a x b x x x +++≤??+++≤?? ??+++≤?≥?? （2） 若（1）式中只有一个1122i i i in n z c x c x c x =+++ ，则该问题为典型的单目标线性规划。我们记:()ij m n A a ?=,()ij r n C c ?=,12(,,,)T m b b b b = ,12(,,,)T n x x x x = ， 12(,,,)T r Z Z Z Z = . 则上述多目标线性规划可用矩阵形式表示为: max Z Cx = 约束条件：0 Ax b x ≤?? ≥? （3） 二．MATLAB 优化工具箱常用函数[3] 在MA TLAB 软件中，有几个专门求解最优化问题的函数，如求线性规划问题的linprog 、求有约束非线性函数的fmincon 、求最大最小化问题的fminimax 、求多目标达到问题的fgoalattain 等,它们的调用形式分别为： ①.[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub) f 为目标函数系数,A,b 为不等式约束的系数, Aeq,beq 为等式约束系数, lb,ub 为x 的下 限和上限, fval 求解的x 所对应的值。 算法原理：单纯形法的改进方法投影法 ②.[x,fval ]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub ） fun 为目标函数的M 函数, x0为初值,A,b 为不等式约束的系数, Aeq,beq 为等式约束 北京联合大学 实验报告 项目名称：运筹学专题实验报告 学院：自动化专业：物流工程 班级： 1201B 学号：2012100358081 姓名：管水城成绩： 2015 年 5 月 6 日 实验二：MATLAB 编程单纯形法求解 一、实验目的： (1)使学生在程序设计方面得到进一步的训练;，掌握Matlab (C 或VB)语言进行程序设计中一些常用方法。 (2)使学生对线性规划的单纯形法有更深的理解. 二、实验用仪器设备、器材或软件环境 计算机, Matlab R2006 三、算法步骤、计算框图、计算程序等 本实验主要编写如下线性规划问题的计算程序: ?? ?≥≥≤0 ,0..min b x b Ax t s cx 其中初始可行基为松弛变量对应的列组成. 对于一般标准线性规划问题: ?? ?≥≥=0 ,0..min b x b Ax t s cx １．求解上述一般标准线性规划的单纯形算法（修正）步骤如下： 对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可行解。设初始基为B,然后执行如下步骤： (1).解B Bx b =,求得 1 B x B b -=，0,N B B x f c x ==令计算目标函数值 1(1,2,...,)i m B b i -=i 以b 记的第个分量 (2).计算单纯形乘子w, B wB C =,得到1 B w C B -=,对于非基变量，计算判别 数1i i i B i i z c c B p c σ-=-=-,可直接计算 σ =1 B A c c B --令 max{}k i R σσ∈=,R 为非基变量集合 若判别数0k σ≤ ,则得到一个最优基本可行解，运算结束；否则，转到下一 步 (3).解k k By p =,得到 1 k k y B p -=；若0k y ≤,即k y 的每个分量均非正数， 则停止计算，问题不存在有限最优解，否则，进行步骤(4).确定下标r,使 { }:0 min ,0 t r rk tk tk b b tk y y t y y >=>且r B x 为离基变量, ,r k B x p k 为进基变量,用p 替换得到新的基矩阵B,还回步骤(1) ; 线性规划及单纯形法 一．选择 1. 运筹学应用分析、试验、（C ）的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 A 统筹 B 量化 C 优化 D 决策 2. 运筹学研究的基本手段是（A ）。 A 建立数学模型 B 进行数学分析 C 进行决策分析 D 建立管理规范 3. 运筹学研究的基本特点是（ C ）。 A 进行系统局部独立分析 B 考虑系统局部优化 C 考虑系统的整体优化 D 进行系统的整体决策 4. 线性规划问题的数学模型包含三个组成要素：决策变量、目标函数、（B ） A 表达式 B 约束条件 C 方程变量 D 价值系数 5. 线性规划问题的基可行解X 对应线性规划问题可行域（凸集）的（ C ） A 边 B 平面 C 顶点 D 内部 6. 目标函数取极小化（Z min ）的线性规划问题可以转化为目标函数取极大化即（C ）的线性规划问题求解 A Z min B )min(Z - C )max(Z - D Z max - 7. 标准形式的线性规划问题，最优解（C ）是可行解 A 一定 B 一定不 C 不一定 D 无法确定 8. 在线性规划问题中，称满足所有约束条件方程和非负限制的解为（ C ）。 A 最优解 B 基可行解 C 可行解 D 基解 9. 生产和经营管理中经常提出任何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是所谓的（D ） A 管理问题 B 规划问题 C 决策问题 D 优化问题 10. 在线性规划问题中，图解法适合用于处理变量（ B ）个的线性规划问题 A 1 B 2 C 3 D 4 11. 求解线性规划问题时，解的情况有:唯一最优解、无穷多最优解、（ C ）、无可行解 A 无解B 无基解 C 无界解 D 无基可行解 12. 在用图解法求解的时，找不到满足约束条件的公共范围，这时问题有（D ），其原因是模型本身有错误，约束条件之间相互矛盾，应检查修正。 A 唯一最优解 B 无穷多最优解 C 无界解D 无可行解 13. 线性规划问题的基可行解()T n X X X ,,1 =为基可行解的充要条件是X 的正分量所对 应的系数列向量是（B ） A 线性相关 B 线性独立 C 非线性独立 D 无法判断 14. 线性规划问题进行最优性检验和解的判别时，如果当0≤j σ时，人工变量仍留在基本量中且不为零，（D ） A 唯一最优解 B 无穷多最优解 C 无界解 D 无可行解 15.如果集合C 中任意两个点21,X X 其连线上的所有点也都是集合C 中的点，称C 为（B ） 第一章 线性规划及单纯形法习题 1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。 （1）??? ??≥≥+≥++=0,42266432min 2121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ?? ? ??≤≤≤≤≤++=8 3105120 106max 21212 1x x x x x x z (4) ??? ??≥≤+-≥-+=0,2322 265max 1 2212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。 (1)????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43214321432143214321,0,,2321422 245243min x x x x x x x x x x x x x x x x x x x x z (2) ????? ? ?≥≤≥-++-≤-+-=++-+-=无约束 32143213213213 21,0,023*******min x x x x x x x x x x x x x x x x z 3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优解。 (1) ??? ?? ? ?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213 21Λj x x x x x x x x x x x x x x z j (2) ??? ??=≥=+++=+++++-=)4,,1(0102227 4322325min 432143214321Λj x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。 一、用单纯形第Ⅰ阶段和第Ⅱ阶段解下列问题 s.t. 解：1)、将该线性问题转为标准线性问题 一、第一阶段求解初始可行点 2)、引入人工变量修改约束集合 取人工变量为状态变量，问题变量和松弛变量为决策变量，得到如下单纯形表，并是所有决策变量的值为零，得到人工变量的非负值。 2 -2 -1 1 2 1 1 -1 -1 1 2 -1 -2 1 2 5 -2 -4 1 -1 1 5 0 0 0 0 0 3)、对上述单纯形表进行计算，是目标函数进一步减小，选为要改变的决策变量，计算改变的限值。 2 -2 -1 1 2 1 1 1 -1 -1 1 0 2 -1 -2 1 2 0 5 -2 -4 1 -1 1 5 1 0 0 0 0 0 0 1 0 0 0 4)、由于，为人工变量，当其到达零值时，将其从问题中拿掉保证其值不会再变。同时将以改变的决策变量转换为状态变量。增加的值使目标函数值更小。 1 -3 1 1 1 0 1 1 -1 1 1 -3 1 1 1 0 0 0 0 0 0 0 0 5）使所有人工变量为零的问题变量的值记为所求目标函数的初始可行点，本例为， 二、第二阶段用单纯形法求解最优解 -2 2 1 0 1 1 -1 0 -2 1 2 1 5 1 3 要使目标函数继续减小，需要减小或的值，由以上计算，已经有两个松弛变量为零，因此或不能再减小了，故该初始可行点即为最优解。 2、求解问题 s.t. 如果目标函数变成，确定使原解仍保持最优的c值范围，并把目标函数最 大值变达成c的函数。 解：先采用单纯形法求解最优解，再对保持最优解时C值的范围进行讨论。 1）将问题华为标准线性问题 s.t. 2）用单纯形表表示约束条件，同时在不引入人工变量的前提下，取松弛变量得初始值为零值，求解初始解和最优解 10 -1 -1 -1 10 -20 1 5 1 -20 -2 -1 -1 0 0 0 0 要使目标函数继续减小，可以增大，增大的限值是10。 10 -1 -1 -1 10 0 -20 1 5 1 -20 -10 -2 -1 -1 0 -20 0 0 0 10 0 0 3）转轴。将为零的松弛变量和决策变量交换进行转轴 10 -1 -1 -1 10 -10 4 0 -1 -10 0 -20 1 1 2 -20 大连民族学院 数学实验报告 课程：____________________ 最优化方法______________________ 实验题目： ___________ 单纯形法的matlab实现 ___________________ 系别：______________________ 理学院________________________ 专业：__________________ 信息与计算科学____________________ 姓名：__________________________________________________ 班级：_____________________ 信息102班 ____________________ 指导教师：___________________ 葛仁东_______________________ 完成学期：2013 年__9 ___________ 月_2________ 日 实验目的： 实验方法和步骤(包括数值公式、算法步骤、程序) ： 考察标准形式的线性规划问题： min f(x) C T x s.t Ax b, x 0 设x(k)F为一个基本可行解，单纯形方法首先检验它的最优性。如果它不是最优的，确定与该顶点相连的一条使目标函数下降的边；接下来确定沿这个边移 动多远可以到达另一个更优的相邻点，也就是得出一个新的基本可行解 算法步骤： 步骤1给定一个初始基本可行解，记迭代次数 k 1 ； 步骤2 :计算单纯形乘子y k B k T c B k)和简约价值系数向量C N k) c N k) N T y k ； 步骤3 :最优性检验，计算C?k) min{C (k)|j 2}，如果C?k) 0，则x (k)为最优解， 停止迭代；否则有x p 0，选x p 为入基变量； 步骤4:确定出基变量，计算g k) B k 1a p ，如果对所有j B k ，有器)0,则问题 无有界的最优解，停止迭代；否则确定出基变量指标 步骤5:交换B k 的列a q 与N k 的列a p 得到新的基矩阵 盼和山+1，计算新的基本可 行解 x (k1),置k:k 1后转步骤 2； 在上述算法中，当存在不止一个简约价值系数 C j k) 0时，选取最负的?“的 指标为p ，并以X p 作为入基变量。 Matlab 计算程序： Function] x,f]=zuiyouhua(A,b,c) Size(A)=[m, n]; i=n+1: n+m; N=1: n; B=eye(m,m); xb=b '; xn=zeros(m,1); f1=0; w=zeros(1,m); z=-c; flag=1; while(1) [a,k]=max(z); If a<=0 flag=0; break else y=i nv(B)*A(:,k) b (k) B k }； min{ _(k )殆 0, j 《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》 ? ? ??≥=+ +=+++++=?? ? ??≥≤+≤++=0 ,,,24 261553).(002max ,,0,24 261553).(2max 14.1843214213 214 321432121212 1x x x x x x x x x x t s x x x x z x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【为初始基变量， 选择43,x x )1000(00)0010(01 )2050(12)6030(24321=?+?-==?+?-==?+?-==?+?-=σσσσ 为出基变量。为进基变量，所以选择41x x 3 /1)6/122/10(00 )0210(03 /1)3/1240(10)1200(24321-=?+-?-= =?+?-==?+?-==?+?-=σσσσ 为出基变量。 为进基变量，所以选择32x x 24 /724/528/11012/112/124/1100 021110 120124321-=?+-?-=-=-?+?-==?+?-==?+?-=）（）（）（）（σσσσ 4 33 4341522max , )4 3,415(),(2112= +?=+===x x z x x X T T 故有：所以，最优解为 ??? ??? ?≥=+ +=+=+ ++++=?????? ?≥≤+≤≤+=0,,,,18232424).(0002max ,,,0 ,182312212 ).(52max 24.185432152142315 43215432121212 1x x x x x x x x x x x x t s x x x x x z x x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【 )000010(00001000000000100520200052300010254321=?+?+?-==?+?+?-==?+?+?-==?+?+?-==?+?+?-=σσσσσ）（）（）（）（ 为出基变量。为进基变量，所以选择42x x function Z=dcxf(c,A,N) %定义函数名称为dcxf。 l=length(N); CB=c(N(1):N(l)) [m,n]=size(A); b=A(:,n); A=A(:,1:n-1); %参数包括目标函数系数(C)，约束条件的系数矩阵(A)， %其中A的最后一列为约束条件的右端值b，初始基向量的位置(N)。 sigma=c-CB*A;%计算检验数sigma。 display('初始单纯形表为:');%输出初始的单纯形表table=[nan,nan,nan,c;CB',N',b,A;nan,nan,nan,si gma] opt=1;step=0; while opt step=step+1;%定义循环，直到第“step”步找到最优解(opt=0)。 if sum(sigma>0)==0 %利用检验数判断是否得到最优解，并给出提示。 display('没有得到最优解,继续迭代．'); opt=0; else inb=find(sigma==max(sigma)); %利用单纯形方法找到入基变量的位置 num=length(inb); Inb=inb(num) flag=0; for i=1:m %利用单纯形方法找出出基变量的位置 if A(i,inb)>0 theta(i)=b(i)/A(i,inb); else theta(i)=inf; end end outb=find(theta==min(theta)); num=length(outb); %判断足否出现退化现象，如出现退化，给il{语言提示，并取最后出现的符合出基条件的变量为出基变量。 if num~=1 display('出现退化情况．'); end outb=outb(num); 单纯形法（Mat lab程序） %%单纯形法（Mat lab程序）a= input (' input the major matrix A '); b=input (' input the matrix b '); n=input C input the judgement '); %%为计数器(确定循环次数) 萨0; while g<40 %%确定非负 alength=max(size(n)); blength二max(size(b)); m=0; for i=l:alength 辻n(i)〉=0 m二m+1; end end; if m==alength x=b; break end; %%找K s二min(n); for i=l:alength if n(i) ==s k二i; break end; end; %%a[i,k]的非负性 m=0; for i=l:blength if a(i, k)<0 m二m+1; end; end; if m==blength disp('x does not exit'); judge二1； break end; %%找L确定主元cc=100000; for i=l:blength if a (i, k) >0 if (b(i)/a(i, k))< cc cc=b(i)/a(i, k); end end end; for i=l:blength if a(i, k)~=0 if (b(i)/a(i, k))==cc 1二i； break end end end; %%计算,a 标准化zu=a(l, k); aa=a; for i=l:1-1 for j=l:alength aa(i, j)=a(i, j)- a(l, j)*a(i, k)/a(l, k); end end; for i=l+l:blength for j=l :alength aa(i, j)=a(i, j)- a(l, j)*a(i, k)/a(l, k); end end; for j=l:alength aa(l, j)=a(l, j)/zu; end; %%b 勺判别bb=b; bb(l)=b(l)/zu; for i=l: 1~1 bb(i)=b(i)~ b⑴*a(i, k)/a(l, k); end; for i=l+l:blength bb(i)二b(i)- b(l)*a(i, k)/a(l, k); end; b二bb; %%确定判别数 第1章 线性规划与单纯形法 1、用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。 ??? ??≥≥+≥++=0 x x 42x 4x 66x 4x 3x 2x minz )a (21 21212 1， ?? ? ??≥≥+≤++=0 x ,x 124x 3x 2 x 2x 2x 3x maxz )b (2121212 1 ?? ???≤≤≤≤≤++=8x 310x 5120 10x 6x x x maxz )c (21 212 1 ?? ? ??≥≤+-≥-+=0 x ,x 23x 2x 2x 2x 6x 5x maxz )d (2121212 1 2、用单纯形法求解下列线性规划问题。 ?????≥ ≤+≤++=0 x ,x 82x 5x 94x 3x 5x 10x maxz )a (21 2 121 2 1 ????? ? ? ≥ ≤+≤+≤+=0 x ,x 5x x 242x 6x 155x x 2x maxz )b (2 1 212 122 1 3、用大M 法和两阶段法求解下列线性规划问题，并指出属于哪一类解。 ??? ?? ??≥≥-≥+-≥+++-=0 x x x 0 x 2x 2x 2x 6 x x x 2x x 2x maxz )a (3 , 2,132 3 13213 21 ??? ??≥≥+≥++++=0 x , x ,x 6 2x 3x 82x 4x x x 3x 2x minz )b (3 21 2 1 3 21 3 21 4、已知线性规划问题的初始单纯形表（如表1所示）和用单纯形法迭代后得到的表（如表2所示）如下，试求括弧中未知数a ～l 的值。 表1 实验报告 实验题目: 单纯形法的matlab实现学生: 学号: 实验时间: 2013-4-15 一．实验名称: 单纯形法的MATLAB 实现 二．实验目的及要求: 1. 了解单纯形算法的原理及其matlab 实现. 2. 运用MATLAB 编辑单纯形法程序解决线性规划的极小化问题, 求出最优解及目标函数值. 三．实验容: 1. 单纯形方法原理: 单纯形方法的基本思想, 是从一个基本可行解出发, 求一个使目标函数值有所改善的基本可行解; 通过不断改进基本可行解, 力图达到最优基本可行解. 对问题 . 0 ,A s.t. def min ≥=x b x cx f 其中A 是一个m ×n 矩阵, 且秩为m, c 为n 维行向量, x 为n 维列向量, b 为m 维非负列向量. 符号“”表示右端的表达式是左端的定义式, 即目标函数f 的具体形式就是cx . 记 ),...,,(n 21p p p A = 令A =(B,N), B 为基矩阵, N 为非基矩阵, 设 ?? ? ???=0B 1-) 0(b x 是基本可行解, 在) 0(x 处的目标函数值 b c b c c cx f 1 -B 1-N B ) 0(0B 0B ),(=?? ????==, 其中B c 是c 中与基变量对应的分量组成的m 维行向量; N c 是c 中与非基变量对应的分量组成的n-m 维行向量. 现由基本可行解) 0(x 出发求解一个改进的基本可行解. 设?? ? ? ??=N B x x x 是任一可行解, 则由b Ax =得到 N 1-1-B N B B x b x -=, 在点x 处的目标函数值 ∑∈--=?? ? ???==R j j j j f x x c c cx f x )c z (),(0N B N B , 其中R 是非基变量下标集, j j p c 1-B B z =. 2. 单纯形方法计算步骤: 首先给定一个初始基本可行解, 设初始基为B, 然后执行下列主要步骤: （1）解b x B =B , 求得_ 1 b b B x B ==-, 令0=N x , 计算目标函数值B B x c f =. （2）求单纯形乘子w , 解B c wB =, 得到1 -=B c w B . 对于所有非基变量, 计算判别数 j j j j j c c -z -=p w . 令 } c -{z max c -z j j R j k k ∈=. 若0c -z k k ≤, 则对于所有非基变量0c -z j j ≤, 对应基变量的判别数总是为零, 因此停止计算, 现行基本可行解是最优解. 否则, 进行下一步. （3）解k k p By =, 得到k 1 k p B y -=, 若0k ≤y , 即k y 的每个分量均非正数, 则停止计算, 问题不存在有限最优解. 否则进行步骤（4）. （4）确定下标r, 使 康福 0031 一．无约束优化方法 无约束优化方法的必要性 一般机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。但是为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优 化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 （4）对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可 微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。 共轭梯度法 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 （1）间接法——要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度 法等。 （2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。 用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（n ≤20）问题，一般情况下比间接法效率低。 间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛 矩阵。 搜索方向的构成问题乃是无约束优化方法的关键。 1(0,1,2,) k k k k s k α+=+=L x x 共轭梯度法是沿着共轭方向进行搜索，属于共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。共轭梯度法作为一种实用的迭代法，它主要有下面的优点： （1）算法中，系数矩阵Ａ的作用仅仅是用来由已知向量P 产生向量W=AP ，这不仅 可充分利用Ａ的稀疏性，而且对某些提供矩阵Ａ较为困难而由已知向量P 产生向量W=AP 又十分方便的应用问题是很有益的。 （2）不需要预先估计任何参数就可以计算，这一点不像SOR 等； （3）每次迭代所需的计算，主要是向量之间的运算，便于并行化。 共轭梯度法原理的知识较多，请详见《机械优化设计》第四章的第四、五节。 图1为共轭梯度法的程度框图 图1为共轭梯度法的程度框图 二．设计题目及要求 设计题目 用共轭梯度法求二次函数 2 21212 112(,)242f x x x x x x x =+-- 的极小点及极小值。 设计要求 （1）使用matlab 编写程序，熟练撑握matlab 编程方法。 （2）学习并撑握共轭梯度法的原理、方法及应用，并了解不同无约束优化方法的 区别、优缺点及特殊要求。 （3）编写程序，计算出二次函数的极小点及极小值，并适当选取不同的初始点及 迭代精度精度，分析比较结果。最优化实验报告(单纯形法的matlab程序,lingo程序)
单纯形法matlab
matlab单纯形法
单纯形法matlab程序
16991-运筹学-习题答案选01_线性规划和单纯形法
单纯形法MATLAB程序
运用Matlab进行线性规划求解(实例)
多目标线性规划的若干解法及MATLAB实现
实验二：MATLAB编程单纯形法求解
第1章线性规划及单纯形法
线性规划及单纯形法习题
最新单纯形法解线性规划问题
单纯形法的matlab实现(20200814192014)
线性规划单纯形法(例题)
单纯形法matlab程序
单纯形法MATLAB程序
线性规划与单纯形法
单纯形法的matlab实现(极小化问题)
用MATLAB实现共轭梯度法求解实例