Решение комбинаторных задач и оптимизация в Python: готовые методы

def generate_combinations(elements, k):
if k == 0:
return [[]]

if not elements:
return []

head = elements[0]
rest = elements[1:]

combinations_without_head = generate_combinations(rest, k)
combinations_with_head = [[head] + combo for combo in generate_combinations(rest, k-1)]

return combinations_without_head + combinations_with_head

# Пример использования
result = generate_combinations([1, 2, 3, 4], 2)
print(result) # [[2, 3], [2, 4], [3, 4], [1, 3], [1, 4], [1, 2]]

import itertools

# Генерация комбинаций
colors = ['красный', 'синий', 'зеленый', 'желтый']
for combo in itertools.combinations(colors, 2):
print(f"Комбинация цветов: {combo[0]} и {combo[1]}")

# Генерация перестановок
digits = [1, 2, 3]
for perm in itertools.permutations(digits):
print(f"Перестановка: {perm}")

# Комбинации с повторениями
dice_rolls = list(itertools.combinations_with_replacement(range(1, 7), 2))
print(f"Возможные броски двух костей (с учетом одинаковых значений): {len(dice_rolls)}")

# Декартово произведение
sizes = ['S', 'M', 'L']
colors = ['черный', 'белый']
for item in itertools.product(sizes, colors):
print(f"Вариант товара: размер {item[0]}, цвет {item[1]}")

import itertools

def find_optimal_subset(items, max_weight, value_key='value', weight_key='weight'):
"""
Находит подмножество элементов с максимальной суммарной ценностью
при ограничении по весу (упрощенная задача о рюкзаке)
"""
best_value = 0
best_combination = None

# Перебираем все возможные комбинации элементов
for i in range(1, len(items) + 1):
for combo in itertools.combinations(items, i):
total_weight = sum(item[weight_key] for item in combo)
total_value = sum(item[value_key] for item in combo)

if total_weight <= max_weight and total_value > best_value:
best_value = total_value
best_combination = combo

return best_combination, best_value

# Пример использования
items = [
{'name': 'Ноутбук', 'weight': 3, 'value': 2000},
{'name': 'Смартфон', 'weight': 1, 'value': 800},
{'name': 'Камера', 'weight': 2, 'value': 1000},
{'name': 'Наушники', 'weight': 0.5, 'value': 300},
{'name': 'Планшет', 'weight': 1.5, 'value': 1200}
]

result, value = find_optimal_subset(items, 5)
print(f"Оптимальный набор вещей (ценность: {value}):")
for item in result:
print(f"- {item['name']}: {item['weight']} кг, {item['value']} у.е.")

import numpy as np
from scipy import optimize
import matplotlib.pyplot as plt

# Определение функции для минимизации
def objective_function(x):
return x[0]**2 + x[1]**2 – x[0]*x[1] + x[1] + 1

# Минимизация функции без ограничений
initial_guess = [0, 0]
result = optimize.minimize(objective_function, initial_guess, method='BFGS')

print(f"Минимум найден в точке: {result.x}")
print(f"Минимальное значение функции: {result.fun}")
print(f"Успешность оптимизации: {result.success}")
print(f"Количество итераций: {result.nit}")

# Минимизация с ограничениями
def constraint1(x):
return x[0] + x[1] – 2 # x[0] + x[1] >= 2

def constraint2(x):
return 10 – x[0] – 3*x[1] # x[0] + 3*x[1] <= 10

constraints = [
{'type': 'ineq', 'fun': constraint1},
{'type': 'ineq', 'fun': constraint2}
]

bounds = ((0, None), (0, None)) # x[0] >= 0, x[1] >= 0

result_constrained = optimize.minimize(
objective_function, 
initial_guess, 
method='SLSQP', 
bounds=bounds,
constraints=constraints
)

print(f"\nС ограничениями:")
print(f"Минимум найден в точке: {result_constrained.x}")
print(f"Минимальное значение функции: {result_constrained.fun}")

from scipy.optimize import curve_fit

# Генерируем тестовые данные с шумом
def true_model(x, a, b, c):
return a * np.exp(-b * x) + c

x_data = np.linspace(0, 4, 50)
y_true = true_model(x_data, 2.5, 1.3, 0.5)
y_noise = 0.2 * np.random.normal(size=x_data.size)
y_data = y_true + y_noise

# Аппроксимация данных моделью
params, params_covariance = curve_fit(true_model, x_data, y_data)

print(f"Найденные параметры: a={params[0]:.2f}, b={params[1]:.2f}, c={params[2]:.2f}")
print(f"Стандартные отклонения параметров: {np.sqrt(np.diag(params_covariance))}")

# Визуализация результатов
plt.figure(figsize=(10, 6))
plt.scatter(x_data, y_data, label='Экспериментальные данные')
plt.plot(x_data, true_model(x_data, *params), 'r-', label='Подобранная модель')
plt.legend()
plt.xlabel('x')
plt.ylabel('y')
plt.title('Подгонка экспоненциальной модели')
plt.grid(True)
plt.savefig('curve_fit.png')

from scipy.optimize import differential_evolution, dual_annealing, shgo

# Функция с множеством локальных минимумов
def multimodal_function(x):
return np.sin(5 * x[0]) * np.cos(5 * x[1]) * np.exp(-x[0]**2 – x[1]**2)

bounds = [(-2, 2), (-2, 2)]

# Дифференциальная эволюция (генетический алгоритм)
result_de = differential_evolution(multimodal_function, bounds)
print(f"\nДифференциальная эволюция:")
print(f"Глобальный минимум: {result_de.x}")
print(f"Значение функции: {result_de.fun}")

# Имитация отжига
result_da = dual_annealing(multimodal_function, bounds)
print(f"\nИмитация отжига:")
print(f"Глобальный минимум: {result_da.x}")
print(f"Значение функции: {result_da.fun}")

# SHGO (Simplicial Homology Global Optimization)
result_shgo = shgo(multimodal_function, bounds)
print(f"\nSHGO:")
print(f"Глобальный минимум: {result_shgo.x}")
print(f"Значение функции: {result_shgo.fun}")

# Решение транспортной задачи с использованием PuLP
from pulp import LpMaximize, LpMinimize, LpProblem, LpStatus, LpVariable, lpSum, value

# Создание модели
model = LpProblem(name="transport-problem", sense=LpMinimize)

# Данные задачи
supply_points = ['Завод1', 'Завод2']
demand_points = ['Магазин1', 'Магазин2', 'Магазин3']

# Стоимость перевозки единицы продукции
costs = {
('Завод1', 'Магазин1'): 10,
('Завод1', 'Магазин2'): 7,
('Завод1', 'Магазин3'): 14,
('Завод2', 'Магазин1'): 8,
('Завод2', 'Магазин2'): 12,
('Завод2', 'Магазин3'): 9
}

# Предложение на заводах
supply = {
'Завод1': 120,
'Завод2': 80
}

# Спрос в магазинах
demand = {
'Магазин1': 70,
'Магазин2': 50,
'Магазин3': 80
}

# Переменные решения: сколько единиц продукции перевозить по каждому маршруту
vars = {(i, j): LpVariable(name=f'route_{i}_{j}', lowBound=0, cat='Integer')
for i in supply_points for j in demand_points}

# Целевая функция: минимизировать общую стоимость транспортировки
model += lpSum([costs[i, j] * vars[i, j] for i, j in vars]), "Общая стоимость транспортировки"

# Ограничения по предложению
for i in supply_points:
model += lpSum([vars[i, j] for j in demand_points]) <= supply[i], f"Предложение_{i}"

# Ограничения по спросу
for j in demand_points:
model += lpSum([vars[i, j] for i in supply_points]) >= demand[j], f"Спрос_{j}"

# Решение модели
model.solve()

# Вывод результатов
print(f"Статус: {LpStatus[model.status]}")
print(f"Общая минимальная стоимость: {value(model.objective)}")
print("\nОптимальный план перевозок:")
for i, j in vars:
if value(vars[i, j]) > 0:
print(f"Из {i} в {j}: {int(value(vars[i, j]))} единиц")

# Решение транспортной задачи с использованием Pyomo
import pyomo.environ as pyo

# Данные задачи (те же, что и выше)
supply_points = ['Завод1', 'Завод2']
demand_points = ['Магазин1', 'Магазин2', 'Магазин3']

costs = {
('Завод1', 'Магазин1'): 10,
('Завод1', 'Магазин2'): 7,
('Завод1', 'Магазин3'): 14,
('Завод2', 'Магазин1'): 8,
('Завод2', 'Магазин2'): 12,
('Завод2', 'Магазин3'): 9
}

supply = {
'Завод1': 120,
'Завод2': 80
}

demand = {
'Магазин1': 70,
'Магазин2': 50,
'Магазин3': 80
}

# Создание модели
model = pyo.ConcreteModel()

# Определение наборов
model.supply_points = pyo.Set(initialize=supply_points)
model.demand_points = pyo.Set(initialize=demand_points)
model.routes = pyo.Set(initialize=costs.keys(), dimen=2)

# Определение параметров
model.costs = pyo.Param(model.routes, initialize=costs)
model.supply = pyo.Param(model.supply_points, initialize=supply)
model.demand = pyo.Param(model.demand_points, initialize=demand)

# Определение переменных
model.shipments = pyo.Var(model.routes, domain=pyo.NonNegativeIntegers)

# Целевая функция
def objective_rule(model):
return sum(model.costs[i, j] * model.shipments[i, j] for i, j in model.routes)
model.objective = pyo.Objective(rule=objective_rule, sense=pyo.minimize)

# Ограничения по предложению
def supply_rule(model, i):
return sum(model.shipments[i, j] for j in model.demand_points if (i, j) in model.routes) <= model.supply[i]
model.supply_constraint = pyo.Constraint(model.supply_points, rule=supply_rule)

# Ограничения по спросу
def demand_rule(model, j):
return sum(model.shipments[i, j] for i in model.supply_points if (i, j) in model.routes) >= model.demand[j]
model.demand_constraint = pyo.Constraint(model.demand_points, rule=demand_rule)

# Решение модели
solver = pyo.SolverFactory('glpk')
results = solver.solve(model)

# Вывод результатов
print(f"Статус: {results.solver.termination_condition}")
print(f"Общая минимальная стоимость: {pyo.value(model.objective)}")
print("\nОптимальный план перевозок:")
for i, j in model.routes:
if pyo.value(model.shipments[i, j]) > 0:
print(f"Из {i} в {j}: {int(pyo.value(model.shipments[i, j]))} единиц")

# Пример задачи нелинейного программирования в Pyomo
model = pyo.ConcreteModel()

# Переменные
model.x = pyo.Var(domain=pyo.NonNegativeReals)
model.y = pyo.Var(domain=pyo.NonNegativeReals)

# Целевая функция (нелинейная)
model.objective = pyo.Objective(
expr=model.x**2 + model.y**2,
sense=pyo.minimize
)

# Ограничения
model.constraint1 = pyo.Constraint(
expr=model.x + model.y >= 10
)
model.constraint2 = pyo.Constraint(
expr=model.x * model.y >= 25
)

# Решение с использованием нелинейного солвера
solver = pyo.SolverFactory('ipopt')
results = solver.solve(model)

print(f"x = {pyo.value(model.x):.2f}, y = {pyo.value(model.y):.2f}")
print(f"Минимальное значение: {pyo.value(model.objective):.2f}")

import numpy as np
from python_tsp.heuristics import solve_tsp_simulated_annealing

# Создание матрицы расстояний между городами (в км)
distances = np.array([
[0, 12, 25, 33, 41],
[12, 0, 18, 27, 39],
[25, 18, 0, 16, 23],
[33, 27, 16, 0, 14],
[41, 39, 23, 14, 0]
])

# Решение задачи коммивояжера с использованием метода имитации отжига
permutation, distance = solve_tsp_simulated_annealing(distances)

print(f"Оптимальный маршрут: {permutation}")
print(f"Общее расстояние: {distance} км")

# Восстановление полного маршрута (возвращение в начальную точку)
full_route = permutation + [permutation[0]]
print(f"Полный маршрут: {full_route}")

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def create_data_model():
"""Создает данные для задачи."""
data = {}
data['distance_matrix'] = [
[0, 12, 25, 33, 41],
[12, 0, 18, 27, 39],
[25, 18, 0, 16, 23],
[33, 27, 16, 0, 14],
[41, 39, 23, 14, 0]
]
data['num_vehicles'] = 2
data['depot'] = 0
return data

def solve_vrp():
"""Решает задачу маршрутизации транспортных средств."""
data = create_data_model()

# Создаем менеджер маршрутизации
manager = pywrapcp.RoutingIndexManager(
len(data['distance_matrix']),
data['num_vehicles'],
data['depot'])

# Создаем модель маршрутизации
routing = pywrapcp.RoutingModel(manager)

# Регистрируем функцию расстояния
def distance_callback(from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Настраиваем параметры поиска
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# Решаем задачу
solution = routing.SolveWithParameters(search_parameters)

# Выводим решение
if solution:
print_solution(data, manager, routing, solution)

def print_solution(data, manager, routing, solution):
"""Выводит решение задачи маршрутизации."""
total_distance = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = f'Маршрут для автомобиля {vehicle_id}:\n'
route_distance = 0
while not routing.IsEnd(index):
plan_output += f' {manager.IndexToNode(index)} ->'
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
plan_output += f' {manager.IndexToNode(index)}\n'
plan_output += f'Расстояние: {route_distance} км\n'
print(plan_output)
total_distance += route_distance
print(f'Общее расстояние для всех автомобилей: {total_distance} км')

solve_vrp()

import pandas as pd
import numpy as np
from pypfopt import EfficientFrontier
from pypfopt import risk_models
from pypfopt import expected_returns

# Загрузка исторических данных о ценах акций
# В реальном сценарии эти данные загружались бы из CSV или API
# Здесь мы используем синтетические данные для примера
np.random.seed(42)
stocks = ['AAPL', 'MSFT', 'AMZN', 'GOOGL', 'FB']
data = {}

for stock in stocks:
# Генерируем случайные цены с трендом для демонстрации
prices = [100]
for _ in range(251): # ~1 год торговых дней
change = np.random.normal(0.0005, 0.015) # Среднее изменение и волатильность
prices.append(prices[-1] * (1 + change))
data[stock] = prices

# Создаем DataFrame с ценами
df = pd.DataFrame(data)
df.index = pd.date_range(start='2020-01-01', periods=len(df), freq='B')

# Расчет ожидаемой доходности и ковариационной матрицы
mu = expected_returns.mean_historical_return(df)
S = risk_models.sample_cov(df)

# Оптимизация портфеля для максимального соотношения Шарпа
ef = EfficientFrontier(mu, S)
weights = ef.max_sharpe()
cleaned_weights = ef.clean_weights()

print("Оптимальные веса для максимального соотношения Шарпа:")
for stock, weight in cleaned_weights.items():
print(f"{stock}: {weight:.4f}")

# Получение информации о портфеле
expected_return, annual_volatility, sharpe_ratio = ef.portfolio_performance()
print(f"Ожидаемая годовая доходность: {expected_return:.2%}")
print(f"Годовая волатильность: {annual_volatility:.2%}")
print(f"Коэффициент Шарпа: {sharpe_ratio:.2f}")

import random
import numpy as np
from deap import base, creator, tools, algorithms

# Определение задачи: найти минимум функции Растригина
def rastrigin(x):
return 10 * len(x) + sum(xi**2 – 10 * np.cos(2 * np.pi * xi) for xi in x)

# Настройка DEAP для минимизации
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)

# Инициализация инструментов
toolbox = base.Toolbox()
toolbox.register("attr_float", random.uniform, -5.12, 5.12)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_float, n=2)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# Определение операторов генетического алгоритма
toolbox.register("evaluate", rastrigin)
toolbox.register("mate", tools.cxBlend, alpha=0.5)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.2)
toolbox.register("select", tools.selTournament, tournsize=3)

def run_ga():
# Параметры алгоритма
pop_size = 100
cx_pb = 0.7
mut_pb = 0.2
n_gen = 50

# Инициализация популяции
pop = toolbox.population(n=pop_size)
hof = tools.HallOfFame(1)
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("avg", np.mean)
stats.register("min", np.min)

# Запуск генетического алгоритма
pop, log = algorithms.eaSimple(pop, toolbox, cxpb=cx_pb, mutpb=mut_pb, ngen=n_gen, 
stats=stats, halloffame=hof, verbose=True)

# Вывод результата
best = hof[0]
print(f"Наилучшее найденное решение: {best}")
print(f"Минимальное значение функции Растригина: {rastrigin(best)}")

return best, log

run_ga()

from pulp import LpMaximize, LpProblem, LpVariable

# Создаем модель максимизации прибыли
model = LpProblem(name="production-planning", sense=LpMaximize)

# Определяем переменные: сколько единиц каждого продукта производить
x1 = LpVariable(name="product_A", lowBound=0) # Количество продукта A
x2 = LpVariable(name="product_B", lowBound=0) # Количество продукта B

# Прибыль на единицу продукта
profit_A = 200 # у.е. за единицу A
profit_B = 300 # у.е. за единицу B

# Целевая функция: максимизировать общую прибыль
model += profit_A * x1 + profit_B * x2, "Total Profit"

# Ограничения ресурсов
# Время на машине 1 (часов в неделю)
model += 2 * x1 + 1 * x2 <= 100, "Machine_1_Time"
# Время на машине 2 (часов в неделю)
model += 1 * x1 + 3 * x2 <= 90, "Machine_2_Time"
# Доступное сырье (кг в неделю)
model += 5 * x1 + 4 * x2 <= 450, "Raw_Material"

# Решаем модель
model.solve()

# Выводим результаты
print(f"Статус: {model.status}, {LpStatus[model.status]}")
print(f"Оптимальное количество продукта A: {x1.value()}")
print(f"Оптимальное количество продукта B: {x2.value()}")
print(f"Максимальная прибыль: {model.objective.value()} у.е.")