AMPL modell az étrend problémájához

AMPL modell az étrend problémájához

étrend

1. A probléma leírása

Fontolja meg az elkészített ételek kiválasztásának problémáját, hogy megfeleljenek bizonyos táplálkozási követelményeknek. Tegyük fel, hogy a következő típusú előfőzött vacsorák csomagonként a következő áron állnak rendelkezésre:

Makaróni sajt

Ezek a vacsorák a következő százalékokat adják csomagonként az A, C, B1 és B2 vitamin minimális napi követelményeinek.

A probléma az, hogy megtalálja a legolcsóbb csomagkombinációt, amely megfelel a heti követelményeknek, vagyis az egyes tápanyagok napi szükségletének legalább 700% -a.

2. LP megfogalmazás

Írjuk meg a megvásárolható marhahús vacsora csomagok számára X BEEF, a megvásárolható marhahús vacsora csomagok számára pedig X CHK stb. Ekkor a diéta teljes költsége:

3,19 X MARHA + 2,59 X CHK + 2,29 X HAL +2,89 X HAM +

1,89 X MCH + 1,99 X MTL + 1,99 X SPG + 2,49 X TUR

Az A-vitamin szükséglet teljes százalékát hasonló képlet adja meg, azzal a különbséggel, hogy az X BEEF, X CHK és így tovább a csomagonkénti százalékkal megszorozzuk a csomagonkénti költség helyett:

Az A-vitamin teljes napi szükségletének teljes százaléka =

60 X MARHA + 8 X CHK + 8 X HAL + 40 X HAM +

15 X MCH + 70 X MTL + 25 X SPG + 60 X TUR

Ennek az összegnek nagyobbnak vagy egyenlőnek kell lennie, mint 700 százalék. Minden más vitaminnak van egy hasonló képlete, és mindegyiknek nagyobbnak vagy egyenlőnek kell lennie, mint 700 százalék.

Mindezeket összerakva a következő lineáris programmal rendelkezünk:

3,19 X MARHA + 2,59 X CHK + 2,29 X HAL +2,89 X HAM +

1,89 X MCH + 1,99 X MTL + 1,99 X SPG + 2,49 X TUR

60 X MARHA + 8 X CHK + 8 X HAL + 40 X HAM +

15 X MCH + 70 X MTL + 25 X SPG + 60 X TUR> = 700

20 X MARHA + 0 X CHK + 10 X HAL + 40 X HAM +

35 X MCH + 30 X MTL + 50 X SPG + 20 X TUR> = 700

10 X marhahús + 20 X CHK + 15X HAL + 35 X sonka +

15 X MCH + 15 X MTL + 25 X SPG + 15 X TUR> = 700

15 X marhahús + 20X CHK + 10 X HAL + 10 X sonka +

15 X MCH + 15X MTL + 15 X SPG + 10 X TUR> = 700

X MARHA, X CHK, X HAL, X HAM, X MCH, X MTL, X SPG, X TUR> = 0

A lineáris program leírásának másik módja a következő:

Adva: F, élelmiszerek halmaza

N, tápanyagok halmaza

c j = j vacsora csomagonkénti költség, minden j esetében F-ben

p i, j = az i tápanyag százalékos aránya vacsoracsomagonként, minden i-re N-ben, j-ben F-ben

l j = j tápanyag minimális heti szükséglete minden j-re F-ben

Döntési változók: X j = megvásárolható j vacsora csomagok minden j-re F-ben

Ez a modell két dologgal foglalkozik: tápanyagokkal és ételekkel. Így egy AMPL modellel kezdjük, és deklaráljuk mindegyik halmazát:

Ezután meg kell adnunk a modell által megkövetelt számokat. Minden egyes étel esetében biztosan pozitív költséget kell fizetni:

Egy adott étel költségét mondjuk költségként [BEEF] írják, bár az LP modellben szereplő konkrét értékekre való hivatkozások általában olyan indexekben vannak, mint a j, nem pedig olyan meghatározott halmazok, mint a BEEF .

Annak érdekében, hogy a modell valamivel általánosabb legyen, mint az eddigi LP-k, azt is meghatározzuk, hogy az egyes élelmiszerek esetében az étrendben lévő csomagok számának alsó és felső határai vannak:

param f_max> = f_min [j];

Figyeljük meg, hogy szükségünk van egy j j indexre, hogy az F_max deklarációban elfussunk a FOOD-on, hogy azt mondhassuk, hogy az egyes élelmiszerek maximális értékének nagyobbnak vagy egyenlőnek kell lennie a megfelelő minimummal.

Ugyancsak kényelmesnek találjuk megadni az étrendben lévő egyes tápanyagok mennyiségének hasonló alsó és felső határát:

param n_max > = n_min [i];

Végül egy tápanyag és egy élelmiszer kombinációjához szükségünk van egy számra, amely az egyes i tápanyagok mennyiségét jelöli az élelmiszer csomagolásában. A két készlet ilyen "termékét" úgy írják, hogy mindkettőt felsorolja:

Erre a paraméterre való hivatkozásokhoz két index szükséges. Például az amt [i, j] az i tápanyag mennyisége egy j csomagban .

E modell döntési változói a különféle élelmiszerek megvásárolható csomagjainak száma:

Néhány megvásárolható j élelmiszer csomagjainak neve Vásárlás [j] lesz; bármely elfogadható megoldásnak f_min [j] és f_max [j] között kell lennie .

J élelmiszer vásárlásának teljes költsége csomagonkénti költség, költség [j], a csomagok számának a szorosa. Vásárlás [j]. A minimalizálandó cél ennek a terméknek az összes élelmiszerre vonatkozó összege j:

minimalizálja az összköltséget: összegköltség [j] * Vásárlás [j];

Hasonlóképpen, az j táplálék által szállított i tápanyag mennyisége a csomagolásonkénti tápanyag, amt [i, j], szorozva a Buy [j] csomag számát. Az általam szállított tápanyag teljes mennyisége a termék összes j élelmiszerének összege:

A modell elkészítéséhez csak azt kell megadnunk, hogy minden ilyen összegnek a megfelelő határok között kell lennie. Megkezdődik a kényszernyilatkozatunk

diéta alatt áll :

mondani, hogy az étrendnek [i] nevű korlátozást kell előírni a NUTR minden i tagjára. A deklaráció további része megadja az i tápanyagra vonatkozó korlát algebrai megállapítását: a változóknak meg kell felelniük

Az ilyen "kettős egyenlőtlenséget" nyilvánvaló módon értelmezik: a középen lévő összeg értékének n_min [i] és n_max [i] között kell lennie. A következő a teljes modell.

param f_max> = f_min [j];

param n_max > = n_min [i];

Megfelelő adatok megadásával bármelyik lineáris programot meg tudjuk oldani, amely megfelel a fenti modellnek. Kezdjük a dokumentum elejétől származó adatok felhasználásával. Az alábbiak az adatok AMPL formátumban.

halmaz NUTR: = A B1 B2 C;

készlet FOOD: = MARHA CHK FISH HAM MCH MTL SPG TUR;

param: költség f_min f_max: =

param: n_min n_max: =

MARHA 60 20 10 15

HAL 8 10 15 10

HAM 40 40 35 10

MCH 15 35 15 15

MTL 70 30 15 15

SPG 25 50 25 15

TUR 60 20 15 10;

Az f_min és n_min értéke megegyezik az eredetileg megadott értékkel, míg az f_max és n_max értéke egyelőre olyan nagy értékekre van állítva, amelyek nem befolyásolják az optimális megoldást. Az amt táblázatban a (tr) jelölés azt jelzi, hogy "átültettük" a táblázatot, így az oszlopok az első indexnek (tápanyagok), a sorok pedig a másodiknak (élelmiszerek) felelnek meg. Alternatív megoldásként megváltoztathattuk volna a modellt

ebben az esetben amt [j, i] -et kellett volna írnunk a kényszerbe.

Tegyük fel, hogy a modell és az adatok a diet.mod és a diet.dat fájlokban vannak tárolva. Ezután az AMPL-t a következőképpen használják ezeknek a fájloknak az olvasására és az így kapott lineáris program megoldására:

ampl: modell étrend.mod;

ampl: adatdiéta.dat;

CPLEX 2.0: optimális megoldás; 88.2. cél

2 ismétlés (1 az I. fázisban)

ampl: display Vásárlás;

Tegyük fel, hogy a következő fejlesztéseket szeretnénk végrehajtani. A változatosság elősegítése érdekében a heti étrendnek 2-10 csomagot kell tartalmaznia minden egyes ételből. Az egyes csomagok nátrium- és kalóriamennyiségét is megadják; az összes nátrium nem haladhatja meg a 40 000 mg-ot, az összes kalória pedig 16 000 és 24 000 között lehet. Mindezek a változtatások az adatok néhány módosításával elvégezhetők. Az alábbiakban bemutatjuk az új AMPL-adatsort a változtatások után.

halmaz NUTR: = A B1 B2 C NA CAL;

készlet FOOD: = MARHA CHK FISH HAM MCH MTL SPG TUR;

param: költség f_min f_max: =

param: n_min n_max: =

16000 24000 CAL;

A C B1 B2 NA CAL: =

MARHA 60 20 10 15 938 295

8 0 20 20 2180 770 CHK

HAL 8 10 15 10 945 440

HAM 40 40 35 10 278 430

MCH 15 35 15 15 1182 315

MTL 70 30 15 15 896 400

SPG 25 50 25 15 1329 370

TUR 60 20 15 10 1397 450;

Az új adatokat a diet2.dat fájlba helyezve újra futtathatjuk az AMPL-t:

ampl: modell étrend.mod;

ampl: data diet2.dat;

CPLEX 2.0: megvalósíthatatlan probléma

7 ismétlés (7 az I. fázisban)

A megvalósíthatatlan üzenet azt mondja nekünk, hogy túl szorosan korlátoztuk az étrendet; semmilyen módon nem lehet teljesíteni az összes korlátozást.

Az AMPL vizsgálja meg a megoldó által előállított értékek sokaságát, miközben megpróbál megoldást találni. A megoldhatatlanság forrását megkereshetjük a megoldáshoz társított értékek megjelenítésével.

ampl: display diet.lb, diet.body, diet.ub;

: diéta.lb diéta.testdiéta.ub: =

A 700 1993.09 20000

B1 700 841,091 20000

B2 700 601,091 20000

C 700 1272,55 20000

CAL 16000 17222,9 24000

NA 0 40000 40000

A diet.lb és a diet.ub értéke az "alsó határok" és a "felső határok" a korlátok étrendjében szereplő változók összegénél [i] ebben az esetben csak az n_min [i] és az n_max [i értékek ]; diet.body a változók aktuális összege. Láthatjuk, hogy az étrend nem szolgáltat elegendő B2-vitamint, míg a nátrium (NA) mennyisége elérte felső határát. Ha 50 000 mg-ra lazítjuk a nátrium-határértéket, megvalósítható megoldás válik lehetővé:

ampl: legyen n_max ["NA"]: = 50000; megoldani;

CPLEX 2.0: optimális megoldás; objektív 118.0594032

11 ismétlés (7 az I. fázisban)

Ez legalább kezdet egy kellemes étrend felé, bár 118,06 dollárt kell költenünk, szemben az eredeti, kevésbé korlátozott esetek 88,20 dollárjával. Nyilvánvaló, hogy a modell felállítása után könnyű lenne sok más lehetőséget kipróbálni. A megoldás még mindig kiábrándító szempontja, hogy 5,36061 csomag marhahúst és 9,30365 spagettit kell vásárolni. Mi van, ha csak egész csomagokat tudunk vásárolni? Gondolhatja, hogy az optimális értékeket egész számokra kerekíthetjük, de ezt nem olyan könnyű megvalósítható módon megtenni. A kényszerhatárok optimális megjelenítése.

ampl: display diet.lb, diet.body, diet.ub;

: diéta.lb diéta.testdiéta.ub: =

A 700 1956,29 20000

B1 700 1036,26 20000

B2 700 700 20000

C 700 1682,51 20000

CAL 16000 19794,6 24000

NA 0 50000 50000

látjuk, hogy például 6 csomag marhahús és 10 csomag spagetti megsérti a nátrium-határértéket, míg 5 csomag marhahús és 9 csomag spagetti elégtelen B2-vitamint biztosít. Még ha találunk is egy közeli, egész számot tartalmazó megoldást, amely kielégíti a megszorításokat, nem lenne garancia arra, hogy ez lenne a legkevésbé költséges egész egész megoldás. Az AMPL előírja, hogy az integritáskorlátozást közvetlenül a változók deklarációjába kell tenni:

var Buy integer> = f_min [j],

Ez azonban csak akkor segít, ha olyan megoldót használ, amely képes kezelni az úgynevezett egész programokat. Általánosságban az integritás és más "diszkrét" korlátozások miatt a modell sokkal nehezebben megoldható.