Linear Programming, Reduction, and Max Flow Networks In the past few units, you have learned about many discrete math and computer science optimization problems, including min cut, max flow; shortest...

1 answer below »

Linear Programming, Reduction, and Max Flow Networks


In the past few units, you have learned about many discrete math and computer science optimization problems, including min cut, max flow; shortest paths; minimum spanning trees; and matching. Each of these optimization problems can be rephrased or rewritten as an equivalent linear programming problem. A linear programming problem consists of an objective (that is, a value to be maximized or minimized) and constraints.


Each of the graphical optimization problems discussed in this class can be rephrased as a linear programming problem by altering the objective or the constraints to refit the problem at hand. Another way to use a linear program to solve an optimization problem is to transform a new problem into a problem for which we already have a linear program solution—this is a reduction. The idea is that you already have a solution for a known linear programming problem. If you can somehow transform a new problem that you have into this known linear programming problem, you already have the solution. The tricky part is to figure out how to transform your problem into a known solution problem.


For this assignment, read the Notes section on page 529of your textbook. There is a linear program on this pagethat describes finding a maximal flow in a networkG, with a sourcea, a sinkz, flowsF, and capacitiesC. If we want to find a solution to a different problem, maybe the matching problem, for example, we could (1) formulate a linear program for the matching problem or (2) transform the matching problem into a maximal flow problem, then use the already known linear program that solves the maximal flow problem.


To better understand linear programs and reductions, write a two- to three-page paper that addresses the following questions:



  1. What is a linear program? Explain in at least one paragraph. Feel free to show an example.

  2. What are constraints in linear programming problems? Offer at least one example.

  3. What is an optimization problem? Offer an example and explain.

  4. What is a reduction (specifically, changing one problem into another)? Provide an example. You may use the Internet to locate an example.

  5. Given Example 10.4.4 and Theorem 10.4.5 in the textbook, explain how you would transform the matching problem into a maximal flow problem.

  6. Once you complete question 5, use the already known linear program that solves the maximal flow problem. Show all of your work and how you are doing the reduction.


Show all of your work and include references for resources you use to complete the assignment.



Hint 1: Transform the matching problem into a matching network, and then find the maximal flow to this network.



Hint 2: The goal here is to learn that, while problems might appear different, they are often the same. Knowing how to transform a new problem into a known problem can save a lot of solving time. Use the Internet and your textbook.


Review the Linear Programming, Reduction, and Max Flow Networks Scoring Guide to understand how the assignment will be graded.

Answered 2 days AfterSep 05, 2021

Answer To: Linear Programming, Reduction, and Max Flow Networks In the past few units, you have learned about...

Aditi answered on Sep 08 2021
141 Votes
1) Linear program :
Definition:
A function f(x1, x2, . . . , xn) of x1, x2, . . . , xn is a linear function if and only if for some set of constants C1, C2, . . . , Cn,
f(x1,
x2, . . . , xn) = C1x1+ C2 x2 +, . . . ,+ Cn xn.
Examples:
· x1
· 5x1 + 6x4 − 2x2 + 1
· 3
2) Constraints:
The linear inequalities or equations or restrictions on the variables of a linear programming problem are called constraints. The conditions x ≥ 0, y ≥ 0 are called non-negative restrictions.
3) Optimization Problem:
A problem which seeks to maximize or minimize a linear function (say of two variables x and y) subject to certain constraints as determined by a set of linear inequalities is called an optimization problem. Linear programming problems are special type of optimization problems.
Example:
(Diet problem): A dietician wishes to mix two types of foods in such a way that vitamin contents of the mixture contain at least 8 units of vitamin A and 10 units of vitamin C. Food ‘I’ contains 2 units/kg of vitamin A and 1 unit/kg of vitamin C. Food ‘II’ contains 1 unit/kg of vitamin A and 2 units/kg of vitamin C. It costs Rs 50 per kg to purchase Food ‘I’ and Rs 70 per kg to purchase Food ‘II’. To formulate this problem as a linear programming problem to minimize the cost of such a mixture,
Let the mixture contain x kg of Food ‘I’ and y kg of Food ‘II’.
Clearly, x ≥ 0, y ≥ 0.
Since the mixture must contain at least 8 units of vitamin A and 10 units of vitamin C, we have the constraints:
2x + y ≥ 8
x + 2y ≥ 10
Total cost Z of purchasing x kg of food ‘I’ and y kg of Food ‘II’ is
Z = 50x + 70y
Hence, the mathematical formulation of the problem is:
Minimise Z = 50x + 70y ... (1)
subject to the constraints:
2x + y ≥ 8 ... (2)
x + 2y ≥ 10 ... (3)
x, y ≥ 0...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here