Методические пособия
Студент должен сдать:
ВВЕДЕНИЕ В ПРЕДМЕТ
Тема: Линейное программирование
1.1. Экономико-математическая модель оптимизационной задачи и задачи линейного программирования
Модель оптимизационной задачи
Общая задача линейного программирования (ЗЛП)
Оптимальный план выпуска молочной продукции
Решение:
Отчет по устойчивости
1.2. Графический метод решения задачи линейного программирования
Геометрическая интерпретация линейных неравенств и их систем
1.3. Симплекс-метод решения задач линейного программирования
Схема сравнения методов
Основные этапы симплексного метода:
Отчет по устойчивости
Пример
4.54M
Категория: МатематикаМатематика

Введение в предмет математики

1.

Рекомендуемая литература:
а) основная:
1. Гармаш А.Н., Орлова И.В. Математические методы в
управлении: Учеб. пособие. – М.: Вузовский учебник:
ИНФРА-М, 2012.
ЭБС «Znanium.com»: https://www.znanium.com
2.
Методы оптимальных решений в экономике и
финансах: учебник / коллектив авторов; под ред. В.М.
Гончаренко, В.Ю. Попова. – М.: КНОРУС, 2014, 2016. – 400
с.
ЭБС «Book.ru»: https://www.book.ru/book/915989
3.
Орлова
И.В.,
Половников
В.А.
Экономикоматематические методы и модели: компьютерное
моделирование: Учеб. пособие. – 3-е изд., перераб. и доп.
– М.: Вузовский учебник: ИНФРА-М, 2012, 2014.
ЭБС «Znanium.com»: https://www.znanium.com
4. Филонова Е.С. Линейные модели в экономике. Учебное
пособие. – Орел: ООО ПФ «Картуш», 2016.

2.

б) дополнительная:
5. Кремер Н.Ш. и др. Исследование операций в экономике:
Учебник для вузов. – М.: Издательство ЮРАЙТ, 2014, 2016. –
Серия: Бакалавр. Академический курс.
ЭБС «Biblio-online.ru»: https://www. biblio-online.ru
6. Орлова И.В.
Экономико-математическое
моделирование: Практическое пособие по решению задач.
– 2-е изд., испр. и доп. – М.: Вузовский учебник: ИНФРА-М,
2012 – 2014.
ЭБС «Znanium.com»: https://www.znanium.com
7.
Экономико-математические методы и прикладные
модели: учебник для бакалавриата и магистратуры / В.В.
Федосеев, А.Н. Гармаш, И.В. Орлова; под ред. В.В.
Федосеева. – 4-е изд. перераб. и доп. – М.: Издательство
Юрайт, 2016.
ЭБС «Biblio-online.ru»: https://www. biblio-online.ru

3. Методические пособия

1. Методы оптимальных решений. Методические указания по
выполнению контрольной работы. – М.: Финансовый
университет, 2016.
2. Теория игр. Учебно-методическое пособие. - Орел. ООО ПФ
«Картуш», 2013.
3. Филонова Е.С., Агеев А.В.
Экономико-математические
методы
и
прикладные
модели. Практикум (по теме «Модели управления
товарными запасами») для студентов бакалавриата,
обучающихся на третьем курсе по направлениям 080500.62
«Менеджмент», 080100.62 «Экономика». – М.: ВЗФЭИ, 2011.
Учебно-методический
комплекс

4. Студент должен сдать:

1) домашнюю контрольную работу,
(в том числе пройти по ней
собеседование и получить баллы за
текущий контроль);
2) экзамен в зимнюю сессию

5. ВВЕДЕНИЕ В ПРЕДМЕТ

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

6.

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

7.

Модель – это упрощенный образ
(подобие) исследуемого явления,
процесса, объекта
Современная экономика
и управление – это мир моделей
1
2
Y oK L

8.

Бухгалтерский баланс
A
ст. АКТИВА
В
ст. ПАССИВА

9.

S P (1 ni )
S P (1 i )
Сравнение множителей наращения
(ставка 15 %, временная база 360 дней)
Срок депозита n
Множители наращения
(1 ni)
30 дней
180 дней
1 год
5 лет
10 лет
20 лет
(1 i)
1,0125
1,075
1,15
1,0117
1,0724
1,15
1,75
2,5
4
2,0114
4,0456
16,3665
n
n

10.

Виды моделей:
1) физические
2) абстрактные:
а) символические
б) словесно-описательные
Цели моделирования:
1) оптимизация
2) имитация
3) анализ и прогнозирование

11.

Экономико-математическая модель
(ЭММ) – это образ экономического объекта,
примерно воссоздаваемый с помощью
математического языка
Классификация ЭММ:
1) макро- и микроэкономические;
2) прескриптивные и дескриптивные;
3) статические и динамические;
4) детерминированные и стохастические

12.

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

13. Тема: Линейное программирование

1.1. Экономико-математическая
модель оптимизационной задачи и
задачи линейного программирования
1.2. Графический метод решения
задачи линейного программирования
1.3. Симплекс-метод решения задач
линейного программирования
1.4. Основы теории двойственности

14. 1.1. Экономико-математическая модель оптимизационной задачи и задачи линейного программирования

Принцип оптимальности:
выбор среди множества допускаемых в
данной ситуации решений наиболее
выгодного с точки зрения критерия
оптимальности
Критерии оптимальности:
1.
2.
3.
4.
5.
Максимум прибыли
Минимум затрат
Максимальное число комплектов
Минимальные временные затраты
Минимальная стоимость перевозок

15. Модель оптимизационной задачи

F f ( x1 , x2 ,..., xn ) max (min)
g1 ( x1 , x2 ,..., xn ) , , b1
g 2 ( x1 , x2 ,..., xn ) , , b 2
.........................................
g m ( x1 , x2 ,..., xn ) , , b m
x j 0, j 1,2,..., n

16. Общая задача линейного программирования (ЗЛП)

F c1 x1 c2 x2 ... cn xn max (min)
a 11 x1 a12 x2 ... a1n xn , , b1
a 21 x1 a22 x2 ... a2 n xn , , b 2
......................................................
a m1 x1 am 2 x2 ... amn xn , , b m
x j 0, j 1,2,..., n.

17.

Примеры на построение ЭММ
Для изготовления двух видов продукции Р1 и Р2 используют четыре
вида ресурсов S1 , S 2 , S 3 , S 4 . Необходимые данные приведены в таблице:
Вид ресурса
Запас
ресурса
Количество ресурсов на единицу
продукции
Р1
Р2
S1
18
1
3
S2
16
2
1
S3
5
-
1
S4
21
3
-
-
2
3
Прибыль от
единицы
продукции

18.

ЭММ задачи

19.

20. Оптимальный план выпуска молочной продукции

Ресурсы
Продукция
Молоко
Запасы
Кефир
Сметана
Молоко
1,01
1,01
9,45
136
Основн. обор.
0,18
0,19
-
21,4
Спец. автом.
-
-
3,25
16,25
30
22
136
Прибыль
F 30 x1 22 x2 136 x3 max
1.01x1 1.01x2 9.45 x3 136
0.18 x1 0.19 x2
21.4
3.25x 3 16.25
100
x1
x1,2,3
0

21. Решение:

X1
X2
X3
118.8889
0
1.684891 F
30
22
136
3795.812
1
0
0
118.8889
>=
100
1.01
1.01
9.45
136
<=
136
0.18
0.19
0
21.4
<=
21.4
0
0
3.25
5.475897
<=
16.25

22. Отчет по устойчивости

Изменяемые ячейки
Результ.
Ячейка
Имя
значение
Нормир.
Целевой
Допустимое
Допустимое
стоимость
Коэффициен
т
Увеличение
Уменьшение
$B$3
X1
118.8888889
0
30
1E+30
8.392871067
$C$3
X2
0
8.859141682
22
8.859141682
1E+30
$D$3
X3
1.68489124
0
136
144.6930693
136
Ячейка
Имя
Результ.
Теневая
Ограничение
Допустимое
Допустимое
значение
Цена
Правая часть
Увеличение
Уменьшение
$E$6
F
118.8888889
0
100
18.88888889
1E+30
$E$7
F
136
14.39153439
136
31.32777778
15.92222222
$E$8
F
21.4
85.91416814
21.4
2.837623762
3.4
$E$9
F
5.475896531
0
16.25
1E+30
10.77410347

23. 1.2. Графический метод решения задачи линейного программирования

F c1 x1 c2 x2 ... cn xn max (min)
a 11 x1 a12 x2 ... a1n xn , , b1
a 21 x1 a22 x2 ... a2 n xn , , b 2
......................................................
a m1 x1 am 2 x2 ... amn xn , , b m
x j 0, j 1,2,..., n.

24. Геометрическая интерпретация линейных неравенств и их систем

ai1 x1 ai 2 x2 bi
x2
II
III
I
a11 x1 a12 x 2 b1
a 21 x1 a 22 x 2 b2
IV
A
ОДР
............................
a m1 x1 a m 2 x 2 bm
B
5
С
D
C
Fmax
0
E
F=0
7
x1

25.

Графический метод. Пример
Для изготовления двух видов продукции Р1 и Р2 используют четыре
вида ресурсов S1 , S 2 , S 3 , S 4 . Необходимые данные приведены в таблице:
Вид ресурса
Запас
ресурса
Количество ресурсов на единицу
продукции
Р1
Р2
S1
18
1
3
S2
16
2
1
S3
5
-
1
S4
21
3
-
-
2
3
Прибыль от
единицы
продукции

26.

Графический метод. Пример
x2
II
III
I
IV
A
B
5
С
ОДР
D
C
Fmax
0
Анализ чувствительности
Особые случаи граф. метода
E
F=0
7
x1

27. 1.3. Симплекс-метод решения задач линейного программирования

a11x1 a12 x2 ... a1 j x j ... a1n xn b1
a21x1 a22 x2 ... a2 j x j ... a2 n xn b2
............................................................
ai1 x1 ai 2 x2 ... aij x j ... ain xn bi
............................................................
am1 x1 am 2 x2 ... amj x j ... amn xn bm

28. Схема сравнения методов

29. Основные этапы симплексного метода:

1) определение какого-либо первоначального
допустимого базисного решения задачи;
2) правило перехода к нехудшему решению;
3)
проверка
оптимальности
допустимого
базисного решения.
Различают симплексный метод:
а) с естественным базисом;
б) с искусственным базисом

30.

Симплекс-метод с естественным
базисом
F 3x1 4 x 2 3x3 x 4 max
F 3x1 4 x2 3x3 x4 0
7 x1 2 x 2 2 x3 6 x 4 80
7 x1 2 x 2 2 x3 6 x 4 x5 80
5 x1 8 x 2 4 x3 3x 4 480
5 x1 8 x 2 4 x3 3x 4 x6 480
2 x1 4 x 2 x3 8 x 4 130
2 x1 4 x 2 x3 8 x 4 x7 130
x1 , x 2 , x 3 , x 4 0
Базис Свободный
член
Переменные
x1
x2
x3
x4
x5
x6
x7
Оценочные
отношения
x5
80
7
2
2
6
1
0
0
40
x6
480
5
8
4
3
0
1
0
60
x7
130
2
4
1
8
0
0
1
32.5
F
0
-3
-4
-3
-1
0
0
0
Первая симплексная таблица

31.

Вторая симплексная таблица
Свободный
Базис
член
Переменные
x1
x2
x3
x4
x5
x6
x7
Оценочные
отношения
x5
15
6
0
3/2
2
1
0
-1/2
10
x6
220
1
0
2
-13
0
1
-2
110
32,5
1/2
1
1/4
2
0
0
1/4
130
130
-1
0
-2
7
0
0
1
x2
F

32.

Третья симплексная таблица
Свободный
Базис
член
x3
x6
x2
F
Переменные
x1
x2
x3
x4
x5
x6
x7
10
4
0
1
4/3
2/3
0
-1/3
200
-7
0
0
15
2
3
-4/3
1
14
1
2
3
-1/6
0
2
4/3
0
1/3
30
-1/2
1
0
150
7
0
0
9
2
3
1
4
Оценочные
отношения

33.

1.4. Основы теории двойственности
F ( X ) с1 x1 с2 x2 ... сn xn max
a11 x1 a12 x2 ... a1n xn b1
a x a x ... a x b
2n n
2
21 1 22 2
..........................................
a x a x ... a x b
mn n
m
m1 1 m 2 2
xi 0, i 1,..., n
Z ( X ) b1 y1 b2 y 2 ... bm y m min
a11 y1 a21 y 2 ... am1 y m c1
a y a y ... a y c
m2 m
2
12 1 22 2
..........................................
a y a y ... a y c
mn m
n
1n 1 2 n 2
yi 0, i 1,..., m,

34. Отчет по устойчивости

Изменяемые ячейки
Результ.
Ячейка
Имя
значение
Нормир.
Целевой
Допустимое
Допустимое
стоимость
Коэффициен
т
Увеличение
Уменьшение
$B$3
X1
118.8888889
0
30
1E+30
8.392871067
$C$3
X2
0
-8.859141682
22
8.859141682
1E+30
$D$3
X3
1.68489124
0
136
144.6930693
136
Ячейка
Имя
Результ.
Теневая
Ограничение
Допустимое
Допустимое
значение
Цена
Правая часть
Увеличение
Уменьшение
$E$6
F
118.8888889
0
100
18.88888889
1E+30
$E$7
F
136
14.39153439
136
31.32777778
15.92222222
$E$8
F
21.4
85.91416814
21.4
2.837623762
3.4
$E$9
F
5.475896531
0
16.25
1E+30
10.77410347

35.

Теоремы двойственности
Теорема 1
Fmax Z min
Теорема 2
n
yi aij x j bi 0;
j 1
m
x j aij yi c j 0
i 1
Теорема 3
Fmax
yi* , i 1, 2, ..., m.
bi

36. Пример

Задача об оптимальном использовании ресурсов
(задача о коврах)
В распоряжении фабрики имеется определенное количество ресурсов:
рабочая сила (80 чел.-дней), сырье (480 кг), оборудование (130 станкочасов). Фабрика может выпускать ковры четырех типов. Данные о
количестве единиц каждого ресурса, необходимых для производства
одного ковра каждого типа, и доходах, получаемых предприятием от
единицы каждого типа товаров, приведены в таблице. Необходимо
составить план производства, максимизирующий доход от реализации.
Ресурсы
Нормы расхода ресурсов на один ковер
«Лужайка»
«Силуэт»
«Детский»
«Дымка»
Наличие
ресурсов
Труд
7
2
2
6
80
Сырье
5
8
4
3
480
Оборудование
2
4
1
8
130
Цена ковра, тыс. руб.
3
4
3
1

37.

Пример
F 3x1 4 x 2 3x3 x 4 max
7 x1 2 x 2 2 x3 6 x 4 80
5 x1 8 x 2 4 x3 3x 4 480
2 x1 4 x 2 x3 8 x 4 130
x1 , x 2 , x 3 , x 4 0.
Z 80 y1 480 y2 130 y3 min
7 y1 5 y2 2 y3 3
2 y1 8 y2 4 y3 4
2 y1 4 y2 y3 3
6 y1 3 y2 8 y3 1
y1 , y 2 , y 3 0.

38.

Пример
7 0 2 30 2 10 6 0 80
5 0 8 30 4 10 3 0 280 480
2 0 4 30 10 8 0 130
2 y1 8 y 2 4 y 3 4
2 y1 4 y 2 y 3 3
y 0
2
y1 2 y 3 2
2 y1 y 3 3
y1 2 2 y 3
2 2 2 y 3 y 3 3
4 4 y3 y3 3
y3
1
3
1
y1 2 2
3
1
y1 1 .
3
1
1
y1 1 , y 2 0, y 3
3
3
1
1
Z min 80 1 480 0 130 150.
3
3

39.

Целесообразность включения в план
производства новых видов изделий
j a1 j y1 a 2 j y 2 ... a mj y m c j
j 5 4 / 3 2 0 9 1 / 3 2 29 / 3 6 / 3 23 / 3 0

40.

Тема. Специальные задачи
линейного программирования
2.1. Задачи дискретного
программирования
2.2. Транспортная задача
2.3. Задача о назначениях

41.

Специальные задачи линейного
программирования
1. Задачи дискретного
программирования:
- целочисленные,
- с двоичными переменными.
2. Транспортные задачи:
- задачи о назначениях

42.

2.1. Задачи дискретного
программирования
Модель задачи целочисленного
программирования
F ( X ) с1 x1 с 2 x 2 ... с n x n max
a11 x1 a12 x 2 ... a1n x n b1
a x a x ... a x b
22 2
2n n
2
21 1
..........................................
a x a x ... a x b
m2 2
mn n
m
m1 1
x j 0, j 1,..., n
x j - целые числа
Методы целочисленной
оптимизации:
1. Методы отсечения
2. Комбинаторные методы
3. Приближенные методы

43.

Сущность методов отсечения

44.

Задачи с двоичными переменными
Управляющему банком предложены четыре проекта, претендующие
на получение кредита в банке. Ресурс банка в каждом периоде,
потребности проектов и прибыль по ним приведены в таблице (в усл. ед.):
Какие проекты следует финансировать, если цель состоит в
максимизации прибыли банка от кредитования?
Проект
Потребности проектов в объемах кредитов
Прибыль
Период 1
Период 2
Период 3
Период 4
А
8
8
10
10
34
Б
7
9
9
11
30
В
5
7
9
11
27
Г
9
8
7
6
39
Ресурс
банка
22
25
38
30

45.

2.2. Транспортная задача
Поставщики
Потребители

B1
Bj
B2
Запасы

Bn
А1
c11
c12

c1 j

c1n
А2
c21
c 22

c2 j

c2n

Ai

c i1

Ат
Потребности


ci 2


b1
b2

c ij


cm 2
c m1





c mj
bj

a2

cin


a1

ai

c mn


bn

46.

Различают открытую и закрытую
транспортные задачи
Закрытая транспортная задача
m
n
c x
ij ij
i 1 j 1
m
a b
i 1
m
n
i
j 1
j
x
ij
i 1
n
x
j 1
ij
min
bj ,
ai ,
xij 0.

47.

Открытая транспортная задача
m
n
a b
i
i 1
m
j 1
n
c x
ij ij
i 1 j 1
m
x
i 1
ij
m
j
n
a b
i 1
m
min
bj ,
i
n
c x
ij ij
i 1 j 1
m
x
ij
i 1
n
xij ai ,
j 1
xij 0.
j 1
n
x
j 1
ij
j
min
bj ,
ai ,
xij 0.

48.

Пример
Поставщики
Потребители
1
2
Запасы
3
4
1
4
1
2
5
40
2
3
2
3
7
60
3
4
4
5
2
90
Потребности
45
35
55
65

49.

Экономико-математическая модель задачи
F 4 x11 1 x12 2 x13 5 x14 3 x21 2 x22
3 x23 7 x24 4 x31 4 x32 5 x33 2 x34 min
3
4
c
i 1 j 1
3
x
i 1
j 1
xij min
ij
b j , (1)
ij
a i , ( 2)
4
x
ij
xij 0.
x11 x 21 x31 45
x12 x 22 x32 35
x13 x 23 x33 55
x14 x 24 x34 65
x11 x12 x13 x14 40
x 21 x 22 x 23 x 24 60
x31 x32 x33 x34 90
xij 0

50.

2.3. Задачи о назначениях
n
n
c
i 1
j 1
n
x
i 1
ij
n
x
j 1
ij
ij
xij
1,
1,
xij двоичны

51.

Пример
Предприниматель имеет 6 торговых точек по продаже продуктов питания. На
следующий рабочий день он располагает 5 продавцами (один из продавцов не успел
оформить медицинскую книжку). Из анализа сдачи ежедневной выручки в прошлом,
предприниматель произвел оценку среднедневного объема продаж продуктов в различных
торговых точках каждым из продавцов (произвел оценку элементов матрицы эффективностей
назначений). Результаты этой оценки представлены в таблице. Назначение продавца Б на
торговую точку III недопустимо по медицинским показаниям, т.е. в матрице эффективностей
проставлен запрет – «-».
Как предприниматель должен осуществить назначение продавцов по торговым точкам,
чтобы достичь максимального объема продаж?
Продавец
Среднедневной объем продаж по торговым точкам, у.е.
I
II
III
IV
V
VI
А
68
72
75
83
75
69
Б
56
60
-
63
61
59
В
35
38
40
45
25
27
Г
40
42
47
45
53
36
Д
62
70
68
67
69
70
English     Русский Правила