supplement 1: LP

Question 1

2 general techniques for LP

Answer 1

Graphical

Computer-based

Question 2

Graphical LP

Answer 2

Visual portrayal of concepts usually with only two variables

Question 3

Computer LP solutions

Answer 3

to complex problems involving a large number of variables. (Actually, for all problems, i.e. no need of Graphical technique).

Question 4

how many objectives does LP have?

Answer 4

only 1

Question 5

Objective function

Answer 5

a mathematical expression to find the total profit/cost/time

Question 6

Decision variables

Answer 6

choices to arrive at the objective function (mathematical expression) and the constraints surrounding it

Question 7

Graphical LP formulation

Answer 7

1. Plot all constraints.
2. Find the area where all constraints are satisfied (the solution space)
3. plot the objective function by equating it to the product of parameter values

–> move it in parallel to find the solution point

–> For max problem, start at origin and move it away

–> For min problem, start at far away and move it closer to origin

4. Find solution

Question 8

the solution space

Answer 8

the area where all constraints are satisfied

Question 9

Optimal solution

Answer 9

at a corner point of feasible solution space

Question 10

Redundant constraints

Answer 10

not part of feasible solution space

Question 11

maximization solution point

Answer 11

the furthest away en diagonal a droite in the graph but still in the solution space

Question 12

minimization solution point

Answer 12

the closest to the origin in the graph but still in the solution space

Question 13

Binding constraint

Answer 13

a constraint that passes through the solution point on the feasible solution space

Question 14

Slack

Answer 14

when the optimal values of decision variables are substituted into a ≤ constraint and the resulting value is less than the right side value

Suppose, the optimal value of x1 is 10, and x2 is 20, and one of the constraint is 3x1 + 2x2 ≤ 100; then LHS is 70, and slack is 100-70, i.e. 30.

difference between value of constraint and the optimal value (when the latter is smaller than the slack constraint)

Question 15

Surplus

Answer 15

When the optimal values of decision variables are substituted into a ≥ constraint and the resulting value exceeds the right side value

Suppose, the optimal value of x1 is 10, and x2 is 15, and one of the constraint is 4x1 + x2 ≥ 50; then LHS is 55, and surplus is 55-50, i.e. 5.

difference between value of constraint and the optimal value (when the latter is bigger than the surplus constraint)

Question 16

LHS value in Slack or Surplus of a constraint

Answer 16

the actual amount of the resource being “used”

Question 17

RHS value in Slack or Surplus of a constraint

Answer 17

actual constrain or limit

Question 18

what is the Slack/Surplus of a binding constraint?

Answer 18

0

LHS = RHS

Question 19

Inference

Answer 19

Slack/Surplus is the amount of unused capacity of a resource

If slack/surplus is removed, constraint inequality becomes equality, and still gets the same solution