# 割平面法

{% hint style="info" %}
**割平面法 (Cutting Plane Method)** 是一种优化算法, 广泛用于求解整数规划和混合整数规划问题
{% endhint %}

### 核心思想

逐步添加新的约束 (即“割”) 来裁剪可行区域, 从而排除不可行解, 最终达到整数解

***

### 算法过程

1. (初始化) 松弛原问题, 允许解是分数; 求解松弛后的问题得到解 $$x$$
2. (停止条件) 如果 $$x$$ 满足原问题约束, 则算法停止, 返回 $$x$$; 否则, 进行步骤3
3. (迭代过程) 添加一个线性不等式 ("割") 使得 $$x$$ 不满足, 但原问题的所有可行解满足, 返回步骤2

***

### Gomory割

* 让 $$x^{\*}$$ 表示松弛问题的最优解, $$B$$ 表示对应的基, $$N$$ 表示非基变量的集合
* 让 $$\overline{a\_{ij}} = (B^{-1}A\_{j})*{i}$$*,\_ $$\overline{a\_{i0}} = (B^{-1}b)\_{i}$$
* 由于松弛解不满足要求, 则考虑 $$\overline{a\_{i0}}$$ (一个不满足原约束的分数)
* 我们构建不等式 $$\sum\_{j\in N} (\lfloor \overline{a\_{ij}} \rfloor - a\_{ij}) x\_{j} \leq \lfloor \overline{a\_{i0}} \rfloor - a\_{i0}$$
* 我们添加一个一个新的松弛变量 $$x\_{k} \in \mathbb{Z\_{+}}$$: $$x\_{k} + \sum\_{j\in N} (\lfloor \overline{a\_{ij}} \rfloor - a\_{ij}) x\_{j} = \lfloor \overline{a\_{i0}} \rfloor - a\_{i0}$$
* 添加新约束重新计算松弛解, 不断重复这个过程直到找到符合原约束的解即为最优解


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yutians-organization.gitbook.io/yun-chou-xue-he-you-hua-dao-lun/zheng-shu-gui-hua-wen-ti/ge-ping-mian-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.