Варианты по списку
Текущий балл в семестре
LAB #2. Решение задачи о рюкзаке. С ограничениями
Задача о рюкзаке — это классическая проблема комбинаторной оптимизации, где требуется выбрать набор предметов с максимальной ценностью при ограничении по весу.
Основные характеристики задачи:
  • Каждый предмет имеет вес и стоимость
  • Предметы нельзя делить на части
  • Можно брать каждый предмет только один раз
  • Цель — максимизировать общую стоимость при соблюдении весового ограничения
Задача системного анализа
Задача системного анализа: Оптимизация рациона питания
Постановка задачи
Необходимо составить оптимальный рацион питания, удовлетворяющий следующим критериям:
  • Минимизация затрат при заданной максимальной стоимости
  • Соблюдение норм калорийности
  • Соблюдение баланса белков, жиров и углеводов
Исходные данные
Матрица данных о продуктах P = [ci, mi, ki, bi, ji, ui], где:
  • ci — стоимость единицы продукта
  • mi — масса
  • ki — калорийность
  • bi — содержание белков
  • ji — содержание жиров
  • ui — содержание углеводов
Ограничения: html
  • Максимальная стоимость: Cmax = 1500 руб.
  • Калорийность:
    • Kmin = 2000 ккал (минимум)
    • Kmax = 2200 ккал (максимум)
  • Нормы БЖУ:
    • Белки ≥ 30% от калорийности
    • Жиры ≥ 30% от калорийности
    • Углеводы ≤ 40% от калорийности
Математическая модель
Целевая функция: F(x) = ∑i=1n ci · xi → min
Ограничения:
1. По стоимости: ∑i=1n ci · xi ≤ Cmax 2. По калорийности: −∑i=1n ki · xi ≤ −Kmin ∑i=1n ki · xi ≤ Kmax 3. По БЖУ: 4bi · xi − 0.3ki · xi ≥ 0 9ji · xi − 0.3ki · xi ≥ 0 4ui · xi − 0.4ki · xi ≤ 0
Аналитическое решение
Для аналитического решения используем метод линейного программирования. Вводим переменные: xi — количество единиц i-го продукта
Формируем систему неравенств:
{
∑i=1n ci · xi ≤ 1500
−∑i=1n ki · xi ≤ −2000
∑i=1n ki · xi ≤ 2200
4bi · xi − 0.3ki · xi ≥ 0
9ji · xi − 0.3ki · xi ≥ 0
4ui · xi − 0.4ki · xi ≤ 0
}
MATLAB код для оптимизации питания
clear all
close all
% Читаем данные из Excel файла
filename = 'products.xlsx';
sheet = 1;
% Читаем числовые данные
data = readmatrix(filename, "Sheet", sheet, "Range", "A2:I21");
product_names = readcell(filename, "Sheet", sheet, "Range", "B2:B21");
% Распределяем данные
cost = data(:,3);
mass = data(:,4);
calories = data(:,5);
proteins = data(:,6);
fats = data(:,7);
carbs = data(:,8);
% Параметры задачи
max_cost = 9000;
min_calories = 2000;
max_calories = 2200;
% Подготовка для intlinprog
n = length(cost);
f = -cost;
% Создаем матрицу ограничений A
num_constraints = 6;
A = zeros(num_constraints, n);
% Заполняем матрицу A
A(1,:) = cost;
A(2,:) = -calories;
A(3,:) = calories;
A(4,:) = proteins*4 - 0.3*calories;
A(5,:) = fats*9 - 0.3*calories;
A(6,:) = carbs*4 - 0.4*calories;
% Вектор ограничений b
b = zeros(num_constraints, 1);
b(1) = max_cost;
b(2) = -min_calories;
b(3) = max_calories;
b(4) = 0;
b(5) = 0;
b(6) = 0;
% Тип переменных
intcon = [];
% Границы
lb = zeros(1, n);
ub = inf(1, n);
x, fval, exitflag = intlinprog(f,, A, b,,, lb, ub);
% Проверка результатов
if exitflag > 0
% Расчет показателей
total_cost = sum(cost.* x);
total_calories = sum(calories.* x);
total_proteins = sum(proteins.* x);
total_fats = sum(fats.* x);
total_carbs = sum(carbs.* x);
% Защита от деления на ноль
if total_calories == 0
total_calories = 1e-6;
end
% Вывод результатов
fprintf('Оптимальный набор продуктов:\n');
for i = 1:n
if x(i) > 0
fprintf('Продукт %s: %.2f единиц\n', product_names{i}, x(i));
end
end
fprintf('\nРезультаты оптимизации:\n');
fprintf('Общая стоимость: %.2f руб\n', total_cost);
fprintf('Общая калорийность: %.2f кКал\n', total_calories);
fprintf('Белки: %.2f г (%.2f%% от калорийности)\n', total_proteins, total_proteins*4/total_calories*100);
fprintf('Жиры: %.2f г (%.2f%% от калорийности)\n', total_fats, total_fats*9/total_calories*100);
fprintf('Углеводы: %.2f г (%.2f%% от калорийности)\n', total_carbs, total_carbs*4/total_calories*100);
else
fprintf('Решение не найдено!\n');
end
Оптимизация состава армии (Пример другой формализации критериев)

Оптимизация состава армии

Целевая функция

$$\max \sum_{i=1}^{n} E_i \cdot x_i$$

где:

  • $E_i$ — эффективность i-го типа юнита
  • $x_i$ — количество юнитов i-го типа

Система ограничений

Бюджетное ограничение

$$\sum_{i=1}^{n} C_i \cdot x_i \leq B$$

где:

  • $C_i$ — стоимость содержания одного юнита i-го типа
  • $B$ — общий бюджет на содержание армии

Ограничения по численности

$$N_{min} \leq \sum_{i=1}^{n} x_i \leq N_{max}$$

где:

  • $N_{min}$ — минимально необходимая численность
  • $N_{max}$ — максимально допустимая численность

Балансировка сил

$$\sum_{i \in P} x_i \geq \alpha \cdot \sum_{i=1}^{n} x_i$$ (пехота)
$$\sum_{i \in T} x_i \geq \beta \cdot \sum_{i=1}^{n} x_i$$ (танки)
$$\sum_{i \in A} x_i \geq \gamma \cdot \sum_{i=1}^{n} x_i$$ (авиация)

где:

  • $P$ — множество пехотных юнитов
  • $T$ — множество танковых юнитов
  • $A$ — множество авиационных юнитов
  • $\alpha$, $\beta$, $\gamma$ — доли соответствующих типов войск

Технические ограничения

$$\sum_{i=1}^{n} L_i \cdot x_i \leq L_{max}$$

где:

  • $L_i$ — логистическая нагрузка одного юнита
  • $L_{max}$ — максимальная логистическая емкость

Специализационные ограничения

$$\sum_{i \in S} x_i \geq S_{req}$$

где:

  • $S$ — множество специализированных юнитов
  • $S_{req}$ — требуемое количество

Дополнительные параметры

Боевые характеристики

$$\sum_{i=1}^{n} D_i \cdot x_i \geq D_{min}$$ (урон)
$$\sum_{i=1}^{n} Z_i \cdot x_i \geq Z_{min}$$ (защита)
$$\sum_{i=1}^{n} M_i \cdot x_i \geq M_{min}$$ (мобильность)
$$\sum_{i=1}^{n} R_i \cdot x_i \geq R_{min}$$ (дальность действия)

Логистические параметры

$$\sum_{i=1}^{n} F_i \cdot x_i \leq F_{max}$$ (топливо)
$$\sum_{i=1}^{n} P_i \cdot x_i \leq P_{max}$$ (запасные части)
$$\sum_{i=1}^{n} M_i \cdot x_i \leq M_{max}$$ (тех. обслуживание)

Обучающие параметры

$$\sum_{i=1}^{n} T_i \cdot x_i \leq T_{max}$$ (время подготовки)
$$\sum_{i=1}^{n} Q_i \cdot x_i \geq Q_{min}$$ (квалификация персонала)
$$\sum_{i=1}^{n} C_i \cdot x_i \leq C_{max}$$ (сложность эксплуатации)

Территориальные ограничения

$$\sum_{i=1}^{n} S_i \cdot x_i \leq S_{max}$$ (размещение)
$$\sum_{i=1}^{n} B_i \cdot x_i \leq B_{max}$$ (базирование)
$$\sum_{i=1}^{n} O_i \cdot x_i \geq O_{min}$$ (операционные зоны)

Временные факторы

$$\sum_{i=1}^{n} L_i \cdot x_i \geq L_{min}$$ (срок службы)
$$\sum_{i=1}^{n} M_i \cdot x_i \leq M_{max}$$ (моральное устаревание)
$$\sum_{i=1}^{n} R_i \cdot x_i \geq R_{min}$$ (плановая замена)

Заключение

Данная модель оптимизации позволяет:

  • Эффективно распределять ресурсы
  • Поддерживать необходимый баланс сил
  • Учитывать логистические ограничения
  • Обеспечивать требуемые боевые характеристики
  • Планировать развитие вооруженных сил
Задание
  • балл: 0
    описание:
    • на основе собственного набора данных из lab 1( набор данных 20-30 предметов).
    • Экспортировать данные в матлаб или "ручками"
  • балл: 0
    intlinprog
    описание:
    • реализация решения с использование intlinprog, с собственными ограничениями трех новых критериев зависимых от общего целого, не являющегося "аналогом стоимости"
вывод результата расчета с пояснения, обязательно для допуска к защите!
Примеры данных
код products.xls
Made on
Tilda