1. Structure of Linear programming problem
General structure of Linear programming problem
(Maximize or Minimize) `Z_x=c_1x_1+c_2x_2+c_3x_3+...+c_nx_n` (objective function)
Subject to the constraints
`a_11x_1+a_12x_2+a_13x_3+...+a_(1n)x_n(<=,>=,=)b_1`
`a_21x_1+a_22x_2+a_23x_3+...+a_(2n)x_n(<=,>=,=)b_2`
:
:
`a_(m1)x_1+a_(m2)x_2+a_(m3)x_3+...+a_(mn)x_n(<=,>=,=)b_m` (constraints)
and `x_1,x_2,...,x_n>=0` (non-negative condition)
Here `x_1,x_2,...,x_n` are decision variables
Each constraint may be either
1. `<=` (less than or equal to)
2. `>=` (greater than or equal to)
3. `=` (equal to)
`x_1,x_2,...,x_n>=0` means each `x_i` must be non-negative
A linear problem is said to be in standard form if
- It is maximization problem
- There are only equalities (=) (by adding slack, surplus or artificial variables)
- All variables are restricted to be non-negativity
Any linear program can in fact be transformed into an equivalent linear program in standard form
- If the objective function is minimize `Z=2x_1-3x_2` then we can simply maximize it by multiplying -1,
maximize `Z'=` minimize `-Z=-2x_1+3x_2`
- If constraint is `<=` type then we have to add slack variable
eg. `3x_1+2x_2<=4` then `3x_1+2x_2+S_1=4` (here `S_1` is slack variable)
- If constraint is `>=` type then we have to subtract surplus variable and add aritificial variable
eg. `5x_1+3x_2>=6` then `5x_1+3x_2-S_2+A_1=4` (here `S_2` is surplus variable and `A_1` is aritificial variable)
- If constraint is `=` type then we have to add aritificial variable
eg. `x_1-x_2=1` then `x_1-x_2+A_2=1` (here `A_2` is aritificial variable)
- If `x_1` is unrestricted in sign then we can introduce two new decision variables `x_1'` and `x_1''`
and now `x_1=x_1'-x_1''` where `x_1,x_1',x_1'' >= 0`
For eg.
Min `Z=2x_1-3x_2`
subject to the constraint
`3x_1+2x_2<=4`
`5x_1+3x_2>=6`
`x_1-x_2=1`
and `x_1,x_2>=0`
Then it is converted to
Max `Z'=-2x_1+3x_2`
subject to the constraint
`3x_1+2x_2+S_1=4`
`5x_1+3x_2-S_2+A_1=4`
`x_1-x_2+A_2=1`
and `x_1,x_2,S_1,S_2,A_1,A_2>=0`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
