运筹学单纯形法求解线性规划问题_运筹学单纯形法计算步骤

运筹学单纯形法求解线性规划问题_运筹学单纯形法计算步骤线性规划是研究在一组线性不等式或等式约束下使得某一线性目标函数取最大(或最小)的极值问题。

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

运筹学——线性规划及单纯形法求解

 

1. 线性规划的概念

线性规划是研究在一组线性不等式或等式约束下使得某一线性目标函数取最大(或最小)的极值问题。

 

2. 线性规划的标准形

 

clip_image002

 

特点目标函数极大等式约束变量非负

clip_image004clip_image006

则线性规划标准形的矩阵表达式为:

 

clip_image008

约定:clip_image010

 

如何化标准形:

(I) 目标函数实现极大化,即clip_image012,令clip_image014,则clip_image016

(II)约束条件为不等式

约束条件为“clip_image018” 不等式,则在约束条件的左端加上一个非负的松弛变量;

约束条件为“clip_image020” 不等式,则在约束条件的左端减去一个非负的松弛变量。

(III)若存在无约束的变量clip_image022,可令clip_image024,其中clip_image026

 

3. 单纯形法求解

(I) 化为标准形(要求clip_image028),确定初始基clip_image030,建立初始单纯形表(假设A矩阵中存在单位矩阵);

 

clip_image032

(II)若clip_image034,则已得到最优解,停止。否则转入下一步;

(III)若在clip_image036中,存在clip_image038,而clip_image040,则无最优解,停止。否则转入下一步;

(IV)由clip_image042,确定clip_image022[1]为换入变量,按clip_image045规则

clip_image047

可确定clip_image049为换出变量;

(V)以clip_image051为主元进行迭代

即将clip_image053 迭代成clip_image055

并将单纯形表clip_image057列中的clip_image049[1]换成clip_image022[2],得到新的单纯形表;

重复(ⅱ)~(ⅴ)。

4. 单纯形法求解例示

 
 
 
  clip_image002[1]

 

 

clip_image063

 

clip_image065

 

clip_image067

 

clip_image069

 

clip_image071

 

clip_image073

 

clip_image075

 

clip_image077

 

两阶段法

第一阶段求初始基可行解:在原线性规划问题中加入人工变量,使约束矩阵出现单位子矩阵,然后以这些人工变量之和W求最小为目标函数,构造如下模型:

 
  clip_image079

 

对上述模型求解(单纯形法),若W=0,说明问题存在基本可行解,可以进行第二个阶段;否则,原问题无可行解,停止运算。

 

第二阶段:在第一阶段的最终表中,去掉人工变量,将目标函数的系数换成原问题的目标函数系数,作为第二阶段计算的初始表(用单纯形法计算)。

 

clip_image081

 

例:

第一阶段

 

clip_image083

第二阶段

 

clip_image085

∴最优解为(4 1 9 0 0),目标函数 Z = –2

 

退化: 即计算出的θ(用于确定换出变量)存在有两个以上相同的最小比值,会造成下一次迭代中由一个或几个基变量等于零,这就是退化(会产生退化解)。

虽任意换出变量,目标函数值不变,但此时不同的基却表示为同一顶点,其特例是永远达不到最优解。需作如下处理:

⑴. .当clip_image087中出现两个以上最大值时,选下标最小非基变量换入变量;

⑵.当θ中出现两个以上最小值时,选下标最小的基变量为换出变量。

参考文献:

[1] 《运筹学》教材编写组. 运筹学. 北京: 清华大学出版社.

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/166557.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号