Расчётно-графическое задание (стр. 2 из 4)

y₂=0

y₃=10,22

y₄=2,99

y₅=5,5

Дефицитным являются ресурсы III, IVи V.

Недефицитными являются ресурсы I, II.

Недефицитные ресурсы недоиспользуются:

I ресурс на 230,7 кг;

II ресурс на 1057,07 кг

При увеличении запаса III ресурса на 1 ед. (204 кг) можно получить увеличение прибыли на 10,22 руб. она составит F=4706,27 руб. При этом план выпуска продукции 4 надо увеличить на 0,065 т.е. x₄=1,238, продукции 1 надо увеличить на -0,1 т.е. x₁=2,1, продукции 2 надо увеличить на 0,038 т.е. x₂=33,098. В этом случае недефицитные ресурсы будут недоиспользоваться:

1 ресурс на 0,89; его недоиспользование составит 231,69 кг;

2 ресурс на 0,64; его недоиспользование составит 1057,71 кг

Покажем допустимые пределы изменения запасов ресурсов.

Составим матрицу Р

и вектор столбец

Найдем матрицу P

Р^-1(b+∆b)=

=

Покажем допустимые пределы изменения цен на выпускаемые виды продукции.

p^-1(c+∆c)

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

Приводим задачу к каноническому виду

F*= - 500y₁-1402y₂-203y₃-600y₄-150y₅+0y₆+0y₇+0y₈+0y₉→max

7y₁+9y₂+5y₃+17y₄+4y₅-y₆=124

6y₁+13y₂+7y₃+5y₄+7y₅-y₇=125

5y₁+17y₂+15y₃+24y₄+23y₅-y₈=195

21y₁+16y₂+19y₃+23y₄+2y₅-y₉=274

i=

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

G=0y₁+0y₂+0y₃+0y₄+0y₅+0y₆+0y₇+0y₈+0y₉-y₁₀-y₁₁-y₁₂-y₁₃→min

7y₁+9y₂+5y₃+17y₄+4y₅-y₆+y₁₀=124

6y₁+13y₂+7y₃+5y₄+7y₅-y₇+y₁₁=125

5y₁+17y₂+15y₃+24y₄+9y₅-y₈+y₁₂=195

21y₁+16y₂+19y₃+23y₄+2y₅-y₉+y₁₃=274

i=

Базис	Сб	Опорное решение	С1	С2	С3	С4	С5	С6	С7	С8	С9
			500	1402	203	600	150	0	0	0	0
			А1	А2	А3	А4	А5	А6	А7	А8	А9
А4	-600	2,99	0,19	0,07	0	1	0	-0,08	0,04	0	0,005
А5	-150	5,5	-0,17	1,17	0	0	1	-0,04	-0,13	0	-0,06
А3	-203	10,2	0,9	0,6	1	0	0	0,01	-0,04	0	-0,06
А8	0	79,6	11,4	4,7	0	0	0	-0,8	-0,76	1	-0,3
∆j	F=-4696,05		230,07	1057	0	0	0	33,6	2,2	0	1,17

Заключительная симплекс-таблиц

Составим матрицу P и вектор-столбец

P =

;

=

Найдём матрицу

=

∆c)=

* =

Покажем целесообразность введения в план производства выпуск ткани с разновидностью рисунка Р5:

∆p₅=6*0+2*0+1*10,22+4*2,99+4*5,5-5000=-4955,82

Т.к. ∆р₅<0, то есть смысл ввести в план производства выпуск ткани с разновидностью рисунка р₅.

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

Дефицитным является краситель А₃, А₄ и А₅. Значит Db₃=10, Db₄=10 и Db₅=10. Остальные Db₁=Db₂ =0, тогда

Увеличение дефицитных красителей не приводит к изменению плана производства тканей.

Задание №2

Коммивояжер выезжает из одного из городов (все равно какого) и должен объехать все города, преодолев минимальное расстояние. При этом в каждый город он может только 1 раз въехать и только 1 раз выехать. Составить экономико-математическую модель задачи и решить задачу методом ветвей и границ.

Дон.	Ерев.	Жит.	Казань	Калин.	Каун.
Донецк	1523	863	1899	1809	1578
Ереван	1523	2329	1622	3275	3044
Житомир	863	2329	1801	1208	977
Казань	1899	1622	1801	2023	1792
Калининград	1809	3275	1208	2023	247
Каунас	1578	3044	977	1792	247

F= 1523x₁₂ + 1523₂₁ + 863x₁₃ + 863x₃₁ + 1899x₁₄ + 1899x₄₁ + 1809x₁₅ + 1809x₅₁ + 1578x₁₆ + 1578x₆₁ + 2329x₃₂ + 2329x₂₃ + 1622x₂₄ +1622x₄₂ + 3275x₂₅ + 3275x₅₂ + 3044x₂₆ + 3044x₆₂ + 1801x₃₄ + 1801x₄₃ + 1208x₃₅ + 1208x₅₃ + 977x₃₆ + 977x₆₃ + 2023x₄₅ + 2023x₅₄ + 1792x₄₆ + 1792x₆₄ + 247x₅₆ + 247x₆₅

min

x₁₂ + x₁₃ + x₁₄ + x₁₅ + x₁₆ = 1

x₂₁ + x₂₃ + x₂₄ + x₂₅ + x₂₆ = 1

x₃₁ + x₃₂ + x₃₄ + x₃₅ + x₃₆ = 1

x₄₁ + x₄₂ + x₄₃ + x₄₅ + x₄₆ = 1

x₅₁ + x₅₂ + x₅₃ + x₅₄ + x₅₆ = 1

x₆₁ + x₆₂ + x₆₃ + x₆₄ + x₆₅ = 1

x₂₁ + x₃₁ + x₄₁ + x₅₁ + x₆₁ = 1

x₁₂ + x₃₂ + x₄₂ + x₅₂ + x₆₂ = 1

x₁₃ + x₂₃ + x₄₃ + x₅₃ + x₆₃ = 1

x₁₄ + x₂₄ + x₃₄ + x₅₄ + x₆₄ = 1

x₁₅ + x₂₅ + x₃₅ + x₄₅ + x₆₅ = 1

x₁₆ + x₂₆ + x₃₆ + x₄₆ + x₅₆ = 1

Решение задачи методом ветвей и границ.

Преобразуем матрицу s

Определяем сумму приводимых элементов

h¹=863+1523+863+1622+247+247+99=5464

Определяем претендентов для ветвления в множестве Y

Претендентами на ветвление могут быть S₁₃, S₂₁, S₂₄, S₃₁, S₄₂, S₅₆,S₆₅

Q₁₃ = 660+179=839;

Q₂₁ = 0;

Q₂₄ = 839;

Q₃₁ = 114;

Q₄₂ =660+170=830;

Q₅₆ = 170+961=1131;

Q₆₅ = 345+730=1075

Максимальную оценку имеет маршрут: Q42=830

w

= h¹+Q42= 5464 + 830 = 6294

Преобразуем матрицу: