solution.tex

\begin{flushleft}Given the following linear system and objective function, find the optimal solution.\end{flushleft}\begin{equation*}\max{ 8623089553905663/4503599627370496x_1 + 4642729142352447/562949953421312x_2 + 67104339147525/70368744177664x_3 + 8623089553905663/4503599627370496x_4 + 2341124474634787/281474976710656x_5 + 2181830497379145/2251799813685248x_6 + 4642729142352447/562949953421312x_7 + 2341124474634787/281474976710656x_8 + 1169966892480561/140737488355328x_9 + 67104339147525/70368744177664x_10 + 2181830497379145/2251799813685248x_11 + 1169966892480561/140737488355328x_12 } \\ \end{equation*}\[\left\{\begin{array}{c}- -4y_5 - y_13 + y_14 \geq -3 \\ - -4y_6 - y_13 + y_15 \geq -3 \\ - -4y_8 + y_13 - y_14 \geq -3 \\ - -4y_9 - y_14 + y_15 \geq -3 \\ - -4y_11 + y_13 - y_15 \geq -3 \\ - -4y_12 + y_14 - y_15 \geq -3 \\ - y_1 - y_2 - y_3 \geq -1 \\  y_1 + y_2 + y_3 \geq 1 \\ - y_4 - y_5 - y_6 \geq -1 \\  y_4 + y_5 + y_6 \geq 1 \\ - y_7 - y_8 - y_9 \geq -1 \\  y_7 + y_8 + y_9 \geq 1 \\ - y_10 - y_11 - y_12 \geq -1 \\  y_10 + y_11 + y_12 \geq 1 \\ - y_4 - y_7 - y_10 \geq -1 \\  y_4 + y_7 + y_10 \geq 1 \\ - y_1 - y_8 - y_11 \geq -1 \\  y_1 + y_8 + y_11 \geq 1 \\ - y_2 - y_5 - y_12 \geq -1 \\  y_2 + y_5 + y_12 \geq 1 \\ - y_3 - y_6 - y_9 \geq -1 \\  y_3 + y_6 + y_9 \geq 1 \\ \end{array}\right.\]\begin{flushleft}\textbf{Solution}\end{flushleft}\begin{flushleft}Add slack variables to turn all inequalities to equalities.\end{flushleft}\[\left\{\begin{array}{c}- y_7 + y_8 - y_17 + y_18 + s_1 = 8623089553905663/4503599627370496 \\ - y_7 + y_8 - y_19 + y_20 + s_2 = 4642729142352447/562949953421312 \\ - y_7 + y_8 - y_21 + y_22 + s_3 = 67104339147525/70368744177664 \\ - y_9 + y_10 - y_15 + y_16 + s_4 = 8623089553905663/4503599627370496 \\ - -4y_1 - y_9 + y_10 - y_19 + y_20 + s_5 = 2341124474634787/281474976710656 \\ - -4y_2 - y_9 + y_10 - y_21 + y_22 + s_6 = 2181830497379145/2251799813685248 \\ - y_11 + y_12 - y_15 + y_16 + s_7 = 4642729142352447/562949953421312 \\ - -4y_3 - y_11 + y_12 - y_17 + y_18 + s_8 = 2341124474634787/281474976710656 \\ - -4y_4 - y_11 + y_12 - y_21 + y_22 + s_9 = 1169966892480561/140737488355328 \\ - y_13 + y_14 - y_15 + y_16 + s_10 = 67104339147525/70368744177664 \\ - -4y_5 - y_13 + y_14 - y_17 + y_18 + s_11 = 2181830497379145/2251799813685248 \\ - -4y_6 - y_13 + y_14 - y_19 + y_20 + s_12 = 1169966892480561/140737488355328 \\ - y_1 - y_2 + y_3 + y_5 + s_13 = 0 \\  y_1 - y_3 - y_4 + y_6 + s_14 = 0 \\  y_2 + y_4 - y_5 - y_6 + s_15 = 0 \\ \end{array}\right.\]\begin{flushleft}Create the initial tableau of the new linear system.\end{flushleft}\begin{equation*}\begin{bmatrix}\begin{array}{ccccccccccccccccccccccccccccccccccccc|c}y_1 &y_2 &y_3 &y_4 &y_5 &y_6 &y_7 &y_8 &y_9 &y_10 &y_11 &y_12 &y_13 &y_14 &y_15 &y_16 &y_17 &y_18 &y_19 &y_20 &y_21 &y_22 &s_1 &s_2 &s_3 &s_4 &s_5 &s_6 &s_7 &s_8 &s_9 &s_10 &s_11 &s_12 &s_13 &s_14 &s_15 &b \\ \hline0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 8623089553905663/4503599627370496 \\0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4642729142352447/562949953421312 \\0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 67104339147525/70368744177664 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 8623089553905663/4503599627370496 \\-4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2341124474634787/281474976710656 \\0 & -4 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2181830497379145/2251799813685248 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4642729142352447/562949953421312 \\0 & 0 & -4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2341124474634787/281474976710656 \\0 & 0 & 0 & -4 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1169966892480561/140737488355328 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 67104339147525/70368744177664 \\0 & 0 & 0 & 0 & -4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 2181830497379145/2251799813685248 \\0 & 0 & 0 & 0 & 0 & -4 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1169966892480561/140737488355328 \\-1 & -1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\1 & 0 & -1 & -1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\0 & 1 & 0 & 1 & -1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \hline3 & 3 & 3 & 3 & 3 & 3 & 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\end{array}\end{bmatrix}\begin{array}{c}\\s_1 \\s_2 \\s_3 \\s_4 \\s_5 \\s_6 \\s_7 \\s_8 \\s_9 \\s_10 \\s_11 \\s_12 \\s_13 \\s_14 \\s_15 \\\\\end{array}\end{equation*}\end{document}