CHAPTER 3

LINEAR PROGRAMMING

3.1. Introduction to Linear Programming

3.2. Characteristics of LP problems
3.3. A Maximization Problem
3.4. A Trial-and-Error Approach in Solving LP problems
3.5. Graphical Solution of an LP Problem
3.6. A Minimization Problem
3.7. General Formulation and Assumptions of LP Models
3.8. Solving LP Problems

3.1. Introduction

The optimal allocation of limited resources among “competing” activities, i.e. among
activities that “strive” for the same resources, is a very common problem in any enterprise
and in any sector of the economy. Deciding on the allocation of funds between R&D,
promotion, human resources advancement, and other important activity is a common issue
in any company. Or, deciding on the optimal allocation of workers among on-going projects
is another important problem. Or, deciding what should be the optimal mix of products to
produce given the limited availability of resources or of the market size is another common
type of decision. Or, deciding what should be the priorities of customer orders to be
satisfied, given the limited time and availability of resources is yet another common problem

This type of allocation of resources problem does not appear only at the enterprise level; it is
a classic problem that can be encountered at almost any level of economic activity. At the
central government level, key issues like budget allocation among ministries or strategic
projects fall in this category of decisions. Even at our own, the personal level, the allocation
of available resources like time, money, effort, etc is also a common decision. In all of the
above cases, the key question is: Which activities should we pursue, to which extent, and
how should the allocation of the limited available resources be made.

Linear Programming (LP) is frequently used to address these problems. It provides not only
optimal solutions, but also substantial additional financial information (in the form of
shadow prices, reduced costs, sensitivity analysis, etc) that can be very useful in evaluating
alternative scenaria and formulating strategy. LP is concerned with activities planning in
order to achieve a certain goal under some constraints. For example, in the production field,
a commonly reported problem is to determine the production plan for the company’s
products (choice of products, production rate, etc) in order to maximize the resulting
revenue and to achieve the objectives of customer orders. A related problem is to determine

Chapter 3: Linear Programming 1

the optimum mix of raw materials for the production of a specific product, in order to meet
all the production specifications at the most economic way.

Transportation problems constitute another area which requires planning. The route
selection for the transportation of products, especially for companies that have many
production sites and distribution points, can significantly reduce costs by carefully planning
the transportation of goods. If the company has its own vehicles, the problem is to find out
the paths that minimize the total cost. When the company rents vehicles, planning becomes
more complicated in order to include any special features of various modes of transport cost.

Another example which requires planning is in the field of investments. In these problems
the investor faces a series of alternative investment programs each of which is characterized
by different requirements for capital (or other) investment, duration, amount of returns, risk
or uncertainty of returns, etc. The investor’s program should clearly determine: the specific
investment projects that he will undertake, the time that each program should be assigned,
the amount of money that he will invest in each program, and at the same time ensure that
all (financial or material) resources necessary for completion of these projects are available.

In this chapter we first illustrate the formulation of LP models by considering a

maximization problem. Then we present the graphical solution and give intuitive guidelines
that result from its solution. Next, the standard form of LP problems is presented, and the
necessary hypotheses for LP problems are discussed. Finally, a brief presentation of the
solution of Linear Programming problems using Excel’s-Solver is examined.

3.2. Characteristics of LP Problems

When we formulate an LP model, we should remember that any LP model consists of three
components: a) a set of decision variables, b) the objective function, and c) a set of
constraints. Therefore, we have to understand the role of each of these components, in
order to correctly identify them in a given situation.

The decision variables in an LP model reflect the alternative activities to be developed. For
example, the quantities of products to produce could constitute the decision variables in a
production problem. The quantities of raw materials to ship from a supplier to a
manufacturer could be the decision variables in a transportation problem. The amount of the
advertising budget to be allocated to the various advertising media in a campaign could be
the decision variables in a marketing problem. The decision variables are usually denoted as
X1, X2, … Xn, to indicate the level at which activity 1, 2, … n will be pursued. Instead of the
symbols Xi, we can also use names that remind us the activities themselves, e.g. Product1,
Product2, etc

The objective function represents the goal that has to be optimized. The objective function
in an LP problem will be either maximized, or minimized. For example, maximization of

Chapter 3: Linear Programming 2

revenue, of sales, or of profit is a common objective function in LP problems. Similarly,
minimization of cost, or of unused materials, is another common objective function. The
objective function is usually denoted by Z, and is expressed as a linear function of the
decision variables. Therefore, in an LP problem, the objective will be
Maximize or Minimize Z = c1X1 + c2X2 + … + cnXn

The constraints of an LP problem express the restrictions or the limitations of the business
environment of the decision maker. For example, the limited availability of the resources is a
common set of constraints in a production problem, expressed in the form quantities
consumed ≤ total availability. Or, the limited size of the market is another common
constraint, expressed in the form sales ≤ market size. Or, the legal or policy restrictions that
reflect the liquidity requirement in a bank constitute an important constraint in a banking
asset and liability problem, expressed in the form liquidity ≥ requirements. Or, finally, the
traffic inflows to a certain node = traffic outflows of that node. The constraints are
expressed as algebraic inequalities or equalities, and include the left-hand side which is
expressed in terms of the decision variables and the right hand side which is a constant. The
constraint set of an LP problem could include constraints of the following type:

a11X1 + a12X2 + … +a1nXn ≤ b1

a21X1 + a22X2 + … +a2nXn ≥ b2
. . .
am1X1 + am2X2 + … +amnXn = bm

where m is the number of constraints of the problem. It can be seen that some constraints
are of the ≤ type, whereas others could be of the ≥ type, and others could be of the = type.

To summarize, when formulating an LP model, we follow the following four steps:

Step 1: Understand the problem. In this step we understand the problem, the business
environment, the objectives, the constraints, the units of measurement, etc.
Step 2: Identify the decision variables. In this step we identify the decisions that need to be made
within the context of the problem, and we express these decisions in terms of variables. The
decision variables are explicitly defined in this step. Note that the unit of measurement for
each decision variable has to be explicitly stated.
Step 3: Identify the objective function. In this step we identify the objective to be optimized. Even
though this might sound as a trivial step, in reality it is far from trivial. The identification of
the correct target is crucial, and many times in real life, we realize that the wrong objective
has been set, leading to a mistaken approach towards the solution of the problem.
Step 4: Identify the constraints. In this step we identify and express the constraints of the
problem. Each constraint has to be identified, expressed and explained, and all constraints
that relate to the problem have to be stated. Make sure that you include any possible upper
or lower bounds on the variables.

Chapter 3: Linear Programming 3

3.3. A Maximization Problem

Consider the following simple production problem: A furniture company produces tables
and chairs. Both products require time for the manufacturing process and time for the
dyeing process. A table requires 4 hours manufacturing and 2 hours dyeing, while a chair
requires 3 hours manufacturing and 1 hour dyeing. For the next 2 weeks the firm has 240
hours available for the manufacturing process and 100 hours for dyeing. Management has
determined that at most 60 chairs should be produced due to limited demand for chairs,
while the forecast for tables is that all tables produced can be sold (demand is much bigger
than the firm’s capacity). Each chair sells for $50 while each table sells for $70. The firm
seeks to determine the optimal number of furniture (chairs and tables) to produce in order
to maximize the total revenue.

To formulate the model of the problem we follow the 4 steps presented above:
Step 1: Understand the problem
This is a simple problem, where we are asked to determine the optimal number of chairs and
tables to be produced so as to maximize the anticipated revenue. The constraints include the
limitation of manufacturing time, the limitation of dyeing time, and the upper limit of chairs
that should be produced.

Step 2: Identify the decision variables.

The decision variables are the quantities of tables and chairs to be produced. We will use T
and C to denote the unknown quantities of tables and chairs that need to be determined.

Step 3: Identify the objective function.

The objective of the problem is to maximize the revenue generated from the production and
sale of the produced chairs and tables. Therefore, given the decision variables T and C, we
wish to maximize the total revenue
Ζ = 70Τ + 50C

Step 4: Identify the constraints.

There are three constraints in the problem, that relate to the limitation of the manufacturing
and dyeing times, and the maximum allowable production of chairs. We can express these
constraints as follows:
4Τ + 3C ≤ 240 (1)
2Τ + C ≤ 100 (2)
C ≤ 60 (3)
Τ≥0 C≥0

Constraint (1) is calculated as follows: provided that every table requires 4 hours for the
manufacturing procedure and every chair 3 hours, then the production of T tables and C

Chapter 3: Linear Programming 4

chairs requires (4Τ + 3C) hours of manufacturing. But the availability of hours for the
manufacturing process is limited up to 240 hours. Hence constraint (1) is introduced. Similar
constraints apply for the dyeing hours (constraint 2) and for the demand requirements
(constraint 3). In addition, we have introduced two non-negativity constraints of the decision
variables, which state that it is impossible to produce negative quantities of tables and chairs.

3.4. A Trial-and-Error Approach in Solving LP Problems

To identify the solution to the problem, we could try a trial-and error approach by
enumerating “reasonable” answers and checking out their value in the objective function.
Let us see how it works.

We can start with a suggestion of producing 50 chairs and 50 tables. This production plan
produces a Z value of 6,000 (70*50+50*50), but we realize that it is not feasible, as it violates
the first constraint (4*50+3*50=350 > 240), as well as the second constraint (2*50+50=150
> 100). This means that this production plan requires more resources (manufacturing and
dyeing times) than available. Therefore the number of chairs, or the number of tables, or
both has to be reduced. Let us reduce the number of chairs, as it contributes less to the
objective function ($50 vs. $70). So, how about 25 chairs and 50 tables? This produces a Z
value of 4,750 (70*50+50*25), but it is still not feasible, as it again violates the first
constraint, as well as the second constraint. Let us now try reducing the number of tables,
and let us assume that T=40 and C=20. In this case, the Z value becomes 3,800
(70*40+50*20), and all constraints are satisfied. In fact, constraint (A) is amply satisfied (i.e.
there is manufacturing time which is not used), while dyeing time is fully exhausted.
Therefore, this production plan (T=40, C=20) is a feasible plan, producing a Z-value of
$3,800.

But, is it optimal? If not, how far is it from the optimal? The answer to both questions is that
we do not know. In fact, if we wanted to be sure of the optimal answer, we should continue
this process of trial-and-error, trying out many alternative solutions, and checking out: a) If
they are feasible, and b) What their Z-value is, until we come up with the best. It is easy to
realize that in this process we could spend a very large amount of time, and even then, we
could still not be absolutely sure that we have identified the optimal answer to the problem.
Note also that throughout this process, we could not be sure of how far a given answer is
from the optimal, as the value of the optimal answer is not known.

3.5. Graphical Solution of an LP Problem

We will now try an alternative solution to the problem. This is a graphical solution, and it
can be used when the number of variables is equal to 2, as the problem can be represented in
2 dimensions. The graphical method cannot be implemented for problems with more than 2
variables. However, it is interesting to see the method, as it provides some useful insights

Chapter 3: Linear Programming 5

about the properties of the optimal answer. The graphical method is composed of 4 easy
steps.

Step 1: Plotting the constraints

Constraint (1) can be plotted on a 2-dimensional graph, as illustrated in figure 3.1:

CΚ

80

4T+3C = 240
4Τ + 3Κ = 240 (Α) (1)

•Ρ
P

•
Σ
M
Τ T
60
Figure 3.1: Plotting constraint (1)

Figure 3.1 shows that in order to satisfy the constraint A: 4Τ + 3C ≤ 240, the production
plan (that is the point which we are going to choose) must lie either under the line 4Τ+3C =
240 (shadowed region), or exactly on the line. For example, point M, whose coordinates are
(30, 20) satisfies the constraint with inequality (provided that 4*30+3*20 = 180 < 240) while
point Ρ (70, 40) does not satisfy the constraint (provided that 4*70 + 3*40 = 400 > 240).

In the same way constraints (2) and (3) can be plotted. They are illustrated in Figure 3.2:

Κ
CΚ C

100 2T+C = 100 (2) C = 60 (3)

2Τ + Κ = 100 Κ = 60

60

(Γ)
(Β)

Τ T Τ T
50

Figure 3.2: Plotting constraints (2) and (3)

Chapter 3: Linear Programming 6

In order to satisfy the three mentioned constraints and the non negativity constraints, we
conclude in figure 3.3:

K C
100
(1)
(A)

(B) (2)
70
(3)
(Γ)

2
3
50
4

20

5
1
T
T
10 20 30 40 50 60

Figure 3.3: Putting all constraints together

We are now ready to move to step 2 of the graphical method, which is to identify the
feasible region of the problem.

Step 2: Identifying the feasible region

Given that all constraints have to be satisfied, any point (T, C), which we are going to select
as the optimum production plan, must lie inside or along the borders of the shadowed polygon.
The polygon consists of the common points (the common set) of all constraints and is
known as the feasible region. The feasible region of the problem is shown in Figure 3.4.

ΚC T

2 3

E 4

K Τ
1 5

Figure 3.4: The feasible region of the problem

Chapter 3: Linear Programming 7

The feasible region contains an infinite number of points which satisfy the constraints and
give us a feasible solution. In order to determine the optimal solution, we have to take into
account the objective function Z. So, we are ready to move to the next step of the graphical
method, which is to plot the objective function.

Step 3: Plotting the objective function

The objective function Ζ = 70Τ + 50C represents a family of functions with the same slope.
More specifically, the objective function, depending on the value of Z, can be a different
line, but will always have the same slope. This slope is defined by the coefficients of the two
variables in the objective function, and is defined as
Slope = c1 / c2
Where c1 is the coefficient of the first variable (T), and c2 is the coefficient of the second
variable (C). In our problem, the slope is equal to 7/5. Plotting the function Z and giving
two arbitrary values to Z (Z=7,000 and Z=3,500) we get figure 3.5.
C
140

Ζ = 7,000

70

Ζ = 3,500

T
50 100
Figure 3.5: Plotting the objective function
For example every point (T,C) along the line Z=3,500 satisfies the function 70Τ+50C=3,500
and yields a revenue of $3,500, while every point along the line Z=7,000 satisfies the
function 7Τ + 5C = 7,000 and give us a revenue of $7,000.

We are now ready to move to the fourth step of the graphical method, which is to identify
the optimal solution.

Step 4: Identifying the optimal solution

From Figure 3.5 we can see that the value of Z increases as the line draws away from the
starting point of the axes. Since our objective is to maximize Z, we will move the Z-line,
parallel to itself, as far as possible from the origin of the axes. This can be done only as long
as Z retains common points within the feasible region. Therefore, if the objective function
line is moved parallel to itself upward through the feasible region (figure 3.6), the optimal
feasible point is found to lie where the objective function line touches the last point of the
feasible region, which is the corner . This point is the optimal solution of the problem.

Chapter 3: Linear Programming 8

 KT

2 3

1 5
K T

Figure 3.6: Determining the Optimal Point

Point is the intersection of
2Τ + C = 100 and 4Τ + 3C = 240
This system is a system of two equations and two unknowns. Therefore, one and only
solution exists, which may be easily determined (e.g. with Cramer's rule or with the
substitution method). Thus, the solution of the system indicates that:
Τ = 30 and C = 40
Therefore, the company should produce 30 tables and 40 chairs. Such production would
yield the maximum possible revenue, which equals Ζ = 70*30 + 50*40 = $4,100.

From the solution of the problem we can observe and generalize the following conclusion:
The optimal solution of an LP problem is always one of the corners of the feasible region,
which is determined by the constraints of the problem. This facilitates the search for the
optimal solution, as the enumeration of alternative feasible solution needs only to be done
among the corner points. We can now move to the last step, which is to analyze the
sensitivity of the solution to possible changes of the problem parameters.

Step 5: Analyzing the sensitivity of the solution

After having determined the optimal solution, the next step is called Sensitivity Analysis.
This will be discussed in detail in chapter 4. Here, we will give a preview of the sensitivity
analysis, as to what happens when the coefficients in the objective function change, or when
the Right Hand Side (RHS) constants of the constraints change.

Analyzing possible changes in the coefficients of the objective function, we notice that the
optimal corner is determined by the slope of the objective function. Specifically, provided
that Ζ = c1T + c2C, shifting parametrically the value of the slope c1/c2 the optimal corner
simultaneously changes, as follows:

Chapter 3: Linear Programming 9

 If c1/c2 ≤ 4/3 then the optimal corner is
If 4/3 ≤ c1/c2 ≤ 2 then the optimal corner is
If c1/c2 > 2 then the optimal corner is

As an example, let us assume that the selling price of a table increases from $70 to $110. The
new objective function is Ζ = 110Τ + 50C, and the new slope is c1 / c2 = 110/50 > 2. This
slope means that the new optimal solution is corner , which is given by the intersection
(cut) of the constraint 2Τ + C ≤ 100 and the axis C=0, so the coordinates of the optimal
solution are: Τ=50, C=0. We realize that for values of c1 < 100 (as long as c2=50) the
optimal solution remains T=30 and C=40. This is a very interesting conclusion, as it
indicates that for relatively small changes of the prices, the production plan remains the same; thus, the
pricing policy is decomposed from the production process. This is a very important
conclusion, as will be discussed later on.
This conclusion will not hold for small changes in the RHS constants, as we will see later on.
The range of prices for which the optimal solution will not change is given by the sensitivity
analysis, and will be discussed in chapter 4. It should be noted that in cases that the slope of
the objective function is equal to that of one of the constraints, the optimal solution is every
point along the line of the constraint.

Looking for possible changes in the RHS constants, we realize that constraints (1) and (2)
are satisfied with equality, i.e. they exhaust all resources. This means that any change in the
RHS constants of these constraints will have an immediate impact on the solution, as the
boundary of the feasible region will move, and a new corner point will be defined. This is
another interesting conclusion, as it indicates that for any change of the quantity of the critical
resources, the production plan changes; thus, the production plan cannot be formulated until these
quantities are known.

3.6. A minimization problem

A livestock company plans to determine the nutrition of its cattle. For this reason two types
of feed (A and B) are used, which will be mixed in the final diet in order to include the
necessary ingredients (protein, vitamins, iron) for the development of healthy animals. The
content of feed A and B in the aforementioned ingredients appear in the table 3.1.

Minimum required
Ingredients Feed Α Feed Β
quantity
Proteins 5 10 90
Vitamins 4 3 48
Iron 0.5 0 1.5
Cost per Kilo (in $) 2 3

Table 3.1: Data for the Livestock Company

Chapter 3: Linear Programming 10

Give the quantity of the ingredients that required in the animals’ diet to meet the healthy
nutrition of the livestock, we need the necessary quantities of feed A and B that are need so
as to minimize the total cost of the diet.

Let as assume that A is the quantity (in kilos) of feed A, and B the quantity of B respectively.
The problem is formulated as follows: Minimize the total cost
Ζ = 2Α + 3Β
Subject to the following constraints
5Α + 10Β ≥ 90 (Proteins)
4Α + 3Β ≥ 48 (Vitamins)
0.5Α ≥ 1.5 (Iron)
Α ≥ 0, Β ≥ 0
The graphical solution of the problem follows: The constraints of the problem are depicted
in the following figure:

BB
20
Iron
Σίδηρος

15

10
Vitamins
Βιταµίνες

Proteins
Πρωτεΐνες
5 2

5 10 15
A 20 A
Figure 3.7: Constraints of the livestock company’s problem

The feasible region of the problem is the region constrained by the three constraints and the
A-axis. By placing the objective function Ζ = 2Α + 3Β on the graph, we see that the optimal
point is which comes from the cut of the proteins and vitamins constraint lines.

By setting the two equalities expressed by point we have:

5Α + 10Β = 90
4Α + 3Β = 48
Therefore,
A = 8.4 B=4.8

Chapter 3: Linear Programming 11

Therefore we need 8.4 units of Α and 4.8 units of Β to produce the optimal diet of the
animals. This combination will cost $31.20.

3.7. General Formulation and Sssumptions of LP Models

A Linear Programming problem can be formulated as follows:

Calculate the values (X1, X2, …, Xn) for the activities (1, 2, …, n) so as to maximize the
objective function
Z = c1X1 + c2X2 … + cnXn
subject to the following constraints:
a11X1 + a12X2 + … + a1nXn ≤ b1
a21X1 + a22X2 + … + a2nXn ≤ b2
.
.
.
am1X1 + am2X2 + … + amnXn ≤ bm
X1, X2, …, Xn ≥ 0

This formulation is the standard form of an LP problem. Except from this form, there are a
variety of other forms, such as:
• Minimize the objective function
• Some Constraints can take other forms, such as ≥ bi
• Some Constraints can take other forms, such as = bi
• Some variables can take other forms, such as Xj ≤ 0
• Some variables do not have a constraint

As with all mathematical models, certain inherent assumptions must be made in order to use
the linear programming approach. The modeler must be aware of the impact of these
assumptions; if these assumptions are deemed unacceptable, the model must be modified or
another model must be developed. Although the assumptions may appear to be overly
restrictive, they frequently provide ‘close enough’ approximations to many problems, taking
into account that this approximation will affect the accuracy of the solution.

All linear models satisfy three assumptions: a) Linearity, b) Divisibility, c) Certainty. Linearity
assumes that the LP model, the objective function and the constraints of the problem have
to be linear functions in terms of the decision variables. In practice, in many cases linearity
does not apply. For example, the proportion of freights for the transportation of goods is
based on their weight, but this proportion for each kilogram declines as the total weight of
the cargo grows (economies of scale). Or, the production of large quantities of a product
may cause substantial reduction in costs of raw materials if discounts exist. For these

Chapter 3: Linear Programming 12

reasons, we should check the condition of linearity before using the LP model. If the
linearity assumption doesn’t apply, then another model may have to be used (e.g. Non-
Linear Programming, as in the part on Finance).

The divisibility assumption implies that each activity (i.e. variable) is continuous and divisible.
This continuity assumption implies that the decision variables (i.e. activities and raw
materials) can take fractional or integer values. This condition holds for many variables. If,
for example the variable indicates time, money etc, then the fraction makes sense. In other
cases this is not true. For example, the number of people who are going to work in the
graveyard shift, or the number of branches that a company will locate, have sense only as
integer values. In these cases, one can either approximate by solving the problem as an LP
and approximating to the closest integer, or use another model, e.g. Integer Programming.

The certainty assumption appears to be the most limiting one. It asserts that all parameters of
the problem are known with certainty. These parameters include availability of raw materials,
the contribution of each activity in the objective function (selling price, cost, profit, etc) and
the usage (proportions) of resources (raw materials) for the completion of the activities.
Even though this assumption frequently does not apply, we often use LP as an
approximation using best estimates of these parameters. Once we obtain the LP solution, we
rely on sensitivity analysis which shows the effects on the solution from possible changes in the
parameters of the problem.

3.8. Solving LP Problems

LP problems are solved through the use of a well-known method, called Simplex. The
simplex method consists of a set of steps with which an ‘initial’ table of the problem is
transformed in a final table. This method is extensively discussed in many Management
Science and Operational Research books and has been “translated” to a large number of
computer programs; hence, it will not be presented in this textbook.

Here we will present briefly the solution of LP problems, using Excel’s Solver as the main
tool. A thorough presentation of the Excel’s Solver tool (data entry, commands, screens,
examples) is given in chapter 3.

The solution of the two problems presented earlier in this chapter (sections 3.3 and 3.6) is
illustrated in tables 3.2 and 3.3.

Chapter 3: Linear Programming 13

 Table 3.2: Solution for the Furniture Company’s problem using Solver

In table 3.2 the solution of the problem in section 3.3 is illustrated. We see that
Τ=30, Κ=40, Ζ=4,100
Note that the first two constraints are satisfied with equality, which means that all available
hours for manufacturing and dyeing are used.

The solution of the problem in section 3.6 is illustrated in table 3.3.

Chapter 3: Linear Programming 14

 Table 3.3: Solution for the Livestock Company’s problem using Solver

The above screenshot shows the optimal solution of the problem, which is:
Α=8.4 Β=4.8 and Ζ=31.20

Therefore, the proteins and vitamins constraints are satisfied in the minimum allowable limit
(equality), while the iron constraint is overlapped (inequality).

Chapter 3: Linear Programming 15

Problems

Problem 1
A company produces three types of tools (A, B, C). The resources used to produce each type
of tool are shown in the following table.

Tools
A B C
Iron (kg) 9 8 7.5
Machine time (minutes) 50 110 90
Labor time (minutes) 60 40 55
Profit ($) 12 15 13.5

The company works on a weekly schedule of 5 days, with 2 shifts of 7.5 hours each. It has 4
machines available for production and 15 employees on each shift.
The marketing department requires that at least 300 tools of all types be produced each
week. The company’s capacity is 3 tons of iron.
The production manager is interested in developing the optimal production plan that
maximizes the company’s total profit.

Problem 2
A firm produces four different types of toys: T1, T2, T3 and T4. For the production three
different kinds of raw materials are required (plastic, metal and material). The cost per unit
and the available quantities of raw materials, the selling price for each type of toy are
required in the next table.

Type of Required Content in Price ($)

Toy
Plastic Metal Material

T1 1 2 3 20
T2 1.5 1.7 1.4 17
T3 1.8 1.6 2 15
Cost ($)
5 6 4.5 6
Available
400 200 250
Quantities

The firm wishes to determine the optimum production level of each toy that maximizes its
total profit.

Chapter 3: Linear Programming 16

 Problem 3
A publishing company is publishing five different book categories (A, B, C, D, E). The
company collaborates with three subcontractors (1, 2, 3). The following table presents the
orders and the profit for each book category, the maximum available time (in hours) each
subcontractor has and the maximum number of books each subcontractor can print. Also,
presents the time in minutes each subcontractor needs to print a book.

Book Profit/book Orders Time (in minutes) each subcontractor

categories in $ needs
1 2 3
A 17 2,000 30 35 25
B 18 3,000 40 30 35
C 20 1,800 25 30 25
D 17 2,500 15 20 30
E 20 1,900 20 25 20
Maximum
Available time 160 200 250
(in hours)
Maximum no. of
4,500 3,000 3,500
books

The publishing company wants to find which subcontractor to use for each book category in
order to maximize the total profit.

Problem 4
A company produces two types of dolls (D1 and D1). The following table gives the selling
price, the labor time, machine time and raw material required for the production each type of
doll, D1 and D2 respectively. Each week, up to 450 kg of raw material can be purchased at a
cost of $3 per kg. The company employs four workers, who regularly work 40 hours per
week. Each week 400 hours of machine time are available.

D1 D2
Selling price $12 $8
Labor required 0.7 hour 0.5 hour
Machine time required 1.5 hours 0.8 hour
Raw Material required 2 kg 1 kg

At most 50 dolls D1 and 60 toys D2 are expected to be demanded each week.

The production manager is interested in developing the optimal production plan that
maximizes the total profit.

Problem 5
A farm family has 200 acres. For the upcoming growing season, the farm will grow wheat,
corn, oats and soybeans. The following table gives the expected crop yields, labor required,
and water required. Also, gives the price per bushel.

Chapter 3: Linear Programming 17

 Crop Yield Labor Water Price
(bu./acre) (hours/acre) (acre-feet)/acre ($/bu.)
Wheat 120 3 5 4
Corn 200 4 6 2.5
Oats 180 2 2 1.5
soybeans 170 8 4 3.5

The farmer wishes to produce at least 20,000 bushels of wheat and 25,000 bushels of corn,
but no more than 30,000 bushels of oats. He plans to work up to 2,000 hours during the
season and he also does not wish to exceed the water supply of 1,500 acre-feet allocated to
the farm.
The farmer is interested in developing the optimal number of acres for each crop should
plan in order to maximize the total revenue.

Chapter 3: Linear Programming 18

References
Eppen, G.and F. Gould, Quantitative Concepts for Management: Decision Making without Algorithms,
Prentice-Hall, 1979
Dorfman, R., P. A. Samuelson and R. M. Solow, Linear Programming and Economic Analysis, McGraw
Hill, 1958
Dantzig, G., Linear Programming and Extensions, Princeton University Press, 1963.
Shapiro, J., Mathematical Programming: Structures and Algorithms, Wiley, 1979.
Murty, K., Linear and Combinatorial Programming, Wiley, 1976.
Wagner, H., Principles of Operations Research, Prentice Hall, 1969.

Chapter 3: Linear Programming 19

Chapter 5: Sensitivity Analysis 20