运筹优化学习15:求解线性规划的单纯形法【手把手计算,够你应付考试了,看不懂算我输】(上)

简介: 运筹优化学习15:求解线性规划的单纯形法【手把手计算,够你应付考试了,看不懂算我输】

本博主研究了一天没有搞明白,幸得大神指点迷津,现将学习过程记录如下

1 理论部分

1.1 单纯形表的要素含义解释

20191108144037152.png

1.2 计算步骤


2019110814425339.png

1.3 黄丽娟老师的课件

初始单纯形表


20191220223048136.png

计算检验数:20191220223209762.png

计算换出比率:20191220223251681.png

得到主元:

20191220223405480.png

做初等行变换:

20191220223554509.png

20191220223700279.png

2 计算示例

gif.png

2.1 初始单纯形表

【敲黑板:单位矩阵的检验数一定是0;单位矩阵对应的变量为基变量】


image.png

检验数的计算:

gif.png

gif.png

依次计算所有的检验数,选择其中检验数最大的变量作为入基变量,即gif.gif

分别计算b列与gif.gif列的比值,得到换入变量比率;

计算过程:

gif.gif

gif.gif 【分母为负数或0,比率用 - 标记】

gif.gif

因此我们确定出入基变量为gif.gif和出基变量gif.gif

2.2 第二次变换

要把系数矩阵中的gif.gif变换成单位矩阵

在初始单纯形表的基础上,

image.png

确定主元列为x_2,更新入基变量的gif.gif值;然后,将主元列化为单位向量,执行如下两步变换:

  1. 第三行 * (-1/2)加到第一行,得到变换后的第一行;
  2. 第三行 * (1/4)

得到更新后的单纯形表,

image.png

重新计算检验数和价值比率

image.png





相关文章
|
4月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
150 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
9月前
【编程题-错题集】非对称之美(找规律 / 贪心)
【编程题-错题集】非对称之美(找规律 / 贪心)
|
9月前
|
机器学习/深度学习 存储 供应链
【软件设计师备考 专题 】运算基本方法:预测与决策、线性规划、网络图、模拟
【软件设计师备考 专题 】运算基本方法:预测与决策、线性规划、网络图、模拟
130 0
|
机器学习/深度学习 人工智能 算法
强化学习从基础到进阶-常见问题和面试必知必答[2]:马尔科夫决策、贝尔曼方程、动态规划、策略价值迭代
强化学习从基础到进阶-常见问题和面试必知必答[2]:马尔科夫决策、贝尔曼方程、动态规划、策略价值迭代
|
算法
计算方法/数值分析 期末复习整理
计算方法/数值分析 期末复习整理
176 0
计算方法/数值分析 期末复习整理
|
决策智能
运筹优化学习15:求解线性规划的单纯形法【手把手计算,够你应付考试了,看不懂算我输】(下)
运筹优化学习15:求解线性规划的单纯形法【手把手计算,够你应付考试了,看不懂算我输】
|
算法 Python
蓝桥杯 每日一题 承压计算 深入分析
蓝桥杯 每日一题 承压计算 深入分析
118 0
蓝桥杯 每日一题 承压计算 深入分析
|
存储 算法
|
机器学习/深度学习 存储 算法
划重点!十分钟掌握牛顿法凸优化
之前,我发过一篇文章,通俗地解释了梯度下降算法的数学原理和推导过程,推荐一看。链接如下: 简单的梯度下降算法,你真的懂了吗?
509 0
划重点!十分钟掌握牛顿法凸优化
|
算法 开发者
算法编程题目精解征文开始啦!快来Show出你的最优思路
阿里云开发者社区在线编程平台征稿活动正式启动!秀思路,赢社区周边!
算法编程题目精解征文开始啦!快来Show出你的最优思路