Варианты по списку
Текущий балл в семестре
LAB #2. Решение задачи о рюкзаке. С ограничениями
Задача о рюкзаке — это классическая проблема комбинаторной оптимизации, где требуется выбрать набор предметов с максимальной ценностью при ограничении по весу.
Основные характеристики задачи:
  • Каждый предмет имеет вес и стоимость
  • Предметы нельзя делить на части
  • Можно брать каждый предмет только один раз
  • Цель — максимизировать общую стоимость при соблюдении весового ограничения
Задача системного анализа
Задача системного анализа: Оптимизация рациона питания
Постановка задачи
Необходимо составить оптимальный рацион питания, удовлетворяющий следующим критериям:
  • Минимизация затрат при заданной максимальной стоимости
  • Соблюдение норм калорийности
  • Соблюдение баланса белков, жиров и углеводов
Исходные данные
Матрица данных о продуктах P = [ci, mi, ki, bi, ji, ui], где:
  • ci — стоимость единицы продукта
  • mi — масса
  • ki — калорийность
  • bi — содержание белков
  • ji — содержание жиров
  • ui — содержание углеводов
Ограничения:
  • Максимальная стоимость: Cmax = 1500 руб.
  • Калорийность: Kmin = 2000 ккал, Kmax = 2200 ккал
  • Нормы БЖУ: белки и жиры ≥ 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
}
Пример решения
Пусть у нас есть 3 продукта:
Продукт Стоимость (руб) Калорийность (ккал) Белки (г) Жиры (г) Углеводы (г)
A 100 200 20 10 30
B 150 300 15 25 20
C 80 150 10 5 25
Решение системы ограничений
1. Целевая функция:
F(x) = 100x₁ + 150x₂ + 80x₃ → min
2. Ограничения по стоимости:
100x₁ + 150x₂ + 80x₃ ≤ 1500
3. Ограничения по калорийности:
−200x₁ − 300x₂ − 150x₃ ≤ −2000
200x₁ + 300x₂ + 150x₃ ≤ 2200
4. Ограничения по БЖУ: Для белков:
4 · 20x₁ − 0.3 · 200x₁ ≥ 0
4 · 15x₂ − 0.3 · 300x₂ ≥ 0
4 · 10x₃ − 0.3 · 150x₃ ≥ 0
Для жиров:
9 · 10x₁ − 0.3 · 200x₁ ≥ 0
9 · 25x₂ − 0.3 · 300x₂ ≥ 0
9 · 5x₃ − 0.3 · 150x₃ ≥ 0
Для углеводов:
4 · 30x₁ − 0.4 · 200x₁ ≤ 0
4 · 20x₂ − 0.4 · 300x₂ ≤ 0
4 · 25x₃ − 0.4 · 150x₃ ≤ 0
Поиск решения
Предположим x₁ = 4, x₂ = 2, x₃ = 3 Проверка ограничений:
  • Стоимость: 100 · 4 + 150 · 2 + 80 · 3 = 1180 ≤ 1500
  • Калорийность: 200 · 4 + 300 · 2 + 1 50 · 3 = 2050 (в пределах 2000-2200)
Расчет БЖУ
Белки: 20 · 4 + 15 · 2 + 10 · 3 = 130 г
Жиры: 10 · 4 + 25 · 2 + 5 · 3 = 85 г
Углеводы: 30 · 4 + 20 · 2 + 25 · 3 = 215 г
Процентное соотношение
Белки: (130 · 4)(2050) · 100 = 25.3%
Жиры: (85 · 9) / (2050) · 100 = 37.1%
Углеводы: (215 · 4) / 2050 · 100 = 41.9%
Анализ результатов
Полученное решение удовлетворяет большинству ограничений, но не полностью соответствует нормам БЖУ. Необходимо скорректировать количество продуктов для достижения оптимальных показателей. Рекомендации по улучшению:
  • Увеличить количество белковой пищи для повышения процента белков
  • Возможно уменьшить количество углеводной пищи
  • Провести повторный расчет с новыми значениями
Пример кода MATLAB для оптимизации рациона

Чтение данных из 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 = 1500;
min_calories = 2000;
max_calories = 2200;

Подготовка для оптимизации

n = length(cost);
f = -cost;

num_constraints = 6;
A = zeros(num_constraints, n);

% Вывод результатов
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

Пояснения к коду

  • Код читает данные из Excel файла
  • Формирует математическую модель оптимизации
  • Решает задачу линейного программирования
  • Выводит результаты в удобном формате

Важные моменты

  • Используются ограничения по стоимости и калорийности
  • Учитываются соотношения БЖУ
  • Проводится проверка корректности результатов
  • Реализована защита от ошибок
Задание
Made on
Tilda