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

 

Задача 2

1. Построить  сетевой график (длина работы - t_ij )

2. Выделить  критический путь и найти его  длину.

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

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

5. Выполнить  оптимизацию сетевого графика  по времени.

Работы	tij	dij	kij
1,2	9	6	0.6
1,3	8	3	0.1
1,4	14	12	0.3
2,3	16	2	0.8
2,5	5	2	0.9
3,5	12	7	0.5
4,6	4	2	0.3
5,6	10	7	0.4
	В=165

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

Решение

Построим сетевой график

  9,6            16,2       5, 2

         8,3

                                              12,7                   10, 7                      0

           14,12                                 4,2

                           

Характеристики событий 

1. Ранний срок свершения события

t_p(0) = 0,

t_p(j) = max_i {t_p(i) + t(ij)},  j = 1¸N

2. Поздний срок свершения события

t_п(N) = t_p(N),

t_п(i) = min_j {t_п(j) - t(ij)},  i = 1¸N-1

3. Резерв времени события

R(i) = t_п(i) - t_p(i)

i	tp(i)	tп(i)	R(i)
1	0	0	0
2	9	9	0
3	25	25	0
4	14	43	29
5	37	37	0
6	47	47	0

 

Анализ  таблицы и сетевого графика показывает, что существует критический путь (1-2-3-5-6) длины t_кр=47.

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

Характеристики работы (i,j)

1. Ранний срок начала работ t_pн(i,j)=t_p(i).                                                                             

2. Ранний срок окончания работы t_po(i,j)= t_pн(i,j) + t_ij =t_p(i) + t_ij                                                             

3. Поздний срок начала работы: t_пн(i,j)=t_п(j) – t_ij.                                                                 

4. Поздний срок окончания работы: t_по(i,j) = t_п(j).                                                                

5. Резервы времени работ:

• полный резерв R_п(i,j) = t_п(j) - t_p(i) - t_ij.                                                                              
• частный резерв  R₁(i,j) = R_п(i,j) - R(i)   =  t_п(j) – t_п(i) - t_ij.                                              
• свободный резерв R_с(i,j) = R_п(i,j) - R(j)   =  t_p(j) – t_p(i) - t_ij.                                            
• независимый резерв R_н(i,j) = R_п(i,j) - R(i) – R(j)   =  t_p(j) – t_п(i) - t_ij.                              

Коэффициент напряженности работ:

К_н(i,j) = ( t(L_max)-t`_кр ) / (t_кр-t^'_кр) = 1 – R_п(i,j) / (t_кр-t^'_кр),

где t(L_max(i,j)) – продолжительность максимального пути L_max(i,j), проходящего через работу (i,j); t^'_кр – продолжительность отрезка пути L_max(i,j), совпадающего с критическим путем.

 

работы	tij	tрн(ij)	tр0(ij)	tпн	tп0=tп(j)	Rп	R1	Rc	Rн	Кн
1,2	9	0	9	0	9	0	0	0	0	-
1,3	8	0	8	17	25	17	17	17	17	0,32
1,4	14	0	14	29	43	29	29	0	0	0,383
2,3	16	9	25	9	25	0	0	0	0	-
2,5	5	9	14	32	37	23	23	23	23	0,179
3,5	12	25	37	25	37	0	0	0	0	-
4,6	4	14	18	43	47	29	0	29	0	0,383
5,6	10	37	47	37	47	0	0	0	0	-
6,7	0	47	47	47	47	0	0	0	0	-

Анализ  таблицы и сетевого графика показывает, что критический путь имеет вид (1-2-3-5-6) длины t_кр=47.

Продолжительность выполнения работ линейно зависит  от дополнительно вложенных средств и выражается соотношением

_.

_{Требуется оптимизировать общее время выполнения работ, чтобы сумма дополнительно вложенных средств не превысила 165.}

Тогда целевая  функция запишется в виде

.

Запишем ограничения задачи:

а) ,

б) продолжительность  выполнения каждой работы должна быть не меньше минимально возможного времени:

, , , ,

, ,

  , .

в) зависимость  продолжительности работ от вложенных  средств:

, , ,

   , ,

, .

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

, , , , , ,

, , .

д) условие неотрицательности неизвестных:

, .

Решим задачу, выполнив Поиск решения с помощью  Excel. Имеющуюся информацию вводим в ячейки следующим образом.

В ячейки C6:Y30 внесены исходные данные в соответствии с условием задачи:

В ячейках C4:Y4 будут представлены рассчитанные значения неизвестных:

a) в ячейках R4:Y4 – суммы средств, вкладываемых в каждую работу;

b) в ячейках C4:Q4 – время начала и окончания работ.

В ячейку Z33 внесена формула для вычисления целевой функции СУММПРОИЗВ($C$4:$Y$4;C33:Y33). Значение функции равно времени начала фиктивной работы (6-7), поэтому в ячейку P33 внесено значение 1.

В столбце  Z5:Z32 размещены заданные по условию значения ограничений, а в столбце AA5:AA32 показаны их знаки. Соответственно, в столбец AB5:AB32 внесены формулы для расчета реальных значений ограничений:

в ячейку Z5: СУММПРОИЗВ($C$4:$Y$4;C5:Y5);

…………………………………………………………

В ячейку Z32: СУММПРОИЗВ($C$4:$Y$4;C32:Y32);

Ограничения задачи для удобства разобьем по блокам:

1 блок. Сумма вложенных во все работы средств не должна превышать наличного их количества (140).

2 блок. Время выполнения каждой операции должно быть не меньше минимально возможного времени :

3 блок. На основании данной формулы продолжительность операции зависит от вложенных средств как ограничение-равенство .

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

 

Теперь  в терминах рабочего листа Excel задача может быть сформулирована следующим образом: добиться минимально возможного значения в ячейке Z33, изменяя значения ячеек C4:Y4 при условии выполнения ограничений в ячейках Z5:AB32 и неотрицательности значений в ячейках C4:V4.

Для решения  задачи используем программное средство Поиск решения табличного процессора Excel.

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

Таким образом, общая сумма дополнительно вложенных  денежных средств составляет 40 ден.ед., при этом в работу (1,2) следует вложить 5 ден.ед., что сократит ее продолжительность на 5·0,6 = 3 ед., новая длительность 5, в работу (2,3) следует вложить 17,5 ден.ед., что сократит ее продолжительность на 17,5·0,8 = 14 ед., новая длительность 2, в работу (3,5) следует вложить 10 ден.ед., что сократит ее продолжительность на 10·0,5 = 5 ед., новая длительность 7, в работу (5,6) следует вложить 7,5 ден.ед., что сократит ее продолжительность на 7,5·0,4 = 3 ед., новая длительность 7.

Новый критический  путь составляют работы (1-2-3-5-6), причем длительности всех работ, находящихся на критическом пути, равны минимально возможным значениям, длина критического пути равна 22.

Заметим, что теперь путь (1-3-5-6) также является критическим.

 

 

Задача 3

Для изготовления четырех видов  продукции используются три вида сырья.

Ресурсы	Запас ресурсов, ед.	Нормы расхода сырья на единицу  продукции
		А	Б	В	Г
I	40	1	1	1	1
II	250	6	5	4	3
III	180	4	6	10	13
Прибыль от реализации единицы продукции, ден.ед.		60	70	120	130

 Необходимо:

1. Записать прямую задачу. Определить план выпуска продукции, при котором прибыль от ее реализации  будет.
2. Записать двойственную задачу. Получить решение двойственной задачи. Пояснить экономический смысл полученных объективно обусловленных (теневых) оценок ресурсов.
3. Найти интервалы устойчивости двойственных оценок по отношению к изменению запаса ресурсов каждого вида.
4. Определить изменение максимальной прибыли от реализации продукции при увеличении запаса ресурса I на 10 ед., ресурса II – на 50 ед. и уменьшении запаса ресурса III на 30 ед. Оценить раздельное влияние этих изменений и суммарное влияние.
5. Сопоставить оценку затрат и прибыли по оптимальному плану и каждому виду продукции.

Решение

Запишем экономико-математическую модель задачи

,

,

Здесь переменные обозначают объемы производства соответствующих видов продукции, Z – выручка от реализации продукции при заданных ценах (60, 70, 120, 130) и заданных ограничениях по сырью (40, 250, 180).

Решение задачи будем осуществлять при помощи пакета Excel с помощью функции Поиск решения.

Создадим  в Excel следующую таблицу:

 

	Переменные						Запас
	Х1	Х2	Х3	Х4	Расчет.	Вид
Ресурс					значен.	огран.	сырья
Прибыль	60	70	120	130		max
I	1	1	1	1		≤	40
II	6	5	4	3		≤	250
III	4	6	10	13		≤	180

 

Присвоим  блоку переменных уникальное имя  Переменные, введем формулы для вычисления значений прибыли и используемых ресурсов с использованием функции СУММПРОИЗВ, умножая и складывая диапазон Переменные с коэффициентами, находящимися в соответствующих строках.

Решим задачу оптимизации. Выберем команду Поиск  решения. В поле Установить целевую ячейку выделим ячейку со значением целевой функции модели и выберем максимизировать значение. В поле Изменяя ячейки выделим блок Переменные, в поле Ограничения введем ограничения, накладываемые на решение задачи. В окне Параметры поиска решения установим флажки Линейная модель и Неотрицательные значения. Выполним решение задачи, зададим тип отчета Результаты и Устойчивость.

 

Запишем первоначальную и все промежуточные симплексные таблицы:

 

 

Базис	С	b	х1	х2	х3	х4	х5	х6	х7	Θ
			60	70	120	130	0	0	0
х5	0	40	1	1	1	1	1	0	0	40
х6	0	250	6	5	4	3	0	1	0	83,33
х7	0	180	4	6	10	13	0	0	1	13,846
		0	-60	-70	-120	-130	0	0	0
Базис	С	b	х1	х2	х3	х4	х5	х6	х7	Θ
			60	70	120	130	0	0	0
х5	0	26,154	0,6923	0,5385	0,2308	0	1	0	-0,077	37,778
х6	0	208,46	5,076923	3,6154	1,6923	0	0	1	-0,231	41,06
х4	130	13,846	0,3076923	0,4615	0,7692	1	0	0	0,0769	45
		1800	-20	-10	-20	0	0	0	10
Базис	С	b	х1	х2	х3	х4	х5	х6	х7	Θ
			60	70	120	130	0	0	0
х1	60	37,778	1	0,7778	0,3333	0	1,4444	0	-0,111	113,33
х6	0	16,667	0	-0,333	0	0	-7,333	1	0,3333	-
х4	130	2,2222	0	0,2222	0,667	1	-0,444	0	0,1111	3,3333
		2555,56	0	5,5556	-13,33	0	28,889	0	7,7778
Базис	С	B	х1	х2	х3	х4	х5	х6	х7	Θ
			60	70	120	130	0	0	0
х1	60	36,667	1	0,6667	0	-0,5	1,6667	0	-0,167
х6	0	16,667	0	-0,333	0	0	-7,333	1	0,3333
х3	120	3,3333	0	0,3333	1	1,5	-0,667	0	0,1667
		2600	0	10	0	20	20	0	10