Linear programming
About
What is Linear Programming?
A problem with a goal to maximize or minimize a linear function within certain constraints that are determined by a set of linear inequalities.
A way to find the best solution for a linear function
This best solution is called The Objective Function
The Objective Function is subject to constraints
Constraints can be linear inequalities, equations, or restrictions
subtask
A Linear Objective Function is a Linear function that has to be maximized or minimized
Linear Function: z=ax+by, where a and b are constants
Terms
Feasible Region
Common region met by all constraints
The feasible region is reflected by a shaded area
Feasible Solution
A solution that satisfies the set of constraints and non-negative restrictions
x is greater than or equal to 0 and y is greater than or equal to 0 are non-negative restrictions.
Decision variables and slack variables are non-negative
If a Basic Solution has no negative values, it is a Basic Feasible Solution
Basic Solution
Obtained by assigning the non-basic variables a value of zero and solving for the basic variables
Non-basic varibales are zeros
Basic variables are all others
task
Optimal Solution
Any point in the feasible region that gives the optimal value
Optimal Value meaning the maximum or minimum
Decision Variables
the unknown quantites
indicated by x1,x2, x3...
How To Solve:
Determine the decision variables
Write the objective function as a linear function using the decision variables above, slack variables and equal signs
Solve the equations using the slack variables to optimal solutions