Catégorie : Excel VBA Course

In the general case, the transportation problem can be formulated as follows: in mm supply points A₁,…,A_m there is a homogeneous commodity with quantities a₁,…,a_m units, respectively. This commodity must be delivered to consumers B₁,…,B_n with demands b₁,…,b_n. The cost of transporting one unit from supply point i (i=1,…,m) to destination j (j=1,…,n) is c_ij. It is required to construct a shipping plan that fully satisfies consumer demand while minimizing the total transportation cost.

Mathematically, the transportation problem can be written as:

Thus, given the system of constraints with and the linear objective, the task is to find among all solutions a non-negative solution that minimizes if the total supply equals the total demand:

If either of the following holds:

then the model is called open (unbalanced).

To make an open transportation problem solvable, it should be transformed into a closed one:

• If

introduce a dummy destination B_n+1 (i.e., add an extra column). The demand of the dummy consumer is  .

The transportation costs to the dummy destination are taken equal (usually zero, if no storage cost is specified), i.e .

• If

introduce a dummy supplier A_m+1 (i.e., add an extra row). The supply of the dummy supplier is

 .

The transportation costs from the dummy supplier are taken equal (usually zero, if no penalty costs for under-delivery are specified), i.e.,

.

When transforming an open problem into a closed one, the objective function does not change, since all terms corresponding to the additional (dummy) shipments are zero.

 

To produce fertilizers of types 1 and 2, chemical substances A, B, C, and D are used, with the requirements shown in Table 1. 

Table 1. Requirements for chemical content in fertilizers

Fertilizer type	Requirements for chemical content
1	No more than 50% of substance A No more than 60% of substance B
2	From 40% to 70% of substance B At least 20% of substance C No more than 80% of substance D

The characteristics and reserves of the minerals used to produce the chemical substances A, B, C, and D are shown in Table.

Table 2. Characteristics and reserves of minerals

Mineral	Maximum stock, t	Composition, % (A, B, C, D)	Price, u.c./t
1	1200	30, 20, 15, 35	40
2	2500	20, 30, 10, 40	50
3	3100	15, 15, 40, 30	60

The selling price of 1 ton of fertilizer type 1 is 320 u.c., and of fertilizer type 2 is 350 u.c.
It is required to maximize the profit from the sale of fertilizers of both types.

Step 1. Mathematical Model

Let:

•  amounts of chemical substances A, B, C, D used to produce fertilizer type 1.
•  amounts of chemical substances A, B, C, D used to produce fertilizer type 2.
• = amounts of the i-th mineral used.

The model is: maximize

subject to the following constraints:

• Composition of fertilizers (Table 1):

• Mineral characteristics (Table 2):

• Variable bounds:

Step 2. Preparing the Excel Worksheet

Data for solving the problem are placed on the worksheet.

Table. Calculation formulas used in Excel for the fertilizer problem

Description	Cell	Formula
Objective function	D11	=320*SUM(C5:C8)+350*SUM(D5:D8)-40*F5-50*F6-60*F7
Constraint 1	B14	=C5-0.5*SUM(C5:C8)
Constraint 2	B15	=C6-0.6*SUM(C5:C8)
Constraint 3	B16	=D6-0.7*SUM(D5:D8)
Constraint 4	B17	=0.4*SUM(D5:D8)-D6
Constraint 5	B18	=0.2*SUM(D5:D8)-D7
Constraint 6	B19	=D8-0.8*SUM(D5:D8)
Constraint 7	B20	=SUM(C5:D5)-0.3*$F$5-0.2*$F$6-0.15*$F$7
Constraint 8	B21	=SUM(C6:D6)-0.2*$F$5-0.3*$F$6-0.15*$F$7
Constraint 9	B22	=SUM(C7:D7)-0.15*$F$5-0.1*$F$6-0.4*$F$7
Constraint 10	B23	=SUM(C8:D8)-0.35*$F$5-0.4*$F$6-0.3*$F$7

Step 3. Entering Data in the Solver Parameters Window

Fill in the Solver Parameters window as shown:

Do not forget to adjust the required Solver Options.

Step 4. Solver Results

The solution to the fertilizer composition problem is shown:

Solver produces:

• Optimal quantities of fertilizers 1 and 2.
• Mineral usage within the stock limits.
• Reports (Answer, Sensitivity, Limits) that describe the structure and robustness of the solution.

Let us consider an example related to the production of materials. Suppose a company produces two types of construction materials: A and B. Both products are sold on the market.

To manufacture these materials, two raw products are used: I and II. The maximum daily available stock of these raw products is 7 and 9 tons respectively. The consumption of raw products I and II per 1 ton of each type of material is shown in Table.

Table. Consumption of raw products

Raw product	Consumption per 1 ton of materials, t	Maximum available stock, t
	Material A	Material B
I	3	2
II	2	3

Market research showed that the daily demand for material B never exceeds the demand for material A by more than 1 ton. In addition, the demand for material A never exceeds 3 tons per day. The wholesale prices per ton are: 4000 u.c. for material B and 3000 u.c. for material A.

Question: What quantity of each material should the factory produce to maximize revenue?

Step 1. Formulating the Mathematical Model

• Decision variables:
  • x₁ – daily production of material A (tons)
  • x₂ – daily production of material B (tons)
• Objective function (optimization criterion):
  The total daily profit from producing x₁ tons of A and x₂ tons of B is:

F=4000x₂+3000x₁

The goal is to maximize this function:

Maximize F=4000x₂+3000×1

• Constraints:
• Non-negativity:

x₁≥0,x₂≥0

• Raw material usage:

3x₁+2x₂≤7

• Market demand:

x₂−x₁≤1,x₁≤3

Thus, the full mathematical model is:

Maximize F=4000x₂+3000×1

subject to:

2x₂+3x₁≤1

3x₂+2x₁≤1

Step 2. Preparing the Excel Worksheet

On the worksheet, enter the required text, data, and formulas as shown in Fig. 9.6.

• The variables x₁ and x₂ are located in cells C3 and C4 respectively.
• The objective function is in cell C6, with the formula:

=4000*C4+3000*C3

• Constraints for the problem are entered in cells C9:D12.

Step 3. Working with the Solver Add-in

Using the Solver command on the Data tab (in the Analysis group), enter the required data for this problem.

• To add constraints, in the Solver Parameters window, under Subject to the Constraints, click Add.
• In the Add Constraint window , enter the first group of constraints:
  • In the Cell Reference field, input the left-hand side (C3:C4).
  • In the Constraint field, input the right-hand side (0).
  • From the dropdown list, select the relation “>=”.
  • This defines the non-negativity requirement for the variables.

Click Add again to enter the second group of constraints: C9:C12 <= D9:D12.
Press OK to complete entry. The Solver Parameters window now displays all the constraints.

• Click Solve to run Solver.
• The Solver Results window will display the solution and provide the option to generate a report.

Step 4. Reports

• Answer Report:
  • Displays the target cell (objective function), the decision variables (x₁, x₂), and the constraints.
  • In the Formula field – the dependencies used in Solver.
  • In the Allowable field – the quantities of raw materials used. If the material is fully consumed, the status is shown as binding; otherwise, not binding.
  • For boundary conditions, the difference between the optimal solution and the set boundary is shown.

• Sensitivity Report:
  • Displays variable values in the solution and the ranges of changes to constraints that preserve the optimal solution.

• Limits Report:
  • Shows the ranges within which the quantities of materials in the optimal solution can vary while keeping the solution structure unchanged.
  • Displays lower and upper bounds of the variables and the corresponding objective function values.

Building a Mathematical Model of the Problem

Work on solving any optimization problem always begins with building a mathematical model, which requires answering the following questions:

• What are the variables of the model (i.e., which quantities is the model built to determine)?
• What is the goal, for which the optimal values are chosen from among all admissible values of the variables?
• What constraints must the unknowns satisfy?

It should be noted that when constructing a model, formulating the constraints is the most critical part. In some cases, constraints are obvious (e.g., a raw material limitation). Other constraints may be less obvious and could be defined incorrectly. For example:

• In a multi-period model, the value of a material resource at the beginning of the next period must equal its value at the end of the previous period.
• In a supply model, the stock at the beginning of a period plus the quantity received must equal the stock at the end of the period plus the quantity shipped.
• Many quantities, by their physical meaning, cannot be negative (e.g., the number of units received).

At this stage, conclusions are drawn about:

• the source data (deterministic or random),
• the decision variables (continuous or discrete),
• the ranges within which the variables can lie,
• the dependencies between variables (linear or nonlinear),
• and the criteria by which the optimal solution should be found.

This also includes handling inconsistency and unboundedness of the objective function:

• For maximization, the feasible region must be bounded from above.
• For minimization, it must be bounded from below.

Preparing the Excel Worksheet for Optimization

It is recommended to:

• Correctly arrange all source data on the worksheet.
• Properly enter the formulas for the objective function and other relationships.
• Reserve a place for the variable values.

Solving the Problem with the Solver Add-in

All constraints, variables, objective function, and other values should be correctly entered into the Solver Parameters window.

Most optimization problems are linear programming problems, where both the objective function and the constraints are linear. In this case, you must enable the Assume Linear Model option in the Solver Parameters window. This ensures the use of the Simplex method. Otherwise, even for linear problems, Solver will use more general (and slower) methods.

Solver can also handle nonlinear dependencies and constraints, such as nonlinear programming problems or solving systems of nonlinear equations. For Solver to work effectively, dependencies should be smooth or at least continuous. Discontinuous dependencies most often arise when using the IF() function with variable arguments. Problems may also occur when using functions like ABS(), ROUND(), etc.

In the case of nonlinear dependencies, it is advisable to:

• Provide initial guesses for the decision variables (sometimes graphical analysis can give approximate solutions).
• In the Solver Options window, disable the Assume Linear Model option (if enabled).

For integer programming problems, remember the requirements of integrality and Boolean conditions.

Analyzing the Optimization Solution

If necessary, analysis of the solution can be carried out. Often, the solution is also presented in the form of charts or graphs. Solver can also generate a Solver Report.

There are three types of reports:

1. Answer Report – contains the final values of the objective function and constraints.
2. Sensitivity Report – shows the results of small changes in Solver parameters.
3. Limits Report – demonstrates the effect of sequentially maximizing and minimizing each variable while holding the others constant.

The type of report is selected at the end of the solution process in the Solver Results window . Multiple reports (two or all three) can be generated simultaneously.

The Solver add-in is launched, as previously mentioned, by the corresponding command in the Analysis group on the Data tab of the ribbon.

The appearance of the Solver Parameters window and its options are shown in Figures and in Table.

By clicking the Options button (in the Solver Parameters window), the Options dialog box opens, whose characteristics are described in Table.

Table. Options of the Solver Parameters window

Name	Description
Set Objective	Specifies the cell containing the objective function (optimization criterion) of the task under consideration.
To	Select one of three options (Max, Min, Value Of) to determine the type of relationship between the solution and the target cell.
By Changing Variable Cells	Specifies the cells that should change during the solving process (i.e., the decision variables).
Subject to the Constraints	Displays the constraints imposed on the variables. Constraints may take the form of equalities, inequalities, integer requirements, or binary values (0 or 1). To add, edit, or delete a constraint, use the respective Add, Change, or Delete buttons. Constraints are added one at a time and displayed in the Add Constraint window (Fig. 9.3), opened by clicking Add. In the Cell Reference field, the left-hand side of the constraint is entered; in the Constraint field, the right-hand side. The dropdown menu specifies the relationship type: >=, <=, =, int, bin, or dif (different). – int requires integer values only; bin requires binary values (0 or 1); dif requires all values to be distinct. Pressing Add allows entry of the next constraint. Pressing OK completes constraint entry and returns to the Solver Parameters window with all data filled in.
Make Unconstrained Variables Non-Negative	Sets the requirement that variables must be non-negative.
Select a Solving Method	Allows the selection of an optimization algorithm used by Solver: GRG Nonlinear, Simplex LP, or Evolutionary. A note under the list provides guidance on the use of each method.
Reset All	Restores Solver Parameters to their initial state, clearing all settings.
Load/Save	Allows saving or loading of Solver configurations.
Options	Allows modification of solving conditions and options. Default values are suitable for most problems.
Solve	Starts the solution process with the current parameters. Upon completion, the Solver Results dialog box will appear.

Table. Options of the Options window

Tab: All Methods

Name	Description
Constraint Precision	Sets the required precision with which the solution must satisfy constraints. A constraint is considered satisfied if the difference between the cell value and the constraint value does not exceed the specified number. The smaller the number, the higher the precision.
Use Automatic Scaling	Enables automatic normalization of input and output values that differ greatly in magnitude (e.g., maximizing return percentage relative to investments measured in millions).
Show Iteration Results	Pauses the solution process to display intermediate iterations for inspection.

Group: Integer Constraints

• Ignore Integer Constraints and Integer Optimality (%).
• The default value of Integer Optimality (%) is 1%. Set to 0% for the most accurate solution to integer or binary problems.
• Note: For integer constraint problems, it is recommended to re-run Solver after finding an initial solution with default settings, using greater precision and smaller tolerance, then compare with the original solution.

Group: Solution Limits

• Max Time (seconds): limits the time allocated for solving.
• Iterations: limits the number of intermediate computations.
• Evolutionary and Integer Limits (for evolutionary and integer-constrained problems):
  • Max Subproblems: sets the maximum number of subproblems to process.
  • Max Feasible Solutions: sets the maximum number of feasible solutions to consider.

Note: If the solution process reaches any maximum (time, iterations, subproblems, or feasible solutions), Solver will return the best solution found and display it in the Solver Results window.

Tab: GRG Nonlinear

Name	Description
Convergence	Sets the tolerance for acceptable deviation from the optimal solution.
Derivatives Group	Allows selection of the numerical differentiation method. Choosing Central Derivatives produces more accurate results but significantly increases computation time.
Multi-Start Group	Used for sequential searches of optimal solutions. Enabling Use Multi-Start processes several starting points. – Population Size: sets the number of solution attempts (minimum 10, maximum 200). – Random Seed: specifies an initial positive value for the random number generator. Different seeds yield different final results. Leaving the field empty uses a new random number each run. – Require Bounds on Variables: upper and lower bounds for variables must be defined.

Tab: Evolutionary

Name	Description
Convergence	Sets the tolerance for acceptable deviation from the optimal solution.
Mutation Rate	A number between 0 and 1 indicating the relative frequency of changes in the population of solutions.
Population Size	Sets the number of solutions (minimum 10, maximum 200).
Random Seed	Specifies a starting random number seed.
Maximum Time Without Improvement	Sets the maximum seconds allowed without significant improvement in the solution.
Require Bounds on Variables	Requires definition of upper and lower bounds for variables in the constraints list.

 

Let us now consider various examples of using the Solver add-in. Usually, Solver can be found on the Data tab of the ribbon in the Analysis group. If this command is missing from the specified location, perform the following steps: go to the File tab of the ribbon and select Options. In the Excel Options window that appears, select Add-ins on the left, and on the right under the Manage group choose Excel Add-ins from the list and click Go. Next, in the Add-ins window, in the list of available add-ins, check the box in front of Solver Add-in and click OK.

General Formulation of an Optimization Problem

An optimization problem in its general form can be stated as shown in Table 9.1.

Table. General formulation of an optimization problem

№	Name	Mathematical notation	Description
1	Objective function (optimization criterion)	max(min,const) f(x₁,…,xⱼ,…,xₙ)	Indicates in what sense the solution should be optimal, i.e., the best. Three types of objective functions are possible: maximization, minimization, or assigning a specific value.

 

2	Constraints	gᵢ(xⱼ) ≤ bᵢ, i = 1,…,m; j = 1,…,n xⱼ ∈ ℤ, j = 1,…,k (for integer programming problems). xⱼ ∈ {0,1}, j = 1,…,k (for problems with Boolean variables).	Establish dependencies between variables. Constraints may be one-sided or two-sided. A two-sided constraint is written as two one-sided constraints.
3	Boundary conditions	dⱼ ≤ xⱼ ≤ Dⱼ, j = 1,…,n	Show the limits within which the values of the sought variables in the optimal solution may lie.

A solution of tasks (1)—(3) that satisfies all constraints and boundary conditions is called a feasible solution.

An important characteristic of an optimization problem is its dimension, determined by the number of variables n and the number of constraints m.

• If n < m, the problem has no solutions.
• A necessary requirement for optimization problems is the condition n > m.
• A system of equations where n = m is considered as an optimization problem having a single feasible solution (it can be solved as a standard optimization problem by designating any variable as the objective function).

Thus, a problem has an optimal solution if it meets two requirements:

• There is more than one solution, i.e., feasible solutions exist.
• There is a criterion that shows in what sense the accepted solution should be optimal, i.e., the best among the feasible ones.