运筹优化学习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





相关文章
|
3月前
|
人工智能 算法 BI
第一周算法设计与分析 D : 两面包夹芝士
这篇文章介绍了解决算法问题"两面包夹芝士"的方法,通过找出两个数组中的最大最小值,计算这两个值之间的整数个数,包括特判不存在整数的情况。
|
6月前
数字信号处理期末复习——计算大题(一)
数字信号处理期末复习——计算大题(一)
108 0
数字信号处理期末复习——计算大题(一)
|
6月前
数字信号处理期末复习——计算小题(二)
数字信号处理期末复习——计算小题(二)
32 0
数字信号处理期末复习——计算小题(二)
|
3月前
|
人工智能 移动开发 算法
【2023华中杯数学建模】B 题 小学数学应用题相似性度量及难度评估详细建模方案及实现代码
本文提供了2023年华中杯数学建模B题的详细建模方案和实现代码,包括设计小学数学应用题相似性度量方法、建立题目难度评估数学模型、对题库进行相似性或难度分类,以及使用TF-IDF和K-Means聚类算法进行题目难度分析和相似题目推荐。
66 0
【2023华中杯数学建模】B 题 小学数学应用题相似性度量及难度评估详细建模方案及实现代码
|
3月前
|
算法 关系型数据库 程序员
第一周算法设计与分析:B : 如何溜的最快
这篇文章提供了解决算法问题"如何溜的最快"的方法,即计算从原点(0,0)到任意点(x,y)所需的最短步数,每步长度固定为R,通过特判和计算总距离除以步长向上取整来确定步数。
|
5月前
大学物理(上)-期末知识点结合习题复习(4)——质点运动学-动能定理 力做功 保守力与非保守力 势能 机械能守恒定律 完全弹性碰撞
大学物理(上)-期末知识点结合习题复习(4)——质点运动学-动能定理 力做功 保守力与非保守力 势能 机械能守恒定律 完全弹性碰撞
80 0
|
算法
计算方法/数值分析 期末复习整理
计算方法/数值分析 期末复习整理
155 0
计算方法/数值分析 期末复习整理
|
达摩院 算法 API
如何吃,少花钱又营养丰富?可用MindOpt线性规划求解来决策
营养调配问题的的目标是利用优化模型来设定每日饮食菜单,在满足各类营养的需求同时更能优化总成本
如何吃,少花钱又营养丰富?可用MindOpt线性规划求解来决策
|
决策智能
运筹优化学习15:求解线性规划的单纯形法【手把手计算,够你应付考试了,看不懂算我输】(下)
运筹优化学习15:求解线性规划的单纯形法【手把手计算,够你应付考试了,看不懂算我输】
运筹优化学习15:求解线性规划的单纯形法【手把手计算,够你应付考试了,看不懂算我输】(下)
|
存储 算法 C++