Current location - Training Enrollment Network - Mathematics courses - How to transform a transportation problem with unbalanced production and marketing into a transportation problem with balanced production and marketing?
How to transform a transportation problem with unbalanced production and marketing into a transportation problem with balanced production and marketing?
The method of transforming the transportation problem with unbalanced production and marketing into the transportation problem with balanced production and marketing is as follows:

The mathematical model of balanced transportation of production and marketing can be expressed as follows.

In the formula, min means to get the minimum, because the objective function means the total transportation cost and requires it to be the minimum, and S.T. means "the constraint condition is". The meaning of the first m lines in the constraint condition is that the sum of the quantity xij of goods transported from a certain production area ai to each sales area is equal to the output Ai of that production area.

The last n line means that the sum of the quantity xij of goods transported from a certain production area Bj to each sales place is equal to the sales volume bi of the sales place, and the last line means that the variable is not negative, because it is meaningless to have negative goods. If the total output of the transportation problem is equal to the total sales, there are

When bj and I meet this condition, it is called a transportation problem with balanced production and marketing, otherwise it is called a transportation problem with unbalanced production and marketing. The transportation problem of unbalanced production and sales can be transformed into the transportation problem of balanced production and sales by increasing the imaginary production area or imaginary sales area.

The above model is a linear programming model, and simplex method is a very effective general method to solve linear programming problems, so simplex method can also solve transportation problems. However, when the simplex method of linear programming is used to solve the transportation problem, even if three production areas and four sales areas are solved (m=3, n=4), an artificial variable must be introduced into each constraint condition.

Extended data:

Solution idea

The solution X=(xij) of the transportation problem obtained according to the mathematical model of the transportation problem represents a transportation scheme, in which the value of each variable xij indicates that Ai dispatches goods with quantity xij to Bj. It is pointed out that the transportation problem is a linear programming problem and can be solved by iterative method, that is, a feasible solution is found first.

Check the optimality of the solution, if it is not the optimal solution, make iterative adjustment to get a new and better solution, and continue to check, adjust and improve until the optimal solution is obtained. To solve the transportation problem according to the above ideas, it is required that the solution X=(xij) obtained in each step must be its basic feasible solution, that is:

Solution x must satisfy all constraints in the model; The coefficient column vector of the constraint equation corresponding to the base variable is linearly independent; The number of non-basic variables in the solution cannot be greater than (m+n- 1), because although there are (m+n) structural constraints in the transportation problem, only (m+n- 1) structural constraints are linearly irrelevant, because the total output is equal to the total sales;

In order to make the iteration go smoothly, the number of base variables should always be (m+n- 1). Because it can be proved that the coefficient column vector of the constraint equation corresponding to the (m+n- 1) base variable is linearly independent.

Baidu encyclopedia-traffic problems