Задача составления кормовой смеси или задача о диете
МОСКОВСКИЙ ФИНАНСОВО-ЮРИДИЧЕСКИЙ УНИВЕРСИТЕТ
КИРОВСКИЙ ФИЛИАЛ
Методы анализа данных
Методическое пособие и контрольные задания по темам
«Математическое программирование» 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 | ||||||
Источник
Бройлерное хозяйство птицеводческой фермы насчитывает 20 000 цыплят, которые выращиваются до 8-недельного возраста и после соответствующей обработки поступают в продажу. Недельный расход корма в среднем (за 8 недель) составляет 500г = 0.5 кг.
Для того, чтобы цыплята достигли к 8-й неделе необходимого веса, кормовой рацион должен удовлетворять определённым требованиям по питательности. Этим требованиям могут соответствовать смеси различных видов кормов, или ингредиентов.
В табл. приведены данные, характеризующие содержание (по весу) питательных веществ в каждом из ингредиентов и удельную стоимость каждого ингредиента. Смесь должна содержать:
не менее 0.8% кальция (от общего веса смеси)
не менее 22% белка (от общего веса смеси)
не более 5% клетчатки (от общего веса смеси )
Требуется определить количество (в кг) каждого из трёх ингредиентов, образующих смесь минимальной стоимости, при соблюдении требований к общему расходу кормовой смеси и её питательности.
| Ингредиент | Содержание питательных веществ (кг/ингредиента) | Стоимость (руб./кг) | |||
| Кальций | Белок | Клетчатка | |||
| Известняк Зерно Соевые бобы | 0.38 0.001 0.002 | – 0.09 0.002 | – 0.02 0.08 | 0.4 0.15 0.40 |
Математическая формулировка задачи. Введём следующие обозначения:
X 1 – содержание известняка в смеси (кг);
Х2 – содержание зерна в смеси (кг);
Х3 – содержание соевых бобов в смеси (кг);
Общий вес смеси, еженедельно расходуемый на кормление цыплят:
20 000 х 0.5 = 10 000 кг.
Ограничения, связанные с содержанием кальция, белка и клетчатки в кормовом рационе, имеют вид:
0.38X1 + 0.001Х2 + 0.002Х3 ≥ 0.008 х 10 000,
0.09Х2 + 0.50Х3 ≥ 0.22 х 10 000,
0.02Х2+ 0.08Х3 ≤ 0.05 х 10 000.
Окончательный вид математической формулировки задачи:
min f(X) = 0.04 x1 + 0.15Х2 +0,40Х3
при ограничениях
Х1+Х2+Х3= 10 000
0.38Х1 + 0.001Х2 + 0.002Х3 ≥ 80
0.09Х2+ 0.50Х3 ≥ 2200
0.02Х2+ 0.08Х3 ≤ 500
Xj > 0, j = 1, 2, 3
Задача о составлении рациона (задача о диете, задача о смесях)
Имеется два вида продукции П1 и П2, содержащие питательные вещества S1, S2, S3, S4 (жиры, белки, углеводы, витамины). Содержание числа единиц питательных веществ в единице каждого вида продукции и необходимый минимум питательных веществ приведены в табл. 2.
Таблица 2
| Питательные вещества | Число единиц питательных веществ в единице продукции | Необходимый минимум питательных веществ |
| П1 | П2 | |
| S1 | ||
| S2 | ||
| S3 | ||
| S4 |
Стоимость единицы продукции П1 и П2 соответственно равна 3 и 4 д.е.
Решение. Обозначим через х1 и х2 – количество продукции П1 и П2, входящей в дневной рацион. Тогда общая стоимость рациона составит (д.е.)
F = 3×1 + 4×2. (5)
С учетом необходимого минимума питательных веществ составим систему ограничений. Рацион включает (x1 + 2×2) единиц питательного вещества S1, (3×1 + 2×2) единиц питательного вещества S2, (2×1 + x2) единиц питательного вещества S3 и (2×1 + 2×2) единиц питательного вещества S4. Так как содержание питательных веществ S1, S2, S3, S4 в рационе должно быть не менее 10, 8, 9, 11 единиц, соответственно, то получим систему ограничений неравенств:
Итак, экономико-математическая модель задачи: составить дневной рацион , удовлетворяющий системе ограничений (6), при котором функция (5) принимает минимальное значение.
Сформулируем данную задачу в общей постановке.
Обозначим через xj (j = 1, 2,…, n) – количество единиц j-го продукта в дневном рационе. В рационе используется n видов продуктов. Каждый продукт содержит m питательных веществ в количестве не менее bi (i = 1,2,…,m) единиц, aij – число единиц питательного вещества si в единице продукта j-го вида. Известна стоимость cj единицы j-го продукта. Необходимо составить рацион нужной питательности при минимальных затратах на него.
Экономико-математическая модель примет вид:
F=c1x1+c2x2+…+cnxn→(min) (7)
Замечание 2. В задаче составления рациона (диеты, кормовой смеси) могут использоваться ограничения не только по необходимому минимуму питательных веществ, но и по минимальному общему весу смеси.
Например. Некоторая фирма имеет возможность купить n различных видов сырья и приготавливать различные виды смесей (продуктов). Каждый вид сырья содержит разное количество питательных веществ. Установлено, что продукция должна удовлетворять некоторым минимальным требованиям с точки зрения питательности (полезности). Необходимо определить количество каждого j-го вида сырья, образующего смесь минимальной стоимости при соблюдении требований к общему расходу смеси и её питательность.
Экономико-математическая модель задачи будет иметь вид:
при ограничениях: на общий расход смеси
на питательность смеси
на не отрицательность переменных
xj≥0, j=1,2,…n,
где xj – количество j-го сырья в смеси;
n – количество видов сырья;
m – количество питательных веществ;
aij – количество i-го питательного вещества, содержащегося в единице j-го вида сырья;
b1 – минимальное количество i-го питательного вещества, содержащегося в единице смеси;
cj – стоимость единицы сырья j;
q – минимальный общий вид смеси
Источник
Исторически задача о диете была одной из первых задач линейного программирования. Диета – это пищевой рацион для человека, кормовой рацион разрабатывают для сельскохозяйственных животных, а смеси могут быть совершенно различными. Это и комбикорм для кормления животных, и жидкие химические вещества, и смеси для металлургии. Во всех задачах этого типа необходимо соблюдать требования по сбалансированности состава в соответствии с заданными требованиями.
В задачах о рационе весьма небольшая часть информации – экономическая, это, как правило, критерий оптимальности на минимум суммарной стоимости рациона. Все остальные ограничения весьма специфические, они требуют специальных знаний в исследуемой области.
Задача 2.2
Для осуществления откорма крупного рогатого скота в подсобном хозяйстве учреждения УИС необходимо разработать суточный кормовой рацион в среднем на одну голову, содержащий в соответствии с зоотехническими нормами (не менее):
- – 12,5 кг кормовых единиц,
- – 1400 г переваримого протеина,
- – 520 мг каротина,
- – 12 кг сухого вещества.
На данный период подсобное хозяйство располагает двумя видами корма – комбикорм стоимостью 4,85 руб. за килограмм и силос кукурузный стоимостью 0,9 руб. за килограмм.
В одном килограмме комбикорма содержится: 0,9 кг кормовых единиц, 112 г переваримого протеина, 0,87 кг сухого вещества. Один килограмм кукурузного силоса содержит 0,18 кг кормовых единиц, 13 г переваримого протеина, 15 мг каротина и 0,26 кг сухого вещества.
Необходимо составить кормовой рацион, удовлетворяющий зоотехническим требованиям по питательности таким образом, чтобы его суммарная стоимость была минимальной.
Формулировка условий и цели задачи в математической форме
Обозначим: xj – содержание в рационе комбикорма, кг;
*2 – содержание в рационе силоса кукурузного, кг.
Кормовой рацион в соответствии с зоотехническими требованиями, разработанными с учетом живой массы и продуктивности данного вида животных, должен отвечать следующим условиям: содержать: 1) не менее 12,5 кг кормовых единиц; 2) не менее 1400 г пере- варимого протеина; 3) не менее 520 мг каротина; 4) не менее 12 кг сухого вещества.
- 1) кормовые единицы, кг:
- 0,9х, + 0,18х2 > 12,5;
- 2) переваримый протеин, г:
- 112xj + 13х2 >1400;
- 3) каротин, мг:
- 15х2 > 520;
- 4) сухое вещество, кг:
- 0,87xj +0,26х2 >12.
Переменные xj и не могут быть отрицательными;
4) X] > 0, > 0.
Общую стоимость кормового рациона фермер стремится минимизировать. Это цель решения задачи, отсюда сформулируем критерий оптимальности:
Задача является многовариантной, xj и х2 могут принимать бесконечное множество значений. Из этих значений следует выбрать такие значения переменных, при которых функция Z принимает минимальное значение, а переменные удовлетворяли бы системе ограничений:
Задача (2.8)-(2.9) является задачей линейного программирования (все ограничения и целевая функция являются линейными). Она несколько отличается от задачи (2.3) планирования производства, во-первых, тем, что в системе ограничений все неравенства типа >; во-вторых, тем, что целевая функция имеет критерий на минимум.
Обобщение задачи на п видов кормов и т питательных веществ
Имеется п видов корма, содержание которых в рационе необходимо выяснить, обозначим их лу, х2, …хп. Согласно зоотехническим условиям рацион должен содержать т видов питательных веществ: не менее Ъ питательного вещества первого вида,… не менее bt – питательного вещества /-го вида,… не менее Ьт – питательного вещества т-то вида. Известны коэффициенты ау – содержание питательного вещества /-го вида в единице j-го вида корма. Коэффициенты ау образуют матрицу размерностью тхп. Экономической информацией в задаче являются данные о – себестоимости (или стоимости покупки) единицыу’-го вида корма, j = i,n.
Необходимо найти план X(x19x29..jcn), удовлетворяющий условиям
и доставляющий функции
минимум.
Используя знаки суммирования, задачу (2.10)—(2.11) запишем следующим образом.
Найти план X(xh х2,…хп),
при котором
Задача 2.1 и 2.2 и их математические модели – это классические задачи планирования производства и о кормовом рационе, модель задачи 2.1 содержит неравенства типа » и целевую функцию на минимум. Но в практике вряд ли можно найти задачи в чистом виде. Если в задачу 2.1 ввести требования о выполнении плана по производству какого-либо продукта, получим неравенство типа >, а критерием оптимальности может быть минимум затрат на продукцию. В задаче 2.2 может быть введено требование по максимальному количеству какого-либо вещества (например, двухстороннее ограничение – сухого вещества «не более»), либо ограничения по наличию какого-либо корма. Кроме того, в задачах могут быть ограничения в виде уравнений или условия балансового типа. Как же различит эти постановки? Конечно же, по неформальным признакам, по постановке задачи, которая отвечает на три взаимосвязанных вопроса: что необходимо определить, с какой целью и при каких условиях.
Источник