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.$

Mathxyz - upsc.xyz

0 votes

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}$

37 questions

27 answers

2 comments

34 users