Solve the above problem using simplex algorithm show all it

Assignment Help Other Subject
Reference no: EM13974176

Linear Programming Problem

Max { z = 4x1 + x2 + 5x3 + 3x4 }  subject to constraints:
x1 - x2 - x3 + 3x4 ≤1;
5 x1 + x2 + 3x3 + 8x4 ≤ 55;
-x1 + 2x2 + 3x3 - 5x4 ≤ 3;
xj ≥ 0, j = 1, 2, 3, 4.

Solve the above problem using Simplex algorithm, show all iterations, then compose the corresponding dual problem and apply results of the Duality Theory to the dual pair.

1) Simplex solution: Introducing 3 more variables ( x5, x6, x7 ) to equalize the constraints we get:

1538_111.png

The simplex solution in 3 iterations is shown above. The optimal solution: 

z_max = 29, x1 = 0, x2 = 14, x3 = 0, x4 = 5 ( x5 = 0, x6 = 1, x7 = 0 )

2) The dual problem: We have a symmetric dual pair since in the original all constraints are inequalities ("≤ " in max-problem) with non-negative variables, hence the dual variables (y1, y2, y3) are also non-negative and all constraints should be inequalities ("≥" in min-problem). The matrices of both problems are transposed (so min-problem will have 4 constraints with 3 variables). Finally the object function coefficients in each problem become right hand sides in the dual and vice versa:

Min { w = y1 + 55y2 + 3y3 }  subject to constraints:

y1 + 5y2 - y3 ≥ 4;
-y1 + y2 + 2y3 ≥ 1;
-y1 + 3y2 + 3y3 ≥ 5;
3y1 + 8y2 - 5y3 ≥ 3;
yi≥ 0, i = 1, 2, 3.

3) Optimal solutions for the dual pair: According the Duality Theory in Linear Programming the optimal simplex tableau of the primal problem provides the optimal solution of the dual also: take the final Δj,  j = 5, 6, 7, corresponding to variables from the initial basis (x5, x6, x7) and add their object coefficients (all c5, c6, c7 are 0 here)

y1 = Δ5 + c5 = 11 + 0 = 11; y2 = Δ6 + c6 = 0 + 0 = 0;  y3 = Δ7 + c7 = 6 + 0 = 0

For (y1, y2, y3 ) = (11, 0, 6) we have w_min = 11 + 55*0 + 3*6 = 29 = z_max as proven in the Main Duality Theorem.

For the optimal solution X_max = (0, 14, 0, 5) we have:
0 - 14 - 0 + 3*5 = 1, so the 1st constraint is satisfied exactly;
5*0 + 14 + 3*0 + 8*5 = 54 < 55, so the 2nd constraint is not satisfied exactly (x6 = 1 > 0), hence y2 = 0 in Y_min;
-0 + 2*14 + 3*0 - 5*5 = 3, so the 3rd constraint is satisfied exactly;
Also 2nd and 4th components in X_max being positive means that 2nd and 4th dual constraints are satisfied exactly.

For the optimal solution Y_min = (11, 0, 6) the 1st and 3rd constraints are not satisfied exactly, hence in the optimal solution of the primal x1 = x 3 = 0; 1st and 3rd components being positive implies the corresponding constraints in the max-problem to be satisfied exactly, as shown above.

Reference no: EM13974176

Questions Cloud

What does the dalai lama mean by basic human values : What does the Dalai Lama mean by "basic human values"? In your opinion, does the lack of basic human values contribute to the tensions in the world? What is the difference between empathy and compassion
Lead managers to develop various pricing strategies. : Propose how differences in demand and elasticity lead managers to develop various pricing strategies.
Write one page summary of given video : Peru's City Of Ghosts- https://www.youtube.com/watch?v=Nbw-_15xAXc and Watch this video and write 1 page (250 - 350 words ) summary(notes)
What is the rationale or justification offered by hackers : What is the rationale or justification offered by hackers such as Anonymous or Wikileaks? How can the activities of such groups be considered "cybercrime"?
Solve the above problem using simplex algorithm show all it : Solve the above problem using Simplex algorithm, show all iterations, then compose the corresponding dual problem and apply results of the Duality Theory to the dual pair. Simplex solution: Introducing 3 more variables ( x5, x6, x7 ) to equalize the ..
Find a internet article or essay on topic of interest to you : Use the simple rubric below to evaluate the thesis. On a scale from one (no thesis) to five (exceptionally well-written and organized).Explain why you have selected the rating. For example, why do you believe the statement is exceptionally well wr..
During june, each worked an average hours at an average rate : The company employs 10 persons to work on the production of Fruta. During June, each worked an average of 160 hours at an average rate of $12.50 per hour.
Discuss educational issues regarding digital schools : These articles discuss educational issues regarding digital schools in addition to the advantages and disadvantages of incorporating technology in the classroom. Develop a 2- to 3-page analysis paper that addresses the following: Identify 3 major ..
Identify an educational issue within your school : For your final assessment, create a presentation by doing the following: Identify an educational issue within your school, work place, or prior education-related work experience

Reviews

Write a Review

 

Other Subject Questions & Answers

  Implicated in pain alleviation

Which of the following has been implicated in pain alleviation?

  What do twin and adoption studies

What do twin and adoption studies tell us about the effects of nature

  Measure the success of the initiative

If you wanted to implement a Must Haves program in your organization, what elements would you include in your implementation plan? What metrics would you use to measure the success of the initiative?

  Why do you think davidson goes to great lengths

Why do you think Davidson goes to great lengths to describe these differences? Do you think there really are any differences? After having read about the many achievements of Athens laid out in the textbook, how does this expose on the sexuality an..

  Innovation and knowledge management

You are expected to write a scholar essay to link and address the following: 1. Innovation in healthcare, as a result between knowledge management concepts and innovation concepts.

  Disturbance in the release of the hormone

Nina's pineal gland has been damaged. She can expect a disturbance in the release of the hormone

  Assumptions of differing cultural groups in united states

Communication Patterns and Assumptions of Differing Cultural Groups in the United States" and examine their patterns and assumptions in relation to one another. What common elements can you find? In what ways do cultural differences impact verbal ..

  Explain the types of fobic disorders

In your own words, explain the types of fobic disorders, the theories that may cause these disorder, and what treatments are used to treat these disorders.

  Develop the null and the alternative hypothesis

Develop the null and the alternative hypothesis

  Description of the rhetor and the advertisement

A description of the rhetor and the advertisement. This should include some background about the advertiser-who are they, what types of goods or services do they produce, what is their target audience etc

  Statistical process control issues

What does statistical control mean? What is the difference between capability and control? Why should we care about each of these?

  Religion and philosophy

Religion and philosophy both address many of the same questions. (Is there a god? Is man good or evil? etc) Both look for some form of enlightenment or ultimate truth. What is the difference in the approaches that these two disciplines take when i..

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd