2011-2012-2实验1 单纯形法求解线性规划

线性规划问题的单纯形法求解步骤线性规划是一种优化问题，它的解决方法有很多种，在这里我们来介绍其中一种常用的方法——单纯形法。

我们将介绍单纯形法的求解步骤，以帮助读者更好地理解和掌握这种求解方法。

1. 建立数学模型任何一个线性规划问题的解决都需要先进行建模。

我们将问题转换成数学模型，然后使用数学方法进行求解。

线性规划问题的一般形式为：max cxs.t.Ax ≤ bx ≥ 0其中，c、x、b、A都是向量或矩阵，x≥0表示各变量都是非负数。

其中c表示目标函数，A和b表示约束条件。

2. 计算初始基可行解我们需要从初始点开始，逐步优化目标函数。

但是，在开始优化前我们需要先找到一个基可行解。

基可行解的定义是：如果所有非基变量的取值都是0，并且所有基变量的取值都是非负的，则该解被称为基可行解。

当基可行解找到后，我们就可以开始进行优化。

3. 确定进入变量在单纯形法中，每次迭代中我们都需要找到进入变量。

进入变量是指，通过操作非基变量可以使得目标函数增加的变量。

我们需要找到一个使得目标函数增加最多的非基变量，将其称为进入变量。

4. 确定离开变量在确定进入变量后，我们需要确定一个离开变量。

离开变量是指，通过操作基变量可以使得目标函数增加的变量。

我们需要找到一个离开变量，使得当进入变量增加到某个值时，该离开变量的值为0。

这样，我们就找到了一个最小的正根比率，使得通过基本变量出基到进入变量变为零而得到的新解是可行的。

5. 交换变量接下来，我们需要将已选定的进入变量和离开变量进行交换。

此时，我们将进入变量转变为基变量，离开变量转变为非基变量。

通过这种交换，我们还需要调整我们的基向量。

由于这个交换，我们将得到一个新的基可行解，并且它可以比之前的解更好。

6. 重复迭代我们需要重复上述步骤，直到我们找到最优解。

重复迭代意味着我们将不断查找新的进入变量和离开变量，并进行变量交换。

这种找到最优解的过程可能非常复杂，但是单纯形法的效率很高，通常可以在很短的时间内找到最优解。

单纯形法解线性规划问题金融83 周慧媛0812178摘要：线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.研究线性约束条件下线性目标函数的极值问题的数学理论和方法,英文缩写LP。

自1946年G.B.Dantizig提出单纯形法以来，它一直是求解线性规划问题的最有效的数学方法之一。

单纯形法的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到。

顶点所对应的可行解称为基本可行解。

通过引入普通单纯形法，依次迭代并判断，逐步逼近，最后得到最优解。

关键字：线性规划，单纯形法，最优值，最优解一、单纯形法的基本思想任何一种单纯形法的迭代算法必须解决三个问题：1.从哪一个顶点开始？2.用一条什么样的有效途径进行出一个顶点向另一个较好的顶点移动？3.何时停止该过程？单纯形法即从一个粗的解开始，成功改进现有的解，直到所要求的目标满足为止。

对于一个迭代算法，要求一个停止规划，以检查是否达到目标。

单纯形法的计算方法：1.找出一个初始的可行基B12.求出对应的典式及检验数向量&3.求&k = max {&j /j=1,2,3….n}4.若&k<=0，停止。

随着经济全球化的不断深化，企业面临更加激烈的市场竞争。

企业须不断提高管理水平，增强其获利能力，在生产、销售、新产品研发等一系列过程中只有自己的优势，提高企业效率，降低成本，形成企业的核心竞争力。

过去很多企业在生产、运输、市场营销等方面没有利用线性规划进行合理的配置，从而增加了企业的生产，使企业的利润不能达到最大化。

在竞争日益激烈的今天，如果还按照过去的方式，是难以生存的，所以就有必要利用线性规划的知识对战略计划、生产、销售各个环节进行优化从而降低生产成本，提高企业的效率。

在各类经济活动中，经常遇到这样的问题：在生产条件不变的情况下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效益最好。

的充要条件是X的正分量对应的系数列向量 是线性独立的。
• 定理2：线性规划问题的基可行解X对应于 可行域D的顶点。 证明：反证法。分两步。
• 定理3：若可行域有界，线性规划问题的目 标函数一定可以在其可行域的顶点上达到最 优。
几点结论：
线性规划问题的可行域是凸集。 若线性规划问题有最优解，一定存在一个
为了求得以x3,x4,x2为基变量的一个基可行解和相
应的检验数，需将x2 与x5的位置对换。得到 X3 +2x2 =8 - x1 (1) x4 =16-4x1 (2) 4x2=12 - x5 (3) 用消元法，得： x3 =2- x1 +1/2x5 (1)‘ x4 =16-4x1 (2)‘ x2=3 -1/4 x5 (3)‘
x 1 2x 2 x 3 4x1 4x2 x4
8 16 x5 12
X ( 4 , 3 , 2 , 0 , 0 ) 非基可行解 1
例
P ,P ,P 3 4 5
基变量
非基变量
x3, x4 , x5
1 B2 0 0
0 1 0
0 0 1
x1 , x2
P, j j=1，2，…,m —— 基向量。 j=1，2，…,m —— 基变量。 X， j , j=m+1,…,n —— 非基变量。 X j
为了进一步讨论线性规划问题的解，下
线 性 规 划 问 题 解 的 概 念
面研究约束方程的求解问题。假设该方 程组系数矩阵A的秩为m,因m<n,故它 有无穷多个解。假设前m个变量的系数 列向量是线性独立的。
1 0 0 B 0 (P 3, P 4, P 5) 0 1 0 0 0 1
2、求对应于 X0的检验数

实 验 报 告求解线性规划实验（运筹学与最优化方法，4学时）班级专业 姓名 学号 日期一 实验目的掌握线性规划的求解，会用单纯形法法、大M 法解线性规划。

二 实验内容1 用单纯形法解线性规划：1212121212min 232210..315,0z x x x x x x s t x x x x =---+≤⎧⎪+≤⎪⎨+≤⎪⎪≥⎩2 用大M 法解线性规划：123123123123min 323236..24,,0z x x x x x x s t x x x x x x =-+++-=⎧⎪-+-=-⎨⎪≥⎩3.解下列线性规划，考虑其是哪一种特殊情况。

（1）12122121212max 5040351502085300..50,0z x x x x x x x s t x x x x =++≤⎧⎪≤⎪⎪+≤⎨⎪+≥⎪≥⎪⎩（无解）（2）121212max 20102..5,0z x x x s t x x x =+≥⎧⎪≤⎨⎪≥⎩（没有边界）（3）121221212max30503515020..85300,0z x xx xxs tx xx x=++≤⎧⎪≤⎪⎨+≤⎪⎪≥⎩（多个最优解）（4）121221212max50403517520..85300,0z x xx xxs tx xx x=++≤⎧⎪≤⎪⎨+≤⎪⎪≥⎩三实验步骤（算法）与结果1.算法：A=[-1 1 1 0 0 2;1 2 0 1 0 10;3 1 0 0 1 15;-2 -3 0 0 0 0]; N=[1 2 3 ];>> [sol,val,k]=simplex(A,N)function [sol,val,k]=simplex(A,N)[m,n]=size(A);k=0;flag=1;while flagk=k+1;if A(m,:)>=0flag=0;break;sol=zeros(1,n-1);for i=1:m-1sol(N(i))=A(i,n);endval=-A(m,n);if flagtemp=0;for i=1:n-1if A(m,i)<0temp=A(m,i);inb=i;endendsita=zeros(1,m-1);for i=1:m-1sita(i)=A(i,n)/A(i,inb);endtemp=1000;for i=1:m-1if sita(i)>0&sita(i)<temptemp=sita(i);outb=i;endendfor i=1:m-1if i==outbN(i)=inb;endendA(outb,:)=A(outb,:)/A(outb,inb);for i=1:mif i~=outbA(i,:)=A(i,:)-A(outb,:)*A(i,inb);endendendendend结果：sol =4.0000 3.0000 3.0000 0 0val =-17k =42算法function [sol,val,k]=simpleM(C,A,b) [m,n] = size(A);for j=1:mif b(j)<0b(j)=-b(j);A(j,:)=-A(j,:);endendA = [A,eye(m)];M = 1000;for run = 1:1:mC = [C,M];endN = (n+1:n+m);%N承装初始基变量的下标n= n+m;val=0;x = zeros(1,n);for j = 1:mx(N(j)) = b(j);endval = C*x';sita = zeros(1,n);for i = 1:ntemp = 0;for j = 1:mtemp = temp + C(N(j))*A(j,i);endsita(i) = C(i)-temp;endk=0;while min(sita)<0k=k+1;for j=1:nif sita(j)<0inb=j;%入基变量的下标endendtheta = zeros(1,m);for j = 1:mtheta(j) = b(j)/A(j,inb);endtemp = Inf;for j = 1:mif theta(j)>0 & theta(j)<temptemp = theta(j);outb=N(j);%离基变量的下标outl = j;%出基变量在基变量中的位置endendfor j = 1:mif N(j) == outb;N(j) =inb;endend%下面进行转轴运算b(outl) = b(outl)/A(outl,inb);A(outl,:) = A(outl,:)/A(outl,inb);val=-(sita(outl)/A(outl,inb))*b(outl)-val;for j = 1:mif j ~= outlb(j) = b(j) - b(outl)*A(j,inb);A(j,:) = A(j,:) - A(outl,:)*A(j,inb);endendfor i=1:nsita(i)=sita(i)-sita(inb)/A(outl,inb)*A(outl,i);endsita;endsol=zeros(1,n);for i=1:msol(N(i))=b(i);endval;结果：3.算法function [x,val,flag,k]=originalsimpleM(C,A,b) M = 1e5;[m,n] = size(A);A = [A,eye(m)];for run = 1:1:mC = [C,-M];endN = (n+1:n+m);%N承装初始基变量的下标n = n+m;k = 0;while 1k = k +1;flag = 0;%%sita = zeros(1,n);for i = 1:ntemp = 0;for j = 1:mtemp = temp + C(N(j))*A(j,i);endsita(i) = C(i)-temp;end%%if sita<=0x = zeros(1,n);for j = 1:mx(N(j)) = b(j);endfor j = 1:mfor temp = n-m+1:nif N(j)==temp && x(temp)~=0 flag = 3;%方程组没有无解x = 0;val = 0;break;endendif flag == 3break;endendif flag == 3break;endfor i = 1:ntflag = 0;for j = 1:mif i == N(j)tflag = 1;break;endendif tflag == 0if sita(i) == 0flag = 1; %方程组有无穷多解break;endendendif flag == 1x = x(:,1:n-m);break;endif flag == 0;x = x(:,1:n-m);val;endelsefor i = 1:nif sita(i)>0 & A(:,i)<=0flag = 2;%方程组无界x = 0;val = 0;break;endendif flag == 2break;end%%temp = 0;for i = 1:nif sita(i)>temptemp = sita(i);inb = i;%入基变量的下标endendtheta = zeros(1,m);for j = 1:mif A(j,inb)>0theta(j) = b(j)/A(j,inb);endendtemp = Inf;for j = 1:mif theta(j)>0 & theta(j)temp = theta(j);outb = N(j);%离基变量的下标outl = j;%离基变量在基变量中的位置endend%%b(outl) = b(outl)/A(outl,inb);A(outl,:) = A(outl,:)/A(outl,inb);if j ~= outlb(j) = b(j) - b(outl)*A(j,inb);A(j,:) = A(j,:) - A(outl,:)*A(j,inb);endend%%for j = 1:mif N(j) == outb;N(j) = inb;endendendend%%if flag == 0disp('此方程组有唯一解');x;val;endif flag == 1disp('此方程组有无穷多解');endif flag == 2disp('此方程组无界');endif flag == 3disp('此方程组没有无解');end(1)结果（2）此方程组无界（3）此方程组有无穷多解（4）此方程组没有最优解四实验收获与教师评语。