Solving the direct and dual problems of linear programming with Python

Introduction

It should be noted that the methods of solving linear programming problems are not related to economics, but to mathematics and computer engineering. At the same time, the economist needs to provide the most comfortable conditions for dialogue with the appropriate software. In turn, such conditions can only be provided by dynamically developing and interactive development environments, which have in their arsenal a set of libraries necessary for solving such problems. One of the software development environments is definitely Python.

Formulation of the problem

In publications [1, 2], solutions of direct optimization problems by the linear programming method were considered and a reasonable choice of the scipy solver was proposed. optimize.

However, it is known [3] that for each linear programming problem there corresponds a so-called distinguished (dual) problem. Compared to the direct problem, it transforms rows into columns, inequalities change sign, instead of a maximum, a minimum is sought (or vice versa, instead of a minimum, a maximum). The dual to dual task is the original task itself.
')
Solving the dual problem is very important for analyzing the use of resources. In this publication, it will be proved that the optimal values ​​of the objective functions in the initial and dual problems coincide (that is, the maximum in the initial problem coincides with the minimum in the dual one).

The optimal values ​​of the cost of material and labor will be evaluated according to their contribution to the objective function. As a result, “objectively determined estimates” of raw materials and labor will be obtained, which do not coincide with market prices.

Solution of the direct problem of the optimal production program

Given the high level of mathematical training of the overwhelming majority of users of this resource, I will not give balance equations with upper and lower constraints and an introduction to the transition to equalities of additional variables. Therefore, I will immediately give the notation for the variables used in the solution:
N - the number of types of products;
m is the number of types of raw materials used;
b_ub is the vector of available resources of dimension m;
A_ub is an m × N matrix, each element of which is a consumption of a resource of type i for the production of a unit of a product of type j;
- vector of profit from the production of a unit of a product of each type;
x - the required volume of manufactured products of each type (optimal production plan) ensuring maximum profit.

Goal function
maxF (x) = c × x

Restrictions
A × x≤b

Numerical values ​​of variables:
N = 5; m = 4; b_ub = [700,250,600,400]; A_ub = [[1,2,3,2,4], [5,4,3,2,1], [3,4,2,5,3], [4,2,5,3,1] ]; c = [25, 35,25,40,30].

Tasks
1. Find x for maximum profit.
2. Find the resources used when performing p.1
3. Find the remaining resources (if any) when performing p.1

Solution features with scipy library. optimize
To determine the maximum (by default, the minimum is determined, the coefficients of the objective function must be written down with a negative c = [-25, -35, -25, -40, -30] and ignore the minus sign before the profit.

Used in the display of the results of notation:
x is an array of variable values ​​that deliver a minimum (maximum) of the objective function;
slack - values ​​of additional variables. Each variable corresponds to a constraint-inequality. The zero value of the variable means that the corresponding limit is active;
success - True if the function succeeded in finding the optimal solution;
status - decision status:
0 - the search for the optimal solution was completed successfully;
1 - the limit on the number of iterations is reached;
2 - the problem has no solutions;
3 - the objective function is unlimited.
nit is the number of iterations performed.


The results of solving the problem
nit 3
status 0
message Optimization terminated successfully.
success true
x [0. 0. 18.18181818 22.72727273 150.]
A_ub * x [700.0, 250.0, 600.0, 309.09090909090912]
b_ub-A_ub * x [0. 0. 0. 90.90909091]
fun -5863.63636364
slack [0. 0. 0. 90.90909091]

findings

1. Found the optimal plan for the types of products [0.0 0. 0 18.182 22.727 150. 0]
2. Found the actual use of resources [700.0, 250.0, 600.0, 309.091]
3. Found the remainder of the unused fourth type of resource [0. 0 0.0 0.0 90.909]
4. There is no need for calculations according to claim 3, since the same result is output in the variable slack

Solving the dual problem of an optimal production program

The fourth type of resource in the direct problem is not fully used. Then the value of this resource for the enterprise turns out to be lower compared to the resources that limit output, and the enterprise is ready to pay a higher price for the acquisition of resources that allow for increased profits.

We introduce a new assignment of the desired variable x as a certain “shadow” price, which determines the value of this resource in relation to the profit from the sale of products.

Further, for comparative analysis, we partially save the previously adopted notation, but with a new content:

c is the vector of available resources;
b_ub is the vector of profit from the production unit of a product of each type
A_ub_T– transposed matrix A_ub.

Goal function
minF (x) = c × x

Restrictions
A_ub_T × x≥ b_ub

Numerical values ​​and ratios for variables:
c = [700,250,600,400]; A_ub_T transpose (A_ub); b_ub = [25, 35,25,40,30].

Task:
Find x showing the value for the manufacturer of each type of resource.

Solution features with scipy library. optimize
To replace the top constraints on the bottom constraints, multiply by minus one both parts of the constraint - A_ub_T × x≥ b_ub ... To do this, write the initial data in the form: b_ub = [-25, -35, -25, -40, -30]; A_ub_T = - scipy.transpose (A_ub).


The results of solving the problem
nit 7
message Optimization terminated successfully.
fun 5863.63636364
x [2.27272727 1.81818182 6.36363636 0.]
slack [5.45454545 2.27272727 0. 0. 0.]
status 0
success true

findings

The third type of resources has the greatest value for the manufacturer, therefore this type of resources must be purchased first, then the first and second types. The fourth type of resource has zero value for the manufacturer and is purchased last.

The results of the comparison of the direct and dual problems

1. The dual task expands the possibilities of production planning, but using scipy. optimize is solved in twice the direct number of iterations.
2. The variable slack displays information about the activity of restrictions in the form of inequalities, which can be used, for example, to analyze raw material residues.
3. The direct problem is the maximization problem, and the dual problem is the minimization problem, and vice versa.
4. The coefficients of the goal function in the direct problem are constraints in the dual problem.
5. The constraints in the direct problem become the coefficients of the goal function in the dual.
6. Signs of inequalities in the restrictions are reversed.
7. The matrix of the system of equalities is transposed.

Links

1. Solving a closed transport problem with additional conditions using Python tools.
2. Solving linear programming problems using Python.
3. Duality in linear programming problems.