问题定义:
问题定义比较复杂,建议看《算法导论》里的线性规划一章。单纯型算法用于求解如下这类问题:
例:
求等式的最小值: -2X1– 3X2
且自变量满足如下约束:
X1 + X2 = 7
X1 – 2X2<= 4
X1>= 0
将约束等式转换为标准型:
标准型的条件:
1. 求目标函数的最大值
2. 每个自变量都大于等于零(非负约束)
3.约束不等式,只有最小化约束
转换结果如下:
max 2X1 – 3X2 + 3X3
并且满足:
X1 + X2- X3 <= 7
-X1 – X2+ X3 <= -7
X1 – 2X2+ 2X3 <= 4
X1, X2, X3 >= 0
将标准型转换成松弛型:
z = 2X1– 3X2 + 3X3
X4 = 7- X1 - X2
+ X3
X5 = -7+ X1 + X2 - X3
X6 = 4- X1 + 2X2 - 2X3
则基本变量为的下标集合 B = {4, 5, 6}
非基本变量的下标集合 N = {1, 2, 3}
C = [ 2 3 3 ]T
b = [ 7 -7 4 ]T
v = 0
具体实现时,将 A, b, C, v都存储在一个数组中
data
|
0v
|
2c
|
-3c
|
3c
|
7b
|
1A
|
1A
|
-1A
|
-7b
|
-1A
|
-1A
|
1A
|
4b
|
1A
|
-2A
|
2A
|
代码如下:
分享到:
相关推荐
1. 线性规划 - 单纯形法 1. 线性规划 - 单纯形法(续一) 1. 线性规划 - 单纯形法(续二) 1. 线性规划 - 单纯形法(续三) 1. 线性规划
北京科技大学运筹学用C#窗体应用程序编写的单纯型算法模拟,包括对偶规划算法和一般两阶段算法
这是一个老师布置的作业程序,我是用C++ Builder 4.0写的. 如果学过<线性规划>的话,这个程序要干什么大家都知道,就是求解线性规划问题,即在一组线性不等式或等式组的约束条件下求某个线性函数的最值问题。
单纯形法是解决线性规划问题的一个有效的算法。线性规划就是在一组线性约束条件下,求解目标函数最优解的问题。资源中包含了实现计算单纯形表的Java代码。
将线性规划问题转化为标准型,求minz转化为求max-z 以下图为例 初始化 import numpy as np class Simplex(object): #构造函数(初始化函数) def __init__(self,z,B,bound): self.X_count=len(z) #变量个数 ...
是单纯型算法的完整实现,希望对需要的朋友有所帮助。
1.3 对偶单纯型算法 1.4 灵敏度分析及影子价格 1.5 用MATLAB优化工具箱解线性规划 1.6 习题 第2章 整数线性规划 2.1 割平面法 2.2 分枝定界法 2.3 习题 第3章 无约束优化 3.1 数学预备...
用单纯形算法计算线性规划的C语言编程的源代码
1.3 对偶单纯型算法 1.4 灵敏度分析及影子价格 1.5 用MATLAB优化工具箱解线性规划 1.6 习题 第2章 整数线性规划 2.1 割平面法 2.2 分枝定界法 2.3 习题 第3章 无约束优化 3.1 数学预备...
线性规划的基本理论与单纯型算法、对偶理论与对偶单纯型算法,整数规划的割平面算法与分枝定界算法,非线性规划的最优性条件与直线搜索方法、共轭梯度方法、可行下降方法与罚函数方法,动态规划的最优性原理与多种...
线性规划的基本理论与单纯型算法、对偶理论与对偶单纯型算法,整数规划的割平面算法与分枝定界算法,非线性规划的最优性条件与直线搜索方法、共轭梯度方法、可行下降方法与罚函数方法,动态规划的最优性原理与多种...
针对漂移型灰色二层线性规划,基于单纯形法提出了一种具有全局收敛性质的算法来求解该问题.用下层的Kuhn-Tucker条件代替下层问题,将灰色二层线性规划转化为灰色单层规划问题,利用对偶理论将该单层规划转化为一系列...
用matlab实现单纯形算法。 单纯形算法主要是用来解决大型线性规划方程组的方法。
线性规划的基本理论与单纯型算法、对偶理论与对偶单纯型算法,整数规划的割平面算法与分枝定界算法,非线性规划的最优性条件与直线搜索方法、共轭梯度方法、可行下降方法与罚函数方法,动态规划的最优性原理与多种...
线性规划的基本理论与单纯型算法、对偶理论与对偶单纯型算法,整数规划的割平面算法与分枝定界算法,非线性规划的最优性条件与直线搜索方法、共轭梯度方法、可行下降方法与罚函数方法,动态规划的最优性原理与多种...
线性规划的基本理论与单纯型算法、对偶理论与对偶单纯型算法,整数规划的割平面算法与分枝定界算法,非线性规划的最优性条件与直线搜索方法、共轭梯度方法、可行下降方法与罚函数方法,动态规划的最优性原理与多种...
线性规划的基本理论与单纯型算法、对偶理论与对偶单纯型算法,整数规划的割平面算法与分枝定界算法,非线性规划的最优性条件与直线搜索方法、共轭梯度方法、可行下降方法与罚函数方法,动态规划的最优性原理与多种...
线性规划的基本理论与单纯型算法、对偶理论与对偶单纯型算法,整数规划的割平面算法与分枝定界算法,非线性规划的最优性条件与直线搜索方法、共轭梯度方法、可行下降方法与罚函数方法,动态规划的最优性原理与多种...
单纯形法是求解线性规划问题最常用、最有效的算法之一;如果线性规划问题的最优解存在,则一定可以在其可行区域的顶点中找到。基于此,单纯形法的基本思路是:先找出可行域的一个顶点,据一定规则判断其是否最优;若...
当决策变量个数n和约束条件个数m较大时,单纯形法是求解线性规划问题的通用方法。 从线性方程组找出一个个的单纯形,每一个单纯形可以求得一组解,然后再判断该解使目标函数值是增大还是变小了,决定下一步选择的...