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

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ

Рекомендовано редакционно-издательским советом университета в качестве учебного пособия для студентов специальностей 080105, 080107, 080109, 080504 очной и заочной форм обучения

Кострома

КГТУ

УДК 519.8 (075)

П958

Рецензенты:

д.п.н., зав. кафедрой математического анализа ЯГПУ, профессор Е.И.Смирнов;

д.э.н., зав кафедрой математических методов в экономике КГУ им. Н.А.Некрасова, профессор Е.М. Скаржинская;

к.э.н., старший преподаватель кафедры математических методов в экономике КГУ им. Н.А.Некрасова А.С. Илюхина.

Пыханова Т.В. Экономико-математические модели и методы : учеб. пособие / Т.В. Пыханова, С.Ф. Катержина. – Кострома: Изд-во Костром. гос. технол. ун-та, 2008. – 41 с.

ISBN

Пособие соответствует требованиям Государственного образовательного стандарта и учебному плану по дисциплине «Математика» и рекомендуется для студентов специальностей 080105, 080107, 080109 и 080504 очной и заочной форм обучения для аудиторной и самостоятельной работы.

© Костромской государственный технологический университет, 2008

ОГЛАВЛЕНИЕ

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ КАК ПРОСТЕЙШИЙ СЛУЧАЙ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ.. 4

1. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 5

Задачи для самостоятельного решения. 7

2. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ.. 12

2.1. Составление двойственных задач. 12

2.2. Основные теоремы двойственности. 13

Задачи для самостоятельного решения. 16

3. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.. 19

3.1. Математическая модель транспортной задачи (ТЗ) 19

3.2. Свойства транспортной задачи. 21

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

3.3.1. Метод северо-западного угла. 22

3.3.2. Метод минимального элемента. 23

3.4. Метод потенциалов. 24

3.4.1. Циклы матрицы перевозок. 24

3.4.2. Метод потенциалов, его алгоритм.. 25

Задачи для самостоятельного решения. 30

4. СЕТЕВЫЕ МОДЕЛИ.. 33

4.1. Сетевой график комплекса операций и правила его построения. 33

4.2. Расчет временных параметров сетевого графика. 35

Задачи для самостоятельного решения. 40

Список рекомендуемой литературы………………………………………………………….......41

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ КАК ПРОСТЕЙШИЙ СЛУЧАЙ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

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

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

; (1)

. (2)

При рассмотрении задач МП различают 2 этапа:

· постановка задачи;

· решение задачи.

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

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

· выбор переменных задачи;

· составление системы ограничений;

· выбор целевой функции.

Задача линейного программирования соответствует случаю, когда левые части функции (1) и ограничений (2) – линейные функции от x₁, x₂, …, x_n .

Переменными задачи называются величины x₁, x₂, …, x_n , которые полностью характеризуют экономический процесс.

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

Функция, подлежащая максимизации (или минимизации), называется целевой.

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

(3)

при условиях

(4)     (5)   (6)

где – заданные постоянные величины и .

Задача ЛП называется стандартной или симметричной, если она состоит в определении max (min) значения функции (3) при условиях (4) и (6).

Задача ЛП называется канонической или основной, если она состоит в определении максимального значения функции (3) при условиях (5) и (6).

Задача 1.23

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

Продукт	Время обработки, ч
I	II	III
A	0,5	0,4	0,2
B	0,25	0,3	0,4

Время работы машин I, II, III, соответственно, 40, 36 и 36 часов в неделю. Прибыль от изделий А и В составляет, соответственно, 5 и 3 долларов.

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

Задача 1.24

Прибыль от изделий А, В, С составляет, соответственно, 3, 4, 5 единиц. Для каждого изделия требуется время использования станка I и II, которые доступны, соответственно, 12 и 15 часов в день:

Станок	Время использования станка, ч
А	В	С
I
II

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

Задача 1.25

Два изделия В1 и В2 последовательно обрабатываются на станках № 1, 2, 3, 4, 5. Машинное время на единицу изделий на каждом станке указано в таблице. Здесь же приведена прибыль от каждого изделия, причем объем производства второго вида продукции не должен превышать 40 % общего выпуска.

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

Изделие	Машинное время для станка, мин	Прибыль, руб/шт.
В1
В2						1,5
Недельный фонд рабочего времени, мин

Решите задачу графически.

Задача 1.26

На предприятии могут изготавливать два вида продукции i₁ и i₂. На выпуск единицы продукции i₁ расходуется 3 единицы ресурса, а на единицу продукта i₂ – 1 единица того же ресурса. В плановом периоде в распоряжении предприятия имеется 300 единиц этого же ресурса. Ограничение по выпуску продукции первой и высшей категории качества выглядит следующим образом: . При этом требуется, чтобы продукции i₁ было выпущено не менее 40 единиц. Предприятие желает получить максимальную прибыль.

Каждое изделие вида i₁ дает 3 доллара прибыли, каждое изделие вида i₂ дает 4 доллара прибыли. Решите эту задачу графически.

Задача 1.27

Средства очистки пола оценивают по следующим трем показателям:

а) очищающие свойства;

б) дезинфицирующие свойства;

в) раздражающее воздействие на кожу.

Каждый из этих показателей измеряется по линейной шкале от 0 до 100.

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

	Свойства продукта
Очиститель	Очищающие	Дезинфицирующие	Раздражающие
А
В
С

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

Задача 1.28

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

Сырье	Запас сырья, кг	Затраты на единицу продукции, кг
свитер	пуловер	костюм
Чистая шерсть		0,4	0,2	0,8
Силон		0,2	0,1	0,2
Прибыль за изделие, ден. ед.

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

Задача 1.29

Фабрика производит два основных типа товара. Изделию типа I требуется 3 единицы сырья А и единица сырья В. Оно приносит прибыль 3 единицы. Изделию типа II требуется 4 единицы сырья А и 3 единицы сырья В. Оно приносит прибыль в 2 единицы. Найдите оптимальный план производства, если доступны всего 20 единиц сырья А и 10 единиц сырья В (используйте графический метод).

Как изменится оптимальный план производства, если окажется доступной еще одна единица сырья А, а затем и еще одна единица сырья В?

Задача 1.30

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

Продукты	Питательные вещества
Белок (г/кг)	Кальций (г/кг)	Витамины (мг/кг)
Сено
Силос
Концентраты

Составить самый дешевый рацион, если стоимость 1 кг сена, силоса и концентрата равна, соответственно, 1, 5, 2 и 6 рублей .

Метод северо-западного угла

Вычисление проводим по формуле (11), начиная с элемента x₁₁, стоящего в северо-западном углу матрицы перевозок.

Пример 3. Найти начальный план перевозок в ТЗ методом северо-западного угла

Запишем матрицу перевозок (табл. 3.2).

Таблица 3.2

Bj Ai	B1	B2	В3	B4	Запасы ai
A1			*
A2	*
A3		*	*
Потребности bj

Начинаем с северо-западного угла, т. е.

.

Тогда в пункте B₁ потребности удовлетворены, и, следовательно, (в табл. 3.2 ставится точка (*)). Первый столбец выбывает из рассмотрения.

Продолжаем с северо-западного угла, т.е.

.

Запасы в пункте А₁ исчерпаны и (в табл. 3.2 ставится точка). Первая строка таблицы выбывает из рассмотрения.

Продолжаем с северо-западного угла:

.

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

Продолжаем с северо-западного угла:

и .

Третий столбец выбывает из рассмотрения.

.

Запасы в пункте А₂ исчерпаны.

.

Получен начальный план перевозок:

с суммарной стоимостью

.

Число базисных клеток m + n – 1 = 3 + 4 – 1 = 6.

Примечание. При нахождении начального плана перевозок возможен случай вырождения, когда в результате вычислений значения x_ij получается, что потребности в пункте B_j удовлетворены, а запасы в пункте A_i исчерпаны. Тогда одновременно из рассмотрения выбывают строка и столбец. Рекомендуется в одну из клеток выбывающих строки и столбца (лучше в клетку с наименьшей стоимостью) ставить так называемый базисный нуль. Эта клетка считается базисной (в ней пишется 0), а общее число базисных клеток остается равным

m + n – 1.

Метод минимального элемента

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

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

Пример 4. Найти начальный план перевозок в ТЗ (пример 3) методом минимального элемента.

Запишем матрицу перевозок (табл. 3.3).

Таблица 3.3

Bj Ai	B1	B2	В3	B4	Запасы ai
A1			*
A2
A3		*	*
Потребности bj

Заполняем клетку с наименьшей стоимостью:

.

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

Среди оставшихся клеток ищем клетку с наименьшей стоимостью:

– случай вырождения, базисный нуль .

Из оставшихся клеток заполняем клетку с наименьшей стоимостью:

.

Потребности в пункте В₃ удовлетворены, выбывает третий столбец.

.

Получен начальный план перевозок:

с суммарной стоимостью

,

которая меньше стоимости, полученной методом северо-западного угла. Число базисных клеток m + n – 1 = 3 + 4 – 1 = 6.

Метод потенциалов

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

Циклы матрицы перевозок

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

а б в

Рис. 3. Простейшие циклы

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

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

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

СЕТЕВЫЕ МОДЕЛИ

Список рекомендуемой литературы

1. Кузнецов Б.Т. Математические методы и модели исследования операций / Б.Т.Кузнецов. – М., 2005.

2. Костевич П.С. Математическое программирование. – Минск, 2003.

3. Кузнецов А.В. Математическое программирование. – Минск, 1984.

4. Пантелеев А.В. Методы оптимизации в примерах и задачах / А.В.Пантелеев, Т.А. Летова– М., 2002.

5. Количественные методы в экономических исследованиях / [М.В.Грачева и др.]; под общ. ред. М.В.Грачевой – М., 2004.

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ

Рекомендовано редакционно-издательским советом университета в качестве учебного пособия для студентов специальностей 080105, 080107, 080109, 080504 очной и заочной форм обучения

Кострома

КГТУ

УДК 519.8 (075)

П958

Рецензенты:

д.п.н., зав. кафедрой математического анализа ЯГПУ, профессор Е.И.Смирнов;

д.э.н., зав кафедрой математических методов в экономике КГУ им. Н.А.Некрасова, профессор Е.М. Скаржинская;

к.э.н., старший преподаватель кафедры математических методов в экономике КГУ им. Н.А.Некрасова А.С. Илюхина.

Пыханова Т.В. Экономико-математические модели и методы : учеб. пособие / Т.В. Пыханова, С.Ф. Катержина. – Кострома: Изд-во Костром. гос. технол. ун-та, 2008. – 41 с.

ISBN

Пособие соответствует требованиям Государственного образовательного стандарта и учебному плану по дисциплине «Математика» и рекомендуется для студентов специальностей 080105, 080107, 080109 и 080504 очной и заочной форм обучения для аудиторной и самостоятельной работы.

© Костромской государственный технологический университет, 2008

ОГЛАВЛЕНИЕ

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ КАК ПРОСТЕЙШИЙ СЛУЧАЙ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ.. 4

1. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 5

Задачи для самостоятельного решения. 7

2. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ.. 12

2.1. Составление двойственных задач. 12

2.2. Основные теоремы двойственности. 13

Задачи для самостоятельного решения. 16

3. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.. 19

3.1. Математическая модель транспортной задачи (ТЗ) 19

3.2. Свойства транспортной задачи. 21

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

3.3.1. Метод северо-западного угла. 22

3.3.2. Метод минимального элемента. 23

3.4. Метод потенциалов. 24

3.4.1. Циклы матрицы перевозок. 24

3.4.2. Метод потенциалов, его алгоритм.. 25

Задачи для самостоятельного решения. 30

4. СЕТЕВЫЕ МОДЕЛИ.. 33

4.1. Сетевой график комплекса операций и правила его построения. 33

4.2. Расчет временных параметров сетевого графика. 35

Задачи для самостоятельного решения. 40

Список рекомендуемой литературы………………………………………………………….......41

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ КАК ПРОСТЕЙШИЙ СЛУЧАЙ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

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

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

; (1)

. (2)

При рассмотрении задач МП различают 2 этапа:

· постановка задачи;

· решение задачи.

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

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

· выбор переменных задачи;

· составление системы ограничений;

· выбор целевой функции.

Задача линейного программирования соответствует случаю, когда левые части функции (1) и ограничений (2) – линейные функции от x₁, x₂, …, x_n .

Переменными задачи называются величины x₁, x₂, …, x_n , которые полностью характеризуют экономический процесс.

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

Функция, подлежащая максимизации (или минимизации), называется целевой.

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

(3)

при условиях

(4)     (5)   (6)

где – заданные постоянные величины и .

Задача ЛП называется стандартной или симметричной, если она состоит в определении max (min) значения функции (3) при условиях (4) и (6).

Задача ЛП называется канонической или основной, если она состоит в определении максимального значения функции (3) при условиях (5) и (6).