The Dual Linear Programming Problem

*James D. Gaboardi*

*Florida State University*     |     *Department of Geography*

GNU LESSER GENERAL PUBLIC LICENSE

Version 3, 29 June 2007

Copyright (C) 2007 Free Software Foundation, Inc.

Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed.

Adapted from:

Daskin, M. S. 1995. Network and Discrete Location: Models, Algorithms, and Applications. Hoboken, NJ, USA: John Wiley & Sons, Inc.

1. Canonical Form

Maximize

        $\sum_{j}$  b_iU_i

Subject to

        $∑_{j}$ a_ijU_i ≤ c_j        ∀ j

        U_i ≥ 0                  ∀ i

where

         − i = a specific origin in a matrix

         − j = a specific destination in a matrix

         − c_j = user-defined constants

         − b_i = user-defined constants

         − a_ij = user-defined constants

         − U_i = dual decision variables

2. Standard Form

Maximize

        $\sum_{j}$  b_iU_i

Subject to

        $∑_{j}$ a_ijU_i + T_j = c_j        ∀ j

        U_i ≥ 0                          ∀ i

        T_j ≥ 0                          ∀ j

where

         − i = a specific origin in a matrix

         − j = a specific destination in a matrix

         − c_j = user-defined constants

         − b_i = user-defined constants

         − a_ij = user-defined constants

         − U_i = dual decision variables

         − T_j = slack variables