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

大家好，又见面了，我是你们的朋友全栈君。

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

1. 线性规划的概念

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

2. 线性规划的标准形

clip_image002

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

令

clip_image004

clip_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_image063

clip_image065

clip_image067

clip_image069

clip_image071

clip_image073

clip_image075

clip_image077

两阶段法

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

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

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

clip_image081

例：

第一阶段

clip_image083

第二阶段

clip_image085

∴最优解为（4 1 9 0 0），目标函数 Z = –2

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

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

⑴. .当

clip_image087

中出现两个以上最大值时，选下标最小的非基变量为换入变量；

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

参考文献：

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

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/166557.html原文链接：https://javaforall.cn