4 Show that if ties are broken in favor of lower-numberedrows, then cycling occurs when the simplex method is usedto solve the following LP:max z = -3x1 + x2 – 6x39x1 + x2 - 9x3 – 2x4 5 0Xi + - 2x3 - s 0-9x1 - x2 + 9x3 + 2x4 < 1X, 2 0 (i = 1, 2, 3, 4)

Given: max z=-3x1+x2-6x39x1+x2-9x3-2x4≤0x1+x23-2x3-x43≤0-9x1-x2+9x3+2x4≤1xi≥0 (i=1, 2, 3, 4) To…

Answered: 4 Show that if ties are broken in favor…

Advanced Engineering Mathematics

10th Edition

ISBN:9780470458365

Author:Erwin Kreyszig

Publisher:Erwin Kreyszig

Chapter2: Second-order Linear Odes

Section: Chapter Questions

Problem 1RQ

See similar textbooks

Related questions

Question

4 Show that if ties are broken in favor of lower-numbered
rows, then cycling occurs when the simplex method is used
to solve the following LP:
max z = -3x1 + x2 – 6x3
9x1 + x2 - 9x3 – 2x4 5 0
Xi + - 2x3 - s 0
-9x1 - x2 + 9x3 + 2x4 < 1
X, 2 0 (i = 1, 2, 3, 4)

Expert Solution

Step 1

Given:

$m a x z = - 3 x_{1} + x_{2} - 6 x_{3} 9 x_{1} + x_{2} - 9 x_{3} - 2 x_{4} \leq 0 x_{1} + \frac{x_{2}}{3} - 2 x_{3} - \frac{x_{4}}{3} \leq 0 - 9 x_{1} - x_{2} + 9 x_{3} + 2 x_{4} \leq 1 x_{i} \geq 0 (i = 1, 2, 3, 4)$

To show that cycling occurs when ties are broken in favour of lower-numbered rows, we need to show that the initial tableau has multiple optimal solutions.

Linear programming problem (LP):

A linear programming problem (LP) is a type of optimisation problem where the goal is to maximise or minimise a linear objective function subject to a set of linear constraints. The linear objective function and constraints can be written in the form of linear equations or inequalities involving a set of decision variables. The decision variables represent the quantities to be determined or optimised. The LP problem seeks to find the values of the decision variables that satisfy the constraints and optimise the objective function. Linear programming problems have numerous real-world applications, including production planning, transportation, resource allocation, and portfolio optimisation. Linear programming can be solved using various algorithms, such as the simplex method or interior point methods.

Step 2

The initial tableau for the given LP is:

x_1	x_2	x_3	x_4	RHS
-3	1	-6	0	0
9	1	-9	-2	0
1	$\frac{1}{3}$	-2	$- \frac{1}{3}$	0
-9	-1	9	2	1

Step 3

To apply the simplex method, we first choose the most negative coefficient in the objective row, which is -3 in this case. We then choose the pivot element in the column corresponding to $x_{1}$ , which is 9 in the second row. We divide the second row by 9 to get a 1 in the pivot position and then use row operations to get zeros in the rest of the column:

x_1	x_2	x_3	x_4	RHS
0	$\frac{2}{3}$	-3	$\frac{2}{3}$	0
1	$\frac{1}{9}$	-1	$- \frac{2}{9}$	0
0	$\frac{2}{27}$	-1	$- \frac{5}{27}$	0
0	8	-6	18	1

Step 4

The next pivot element is in the column corresponding to $x_{2}$ , which has a tie between the first and fourth rows. According to the tie-breaking rule, we choose the lower-numbered row (the first row) as the pivot row. The pivot element is $\frac{2}{3}$ in the first row, so we divide the first row by $\frac{2}{3}$ to get a 1 in the pivot position and then use row operations to get zeros in the rest of the column: