Electronics Company

Electronic

Electronics Company
Problem Statement
An electronics company has a contract to deliver 20,000 radios within the next four weeks. The client is willing to pay $20 for each radio delivered by the end of the first week, $18 for those delivered by the end of the second week, $16 by the end of the third week, and $14 by the end of the fourth week. Since each worker can assemble only 50 radios per week, the company cannot meet the order with its present labor force of 40; hence it must hire and train temporary help. Any of the experienced workers can be taken off the assembly line to instruct a class of 3 trainees; after one week of instruction, each of the trainees can either proceed to the assembly line or instruct additional new classes. At present, the company has no other contracts; hence some workers may become idle once the delivery is completed. All of them, whether permanent or temporary, must be kept on the payroll 'til the end of the fourth week. The weekly wages of a worker, whether assembling, instructing, or being idle, are $200; the weekly wages of a trainee are $100. The production costs, excluding the worker's wages, are $5 per radio.

Notation




     Week   # Experienced   # Assemblers   # Trainees 


        1              E1             A1           T1


        2              E2             A2           T2


        3              E3             A3           T3


        4              E4             A4           T4

Profit
The profit made for the company, by each assembler, during a week is




     Week    Profit per assembler


     1       (20 - 5) * 50  = 750


     2       (18 - 5) * 50  = 650


     3       (16 - 5) * 50  = 550


     4       (14 - 5) * 50  = 450

The total profit over the four week period is




     z = 750 * A1 - 200 *  E1 - 100 * T1


       + 650 * A2 - 200 *  E2 - 100 * T2


       + 550 * A3 - 200 *  E3 - 100 * T3


       + 450 * A4 - 200 *  E4 - 100 * T4

Experienced Employee Relation
The relationship between the number of experienced employees between weeks is




     Constraint                Dual Variable


     E1               = 40     (e1)


     E2  -  E1 -  T1  = 0      (e2)


     E3  -  E2 -  T2  = 0      (e3)


     E4  -  E3 -  T3  = 0      (e4)

Assembler and Trainer constraint
The constraint on the number of assemblers and trainer during week one is A1 + T1/3 <= E1. A similar constraint holds for the other weeks. As part of standard primal form, this becomes:




     Constraint                Dual Variable 


     - E1 +  A1 +  T1/3  <= 0  (i1)


     - E2 +  A2 +  T2/3  <= 0  (i2)


     - E3 +  A3 +  T3/3  <= 0  (i3)


     - E4 +  A4 +  T4/3  <= 0  (i4)

Total Number of Radios
The total number of radios produced is




     Constraint                                            Dual Variable


     50 * A1 + 50 * A2 + 50 * A3 + 50 *  A4  = 20,000      (r)

Dual Problem
Using this notation, the dual problem is




     minimize     40 * e1 + 20000 * r


     subject to   i1 + 50 * r   >=  750                (A1)


                  i2 + 50 * r   >=  650                (A2)


                  i3 + 50 * r   >=  550                (A3)


                  i4 + 50 * r   >=  440                (A4)


                  e1 - e2 - i1  >= -200                (E1)


                  e2 - e3 - i2  >= -200                (E2)


                  e3 - e4 - i3  >= -200                (E3)


                  e4      - i4  >= -200                (E4)


                  - e2 + i1 / 3 >= -100                (T1)


                  - e3 + i2 / 3 >= -100                (T2)


                  - e4 + i3 / 3 >= -100                (T3)


                  i4 / 3        >= -100                (T4)

Solution




%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%



Load Avg: ( 1.17 , 1.59 , 2.19 )

Coin LP version 1.02.02, build Mar 20 2006

command line - /home/neos/neos-bin/clp clp.mps - 

At line 4 NAME          Electron

At line 5 ROWS

At line 16 COLUMNS

At line 67 RHS

At line 70 ENDATA

Problem Electron has 9 rows, 12 columns and 26 elements

Model was imported from ./clp.mps in 0 seconds

Switching to line mode

Clp:Clp:Clp:Presolve 5 (-4) rows, 7 (-5) columns and 17 (-9) elements

Perturbing problem by 0.001 % of 61.0056 - largest nonzero change 2.15098e-05 (% 6.16904e-05) - largest zero change 0

0  Obj -32000 Primal inf 458.881 (1) Dual inf 2.99952e+10 (4)

7  Obj 127000

Optimal - objective value 127000

After Postsolve, objective 127000, infeasibilities - dual 0 (0), primal 0 (0)

Optimal objective 127000 - 7 iterations time 0.002, Presolve 0.00

Clp:

      0 E1                   40                      0

      1 A1                   10          6.9277917e-14

      2 T1                   90           4.146683e-14

      3 E2                  130         -2.8421709e-14

      4 A2                  130          1.2612134e-13

      5 T2                    0             -154.16667

      6 E3                  130                      0

      7 A3                  130          6.9277917e-14

      8 T3                    0             -208.33333

      9 E4                  130                      0

     10 A4                  130          4.0856207e-14

     11 T4                    0                 -162.5

Clp:



%%%%%%%%%%%%%%%%%%%% CLP Results %%%%%%%%%%%%%%%%%%%%

The primal solution above determined using Clp and the Neos input file below is




     E = ( 40 , 130 , 130 , 130 )^T


     A = ( 10 , 130 , 130 , 130 )^T


     T = ( 90 ,   0 ,   0 ,   0 )^T

The dual solution is (could be obtained by solving the dual problem)




     e = (    550 ,  262.5 ,     75 ,  -12.5 )^T 


     i = (  487.5 ,  387.5 ,  287.5 ,  187.5 )^T 


     r = 5.25

Checking Solution

Check primal equality constraints 40 = E1 = 40 0 = E2 - E1 - T1 = 130 - 40 - 90 0 = E3 - E2 - T2 = 130 - 130 - 0 0 = E4 - E3 - T3 = 130 - 130 - 0 20000 = 50 * (A1 + A2 + A3 + A4) = 50 * (10 + 130 + 130 + 130)
Check primal inequality constraints 0 >= - E1 + A1 + T1/3 = - 40 + 10 + 90/3 0 >= - E2 + A2 + T2/3 = - 130 + 130 + 0/3 0 >= - E3 + A3 + T3/3 = - 130 + 130 + 0/3 0 <= - E4 + A4 + T4/3 = - 130 + 130 + 0/3
Value of the primal objective z = 750 * A1 - 200 * E1 - 100 * T1 + 650 * A2 - 200 * E2 - 100 * T2 + 550 * A3 - 200 * E3 - 100 * T3 + 450 * A4 - 200 * E4 - 100 * T4 = 750 * 10 - 200 * 40 - 100 * 90 + 650 * 130 - 200 * 130 - 100 * 0 + 550 * 130 - 200 * 130 - 100 * 0 + 450 * 130 - 200 * 130 - 100 * 0 = 127000
Check dual equality constraints (there are none because all of the primal variables are constrained to be positive).
Check dual inequality constraints: A1: 750 <= i1 + 50 * r = 487.5 + 50 * 5.25 = 750 A2: 650 <= i2 + 50 * r = 387.5 + 50 * 5.25 = 650 A3: 550 <= i3 + 50 * r = 287.5 + 50 * 5.25 = 550 A4: 450 <= i4 + 50 * r = 187.5 + 50 * 5.25 = 450 E1: -200 <= e1 - e2 - i1 = 550 - 262.5 - 487.5 = -200 E2: -200 <= e2 - e3 - i2 = 262.5 - 75 - 387.5 = -200 E3: -200 <= e3 - e4 - i3 = 75 + 12.5 - 287.5 = -200 E4: -200 <= e4 - i4 = -12.5 - 187.5 = -200 T1: -100 <= - e2 + i1 / 3 = - 262.5 + 487.5 / 3 = -100 T2: -100 <= - e3 + i2 / 3 = - 75 + 387.5 / 3 = 54.167 T3: -100 <= - e4 + i3 / 3 = + 12.5 + 287.5 / 3 = 108.33 T4: -100 <= i4 / 3 = 187.5 / 3 = 62.5
Check dual objective q = 40 * e1 + 20000 * r = 40 * 550 + 20000 * 5.25 = 127000

Neos Input File




<document>





<category>lp</category>


<solver>Clp</solver>


<inputMethod>MPS</inputMethod>





<comments><![CDATA[


Week   # Experienced   # Assemblers   # Trainees 


   1              E1             A1           T1


   2              E2             A2           T2


   3              E3             A3           T3


   4              E4             A4           T4





Profit


z = 750 * A1 - 200 *  E1 - 100 * T1


  + 650 * A2 - 200 *  E2 - 100 * T2


  + 550 * A3 - 200 *  E3 - 100 * T3


  + 450 * A4 - 200 *  E4 - 100 * T4





Constraint                             Dual Variable


50 * (A1 + A2 + A3 + A4) = 20,000      (r)


E1                       = 40          (e1)


E2  -  E1 -  T1          = 0           (e2)


E3  -  E2 -  T2          = 0           (e3)


E4  -  E3 -  T3          = 0           (e4)


- E1 +  A1 +  T1/3      <= 0           (i1)


- E2 +  A2 +  T2/3      <= 0           (i2)


- E3 +  A3 +  T3/3      <= 0           (i3)


- E4 +  A4 +  T4/3      <= 0           (i4)





Name the equations by the corresponding dual variables


(except for the objective which is named $pre z$$).


]]></comments>





<MPS><![CDATA[*


*Op Name0---  Name1---  Value1------


*23 56789012  56789012  567890123456


NAME          Electron


ROWS


 N  z


 E  r


 E  e1


 E  e2


 E  e3


 E  e4


 L  i1


 L  i2


 L  i3


 L  i4


COLUMNS


*Op Name0---  Name1---  Value1------


    E1        z         -200


    E1        e1        1


    E1        e2        -1


    E1        i1        -1


*


    A1        z         750


    A1        r         50


    A1        i1        1


*


    T1        z         -100


    T1        e2        -1


    T1        i1        .3333333333


*


    E2        z         -200


    E2        e2        1


    E2        e3        -1


    E2        i2        -1


*


    A2        z         650


    A2        r         50


    A2        i2        1


*


    T2        z         -100


    T2        e3        -1


    T2        i2        .3333333333


*


    E3        z         -200


    E3        e3        1


    E3        e4        -1


    E3        i3        -1


*


    A3        z         550


    A3        r         50


    A3        i3        1


*


    T3        z         -100


    T3        e4        -1


    T3        i3        .3333333333


*


    E4        z         -200


    E4        e4        1


    E4        i4        -1


*


    A4        z         450


    A4        r         50


    A4        i4        1


*


    T4        z         -100


    T4        i4        .3333333333


RHS


    rhs       e1        40


    rhs       r         20000


ENDATA


*]]></MPS>





<param><![CDATA[


maximize


primalSimplex


solution -


]]></param>





</document>

Input File: Electronic.omh