IX Международная студенческая научная конференция Студенческий научный форум - 2017

ВВЕДЕНИЕ

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

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

Актуальность работы заключается в том, что использование методов оптимизации, в том числе и линейного программирования позволяет с максимальной выгодой и минимальными расходами разрешить задачу о диете, составить наиболее оптимальный рацион, а также сбалансированный режим питания. Разрешение оптимизационной задачи о диете играет важную роль в составлении специализированного рациона питания здоровых и больных людей, а также в сельском хозяйстве при составлении режима кормлении животных[1].

Цель и задачи исследования. Целью выполнения данной работы является углубление знаний по вопросам оптимизационной задачи о диете, получение навыков работы с научной и научно-популярной литературой. К задачам исследования можно отнести:

• описать общую задачу оптимизации;

• привести постановку задач линейного программирования;

• описать возможности ЭТ MS Excel и математического пакета

Mathcad по решению оптимизационных задач;

• выполнить поставку задачи и разработать математическую модель задачи о нахождении оптимальной диете по критерию минимальной стоимости и

заданной калорийности;

• рассмотреть порядок решения задачи, которая рассматривается в работе, в среде ЭТ MS Excel и в среде математического пакета Mathcad.

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

Математическое программирование можно представить как математическую дисциплину, которя занимается изучением как экстремальных задач, так и разработкой методов их решения[5].

1.Общая задача оптимизации

1.1Постановка общей задачи оптимизации

На нахождение лучших хозяйственных решений, которые могут обеспечивать максимальное значение целевой функции и минимальное значение затрат, влияют экономические методы управления производством, развитие рыночных отношений, а также распространение договорных. Необходимость в поиск подобного рода решений объяснется наличие различных ограничений на всевозможные факторы производства, позволяющие предприятиям полноценно и бесперебойно функционировать. Отсутствие подобных ограничений привело бы к тому, что нечего было бы выбирать, таким образом, не было бы и вариантов решений[3].

Общий вид постановки математической модели экстремальной задачи представляет собой определение максимального или минимального значения целевой функции

при следующем условии ,

где f и g_i − заданные функции, a b_i − некоторые действительные числа.

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

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

Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.

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

Все задачи программирования можно разделить на три огромных группы:

• задачи линейного программирования,

• задачи нелинейного программирования;

• задачи динамического программирования.

1.1 Классификация задач оптимизации

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина "математическое программирование". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина "линейное программирование" возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач[10].

Термин "линейное программирование" возник в результате неточного

перевода английского "linear programming". Одно из значений слова "programming" − составление планов, планирование. Следовательно, правильным переводом английского "linear programming" было бы не "линейное программирование", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

Итак, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности.

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

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

Существует несколько методов решения задач ЛП. В данной работе будут рассмотрены некоторые из них, в частности:

• Графический метод решения задачи ЛП;

• Симплексный метод;

• Решение задачи ЛП средствами табличного процессора Excel;

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

• рационального использования сырья и материалов;

• задачи оптимального раскроя;

• оптимизации производственной программы предприятий;

• оптимального размещения и концентрации производства;

• составления оптимального плана перевозок, работы транспорта (транспортные задачи);

• управления производственными запасами;

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

ЗЛП записывается в общем виде так:

Наиболее часто встречаются задачи в виде: имеется n ресурсов при m ограничениях. Нужно определить объемы этих ресурсов, при которых целевая функция будет достигать максимума (минимума), т. е. найти оптимальное распределение ограниченных ресурсов. При этом имеются естественные ограничения x_j > 0.

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

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

1. обозначить переменные;

2. составить целевую функцию;

3. записать систему ограничений в соответствии с целью задачи;

4. записать систему ограничений с учетом имеющихся в условии задачи показателей.

Если все ограничения задачи заданы уравнениями, то модель такого вида называется канонической. Если хоть одно из ограничений дано неравенством, то модель неканоническая. [5]

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

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

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

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

Решение задач методами динамического программирования проводится на основе сформулированного Р.Э.Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения. [3]

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

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

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

Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных – переменную состояния S и переменную управления X. Переменная S определяет, в каких состояниях может оказаться

система на данном k-м шаге. В зависимости от S на этом шаге можно применить некоторые управления, которые характеризуются переменной X. Применение управления X на k-м шаге приносит некоторый результат W_k(S,X_k) и переводит систему в некоторое новое состояние S'(S,X_k). Для каждого возможного состояния на k-м шаге среди всех возможных управлений выбирается оптимальное управление X*_k такое, чтобы результат, который достигается за шаги с k-го по n-й, оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана F_k(S) и зависит от номера шага k и состояния системы S.

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

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

В общем виде задача динамического программирования формулируется следующим образом: требуется определить такое управление X*, переводящее систему из начального состояния S₀ в конечное состояние Sn, при котором целевая функция F(S₀,X*) принимает наибольшее (наименьшее) значение.

Особенности математической модели динамического программирования заключаются в следующем:

• задача оптимизации формулируется как конечный многошаговый процесс управления;

• целевая функция является аддитивной и равна сумме целевых функций каждого шага

• выбор управления X_k на каждом шаге зависит только от состояния системы к этому шагу S_k-1 и не влияет на предшествующие шаги;

Состояние системы S_k после каждого шага управления зависит только от предшествующего состояния системы S_k-1 и этого управляющего воздействия X_k (отсутствие последействия) и может быть записано в виде уравнения состояния:

На каждом шаге управление X_k зависит от конечного числа управляющих переменных, а состояние системы S_k зависит от конечного числа переменных;

Оптимальное управление X* представляет собой вектор, определяемый последовательностью оптимальных пошаговых управлений:

X*=(X*₁, X*₂, …, X*_k, …, X*n),

число которых и определяет количество шагов задачи.

Условная оптимизация. Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем n-м шаге найти оптимальное управление X*n и значение функции Беллмана Fn(S) не сложно, так как

)},

где максимум ищется по всем возможным значениям Xn.

Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге:

. (1)

Этот максимум (или минимум) определяется по всем возможным для k и Sзначениям переменной управления X.

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый (на первом шаге k=1 состояние системы равно ее начальному состоянию S₀), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге X₁, применение которого приведет систему в состояние S₁(S,x₁*), зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага. [11]

2. Линейное программирование

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

Наиболее удобным и распространенным математическим инструментом при моделировании и решении оптимизационных задач является линейное программирование – специальный класс оптимизационных задач, в котором все отношения между переменными выражаются линейными функциями, а переменные принимают действительные значения. Преимущество этого класса в том, что разработаны универсальные алгоритмы для решения таких задач большой̆ размерности. Впервые задача линейного программирования в России была сформулирована в 1939 г. Л. В. Канторовичем, который̆ применил математическую модель этой задачи в экономике и разработал метод решения. В 1975 г. Л. В. Канторович получил Нобелевскую премию за достижения в этой области. В 1947 г. американский учёный Д. Данциг разработал алгоритм решения этой задачи. С этого момента линейное программирование стало важным инструментом в исследовании операций. [5]

Часто из условия задачи следует, что значения некоторых переменных принятия решений принадлежат множеству целых чисел. Например, если переменная отвечает за размер детали, то она может принимать значения толь- ко из заданного множества возможных размеров деталей. Такого рода задачи принадлежат к классу задач целочисленного линейного программирования или смешанного целочисленного линейного программирования. Они отличаются от задач линейного программирования высокой сложностью и особой практической значимостью. Задачам из этих классов в данном пособии уделяется особое внимание. Прежде чем переходить к построению математической модели, необходимо пройти несколько этапов. Данная проблема решается в интересах так называемого лица, принимающего решения (ЛПР). ЛПР формулирует проблему, участвует в построении модели, анализирует полученное решение, а затем принимает или отвергает его. Построение математической модели и решение

задачи лучше доверить специалистам по исследованию операций.

Исследование задачи начинается с появления некоторой проблемы. Большинство оптимизационных задач возникает из практических приложений.

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

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

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

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

Следующий важный этап состоит в построении математической модели. Как архитектор использует бумагу для построения макета здания, так и математический язык используется для записи моделей. Может оказаться, что символическая запись слишком сложна в той постановке, которая получилась на предыдущем шаге. Сложность может заключаться в том, что критерии оптимизации или ограничения выражаются нелинейными функциями или число ограничений и переменных слишком велико. В результате время работы алгоритма с такой моделью окажется неприемлемо большим. В этом случае необходимо вернуться на шаг уяснения и формулировки задачи, переопределить переменные и ограничения. Построение модели − это своего рода искусство. Не существует единственного верного способа, как это делать. Для одной и той же задачи можно построить несколько эквивалентных моделей с разным числом переменных и ограничений, так же как для теорем может быть предложено несколько различных доказательств.

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

практического внедрения. Может оказаться, что поиск оптимума требует больших вычислительных ресурсов, в то время как приближенное решение не сильно отличается от оптимального или оно устраивает того, кто принимает решение. Кроме того, при моделировании часто возникают труднореализуемые аспекты. Имеется много критериев оптимизации, и понятие оптимального решения является условным. Многовариантные расчеты по сценарию «А что, если...?» позволяют проверить чувствительность решений к изменениям исходных данных, исследовать различные предположения и оценить последствия принимаемых решений.

В большинстве задач выбора имеется много критериев оценки вариантов решения. Критерии могут быть зависимыми или независимыми. Зависимы- ми называют те критерии, при которых оценка альтернативы по одному из них определяет оценку по другому критерию. Количество критериев влияет на сложность задачи принятия решений. При небольшом числе критериев (два- три) задача сравнения по ним может быть выполнена непосредственно. При большом числе критериев задача становится труднообозримой, и тогда необходимо использовать специальные методы решения многокритериальных задач оптимизации. [1]

2.2 Графический метод

Рассмотрим следующую задачу ЛП. Предприятие химической промышленности выпускает соляную и серную кислоту. Выпуск одной тонны соляной кислоты – 25 денежных единиц выпуск одной тонны серной кислоты – 40 денежных единиц. Для выполнения государственного заказа необходимо выпустить не менее 200 т соляной и не менее 100 т серной кислоты. Кроме того, необходимо учитывать, что выпуск кислот связан с образованием опасных отходов. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов, при выпуске одной тонны серной кислоты – 1,2 т опасных отходов. Общее количество опасных отходов не должно превышать 600 т, так как

превышение этого ограничения приведет к выплате предприятием крупного штрафа. Требуется определить, сколько соляной и серной кислоты должно выпустить предприятие, чтобы получить максимальную прибыль.

Составим математическую модель задачи.

1. Пусть x₁ – количество соляной кислоты, x₂ – количество серной кислоты.

2. Введем целевую функцию – максимальную прибыль от реализации, которая составляет F(x₁,x₂)=25x₁+40x₂, и которую необходимо максимизировать.

3. Ограничения.

3.1. Ограничения по опасным отходам. Количество, образованных опасных отходов, равно 0,5x₁+ 1,2x₂, при этом по условию оно не должно превосходить 600 тонн, т.е.

0,5x₁+ 1,2x₂ ≤600.

3.2. Ограничение на соляной кислоте и серной кислоте:

x₁≤ 200, x₂ ≤ 100.

3.3. Условие неотрицательности:

x₁ ≥ 0, x₂ ≥ 0.

Таким образом, задача заключается в следующем: максимизировать целевую функцию

F(x₁,x₂) = 25x₁+40x₂→ max

Решим задачу графическим методом. Решение в ЭТ MS Excel будет иметь следующий вид:

1. Введем начальные данные, значения х₁, а также ограничение в таблицу.

Рисунок 1 – Excel-документ графическое решение задачи линейного программирования

1. Изобразим полученные значения на графике

Рисунок 2 – Excel-документ графическое решение ЗЛП

1. Найдем координаты точек А и В, а также значение целевой функции в них.

Рисунок 3 – Excel-документ графическое решение задачи линейного программирования

Рисунок 4 – Excel-документ аналитическое решение задачи линейного программирования

Вывод: Таким образом, оптимальное решение находится в точке А= (960; 100). Это означает, что предприятию следует выпустить 960 т соляной кислоты и 100 т серной кислоты. Прибыль при этом составит 28000 денежных единиц.

Решение в математическом пакете Mathcad будет иметь следующий вид:

Рисунок 5 – Matchad-документ аналитическое решение задачи линейного программирования

Рисунок 6 – Mathcad-документ решения задачи линейного программирования

3. Оптимизационная задача о диете и ее решение в среде ЭТ MS Excel и математического пакета Mathcad

3.1 Понятия и основы пакета MathCad

MathСad - система компьютерной алгебры из класса систем автоматизированного проектирования, ориентированная на подготовку интерактивных документов с вычислениями и визуальным сопровождением, отличается легкостью использования и применения для коллективной работы.

MathСad был задуман и первоначально написан Алленом Раздовым из Массачусетского технологического института (MIT), соучредителем компании Mathsoft, которая с 2006 года является частью корпорации PTC (Parametric Technology Corporation).

MathСad имеет простой и интуитивный для использования интерфейс пользователя. Для ввода формул и данных можно использовать как клавиатуру, так и специальные панели инструментов.

Некоторые из математических возможностей MathСad (версии до 13.1 включительно) основаны на подмножестве системы компьютерной алгебры Maple (MKM, Maple Kernel Mathsoft). Начиная с 14 версии - использует символьное ядро MuPAD. [15]

Работа осуществляется в пределах рабочего листа, на котором уравнения и выражения отображаются графически, в противовес текстовой записи в языках программирования. При создании документов-приложений используется принцип WYSIWYG (What You See Is What You Get - "что видишь, то и получаешь").

Несмотря на то, что эта программа в основном ориентирована на пользователей-непрограммистов, MathСad также используется в сложных проектах, чтобы визуализировать результаты математического моделирования, путем использования распределённых вычислений и традиционных языков программирования. Также MathCad часто используется в крупных инженерных проектах, где большое значение имеет трассируемость и соответствие стандартам.

MathСad достаточно удобно использовать для обучения, вычислений и инженерных расчетов. Открытая архитектура приложения в сочетании с поддержкой технологий .NET и XML позволяют легко интегрировать MathCad практически в любые ИТ-структуры и инженерные приложения. Есть возможность создания электронных книг (e-Book).

Основные возможности MathCad.

MathСad содержит сотни операторов и встроенных функций для решения различных технических задач. Программа позволяет выполнять численные и символьные вычисления, производить операции с скалярными величинами, векторами и матрицами, автоматически переводить одни единицы измерения в другие.

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

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

• проведение математических расчетов (как аналитических, так и при помощи численных методов);

• подготовка графиков с результатами расчетов;

• ввод исходных данных и вывод результатов в текстовые файлы или файлы с базами данных в других форматах;

• подготовка отчетов работы в виде печатных документов;

• подготовка Web-страниц и публикация результатов в Интернете;

• получение различной справочной информации из области математики.

Среди возможностей MathСad можно выделить:

• Решение дифференциальных уравнений, в том числе и численными методами.

• Построение двумерных и трёхмерных графиков функций (в разных системах координат, контурные, векторные и т. д.).

• Использование греческого алфавита как в уравнениях, так и в тексте.

• Выполнение вычислений в символьном режиме.

• Выполнение операций с векторами и матрицами.

• Символьное решение систем уравнений.

• Аппроксимация кривых.

• Выполнение подпрограмм.

• Поиск корней многочленов и функций.

• Проведение статистических расчётов и работа с распределением вероятностей

• Поиск собственных чисел и векторов.

• Вычисления с единицами измерения.

• Интеграция с САПР системами, использование результатов вычислений в качестве управляющих параметров.

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

Вычислительный блок Given/Find

Рассмотрим решение системы n нелинейных уравнений с m неизвестными

Здесь f_i(x_i, ..., х_m) =b₁, . .., fn(x_i, ..., х_m) =bn– некоторые скалярные выражения, зависящие от скалярных переменных x₁,x₂, ... ,х_m и, возможно, от еще каких-либо переменных. Уравнений может быть как больше, так и меньше числа переменных. Заметим, что систему можно формально переписать в виде:

f(x)=b,

где х – вектор, составленный из переменных x₁,x₂,.. . ,хn, b – вектор, составленный из правых частей уравнений, а f(х) – соответствующая векторная

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

• Given ключевое слово;

• система, записанная логическими операторами в виде равенств и, возможно, неравенств;

• Find (x_i, . .. ,х_m) – встроенная функция для решения системы уравнений относительно переменных x₁, ..., х_m.

• Вставлять логические операторы следует, пользуясь панелью инструментов Boolean (Булевы операторы). Если вы предпочитаете ввод с клавиатуры, помните, что логический знак равенства вводится сочетанием клавиш +. Значение функции Find представляет собой матрицу, составленную из всевозможных решений по каждой переменной, причем количество ее строк в точности равно числу аргументов Find.

Поиск экстремума функции

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

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

Для численного решения задач поиска локального максимума и минимума в Mathcad имеются встроенные функции Minerr, Minimize и Maximize. Принцип их

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

Таким образом, как и в случае решения уравнений, чтобы найти глобальный максимум (или минимум), требуется сначала просканировать с некоторым шагом рассматриваемую область и вычислить все локальные значения и потом выбрать из них наибольший (наименьший). Другим вариантом будет простое сканирование с вычислением значений функции, позволяющее выделить из нее подобласть наибольших (наименьших) значений функции и осуществить поиск глобального экстремума, уже находясь в его окрестности. Последний путь таит в себе некоторую опасность уйти в зону другого локального экстремума, но часто может быть предпочтительнее из соображений экономии времени. [4]

1.  

   1. Задача о диете

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

Пусть имеется m видов продуктов P₁,P₂,…….,P_m, содержащих питательные вещества и незаменимые компоненты B₁, B₂,…….,Bn. Известны величины a_ij –

количество i питательного вещества в 100 г продукта P_j. Кроме того известны величины b_i – ежесуточная минимальная потребность организма в Bi питательном веществе. Также известны величины S_j и e_j – стоимость и энергетическая ценность 100 г продукта P_j соответственно.

Оптимизационную задачу о диете можно сформулировать двумя способами.

Первый вариант:

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

Второй вариант:

Рассчитать диету с заданной калорийностью, обеспечивающую минимальную суточную потребность, после чего найти ее стоимость.

Все данные сведем в следующую таблицу 1.

Таблица 1 – Решение оптимизационной задачи о диете

Минимальные вещества незаменимые компоненты	Минимальная суточная потребность	Содержание питательных веществ в 100г продукта
		P1		P2		…		Pm
B1	b1	a11		a12		…		a1m
B2	b2	a21		a22				a2m
…	…	…		…		…		…
		an1		an2		…		anm
Стоимость 100г продукта			S1		S2		…		Sm
Калорийность 100г продукта			e1		e2		...		em

Для решения сформулированной задачи составим ее математическую модель.

1.  

   1. Математическая модель задачи

1. Определим неизвестные и их количества: Обозначим x_j(j=1,m) – количество (грамм) продукта P_j, вошедшего в диету.

2. Запишем целевую функцию:

3. Ограничения:

Минимальная суточная потребность:

Неотрицательность:

Пределы функции:

Таким образом целевые функции I и II и ограничения образуют задачу о диете.

Постановка задачи. Пусть имеются n видов продуктов Р₁,Р₂,...,Рn, содержащих питательные вещества и незаменимые компоненты В₁,В₂,…,В_m. В 100 граммах продукта Р_j содержится известное a_ijколичество питательного вещества

или незаменимого компонента В_i. Кроме того, известны: b_i – ежесуточная минимальная потребность организма в веществах В_i(i=1,2,…,m), s_j и е_j – стоимость и энергетическая ценность (в килокалориях) 100 грамм продукта Р_j (j=1,2,…,n).

Требуется:

1. Выполнить математическую постановку задачи линейного программирования (ЗЛП);

2. Решить ЗЛП в среде электронных таблиц MS Excel и пакета MathСad.

Таблица 2 − Решение оптимизационной задачи о диете

Питательные вещества, г	Мин. суточная потребность, г	Содержание питательных веществ в 100 г продукта
		Хлеб ржаной	Масло	Творог жирный	Крупа гречневая	Мясо свинное	Колбаса вареная	Яблоки	Морковь
Белки, г	90	6,6	1	14	12,6	14,3	12,1	0,4	1,3
Жиры, г	55	1,2	82,5	18	3,3	33,3	13,5	0,4	0,1
Углеводы, г	330	34,2	0,9	2,9	62,1	0	0	9,8	7,2
Ретинол (вит А)	0,00017	0	0,54	0,2	0,3	0,1	0	0,1	0
Каротин (вит А)	0,0059	0	0,38	0,07	0,01	0	0	0,03	9
В1, мг	0,0013	0,18	0	0,06	0,43	0,4	0,06	0,03	0,06
В2, мг	0,0017	0,08	0,1	0,4	0,2	0,1	0,13	0,02	0,07
РР, мг	0,018	0,67	0,05	0,3	4,19	2,2	0	0,3	1
С,мг	0,08	0	0	0,3	0	0	0	165	5
Стоимость 100 г продукта (руб.)		2,9	21	10	3,8	12	17	8	3,5
Энергетическая ценность 100 г продукта (Ккал.)		181	748	245	335	485	170	43	34

3.4 Решение с помощью пакета ЭТ MSExcel

Для решения необходимо:

1. Набрать таблицу математической постановки добавив в нее столбец “фактическое суточное потребление”. В этот столбец записываются формулы левой части ограничения, после того как будет сформирована таблица 2.

Рисунок 7  MS Excel-документ решение оптимизационной задачи о диете

1. Сформировать вторую таблицу, где перечислены продукты, переменные математической модели и количества каждого продукта, вошедшего в диету.

Рисунок 8  MS Excel-документ решение оптимизационной задачи о диете

1. Записать целевую функцию I для составления диеты с минимальной потребностью.

Рисунок 9  MS Excel-документ решение оптимизационной задачи о диете

1. Составить таблицу 3 с ограничением 3.3 с максимальным и минимальным количеством вошедшего продукта.

Рисунок 10  MS Excel-документ решение оптимизационной задачи о диете

Записать калорийность полученной диеты.

Рисунок 11  MS Excel-документ решение оптимизационной задачи о диете

1. Вызвать надстройку “Поиск решения”. Выполнить необходимые установки.

Рисунок 12  MS Excel-документ решение оптимизационной задачи о диете

Рисунок 13  MS Excel-документ решение оптимизационной задачи о диете

На следующем листе Excel сформулировать задачу разработки диеты с заданной калорийность. Подсчитать цену полученной диеты.

Рисунок 14  MS Excel-документ решение оптимизационной задачи о диете

3.5 Решение с помощью пакета MathСad

Встроенные функции MathСad не позволяют сформулировать оптимизационную задачу с заданной калорийностью, поэтому решается только задача с минимальной стоимостью полученной диеты.

Для решения задачи в среде пакета MathСad:

1. Зададим исходные данные.

2. Присвоим переменным начальные нулевые значения.

3. Определим целевую функцию – суммарную прибыль предприятия.

4. Введем служебное слово Given и, после него, систему ограничений.

5. Найдем оптимальное решение с помощью функции Minimize.

6. Вычислим минимальное значение и энергетическую ценность.

Рисунок 15  MathCad-документ решение оптимизационной задачи о диете

ЗАКЛЮЧЕНИЕ

Данная работа показывает широкие возможности работы с пакетами ЭТ MS Excel и MathCad. Результатом данного исследования является разработка идеального плана диеты, с одной стороны учитывая минимальную стоимость продуктов, с другой – калорийность диеты.

Глядя на результаты двух таблиц Excel, можно увидеть, что итоговые стоимость и калорийность будут различны. Такое же исследование проведено и в пакете MathCad. К сожалению, как уже говорилось ранее, MathCad не может исследовать оптимизационную задачу с заданной калорийностью, поэтому данное условие рассматривают только с одной стороны.

Как видно, результаты таблицы Excel и программы MathCad совпадаю, что говорит о правильном решении поставленной задачи.

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

1. Аверьянова С.Ю., Растеряев Н.В. Содержательные задачи линейного программирования и их решение с помощью ЭТ MS EXCEL и пакета MATHCAD: учебное пособие/ Южный федеральный университет. – Ростов-на-Дону: Издательство ЮФУ, 2014. – 132 с.

2. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. Вузов / И.Л. Акулич. – М.: Высшая школа, 1986. –С.150

3. Ашманов С.А. Линейное программирование / С.А. Ашманов. – М.: Наука, 1981. – 356с.

4. Барсов А.С. Что такое линейное программирование / А.С. Барсов. – М.: Государственное издательство физико-математической литературы, 1959. – 105с.

5. Боборыкин В.А. Математические методы решения транспортных задач / В.А. Бобрыкин.- Л.: СЗПИ, 1986.-С.146

6. Бородакий Ю.В. Линейное программирование в современных задачах оптимизации / Ю.В. Бородакий. – М.: МИФИ, 2008. – 564с.

7. Данциг Д. Линейное программирование, его обобщение и применение / Д. Данциг. – М.: Прогресс, 1966. – 450с.

8. Еремин И.И. Введение в теорию линейного и выпуклого программирования / И.И. Еремин, Н.Н. Астафьев. - М.; Наука, 1976. – 150с.

9. Карманов В.Г. Математическое программирование / В.Г. Карманов. – М.; Наука, 1986г.-98с.

10. Киселева Э.В. Математическое программирование (линейное программирование) / Э.В. Киселева, С.И. Соловьева. – Новосибирск: НГАСУ, 2002. – 256с.

11. Кремер Н.Ш. Исследование операций в экономике/ Н.Ш. Кремер. — М.: Юнити,2000. — 400 с.

12. Кузнецов Ю.Н. Математическое программирование / Ю.Н. Кузнецов, В.И. Кузубов, А.Б. Волощенко.- М.: Высшая школа, 1980. – 450с.

13. Моисеев Н.Н. Методы оптимизации / Н.Н. Моисеев, Ю.П. Иванов, Е.М. Столярова. – М.; Наука, 1978г. 187с.

14. Палий И.А. Линейное программирование. Учебное пособие / И.А. Палий. - М.: Наука, 2008.- 350с.

15. Руденко А.И. Экономика предприятия/А.И. Руденко, Учебник для экономических вузов.– Минск, 2005. -248с.

16. Смирнов В.А. Лекции – Линейное программирование с примерами решения задач / В.А. Смирнов. – М.: Наука, 2002. – 500с.

17. Тарасова Н.В., Организации и планирование производства/ Н.В. Тарасова, Ларионова И.А., Алексахин А.В. Методические указания. М.:МИСиС -2001г. 300с.

18. Юдин Д.Б. Линейное программирование (теория, методы, приложения) / Д.Б. Юдин, Н.Г. Гольштейн. – М.: Наука, 1969. – 300с.

Код для цитирования: Скопировать