Двойственные решения

Для задач линейного (LP) и квадратичного (QP) программирования доступно получение двойственных решений.

Внимание

Функционал доступен только для задач без целочисленных переменных и являющихся выпуклыми (convex).

Для получения двойственных решений используется метод SolveResult.get_dual_value() (в Python) и функция GetDualValue() (в C++). В качестве параметра в обоих случаях может передается наименование ограничения result.get_dual_value("constraint") или ссылка на экземпляр класса Constraint.

Пример

Рассмотрим следующую задачу линейного программирования

Maximize
 obj: 3 x1 + 5 x2 

Subject To
c1 : x1 <= 4
c2 : 2 x2 <= 12
c3 : 3 x1 + 2 x2 <= 18

Bounds
End

Реализация с использованием солвера ArhiCloud имеет следующий вид.

Python

import arhiplexpy

# Создание экземпляра модели

model = arhiplexpy.Model()

# Создание переменных

x1 = model.add_variable(0, arhiplexpy.kArhiplexInf, 3, arhiplexpy.variable_type.continuous, 'x1')
x2 = model.add_variable(0, arhiplexpy.kArhiplexInf, 5, arhiplexpy.variable_type.continuous, 'x2')

# Добавление ограничений

model.add_constraint(x1 <= 4, 'c1')
model.add_constraint(2 * x2 <= 12, 'c2')
model.add_constraint(3 * x1 + 2 * x2 <= 18, 'c3')

# Направление оптимизации

model.set_objective_sense(arhiplexpy.objective_sense.maximize)

# Запуск расчёта на ArhiCloud

result = model.solve_remote("mapping.map")

# Вывод решений

print('Objective:', result.get_objective_value())
print('x1:', result.get_variable_value("x1"))
print('x2:', result.get_variable_value("x2"))

print('The dual value of c1:', result.get_dual_value("c1"))
print('The dual value of c2:', result.get_dual_value("c2"))
print('The dual value of c3:', result.get_dual_value("c3"))

Результат решения задачи

Запуск ArhiCloud
Права на использование (c) 2024 Arhitex

Параметры запуска:
presolve : on
problem_type : max
time_limit : 90
abs_gap : 1e-06
gap : 0.0001
primal_feasibility_tolerance : 1e-06
mip_feasibility_tolerance : 1e-06
remote_timeout : 300
Отправка запроса на расчет . . . успешно
UID: 20241022_111823_8378ac
Начало загрузки модели . . . успешно
Ожидание начала расчета .Запуск ArhiPlex 2.0.11.123984
Права на использование (c) 2024 Arhitex
Процессор Intel Xeon Processor (Icelake) [ AVX512, AVX2 ], физических ядер CPU: 10

Параметры запуска:
        multiprocess_max_process_count = 14
        time_limit =    90.00000000

Оригинальная задача LP temp.mps содержит ограничений: 3, переменных: 2 (дробных: 2, бинарных: 0, целых: 0)

Отчет
  Статус                      : Оптимально
  Значение целевой функции    : 36
  Статус решения              : Достижимо
  Время                       : 0.0 с.
  LP итераций                 : 9
Objective: 36.0
x1: 2.0
x2: 6.0
The dual value of c1: 0.0
The dual value of c2: 1.5
The dual value of c3: 1.0