Вход

Методы принятия управленческих решений

Рекомендуемая категория для самостоятельной подготовки:
Контрольная работа*
Код 230053
Дата создания 03 июля 2016
Страниц 39
Мы сможем обработать ваш заказ (!) 1 апреля в 12:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
730руб.
КУПИТЬ

Описание

-00-- ...

Содержание

Содержание



Задание №1 3
Задание №2 13
Задание №3 19
Задание №4 29
Список использованной литературы 39

Введение

Задание №1

Симплекс методом решить ЗЛП.
Предприятие производит 3 вида продукции: А1, А2, А3, используя сырье двух видов: В1 и В2. Известны затраты сырья i-го вида на единицу изделия j-го вида аij , количество сырья каждого вида bi (i = 1, 2), а также прибыль, полученная от единицы изделия j-го вида сj (j=1,2,3).
Сколько изделий каждого вида необходимо произвести, чтобы получить:
1)максимум прибыли;
2) максимум товарной продукции?
Обозначения: в таблице приведена матрица затрат: А=(аij), справа от таблицы значение bi (i=1,2) и внизу сj (j=1,2,3).

Фрагмент работы для ознакомления

x1 = 2.
F(X) = 3 • 0 + 5 • 2 = 10.
Задание №3
Решить транспортную задачу. С – матрица стоимостей. Прочерк означает невозможность перевозки по данному маршруту.
a1 = 100; a2 = 50; a3 = 70;
b1 = 10; b2 = 80; b3 = 90; b4 = 20.
Решение
Математическая модель транспортной задачи:
F = ∑∑cijxij,
при условиях:
∑xij = ai, i = 1,2,…, m,
∑xij = bj, j = 1,2,…, n,
xij ≥ 0.
Запишем экономико-математическую модель для нашей задачи.
Переменные:
xij – количество груза от i-го поставщика j-му потребителю.
Ограничения по запасам:
x11 + x12 + x13 + x14 ≤ 100;
x21 + x22 + x23 + x24 ≤ 50;
x31 + x32 + x33 + x34 ≤ 70.
Ограничения по потребностям:
x11 + x21 + x31 ≥ 10;
x12 + x22 + x32 ≥ 80;
x13 + x23 + x33 ≥ 90;
x14 + x24 + x34 ≥ 20.
Так как в условии задачисуществуют запреты на перевозку из i-го пункта в j-й, то в качестве стоимостей указываем величину больше максимального значения тарифа (ставим 100 вместо прочерков).
Целевая функция:
4x11 + 7x12 + 1x13 + 1x14 + 5x21 + 100x22 + 3x23 + 4x24 + 3x31 +
+ 100x32 + 2x33 + 8x34 → min
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов:

1
2
3
4
Запасы
1
4
7
1
1
100
2
5
100
3
4
50
3
3
100
2
8
70
Потребности
10
80
90
20
Проверим необходимое и достаточное условие разрешимости задачи:
∑a = 100 + 50 + 70 = 220;
∑b = 10 + 80 + 90 + 20 = 200.
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза у поставщиков. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равную 20 (200—220). Тарифы перевозки единицы груза от поставщика ко всем потребителям полагаем равны нулю.
Занесем исходные данные в распределительную таблицу:
1
2
3
4
5
Запасы
1
4
7
1
1
100
2
5
100
3
4
50
3
3
100
2
8
70
Потребности
10
80
90
20
20
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены:
1
2
3
4
5
Запасы
1
4
7
1[90]
1[10]
100
2
5
100[40]
3
4[10]
50
3
3[10]
100[40]
2
8
0[20]
70
Потребности
10
80
90
20
20
В результате получен первый опорный план, который является допустимым, так как все грузы от поставщиков вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 1*90 + 1*10 + 100*40 + 4*10 + 3*10 + 100*40 = 8170.
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v3 = 1; 0 + v3 = 1; v3 = 1
u1 + v4 = 1; 0 + v4 = 1; v4 = 1
u2 + v4 = 4; 1 + u2 = 4; u2 = 3
u2 + v2 = 100; 3 + v2 = 100; v2 = 97
u3 + v2 = 100; 97 + u3 = 100; u3 = 3
u3 + v1 = 3; 3 + v1 = 3; v1 = 0
u3 + v5 = 0; 3 + v5 = 0; v5 = -3.
v1=0
v2=97
v3=1
v4=1
v5=-3
u1=0
4
7
1[90]
1[10]
u2=3
5
100[40]
3
4[10]
u3=3
3[10]
100[40]
2
8
0[20]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij:
(1;2): 0 + 97 > 7; ∆12 = 0 + 97 - 7 = 90
(2;3): 3 + 1 > 3; ∆23 = 3 + 1 - 3 = 1
(3;3): 3 + 1 > 2; ∆33 = 3 + 1 - 2 = 2
max(90,1,2) = 90.
Выбираем максимальную оценку свободной клетки (1;2): 7.
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-»:
1
2
3
4
5
Запасы
1
4
7[+]
1[90]
1[10][-]
100
2
5
100[40][-]
3
4[10][+]
50
3
3[10]
100[40]
2
8
0[20]
70
Потребности
10
80
90
20
20
Цикл приведен в таблице (1,2 → 1,4 → 2,4 → 2,2).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 4) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план:
1
2
3
4
5
Запасы
1
4
7[10]
1[90]
1
100
2
5
100[30]
3
4[20]
50
3
3[10]
100[40]
2
8
0[20]
70
Потребности
10
80
90
20
20
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 7; 0 + v2 = 7; v2 = 7
u2 + v2 = 100; 7 + u2 = 100; u2 = 93
u2 + v4 = 4; 93 + v4 = 4; v4 = -89
u3 + v2 = 100; 7 + u3 = 100; u3 = 93
u3 + v1 = 3; 93 + v1 = 3; v1 = -90
u3 + v5 = 0; 93 + v5 = 0; v5 = -93
u1 + v3 = 1; 0 + v3 = 1; v3 = 1.
v1=-90
v2=7
v3=1
v4=-89
v5=-93
u1=0
4
7[10]
1[90]
1
u2=93
5
100[30]
3
4[20]
u3=93
3[10]
100[40]
2
8
0[20]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij.
(2;3): 93 + 1 > 3; ∆23 = 93 + 1 - 3 = 91
(3;3): 93 + 1 > 2; ∆33 = 93 + 1 - 2 = 92
max(91,92) = 92.
Выбираем максимальную оценку свободной клетки (3;3): 2.
Для этого в перспективную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-»:
1
2
3
4
5
Запасы
1
4
7[10][+]
1[90][-]
1
100
2
5
100[30]
3
4[20]
50
3
3[10]
100[40][-]
2[+]
8
0[20]
70
Потребности
10
80
90
20
20
Цикл приведен в таблице (3,3 → 3,2 → 1,2 → 1,3).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 40. Прибавляем 40 к объемам грузов, стоящих в плюсовых клетках и вычитаем 40 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план:
1
2
3
4
5
Запасы
1
4
7[50]
1[50]
1
100
2
5
100[30]
3
4[20]
50
3
3[10]
100
2[40]
8
0[20]
70
Потребности
10
80
90
20
20
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 7; 0 + v2 = 7; v2 = 7
u2 + v2 = 100; 7 + u2 = 100; u2 = 93
u2 + v4 = 4; 93 + v4 = 4; v4 = -89
u1 + v3 = 1; 0 + v3 = 1; v3 = 1
u3 + v3 = 2; 1 + u3 = 2; u3 = 1
u3 + v1 = 3; 1 + v1 = 3; v1 = 2
u3 + v5 = 0; 1 + v5 = 0; v5 = -1.
v1=2
v2=7
v3=1
v4=-89
v5=-1
u1=0
4
7[50]
1[50]
1
u2=93
5
100[30]
3
4[20]
u3=1
3[10]
100
2[40]
8
0[20]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij:
(1;4): 0 + 2 > 1; ∆14 = 0 + 2 - 1 = 1.
Выбираем максимальную оценку свободной клетки (1;4): 1.
Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-»:
1
2
3
4
5
Запасы
1
4
7[80]
1[20][-]
1[+]
100
2
5
100
3[10][+]
4[20][-]
0[20]
50
3
3[10]
100
2[60]
8
70
Потребности
10
80
90
20
20
Цикл приведен в таблице (1,4 → 1,3 → 2,3 → 2,4).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план:
1
2
3
4
5
Запасы
1
4
7[80]
1
1[20]
100
2
5
100
3[30]
4[0]
0[20]
50
3
3[10]
100
2[60]
8
70
Потребности
10
80
90
20
20
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 7; 0 + v2 = 7; v2 = 7
u1 + v4 = 1; 0 + v4 = 1; v4 = 1
u2 + v4 = 4; 1 + u2 = 4; u2 = 3
u2 + v3 = 3; 3 + v3 = 3; v3 = 0
u3 + v3 = 2; 0 + u3 = 2; u3 = 2
u3 + v1 = 3; 2 + v1 = 3; v1 = 1
u2 + v5 = 0; 3 + v5 = 0; v5 = -3.
v1=1
v2=7
v3=0
v4=1
v5=-3
u1=0
4
7[80]
1
1[20]
u2=3
5
100
3[30]
4[0]
0[20]
u3=2
3[10]
100
2[60]
8
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Изобразим оптимальный план перевозок в виде графа (рис. 1).
Рис. 1. Оптимальный план перевозок в виде графа
Минимальные затраты составят:
F(x) = 7*80 + 1*20 + 3*30 + 0*20 + 3*10 + 2*60 = 820.
Анализ оптимального плана.
От 1-го поставщика необходимо груз направить 2-му потребителю (80), 4-му потребителю (20). От 2-го поставщика необходимо весь груз направить 3-му потребителю. От 3-го поставщика необходимо груз направить 1-му потребителю (10), 3-му потребителю (60).
У 2-го поставщика остался невостребованным груз в количестве 20 ед.
Задача имеет множество оптимальных планов, поскольку оценка для (2;4) равна 0.
Задание №4
Решите методом ветвей и границ следующую задачу коммивояжера:
Решение
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 39 + 20 + 55 + 18 + 25 + 16 = 173.
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент:
di = min(j) dij
i j
1
2
3
4
5
6
di
1
M
39
45
2
51
33
2
2
30
M
20
33
40
35
20
3
54
16
M
55
22
56
16
4
19
36
25
M
18
43
18
5
29
8
8
12
M
25
8
6
16
47
31
14
8
M
8
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль:
i j
1
2
3
4
5
6
1
M
37
43
49
31
2
10
M
13
20
15
3
38
M
39
6
40
4
1
18
7
M
25
5
21
4
M
17
6
8
39
23
6
M
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
i j
1
2
3
4
5
6
1
M
37
43
49
31
2
10
M
13
20
15
3
38
M
39
6
40
4
1
18
7
M
25
5
21
4
M
17
6
8
39
23
6
M
dj
1
15
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
i j
1
2
3
4
5
6
1
M
37
43
49
16
2
9
M
13
20
3
37
M
39
6
25
4
18
7
M
10
5
20
4
M
2
6
7
39
23
6
M
Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 2+20+16+18+8+8+1+0+0+0+0+15 = 88.
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j. Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij ≥ 0.
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город. Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.
Шаг №1. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках:
i j
1
2
3
4
5
6
di
1
M
37
43
0(20)
49
16
16
2
9
M
0(0)
13
20
0(2)
3
37
0(6)
M
39
6
25
6
4
0(7)
18
7
M
0(0)
10
5
20
0(0)
0(0)
4
M
2
6
7
39
23
6
0(6)
M
6
dj
7
4
2
d(1,4) = 16 + 4 = 20; d(2,3) = 0 + 0 = 0;
d(2,6) = 0 + 2 = 2; d(3,2) = 6 + 0 = 6;
d(4,1) = 0 + 7 = 7; d(4,5) = 0 + 0 = 0;
d(5,2) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0;
d(6,5) = 6 + 0 = 6.
Наибольшая сумма констант приведения равна (16 + 4) = 20 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
Исключение ребра (1,4) проводим путем замены элемента d14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу:
i j
1
2
3
4

Список литературы

1. Акулич, И. Л. Математическое программирование в примерах и задачах : учеб. пособие / И. Л. Акулич. - Изд. 2-е, испр. -СПб. [и др.] : Лань, 2009. - 347 с.
2. Балдин, К. В. Математическое программирование : учебник / К. В. Балдин, Н. А. Брызгалов, А. В. Рукосуев ; под общ. ред. К. В. Балдина. -М. : Дашков и К, 2009.- 218 с.
3. Власов М.П. Моделирование экономических процессов : учеб. пособие / М.П. Власов, П.Д. Шимко. – СПб. : СПбГИЭУ, 2006. - 386 с.
4. Грахов В.Б. Линейное программирование в упражнениях и задачах. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2006.
5. Казанская О.В., Юн С.Г., Альсова О.К. Модели и методы оптимизации. Практикум: уч. пособие - Новосибирск: Изд-во НГТУ, 2012.- 204 с.
6. Лугинин О.Е. Экономико-математические методы и модели: теория и практика с решением задач: учебное пособие. – Ростов н/Д: Феникс, 2009.
7. Минюк С. А., Ровба Е. А., Кузьмич К. К. Математические методы и модели в экономике: Учеб. пособие /— Мн.: ТетраСистемс, 2002. - 432 с.
8. Орлов А.И. Теория принятия решений: учеб. пособие. М.: Экзамен, 2005.- 656 с.
9. Соколов А.В., Токарев В.В. Методы оптимальных решений. М.: Физматлит, 2010.
10. Экономико-математическое моделирование: учебник / под ред. И.Н. Дрогобыцкого. – М. : ЭКЗАМЕН XXI, 2006. – 797 с.
Очень похожие работы
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
bmt: 0.00618
© Рефератбанк, 2002 - 2024