M&S4
Workshop 1
Linear programming (LP) problem
- Maximizing or minimizing a linear goal function subject to linear
constraints
- How to allocate limited resources among competing activates in a best
possible way
Elements of a LP problem
- Decision variables x1/x2 (what units to change to reach objective?)
- Objective function maximize profit (goals of problem)
- Constraints restrictions
Steps
1. Determine the variables
2. Formulate the objective
3. Write the constraints
4. Solve the LP problem
Terminology solutions
- Feasible solution
All constraints are satisfied
- Optimal solution
Feasible solution with most favorable value of the objective (always
a corner point)
- Corner-point feasible solution (CPF)
Solution at the corner of the feasible region
Workshop 2
IP = integer programming
- Geheel getal
- Can never be better than LP, so worse solution
- Integer constraint can be added in the constraints window whilst solving
the problem
Binary variables
- Just two possibilities within integer programming
- Yes or no, 1 or 2
Transportation problem
Objective is always min or max Z, constraints are always from demand, supply (if
applicable) and nonnegativity
, Week 2
Workshop 1
Simplex method: algebraic method to compute the optimum
- Always tried to find a maximum
- Min Z = Max(-Z) min (costs) = max (-costs)
- Equality (=) constraints are needed instead of inequalities
- Add slack variables, by converting < to =
-
Requirements:
- Maximization
- Equalities
- Non-negative otherwise multiply it by -1
- Simplex tableau
o Coefficients of variables
o Solutions on the right-hand sides of the equations
o Basic variable appearing on each equation
Augmented solution: solution for the original variables that has been
augmented by the corresponding values of the slack variables (blue variables)
RHS (right-hand side) is
equal to the maximum
amount of resources
available
Slack variables have
value 1 in ‘their’ row =
source to convert
inequality
Basic and nonbasic variables
- Non basic variables = value equals 0 and multiple values in the row are
not equal to 0
Workshop 1
Linear programming (LP) problem
- Maximizing or minimizing a linear goal function subject to linear
constraints
- How to allocate limited resources among competing activates in a best
possible way
Elements of a LP problem
- Decision variables x1/x2 (what units to change to reach objective?)
- Objective function maximize profit (goals of problem)
- Constraints restrictions
Steps
1. Determine the variables
2. Formulate the objective
3. Write the constraints
4. Solve the LP problem
Terminology solutions
- Feasible solution
All constraints are satisfied
- Optimal solution
Feasible solution with most favorable value of the objective (always
a corner point)
- Corner-point feasible solution (CPF)
Solution at the corner of the feasible region
Workshop 2
IP = integer programming
- Geheel getal
- Can never be better than LP, so worse solution
- Integer constraint can be added in the constraints window whilst solving
the problem
Binary variables
- Just two possibilities within integer programming
- Yes or no, 1 or 2
Transportation problem
Objective is always min or max Z, constraints are always from demand, supply (if
applicable) and nonnegativity
, Week 2
Workshop 1
Simplex method: algebraic method to compute the optimum
- Always tried to find a maximum
- Min Z = Max(-Z) min (costs) = max (-costs)
- Equality (=) constraints are needed instead of inequalities
- Add slack variables, by converting < to =
-
Requirements:
- Maximization
- Equalities
- Non-negative otherwise multiply it by -1
- Simplex tableau
o Coefficients of variables
o Solutions on the right-hand sides of the equations
o Basic variable appearing on each equation
Augmented solution: solution for the original variables that has been
augmented by the corresponding values of the slack variables (blue variables)
RHS (right-hand side) is
equal to the maximum
amount of resources
available
Slack variables have
value 1 in ‘their’ row =
source to convert
inequality
Basic and nonbasic variables
- Non basic variables = value equals 0 and multiple values in the row are
not equal to 0
