Deterministic Optimization on linear program formulation and Max/Min flow problems.
Requires a highly understanding on Deterministic Optimizations and using Gurobi, which aims to do:
1. Formulation on linear programs, topics include:
– tea blending: minimizing total cost of raw materials while aiming to buy raw materials to produce enough of the tea blends to satisfy demands.
– debt repayment: maximizing total combined values of assets.
– power distribution
2. Maximum flow and minimum cost flow problems, topics include:
– Graphs, road trips problems
Please provide me brief but clear process and explanation solving each problem and correct answers, long sentence are not required, thank you a lot!
Requirements: brief but clear process and explanation solving each problem and correct answers
Co370: Deterministic Optimization OR Models Assignment 1 problems ¥ You should justify all of your solutions, unless you are explicitly asked not to. ¥ You are graded on both your accuracy and your presentation (see below). A correct solution that is poorly presented may not receive full marks. The markers will not spend a lot of time figuring out something you write that is not clear. ¥ Each of the problems is worth 20 marks. ¥ Guidelines to writing solutions. Your goal is to present your solutions so that your reader can easily understand what you are writing and be convinced of your arguments. So the quality of your solutions is very important. Here are some guidelines that you should keep in mind when writing your solutions. ¥ Write in complete sentences. Separate major steps in the solution into paragraphs. ¥ When writing a proof, make sure that every statement follows from earlier statements. Cite results or assumptions when you use them. Only use results from the lectures or the course notes. ¥ Use proper notation. Mathematics is a precise language, and improper use of notation can easily cause confusion. ¥ Define a variable before you use it. It can be as simple as “Let p=3x for some x∈Z” if this is the first time you are using x. ¥ Do not include irrelevant facts. Only state facts that are necessary in the argument.
A1-1. LP formulation: Tea blending Daisy’s Tea is creating n new blends of tea T = {1, . . . , n}. These tea blends need to satisfy m characteristics scores C = {1, . . . , m}. They can blend q sources of raw materials R = {1, . . . , q} to create the tea. Here are the relevant data: For each tea blend i ∈ T… • Its required characteristic score for each j ∈ C is αij . • There is a demand of di kilograms. For each raw material k ∈ R… • Its characteristic score for each j ∈ C is βjk. • Its price is pk per kilogram. • There is a maximum of vk kilograms available. When blending the raw materials, the characteristic scores changes linearly. For example, suppose brightness is one of the characteristics. Then 1kg of material with brightness 3 and 3kg of material with brightness 2 will yield 4kg with brightness (1 · 3 + 3 · 2)/4 = 2.25. Now getting the exact characteristic scores for all tea blends may be impossible. So each characteristic score for each tea blend is allowed to differ from the requirement by up to a constant ε. The goal is to buy raw materials to produce enough of the tea blends to satisfy the demands, while minimizing the total cost of buying raw materials. (a) Formulate this as a linear program. Clearly explain your variables, objective function and constraints. (You may assume that αij,di,βjk,pk,vk,ε are given constants.) (b) We now consider a specific example with 2 tea blends, 3 characteristics, and 3 raw material types, with ε = 0.5. Their data are given below. Tea blend characteristics and demands. Blend name Brightness Colour Thickness Demand (kg) Tea 1 4.3 1.9 3.7 10000 Tea 2 7.0 5.7 3.1 6000
Raw material characteristics, prices and availability. Material type Brightness Colour Thickness Price ($/kg) Availability (kg) R1 5.0 3.5 9.0 2.40 5000 R2 2.5 0.5 2.0 1.20 6000 R3 9.0 8.0 3.0 1.70 14000 Using Gurobi, implement the linear program from part (a) as applied to the data given here and solve it. Include the program you input into the software, and the output that includes the optimal solution and optimal value. (Note: It would be helpful to think about how to implement this problem when there are more tea blends, materials, and characteristics.
A1-2. LP formulation: Debt repayment Larry’s Lazy Lawn (LLL) is a service company that is currently $D in debt. To avoid defaulting on its debt, it needs to make a payment of at least 5% interest on its current debt at the end of each year, where any amount over the interest reduces the debt. It needs to pay off all debts by the end of year n. At the start of year 1, LLL has $0 in cash and $A of value in assets such as lawnmowers and other gardening tools. At the start of each year, it has the option of selling parts of its assets at 50% loss to generate more cash, or acquire new assets valued at up to 10% of the current assets using available cash. (For example, say the company has $10,000 in assets. Then it can sell $2,000 worth of assets and receive $1,000 in cash, leaving it with $8,000 in assets. Or it can spend $1,000 to buy $1,000 worth of assets, leaving it with $11,000 in assets.) The company estimates that it can generate cash revenue equal to a quarter of its total asset values each year. (For example, if the company has $10,000 in assets, then it can generate $2,500 in cash revenue this year.) There is also the option of taking a cash loan at the start of each year at another bank, but it needs to repay all of the loan at the start of next year at 7% interest. The goal for LLL is to pay off all debts and loans by the end of year n (assume that a loan taken at the start of year n is paid at the end of year n), and maximizing the total combined values of assets and cash at the end of year n. Formulate this problem as a linear program. Clearly explain your variables, objective function and constraints. (You may assume that D, A are given constants.)
A1-3. LP formulation: Power distribution Power ON is a hydro company that is distributing electricity across a certain region of Ontario. The company owns n power plants P = {1,…,n}, and it is serving m different cities in the region C = {1, . . . , m}. Each power plant i ∈ P can generate up to αi megawatt- hours (MWh) of electricity a year. The cost of producing 1 MWh of electricity at plant i is $ci. Each city j ∈ C requires at least βj MWh a year. There are power transmission lines that can transport electricity from any power plant to any city, and assume that there are different lines joining any power plant and any city. The cost of sending 1 MWh of electricity from power plant i to city j is $tij. However, some power is lost along the transmission lines. For each 1 MWh sent from power plant i, it is estimated that lij MWh reaches city j. The goal is to supply each city with enough electricity during the year, while minimizing the total cost. (Assume that αi,ci,βj,tij,lij are given constants.) 1. (a) Formulate this problem as a linear program. Clearly explain your variables, objective function and constraints. 2. (b) Power plant 1 produces electricity through renewable sources, and the government wants to encourage production of clean energy. So the government has an incentive program that gives Power ON $0.30 per MWh produced by power plant 1 for the first million MWh, $0.10 per MWh produced for the next million MWh, and $0.05 for any additional MWh. Explain how you would change the formulation from part (a) to implement this new condition. Explain why your solution works. (Make sure that your implementation is still allowed in a linear program.) 3. (c) Suppose we now change the incentives to the following: $0.10 for the first million MWh, $0.30 for the next million, and $0.60 for any additional power produced. Suppose you simply change the numbers from part (b) to the new ones given here. Does the updated linear program properly implement this new incentive scheme? Explain why. 4. (d) Suppose that instead of minimizing the total cost, Power ON wants to utilize the power lines as evenly as possible. This avoids overloading certain power lines. We want to find a way to distribute the electricity so that the maximum load of a power line is minimized. Explain how you would change the formulation from part (a) to implement this new condition. Explain why your solution works.
A1-4. Maximum flow and minimum cost flow problems Consider the following instance of the maximum flow problem. You are given a directed graph, and each arc has a label indicating its capacity. Consider the following instance of the minimum cost flow problem. You are given a directed graph, each node v has a label indicating its net supply bv, and each arc e is labelled with its cost and capacity (ce, ue).
1. (a) Write down the the LP formulation for both problems. No justifications required. 2. (b) Using Gurobi to implement both LPs from part (a), and find optimal solutions for both where all flow values are integers. Include the programs you input into the software, and the output that includes the optimal solution and optimal value. Then write the solutions on copies of the directed graphs. (On Gurobi, you can force a variable to take on only integer values by having a new section called Integers, followed by a list of variables that should be integers in the next line.) 3. (c) Both LPs have an optimal solutions where some flow values are fractional. Produce one such solution for each, and show it on a copy of the directed graph. (You do not need to show how you have obtained this solution. If you want to use Gurobi to find such a solution, you can experiment by setting a fractional lower bound or upper bound on some arcs. Remember to remove the integer constraint.)
A1-5. Maximum flow formulation: Family road trip Several families are planning a road trip to ORegon together. There are n families F = {1,…,n}, and family i has ai members. There are m cars available C = {1,…,m}, and car j has space for bj people. They need to plan on how to transport everyone to ORegon and back. To increase interaction between the different families, each car can take at most 2 members of the same family. But as it is such a long trip, people who are in the same car going to ORegon must be in different cars on the return trip. The goal is to assign people to cars on the way there, and on the way back. Formulate this as a maximum flow problem. You need to state the directed graph, the two nodes s and t, and the capacities of the arcs. Then draw a sketch of the formulation. Briefly explain why your formulation works, and how an optimal solution can help you determine if such assignments are possible.
Co370: Deterministic Optimization OR Models Assignment 1 problems ¥ You should justify all of your solutions, unless you are explicitly asked not to. ¥ You are graded on both your accuracy and your presentation (see below). A correct solution that is poorly presented may not receive full marks. The markers will not spend a lot of time figuring out something you write that is not clear. ¥ Each of the problems is worth 20 marks. ¥ Guidelines to writing solutions. Your goal is to present your solutions so that your reader can easily understand what you are writing and be convinced of your arguments. So the quality of your solutions is very important. Here are some guidelines that you should keep in mind when writing your solutions. ¥ Write in complete sentences. Separate major steps in the solution into paragraphs. ¥ When writing a proof, make sure that every statement follows from earlier statements. Cite results or assumptions when you use them. Only use results from the lectures or the course notes. ¥ Use proper notation. Mathematics is a precise language, and improper use of notation can easily cause confusion. ¥ Define a variable before you use it. It can be as simple as “Let p=3x for some x∈Z” if this is the first time you are using x. ¥ Do not include irrelevant facts. Only state facts that are necessary in the argument.
A1-1. LP formulation: Tea blending Daisy’s Tea is creating n new blends of tea T = {1, . . . , n}. These tea blends need to satisfy m characteristics scores C = {1, . . . , m}. They can blend q sources of raw materials R = {1, . . . , q} to create the tea. Here are the relevant data: For each tea blend i ∈ T… • Its required characteristic score for each j ∈ C is αij . • There is a demand of di kilograms. For each raw material k ∈ R… • Its characteristic score for each j ∈ C is βjk. • Its price is pk per kilogram. • There is a maximum of vk kilograms available. When blending the raw materials, the characteristic scores changes linearly. For example, suppose brightness is one of the characteristics. Then 1kg of material with brightness 3 and 3kg of material with brightness 2 will yield 4kg with brightness (1 · 3 + 3 · 2)/4 = 2.25. Now getting the exact characteristic scores for all tea blends may be impossible. So each characteristic score for each tea blend is allowed to differ from the requirement by up to a constant ε. The goal is to buy raw materials to produce enough of the tea blends to satisfy the demands, while minimizing the total cost of buying raw materials. (a) Formulate this as a linear program. Clearly explain your variables, objective function and constraints. (You may assume that αij,di,βjk,pk,vk,ε are given constants.) (b) We now consider a specific example with 2 tea blends, 3 characteristics, and 3 raw material types, with ε = 0.5. Their data are given below. Tea blend characteristics and demands. Blend name Brightness Colour Thickness Demand (kg) Tea 1 4.3 1.9 3.7 10000 Tea 2 7.0 5.7 3.1 6000
Raw material characteristics, prices and availability. Material type Brightness Colour Thickness Price ($/kg) Availability (kg) R1 5.0 3.5 9.0 2.40 5000 R2 2.5 0.5 2.0 1.20 6000 R3 9.0 8.0 3.0 1.70 14000 Using Gurobi, implement the linear program from part (a) as applied to the data given here and solve it. Include the program you input into the software, and the output that includes the optimal solution and optimal value. (Note: It would be helpful to think about how to implement this problem when there are more tea blends, materials, and characteristics.
A1-2. LP formulation: Debt repayment Larry’s Lazy Lawn (LLL) is a service company that is currently $D in debt. To avoid defaulting on its debt, it needs to make a payment of at least 5% interest on its current debt at the end of each year, where any amount over the interest reduces the debt. It needs to pay off all debts by the end of year n. At the start of year 1, LLL has $0 in cash and $A of value in assets such as lawnmowers and other gardening tools. At the start of each year, it has the option of selling parts of its assets at 50% loss to generate more cash, or acquire new assets valued at up to 10% of the current assets using available cash. (For example, say the company has $10,000 in assets. Then it can sell $2,000 worth of assets and receive $1,000 in cash, leaving it with $8,000 in assets. Or it can spend $1,000 to buy $1,000 worth of assets, leaving it with $11,000 in assets.) The company estimates that it can generate cash revenue equal to a quarter of its total asset values each year. (For example, if the company has $10,000 in assets, then it can generate $2,500 in cash revenue this year.) There is also the option of taking a cash loan at the start of each year at another bank, but it needs to repay all of the loan at the start of next year at 7% interest. The goal for LLL is to pay off all debts and loans by the end of year n (assume that a loan taken at the start of year n is paid at the end of year n), and maximizing the total combined values of assets and cash at the end of year n. Formulate this problem as a linear program. Clearly explain your variables, objective function and constraints. (You may assume that D, A are given constants.)
A1-3. LP formulation: Power distribution Power ON is a hydro company that is distributing electricity across a certain region of Ontario. The company owns n power plants P = {1,…,n}, and it is serving m different cities in the region C = {1, . . . , m}. Each power plant i ∈ P can generate up to αi megawatt- hours (MWh) of electricity a year. The cost of producing 1 MWh of electricity at plant i is $ci. Each city j ∈ C requires at least βj MWh a year. There are power transmission lines that can transport electricity from any power plant to any city, and assume that there are different lines joining any power plant and any city. The cost of sending 1 MWh of electricity from power plant i to city j is $tij. However, some power is lost along the transmission lines. For each 1 MWh sent from power plant i, it is estimated that lij MWh reaches city j. The goal is to supply each city with enough electricity during the year, while minimizing the total cost. (Assume that αi,ci,βj,tij,lij are given constants.) 1. (a) Formulate this problem as a linear program. Clearly explain your variables, objective function and constraints. 2. (b) Power plant 1 produces electricity through renewable sources, and the government wants to encourage production of clean energy. So the government has an incentive program that gives Power ON $0.30 per MWh produced by power plant 1 for the first million MWh, $0.10 per MWh produced for the next million MWh, and $0.05 for any additional MWh. Explain how you would change the formulation from part (a) to implement this new condition. Explain why your solution works. (Make sure that your implementation is still allowed in a linear program.) 3. (c) Suppose we now change the incentives to the following: $0.10 for the first million MWh, $0.30 for the next million, and $0.60 for any additional power produced. Suppose you simply change the numbers from part (b) to the new ones given here. Does the updated linear program properly implement this new incentive scheme? Explain why. 4. (d) Suppose that instead of minimizing the total cost, Power ON wants to utilize the power lines as evenly as possible. This avoids overloading certain power lines. We want to find a way to distribute the electricity so that the maximum load of a power line is minimized. Explain how you would change the formulation from part (a) to implement this new condition. Explain why your solution works.
A1-4. Maximum flow and minimum cost flow problems Consider the following instance of the maximum flow problem. You are given a directed graph, and each arc has a label indicating its capacity. Consider the following instance of the minimum cost flow problem. You are given a directed graph, each node v has a label indicating its net supply bv, and each arc e is labelled with its cost and capacity (ce, ue).
1. (a) Write down the the LP formulation for both problems. No justifications required. 2. (b) Using Gurobi to implement both LPs from part (a), and find optimal solutions for both where all flow values are integers. Include the programs you input into the software, and the output that includes the optimal solution and optimal value. Then write the solutions on copies of the directed graphs. (On Gurobi, you can force a variable to take on only integer values by having a new section called Integers, followed by a list of variables that should be integers in the next line.) 3. (c) Both LPs have an optimal solutions where some flow values are fractional. Produce one such solution for each, and show it on a copy of the directed graph. (You do not need to show how you have obtained this solution. If you want to use Gurobi to find such a solution, you can experiment by setting a fractional lower bound or upper bound on some arcs. Remember to remove the integer constraint.)
A1-5. Maximum flow formulation: Family road trip Several families are planning a road trip to ORegon together. There are n families F = {1,…,n}, and family i has ai members. There are m cars available C = {1,…,m}, and car j has space for bj people. They need to plan on how to transport everyone to ORegon and back. To increase interaction between the different families, each car can take at most 2 members of the same family. But as it is such a long trip, people who are in the same car going to ORegon must be in different cars on the return trip. The goal is to assign people to cars on the way there, and on the way back. Formulate this as a maximum flow problem. You need to state the directed graph, the two nodes s and t, and the capacities of the arcs. Then draw a sketch of the formulation. Briefly explain why your formulation works, and how an optimal solution can help you determine if such assignments are possible.
Collepals.com Plagiarism Free Papers
Are you looking for custom essay writing service or even dissertation writing services? Just request for our write my paper service, and we'll match you with the best essay writer in your subject! With an exceptional team of professional academic experts in a wide range of subjects, we can guarantee you an unrivaled quality of custom-written papers.
Get ZERO PLAGIARISM, HUMAN WRITTEN ESSAYS
Why Hire Collepals.com writers to do your paper?
Quality- We are experienced and have access to ample research materials.
We write plagiarism Free Content
Confidential- We never share or sell your personal information to third parties.
Support-Chat with us today! We are always waiting to answer all your questions.
