Linear Programming

Linear Programming
1. Objective Function – is the function that needs to

be optimized (either maximized or minimized).
Examples are profit functions and cost functions.
2. Constraint – is a limitation on the resources (such as
materials and labor) or a requirement that must be
complied (such as laws or material specification).
3. Linear Programming Problem – consists of a linear
objective function to be maximized or to be minimized
subject to certain constraints in the form of linear
equations or inequalities.
Requirements of LP Models
1. The decision maker must have an objective to achieve.
This objective must relate to a quantity such as profit or
cost, which the decision maker wishes to optimize.
2. There must be at least two decision variables that the
decision maker can operate at different levels.
3.The decision variables must be operated at levels that
do not violate the limitations/ restrictions placed on the
decision maker.
4. The variables must be interrelated and the decision
maker must be able to express the relationship in terms
of linear equations or linear inequalities.
Steps in LP Model Formulation
1. If possible, tabulate the given information in the problem.

2. Identify the objective (either to maximize or to minimize a certain
quantity).
3. Identify the decision variables.
4. Write an equation which expresses the quantity to be maximized or
to be minimized in terms of the decision variables. This is the
objective function.
5. Write the equations or inequalities that express the different
constraints. These are the explicit constraints.
6. Include the non-negativity constraint.
Formulate but do not solve the LP problems:
1. MD Electronics Corp. is planning to produce

two products C13 and C15. At the assembly
plant, a C13 unit requires 4 hours and a C15
requires 5 hours. C13 and C15 units require 3
and 2 hours, respectively, for finishing. At
most 220 hours and 210 hours of assembly
and finishing, respectively, are available per
month. If the anticipated profit is P30/unit
for C13 and P25/unit for C15, find the product
mix to maximize profit.
2. ABC Furniture produces inexpensive tables and
chairs. Both require labor hours for carpentry and
painting jobs. Each table requires 4 hours of
carpentry time and 2 hours of painting time. Each
chair requires 3 hours of carpentry and 1 hour of
painting time. During the next production period,
there are 240 hours available for carpentry and 100
hours for painting. Each table yields P150 profit and
each chair, P75. Determine the best product
combination to optimize profit.
3. As a part of quality improvement initiative, Consolidated Electronics
employees complete a three-day training program on team-building
and a two-day training program on problem solving. The manager of
quality improvement has requested that at least 8 training programs
on team-building and at least 10 training programs on problem
solving be offered during the next six months. In addition, senior
level management has specified that at least 25 training programs
must be offered during this period. The company uses a consultant
to teach the training programs. During the next quarter, the
consultant has 84 days of training time available.
Each training program on team-building costs P150,000 and each
training program on problem solving costs P125,000. Formulate a
linear programming model that can be used to determine the
number of training programs on team-building and the number of
training programs on problem solving that should be offered in order
to minimize the total cost.
4. The Kal-Q Company produces two types of calculators: the standard
model on which profit is PhP150 and the scientific model on which
the profit is PhP240. Weekly supply of chips necessary for the
calculators is limited to 6,000 units. Each standard calculator requires
3 chips and each scientific type needs 6 chips. It takes 3 hours to
assemble a standard calculator and 2 hours to assemble a scientific
calculator. The company has 75 skilled workers, each working 40
hours a week with the company. Furthermore, the company
estimates that at most 1,200 calculators can be sold each week. At
most 700 standard calculators and at most 900 scientific calculators
can be assembled weekly. How many standard and scientific
calculators must be produced each week in order to maximize profit?
6. A small generator burns two types of fuel: low sulfur and high sulfur
to produce electricity. For one hour, each gallon of low sulfur emits 3
units of sulfur dioxide, generates 4 kilowatts electricity and cost
PhP160. Each gallon of high sulfur emits 5 units of sulfur dioxide,
generates 4 kilowatts and costs PhP150. The environmental
protection agency insists that the maximum amount of sulfur dioxide
that can be emitted per hour is 15 units. Suppose that at least 16
kilowatts must be generated per hour, how many gallons of high
sulfur and low sulfur must be utilized per hour in order to minimize
the cost of fuel?
7. Mr. Investor has ₱500,000 that he intends
to invest in one or both of two opportunities.
The minimum amount that can be invested in
opportunity 1 is ₱200,000, while the
maximum in opportunity 2 is ₱300,000.
Interest rates per year are 8% for opportunity
1 and 10% for opportunity 2. How much
should he invest in each in order to maximize
his earnings?
8. A hospital is minimizing the cost of its beef and
pork diet. The average diet requires 2 kilos of lean
meat and 1 ½ kilos of fat meat per person. The beef,
which cost PhP450 per kilo, is 20% of fat and 80%
lean meat. The pork, which costs PhP250 per kilo, is
60% fat and 40% lean meat. If the hospital has 300
patients on this diet and if it cannot purchase more
than 1,250 kilos of meat because of refrigerator
space, how many kilos of beef and how many kilos
of pork should be purchased to keep the cost at a
minimum.
9. As part of a campaign to promote its annual clearance sale, Shangri-
Son Malls decided to buy television advertising time on Station ABS-
5. Its advertising budget is P5M. Morning time costs
P150,000/minute, afternoon time costs P50,000/minute and evening
or prime time costs P600,000/minute. Station ABS-5 cannot offer
Shangri-Son Mall more than 6 minutes of prime time or more than a
total of 25 minutes of advertising time over the weeks in which the
commercials are to be run. Station ABS-5 estimates that morning
commercials are seen by 200,000 people, afternoon commercials are
seen by 100,000 people while evening commercials are seen by
600,000 people. How much morning, afternoon and evening
advertising time should Shangri-Son Malls buy in order to maximize
exposure of its commercials?

Linear Programming

Uploaded by

Copyright:

Available Formats

Linear Programming

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Linear Programming

Uploaded by

Copyright:

Available Formats

Linear Programming

1. Objective Function – is the function that needs to

1. If possible, tabulate the given information in the problem.

1. MD Electronics Corp. is planning to produce

You might also like