用单纯形法求解线性规划问题.docx
17页
目录一•摘要 2二.实验目的 2三•实验内容 2四. 建立数学模型 3五. 实验原理 5六. MALTAB程序代码及注释 7七. 结果运行测试 13八. 心得与感悟 15一•摘要：线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重 要分支，它是辅助人们进行科学管理的一种数学方法•研究线性约束条件下线性 目标函数的极值问题的数学理论和方法，英文缩写LP自1946年G.B.Dantizig提出单纯形法以来，它一直是求解线性规划问题的 最有效的数学方法之一单纯形法的理论根据是：线性规划问题的可行域是n 维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到顶 点所对应的可行解称为基本可行解通过引入普通单纯形法，依次迭代并判断， 逐步逼近，最后得到最优解若不是，则按照一定法则转换到另一改进的基本可 行解，再鉴别；若仍不是，则再转换，按此重复进行因基本可行解的个数有限, 故经有限次转换必能得出问题的最优解如果问题无最优解也可用此法判别关键字：线性规划，单纯形法，最优值，最优解二实验目的：1•加强学生分析问题能力，锻炼数学建模能力2. 了解并掌握MATLAB软件中的线性规划问题的编程、求解和分析。
3. 利用所学的MALTAB语言，完成对单纯形法问题的编程设计三•实验内容:某商场决定，营业员每周连续工作5天后连续休息2天，轮流休息，据统计, 商场每天需要营业员如下：星期一：300，二：300；三：350,四：400，五：480, 六：600； 日: 500；(1) 商场人力资源部应如何安排每天上班的人数才能使商场总的营业员最 少(2) 若商场可以雇佣临时工，上班时间同正式工，若正式工每天工资80， 临时工每天100，问商场是否应雇佣临时工及雇佣多少名？四•建立数学模型：从实际问题中建立数学模型一般有以下三个步骤：1. 根据影响所要达到目的的因素找到决策变量；2. 由决策变量和所在达到目的之间的函数关系确定目标函数；3. 由决策变量所受的限制条件确定决策变量所要满足的约束条件当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等 式时称此数学模型为线性规划模型线性规划问题的标准形式:max z 二 卩］+ c2x2 H 1- cnxna2Ax}+a22x2+-^ + a2nxn=b2卡,兀2厂…，兀鬥二0由题可知，可设每天上班人数分别应为xl,x2,x3,x4,x5,x6,x7;建立下列数学模型min Z=x} +x2 +花-\-x4 +无 +x6 +x. sA. X］ +x5 >= 300xL +x2 -\-x5 >= 300旺+卷+屯+兀+工丁〉= 3 50Xj + 卷 +尤3 +'尤4 +无7〉= 4()() 兀I +兀二+兀§ +兀4 +兀5〉= 480 兀］+ 心 + *4 + 屯 + % >= 600 些 +x +% +x? >= 550 兀〉=0 j = 13233?4?5,6?7将其转化为标准形式为:= 300 = 300■V10= 350= 400 = 480 = 600—xL4 = 550 j = l?23?4?5?6?7,8?9?10?ll,12J3J4即 尸 「min 7=
使目标函数达到最大 值（或最小值）的可行解称为最优解这样，一个或多个最优解能在整个由约束 条件所确定的可行区域内使目标函数达到最大值（或最小值）求解线性规划问 题的目的就是要找出最优解最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最 优解；③不存在最优解，这只在三种情况下发生，即没有可行解或各项约束条件 不阻止目标函数的值无限增大（或向负的方向无限增大）单纯形法的一般解题步骤可归纳如下：① 把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作 为初始基本可行解② 若基本可行解不存在，即约束条件有矛盾，则问题无解③ 若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可 行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一 基本可行解④ 按步骤3进行迭代，直到对应检验数满足最优性条件（这时目标函数值不 能再改善），即得到问题的最优解⑤ 若迭代过程中发现问题的目标函数值无界，则终止迭代流程图如下六. MALTAB程序代码及注释：function [x,minf,flag,cpt]=dcxsf(A,b,c)format rat %吏数据可以以分数形式输出c=-c; %将目标函数系数向量加负号得到单纯形表第0行[m,n]=size(A); %求约束矩阵的行数和列数m1=m; %保存下原来的行数s=eye(m); %生成秩为m的单位矩阵A=[A s]; %将$矩阵添加到A矩阵右侧A=[A b]; %将匕向量添加到A矩阵右侧 g1=zeros(1,n); %生成一个1行n列的零矩阵g1 x=ones(1,m); %生成一个1行m列元素全为1的矩阵 g1=[g1 -x]; %将§1和-x合并，产生一个新的前n列为0后m列为-1的单行矩阵g=[0]; %初始化一个单元素零矩阵g1=[g1 g];%将单元素零矩阵添加到g1右侧，生成人工向量的检验向量g1 s1=n+m+1; %记录目前列数之和s2 = zeros(1,m+1);% 生成 1 行 m+1 列的零矩阵s2c=[c s2];%将s2添加到c右侧A1=zeros(m,1);%生成一个m行1列的零矩阵A1for i1=1:mA1(i1,1)=i1+n;%基变量的数值存储区endfor i=1:mg1(1,:)= g1(1,:)+A(i,:);enddecide=find(g1(1,1:m+n)>0); %寻找g1中大于零的数值列数存于decide 数组中while ~isempty(decide) %Sdecide 不为空i=decide(1); 将列数赋给itext=find(A(1:m,i)>0); %ext存放该列中所有数值大于零的行数if isempty(text) 如果text为空贝V无解flag=0;break;endmin=inf;%mi初始化为无穷大for i1=1:m 当该列存在大于零的数值时i A(i1,i)>0 &A(i1,s1)/A(i1,i)
