假设我们有一个想要最大化的线性目标函数。所有变量都来自实数集。我们有一个形式的约束：

$$\max(x_1,x_2) + \max(x_3,x_4)\leq c\,, \text{ with } c\in\mathbb{R}$$

我们能否对其进行转换以获得线性程序？我已经阅读了表单的约束

$$\max(x_1,x_2)\geq x_3$$

是有问题的，因为这会转化为

$x_1\geq x_3$或 $x_2\geq x_3$

回到我的约束，我会做以下转换：

$m_1 + m_2\leq c$

$\max(x_1,x_2)\leq m_1$

$\max(x_3,x_4)\leq m_2$

它被转化为

$m_1 + m_2\leq c$

$x_1\leq m_1$

$x_2\leq m_1$

$x_3\leq m_2$

$x_4\leq m_2$

这对我来说似乎是合理的，因为没有引入 OR 并且两者对我来说都具有相同的含义。放大只是输入原始大小的多项式。

您能否用证明说明这种转换是否正确？我很想了解这些证明是如何工作的。我知道线性约束将凸可行集拆分为凸可行集和不可行集。我引入的约束是线性的，应该使可行集凸出。但这与我原来最大化的问题有什么关系呢？得到的线性规划的解会不会是原优化问题的最优解？