ZuoTi.Pro
Question

Problem on Linear programming and Simplex method

Problem on Linear programming and Simplex method

The \(\ell_{1}\) norm of a vector \(v \in \mathbb{R}\) is defined by

$$ \|v\|_{1}:=\sum_{i=1}^{n}\left|v_{i}\right| $$

Problems of the form Minimize \(\|v\|_{1}\) subject to \(v \in \mathbb{R}^{n}\) and \(A v=b\) arise very frequently in applied math, particularly in the field of compressed sensing.

Consider the special case of this problem whith \(n=3\),

$$ A=\left(\begin{array}{lll} 1 & 1 & 0 \\ 3 & 0 & 1 \end{array}\right) \quad \text { and } \quad b=\left(\begin{array}{l} 3 \\ 8 \end{array}\right) $$

(a) (3 points) Explain how to transform this into the following equivalent linear program in standard form (no need for a complete proof of equivalence)

Minimize \(x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}\)

under the constraints

$$ \begin{array}{r} x_{1}-x_{2}+x_{3}-x_{4}=3 \\ 3 x_{1}-3 x_{2}+x_{5}-x_{6}=8 \\ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6} \geq 0 \end{array} $$

(b) (6 points) Solve the linear program of part (a) using the simplex method.

(c) ( 2 points) What \(v \in \mathbb{R}^{3}\) minimizes the original problem?

math   Advanced-Math   
1 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

✔ Recommended Answer
Answer #7

Part(a) and part(b)

Part(c)

1 0
Add a comment
Answer #5

Answer:-

please like it if you have any issue mention in comment

0 0
Add a comment
Answer #1

0 0
Add a comment
Answer #2

0 0
Add a comment
Answer #3

0 0
Add a comment
Answer #4

0 0
Add a comment
Answer #6

0 0
Add a comment
Know the answer?
Add Answer to:
Problem on Linear programming and Simplex method
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • linear algebra

    Problem settingConsider the linear transformation \(\phi(\cdot): \mathbb{R}^{2} \rightarrow \mathbb{R}^{2}\) on the standard vector space of dimension two over the field of real numbers defined as:$$ \phi\left(\left(\begin{array}{l} x_{0} \\ x_{1} \end{array}\right)\right)=\left(\begin{array}{r} 3 x_{0}-x_{1} \\ -7 x_{0}+2 x_{1} \end{array}\right) $$Problem taskFind \(\mathcal{R}_{G \rightarrow E}(\) id \()\) that is the change of basis matrix from basis \(G\) to the standard basis \(E\) where the standard basis vectors are:$$ \begin{array}{l} \vec{e}_{0}=\left(\begin{array}{l} 1 \\ 0 \end{array}\right) \\ \vec{e}_{1}=\left(\begin{array}{l} 0 \\ 1 \end{array}\right) \end{array} $$given that...

  • >Consider the following linear fractional program (LFP):

    Consider the following linear fractional program (LFP):$$ \begin{array}{ll} \max f\left(x_{1}, x_{2}\right)= & \frac{10 x_{1}+20 x_{2}+10}{3 x_{1}+4 x_{2}+20} \\ \text { s.t. } \quad & x_{1}+3 x_{2} \leq 50 \\ & 3 x_{1}+2 x_{2} \leq 80 \\ & x_{1}, x_{2} \geq 0 \end{array} $$(a) Transform this problem into an equivalent linear program.(b) Use Matlab (or other software) to solve the LP you created in part (a).(c) Use your answer from part (a) to find a solution to the original LFP.(d) Does...

  • Consider the 3 × 3 matrices

    3. (3pts) Consider the \(3 \times 3\) matrices \(B=\left[\begin{array}{ccc}1 & 1 & 2 \\ -1 & 0 & 4 \\ 0 & 0 & 1\end{array}\right]\) and \(A=\left[\begin{array}{lll}\mathbf{a}_{1} & \mathbf{a}_{2} & \mathbf{a}_{3}\end{array}\right]\), where \(\mathbf{a}_{1}\), \(\mathbf{a}_{2}\), and \(\mathrm{a}_{9}\) are the columns of \(A\). Let \(A B=\left[\begin{array}{lll}v_{1} & v_{2} & v_{3}\end{array}\right]\), where \(v_{1}, v_{2}\), and \(v_{3}\) are the columns of the product. Express a as a linear combination of \(\mathbf{v}_{1}, \mathbf{v}_{2}\), and \(\mathbf{v}_{3}\).4. (3pts) Let \(T(x)=A x\) be the linear transformation given by$$...

  • Help with Linear Algebra

    1. Suppose that \(T\) is the matrix transformation defined by the matrix \(A\) and \(S\) the matrix transformation defined by \(B\) where$$ A=\left[\begin{array}{rrr} 3 & -1 & 0 \\ 1 & 2 & 2 \\ -1 & 3 & 2 \end{array}\right], \quad B=\left[\begin{array}{rrr} 1 & -1 & 0 \\ 2 & 1 & 2 \end{array}\right] $$a. If \(T: \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}\), what are the values of \(m\) and \(n ?\) What values of \(m\) and \(n\) are appropriate for the...

  • 6. This problem uses least squares to find the curve y=ax+bx2 that best fits these 4...

    This problem uses least squares to find the curve \(y=a x+b x^{2}\) that best fits these 4 points in the plane:$$ \left(x_{1}, y_{1}\right)=(-2,2), \quad\left(x_{2}, y_{2}\right)=(-1,1), \quad\left(x_{1}, y_{3}\right)=(1,0), \quad\left(x_{4}, y_{4}\right)=(2,2) . $$a. Write down 4 equations \(a x_{i}+b x_{i}^{2}=y_{i}, i=1,2,3,4\), that would be true if the line actually went through a11 four points.b. Now write those four equations in the form \(\mathbf{A}\left[\begin{array}{l}a \\ b\end{array}\right]=\mathbf{y}\)c. Now find \(\left[\begin{array}{l}\hat{a} \\ \hat{b}\end{array}\right]\) that minimizes \(\left\|A\left[\begin{array}{l}a \\ b\end{array}\right]-\mathbf{y}\right\|^{2}\).

  • True or false: V = is a subspace of R3

    True or false: $$ V=\left\{\left[\begin{array}{l} x \\ y \\ z \end{array}\right] \in \mathbb{R}^{3}: x \geq 0\right\} $$is a subspace of R3. True False Question 10 (1 point) True or false: $$ V=\left\{\left[\begin{array}{l} x \\ y \\ z \end{array}\right] \in \mathbb{R}^{3}: x-y=z+1\right\} $$is a subspace of R3. True False 

  • Suppose that the functions

    Suppose that the functions \(f: \mathbb{R}^{3} \rightarrow \mathbb{R}, g: \mathbb{R}^{3} \rightarrow \mathbb{R}\), and \(h: \mathbb{R}^{3} \rightarrow \mathbb{R}\) are continuously differentiable and let \(\left(x_{0}, y_{0}, z_{0}\right)\) be a point in \(\mathbb{R}^{3}\) at which$$ f\left(x_{0}, y_{0}, z_{0}\right)=g\left(x_{0}, y_{0}, z_{0}\right)=h\left(x_{0}, y_{0}, z_{0}\right)=0 $$and$$ \left\langle\nabla f\left(x_{0}, y_{0}, z_{0}\right), \nabla g\left(x_{0}, y_{0}, z_{0}\right) \times \nabla h\left(x_{0}, y_{0}, z_{0}\right)\right\rangle \neq 0 $$By considering the set of solutions of this system as consisting of the intersection of a surface with a path, explain why that in a...

  • Use A-1 to solve the following system of linear exuations

    Let \(A=\left[\begin{array}{ccc}2 & 0 & -1 \\ 1 & -5 & 1 \\ 2 & -7 & 1\end{array}\right]\)a) Compute \(A^{-1} .\)b) Use \(A^{-1}\) to solve the following system of linear exuations:$$ \begin{array}{r} 2 x_{1}+-x_{3}=3 \\ x_{1}-5 x_{2}+x_{3}=1 \\ 2 x_{1}-7 x_{2}+x_{3}=4 \end{array} $$

  • Find the matrix A such that T(x)=Ax

    Let \(T: R^{3} \rightarrow R^{2}\) defined by \(T\left(\left[\begin{array}{l}x_{1} \\ x_{2} \\ x_{3}\end{array}\right]\right)=\left[\begin{array}{c}2 x_{1}+x_{3} \\ -x_{2}\end{array}\right]\).a. Find the matrix \(A\) such that \(T(x)=A x\)b. Demonstrate that \(T\) is a linear transformation.

  • Solve the linear programming problem by simplex method. . Minimize C= -x - 2y + z....

    Solve the linear programming problem by simplex method. . Minimize C= -x - 2y + z. subject to 2x + y +2 < 14 4x + 2y + 3z < 28 2x + 5y + 5z < 30 x = 0, y>02 > 0

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT