# THE COMPLETE DUALIZED SYSTEM OF THE SIMPLEX METHOD

Original Publication Date: 1956-Aug-09

Included in the Prior Art Database: 2005-Sep-19

## Publishing Venue

Software Patent Institute

## Related People

Orchard-Hays, William: AUTHOR [+2]

## Abstract

The augmented tableau of the revised simplex method is further augmented to display all relationships involved. The simplex method is applied to the dual system to solve the primal system starting from a solution which is feasible for the dual. The simplex method works with m X m basis matrices drawn from columns of an m X n restraint matrix. In the algorithm with the product form of inverse, we expanded this, for convenience, to an (m + 1) X (m + 1) basis drawn from an (m + 1) X (n + 1) matrix, i.e. including the cost row. We will now show how this tableau can be embedded in a larger one, (m + n + 1) X (n + 1). In this form we will have equations (instead of inequalities) in both directions -- across and down. The value of the solution will appear explicitly as the common value of two linear forms. We continue in the notation of P-810 but without the iteration index t = 1, ..., T. For simplicity, let us assume the present basis is μ h i = a h i (i, h = 0, 1, ..., m) i.e., the first m + 1 columns of a j i . The inverse is denoted as usual by π i h . Then the pricing vector π i satisfies ( [ Equation no. ] 1) [ Equation omitted ] Let us use the (n + 1)-order identity matrix and denote it by [ Equation omitted ] to distinguish it from the (m + 1)-order identity δ h i . Then using Δ j 0 on the right and the other rows Δ j k on the left, (1) can be written ( [ Equation no. ] 2) [ Equation omitted ] The present solution vector β h satisfies [ Equation omitted ] that is [ Equation omitted ] Note that x j &neq; 0 implies d j = 0. Consequently [ Equation omitted ] identically for basic solutions. Therefore, since [ Equation omitted ] clearly [ Equation omitted ] . This observation enables us to incorporate all the quantities of the problem in a single tableau consisting of horizontal and vertical identities, as follows. [ Figure containing following caption omitted: [ Figure omitted ] ] We have written a 0 i in numerical form since it is always the same. Likewise π 0 = 1 always. This format makes it clear that what we did by incorporating the cost row in the restraint matrix was to create a new cost row which is simply Δ j 0 . We shall call the first m + 1 rows the primal system. It is now very easy to visualize the duality theorem which can be stated as follows.

**This text was extracted from a PDF file.**

**This is the abbreviated version, containing approximately 31% of the total text.**

__Page 1 of 4__THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

**THE COMPLETE DUALIZED SYSTEM OF THE
SIMPLEX METHOD **

William Orchard-Hays

P-916

August 9, 1956

The RAND Corporation 1700 MAIN ST., SANTA MONICA, CALIFORNIA

**SUMMARY **

The augmented tableau of the revised simplex method is further augmented to display all relationships involved. The simplex method is applied to the dual system to solve the primal system starting from a solution which is feasible for the dual. The simplex method works with m X m basis matrices drawn from columns of an m X n restraint matrix. In the algorithm with the product form of inverse, we expanded this, for convenience, to an (m + 1) X (m + 1) basis drawn from an (m + 1) X (n + 1) matrix, i.e. including the cost row. We will now show how this tableau can be embedded in a larger one, (m + n + 1) X (n + 1). In this form we will have equations (instead of inequalities) in both directions -- across and down. The value of the solution will appear explicitly as the common value of two linear forms.

We continue in the notation of P-810 but without the iteration index t = 1, ..., T. For simplicity, let
us assume the present basis is
µ_{h}^{i} = a_{h}^{i} (i, h = 0, 1, ..., m)

i.e., the first m + 1 columns of a_{j}^{i}. The inverse is denoted as usual by π_{i}^{h}. Then the pricing vector
π_{i} satisfies
( [ Equation no. ] 1) [ Equation omitted ]

Let us use the (n + 1)-order identity matrix and denote it by
[ Equation omitted ]
to distinguish it from the (m + 1)-order identity δ_{h}^{i}. Then using ∆_{j}^{0} on the right and the other rows
∆_{j}^{k} on the left, (1) can be written
( [ Equation no. ] 2) [ Equation omitted ]

The present solution vector β^{h} satisfies
[ Equation omitted ]

that is [ Equation omitted ]

Note that x^{j} ≠ 0 implies d_{j} = 0. Consequently
[ Equation omitted ]
identically for basic solutions. Therefore, since
[ Equation omitted ]
clearly
[ Equation omitted ] .

Rand Corporation Page 1 Aug 09, 1956

__Page 2 of 4__THE COMPLETE DUALIZED SYSTEM OF THE SIMPLEX METHOD

This observation enables us to incorporate all the quantities of the problem in a single tableau consisting of horizontal and vertical identities, as follows.

(Image Omitted)

We have written a_{0}^{i} in numerical form since it is always the same. Likewise π_{0} = 1 always. This
format makes it clear that what we did by incorporating the cost row in the restraint matrix was
to create a new cost row which is simply ∆_{j}^{0}. We shall call the first m + 1 rows the primal system.

It is now very easy to visualize the duality theorem which can be stated as follows. f, given a_{j}^{i}, b^{i}
(i = 0, 1, ..., m; j = 0, 1, ..., n) where a_{0}^{i} = δ_{0}^{i} there exists a vector x satisfying
[ Equation omitted ]
such that
[ Equation omitted ]
then there exists a vector π_{i} (π_{0} = 1 ) satisfying
[ Equation omitted ]
such that
[ Equation omitted ]
and moreover
max x^{0} = min π_{i} b^{i}.

For, suppose our basic solution is feasible and optimal. Then all d_{j} ≥ 0. But if the primal
equations were originally inequalities of...