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

Оглавление:

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

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

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

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

К оглавлению…

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

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

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

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

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

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

К оглавлению…

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

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

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

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

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

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

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

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

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

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

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

Пример задачи №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

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

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

Решение:

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

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

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

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

Таким образом,

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

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

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

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

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

Определим искомые изменения межотраслевых потоков.

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