代写CO 250 Spring 2024: Practice Problems 2代做Java程序
- 首页 >> Algorithm 算法CO 250 Spring 2024: Practice Problems 2
These are practice problems, no solutions will be provided. You are welcome to discuss solutions to these problems on Piazza and during office hours.
P2-1. Suppose we are formulating a certain integer program problem, which includes these five variables x1 , x2 , x3 , x4 , x5 . We already have the following constraints in the IP:
0 ≤ x1 , x2 , x3 ≤ 1, x4 , x5 ≥ 0, x4 , x5 ≤ 100, x1 , x2 , x3 , x4 , x5 ∈ Z
Each of the following is a condition that we want to implement for our IP. Write down constraints that formulate each condition.
(a) Exactly one of x1 , x2 , x3 is equal to 1.
(b) If x2 is 0, then x4 is also 0.
(c) x5 is odd or x4 < x5 .
(d) Exactly one of the following holds:
• x4 + x5 ≥ 50.
• x2 = x3 .
P2-2. A company with 100 employees had record profits in 2022, and it is paying all employees to go on some tours. There are five possible destinations: Australia, Bahamas, Cuba, Denmark and Egypt. The company wants to select at most 3 of these destinations for its employees. For each destination, if it is chosen, then there is a fixed cost (the cost to run a tour regardless of the number of participants) and a per person cost (the additional cost of having each person in the tour). There is a limit on the number of participants in a tour, and every employee must join a tour of one of the selected destinations. The data is recorded in the following table.
Destinations Australia Bahamas Cuba Denmark Egypt
Fixed cost 20,000 7,000 5,000 12,000 10,000
Per person cost 2,000 1,500 1,000 3,000 1,200
Maximum # of people 30 50 25 40 35
In addition, if Cuba and Egypt are both selected, then Bahamas cannot be selected. The company wants to minimize the total cost of these tours.
Formulate this problem as an integer program.
P2-3. Coach Stephen of the WatPivots basketball team must choose this year’s starting line-up. There are ten candidates who can play the positions Center (C), Guard (G), and/or Forward (F). Their skill levels (0 = bad to 3 = great) of shooting, rebounding and defense, and the positions that they can play are listed in the following table:
(a) Formulate an IP that selects 5 candidates for the starting line-up that maximizes the total defensive skill level (i.e., the sum of the defensive skill levels of the candidates on the starting line-up). In addition, at least two candidates must be able to play guard, at least two candidates must be able to play forward, and at least one candidate must be able to play center.
Coach Stephen also has additional personnel requirements. For each of the following conditions, state the constraints and/or variables that must be added to the IP in part (a) to satisfy that condition.
(b) Both the average shooting skill level and the average rebounding skill level of the starting line-up must be at least 2 each.
(c) The absolute value of the difference between the total shooting skill level (of the starting line-up) and the total rebounding skill level (of the starting line-up) must be at least two.
(d) Either Bill and Hillary start, or Donald and Feridun start, or all four start. (e) Either all three of Guang, Hillary, and Justin start or none of them start.
P2-4. For each of the following parts, explain how to use additional integer variables and linear constraints to ensure that the described conditions are satisfied.
(a) How can one ensure that the variable w1 assumes only one of the five values
2017, 2027, 2029, 2039, 2053, i.e., ensure that w1 ∈ {2017, 2027, 2029, 2039, 2053}. (b) Let α , β , δ , γ , θ, and λ be non-negative real-valued constants.
How can one ensure that the non-negative real-valued variables x and y satisfy either
αx + βy ≥ θ,
or
γx + δy ≥ λ (or both)?
P2-5. WatWagen (a subsidiary of Volkswagen) manufactures three types of automobiles: compact, midsize, and large. The resources required for each type and the profits yielded by each type are given in the following table.
Compact Midsize Large
Steel required 1.5 tons 3 tons 5 tons
Labor required 30 hours 25 hours 40 hours
Profit $4000 $6000 $8000
WatWagen has 30,000 tons of steel and 300,000 hours of labor available. If the firm decides to produce a type of auto, then for it to be economically feasible at least 1,000 cars of that type much be produced.
(a) Formulate an integer programming model to maximize WatWagen’s profit.
(b) Modify your model to handle the following additional condition. Due to marketing considerations, WatWagen can only produce the large model if it also produces either the compact or the midsize model, that is, it cannot choose to use its entire production capacity for the large model.
P2-6. This question is inspired by the board game Power Grid. Suppose you want to build some power plants, and buy enough fuel to power a certain number of cities. We give a list of available power plants and their information in this table.
The goal is to build enough power plants to power at least 17 cities, while minimizing the total cost of building the plants and buying fuel.
For each plant i ∈ {1, . . . , 12}, it costs $αi to build it (the currency is called “elektro”). Each power plant can be built at most once. There are 4 types of power plants: coal, oil, hybrid, and renewable. In order to run plant i, you need to buy exactly βi units of the fuel required for that plant. (For example, plant #6 requires 3 units of coal.) And the result is that you are able to power γi cities. For a hybrid power plant, the fuel can be any combination of coal and oil. (For example, plant #11 can run using 1 unit of coal and 2 units of oil.) For a renewable energy plant, no fuel is required.
The cost of one unit of coal is dependent on the number of units needed. The first 3 units of coal costs $3 each, the next 3 units of coal costs $5 each, and any further units of coal costs $7 each. Similarly for oil, the first 3 units of oil costs $4 each, the next 3 units of oil costs $6 each, and any further units of oil costs $8 each.
As an example, one possible way of powering at least 17 cities is to build plant #9, #10, and #11, for a total building cost of $132. We need 2 units of coal for #9. No fuel is required for #10. We decide to buy 2 units of coal and 1 unit of oil for #11. In total, the 4 units of coal cost $14, and the 1 unit of oil cost $4. The total cost is $150, and we are able to power 18 cities.
Model this problem as an integer program.
P2-7. A certain Canadian company is hiring agents for its call centre that responds to calls 24 hours a day. The company divides the time into 4-hour shifts, and each hired agent will work 2 consecutive shifts. There are 3 types of agents that they can hire: English-only, French-only, or bilingual. Based on historical data, the company sets the minimum number of agents speaking English or French for each shift in the table here.
Shift English French
1am - 5am (*) 5 7
5am - 9am (*) 15 17
9am - 1pm 35 37
1pm - 5pm 55 47
5pm - 9pm (*) 45 27
9pm - 1am (*) 25 17
A bilingual agent counts as both an English agent and a French agent for this table. For example, the 1am - 5am shift can be completed by 3 English-only, 5 French-only, and 2 bilingual agents.
The base salary for any hired agent is $20/hour (or $80 per shift). French-only agents will have their salaries multiplied by 1.3, and bilingual agents will have their salaries multiplied by 1.7. In addition, any agent that works during shifts marked by (*) will have their salaries multiplied by 1.5 for that shift. For example, a bilingual agent working the 5pm - 9pm shift will receive $20 · 1.7 · 1.5 = $51 per hour.
The goal is find a way of hiring agents that satisfies all the constraints while minimizing the total salary paid to all agents. Use an integer program to model this problem.
P2-8. A miniatures enthusiast has rented out a 3D printer for the day to print out some of their favourite miniature figures. The printer can be used from 8am to 12pm, and also from 12:30pm to 5pm. There are 500 grams of filament available (the filament is like the “ink” for the printer). The printer can only print one figure at a time. For each figure that you print, it is either printed completely before 12, or it is printed completely after 12:30.
There are 7 possible figures that can be printed, say the figures are labeled 1, . . . , 7. For each figure i, it takes ti hours to print it on the 3D printer, and uses fi grams of filament. Once the figure is produced, it can be sold for a profit of $pi. Also, each figure can only be printed at most once. The data are recorded here.
Figure i 1 2 3 4 5 6 7
Time ti 0.5 1.2 3 1.7 2.5 1.5 2.1
Filament fi 35 75 200 120 180 95 140
Profit pi 25 30 110 70 100 45 75
Write an integer program that satisfies all the constraints while maximizing the total profit.
P2-9. A company wants to form three different teams A,B,C from a pool of 7 employees, which we represent as the set E = {1, . . . , 7}. Each employee i has a certain number of years αi of experience at the company, and has βi as their current annual salary. Note that αi ,βi are constants, but you may assume that 0 ≤ αi ≤ 10 and 0 ≤ βi ≤ 100000.
We define binary variables xij for all i ∈ E and j ∈ {A,B, C} to represent
xij = { 1 employee i is on team j
0 otherwise
Suppose we are writing an integer program, and we have already defined the constraints which ensure that each xij is a binary variable.
For each of the following conditions, give constraints that correctly formulate it. You may use additional variables. You need to explain why your constrains work. (Note: Each condition is independent of each other.)
(a) Each employee is in either 1 or 2 teams.
(b) The average salary for team A is at least 50000.
(c) The difference between the total experience of any two teams is at most 2 years.
(d) At least 2 of these 3 conditions hold:
• Team A has at least 5 years of experience.
• Team B has at most 250000 in combined annual salary.
• Teams B and C have the same number of employees.