A diéta probléma

Összegzés: A cél diéta probléma olyan élelmiszerek kiválasztása, amelyek minimális költséggel kielégítik a napi táplálkozási szükségleteket. A probléma megfogalmazása a lineáris program ahol a költségek minimalizálása a cél, és a korlátozásoknak meg kell felelniük a meghatározott táplálkozási követelményeknek. Az étrend problémakorlátjai általában szabályozzák a kalóriák számát, valamint a vitaminok, ásványi anyagok, zsírok, nátrium és koleszterin mennyiségét az étrendben. Bár a matematikai megfogalmazás egyszerű, a megoldás nem feltétlenül ízletes! A táplálkozási igények kielégíthetők az íz és a változatosság figyelembevétele nélkül, ezért vegye fontolóra a kimenetet, mielőtt az étkezésbe belevágna egy "optimális" menüből!

Esettanulmány tartalma

  • Történelem
  • Probléma nyilatkozat
  • Diéta problémamegoldó
  • Matematikai megfogalmazás
  • AMPL megvalósítás
  • A megoldás értelmezése
  • Köszönetnyilvánítás

Történelem

A diétás probléma az 1930-as és 1940-es években az egyik első tanulmányozott optimalizálási probléma volt. A problémát az indokolta, hogy a hadsereg arra törekedett, hogy minimalizálja a földi eredetű földrajzi jelek táplálásának költségeit, miközben továbbra is egészséges étrendet biztosít. Az egyik korai kutató, aki a problémát tanulmányozta, George Stigler volt, aki heurisztikus módszerrel művelt találgatást adott az optimális megoldásról. Az optimális étrend költségére vonatkozó becslése 39,93 dollár volt évente (1939-es árak). 1947 őszén Jack Laderman, a Nemzeti Szabványügyi Hivatal Matematikai Táblázatok Projektje az újonnan kifejlesztett szimplex módszerrel oldotta meg Stigler modelljét. Az optimalizálás első "nagy léptékű" számításaként a lineáris program kilenc egyenletből állt, 77 ismeretlenben. Kilenc ügyintézőnek kellett kézzel működtetett asztali számológépekkel 120 embernapot megoldania az optimális 39,69 dolláros megoldás érdekében. Stigler találgatása csak 0,24 dollár volt évente!

Probléma nyilatkozat

Mivel az élelmiszerek összessége, az egyes élelmiszerek tápanyag-információival és az egyes élelmiszerek adagonkénti költségeivel együtt, a diétás probléma célja az egyes megvásárolható (és elfogyasztandó) adagok számának kiválasztása a fogyasztás minimalizálása érdekében. az élelmiszer költsége, miközben megfelel a meghatározott táplálkozási követelményeknek. A tápanyagigény általában az egyes tápanyag-összetevők minimális és maximális megengedett szintjeként van kifejezve. Egyéb korlátozások, például a minimális és/vagy maximális adagok szerepelhetnek a menü minőségének javítása érdekében.

Vizsgáljuk meg a következő egyszerű példát (The Diet Problem: A WWW-alapú interaktív esettanulmány a lineáris programozásban). Tegyük fel, hogy három élelmiszer áll rendelkezésre, kukorica, tej és kenyér, és korlátozottak a kalóriák száma (2000 és 2250 között) és az A-vitamin mennyisége (5000 és 50 000 között). Az első táblázat felsorolja minden ételre az egy adag költségét, az A-vitamin mennyiségét és az egy adagban szereplő kalóriák számát.

Étel Adagonkénti költség A-vitamin Kalóriák
Kukorica 0,18 USD 107. 72
2% tej 0,23 USD 500 121
Kenyér 0,05 USD 0 65

Tegyük fel, hogy az adagok maximális száma 10. Ezután a probléma optimális megoldása 1,94 adag kukorica, 10 adag tej és 10 adag kenyér, összköltsége 3,15 USD. Az A-vitamin teljes mennyisége 5208, a kalóriák száma pedig 2000.

Diéta problémamegoldó

Kattintson ide vagy a képre, hogy megoldja saját diétás problémáit!

összes F-ben

Matematikai megfogalmazás

A diétaprogram matematikailag lineáris programozási problémaként fogalmazható meg, az alábbiak szerint.

Készletek
F = élelmiszerek halmaza
N = tápanyagok halmaza

Paraméterek
\ (a_ \) = tápanyag mennyisége (j) az élelmiszerekben \ (i \), \ (\ forall i \ in F \), \ (\ forall j \ in N \)
\ (c_i \) = étel adagra vetített ára \ (i \), \ (\ összes i \ F-ben)
\ (Fmin_i \) = a szükséges adagok minimális száma \ (i \), \ (\ összes i \ F-ben)
\ (Fmax_i \) = az élelmiszerek maximálisan megengedett adagja \ (i \), \ (\ forall i \ in F \)
\ (Nmin_j \) = minimális szükséges tápanyagszint \ (j \), \ (\ összes j \ N-ben)
\ (Nmax_j \) = maximálisan megengedett tápanyagszint \ (j \), \ (\ összes j \ N-ben)

Változók
\ (x_i \) = a megvásárolható/elfogyasztandó ételadagok száma \ (i \), \ (\ összes i \ F-ben)

Objektív funkció: Minimalizálja az étel teljes költségét
Kicsinyítés \ (\ összeg_ c_i x_i \)

1. kényszerhalmaz: Minden egyes tápanyag esetében (j \ N-ben) legalább el kell érnie a minimálisan szükséges szintet.
\(\összeg_ a_ x_i \ geq Nmin_j, \ összes j \ N-ben)

2. kényszerhalmaz: Az egyes tápanyagok esetében \ (j \ N-ben) ne lépje túl a maximálisan megengedett szintet.
\(\összeg_ a_ x_i \ leq Nmax_j, \ forall j \ N-ben)

3. kényszerkészlet: Minden ételhez \ (i \ F-ben) válassza ki a minimálisan szükséges adagokat.
\ (x_i \ geq Fmin_i, \ összes i \ -ban F \)

4. kényszerkészlet: Az egyes ételeknél (i-ben F-ben) ne lépje túl a maximálisan megengedett adagok számát.
\ (x_i \ leq Fmax_i, \ összes i \ F-ben)

Ennek a lineáris programozási problémának a megoldásához használhatjuk a NEOS Server megoldókat a Linear Programming kategóriában. Minden LP megoldónak van egy vagy több bemeneti formátuma, amelyet elfogad. Példaként egy AMPL modellt adunk meg a fent leírt egyszerű példához.

AMPL megvalósítás

param a> = 0;
param c> = 0;
param Fmin> = 0;
param Fmax > = Fmin [i];
param Nmin> = 0;
param Nmax> = Nmax [j];

minimalizálja a teljes_költséget: összeg c [i] * x [i];

a táplálkozási_kérdések függvényében:
Nmin [j]