Production Optimization

Prompt

An electronics company produces transistors, resistors, and computer chips. Each transistor requires four units of copper, one unit of zinc, and two units of glass. Each resistor requires three units of copper, three units of zinc, and one unit of glass. Each computer chip requires two units of copper, one unit of zinc and 3 units of glass. The production requirements are summarized in figure 1.

Supplies of these materials vary from week to week, so the company needs to determine a different production run each week. For example, one week the total amounts of materials available are 960 units of copper, 510 units of zinc, and 610 units of glass. Set up the system of equations modeling the production run. Solve for the number of transistors, resistors, and computer chips to be manufactured this week using a numerical method for solving linear systems learned in this class. Make sure to show your work for the numerical approach. Calculate the analytical approach by solving by hand or using the MATLAB backslash operator.

Figure 1: Table containing production components and raw material ratios

Setting Up the Problem for Both Approaches

Looking at the problem we can see that setting up a system of linear equations will facilitate our numerical and analytical approaches. A system of equations allows us to graph the function (in some cases) or utilize the time-saving properties matrices. Matrices also enable us to more easily leverage software tools like MATLAB to evaluate the functions. Below we convert the provided data into a system of linear equations, then into a matrix of Ax = b form. The numerical and analytical solutions provide different methods for evaluating 'x'.

Numerical Solution Steps

A variety of numerical methods can be used to solve the system. For ill-conditioned matrices especially, different methods may lead to different results as some approaches manipulate the coefficient matrix differently and can preserve greater or fewer significant figures. For systems with four or more equations, the graphical approach cannot be used at all as four-dimensional modeling is infeasible. Below we use Naive Gauss elimination to solve the system.

The naive Gauss method involves eliminating variables in equations 2 through n (where n is total number of rows) by subtracting preceding rows that are scaled by some number. We do this until each row n has its pivot column equal to n. The last variable x(n) can be solved for directly in row n and can then be substituted back into preceding equations to solve for the remaining variables. See below.

Sample calculation (using provided data)

Pseudocode for numerical approach

%% Variable declarations and input data

% Declare matrix A (coefficients) and B (of form Ax = b)

a = ...;

b = ...;

% Collect size information about A. 'n' is used for number of equations.

[n,m] = size(a);

% Allocate space for solution vector 'x'

x = size(n);

%% Forward elimination loops

    DO for k = 1:n - 1

        for i = k + 1: n

            % Find value to multiply row n by

            factor = a(i,k) / a(k,k);

            % Subtract the altered row n from row n + 1 by navigating each column individually.

            % Now the leading variable in row n+1 has a coefficient of zero

            DO for j = k + 1: n

                a(i,j) = a(i,j) - factor*a(k,j);

            end DO

            % Subtract scaled value of b(n) in row n from b(n+1) in row n+1.

            b(i) = b(i) - factor*b(k);

        end DO

    end DO

%% Back substitution operations

    % Solve for last variable since there is only one unknown.

    x(n) =  b(n)/a(n,n);

    % Begin substitution loop. Starts at second to last row and works its

    % way up the matrix

    DO for i = n - 1: -1: 1

        % Temporary variable sum declared

        sum = b(i);

        % Use sum to isolate variable being solved for in each row

        DO for j = i + 1:n

            sum = sum - a(i,j)*x(j);

        end DO

        % Divide a variable's corresponding coefficient over to get the

        % variable alone on one side. This determines the variable's value

        x(i) = sum/a(i,i);

    end DO

%% Plot 3-dimensional functions

Analytical Solution Steps

The analytical solution uses MATLAB's backslash solver to determine the values of entries in vector x. The problem setup is identical and the same system of equations (A and B matrices) used numerical approach are used here. Instead of calling function Gauss in the command window to solve the matrix type the code below into the command window. MATLAB solves the matrix using the backslash function (or notifies you if it is not solvable) and displays the solution vector in the workspace.

>> A = [4,3,2;1,3,1;2,1,3];

>> B = [960;510;610];

>> x = A\B

Figure 2: Screenshot showing declaration of variables and calling function to numerically solve system using Gaussian function.

Numerical Results

Using the script provided in Appendix I we see the solution vector in Figure 2 displayed in the command window. The result is the same vector as seen in the analytical solution, showing this is an acceptable numerical approach for this particular system. It is worth mentioning that naive gauss elimination was used without partial pivoting, scaling, or error checking. In many systems, using this method may result in a division by zero which will cause an error. This can be avoided by adding components to the script that check for the mistake before completing the calculation (not checking for the mistake is "naive"). Pivoting rows and columns may also lead to a faster solution in some cases.

For added confirmation, a plot is added at the end of the script which graphs the three planes in a 3-Dimensional space. This is another numerical method called the "graphical method". Observing the point at which the three planes intersect (in a three-equation system) also gives us the coordinates of the solution vector. Looking at Figure 3 below, we can see the three planes and observe that the point of intersection coincides with our result from naive-gauss elimination and our analytical method.

Figure 3: All three equations plotted together using MATLAB. Determining the point at which all planes intersect also gives us the solution. This is known as the "graphical method".

Figure 4: Screenshot depicting results using MATLAB's built-in backslash feature for solving systems of linear equations

Analytical Results

Our analytical solution involves using MATLAB's backslash function in the command window to directly solve for the solution matrix. This checks the validity of our numerical approach (as we can be confident the MATLAB function operates properly) and confirms that Naive-Gauss elimination can be used for this system.

Figure 5: Condition number of our matrix "a"

Figure 6: Percent Error Calculations

Error Analysis

The analytical and numerical approaches both produced the same results for the solution vector x. Because each entry in the x vector in the numerical solution was identical to that of the same entry in the analytical solution, we know there is no true error for our numerical model (see Figure 6).

Looking at the condition number of the coefficient matrix may give us some insight into how susceptible our system is to round-off error.

Ill-conditioned systems refer to systems of equations where small changes to the coefficient matrix lead to significant changes in the solution matrix x (or in this case, 'C'). These systems may introduce error, especially in the form of round-off error and truncation error, because a large set of potential solutions to the system will satisfy the equations. As we perform row operations, scale, and eliminate variables from the matrix, any amount of rounding (which the computer must do if there are enough decimals on a coefficient) may lead to inaccurate solutions. You can think of an ill-conditioned system as one whose solution matrix is very sensitive to changes in A.

Condition numbers are used for coefficient matrices to determine whether they are ill-conditioned or well-conditioned. Having a high condition number can mean your system is ill-conditioned and is prone to truncation and round-off errors. Having a condition number close to 1 means the system is well-conditioned and we can be confident about the solution to a greater number of significant figures.

Our matrix A has a condition number of 5.3009, calculated using MATLAB's built-in function cond(A) (see Figure 5), meaning our system is well-conditioned. The number of lost significant figures in our operations is determined by the following equation:

= log(condition #)

= log(5.3009)

= 0.7243

This small rounding error originates from our low condition number and suggests that small changes in A would not significantly impact our solution x.

Appendix I: MATLAB CODE (Numerical Solution)

clear all; close all; clc; %% Variable declarations and input data % Declare matrix A (coefficients) and B (of form Ax = b)a = [4 3 2;1 3 1;2 1 3];b = [960;510;610]; % Collect size information about A. 'n' is used for number of eqns.[n,m] = size(a); % Allocate space for solution vector 'x'x = size(n); %% Forward elimination loops for k = 1:n - 1 for i = k + 1: n % Find value to multiply row n by factor = a(i,k) / a(k,k); % In coefficient matrix. Subtracts the altered row n % from row n + 1 by navigating each column individually. % Now the leading variable in row n+1 has a coefficient of zero for j = k + 1: n a(i,j) = a(i,j) - factor*a(k,j); end % In matrix 'b'. Subtracts scaled value of b(n) in row n from % b(n+1) in row n+1. This preserves validity of system (must % operate on 'both sides') b(i) = b(i) - factor*b(k); end end %% Back substitution operations % Solves for last variable (and in this case in the last row) directly % since there is only one unknown. x(n) = b(n)/a(n,n); % Begin substitution loop. Starts at second to last row and works its % way up the matrix for i = n - 1: -1: 1 % Temporary variable used to hold and transport the known aspects % of each row (each equation) to the same side as 'b'. Initialize % this variable with the b(i) value of its row sum = b(i); % Uses sum to move the individual products of all known variables and their % coefficients over to the side of 'b' in each row. This isolates the % unknown variable and prepares it to be evaluated by dividing both % sides by its coefficient for j = i + 1:n sum = sum - a(i,j)*x(j); end % Divides a variable's corresponding coefficient over to get the % variable alone on one side. This determines the variable's value x(i) = sum/a(i,i); end % Re-orient matrix x to be column vector. Display x = x'; display(x); %% Plot 3-dimensional functions figure(1)hold all;fsurf(@(s,t) 0.5*(960-(4*s)-(3*t)), [50, 150, 50, 150],'r'); hold on;fsurf(@(s,t) (510-(s)-(3*t)), [50, 150, 50, 150],'g'); hold on;fsurf(@(s,t) (1/3)*(610-(2*s)-(t)), [50, 150, 50, 150],'b'); hold on;xlabel('Variable x1 ("x")');ylabel('Variable x2 ("y")');zlabel('Variable x3 ("z")');title('Graphical Solution to Production Matrix');legend('Equation 1','Equation 2','Equation 3','location', 'northeast')box on; grid on;

Appendix II: MATLAB CODE (Analytical Solution)

% Type the following into the command window

>> A = [4,3,2;1,3,1;2,1,3];

>> B = [960;510;610];

>> x = A\B

% Solution will be displayed in command window

Google Sites

Report abuse