Questão 751613

Seja o Problema de Fluxo a Custo Mínimo (PFCM), em que x_ij decide o fluxo no arco (i, j) da rede subjacente, descrita por um grafo G= (V,E). Neste problema, c_ij é o custo de transporte por unidade de fluxo no arco (i, j) e k_ij é a capacidade máxima de transporte do arco (i, j). Escrevendo o PFCM a seguir como um modelo de programação matemática, tem-se:

(1) \(\min z = \sum\limits_{(i,j) \in E} c_{ij}x_{ij}\)

sujeito a:

(2) \(\sum\limits_{(j,i) \in E} x_{ji} - \sum\limits_{(i,j) \in E} x_{ij} = d_i, \quad \forall i \in V\)

(3) \(x_{ij} \le k_{ij}, \forall (i,j) \in E\)

(4) \(x_{ij} \ge 0, \forall (i,j) \in E\)

Fonte: Banca Examinadora, 2026.

Denominando os preços duais das restrições (2) de u_i para cada vértice i do grafo, e os preços duais das restrições (3) de v_ij para cada arco (i, j), pode-se afirmar que a forma geral das inequações duais associadas a esse problema, seria dada por: