Operations Research

GRAPHICAL METHOD

wine production

Objective Function:

Maximize $50X_{1}+120X_{2}$

Constraints:

$X_{1}+X_{2}\leq 110$
$100X_{1}+200X_{2}\leq 10.000$
$10X_{1}+30X_{2}\leq 1.200$
$X_{1},X_{2}\geq 0$

SIMPLEX METHOD

Maximize z = 3x₁ + 2x₂

subject to:

-x₁ + 2x₂ ≤ 4
3x₁ + 2x₂≤ 14
x₁ – x₂ ≤ 3

x₁, x₂ ≥ 0

Converting inequalities to equalities

-x₁ + 2x₂ + x₃ = 4
3x₁ + 2x₂ + x₄ = 14
x₁ – x₂ + x₅ = 3
x₁, x₂, x₃, x₄, x₅ ≥ 0

Where x₃, x₄ and x₅ are slack variables.

Maximize z = 3x₁ + 2x₂ + 0x₃ + 0x₄ + 0x₅

x₁ = 0, x₂ = 0, z = 0
x₃ = 4, x₄ = 14, x₅ = 3

Simplex Method Examples, Operations Research

a₁₁ = -1, a₁₂ = 2, a₁₃ = 1, a₁₄ = 0, a₁₅ = 0, b₁ = 4
a₂₁ = 3, a₂₂ = 2, a₂₃ = 0, a₂₄= 1, a₂₅ = 0, b₂ = 14
a₃₁= 1, a₃₂ = -1, a₃₃ = 0, a₃₄ = 0, a₃₅ = 1, b₃= 3

Calculating values for the index row (z_j– c_j)

z₁– c₁ = (0 X (-1) + 0 X 3 + 0 X 1) – 3 = -3
z₂– c₂ = (0 X 2 + 0 X 2 + 0 X (-1)) – 2 = -2
z₃– c₃ = (0 X 1 + 0 X 0 + 0 X 0) – 0 = 0
z₄– c₄ = (0 X 0 + 0 X 1 + 0 X 0) – 0 = 0
z₅– c₅ = (0 X 0 + 0 X 0 + 0 X 1) – 0 = 0

Calculating values for table 2

x₃ row

a₁₁ = -1 – 1 X ((-1)/1) = 0
a₁₂ = 2 – (-1) X ((-1)/1) = 1
a₁₃ = 1 – 0 X ((-1)/1) = 1
a₁₄ = 0 – 0 X ((-1)/1) = 0
a₁₅ = 0 – 1 X ((-1)/1) = 1
b₁ = 4 – 3 X ((-1)/1) = 7

x₄ row

a₂₁ = 3 – 1 X (3/1) = 0
a₂₂ = 2 – (-1) X (3/1) = 5
a₂₃ = 0 – 0 X (3/1) = 0
a₂₄ = 1 – 0 X (3/1) = 1
a₂₅ = 0 – 1 X (3/1) = -3
b₂ = 14 – 3 X (3/1) = 5

x₁ row

a₃₁ = 1/1 = 1
a₃₂ = -1/1 = -1
a₃₃ = 0/1 = 0
a₃₄ = 0/1 = 0
a₃₅ = 1/1 = 1
b₃ = 3/1 = 3

Table 2

	c_j	3	2	0	0	0
c_B	Basic variables B	x₁	x₂	x₃	x₄	x₅	Solution values b (= X_B)
0	x₃	0	1	1	0	1	7
0	x₄	0	5	0	1	-3	5
3	x₁	1	-1	0	0	1	3
z_j-c_j		0	-5	0	0	3

(z_j– c_j)

z₁– c₁ = (0 X 0 + 0 X 0 + 3 X 1) – 3 = 0
z₂– c₂ = (0 X 1 + 0 X 5 + 3 X (-1)) – 2 = -5
z₃– c₃ = (0 X 1 + 0 X 0 + 3 X 0) – 0 = 0
z₄– c₄ = (0 X 0 + 0 X 1 + 3 X 0) – 0 = 0
z₅– c₅ = (0 X 1 + 0 X (-3) + 3 X 1) – 0 = 3

a₁₁ = 0 – 0 X (1/5) = 0
a₁₂ = 1 – 5 X (1/5) = 0
a₁₃= 1 – 0 X (1/5) = 1
a₁₄ = 0 – 1 X (1/5) = -1/5
a₁₅ = 1 – (-3) X (1/5) = 8/5
b₁ = 7 – 5 X (1/5) = 6

x₂ row

a₂₁ = 0/5 = 0
a₂₂ = 5/5 = 1
a₂₃ = 0/5 = 0
a₂₄ = 1/5
a₂₅ = -3/5
b₂ = 5/5 = 1

x₁ row

a₃₁ = 1 – 0 X (-1/5) = 1
a₃₂ = -1 – 5 X (-1/5) = 0
a₃₃ = 0 – 0 X (-1/5) = 0
a₃₄ = 0 – 1 X (-1/5) = 1/5
a₃₅ = 1 – (-3) X (-1/5) = 2/5
b₃ = 3 – 5 X (-1/5) = 4