Duals of LP: Consider the linear programming problem given below: max z= x 1 + 2 x 2 Subject to constraints: 3 x 1 + x 2 ≤ 6 2 x 1 + x 2 = 5 x 1 , x 2 ≥ 0 a. To find the dual of the above LP proceed as follows: Step 1: Max z min w ( x 1 ≥ 0 ) ( x 2 ≥ 0 ) x 1 x 2 ( y 1 ≥ 0 ) y 1 3 1 ≤ 6 y 2 2 1 = 5 * ≥ 1 ≥ 2 Step 2: In this case, the second primal constraint is equality and therefore dual variable y 2 is now unrestricted in sign(urs). The asterisk (*) sign represents the places where rules must be applied to determine part of the dual

Question

Want to see the full answer?

Answer 1

Expert Solution & Answer

Chapter 6.5, Problem 5P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2=5

x1,x2≥0

a.

To find the dual of the above LP proceed as follows:

Step 1:

Max z
min w (x1≥0) (x2≥0)
x1 x2
(y1≥0) y1 3 1 ≤6
y2 2 1 =5*
≥1 ≥2

Step 2:

In this case, the second primal constraint is equality and therefore dual variable y2 is now unrestricted in sign(urs).

The asterisk (*) sign represents the places where rules must be applied to determine part of the dual

Explanation of Solution

b.

As the above linear programming problem is not a normal max problem, therefore the following steps are to be performed to convert it into a normal form.

Step 1: Multiply each ≥ constraint by -1 as mentioned below:

There is no ≥ constraint in this LP.

Step 2:

Replace the equality constraint 2x1+x2=5 by two inequality constraints as,

2x1+x2≤5

−2x1−x2≤−5

Step 3:

Now replace each urs variable x_i by xi=xi'−xi'' as there is no urs variable in the given LP.

Now write the transformed LP as,

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2≤5

−2x1−x2≤−5

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0) (x2≥0)
x1

Explanation of Solution

c.

Now put y2=y2'−y2'' in the part (b) answer. So that,

min w= 6y1+5y2

Subject to constraints

3y1+2y2≥1

y1+y2≥2

y1≥0,y2 urs

Since,

y2

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Students have asked these similar questions

A3Q3.c - You are to write a C program that implements the following disk scheduling algorithms: a. FCFS [10 marks] b. SCAN [10 marks] c. C-SCAN [10 marks] d. SSTF [10 marks] e. LOOK [10 marks] f. C-LOOK [10 marks] • Your program will service a disk with 300 cylinders numbered 0 to 299. • • • • The program will service the requests (a list of 20 cylinder numbers) given in the file request.bin. This file contains (4 byte) integer values representing requests ranging from 0-299. Your program will take the initial position of the disk head as the first command line argument and the direction of the head as the second command line argument. It will then output the requests in the order in which they are serviced, and the total amount of head movements required by each algorithm. In particular, your program needs to do the following: Your program should take two command line arguments a) First command line argument - initial position of the disk head (an integer value) b) Second command line…

2. The memory management has contiguous memory allocation, dynamic partitions, and paging. Compare the internal fragmentation and external fragmentation for these three approaches. [2 marks] 3. Suppose we have Logical address space = 24 = 16 (m = 4), Page size=2² =4 (n = 2), Physical address space = 26 = 64 (r = 6). Answer the following questions: [4 marks] 1) Total # of pages ? 2) Total # of frames ? 3) Number of bits to represent logical address? 4) Number of bits to represent offset ? 5) Number of bits to represent physical address? 6) Number of bits to represent a page number? 7) Number of bits to represent a frame number / 4. What is translation look-aside buffers (TLBS)? Why we need them to implement the page table? [2 marks] 5. Why we need shared pages for multiple processes? Give one example to show the benefits. [2 marks] 6. How to implement the virtual memory by using page out and page in? Explain with an example. [2 marks] 7. We have a reference string of referenced page…

8. List three HDD scheduling algorithms. [2 marks] 9. True or False? The NVM has the same scheduling algorithms with HDD. Explain why? [2 marks] 10. Why the modern mouses use polling to detect movements instead of interrupts? [2 marks] 11. What is thrashing? How does it happen? [2 marks] 12. Given a reference string of page numbers 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 and 4 frames show how the page replacement algorithms work, and how many page faults? [6 marks], 1) FIFO algorithm? [2 marks] 2) Optimal algorithm? [2 marks] 3) LRU algorithm? [2 marks] 13. List at least three file systems that you know. [2 marks] 14. In C programming, how the seek to a specific position in the file by offset? [2 marks]

Answer 2

Expert Solution & Answer

Chapter 6.5, Problem 5P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2=5

x1,x2≥0

a.

To find the dual of the above LP proceed as follows:

Step 1:

Max z
min w (x1≥0) (x2≥0)
x1 x2
(y1≥0) y1 3 1 ≤6
y2 2 1 =5*
≥1 ≥2

Step 2:

In this case, the second primal constraint is equality and therefore dual variable y2 is now unrestricted in sign(urs).

The asterisk (*) sign represents the places where rules must be applied to determine part of the dual

Explanation of Solution

b.

As the above linear programming problem is not a normal max problem, therefore the following steps are to be performed to convert it into a normal form.

Step 1: Multiply each ≥ constraint by -1 as mentioned below:

There is no ≥ constraint in this LP.

Step 2:

Replace the equality constraint 2x1+x2=5 by two inequality constraints as,

2x1+x2≤5

−2x1−x2≤−5

Step 3:

Now replace each urs variable x_i by xi=xi'−xi'' as there is no urs variable in the given LP.

Now write the transformed LP as,

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2≤5

−2x1−x2≤−5

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0) (x2≥0)
x1

Explanation of Solution

c.

Now put y2=y2'−y2'' in the part (b) answer. So that,

min w= 6y1+5y2

Subject to constraints

3y1+2y2≥1

y1+y2≥2

y1≥0,y2 urs

Since,

y2

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 3

Expert Solution & Answer

Chapter 6.5, Problem 5P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2=5

x1,x2≥0

a.

To find the dual of the above LP proceed as follows:

Step 1:

Max z
min w (x1≥0) (x2≥0)
x1 x2
(y1≥0) y1 3 1 ≤6
y2 2 1 =5*
≥1 ≥2

Step 2:

In this case, the second primal constraint is equality and therefore dual variable y2 is now unrestricted in sign(urs).

The asterisk (*) sign represents the places where rules must be applied to determine part of the dual

Explanation of Solution

b.

As the above linear programming problem is not a normal max problem, therefore the following steps are to be performed to convert it into a normal form.

Step 1: Multiply each ≥ constraint by -1 as mentioned below:

There is no ≥ constraint in this LP.

Step 2:

Replace the equality constraint 2x1+x2=5 by two inequality constraints as,

2x1+x2≤5

−2x1−x2≤−5

Step 3:

Now replace each urs variable x_i by xi=xi'−xi'' as there is no urs variable in the given LP.

Now write the transformed LP as,

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2≤5

−2x1−x2≤−5

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0) (x2≥0)
x1

Explanation of Solution

c.

Now put y2=y2'−y2'' in the part (b) answer. So that,

min w= 6y1+5y2

Subject to constraints

3y1+2y2≥1

y1+y2≥2

y1≥0,y2 urs

Since,

y2

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 4

Expert Solution & Answer

Chapter 6.5, Problem 5P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2=5

x1,x2≥0

a.

To find the dual of the above LP proceed as follows:

Step 1:

Max z
min w (x1≥0) (x2≥0)
x1 x2
(y1≥0) y1 3 1 ≤6
y2 2 1 =5*
≥1 ≥2

Step 2:

In this case, the second primal constraint is equality and therefore dual variable y2 is now unrestricted in sign(urs).

The asterisk (*) sign represents the places where rules must be applied to determine part of the dual

Explanation of Solution

b.

As the above linear programming problem is not a normal max problem, therefore the following steps are to be performed to convert it into a normal form.

Step 1: Multiply each ≥ constraint by -1 as mentioned below:

There is no ≥ constraint in this LP.

Step 2:

Replace the equality constraint 2x1+x2=5 by two inequality constraints as,

2x1+x2≤5

−2x1−x2≤−5

Step 3:

Now replace each urs variable x_i by xi=xi'−xi'' as there is no urs variable in the given LP.

Now write the transformed LP as,

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2≤5

−2x1−x2≤−5

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0) (x2≥0)
x1

Explanation of Solution

c.

Now put y2=y2'−y2'' in the part (b) answer. So that,

min w= 6y1+5y2

Subject to constraints

3y1+2y2≥1

y1+y2≥2

y1≥0,y2 urs

Since,

y2

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 5

Expert Solution & Answer

Answer 6

Expert Solution & Answer

Answer 7

Chapter 6.5, Problem 5P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2=5

x1,x2≥0

a.

To find the dual of the above LP proceed as follows:

Step 1:

Max z
min w (x1≥0) (x2≥0)
x1 x2
(y1≥0) y1 3 1 ≤6
y2 2 1 =5*
≥1 ≥2

Step 2:

In this case, the second primal constraint is equality and therefore dual variable y2 is now unrestricted in sign(urs).

The asterisk (*) sign represents the places where rules must be applied to determine part of the dual

Explanation of Solution

b.

As the above linear programming problem is not a normal max problem, therefore the following steps are to be performed to convert it into a normal form.

Step 1: Multiply each ≥ constraint by -1 as mentioned below:

There is no ≥ constraint in this LP.

Step 2:

Replace the equality constraint 2x1+x2=5 by two inequality constraints as,

2x1+x2≤5

−2x1−x2≤−5

Step 3:

Now replace each urs variable x_i by xi=xi'−xi'' as there is no urs variable in the given LP.

Now write the transformed LP as,

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2≤5

−2x1−x2≤−5

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0) (x2≥0)
x1

Explanation of Solution

c.

Now put y2=y2'−y2'' in the part (b) answer. So that,

min w= 6y1+5y2

Subject to constraints

3y1+2y2≥1

y1+y2≥2

y1≥0,y2 urs

Since,

y2

Answer 8

Chapter 6.5, Problem 5P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2=5

x1,x2≥0

a.

To find the dual of the above LP proceed as follows:

Step 1:

Max z
min w (x1≥0) (x2≥0)
x1 x2
(y1≥0) y1 3 1 ≤6
y2 2 1 =5*
≥1 ≥2

Step 2:

In this case, the second primal constraint is equality and therefore dual variable y2 is now unrestricted in sign(urs).

The asterisk (*) sign represents the places where rules must be applied to determine part of the dual

Answer 9

Chapter 6.5, Problem 5P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2=5

x1,x2≥0

a.

To find the dual of the above LP proceed as follows:

Step 1:

Max z
min w (x1≥0) (x2≥0)
x1 x2
(y1≥0) y1 3 1 ≤6
y2 2 1 =5*
≥1 ≥2

Step 2:

In this case, the second primal constraint is equality and therefore dual variable y2 is now unrestricted in sign(urs).

The asterisk (*) sign represents the places where rules must be applied to determine part of the dual

Answer 10

Explanation of Solution

b.

As the above linear programming problem is not a normal max problem, therefore the following steps are to be performed to convert it into a normal form.

Step 1: Multiply each ≥ constraint by -1 as mentioned below:

There is no ≥ constraint in this LP.

Step 2:

Replace the equality constraint 2x1+x2=5 by two inequality constraints as,

2x1+x2≤5

−2x1−x2≤−5

Step 3:

Now replace each urs variable x_i by xi=xi'−xi'' as there is no urs variable in the given LP.

Now write the transformed LP as,

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2≤5

−2x1−x2≤−5

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0) (x2≥0)
x1

Answer 11

Explanation of Solution

b.

As the above linear programming problem is not a normal max problem, therefore the following steps are to be performed to convert it into a normal form.

Step 1: Multiply each ≥ constraint by -1 as mentioned below:

There is no ≥ constraint in this LP.

Step 2:

Replace the equality constraint 2x1+x2=5 by two inequality constraints as,

2x1+x2≤5

−2x1−x2≤−5

Step 3:

Now replace each urs variable x_i by xi=xi'−xi'' as there is no urs variable in the given LP.

Now write the transformed LP as,

max z= x1+2x2

Subject to constraints:

3x1+x2≤6

2x1+x2≤5

−2x1−x2≤−5

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0) (x2≥0)
x1

Answer 12

Explanation of Solution

c.

Now put y2=y2'−y2'' in the part (b) answer. So that,

min w= 6y1+5y2

Subject to constraints

3y1+2y2≥1

y1+y2≥2

y1≥0,y2 urs

Since,

y2

Answer 13

Explanation of Solution

c.

Now put y2=y2'−y2'' in the part (b) answer. So that,

min w= 6y1+5y2

Subject to constraints

3y1+2y2≥1

y1+y2≥2

y1≥0,y2 urs

Since,

y2

Answer 14

Expert Solution & Answer

Answer 15

Expert Solution & Answer

Answer 16

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 17

Ch. 6.1 - Prob. 1P Ch. 6.1 - Prob. 2P Ch. 6.1 - Prob. 3P Ch. 6.1 - Prob. 4P Ch. 6.1 - Prob. 5P Ch. 6.2 - Prob. 1P Ch. 6.2 - Prob. 2P Ch. 6.3 - Prob. 1P Ch. 6.3 - Prob. 2P Ch. 6.3 - Prob. 3P

Solution Summary: The author explains that the second primal constraint is equality, so the dual variable y_2 is now unrestricted.

Concept explainers

Explanation of Solution

Explanation of Solution

Explanation of Solution

c.

Now put y2=y2'−y2'' in the part (b) answer. So that,

min w= 6y1+5y2

Subject to constraints

3y1+2y2≥1

y1+y2≥2

y1≥0,y2 urs

Since,

y2

Want to see the full answer?

Chapter 6 Solutions

Max z
min w	(x1≥0)	(x2≥0)
	x1	x2
(y1≥0)	y1	3	1	≤6
	y2	2	1	=5*
	≥1	≥2

Solution Summary: The author explains that the second primal constraint is equality, so the dual variable y_2 is now unrestricted.

Concept explainers

Explanation of Solution

Explanation of Solution

Explanation of Solution

c. Now put y2=y2'−y2'' in the part (b) answer. So that, min w= 6y1+5y2 Subject to constraints 3y1+2y2≥1 y1+y2≥2 y1≥0,y2 urs Since, y2

Want to see the full answer?

Chapter 6 Solutions

c.

Now put y2=y2'−y2'' in the part (b) answer. So that,

min w= 6y1+5y2

Subject to constraints

3y1+2y2≥1

y1+y2≥2

y1≥0,y2 urs

Since,

y2