Browse Prior Art Database

THE COMPLETE DUALIZED SYSTEM OF THE SIMPLEX METHOD

IP.com Disclosure Number: IPCOM000128842D
Original Publication Date: 1956-Aug-09
Included in the Prior Art Database: 2005-Sep-19
Document File: 4 page(s) / 25K

Publishing Venue

Software Patent Institute

Related People

Orchard-Hays, William: AUTHOR [+3]

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 µhi = ahi (i, h = 0, 1, ..., m)
i.e., the first m + 1 columns of aji. The inverse is denoted as usual by πih. 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 δhi. Then using ∆j0 on the right and the other rows ∆jk 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 xj ≠ 0 implies dj = 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 a0i 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 ∆j0. 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 aji, bi (i = 0, 1, ..., m; j = 0, 1, ..., n) where a0i = δ0i there exists a vector x satisfying [ Equation omitted ] such that [ Equation omitted ] then there exists a vector πi0 = 1 ) satisfying [ Equation omitted ] such that [ Equation omitted ] and moreover max x0 = min πi bi.

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