COMP4041-LDO Workshop 2 Fundamentals of Linear Programming

Purpose: Develop algebraic and spreadsheet models for small optimization problems and apply the graphical method to 2-variable LP models.

The Excel file for this workshop includes a screenshot of the spreadsheet LP model for the following optimization problem:

A company does VEGETABLES DISTRIBUTION to grocery stores. A box of each vegetable uses 1.25 units of storage space and the amount of available space in the warehouse is 18,000 units. The budget that the company has for buying vegetables for distribution is ¡ê30,000. The predicted minimum and maximum demand for each vegetable is given in the table together with the cost for each box of the vegetables and the retail price. The profit for each vegetable is given by the retail price minus the cost. The company wants to decide how many boxes of each vegetable to buy in order to maximise their total profit subject to the storage capacity, budget limitation and predicted demands.

Examine the spreadsheet model and extract the algebraic formulation implemented (replicating the spreadsheet model is optional). Solve the algebraic model in LP-Solve. Note that the algebraic model must correspond to the spreadsheet (there might be other ways to write the algebraic formulation). Type algebraic expressions in the standard form with all decision variables on the left and the single scalar value on the right.

Implement the spreadsheet (Excel) and algebraic (LP-solve) LP models to solve the following optimization problem:

A company buys APPLES and produces apple-syrup and apple-juice. It costs $0.80 to produce one litre of apple-syrup and $0.60 to produce one litre of apple-juice. At least 20% but not more than 60% of the overall production in litres must be apple-juice. The company would like to meet but definitely not exceed the estimated demand of each product. The estimated demand is initially 5,000 litres of apple-syrup and 4,000 litres of apple-juice. However, an additional demand of 3 litres of apple-syrup is estimated for each $1 spent in advertising the syrup. Similarly, an additional demand of 5 litres of apple-juice is estimated for each $1 spent in advertising the juice. The overall budget for production and advertising is $16,000. A litre of apple-syrup sells at $1.75 and a litre of apple-juice sells also at $1.75. The company wants to know how much to produce of each product and how much to spend in advertising for each product in order to maximize profit which is calculated as the total revenue minus the production and advertising costs.

With reference to the LP model developed for the above APPLES problem, consider different approaches to develop the model using different set of decision variables. Aim to develop two different LP models that produce an optimal solution with the same objective function value. Implement the alternative model in LP-Solve.

Apply the graphical method to solve the following LP model. Make sure to clearly identify the following in the graph: constraints, feasible region, objective function, CPF solutions, optimal CPF solution, binding constraints and non-binding constraints.

Maximize: Subject to:

Z = 25X1 + 10X2

10X2 <= 800 (1) 25X1 <= 1500 (2)
5X1 + 7X2 <= 600 (3) X1 >= 0 (4) X2 >= 0 (5)

The following modification is made to the original model of Step 4. Apply the graphical method to solve the new model after the modification.

– change constraint (3) to 7X1 + 2.8X2 <= 600
Write the algebraic LP model for the following optimization problem. You might want to also implement the model in Excel or Lp-Solve.
As a TOY BUILDER you enjoy making toys for both fun and profit. For your latest production batch, you need to decide how many of each toy to make. The three types of toys you make are airplanes, helicopters, and cars. To build an airplane you need 3 blue blocks, 2 green rods, and 1 red wheel. To build a helicopter you need 2 blue blocks, 4 green rods, and 1 red wheel. To build a car you need 1 blue block, 2 green rods, and 4 red wheels. Your profit margins for each toy are as follows: Airplane ¡ê7, Helicopter ¡ê8, Car ¡ê5. The parts available to you are as follows: 25 blue blocks, 29 green rods, and 30 red wheels. It is ok to have leftover parts. The objective is to maximize the total profit margin.