Контрольная работа по "Методам оптимальных решений"

 

 

Оценка свободной ячейки A₂B₃ (незадействованного маршрута) отрицательная ( ₂₃ =-1) , следовательно решение не является оптимальным.

Построим цикл для выбранной  ячейки A₂B₃:

По маршруту от поставщика A₂ к потребителю B₁ мы полностью перестаем доставлять продукцию.

Общие затраты уменьшатся на 15 * 10 ден. ед.

От поставщика A₄ к потребителю B₁ дополнительно поставим 10 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты увеличатся на 0 * 10 ден. ед.

Сократим поставку от поставщика A₄ к потребителю B₂ на 10 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты уменьшатся на 0 * 10 ден. ед.

От поставщика A₃ к потребителю B₂ дополнительно поставим 10 единиц продукции, по цене доставки 12 за единицу продукции. Общие затраты увеличатся на 12 * 10 ден. ед.

Сократим поставку от поставщика A₃ к потребителю B₃ на 10 единиц продукции, по цене доставки 11 за единицу продукции. Общие затраты уменьшатся на 11 * 10 ден. ед.

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

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1	-     10	-     11	0     9	16     6	110     8	126
A 2	10 - 10     15	-     16	+ 10 -1 13	-     11	-     14	10
A 3	-     14	16 + 10     12	82 - 10     11	-     11	-     12	98
A 4	58 + 10     0	52 - 10     0	-     0	-     0	-     0	110
Потребность	68	68	82	16	110

 

Получаем:

 

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1	-     10	-     11	0     9	16     6	110     8	126
A 2	-     15	-     16	10     13	-     11	-     14	10
A 3	-     14	26     12	72     11	-     11	-     12	98
A 4	68     0	42     0	-     0	-     0	-     0	110
Потребность	68	68	82	16	110

 

Оценим новый план.

 

v₃ + u₁ = c₁₃ v₃ + u₁ = 9 u₁ = 9 - 0 = 9

v₄ + u₁ = c₁₄ v₄ + u₁ = 6 v₄ = 6 - 9 = -3

v₅ + u₁ = c₁₅ v₅ + u₁ = 8 v₅ = 8 - 9 = -1

v₃ + u₂ = c₂₃ v₃ + u₂ = 13 u₂ = 13 - 0 = 13

v₃ + u₃ = c₃₃ v₃ + u₃ = 11 u₃ = 11 - 0 = 11

v₂ + u₃ = c₃₂ v₂ + u₃ = 12 v₂ = 12 - 11 = 1

v₂ + u₄ = c₄₂ v₂ + u₄ = 0 u₄ = 0 - 1 = -1

v₁ + u₄ = c₄₁ v₁ + u₄ = 0 v₁ = 0 - ( -1 ) = 1

 

Поставщик	Потребитель					U j
	B 1	B 2	B 3	B 4	B 5
A 1	-     10	-     11	0     9	16     6	110     8	u 1 = 9
A 2	-     15	-     16	10     13	-     11	-     14	u 2 = 13
A 3	-     14	26     12	72     11	-     11	-     12	u 3 = 11
A 4	68     0	42     0	-     0	-     0	-     0	u 4 = -1
V i	v 1 = 1	v 2 = 1	v 3 = 0	v 4 = -3	v 5 = -1

 

₁₁ = c₁₁ - ( u₁ + v₁ ) = 10 - ( 9 + 1 ) = 0

₁₂ = c₁₂ - ( u₁ + v₂ ) = 11 - ( 9 + 1 ) = 1

₂₁ = c₂₁ - ( u₂ + v₁ ) = 15 - ( 13 + 1 ) = 1

₂₂ = c₂₂ - ( u₂ + v₂ ) = 16 - ( 13 + 1 ) = 2

₂₄ = c₂₄ - ( u₂ + v₄ ) = 11 - ( 13 + ( -3 ) ) = 1

₂₅ = c₂₅ - ( u₂ + v₅ ) = 14 - ( 13 + ( -1 ) ) = 2

₃₁ = c₃₁ - ( u₃ + v₁ ) = 14 - ( 11 + 1 ) = 2

₃₄ = c₃₄ - ( u₃ + v₄ ) = 11 - ( 11 + ( -3 ) ) = 3

₃₅ = c₃₅ - ( u₃ + v₅ ) = 12 - ( 11 + ( -1 ) ) = 2

₄₃ = c₄₃ - ( u₄ + v₃ ) = 0 - ( -1 + 0 ) = 1

₄₄ = c₄₄ - ( u₄ + v₄ ) = 0 - ( -1 + ( -3 ) ) = 4

₄₅ = c₄₅ - ( u₄ + v₅ ) = 0 - ( -1 + ( -1 ) ) = 2

Поставщик	Потребитель					U j
	B 1	B 2	B 3	B 4	B 5
A 1	- 0 10	- 1 11	0     9	16     6	110     8	u 1 = 9
A 2	- 1 15	- 2 16	10     13	- 1 11	- 2 14	u 2 = 13
A 3	- 2 14	26     12	72     11	- 3 11	- 2 12	u 3 = 11
A 4	68     0	42     0	- 1 0	- 4 0	- 2 0	u 4 = -1
V i	v 1 = 1	v 2 = 1	v 3 = 0	v 4 = -3	v 5 = -1

 

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

S_min = 6 * 16 + 8 * 110 + 13 * 10 + 12 * 26 + 11 * 72 + 0 * 68 + 0 * 42 = 2210

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

 

 

 

 

	Вариант N 028			Задача 4
Фирма может   влиять  дополнительным  финансированием  на скорость  строительства
своего  торгового павильона.  Очередность выполнения работ,  нормальная  и срочная
продолжительность их выполнения приведены в следующей таблице:
Имя работы		A	B	C	D	E
Опирается на работу		E, H	G		C, F, Q
Нормальный срок (дни)		20	30	40	10	33
Ускоренный срок (дни)		18	27	36	9	27
Нормал. ст-сть (тыс.р.)		131,4	97,2	140,4	73,8	229,5
Срочная ст-сть (тыс.р.)		146	108	156	82	280,5
Имя работы		F	G	H	Q	V
Опирается на работу		E, H	V	G	V
Нормальный срок (дни)		10	10	10	36	10
Ускоренный срок (дни)		9	9	9	27	9
Нормал. ст-сть (тыс.р.)		34,2	27,9	30,6	261,9	90
Срочная ст-сть (тыс.р.)		38	31	34	349,2	100
1. С учетом технологической  последовательности работ построить  сетевой график выполнения
этих работ.
2. Рассчитать временные характеристики  сетевого графика при нормальном  режиме выполнения
работ. Найти критический  срок, указать все возможные критические  пути, определить
стоимость всего комплекса работ.
3 . Указать стратегию минимального удорожания комплекса работ при сокращении сроков
строительства на 2 дня.  В какую  итоговую сумму обойдется фирме  ускоренная стройка
павильона?