Элементы теории игр (стр. 3 )

Начальное состояние . разобьем весь процесс выделения средств предприятиям на 4 шага.

На 1-ом шаге выделяем Х1 1-му предприятию. После этого останется .

На 2-ом шаге выделяем Х2 2-му предприятию. После этого останется .

На 3-ом шаге выделяем Х3 3-му предприятию. После этого останется .

На 4-ом шаге выделяем Х4 4-му предприятию.

Уравнения Беллмана будут иметь вид:

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

Если k=4, тогда .

Заполним таблицу:

S3\X4	0	20	40	60	Z4(S3)	X*4
0	0				0	0
20		14			14	20
40			20		20	40
60				35	35	60

В столбце S3 и строке X4 указаны все возможные значения. Все оставшиеся перед 4-ым шагом средства нужно выделить 4-му предприятию. Поэтому числа из столбца исходной таблицы записываем в нашу таблицу в столбцы со 2-го по 5-ый. В столбцах со 2-ой по 5-ый определяем максимум в каждой строке, и результат пишем в 6-ой столбец. Те X4, которым соответствуют числа 6-ого столбца, пишем в 7-ой столбец.

Пусть k=3, тогда .

Определим оптимальную стратегию при распределении средств между 3-м и 4-м предприятиями. Заполним новую таблицу:

S2\X3	0	20	40	60	Z3(S2)	X*3
0	0+0=0				0	0
20	0+14=14	14+0=14			14	0 или 20
40	0+20=20	14+14=28	21+0=21		28	20
60	0+35=35	14+20=34	21+14=35	34+0=34	35	0 или 40

В 1-м столбце указано, сколько средств осталось для 3-го и 4-го предприятий. В строке X3 дана информация о том сколько из этих оставшихся средств достанется 3-му предприятию. Поясним как заполняются столбцы со 2-го по 5-ый.

В клетке (2;2) на долю 3-го и 4-го предприятия приходится , из них на долю 3-го предприятия приходится . поэтому нужно сложить значения из исходной таблицы для (это 0) и из предпоследнего столбца предыдущей таблицы при , то есть 0+0=0.

В клетке (3;2) на долю 3-го и 4-го предприятия приходится , из них на долю 3-го предприятия приходится . поэтому нужно сложить значения из исходной таблицы для (это 0) и из предпоследнего столбца предыдущей таблицы при , (это 14) то есть 0+14=0. И т. д.

В столбцах со 2-ой по 5-ый определяем максимум в каждой строке, и результат пишем в 6-ой столбец. Те X3, которым соответствуют числа 6-ого столбца, пишем в 7-ой столбец.

Пусть k=2, тогда .

Определим оптимальную стратегию при распределении средств между 2-м, 3-м и 4-м предприятиями. Заполним новую таблицу:

S1\X2	0	20	40	60	Z2(S1)	X*2
0	0+0=0				0	0
20	0+14=14	6+0=6			14	0
40	0+28=28	6+14=20	23+0=23		28	0
60	0+35=35	6+28=34	28+14=37	30+0=30	37	40

В 1-м столбце указано, сколько средств осталось для 2-го, 3-го и 4-го предприятий. В строке X2 дана информация о том, сколько из этих оставшихся средств достанется 2-му предприятию. Поясним, как заполняются столбцы со 2-го по 5-ый.

Например, в клетке (5;4) на долю 2-го 3-го и 4-го предприятия приходится , из них на долю 2-го предприятия приходится . поэтому нужно сложить значения из исходной таблицы для (это 23) и из предпоследнего столбца предыдущей таблицы при , (это 14) то есть 23+14=37. И т. д.

В столбцах со 2-ой по 5-ый определяем максимум в каждой строке, и результат пишем в 6-ой столбец. Те X2, которым соответствуют числа 6-ого столбца, пишем в 7-ой столбец.

Пусть k=1, тогда .

Определим оптимальную стратегию при распределении средств между предприятиями. Заполним новую таблицу:

S0\X1	0	20	40	60	Z1(S0)	X*1
0	0+0=0				0	0
20	0+14=14	7+0=7			14	0
40	0+28=28	7+14=21	23+0=23		28	0
60	0+37=37	7+28=35	28+14=37	31+0=31	37	о или 40

В 1-м столбце указано, сколько средств. В строке X1 дана информация о том, сколько из этих оставшихся средств достанется 1-му предприятию. Поясним, как заполняются столбцы со 2-го по 5-ый.

Например, в клетке (4;3) на долю предприятий приходится , из них на долю 1-го предприятия приходится . поэтому нужно сложить значения из исходной таблицы для (это 7) и из предпоследнего столбца предыдущей таблицы при , (это 14) то есть 7+14=21. И т. д.

В столбцах со 2-ой по 5-ый определяем максимум в каждой строке, и результат пишем в 6-ой столбец. Те X1, которым соответствуют числа 6-ого столбца, пишем в 7-ой столбец.

Максимальное значение . Если .

Из таблицы при k=2 и находим в последнем столбце , тогда .

Из таблицы при k=3 и находим в последнем столбце . Если тогда .

Из таблицы при k=4 и находим в последнем столбце .

Получен оптимальный вариант распределения средств:

Если тогда . Из таблицы при k=4 и находим в последнем столбце .

Получен еще один оптимальный план распределения средств: .

Если . Из таблицы при k=2 и находим в последнем столбце , тогда . Действия при рассмотрены выше.

Получим еще два оптимальных варианта распределения средств:

и

Для наглядности сведем оптимальные решения в таблицу:

Х*1	Х*2	Х*3	Х*4
0	40	0	20
0	40	20	0
40	0	0	20
40	0	20	0

Общий прирост выпуска продукции в каждом из вариантов равен 37 млн. руб.

Замечание: такие результаты были бы получены и при любом другом порядке распределения денег между предприятиями.

Замечание: такие результаты были бы получены и при любом другом порядке распределения денег между предприятиями.

Задача: между 4-мя предприятиями распределяется 60 миллионов рублей. Прирост выпуска продукции на каждом предприятии зависит от выделенной суммы средств X. Значения прироста задаются в виде таблицы . Найти такой план распределения средств между предприятиями, при котором общий прирост выпуска продукции будет максимальным.

Средства Х, млн. руб.	Прирост выпуска продукции, млн. руб.
g1(x)	g2(x)	g3(x)	g4(x)
0	0	0	0	0
20	6	5	12	10
40	21	19	22	20
60	29	31	33	34

Задания.

1.  Найти оптимальное распределение средств между nпредприятиями, при условии, что прибыль f(x), полученная от каждого предприятия, является функцией от вложенных в нее средств х. Вложения кратны Dх, а f(x) задана таблично.

a.  s0=9; n=3; Dх=1

x	1	2	3	4	5	6	7	8	9
f1(x)	5	9	12	14	15	18	20	24	27
f2(x)	7	9	11	13	16	19	21	22	25
f3(x)	6	10	13	15	16	18	21	22	25

b.  s0=5; n=4; Dх=1

x	1	2	3	4	5
f1(x)	0.2	0.9	1.0	1.2	2.0
f2(x)	1.0	1.1	1.3	1.4	1.8
f3(x)	2.1	2.5	2.9	3.9	4.9
f4(x)	0	2.0	2.5	3.0	4.0

В условиях задачи 1 а найти оптимальное распределение средств при s0=8.

Модели сетевого планирования и управления.

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

Первые системы, использующие графики были применены в США в конце 50-ых годов и получили название CPM (английская аббревиатура, обозначающая метод критического пути) и PERT (метод оценки и обзора программы). Система CPM была впервые применена при управлениями строительными работами, система PERT при разработке системы "Полярис".

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

СПУ основано на моделировании процесса с помощью сетевого графика и представляет собой совокупность расчетных методов и контрольных мероприятий по планированию и управлению комплексом работ.

Система СПУ позволяет:

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

·  выявлять и мобилизовать резервы времени, трудовые материальные и денежные ресурсы;

·  осуществлять управление комплексом работ по принципу "ведущего звена" с прогнозированием и предупреждением возможных срывов работ;

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

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

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

Элементы сетевой модели:

·  события;

·  работы (допустимые управления).

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

Ожидание . – протяженный во времени процесс, не требующий затрат ресурсов (например, сушка, затвердевание бетона и т. д.).

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

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

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

Исходное событие не имеет предшествующих работ и событий.

Завершающее событие не имеет последующих работ и событий.

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

Пример фрагмента сетевого графика представлен на рисунке.

Рисунок 4

 

Рисунок 5

На рисунке приведен пример сетевого графика задачи моделирования и построения некоторого экономического объекта, где работы означают:

А – формулирование проблемы исследования;

Б – построение математической модели;

В – сбор информации;

Г – выбор метода решения;

Д – написание программы;

Е – расчет по программе;

Ж – представление результатов.

Из графика видно, что работы В и Г могут выполняться одновременно, независимо одна от другой, после свершения события 3, т. е. когда выполнены работы А и Б. Работа Д может быть выполнена после свершения события 4, т. е. когда выполнены работы А, Б и Г, а работа Е может быть выполнена только после наступления события 5, т. е. при выполненных работах А, Б, В, Г и Д.

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

 

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

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

Следует отметить, что принцип построения "работы – связи", в отличие от принципа "события – работы" имеет ряд преимуществ:

·  не содержит фиктивных работ,

·  имеет более простую технику построения и перестройки,

·  включает только понятные исполнителю работы;

и недостатков:

·  более громоздкий,

·  менее эффективный с точки зрения управления комплексом.

Показатель эффективности сети – это отношение числа работ к числу событий.

Порядок построения сетевых графиков.

Сетевые графики составляются на начальном этапе планирования.

Порядок построения:

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

2.  составляется (сшивается) сетевой график;

3.  рассчитываются параметры событий и работ. определяют резервы времени и критический путь;

4.  проводится анализ и оптимизация сетевого графика, который при необходимости вычерчивается заново с пересчетом параметров событий и работ.

Правила, которые необходимо соблюдать при построении сетевого графика:

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

Из события 3 нет последующих работ, следовательно работа 23 не нужна или не замечено необходимости определить работу за событием 3.

2. В сетевом графике не должно быть "хвостовых" событий, кроме исходного, которым не предшествовала хотя бы одна работа.

Событие 3 не может сбыть совершенным, следовательно работа 32 не может быть выполненной.

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

В сложных сетях контуры возникают достаточно часто и обнаруживаются с помощью ЭВМ

4. Два события должны быть связаны не более чем одной работой.

Такая ситуация возникает при изображении параллельно выполняемых работ. В этом случае вводится фиктивное событие 2' и фиктивная работа 22'. При этом одна из параллельных работ замыкается на этом событии.

5. В сети рекомендуется иметь одно исходное и одно завершающее событие.

В этом случае вводятся фиктивные события и фиктивные работы.

Фиктивные работы и события необходимо вводить и в ряде других случаев:

- для отражения зависимости событий, не связанных с реальными работами;

Работы А и Б могут выполняться независимо друг от друга, но по условию производства работа Б не может начаться раньше, чем окончится работа А. Вводим фиктивную работу С

- при неполной зависимости работ;

Работа С требует для своего начала завершения работ А и Б, но работа Д связана только с работой Б и не зависит от А, следовательно, требуется выполнение фиктивной работы Ф и фиктивного события 3'.

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

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

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

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

Задания.

1.  Построить сетевой график и найти продолжительность комплекса работ: Сделать деревянный ящик (работу выполняет один человек). Разместить доски в соответствии с размером ящика (15 мин.); разрезать доски (12 мин.); склеить части ящика (40 мин.); прибить к крышке ящика петли (8 мин.); подождать пока ящик высохнет, и вытереть его (15 мин.) петли с крышкой прибить к ящику (10 мин.).

2.  Построить сетевой график и найти продолжительность комплекса работ: Заменить колесо машины (работу выполняют 2 человека). Достать из багажника домкрат и инструменты (40 с); снять диск с колеса (30 с); освободить колесо (50 с ); поставить домкрат под машину (26 с); поднять машину (20 с ); из багажника взять запасное колесо (25 с); снять гайки и колесо (20 с); установить запасное колесо на ось (10 с); завинтит (не сильно) гайки на оси (15 с); опустить машину и собрать домкрат(25 с); поставить домкрат обратно в багажник (10 с); завинтить гайки на оси до конца (12 с); положить плохое колесо и инструменты в багажник (40 с); поставить на место диск колеса (10 с).

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

1.  Исследование операций в экономике / п/р Н. Ш Кремера. – М.: ЮНИТИ, 2000. – 407с.

2.  Акулич программирование в примерах и задачах. – М.: Высшая школа, 1986.

3.  Основы линейного программирования. – М.: Радио и связь, 1989.

4.  Венцель операций. – М.: Сов. радио, 1972.

5.  Венцель операций. Задачи, принципы, методология – М.: Наука, 1980.

6.  , Ушаков операций. – М.: Машиностроение, 1986.

7.  , компьютерные экономико-математические модели. – М.: Компьютер, ЮНИТИ, 1995.

8.  Методы и модели исследования операций. – М.: Мир, 1996.

9.  , , Черемных методы в экономике. – М.: Издательство «Дело и сервис», 2001.

10.  Просветов модели в экономике: Учебно-методическое пособие. - М.: Издательство РДЛ, 2005.

11.  Просветов модели в экономике: Учебно-методическое пособие. 2-е изд. - М.: Издательство РДЛ, 2005.

12.  Малик экономики и математические методы" href="/text/category/instrumentalmznie_i_matematicheskie_metodi/" rel="bookmark">математические методы в планировании. – М. "Высшая школа", 1988

[1] Мы уже сталкивались с этим правилом, при графическом решении задачи линейного программирования