问题标签 [simplex-algorithm]

I am trying to implement a simplex algorithm following the rules I was given at my optimization course. The problem is

All vectors are assumes to be columns, ' denotes the transpose. The algorithm should also return the solution to dual LP. The rules to follow are:

Here, A_J denotes columns from A with indices in J and x_J, x_K denotes elements of vector x with indices in J or K respectively. Vector a_s is column s of matrix A.

Now I do not understand how this algorithm takes care of condition x >= 0, but I decided to give it a try and follow it step by step. I used Matlab for this and got the following code.

Functions findpositive(x) and findnegative(x, S) return the first index of positive or negative value in x. S is the set of indices, over which we look at. If S is omitted, whole vector is checked. Semicolons are omitted for debugging purposes.

The problem I tested this code on is

The reason for zeros(1,3) and eye(3) is that the problem is inequalities and we need slack variables. I have set starting basis to [4 5 6] because the notes say that starting basis should be set to slack variables.

Now, what happens during execution is that on first run of while, variable with index 1 enters basis (in Matlab, indices go from 1 on) and 4 exits it and that is reasonable. On the second run, 2 enters the basis (since it is the smallest index such that c(idx) < 0 and 1 leaves it. But now on the next iteration, 1 enters basis again and I understand why it enters, because it is the smallest index, such that c(idx) < 0. But here the looping starts. I assume that should not have happened, but following the rules I cannot see how to prevent this.

I guess that there has to be something wrong with my interpretation of the notes but I just cannot see where I am wrong. I also remember that when we solved LP on the paper, we were updating our subjective function on each go, since when a variable entered basis, we removed it from the subjective function and expressed that variable in subj. function with the expression from one of the equalities, but I assume that is different algorithm.

Any remarks or help will be highly appreciated.

Objective function => x1 - 2x2
Subject to =>

Maximize?

convert to standard form :
Maximize -> -x1 + 2x2
Subject to ->

convert to slack form :

Basic solution (0,0,5,-2)

Can I found optimal solution in here? If not why?

我试图找出“算法简介，第 3 版”一书中的单纯形算法。“Initial-Simplex”程序以标准形式为输入，检查标准形式是否存在初始基本可行解。伪代码如下：

在第 2 行，它检查数组 b 中的最小变量是否大于或等于 0。如果不是，则构造一个 Laux 并执行一个枢轴以消除 b 中的负变量。然后在第 9 行，它显示基本解决方案对于 Laux 是可行的。问题是，如果最初在数组 b 中，有多个负变量怎么办？例如原点 b 是 [-2, -1, 3, 1]，那么在第 1 行，我们有 b[k]=-2，所以 k=0。但是执行完第4行到第9行后，b内还有一个负变量-1。在这种情况下，我们不能说基本的解决方案对 Laux 来说是可行的。总之，没有检查b中的所有变量是否为非负的机制，并且第4行到第9行不在循环内。该算法是否假设最初小于一个负变量在 b 内？

我正在阅读 Dasgupta-Papadimitriou-Vairani 的题为 Algorithms 的教科书中的单纯形算法

在每次迭代中，单纯形有两个任务： 1. 检查当前顶点是否最优（如果是，则停止）。2. 确定下一步要搬到哪里。

正如我们将看到的，如果顶点恰好在原点，这两个任务都很容易。如果顶点在别处，我们将变换坐标系以将其移动到原点！

首先让我们看看为什么起源如此方便。假设我们有一些通用的 LP

最大 c 转置 * x Ax <= bx >= 0

其中 x 是变量向量，x = (x1; : : : ; xn)。假设原点是可行的。那么它肯定是一个顶点，因为它是 n 个不等式 {x1>=0, ..., xn>=0 } 紧的唯一点。

现在让我们解决我们的两个任务。任务1：

当且仅当所有 ci <= 0 时，原点才是最优的

如果所有 ci <= 0，则考虑到约束 x>=0，我们不能指望更好的客观值。相反，如果某些 ci > 0，则原点不是最优的，因为我们可以通过提高 xi 来增加目标函数。

因此，对于任务 2，我们可以通过增加一些 ci > 0 的 xi 来移动。我们可以增加多少？直到我们遇到其他一些限制。也就是说，我们释放紧约束 xi >= 0 并增加 xi 直到一些其他不等式，以前松散，现在变得紧。

在那一点上，我们又恰好有 n 个紧不等式，所以我们处于一个新的顶点。

例如，假设我们正在处理以下线性程序。

单纯形可以从约束 4 和 5 指定的原点开始。要移动，我们释放紧约束 x2 >= 0。随着 x2 逐渐增加，它遇到的第一个约束是 -x1 + x2 <= 3，因此它必须在 x2 = 3 处停止，此时这个新的不平等很严重。因此，新顶点由方程 3 和方程 4 给出。

因此，如果我们在原点，我们知道该怎么做。但是如果我们当前的顶点 u 在其他地方呢？诀窍是将 u 转换为原点，方法是将坐标系从通常的 (x1, ..., xn) 转移到 u 的局部视图。这些局部坐标由（适当缩放的）距离 y1, ..., yn 到定义和包围 u 的 n 个超平面（不等式）组成：

具体来说，如果这些封闭不等式之一是 ai * x <= bi，那么从点 x 到那个特定“墙”的距离是 yi = bi - ai * x

这种类型的 n 个方程，每壁一个，将 yi 定义为 xi 的线性函数，并且这种关系可以反转以将 xi 表示为 yi 的线性函数。因此，我们可以根据 y 重写整个 LP。这并没有从根本上改变它（例如，最佳值保持不变），而是在不同的坐标系中表达它。修改后的本地 LP 具有以下三个属性：

修正后的局部 LP 具有以下三个性质： 1. 它包括不等式 y >= 0，它们只是定义 u 的不等式的变换版本。2. u 本身就是 y 空间的原点。3. 成本函数变为 max cu + ~cT * y，其中 cu 是目标函数在 u 处的值，~c 是转换后的成本向量。

我很难理解下面提到的上述语句中的技巧：

诀窍是将 u 转换为原点，方法是将坐标系从通常的 (x1, ..., xn) 转移到 u 的局部视图。这些局部坐标由（适当缩放的）距离 y1, ..., yn 到定义和包围 u 的 n 个超平面（不等式）组成：

作者在上述语句中将坐标系从“u”转移到局部视图是什么意思？

局部坐标由到 n 个超平面的距离组成是什么意思？

请解释

提前感谢您的时间和帮助

我试图估计y = m(xb)^n形式的幂律拟合参数(m, n, b)的估计中的误差/不确定性，我将其拟合到数据集。当我使用 scipy.optimize.minimize 中的Nelder -Mead 方法时，我得到一个最终的单纯形而不是hess_inv 输出。我想知道如何利用这个输出来估计输出参数的错误/不确定性。

在 scipy.optimize.minimize 中使用 Nelder-Mead 方法得到的输出如下：

这是问题陈述

一个印度农民有一块农田，比如说 L 平方公里长，想要播种小麦或水稻或两者兼而有之。农民有有限数量的 F 公斤化肥和 P 公斤杀虫剂。

每平方公里小麦需要 F1 公斤的肥料和 P1 公斤的杀虫剂。每平方公里水稻种植需要 F2 Kg 肥料和 P2 Kg 杀虫剂。令 S1 为出售一平方公里收获的小麦所获得的价格，而 S2 为出售一平方公里收获的大米所获得的价格。

您必须通过选择应该种植小麦和/或稻米的区域来找到农民可以获得的最大总利润。

例如：

L = 10 Km2，F = 10 Kg，P = 5 Kg，F1 = 2 Kg，P1 = 2 Kg，F2 = 3 Kg，P2 = 1 Kg，S1 = 14，S2 = 25。

在这种情况下，如果农民在 Km2 面积上只播种水稻，则将获得最大利润3.33，最大利润值为83.33。

输入格式

唯一的输入将由 9 个以空格分隔的整数组成，L, F, P, F1, P1, F2, P2, S1, S2

约束

输出格式

输出将是

• 最大利润修正高达 2 位数
• 小麦应种植的公里数 2 位数
• 以km 2 为单位的值，水稻应正确种植最多2 位数字。

对于问题输出中考虑的示例，将是83.33 0.00 3.33.

示例测试用例

输入

输出

解释

假设 L = 10 Km2，F = 10 Kg，P = 5 Kg，F1 = 2 Kg，P1 = 2 Kg，F2 = 3 Kg，P2 = 1 Kg，S1 = 14，S2 = 25。如果农民在 3.33 平方公里的土地上不种植小麦而种植水稻，则总利润最大，最大利润值为 83.33 。

我需要解决这个问题。但是，无法掌握语句本身。请帮我。

我正在尝试优化以下内容：人员（列 ID）应该转到 A:G 点之一。假设正好有两个人（一组 14 人）必须去 7 个地点之一。我想最小化所覆盖的距离的总和。

我想用二进制变量写一个线性规划问题。

是否可以在 R 中解决？

我正在尝试解决 Saul Grass 在他的书“线性规划图解指南”第 12 页的运输问题中描述的问题。

冰箱必须按
以下数量（10、8、7）运送到 3 家商店（S1、S2、S3）
从工厂 F1、F2 到商店的运输成本为：
F1（8、6、10）= 11（总计F1)
F2 (9,5,7) = 14 (F2 总出货量)

Saul Grass 给出了最小化的目标函数：

8x_11 + 6x_12 + 10x_13 + 9x_21 + 5x_22 + 7x_23

和约束 c 为：
x_11 + x_12 + x_13 + 0x_21 + 0x_22 + 0x_23 = 11
0x_11 + 0x_12 + 0x_13 + x_21 + x_22 + x_23 = 14
x_11 + 0x_12 + 0x_13 + x_21 + 0x_22 + 0x_23 = 20
x_1110 + x_1 + 0x_21 + x_22 + 0x_23 = 8
0x_11 + 0x_12 + x_13 + 0x_21 + 0x_22 + x_23 = 7

他最好的解决方案是 [10,1,0,0,7,7] ：

10 x 8x_11 + 1 x 6x_12 + 0 x 10x_13 + 0 x 9x_21 + 7 x 5x_22 + 7 x 7x_23 = 170

我试图用 scipy 解决这个问题，但得到的结果不如 Saul Grass 的解决方案（204 vs. 170）。我的解决方案有什么问题？

我的代码：

我的结果：

假设我们有一个(LP)至少有两个最优基B1和的线性规划B2。关联的对偶值是否B1等于关联的对偶值B2？换句话说，LP即使该程序承认不止一个最优基，我们是否可以将每个约束关联到唯一对偶值？

我已经得到了我的方程式和一切。我只是不知道如何迭代，即如何更新 A、b 和 c。我一直在尝试使用矩阵形式。如果有人可以帮助解决这个问题或表格形式，那就太棒了！我的问题很简单： min cx s,t Ax=b 其中这本身包括松弛变量，因此是初始 bfs 的明显选择。