Линейное программирование задачи с решением задача о диете

В поисках оптимальной диеты методом линейного программирования -2

Разработка под Windows, Математика, Python

Линейное программирование задачи с решением задача о диете

Вопрос диеты всегда будоражил умы слабого пола и не только. Не взирая на большое количество рекомендаций диетологов, вопрос диеты для многих так и остаётся нерешённым. В таких условиях хочу предложить альтернативный вариант, особо не привлекая диетологию, а опираясь исключительно на линейное программирование, надеюсь, неплохой повод уже серьёзно задуматься о проблеме.

Должна ли диета быть экономной?

Для поддержания нормальной жизнедеятельности человеку необходимо потреблять в день не менее 118 г белков, 56 г жиров, 500 г углеводов и 28 г минеральных солей. Эти питательные вещества содержатся в разных количествах и разных пищевых продуктах.

В таблице приведено количество питательных веществ в различных продуктах в г/кг и цена этих продуктов за 1 кг. Необходимо составить дневной рацион, содержащий минимальную суточную норму питательных веществ при минимальной их стоимости.

Обозначив через: Х1 –количество мяса; Х2- количество рыбы; Х3- количество молока; Х4- количество масла; Х5- количество сыра; Х6- количество крупы; Х7- количество картофеля, потребляемых человеком в день. Можем составить уравнение общей стоимости F питания в день:
F=333*X1+308*X2+52*X3+400*X4+450*X5+56*X6+25*X7

Нам нужно найти минимум F.
Суммарное количество белков в рационе человека должно быть не меньше 118 г. Отсюда,
180*X1+190*X2+30*X3+10*X4+260*X5+130*X6+21*X7?118

Такие же неравенства составляем для жиров, углеводов и солей. Имеем:
20*X1+3*X2+40*X3+865*X4+310*X5+30*X6+2*X7?56
50*X3+6*X4+20*X5+650*X6+200*X7?500
9*X1+10*X2+7*X3+12*X4+60*X5+20*X6+10*X7?28

Решим задачу на Python

from cvxopt.modeling import variable, op
import time
start = time.time()
x = variable(7, ‘x’)
z=(333*x[0] + 308*x[1] +52* x[2] +400*x[3] +450*x[4] +56* x[5]+20*x[6])
mass1 =(- (180*x[0] + 190*x[1] +30* x[2] +10*x[3] +260*x[4] +130* x[5]+21*x[6]) <= -118)
mass2 =(- (20*x[0] + 3*x[1] +40* x[2] +865*x[3] +310*x[4] +30* x[5]+2*x[6]) <= -56)
mass3 =(- (50* x[2] +6*x[3] +20*x[4] +650* x[5]+200*x[6]) <= -500)
mass4 =(- (9*x[0] + 10*x[1] +7* x[2] +12*x[3] +60*x[4] +20* x[5]+10*x[6]) <= -28)
x_non_negative = (x >= 0)
problem =op(z,[mass1,mass2,mass3,mass4 ,x_non_negative])
problem.solve(solver=’glpk’)
problem.status
print(“Результат:”)
print(round(1000*x.value[0],1),’-грамм мяса, затраты -‘,round(x.value[0]*333,1),’руб.’)
print(round(1000*x.value[1],1),’-грамм рыбы, затраты -‘,round(x.value[1]*308,1),’руб.’)
print(round(1000*x.value[2],1),’-миллилитров молока, затраты -‘,round(x.value[2]*52,1),’руб.’)
print(round(1000*x.value[3],1),’-грамм масла, затраты -‘,round(x.value[3]*400,1),’руб.’)
print(round(1000*x.value[4],1),’-грамм сыр, затраты -‘,round(x.value[4]*450,1),’руб.’)
print(round(1000*x.value[5],1),’-грамм крупы, затраты -‘,round(x.value[5]*56,1),’руб.’)
print(round(1000*x.value[6],1),’-грамм картофеля, затраты -‘,round(x.value[6]*25,1),’руб.’)
print(round(problem.objective.value()[0],1),”- стоимость рациона одного человека в день”)
stop = time.time()
print (“Время :”,round(stop-start,3))

Следует отметить некоторые особенности написания программы с использованием модуля cvxopt. Modeling: все переменные сохраняются в списках, а индексы списков начинаются не с 1, а с ; в условиях, которые записываются в виде нестрогих неравенств должно быть установлено ограничение сверху, поэтому, для перехода от ограничения снизу, обе части неравенств умножены на -1.

Результат:

0.0 -грамм мяса, затраты — 0.0 руб.
0.0 -грамм рыбы, затраты — 0.0 руб.
0.0 -миллилитров молока, затраты — 0.0 руб.
38.0 -грамм масла, затраты — 15.2 руб.
-0.0 -грамм сыр, затраты — -0.0 руб.
679.3 -грамм крупы, затраты — 38.0 руб.
1395.9 -грамм картофеля, затраты — 34.9 руб.
81.1 — стоимость рациона одного человека в день
Время: 0.09

Анализ результатов показывает: ни мяса, ни рыбы- крупа, масло и картофель — вот такое линейное программирование. Вряд ли такой рацион можно рассматривать серьёзно, но для общности анализа пусть будет. А мы продолжим поиск.

Должна ли диета быть калорийной?

Для определённости предположим, что в качестве исходных продуктов рассмотрим хлеб, мясо, сыр, бананы, огурцы, помидоры, виноград – всего семь продуктов. В качестве питательных веществ – белки, жира, углеводы.

Калорийность одной весовой единицы каждого из продуктов следующая: c1=2060, c2=2430, c3=3600, c4=890, c5=140, c6=230, c7=650.

Содержание питательных веществ в продуктах питания поместим в следующую таблицу.

Минимальная суточная потребность человека в питательных веществах следующая: в белках b1=100, в жирах b2=70, в углеводах b3=400.

Не уменьшая общности решаемой задачи, можно считать, что калорийность продуктов измеряется в килокалориях/кг, суточная потребность в питательных веществах – в граммах, а содержание питательных веществ в продуктах– в граммах/кг. В указанных условиях становится возможным выполнить дополнительную проверку сформированных условий задачи на основе рассмотрения физической размерности целевой функции и ограничений.

Обозначив через: x1 –количество хлеба; x2- количество мяса; x3- количество сыра; x4- количество бананов; x5- количество огурцов; x6- количество помидоров; x7- количество винограда, потребляемых человеком в день в килограммах.

Можем составить уравнение общей калорийности F питания в день:
F=2060*x1 + 2430*x2 +3600* x3+890*x4 +140*x5 +230* x6+650*x7

Нам нужно найти минимум F.
Суммарное количество белков в рационе человека должно быть не меньше 100 г. Отсюда
61*x1+ 220*x2 +230* x3 +15*x4 +8*x5 +11* x6+6*x7 ?100

Такие же неравенства составляем для жиров и углеводов. Имеем:
12*x1 +172*x2 +290* x3+1*x4 +1*x5 +2* x6+2*x7 ?70
420*x1 +0*x2 +0* x3 +212*x4+26*x5 +38* x6+155*x7 ?400

Решим задачу на Python

from cvxopt.modeling import variable, op
import time
start = time.time()
x = variable(7, ‘x’)
z=(333*x[0] + 308*x[1] +52* x[2] +400*x[3] +450*x[4] +56* x[5]+20*x[6])
mass1 =(- (180*x[0] + 190*x[1] +30* x[2] +10*x[3] +260*x[4] +130* x[5]+21*x[6]) <= -118)
mass2 =(- (20*x[0] + 3*x[1] +40* x[2] +865*x[3] +310*x[4] +30* x[5]+2*x[6]) <= -56)
mass3 =(- (50* x[2] +6*x[3] +20*x[4] +650* x[5]+200*x[6]) <= -500)
mass4 =(- (9*x[0] + 10*x[1] +7* x[2] +12*x[3] +60*x[4] +20* x[5]+10*x[6]) <= -28)
x_non_negative = (x >= 0)
problem =op(z,[mass1,mass2,mass3,mass4 ,x_non_negative])
problem.solve(solver=’glpk’)
problem.status
print(“Результат:”)
print(round(1000*x.value[0],1),’-грамм хлеба’)
print(round(1000*x.value[1],1),’-грамм мяса’)
print(round(1000*x.value[2],1),’-грамм сыра’)
print(round(1000*x.value[3],1),’-грамм бананов’)
print(round(1000*x.value[4],1),’-грамм огурцов’)
print(round(1000*x.value[5],1),’-грамм помидоров’)
print(round(1000*x.value[6],1),’-грамм винограда’)
print(round(problem.objective.value()[0],1),”-Калорийность рациона одного человека в день”)
stop = time.time()
print (“Время :”,round(stop-start,3))

Результат:

0.0 -грамм хлеба
211.5 -грамм мяса
109.4 -грамм сыра
1886.8 -грамм бананов
0.0 -грамм огурцов
0.0 -грамм помидоров
0.0 -грамм винограда
2587.1 -килокалорий -калорийность
рациона одного человека в день
Время: 0.06

Анализ результатов решения показывает, что для удовлетворения суточной потребности в питательных веществах (белки, жиры, углеводы), следует использовать 211 грамм мяса баранины, 109 грамм сыра, 1887 грамм бананов, совсем отказаться от хлеба, огурцов, помидоров и винограда. При этом общая калорийность найденной оптимальной диеты будет равна 2587 килокалорий, что вполне соответствует малоактивному образу жизни без существенных физических нагрузок. Напомним, что согласно медицинским данным, энергетические затраты работников умственного труда (программисты, юристы, врачи, педагоги, бухгалтера) лежат в пределах 3000 килокалорий.

Содержательный анализ результатов задачи об оптимальной диете явно выявляет недостатки рассмотренной математической модели. С одной стороны, для вкусной и питательной пищи не всегда приемлемым оказывается ограниченный рацион продуктов питания, который совершенно игнорирует индивидуальные предпочтения при выборе отдельных продуктов. С другой стороны, найденное оптимальное решение (мясо + сыр + бананы) для многих покажется однообразным и способным повергнуть в уныние даже пациентов больницы. Наконец, рассмотренная математическая модель задачи об оптимальной диете не учитывает суточную потребность в витаминах и микроэлементах, учет которых может существенно повлиять на выбор оптимального состава продуктов.

Что можно предложить заинтересованному читателю?

Заинтересованным читателям данной публикации в качестве упражнения предлагается рассмотреть собственную постановку задачи об оптимальной диете, отражающую их индивидуальные предпочтения в выборе тех или иных продуктов. При этом условия задачи можно несколько изменить, включив в качестве одного из ограничений общую калорийность диеты, а в качестве целевой функции рассмотреть общую массу наиболее предпочтительных продуктов.

Решение задачи на Python (только как пример)

from cvxopt.modeling import variable, op
import time
start = time.time()
x = variable(7, ‘x’)
z=( x[0] + x[1] +x[2] +x[3] +x[4] +x[5]+x[6])
mass1 =(- (61*x[0] + 220*x[1] +230* x[2] +15*x[3] +8*x[4] +11* x[5]+6*x[6]) <= -100)
mass2 =(- (12*x[0] +172*x[1] +290* x[2] +1*x[3] +1*x[4] +2* x[5]+2*x[6]) <= -70)
mass3 =(- (420*x[0] +0*x[1] +0* x[2] +212*x[3] +26*x[4] +38* x[5]+155*x[6]) <= -400)
mass4 =(-( 2060*x[0] + 2430*x[1] +3600* x[2] +890*x[3] +140*x[4] +230* x[5]+650*x[6]) <= -3000)
x_non_negative = (x >= 0)
problem =op(z,[mass1,mass2,mass3, mass4,x_non_negative])
problem.solve(solver=’glpk’)
problem.status
print(“Результат:”)
print(round(1000*x.value[0],1),’-грамм хлеба’)
print(round(1000*x.value[1],1),’-грамм мяса’)
print(round(1000*x.value[2],1),’-грамм сыра’)
print(round(1000*x.value[3],1),’-грамм бананов’)
print(round(1000*x.value[4],1),’-грамм огурцов’)
print(round(1000*x.value[5],1),’-грамм помидоров’)
print(round(1000*x.value[6],1),’-грамм винограда’)
print(round(problem.objective.value()[0],1),”-килограмм-общая масса продуктов из n рациона одного человека в день”)
stop = time.time()
print (“Время :”,round(stop-start,3))

Результат:

952.4 -грамм хлеба
0.0 -грамм мяса
288.4 -грамм сыра
0.0 -грамм бананов
0.0 -грамм огурцов
0.0 -грамм помидоров
0.0 -грамм винограда
1.2 -килограмм-общая масса продуктов из
рациона одного человека в день
Время: 0.051

Это мне напоминает рацион долгожителей высокогорных районов лепёшки на козьем молоке и сыр того же происхождения, но воспоминания скорее всего обманчивы, поскольку список продуктов явно не оттуда.

Вместо вывода

Несмотря на выявленные недостатки рассмотренной математической модели задачи об оптимальной диете, найденное оптимальное решение в точности соответствует исходной постановке задачи. Это свидетельствует о достаточно высокой точности решения задач линейного программирования при помощи библиотеки cvxopt. Modeling Python.
Интерфейс программы настолько простой и наглядный, что не требует каких-либо дополнительных навыков. Достаточно скачать и установить последнюю версию Python, например, с сайта [1], а библиотеку cvxopt с сайта [2]. Затем создать файл с расширением py и поместить в него любую из приведенных в статье программ, предварительно модифицировав её под свою задачу с новой функцией цели и ограничениями.

Ссылки

Python.
Windows binaries for python.

Источник

МОСКОВСКИЙ ФИНАНСОВО-ЮРИДИЧЕСКИЙ УНИВЕРСИТЕТ

КИРОВСКИЙ ФИЛИАЛ

Методы анализа данных

Методическое пособие и контрольные задания по темам

«Математическое программирование» c использованием табличного процессора Microsoft Excel

для студентов заочной формы обучения направления «Экономика»

Киров 2014г.

Методы линейного программирования получили широкое распространение при решении практических задач, связанных с составлением производственных планов, графиков обслуживания потребителей, оптимальным распределением ресурсов, транспортных потоков, размещением оборудования, с составлением различного рода смесей и т.д.

Методическое пособие содержит краткие теоретические сведения, необходимые для выполнения лабораторных работ, и практический материал для решения задач линейного программирования с использованием возможностей табличного процессора Excel. На конкретных типовых примерах подробно разобраны порядок выполнения лабораторных работ по линейной оптимизации.

В целях закрепления пройденного материала в конце каждой темы приведены задания для самостоятельной работы. Каждое задание содержит 5 вариантов. Для выполнения работы необходимо знание соответствующего теоретического материала.

Задачи линейного программирования

Линейное программирование (ЛП) — это раздел математики, занимающийся решением таких задач на отыскание наибольших и наименьших значений, для которых методы математического анализа оказываются непригодными. Другими словами термин «линейное программирование» характеризует определение программы (плана) работы конкретного экономического объекта на основе выявления линейных связей между его элементами. Задачей линейного программирования является нахождение оптимального, т. е. наилучшего, плана при заданной системе налагаемых на решение ограничений.

К классу задач линейного программирования относится большое количество разнообразных задач планирования и управления, как, например:

1) нахождение оптимального плана выпуска продукции (оптимальное распределение ресурсов);

2) оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям);

3) определение оптимального рациона (оптимизация состава химической смеси);

4) транспортная задача (оптимальное распределение потоков товарных поставок по транспортной сети);

5) задача о размещении производства (планирование с учётом затрат на производство и транспортировку продукции);

6) задача о назначениях (оптимальное распределение различных видов транспортных средств) и др.

Задачей линейного программирования — задача оптимизации (т. е. максимизации или минимизации) линейной функции

(1)

при наличии линейных ограничений

(2)

Другими словами, необходимо найти такое решение системы (2), при котором линейная функция (1) принимает оптимальное значение.

В этой задаче число неизвестных должно быть больше числа условий , иначе будет нарушено условие единственности решения, выполняющееся в оптимизационной задаче.

Задача об оптимальном составе смеси (задача составления рациона, задача о диете)

К группе задач о смесях относят задачи по отысканию наиболее экономичного набора из определённых ингредиентов (пищевых продуктов, руды, нефти и др.), обеспечивающих получение смеси с заданными свойствами (ограничения на физический или химический состав смеси и на наличие необходимых материалов). Иными словами, получаемые смеси должны иметь в своём составе различных компонентов в определённых количествах, а сами компоненты являются составными частями исходных материалов.

Задача 1. Для откорма животных на ферме в их ежедневный рацион необходимо включить не менее 33-х единиц питательного вещества , 23-х единиц вещества и 12-ти единиц вещества . Для откорма используется 3 вида кормов. Данные о содержании питательных веществ и стоимости весовой единицы каждого корма даны в таблице 1.

Таблица 1

Требуется составить наиболее дешёвый рацион, при котором каждое животное получило бы необходимые количества питательных веществ , и .

Математическая постановка задачи 1. Пусть , , — количества кормов I, II, III видов, включаемые в ежедневный рацион ( , ). Тогда должно быть:

(3)

При этом линейная функция (стоимость рациона)

(4)

Решение задачи 1 в среде Microsoft Excel.

В настоящее время одним из наиболее известных способов численного решения задач линейного программирования является использование надстройки «Поиск решения» электронных таблиц Microsoft Excel.

Теоретической основой надстройки «Поиск решения» является симплекс-метод, позволяющий находить оптимальное решение задачи планирования с помощью итерационного процесса перехода к улучшающимся планам. «Поиск решения» является дополнением Excel, т. е. может не входить в стандартный вариант установки электронных таблиц. Для его добавления достаточно воспользоваться командой Сервис®Надстройки®Поиск решения.

При решении задачи с помощью надстройки Поиск решения необходимо:

1. открыть окно Microsoft Excel;

2. заполнить ячейкиA1-А4 таблицы обозначениями , , и min соответственно (см. рисунок 1);

Рисунок 1

3. в ячейку В4 записать формулу (4) через адреса соответствующих ячеек (адреса ячеек вводятся щелчком мыши по соответствующей ячейке или набираются с клавиатуры на английской раскладке) (см. рисунок 2), нажать Enter;

Рисунок 2

4. в диапазон ячеек А7-С9 записать систему (3) через адреса соответствующих ячеек, т. е. в А7 ввести формулу , нажать Enter, в А8 ввести формулу , нажать Enter, в А9 ввести формулу , нажать Enter, в ячейки В7-В9 ввести слова не менее, в ячейки С7-С9 33, 23 и 12 соответственно (см. рисунок 3);

Рисунок 3

5. для решения поставленной задачи в меню Сервис выбрать пункт Поиск решения… (см. рисунок 4);

Рисунок 4

6. в появившемся окне Поиск решения в поле Установить целевую ячейку надо щёлкнуть по кнопке , затем в ячейке B4 и снова по кнопке ; в поле Равной установить флажок (щёлкнуть левой кнопкой мыши в соответствующем кружке) минимальному значению, в поле Изменяя ячейки щёлкнуть по кнопке , выделить мышью диапазон ячеек В1¸В3 и снова щёлкнуть по кнопке (см. рисунок 5);

Рисунок 5

7. в этом же окне Поиск решения осталось незаполненным поле Ограничения, поэтому надо нажать на копку Добавить: появится новое окно Добавление ограничения, в поле Ссылка на ячейку надо щёлкнуть по кнопке , затем выделить мышью диапазон ячеек В1¸В3 и снова щёлкнуть по кнопке , в следующем поле необходимо выбрать знак >=, нажав , затем в поле Ограничение ввести 0 (см. рисунок 6);

Рисунок 6

8. в этом же окне Добавление ограничения нажать кнопку Добавить (появится новое лось окно Добавление ограничения) и ввести новое ограничение: в поле Ссылка на ячейку надо щёлкнуть по кнопке , затем выделить мышью диапазон ячеек А7¸А9 и снова щёлкнуть по кнопке , в следующем поле необходимо выбрать знак >=, нажав , затем в поле Ограничение надо щёлкнуть по кнопке , затем выделить мышью диапазон ячеек C7¸C9 и снова щёлкнуть по кнопке (см. рисунок 7);

Рисунок 7

9. теперь все ограничения нами учтены: надо нажать кнопку ОК, после чего снова откроется диалоговое окно Поиск решения, и надо нажать кнопку Выполнить (см. рисунок 8);

Рисунок 8

10. в появившемся диалоговом окне Результаты поиска решения (в котором компьютер предлагает по умолчанию сохранить найденное решение) надо нажать кнопку ОК (см. рисунок 9).

Рисунок 9

11. Результат полученных вычислений представлен на рисунке 10.

Рисунок 10

Замечание 1. Если в неравенствах (3) знаки разные ( , , ), то ограничения в пункте 8 вносятся отдельно для каждой строки, а не через диапазон, как в примере.

Замечание 2. Если часть ограничений представляют собой неравенства другого знака (в данном случае ), то все коэффициенты и свободные члены для данных строк умножаются на и знак выставляется одинаковый для всей системы.

Замечание 3. На практике часто требуется, чтобы на переменные , , налагалось условие целочисленности (например, если какой-то продукт нельзя разрезать на части, а можно добавлять в рацион только целыми порциями), в этом случае в окне Добавление ограничения, в поле Ссылка на ячейку надо щёлкнуть по кнопке , затем выделить мышью диапазон ячеек В1¸В3 и снова щёлкнуть по кнопке , в следующем поле необходимо выбрать условие ЦЕЛ, нажав (см. рисунок 11).

Рисунок 11

Задача 2. В баре имеются три компонента: коньяк, шампанское, сок. Цель: подобрать оптимальный состав коктейля из этих трёх компонентов, если известно: 1. стоимости ингредиентов в рублях: , , ; 2. содержание алкоголя в промиллях , , ; 3. вкусовые качества в баллах , , . Крепость коктейля должна быть не меньше 0,2 промилле. Вкус должен иметь не менее 8 баллов.

Математическая постановка задачи 2. Пусть , , — доля каждого компонента в коктейле ( , ).

Тогда должно быть:

(5)

(третье условие отражает наличие в составе смеси только трёх компонентов, т. е. то, что все три компонента составляют весь коктейль в целом — 1).

При этом линейная функция (стоимость коктейля) будет иметь вид:

(6)

Решим задачу 2 в программе Microsoft Excel. Для этого:

1. надо заполнить ячейки А1-А3 таблицы обозначениями , , и min соответственно (см. рисунок 12);

Рисунок 12

2. выполнить действия, аналогичные действиям, описанным в пунктах 3–9 (с учётом Замечания 1) Задачи 1, изменяться только ссылки на ячейки (см. рисунки 13-14):

Рисунок 13 Рисунок 14

(в ячейку А7 введена формула: , в ячейку А8 введена формула: ), в результате чего окно Поиск решения будет выглядеть так, как представлено на рисунке 15, а решение задачи — на рисунке 16.

Рисунок 15 Рисунок 16

Замечание 5. Для того чтобы в решении задачи после запятой отображалось только 2 знака, надо выделить соответствующий диапазон ячеек, щёлкнуть на выделенном правой кнопкой мыши, в появившемся контекстном меню выбрать пункт Формат ячеек и на вкладке Число выбрать Числовой, указав Число десятичных знаков 2 (см. рисунок 17).

Рисунок 17

Варианты индивидуальных заданий

Решить задачу в Microsoft Excel.

Имеется продуктов , содержащих видов питательных веществ . Пусть , где ; — количество единиц -го питательного вещества в единице -го продукта; — суточная потребность (минимальная норма) организма в -м питательном веществе; — стоимость единицы -го продукта. Требуется выбрать такой суточный рацион питания (т. е. назначить количества продуктов , входящих в него), чтобы условия по питательным веществам были выполнены, а стоимость рациона была минимальной (варианты заданий даны в таблице 2).

Таблица 2

Вариант	Виды питательных веществ	Количество единиц питательных веществ в единице продукта				Минимальная норма питательных веществ	Стоимость единицы продукта
Вариант	Виды питательных веществ					Минимальная норма питательных веществ
1	3	1	–	–	9	4	6	–	–
	1	2	–	–	8
	1	6	–	–	12
2	1,2	1,4	0,8	–	1,6	3	4	5	–
	80	280	240	–	200
	5	5	100	–	10
3	26,5	7,8	0	0	21	14,4	16	12,8	10,5
	51	26	45,7	0	30
	0	0	5	72,5	500
4	1	5	–	–	10	2	3	–	–
	3	2	–	–	12
	2	4	–	–	16
	2	2	–	–	10
	1	0	–	–	1
5	0,18	0,24	1,2	–	12	1	1,1	7,5	–
	10	8	200	–	100
	15	1	1,5	–	450

Источник