Экономико математические методы задачи с решением и примерами

Прежде чем изучать готовые решения задач по экономико математическим методам, нужно знать теорию, поэтому для вас я подготовила краткую теорию по предмету «Экономико математические методы» и задачи с решением и примерами.

Эта страница подготовлена для школьников и студентов.

Если что-то непонятно — вы всегда можете написать мне в WhatsApp и я вам помогу!

Экономико-математические методы

Экономико-математические методы (ЭММ) — это математическое описание экономического объекта или процесса с целью их исследования и управления ими. Это математическая запись решаемой экономической задачи.

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

Классические задачи оптимизации

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

Возможно эта страница вам будет полезна:

Предмет экономико-математические методы (ЭММ)

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

Задача на безусловный экстремум

В основе методов решения классических задач оптимизации лежит теория дифференциального исчисления.

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

Если точка является точкой экстремума функции, то она является стационарной точкой функции, т.е. частные производные в этой точке равны нулю:

Таким образом, экстремумы функции следует искать среди ее стационарных точек. Однако, возможно, не каждая стационарная точка является точкой экстремума.

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

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

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

Возможно эта страница вам будет полезна:

Решение экономико математических методов

Пример задачи №1

Исследовать на экстремум функцию

Решение:

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

Данная система имеет два решения

Найдены две стационарные точки: и . Проверим, являются ли они точками экстремума. Составим матрицу Гессе и вычислим ее значение в точке .

Вычислим главные диагональные миноры матрицы .

Следовательно, точка не является точкой экстремума функции. Составим матрицу Гессе в точке :

Вычислим главные диагональные миноры матрицы .

Следовательно, точка является точкой минимума функции,

Пример задачи №2

Исследовать на экстремум функцию

Решение:

Найдем стационарную точку из условий

Итак,

Исследуем статус этой точки, т.е. проверим, является ли она точкой экстремума. Для этого вычислим матрицу Гессе:

Вычислим главные диагональные миноры матрицы Гессе.

Минор второго порядка отрицателен, значит, в точке экстремума нет.

Задача на условный экстремум. Метод множителей Лагранжа

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

(последнее условие называют также условием связи).

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

Возможно эта страница вам будет полезна:

Решение задач по ЭММ

Пример задачи №3

Найти экстремум функции , при условии .

Решение:

Из уравнения связи выразим через и подставим полученное выражение в функцию :

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

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

Алгорищм метода множителей Лагранжа

• Составить функцию Лагранжа:

где — множитель Лагранжа, соответствующий -му ограничению.

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

• Решив получившуюся систему из уравнений, найти стационарные точки.

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

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

Пример задачи №4

Найти экстремумы функции

при условии

Решение:

Заметим, что функции

непрерывны и имеют непрерывные частные производные. Составим функцию Лагранжа:

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

Получаем две стационарные точки:

Принимая во внимание характер целевой функции, линиями уровня которой являются плоскости, и функции (эллипс) заключаем, что в точке функция принимает минимальное значение, а в точке максимальное.

В области решений системы

найти максимальное и минимальное значение функции

при условии

Решение:

Пересечением области допустимых решений и прямой

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

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

Решая систему, получаем стационарную точку . Сравним значения целевой функции в точках :

Следовательно,

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

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

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

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

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

при ограничениях:

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

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

Если в задаче линейного программирования ограничения заданы в виде неравенств

то говорят, что задача представлена в симметричной форме записи.

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

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

Построение математических моделей

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

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

— запасы -го вида ресурса;

— затраты -го вида ресурса на производство единицы -го вида продукции;

— прибыль от реализации единицы -го вида продукции. Данные задачи можно представить в виде таблицы.

Обозначим через планируемый выпуск -го вида продукции; — план выпуска продукции. Тогда прибыль от реализации всей выпускаемой продукции составит

Составим ограничения по ресурсам. Найдем расход ресурса первого вида при данном плане выпуска:

Ресурса первого вида имеется в наличии условных единиц, т.е. получаем ограничение

Аналогично составляем ограничения по всем остальным видам ресурсов.

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

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

при ограничениях

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

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

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

Введем обозначения:

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

— минимальное содержание -го питательного вещества в суточной диете;

— цена единицы — го продукта.

Данные задачи можно представить в виде таблицы.

Пусть единиц -го продукта включается в суточную диету, тогда

—суточная диета. Цена диеты:

Содержание первого питательного вещества в диете составит

и это количество должно быть не менее чем единиц:

Аналогично составляем ограничения по всем видам питательных веществ.

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

Математическая модель задачи: найти минимум функции

при ограничениях:

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

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

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

Составим математическую модель данной задачи. Введем обозначения: — номер вида заготовки, ; — номер варианта раскроя прутка, ;

— количество заготовок -го вида, получаемых из одного прутка, разрезаемого по -му варианту;

— требуемое число заготовок -го вида;

— длина концевого отрезка, оставшегося от одного прутка при разрезании прутка по -му варианту.

Данные задачи можно представить в виде таблицы.

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

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

Следовательно, общая длина концевых отрезков при разрезании прутков по всем вариантам составляет

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

Из одного прутка, разрезаемого по первому варианту, получают шт. заготовок первого вида, а из прутков — шт.; по второму вариант) из одного прутка получают шт., а из прутков — шт. и т.д., по -му варианту — шт. Отсюда получаем первое ограничение

Аналогично получаем ограничения по всем заготовкам.

Кроме того, так как число прутков не может быть отрицательным.

Математическая модель задачи: найти наименьшее значение функции

при ограничениях:

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

Графический метод решения

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

при ограничениях:

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

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

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

Пусть — некоторое число. Прямая является линией уровня целевой функции. В каждой точке этой прямой целевая функция принимает одно и то же значение, равное . Вектор — градиент целевой функции

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

• Область допустимых решений — выпуклая неограниченная область.

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

Алгоритм графического метода:

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

Возможно эта страница вам будет полезна:

Помощь по экономико математическим методам

Пример задачи №5

Найти наименьшее и наибольшее значения функции при ограничениях:

Решение:

1) Строим область допустимых решений (ОДР). Она представляет собой выпуклый четырехугольник (рис. 2.1).

2) Строим вектор (3; 4) и перпендикулярно ему линии уровня, проходящие через область.

3) Из рисунка 2.1 видно, что наиболее удаленной в направлении градиента угловой точкой является точка , так как через нее проходит самая дальняя линия уровня . Следовательно в точке целевая функция принимает наибольшее значение, т.е. . Через угловую точку проходит ближайшая линия уровня , следовательно, функция в точке принимает наименьшее значение, т.е.

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

Решим систему, составленную из уравнений этих прямых

Получим

Точка лежит на пересечении второй и четвертой прямых. Решим систему, составленную из уравнений этих прямых

Получим

Пример задачи №6

Найти наибольшее значение функции

при ограничениях:

Решение:

1) Строим область допустимых решений. Получим пятиугольник (рис.22).

2) Строим вектор (2; 4) и перпендикулярно ему линию уровня .

3) В данном случае линии уровня параллельны прямой, проходящей через точки и .

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

Получим

Точка лежит на пересечении первой и второй прямых. Решая систему, составленную из уравнений этих прямых, получим

Так как целевая функция принимает наибольшее значение в любой точке отрезка , то

Пример задачи №7

Найти наибольшее значение функции

при ограничениях:

Решение:

1) Строим область допустимых решений.

ОДР представляет собой выпуклую неограниченную область (рис. 2.3).

2) Строим вектор (2; 5) и линию уровня , перпендикулярную к вектору .

3) Так как в направлении вектора с можно провести сколь угодно удаленную линию уровня, проходящую через ОДР, следовательно, функция в этой области не достигает своего наибольшего значения

Пример задачи №8

Найти наибольшее значение функции при ограничениях:

Решение:

Выразим базисные переменные через свободные:

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

Получим:

Так как

то получим систему неравенств

Исходная задача сведена к новой, которую можно решить графически.

Решая эту задачу графически, получим

Найдем оптимальное решение исходной задачи, для этого найдем значения базисных переменных при

Тогда

Возможно эта страница вам будет полезна:

Курсовая работа по экономико математическим методам

Симплексный метод решения

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

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

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

Алгоритм симплексного метода

1. Привести задачу к каноническому виду.
2. Найти неотрицательное базисное решение системы ограничений.
3. Рассчитать оценки свободных переменных по формуле

где — коэффициенты при свободной переменной ,

— коэффициенты при базисных переменных в целевой функции,

— коэффициент при свободной переменной в целевой функции.

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

а) если все оценки , то найденное решение оптимально и задача решена;

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

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

Замечание 1. Критерием оптимальности для ЗЛП на минимум является неположительность оценок, т.е. все

Замечание 2. В ЗЛП максимум и минимум целевой функции понимаются как глобальные.

Пример задачи №9

Найти наибольшее значение функции

при ограничениях:

Решение:

Задача имеет канонический вид. Найдем исходное опорное решение.

Проверим это решение на оптимальность.

Найденное решение не оптимально, так как . Введем в базис свободную переменную с отрицательной оценкой .

Так как среди оценок нет отрицательных чисел, то второе опорное решение оптимально.

Пример задачи №10

Найти наибольшее значение функции

при ограничениях:

Решение:

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

Найдем исходное опорное решение.

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

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

Возможно эта страница вам будет полезна:

Контрольная по экономико математическим методам

Метод искусственного базиса

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

Алгоритм метода искусственного базиса

1. Привести задачу линейного программирования к каноническому виду.
2. Построить -задачу. Для этого в каждое уравнение системы ограничений, не имеющее переменной, исключенной из других уравнений, необходимо ввести искусственную переменную с коэффициентом 1, не меняя знак равенства. Искусственные переменные также вводятся и в целевую функцию с коэффициентом — (или +, если решается задача на минимум), где — сколь угодно большое число.
3. Выписать исходное опорное решение.
4. Рассчитать оценки свободных переменных по формуле

где

— коэффициенты при свободной переменной

— коэффициенты при базисных переменных в целевой функции,

— коэффициент при свободной переменной в целевой функции; и записать оценки в двух строках и : строка содержит коэффициенты при множителе в оценке ; строка содержит другую часть оценки.

• Решить -задачу симплексным методом. Критерий оптимальности проверяется по строке так же, как и в симплексном методе. Учесть следующие возможные случаи:

а) если в оптимальном решении -задачи все искусственные переменные равны 0, то соответствующее решение исходной задачи является оптимальным и экстремумы целевых функций равны;

б) если в оптимальном решении -задачи хотя бы одна из искусственных переменных не равна 0, то исходная задача не имеет оптимального решения из-за несовместности системы ограничений;

в) если -задача не имеет оптимального решения, то исходная задача также не имеет оптимального решения.

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

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

Пример задачи №11

Найти наибольшее значение функции

при ограничениях:

Решение:

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

Решим -задачу симплексным методом.

является оптимальным решением -задачи, тогда соответствующее ему решение

является оптимальным решением исходной задачи, причем

Теория двойственности

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

В зависимости от вида исходной задачи различают симметричные, несимметричные и смешанные пары двойственных задач.

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

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

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

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

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

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

Итак, двойственная задача состоит в нахождении наименьшего значения функции

при ограничениях:

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

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

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

при ограничениях:

Двойственная задача состоит в нахождении наименьшего значения функции:

при ограничениях:

Пусть исходная задача имеет вид:

при ограничениях:

Тогда двойственная задача имеет вид:

при ограничениях:

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

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

Пусть исходная задача имеет вид:

при ограничениях:

Тогда двойственная задача имеет вид:

при ограничениях:

Возможно эта страница вам будет полезна:

Заказать работу по экономико математическим методам

Пример задачи №12

Составить двойственную задачу к следующей: найти наибольшее значение функции

при ограничениях:

свободны по знаку.

Двойственная задача: найти наименьшее значение функции

при ограничениях:

свободны по знаку, .

Нахождение решения двойственных задач

Первый способ нахождения решения двойственной задачи в симметричной паре основан на применении основных теорем двойственности.

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

Если целевая функция одной из задач не ограничена на ОДР, то система ограничений двойственной задачи не совместна, и наоборот.

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

Пример задачи №13

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

Данная задача имеет оптимальное решение

Составим двойственную задачу:

Из первой теоремы двойственности следует, что

Применим вторую теорему двойственности: так как в оптимальном решении исходной задачи

то на оптимальном решении двойственной задачи первое и второе ограничения двойственной задачи выполняются как равенства

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

Получим систему трех уравнений с тремя неизвестными:

Решая систему, получим

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

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

Запишем системы ограничений симметричной пары двойственных задач:

Приведем их к каноническому виду:

где — основные, — балансовые: — балансовые, — основные. Если исходная задача решена симплексным методом, то

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

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

Пример задачи №14

Найти наименьшее значение функции

при ограничениях:

Решение:

Составим двойственную задачу:

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

Целевая функция остается без изменения.

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

Тогда по первой теореме двойственности

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

Тогда

Нахождение решения двойственной задачи в несимметричной паре

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

Пример задачи №15

Найти наибольшее значение функции

при ограничениях:

Данная задача имеет оптимальное решение

Составим двойственную задачу: найти наименьшее значение функции

при ограничениях:

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

По второй теореме двойственности, так как в оптимальном решении исходной задачи

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

Решая эту систему, получим

Экономическая интерпретация двойственных задач Рассмотрим экономическую интерпретацию двойственных задач на примере задачи об оптимальном использовании ресурсов. Исходная задача: найти наибольшее значение функции

при ограничениях:

Двойственная задача: найти наименьшее значение функции

при ограничениях:

Установим размерность двойственных переменных которые еще называют двойственными оценками.

Из ограничений двойственной задачи ; следует, что размерность произведения совпадает с размерностью , т.е. (знак означает эквивалентность размерности), отсюда

Таким образом, измеряется в рублях на единицу ресурса. Назовем yt условной ценой или оценкой -го ресурса. Рассмотрим свойства оценок.

1) Оценки — мера дефицитности ресурса. Дефицитный ресурс полностью используется при оптимальном плане и имеет положительную оценку, т.е.

Недефицитный ресурс используется не полностью и имеет нулевую оценку, так как если

2) Оценки — мера влияния свободных членов системы ограничений исходной задачи на значение целевой функции, так как

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

Пример задачи №16

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

Составим двойственную задачу:

Найдем решения обеих задач:

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

Целочисленное программирование

Метод Гомори

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

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

при ограничениях:

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

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

Напомним, что целой частью числа а называется наибольшее целое число, не превышающее . Дробной частью числа а называется разность между числом и его целой частью. Целую часть числа обозначают [], а дробную часть — , т.е. .

Алгоритм метода Гомори

1. Отбросив условие целочисленности, решить исходную задачу симплексным методом. Если получится целочисленное оптимальное решение, то задача решена.
2. Если в оптимальном решении не все переменные целочисленные, составить дополнительное ограничение (сечение Гомори). Сечение строится по базисной переменной, имеющей наибольшую дробную часть. Пусть в оптимальном решении базисная переменная, имеющая наибольшую дробную часть

где — множество индексов свободных переменных.

Разбить все коэффициенты и свободный член (2.2) на два слагаемых — целую и дробную часть. Неравенство

называется сечением Гомори. Дополнительное ограничение имеет вид

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

Пример задачи №17

Найти наибольшее значение функции

при ограничениях:

Решим задачу симплексным методом без учета целочисленности Для этого приведем ее к каноническому виду

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

Сечение примет вид

или

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

Решим задачу симплексным методом.

Данное решение целочисленное, значит, исходная задача решена.

Дадим геометрическую иллюстрацию метода Гомори по задаче из предыдущего примера. Областью допустимых решений является четырехугольник (Рис.2.4). Оптимальное решение задачи совпадает с точкой . Наибольшую дробную часть имеет переменная , ее целая часть равна 5.

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

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

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

Имеется пунктов производства однородного продукта с объемами производства и пунктов потребления с объемами потребления . Известна стоимость перевозки единицы продукта от каждого пункта производства до каждого пункта потребления:

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

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

то это задача закрытого типа. В противном случае задачу называют задачей открытого типа.

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

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

Алгоритм решения транспортной задачи закрытого типа

1. Найти первоначальное опорное решение (распределение поставок), например, методом «минимального тарифа».
2. Проверить решение на оптимальность методом потенциалов. Для этого найти потенциалы для каждой строки и столбца из условия

справедливого для занятых клеток. Первоначально положить .

• Для всех свободных клеток рассчитать оценки

Если все , то найденное решение оптимально.

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

• Если решение не оптимально, необходимо перейти к новому опорному решению (новому плану поставок), которое ближе к оптимальному, чем предыдущее. Необходимо ввести в базис свободную переменную имеющую наибольшую положительную оценку. Для этого построить цикл для соответствующей этой переменной клетки. Цикл строится по занятым клеткам и имеет прямоугольную конфигурацию. Вершины цикла занумеровать, начиная со свободной клетки. Среди клеток с четными номерами найти наименьший объем поставок X и перераспределить его по циклу: в клетки с нечетными номерами его надо прибавить к поставке, в клетки с четными номерами вычесть. Выписать новое решение и значение целевой функции.
• Переход в п. 2.

Пример задачи №18

Найдем исходное опорное решение по методу «наименьшего тарифа» и оценим это решение на оптимальность.

По занятым клеткам составим систему уравнений:

Получим 7 уравнений и 8 неизвестных.

Если

Находим оценки свободных клеток по формуле

Найденное решение не оптимально, так как

Построим цикл для клетки (1; 5). В таблице в клетку (1; 5) даем поставку величиной , тогда нарушится баланс в первой строке и в пятом столбце. Это же количество поставок вычтем из поставок клеток (1; 4) и (2; 5) и прибавим к (2; 4).

Цикл построен.

Определим

Построим вторую таблицу, в которой изменятся только клетки цикла.

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

Находим оценки свободных клеток:

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

Строим третью таблицу.

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

Находим оценки свободных клеток:

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

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

Если суммарные поставки меньше суммарных потребностей, т.е.

то вводят фиктивный пункт производства с объемом

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

Если суммарные поставки больше суммарных потребностей, т.е.

то вводят фиктивный пункт потребления с объемом

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

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

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

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

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

Если два решения и являются оптимальными, то множество всех оптимальных решений имеет вид:

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

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

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

при условиях:

причем функции и могут быть нелинейными.

Графический метод решения

Задачи нелинейного программирования, содержащие две переменные, можно решать графическим методом. Основные принципы решения те же, что и в линейном программировании.

Алгоритм графического метода

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

Пример задачи №19

Найти глобальные экстремумы функции

при ограничениях

Решение:

Построим область допустимых решений. Она состоит из двух частей: и . Линиями уровня являются параллельные

Градиент функции . Следовательно, функция достигает своего глобального максимума в точке , а в точке —глобального минимума,

Очевидно, что в точке функция имеет локальный минимум, а в точке — локальный максимум.

Пример задачи №20

Найти глобальные экстремумы функции при ограничениях

Решение:

Множество является областью допустимых решений. Линии уровня функции

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

минимум — в точке

Пример задачи №21

Определить глобальный минимум функции

на множестве решений системы

Решение:

Множество допустимых решений является выпуклым. Линии уровня функции — эллипсы с центром в точке (3; 6). Минимум достигается в точке касания прямой и некоторого эллипса из семейства линий уровня. Из уравнения прямой определим ее вектор нормали . В точке касания градиент функции направлен по нормали к линии уровня, то есть его направление совпадает с направлением нормали к прямой . Найдем градиент функции

Так как точка касания лежит на прямой ив ней градиент функции коллинеарен вектору нормали к прямой , то получаем систему из двух уравнений для определения координат этой точки:

Решением данной системы является:

откуда

при этом

Пример задачи №22

Найти экстремумы функции

при условии

Решение:

Из рисунка видно, что минимум целевой функции достигается в точке , а максимум в точке .

Точка является точкой пересечения линии уровня

и гиперболы

Найдем ее координаты.

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

Точка есть пересечение линии уровня и прямой . Угловой коэффициент линии уровня: . Поскольку касательная и радиус, проведенный к точке касания, перпендикулярны, . Тогда уравнение прямой Найдем координаты точки .

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

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

при условиях

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

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

Тогда задача (3.4) — (3.6) примет вид

при ограничениях

В результате получена задача линейного программирования. После ее решения симплексным методом, используя соотношения (3.7), можно найти оптимальное решение исходной задачи (3.4), (3.5). Пример 1. Найти максимальное значение функции

при ограничениях

Решение:

Так как по условию все переменные неотрицательные, то выполнено условие (3.6):

Введем вспомогательную переменную

и, соответственно, дополнительное ограничение

Задача принимает вид:

при условиях:

Умножим второе, третье и четвертое ограничения на , введем новые переменные:

Получена задача линейного программирования: найти максимум функции

при ограничениях

Решив эту задачу симплексным методом, получим

Используя формулу (8.7), возвратимся к исходным переменным:

Итак,

Графический метод Задачи дробно-линейного программирования с двумя переменными можно решать графически. Рассмотрим следующую задачу

Будем считать, что

Для решения этой задачи найдем многоугольник решений, определяемый ограничениями (3.9). Из выражения (3.8) найдем :

где — прямая, проходящая через начало координат.

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

Установим, как будет вести себя угловой коэффициент при монотонном возрастании . Найдем производную от по .

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

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

Алгоритм графического метода

1. Построить многогранник решений.
2. Определить угловой коэффициент и установить направление поворота линий уровня целевой функции.
3. Найти точку экстремума целевой функции или установить неразрешимость задачи.

Пример задачи №23

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

Первый тип оборудования целесообразно использовать не менее 10 ч, оборудование 2 типа — не более 41 ч, 3 типа — не более 6 ч.

Составить оптимальный план производства изделий при минимальной себестоимости.

Решение:

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

Запишем математическую модель задачи:

при ограничениях

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

Угловой коэффициент . Найдем производную от по .

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

при выпуске 6 изделий вида и 4 изделий вида .

Градиентный метод

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

Пусть дана целевая функция

Градиент функции в некоторой точке

есть вектор

Вектор (3.12) направлен по нормали к поверхности уровня и показывает направление максимальной скорости роста функции.

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

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

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

Пусть дана задача выпуклого программирования

при ограничениях

Алгоритм градиентного метода

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

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

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

Определить пересечения всех граничных гиперповерхностей, решив системы уравнений вида

Отобрать допустимые решения при

и вычислить значения при этих решениях.

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

Сравнить значения целевой функции во всех точках, определенных в пунктах 1—3 и выбрать и .

Пример задачи №24

Определить градиентным методом максимум функции

начиная итерационный процесс с точки .

Решение:

Определим градиент функции начальной точке .

Выбираем новую точку

Найдем градиент функции в новой точке:

Решаем уравнение

откуда имеем

Получен нулевой градиент, следовательно, точка является стационарной. Так как целевая функция является выпуклой (как сумма выпуклых функций

то в найденной точке достигается

Ответ.

Пример задачи №25

Минимизировать функцию

при ограничениях

Решение:

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

Определим градиент целевой функции

Определим стационарную точку

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

Рассмотрим граничную линию

Составим для нее систему вида (3.16):

Имеем

откуда получаем

Так как точка

удовлетворяет системе ограничений и , то данная точка является стационарной.

Рассматриваем следующую граничную линию:

Для нее и система (3.16) имеет вид

Решение этой системы:

Однако точка

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

Имеем систему

откуда

Так как , стационарных точек на грани нет. Аналогично,

Имеем систему

откуда

Так как , стационарных точек на грани нет.

Решая систему уравнений граничных линий, находим угловые точки области допустимых решений: (6; 5), (8; 0), (0; 8). Находим значения в этих точках и ранее найденной точке

Следовательно,

Динамическое программирование

Динамическое программирование позволяет находить оптимальное решение задачи путем ее декомпозиции на несколько этапов. Эта декомпозиция осуществляется по различным принципам. В некоторых задачах по временным периодам, в других — по объектам управления. Иногда разбиение производится искусственно. Фундаментальным принципом динамического программирования, составляющим основу декомпозиции задачи на этапы, является оптимальность.

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

Это значительно сокращает объем вычислений и ускоряет процесс принятия управленческих решений.

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

Пример задачи №26

Определить оптимальный маршрут из пункта 1 в пункт 10 по схеме маршрутов движения (рис. 4.1).

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

Требуется определить такой путь из пункта 1 в пункт 10, общая стоимость которого является минимальной.

Решение:

Используем формулу рекуррентных соотношений Беллмана:

где — количество этапов в решении;

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

Начинаем поиск оптимального маршрута от конечного пункта, положив

Таким образом, определен оптимальный путь: 1-3-7-9-10, затраты по которому составляют

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

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

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

Пример задачи №27

Решить задачу управления запасами при следующих условиях: количество отрезков планового периода , спрос одинаков для всех отрезков . Затраты равны

где — объем производства; — запасы на конец отрезка планирования, — затраты на хранение единицы продукции, .

Считаем, что и — целые, причем .

Решение:

Используем рекуррентные соотношения:

где — количество этапов в решении;

— множество значений переменной ;

— затраты, соответствующие оптимальной стратегии, если до конца планируемого периода остается этапов;

— объем производства, обеспечивающий оптимальную стратегию. Начинаем формирование оптимального плана от последнего этапа, положив .

Так как по условию задачи, то на этом этапе получаем следующие возможные значения функции :

Для удобства занесем эти данные в таблицу.

Положим

Тогда для

следовательно

Аналогично

Таблица имеет вид.

Положив , получим следующую таблицу.

Наконец, для таблица примет вид.

Таким образом, получим два варианта оптимального плана работы с затратами, равными 49 единицам: 3;4;5;0и4;5;0;3.

Теория игр

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

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

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

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

Пример задачи №28

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

У первого игрока три стратегии (варианта действия): (записать 1), (записать 2) и (записать 3); у второго игрока также три стратегии: .

Задача первого игрока — максимизировать свой выигрыш, задача второго игрока — минимизировать свой проигрыш.

Матрица игры, или платежная матрица, имеет вид

Найдем наилучшую стратегию первого игрока. Если игрок выбрал стратегию , то в худшем случае он получит выигрыш

Соответственно при выборе стратегии —

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

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

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

При выборе стратегий и проигрыш составит, соответственно,

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

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

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

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

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

Аналогично для второго игрока наборы вероятностей определяют -мерные векторы

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

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

Пример задачи №29

Рассмотрим игру, представленную платежной матрицей

Решение:

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

Для второго игрока, сравнивая и , исключаем сравнивая и , исключаем .

В результате преобразований получим матрицу

Графический метод решения матричных игр

Графический метод применим к играм, в которых хотя бы один игрок имеет только две стратегии.

Пример задачи №30

Найти решение игры, заданной матрицей

Решение:

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

По формулам

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

Ответ. Оптимальные смешанные стратегии игроков

цена игры составляет .

Данный ответ означает следующее:

— если первый игрок с вероятностью будет применять первую стратегию и с вероятностью вторую, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее ;

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

Пример задачи №31

Найти решение игры, заданной матрицей

Решение:

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

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

Решение игры сводится к решению игры с матрицей 2×2

По формулам находим оптимальные стратегии и цену игры:

Ответ. Оптимальные смешанные стратегии игроков

цена игры составляет .

V 3 3 ) 3

Данный ответ означает следующее:

— если первый игрок с вероятностью будет применять первую стратегию и с вероятностью вторую, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее ;

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

Пример задачи №32

Найти решение игры, заданной матрицей

Решение:

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

Верхней границей проигрыша для игрока является ломаная . Стратегии и являются активными стратегиями игрока А. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Первому игроку не выгодно применять стратегии и , поэтому вероятность их применения равна 0, т.е. .

Решение игры сводится к решению игры с матрицей 2×2:

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

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

Рассмотрим игру двух лиц с нулевой суммой, заданную платежной матрицей

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

Рассмотрим задачу отыскания оптимальной стратегии игрока , для которой имеют место ограничения

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

По условию

Разделим обе части этого равенства на

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

должна принимать минимальное значение.

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

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

Рассмотрим задачу отыскания оптимальной стратегии игрока , для которой имеют место ограничения

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

По условию

Разделим обе части этого равенства на

Оптимальная стратегия игрока В должна минимизировать величину , следовательно, функция

должна принимать максимальное значение.

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

Пример задачи №33

Найти решение игры, заданной матрицей

Решение:

Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий.

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

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

Оптимальные решения пары двойственных задач имеют вид

Учитывая соотношения между

а также равенство

находим оптимальные стратегии игроков и иену игры

Игры с природой

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

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

• Критерий Вальда. Рекомендуется применять максиминную стратегию. Она выбирается из условия

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

• Критерий максимума. Он выбирается из условия

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

• Критерий Гурвица. Критерий рекомендует стратегию, определяемую по формуле

где — степень оптимизма и изменяется в диапазоне [0, 1 ].

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

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

Элементы матрицы рисков находятся по формуле

где — максимальный элемент в столбце исходной матрицы.

Оптимальная стратегия определяется выражением

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

Пример задачи №34

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

Платежная матрица в тысячах рублей оценивается следующим образом:

Что должен посеять Иванов?

Решение:

• Согласно критерию Вальда рекомендуется применять максимальную стратегию.

Следует сеять пшеницу.

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

Оптимальная стратегия определяется выражением

Найдем

В соответствии с этим критерием следует сеять пшеницу. 3. Воспользуемся критерием Гурвица. Оптимальная стратегия определяется по формуле

где — степень оптимума и изменяется в диапазоне [0; 1], предположим

т.е. следует принять решение о посеве пшеницы.

• Если принять известным распределение вероятностей для различных состояний природы, например считать эти состояния равновероятными

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

так как максимальное значение имеет , то следует сеять пшеницу.

Теория графов

Непустое множество и множество отношений называется графом и обозначается . Граф называется конечным, если множество конечно.

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

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

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

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

Графы можно задавать списками пар вершин, соединенных ребрами или заданием для каждой вершины множества смежных вершин.

Характеристики графа

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

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

Теорема 1. Если конечный граф (без петель) имеет вершин и ребер, то

Теорема 2. Число нечетных вершин любого графа четно.

Теорема 3. Во всяком графе с вершинами ( > 2) всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.

Теорема 4. Если в графе с вершинами ( > 2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени — 1.

Путь и цикл в графе

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

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

Теорема 5. Если у графа все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.

Связность графа, деревья

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

Теорема 6. Связный граф представляет собой простой цикл тогда и только тогда, когда каждая его вершина имеет степень 2.

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

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

Плоские графы

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

Плоское представление имеет только плоский граф, и обратно: у всякого плоского графа всегда найдется плоское представление.

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

В плоском представлении дерева за грань принимают всю плоскость чертежа.

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

которое называется формулой Эйлера.

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

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

Теорема 7. Для любого плоского графа существует плоское представление, в котором все ребра — прямолинейные отрезки.

Эйлеровы графы

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

Теорема 8. Эйлеров граф является связным, и все его вершины — четными.

Теорема 9. Если граф связный и все его вершины четны, то он обладает эйлеровым циклом.

Теорема 10. Если граф обладает эйлеровым путем с концами и , то граф связный и А и В его единственные нечетные вершины.

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

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

Гамильтоновы графы

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

Теорема 13. Граф с вершинами имеет гамильтонов цикл, если для любой его вершины

Ориентированные графы

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

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

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

Последовательность дуг

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

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

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

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

Ориентированный граф можно задать с помощью матрицы инцидентности. Пусть — вершины графа, — дуги графа.

Матрицей инцидентности графа называется матрица у которой элемент , равен 1, если дуга исходит из вершины равен -1, если дуга входит в вершину равен 0, если дуга и вершина не инцидентны.

Сетевое планирование и управление

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

Построение минимального остовного дерева сети

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

Рассмотрим процедуру построения минимального остовного дерева.

Введем обозначения:

—множество узлов сети;

— связное множество узлов сети, соединенных алгоритмом после выполнения -й итерации;

— множество узлов сети, не соединенных с узлами множества после выполнения -й итерации.

Алгоритм построения минимального остовного дерева сети

1. Взять произвольный узел сети ;
2. Выбрать из оставшихся узлов узел , ближайший к множеству узлов
3. Выбрать из множества узел, ближайший к узлам множества , включить его в множество и исключить из множества .

За конечное число шагов будут обработаны все узлы сети и построено минимальное остовное дерево.

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

Введем следующие обозначения: — исходный узел; — узел назначения;

— расстояние на сети между смежными узлами и

— кратчайшее расстояние от узла до узла , . Алгоритм нахождения кратчайшего пути состоит в последовательном нахождении значений для каждого узла от исходного узла до узла назначения. Значение для каждого узла рассчитывается по формуле

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

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

Сетевое планирование

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

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

Фиктивная работа — это связь между результатами работ (событиями), не требующая затрат времени и ресурсов.

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

Путь — это любая непрерывная последовательность (цепь) работ и событий.

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

При построении сетевых моделей необходимо соблюдать следующие правила:

1. Сеть вычерчивается слева направо, и каждое событие с большим порядковым номером изображается правее предыдущего. Общее направление стрелок, изображающих работы, также в основном должно быть расположено слева направо, при этом каждая работа должна выходить из события с меньшим номером и входить в событие с большим номером.
2. Два соседних события могут объединяться лишь одной работой. Для изображения параллельных работ вводятся промежуточное событие и фиктивная работа.
3. В сети не должно быть тупиков, т.е. промежуточных событий, из которых не выходит ни одна работа.
4. В сети не должно быть промежуточных событий, которым не предшествует хотя бы одна работа.
5. В сети не должно быть замкнутых контуров, состоящих из взаимосвязанных работ, создающих замкнутую цепь. Для правильной нумерации событий поступают следующим образом: нумерация событий начинается с исходного события, которому дается номер 1.

Из исходного события 1 вычеркивают все исходящие из него работы, на оставшейся сети вновь находят событие, в которое не входит ни одна работа. Этому событию дается номер 2. Затем вычерчивают работы, выходящие из события 2, и вновь находят на оставшейся части сети событие, в которое не входит ни одна работа, ему присваивается номер 3, и так продолжается до завершающего события.

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

Рассмотрим прямой проход.

— ранний срок начала всех операций, выходящих из события .

Если

— ранний срок начала всех операций, входящих в .

где — продолжительность операции .

Различают два вида резервов времени: полный резерв и свободный резерв .

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

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

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

Стоимостные факторы при реализации сетевого графика учитываются путем определения зависимости «затраты — продолжительность» для каждой операции. При этом рассматриваются прямые затраты, а косвенные типа административных или управленческих расходов не принимаются во внимание.

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

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

Системы массового обслуживания

Системы массового обслуживания (СМО) с отказами

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

Вероятность простоя каналов обслуживания

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

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

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

Среднее число занятых каналов

Доля каналов, занятых обслуживанием, составляет

СМО с неограниченным ожиданием В СМО с неограниченным ожиданием заявка, нашедшая все каналы занятыми, становится в очередь, на которую не наложено ограничений ни по длине очереди, ни по времени ожидания. В силу неограниченности очереди каждая заявка рано или поздно будет обслужена, поэтому , . Для СМО с неограниченной очередью накладывается ограничение . Если это условие нарушено, то очередь растет до бесконечности, наступает явление «взрыва».

• Вероятность простоя каналов:

• Вероятность занятости обслуживанием к каналов:

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

• Вероятность наличия очереди есть вероятность того, что число требований в системе больше числа каналов:

• Вероятность для заявки попасть в очередь есть вероятность занятости всех каналов, эта вероятность равна сумме вероятностей наличия очереди и занятости всех каналов при отсутствии очереди:

• Среднее число занятых обслуживанием каналов:

• Доля каналов, занятых обслуживанием:

• Среднее число заявок в очереди (длина очереди):

• Среднее число заявок в системе:

• Среднее время ожидания заявки в очереди:

• Среднее время пребывания заявки в системе:

СМО с ожиданием и ограниченной очередью

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

Системы с ограниченной очередью являются обобщением двух рассмотренных ранее СМО: при = 0 получаем СМО с отказами, при СМО с ожиданием.

Вероятность простоя каналов обслуживания

Вероятность отказа в обслуживании равна вероятности того, что в очереди уже стоят заявок:

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

Абсолютная пропускная способность определяется равенством

Среднее число занятых каналов

Средняя длина очереди, т.е. среднее число заявок в очереди

Среднее время ожидания обслуживания в очереди

Среднее число заявок в СМО

Среднее время пребывания заявки в СМО

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

Вероятность простоя системы определяется формулой

Финальные вероятности состояний системы

Среднее число занятых каналов:

Абсолютная пропускная способность системы:

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

Пример задачи №35

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

Решение. В условии задачи

вероятность простоя определяем по формуле (8.1).

т.е. вероятность отказа

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

Абсолютная пропускная способность

Среднее число занятых каналов

Пример задачи №36

Рабочий обслуживает 4 станка. Каждый станок отказывает с интенсивностью = 0,5 отказа в час, среднее время ремонта = 0,8 ч. Определить пропускную способность системы.

Эта задача рассматривает замкнутую СМО,

Вероятность простоя рабочего определяем по формуле (8.27):

вероятность занятости рабочего

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

станка в час.

Модель потребительского выбора

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

где — количество -го товара.

Функция

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

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

при ограничениях

где — цены товаров.

Для решения задачи (9.1) используется метод Лагранжа. Функция Лагранжа имеет вид

где — множитель Лагранжа.

Найдем частные производные функции Лагранжа.

где

Исключив из системы (9.2) неизвестный множитель Лагранжа , получим систему двух уравнений с двумя неизвестными :

Решением задачи потребительского выбора является решение системы (9.3), которое называется точкой спроса.

Точка спроса является функцией цен и дохода и в общем виде представляет набор функций, каждая из которых зависит от + 1 аргумента:

Функции (9.4) называются функциями спроса соответствующих товаров.

Пример задачи №37

Найти функцию спроса для набора из двух товаров на рынке, если функция полезности задана в виде

Решение:

Дифференцируя заданную функцию полезности получим

Подставим полученные выражения в систему (9.3).

Из первого уравнения системы (9.5) следует:

откуда

Полученное выражение подставим во второе уравнение системы (9.5):

Из уравнения (9.6)

Подставим полученное выражение во второе уравнение системы (9.5):

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

Расходы на первый товар составляют 0,3 дохода потребителя, расходы на второй товар — 0,7 дохода потребителя. Количество приобретенного товара равно затраченной на него сумме, поделенной на цену товара.

Производственные функции

Производственной функцией называется зависимость объема производства у от затрат производственных ресурсов

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

называемая функцией Кобба—Дугласа. Эта функция задает зависимость объема производства у от двух важнейших производственных факторов — труда (рабочей силы) и основных производственных фондов .

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

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

Предельной эффективностью (производительностью) труда называется выражение

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

Эластичностью выпуска по затратам труда называется показатель

выражающий процентное увеличение выпуска продукции при увеличении затрат труда на 1%.

Средний продукт по второму ресурсу — объему основных фондов, называется фондоотдачей:

Фондоотдача выражает объем продукции в расчете на единицу используемых производственных фондов. Предельная фондоотдача

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

Эластичность выпуска продукции по фондам определяется коэффициентом

и показывает, на сколько процентов изменится выпуск продукции при увеличении объема фондов на 1%.

Нормы замещения ресурсов определяются по формулам:

Предельной нормой замещения первого ресурса вторым называется величина

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

Для предельных норм замещения ресурсов справедливо соотношение

Пример задачи №38

Пусть некоторое производство можно описать с помощью функции Кобба — Дугласа. В настоящее время один работник производит в месяц продукции на 1 млн руб. Общая численность работников 1000 чел. Основные фонды оцениваются в 10 млрд. руб. Известно, что для увеличения выпуска продукции на 3% следует увеличить или стоимость фондов на 6%, или численность работников на 9%.

1. Составить для данного предприятия производственную функцию, определив коэффициенты эластичности.
2. Определить среднюю и предельную производительность труда.
3. Определить среднюю и предельную фондоотдачу.
4. Найти нормы замещения ресурсов, предельные нормы замещения ресурсов.
5. Определить численность работников, если стоимость основных фондов увеличить в 100 раз, уменьшить в 100 раз.

Решение:

Производственная функция Кобба — Дугласа имеет вид

где — затраченный труд; — капитал.

Найдем коэффициенты эластичности.

По условию

Тогда

объем продукции в стоимостном выражении.

Перепишем функцию Кобба — Дугласа в относительных приращениях:

где — прирост объема продукции;

— прирост трудовых ресурсов;

— прирост фондов.

Нам известно, что для увеличения выпуска продукции на 3% ( = 3%) следует увеличить стоимость фондов на 6% ( = 6%), т.е. 0,03 -=

либо численность работников увеличить на 9% ( =9%), т.е.

Тогда коэффициенты эластичности:

Теперь производственная функция имеет вид:

Итак, производственная функция имеет вид:

Определим среднюю и предельную производительность труда:

— средняя производительность труда;

— предельная производительность труда.

• Определим среднюю и предельную фондоотдачу:

— средняя фондоотдача;

— предельная фондоотдача.

• Найдем нормы замещения ресурсов.

— норма замещения первого ресурса вторым.

— норма замещения второго ресурса первым.

— предельная норма замещения первого ресурса вторым.

— предельная норма замещения второго ресурса первым.

Определим численность работников, необходимую для сохранения объема выпуска продукции, если стоимость основных средств увеличить в 100 раз; уменьшить в 100 раз.

а) Увеличение в 100 раз.

б) Уменьшение в 100 раз.

Пример задачи №39

Дана производственная функция

где — объем товарной продукции в стоимостном выражении, — фонд заработной платы, — стоимость основных фондов. Произошло изменение используемых ресурсов: фонд заработной платы уменьшился на 3%, стоимость основных фондов возросла на 2%. На сколько процентов при этом изменятся:

1) объем товарной продукции;

2) производительность труда;

3) фондоотдача.

Решение:

Решим задачу двумя способами.

Первый способ. Полагаем, что

тогда производственная функция имеет вид:

и это есть 100%. По условию, уменьшилось на 3%, т.е. стало 0,97, а на 2% увеличилось, т.е. стало 1,02. Тогда новое значение производственной функции:

Узнаем, сколько процентов составляет по отношению к :

Таким образом, объем продукции практически не изменился. Производительность труда

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

Пусть прежнее значение производительности труда

составляет 100%. Тогда новое значение

Так как

то произошло увеличение производительности труда на 3%.

Фондоотдача

так как и изменились. Новая фондоотдача составит:

Составим пропорцию

т.е. фондоотдача уменьшилась на 100% — 98% = 2%.

Второй способ. Прологарифмируем производственную функцию:

Продифференцируем полученное равенство

Тогда

Величины

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

Следовательно, объем товарной продукции не изменился. Производительность труда определяется равенством

Логарифмируя это равенство, получим

Таким образом, производительность труда возросла на 3%. Фондоотдача выражается формулой

Логарифмируя это равенство, получим

Следовательно, фондоотдача снизилась на 2%.

Межотраслевой баланс

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

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

Общий вид межотраслевого баланса представим в виде таблицы.

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

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

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

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

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

Аналогично, для любого столбца с номером справедливо равенство

Равенство (11.2) представляет стоимостную структуру продукта каждой отрасли. Оно показывает, что стоимость валовою продукта отрасли складывается из затрат других отраслей на его производство и стоимости условно-чистой продукции, не производящейся внутри производственной системы.

Отметим и еще одно важное соотношение межотраслевого баланса: суммарный конечный продукт равен суммарной условно-чистой продукции:

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

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

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

называют матрицей прямых материальных затрат.

Технологические коэффициенты имеют следующие свойства:

Используя соотношения (11.1) и (11.4), составим линейную балансовую модель:

или в матричной форме:

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

1) По заданному вектору конечного потребления найти вектор валового выпуска . Решение матричного уравнения (11.7) относительно имеет вид:

2) По заданному вектору валового выпуска найти вектор конечного потребления . Решив матричное уравнение (11.7), относительно , получим:

3) Смешанная задача: по некоторым заданным и найти соответствующие и .

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

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

Если матрица — продуктивная, то для любого существует неотрицательное решение уравнения (11.7).

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

Матрицу называют матрицей полных материальных затрат или обратной матрицей Леонтьева. Таким образом, решение уравнения (11.7) относительно можно найти по формуле:

или в координатной форме

Пример задачи №40

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

а) вектор валового продукта , если вектор конечного потребления

б) вектор конечного потребления , если вектор валового продукта

Решение:

Для построения балансовых уравнений найдем коэффициенты прямых материальных затрат по формуле (11.5):

Система балансовых уравнений (11.6) имеет вид:

а) При заданном

имеем:

Полученную систему линейных уравнений решим по формулам

б) При заданном

система балансовых уравнений принимает вид:

Пример задачи №41

Найдите вектор валового продукта для заданной матрицы прямых материальных затрат

и вектора конечного потребления

Решение:

Для решения задачи используем формулы (11.10) и (11.11). Найдем матрицу по следующему алгоритму:

— составим матрицу ;

— вычислим определитель det;

— найдем алгебраические дополнения , к элементам матрицы ;

— составим из алгебраических дополнений матрицу и транспонируем ее, полученную матрицу назовем ;

— найдем по формуле:

Пример задачи №42

Даны матрица прямых материальных затрат

и вектор валового продукта

Найти вектор конечного потребления .

Решение:

Найдем решение по формуле (11.9).

Пример задачи №43

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

Решение:

Изменение межотраслевых потоков вычисляется по формуле:

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

Таким образом,

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

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

Определим искомые изменения межотраслевых потоков.