Контрольная работа по «Экономико-математические методы и модели в планировании и управлении»

Министерство связи РФ

Сибирский государственный университет телекоммуникаций и информатики

 

 

 

 

Кафедра Э и Ф

 

 

 

Контрольная работа

по курсу «Экономико-математические методы и модели в планировании и управлении»

Вариант 3

 

 

 

Проверил:

Батый А.Р.

 

Выполнил:

ЦПС, гр. ЭМ-03с

Баева А.В.

 

 

 

 

 

Новосибирск

2005

Задача 1.

Четыре предприятия экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственного равны q1 = 60, q2 = 70, q3 = 120, q4 = 130 ед.. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны Q1 = 140, Q2=160, Q3 = 180 ед.. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок будет минимальной.

 

Решение.

Для решения задачи воспользуемся распределительным методом.

=140 + 160 + 180 = 480 ед.

= 60 + 70 + 120 + 130 = 380 ед.

Задача имеет открытую транспортную модель, так как . Поэтому для решения задачи необходимо перейти с закрытой транспортной модели. Введем условного потребителя q5. Потребность в сырье данного предприятия q5 = 100 ед. (480 – 380 = 100).

Обозначим за xij объем груза, перевозимый от i-го поставщика к j-му потребителю. Тогда получим следующие ограничения:

- ограничения по возможности  поставщиков

- ограничения по спросу потребителей

При этом перевозимый объем продукции не может быть отрицательным, т.е. xij ³ 0.

Линейная форма Z, на минимум которой решается задача, представляет собой сумму парных произведений:

Z = 7×xА1 + 8×xА2 + 1×xА3 + 2×xА4 + 0×xА5+ 4×xВ1 + 5×xВ2 + 9×xВ3 + 8×xВ4 + 0×xВ5 + 9×xС1 + 2×xС2 +  3×xС3 + 6×xС4 + 0×xС5 ® min.

Для решения транспортной задачи используется матрица.

Составим исходный план способом наименьшего элемента в столбце.

	1		2		3		4		5		Qi
А		7		8	120	1	20	2		0	140
В	60	4		5		9		8	100	0	160
С		9	70	2		3	110	6		0	180
qj	60		70		120		130		100		480

 

Необходимые условия для проверки плана на оптимальность следующие:

1. Число занятых мест в плане должно быть на единицу меньше, чем поставщиков и потребителей (m+n-1).
2. Занятые места должны образовывать вычеркиваемую комбинацию.

В данном случае имеет место вырождение, т.е. заполненных мест меньше, чем надо. Заполним одну из пустых клеток нулем. Пусть это будет клетка В4.

 

 

 

	1		2		3		4		5		Qi
А		7		8	120 -	1	20     +	2		0	140
В	60	4		5		9	0	8	100	0	160
С		9	70	2	+	3	110     -	6		0	180
qj	60		70		120		130		100		480

 

Полученный план проверяется на оптимальность с помощью характеристик, рассчитываемых для свободных мест плана. Для определения характеристик строятся замкнутые контуры. Контур состоит из прямых вертикальных и горизонтальных отрезков. Одна вершина контура лежит в свободной клетке, а все остальные вершины – только в занятых местах. Вершине контура, лежащей в свободной клетке, присваивается знак «+», знаки других вершин чередуются (– , + ,  – и т.д.).Значение самой характеристики находится как алгебраическая сумма затрат (cij), стоящих у вершин контуров и взятых с теми знаками, которые присвоены вершинам контура. План будет оптимальный, если все характеристики окажутся положительными. Если же хотя бы одна характеристика будет отрицательной, план необходимо улучшать. Улучшение плана производится до тех пор, пока все характеристики свободных мест не станут положительными. Такой план будет оптимальным.

 Посчитаем характеристики свободных  мест для построенного плана.

А1: +7–4+8–2 = +9

А2: +8–2+6–2 = +10

А5: +0–0+8–2 = +6

В2: +5–2+6–8 = +1

В3: +9–1+2–8 = +2

С1: +9–4+8–6 = +7

С3: +3–1+2–6 = –2

С5: +0–6+8–0 = +2.

Из всех характеристик отрицательное значение имеет клетка С3. Значит, план неоптимальный и его следует улучшать перераспределением поставок.

Для оптимизации плана возьмем клетку С3 как единственную с отрицательной характеристикой. (-2). Так как 2 клетки имеют такое значение, выберем любую из них, например, С3. Объем вводимой поставки в клетку определяется как минимум из поставок, стоящих у отрицательных характеристик.

Min{120,110} = 110

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

Получаем новый план:

	1		2		3		4		5		Qi
А		7		8	10 -	1	130     +	2		0	140
В	60	4	+	5		9	0   -	8	100	0	160
С		9	70    -	2	110     +	3		6		0	180
qj	60		70		120		130		100		480

 

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

А1: +7–4+8–2 = +11

А2: +8–2+3–1 = +8

А5: +0–0+8–2 = +6

В2: +5–2+3–1+2–8 = –1

В3: +9–1+2–8 = +2

С1: +9–4+8–6 = +7

С4: +6–3+1–2 = +2

С5: +0–3+1–2+8–0 = +4

План неоптимальный, его необходимо улучшать.

Min{70,10,0} = 0

Получаем новый план:

	1		2		3		4		5		Qi
А		7		8	10	1	130	2		0	140
В	60	4	0	5		9		8	100	0	160
С		9	70	2	110	3		6		0	180
qj	60		70		120		130		100		480

 

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

А1: +7–4+5–2+3–1 = +8

А2: +8–2+3–1 = +8

А5: +0–0+5–2+3–1 = +5

В3: +9–3+2–5 = +3

В4: +8–2+1–3+2–5 = +1

С1: +9–4+5–2 = +8

С4: +6–3+1–2 = +2

С5: +0–2+5–0 = +3

 

Все характеристики плана получились положительными, значит, этот план оптимальный.

 

Задача 2.

Необходимо оценить работу автоматической телефонной станции (АТС), которая имеет n линий связи. Моменты поступления вызовов на станцию являются случайными и независимыми друг от друга. Средняя плотность потока равна l вызовов в единицу времени. Продолжительность каждого разговора является величиной случайной и подчинена показательному закону распределения. Среднее время одного разговора равно tобс единиц времени.

Исходные данные:

n = 10

l = 2

tобс = 0,5

 

Решение.

Работу автоматической АТС можно отнести к системе с отказами.

Основным показателем работы систем с отказами является вероятность отказа.

Определим нагрузку системы по формуле:

j = l×t,

где t – время обслуживания одного требования;

     l – интенсивность потока.

     j = 2×0,5 = 1 эрл.

Вероятность, что из n линий k будет занято, определяется по формуле:

,                            

Вероятность отказа определяется по формуле:

Среднее число занятых линий определяется по формуле:

Среднее число свободных линий:

Коэффициент простоя и коэффициент занятости определяются по следующим формулам:

;                                   

Все расчеты представлены в таблице 4.

Таблица 4 – Расчет показателей работы автоматической АТС

k		Pk	или (k×Pk)	(n-k)×Pk
1	2	3	4	5
0	1	0,3679	0	3,679
1	1	0,3679	0,3679	3,3111
2	0,5	0,184	0,368	1,472
3	0,1667	0,0613	0,1839	0,4291
4	0,0417	0,0153	0,0612	0,0918
5	0,0083	0,0031	0,0155	0,0155
6	0,0014	0,0005	0,003	0,002
7	0,0002	0,0001	0,0007	0,0003
8	0	0	0	0
9	0	0	0	0
10	0	0	0	0
Итого	2,7183	1,0001	1,0002	9,0008

 

После определения значений графы 2 можно рассчитать P0.

= 0,3679

Параметры граф 3,4 и 5 находятся по вышеприведенным формулам.

Вероятность отказа (последняя цифра графы 3):

(безотказная система)

Среднее число занятых линий (итог графы 4):

Среднее число свободных линий (итог графы 5):

Коэффициент занятости:

= 0,1 = 10%

 

Задача 3.

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

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

Исходные данные приведены в таблице 5:

Таблица 5 – План-прогноз производства промышленного оборудования.

Квартал	Прогноз		Q - емкость склада, шт.	Р - стоимость переналадки линии производственных агрегатов (млн. руб.)	S - себестоимость производства 1 агрегата (млн. руб.)	Н - средние затраты на хранение 1 агрегата (млн. руб.)
	С - дополнительного спроса	М - дополнительной мощности
1	9	10	2	100	30	1
2	5	6	2	90	26	0,6
3	7	6	2	60	28	0,6
4	6	8	2	80	32	0,7

 

Решение.

Разделим процесс планирования на этапы. В данном случае этапом является квартал.

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

Введем следующие обозначения:

xk  - количество агрегатов, которые будут произведены в k-м квартале;

y – остаток нереализованных агрегатов.

Составим функциональное уравнение, которое отражает зависимость затрат на производство от объема выпускаемой продукции:

.

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

Ck – yk-1 £ xk £ M

0 £ yk £ Q.

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

Нереализованных агрегатов не может быть больше, чем емкость склада.

 

Построим динамическую экономико-математическую модель поквартального удовлетворения спроса при минимальных суммарных затратах. Эта модель отражает все возможные варианты по выпуску агрегатов и их хранению в течение всего периода.

 

Для 4 квартала получаем следующие уравнения, решив которые, определяем значение х в точке минимума:

= 272 д.е. =>  x4 = 6

= 240 д.е. =>  x4 = 5

= 208 д.е. => x4 = 4

 

Для 3 квартала (с учетом результата за 4 квартал) получаем:

 не имеет решения (т.к. С >M).

= 500 д.е. =>  x3 = 6

= 468,6 д.е. =>  x3 = 6

 

Для 2 квартала (с учетом результата за 3 и 4 кварталы) получаем:

= 746,6 д.е. =>  x2 = 6

= 715,8 д.е. =>  x2 = 6

= 689,8 д.е. =>  x2 = 5

 

Для 1 квартала (с учетом результата за 2, 3 и 4 кварталы) получаем:

= 1116,6 д.е. =>  x1 = 9

= 1086,6 д.е. =>  x1 = 8

= 1056,6 д.е. =>  x1 = 7

По динамической экономико-математической модели можно определить оптимальную стратегию производства и хранения агрегатов. Она определяется непрерывной жирной линией.

Существует 3 варианта плана производства:

1. Если на складе остаток нереализованных агрегатов равен нулю, то в 1 квартале необходимо произвести 9 единиц продукции, во втором квартале – 6, в 3 квартале  – 6 и в 4 квартале – 6.
2. Если остаток на складе равен 1, то в 1 квартале необходимо произвести 8 агрегатов, в остальных кварталах – как в 1 варианте
3. Если остаток на складе равен 2, то в 1 квартале необходимо произвести 7 агрегатов, в остальных кварталах – как в предыдущем варианте.

 

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

F = 1056,6 д.е

 

Задача 4.

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

 

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

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

 

Исходные данные:

Работы	дни	Число исполнителей работ по вариантам
1-2	2	5
1-5	8	9
1-3	2	20
1-4	3	5
2-6	3	8
3-5	2	12
4-6	7	5
5-6	4	11
Всего		22

 

Решение.

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

К таким параметрам относятся:

• tij – продолжительность данной работы
• , - возможные ранние сроки начала и окончания данной работы;
• , - допустимые поздние сроки начала и окончания данной работы;
• TКР – длина критического пути
• rij – частный резерв времени данной работы;
• Rij – общий полный резерв времени данной работы;

 

Для расчета параметров графика воспользуемся табличным способом.

Колонки 1, 2 и 3 заполняются согласно исходным данным (см. рисунок).

Затем рассчитываются значения колонок 4 и 5, то есть ранние сроки начала и окончания работ.

Раннее начало работ, выходящих из начального события, равны нулю.

Раннее возможное окончание работы определяется по формуле:

.

Если данной работе предшествует только одна работа, то раннее начало данной работы равно раннему окончанию предшествующей работы:

.

Если данной работе предшествуют несколько работ, то ее раннее начало равно максимальному значению из всех ранних окончаний предшествующих работ:

.

После заполнения колонок 4 и 5 определяется длина критического пути TКР. Она равна максимальному из ранних окончаний завершающий работ.

= 12 дней.

Далее определяются поздние сроки начала и окончания работ (колонки 6 и 7).

Позднее окончание работ, входящих в конечное событие, равно ТКР.

Допустимое позднее начало работы определяется по формуле:

.

Если у данной работы последующих работ одна, ее позднее окончание равно позднему началу последующей работы:

.

Если за данной работой следуют 2 и более работ, то ее позднее окончание будет равно минимальному значению из всех поздних начал последующих работ:

Далее определяются полный и частный резервы времени (колонки 8 и 9).

Пути, у которых поздние начала совпадают с ранними, называют критическими. Они не располагают резервами времени. Эти работы лежат на критическом пути.

Работы, не лежащие на критическом пути, располагают определенными запасами времени на их выполнение.

Полный резерв определяется по формуле:

   или   .

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

Частный резерв определяется по формуле:

.

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

 

Результаты расчетов представлены в таблице:

Кол-во предш.	Работы	tij	РНij	РОij	ПНij	ПОij	rij	Rij
0	1-2	2	0	2	7	9	0	7
	1-5	8	0	8	0	8	0	0
	1-3	2	0	2	4	6	0	4
	1-4	3	0	3	2	5	0	2
1	2-6	3	2	5	9	12	7	7
1	3-5	2	2	4	6	8	4	4
1	4-6	7	3	10	5	12	2	2
2	5-6	4	8	12	8	12	0	0

 

Работы 1-5 и 5-6 образуют критический путь.

 

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

Построим диаграмму сетевого графика на основании произведенных ранее расчетов.

Дни	1	2	3	4	5	6	7	8	9	10	11	12	Итого
Работы
1-2	5	5											10
1-5	9	9	9	9	9	9	9	9					72
1-3	20	20											40
1-4	5	5	5										15
2-6			8	8	8								24
3-5			12	12									24
4-6				5	5	5	5	5	5	5			35
5-6									11	11	11	11	44
Итого	39	39	34	34	22	14	14	14	16	16	11	11	264