LINEAR PROGRAMMING PART 1 Flashcards
A model consisting of linear relationships
representing a firm’s objective and resource
constraints
Linear Programming (LP)
LP problem involves a linear objective
functions, which is the function that must be
maximized or minimized. This objective
function is subject to some constraints, which
are inequalities or equations that restrict the
values of the variables.
Linear Programming (LP)
LP is used to find the best or optimal solution
to a problem that requires a decision about
how best to use a set of limited resources to
achieve
Linear Programming (LP)
Determines the resource
capacity needed to meet demand over
an immediate horizon, including units produced, workers hired and
. Production Planning
Menu of food items that meets nutritional or
other requirements, for example, hospital or school
cafeteria menus.
. Diet
Assigns work to limited resources, example ; assigning jobs or workers to different
machines.
Assignment
Mix of different products to
produce that will maximize profit or minimize cost
given resource constraints such as material, labor, budget, et
Production Mix
Financial model that
determines amount to invest in different alternatives
given return objectives and constraints for risk, diversity, etc.
Investment Budgeting
Schedules regular and
overtime production, plus inventory to carry over, to
meet demand in future periods.
Multi-period Scheduling
Logistical flow of items (goods or
items) from sources to destinations.
Transportation
Determines “recipe” requirement
Blend
Maximizes the amount of flow from
sources to destinations; for example, the flow of work
in process through an assembly operation.
Maximal Flow
Shortest routes from sources to
destinations.
Shortest Route
Optimization in Medicine
The objective in an optimization model could be
Maximize lifespan of a patient
Maximize average lifespan of a population
Minimize radiation exposure to healthy tissue
Maximize radiation exposure to cancer tissue
Minimize the probability of an adverse event
Minimize costs
Optimization in Medicine
The constraints in an optimization model could arise
due to:
Budget constraints
Maximum allowable exposure to a treatment
Minimum or maximum time between treatments
Maximum allowable risk level
This system is generated when the
number of decision variables is equal to the number of
constraints, that is, the number of rows = the number
of columns. In this system, there exists a unique
solution.
Square system
This system is generated when the
number of decision variables is lesser than the
number of constraints, that is, the number of
rows > the number of columns. In this system,
there are many representative solutions
Tall system
This system is generated when the
number of decision variables is more than the
number of constraints, that is, the number of
ows < number of columns. In this system,
there is infinite solution.
Flat system
Approaches used in Linear Programming
Geometric Approach, Algebraic Approach
graphical method
- uses feasible region and corner points (coordinate
points)
to determine the optimal
Geometric Approach
SIMPLEX method
developed by George B. Dantzig in 1947
- utilized if there are more decision variables and
problem constraints
Algebraic Approach
APPLICATION FORMULATING LP MODELS STEP 1
Step 1. Read the problem carefully. If appropriate, organize the data into a table
APPLICATION FORMULATING LP MODELS STEP 2
Step 2. Determine and define the variables. These
variables represent the unknown quantities whose
values are what you want to find.
APPLICATION FORMULATING LP MODELS STEP 3
Step 3. Formulate the objective function. This is what
you want to maximize or minimize.
APPLICATION FORMULATING LP MODELS STEP 4
Step 4. Formulate the constraints inequalities. These
are expressions that limit the amount of resources you
can use and the restrictions of your constraint
variables.
APPLICATION FORMULATING LP MODELS STEP 5
Step 5. Solve the problem using an appropriate
algorithm or mathematical technique manually and/or
using any available
A mathematical procedure for solving linear
programming problems; can handle two or more
decision variables.
Simplex Method
A linear programming problem is
a. the objective function is to be maximized
b. all decision variables are nonnegative
C. all constraints involve <
d. the constants on the right side in the constraints are
all positive
Simplex Method Step 1
Determine the objective function.
Simplex Method Step 2
. Write down all necessary constraint
Simplex Method Step 3
Convert each constraint into an equation by adding
a slack variable.
Simplex Method Step 4
Set up the initial simplex table
Simplex Method Step 5
Select pivot column by finding the most negative
indicator
Simplex Method Step 6
- Select pivot row. (Divide the last column by pivot
column for each corresponding entries. Choose the
smallest positive result. The corresponding row is
the pivot row. In case there is no positive entry in
pivot there is no optimal solutions. Stop!
Simplex Method Step 7
- Find pivot: Circle the pivot entry at the intersection
of the pivot column and the pivot row, and identify
entering variable and leaving variable . Divide pivot
by itself in that row to obtain 1. Also obtain zeros for
all rest entries in pivot column.
Simplex Method Step 8
- Perform row operation using Pivoting Method
