You have started a new travel website that finds the cheapest direct or multi-leg flight between any given origin and destination. You do this by first asking your customer to enter information about his/her desired departure date, time, and the origin, as well as his/her desired arrival date, time, and the destination. You will then get information on all flights departing from the origin whose departure times are within your customer's specifications (leg 1). For each of those flights, you will get information on all flights that will depart after at least an hour from the first flight's arrival time from the same airport (leg 2). You will repeat this until a flight's destination is the same as your customer's destination or its arrival date and time is not within your customer's acceptable arrival date and time. This will give you a table like the following:

Airport	A	B	C	D	E	DEST
Origin	140	200	150	-	-	900
A	-	100	-	170	-	-
B	-	-	200	180	400	-
C	-	-	-	-	250	-
D	-	-	-	-	160	300
E	-	-	-	-	-	210

The entries in the above table represent the total cost of using that route. Specifically, it includes any disutility that your customer may experience from the layover period in any airport other than the origin and destination. If a cell is filled with "-", it means that it is not possible to go from the airport identified by the cell's row label, to the airport identified by the cell's column label. For example, there is no flight between airports A and C that fits your customer's specification.

Here are a few other examples:

• There is a flight from origin to airport A, and it costs 140.
• There is a flight from airport A that goes to airport B and it costs 100. There is also a flight from airport A that goes to airport D and it costs 170.
• There is a flight from airport D that goes to airport E and costs 160. There is also a flight from airport D that goes to Destination (DEST) and costs 300.

answer follwoing 6 questions, question 1,3 and 6 answering by Excel file

1.Draw a graph that represents the above data. (Denote each airport by a node. Connect two nodes by an edge if it is possible to go from one node to the other, with the direction denoted by an arrow.)UploadExcel document

2. Formulate an optimization problem whose solution is the cheapest route from the Origin to the Destination.

1. Clearly list all inputs (i.e., decision variables), parameters, and outputs (i.e., objective function) and assign them a symbol if necessary. [8 pts] Instruction: Please list all decision variables. For parameters, you can simply (but unambiguously) refer to the relevant data in the text. Please be as explicit as you can.
2. Express the algebraic relationship between inputs/parameters and constraints/objective function. [10 pts] Instruction: Please list ALL constraints, including constraints on the sign and type of the decision variables.If you are not comfortable with expressing these relationships algebraically, state them in words andclearly reference the parts of the Excel sheet that implement them.When there are too many constraints to list, you can group them and describe each group individually. Please specify how many constraints are in each group and what they represent. Hint: If you don't know how to approach this problem, review the Arbitrage in FX Market problem.

3. Implement your Q2 formulation in MS Excel, solve for the optimal solution, and upload the file. [7 pts]uploadexcelfile Instruction: Please clearly label the 4 distinct parts of your implementation: Parameters, Decision variables, Objective, Constraints. Five points will be given to correct implementation. Two points will be given to clear presentation.

4. Clearly describe the strategy (route) that achieves the minimum cost. [2 pts]

5. Reformulate the problem such that it allows the customer to specify an upper bound on the number of connections. This bound will be part of your data, i.e., it will be a known constant such as one or two (one means that the customer can tolerate at most one connection, i.e., his/her trip can consists of either a direct flight to the destination or two flights connecting at an intermediate airport and ending at the destination). You must providea single formulationthat works withany given upper boundfor the number of connection.

hint: You can introduce binary decision variables. Review the warehouse selection problem if you are not sure how to use these binary decision variables. Instruction: Please list ALL constraints, including constraints on the sign and type of the decision variables.If you are not comfortable with expressing these relationships algebraically, state them in words andclearly reference the parts of the Excel sheet that implement them.When there are too many constraints to list, you can group them and describe each group individually. Please specify how many constraints are in each group and what they represent. [12 points for correct formulation; 3 points for clarity]

6. Implement your formulation in Q5 and solve it when

1. the maximum number of connections is set to 1, and
2. the maximum number of connections is set to 3.

For each case (A and B) describe the optimal route and report the minimum cost. Instruction: Please have a separate sheet for each case. Provide your description in the corresponding sheet. [2 points for correct implementation; 3 point for clear presentation; 5 point for the description of the optimal route and minimum achievable cost]UploadExcel file