Question

Solve the following linear programming problem by simplex method: Maximize

    $z= 3x_1+5x_2+4x_3$

subject to

    $2x_1+3x_2\leq8 \\ 2x_2+5x_3\leq10 \\ 3x_1 + 2x_2 + 4x_3 \leq 15 \\ x_1,x_2,x_3 \geq 0.$

Answer 1

Adding slack variables, $x_4, x_5, x_6$, we get the simplex table as follows:

Base	$C_b$	$b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$b/a$
$x_4$	0	8	2	3	0	1	0	0	$\frac{8}{3}$
$x_5$	0	10	0	2	5	0	1	0	5
$x_6$	0	15	3	2	4	0	0	1	$\frac{15}{2}$
Z		0	-3	-5	-4	0	0	0

Taking pivot variable as indicated, 

Base	$C_b$	$b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$b/a$
$x_2$	5	$\frac{8}{3}$	$\frac{2}{3}$	1	0	$\frac{1}{3}$	0	0	-
$x_5$	0	$\frac{14}{3}$	$\frac{-4}{3}$	0	5	$\frac{-2}{3}$	1	0	$\frac{14}{15}$
$x_6$	0	$\frac{29}{3}$	$\frac{5}{3}$	0	4	$\frac{-2}{3}$	0	1	$\frac{29}{12}$
Z		$\frac{40}{3}$	$\frac{1}{3}$	0	-4	$\frac{5}{3}$	0	0

Again taking pivot variable as indicated,

Base	$C_b$	$b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$b/a$
$x_2$	5	$\frac{8}{3}$	$\frac{2}{3}$	1	0	$\frac{1}{3}$	0	0	4
$x_3$	4	$\frac{14}{15}$	$\frac{-4}{15}$	0	1	$\frac{-2}{15}$	$\frac{1}{5}$	0	$\frac{-7}{2}$
$x_6$	0	$\frac{89}{15}$	$\frac{41}{15}$	0	0	$\frac{-2}{15}$	$\frac{-4}{15}$	1	$\frac{89}{41}$
Z		$\frac{256}{15}$	$\frac{-11}{15}$	0	0	$\frac{17}{15}$	$\frac{4}{5}$	0

Again taking the indicated element as pivot variable, we get the simplex table as:

Base	$C_b$	$b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$b/a$
$x_2$	5	$\frac{50}{41}$	0	1	0	$\frac{15}{41}$	$\frac{8}{41}$	$\frac{-10}{41}$	-
$x_3$	4	$\frac{62}{41}$	0	0	1	$\frac{-6}{41}$	$\frac{5}{41}$	$\frac{4}{41}$	-
$x_1$	3	$\frac{89}{41}$	1	0	0	$\frac{-2}{41}$	$\frac{-12}{41}$	$\frac{15}{41}$	-
Z		$\frac{765}{15}$	0	0	0	$\frac{45}{41}$	$\frac{24}{41}$	$\frac{11}{41}$

This gives us the optimal solution as 

    $z = \frac{765}{41}$

at

    $x_1 = \frac{89}{41} \\ x_2 = \frac{50}{41} and \\ x_3 = \frac{62}{41}$