Problem # $1$

A student must select eight elective courses from four different departments, with at least one course from each department. The courses offered by each department are intended to maximize the $$knowledge$$ in a particular discipline. Departments measure knowledge on a $100-$point scale depending on the number of courses taken by the student, as shown in the following chart:

Department Number of courses

$12345$

I

II

III

IV $25$

$20$

$40$

$1050$

$70$

$60$

$2060$

$90$

$80$

$3080$

$100$

$100$

$40100$

$100$

$100$

$50$

The student would like to select her elective courses with the objective of maximizing the total knowledge she will gain. She has developed the following BACKWARD DYNAMIC PROGRAMMING FORMULATION:

Stage: n $=$ department number $($n $=1,2,3,4).$

State: sn $=$ number of courses that still need to be selected at the beginning of stage n$.$

Decision variable: xn $=$ number of courses selected from department n$.$

Immediate contribution: cn$($xn$)=$ knowledge to be gained by taking xn courses from department n$.$

State transformation: sn$+1=$ tn$($sn$,$xn$*)=$ sn $-$ xn$*.$

Optimal value function: fn$*($sn$)=$ maximum knowledge that can be gained from stage n $($site n$)$ to the last stage given that sn courses have to be selected at the beginning of stage n$.$

fn$*($sn$)=$ max $\{$ cn$($xn$)+$ fn$+1*($ sn$+1)\}.$

xn

Optimal solution: f$1*(8).$

The student is unable to complete the DYNAMIC PROGRAMMING PROCEDURE and needs your help to solve the problem.

$($a$)$ Complete the tables in stage $3,2,$ and $1.$

$($b$)$ Provide the optimal number of courses to be taken from each department and the maximum knowledge that will be gained. In your answer, you have to include the arguments $($in parenthesis$)$ of the optimal decisions and the optimal value function. If multiple optima exist, report all optimal solutions.

STAGE $4($INITIALIZATION$)$:

s$4$ f$4*($s$4)$ x$4*$ s$5=$ s$4$ x$4*$

$11010$

$22020$

$33030$

$44040$

$55050$

STAGE $3$:

s$3$ c$3($x$3)+$ f$4*($ s$4)$

f$3*($s$3)$

x$3*$

s$4=$ s$3$ x$3*$

x$3=1$ x$3=2$ x$3=3$ x$3=4$ x$2=5$

$240+10----5011$

$340+2060+10---7021$

$440+3060+2080+10--9031$

$5$

$6$

STAGE $2$:

s$2$ c$2($x$2)+$ f$3*($ s$3)$

f$2*($s$2)$

x$2*$

s$3=$ s$2$ x$2*$

x$2=1$ x$2=2$ x$2=3$ x$2=4$ x$2=5$

STAGE $1$:

s$1$ c$1($x$1)+$ f$2*($ s$2)$

f$1*($s$1)$

x$1*$

s$2=$ s$1$ x$1*$

x$1=1$ x$1=2$ x$1=3$ x$1=4$ x$1=5$

OPTIMAL SOLUTION:

x$1*()=$ x$2*()=$ x$3*()=$ x$4*()=$

f$1*()=$