1
2
Linear Programming
Optimization is an important and fascinating area of management science
and operations research. It helps to do less work, but gain more.
Applicability: There are many real–
world applications that can be
modeled as linear programming;
Solvability: There are theoretically
and practically efficient techniques
for solving large-scale problems.
Hi! My name is Cathy. I will guide you in tutorials during the
semester.
In this tutorial, we introduce the basic elements of an LP and
present some examples that can be modeled as an LP. In the
next tutorials, we will discuss solution techniques.
Linear programming (LP) is a
central topic in optimization. It
provides a powerful tool in
modeling many applications. LP
has attracted most of its attention
in optimization during the last six
decades for two main reasons:
3
Basic Components of an LP:
Each optimization problem consists of three elements:
decision variables: describe our choices that are under our control;
objective function: describes a criterion that we wish to minimize
(e.g., cost) or maximize (e.g., profit);
constraints: describe the limitations that restrict our choices for
decision variables.
Formally, we use the term “linear programming (LP)”
to refer to an optimization problem in which the objective
function is linear and each constraint is a linear inequality
or equality. I’ll discuss these features soon.
4
An Introductory Example
I am a bit confused about the LP
elements. Can you give me more
details.
Let’s start with an example. I’ll describe it first in words, and then
we’ll translate it into a linear program.
Oh! I forgot to introduce myself. I am To m ; a
new member of the 15.053 class. I am
interested in learning linear programming. I
will be with you during the tutorials.
5
An Introductory Example
Problem Statement: A company makes two products (say, P and Q)
using two machines (say, A and B). Each unit of P that is produced
requires 50 minutes processing time on machine A and 30 minutes
processing time on machine B. Each unit of Q that is produced requires
24 minutes processing time on machine A and 33 minutes processing
time on machine B.
Machine A is going to be available for 40 hours and machine B is available
for 35 hours. The profit per unit of P is $25 and the profit per unit of Q
is $30. Company policy is to determine the production quantity of each
product in such a way as to maximize the total profit given that the
available resources should not be exceeded
Task: The aim is to formulate the problem of deciding how much of each product to
make in the current week as an LP.
6
Step 1: Defining the Decision Variables
The company wants to determine the optimal
product to make in the current week. So there are
two decision variables:
x: the number of units of P
y: the number of units of Q
We often start with identifying decision variables (i.e., what we want
to determine among those things which are under our control).
Tom! Can you identify the decision variables for our example?
Good job! Let’s move on to
the second step.
Step 2: Choosing an Objective Function
We usually seek a criterion (or a measure) to compare alternative solutions. This
yields the objective function.
Tom! It is now your turn to identify the objective function.
We want to maximize the total profit. The profit per each unit of
product P is $25 and profit per each unit of product Q is $30.
Therefore, the total profit is 25x+30y if we produce x units of P
and y units of Q. This leads to the following objective function:
