User:Olathe

From Wikipedia, the free encyclopedia

The easiest way to do it is:

  1. Find b2 − 4ac. If it's a negative number, you can stop, because you can't factor it.
  2. Get \sqrt{b^2 - 4ac} (you already have b2 − 4ac). Let's call it d (for discriminant).
  3. Now, the factored answer is a \left [ x + \frac{b + d}{2a} \right ] \left [ x + \frac{b - d}{2a} \right ].

So, let's say we want to factor 2x2 − 11x − 6. Here's the work shown for that :

  1. d = \sqrt{ (-11)^2 - 4 \cdot 2 \cdot (-6) }
  2. = \sqrt{ 121 + 48 } (the number inside the square root isn't negative, so you know how to take its square root).
  3. = \sqrt{ 169 }
  4. = 13 (our discriminant is 13).
  5. 2 \left [ x + \frac{-11 + 13}{2 \cdot 2} \right ] \left [ x + \frac{-11 - 13}{2 \cdot 2} \right ]
  6. 2 \left [ x + \frac{2}{4} \right ] \left [ x + \frac{-24}{4} \right ]
  7. 2 \left [ x + \frac{1}{2} \right ] \left [ x - 6 \right ]

If you want, you can get rid of the 1/2 in (x + 1/2). You just multiply out 2 (x + 1/2) :

\left [ 2x + 1 \right ] \left [ x - 6 \right ]
This user eats sushi.
This user hates Wikipedia.


% DIST   The distribution problem algorithm.
%   Finds a way, if possible, to satisfy all demands for supplies when some
%   source-destination routes have a maximum capacity.
% 
% USAGE
%   flow = dist(route_maxes, supplies, demands, show_stages) 
%   
% OUTPUTS
%   flow        : a way to distribute the supplies; if it is impossible to
%                 satisfy all demands, this is a 1-by-0 empty matrix
% 
% REQUIRED INPUTS
%   route_maxes : maximum delivery from each source to each destination
%                 (one row per source; one column per destination)
%   supplies    : supplies at each source
%   demands     : demands at each destination
% 
% OPTIONAL INPUTS
%   show_stages : true to show each stage, false or left out to hide stages
% 
% EXAMPLE
%   route_maxes = [5 0 4 4 0; 4 4 4 0 1; 3 3 4 5 7; 7 5 0 4 3];
%   supplies    = [6 9 6 17]';
%   demands     = [8 5 6 8 10];
%   dist(route_maxes, supplies, demands)
%   
%   ans =
%   
%        0     0     2     4     0
%        2     2     4     0     1
%        0     0     0     0     6
%        6     3     0     4     3

% by C Erler, 2005
% Public domain, no warranty

function flow = dist(route_maxes, supplies, demands, show_stages)
    if nargin < 4
        show_stages = false;
    end
    
    % === Problem preparation ===
    check_preconditions;
    
    if sum(demands) > sum(supplies)
        if show_stages
            disp(sprintf('The total demand (%d) exceeds the total supply (%d) by %d.', ...
                sum(demands), sum(supplies), sum(demands) - sum(supplies)));
        end
        disp_nonfeasible;
        flow = zeros(1, 0);
        return;
    end
    
    if size(supplies, 2) > 1
        supplies = supplies';
    end
    if size(demands, 1) > 1
        demands = demands';
    end
    
    surplus = supplies;
    unmet = demands;
    flow = zeros(size(route_maxes));
    
    row_labels = zeros(size(route_maxes));
    column_labels = zeros(size(route_maxes));
    
    % === Steps 1 and 2 (and 3a) ===
    for source = 1:length(supplies)
        for destination = 1:length(demands)
            flow(source, destination) = min([route_maxes(source, destination),...
                surplus(source), unmet(destination)]);
            surplus(source) = surplus(source) - flow(source, destination);
            unmet(destination) = unmet(destination) - flow(source, destination);
        end
    end
    
    disp_table('Original problem', false);
    
    if ~unmet
        return;
    end
    
    new_rows = surplus;
    new_columns = zeros(size(demands));
    
    while 1
        % === Step 3b ===
        added_column_labels = ...
            min(route_maxes - flow, repmat(new_rows, 1, length(demands))) .* ...
            repmat(~sum(column_labels), length(supplies), 1);
        column_labels = column_labels + added_column_labels;
        new_columns = max(added_column_labels);
        
        if length(find(new_columns > 0)) == 0
            disp_nonfeasible;
            flow = zeros(1, 0);
            return;
        end
        [increase, column] = max(new_columns .* ~~unmet);
        increase = min(increase, unmet(column));
        
        if increase
            unmet(column) = unmet(column) - increase;
            while column
                row = find(column_labels(:, column) >= increase, 1);
                flow(row, column) = flow(row, column) + increase;
                column = find(row_labels(row, :) >= increase, 1);
                if column
                    flow(row, column) = flow(row, column) - increase;
                end
            end
            surplus(row) = surplus(row) - increase;
                    
            if ~unmet
                disp_table('Final result');
                return;
            end
            disp_table;
            
            row_labels = zeros(size(route_maxes));
            column_labels = zeros(size(route_maxes));
            
            new_rows = surplus;
            new_columns = zeros(size(demands));
        else
            % === Step 3c ===
            added_row_labels = ...
                min(flow, repmat(new_columns, length(supplies), 1)) .* ...
                repmat(~sum(row_labels')', 1, length(demands)) .* ...
                repmat(~surplus, 1, length(demands));
            row_labels = row_labels + added_row_labels;
            new_rows = max(added_row_labels')';
            
            if length(find(new_rows > 0)) == 0
                disp_nonfeasible;
                flow = zeros(1, 0);
                return;
            end
        end
    end
    
    
    % Check preconditions
    function check_preconditions
        if ~isvector(supplies), error('supplies must be a vector.'), end
        if ~isvector(demands),  error('demands must be a vector.'),  end
        
        if size(route_maxes, 1) ~= length(supplies)
            error('The source count must match in route_maxes and supplies.');
        end
        if size(route_maxes, 2) ~= length(demands)
            error('The destination count must match in route_maxes and demands.');
        end
        
        if find(supplies < 0)
            error('All elements of supplies must be nonnegative.');
        end
        if find(demands < 0)
            error('All elements of demands must be nonnegative.');
        end
        if find(route_maxes < 0)
            error('All elements of route_maxes must be nonnegative.');
        end
    end
    
    % Display the table nicely.
    function disp_table(header, add_blank_line)
        if show_stages
            data = [route_maxes supplies; demands 0];
            data = data .* ~(data == Inf);
            field_width = max(floor(log10(max(max(data)))) + 1, 3);
            
            end_field_format = sprintf('%%s%%%dd : %%%dd', field_width, field_width);
            field_format = sprintf('%%%dd : %%%dd |', field_width, field_width);
            end_separator = repmat('-', 1, field_width * 2 + 4);
            separator = sprintf('%s+', end_separator);
            no_column_labels = sprintf('%s|', repmat(' ', 1, field_width * 2 + 4));
            
            if nargin < 2 || add_blank_line
                disp(' ');
            end
            if nargin > 0
                disp(repmat('=', 1, length(header) + 2));
                disp(sprintf(' %s ', header));
                disp(repmat('=', 1, length(header) + 2));
            end
            
            for row = 1:length(supplies)
                line = '';
                line = sprintf(field_format, [route_maxes(row, :); flow(row, :)]);
                line = sprintf(end_field_format, line, supplies(row), surplus(row));
                labels = find(row_labels(row, :) > 0);
                if surplus(row) > 0
                    line = sprintf('%s [ S ]', line);
                elseif labels
                    line = sprintf('%s [%s ]', line, sprintf(' %d', labels));
                end
                disp(line);
            end
            disp(sprintf('%s%s', repmat(separator, 1, length(demands)), ...
                end_separator));
            disp(sprintf(field_format, [demands; unmet]));
            line = '';
            for column = 1:size(route_maxes, 2)
                labels = sprintf(' %d', find(column_labels(:, column) > 0));
                if ~strcmp(labels, ' ')
                    labels = sprintf('%s[%s ]%s', ...
                        repmat(' ', 1, floor(field_width - length(labels) / 2)), ...
                        labels, ...
                        repmat(' ', 1, ceil(field_width + 1 - length(labels) / 2)));
                    line = sprintf('%s%s', line, sprintf('%s|', labels));
                else
                    line = sprintf('%s%s', line, no_column_labels);
                end
            end
            disp(line);
        end
    end
    
    % Inform the user that there is no feasible solution.
    function disp_nonfeasible
        if show_stages
            disp(' ');
            disp('+-----------------------+');
            disp('| No feasible solution. |');
            disp('+-----------------------+');
        end
    end
end

[edit] Systems of equations

You will be given a bunch of equations and asked to find what all the variables equal :

37a + 5b + 11c + 2d = 5e + 35
6a + d + 250e - 9 = 2
240a + 11b + 12c + 4e + 5 = 0
56a + 10b + d + 5e = 2
2c + 30d = 1 - 15e

Get them in the form variables = number.

37a + 5b + 11c + 2d - 5e = 35
6a + d + 250e = 11
240a + 11b + 12c + 4e = -5
56a + 10b + d + 5e = 2
2c + 30d + 15e = 1

Make a table with columns for each of the variables and a column for the number on the other side of each equation :

\left (  \begin{matrix}   37 & 5 & 11 & 2 & -5 \\   6 & 0 & 0 & 1 & 250 \\   240 & 11 & 12 & 0 & 4 \\   56 & 10 & 0 & 1 & 5 \\   0 & 0 & 2 & 30 & 15  \end{matrix}  \;  \right |  \left.  \begin{matrix}   35 \\   11 \\   -5 \\   2 \\   1  \end{matrix}  \right )

This is how you want it to look (the stars can be anything) :

\left (  \begin{matrix}   1 & * & * & * & * \\   0 & 1 & * & * & * \\   0 & 0 & 1 & * & * \\   0 & 0 & 0 & 1 & * \\   0 & 0 & 0 & 0 & 1  \end{matrix}  \;  \right |  \left.  \begin{matrix}   \mbox{*} \\   \mbox{*} \\   \mbox{*} \\   \mbox{*} \\   \mbox{*}  \end{matrix}  \right )

The important part is that each row starts with a one and it starts a little later than the rows before, even if it looks something like this :

\left (  \begin{matrix}   1 & * & * & * & * \\   0 & 0 & 0 & 1 & * \\   0 & 0 & 0 & 0 & 0 \\   0 & 0 & 0 & 0 & 0 \\   0 & 0 & 0 & 0 & 0  \end{matrix}  \;  \right |  \left.  \begin{matrix}   \mbox{*} \\   \mbox{*} \\   0 \\   0 \\   0  \end{matrix}  \right )

Even though the each new row doesn't start exactly one square behind the last one, they all still start with one and start later and later.

You can now use three rules to change this around :

  1. Change the order of the rows however you want.
  2. Multiply everything on a row by any number except zero.
  3. Add or subtract a row from another.