用单纯形法求解性规划问题.doc

……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………:膁线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,,英文缩写LP。,它一直是求解线性规划问题的最有效的数学方法之一。单纯形法的理论根据是:线性规划问题的可行域是n维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。通过引入普通单纯形法,依次迭代并判断,逐步逼近,最后得到最优解。若不是,则按照一定法则转换到另一改进的基本可行解,再鉴别;若仍不是,则再转换,按此重复进行。因基本可行解的个数有限,故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。莆关键字:线性规划,单纯形法,最优值,:,锻炼数学建模能力。、求解和分析。,完成对单纯形法问题的编程设计。:袆某商场决定,营业员每周连续工作5天后连续休息2天,轮流休息,据统计,商场每天需要营业员如下:星期一:300,二:300;三:350,四:400,五:480,六:600;日:500;螄(1)商场人力资源部应如何安排每天上班的人数才能使商场总的营业员最少蒂(2)若商场可以雇佣临时工,上班时间同正式工,若正式工每天工资80,临时工每天100,问商场是否应雇佣临时工及雇佣多少名?:膃从实际问题中建立数学模型一般有以下三个步骤:;;。羃当我们得到的数学模型的目标函数为线性函数,约束条件为线性等式或不等式时称此数学模型为线性规划模型。蒁蒆线性规划问题的标准形式:芆蚃由题可知,可设每天上班人数分别应为x1,x2,x3,x4,x5,x6,x7;艿建立下列数学模型袈螆将其转化为标准形式为::袂根据单纯形法的原理,在线性规划问题中,决策变量(控制变量)x1,x2,…xn的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值(或最小值)的可行解称为最优解。这样,一个或多个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值(或最小值)。求解线性规划问题的目的就是要找出最优解。聿最优解可能出现下列情况之一:①存在着一个最优解;②存在着无穷多个最优解;③不存在最优解,这只在三种情况下发生,即没有可行解或各项约束条件不阻止目标函数的值无限增大(或向负的方向无限增大)。肆单纯形法的一般解题步骤可归纳如下:薆把线性规划问题的约束方程组表达成典范型方程组,找出基本可行解作为初始基本可行解。薂若基本可行解不存在,即约束条件有矛盾,则问题无解。肀若基本可行解存在,从初始基本可行解作为起点,根据最优性条件和可行性条件,引入非基变量取代某一基变量,找出目标函数值更优的另一基本可行解。葿按步骤3进行迭代,直到对应检验数满足最优性条件(这时目标函数值不能再改善),即得到问题的最优解。羅若迭代过程中发现问题的目标函数值无界,则终止迭代。莂流程图如下:膂薇対原问题增加m个人工变量构造辅助问题莅肃判断辅助问题最优值g=0罿无解,停止罿人工变量xj是否为非基变量袄袃把人工变量对应的列从单纯形表中去掉肀肈进行换基迭代得到新矩阵B芃薃B中是否有人工变量肂膆得到初始可行基B羇莄求对应典式和检验数ξ衿蕿莆判断ξk≤0肄羀得到最优解蚇进行换基迭代得到新基螆判断Ak≤0薁羂问题无界聿否芅是芁否蝿否膈是蚄是肁否袁是芆