I am dealing with a type of scheduling problem - we need to schedule $n$ courses with length $p_1$, ..., $p_n$ into three classes $S_1$, $S_2$, $S_3$ with the use of linear programming. I already did the primal program but don't know how to create the dual.
The primal program has variables:
- $x ≥ 0$ is the length of teaching
- $x_{i,k} ≥ 0$ for each i from {1, ..., n} and k from {1, 2, 3}
The objective function is min $x$ - we want the teaching to be as short as possible
The constraints are:
- $x_{1,1}$ = 1 because we have to have the first course in the first class
- $x_{i,1}$ + $x_{i,2}$ + $x_{i,3}$ = 1 because no class can be taught in more classes at the same time
- $x$ ≥ Σ $p_i$ * $x_{i,k}$ for each $i$ from {1, ..., n} and $k$ from {1, 2, 3} because the teaching will finish when the last course in one of the classes will finish
I believe that for the dual program, I want to maximize the number of classes used. So I created a variable $y_k$ for each class. The objective function will be max Σ $y_k$ for each $k$ from {1, 2, 3}
I am unsure how to continue and use the lengths of the courses in the dual program. Any hints?
I'm attaching the primal-dual table
Thanks in advance.
I'm renaming your single $x$ without subscript to $t$ for length of teaching for better clarity.
Hint:
Since the primal is:
$$\min z = t$$ $$\text{Subject to: }\qquad\qquad\qquad$$ $$x_{i1}+x_{i2}+x_{i3}=1\quad\forall i$$ $$x_{11}=1$$ $$ p_i(x_{i1} + x_{i2} + x_{i3}) - t\le 0 \quad\forall i$$ $$t\ge0,\quad x_{i1}, x_{i2}, x_{i3}\ge0\quad\forall i$$
Which is of the form: $$\min z = c^Tx$$ $$Ax\le b$$ $$x\ge0$$
The dual will be of the form: $$\max w = b^Ty$$ $$A^Ty\ge c$$ $$y\le0, \text{ and for some $y_i$ is unrestricted}$$
Try writing out the primal for say $n=5$, and then take the dual of that to see what properties are appearing to take form in the dual, and then abstract that dual to $n$. It may be helpful to write out the whole coefficient matrix and transposing it to understand what it'll look like for the dual.