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

Общий вес смеси, еженедельно расходуемый на кормление цыплят: 20 000 х 0.5 = 10 000 кг.
Ограничения, связанные с содержанием кальция, белка и клетчатки в кормовом рационе, имеют вид:
0.38X₁ + 0.001Х₂ + 0.002Х₃ ≥ 0.008 х 10 000,
0.09Х₂ + 0.50Х₃ ≥ 0.22 х 10 000,
0.02Х₂+ 0.08Х₃ ≤ 0.05 х 10 000.
Окончательный вид математической формулировки задачи:
min f(X) = 0.04 x₁ + 0.15Х₂ +0,40Х₃
при ограничениях
Х₁+Х₂+Х₃= 10 000
0.38Х₁ + 0.001Х₂ + 0.002Х₃ ≥ 80
0.09Х₂+ 0.50Х₃ ≥ 2200
0.02Х₂+ 0.08Х₃ ≤ 500
X_j > 0, j = 1, 2, 3.

Число единиц питательных веществ в единице продукции

Необходимый минимум питательных веществ

F = 3x₁ + 4x₂. (5)
С учетом необходимого минимума питательных веществ составим систему ограничений. Рацион включает (x₁ + 2x₂) единиц питательного вещества S₁, (3x₁ + 2x₂) единиц питательного вещества S₂, (2x₁ + x₂) единиц питательного вещества S₃ и (2x₁ + 2x₂) единиц питательного вещества S₄. Так как содержание питательных веществ S₁, S₂, S₃, S₄ в рационе должно быть не менее 10, 8, 9, 11 единиц, соответственно, то получим систему ограничений неравенств:
x₁+2x₂ ≥ 10 (6)
3x₁+2x₂ ≥ 8
2x₁+x₂ ≥ 9
2x₁+2x₂ ≥ 11
x₁ ≥ 0, x₂ ≥ 0
Итак, экономико-математическая модель задачи: составить дневной рацион , удовлетворяющий системе ограничений (6), при котором функция (5) принимает минимальное значение.
Сформулируем данную задачу в общей постановке.
Обозначим через x_j (j = 1, 2,…, n) – количество единиц j-го продукта в дневном рационе. В рационе используется n видов продуктов. Каждый продукт содержит m питательных веществ в количестве не менее b_i (i = 1,2,…,m) единиц, a_ij – число единиц питательного вещества s_i в единице продукта j-го вида. Известна стоимость c_j единицы j-го продукта. Необходимо составить рацион нужной питательности при минимальных затратах на него.
Экономико-математическая модель примет вид:

(8)
Замечание 1. Целевую функцию (7) и систему ограничений неравенств можно записать, используя знак ∑ (суммы).

(10)
Замечание 2. В задаче составления рациона (диеты, кормовой смеси) могут использоваться ограничения не только по необходимому минимуму питательных веществ, но и по минимальному общему весу смеси.
Например. Некоторая фирма имеет возможность купить n различных видов сырья и приготавливать различные виды смесей (продуктов). Каждый вид сырья содержит разное количество питательных веществ. Установлено, что продукция должна удовлетворять некоторым минимальным требованиям с точки зрения питательности (полезности). Необходимо определить количество каждого j-го вида сырья, образующего смесь минимальной стоимости при соблюдении требований к общему расходу смеси и её питательность.
Экономико-математическая модель задачи будет иметь вид:

,
при ограничениях: на общий расход смеси
на питательность смеси

на не отрицательность переменных

x_j≥0, j=1,2,…n,
где x_j – количество j-го сырья в смеси;
n – количество видов сырья;
m – количество питательных веществ;
a_ij – количество i-го питательного вещества, содержащегося в единице j-го вида сырья;
b₁ – минимальное количество i-го питательного вещества, содержащегося в единице смеси;
c_j – стоимость единицы сырья j;
q – минимальный общий вид смеси.

Пример №3 . В заводской лаборатории создается антифрикционный сплав (оловянистый баббит), который должен содержать: олова — не меньше 15%, сурьмы — не меньше 15%, свинца — около 70%. Есть четыре сплава, процентный состав и цены на которые приведенные в таблице:

По материалам math.semestr.ru

Многие практические задачи сводятся к случаю, когда необходимо найти либо максимум или минимум функции f(x₁, x₂,…, x_n):

и на переменные x₁, x₂, …, x_n наложены различные ограничения в виде неравенств или равенств:

Функция (1.1) называется функцией цели (целевой функцией, линейной функцией, линейной формой).

Соотношения (1.2) – (1.5) представляют собой запись условий ограничений (неравенств ограничений, система ограничений) функции (1.1).

Программирование– нахождение экстремума (max или min) функции (1.1) при заданных ограничениях (1.2) – (1.5), т.е. другими словами, найти оптимальное решение функции f(x₁, x₂, …, x_n) при наложенных ограничениях.

Линейное программирование (задачи линейного программирования) – это нахождение оптимального решения (оптимального плана) при условии, что функция цели f(x₁, x₂, …, x_n) линейна, все условия ограничения линейны и x₁, x₂, …, x_n ≥ 0.

Пусть имеется n переменных x₁, x₂, …, x_n. Необходимо найти такие значения этих переменных, чтобы достигался max или min функции цели (линейной):

при соответствующей системе ограничений:

(1.7)

Для конкретной практической задачи система ограничений может содержать любой из знаков неравенства. Но сами переменные x₁, x₂, …, x_n всегда должны быть больше либо равны нулю.

Необходимо найти решение системы ограничений X=(x₁, x₂, …, x_n), при котором функция цели (1.6) будет принимать экстремальное значение (max или min). При этом данное решение должно удовлетворять системе ограничений (1.7). Нахождение такого решения и составляет задачу линейного программирования (ЛП).

Задачу линейного программирования можно записать и в более краткой форме:

(1.8)

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

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

(1.9)

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

(1.10)

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

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

i — номер группы оборудования (i=1,2,…,m);

j — номер вида изделия (j=1,2,…,n) ;

a_ij — норма времени на обработку единицы j-ого изделия на i-й группеоборудования;

b_i — фонд времени работы i-й группы оборудования;

c_j — прибыль на одно изделие j-ого вида;

x_j — планируемое количество единиц j-ого изделия;

— искомый план производства.

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

На обработку x₁ единиц первого изделия на i-й группе оборудования будет затрачено a_i1x₁ единиц времени; на обработку x₂ единиц второго изделия на той же группе оборудования будет затрачено a_i2x₂ единиц времени и т. д.

Необходимое время на обработку всех изделий на i-й группе оборудования будет равно сумме ( ).

Эта сумма не может превышать фонд времени работы i-й группыоборудования, т. е. должна быть меньше либо равна . Выписывая такие условия для всех m групп оборудования, формирется система:

(1.11)

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

.

При плане производства ( ) прибыль предприятия будет равна

. (1.12)

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

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

Исходные параметры задачи могут быть представлены в виде матрицы А удельных затрат ресурсов, вектора В объемов ресурсов и вектора С удельной прибыли:

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

Производственное объединение получило заказ на изготовление n видов изделий в количествах d₁, d₂, …, d_n соответственно. Объединению подчинены m предприятий, на каждом из которых может быть выполнен заказ на любое изделие.

b_i — действительный фонд времени работы i-го предприятия;

a_ij и c_ij — соответственно норма расхода времени и себестоимость изготовления единицы j-го изделия на i-м предприятии;

x_ij — число изделий j-го вида, которое поручается изготовить i-му предприятию.

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

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

, где ,

и будет изготовлено необходимое количество изделий каждого вида

, .

, где , .

Задача о диете. Необходимые в дневном рационе питания m видов питательных веществ содержатся в n видах продуктов.

a_ij — количество единиц i-го питательного вещества в единице j-го продукта;

b_i — необходимое количество единиц i-го питательного вещества в дневном рационе;

c_j — стоимость единицы j-го продукта.

Задача состоит в том, чтобы найти план покупок , минимизирующий суммарные затраты:

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

, где ,

причем по смыслу задачи , где .

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

b₁, b₂ — грузоподъемность и вместимость грузового отсека корабля;

x_j — количество единиц j-го типа груза, который мы хотели бы погрузить.

Задача состоит в том, чтобы найти набор , максимизирующий суммарную ценность

при ограничениях по грузоподъемности и вместимости

,

где , , x_j – целое, .

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

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

Для производства компьютерных столов I-го и II-го видов требуются три типа ресурсов: дерево, пластик и трудозатраты. Потребности в ресурсах для производства одного стола каждого вида, запасы ресурсов, а также прибыль от реализации одного стола каждого вида, заданы в таблице 1.1.:

По материалам lektsia.com

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

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

Актуальность работы заключается в том, что использование методов оптимизации, в том числе и линейного программирования позволяет с максимальной выгодой и минимальными расходами разрешить задачу о диете, составить наиболее оптимальный рацион, а также сбалансированный режим питания. Разрешение оптимизационной задачи о диете играет важную роль в составлении специализированного рациона питания здоровых и больных людей, а также в сельском хозяйстве при составлении режима кормлении животных[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.

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

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

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

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

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

Если все ограничения задачи заданы уравнениями, то модель такого вида называется канонической. Если хоть одно из ограничений дано неравенством, то модель неканоническая. [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* представляет собой вектор, определяемый последовательностью оптимальных пошаговых управлений:

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

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

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

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

Этот максимум (или минимум) определяется по всем возможным для 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.1. Ограничения по опасным отходам. Количество, образованных опасных отходов, равно 0,5x₁+ 1,2x₂, при этом по условию оно не должно превосходить 600 тонн, т.е.

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

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

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

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

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

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

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

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

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

Рисунок 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 неизвестными

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Минимальные вещества незаменимые компоненты

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

Содержание питательных веществ в 100г продукта

По материалам scienceforum.ru