版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、四、单纯形法的一般描述: 1、 初始可行解的确定 (1)初始可行基的确定 观察法观察系数矩阵中是否含有现成的单位阵? LP限制条件中全部是“”类型的约束 将新增的松弛变量作为初始基变量,对应的系数列向量构成单位阵;,先将约束条件标准化,再引入非负的人工变量, 以人工变量作为初始基变量,其对应的系数列向量构成单位阵,称为“人造基”; 然后用大M法或两阶段法求解;, 线性规划限制条件都是“”或“=”类型的约束,等式约束左端引入人工变量的目的,使约束方程的系数矩阵中出现一个单位阵,用单位阵的每一个列向量对应的决策变量作为“基变量”,这样,出现在单纯形表格中的B(i)列(即约束方程的右边常数)值正好就
2、是基变量的取值。 (注意:用非基变量表示基变量的表达式),如果限制条件中既有“”类型的约束,又有“”或“=”类型的约束,怎麽办? 构造“不完全的人造基”!,讨 论,为什麽初始可行基一定要选单位阵? b列正好就是基变量的取值,检验数行 和b列交叉处元素也正好对应目标函数值, 因此称b列为解答列,(2)写出初始基本可行解 根据“用非基变量表示基变量的表达式”,非基变量取0,算出基变量,搭配在一起构成初始基本可行解。,2、建立判别准则: (1)两个基本表达式的一般形式 就LP限制条件中全部是“”类型约束,新增的松弛变量作为初始基变量的情况来描述:,此时LP的标准型为,初始可行基 :,初始基本可行解:
3、,一般(经过若干次迭代),对于基B, 用非基变量表出基变量的表达式 为:,用非基变量表示目标函数的表达式:,若 是对应于基B的基本可行解, 是非基变量 的检验数,若对于一切非基变量的角指标j,均有 0,则X(0)为最优解。,(2)最优性判别定理,(3)无“有限最优解”的判别定理,若 为一基本可行解,有一非基变量xk,其检验数 , 而对于i=1,2,,m,均有 ,则该线性规划问题没有“有限最优解”。,证明思路构造性证明: 依据用非基变量表示基变量的表达式构造一族可行解,其对应的目标函数值趋于无穷大。 几何意义:沿着无界边界前进的一族可行解,举例:用非基变量表示基变量的表达式,代表两个约束条件:,
4、x2对应的系数列向量P2=(1,3)T, 当前的换入变量是 X2,按最小比值原则确定换出变量:,要求:,于是:,如果x2的系数列变成P2=(-1,0)T,则用非基变量表示基变量的表达式就变成;,可行性自然满足,最小比值原则失效,意即x2的值可以任意增大原线性规划无“有限最优解”。,3、进行基变换 (1)选择进基变量原则:正检验数(或最大正检验数)所对应的变量进基,目的是使目标函数得到改善(较快增大); 进基变量对应的系数列称为主元列。 (2)出基变量的确定按最小比值原则确定出基变量,为的是保持解的可行性; 出基变量所在的行称为主元行。 主元行和主元列的交叉元素称为主元素。,思考题,这样进行基变
5、换后得到的新解对应的系数列向量是否线性独立?,4、主元变换(旋转运算或枢运算) 按照主元素进行矩阵的初等行变换把主元素变成1,主元列的其他元素变成0(即主元列变为单位向量) 写出新的基本可行解,返回最优性检验。,单纯形法小结,求解思想 顶点的逐步转移, 条件是 使目标函数值不断得到改善。,表格单纯形法求解步骤,第一步:将LP化为标准型,并加以整理。 引入适当的松驰变量、剩余变量和人工变量,使约束条件化为等式,并且约束方程组的系数阵中有一个单位阵。 (这一步计算机可自动完成) 确定初始可行基,写出初始基本可行解,第二步:最优性检验,计算检验数,检查: 所有检验数是否 0? 是结束,写出最优解和目
6、标函数最优值; 还有正检验数检查相应系数列 0? 是结束,该LP无“有限最优解”! 不属于上述两种情况,转入下一步基变换。 确定是停止迭代还是转入基变换?,选择(最大)正检验数对应的系数列为主元列,主元列对应的非基变量为换入变量; 最小比值对应的行为主元行,主元行对应的基变量为换出变量。,第三步:基变换,确定进基变量和出基变量。,利用矩阵的初等行变换把主元列变成单位向量,主元素变为1,进基变量对应的检验数变成0,从而得到一张新的单纯形表,返回第二步。,第四步 换基迭代(旋转运算、枢运算),完成一次迭代,得到新的基本可行解和相应的目标函数值,该迭代过程直至下列情况之一发生时停止 检验数行全部变为
7、非正值; (得到最优解)或 主元列 0 (最优解无界),停止迭代的标志(停机准则),依据:最优性检验的两个定理 最优性判别定理;无“有限最优解”判断定理,计算机求解时的注意点,1. 输入数据中的分数,需先化为小数再执行输入过程。 2.每一张迭代表格中由基变量列(Basic)和B(i)列(解答列)可以读出现行解及相应的目标函数值,同时显示进基变量和出基变量,从而很容易识别主元列、主元行和主元素。 3.最终表显示最优解、最优目标函数值及总的迭代次数。如遇该线性规划无可行解或无“有限最优解”,则屏幕将显示有关信息: NO feasible solution . 或 * * unbounded sol
8、ution !,五、各种类型线性规划的处理 1、分类及处理原则: (1)类型一:目标要求是“Max”,约束条件是“”类型左边加上非负松弛变量变成等式约束(约束条件标准化),将引入的松弛变量作为初始基变量,则初始可行基是一个单位阵,用原始单纯形法求解。,(2)类型二:目标要求是“Max”,约束条件是“=”类型左边引入非负的人工变量,并将引入的人工变量作为初始基变量,则初始可行基是一个单位阵,然后用大M法或两阶段法求解。 (3)类型三:目标要求是“Max”,约束条件是“”类型约束条件标准化,左边减去非负的剩余变量,变成等式约束,化为类型二。,(4)类型四:目标要求是“Min” 方法1化为极大化问题
9、 方法2按照极小化问题直接在单纯形表格上计算处理,但 相应的原则要作改动。,2、处理人工变量的方法: (1)大M法在约束条件中人为地加入非负的人工变量,以便使它们对应的系数列向量构成单位阵。 问题:加入的人工变量是否合理?如何处理? 在目标函数中,给人工变量前面添上一个绝对值很大的负系数-M(M0),迭代过程中,只要基变量中还存在人工变量,目标函数就不可能实现极大化惩罚!, 最优表中,基变量不包含人工变量,则最优解就是原线性规划的最优解,不影响目标函数的取值; 最优表中,基变量中仍含有人工变量,表明原线性规划的约束条件被破坏,线性规划没有可行解,也就没有最优解!,结 果,问题,结果中求得的最优
10、解是哪个线性规划的最优解?为什麽?,(2) 两阶段法 第一阶段:建立辅助线性规划并求解,以判断原线性规划是否存在基本可行解。 辅助线性规划的结构:目标函数W为所有人工变量之和,目标要求是使目标函数极小化,约束条件与原线性规划相同。,求解结果 W最优值=0即所有人工变量取值全为0(为什麽?),均为非基变量,最优解是原线性规划的一个基本可行解,转入第二阶段; W最优值=0但人工变量中有等于0的基变量,构成退化的基本可行解,可以转化为情况;如何转化? 选一个不是人工变量的非基变量进基, 把在基中的人工变量替换出来,W最优值0至少有一个人工变量取值0,说明基变量中至少有1个人工变量,表明原问题没有可行
11、解,讨论结束。,问题讨论,如果辅助线性规划的结构是:目标函数W为所有人工变量之和的相反数,目标要求是使目标函数极大化,约束条件与原线性规划相同。这与上述的讨论是否矛盾?,试比较:,(1),(2),(1)式目标要求改为极大化(或(2)式目标要求改为极小化)行不行?,第二阶段: 将第一阶段的最优解作为初始可行解,目标函数换成原问题的目标函数,进行单纯形迭代,求出最优解。 问题讨论: 如何实施?需要重新建立初始单纯形表吗?,实施中,在第一阶段最优表格中划去人工变量列,将表头部分和CB列的价值系数换成原问题的价值系数(把目标函数换成原线性规划的目标函数),继续迭代,直至求出最优解。, 在大M法中,当人
12、工变量出基后能否立即划去该人工变量所在的系数列?,3、用表格单纯形法直接计算极小化线性规划时要修改哪些原则? (初始表?最优解判别?换入变量?换出变量?旋转运算?引入人工变量?) 最优性判别:所有检验数非负 换入变量的选择原则:(最小)负检验数所对应的变量进基,以保证目标函数值(较快)减小; 用大M法求解时,在目标函数中人工变量的前面添上一个很大的正系数M;,六、迭代过程中可能出现的问题及处理方法,1、为确定出基变量要计算比值,该比值=解答列元素/主元列元素。对于主元列的0元素或负元素是否也要计算比值? (此时解的可行性自然满足,不必计算;如果主元列元素全部为0元素或负元素,则最小比值失效,线性规划无“有限最优解”),2、出现若干个相同的最小比值怎麽办? (说明出现了退化的基本可行解,即非0分量的个数小于约束方程的个数。按照“摄动原理”所得的规则,从相同比
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年农业行业并购整合趋势及投后管理研究
- 2026年单身公寓产业发展报告:独居经济场景解析与市场预测
- 2026年教育行业危机预警与应对策略分析
- 2026年制造业项目进度管理及风险应对报告
- 2026年动漫行业5G虚拟偶像产业发展报告
- 2026年金融科技行业分析报告:区块链技术应用与风险控制
- 2026年洗鞋行业市场细分领域市场机遇研究报告
- 2026年金融服务收费模式创新分析报告
- 2026年婚庆市场趋势分析报告及未来五年行业预测
- 2026年新能源产业数字化管理看板市场研究报告
- 《相似植物如何区别》课件
- 驾驶员素质提升培训
- My family幼儿园家庭成员介绍手抄报
- 国家安全教育大学生读本-第一章完全准确领会总体国家安全观
- 2016年公务员国考《申论》真题卷及答案(副省级)
- 《外科学》教案:第七章 麻醉
- 产后康复经络与腧穴
- 2023航标灯光强测量和灯光射程计算
- 《工业机器人技术基础》第5章 工业机器人控制系统课件
- 化工传递过程基础全部
- 边坡滑坡及治理
评论
0/150
提交评论