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

Требуется распределить капитал в размере 700 тыс руб (7 единиц по 100 тыс руб) между четырьмя однотипными предприятиями (четырьмя однотипными филиалами фирмы, что то же самое), доходы которых за 1 месяц зависят от размера вложения X и заданы таблицей вида

вклад, в 100 тыс руб	Доходы предприятий, в тыс. руб
X	D1(X)	D2(X)	D3(X)	D4(X)
0	0	0	0	0
1	4,6	7,6	6,6	8,6
2	9,6	12,6	11,6	14,6
3	16,6	16,6	16,6	19,6
4	23,6	20,6	21,6	23,6
5	30,8	25,8	27,8	27,8
6	34,8	29,8	32,8	30,8
7	37,8	32,8	37,8	31,8

Например, выделенное число 11,6 есть доход 11600 руб от третьего предприятия, если капиталовложение в это третье предприятие составит 2 условные единицы, то есть 200000 руб.

Ответом (оптимальным вложением, оптимальным управлением) является набор из вложений ( ) такой, что

1)

2)

3) - целые

4) Суммарный доход от 4х предприятий будет максимальным:

Варианты задания даны в прилагаемом файле Excel «Задача 3. Распределение вложений между 4 предприятиями. xls». Каждый вариант на своем листе.
B. Теоретический материал. Задача об аренде оборудования

1. Планы аренды. Постановка задачи.

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

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

Примеры планов аренды:

1.  (1,2,3,…,7) - план аренды на 6 месяцев, состоящий в том, аренда оформляется 6 раз – каждый раз на 1 месяц;

2.  (1, 3, 5, 7) - план аренды на 6 месяцев, состоящий в том, аренда оформляется 3 раза – каждый раз на 2 месяца;

3.  (1, 3, 7) - план аренды на 6 месяцев, состоящий в том, аренда оформляется 2 раза – первый раз на 2=3-1 месяца (первый и второй), второй раз на 4 месяца (третий, четвертый, пятый и шестой);

4.  (1, 15) план аренды на 14 месяцев, состоящий в том, аренда оформляется 1 раз – с начала 1-го месяца на весь срок – до конца 14 - го месяца.

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

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

Пример. Пусть при стоимости аренды заданы в таблице

j i	2	3	4
1	4	9	15
2	–	6	10
3	–	–	6

Из 4 планов аренды

1) (1,2,3,4), С=4+6+6=16;

2) (1,2,4), С=4+10=14;

3) (1,3,4), С=9+6=15;

4) (1,4), С=15

план (1,2,4), то есть план "взять в аренду на 1мес. + 2 мес." является оптимальным планом со стоимостью Сmin =14 у. е.

2. Сетевая модель задачи и ее решение.

Изобразим моменты в виде вершин графа, а пары в виде ориентированных дуг этого графа (основные понятия теории графов и терминология приведены в Приложении). Проставим на дугах соответствующие стоимости аренды и будем считать их длинами этих дуг. Тогда произвольный план можно представить как путь из вершины 1 в вершину , а стоимость плана – длиной этого пути. Наоборот, каждый путь указанного вида является планом аренды. Оптимальным планом аренды будет кратчайший путь из 1 в . Таким образом, задача об аренде оборудования является частным случаем известной задачи о нахождении кратчайшего пути (маршрута) [1-4].

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

Найдём путь методом потенциалов [3, 4] для бесконтурных сетей.

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

; ,

минимум берётся по всем дугам , выходящим из вершины .

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

Пример 2. . Пусть при стоимости аренды заданы в таблице:

j i	2	3	4	5	6	7
1	49	99	145	197	244	296
2	–	50	96	146	198	247
3	–	–	48	95	147	189
4	–	–	–	49	98	148
5	–	–	–	–	51	101
6	–	–	–	–	–	53

Составим сетевую модель:

Определим потенциал каждого месяца:

V7 = 0 V6 = C6,7+V7 = 53

V5 = min (C5,6+V6;C5,7 +V7) = min (51+53;101) = C5,7+V7 = 101

V4 = min (C4,5+V5;C4,6+V6;C4,7+V7) = min (49+101;98+53;148) = C4,7+V7 = 148

V3 = min (C3,4+V4;C3,5+V5;C3,6+V6;C3,7+V7) = min (48+148;95+101;147+53;189) = C3,7 +V7= 189

V2 = min (C2,3+V3;C2,4+V4;C2,5+V5;C2,6+V6;C2,7+V7) = min (50+189; 96+148; 146+101; 198+53; 247) = C2,3 + V3 = 239

V1 = min (C1,2+V2;C1,3+V3;C1,4+V4;C1,5+V5;C1,6+V6;C1,7+V7) = min (49+239; 99+189; 145+148; 197+101; 244+53; 296) = C1,2 + V2 или С1,3 + V3 = 288.

Получаем сеть следующего вида:

Найдем оптимальный план аренды оборудования.

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

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

a) (1, 2, 3,7) = 1мес. + 1 мес. + 4 мес. и

b) (1, 3, 7) = 2 мес. + 4 мес. со стоимостью Cmin = V1 =288.

3. Табличный метод решения задачи.

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

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

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

Рассмотрим снова пример 2 и получим следующую таблицу.

J i	2	3	4	5	6	7	Vi
1	49	99	145	197	244	296	288
2	–	50	96	146	198	247	239
3	–	–	48	95	147	189	189
4	–	–	–	49	98	148	148
5	–	–	–	–	51	101	101
6	–	–	–	–	–	53	53
7							0

В этой таблице выделены следующие клетки:

1.  (6,7),.так как V6 = C6,7+V7 = 53;

2.  (5.7), так как V5 = C5,7+V7 = 101

3.  (4,7),.так как V4 = C4,7+V7 = 148

4.  (3,7), так как V3 = C3,7 +V7= 189

5.  (2,3), так как V2 = C2,3 + V3 = 239

6.  (1,2) и (1,3), так как V1 = C1,2 + V2 = С1,3 + V3 = 288.

Последовательность выделенных клеток (1,2), (2,3), (3,7) дает оптимальный план аренды (1, 2, 3, 7), а последовательность выделенных клеток (1, 3) и (3,7) дает оптимальный план аренды (1, 3, 7). Стоимость оптимальных планов равна 288 у. е. (первая строка, дополнительный столбец).

Приложение. Основные понятия теории ориентированных графов.

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

Математическим, формальным представлением объектов, между которыми попарно установлены некоторые связи, является граф [1-4]. Сети являются частным случаем графов. Ограничимся случаем ориентированных графов.

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

Будем считать, что между двумя вершинами есть не более одной дуги (нет "параллельных" дуг). Формально этого можно добиться, разбив дугу на две с помощью промежуточной вершины. В дальнейшем дугу будем записать в виде упорядоченной пары (a, b), где a – начало дуги, b – конец дуги.

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

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

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

Замкнутая цепочка называется циклом.

Рис. 1

( a, c, b, d, f ) – путь ( b, d, f, c, b ) – контур ( a, b, c, f ) – цепочка ( a, b, c, a ) – цикл

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

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

а) связности;

б) отсутствия петель (начало и конец дуги различны);

в) отсутствие параллельных дуг. ¨

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

Замечание. В литературе встречается также термин ациклическая сеть.

Сеть на рис.1 не является бесконтурной, т. к. есть контур ( b, d, f, c, b).

Н у м е р а ц и я вершин сети – это сопоставление вершинам номеров – натуральных чисел, при этом различным вершинам сопоставляются различные номера.

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

а) номера идут подряд: 1, 2, …, m, где m – число вершин;

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

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

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

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

2. Присвоим найденной вершине текущий номер. Первый раз таким номером является m – число вершин сети.

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

Замечание. 1. Если не удаётся найти вершину в шаге 1, то в сети есть контур и правильная нумерация невозможна, так что алгоритм Форда является проверкой, будет ли сеть бесконтурной.

2. Правильных нумераций в сети может быть несколько.

Неправильная нумерация Правильная нумерация (1 и 2, 4 и 5 можно поменять местами)

Рис. 2.

C. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНЫХ ЗАДАНИЙ

Задание 1. Классическая транспортная задача.

Задача описана во всех учебниках по моделированию управленческих решений, математическому программированию и исследованию операций. См., например, [1,3,4].

В ответе должны быть:

1) оптимальный план перевозок в виде таблицы с потенциалами;

2) граф перевозок с 3 складами и 3 потребителями (без фиктивных потребителей и складов!);

3) Оптимальная стоимость.

Проверить ответ можно, решив задачу в EXCEL. Смотри прилагаемый файл «Решение в EXCEL двухиндексных задач линейного программирования (ТЗ).doc»

Задание 2. «Задача об аренде оборудования».

О задачах об аренде оборудования можно прочитать в [3]. Постановка задачи и два метода ее решения приводятся в разделе B.

Задачу достаточно решить одним из предложенных способов (при этом студентам-заочникам следует знать оба метода).

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

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

Искать планы аренды методом перебора не разрешается!

Задание 3. Задача распределения вложений.

Задача решается в табличной форме. Необходимо привести несколько таблиц:

1) Исходную таблицу функций доходов;

2) Подробные таблицы 1-4 расчета условных доходов и условных оптимальных управлений . Их можно объединить в одну (если влезет на лист!).

3) Итоговую таблицу условных доходов и условных оптимальных управлений .

4) Расчет (безусловных) оптимальных управлений (вложений) и оптимального дохода. Ответ – 5 чисел. Если решений много, привести все.

Оформление в EXCEL приветствуется! Литература

1.  , Математические методы моделирования экономических систем. Учеб. пособие. 2-е изд. Перераб. и доп. М.: Финансы и статистика. 2006.432 с. (Электронная версия есть на сервере СыктГУ, лаборатория №2 , Учебные материалы\Методы принятия управленческих решений)

2.  Методы и алгоритмы принятия решений в экономике. Учебное пособие. Рек. УМО. Москва: Финансы и статистика, 20 с. (ЭБС). Электронная версия есть на сервере СыктГУ, лаборатория №2 , Учебные материалы\ Факультет управления\ Методы принятия управленческих решений

3.  Никитенков А. А. Задачи линейного программирования и методы их решения. Уч. пособие. Сыктывкар: Изд-во СыктГУ, 2008, 268с.

4.  Математическое моделирование в экономике. М.: БЕК, 2002, 133с.

Учебно-методическая литература

5.  Математическое программирование и исследование операций. Методические указания. Сыктывкар: Изд-во СыктГУ, 2007 (есть электронная версия).

6.  Методы принятия управленческих решений. Пособие и контрольные задания для студентов-заочников. СыктГУ, 2012, 46 с. (Электронная версия есть на сервере СыктГУ, лаборатория №2 , Учебные материалы\ Факультет управления\ Методы принятия управленческих решений)