# 整数规划/混合整数规划的应用

### **设施选址问题 (Facility Location Problem)**

通常如下提出: 假设有 $$n$$ 设施和 $$m$$ 客户. 我们希望选择

1. 开放哪些设施，以及
2. 使用哪些 (开放) 设施来供应 $$m$$ 为了以最低成本满足某些固定需求

我们引入以下符号:

* 让 $$f\_{i}$$ 表示开办设施 $i$ 的 (固定) 成本
* 让 $$c\_{ij}$$ 表示把产品从设施 $i$ 送到客户 $j$ 的成本
* 让 $$d\_{j}$$ 表示客户的需求
* 让 $$u\_{i}$$ 表示设施 $$i$$ 的容量, 对于无限容易设施选址问题, $$u\_{i} = \infty$$

**无限容量设施选址问题 (Uncapacitated Facility Location Problem)** 对应的数学规划模型由以下公式给出:

$$
\begin{aligned}
\min \quad & \sum\_{i=1}^{n} \sum\_{j=1}^{m} c\_{ij} d\_j y\_{ij} + \sum\_{i=1}^{n} f\_i x\_i \\
\text{s.t.} \quad & \sum\_{i=1}^{n} y\_{ij} = 1 \quad \forall j = 1, \dots, m \\
& \sum\_{j=1}^{m} y\_{ij} \leq M x\_i \quad \forall i = 1, \dots, n \\
& y\_{ij} \in {0, 1} \quad \forall i = 1, \dots, n \text{ and } j = 1, \dots, m \\
& x\_i \in {0, 1} \quad \forall i = 1, \dots, n
\end{aligned}
$$

**有限容量设施选址问题 (Capacitated Facility Location Problem)** 有限容量设施选址问题即在无限容量设施选址问题上多考虑了容量问题. 现在每个设施提供的服务是有限的, 其对应的数学规划模型由以下公式给出:

* 现在, $$y\_{ij}$$ 代表的是客户 $$m$$ 有多少比例的需求是被设施 $$n$$ 满足的

$$
\begin{aligned}
\min \quad & \sum\_{i=1}^{n} \sum\_{j=1}^{m} c\_{ij} d\_j y\_{ij} + \sum\_{i=1}^{n} f\_i x\_i \\
\text{s.t.} \quad & \sum\_{i=1}^{n} y\_{ij} = 1 \quad \forall j = 1, \dots, m \\
& \sum\_{j=1}^{m} d\_j y\_{ij} \leq u\_i x\_i \quad \forall i = 1, \dots, n \\
& y\_{ij} \geq 0 \quad \forall i = 1, \dots, n \text{ and } j = 1, \dots, m \\
& x\_i \in { 0, 1 } \quad \forall i = 1, \dots, n
\end{aligned}
$$


---

# 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-hun-he-zheng-shu-gui-hua-de-ying-yong.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.