ПРИНЯТИЕ РЕШЕНИЯ В СЛУЧАЕ ЗАДАЧИ О СОСТАВЛЕНИИ РАЦИОНА ПИТАНИЯ. ЧАСТЬ 2

1 2

---

2 ПРАКТИЧЕСКИЕ АСПЕКТЫ РЕШЕНИЯ ЗАДАЧ О РАЦИОНЕ ПИТАНИЯ 

2.1 Содержательная постановка задачи о рационе питания

Пусть сельскохозяйственное предприятие для откорма поголовья использует два вида кормовых смесей  и , содержащих питательные вещества: жиры, белки, углеводы и витамины. Содержание числа единиц питательных веществ в единице каждого вида кормовой смеси и необходимый минимум питательных веществ, а также стоимость единицы комовой смеси приведены в табл.2. Необходимо составить такой рацион кормления, при котором общие затраты будут минимальны.  

2.2 Составление экономико-математической модели задачи

Обозначим через  необходимое количество кормовой смеси  (ед.), через  необходимое количество кормовой смеси  (ед.). На введенные переменные накладываются следующие ограничения: , т.к. объем кормовой смеси не может быть отрицательным. Ограничение на целочисленность решения не вводим, т.к. под единицей смеси может пониматься различная величина (например, килограмм), которая допускает дробное значение результата. Рассмотрим норму потребления жиров: — в единице кормовой смеси  согласно условию содержание жиров составляет 2 ед., тогда весь объем кормовой смеси  будет содержать  (ед.) жиров; — в единице кормовой смеси  согласно условию содержание жиров составляет 1 ед., тогда весь объем кормовой смеси  будет содержать  (ед.) жиров; — общее содержание жиров в кормовых смесях составит  (ед.); — с учетом накладываемого ограничения по необходимому минимуму потребления жиров получим: . Рассмотрим норму потребления белков: — в единице кормовой смеси  согласно условию содержание белков составляет 3 ед., тогда весь объем кормовой смеси  будет содержать  (ед.) белков; — в единице кормовой смеси  согласно условию содержание белков составляет 2 ед., тогда весь объем кормовой смеси  будет содержать  (ед.) белков; — общее содержание белков в кормовых смесях составит  (ед.); — с учетом накладываемого ограничения по необходимому минимуму потребления белков получим: . Рассмотрим норму потребления углеводов: — в единице кормовой смеси  согласно условию содержание углеводов составляет 2 ед., тогда весь объем кормовой смеси  будет содержать  (ед.) углеводов; — в единице кормовой смеси  согласно условию содержание углеводов составляет 1 ед., тогда весь объем кормовой смеси  будет содержать  (ед.) углеводов; — общее содержание углеводов в кормовых смесях составит  (ед.); — с учетом накладываемого ограничения по необходимому минимуму потребления углеводов получим: . Рассмотрим норму потребления витаминов: — в единице кормовой смеси  согласно условию содержание витаминов составляет 2 ед., тогда весь объем кормовой смеси  будет содержать  (ед.) витаминов; — в единице кормовой смеси  согласно условию содержание витаминов составляет 2 ед., тогда весь объем кормовой смеси  будет содержать  (ед.) витаминов; — общее содержание витаминов в кормовых смесях составит  (ед.); — с учетом накладываемого ограничения по необходимому минимуму потребления витаминов получим: . Исходя  из того,  что  стоимость  единицы  кормовой  смеси  составила  3  ден.ед.  для  и 4 ден.ед. для , то общие затраты составят , а накладывая условие нахождения минимума затрат получим целевую функцию . Таким образом, построена следующая математическая модель задачи:

2.3 Решение задачи о рационе графическим методом

  Строим в декартовой системе координат на плоскости  граничные прямые (рис.1), уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств: Рисунок 1 – Построение граничных прямых Каждая граничная прямая разбивает координатную плоскость на две полуплоскости. Находим полуплоскости, определяемые каждым из ограничений системы: — для определения полуплоскости  возьмем опорную точку О(0;0) и подставим ее координаты в неравенство, получим , что неверно, т.е. точка О не удовлетворяет условиям неравенства и принадлежит противоположной от искомой полуплоскости; — аналогичным образом определим полуплоскости, удовлетворяющие условиям , , ; — полуплоскость, определяемая  лежит правее от прямой (5); — полуплоскость, определяемая  лежит выше прямой (6). На следующем рисунке направление полуплоскостей показано стрелками (рис.2).   Рисунок 2 – Определение полуплоскостей и ОДР   Пересечение всех найденных полуплоскостей (на рисунке показано цветовой заливкой) определяет область допустимых решений задачи. Исходя из анализа рисунка видим, что область допустимых решений представляет собой незамкнутую сверху область  , ограниченную снизу ломанной , каждая из вершин которой является допустимым решением задачи. Определим аналитически координаты вершин: , , , ,  (как точек пересечения соответствующих граничных прямых) (рис.3). Рисунок 3 – Область допустимых решений   Среди допустимых решений задачи найдем оптимальное решение задачи одним из двух методов: — методом прямого перебора; — методом построения основной прямой. Использование метода прямого перебора основано на следующей теореме: «Если задача линейного программирования имеет оптимальное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений», т.е. оптимальное решение задачи можно найти поочередно подставив координаты вершин области  в целевую функцию и выбрав из них необходимый минимум. ;     ;     ; ;   . Таким образом получим, что  при , . Метод построения основной прямой предусматривает на плоскости графической интерпретации решения задачи (рис.3) построения так называемой основной прямой – прямой целевой функции , которая представлена на рис.4 пунктирной линией. Далее выполняем параллельный перенос основной прямой вдоль направленного вектора максимизации функции . Первая точка области, с которой соприкоснется передвигаемая основная прямая , будет являться оптимальным решением задачи (поскольку движемся в направлении максимума, то первая точка – минимум, последняя — максимум). Из рис.4 следует, что оптимальному решению задачи соответствует точка . Подставив координаты точки  в целевую функцию, найдем ее оптимум: . Рисунок 4 – Определение оптимального решения задачи   Таким образом, при решении поставленной задачи графическим методом получили, что для соблюдения минимума затрат в размере 12   ден.ед.  необходимо в рацион питания включить 4  ед. кормовой смеси , а кормовую смесь  не использовать вовсе.  

2.4 Симплекс-метод решения задачи о рационе питания

  Приведем задачу к канонической форме (перевод функциональных ограничений в систему уравнений). Для этого в ограничения задачи введем дополнительные переменные. Обозначим добавочные переменные . Все дополнительные переменные должны быть неотрицательными и они должны иметь тот же знак, что и свободные члены системы ограничений. Алгоритм симплекс-метода:

1. Составление симплекс-таблицы и получение первого базисного решения (в случае, если изначально базис пуст – то сначала выполняются п.3-5).
2. Выполнение проверки условия: все , т.е. проверяется наличие положительных элементов в последней строке симплексной таблицы. Если такие элементы имеются, то оптимальное решение задачи не найдено и необходимо продолжать расчеты.
3. Выбор разрешающего столбца (переменной, вводимой в базис). Разрешающий столбец выбирается в соответствии со следующим условием:

где r — номер разрешающего столбца. Таким образом, при определении разрешающего столбца просматривается последняя строка симплексной таблицы и в ней отыскивается наибольший положительный элемент.

4. Поиск разрешающего элемента в разрешающем столбце. Для этого проверяется условие: все . Если это условие выполняется, то целевая функция задачи неограничена и решения нет, если условие не выполняется – то ищем разрешающий элемент из соотношения:

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

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

Элементы, не принадлежащие разрешающим столбцу и строке, пересчитываются по так называемому правилу прямоугольника: мысленно выделяется прямоугольник, в котором элемент, подлежащий пересчету и разрешающий элемент образуют одну из диагоналей. Формулы будут иметь следующий вид: ; ;; . Построим исходную симплекс-таблицу (табл.3), по которой найдем первоначальное допустимое базисное решение. Ниже приведена исходная симплексная таблица рассматриваемой задачи. В левом столбце записываются основные (базисные) переменные (первоначально базис пуст), в первой строке таблицы перечисляются все переменные задачи. Крайний правый столбец содержит свободные члены системы ограничений . В последней строке таблицы (она называется оценочной) записываются коэффициенты целевой функции , а также значение целевой функции при текущем базисном решении . В рабочую область таблицы (начиная со второго столбца и второй строки) занесены коэффициенты при переменных системы ограничений. Таблица 3 Таким образом, при пустом базисе все переменные равны нулю, соответственно, и значение целевой функции равно нулю. Для заполнения базиса выберем разрешающий столбец (например, , тем самым выводя данную переменную в базис). Проверка показывает, что в данном столбце есть положительные элементы, а значит задача решаема. Выбираем в данном столбце разрешающий элемент из соотношения: , таким образом, разрешающий элемент – 2 (он выделен в табл.3 рамкой). Затем выполним пересчет остальных элементов исходной таблицы и получим новую таблицу (табл.4). Таблица 4 Таким образом, базисная переменная , все остальные переменные равны нулю. При этом целевая функция равна . Выполним перевод в базис переменной , выбрав в качестве разрешающего элемента 1. Результаты пересчета таблицы представлены в табл.5. Таблица 5 Таким образом, в полученной симплекс-таблице базисными переменными являются: , . Неосновные переменные ,, и  равны нулю. Значение целевой функции в этом случае равно 10,5. Для дальнейшего заполнения базиса в качестве разрешающего столбца выберем столбец переменной , выбрав в качестве разрешающего элемента 1. Результаты пересчета таблицы представлены в табл.6. Таблица 6 Таким образом, в полученной симплекс-таблице базисными переменными являются: , , . Неосновные переменные , и  равны нулю. Значение целевой функции в этом случае равно 12. Для дальнейшего заполнения базиса в качестве разрешающего столбца выберем столбец переменной , выбрав в качестве разрешающего элемента . Результаты пересчета таблицы представлены в табл.7. Таблица 7 Таким образом, получено первое базисное решение, в котором базисными переменными являются: , , , . Неосновные переменные и  равны нулю. Значение целевой функции в этом случае равно 12. Полученное решение является оптимальным, поскольку в нижней строке таблицы нет ни одного положительного коэффициента. Таким образом, результат решения симплекс-методом идентичен результату, полученному в результате решения задачи графическим методом.

2.5 Применение функционала табличного процессора MS Excel для решения задачи о рационе питания

  Для решения оптимизационных задач в табличном процессоре MS Excel присутствует надстройка Поиск решений (для активации — Сервис / Надстройки / Поиск решений, для дальнейшего использования – Сервис / Поиск решений). При этом решение будет получено с применением численного метода Ньютона (можно заменить на метод сопряженных градиентов). Изначально необходимо ввести исходные данные на лист табличного процессора (рис.5).   Рисунок 5 – Фрагмент листа MS Excel с исходными данными На рис.5 в таблицу с исходными данными введен столбец Уравнение (столбец Е), он предназначен для введения формул, отображающих условия-ограничения задачи, а также в строке 11 введены начальные значения переменных. Введем необходимые формулы в подготовленные ячейки, для их отображения на листе воспользуемся вкладкой Сервис / Параметры и активируем опцию Формулы. Результат приведен на рис.6. Рисунок 6 — Фрагмент листа MS Excel с расчетными формулами   Для возврата обратно к числовому виду выполним Сервис / Параметры и снимем отметку у опции Формулы. Таким образом, подготовительный этап решения задачи завершен. Выбираем вкладку Сервис / Поиск решений (рис.7).   Рисунок 7 – Выбор надстройки Поиск решения В открывшемся диалоговом окне Поиск решения необходимо выполнить следующие действия (рис.8): 1) установить целевую ячейку $Е$8 (по умолчанию устанавливается как абсолютная ссылка); 2) указать направление оптимизации целевой функции – минимальное значение (соответствует ); 3) выбрать диапазон изменяемых ячеек – ячеек с искомыми значениями переменных — $C$11:$D$11; 4) добавить ограничения (нажав на кнопку Добавить и пошагово ввести все ограничения задачи: $E$4>=$G$4 (соответствует ограничению ), $E$5>=$G$5 (соответствует ограничению ), $E$6>=$G$6 (соответствует ограничению ),  $E$7>=$G$7 (соответствует ограничению ); 5) перейти во вкладку параметры и выбрать опции Линейная модель (т.к. рассматриваемая задача является задачей линейного программирования, а следовательно, и все условия и функция линейны), Неотрицательные значения (, ). Рисунок 8 – Ввод данных в диалоговое окно надстройки Поиск решений После этого необходимо нажать кнопку Выполнить. В открывшемся окне (рис.9) следует выбрать опцию Сохранить найденное решение и нажать ОК. Рисунок 9 – Выбор формата результатов решения В результате будет получено решение задачи, приведенное на рис.10. Рисунок 10 – Результат решения задачи Полученные результаты решения задачи свидетельствуют о том, что для соблюдения минимума затрат в размере 12   ден.ед.  необходимо в рацион питания включить 4  ед. кормовой смеси , а кормовую смесь  не использовать вовсе. Полученные результаты решения задачи совпадают с результатами аналитических расчетов, выполненных в пунктах 2.3-2.4 данной работы.  

2.6 Программная реализация решения задачи о рационе питания

Программная реализация алгоритма решения задачи о рационе питания как задачи линейного программирования симплексным методом выполнена в среде программирования Microsoft Visual C++. Листинг программы приведен в Приложении А. Результаты работы программы представлены на рис.11. Рисунок 11 – Результаты работы программы Таким образом, результаты решения задачи с использованием программной реализации совпали с полученными ранее результатами.

ЗАКЛЮЧЕНИЕ

В ходе выполнения курсовой работы был проведен анализ литературных источников и всесторонне рассмотрена задача о составлении рациона питания как задача линейного программирования. В практической части работы рассмотрена прикладная экономическая задача, для которой была построена математическая модель, оценена применимость и выполнено ее решение аналитическими (графическим и симплексным) методами, причем симплексный метод был реализован как в табличном виде, так и программно, а также с использованием численного метода Ньютона (средствами табличного процессора MS Excel). Получено, что конечный результат решения задачи, а именно оптимальное значение ее целевой функции, одинаков для всех используемых методов. При этом следует заметить, что графический метод применим к решению задач только с двумя базисными переменными, т.к. при большем количестве исследовать графическую интерпретацию сложно. Кроме того, решение симплексным методом в табличной форме также усложняется с ростом количества переменных и уравнений в исходной задаче. Таким образом установлено, что наиболее удобной в применении является программная реализация симплексного метода и применение численных методов решения с использованием средств вычислительной техники.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Афанасьев М.Ю., Багриновский К.А., Матюшок В.М. Прикладные задачи исследования операций: учебное пособие. – И.: ИНФРА-М, 2006. – 352 с.
2. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем. – 2-е изд. – М.: Финансы и статистика, 2006. – 432 с.
3. Исследование операций в экономике: учеб. пособие для студ. вузов / Финансовый университет при Правительстве РФ; ред. Н. Ш. Кремер. — 3-е изд.. — М.: Юрайт, 2013. — 438 с.
4. Конюховский П.В. Математические методы исследования операций в экономике. – СПб: Питер, 2000. – 208 с.
5. Леоненков А.В. Решение задач оптимизации в среде MS Excel. – СПБ.: БХВ-Петербург, 2005. – 704 с.
6. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. — СПб.: Лань, 2015. — 512 с.
7. Попов А.М., Сотников В.Н. Экономико-математические методы и модели: учебник для бакалавров. – М.: Юрайт, 2013. – 479 с.
8. Таха Хэмди А. Введение в исследование операции. – 6-е изд. – М.: ИД «Вильямс», 2001. – 912 с.
9. Ширяев В. Исследование операций и численные методы оптимизации. – 5-е изд. – СПб.: Ленанд, 2017. – 210 с.
10. Юдин Д.Б., Гольштейн Е.Г.Линейное программирование: теория, методы и приложения. – М.: URSS, 2012. – 424 с.

---

1 2