线性规划单纯形法

1、线性规划的单纯形法控制理论与控制工程 20022025 陈惠英）摘要 ：本文通过使用 VISUAL BASIC 编程语言实现了单纯形表格法的运算，从而实现了求 得使满足约束条件下的目标函数的最大值。 对单纯形法做了简要的说明， 并简单地介绍了如 何运用本程序进行最优解的求取。关键词 ：基本变量，进入变量，退出变量，迭代，最优。一、基本原理 线性规划的数学模型表示如下：max z C T x 目标函数Ax B 约束条件A aij m nx x1, x2 .xn ； C c1, ； A aij m n ； B b1 , b2 .bn 求满足约束条件下的目标函数的最大值。（1）基本解如果考虑 Ax

2、B ，注意不等式可以变成等式，因此可以把 Ax B 的约束认为是标准约束。A m n， n m ，变量多于约束；如果 A的秩为 m ；从中选择 m m矩阵，线性无关， 构成 A0，如果 A中其余 n m列所对应的变量为 0，矩阵 B的 m列的对应变量为 xB，则 可写成： A0xB B， xB A 1B ，于是得到解 x ，我们称解为方程式 Ax B关于 A0的基 本解。（2）基本可行解 如果基本解中的每个变量都是非负，则称为基本可行解。（3）松弛变量 为了把不等式约束变成等式约束而引入的变量称为松弛变量。线性规划的单纯形法的基本观点： 从基本可行解的某个开始， 寻找使目标函数有较大增 加的另

3、一基本可行解，这样一步一步做下去，每一步使目标函数增大，最后得到最优解。 而单纯形表格法是主要针对由不等式变成等式约束的情况，先有新增的松弛变量为基本变 量，然后得到初始的基本可行解。1 置初始表 （1）基本变量x1x2xnxn 1xn 2xn mBbj /aijxb1xn 1a11a12a1n100b0xb2xn 2a21a22a11010b1xbmxn mam1am2a11001b1ZC1C2Cn0000表1（1）关键列（进入变量） 选择 C j 最负的那一列。（2）关键行 （ 退出变量 ）xbr /yrj min xbi / yij yij 0min xbi /aij aij 0（3）关

4、键行和关键列相交元称为主元用0 表示，将主元所在的其他元素用高斯消去法变成零。（4）重复上面步骤，直至最后一行基本变量的价值函数让它为零，那么非基本变量的价值 系数全为正（或零） ，则此时目标函数值达到最大。二、程序使用说明1.举例说明max f （x） 13x1 11x24x1 5x2 15005x1 3x2 1575x1 2x2 420x1 0,x2 01. 关键列x1x2x3x4x5Bx3451001500x4530101575x51200142013110000表2关键列是第一列。2 关键行由于1575/ 5为最小，所以到第 4列退出，第 1列进入。同时用 x4乘以 x3、 x5对应的值得如下表格。x1x2x3x4x5Bbj /aijx3013/514/5015001200 /13x113/501/501575525x507/501/5142075016/5013/504095表33 循环做以上两步。x1x2x3x4x5Bx30013/713/745x11002/73/7270x20101/75/77500015/716/74335表4从最后一行得出 4335 是所求的目标函数的最大值。2程序实现。（1）在程序中，行数的确定根据松弛变量的个数加1，列数的确定根据基本变量加松弛变量再加 1。根据上述实例，我们填入行数为4，列数为 6。2