An Approach to Linear Programming with 0–1 Variables

There are many decision making problems in which one seeks to choose the optimal package from a large number of indivisible independent proposals. For instance, jobbing firms have often to choose the most profitable package of orders from hundreds of potential ones under a great many restrictions on available resources, such as working time of different facilities, number of specialists, materials, etc. This article is intended to present a simple approach to obtaining approximate solutions for such problems. The fundamental concept is to make some ordinal scales among proposals. Steps of calculation are illustrated by examples of choosing the optimal mix of orders, one of which involves 60 candidate proposals with 30 restricting conditions. This method may be of great help when (1) the number of candidates and restricting conditions are large; (2) the estimated or raw data on required resources for proposals and their incremental profits contain some errors; and (3) the distribution of incremental profits and required resources of candidates differs greatly, say, week by week, and the limits on resources can be extended in a practical manner by carrying over an inventory of profitable backlog orders, reducing, in effect, the remaining capacity in the future week.

• 저널Management Science · 15(4) · B–196
• 토픽Optimization and Mathematical Programming · Control and Systems Engineering
• DOI10.1287/mnsc.15.4.b196
• 저자Shizuo Senju, Yoshiaki Toyoda