Hardc0re Asked:2020-02-28 01:29:04 +0000 UTC2020-02-28 01:29:04 +0000 UTC 2020-02-28 01:29:04 +0000 UTC 用图解法求解LLP 772 有必要使用图形方法解决 ZLP，或者更确切地说，类比编写程序。 锻炼： 编程有几个问题： 将 x1 和 x2 代入一些值后，我们得到 3 条线的坐标 + 它们的方向。找出直线的交点。他们和方向将形成 ODZ。 在您需要绘制渐变之后，在我的例子中它将是 (2; 1) 并从中寻找最大值。但是在程序中如何实现呢？ алгоритм 1 个回答 Voted Best Answer Yuri Negometyanov 2020-02-28T19:25:08Z2020-02-28T19:25:08Z 求解 LLP 的图形方法基于构建完全位于第一象限的凸多边形（单纯形）。初始近似是整个第一象限，即 顶点为(0,0)、(Inf,0)、(0, Inf) 的三角形，其中Inf是要“切断”的无穷大。 “切断”的理想选择是形式为ax 1 + bx 2 <= c, (a>0, b>0, c>0) 的不等式，它消除了两个奇异顶点。在这种情况下，不存在这样的不等式，但存在第一个不等式(a 1 > 0, c 1 > 0)，以及第二个不等式，在乘以“-1”后得到(b 2 > 0, c 2 > 0),对应直线的交点M(x,y)位于第一象限。这意味着已经获得了具有顶点(0,0)、(c 1 /a 1 ,0)、(x,y)、(0,c 2 /a 2 ) 的单纯形。顶点按逆时针循环顺序排列，与存储它们的顺序相同。 每一个新的不等式都会剪掉单纯形上不满足它的相邻点群，并用一对新的不等式代替。如果我们将连接它与前一个和后一个顶点的直线方程附加到每个顶点，并保持顶点的循环顺序，则该算法很简单。 如果单纯形的所有顶点都是已知的，则其中一个顶点达到目标函数的最大值。出于实现方便的原因，可以选择起点，旁路方向——增加目标函数的方向。对于任何方向的旁路，都可以取第一个局部最大值。
求解 LLP 的图形方法基于构建完全位于第一象限的凸多边形（单纯形）。初始近似是整个第一象限，即 顶点为(0,0)、(Inf,0)、(0, Inf) 的三角形，其中Inf是要“切断”的无穷大。
“切断”的理想选择是形式为ax 1 + bx 2 <= c, (a>0, b>0, c>0) 的不等式，它消除了两个奇异顶点。在这种情况下，不存在这样的不等式，但存在第一个不等式(a 1 > 0, c 1 > 0)，以及第二个不等式，在乘以“-1”后得到(b 2 > 0, c 2 > 0),对应直线的交点M(x,y)位于第一象限。这意味着已经获得了具有顶点(0,0)、(c 1 /a 1 ,0)、(x,y)、(0,c 2 /a 2 ) 的单纯形。顶点按逆时针循环顺序排列，与存储它们的顺序相同。
每一个新的不等式都会剪掉单纯形上不满足它的相邻点群，并用一对新的不等式代替。如果我们将连接它与前一个和后一个顶点的直线方程附加到每个顶点，并保持顶点的循环顺序，则该算法很简单。
如果单纯形的所有顶点都是已知的，则其中一个顶点达到目标函数的最大值。出于实现方便的原因，可以选择起点，旁路方向——增加目标函数的方向。对于任何方向的旁路，都可以取第一个局部最大值。