人工变量法_百度百科


本站和网页 https://baike.baidu.com/item/人工变量法/16629814 的作者无关,不对其内容负责。快照谨为网络故障时之索引,不代表被搜索网站的即时页面。

人工变量法_百度百科
百度首页
网页
新闻
贴吧
知道
网盘
图片
视频
地图
文库
百科
进入词条
全站搜索
帮助
清除历史记录关闭
近期有不法分子冒充百度百科官方人员,以删除词条为由威胁并敲诈相关企业。在此严正声明:百度百科是免费编辑平台,绝不存在收费代编服务,请勿上当受骗!详情>>
首页
历史上的今天
百科冷知识
图解百科
秒懂百科
懂啦
秒懂本尊答
秒懂大师说
秒懂看瓦特
秒懂五千年
秒懂全视界
特色百科
数字博物馆
非遗百科
恐龙百科
多肉百科
艺术百科
科学百科
用户
蝌蚪团
热词团
百科校园
分类达人
百科任务
百科商城
知识专题
权威合作
合作模式
常见问题
联系方式
下载百科APP
个人中心
收藏
查看我的收藏
有用+1
已投票
人工变量法
播报
编辑
锁定
讨论
上传视频
特型编辑
数学术语
本词条由“科普中国”科学百科词条编写与应用工作项目
审核
在线性规划问题的单纯形法中,若标准化后找不到单位矩阵,可以采用人造基,给方程加入人工变量后,用大M法和两阶段法处理求解。是求解线性规划问题的一种方式。
中文名
人工变量法
外文名
Artificial variable method
适用领域
线性规划
应用学科
组合数学、运筹学
方 法
大M法和两阶段法
意 义
求解特殊的线性规划问题
相关视频查看全部
目录
定律定义
求解方法
大M法
两阶段法
求解结果
适用范围
人工变量法定律定义
编辑
播报
其公式如下:
,其中Xs是xs松弛变量组成的向量。正如上式所展示的那样,所有约束是(≤),并且有非负右端项(bi≥0)的线性规划,化为标准形式是在每个不等式的左端添加一个松弛变量,这时约束等式左端的系数矩阵就含有一个单位矩阵I,取这个单位矩阵为初始基,很容易得到一个初始基本可行解,从而建立单纯形表。
[1]
但包含(=)和或(≥)约束条件则不是如此。对于(≥)型约束来说,标准化时需添加剩余变量,其系数为-1,而对(=)型约束,则没有松弛变量,因此存在这两种约束条件标准化后缺少足够的松弛变量的系数组成(诸如
)十分直观的单位矩阵,也即无法不做变换地找到基本可行解。这时候可以利用人工变量x(artificial variables)类似松弛变量添加到等式中去,让它们在第一次迭代起着松弛变量的作用,并随后用某次迭代中再把这些人工变量去掉。
[2]
由于人工变量存在于初始基本可行解,而且人工变量是虚拟变量,它们在目标函数取极值时不应该存在数值,因此需要将它们从基变量中替换出来。若人工变量可以从基变量中替换出来,即基变量中不含有非零的人工变量,表示原问题有解;若人工变量不可以从基变量中替换出来,则表示原问题无可行解。
[3]
人工变量法求解方法
编辑
播报
加入人工变量后,一般可采用大M法或两阶段法处理。
人工变量法大M法
如果是求极大值,即假定人工变量在目标函数中的系数为-M(M是任意大正数);如果是求极小值,人工变量在目标函数中的系数为M。用单纯形法对模型求解,如基变量中还存在M,就不能实现极值。
人工变量法两阶段法
用计算机处理数据时,只能用很大的数代替M,可能造成错误,故多采用两阶段法。第一阶段:在原线性规划问题中加入人工变量,构造模型。构造模型的目标函数为:
用单纯形法对上述模型求解。若W=0,说明问题存在基本可行解,可以进行第二个阶段;否则,原问题无可行解,停止运算。第二阶段:在第一阶段的最终表中,(1)去掉人工变量,(2)将目标函数的系数换成原问题的目标函数系数,作为第二阶段计算的初始表,用单纯形法计算。
[4]
人工变量法求解结果
编辑
播报
1、无可行解:运算到检验数全负为止,若仍含有人工变量在基可行解未进入非基变量,则无可行解。2、退化:若计算出的用于确定换出变量的
有两个以上最小值,会造成下一次迭代中有一个或几个基变量等于零。为避免退化,虽任意换出变量目标函数值不变,但此时不同的基却表示为同一顶点,其特例是永远达不到最优解,需作如下处理兰特Bland规则:(1)当
中出现两个以上最大值时,选下标最小的非基变量为换入变量;(2)当
中出现两个以上最小值时,选下标最小的基变量为换出变量。
[4]
人工变量法适用范围
编辑
播报
当存在(=)和或(≥)约束条件时使用该方法。虽然标准化后可能存在单位矩阵可以不需要添加人工变量,但是它不具有代表性,而且人工变量法具有普适性,即使添加上了不妨碍结果,人工变量法比起寻找单位矩阵,无论在人工还是计算机计算时都有更高的可操作性。
[4]
百度百科内容由网友共同编辑,如您发现自己的词条内容不准确或不完善,欢迎使用本人词条编辑服务(免费)参与修正。立即前往>>
词条图册
更多图册
参考资料
贾贞.运筹学原理与实验教程.武汉:华中师范大学出版社,2008:23
哈姆迪·A·塔哈 (Hamdy A.Taha).管理科学与工程经典译丛:运筹学导论(第9版·基础篇):中国人民大学出版社,2014
卢开澄,卢华明.组合数学(第四版):清华大学出版社,2006
胡运权.运筹学教程 第4版:清华大学出版社,2012:31-35
图集
人工变量法的概述图(1张)
科普中国
致力于权威的科学传播
本词条认证专家为
尚轶伦
副教授审核
同济大学数学科学学院
V百科往期回顾
权威合作编辑
“科普中国”科学百科词条编写与应用工作项目
“科普中国”是为我国科普信息化建设塑造的全...
什么是权威编辑
词条统计
浏览次数:次
编辑次数:7次历史版本
最近更新:
smile路过倾城
(2022-03-31)
定律定义
求解方法
大M法
两阶段法
求解结果
适用范围
为您推荐广告
新手上路
成长任务
编辑入门
编辑规则
本人编辑
我有疑问
内容质疑
在线客服
官方贴吧
意见反馈
投诉建议
举报不良信息
未通过词条申诉
投诉侵权信息
封禁查询与解封
©2022 Baidu 使用百度前必读 | 百科协议 | 隐私政策 | 百度百科合作平台 | 京ICP证030173号
京公网安备11000002000001号
进入词条
清除历史记录关闭
播报
编辑
讨论
收藏
登录
扫码下载百科APP
领取50财富值奖励
分享到微信朋友圈
打开微信“扫一扫”即可将网页分享至朋友圈
选择朗读音色
00:00
00:00

Copyright ©uecom 京ICP备18064371号-1 IPV6
2024-03-29 20:03:55
uenu.com
10.0.12.16