Question

The company PROD produces two different products, \(\mathrm{P}_{1}\) and \(\mathrm{P}_{2}\), based on three different raw materials, \(\mathrm{M}_{1}, \mathrm{M}_{2}\) og \(\mathrm{M}_{3}\). The following table shows how much of each raw material \(\mathrm{M}_{i}\) that is required to produce a single unit of each product \(\mathrm{P}_{j}\) : For instance, to produce one unit of \(\mathrm{P}_{2}\) one needs 1 unit of \(\mathrm{M}_{1}, 3\) units of \(\mathrm{M}_{2}\) and 4 units of \(\mathrm{M}_{3}\). Furthermore, PROD has available 100 , 80 and 150 units of material \(\mathrm{M}_{1}, \mathrm{M}_{2}\) and \(\mathrm{M}_{3}\) respectively (for the time period considered). The revenue per produced unit of product \(\mathrm{P}_{1}\) is \(150 \mathrm{NOK}\), and for one unit of \(\mathrm{P}_{2}\) it is \(175 \mathrm{NOK}\). On the other hand the raw materials \(\mathrm{M}_{1}, \mathrm{M}_{2}\) and \(\mathrm{M}_{3}\) cost 10,17 and \(25 \mathrm{NOK}\) per unit, respectively. The question is: How much should PROD produce of each product? We here assume that PROD wants to maximize its net revenue (which is revenue minus costs). a) Let \(x\) and \(y\) be the number of units produced of product \(P_{1}\) and \(\mathrm{P}_{2}\), respectively. Explain why the total revenue \(f(x, y)\) is given by \(f(x, y)=150 x-(10 \cdot 2+17 \cdot 5) x+175 y-(10 \cdot 1+17 \cdot 3+25 \cdot 4) y\) and simplify this expression. The function \(f(x, y)\) is linear in \(x\) and \(y\) (check that you know what linearity means). b) Explain why PROD's problem may be stated mathematically as follows: maximize \(f(x, y)\) subject to $$ \begin{array}{r} 2 x+y \leq 100 \\ 5 x+3 y \leq 80 \\ 4 y \leq 150 \\ x \geq 0, y \geq 0 \end{array} $$ This is an example of a linear optimization problem. c) The production \((x, y)\) may be considered as a point in the plane. Illustrate geometrically the set \(T\) of all such points that satisfy the constraints in model (7.8). Every point in this set is called a feasible point. (Hint: For every inequality determine first the straight line obtained by replacing the inequality by equality. Then, find the points satisfying the inequality (a halfplane), and finally, intersect these halfplanes.) d) Make a program optimization1.py for drawing the straight lines defined by the inequalities. Each line can be written as \(a x+b y=c\). Let the program read each line from the command line as a list of the \(a, b\), and \(c\) values. In the present case the command-line arguments will be $$ [2,1,100],[5,3,80],[0,4,150], \quad[1,0,0], \quad[0,1,0] \text {, } $$ e) Let \(\alpha\) be a positive number and consider the level set of the function \(f\), defined as the set $$ L_{\alpha}=\\{(x, y) \in T: f(x, y)=\alpha\\} $$ This set consists of all feasible points having the same net revenue \(\alpha\). Extend the program with two new command-line arguments holding \(p\) and \(q\) for a function \(f(x, y)=p x+q y\). Use this information to compute the level set lines \(y=\alpha / q-p x / q\), and plot the level set lines for some different values of \(\alpha\) (use the \(\alpha\) value in the legend for each line). f) Use what you saw in e) to solve the problem (7.8) geometrically.

Short answer

Maximize net revenue function with constraints by intersecting feasible regions; optimize using boundary intersections.

Step-by-step solution

Define Revenue and Costs

To calculate the total revenue and costs for products \(P_1\) and \(P_2\), we use the given prices and costs for raw materials. The revenue for \(P_1\) is 150 NOK per unit and for \(P_2\) is 175 NOK per unit. The costs for producing one unit of each are calculated using the costs of raw materials. For \(P_1\), it requires 2 units of \(M_1\) and 5 units of \(M_2\), thus costing \(10 \times 2 + 17 \times 5\). For \(P_2\), it requires 1 unit of \(M_1\), 3 units of \(M_2\), and 4 units of \(M_3\), hence costing \(10 \times 1 + 17 \times 3 + 25 \times 4\).

Calculate Net Revenue Function

The net revenue function \(f(x, y)\) is given by subtracting the total costs from total revenues. The expression for \(f(x, y)\) is: \[ f(x, y) = 150x - (10 \times 2 + 17 \times 5)x + 175y - (10 \times 1 + 17 \times 3 + 25 \times 4)y\] Calculating the costs: For \(P_1\): \(10 \times 2 + 17 \times 5 = 105\)For \(P_2\): \(10 \times 1 + 17 \times 3 + 25 \times 4 = 163\)Substituting these back, we get: \[ f(x, y) = (150 - 105)x + (175 - 163)y = 45x + 12y\]

Formulate Linear Optimization Problem

The goal is to maximize the net revenue function \(f(x, y) = 45x + 12y\) subject to raw material constraints and non-negativity constraints. The constraints can be outlined as:- \( 2x + y \leq 100 \) (Material \(M_1\) constraint)- \( 5x + 3y \leq 80 \) (Material \(M_2\) constraint)- \( 4y \leq 150 \) (Material \(M_3\) constraint)- \( x \geq 0, y \geq 0 \) (Non-negativity) This leads to the optimization problem setup as a system of linear inequalities.

Graph Feasible Region

To graphically determine feasible points, plot the lines given by the constraints by converting inequalities to equations (equality form) and then identifying the half-planes that satisfy the inequalities. Intersecting the half-planes yields the feasible region. The lines are:1. \(2x + y = 100\)2. \(5x + 3y = 80\)3. \(4y = 150\)4. \(x = 0\)5. \(y = 0\)These lines form boundaries of the feasible region in the first quadrant.

Plotting Lines and Solving with Optimization Program

Write a program named `optimization1.py` to plot these constraint lines. The command line inputs for the program will be coefficients of each line equation. Also, implement logic to determine feasible intersections and highlight these on a plot. Extend the program to accept new coefficients for the net revenue function and plot the level set lines \(y = \frac{\alpha}{q} - \frac{p}{q}x\) for various \(\alpha\) values, visually confirming optimal solutions.

Graphical Solution of Optimization Problem

Using the graphical output, identify the intersection point on the boundary of the feasible region where the net revenue function \(f(x, y) = 45x + 12y\) has the highest possible value, subject to being within the feasible region. This point will visually be where the farthest level curve intersects the feasible region boundary.

Key concepts

Net Revenue Function

In a linear optimization problem, the net revenue function represents the total profit a company earns after accounting for costs. Specifically, for the company PROD, the function captures how revenues from products are affected by raw material costs.

• The net revenue function is derived by subtracting total production costs from total revenues.
• For product \(P_1\), each unit sells for 150 NOK, and costs involve 2 units of \(M_1\) and 5 units of \(M_2\). The total cost per unit is \(10 \times 2 + 17 \times 5 = 105\).
• For \(P_2\), the selling price is 175 NOK per unit, with costs linked to 1 unit of \(M_1\), 3 of \(M_2\), and 4 of \(M_3\). Thus, the cost is \(10 \times 1 + 17 \times 3 + 25 \times 4 = 163\).

The net revenue function becomes\(f(x, y) = 45x + 12y\), where \(x\) and \(y\) are the quantities of \(P_1\) and \(P_2\) produced, respectively. Maximizing this function is the primary objective of PROD's problem.

Feasible Region

The feasible region is a critical concept in linear optimization that describes the set of all possible solutions that satisfy a problem's constraints.

• Each constraint is an inequality that the solution must meet, such as available material limits or non-negativity for product quantities the company can't exceed.
• For PROD, constraints include maximum uses of materials \(M_1\), \(M_2\), and \(M_3\), and are expressed as: \[\begin{align*} 2x + y &\leq 100, \ 5x + 3y &\leq 80, \ 4y &\leq 150, \ x &\geq 0, \ y &\geq 0.\end{align*}\]

This set of inequalities defines a polygonal area on the graph known as the feasible region. All optimal production combinations (\(x, y\)) lie within this region.

Linear Inequalities

Linear inequalities are the backbone of constraints in optimization problems. They represent limits such as resources and costs and are mathematically expressed in forms like \(ax + by \leq c\).

• Each inequality in PROD's problem links the production quantities to the resources.
• The inequality \(2x + y \leq 100\) denotes how products \(P_1\) and \(P_2\) together should not exceed the available \(M_1\).

Graphically, these inequalities create half-planes on the coordinate grid. The intersection of these half-planes forms PROD's feasible region.

Graphical Method

The graphical method is used in linear optimization to visually identify the best solution within a feasible region. By plotting the constraints as lines on a graph, you can easily see where feasible solutions might exist.

• To plot the inequalities from the constraints, convert each inequality to an equality (e.g., change \(2x + y \leq 100\) to \(2x + y = 100\)).
• The intersection of these lines forms vertices of the polygonal feasible region.

The optimal solution is typically found at one of these vertices. These methods can be used manually on graph paper or through a programmed approach that automates the plot, such as with Python script `optimization1.py`. This script utilizes command-line input to generate the constraint lines and level set lines, helping visualize potential solutions.