Обобщение: Целта на диетичен проблем е да изберете набор от храни, които да задоволят набор от дневни хранителни нужди при минимални разходи. Проблемът е формулиран като a линейна програма където целта е да се минимизират разходите, а ограниченията да отговарят на определените хранителни изисквания. Ограниченията на диетичните проблеми обикновено регулират броя на калориите и количеството витамини, минерали, мазнини, натрий и холестерол в диетата. Макар математическата формулировка да е проста, решението може да не е вкусно! Хранителните изисквания могат да бъдат изпълнени без оглед на вкуса или разнообразието, така че вземете предвид резултата, преди да се впуснете в ястие от „оптимално“ меню!

Съдържание на казуса

  • История
  • Декларация за проблема
  • Диета за решаване на проблеми
  • Математическа формулировка
  • Прилагане на AMPL
  • Тълкуване на решението
  • Благодарности

История

Проблемът с диетата е един от първите проблеми с оптимизацията, изследван през 30-те и 40-те години. Проблемът е мотивиран от желанието на армията да сведе до минимум разходите за хранене на ГИ на полето, като същевременно осигурява здравословна диета. Един от ранните изследователи, изучавали проблема, е Джордж Стиглер, който прави образовани предположения за оптимално решение, използвайки евристичен метод. Неговото предположение за цената на оптималната диета е \ $ 39,93 на година (цени от 1939 г.). През есента на 1947 г. Джак Ладерман от проекта за математически таблици на Националното бюро за стандарти използва новоразработения симплекс метод за решаване на модела на Щиглер. Като първото "широкомащабно" изчисление при оптимизацията, линейната програма се състои от девет уравнения в 77 неизвестни. Девет служители, използващи ръчни калкулатори за бюро, отнеха 120 човекодни, за да намерят оптималното решение от $ 39,69. Предположенията на Stigler бяха изключени само с $ 0,24 годишно!

Декларация за проблема

Като се има предвид набор от храни, заедно с информацията за хранителните вещества за всяка храна и цената на порция на всяка храна, целта на диетичния проблем е да се избере броят на порциите от всяка храна, която да се закупи (и консумира), така че да се сведе до минимум цената на храната, като същевременно отговаря на определените хранителни изисквания. Обикновено хранителните нужди се изразяват като минимално и максимално допустимо ниво за всеки хранителен компонент. Други ограничения, като минимален и/или максимален брой порции, могат да бъдат включени, за да се подобри качеството на менюто.

Помислете за следния прост пример (от The Diet Problem: Базирано на WWW интерактивно изследване на казуса в линейното програмиране). Да предположим, че има три храни на разположение, царевица, мляко и хляб, и има ограничения за броя на калориите (между 2000 и 2250) и количеството на витамин А (между 5000 и 50 000). В първата таблица са изброени, за всяка храна, цената на порция, количеството витамин А на порция и броят на калориите на порция.

Храна Цена на порция Витамин А Калории
Царевица $ 0,18 107 72
2% мляко $ 0,23 500 121
Пшеничен хляб $ 0,05 0 65

Да предположим, че максималният брой порции е 10. Тогава оптималното решение на проблема е 1,94 порции царевица, 10 порции мляко и 10 порции хляб с обща цена от 3,15 долара. Общото количество витамин А е 5208, а общият брой калории е 2000.

Диета за решаване на проблеми

Щракнете тук или на изображението, за да решите собствените си проблеми с диетата!

проблем

Математическа формулировка

Задачата за диетата може да бъде формулирана математически като задача за линейно програмиране, както е показано по-долу.

Комплекти
F = набор от храни
N = набор от хранителни вещества

Параметри
\ (a_ \) = количество хранително вещество \ (j \) в храната \ (i \), \ (\ forall i \ in F \), \ (\ forall j \ in N \)
\ (c_i \) = цена на порция храна \ (i \), \ (\ forall i \ in F \)
\ (Fmin_i \) = минимален брой необходими порции храна \ (i \), \ (\ forall i \ in F \)
\ (Fmax_i \) = максимално допустим брой порции храна \ (i \), \ (\ forall i \ in F \)
\ (Nmin_j \) = минимално необходимо ниво на хранителни вещества \ (j \), \ (\ forall j \ in N \)
\ (Nmax_j \) = максимално допустимото ниво на хранителни вещества \ (j \), \ (\ за всички j \ в N \)

Променливи
\ (x_i \) = брой порции храна \ (i \) за закупуване/консумиране, \ (\ forall i \ in F \)

Целева функция: Минимизиране на общите разходи за храната
Намаляване \ (\ sum_ c_i x_i \)

Комплект ограничения 1: За всяко хранително вещество \ (j \ in N \) поне отговаряйте на минимално необходимото ниво.
\ (\ sum_ a_ x_i \ geq Nmin_j, \ forall j \ in N \)

Набор за ограничение 2: За всяко хранително вещество \ (j \ in N \), не надвишавайте максимално допустимото ниво.
\ (\ sum_ a_ x_i \ leq Nmax_j, \ forall j \ in N \)

Набор за ограничение 3: За всяка храна \ (i \ in F \) изберете поне минимално необходимия брой порции.
\ (x_i \ geq Fmin_i, \ forall i \ in F \)

Набор за ограничение 4: За всяка храна \ (i \ in F \), не надвишавайте максимално допустимия брой порции.
\ (x_i \ leq Fmax_i, \ forall i \ in F \)

За да разрешим този проблем с линейното програмиране, можем да използваме един от решавачите на NEOS Server в категорията Линейно програмиране. Всеки LP Solver има един или повече входни формати, които приема. Като пример предоставяме AMPL модел за простия пример, описан по-горе.

Прилагане на AMPL

param a> = 0;
параметър c> = 0;
param Fmin> = 0;
param Fmax > = Fmin [i];
параметър Nmin> = 0;
параметър Nmax> = Nmax [j];

минимизиране на total_cost: сума c [i] * x [i];

предмет на nutritional_reqs:
Nmin [j]