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

Размещено на http://www.allbest.ru/

36

Размещено на http://www.allbest.ru/

Задача №1

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

Депозиты можно оформлять с погашением не позднее начала 4?го месяца на сроки: один, два, три месяца, соответственно, под 1%, 2,5%, 4,0%. Оформление 2?х месячного депозита, начиная со второго месяца, пока не предлагается. В нижеследующей таблице приведен пример возможной стратегии оформления депозитов в течение рассматриваемого трехмесячного промежутка времени.

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

Требуется:

1) Формализовать задачу управления, представив в виде ЭММ, упростить и представить графически.

2) Установить, будет ли оптимальной приведенная в таблице, стратегия управления свободным оборотным капиталом фирмы. Если нет, то найти такую стратегию и оптимальные двойственные оценки ограничений. Дать экономическую интерпретацию двойственных оценок.

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

Начальная сумма	1 месяц	2 месяц	3 месяц	конец	Суммарный доход по проц.
	290	100	100	100
Погашенные вклады	0	160	60,6	101,21
Доход по процентам	0	1,6	0,61	1,01	3,22
1?месячный депозит	160	60,6	101,21
2?месячный депозит	0	0	0
3?месячный депозит	0	0	0
Расходы/(?) приходы	30	101	-40
Необходимый резерв	100	100	100

Решение

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

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

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

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

x₂₁ - двухмесячный депозит, оформленный в первом месяце

x₃₁ - трехмесячный депозит, оформленный в первом месяце

x₁₂ - одномесячный депозит, оформленный во втором месяце

x₁₃ - одномесячный депозит, оформленный в третьем месяце

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

x₁₁+x₂₁+x₃₁+30+70=290

x₁₂+101+70=100+1,01x₁₁

x₁₃-40+100=100+1,01x₁₂+1,025x₂₁

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

x₁₁+x₂₁+x₃₁=160

-1,01x₁₁+x₁₂=-101

-1,01x₁₂+x₁₃-1,025x₂₁=40

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

Z=0,01x₁₁+0,025x₂₁+0,04x₃₁+0,01x₁₂+0,01x₁₃max

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

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

u₁-1,01u₂0,01

u₂-1,01u₃0,01

u₃0,01

u₁-1,025u₃0,025

u₁0,04

W=160u₁-101u₂+40u₃min

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

0=160-x₁₁-x₂₁-x₃₁

0=-101+1,01x₁₁-x₁₂

0=40+1,01x₁₂-x₁₃+1,025x₂₁

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

v₁₁=0,01-u₁+1,01u₂

v₁₂=0,01-u₂+1,01u₃

v₁₃=0,01-u₃

v₂₁=0,025-u₁+1,025u₃

v₃₁=0,04-u₁

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



		v11= -x11	v12= -x12	v13= -x13	v21= -x21	v31= -x31	W= 1
u1	0=	1	0	0	1	1	160
u2	0=	-1,01	1	0	0	0	-101
u3	0=	0	-1,01	1	-1,025	0	40
1	Z=	-0,01	-0,01	-0,01	-0,025	-0,04	0

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

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

		v11= -x11	v12= -x12	v13= -x13	v21= -x21	u1= 0	W= 1
v31	x31=	1	0	0	1	1	160
u2	0=	-1,01	1	0	0	0	-101
u3	0=	0	-1,01	1	-1,025	0	40
1	Z=	0,03	-0,01	-0,01	0,015	0,04	6,4

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

		v11= -x11	u2= 0	v13= -x13	v21= -x21	W= 1
v31	x31=	1	0	0	1	160
v12	x12=	-1,01	1	0	0	-101
u3	0=	-1,0201	1,01	1	-1,025	-62,01
1	Z=	0,0199	0,01	-0,01	0,015	5,39

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



		v11= -x11	u3= 0	v21= -x21	W= 1
v31	x31=	1	0	1	160
v12	x12=	-1,01	0	0	-101
v13	x13=	-1,0201	1	-1,025	-62,01
1	Z=	0,009699	0,01	0,00475	4,7699

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

		v11= -x11	v21= -x21	W= 1
v31	x31=	1	1	160
v12	x12=	-1,01	0	-101
v13	x13=	-1,0201	-1,025	-62,01
1	Z=	0,009699	0,00475	4,7699

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

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

		v12= -x12	v21= -x21	W= 1
v31	x31=	0,990099	1	60
v11	x11=	-0,9901	0	100
v13	x13=	-1,01	-1,025	40
1	Z=	0,009603	0,00475	3,8

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

X*=(100;0;40;0;60)

v₁₁=v₁₃=v₃₁=0; v₁₂=0,0096; v₂₁=0,00475

v₁₃=0,01-u₃ 0=0,01-u₃ u₃=0,01

v₃₁=0,04-u₁ 0=0,04-u₁ u₁=0,04

v₁₂=0,01-u₂+1,01u₃ 0,0096=0,01-u₂+1,010,01 u₂=0,0105

Задача №2

Для полного удовлетворения еженедельного спроса на продукцию фирмы в пунктах В1 и В2 в объемах 50 единиц и 200 единиц администрация фирмы рассматривает четыре возможных проекта создания дополнительных производственных филиалов в пунктах А1, А2, А3 и А4. Проектируемые еженедельные мощности, расчетные себестоимости единиц продукции и ожидаемы транспортные расходы на доставку единицы продукции от созданного филиала названным потребителям приведены в нижеследующей таблице.

Имя проекта	Мощность (ед.)	Себес-сть (руб.)	Транспортный тариф
			До пункта В1	До пункта В2
Филиал А1	10	8	3	11
Филиал А2	100	5	7	11
Филиал А3	140	9	5	10
Филиал А4	170	3	8	16

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

Требуется:

1. Формализовать задачу управления размещения филиалов и транспортировкой продукции.

2. Найти решение перебором всех возможных вариантов размещения филиалов и транспортировки продукции.

Решение

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

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

x₁₁+x₁₂10y₁

x₂₁+x₂₂100y₂

x₃₁+x₃₂140y₃

x₄₁+x₄₂170y₄

x₁₁+x₂₁+x₃₁+x₄₁50

x₁₂+x₂₂+x₃₂+x₄₂200

x_ij0

S₀=108y₁+1005y₂+1409y₃+1703y₄ (производственные затраты)

S₁=3x₁₁+11x₁₂+7x₂₁+11x₂₂+5x₃₁+10x₃₂+8x₄₁+16x₄₂ (транспортные затраты)

S=S₀+S₁min (суммарные затраты)

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

y⁽¹⁾=(1,1,1,1) S₀⁽¹⁾=80+500+1260+510=2350

y⁽²⁾=(1,1,1,0) S₀⁽²⁾=80+500+1260=1840

y⁽³⁾=(1,1,0,1) S₀⁽³⁾=80+500+510=1090

y⁽⁴⁾=(1,0,1,1) S₀⁽⁴⁾=80+1260+510=1850

y⁽⁵⁾=(0,1,1,1) S₀⁽⁵⁾=500+1260+510=2270

y⁽⁶⁾=(0,1,0,1) S₀⁽⁶⁾=500+510=1010

y⁽⁷⁾=(0,0,1,1) S₀⁽⁷⁾=1260+510=1770

1. y⁽¹⁾=(1,1,1,1)

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

420-250=170

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

Филиалы	Потребитель
	50	200	170
10	3		11		0
100	7		11		0
140	5		10		0
170	8		16		0

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

Филиалы	Потребитель
	50	200	170
10	3	10	11		0
100	7	40	11	60	0
140	5		10	140	0
170	8		16	0	0	170

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

v1-u1=3

v1-u2=7

v2-u2=11

v2-u3=10

v2-u4=16

v3-u4=0

Пусть u1=10, тогда u2=6; u3=7; u4=1; v1=13; v2=17; v3=1

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

17- 10- 11< 0	1- 10- 0< 0	1- 6- 0< 0	13- 7- 5> 0	1- 7- 0< 0	13- 1- 8> 0

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

Филиалы	Потребитель
	50	200	170
10	3	10	11		0
100	7	40	11	60	0
140	5		10	140	0
170	8	0	16		0	170

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

u1=10; u2=6; u3=7; u4=5; v1=13; v2=17; v3=5

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

17- 10- 11< 0	5- 10- 0< 0	5- 6- 0< 0	13- 7- 5> 0	5- 7- 0< 0	17- 5- 16< 0

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

Филиалы	Потребитель
	50	200	170
10	3	10	11		0
100	7		11	100	0
140	5	40	10	100	0
170	8	0	16		0	170

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

u1=10; u2=7; u3=8; u4=5; v1=13; v2=18; v3=5

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

18- 10- 11< 0	5- 10- 0< 0	13- 7- 7< 0	5- 7- 0< 0	5- 8- 0< 0	18- 5- 16< 0

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

X(1)*=	10	0
	0	100
	40	100
	0	0

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

S₁⁽¹⁾=310+11100+540+10100=2330, S⁽¹⁾=2350+2330=4680

2. y⁽²⁾=(1,1,1,0)

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



Филиалы	Потребитель
	50	200
10	3		11
100	7		11
140	5		10

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

Филиалы	Потребитель
	50	200
10	3	10	11
100	7	40	11	60
140	5		10	140

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

v1-u1=3

v1-u2=7

v2-u2=11

v2-u3=10

Пусть u1=10, тогда u2=6; u3=7; v1=13; v2=17

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

17- 10- 11< 0	13- 7- 5> 0

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



Филиалы	Потребитель
	50	200
10	3	10	11
100	7		11	100
140	5	40	10	100

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

u1=10; u2=7; u3=8; v1=13; v2=18

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

18- 10- 11< 0	13- 7- 7< 0

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

X(2)*=	10	0
	0	100
	40	100
	0	0

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

S₁⁽²⁾=310+11100+540+10100=2330, S⁽²⁾=1840+2330=4170

3. y⁽³⁾=(1,1,0,1)

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

280-250=30

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

Филиалы	Потребитель
	50	200	30
10	3		11		0
100	7		11		0
170	8		16		0

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

Филиалы	Потребитель
	50	200	30
10	3	10	11		0
100	7	40	11	60	0
170	8		16	140	0	30

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

v1-u1=3

v1-u2=7

v2-u2=11

v2-u3=16

v3-u3=0

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

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

17- 10- 11< 0	1- 10- 0< 0	1- 6- 0< 0	13- 1- 8> 0

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



Филиалы	Потребитель
	50	200	30
10	3	10	11		0
100	7		11	100	0
170	8	40	16	100	0	30

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

u1=10; u2=10; u3=5; v1=13; v2=21; v3=5

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

21- 10- 11= 0	5- 10- 0< 0	13- 10- 7< 0	5- 10- 0< 0

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

X(3)*=	10	0
	0	100
	0	0
	40	100

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

S₁⁽³⁾=310+11100+840+16100=3050, S⁽³⁾=1090+3050=4140

4. y⁽⁴⁾=(1,0,1,1)

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

320-250=70

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

Филиалы	Потребитель
	50	200	70
10	3		11		0
140	5		10		0
170	8		16		0

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

Филиалы	Потребитель
	50	200	70
10	3	10	11		0
140	5	40	10	100	0
170	8		16	100	0	70

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

v1-u1=3

v1-u2=5

v2-u2=10

v2-u3=16

v3-u3=0

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

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

18- 10- 11< 0	2- 10- 0< 0	2- 8- 0< 0	13- 2- 8> 0

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

Филиалы	Потребитель
	50	200	70
10	3	10	11		0
140	5		10	140	0
170	8	40	16	60	0	70

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

u1=10; u2=11; u3=5; v1=13; v2=21; v3=5

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

21- 10- 11= 0	5- 10- 0< 0	13- 11- 5< 0	5- 11- 0< 0

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

X(4)*=	10	0
	0	0
	0	140
	40	60

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

S₁⁽⁴⁾=310+10140+840+1660=2710, S⁽⁴⁾=1580+2710=4560

5. y⁽⁵⁾=(0,1,1,1)

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

410-250=160

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

Филиалы	Потребитель
	50	200	160
100	7		11		0
140	5		10		0
170	8		16		0

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

Филиалы	Потребитель
	50	200	160
100	7	50	11	50	0
140	5		10	140	0
170	8		16	10	0	160

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

v1-u1=7

v2-u1=11

v2-u2=10

v2-u3=16

v3-u3=0

Пусть u1=10, тогда u2=11; u3=5; v1=17; v2=21; v3=5

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

5- 10- 0< 0	17- 11- 5> 0	5- 11- 0< 0	17- 5- 8> 0

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

Филиалы	Потребитель
	50	200	160
100	7	40	11	60	0
140	5		10	140	0
170	8	10	16		0	160

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

u1=10; u2=11; u3=9; v1=17; v2=21; v3=9

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

9- 10- 0< 0	17- 11- 5> 0	9- 11- 0< 0	21- 9- 16< 0

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

Филиалы	Потребитель
	50	200	160
100	7		11	100	0
140	5	40	10	100	0
170	8	10	16		0	160

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

u1=10; u2=11; u3=8; v1=16; v2=21; v3=8

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

16- 10- 7< 0	8- 10- 0< 0	8- 11- 0< 0	21- 8- 16< 0

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

X(5)*=	0	0
	0	100
	40	100
	10	0

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

S₁⁽⁵⁾=11100+540+10100+810=2380, S⁽⁵⁾=2270+2380=4650

6. y⁽⁶⁾=(0,1,0,1)

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

270-250=20

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

Филиалы	Потребитель
	50	200	20
100	7		11		0
170	8		16		0

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



Филиалы	Потребитель
	50	200	20
100	7	50	11	50	0
170	8		16	150	0	20

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

v1-u1=7

v2-u1=11

v2-u2=16

v3-u2=0

Пусть u1=10, тогда u2=5; v1=17; v2=21; v3=5

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

5- 10- 0< 0	17- 5- 8> 0

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

Филиалы	Потребитель
	50	200	20
100	7		11	100	0
170	8	50	16	100	0	20

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

u1=10; u2=5; v1=13; v2=21; v3=5

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

13- 10- 7< 0	5- 10- 0< 0

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

X(6)*=	0	0
	0	100
	0	0
	50	100

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

S₁⁽⁶⁾=11100+850+16100=3110, S⁽⁶⁾=1010+3100=4110

7. y⁽⁷⁾=(0,0,1,1)

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

310-250=60

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

Филиалы	Потребитель
	50	200	60
140	5		10		0
170	8		16		0

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

Филиалы	Потребитель
	50	200	60
140	5	50	10	90	0
170	8		16	110	0	60

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

v1-u1=5

v2-u1=10

v2-u2=16

v3-u2=0

Пусть u1=10, тогда u2=4; v1=15; v2=20; v3=4

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

4- 10- 0< 0	15- 4- 8> 0

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

Филиалы	Потребитель
	50	200	60
140	5		10	140	0
170	8	50	16	60	0	60

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

u1=10; u2=4; v1=12; v2=20; v3=4

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

12- 10- 5< 0	4- 10- 0< 0

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

X(7)*=	0	0
	0	0
	0	140
	50	60

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

S₁⁽⁷⁾=10140+850+1660=2760, S⁽⁷⁾=1770+2760=4530

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

Y^*=(0;1;0;1)

X(6)*=	0	0
	0	100
	0	0
	50	100

S_1min=3100 S_min=4110

Задача №3

Администрация производственной фирмы желает рассчитать еженедельную программу выпуска своих изделий А и В, которая дает максимум чистого дохода на рубль всех сделанных затрат. Изделие А гарантировано реализуется по цене 111,6 руб. , а изделие В по цене 200,0 руб.

Расход сырья на изделие А составляет 5 кг., а на изделие В ? 3 кг. Расход оборудования на изделие А составляет 3 ст. час., на изделие В ? 6 ст.час. Минимальные объемы сырья и станочного парка, при которых не произойдет остановки производства составляют, соответственно: 750 кг и 1500 ст.час. в неделю.

Фирма же имеет 2250 кг сырья и 3000 ст.час. оборудования. Себестоимости изделия А и изделия В (без учета заработной платы) составляют, соответственно, 100,0 руб., 152,0 руб. Сумма оплаты рабочих и служащих фирмы с другими накладными расходами составляет 24,00 тыс. руб. в неделю.

Требуется:

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

Решение:

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

	A	B
Цена реализации	111,6	200	Минимум	В наличии
Сырье	5	3	750	2250
Оборудование	3	6	1500	3000
Себестоимость	100	152
З/плата	24000

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

7505x₁+3x₂2250 - по сырью

15003x₁+6x₂3000 - по оборудованию

x₁0, x₂0

Выручка: Z₁=111,6x₁+200x₂

Затраты: Z₂=100x₁+152x₂+24000

Доход: Z₁-Z₂=11,6x₁+48x₂-24000

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

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

x₁0, x₂0

5x₁+3x₂2250

-5x₁-3x₂-750

3x₁+6x₂3000

-3x₁-6x₂-1500

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

y₁=2250-5x₁-3x₂0

y₂=-750+5x₁+3x₂0

y₃=3000-3x₁-6x₂0

y₄=-1500+3x₁+6x₂0

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

	-x1	-x2	1
y1	5	3	2250
y2	-5	-3	-750
y3	3	6	3000
y4	-3	-6	-1500
Z1-Z2	-11,6	-48	-24000
Z2	-100	-152	24000

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

Разрешающий столбец выберем второй. Т.к. min{2250/3;-750/-3;3000/6;-1500/-6}=250, то разрешающая строка четвертая. Переходим к следующей симплекс-таблице

	-x1	-y4	1
y1	3,5	0,5	1500
y2	-3,5	-0,5	0
y3	0	1	1500
x2	0,5	- 1/6	250
Z1-Z2	12,4	-8	-12000
Z2	-24	-25 1/3	62000

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

Обобщающим критерием оптимальности является неотрицательность определителей _jЎЭ0

1=	12,4	-12000	>0
	-24	62000
2=	-8	-12000	<0
	-25 1/3	62000

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

	-x1	-y4	1
y1	3,5	-0,5	750
y2	-3,5	0,5	750
y3	0	1	1500
x2	0,5	1/6	500
Z1-Z2	12,4	8	0
Z2	-24	25 1/3	100000



1=	12,4	0	>0
	-24	100000
2=	8	0	>0
	25 1/3	100000

Условие оптимальности выполнено.

x₁=0 x₂=500 z=0/100000=0

Задача №5

Администрация фирмы желает увеличить производство своих изделий за счет привлечения дополнительной производственной площади в объеме 10 кв. метров, а также покупки у машиностроительных фирм современных автоматов по производству аналогичной продукции на сумму 33 млн. рублей.

После изучения соответствующих рекламных проспектов подходящими для покупки признаны: автомат фирмы А, занимающий площадь 1 кв. метр, имеющий цену 3 млн. руб., и обладающий производительностью 8 изделий в час; а также автомат фирмы В, занимающий площадь 2 кв. метра, имеющий цену 8 млн. руб., и дающий производительность 21 изделие в час.

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

Требуется:

1) Формализовать задачу управления закупками оборудования, как модель дискретного программирования.

2) Применить метод ветвей и границ и получить оптимальное численное решение.

Решение:

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

	A	B	В наличии
Площадь	1	2	10
Затраты	3	8	33
Производительность	8	21

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

x₁+2x₂10

3x₁+8x₂33

x₁0, x₂0, x₁, x₂ - целые

Критерий эффективности: Z=8x₁+21x₂max

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

x₁+2x₂10

y₁=10-x₁-2x₂0

3x₁+8x₂33

y₂=33-3x₁-8x₂0

x₁0, x₂0

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

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

	-x1	-x2
y1	1	2	10
y2	3	8	33
Z	-8	-21	0

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

	-x1	-y2
y1	0,25	-0,25	1,75
x2	0,375	0,125	4,125
Z	-0,125	2,625	86,625

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

	-y1	-y2
x1	4	-1	7
x2	-1,5	0,5	1,5
Z	0,5	2,5	87,5

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

Задача 1.1

x₁+2x₂10

3x₁+8x₂33

x₂1

x₁0, x₂0, x₁, x₂ - целые

Z=8x₁+21x₂max

	-x1	-x2
y1	1	2	10
y2	3	8	33
y3	0	1	1
Z	-8	-21	0

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

	-x1	-y3
y1	1	-2	8
y2	3	-8	25
x2	0	1	1
Z	-8	21	21

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

	-y1	-y3
x1	1	-2	8
y2	-3	-2	1
x2	0	1	1
Z	8	5	85

Оптимальное решение задачи 1.1: X^*_1.1=(8;1), Z^*_1.1=85

Задача 1.2

x₁+2x₂10

3x₁+8x₂33

x₂2

x₁0, x₂0, x₁, x₂ - целые

Z=8x₁+21x₂max

	-x1	-x2
y1	1	2	10
y2	3	8	33
y3	0	-1	-2
Z	-8	-21	0

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



	-x1	-y3
y1	1	2	6
y2	3	8	17
x2	0	-1	2
Z	-8	-21	42

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

	-x1	-y2
y1	0,25	-0,25	1,75
y3	0,375	0,125	2,125
x2	0,375	0,125	4,125
Z	-0,125	2,625	86,625

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

	-y3	-y2
y1	- 2/3	- 1/3	1/3
x1	2 2/3	1/3	5 2/3
x2	-1	0	2
Z	1/3	2 2/3	87 1/3

Оптимальное решение задачи 1.2: X^*_1.2=(5 2/3;2), Z^*_1.2=87 1/3

Т.к. решение задачи 1.2 не является целочисленным и Z^*_1.2> Z^*_1.1, то в задачу 1.2 вводим дополнительные ограничения: либо x₁5 (задача 2.1), либо x₁6 (задача (2.2)

Задача 2.1

x₁+2x₂10

3x₁+8x₂33

x₂2

x₁5

x₁0, x₂0, x₁, x₂ - целые

Z=8x₁+21x₂max

	-x1	-x2
y1	1	2	10
y2	3	8	33
y3	0	-1	-2
y4	1	0	5
Z	-8	-21	0

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

	-x1	-y3
y1	1	2	6
y2	3	8	17
x2	0	-1	2
y4	1	0	5
Z	-8	-21	42

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

	-x1	-y2
y1	0,25	-0,25	1,75
y3	0,375	0,125	2,125
x2	0,375	0,125	4,125
y4	1	0	5
Z	-0,125	2,625	86,625

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

	-y4	-y2
y1	-0,25	-0,25	0,5
y3	-0,375	0,125	0,25
x2	-0,375	0,125	2,25
x1	1	0	5
Z	0,125	2,625	87,25

Оптимальное решение задачи 2.1: X^*_2.1=(5;2,25), Z^*_2.1=96,75

Задача 2.2

x₁+2x₂10

3x₁+8x₂33

x₂2

x₁6

x₁0, x₂0, x₁, x₂ - целые

Z=8x₁+21x₂max

	-x1	-x2
y1	1	2	10
y2	3	8	33
y3	0	-1	-2
y4	-1	0	-6
Z	-8	-21	0

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

	-y4	-x2
y1	1	2	4
y2	3	8	15
y3	0	-1	-2
x1	-1	0	6
Z	-8	-21	48

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

	-y4	-y2
y1	0,25	-0,25	0,25
x2	0,375	0,125	1,875
y3	0,375	0,125	-0,125
x1	-1	0	6
Z	-0,125	2,625	87,375

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

Т.к. Z_2.1>Z_1.1 и решение задачи 2.1 не является целочисленным, то в задачу 2.1 вводим дополнительные ограничения: либо x₂2 (задача 3.1), либо x₂3 (задача (3.2)

Задача 3.1

x₁+2x₂10

3x₁+8x₂33

x₂2

x₁5

x₁0, x₂0, x₁, x₂ - целые

Z=8x₁+21x₂max

	-x1	-x2
y1	1	2	10
y2	3	8	33
y3	0	1	2
y4	1	0	5
Z	-8	-21	0

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

	-x1	-y3
y1	1	-2	6
y2	3	-8	17
x2	0	1	2
y4	1	0	5
Z	-8	21	42

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

	-y4	-y3
y1	-1	-2	1
y2	-3	-8	2
x2	0	1	2
x1	1	0	5
Z	8	21	82

Оптимальное решение задачи 3.1: X^*_3.1=(5;2), Z^*_3.1=82

Задача 3.2

x₁+2x₂10

3x₁+8x₂33

x₂3

x₁5

x₁0, x₂0, x₁, x₂ - целые

Z=8x₁+21x₂max

	-x1	-x2
y1	1	2	10
y2	3	8	33
y3	0	-1	-3
y4	1	0	5
Z	-8	-21	0

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

оптимальный перевозка сетевой график

	-x1	-y3
y1	1	2	4
y2	3	8	9
x2	0	-1	3
y4	1	0	5
Z	-8	-21	63

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

	-x1	-y2
y1	0,25	-0,25	1,75
y3	0,375	0,125	1,125
x2	0,375	0,125	4,125
y4	1	0	5
Z	-0,125	2,625	86,625

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

	-y3	-y2
y1	- 2/3	- 1/3	1
x1	2 2/3	1/3	3
x2	-1	0	3
y4	-2 2/3	- 1/3	2
Z	1/3	2 2/3	87

Оптимальное решение задачи 3.2: X^*_3.2=(3;3), Z^*_3.2=87

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

x₁=3 x₂=3 Z_max=87

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

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

Задача №7

Фирма может влиять дополнительным финансированием на скорость строительства своего торгового павильона. Очередность выполнения работ, их нормальная и ускоренная продолжительность выполнения, а также стоимость строительно-монтажных работ при нормальном и ускоренном режиме их выполнения приведены в следующей таблице:

Имя работы	Опирается на работу	Нормальный срок (в днях)	Ускоренный срок (в днях)	Нормальная стоимость (тыс. руб.)	Срочная стоимость (тыс. руб.)
A	E	9	8	40	45
B	G, Q	27	24	120	135
C		36	32	160	180
D	C, H, A	9	8	40	45
E	V	18	16	80	90
F	E	18	16	80	90
G		21	16	80	105
H	G, Q	18	16	80	90
Q	V	15	8	40	75
V		9	8	40	45

Требуется:

1. С учетом технологической последовательности работ построить сетевой график выполнения этих работ.

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

3. Указать стратегию минимального удорожания комплекса работ при сокращении сроков строительства на 5 дн. В какую итоговую сумму обойдется фирме ускоренная стройка павильона?

Решение:

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

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

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

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

=0

=0+9=9

=max(0+21;9+15)=24

=9+18=27

=max(0+36;24+18;27+9)=42

=max(24+27;27+18;42+9)=51

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

=51-9=42

=min(51-18;42-9)=33

=min(51-27;42-18)=24

=min(33-18;24-15)=9

=min(42-36;24-21;9-9)=0

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

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

1) ,

2) ,

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

Работа A:	2733
Работа B:	24=24, 51=51, 24+27=51 - критическая
Работа C:	0=0, 42=42, 0+3642
Работа D:	42=42, 51=51, 42+9=51 - критическая
Работа E:	9=9, 2733
Работа F:	2733
Работа G:	0=0, 24=24, 0+2124
Работа H:	24=24, 42=42, 24+18=42 - критическая
Работа Q:	9=9, 24=24, 9+15=24 - критическая
Работа V:	0=0, 9=9, 0+9=9 - критическая

Таким образом, получили 2 критических пути: V,Q,H,D и V,Q,B.

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

S_норм.=40+120+160+40+80+80+80+80+40+40=760 тыс. руб.

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

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

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

Имя работы	Свободный резерв Rс	Полный резерв Rп	tн-tс	ij
A	6	0	1	5
B	0	0	3	5
C	6	6	4	5
D	0	0	1	5
E	0	6	2	5
F	6	0	2	5
G	3	3	5	5
H	0	0	2	5
Q	0	0	7	5
V	0	0	1	5

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

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

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

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

Удорожание комплекса работ при сокращении срока на 3 дня: S₁=53=15 тыс. руб.

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

S₂=52+52=20 тыс. руб.

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

S=S₁+S₂=15+20=35 тыс. руб.

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

S^у=S^н+S=760+35=795 тыс. руб.

Задача №8

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

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

N	Название месяца	Дополн. спрос (шт.)	Дополн. мощность (шт.)	Емкость склада (шт.)	Стоимость переналадки (тыс.)	Себест. машины (тыс.)	Затраты хранения (тыс.)
1	Январь	11	14	1	5,1	25,9	1,1
2	Февраль	5	8	1	15,5	26,9	1,1
3	Март	4	11	4	4,8	27,9	0,5
4	Апрель	6	5	4	14,6	28,7	0,3

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

Требуется:

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

2.Используя методы СПУ и динамического программ., найти все оптимальные стратегии производства и хранения. Указать сумму минимальных затрат с раскладкой по всем статьям затрат.

Решение:

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

S_t=h_t-1+x_t-h_t

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

x₁-h₁=11

h₁+x₂-h₂=5

h₂+x₃-h₃=4

h₃+x₄=6

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

0x_tM_t

0x₁14

0x₂8

0x₃11

0x₄5

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

0h_tE_t

0h₁1

0h₂1

0h₃4

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

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

f₁=5,1+25,9x₁+1,1h₁

f₂=15,5+26,9x₂+1,1h₂

f₃=4,8+27,9x₃+0,5h₃

f₄=14,6+28,7x₄

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

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

Январь



Спрос	x1	h1	f1=5,1+25,9x1+1,1h1	1=f1(x1,h1)
11	11	0	290	290
	12	1	317	317

Февраль

Спрос	h1	x2	h2	f2=15,5+26,9x2+1,1h2	2=min{1(x1,h1)+f2(x2,h2)}
5	1	5	1	151,1	468,1
	0	6	1	178	468
	1	4	0	123,1	440,1
	0	5	0	150	440

Март

Спрос	h2	x3	h3	f3=4,8+27,9x3+0,5h3	3=min{2(h1,x2,h2)+f3(x3,h3)}
4	1	7	4	202,1	670,1
	0	8	4	230	670
	1	6	3	173,7	641,7
	0	7	3	201,6	641,6
	1	5	2	145,3	613,3
	0	6	2	173,2	613,2
	1	4	1	116,9	584,9
	0	5	1	144,8	584,8

Апрель

Спрос	h3	x4	f4=14,6+28,7x4	4=min{3(x3,h3)+f4(x4,h4)}
6	4	2	72	742
	3	3	100,7	742,3
	2	4	129,4	742,6
	1	5	158,1	742,9

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

x₄=2 h₄=0

x₃=8 h₃=4

x₂=5 h₂=0

x₁=11 h₁=0

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

стоимость переналадки: 5,1 + 15,5 + 4,8 + 14,6 = 40 тыс. руб.

себестоимость машин: 25,911+26,95+27,98+28,72=700 тыс. руб.

затраты хранения: 1,10+1,10+0,54=2 тыс. руб.

Сумма минимальных затрат: 40+700+2=742 тыс. руб.

Размещено на Allbest