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.