Operations Research

Introduction to Linear
Programming
BY
GROUP ONE
 Group Members

STUDENT NAME STUDENT ID NUMBER

Sianamate Samuel 2104035934
Sichinga Davies 2104035847
Namuchimba Annet 2104037093
Chipamba Flaviour 2104036022
Manda Kondwani 2104033576
Phiri Shadrack 2104036074
Banda Veliano 2104033672
 Table of Contents
Introduction to Linear Dual Linear Program
Programming – Understanding the dual problem
– Definition, applications, and Decision-Making Under Uncertainty
key components – Maximax, Maximin, and Minimax
Formulation of the LP Problem regret criteria
– Real-world scenario: Esther’s Summary & Key Takeaways
Bakery – Recap of methods and insights
Graphical Solution Method gained
– Plotting constraints and Questions & Answers
identifying feasible region – Open floor for discussion
Simplex Method
– Tableau construction and
pivoting process
Slack Variables
– Why we add them and how
they work
Introduction to Linear Programming

 Linear Programming (LP) is used to optimize outcomes based on constraints.

 It involves an objective function and a set of constraints.

•Applications: LP is widely used in business, economics,

military, transportation, manufacturing, and agriculture.
•Goal: To optimize (maximize or minimize) a linear objective
function, subject to a set of linear constraints (equalities or
inequalities).
 Key Components

•Objective Function: The function to be optimized, e.g.,

maximize profit: Z = 5x + 3y
•Decision Variables: Variables like x and y that determine
the outcome.
•Constraints: Limitations or requirements such as x + y ≤ 100.
•Non-negativity Restrictions: Typically, variables cannot be
negative (x, y ≥ 0).
 Formulation of the LP Problem

Steps to Formulate
1. Identify decision variables – What are you trying to determine?
(e.g., number of units to produce)
2. Form the objective function – Define what you want to maximize or
minimize.
3. Identify constraints – Translate resources, capacity, or conditions into
inequalities.
4. Include non-negativity – Ensure variables are ≥ 0.
Three Solving Methos Of a Linear
Programming
I. Graphical Solution Method

II. Simplex Method

III. Dual Method

 Real-world Scenario
Esther runs a small bakery where she produces scones and cakes. Each
product requires a combination of labor and baking materials, and each
contributes to her total weekly profit.

• Each scone requires 2 hours of labor and 4 kg of material, yielding a profit

of $6 per unit.

• Each cake requires 3 hours of labor and 2 kg of material, yielding a profit of

$5 per unit.

• Esther has a total of 60 hours of labor and 48 kg of material available each

week.

Her goal is to determine how many scones and cakes she should produce in
a week in order to maximize her profit, without exceeding the available labor
and materials.
 Graphical Solution Method

This method solves LPPs with two variables (x and y) by plotting constraints on a graph.

STEPS TO CONSIDER

1.Plot all constraints on an x-y graph.

2.Identify the feasible region (area that satisfies all constraints).

3.Evaluate the objective function at corner points (vertices) of the feasible region.

4.Choose the point that gives the maximum or minimum value of the objective function.
Graphical Solution
 Graphical Solution to the
Maximization or Minimization
Problem
Whether you're maximizing profit or minimizing cost:

•Maximization: Find the vertex where the objective function is highest.

•Minimization: Find the vertex where the objective function is lowest.

Use objective function line (e.g., Z = 6x + 5y) to slide along the feasible region and

identify the best value.

Note: This method only works well with 2 variables

Corner Points and Objective Values

Z = 6x + 5x

(0, 0): Z = 0

(0, 20): Z = 100

(3, 18): Z = 108 (Optimal)

(12, 0): Z = 72
 The Simplex Method

The Simplex Method is a more advanced algebraic technique used

when the problem has more than two variables, making graphical
methods impractical.
Overview:
 Developed by George Dantzig.
 Iteratively moves from one vertex (corner point) of the feasible
region to another.
 Stops when the optimal value is found.
Uses: Solves both maximization and minimization problems.
The Simplex Method Procedure

1. Convert inequalities into equalities using slack/surplus variables.

2. Set up the initial simplex tableau.
3. Identify pivot column (most negative indicator in the bottom row
for maximization).
4. Identify pivot row using the minimum ratio test.
5. Perform row operations to make pivot element 1 and other
column elements 0.
6. Iterate the process until there are no more negative values in the
bottom row (for maximization).
 Final Tableau gives the optimal values of decision variables and
the objective function.
Solving Solution for Simplex Method
Step 2: Initial Simplex Tableau
Step 1: Convert to Standard Form

X Y S1 S2 Z Total
Introduce slack variables s₁
and s₂ to convert
2 3 1 0 0 60
inequalities into
equations:
4 2 0 1 0 48
2x+3y+s1=60
4x+2y+s2=48
-6 -5 0 0 1 0
Objective function becomes:
Z = 6x + 5y ⇒ Z − 6x − 5y = 0
 Pivot Operations (Make Pivot = 1
and rest of column
Step 3: Identify Pivot Column (Entering
= 0)
Variable)
X Y S1 S2 Z Total
Look at the Z-row:
•Most negative value is -6 → So, x enters
the basis.
2 3 1 0 0 60
Step 4: Identify Pivot Row (Leaving
Variable) 1 ½ 0 0 0 12
 Do the Minimum Ratio Test:
60 48
= 30→ (Row1) and = 12→ (Row2)
2 4 -6 -5 0 0 1 0
 Row 2 is the pivot row, and 4 (in
column x) is the pivot element.
FINAL OUTCOME AFTER ITERATION

X Y S1 S2 Z Total Optimal Solution

No more negative values in Z-row →

0 1 ½ -1/4 0 18 Optimal reached
Solution:
• x = 3 (scones)
1 0 -1/4 3/8 0 3 • y = 18 (cakes)
• Maximum Z = K108

0 0 1 1 0 108
 The Dual Linear Program

 Dual provides resource  2. Constraints Become Variables

valuation (shadow prices). Each constraint in the primal
corresponds to a variable in the
dual. This means that if the primal
has 2 constraints, the dual will have 2
variables each representing the
value (or cost) of using one unit of
1. Maximization ↔ Minimization the resource.
When converting a linear
program, a maximization problem
in the primal becomes a  3. Objective Coefficients Become
minimization problem in the dual, RHS Values
and vice versa. This reflects a shift The coefficients of the objective
function in the primal appear as the
from optimizing outcomes to right-hand side (RHS) values in the
minimizing resource usage or cost. dual. Similarly, the RHS values from
the primal become the objective
function coefficients in the dual.
 Summary and Key Takeaways

 Linear Programming helps in optimizing decisions under constraints.

 Graphical method works for two-variable problems.

 Simplex method extends Linear Programming to higher dimensions.

 Dual problems provide economic interpretations.

 References
Taha, H. A. (2017). Operations Research: An Introduction (10th ed.). Pearson Education.
➤ Covers formulation, graphical method, simplex, and duality.
Hillier, F. S., & Lieberman, G. J. (2021). Introduction to Operations Research (11th ed.). McGraw-Hill.
➤ A comprehensive resource for LP methods and decision models.
Sharma, J. K. (2013). Operations Research: Theory and Applications (5th ed.). Macmillan India.
➤ Useful for step-by-step LP problem solving.
•Winston, W. L. (2004). Operations Research: Applications and Algorithms (4th ed.). Cengage
Learning.
➤ A practical and application-based text with clear simplex method explanations.
YouTube Channel: Maths Partner.
➤ Visual LP tutorials and simplex demonstrations: https://www.youtube.com/c/MathsPartner
OpenAI. (2024). Assistance in preparing slides, graphical solutions, and dual formulation explanation
using AI-generated content.
END OF PRESENTATION