Graduate Thesis Or Dissertation
 

A matrix game approach to linear programming

Public Deposited

Downloadable Content

Download PDF
Request Accessible Version
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/d217qs396

Descriptions

Attribute NameValues
Creator
Abstract
  • It is the hope and expectation of many specialists in the area of linear programming that a major improvement in solution techniques for handling large-scale models with thousands of constraints will be developed in the near future. Although the present state of the art for solving linear programs is still firmly based on the simplex method, it is possible that major improvements might be achieved by utilizing another theory or technique. In recognition of the close relationship between linear programs and matrix games, it was surmised that the theory of the games could provide a way of developing an improved technique. This thesis deals with the exploration and potential contribution of the game theoretical approach to linear programming. It consists of three sections. The first part deals with the comprehensive relationship between matrix games and linear programs in terms of solution criteria. In order to do so, several processes for converting linear programs to matrix games are studied. One of these is selected as the basis for the conversion of the solution criteria for a matrix game to the solution criteria for a linear program. The solution criteria of a linear program thus obtained is verified by proving their equivalence to the simplex criteria. The second part deals with developing a new algorithm which utilizes the criteria obtained in the first part. This algorithm uses the basis updating scheme and unique pivot criteria. It is based on a pivot procedure which is similar to that employed in the simplex method. Then this algorithm is applied to solve matrix games through the conversion processes of matrix games to linear programs. The third part deals with validation and comparison of the new algorithm with other simplex algorithms through several test problems. The test problems were selected from textbooks. The programming of the new algorithm and testing of the problems were exercised on a CDC CYBER 70/Model 73. MPOS (Multi-Purpose Optimization System) was used for the two other simplex algorithms. This testing gave several useful results. First, the validity of the new algorithm was confirmed by its accurate solutions to all problems to which it was applied. Second, the testing revealed that computer space and machine time required to run the new algorithm are comparable to those of the simplex algorithms, and it is consequently believed that the new algorithm could be made more efficient through more advanced bookkeeping and adept programming. Third, the number of iterations and the rate of convergence for the new algorithm were essentially the same as the minimum iteration algorithm; therefore, it is reasonable to expect that the new algorithm could be refined to possibly provide a more efficient means for solving largescale linear programs. In the light of the potential benefits of the game theoretical approach to linear programming, more extensive studies in this area are recommended. The area of prime interest includes all existing solution methods for solving matrix games in conjunction with linear programs, as well as improvement of the presently developed algorithm.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Publisher
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0.82 on a Canon DR-9080C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Accessibility Feature

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details ParkTongkyu1980.pdf 2017-08-10 Public Download