Year: 2024-2025

Spring Semester

Introduction to Operations Research

and Decision Support
Dr. Amany Magdy
Dr. Hillal M. Elshehabey
 Revision

2
 Linear Programming Models

3
 Optimal Solution for New Objective Function
Graphical Solution of Maximization Model
Maximize Z = $40x1 + $50x2 Maximize Z = $70x1 + $20x2
subject to: 1x1 + 2x2  40 subject to: 1x1 + 2x2  40
4x1 + 3x2  120 4x1 + 3x2  120
x1, x2  0 x1, x2  0

Altering the objective

function coefficients
results in a new solution.
 Graphical Solution of Minimization Model

5
Fertilizing farmer’s field
Graphical Solution of Minimization Model (1 of 3)

Minimize Z = $6x1 + $3x2

subject to: 2x1 + 4x2  16
4x1 + 3x2  24
x1, x2  0

Constraint lines for fertilizer model

Fertilizing farmer’s field
Graphical Solution of Minimization Model (2 of 3)

Minimize Z = $6x1 + $3x2

subject to: 2x1 + 4x2  16
4x1 + 3x2  24
x1, x2  0

Feasible solution area

Fertilizing farmer’s field
Graphical Solution of Minimization Model (3 of 3)

Minimize Z = $6x1 + $3x2

subject to: 2x1 + 4x2  16
4x1 + 3x2  24
x1, x2  0

The optimal solution of a minimization

problem is at the extreme point closest
to the origin.

The optimal solution point

Summary of the Graphical Solution Steps

• The steps for solving a graphical linear programming model are

summarized here:
1. Plot the model constraints as equations on the graph; then, considering the
inequalities of the constraints, indicate the feasible solution area.
2. Plot the objective function; then, move this line out from the origin to
locate the optimal solution point.
3. Solve simultaneous equations at the solution point to find the optimal
solution values.

9
 Slack and Surplus Variables

10
Slack Variables – Maximization Model (1 of 2)

• Standard form requires that all constraints be in the form of

equations (equalities).
• A slack variable is added to a  constraint (weak inequality) to
convert it to an equation (=).
• A slack variable typically represents an unused resource.
• A slack variable contributes nothing to the objective function
value.
Beaver Creek Pottery Company – Maximization Model (2 of 2)

Max Z = 40x1 + 50x2 + 0s1 + 0s2

subject to:
1x1 + 2x2 + s1 = 40
4x1 + 3x2 + s2 = 120
x1, x2, s1, s2  0
Where:
x1 = number of bowls
x2 = number of mugs
s1, s2 are slack variables

Solutions at points A, B, and C with slack

Surplus Variables – Minimization Model (1 of 2)
• A surplus variable is subtracted from a  constraint to convert it to
an equation (=).

• A surplus variable represents an excess above a constraint

requirement level.

• A surplus variable contributes nothing to the calculated value of the

objective function.

• Subtracting surplus variables in the farmer problem constraints:

2x1 + 4x2 - s1 = 16 (nitrogen)
4x1 + 3x2 - s2 = 24 (phosphate)
Fertilizing farmer’s field – Minimization Model (2 of 2)

Minimize Z = $6x1 + $3x2 + 0s1 + 0s2

subject to:
2x1 + 4x2 – s1 = 16
4x1 + 3x2 – s2 = 24
x1, x2, s1, s2  0
Where:
x1 = bags of Super-gro
x2 = bags of Crop-quick
s1, s2 are slack variables

Graph of the fertilizer example

 Irregular Types of Linear Programming
Problems

15
For some linear programming models, the general rules do not apply.

Special types of problems include those with:

• Multiple optimal solutions
• Infeasible solutions
• Unbounded solutions
Multiple Optimal Solutions - Beaver Creek Pottery (1 of 4)

• Consider the Beaver Creek Pottery Company example, with the objective
function changed from Z = $40x1 + $50x2 to Z=$40x1 + 30x2.

Maximize Z=$40x1 + 30x2

subject to: 1x1 + 2x2  40
4x1 + 3x2  120
x1, x2  0

• The slight change in the objective function makes it now parallel to the
constraint line, 4x1 + 3x2 = 120
Multiple Optimal Solutions - Beaver Creek Pottery (2 of 4)

The objective function is parallel to

a constraint line.
Maximize Z=$40x1 + 30x2
subject to:
1x1 + 2x2  40
4x1 + 3x2  120
x1, x2  0
Where:
x1 = number of bowls
x2 = number of mugs

Example with multiple optimal solutions

Multiple Optimal Solutions - Beaver Creek Pottery (3 of 4)
• Therefore, as the objective function edge moves outward from the origin, it touches
the whole line segment BC rather than a single extreme corner point before it
leaves the feasible solution area.

• This means that every point along this line segment is optimal (i.e., each point
results in the same profit of 𝑍 = $1,200).

• The endpoints of this line segment, B and C, are typically referred to as the
alternate optimal solutions.

• Alternate optimal solutions are at the endpoints of the constraint line segment that
the objective function parallels.
Multiple Optimal Solutions - Beaver Creek Pottery (4 of 4)

• The pottery company, therefore, has several options in deciding on the number of
bowls and mugs to produce.

• Multiple optimal solutions can benefit the decision maker because the number of
decision options is enlarged.

• The multiple optimal solutions (along the line segment BC ) allow the decision
maker greater flexibility. For example, in the case of Beaver Creek Pottery
Company, it may be easier to sell bowls than mugs; thus, the solution at point C,
where only bowls are produced, would be more desirable than the solution at
point B, where a mix of bowls and mugs is produced.
An Infeasible Problem – (1 of 3)

In some cases, a linear programming problem

has no feasible solution area; thus, there is no
solution to the problem.

Every possible solution violates at least one

constraint:
Maximize Z = 5x1 + 3x2
subject to:
4x1 + 2x2  8
x1  4
x2  6
x1, x2  0 Graph of an infeasible problem
An Infeasible Problem – (2 of 3)

• Point A in satisfies only the constraint,

4x1 + 2x2  8
• whereas point C satisfies only the
constraints x1  4 and x2  6
• Point B satisfies none of the constraints.
• The three constraints do not overlap to
form a feasible solution area.

Graph of an infeasible problem

An Infeasible Problem – (3 of 3)

• Because no point satisfies all three

constraints simultaneously, there is no
solution to the problem.

• Infeasible problems do not typically

occur, but when they do, they are usually
a result of errors in defining the problem
or in formulating the linear programming
model.

Graph of an infeasible problem

An Unbounded Problem – (1 of 2)

In some problems, the feasible solution area

formed by the model constraints is not closed.

Value of the objective function increases

indefinitely without ever reaching a maximum
value because it never reaches the boundary of
the feasible solution area.
Maximize Z = 4x1 + 2x2
subject to:
x1  4
x2  2
x1, x2  0
Graph of an unbounded problem
An Unbounded Problem – (2 of 2)

Unlimited profits are not possible in the real

world; an unbounded solution, like an infeasible
solution, typically reflects an error in defining
the problem or in formulating the model.

Graph of an unbounded problem

 Characteristics and Properties of Linear
Programming Models

26
Characteristics of Linear Programming Problems (1 of 1)
• A linear programming problem requires a choice between alternative courses of
action (i.e., a decision).
• The decision is represented in the model by decision variables.
• Identifying the choice task and defining the decision variables is usually the first
step in the formulation process because it is quite difficult to construct the
objective function and constraints without first identifying the decision variables.
• The problem encompasses a goal, expressed as an objective function, that the
decision maker wants to achieve.
• Restrictions (represented by constraints) exist that limit the extent of
achievement of the objective.
• The objective and constraints must be definable by linear mathematical functional
relationships.
Properties of Linear Programming Models (1 of 5)

• Proportionality - The rate of change (slope) of the objective function and constraint
equations is constant.

• Additivity - Terms in the objective function and constraint equations must be

additive.

• Divisibility - Decision variables can take on any fractional value and are therefore
continuous as opposed to integer in nature.

• Certainty - Values of all the model parameters are assumed to be known with
certainty (non-probabilistic).
Properties of Linear Programming Models (2 of 5)

• The term linear not only means that the functions in the models are graphed as a
straight line; it also means that the relationships exhibit proportionality.

• In other words, the rate of change, or slope, of the function is constant; therefore,
changes of a given size in the value of a decision variable will result in exactly
the same relative changes in the functional value.
Properties of Linear Programming Models (3 of 5)

• Linear programming also requires that the objective function terms and the
constraint terms be additive.

• For example, in the Beaver Creek Pottery Company model, the total profit (𝑍)
must equal the sum of profits earned from making ($40𝑥1 ) bowls and ($50𝑥2 )
mugs.

• Also, the total resources used must equal the sum of the resources used for each
activity in a constraint (e.g., labor).
Properties of Linear Programming Models (4 of 5)

• Another property of linear programming models is that the solution values (of
the decision variables) cannot be restricted to integer values; the decision
variables can take on any fractional value. Thus, the variables are said to be
continuous or divisible, as opposed to integer or discrete.

• For example, although decision variables representing bowls or mugs or

airplanes or automobiles should realistically have integer (whole number)
solutions, the solution methods for linear programming will not necessarily
provide such solutions.
Properties of Linear Programming Models (5 of 5)

• The final property of linear programming models is that the values of all the
model parameters are assumed to be constant and known with certainty.

• In real situations, however, model parameters are frequently uncertain because

they reflect the future as well as the present, and future conditions are rarely
known with certainty.