Задачи 1, 2, 7, 8. Строим экономико-математическую модель

  • ID: 00102 
  • 24 страницы

Фрагмент работы:

Задачи 1, 2, 7, 8. Строим экономико-математическую модель

№1.

1. Строим экономико-математическую модель.

Введем обозначения:

xij – размер депозита, оформляемого в месяц под номером j на срок i, т.е.:

x11 – одномесячный депозит, оформленный в первом месяце

x21 – двухмесячный депозит, оформленный в первом месяце

x31 – трехмесячный депозит, оформленный в первом месяце

x12 – одномесячный депозит, оформленный во втором месяце

x13 – одномесячный депозит, оформленный в третьем месяце

Составим балансовые уравнения:

…=…

…=…

…=…

Нормализуем балансовые уравнения

…=…

…=…

…=…

Критерий эффективности Z равен:

…=…

Для подготовки к построению симплекс-таблицы:

Составим двойственную задачу:

u1-1,01u20,01

u2-1,01u30,01

u30,01

u1-1,025u30,025

u10,035

…=…

Введем дополнительные балансовые переменные

…=…

…=…

…=…

Введем балансовые переменные для двойственной задачи

…=…

…=…

…=…

…=…

…=…

2. Находим решение, используя алгоритм симплекс-метода

v11=

-x11 v12=

-x12 v13=

-x13 v21=

-x21 v31=

-x31 W=

1

…=…

…=…

…=…

…=…

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

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

v11=

-x11 v12=

-x12 v13=

-x13 v21=

-x21 u1=

0 W=

1

…=…

…=…

…=…

…=…

На следующем шаге возьмем в качестве разрешающей вторую строку, а в качестве разрешаю-щего столбца – также второй.

v11=

-x11 u2=

0 v13=

-x13 v21=

-x21 W=

1

…=…

…=…

…=…

…=…

На третьем шаге возьмем в качестве разрешающей строки третью, а в качестве разрешающего столбца – второй

v11=

-x11 u3=

0 v21=

-x21 W=

1

…=…

…=…

…=…

…=…

Исключив после преобразований второй столбец, получим следующую симплекс-таблицу:

v11=

-x11 v21=

-x21 W=

1

…=…

…=…

…=…

…=…

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

max={0,004699/-1,01}=-0,00465, поэтому в качестве разрешающего берем первый столбец.

v12=

-x12 v21=

-x21 W=

1

…=…

…=…

…=…

…=…

Найдено допустимое решение. Т.к. в Z-строке есть отрицательные элементы, то решение не яв-ляется оптимальным. Разрешающий столбец второй. Т.к. min{40/1}=40, то разрешающая строка первая. Составляем новую симплекс-таблицу.

v12=

-x12 v31=

-x31 W=

1

…=…

…=…

…=…

…=…

Т.к. все коэффициенты Z-строки и столбца свободных членов положительны, получено опти-мальное решение:

…=…

…=…

…=…

…=…

…=…

№2.

1. Составим экономико-математическую модель

Пусть xij – объем перевозок от i-го филиала до j-го пункта, а…, тогда

x11+x12135y1

x21+x2280y2

x31+x32130y3

x41+x4240y4

x11+x21+x31+x41180

x12+x22+x32+x4270

xij0

S0=13513y1+8017y2+13019y3+405y4 (производственные затраты)

S1=6x11+16x12+2x21+12x22+3x31+10x32+5x41+11x42= (транспортные затраты)

S=S0+S1min (суммарные затраты)

2. Рассмотрим различные варианты строительства, чтобы суммарная мощность построенных филиалов была не меньше потребностей.

…=…

…=…

…=…

…=…

…=…

…=…

1.…=…

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

…=…

Получаем транспортную задачу

Филиалы Потребитель

180 70 135

135 6 16 0

80 2 12 0

130 3 10 0

40 5 11 0

Заполним матрицу перевозок методом северо-западного угла

Филиалы Потребитель

180 70 135

135 6 135 16 0

80 2 45 12 35 0

130 3 10 35 0 95

40 5 11 0 40

Проверим план на оптимальность. Составим систему уравнений для нахождения условно-поясных единиц:

v1-u1=6

v1-u2=2

v2-u2=12

v2-u3=10

v3-u3=0

v3-u4=0

Пусть u1=10, тогда u2=14; u3=16; u4=16; v1=16; v2=26; v3=16

Находим невязки для пустых клеток:

…=…

Клетка с максимальной невязкой – клетка (1;3). Строим к ней цикл и переходим к следующей матрице перевозок

Филиалы Потребитель

180 70 135

135 6 100 16 0 35

80 2 80 12 0

130 3 10 70 0 60

40 5 11 0 40

Находим условно-поясные единицы.

…=…

Находим невязки для пустых клеток:

20- 10- 16< 0 20- 14- 12< 0 10- 14- 0< 0 16- 10- 3> 0 16- 10- 5> 0 20- 10- 11< 0

Клетка с максимальной невязкой – клетка (3;1). Строим к ней цикл и переходим к следующей матрице перевозок

Филиалы Потребитель

180 70 135

135 6 40 16 0 95

80 2 80 12 0

130 3 60 10 70 0

40 5 11 0 40

Находим условно-поясные единицы.

…=…

Находим невязки для пустых клеток:

23- 10- 16< 0 23- 14- 12< 0 10- 14- 0< 0 10- 13- 0< 0 16- 10- 5> 0 23- 10- 11> 0

Клетка с максимальной невязкой – клетка (4;2). Строим к ней цикл и переходим к следующей матрице перевозок

Филиалы Потребитель

180 70 135

135 6 0 16 0 135

80 2 80 12 0

130 3 100 10 30 0

40 5 11 40 0

Находим условно-поясные единицы.

…=…

Находим невязки для пустых клеток:

23- 10- 16< 0 23- 14- 12< 0 10- 14- 0< 0 10- 13- 0< 0 16- 12- 5< 0 10- 12- 0< 0

План получился оптимальный.

X(1)*= 0 0

80 0

100 30

0 40

Стоимость перевозок при таком плане минимальна и равна:

…=…

2.…=…

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

345-250=95

Получаем транспортную задачу

Филиалы Потребитель

180 70 95

135 6 16 0

80 2 12 0

130 3 10 0

Заполним матрицу перевозок методом северо-западного угла

Филиалы Потребитель

180 70 95

135 6 135 16 0

80 2 45 12 35 0

130 3 10 35 0 95

Проверим план на оптимальность. Составим систему уравнений для нахождения условно-поясных единиц:

v1-u1=6

v1-u2=2

v2-u2=12

v2-u3=10

v3-u3=0

Пусть u1=10, тогда u2=10; u3=16; v1=16; v2=26; v3=16

Находим невязки для пустых клеток:

…=…

Клетка с максимальной невязкой – клетка (1;3). Строим к ней цикл и переходим к следующей матрице перевозок

Филиалы Потребитель

180 70 95

135 6 100 16 0 35

80 2 80 12 0

130 3 10 70 0 60

Находим условно-поясные единицы.

…=…

Находим невязки для пустых клеток:

20- 10- 16< 0 20- 14- 12< 0 10- 14- 0< 0 16- 10- 3> 0

Клетка с максимальной невязкой – клетка (3;1). Строим к ней цикл и переходим к следующей матрице перевозок

Филиалы Потребитель

180 70 95

135 6 40 16 0 95

80 2 80 12 0

130 3 60 10 70 0

Находим условно-поясные единицы.

…=…

Находим невязки для пустых клеток:

23- 10- 16< 0 23- 14- 12< 0 10- 14- 0< 0 10- 13- 0< 0

План получился оптимальный.

…=…

80 0

60 70

0 0

Стоимость перевозок при таком плане минимальна и равна:

…=…

3.…=…

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

255-250=5

Получаем транспортную задачу

Филиалы Потребитель

180 70 5

135 6 16 0

80 2 12 0

40 5 11 0

Заполним матрицу перевозок методом северо-западного угла

Филиалы Потребитель

180 70 5

135 6 135 16 0

80 2 45 12 35 0

40 5 11 35 0 5

Проверим план на оптимальность. Составим систему уравнений для нахождения условно-поясных единиц:

v1-u1=6

v1-u2=2

v2-u2=12

v2-u3=11

v3-u3=0

Пусть u1=10, тогда u2=14; u3=15; v1=16; v2=26; v3=15

Находим невязки для пустых клеток:

…=…

Клетка с максимальной невязкой – клетка (1;3). Строим к ней цикл и переходим к следующей матрице перевозок

Филиалы Потребитель

180 70 5

135 6 130 16 0 5

80 2 50 12 30 0

40 5 11 40 0

Находим условно-поясные единицы.

…=…

Находим невязки для пустых клеток:

…=…

План получился оптимальный.

…=…

50 30

0 0

0 40

Стоимость перевозок при таком плане минимальна и равна:

…=…

4.…=…

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

305-250=55

Получаем транспортную задачу

Филиалы Потребитель

180 70 55

135 6 16 0

130 3 10 0

40 5 11 0

Заполним матрицу перевозок методом северо-западного угла

Филиалы Потребитель

180 70 55

135 6 135 16 0

130 3 45 10 70 0 15

40 5 11 0 40

Проверим план на оптимальность. Составим систему уравнений для нахождения условно-поясных единиц:

v1-u1=6

v1-u2=3

v2-u2=10

v3-u2=0

v3-u3=0

Пусть u1=10, тогда u2=13; u3=13; v1=16; v2=23; v3=13

Находим невязки для пустых клеток:

23- 10- 16< 0 13- 10- 0> 0 16- 13- 5< 0 23- 13- 11< 0

Клетка с максимальной невязкой – клетка (1;3). Строим к ней цикл и переходим к следующей матрице перевозок

Филиалы Потребитель

180 70 55

135 6 120 16 0 15

130 3 60 10 70 0

40 5 11 0 40

Находим условно-поясные единицы.

…=…

Находим невязки для пустых клеток:

23- 10- 16< 0 10- 13- 0< 0 16- 10- 5> 0 23- 10- 11> 0

Клетка с максимальной невязкой – клетка (3;2). Строим к ней цикл и переходим к следующей матрице перевозок

Филиалы Потребитель

180 70 55

135 6 80 16 0 55

130 3 100 10 30 0

40 5 11 40 0

Находим условно-поясные единицы.

…=…

Находим невязки для пустых клеток:

23- 10- 16< 0 10- 13- 0< 0 16- 12- 5< 0 10- 12- 0< 0

План получился оптимальный.

…=…

0 0

100 30

0 40

Стоимость перевозок при таком плане минимальна и равна:

…=…

5.…=…

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

265-250=15

Получаем транспортную задачу

Филиалы Потребитель

180 70 15

135 6 16 0

130 3 10 0

Заполним матрицу перевозок методом северо-западного угла

Филиалы Потребитель

180 70 15

135 6 135 16 0

130 3 45 10 70 0 15

Проверим план на оптимальность. Составим систему уравнений для нахождения условно-поясных единиц:

v1-u1=6

v1-u2=3

v2-u2=10

v3-u2=0

Пусть u1=10, тогда u2=13; v1=16; v2=23; v3=13

Находим невязки для пустых клеток:

23- 10- 16< 0 13- 10- 0> 0

Клетка с максимальной невязкой – клетка (1;3). Строим к ней цикл и переходим к следующей матрице перевозок

Филиалы Потребитель

180 70 15

135 6 120 16 0 15

130 3 60 10 70 0

Находим условно-поясные единицы.

…=…

Находим невязки для пустых клеток:

23- 10- 16< 0 10- 13- 0< 0

План получился оптимальный.

…=…

0 0

60 70

0 0

Стоимость перевозок при таком плане минимальна и равна:

…=…

6.…=…

В данном случае условие баланса выполнено

Филиалы Потребитель

180 70

80 2 12

130 3 10

40 5 11

Заполним матрицу перевозок методом северо-западного угла

Филиалы Потребитель

180 70

80 2 80 12

130 3 100 10 30

40 5 11 40

Проверим план на оптимальность. Составим систему уравнений для нахождения условно-поясных единиц:

v1-u1=2

v1-u2=3

v2-u2=10

v2-u3=11

Пусть u1=10, тогда u2=9; u3=8; v1=12; v2=19

Находим невязки для пустых клеток:

19- 10- 12< 0 12- 8- 5< 0

План получился оптимальный.

X(6)*= 0 0

80 0

100 30

0 40

Стоимость перевозок при таком плане минимальна и равна:

…=…

Сравнивая полученные затраты, приходим к выводу об оптимальности третьего варианта раз-мещения филиалов, а именно:

…=…

…=…

50 30

0 0

0 40

…=…

№3.

Запишем данные задачи в виде таблицы:

A B

Цена реализации 76,9 262,3 Минимум В наличии

Сырье 4 5 3000 4500

Оборудование 5 5 1750 3500

Себестоимость 45 250

З/плата 27500

1. Строим экономико-математическую модель задачи. Пусть x1 и x2 – количество изделий А и В соответственно. Составим систему ограничений:

30004x1+5x24500 – по сырью

17505x1+5x23500 – по оборудованию

x10, x20

Выручка: Z1=76,9x1+262,3x2

Затраты: Z2=45x1+250x2+27500

Доход: Z1–Z2=31,9x1+12,3x2-27500

Критерий эффективности – рентабельность:

Получили задачу дробно-линейного программирования. Запишем условия построенной модели в стандартной форме записи:

x10, x20

4x1+5x24500

-4x1-5x2-3000

5x1+5x23500

-5x1-5x2-1750

Решим задачу симплекс-методом. Введем балансовые переменные:

…=…

…=…

…=…

…=…

Составим симплекс-таблицу:

-x1 -x2 1

y1 4 5 4500

y2 -4 -5 -3000

y3 5 5 3500

y4 -5 -5 -1750

Z1-Z2 -31,9 -12,3 -27500

Z2 -45 -250 27500

Ищем допустимое решение

Разрешающий столбец второй. Т.к. min{4500/5;-3000/-5;3500/5;-1750/-5}=350, то разрешающая строка четвертая. Переходим к следующей симплекс-таблице

-x1 -y4 1

y1 -1 1 2750

y2 1 -1 -1250

y3 0 1 1750

x2 1 -0,2 350

Z1-Z2 -19,6 -2,46 -23195

Z2 205 -50 115000

Разрешающий столбец второй. Т.к. min{2750/1;-1250/-1;1750/1}=1250, то разрешающая строка вторая. Переходим к следующей симплекс-таблице

-x1 -y2 1

y1 0 1 1500

y4 -1 -1 1250

y3 1 1 500

x2 0,8 -0,2 600

Z1-Z2 -22,06 -2,46 -20120

Z2 155 -50 177500

Получилось допустимое решение.

Обобщающим критерием оптимальности является неотрицательность определителей j≥0

…=…

155 177500

…=…

177500 -50

Условие неоптимальности не выполняется для обоих определителей, поэтому можно брать в качестве разрешающего любой столбец. Выберем разрешающим второй столбец. Минимальное симплексное отношение: min{1500/1;500/1}=500. Разрешающая строка - третья. Перейдем к но-вой симплекс-таблице:

-x1 -y3 1

y1 -1 -1 1000

y4 0 1 1750

y2 1 1 500

x2 1 0,2 700

Z1-Z2 -19,6 2,46 -18890

Z2 205 50 202500

…=…

205 202500

…=…

202500 50

Условие неоптимальности не выполняется для 1, поэтому разрешающий столбец берем пер-вый. Минимальное симплексное отношение: min{500/1;700/1}=500,  разрешающая строка третья. Перейдем к новой симплекс-таблице:

-y2 -y3 1

y1 1 0 1500

y4 0 1 1750

x1 1 1 500

x2 -1 -0,8 200

Z1-Z2 19,6 22,06 -9090

Z2 -205 -155 100000

…=…

-205 100000

…=…

100000 -155

…=…

№5.

Запишем данные задачи в виде таблицы:

A B В наличии

Площадь 2 2 15

Затраты 3 4 23

Производительность 12 15

1. Составим экономико-математическую модель задачи. Пусть x1 и x2 – количество станков А и В соответственно. Составим систему ограничений:

2x1+2x215

3x1+4x223

x10, x20, x1, x2 – целые

Критерий эффективности: Z=12x1+15x2max

Снимаем ограничение целочисленности и находим решение этой задачи (0)

…=…

…=…

x10, x20

Решим задачу симплекс-методом.

Составим симплекс-таблицу:

-x1 -x2 1

y1 2 2 15

y2 3 4 23

Z -12 -15 0

Разрешающий столбец второй. Т.к. min{15/2;23/4}=5,75, то разрешающая строка вторая. Со-ставляем новую симплекс-таблицу

-x1 -y2 1

y1 0,5 -0,5 3,5

x2 0,75 0,25 5,75

Z -0,75 3,75 86,25

Разрешающий столбец первый. Т.к. min{3,5/0,5;5,75/0,75}=7, то разрешающая строка первая. Составляем новую симплекс-таблицу

-y1 -y2 1

x1 2 -1 7

x2 -1,5 1 0,5

Z 1,5 3 91,5

Найдено оптимальное решение. Т.к. это решение не является целочисленным, то вводим допол-нительные ограничения: либо x20 (задача 1.1), либо x21 (задача (1.2)

Задача 1.1.

2x1+2x215

3x1+4x223

x20

x10, x20, x1, x2 – целые

…=…

-x1 -x2 1

y1 2 2 15

y2 3 4 23

y3 0 1 0

Z -12 -15 0

Разрешающий столбец 2, разрешающая строка 3

-x1 -y3 1

y1 2 -2 15

y2 3 -4 23

x2 0 1 0

Z -12 15 0

Разрешающий столбец 1, разрешающая строка 1

-y1 -y3 1

x1 0,5 -1 7,5

y2 -1,5 -1 0,5

x2 0 1 0

Z 6 3 90

Оптимальное решение задачи 1.1: X*1.1=(7,5;0), Z*1.1=90

Задача 1.2.

2x1+2x215

3x1+4x223

x2≥1

x10, x20, x1, x2 – целые

…=…

-x1 -x2 1

y1 2 2 15

y2 3 4 23

y3 0 -1 -1

Z -12 -15 0

Разрешающий столбец 2, разрешающая строка 3

-x1 -y3 1

y1 2 2 13

y2 3 4 19

x2 0 -1 1

Z -12 -15 15

Разрешающий столбец 2, разрешающая строка 2

-x1 -y2 1

y1 0,5 -0,5 3,5

y3 0,75 0,25 4,75

x2 0,75 0,25 5,75

Z -0,75 3,75 86,25

Разрешающий столбец 1, разрешающая строка 2

-y3 -y2 1

y1 - 2/3 - 2/3 1/3

x1 1 1/3 1/3 6 1/3

x2 -1 0 1

Z 1 4 91

Оптимальное решение задачи 1.2: X*1.2=(6 1/3;1), Z*1.2=91

Т.к. Z1.2>Z1.1 и решение задачи 1.2 не является целочисленным, то в задачу 1.2 вводим дополни-тельные ограничения: либо x16 (задача 2.1), либо x17 (задача (2.2)

Задача 2.1.

2x1+2x215

3x1+4x223

x2≥1

x1≤6

x10, x20, x1, x2 – целые

…=…

-x1 -x2 1

y1 2 2 15

y2 3 4 23

y3 0 -1 -1

y4 1 0 6

Z -12 -15 0

Разрешающий столбец 2, разрешающая строка 3

-x1 -y3 1

y1 2 2 13

y2 3 4 19

x2 0 -1 1

y4 1 0 6

Z -12 -15 15

Разрешающий столбец 2, разрешающая строка 2

-x1 -y2 1

y1 0,5 -0,5 3,5

y3 0,75 0,25 4,75

x2 0,75 0,25 5,75

y4 1 0 6

Z -0,75 3,75 86,25

Разрешающий столбец 1, разрешающая строка 4

-y4 -y2 1

y1 -0,5 -0,5 0,5

y3 -0,75 0,25 0,25

x2 -0,75 0,25 1,25

x1 1 0 6

Z 0,75 3,75 90,75

Оптимальное решение задачи 2.1: X*2.1=(6;1,25), Z*2.1=90,75

Задача 2.2.

2x1+2x215

3x1+4x223

x2≥1

x1≥7

x10, x20, x1, x2 – целые

…=…

-x1 -x2 1

y1 2 2 15

y2 3 4 23

y3 0 -1 -1

y4 -1 0 -7

Z -12 -15 0

Разрешающий столбец 1, разрешающая строка 4

-y4 -x2 1

y1 2 2 1

y2 3 4 2

y3 0 -1 -1

x1 -1 0 7

Z -12 -15 84

Разрешающий столбец 2, разрешающая строка 1

-y4 -y1

x2 1 0,5 0,5

y2 -1 -2 0

y3 1 0,5 -0,5

x1 -1 0 7

Z 3 7,5 91,5

Система несовместна. Задача 2.2 не имеет решений.

Т.к. Z2.1>Z1.1 и решение задачи 2.1 не является целочисленным, то в задачу 2.1 вводим дополни-тельные ограничения: либо x21 (задача 3.1), либо x22 (задача (3.2)

Задача 3.1.

2x1+2x215

3x1+4x223

x2≤1

x1≤6

x10, x20, x1, x2 – целые

…=…

-x1 -x2

y1 2 2 15

y2 3 4 23

y3 0 1 1

y4 1 0 6

Z -12 -15 0

Разрешающий столбец 2, разрешающая строка 3

-x1 -y3

y1 2 -2 13

y2 3 -4 19

x2 0 1 1

y4 1 0 6

Z -12 15 15

Разрешающий столбец 1, разрешающая строка 4

-y4 -y3

y1 -2 -2 1

y2 -3 -4 1

x2 0 1 1

x1 1 0 6

Z 12 15 87

Оптимальное решение задачи 3.1: X*3.1=(6;1), Z*3.1=87

Задача 3.2.

2x1+2x215

3x1+4x223

x2≥2

x1≤6

x10, x20, x1, x2 – целые

…=…

-x1 -x2

y1 2 2 15

y2 3 4 23

y3 0 -1 -2

y4 1 0 6

Z -12 -15 0

Разрешающий столбец 2, разрешающая строка 3

-x1 -y3 1

y1 2 2 11

y2 3 4 15

x2 0 -1 2

y4 1 0 6

Z -12 -15 30

Разрешающий столбец 2, разрешающая строка 2

-x1 -y2 1

y1 0,5 -0,5 3,5

y3 0,75 0,25 3,75

x2 0,75 0,25 5,75

y4 1 0 6

Z -0,75 3,75 86,25

Разрешающий столбец 1, разрешающая строка 2

-y3 -y2 1

y1 - 2/3 - 2/3 1

x1 1 1/3 1/3 5

x2 -1 0 2

y4 -1 1/3 - 1/3 1

Z 1 4 90

Оптимальное решение задачи 3.2: X*3.2=(5;2), Z*3.2=90

Таким образом, оптимальное решение задачи целочисленного программирования имеет вид:

…=…

Для достижения максимальной производительности 90 изделий в час требуется приобрести 5 автоматов типа А и 2 автомата типа В.

Построим дерево решений:

№7.

1. Построим сетевой график выполнения работ:

Прямоугольниками на сетевом графике обозначены события; в прямоугольниках сверху записан номер события, в левой части прямоугольника находится раннее, а в правой части – позднее время выполнения работ. Стрелками обозначены работы. Жирными стрелками обозначены работы, принадлежащие критическому пути. Над стрелочками написано имя работы, а в скобках - нормальный срок выполнения работы

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

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

…=0

…=0+4=4

…=4+4=8

…=4+8=12

…=…

…=…

Рассчитаем позднее время выполнения работ по формуле…, при этом…=24:

…=24-4=20

…=…

…=…

…=…

…=…

Таким образом, минимальное время, за которое может быть выполнен весь комплекс работ, Ткр=24 дня.

Найдем критические работы, исходя из условий:

1)…,…

2)…,…

Проверяем условия для всех работ:

Работа A: 1216

Работа B: 812

Работа C: 0=0, 1920

Работа D: 1920

Работа E: 4=4, 1216

Работа F: 1216

Работа G: 4=4, 812

Работа H: 812

Работа Q: 4=4, 24=24, 4+20=24 – критическая

Работа V: 0=0, 4=4, 0+4=4 – критическая

Таким образом, получили 1 критический путь: V,Q.

Определим стоимость строительно-монтажных работ в нормальном режиме выполнения:

Sнорм.…=…

руб.

Найдем резервы времени выполнения работ:

свободный резерв:…

полный резерв:…

Имя работы Свободный резерв Rс Полный резерв Rп tн-tс ij

A 3 0 2 5,5

B 3 0 4 5,5

C 0 1 11 5,5

D 1 0 2 5,5

E 0 4 4 5,5

F 3 0 2 5,5

G 0 4 2 5,5

H 4 0 6 5,5

Q 0 0 12 5,5

V 0 0 2 5,5

3. Укажем стратегию минимального удорожания комплекса работ при сокращении сроков стро-ительства на 3 дня, и в какую итоговую сумму обойдётся фирме ускоренная стройка павильона.

Рассчитаем удорожание всех работ за 1 день по формуле:…. Результаты расчетов запишем в таблицу.

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

Сократить работу Q можно сразу на 3 дня, но сокращена она может быть только на 1 день, т.к. появляются новые критические пути.

Удорожание комплекса работ при сокращении срока на 1 день: S1=5,51=5,5 тыс. руб.

Последующее сокращение сроков на 2 дня возможно только при сокращении двух параллель-ных работ. Сократим, например, работы Q и C на 2 дня:

…=…

руб.

Удорожание за счет ускорения на 3 дня:

…=…

руб.

Стоимость работ в ускоренном режиме:

Sу=Sн+S=220+27,5=247,5 тыс. руб.

№8.

Запишем данные задачи в виде таблицы:

№ Месяц Дополнительный

спрос Дополнительная

мощность Емкость склада Стоимость

переналадки Себестоимость

машины Затраты на хранение

1 Январь 6 7 1 10 21 0,8

2 Февраль 1 4 2 4,5 21,7 0,2

3 Март 8 7 1 10,2 22,3 0,8

4 Апрель 3 4 5 5 23 0,1

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

…=…

Ограничения по спросу:

x1-h1=6

h1+x2-h2=1

h2+x3-h3=8

h3+x4=3

Ограничения по мощности:

0xtMt

0x17

0x24

0x37

0x44

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

0htEt

0h11

0h22

0h31

h4=0 (необходимо для минимизации затрат)

Определим затраты: ft – суммарные затраты на переналадку, производство и хранение продук-ции в месяце t:

…=…

…=…

…=…

f4=5+23x4

Критерий эффективности:

Решаем задачу методом динамического программирования

Январь

Спрос x1 h1 f1=10+21x1+0,8h1 1=f1(x1,h1)

6 6 0 136 136

7 1 157,8 157,8

Февраль

Спрос h1 x2 h2 f2=4,5+21,7x2+0,2h2 2=min{1(x1,h1)+f2(x2,h2)}

1 1 2 2 48,3 206,1

0 3 2 70 206

1 1 1 26,4 184,2

0 2 1 48,1 184,1

Март

Спрос h2 x3 h3 f3=10,2+22,3x3+0,8h3 3=min{2(h1,x2,h2)+f3(x3,h3)}

8 2 7 1 167,1 373,1

2 6 0 144 350

1 7 0 166,3 350,4

Апрель

Спрос h3 x4 f4=5+23x4 4=min{3(x3,h3)+f4(x4,h4)}

3 1 2 51 424,1

0 3 74 424

Находим оптимальное решение:

x4=3 h4=0

x3=6 h3=0

x2=3 h2=2

x1=6 h1=0

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

стоимость переналадки: 10 + 4,5 + 10,2 + 5 = 29,7 тыс. руб.

себестоимость машин: 216+21,73+22,36+233=393,9 тыс. руб.

затраты хранения: 0,80+0,22+0,80=0,4 тыс. руб.

Сумма минимальных затрат: 29,7+393,9+0,4=424 тыс. руб.