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

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

Исторические задача о диете является одной из первых задач линейного
программирования.

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

Даме необходимо похудеть, за помощью обратилась к подруге.

Построение модели – рассмотрение этого этапа и является главной целью.

Подруга посоветовала перейти на рациональное питание, состоящее из двух
продуктов P и Q.

Суточное питание этими продуктами должно давать не более 14 единиц жира
(чтобы похудеть), но не менее 300 калорий. На упаковке продукта Р
написано, что в одном килограмме этого продукта содержится 15 единиц жира и 150
калорий, а на упаковке с продуктом Q – 4
единицы жира и 200 калорий соответственно. При этом цена 1 килограмма продукта
Р равна 15 руб., а 1 кг продукта Q – 25
руб.

Так как дама была стеснена в средствах, но ее интересовал вопрос: в какой
пропорции нужно брать эти продукты для того, чтобы выдержать условия диеты и
истратить как можно меньше денег?

Перейдем к формализации данной ситуации на языке математических символов.

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

Количество единиц жира, содержащегося в х кг продукта
Р и в у кг продукта Q, равно
15х + 4 и по условию диеты не должно превосходить 14:

В свою очередь, количество калорий, содержащихся в х
кг продукта Р и в у кг продукта Q,
равно 150х + 200у и по условию диеты должно быть не меньше 300:

Теперь о стоимости z продуктов.
Она равна

и в соответствии с высказанными пожеланиями должна быть минимальной.

Последнее записывается так:

Тем самым мы получили систему формул:

которую решим графическим способом.

Нас интересует только та ее часть, которая лежит над треугольником
BDE. Вычисляя значения z
во всех трех вершинах этого треугольника

и сравнивая полученные результаты, замечаем, что наименьшее значение (35)
достигается в вершине Е. Таким образом,

и искомая пропорция – 2 : 3.

2.2. Задача о выпуске продукции

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

Перейдем к построению математической модели
поставленной задачи. Введем следующие обозначения. Пусть

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

Тогда ожидаемую прибыль можно записать так:

Требуется найти такие значения х и у,
подчиненные условиям

для которых

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

а затем, используя точку начала отсчета О(0, 0),
определить соответствующие полуплоскости. Пересечением полученных полуплоскостей
будет четырехугольник ОВМЕ.

Наша целевая функция достигает наибольшего значения в одной
из вершин четырехугольника.

Нам необходимо найти координаты точки М – точки
пересечения прямых EF и АВ, для этого надо
решить систему уравнений

Вычислить значения z в точках
В(0, 100), Е(150, 0), М(100, 50):

Из полученных значений выберем наибольшее и получим ответ:

2.3. Общая задача линейного программирования

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

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

(линейной функции элементов решения
) при линейных ограничительных
условиях, накладываемых на элементы решения:

где – заданные числа.

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

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

Правило сокращенного суммирования. Для обозначения
суммы чисел :

принята такая запись:

где ∑ – знак суммирования, а
k – индекс суммирования.

Это обозначение очень удобно:

А вот как выглядит запись общей задачи линейного
программирования:

2.4. Транспортная задача

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

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

Пример 1. Рассмотрим транспортную задачу, заданную таблицей

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

при условии, что

Положим и выразим через
t остальные переменные:
из первого уравнения: ,
из второго уравнения: ,
из третьего уравнения:

Тогда

Из того, что все не
отрицательны, получаем, что переменная t должна
удовлетворять одновременно следующим четырем неравенствам:

Тем самым, мы получили условие .

Не трудно заметить, что при
t = 16.

Ответ:

Пример 2. Компания имеет два товарных склада и трех оптовых
покупателей. Известно, что общий объем запасов на складах составляет 300 тыс.
единиц продукции и совпадает с общим объемом заказов покупателей.

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

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

Минимизировать общую стоимость перевозок:

при условии, что

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

Положим и
выразим через u и
v остальные переменные. Имеем

Учитывая, что все перевозки должны получить неотрицательные значения, мы
приходим к задаче

которую можно решить графическим методом.

Выписанные неравенства определяют на плоскости (u,
v) пятиугольник с вершинами (30, 0), (70, 0), (70, 50), (0,
120), (0, 30).

Ответ:

В начало

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

Коротко говоря, у каждой модели есть свой ресурс.

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

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

Вместе с тем, даже весьма грубая на вид идеализация нередко позволяет глубже вникнуть в суть проблемы. Пробуя как-то влиять на параметры модели выбирать их, управлять ими , мы получаем возможность подвергнуть исследуемое явление качественному анализу и сделать выводы общего характера. Дата добавления: ; просмотров: ; Опубликованный материал нарушает авторские права? Лучшие изречения: Как то на паре, один преподаватель сказал, когда лекция заканчивалась – это был конец пары: “Что-то тут концом пахнет”.

Алгоритм — точное предписание о порядке выполнения действий для получения решения по данной задаче и задачам, подобным данной. Вопрос Численное дифференцирование. Задача Коши.

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

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

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

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

Особенности математической модели динамического программирования заключаются в следующем:. Состояние системы S k после каждого шага управления зависит только от предшествующего состояния системы S k-1 и этого управляющего воздействия X k отсутствие последействия и может быть записано в виде уравнения состояния:.

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

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

Составление экономико-математической модели задачи о рационе питания

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

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

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

Предварительный просмотр:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предприятие химической промышленности выпускает соляную и серную кислоту. Выпуск одной тонны соляной кислоты — 25 денежных единиц выпуск одной тонны серной кислоты — 40 денежных единиц.

Для выполнения государственного заказа необходимо выпустить не менее т соляной и не менее т серной кислоты. Кроме того, необходимо учитывать, что выпуск кислот связан с образованием опасных отходов. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов, при выпуске одной тонны серной кислоты — 1,2 т опасных отходов.

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

Пусть x 1 — количество соляной кислоты, x 2 — количество серной кислоты. Ограничения по опасным отходам. Таким образом, задача заключается в следующем: максимизировать целевую функцию. Решим задачу графическим методом. Введем начальные данные, значения х 1 , а также ограничение в таблицу.

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

Рисунок 3 — Excel-документ графическое решение задачи линейного программирования. Рисунок 4 — Excel-документ аналитическое решение задачи линейного программирования. Это означает, что предприятию следует выпустить т соляной кислоты и т серной кислоты. Прибыль при этом составит денежных единиц. Рисунок 5 — Matchad-документ аналитическое решение задачи линейного программирования.

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

Некоторые из математических возможностей MathСad версии до Начиная с 14 версии – использует символьное ядро MuPAD.

Задача составления кормовой смеси или задача о диете

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

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

Открытая архитектура приложения в сочетании с поддержкой технологий. Есть возможность создания электронных книг e-Book.

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

Вычислить значения z в точках В 0, , Е , 0 , М , 50 :. В общем случае и число неизвестных , и число ограничений могут достигать десятков, сотен, тысяч и т. Однако набор соответствующих условий ничем кроме количества от рассмотренных выше примеров не отличается. Это нетрудно заметить уже по общей постановке задачи линейного программирования. Стандартная математическая формулировка общей задачи линейного программирования выглядит так: требуется найти экстремальное значение показателя эффективности целевой функции.

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

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

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

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

Тогда данные таблицы можно представить в следующем виде:.