Vietscholar forum - Xem bài viết đơn

**fool** · #2 (**permalink**) 07-07-2009

Xét flow set tại một nút: $X=\left\{ (x,y)\in\left\{ 0,1\right\} ^{N}\times\mathbb{R}_{+}^{N}:\sum_{j\in N}y_{j}\leq b,y_{j}\leq a_{j}x_{j},j\in N\right\}$ và $C \subseteq N$ là flow cover,

yj: luồng qua cung thứ j.
aj: luồng tối đa qua cung thứ j.
xj: 0 - nếu không có luồng qua cung thứ j - 1 nếu có luồng qua cung thứ j.
Cần chuyển không quá b đơn vị qua nút này theo các cung.

Dựa vào bdt bên trên hoặc cm trực tiếp, thu được bdt sau:

Đly: giả sử $C\subseteq N$ là flow cover với $\text{max}_{j\in C}a_{j}>\lambda$ .Bdt $\begin{equation}\sum_{j\in C}\left[y_{j}+(a_{j}-\lambda)^{+}(1-x_{j})\right]{\displaystyle \leq}b\end{equation}$ là 1 facet defining inequality cho conv(X).

Cái này tôi translate ra tiếng Việt nghĩa là nếu chưa bão hòa thì ta có thể gửi $(a_j - \lambda)^{+}$ đơn vị luồng trên mỗi cung chưa được sử dụng (các cung mà có y_j bằng 0 hay x_j = 0 tương ứng). Còn phần sau thì chưa (có thể đọc mục 9.2.3 - IP của Wosley về các pp cm).

Chắc biên dịch như thế là chính xác, nhưng nó còn có 1 version khác mạnh hơn nữa mà tôi mới đọc và chưa chứng minh và tất nhiên là chưa chuyển thành ý nghĩa cụ thể được (page 191. mục 9.4.1 . proposition 9.6 - Integer Programming, của Wosley).