Scribd
Upload
4 views2 pages

Simplex Algorithm

The document outlines the steps for solving linear programming problems using the Simplex Algorithm. It includes preparation of constraints and objective functions, construction of the initial simplex table, optimality checks, and the process of building iteration tables. Each step is detailed with specific calculations and criteria for determining key variables and elements.

Uploaded by

janaarnesh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views2 pages

Simplex Algorithm

The document outlines the steps for solving linear programming problems using the Simplex Algorithm. It includes preparation of constraints and objective functions, construction of the initial simplex table, optimality checks, and the process of building iteration tables. Each step is detailed with specific calculations and criteria for determining key variables and elements.

Uploaded by

janaarnesh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Quantitative Methods, BBA - 207

(Prepared by Prof. Sreeparna Guha, IEM Kolkata)

Simplex Algorithm for solving Linear programming problem:


**Follow the following steps while solving problem
𝒄𝒋 − 𝐶𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 (𝐶𝑜𝑠𝑡) 𝑜𝑓 𝑡ℎ𝑒 𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑏𝑗𝑒𝑐𝑡𝑖𝑣𝑒 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛

𝐵 − 𝐼𝑛𝑖𝑡𝑖𝑎𝑙 𝐵𝑎𝑠𝑖𝑐 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠


𝐶𝐵𝑗 − 𝐶𝑜𝑒𝑓𝑓𝑒𝑐𝑖𝑒𝑛𝑡(𝑐𝑜𝑠𝑡) 𝑜𝑓 𝑡ℎ𝑒 𝑏𝑎𝑠𝑖𝑐 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑏𝑗𝑒𝑐𝑡𝑖𝑣𝑒 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛

𝑋𝑗 − 𝑐𝑜𝑙𝑢𝑚𝑛 𝑐𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑣𝑒𝑐𝑡𝑜𝑟𝑠 𝑓𝑜𝑟 𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠

Step – 1 (Preparation of constraints & objective function)


Prepare & adjust the objective function and the constraints by introducing slack/surplus
variables.

Step – 2
Construct the initial simplex table (Table – I). The format is below

𝑐𝑗 Solution
𝐶𝐵𝑗
Basic Variables
𝑋𝑗
(B)

𝑍𝑗

𝑍𝑗 − 𝑐𝑗
Step – 3(Optimality Check)
Calculate 𝑍𝑗 = ∑ 𝐶𝐵𝑗 𝑋𝑗

Calculate 𝑍𝑗 − 𝑐𝑗

For optimality: 𝑍𝑗 − 𝑐𝑗 ≥ 0 , (𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑎𝑡𝑖𝑜𝑛 𝑝𝑟𝑜𝑏𝑙𝑒𝑚). If for all ‘j’ the optimality condition
satisfies then terminate the process. But if for any ‘j’ 𝑍𝑗 − 𝑐𝑗 < 0 then proceed to next step.

Step – 4(Key Row & Key Column)


Choose 𝑍𝑗 − 𝑐𝑗 value with the most negative value.

Mark the corresponding column as “Key Column”


Calculate ratio of corresponding members of solution column & key column. Observe the
minimum value of ratios.
Mark the row with minimum ratio value as “Key Row”
Mark the element common to both key row & key column as “Key element”
**The variable corresponding to key element will enter the basic variable column in
place of corresponding basic variable in the key row.

Step – 5 (Building Iteration Table)


New values in the iteration table –
Divide the key row of the initial table by key element.
For the other rows –
𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑖𝑛𝑔 𝑘𝑒𝑦 𝑟𝑜𝑤 𝑣𝑎𝑙𝑢𝑒 × 𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑖𝑛𝑔 𝑘𝑒𝑦 𝑐𝑜𝑙𝑢𝑚𝑛 𝑣𝑎𝑙𝑢𝑒
New value = Old value –
𝐾𝑒𝑦 𝑒𝑙𝑒𝑚𝑒𝑛𝑡

After completion of the above calculation go back to Step – 3


≤

You might also like