# 整数规划基础概念

### 什么是 (线性) 整数规划?

与线性规划不同, **整数规划 (Integer Programming)** 问题的解必须是整数. 比如当变量是人数时候, 分数解显然是不合理的. 当所有变量必须为整数时, 我们称该问题为纯整数规划. 当变量一部分必须为整数, 而另一部分可以为分数时候, 我们称该问题为 **混合整数规划 (Mixed Integer Programming)**

$$
\begin{aligned}
max \quad & c^{T}x \\
s.t \quad & Ax = b\\
\quad & x \in \mathbb{Z}
\end{aligned}
$$

在2.1中的例子中最优解为 (0.5, 8), $$x\_{1}$$ 不是整数, 所以不符合约束条件. 该例子的最优整数解为 (0, 8), 对应的目标函数是16

{% hint style="info" %} <mark style="color:red;">**定理**</mark> 对于同一个约束条件 $$Ax = b$$ 和同一个目标函数 $$\max c^{T}x$$. 设 $$OPT\_{LP}$$ 为线性规划的最优解, $$OPT\_{IP}$$ 为整数规划的最优解, 则 $$OPT\_{IP} \leq OPT\_{LP}$$
{% endhint %}


---

# 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/zheng-shu-gui-hua-ji-chu-gai-nian.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.