1.
Задача о рационе. Экономическая постановка и построение математической модели задачи.
Экономическая постановка
В некотором фермерском хозяйстве производится откорм животных. Для откорма используется n видов кормов. Известно содержание питательных веществ (кальций, фосфор и др.) в единице корма каждого вида. Для полноценного питания животных необходимо потребление питательных веществ не меньше заданных количеств. Известна стоимость единицы каждого корма. Необходимо определить рацион кормления животных, при котором общие затраты на откорм будут минимальными.
Математическая постановка:
Введём обозначения заданных параметров:
j – индекс вида кормов, j = 1, n
i – индекс вида питательных веществ, i = 1, m
аij – содержание i-го питательного вещества в единице корма j-го вида;
Аi – необходимое суточное потребление питательного вещества i –го вида;
Сj – стоимость единицы кормов j-го вида.
Введём неизвестные переменные:
хj – суточный объём кормления животных j-м видом корма.
В терминах введённых обозначений данная задача запишется следующим
образом:
z = С1x1 + С2x2 + … +Сnxn → min
 |
а11x1 + а12x2 +…+ а1nxn ≥ A1
а21x1 + а22x2 +…+ а2nxn ≥ A2
…………………………….
am1x1 + аm2x2 +…+ а mnxn ≥Am
xj ≥ 0, j = 1, n
Задача о выборе назначениях или о назначениях. Экономическая постановка и построение математической модели задачи.
Экономическая постановка :
Имеются n видов работ и n исполнителей. Каждый из исполнителей может выполнить любую, но только одну работу. Задана себестоимость выполнения каждой работы, каждым исполнителем. Необходимо закрепить исполнителей за работой таким образом, чтобы общая стоимость выполнения работ была минимальной.
Математическая постановка .
Введём обозначения заданных параметров.
i – индекс работ, i = 1, m
j – индекс исполнителей, j = 1, n
Cij – себестоимость выполнения i-той работы j-тым исполнителем.
Введём неизвестные переменные. В данной задаче неизвестные переменные могут принимать только два значения 0 или 1. Такие переменные называются нулевыми.
1 - если за i-той работой закреплён j-тый исполнитель;
x ij =
0 - в противном случае.
В терминах введённых обозначений данная задача запишется следующим образом:
z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n -1)x(n-1)(n-1) + Сnnxnn → min
I группа ограничений.
За каждой работой должен быть закреплён только один исполнитель:
x11 + x12 +…+ x1n = 1
x21 + x22 +…+ x2n = 1
……………………..
xn1 + xn2 +…+ xnn = 1
II. группа ограничений.
Каждый исполнитель может выполнить только одну работу:
x11 + x21 +…+ xn1 = 1
x12 + x22 +…+ xn2 = 1
……………………..
x1n + x2n +…+ xnn = 1
x ij = { 0,1} i = 1, n ; j = 1, n
Понятие гиперплоскости полуплоскости, опорная гиперплоскость.
Геометрич. интерпретация системы ограничений и целевой функции в задачи ЛП
Двойственная задача
Пусть предприятие по какой-либо причине не может выпускать продукцию. Для того, чтобы уменьшить затраты простоя, предприятие может реализовать сырье, которое у него имеется. По каким ценам нужно реализовать сырье?
уi- цена i- го вида сырья имеющегося на предприятии.
а11у1+а21у2+…+ ат1ут≥с1
а12х1+а22у2+…+ ат2хп≥с2
……………….. (1’)
а1пу1+а2пу2+…+ атпут≥сп
уi≥0, j = 1,m(2’)
F = b1y1+b2y2+…+bmym ->min(3’)
Требования, предъявляемые к задачам, решаемым методом ДП
Динамическое программирование—математический метод для нахождения оптимальных решений многошаговых задач. Многошаговым является процесс, развивающийся во времени и распадающийся на ряд шагов, или этапов.
Одна из особенностей метода динамического программирования состоит в том, что принятые решения по отношению к многошаговым процессам рассматривается не как единичный акт, а как целый комплекс взаимосвязанных решений. Эту последовательность взаимосвязанных решений называют стратегией.Цель оптимального планирования—выбрать стратегию, обеспечивающую получение наилучшего результата с точки зрения заранее выбранного критерия. Такую стратегию называют оптимальной.
Другой важной особенностью метода является независимость оптимального решения, принимаемого на очередном шаге, от предистории, т.е. от того, каким образом оптимизируемый процесс достиг теперешнего состояния. Оптимальное решение выбирается лишь с учетом факторов, характеризующих процесс в данный момент.
Метод динам программ характеризуется также тем, что выбор оптимального решения на каждом шаге должен производиться с учетом его последствий в будущем. Это означает, что, оптимизируя процесс на каждом отдельном шаге, ни в коем случае нельзя забыть обо всех последующих шагах.
64.Экономическая постановка и построение математической модели задачи, решаемой методом ДП(на примере задачи о распределении капиталовложений). Рекуррентное соотношение Беллмана.
Предварительно поясним, что метод динамического программирования применяется прежде всего к тем задачам, в которых оптимизируемый процесс (или ситуация) разворачивается в пространстве или во времени, или в том и другом.
Пусть сам процесс (ситуация) настолько сложен, что нет возможности его оптимизировать известными методами. Тогда по методу динамического программирования СЛОЖНЫЙ процесс (операция, ситуация) разбивается (членится) на ряд этапов (шагов). Эта разбивка во многих случаях является естественной, но в общем случае привносится искусственно. Например, при рассмотрении какой-либо партии игры в шахматы любой ход каждого из игроков как раз и служит
разбивке всей партии на отдельные шаги (этапы). А в военной операции по преследованию одной ракеты другой весь непрерывный процесс приходится искусственно разбивать на этапы, например, через каждую секунду наблюдения. Метод динамического программирования позволяет оптимизацию всего сложного процесса заменить условной оптимизацией по каждому из этапов
(шагов) с последующим синтезом оптимального управления всем процессом. При этом метод предусматривает, что условная оптимизация на отдельном шаге (этапе) делается в интересах, прежде всего, всей операции.
Все вычисления, дающие возможность найти оптимальное значение эффекта, достигаемого за n шагов, fn(S0), проводятся по формуле (1), которая носит название основного функционального уравнения Беллмана или рекуррентное соотношение. При вычислении очередного значения функции fn-1 используется значение функции fn-(l+1), полученное на предыдущем шаге, и непосредственное значение эффекта Rl+1(Sl,Ul+1), достигаемого в результате выбора решения Ul+1 при заданном состоянии системы Sl. Процесс вычисления значения функции fn-1(l=0,n-1)
Осуществляется при естественном начальном условии f0(Sn)=0, которое означает, что за пределами конечного состояния системы эффект равен нулю.
65. Задача о распределении капитальных вложений (пример).
Для решения задачи об оптимальном распределении капиталовложений мы будем пользоваться функциональным уравнением Беллмана. Сначала с помощью простейшей ситуации проиллюстрируем вывод функционального уравнения Беллмана, а потом на примере докажем, как использовать это уравнение для решения интересующей нас задачи.
Начнем с оптимального распределения выделенных капиталовложений в сумме К между двумя предприятиями. Плановые отделы предприятий на основе своих расчетов сформировали функции дохода q(x) для предприятия П1 и h(x) - для предприятия П2. Функции эти означают, что если первое или второе предприятие получит капиталовложение и размере х, то первым предприятием
будет получен доход q(x), а вторым h(x), причем величина x может принимать непрерывные или известные дискретные значения от 0 до К.
Итак, пусть предприятию П1 выделены капиталовложения в сумме х, тогда предприятию П2 выделяется сумма К - х. В этом случае от первого предприятия будет получен доход q(x), а от второго - h(К - x). Если капиталовложения К были выделены на один плановый период, то общий доход от двух предприятий составит R(K, x) = q(x) + h(K - x). Очевидно, что x и соответственно К - x надо выбирать такими, чтобы R(K, x) приняло свое максимальное значение, которое мы обозначим через F(K):
Эта запись является как бы остовом для более полных записей
функционального уравнения Беллмана. УСЛОЖНИМ нашу задачу, распределив капиталовложения на два плановых периода (два этапа). Пусть изначально решено первому предприятию П1 выделить сумму х, а второму К – х. В целом доход получался бы равным R(K, x) = q(x) +
h(K - x). Если мы будем иметь в виду, что капиталовложения распределяются на 2 периода (2 этапа), то на первом предприятии остаток капиталовложений составит .x, где 
, а на втором - .(К - х), где 
Соответственно доходы за второй период составят q(.x) -по первому предприятию и h[.(K - x)] - по второму. Оптимизацию по методу динамического программирования, как правило, начинают с концевого этапа. Поэтому начнем со второго этапа, обозначив F1 максимально возможный доход от двух предприятий на втором
этапе. Получим
Затем к рассмотренному последнему (в нашем случае второму) этапу как бы пристраиваем предшествующий (у нас первый) этап и находим максимальный доход от двух этапов вместе:
Аналогичным образом для n этапов получаем
где Fn-1 - целевая функция, дающая наилучший результат за последние (n - 1) этапы. Полученное функциональное уравнение Беллмана носит рекуррентный характер, т.е. связывает значение Fn со значением Fn-1.
В более общем начертании уравнение Беллмана имеет вид
где 
, Fn-1 - максимальный доход за (n - 1) последних этапов, Fn -
максимальный доход за все n этапов.
Параметрическое программирование – раздел математического программирования, посвящённый исследованию задач оптимизации, в которых условия допустимости и целевая функция зависят от некоторых детерминированных параметров.
1.
направления использования мат. моделей в экономике.
Математические модели позволяют определять оптимальные значения неизвестных параметров экономических систем, что является важным в процессе принятия решений. Математическое программирование как раз и дает аппарат, позволяющий оптимизировать процесс отбора лучших вариантов планов в процессе управления в экономических системах.
Используется в матстастике, оптимизационные методы, методы экономич. кибернетики, экспериментальные задачи.
При изучении сложных процессов и явлений в экономике очень часто применяется моделирование – вполне определенное конкретное отображение рассматриваемых характеристик изучаемого объекта. Суть его состоит в том, что изучаемое явление воспроизводится в экспериментальных условиях с помощью модели в другом временном и пространственном масштабе. Модель – это специально создаваемый объект, с помощью которого воспроизводится вполне определенные характеристики исследуемой системы с целью ее изучения. Математическое моделирование является наиболее совершенным и вместе с тем эффективным методом получения информации об исследуемом объекте. Оно представляет собой мощное средство анализа в экономике. Результаты исследования с помощью моделей будут иметь практический интерес тогда, когда построенная модель будет достаточно адекватна рассматриваемому явлению, т.е. достаточно хорошо отображать реальную ситуацию.
2. математическое програмирование как наука, его структура. Задачи оптимизации. Трудности применения классических методов оптимизации при решении экономических задач.
Математическое программирование – это раздел прикладной математики, который разрабатывает теоретические основы и методы решения экстремальных задач.
К математическому программированию относятся ряд разделов, основные из которых следующие:
1. Линейное программирование. К данному разделу относятся задачи, в которых неизвестные переменные входят в математические соотношения в первой степени.
2. Нелинейное программирование. К данному разделу относятся задачи, в которых целевая функция и (или) ограничения могут быть нелинейными.
3. Динамическое программирование. К данному разделу относятся задачи, в которых процесс решения можно разбить на отдельные этапы.
4. Целочисленное программирование. К данному разделу относятся задачи, в которых неизвестные переменные могут принимать только целочисленные значения.
5. Стохастическое программирование. К данному разделу относятся задачи, в которых содержатся случайные величины в целевой функции или ограничениях.
6. Параметрическое программирование. К данному разделу относятся задачи, в которых коэффициенты при неизвестных переменных в целевой функции или ограничениях зависят от некоторых параметров.
Для решения задач математического программирования сложно использовать классические методы нахождения экстремума т. к. в задачах математического программирования целевая функция достигает своего экстремального значения на границе области допустимых значений неизвестных переменных, а производные в граничных точках не существуют. Полный перебор допустимых точек невозможен из-за значительного их количества.
3. Понятие математической модели, виды мат. моделей
Математическая модель – это записанная в математических символах и выражениях абстракция реального явления или процесса. Математические модели экономических процессов и явлений называются экономико-математическими моделями
Модели делятся на:
1. линейные, в которых все зависимости описываются линейными соотношениями,
2. нелинейные, в которых имеются нелинейные соотношения;
3. стохастические, в которых учитывается случайный характер изучаемых процессов,
4. детерминированные, в которых учитываются усредненные значения всех параметров.
5. динамические модели, в которых исследуемые системы рассматриваются в развитии в течение нескольких периодов,
6. статические, в которых фактор времени не учитывается.
7. оптимизационные модели, в которых выбор осуществляется в зависимости от экстремизации некоторого критерия,
8. неоптимизационные, в которых критерия оптимальности нет.
9. макромодели (всего хозяйства в целом)
10. микромодели (отдельных звеньев или процессов экономики).
Виды математических моделей: линейные, нелинейные, квадратические, целочисленные, дискретные, параметрические, дробно-линейные, динамические, стохастические
4. Общая постановка задач математического програмирования.
Рассмотрим общую постановку задачи математического программирования.
Общая задача математического программирования состоит в определении оптимального значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений. Математически определение оптимального решения выражается в нахождении экстремума (max или min) функции многих переменных
Z = f (x1, x2, …, xn)
в заданной области изменения этих переменных
gi (x1, x2,…, xn)Ribi (i = 1, 2,…, m),
где Ri - один из знаков ≥, =, ≤.
5. Задача об оптимизации плана выпуска продукции. Экономическая постановка и построение математической модели задач.
Экономическая постановка:
Предприятие производит n видов продукции с использованием m видов сырья. Для производства единицы продукции используется строго определённое количество сырья того или иного вида. Сырьё каждого вида на предприятии ограничено. Предприятие получает определённую прибыль от реализации единицы продукции. Необходимо найти такой план производства продукции, при котором предприятие получит максимальную общую прибыль.
Математическая постановка:
Введём обозначения заданных параметров.
Пусть j – индекс вида продукции j = 1, n
i– индекс вида ресурсов i = 1, m
аij – затраты сырья i-го вида на производство единицы продукции j-го вида;
Аi – заданное ограничение на имеющийся объём ресурсов i-го вида;
Рj – прибыль, получаемая от реализации единицы продукции j-го вида;
Введём неизвестные переменные:
xj – объём выпускаемой продукции j-го вида.
В терминах введённых обозначений данная задача запишется следующим
образом:
z = Р1x1 + Р2x2 + … +Pnxn → max
а11x1 + а12x2 +…+ а1nxn ≤ A1
а21x1 + а22x2 +…+ а2nxn ≤ A2
…………………………….
a m1x1 + а m2x2 +…+ а m n xn ≤ Am
xj ≥ 0, j = 1, n
Дата: 2019-12-22, просмотров: 281.
