Duals of LP: Consider the linear programming problem given below: max z= 3 x 1 + x 2 Subject to constraints: x 1 + x 2 ≤ 1 − x 1 + x 2 ≥ 2 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 1 1 ≤ 1 y 2 -1 1 ≥ 2 * ≥ 3 ≥ 1 Step 2: In this case, the second primal constraint is ≥ and therefore dual variable y 2 must satisfy y 2 ≤ 0 . 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 6P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= 3x1+x2

Subject to constraints:

x1+x2≤1

−x1+x2≥2

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 1 1 ≤1
y2 -1 1 ≥2*
≥3 ≥1

Step 2:

In this case, the second primal constraint is ≥ and therefore dual variable y2 must satisfy y2≤0.

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:

−x1+x2≥2

−1(−x1+x2)≤−2

x1−x2≤−2

Step 2:

Replace the equality constraint by two inequality constraints as,

There is no equality constraint in this LP.

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= 3x1+x2

Subject to constraints:

x1+x2≤1

x1−x2≤−2

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0

Explanation of Solution

c.

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

min w= y1+2y2.....(2)

Subject to constraints

y1−y2≥3

y1+y2

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Students have asked these similar questions

The next problem concerns the following C code: /copy input string x to buf */ void foo (char *x) { char buf [8]; strcpy((char *) buf, x); } void callfoo() { } foo("ZYXWVUTSRQPONMLKJIHGFEDCBA"); Here is the corresponding machine code on a Linux/x86 machine: 0000000000400530 : 400530: 48 83 ec 18 sub $0x18,%rsp 400534: 48 89 fe mov %rdi, %rsi 400537: 48 89 e7 mov %rsp,%rdi 40053a: e8 di fe ff ff callq 400410 40053f: 48 83 c4 18 add $0x18,%rsp 400543: c3 retq 400544: 0000000000400544 : 48 83 ec 08 sub $0x8,%rsp 400548: bf 00 06 40 00 mov $0x400600,%edi 40054d: e8 de ff ff ff callq 400530 400552: 48 83 c4 08 add $0x8,%rsp 400556: c3 This problem tests your understanding of the program stack. Here are some notes to help you work the problem: ⚫ strcpy(char *dst, char *src) copies the string at address src (including the terminating '\0' character) to address dst. It does not check the size of the destination buffer. • You will need to know the hex values of the following characters:

1234 3. Which line prevents compiler optimization? Circle one: 1234 Suggested solution: Store strlen(str) in a variable before the if statement. ⚫ Remove the if statement. Replace index 0 && index < strlen(str)) { 5 } } = str [index] = val;

Character Hex value | Character Hex value Character Hex value 'A' 0x41 'J' Ox4a 'S' 0x53 'B' 0x42 'K' 0x4b "T" 0x54 0x43 'L' Ox4c 'U' 0x55 0x44 'M' 0x4d 'V' 0x56 0x45 'N' Ox4e 'W' 0x57 0x46 '0' Ox4f 'X' 0x58 0x47 'P' 0x50 'Y' 0x59 0x48 'Q' 0x51 'Z' Ox5a 'T' 0x49 'R' 0x52 '\0' 0x00 Now consider what happens on a Linux/x86 machine when callfoo calls foo with the input string "ZYXWVUTSRQPONMLKJIHGFEDCBA". A. On the left draw the state of the stack just before the execution of the instruction at address Ox40053a; make sure to show the frames for callfoo and foo and the exact return address, in Hex at the bottom of the callfoo frame. Then, on the right, draw the state of the stack just after the instruction got executed; make sure to show where the string "ZYXWVUTSRQPONMLKJIHGFEDCBA" is placed and what part, if any, of the above return address has been overwritten. B. Immediately after the ret instruction at address 0x400543 executes, what is the value of the program counter register %rip?…

Answer 2

Expert Solution & Answer

Chapter 6.5, Problem 6P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= 3x1+x2

Subject to constraints:

x1+x2≤1

−x1+x2≥2

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 1 1 ≤1
y2 -1 1 ≥2*
≥3 ≥1

Step 2:

In this case, the second primal constraint is ≥ and therefore dual variable y2 must satisfy y2≤0.

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:

−x1+x2≥2

−1(−x1+x2)≤−2

x1−x2≤−2

Step 2:

Replace the equality constraint by two inequality constraints as,

There is no equality constraint in this LP.

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= 3x1+x2

Subject to constraints:

x1+x2≤1

x1−x2≤−2

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0

Explanation of Solution

c.

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

min w= y1+2y2.....(2)

Subject to constraints

y1−y2≥3

y1+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 6P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= 3x1+x2

Subject to constraints:

x1+x2≤1

−x1+x2≥2

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 1 1 ≤1
y2 -1 1 ≥2*
≥3 ≥1

Step 2:

In this case, the second primal constraint is ≥ and therefore dual variable y2 must satisfy y2≤0.

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:

−x1+x2≥2

−1(−x1+x2)≤−2

x1−x2≤−2

Step 2:

Replace the equality constraint by two inequality constraints as,

There is no equality constraint in this LP.

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= 3x1+x2

Subject to constraints:

x1+x2≤1

x1−x2≤−2

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0

Explanation of Solution

c.

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

min w= y1+2y2.....(2)

Subject to constraints

y1−y2≥3

y1+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 6P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= 3x1+x2

Subject to constraints:

x1+x2≤1

−x1+x2≥2

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 1 1 ≤1
y2 -1 1 ≥2*
≥3 ≥1

Step 2:

In this case, the second primal constraint is ≥ and therefore dual variable y2 must satisfy y2≤0.

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:

−x1+x2≥2

−1(−x1+x2)≤−2

x1−x2≤−2

Step 2:

Replace the equality constraint by two inequality constraints as,

There is no equality constraint in this LP.

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= 3x1+x2

Subject to constraints:

x1+x2≤1

x1−x2≤−2

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0

Explanation of Solution

c.

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

min w= y1+2y2.....(2)

Subject to constraints

y1−y2≥3

y1+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 6P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= 3x1+x2

Subject to constraints:

x1+x2≤1

−x1+x2≥2

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 1 1 ≤1
y2 -1 1 ≥2*
≥3 ≥1

Step 2:

In this case, the second primal constraint is ≥ and therefore dual variable y2 must satisfy y2≤0.

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:

−x1+x2≥2

−1(−x1+x2)≤−2

x1−x2≤−2

Step 2:

Replace the equality constraint by two inequality constraints as,

There is no equality constraint in this LP.

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= 3x1+x2

Subject to constraints:

x1+x2≤1

x1−x2≤−2

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0

Explanation of Solution

c.

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

min w= y1+2y2.....(2)

Subject to constraints

y1−y2≥3

y1+y2

Answer 8

Chapter 6.5, Problem 6P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= 3x1+x2

Subject to constraints:

x1+x2≤1

−x1+x2≥2

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 1 1 ≤1
y2 -1 1 ≥2*
≥3 ≥1

Step 2:

In this case, the second primal constraint is ≥ and therefore dual variable y2 must satisfy y2≤0.

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

Answer 9

Chapter 6.5, Problem 6P

Explanation of Solution

Duals of LP:

Consider the linear programming problem given below:

max z= 3x1+x2

Subject to constraints:

x1+x2≤1

−x1+x2≥2

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 1 1 ≤1
y2 -1 1 ≥2*
≥3 ≥1

Step 2:

In this case, the second primal constraint is ≥ and therefore dual variable y2 must satisfy y2≤0.

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:

−x1+x2≥2

−1(−x1+x2)≤−2

x1−x2≤−2

Step 2:

Replace the equality constraint by two inequality constraints as,

There is no equality constraint in this LP.

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= 3x1+x2

Subject to constraints:

x1+x2≤1

x1−x2≤−2

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0

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:

−x1+x2≥2

−1(−x1+x2)≤−2

x1−x2≤−2

Step 2:

Replace the equality constraint by two inequality constraints as,

There is no equality constraint in this LP.

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= 3x1+x2

Subject to constraints:

x1+x2≤1

x1−x2≤−2

x1,x2≥0

Construct the following table according to the given LP,

Min W (x1≥0

Answer 12

Explanation of Solution

c.

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

min w= y1+2y2.....(2)

Subject to constraints

y1−y2≥3

y1+y2

Answer 13

Explanation of Solution

c.

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

min w= y1+2y2.....(2)

Subject to constraints

y1−y2≥3

y1+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 how to find the dual of the linear programming problem. The asterisk (*) sign represents the places where rules must be applied.

Explanation of Solution

Explanation of Solution

Explanation of Solution

c.

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

min w= y1+2y2.....(2)

Subject to constraints

y1−y2≥3

y1+y2

Want to see the full answer?

Chapter 6 Solutions

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

Solution Summary: The author explains how to find the dual of the linear programming problem. The asterisk (*) sign represents the places where rules must be applied.

Explanation of Solution

Explanation of Solution

Explanation of Solution

c. Now put y¯2=−y2 in the part (b) answer. So that, min w= y1+2y2.....(2) Subject to constraints y1−y2≥3 y1+y2

Want to see the full answer?

Chapter 6 Solutions

c.

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

min w= y1+2y2.....(2)

Subject to constraints

y1−y2≥3

y1+y2