TEXAS A&M UNIVERSITY
CIVIL ENGINEERING DEPARTMENT
STRUCTURAL SYSTEMS 979/845-4395
COLLEGE STATION, TEXAS 77843-3136 Fax 979/845-6156
August 26, 1990
Mr. Jim Ridgeway Re: Problem 5.64
Bryan Construction Co., Inc.
1400 South East Bypass
Bryan, Texas 77801
Solution (perhaps) is here. Work it first before you check your solution.
Dear Jim:
I have received your request for an optimum solution to your problem regarding bids made to your company from various contractors.
As I understand it, you have a list of contractors who are bidding on one of your jobs. Each contractor may bid on the entire job, as well as being permitted to bid on individual parts of the total job. For example, contractor A may bid 16 million to do the entire job, consisting of parts 1,2,3,4,5,6,7 and 8. He may also bid on just parts 1,2 and 3 (7 million), or on parts 4,5,6,7 and 8 (9 million), or on parts 1,3 and 8 (3 million). A list of the contractors you gave me over the phone, and their bids are shown below:
Contractor | Job Part Bid | Amount | |||||||
A0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 16 |
A1 | 1 | 2 | 3 | 7 | |||||
A2 | 4 | 5 | 6 | 7 | 8 | 10 | |||
A3 | 1 | 3 | 8 | 3 | |||||
B0 | 1 | 4 | 5 | 7 | 4 | ||||
B1 | 2 | 3 | 2 | ||||||
C0 | 3 | 5 | 4 | ||||||
C1 | 1 | 6 | 4 | ||||||
C2 | 2 | 3 | 4 | 8 | 8 | ||||
C3 | 6 | 7 | 2 | ||||||
D0 | 1 | 2 | 3 | 5 | 2 | ||||
D1 | 4 | 5 | 7 | 3 |
What a mess! I think that you should just make them bid on each piece individually and forget it. However, I do understand that bidding in groups of things that they know how to do best would save them (and you) a lot of money. The problem looks rather like an assignment problem, except that in this case not every machine is going to get to do a job, and there’s no way that some of the jobs aren’t going to be assigned twice. Some practical solution to this will have to be suggested. Also we have the problem of making absolutely sure that every job gets done at least once. Then of course we need to reduce your costs as much as possible.
Additionally, I understand that since this is a government job, you must assign at least 20% of the total monetary award to minority contractors. You mentioned that bidders B and C were minority owned. Also, contractor C, although a real whiz at this type of work, will be unable to be bonded for over 10 million dollars, because of his small size. Also, contractor B has limited personnel, and could only handle a single job, even if he got two of them. Finally, you mentioned that regardless of the costs, bidder D is a subsidiary of your company, and that you wish to assign at least one of the jobs to him to keep your people working.
As far as I can tell, we should be able to handle all of these requirements using linear programming, and we will proceed at once. I look forward to working with you on this project.
Very truly yours,
Lee L. Lowery, Jr., P.E.
Note to class:
Note that it may be cheaper to let two contractors do one job twice! Example:
Contractor | Do job 1? | Do job 2? | Do job 3? | Bid Price ($) |
A | Yes | Yes | Yes | 800,000 |
B | Yes | Yes | No | 200,000 |
C | No | Yes | Yes | 300,000 |
As you see, it would actually be less expensive to give B and C the jobs, even though job 2 would be done twice. Actually, you can always renegotiate with the two contractors to see which will knock off the most money to get out of doing Job 2. Thus you should not try to force each job be done only once, as that may not be in your best economic interest!