UoBOpt

•  Proportionality 

– Cost of a decision increases linearly

• Additivity

– Costs of different decisions can be added

• Divisibility

– Decisions can take fractional values

• Certainty

– Each parameter is known in advance with certainty

• Parameters - numerical coefficients and constants used 

in the objective function and constraints - DATA.

• No data, no problem to solve. Low quality data, low 

quality results. GIGO.

• Decision variables - mathematical symbols 

representing levels of activity by the firm.

• Objective function - a linear mathematical relationship 

describing an objective of the firm, in terms of decision 

variables - this function is to be maximized or minimized.

• Constraints – requirements or restrictions placed on the 

firm by the operating environment, stated in linear 

relationships of the decision variables.

• Step 1 : Define the decision variables

• Step 2 : Define the objective function

• Step 3 : Define the constraints

Infeasibility is a common mathematical occurrence but 

it is unacceptable in a business setting

1. Check your data for inconsistencies. Unfortunately, there is 

no automated process for generic LPs. Use your data 

analysis skills. 

2. Make sure that there are no unnecessary equality 

constraints

3. Remove inequality constraints from the problem one at a 

time to identify the problematic constraint(s)

4. Alternatively, remove all inequality constraints and add them 

back one at a time to identify the problematic constraint(s)

5. Use Goal Programming (to be covered in week 5)

Unboundedness is not as common as infeasibility, 

but it is equally annoying

1. Add a constraint that forces a (large) bound on the 

objective function. E.g. Maximize Z = 4x 1  + 2x 2  ->        

Add 4x 1  + 2x 2  100000

2. Solve the problem and analyze the result to see the type 

of solution it results in, and identify the missing 

constraint(s)

3. Sometimes it is useful to add a small objective function 

coefficient to the variables which have an objective 

function coefficient of 0. E.g. Maximize Z = 4x 1  + 0x 2  ->  

Maximize Z = 4x 1  - 0.0001x 2  

• Sensitivity analysis determines the effect on the optimal 

solution of changes in parameter values of the objective 

function and constraint equations.

• Changes to 

– Objective function coefficients (e.g. cost / profit values)

– Right hand side coefficients (e.g. amount of a resource)

– Adding a constraint or removing a constraint

• Although interesting from a theoretical point of view, most 

sensitivity analysis is done by what-if analysis on large 

problems

• The most important piece of information returned by 

sensitivity analysis is “shadow prices”

• Defined as the marginal value of one additional 

unit of resource.

• The sensitivity range for a constraint quantity 

value is also the range over which the shadow 

price is valid.

• Useful for answering the questions:

– How much should I pay for acquiring more of a 

resource?

– How much should I charge for selling / leasing some 

of my resources?

■ Let us define two binary variables xA and xB
■ xA= 1 if we decide to take action A, 0 otherwise
■ xB= 1 if we decide to take action B, 0 otherwise
■ How can we state the following in a formulation?

■ If we decide to take action A, we must also take 
action B. It is possible to take action B without 
taking action A.
  ■ xA ≤ xB
■ We must decide to take either action A or action B 
but not both
  ■ xA+ xB= 1
■ We cannot take both actions A and B
  ■ xA+ xB≤ 1

• Unlike LP, the solution is often not on the 
boundary of the feasible  solution space.
• Cannot simply look at points on the solution 
space boundary but must consider other points 
on the surface of the objective function.
• This greatly  complicates solution approaches.

• An undirected graph G = (N, E) consists of 
– A set of nodes N representing the supply and demand points.
– A set E of unordered pairs of nodes called edges representing the 
pathways joining pairs of nodes.
• We say that the edge (i, j) is incident to nodes i and j, and i and j
are its endpoints.
• An undirected graph is said to be connected if for every pair of 
nodes i and j, there is a path from i to j.
• θ(i) denotes the set of nodes that are connected to node i through 
edges.

• Study of problems with several criteria, i.e., multiple 
criteria, instead of a single objective when making a 
decision.
• Goal programming is a variation of linear programming 
considering more than one objective (goals) in the objective 
function.
• Scoring models are based on a relatively simple weighted 
scoring technique.
• When the objective functions have a strict order of priority, 
the are called lexicographically ordered objectives. 
These can be solved by a series of optimization problems.

• A directed graph G = (N, A) consists of a set of N nodes and a set 
A of ordered pairs of nodes called arcs.
• For any arc (i, j), we say that j is the head and i is the tail.
• The arc (i, j) is said to be outgoing from node i and incoming to 
node j and incident to both i and j.
• We define 
– I(i) as the set of nodes which are connected to i through arcs ( j, i )
– O(i) as the set of nodes which are connected to i through arcs ( i, j )
• A directed graph is connected if the underlying undirected graph 
is connected.

• A path is a sequence of nodes connected by arcs (i
1
,…, i
t
) in 
which no node is repeated.
• A cycle is a path with i
1
= i
t
, t > 2.
• A graph is a tree if it is connected and acyclic (has no cycles).
• Properties of trees
– An undirected graph is a tree if and only if it is connected and has |N|-1 
edges.
– For any two distinct nodes i and j in a tree, there exists a unique path from 
i to j.
– If we add an edge to a tree, the resulting graph contains exactly one cycle.