1. 研究目的与意义
1.背景介绍
线性规划是运筹学中研究较早,发展较快,方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.线性规划的主要任务就是在数量上规划出各种最优,以便充分发挥资源的效能去获取最佳经济效益.例如:在原料配给问题中,确定最优成分比例,从而提高质量和降低成本;在资源的分配问题中,实现最优分配,使得分配方案既能满足于各方面的基本要求,又能获得好的经济效益;在农田规划中,最优安排各种农作物的布局,保持高产,稳定以及发挥地区优势;在经济管理,交通运输,工农业生产等经济活动中合理安排人力物力等资源,使经济效果达到最优.
2.研究意义
2. 研究内容和预期目标
二.研究内容
1.人工变量法的定义
对于单纯形表,如果没有初始基,初始单纯形表就无法形成.此时就要首先把LP模型转化为标准形式,即所有的变量均为非负,所有约束条件为等式,所有的右端项系数非负;其次检查每一个约束条件,对每一个没有基变量的约束引入一个新的变量作为基变量,这样就使得每个约束均有基变量.这些新的变量仅仅是为了建立初始单纯形表而引入的,为了把它们和原问题的决策变量加以区别,称为人工变量.
2.人工变量法的求解方法
2.1大M法的基本思想
在约束条件中添加人工变量y(i),将其作为基变量,迅速得到一组初始可行解,使得单纯形法能够顺利实施.
注意:人工变量是后加入到原约束方程的变量,破坏了原来的约束条件,同时还要求它对目标函数的取值不造成因影响.因此必须让人工变量尽快出基,成为非基变量.因为非基变量的取值为0,从而达到不破坏原约束并且对目标函数的取值不造成影响的目的.
2.2大M法的步骤
将线性规划问题化为标准型LP1,在约束方程组的左边加上若干个非负的人工变量,使人工变量对应的系数列向量与其他变量的系数列向量共同构成一个单位矩阵,作为初始基.
在目标函数中赋予人工变量一个任意大的正系数M.
写出LP2,用表格单纯形法求解.
若LP2的最优解中仍然有人工变量,则说明原问题没有可行解,方程组Ax=b不成立.
若没有人工变量,则去除人工变量即为原问题的基础可行解,继续求最优解.
2.3两阶段法的基本思想
先引入人工变量,构造一个辅助问题,用单纯形法求解辅助问题,目的是为了判断原问题是否存在可行解.
注意:用单纯形法求出的第一阶段的最优解不是原线性规划的最优解.
二者的关系是:1.若在辅助问题中的最优基中最小值取到下界0,并且人工变量全部出基,即人工变量全部成为非基变量,而对应的m个基变量全部为原问题的x变量.
2.若在辅助问题的最优基中还有人工变量y,但最小值取到下界0,这时人工变量的取值一定为0.
3.若辅助问题对应最优解的目标函数值大于0,即最优解min Z>0这说明基变量中有人工变量(人工变量的取值大于0),此时原问题无可行解.
2.4两阶段法的步骤
始终包含一个M进行单纯形表的运算是不方便的,为此有了两阶段法.两阶段法就是将引入的人工变量后的规划问题分为两个阶段来求解:
第一阶段：引入m个人工变量,建立辅助问题并求解.
目标函数是全体人工变量之和.
约束条件是:加入人工变量后的约束方程,求出辅助问题的最优解,若已没有人工变量作基变量,且minw=0,则得到原问题的一个基础可行解,否则原线性规划没有可行解.
第二阶段:由第一阶段中求出的基础可行解,继续用单纯形法求原问题的最优解.
3.灵敏度分析
3.1灵敏度分析定义
灵敏度分析是研究与分析一个系统（或模型）的状态或输出变化对系统参数或周围条件变化的敏感程度的方法,其意义很大:其一,很多实际问题中数据常常是不够精确的,很多是估计出来的,因此调整数据是常事;其二,当一个用于决策的问题得出最优解后,决策者为了通观全局,常常要研究其中的某些因素的改变对当前最优决策所造成的影响;其三,当作多种方案比较时,这些不同的方案常常是某些数据不同而已.因而在实际问题进行灵敏度分析是必要的.
3.2灵敏度分析步骤:
1.将参数的改变通过计算反应到最终单纯形表中:具体方法是,按公式计算参数a,b,c的变化引起的最终单纯形表上相关数字的变化:
2.检查原问题是否仍为可行解
3.检查对偶问题是否为可行解
4.按下表所列情况得出结论和决定继续计算的步骤
原问题 | 对偶问题 | 结论或继续计算的步骤 |
可行解 | 可行解 | 问题的最优解或最优基不变 |
可行解 | 非可行解 | 用单纯形法继续迭代求最优解 |
非可行解 | 可行解 | 用对偶单纯形法继续迭代求最优解 |
非可行解 | 非可行解 | 引入人工变量，编制新的单纯形表重新计算 |
4.割平面法
4.1割平面法定义
割平面法是1958年由美国学者高莫利(Gomory)提出的求解全整数规划的一种比较简单的方法.
4.2割平面法的基本思想
在整数规划问题的松弛问题中依此引入线性约束条件（即割平面）,使问题的可行域逐步缩小.但每次切割只切割去问题部分非整数解,直到使问题的目标函数值达到最优的整数点称为缩小后可行域的一个顶点,这样就可以用求解线性规划问题的方法找出这个最优解.
4.3割平面法的构造过程
1.把问题中的所有约束条件的系数均化为整数,若不考虑变量的整数约束,可得到该整数规划的松弛问题的单纯形表.若得到整数解则求解过程结束,否则继续.
2.找出非整数解变量中分数部分最大的一个基变量,并写出约束加以整理后加入松弛变量.
3.将Gomory约束加到G0中得到新的线性规划问题G1
4.重复第一至第三步一直到找出问题的整数最优解为止
5.人工变量法应用实例
5.1人工变量法在灵敏度分析中的实例分析
在真实世界,周围的环境条件是在不断变化的.原材料的成本在变,产品的需求在变,公司购买新设备,股票价格波动,人员流动等都在不断变化.如果我们要用线性规划模型去解决实际问题,那模型的系数就不可能一成不变.
1.目标函数函数中系数c的变化影响到检验数的变化,即引起表 的前两种变化.
2.b的变化就是资源数量发生变化,引起基变量的变化.此时就需算出Δb,并将其加到基变量列的数字上,然后继续求解.
增加一个变量就是增加一种新的产品,此时需要先计算出δ;然后计算P(j);若δ(j)≤0,只需将P(j)和δ(j)的值反映在最终表即可,原最优解不变;否则继续迭代计算.
5.2人工变量法在割平面法中的案例详解
实际问题中当得出的不是整数解时为了进一步得到最优解就需引入割平面法,即可以取新的约束条件然后进行求解,求解过程中还需引入人工变量.
三.拟解决的关键问题
1.在引入人工变量之前各约束已为等式,所以为保持等式的平衡,人工变量最终的取值必须为零.只要人工变量的取值不为零,目标函数就不可能极大化.
2.目标函数的系数取M并且是个极大的正数.
3.在b发生变化时,要注意如果已知最终单纯形表中的基可行解所对应的基B (最终单纯形表中的基变量在初始单纯形表中的列向量所构成的矩阵）,即可在最终单纯形表中找到B的逆(初始单纯形表中的单位矩阵I在最终单纯形表中所对应的矩阵),并且最终单纯形表中的每一列均可用其在初始单纯形表中的相应列左乘B的逆来得到,即b等于B的逆乘以b.
4.割平面法中随着Gomory的序贯增加,会出现多个基本变量是Gomory松弛变量的情况,此时则需注意:当某个松弛变量再次成为基本变量时可以将其从单纯形表中删除其所在的行和列,处理后迭代过程中的单纯形表至多含有n 1个基本变量.切割的可行域的Gomory至多有n-1 m个.
四.写作提纲
1.题目
2.内容摘要
3.关键词
4.背景介绍以及研究意义
5.介绍人工变量法的内容
6.建立模型对引入人工变量法后的线性规划问题进行求解（即大M法和两阶段法的求解方法过程）
7.介绍灵敏度分析和割平面法的相关内容
8.结合一些有背景的实际问题介绍人工变量法的应用（重点介绍其在灵敏度分析和割平面法中的应用）
9.总述全文内容,强调在实际应用中引入人工变量法的必要性以及重要性
10.参考文献
3. 国内外研究现状
线性规划的研究与应用工作,我国开始于20世纪50年代初期,中国科学院数学所筹建了运筹室,最早应用在物资调运等方面,在实践中取得了成果,在理论上提出了论证;同时线性规划在现代管理以及经济管理等方面也起到了重要的作用,美国78%的企业应用线性规划解决生产上的问题,且效果显著.在我国随着计算机的普遍发展,线性规划也已经成为企业中重要的管理方法.
时至今日关于线性规划的人工变量法的研究夜也已经较为成熟,国内高等学校已将其列为运筹学中必选的课程内容之一,在实际应用方面也已列入重点企业试点和研究项目之一;国外也将其应用到各个学科以及实践操作中.
4. 计划与进度安排
2022年11月20日至30日 完成毕业论文文献搜索以及开题报告.
2022年02月26日至2022年03月04日 进入实习单位实习并系统学习运筹学课程,掌握线性规划相关知识理念.
2022年03月05日至11日 学习线性规划的人工变量法,掌握求解过程.两种方法大M法和两阶段法求解过程以及解题中的注意点都要注重并熟练掌握.
5. 参考文献
[1] 钱送迪.运筹学[M].北京:清华大学出版社,1990.
[2] 胡运全.运筹学基础及应用[M].哈尔滨工业大学出版社,1993.
[3] Balas E,Ceria S,Cornuejols G and Natraj G.Gomary cuts revisted[J].Core Discussion Papers,1998,90(3):429-457
以上是毕业论文开题报告，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
