Задача диеты Стиглера
Классическая задача оптимизации рациона, известная как Диета Стиглера, была впервые исследована нобелевским лауреатом Джорджем Стиглером в 1939 году. Эта математическая модель демонстрирует возможность расчета минимально затратного набора продуктов, удовлетворяющего базовые потребности человека в питательных веществах.
Изначально Стиглер рассматривал эту задачу как теоретическое упражнение, а не практическое руководство по питанию. В своих расчетах он пришел к выводу, что оптимальный рацион может стоить всего 39.93 доллара в год по ценам 1939 года. Позже, в 1947 году, Джек Ладерман применил тогда еще новый симплекс-метод для точного решения этой задачи, что потребовало значительных вычислительных ресурсов - 120 человеко-дней работы девяти сотрудников, использовавших механические калькуляторы.
Постановка задачи
- Минимизировать общую стоимость рациона;
- Гарантировать, что потребление каждого питательного вещества соответствует установленным минимальным нормам;
- Рассматривается 77 различных продуктов питания;
- Учитывается 9 питательных веществ (нутриентов): калории, белки, кальций, железо, витамины А, B1, B2, B3, C.
Решение задачи
1. Выбор модели
Для решения задачи диеты Стиглера воспользуемся линейной непрерывной моделью, поскольку классическая формулировка задачи представляет собой линейную задачу на минимум: необходимо подобрать такие количества продуктов, чтобы при минимальной стоимости удовлетворить потребности в питательных веществах. Модель позволяет точно и эффективно решать подобные задачи, где переменные могут быть дробными, а ограничения и целевая функция — линейными.
2. Создание модели
Начнём с создания линейной непрерывной модели. Это означает, что переменные (например, количество продуктов) могут принимать дробные значения и участвуют в линейных выражениях.
// Создаем линейную непрерывную модель (переменные имеют вещественный тип)
Модель = О2
.Модели()
.ЛинейнаяНепрерывнаяМодель()
.СоздатьМодель();
3. Ввод данных
Зададим массив Продукты, содержащий информацию о каждом продукте:
- наименование продукта (потребуется для вывода результата);
- содержание нутриентов: калорий, белков, кальция, железа и витаминов (A, B1, B2, B3, C).
В данном массиве содержание нутриентов нормализовано, то есть приведено в рассчете на 1 доллар. Это позволит в дальнейшем принять, что количество потребляемого продукта эквивалентно его стоимости в долларах.
// Входные данные по содержанию нутриентов (пищевых ценностей): название продукта, калории, белки, кальций, железо и витамины
Продукты = Новый Массив;
Продукты.Добавить("Пшеничная мука, 44.7, 1411, 2, 365, 0, 55.4, 33.3, 441, 0");
Продукты.Добавить("Макароны, 11.6, 418, 0.7, 54, 0, 3.2, 1.9, 68, 0");
Продукты.Добавить("Пшеничные хлопья, 11.8, 377, 14.4, 175, 0, 14.4, 8.8, 114, 0");
// ...
// ... перечисляем все 77 продуктов. см. полный код решения
Создадим массив Нутриенты, в котором перечислим минимально необходимые значения каждого нутриента в день.
// Данные дневных норм потребления по каждому нутриенту
Нутриенты = Новый Массив();
Нутриенты.Добавить("Калории, 3.0");
Нутриенты.Добавить("Белки, 70.0");
Нутриенты.Добавить("Кальций, 0.8");
Нутриенты.Добавить("Железо, 12.0");
Нутриенты.Добавить("Витамин A, 5.0");
Нутриенты.Добавить("Витамин B1, 1.8");
Нутриенты.Добавить("Витамин B2, 2.7");
Нутриенты.Добавить("Витмаин B3, 18.0");
Нутриенты.Добавить("Витамин C, 75.0");
Преобразуем строки с данными в числовой формат с помощью метода МассивЧиселИзСтроки библиотеки О2.
// Оцифровываем массивы входных данных с помощью вспомогательной функции
Для К_прод = 0 По Продукты.ВГраница() Цикл
Продукты[К_прод] = О2.Утилиты().МассивЧиселИзСтроки(Продукты[К_прод]);
КонецЦикла;
Для К_нутр = 0 По Нутриенты.ВГраница() Цикл
Нутриенты[К_нутр] = О2.Утилиты().МассивЧиселИзСтроки(Нутриенты[К_нутр]);
КонецЦикла;
4. Регистрация переменных
Для каждого продукта добавим переменную, которая будет отражать его количество в рационе. Зададим диапазон значений переменных от нуля до бесконечности.
Чтобы не создавать переменные по одной воспользуемся методом МассивПеременныхДиапазона, который регистрирует сразу несколько переменных и возвращает их массивом.
// Региструем переменные (по одной на кадый продукт)
КоличестваПродуктов = Модель.МассивПеременныхДиапазона(
Продукты.Количество(), // <-- размер массива
0, // <-- левая граница значений
Неопределено // <-- правая граница значений (бесконечность)
);
5. Описание ограничений
Сформируем выражения, отражающие общее потребление каждого нутриента по всем продуктам. Установим ограничения: фактическое потребление должно быть не меньше нормы.
// Устанавливаем ограничения: суммарное содержание нутриента >= нормы
СуммыНутриентов = Новый Массив(Нутриенты.Количество());
СуммаНутриента = Модель.Выражения().СоздатьПостроительВыражений();
Для К_нутр = 0 По Нутриенты.ВГраница() Цикл
СуммаНутриента.Очистить(); // <-- очищаем простроитель выражений
Для К_прод = 0 По Продукты.ВГраница() Цикл
Концентрация = Продукты[К_прод][К_нутр + 1];
СуммаНутриента.ДобавитьТерм(КоличестваПродуктов[К_прод], Концентрация); // <-- добавляем слагаемые
КонецЦикла;
СуммыНутриентов[К_нутр] = СуммаНутриента.ПолучитьВыражение(); // <-- получаем итоговое выражение и сохраняем в массив
НормаПотребления = Нутриенты[К_нутр][1]; // <-- нормру берем из входных данных
Модель.Ограничения().ЗначениеБольшеИлиРавно( // <-- устанавливаем ограничение: потребление >= норма
СуммыНутриентов[К_нутр],
НормаПотребления
);
КонецЦикла;
В данном фрагменте СуммаНутриента - это построитель выражений, специальный объект, который позволяет формировать линейное выражение инкрементально в цикле.
Сформированные им выражения сохраняются в массив СуммыНутриентов. Позднее мы вычислим значения этих выражений при выводе результата.
6. Описание целевой функции
Определим цель — минимизировать общую стоимость продуктов. Стоимость продуктов эквивалентна их количеству т.к. цена нормализована, а значит мы момжет просто минимизировать итоговое количество всех продуктов.
// Целевая функция: минимизируем количество продуктов (а значит и стоимость)
СуммаПродуктов = Модель.Выражения().Сумма(КоличестваПродуктов);
Модель.Минимизировать(СуммаПродуктов);
В данном фрагменте СуммаПродуктов - это линейное выражение, являющееся суммой созданных ранее переменных.
Метод Минимизировать - устанавливает задачу по нахождению решения с мимнимальным значением указанного выражения.
7. Решение модели
Вызовем метод Решить, чтобы запустить оптимизационный процесс. Полученный в ходе вычислений объект Решение используем далее для проверки и вывода результата.
// Решение модели
Решение = Модель.Решить();
8. Вывод результатов
Для каждого продукта с ненулевым количеством рассчитаем годовой объём потребления. Также выведем:
- общую годовую стоимость рациона;
- суточное потребление каждого нутриента и его соответствие норме.
// Вывод результатов
Если Решение.РешениеНайдено() Тогда
ФорматВывода = "ЧДЦ=2; ЧН=0; ЧГ=0";
Сообщение = "Годовые закупки продуктов:" + Символы.ПС;
Для К_прод = 0 По КоличестваПродуктов.ВГраница() Цикл
Количество = Решение.ЗначениеПеременной(КоличестваПродуктов[К_прод]);
Если Количество > 0 Тогда
ГодовоеПотребление = Количество * 365;
ГодоваяСтоимость = ГодовоеПотребление;
Сообщение = Сообщение + СтрШаблон(
"%1: %2$%3",
Продукты[К_прод][0],
Формат(ГодоваяСтоимость, ФорматВывода),
Символы.ПС
);
КонецЕсли;
КонецЦикла;
ИтоговаяДневнаяСтоимость = Решение.ЗначениеВыражения(СуммаПродуктов);
ИтоговаяГодоваяСтоимость = ИтоговаяДневнаяСтоимость * 365;
Сообщение = Сообщение + Символы.ПС + СтрШаблон(
"Итоговая годовая стоимость: %1$%2",
Формат(ИтоговаяГодоваяСтоимость, ФорматВывода),
Символы.ПС + Символы.ПС
);
Сообщение = Сообщение + "Потребление нутриентов в день:" + Символы.ПС;
Для К_нутр = 0 По Нутриенты.ВГраница() Цикл
НормаПотребления = Нутриенты[К_нутр][1];
СуммаНутриента = Решение.ЗначениеВыражения(СуммыНутриентов[К_нутр]);
Сообщение = Сообщение + СтрШаблон(
"%1: %2 (минимум %3)%4",
Нутриенты[К_нутр][0],
Формат(СуммаНутриента, ФорматВывода),
Формат(Нутриенты[К_нутр][1], ФорматВывода),
Символы.ПС
);
КонецЦикла;
Сообщить(Сообщение);
Иначе
Сообщить("Задача не имеет решения!");
КонецЕсли;
В данном фрагменте использованы методы ЗначениеПеременной и ЗначениеВыражения. ЗначениеПеременной - возвращает значение конкретной пременной, найденное решателем,
а ЗначениеВыражения - вычисляет значение линейного выражения, подставляя в него найденные значения.
Полный код решения задачи
Ниже представлен полный код решения. Вы также можете скачать пример в виде готовой обработки.
// Создаем линейную непрерывную модель (переменные имеют вещественный тип)
Модель = О2
.Модели()
.ЛинейнаяНепрерывнаяМодель()
.СоздатьМодель();
// Входные данные по содержанию нутриентов (пищевых ценностей): название продукта, калории, белки, кальций, железо и витамины
Продукты = Новый Массив;
Продукты.Добавить("Пшеничная мука, 44.7, 1411, 2, 365, 0, 55.4, 33.3, 441, 0");
Продукты.Добавить("Макароны, 11.6, 418, 0.7, 54, 0, 3.2, 1.9, 68, 0");
Продукты.Добавить("Пшеничные хлопья, 11.8, 377, 14.4, 175, 0, 14.4, 8.8, 114, 0");
Продукты.Добавить("Кукурузные хлопья, 11.4, 252, 0.1, 56, 0, 13.5, 2.3, 68, 0");
Продукты.Добавить("Кукурузная мука, 36.0, 897, 1.7, 99, 30.9, 17.4, 7.9, 106, 0");
Продукты.Добавить("Кукурузная крупа, 28.6, 680, 0.8, 80, 0, 10.6, 1.6, 110, 0");
Продукты.Добавить("Рис, 21.2, 460, 0.6, 41, 0, 2, 4.8, 60, 0");
Продукты.Добавить("Овсяные хлопья, 25.3, 907, 5.1, 341, 0, 37.1, 8.9, 64, 0");
Продукты.Добавить("Белый хлеб, 15.0, 488, 2.5, 115, 0, 13.8, 8.5, 126, 0");
Продукты.Добавить("Цельнозерновой хлеб, 12.2, 484, 2.7, 125, 0, 13.9, 6.4, 160, 0");
Продукты.Добавить("Ржаной хлеб, 12.4, 439, 1.1, 82, 0, 9.9, 3, 66, 0");
Продукты.Добавить("Пирог, 8.0, 130, 0.4, 31, 18.9, 2.8, 3, 17, 0");
Продукты.Добавить("Соленые крекеры, 12.5, 288, 0.5, 50, 0, 0, 0, 0, 0");
Продукты.Добавить("Молоко, 6.1, 310, 10.5, 18, 16.8, 4, 16, 7, 177");
Продукты.Добавить("Сгущенное молоко, 8.4, 422, 15.1, 9, 26, 3, 23.5, 11, 60");
Продукты.Добавить("Масло сливочное, 10.8, 9, 0.2, 3, 44.2, 0, 0.2, 2, 0");
Продукты.Добавить("Маргарин, 20.6, 17, 0.6, 6, 55.8, 0.2, 0, 0, 0");
Продукты.Добавить("Яйца, 2.9, 238, 1.0, 52, 18.6, 2.8, 6.5, 1, 0");
Продукты.Добавить("Сыр Чеддер, 7.4, 448, 16.4, 19, 28.1, 0.8, 10.3, 4, 0");
Продукты.Добавить("Сливки, 3.5, 49, 1.7, 3, 16.9, 0.6, 2.5, 0, 17");
Продукты.Добавить("Арахисовая паста, 15.7, 661, 1.0, 48, 0, 9.6, 8.1, 471, 0");
Продукты.Добавить("Майонез, 8.6, 18, 0.2, 8, 2.7, 0.4, 0.5, 0, 0");
Продукты.Добавить("Растительный жир, 20.1, 0, 0, 0, 0, 0, 0, 0, 0");
Продукты.Добавить("Сало, 41.7, 0, 0, 0, 0.2, 0, 0.5, 5, 0");
Продукты.Добавить("Стейк, 2.9, 166, 0.1, 34, 0.2, 2.1, 2.9, 69, 0");
Продукты.Добавить("Говядина, 2.2, 214, 0.1, 32, 0.4, 2.5, 2.4, 87, 0");
Продукты.Добавить("Жаркое из ребра, 3.4, 213, 0.1, 33, 0, 0, 2, 0, 0");
Продукты.Добавить("Жаркое из лопатки, 3.6, 309, 0.2, 46, 0.4, 1, 4, 120, 0");
Продукты.Добавить("Грудинка, 8.5, 404, 0.2, 62, 0, 0.9, 0, 0, 0");
Продукты.Добавить("Печень говяжья, 2.2, 333, 0.2, 139, 169.2, 6.4, 50.8, 316, 525");
Продукты.Добавить("Окорок ягненка, 3.1, 245, 0.1, 20, 0, 2.8, 3.9, 86, 0");
Продукты.Добавить("Бараньи ребра, 3.3, 140, 0.1, 15, 0, 1.7, 2.7, 54, 0");
Продукты.Добавить("Свиные отбивные, 3.5, 196, 0.2, 30, 0, 17.4, 2.7, 60, 0");
Продукты.Добавить("Свиная корейка, 4.4, 249, 0.3, 37, 0, 18.2, 3.6, 79, 0");
Продукты.Добавить("Бекон, 10.4, 152, 0.2, 23, 0, 1.8, 1.8, 71, 0");
Продукты.Добавить("Ветчина, 6.7, 212, 0.2, 31, 0, 9.9, 3.3, 50, 0");
Продукты.Добавить("Соленая свинина, 18.8, 164, 0.1, 26, 0, 1.4, 1.8, 0, 0");
Продукты.Добавить("Цыпленок для жарки, 1.8, 184, 0.1, 30, 0.1, 0.9, 1.8, 68, 46");
Продукты.Добавить("Телячьи котлеты, 1.7, 156, 0.1, 24, 0, 1.4, 2.4, 57, 0");
Продукты.Добавить("Лосось консервированный, 5.8, 705, 6.8, 45, 3.5, 1, 4.9, 209, 0");
Продукты.Добавить("Яблоки, 5.8, 27, 0.5, 36, 7.3, 3.6, 2.7, 5, 544");
Продукты.Добавить("Бананы, 4.9, 60, 0.4, 30, 17.4, 2.5, 3.5, 28, 498");
Продукты.Добавить("Лимоны, 1.0, 21, 0.5, 14, 0, 0.5, 0, 4, 952");
Продукты.Добавить("Апельсины, 2.2, 40, 1.1, 18, 11.1, 3.6, 1.3, 10, 1998");
Продукты.Добавить("Зеленая фасоль, 2.4, 138, 3.7, 80, 69, 4.3, 5.8, 37, 862");
Продукты.Добавить("Капуста, 2.6, 125, 4.0, 36, 7.2, 9, 4.5, 26, 5369");
Продукты.Добавить("Морковь, 2.7, 73, 2.8, 43, 188.5, 6.1, 4.3, 89, 608");
Продукты.Добавить("Сельдерей, 0.9, 51, 3.0, 23, 0.9, 1.4, 1.4, 9, 313");
Продукты.Добавить("Салат, 0.4, 27, 1.1, 22, 112.4, 1.8, 3.4, 11, 449");
Продукты.Добавить("Лук, 5.8, 166, 3.8, 59, 16.6, 4.7, 5.9, 21, 1184");
Продукты.Добавить("Картофель, 14.3, 336, 1.8, 118, 6.7, 29.4, 7.1, 198, 2522");
Продукты.Добавить("Шпинат, 1.1, 106, 0, 138, 918.4, 5.7, 13.8, 33, 2755");
Продукты.Добавить("Сладкий картофель, 9.6, 138, 2.7, 54, 290.7, 8.4, 5.4, 83, 1912");
Продукты.Добавить("Персики консервированные, 3.7, 20, 0.4, 10, 21.5, 0.5, 1, 31, 196");
Продукты.Добавить("Груши консервированные, 3.0, 8, 0.3, 8, 0.8, 0.8, 0.8, 5, 81");
Продукты.Добавить("Ананас консервированный, 2.4, 16, 0.4, 8, 2, 2.8, 0.8, 7, 399");
Продукты.Добавить("Спаржа консервированная, 0.4, 33, 0.3, 12, 16.3, 1.4, 2.1, 17, 272");
Продукты.Добавить("Зеленая фасоль консервированная, 1.0, 54, 2, 65, 53.9, 1.6, 4.3, 32, 431");
Продукты.Добавить("Фасоль с мясом консервированная, 7.5, 364, 4, 134, 3.5, 8.3, 7.7, 56, 0");
Продукты.Добавить("Кукуруза консервированная, 5.2, 136, 0.2, 16, 12, 1.6, 2.7, 42, 218");
Продукты.Добавить("Горох консервированный, 2.3, 136, 0.6, 45, 34.9, 4.9, 2.5, 37, 370");
Продукты.Добавить("Томаты консервированные, 1.3, 63, 0.7, 38, 53.2, 3.4, 2.5, 36, 1253");
Продукты.Добавить("Томатный суп консервированный, 1.6, 71, 0.6, 43, 57.9, 3.5, 2.4, 67, 862");
Продукты.Добавить("Персики сушеные, 8.5, 87, 1.7, 173, 86.8, 1.2, 4.3, 55, 57");
Продукты.Добавить("Чернослив, 12.8, 99, 2.5, 154, 85.7, 3.9, 4.3, 65, 257");
Продукты.Добавить("Изюм, 13.5, 104, 2.5, 136, 4.5, 6.3, 1.4, 24, 136");
Продукты.Добавить("Горох сушеный, 20.0, 1367, 4.2, 345, 2.9, 28.7, 18.4, 162, 0");
Продукты.Добавить("Лимская фасоль сушеная, 17.4, 1055, 3.7, 459, 5.1, 26.9, 38.2, 93, 0");
Продукты.Добавить("Фасоль сушеная, 26.9, 1691, 11.4, 792, 0, 38.4, 24.6, 217, 0");
Продукты.Добавить("Кофе, 0, 0, 0, 0, 0, 4, 5.1, 50, 0");
Продукты.Добавить("Чай, 0, 0, 0, 0, 0, 0, 2.3, 42, 0");
Продукты.Добавить("Какао, 8.7, 237, 3, 72, 0, 2, 11.9, 40, 0");
Продукты.Добавить("Шоколад, 8.0, 77, 1.3, 39, 0, 0.9, 3.4, 14, 0");
Продукты.Добавить("Сахар, 34.9, 0, 0, 0, 0, 0, 0, 0, 0");
Продукты.Добавить("Кукурузный сироп, 14.7, 0, 0.5, 74, 0, 0, 0, 5, 0");
Продукты.Добавить("Патока, 9.0, 0, 10.3, 244, 0, 1.9, 7.5, 146, 0");
Продукты.Добавить("Клубничное варенье, 6.4, 11, 0.4, 7, 0.2, 0.2, 0.4, 3, 0");
// Данные дневных норм потребления по каждому нутриенту
Нутриенты = Новый Массив();
Нутриенты.Добавить("Калории, 3.0");
Нутриенты.Добавить("Белки, 70.0");
Нутриенты.Добавить("Кальций, 0.8");
Нутриенты.Добавить("Железо, 12.0");
Нутриенты.Добавить("Витамин A, 5.0");
Нутриенты.Добавить("Витамин B1, 1.8");
Нутриенты.Добавить("Витамин B2, 2.7");
Нутриенты.Добавить("Витмаин B3, 18.0");
Нутриенты.Добавить("Витамин C, 75.0");
// Оцифровываем массивы входных данных с помощью вспомогательной функции
Для К_прод = 0 По Продукты.ВГраница() Цикл
Продукты[К_прод] = О2.Утилиты().МассивЧиселИзСтроки(Продукты[К_прод]);
КонецЦикла;
Для К_нутр = 0 По Нутриенты.ВГраница() Цикл
Нутриенты[К_нутр] = О2.Утилиты().МассивЧиселИзСтроки(Нутриенты[К_нутр]);
КонецЦикла;
// Региструем переменные (по одной на кадый продукт)
КоличестваПродуктов = Модель.МассивПеременныхДиапазона(
Продукты.Количество(),
0,
Неопределено
);
// Устанавливаем ограничения: суммарное содержание нутриента >= нормы
СуммыНутриентов = Новый Массив(Нутриенты.Количество());
СуммаНутриента = Модель.Выражения().СоздатьПостроительВыражений();
Для К_нутр = 0 По Нутриенты.ВГраница() Цикл
СуммаНутриента.Очистить(); // <-- очищаем простроитель выражений
Для К_прод = 0 По Продукты.ВГраница() Цикл
Концентрация = Продукты[К_прод][К_нутр + 1];
СуммаНутриента.ДобавитьТерм(КоличестваПродуктов[К_прод], Концентрация); // <-- добавляем слагаемые
КонецЦикла;
СуммыНутриентов[К_нутр] = СуммаНутриента.ПолучитьВыражение(); // <-- получаем итоговое выражение и сохраняем в массив
НормаПотребления = Нутриенты[К_нутр][1]; // <-- нормру берем из входных данных
Модель.Ограничения().ЗначениеБольшеИлиРавно( // <-- устанавливаем ограничение: потребление >= норма
СуммыНутриентов[К_нутр],
НормаПотребления
);
КонецЦикла;
// Целевая функция: минимизируем количество продуктов (а значит и стоимость)
СуммаПродуктов = Модель.Выражения().Сумма(КоличестваПродуктов);
Модель.Минимизировать(СуммаПродуктов);
// Решение модели
Решение = Модель.Решить();
// Вывод результатов
Если Решение.РешениеНайдено() Тогда
ФорматВывода = "ЧДЦ=2; ЧН=0; ЧГ=0";
Сообщение = "Годовые закупки продуктов:" + Символы.ПС;
Для К_прод = 0 По КоличестваПродуктов.ВГраница() Цикл
Количество = Решение.ЗначениеПеременной(КоличестваПродуктов[К_прод]);
Если Количество > 0 Тогда
ГодовоеПотребление = Количество * 365;
ГодоваяСтоимость = ГодовоеПотребление;;
Сообщение = Сообщение + СтрШаблон(
"%1: %2$%3",
Продукты[К_прод][0],
Формат(ГодоваяСтоимость, ФорматВывода),
Символы.ПС
);
КонецЕсли;
КонецЦикла;
ИтоговаяДневнаяСтоимость = Решение.ЗначениеВыражения(СуммаПродуктов);
ИтоговаяГодоваяСтоимость = ИтоговаяДневнаяСтоимость * 365;
Сообщение = Сообщение + Символы.ПС + СтрШаблон(
"Итоговая годовая стоимость: %1$%2",
Формат(ИтоговаяГодоваяСтоимость, ФорматВывода),
Символы.ПС + Символы.ПС
);
Сообщение = Сообщение + "Потребление нутриентов в день:" + Символы.ПС;
Для К_нутр = 0 По Нутриенты.ВГраница() Цикл
НормаПотребления = Нутриенты[К_нутр][1];
СуммаНутриента = Решение.ЗначениеВыражения(СуммыНутриентов[К_нутр]);
Сообщение = Сообщение + СтрШаблон(
"%1: %2 (минимум %3)%4",
Нутриенты[К_нутр][0],
Формат(СуммаНутриента, ФорматВывода),
Формат(НормаПотребления, ФорматВывода),
Символы.ПС
);
КонецЦикла;
Сообщить(Сообщение);
Иначе
Сообщить("Задача не имеет решения!");
КонецЕсли;