Automatic generation of linear programming problems for computer aided instruction

The paper presents a method for generating random linear programming problems with a previously selected type of solution. The user can choose a problem whose solution is unbounded, bounded for minima, maxima or both, unique or multiple, with given structure, at wish. Initially, the feasible solution of the LPP is generated as the sum of a linear space, a cone, and a polytope, depending on the desired properties of the solution. With the aim of obtaining a simple set of constraints, the generators of these three structures are selected as random vectors with integer simple components, the range of which can be given. Next, an objective function that satisfies the required conditions, i.e. leads to a solution of the desired type, is obtained. The generating algorithms have been implemented in Mathematica and some illustrative examples are given to clarify the generation process. With this tool, a LPP can be generated, according to the instructor requirements, where this is a human or an expert system. They can control student progress and generate a sequence of problems covering all possible cases, in steps of increasing difficulty. Combining this tool with another (also produced by the same authors) that solves the problems and explains the whole process, step by step, a computer aided module for learning LPP, which is completely autonomous, can be easily obtained.