Question

The Valley Research Inc. is contemplating a research and development (R&D) program encompassing five potential research projects named 1, 2, 3, 4, and 5. All the projects are expected to go on simultaneously. The company is constrained from embarking on all projects by the number of scientists it has and the budget available for R&D projects. The company has 23 scientists and $300,000 (three hundred thousand dollars) budgeted for R&D projects. Furthermore, since projects 2 and 5 require the involvement of the same scientists, both of them would not be selected, but either may or may not be selected. The Table below shows the expenses in thousands of dollars, the number of scientists required, and the estimated profit in millions of dollars associated with each project.

(a).       Formulate the integer programming model for this problem that will maximize profit. That is, you will define the decision variables, state the objective function, and thirdly, state the constraints.(Hint: This is a 0-1 integer programming problem).

(b).       Use the computer software (QM for Windows or its equivalent) to determine the integer optimal solution. From your optimal solution determine the following.

         (i)     List the optimal projects to be selected for execution.

         

         (ii)    The optimal total profit from all the selected projects.

Project	Expense ($)	Scientists Required	Estimated Profit ($Millions) ($1,000,000)
1	60,000	7	3.0
2	90,000	10	7.0
3	45,000	5	2.5
4	47,000	6	1.6
5	80,000	4	5.5

Answer 1

a) Let P1, P2, P3, P4 and P5 denote if Projects 1,2,3,4, and 5 are selected or not. If the value of these variables is 1 that means the particular project is selected and if it is 0, that means the project is not selected. Thus each of these variables is binary and can be either 0 or 1. Thus the decision variables are P1, P2, P3, P4 and P5.

The objective function, Z is to maximize the profit and this is given by below equation

Z = 3P1+7P2+2.5P3+1.6P4+5.5P5

The objective function need to be maximized subject to below constraints

Number of scientists cannot be more than 23. Hence we have the below constraint

7P1+10P2+5P3+6P4+4P5 23

Total expense cannot be more than the budget $300000. Hence we have the below constraint

60000P1+90000P2+45000P3+47000P4+80000P5 300000

Also as Project 2 and Project 5 cannot be both selected together, which means only one of P2 or P5 can be 1. Hence we have the below constraint

P1+P5 1

As specified at the start each of the variables are binary and can only take a value of 0 or 1 which is another constraint.

b) The problem is formulated in excel as below. The below 2 images show the formulation as well as the formulas used

Post these the solver parameters need to be entered as per the below image.

Once this is done, click on solve. The solver will solve the problem and show the message stating the same. Click on ok. The excel will now have the final solution as per below image.

Hence we can see from above that the optimal projects for selection are Projects 1, 3, 4 and 5.

The optimal total profit from the selected projects is $12.6 million dollars.