operation research homework /

Homework1

OPERATION RESEARCH

Problem 1 – You company is planning production of items for the next year. Your demand is given in the following table. Holding inventory cost $10 per item month. Setups in a period cost $100. No backorders are allowed.

Month										10	11	12
Demand	80	50	70	95	100	210	140	100	60	50	32	12

A. Formulate this problem

B. Add constraints to limit the production of items to less than 200 per month.

Problem 2- Excel power Oil Company as its refinery at Houston, Los Angeles, Beaumont, Lake Charles, and Mobil and has to supply oil to Detroit, Miami, New Orleans, and Florida. Shipping Cost, Capacity of refinery and Demand are given in table below. Determine the optimum shipping schedule.

	Detroit	Miami	New orleans	Florida	Capacity
Houston	$ 80.00	$ 70.00	$ 80.00	$ 90.00	800
Los Angeles	$ 100.00	$110.00	$ 90.00	$105.00	500
Beaumont	$ 90.00	$100.00	$ 105.00	$110.00	1000
Lake Charles	$ 100.00	$ 90.00	$ 10.00	$115.00	600
Mobil	$ 80.00	$100.00	$ 105.00	$ 0.00	700
Demand	1000	900	700	950

Word Problems

Problem Blending - A company makes two types of scrap steel ingots (ingot 1, ingot 2) from four inputs for scrap (input 1, input 2, input 3, and input 4). The chemical composition of the inputs has 2 elements (A, B) shown in table 1. The chemical composition of the output is shown in table 2. The company must produce 2000 tons of ingot 1 and 1000 tons of ingot 2. The cost and supply of the inputs of the inputs is displayed in the figure.

Table 1. Input composition.

Input	Amount of element A	Amount of element B	Cost	Supply
	99.7 %	0.3 %	90	2000
	99.2 %	0.8 %	140	1500
	98.5 %	1.5 %	200	1500
	98.0 %	2.0 %	75	3000

Table 2. Output composition.

	Ingot Type 1		Ingot Type 2
Element	Minimum	Maximum	Minimum	Maximum
	99.2 %	99.4 %	98.5 %	98.8 %
	.6 %	.8 %	1.2 %	1.5 %

Cutting Stock - You are a company that makes paper products in twenty foot roles (20 ft). Your customers demand rolls of paper in 3 ft, 5 ft, 9 ft, 10 ft and 7 ft rolls. Your customer demand is 15 3ft, 25 5 ft, 8 9ft and 9 10 ft roles. List the patterns that can be constructed and formulate the cutting stock integer program for minimizing the number of roles used.

Your boss wants supplier 1 to have at least 20% of the total input. Add this constraint. How would you determine the additional cost from this constraint?

Capital Project Knapsack- You have the following capital project with different costs and value. You have a total project budget of 10 M. Develop a formulation to maximize the value of the project minus the cost of the projects.

Project	Cost (m)	Value
		1.1
	2.1
	.5	1.2
		.6
	1.5	.2
	2.2	4.1
	1.8
	.4	.5
	.8
10	5.9	10

a. Formulate this problem (15 points).

b. Management suggests that you can only do 6 projects in a time period due to management time constraints. Add this constraint to your formulation.

c. Only project 1 or 2 can be performed but not both. Add this constraint.

d. Project 7 cannot be done unless project 6 is done?

Procurement - A government agency wants to purchase fuel for n depots from m bidders. Each bidder can provide ai gallons to the government. Each depot demands dj gallons. Let ci,j be the total cost of delivering a gallon from bidder i to depot j.

Formulate this as linear program to minimize total cost?
Suppose overseas suppliers are limited to 5% of the auction. Let vi be one if the supplier is overseas and zero otherwise.

Linear Programming

1. How do you prove infeasibility in the simplex method?

2. How do you demonstrate an unbound solution in the simplex method?

3. What is the maximum number of points that the simplex method might visit?

4. In your own words, describe the steps of the simplex method?

5. How can you prove that a constraint does not remove any feasible points?

Integer Programming

1. Describe IBM Cplex based on reviewing the website?

2. What is a cutting plane for Integer programming?

3. What is branch and cut?

4. What is NP-hard in terms of integer programming?

5. Describe the lower bound for an integer programming problem not solved to the optimal solution?

6. What can be the results for solving an integer program if you give the computer a fixed amount of time (such as 1 hour)?

7. Solve this knapsack problem via branch and bound by hand.

min 2x1 + 3x2+6 x3 +11 x4

st: 3x1 + 5 x2+ 5 x3 + 6 x4 > 11

Networks (independent learning – might be on test)

Describe Dijkstra’s Algorithm for the shortest path problem? What is the computational complexity? Please provide a worked example.

Explain how to formulate the shortest path problem as a linear program.