August 27, 2017 at 14:20Solving the direct and dual linear programming problems with Python
Introduction
It should be noted that the methods for solving linear programming problems do not relate to economics, but to mathematics and computer engineering. At the same time, the economist needs to ensure the most comfortable conditions for dialogue with the appropriate software. In turn, such conditions can be provided only by dynamically developing and interactive development environments that have in their arsenal a set of libraries necessary for solving such problems. One of what software development environments is certainly Python.
Formulation of the problem
In publications [1,2], solutions to direct optimization problems were considered by the linear programming method and a reasonable choice of the scipy solver was proposed. optimize.
However, it is known [3] that each linear programming problem corresponds to a so-called distinguished (dual) problem. Compared to the direct task, in it, rows turn 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 problem is the original task itself.
The solution of the dual problem is very important for the analysis of resource use. In this publication, it will be proved that the optimal values of the objective functions in the original and dual problems coincide (i.e., the maximum in the original problem coincides with the minimum in the dual).
The optimal values of the cost of material and labor will be evaluated by their contribution to the objective function. As a result, “objectively determined estimates” of raw materials and labor will be obtained that do not coincide with market prices.
Solving the direct problem of the optimal production program
Given the high level of mathematical preparation of the vast majority of users of this resource, I will not give balance equations with upper and lower restrictions and the introduction of additional variables for the equalities. Therefore, I will immediately give the notation of the variables used in the solution:
N - the number of types of manufactured products;
m– the number of types of raw materials used;
b_ub is a vector of available resources of dimension m;
A_ub is a matrix of dimension m × N, each element of which is a resource consumption of type i for the production of a unit of product of type j;
c is the profit vector from the production of a unit of a product of each type;
x - the required volumes of manufactured products of each type (optimal production plan) providing maximum profit.
Target function
maxF (x) = c × x
Constraints
A × x≤b
Numerical values of variables:
N = 5; m is 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 step 1
3. Find the remaining resources (if any) when performing
step 1 Features of the solution with the scipy library. optimize
To determine the maximum (by default the minimum is determined, the coefficients of the objective function should be written with a negative sign c = [-25, -35, -25, -40, -30] and ignore the minus sign before profit. The
notation used in the output of the results:
x- an array of values of variables that deliver a minimum (maximum) of the objective function;
slack - values of additional variables. Each variable corresponds to an inequality constraint. The zero value of the variable means that the corresponding restriction is active;
success - True, if the function managed to find the optimal solution;
status - solution status:
0 - the search for the optimal solution was successful;
1 - the limit on the number of iterations is reached;
2 - the problem has no solutions;
3 - the objective function is not limited.
nit is the number of iterations performed.
Listing a solution to a direct optimization problem
#!/usr/bin/python
# -*- coding: utf-8 -*-
import scipy
from scipy.optimize import linprog # загрузка библиотеки ЛП
c = [-25, -35,-25,-40,-30] # список коэффициентов функции цели
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]]
d=linprog(c, A_ub, b_ub) # поиск решения
for key,val in d.items():
print(key,val) # вывод решения
if key=='x':
q=[sum(i) for i in A_ub*val]#использованные ресурсы
print('A_ub*x',q)
q1= scipy.array(b_ub)-scipy.array(q) #остатки ресурсов
print('b_ub-A_ub*x', q1)
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]
Conclusions
- The optimal plan for the types of products was found [0.0 0. 0 18.182 22.727 150. 0]
- Found actual use of resources [700.0, 250.0, 600.0, 309.091]
- The remainder of the unused fourth type of resource was found [0. 0 0.0 0.0 90.909]
- There is no need for calculations according to claim 3, since the same result should be output in the slack variable
The solution of the dual problem of the 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 in comparison with the resources limiting the production output, and the enterprise is ready to pay a higher price for the acquisition of resources that allow increasing profits.
We introduce a new assignment of the desired variable x as some “shadow” price that determines the value of this resource in relation to profit from sales of manufactured products.
Further, for comparative analysis, we partially preserve the previously accepted notation, but with a new content:
c - vector of available resources;
b_ub - profit vector from the production of a unit of a product of each type;
A_ub_T– the transposed matrix A_ub.
Target function
minF (x) = c × x
Limitations
A_ub_T × x≥ b_ub
Numerical values and relations 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 producer of each type of resource.
Features of the solution with the scipy library. optimize
To replace restrictions from above with restrictions from the bottom, it is necessary to multiply both parts of the restriction by A minus one - 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).
Listing of the solution to the dual optimization problem
#!/usr/bin/python
# -*- coding: utf-8 -*-
import scipy
from scipy.optimize import linprog
A_ub = [[1,2,3,2,4],
[5,4,3,2,1],
[3,4,2,5,3],
[4,2,5,3,1]]
c=[700,250,600,400]
b_ub = [-25, -35,-25,-40,-30]
A_ub_T =-scipy.transpose(A_ub)
d=linprog(c, A_ub_T, b_ub)
for key,val in d.items():
print(key,val)
Problem Solving Results
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
conclusions
The third type of resources is of the greatest value to the manufacturer; therefore, this type of resources should be purchased first, then the first and second types. The fourth type of resource has zero value for the manufacturer and is purchased last.
Comparison of direct and dual problems
- The dual task extends the possibilities of product planning, but by scipy. optimize is solved for twice as much as the direct number of iterations.
- The slack variable displays information about the activity of constraints in the form of inequalities, which can be used, for example, to analyze residual raw materials.
- The direct problem is the task of maximization, and the dual is the task of minimization, and vice versa.
- The coefficients of the objective function in the direct problem are constraints in the dual problem.
- Constraints in the direct problem become coefficients of the objective function in the dual.
- The signs of inequalities in the restrictions are reversed.
- The matrix of the system of equalities is transposed.
References
