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

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

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

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

Задание №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 часов.

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