Расчётно-графическое задание

Цель и назначение работы

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

Задание на выполнение РГР

Задание №1

На фабрике с помощью 5 видов красителей (А1-А5) создается 4 разновидности рисунков для тканей (Р1-Р4). При известной отпускной стоимости 1 м ткани каждого рисунка (руб.), известном расходе каждого красителя на окраску 1 м ткани (г) и известном запасе каждого красителя (кг):

2.1.1 определить план выпуска ткани каждого рисунка, обеспечивающий максимальную прибыль от реализации тканей;

2.1.2 составить двойственную задачу и найти ее решение;

2.1.3 определить теневые цены на каждый краситель; указать дефицитные и недефицитные красители;

2.1.4. указать на сколько недоиспользуются недефицитные красители;

2.1.5 показать прибыль, план выпуска тканей каждого рисунка и недоиспользование недефицитных красителей при увеличении запасов дефицитных красителей на 1 ед.;

2.1.6 показать допустимые пределы изменения запасов красителей;

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

2.1.8 оценить целесообразность введения в план производства выпуск ткани с разновидностью рисунка Р5, если нормы затрат красителей на 1 единицу ткани соответственно равны: 6; 2; 1; 4; 4; и доход, ожидаемый от реализации новой ткани равен 5000 руб;

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

Составляем экономико – математическую модель задачи.

Обозначим:

Х₁ – план выпуска продукции вида Р₁;

Х₂ – план выпуска продукции вида Р₂;

Х₃ – план выпуска продукции вида Р₃;

Х₄ – план выпуска продукции вида Р₄.

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

Решаем задачу с помощью симплекс –таблицы.

Таблица 1

Таблица 2

Таблица 3

Таблица 4

Отрицательных оценок в оценочной строке нет; решение оптимально. Оптимальный опорный план:

Х_опт=(33,06; 2,2; 0; 1,173; 0; 0; 0; 0; 0)^Т

F_max=4696,05 руб.

Для получения максимальной прибыли 4696,05 руб. необходимо выпустить продукции вида Р1 33,06 м ткани, Р2 2,2 м и Р4 1,173 м.

Продукция видов Р₃ является убыточным; его производство является нерентабельным.

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

- теневая цена ресурса I

- теневая цена ресурса II

- теневая цена ресурса Ш

- теневая цена ресурса IV

- теневая цена ресурса V

→min

≥

Т.к. в прямой задаче все неравенства в системе сильных ограничений вида “≤”, найдем решение двойственной задачи по результатам решения прямой задачи.

=4696,05 руб.

y₁=0

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=

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

Составим матрицу 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 раз выехать. Составить экономико-математическую модель задачи и решить задачу методом ветвей и границ.

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

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

Определяем h²= 0;

Оценка по {4,2}=5464

Определяем пару для ветвления

Q₁₃ = 715+730=1445;

Q₂₁ = 0;

Q₂₄ = 839;

Q₃₁ = 114;

Q₅₆ = 114+961=1075;

Q₆₅ = 345+730=1075

Подходящую оценку имеет маршрут: Q21=0

w = w(4;2)+ Q21= 6294

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

Определяем h³= 114+725=839;

Оценка по {2,1}=5464+839=6303

Определяем пару для ветвления

Q₁₃ = 212+730=942;

Q₃₄ = 212;

Q₃₆ = 0;

Q₅₆ = 952;

Q₆₅ = 231+721=952

Подходящую оценку имеет маршрут: Q13=942

w = w(2;1)+ Q13= 6294+942=7236

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

Определяем h⁴= 0;

Оценка по {1,3}= 6303

Определяем пару для ветвления

Q₃₄ = 721;

Q₃₆ = 0;

Q₅₆ = 952;

Q₆₅ = 231

Подходящую оценку имеет маршрут: Q36=0

w = w(1;3)+ Q36= 7236

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

Матрица приведена

Определяем h⁵=952;

Оценка w{3,6}=6303+721=7024

5464 6303 6303 7024

G₀ 4,2 2,1 1,3 3,6

6294 6294 7236 7236

4,2 2,1 1,3 3,6

Нужный маршрут Казань – Ереван – Донецк – Житомир – Каунас – Калининград.

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

Возвращаемся к исходной матрице расстояний и полагаем в ней

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

h⁶=5634

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

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

Q₁₃ = 660+9=669;

Q₂₁ = 0;

Q₂₄ = 839;

Q₃₁ = 114;

Q₄₆ =9;

Q₅₆ = 961;

Q₆₅ = 231+730=961

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

w = h⁶+Q56= 5634 + 961 = 6595

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

Определяем h⁷= 669;

Оценка по {5,6}=5634+669=6303

Определяем пару для ветвления

Q₁₂ = 806;

Q₁₃ = 0;

Q₂₁ = 0;

Q₂₄ = 839;

Q₃₁ = 345;

Q₄₃ = 98;

Q₆₅ = 730+345=1075

Подходящую оценку имеет маршрут: Q24=839

w = w(5;6)+ Q24= 6595+839=7434

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

Определяем h⁸= 0;

Оценка по {2,4}=6303

Определяем пару для ветвления

Q₁₂ = 806;

Q₁₃ = 0;

Q₃₁ = 98+345=443;

Q₄₃ = 98;

Q₆₅ = 730+222=952

Подходящую оценку имеет маршрут: Q12=806

w = w(2;4)+ Q12= 7434+806=8240

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

Определяем h⁹= 0;

Оценка по {1,2}= 6303

Определяем пару для ветвления

Q₃₁ = 98+345=443;

Q₄₃ = 730+98=828;

Q₆₅ = 730+222=952

Подходящую оценку имеет маршрут: Q43=828

w = w(4;3)+ Q12= 8240+828=9068

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

Матрица приведена

Определяем h¹⁰=0;

Оценка w{4,3}=6303

Т.к. получена матрица 2x2 и оценка последнего маршрута не больше всех тупиковых ветвей, то решение оптимально. Маршрутами для завершения могут быть пары (3,1), (6,5).

Составим геометрическую интерпретацию найденного маршрута

5634 5634 6303 6303 6303 6303

G₀ 5,6 2,4 1,2 4,3 3,1

6,5

6595 7434 8240 9068

10744

5,6 2,4 1,2 4,3 3,1 10744

6,5

Нужный маршрут Казань – Ереван – Донецк – Житомир – Каунас – Калининград; x₄₂=1, x₂₁=1, x₁₃=1, x₃₆=1, x₆₅=1, F=5232 км.

Задание №3

На предприятии необходимо выполнить последовательно 12 видов работ (R1÷R12). 12 сотрудников предприятия (S1÷S12) затрачивают на выполнение каждого вида работ различное время в часах. Распределить работников по видам работ так, чтобы общее время на выполнение работ было минимально. Очередность выполнения работ не имеет значения.

Составить экономико-математическую модель задачи и решить задачу с помощью венгерского алгоритма.

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

F = 10x₁₁ + 2x₁₂ + 3x₁₃ + 7x₁₄ + 7x₁₅ + 9x₁₆ + 10x₁₇ + 10x₁₈ + 10,5x₁₉ + 12x₁₁₀ + 14,5x₁₁₁ + 7x₁₁₂ + 12x₂₁ + x₂₂ + 5x₂₃ + 6,5x₂₄ + 8x₂₅ + 10,5x₂₆ + 8x₂₇ + 9x₂₈ + 12x₂₉ + 11x₂₁₀ + 15x₂₁₁ + 7,5x₂₁₂ + 11x₃₁ + x₃₂ + 3,5x₃₃ + 6,5x₃₄ + 8x_3,5 + 10,5x₃₆ + 8x₃₇ + 9x₃₈ + 12x₃₉ + 11x₃₁₀ + 15x₃₁₁ +17,5x₃₁₂ + 11x₄₁ + 2x₄₂ + 4x₄₃ + 6,5x₄₄ + 8x₄₅ + 11x₄₆ + 8x₄₇ + 9,5x₄₈ + 12x₄₉ + 12x₄₁₀ + 15,5x₄₁₁ + 7,5x₄₁₂ + 10x₅₁ + 2,5x₅₂ + 4x₅₃ + 5x₅₄ + 8x₅₅ + 11,5x₅₆ + 8,5x₅₇ + 8x₅₈ + 11x₅₉ + 12x₅₁₀ + 15,5x₅₁₁ + 6x₅₁₂ + 10x₆₁ + 2,5x₆₂ + 4,5x₆₃ + 5x₆₄ + 7,5x₆₅ + 10,5x₆₆ + 8,5x₆₇ + 8x₆₈ + 11x₆₉ + 12x₆₁₀ + 15x₆₁₁ + 6x₆₁₂ + 9,5x₇₁ + x₇₂ + 4x₇₃ + 5,5x₇₄ + 7,5x₇₅ + 10,5x₇₆ +8,5x₇₇ + 9x₇₈ + 11x₇₉ + 12x₇₁₀ + 15,5x₇₁₁ + 6x₇₁₂ + 9,5x₈₁ + 1x₈₂ + 3,5x₈₃ + 6,5x₈₄ + 7x₈₅ + 10,5x₈₆ + 10x₈₇ + 10,5x₈₈ + 12x₈₉ + 10x₈₁₀ + 15,5x₈₁₁ + 6x₈₁₂ + 9,5x₉₁ + 3x₉₂ + 3x₉₃ + 3,5x₉₄ + 6,5x₉₅ + 7x₉₆ + 11x₉₇ + 10,5x₉₈ + 10x₉₉ +12x₉₁₀ +15x₉₁₁ + 7x₉₁₂ + 8x₁₀₁ + 3x₁₀₂ + 3x₁₀₃ + 6,5x₁₀₄ + 7x₁₀₅ + 11x₁₀₆ + 10,5x₁₀₇ + 10x₁₀₈ + 9,5x₁₀₉ + 12x₁₀₁₀ + 15,5x₁₀₁₁ + 6,5x₁₀₁₂ + 8x₁₁₁ + 3x₁₁₂ + 3x₁₁₃ + 6,5x₁₁₄ + 7,5x₁₁₅ + 10x₁₁₆ + 11x₁₁₇ + 10,5x₁₁₈ + 9,5x₁₁₉ + 12x₁₁₁₀ + 15,5x₁₁₁₁ + 6,5x₁₁₁₂ + 8x₁₂₁ + 3x₁₂₂ + 3x₁₂₃ + 6,5x₁₂₄ + 7,5x₁₂₅ + 9x₁₂₆ + 11x₁₂₇ + 10,5x₁₂₈ + 9,5x₁₂₉ + 12x₁₂₁₀ + 15x₁₂₁₁ + 6,5x₁₂₁₂ min

По исходным данным составляем таблицу

Преобразуем составляемую таблицу

1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 4 5 6 7 8 9 10 11 12

Произведем назначение каждого сотрудника на один из видов работ:

S₁→R₂; S₂→?; S₃→?; S₄→R₇; S₅→R₄; S₆→R₈; S₇→?; S₈→?; S₉→R₅; S₁₀→R₁; S₁₁→R₃; S₁₂→R₉

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

Делаем дальнейшее преобразование таблицы.

Минимальное число, через которое не проходит ни одна линия: 0,5

1 2 3 4 5 6 7 8 9 10 11 12

Произведем назначение каждого сотрудника на один из видов работ:

S₁→R₁₁; S₂→R₂; S₃→?; S₄→R₇; S₅→R₄; S₆→R₈; S₇→?; S₈→?; S₉→R₅; S₁₀→R₁; S₁₁→R₃; S₁₂→R₉

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

Делаем дальнейшее преобразование таблицы.

Минимальное число, через которое не проходит ни одна линия: 0,5

1 2 3 4 5 6 7 8 9 10 11 12

Произведем назначение каждого сотрудника на один из видов работ:

S₁→R₁₁; S₂→R₂; S₃→?; S₄→R₇; S₅→R₄; S₆→R₈; S₇→?; S₈→?; S₉→R₅; S₁₀→R₁; S₁₁→R₃; S₁₂→R₉

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

Делаем дальнейшее преобразование таблицы.

Минимальное число, через которое не проходит ни одна линия: 0,5

1 2 3 4 5 6 7 8 9 10 11 12

Произведем назначение каждого сотрудника на один из видов работ:

S₁→R₆; S₂→R₁₁; S₃→R₂; S₄→R₇; S₅→R₄; S₆→R₈; S₇→R₁₂; S₈→?; S₉→R₁₀; S₁₀→R₅; S₁₁→R₃; S₁₂→R₁

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

Делаем дальнейшее преобразование таблицы.

Минимальное число, через которое не проходит ни одна линия: 0,5

1 2 3 4 5 6 7 8 9 10 11 12

Произведем назначение каждого сотрудника на один из видов работ:

S₁→R₆; S₂→R₁₁; S₃→R₂; S₄→R₇; S₅→R₄; S₆→R₈; S₇→R₁₂; S₈→R₁₀; S₉→R₅; S₁₀→R₃; S₁₁→R₁; S₁₂→R₉

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

И окончательно:

1 2 3 4 5 6 7 8 9 10 11 12

При этом время, затрачиваемое на выполнение всех работ, составит:

88,5 часов.

Альтернативных решений нет, решение единственное.