线性规划中的单纯形法

此宏可使用单纯形的修订形式来查找线性规划的最优解。线性规划 (LP) 用于处理只具有线性项的目标函数,并且假定只存在线性约束。

通常,如果约束条件的数目远小于决策变量的数目,则单纯形的原始形式将很低效。

目标函数可以最大化或最小化数学函数,如表示利润或成本的函数。优化通常是带约束的,即最优解必须位于特定范围内,而该范围通常由可用资源数量或项目预算来定义。

下载宏

确保 Minitab 知道可在何处找到您下载的宏。选择工具 > 选项 > 常规。在宏位置下,浏览到您保存宏文件的位置。

重要信息

如果您使用较低版本的 Web 浏览器,则在您单击下载按钮时,此文件可能会在 Quicktime 中打开,因为 Quicktime 与 Minitab 宏使用相同的 .mac 文件扩展名。要保存此宏,请右键单击下载按钮并选择目标另存为

必需输入

  • 包含目标函数系数的列。
  • 与目标函数的每个元素对应的列(包含变量、等号和结果)。这组列中的每行可确定最优的约束。

下面的示例取自 Hillier 和 Lieberman 的文章,它表示 Wyndor Glass Co 的两个产品(x1 和 x2)的制造。这三项约束分别表示了该公司的三家工厂在产品 1 (x1) 和产品 2 (x2) 的生产中使用资源的能力。

MAXIMIZE Profit = 3x1 + 5x2(目标函数)

受约束于:

x1   <= 4 (工厂 1)
  2x2 <= 12 (工厂 2)
3x1 +2x2 <= 18 (工厂 3)

x1 ≥ 0, x2 ≥ 0(非负约束)

应在 Minitab 工作表中输入系数、等号和结果,如下所示:

C1 C2 C3 C4 C5
x1 x2 不等 结果 目标
1 0 <= 4 3
0 2 <= 12 5
3 2 <= 18  

可选输入

MIN
默认情况下,该宏将会计算最大化问题。如果希望将目标函数最小化,请在主命令后输入一个分号,然后在第二行中输入 MIN 命令,并使用句号(“.”)表示命令结束。

运行宏

假设您的数据按以上所述组织。要运行此宏,请选择编辑 > 命令行编辑器,然后键入:

%SIMPLEX C1-C2 C4 C5; 
INEQ C3。

单击提交命令

更多信息

通常情况下,会指定 n + 2 列用于将问题表达为公式。主命令中输入的最后一个参数与包含目标函数系数的列相对应。倒数第二个参数要求使用可指定问题中所有不等式右侧的列(非负除外,因为这是默认假定的)。前 n 列指定了所有 a11*x1 + a12*x2 + ... + a1n*xn 类型的线性约束的系数 (a11, a12,...,a1n)。

最后,如果所有不等式都是“<=”类型,则不必进行任何操作;否则,请在一列中为所有约束指定符号。您可以输入以下任意符号:>=、>、≥、≤、<=、<、=。

有关此算法的更多技术细节,请参阅:

Bazaraa, M.S.、Jarvis, J.J. 和 Sherali, H.D。“Linear Programming and Network Flows”(线性规划和网络流),第四版。John Wiley & Sons,新泽西,2010 年。

使用此网站,即表示您同意对数据分析和个性化内容使用 Cookie。  请阅读我们的政策