Browse Prior Art Database

Matrix Generator for Linear Programming Transportation and Machine Loading Problems

IP.com Disclosure Number: IPCOM000075036D
Original Publication Date: 1971-Jul-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 2 page(s) / 23K

Publishing Venue

IBM

Related People

Gleiberman, L: AUTHOR [+2]

Abstract

This program generates linear programming problems of realistic structure, and generates them in a fashion that guarantees the existence of a feasible solution. The problems that are generated can be either "transportation" problems or "Machine loading" problems, and these problems are thus useful as test cases not only for general LP programs, but also for particular programs such as transportation and machine loading programs.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 79% of the total text.

Page 1 of 2

Matrix Generator for Linear Programming Transportation and Machine Loading Problems

This program generates linear programming problems of realistic structure, and generates them in a fashion that guarantees the existence of a feasible solution. The problems that are generated can be either "transportation" problems or "Machine loading" problems, and these problems are thus useful as test cases not only for general LP programs, but also for particular programs such as transportation and machine loading programs.

The mathematical form of the problems generated is as follows:

(Image Omitted)

To cause the problems to be realistic, the X(ij)'s are not all generated; most are generally to be considered prohibited. The proportion of all possible ones that are to be generated is specified as an input parameter, and a random number generator is used to choose which particular ij combinations are generated, subject to the condition that for every value of j at least one X(ij)is generated. These rules are necessary for realism and for feasibility.

The values of C(ij) and D(j) can each be either specified by the user, or automatically generated using a random number generator to produce either real or integer numbers according to a user-specified statistical distribution. The A(ij)'s can be generated similarly or optionally, can all equal 1 to yield a transportation problem. To ensure feasibility, the S(i)'s can be generated by the following algorithm:

Initially set each S(i...