AMPL модел за проблема с диетата

модел

1. Описание на проблема

Помислете за проблема с избора на готови храни, които да отговарят на определени хранителни изисквания. Да предположим, че готовите вечери от следните видове са налични за следните цени на пакет:

Макарони и сирене

Тези вечери осигуряват следните проценти на опаковка от минималните дневни нужди за витамини А, С, В1 и В2.

Проблемът е да се намери най-евтината комбинация от опаковки, които да отговарят на едноседмичните изисквания, т.е. най-малко 700% от дневните нужди за всяко хранително вещество.

2. Формулировка на LP

Нека напишем X BEEF за броя пакети телешка вечеря, които трябва да бъдат закупени, X CHK за броя пакети телешка вечеря, които ще бъдат закупени и т.н. Тогава общите разходи за диетата ще бъдат:

3,19 X ГОЕВЕ + 2,59 X CHK + 2,29 X РИБА + 2,89 X HAM +

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

Общият процент на нуждите от витамин А се дава по подобна формула, с изключение на това, че X BEEF, X CHK и т.н. се умножават по процента на опаковка вместо по разходите за опаковка:

Общ процент изпълнени дневни нужди от витамин А =

60 X ГОЕВЕ + 8 X CHK + 8 X РИБА + 40 X HAM +

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

Тази сума трябва да бъде по-голяма или равна на 700 процента. Съществува подобна формула за всеки от останалите витамини и всеки от тях също трябва да бъде по-голям или равен на 700 процента.

Събирайки всичко това, имаме следната линейна програма:

3,19 X ГОЕВЕ + 2,59 X CHK + 2,29 X РИБА + 2,89 X HAM +

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

60 X ГОЕВЕ + 8 X CHK + 8 X РИБА + 40 X HAM +

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

20 X ГОЕВЕ + 0 X CHK + 10 X РИБА + 40 X HAM +

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

10 X ГОЕВЕ + 20 X CHK + 15X РИБА + 35 X HAM +

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

15 X ГОЕВЕ + 20X CHK + 10 X РИБА + 10 X HAM +

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

X ГЕЛЕВО, X CHK, X РИБА, X HAM, X MCH, X MTL, X SPG, X TUR> = 0

Друг начин за описване на тази линейна програма е както следва:

Дадено: F, набор от храни

N, набор от хранителни вещества

c j = цена на пакет от вечеря j, за всеки j във F

p i, j = процент на хранително вещество i на опаковка от вечеря j, за всяко i в N, j в F

l j = минимална седмична потребност от хранителни вещества j, за всеки j във F

Променливи за вземане на решение: X j = пакети от вечеря j, които трябва да бъдат закупени, за всеки j във F

Този модел се занимава с две неща: хранителни вещества и храни. По този начин започваме с AMPL модел, като декларираме набори от всеки:

След това трябва да посочим номерата, изисквани от модела. Със сигурност трябва да се даде положителен разход за всяка храна:

Цената на определена храна се записва като, да речем, цена [BEEF], въпреки че препратките към конкретни стойности в модел на LP обикновено са по отношение на индекси като j, а не на конкретни членове като BEEF .

За да направим модела малко по-общ от LP досега, ще уточним също, че за всяка храна има долна и горна граница на броя на опаковките в диетата:

param f_max> = f_min [j];

Забележете, че се нуждаем от фиктивен индекс j, за да прегазим FOOD в декларацията на f_max, за да кажем, че максимумът за всяка храна трябва да бъде по-голям или равен на съответния минимум.

Също така ще сметнем за удобно да посочим подобни долни и горни граници на количеството на всяко хранително вещество в диетата:

param n_max > = n_min [i];

И накрая, за всяка комбинация от хранително вещество и храна се нуждаем от число, което представлява количеството на всяко хранително вещество i в опаковка от храната. Такъв „продукт“ от два комплекта се пише, като се изброят и двата:

Позоваванията на този параметър изискват два индекса. Например, amt [i, j] е количеството хранително вещество i в опаковка от j .

Променливите на решение за този модел са броят на пакетите за закупуване на различните храни:

Броят на опаковките на някои храни j, които трябва да бъдат закупени, ще се нарича Buy [j]; във всяко приемливо решение ще трябва да лежи между f_min [j] и f_max [j] .

Общите разходи за закупуване на храна j са разходите за опаковка, разходите [j], умножени по броя на пакетите. Купете [j]. Целта, която трябва да бъде сведена до минимум, е сумата от този продукт за всички храни j:

минимизиране на total_cost: сума на разходите [j] * Купете [j];

По същия начин количеството хранително вещество i, доставено от храна j, е хранителното вещество на опаковка, amt [i, j], умножено по броя на опаковката Buy [j]. Общото количество хранителни вещества, които съм доставил, е сумата от този продукт за цялата храна j:

За да завършим модела, трябва само да уточним, че всяка такава сума трябва да лежи между подходящите граници. Нашата декларация за ограничение започва

при спазване на диета :

да се каже, че трябва да се наложи ограничение с име диета [i] за всеки член i от NUTR. Останалата част от декларацията дава алгебричното изявление на ограничението за хранително вещество i: променливите трябва да отговарят

"Двойно неравенство" като това се интерпретира по очевидния начин: стойността на сумата в средата трябва да лежи между n_min [i] и n_max [i]. Следва пълният модел.

param f_max> = f_min [j];

param n_max > = n_min [i];

Като посочим подходящи данни, можем да решим всяка от линейните програми, които съответстват на горния модел. Нека започнем, като използваме данните от началото на този документ. По-долу са данните във формат AMPL.

задайте NUTR: = A B1 B2 C;

задайте ХРАНА: = ГОВЕЖДО ЧЕК РИБЕН ШУМ МЧ MTL СПГ ТУР;

param: цена f_min f_max: =

param: n_min n_max: =

ГОЛЯДО 60 20 10 15

РИБИ 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;

Стойностите на f_min и n_min са дадени първоначално, докато f_max и n_max са зададени за момента на големи стойности, които няма да повлияят на оптималното решение. В таблицата за amt нотацията (tr) показва, че сме „транспонирали“ таблицата, така че колоните съответстват на първия индекс (хранителни вещества), а редовете на втория (храни). Друга възможност е да сменим модела, за да кажем

в този случай трябваше да напишем amt [j, i] в ограничението.

Да предположим, че моделът и данните се съхраняват съответно във файловете diet.mod и diet.dat. Тогава AMPL се използва, както следва, за четене на тези файлове и за решаване на получената линейна програма:

ampl: модел diet.mod;

ampl: данни diet.dat;

CPLEX 2.0: оптимално решение; цел 88.2

2 повторения (1 във фаза I)

ampl: дисплей Купи;

Сега да предположим, че искаме да направим следните подобрения. За да се популяризира разнообразието, седмичната диета трябва да съдържа между 2 и 10 пакета от всяка храна. Посочва се и количеството натрий и калориите във всяка опаковка; общият натрий не трябва да надвишава 40 000 mg, а общите калории трябва да бъдат между 16 000 и 24 000. Всички тези промени могат да бъдат направени чрез няколко модификации на данните. По-долу е новият набор от данни AMPL след промените.

задайте NUTR: = A B1 B2 C NA CAL;

задайте ХРАНА: = ГОВЕЖДО ЧЕК РИБЕН ШУМ МЧ MTL СПГ ТУР;

param: цена f_min f_max: =

param: n_min n_max: =

CAL 16000 24000;

A C B1 B2 NA CAL: =

ГОЛЯДО 60 20 10 15 938 295

CHK 8 0 20 20 2180 770

РИБИ 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;

Поставяйки тези нови данни във файл diet2.dat, можем да стартираме AMPL отново:

ampl: модел diet.mod;

ampl: данни diet2.dat;

CPLEX 2.0: неизпълним проблем

7 повторения (7 във фаза I)

Неизпълнимото съобщение ни казва, че сме ограничили диетата твърде строго; няма начин цялото ограничение да бъде изпълнено.

AMPL ни позволява да разгледаме различни стойности, създадени от решаващ инструмент, докато се опитва да намери решение. Можем да потърсим източника на невъзможността, като покажем някои стойности, свързани с това решение.

ampl: показване на diet.lb, diet.body, diet.ub;

: diet.lb diet.body diet.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

Стойността за diet.lb и diet.ub са "долните граници" и "горните граници" на сумата от променливите в диетата за ограничения [i], в този случай, само стойностите n_min [i] и n_max [i ]; diet.body е текущата сума на променливите. Можем да видим, че диетата не осигурява достатъчно витамин В2, докато количеството натрий (NA) е достигнало горната си граница. Ако смекчим ограничението на натрия до 50 000 mg, става възможно решение:

ampl: нека n_max ["NA"]: = 50000; решаване;

CPLEX 2.0: оптимално решение; обектив 118.0594032

11 повторения (7 във фаза I)

Това е поне начало към вкусна диета, въпреки че трябва да похарчим $ 118,06, в сравнение с $ 88,20 за оригиналния, по-малко ограничен случай. Ясно е, че сега, когато моделът е настроен, би било лесно да се изпробват много други възможности. Веднъж все още разочароващ аспект на решението е необходимостта да се купят 5.36061 опаковки говеждо месо и 9.30365 спагети. Ами ако можем да закупим само цели пакети? Може би си мислите, че можем просто да закръглим оптималните стойности до цели числа, но не е толкова лесно да го направим по осъществим начин. Показване на границите на ограничението в оптималното.

ampl: показване на diet.lb, diet.body, diet.ub;

: diet.lb diet.body diet.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

виждаме, че например 6 пакета телешко месо и 10 пакета спагети ще нарушат лимита на натрий, докато 5 пакета говеждо месо и 9 пакета спагети осигуряват недостатъчно витамин В2. Дори и да можем да намерим близко изцяло цяло решение, което отговаря на ограниченията, няма да има гаранция, че то ще бъде най-евтиното решение за цяло число. AMPL предвижда поставянето на ограничението на интегралността директно в декларацията на променливите:

var Купете цяло число> = f_min [j],

Това обаче ще помогне само ако използвате решател, който може да се справи с така наречените цяло число програми. Като цяло интегралността и други „дискретни“ ограничения правят модела много по-труден за решаване.