Реферат Расчётно-графическое задание
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
от 25%
договор
Цель и назначение работы
Целью выполнения расчетно-графической работы является закрепление знаний, умения и навыков, необходимых для математического моделирования социально-экономических процессов. А также, приобретение навыков работы с программными пакетами.
Задание на выполнение РГР
Задание №1
На фабрике с помощью 5 видов красителей (А1-А5) создается 4 разновидности рисунков для тканей (Р1-Р4). При известной отпускной стоимости
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 показать, допустимо ли увеличение всех дефицитных красителей одновременно на
Номер варианта | Вид красителей | Разновидность рисунка. Расход красителей на окраску | Запасы красителей (кг). | |||
Р1 | Р2 | Р3 | Р4 | |||
8 | А1 | 7 | 6 | 5 | 21 | 500 |
А2 | 9 | 13 | 17 | 16 | 1402 | |
А3 | 5 | 7 | 15 | 19 | 203 | |
А4 | 17 | 5 | 24 | 23 | 600 | |
А5 | 4 | 7 | 9 | 2 | 150 | |
Стоимость одного метра ткани (руб.) | 124 | 125 | 195 | 274 | |
Составляем экономико – математическую модель задачи.
Обозначим:
Х1 – план выпуска продукции вида Р1;
Х2 – план выпуска продукции вида Р2;
Х3 – план выпуска продукции вида Р3;
Х4 – план выпуска продукции вида Р4.
Приведем задачу к каноническому виду:
Решаем задачу с помощью симплекс –таблицы.
Таблица 1
Базис | Сб | Опорное решение | С1 | С2 | С3 | С4 | С5 | С6 | С7 | С8 | С9 |
124 | 125 | 195 | 274 | 0 | 0 | 0 | 0 | 0 | |||
А1 | А2 | А3 | А4 | А5 | А6 | А7 | А8 | А9 | |||
А5 | 0 | 500 | 7 | 6 | 5 | 21 | 1 | 0 | 0 | 0 | 0 |
А6 | 0 | 1402 | 9 | 13 | 17 | 16 | 0 | 1 | 0 | 0 | 0 |
А7 | 0 | 203 | 5 | 7 | 15 | 19 | 0 | 0 | 1 | 0 | 0 |
А8 | 0 | 600 | 17 | 5 | 24 | 23 | 0 | 0 | 0 | 1 | 0 |
А9 | 0 | 150 | 4 | 7 | 9 | 2 | 0 | 0 | 0 | 0 | 1 |
∆j | F=0 | -124 | -125 | -195 | -274 | 0 | 0 | 0 | 0 | 0 |
Таблица 2
Базис | Сб | Опорное решение | С1 | С2 | С3 | С4 | С5 | С6 | С7 | С8 | С9 |
124 | 125 | 195 | 274 | 0 | 0 | 0 | 0 | 0 | |||
А1 | А2 | А3 | А4 | А5 | А6 | А7 | А8 | А9 | |||
А5 | 0 | 275,6 | 1,5 | -1,7 | -11,6 | 0 | 1 | 0 | -1,1 | 0 | 0 |
А6 | 0 | 1231,1 | 4,8 | 7,1 | 4,4 | 0 | 0 | 1 | -0,8 | 0 | 0 |
А4 | 274 | 10,7 | 0,3 | 0,4 | 0,8 | 1 | 0 | 0 | 0,05 | 0 | 0 |
А8 | 0 | 354,3 | 10,9 | -3,4 | 5,8 | 0 | 0 | 0 | -1,2 | 1 | 0 |
А9 | 0 | 128,6 | 3,4 | 6,2 | 7,4 | 0 | 0 | 0 | -0,1 | 0 | 1 |
∆j | F=2927,47 | -51,9 | -24,1 | 21,3 | 0 | 0 | 0 | 14,4 | 0 | 0 |
Таблица 3
Базис | Сб | Опорное решение | С1 | С2 | С3 | С4 | С5 | С6 | С7 | С8 | С9 |
124 | 125 | 195 | 274 | 0 | 0 | 0 | 0 | 0 | |||
А1 | А2 | А3 | А4 | А5 | А6 | А7 | А8 | А9 | |||
А5 | 0 | 227,9 | 0 | -1,3 | -12,4 | 0 | 1 | 0 | -0,9 | -0,1 | 0 |
А6 | 0 | 1076,1 | 0 | 8,6 | 1,8 | 0 | 0 | 1 | -0,3 | -0,4 | 0 |
А4 | 274 | 2,2 | 0 | 0,5 | 0,6 | 1 | 0 | 0 | 0,08 | -0,02 | 0 |
А1 | 124 | 32,4 | 1 | -0,3 | 0,5 | 0 | 0 | 0 | -0,11 | 0,09 | 0 |
А9 | 0 | 16,2 | 0 | 7,4 | 5,6 | 0 | 0 | 0 | 0,28 | -0,03 | 1 |
∆j | F=4606,81 | 0 | -40,5 | 49 | 0 | 0 | 0 | 8,7 | 4,7 | 0 |
Таблица 4
Базис | Сб | Опорное решение | С1 | С2 | С3 | С4 | С5 | С6 | С7 | С8 | С9 |
124 | 125 | 195 | 274 | 0 | 0 | 0 | 0 | 0 | |||
А1 | А2 | А3 | А4 | А5 | А6 | А7 | А8 | А9 | |||
А5 | 0 | 230,7 | 0 | 0 | -11,4 | 0 | 1 | 0 | -0,89 | -0,19 | 0,17 |
А6 | 0 | 1057,07 | 0 | 0 | -4,71 | 0 | 0 | 1 | -0,64 | -0,07 | -1,17 |
А4 | 274 | 1,173 | 0 | 0 | 0,307 | 1 | 0 | 0 | 0,065 | -0,005 | -0,061 |
А1 | 124 | 33,06 | 1 | 0 | 0,77 | 0 | 0 | 0 | -0,1 | 0,08 | 0,04 |
А2 | 125 | 2,2 | 0 | 1 | 0,76 | 0 | 0 | 0 | 0,038 | -0,04 | 0,14 |
∆j | F=4696,05 | 0 | 0 | 79,64 | 0 | 0 | 0 | 10,22 | 2,99 | 5,5 |
Отрицательных оценок в оценочной строке нет; решение оптимально. Оптимальный опорный план:
Хопт=(33,06; 2,2; 0; 1,173; 0; 0; 0; 0; 0)Т
Fmax=4696,05 руб.
Для получения максимальной прибыли 4696,05 руб. необходимо выпустить продукции вида Р1 33,06 м ткани, Р2 2,2 м и Р4 1,173 м.
Продукция видов Р3 является убыточным; его производство является нерентабельным.
составим двойственную задачу.
- теневая цена ресурса I
- теневая цена ресурса II
- теневая цена ресурса Ш
- теневая цена ресурса IV
- теневая цена ресурса V
→min
≥
Т.к. в прямой задаче все неравенства в системе сильных ограничений вида “≤”, найдем решение двойственной задачи по результатам решения прямой задачи.
=4696,05 руб.
y1=0
y2=0
y3=10,22
y4=2,99
y5=5,5
Дефицитным являются ресурсы III, IV и V.
Недефицитными являются ресурсы I, II.
Недефицитные ресурсы недоиспользуются:
I ресурс на 230,7 кг;
II ресурс на 1057,07 кг
При увеличении запаса III ресурса на 1 ед. (204 кг) можно получить увеличение прибыли на 10,22 руб. она составит F=4706,27 руб. При этом план выпуска продукции 4 надо увеличить на 0,065 т.е. x4=1,238, продукции 1 надо увеличить на -0,1 т.е. x1=2,1, продукции 2 надо увеличить на 0,038 т.е. x2=33,098. В этом случае недефицитные ресурсы будут недоиспользоваться:
1 ресурс на 0,89; его недоиспользование составит 231,69 кг;
2 ресурс на 0,64; его недоиспользование составит 1057,71 кг
Покажем допустимые пределы изменения запасов ресурсов.
Составим матрицу Р
и вектор столбец
Найдем матрицу P
Р-1(b+∆b)= =
Покажем допустимые пределы изменения цен на выпускаемые виды продукции.
p-1(c+∆c)
Для выполнения данного пункта необходимо решить двойственную задачу симплекс-методом.
Приводим задачу к каноническому виду
F*= - 500y1-1402y2-203y3-600y4-150y5+0y6+0y7+0y8+0y9→max
7y1+9y2+5y3+17y4+4y5-y6=124
6y1+13y2+7y3+5y4+7y5-y7=125
5y1+17y2+15y3+24y4+23y5-y8=195
21y1+16y2+19y3+23y4+2y5-y9=274
i=
Т.к. начальный базис указать невозможно, то решаем задачу методом искусственных переменных.
G=0y1+0y2+0y3+0y4+0y5+0y6+0y7+0y8+0y9-y10-y11-y12-y13→min
7y1+9y2+5y3+17y4+4y5-y6+y10=124
6y1+13y2+7y3+5y4+7y5-y7+y11=125
5y1+17y2+15y3+24y4+9y5-y8+y12=195
21y1+16y2+19y3+23y4+2y5-y9+y13=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:
∆p5=6*0+2*0+1*10,22+4*2,99+4*5,5-5000=-4955,82
Т.к. ∆р5<0, то есть смысл ввести в план производства выпуск ткани с разновидностью рисунка р5.
Определяем, допустимо ли одновременное увеличение запасов дефицитных красителей на
Дефицитным является краситель А3, А4 и А5. Значит Db3=10, Db4=10 и Db5=10. Остальные Db1=Db2 =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= 1523x12 + 152321 + 863x13 + 863x31 + 1899x14 + 1899x41 + 1809x15 + 1809x51 + 1578x16 + 1578x61 + 2329x32 + 2329x23 + 1622x24 +1622x42 + 3275x25 + 3275x52 + 3044x26 + 3044x62 + 1801x34 + 1801x43 + 1208x35 + 1208x53 + 977x36 + 977x63 + 2023x45 + 2023x54 + 1792x46 + 1792x64 + 247x56 + 247x65 min
x12 + x13 + x14 + x15 + x16 = 1
x21 + x23 + x24 + x25 + x26 = 1
x31 + x32 + x34 + x35 + x36 = 1
x41 + x42 + x43 + x45 + x46 = 1
x51 + x52 + x53 + x54 + x56 = 1
x61 + x62 + x63 + x64 + x65 = 1
x21 + x31 + x41 + x51 + x61 = 1
x12 + x32 + x42 + x52 + x62 = 1
x13 + x23 + x43 + x53 + x63 = 1
x14 + x24 + x34 + x54 + x64 = 1
x15 + x25 + x35 + x45 + x65 = 1
x16 + x26 + x36 + x46 + x56 = 1
Решение задачи методом ветвей и границ.
Преобразуем матрицу s
Определяем сумму приводимых элементов
h1=863+1523+863+1622+247+247+99=5464
Определяем претендентов для ветвления в множестве Y
Претендентами на ветвление могут быть S13, S21, S24, S31, S42, S56, S65
Q13 = 660+179=839;
Q21 = 0;
Q24 = 839;
Q31 = 114;
Q42 =660+170=830;
Q56 = 170+961=1131;
Q65 = 345+730=1075
Максимальную оценку имеет маршрут: Q42=830
w = h1+Q42= 5464 + 830 = 6294
Преобразуем матрицу:
Определяем h2= 0;
Оценка по {4,2}=5464
Определяем пару для ветвления
Q13 = 715+730=1445;
Q21 = 0;
Q24 = 839;
Q31 = 114;
Q56 = 114+961=1075;
Q65 = 345+730=1075
Подходящую оценку имеет маршрут: Q21=0
w = w(4;2)+ Q21= 6294
Преобразуем матрицу:
Определяем h3= 114+725=839;
Оценка по {2,1}=5464+839=6303
Определяем пару для ветвления
Q13 = 212+730=942;
Q34 = 212;
Q36 = 0;
Q56 = 952;
Q65 = 231+721=952
Подходящую оценку имеет маршрут: Q13=942
w = w(2;1)+ Q13= 6294+942=7236
Преобразуем матрицу:
Определяем h4= 0;
Оценка по {1,3}= 6303
Определяем пару для ветвления
Q34 = 721;
Q36 = 0;
Q56 = 952;
Q65 = 231
Подходящую оценку имеет маршрут: Q36=0
w = w(1;3)+ Q36= 7236
Преобразуем матрицу:
Матрица приведена
Определяем h5=952;
Оценка w{3,6}=6303+721=7024
5464 6303 6303 7024
G0 4,2 2,1 1,3 3,6
6294 6294 7236 7236
4,2 2,1 1,3 3,6
Нужный маршрут Казань – Ереван – Донецк – Житомир – Каунас – Калининград.
Т.к. оценка последнего маршрута больше оценки одного из тупиковых ветвей, а именно , то необходимо доисследовать процесс ветвления этой ветви.
Возвращаемся к исходной матрице расстояний и полагаем в ней
Определяем сумму приводимых элементов
h6=5634
Определяем претендентов для ветвления в множестве Y
Претендентами на ветвление могут быть S13, S21, S24, S31, S46, S56, S65
Q13 = 660+9=669;
Q21 = 0;
Q24 = 839;
Q31 = 114;
Q46 =9;
Q56 = 961;
Q65 = 231+730=961
Максимальную оценку имеет маршрут: Q56=961
w = h6+Q56= 5634 + 961 = 6595
Преобразуем матрицу:
Определяем h7= 669;
Оценка по {5,6}=5634+669=6303
Определяем пару для ветвления
Q12 = 806;
Q13 = 0;
Q21 = 0;
Q24 = 839;
Q31 = 345;
Q43 = 98;
Q65 = 730+345=1075
Подходящую оценку имеет маршрут: Q24=839
w = w(5;6)+ Q24= 6595+839=7434
Преобразуем матрицу:
Определяем h8= 0;
Оценка по {2,4}=6303
Определяем пару для ветвления
Q12 = 806;
Q13 = 0;
Q31 = 98+345=443;
Q43 = 98;
Q65 = 730+222=952
Подходящую оценку имеет маршрут: Q12=806
w = w(2;4)+ Q12= 7434+806=8240
Преобразуем матрицу:
Определяем h9= 0;
Оценка по {1,2}= 6303
Определяем пару для ветвления
Q31 = 98+345=443;
Q43 = 730+98=828;
Q65 = 730+222=952
Подходящую оценку имеет маршрут: Q43=828
w = w(4;3)+ Q12= 8240+828=9068
Преобразуем матрицу:
Матрица приведена
Определяем h10=0;
Оценка w{4,3}=6303
Т.к. получена матрица 2x2 и оценка последнего маршрута не больше всех тупиковых ветвей, то решение оптимально. Маршрутами для завершения могут быть пары (3,1), (6,5).
Составим геометрическую интерпретацию найденного маршрута
5634 5634 6303 6303 6303 6303
G0 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
Нужный маршрут Казань – Ереван – Донецк – Житомир – Каунас – Калининград; x42=1, x21=1, x13=1, x36=1, x65=1, F=5232 км.
Задание №3
На предприятии необходимо выполнить последовательно 12 видов работ (R1÷R12). 12 сотрудников предприятия (S1÷S12) затрачивают на выполнение каждого вида работ различное время в часах. Распределить работников по видам работ так, чтобы общее время на выполнение работ было минимально. Очередность выполнения работ не имеет значения.
Составить экономико-математическую модель задачи и решить задачу с помощью венгерского алгоритма.
№ варианта | Сотрудник | Виды работ Время, затрачиваемое каждым сотрудником на выполнение каждого вида работ | |||||||||||
R1 | R2 | R3 | R4 | R5 | R6 | R7 | R8 | R9 | R10 | R11 | R12 | ||
8 | S1 | 10 | 2 | 3 | 7 | 7 | 9 | 10 | 10 | 10,5 | 12 | 14,5 | 7 |
S2 | 12 | 1 | 5 | 6,5 | 7,5 | 10 | 8 | 9 | 10 | 11 | 14 | 7,5 | |
S3 | 11 | 1 | 3,5 | 6,5 | 8 | 10,5 | 8 | 9 | 12 | 11 | 15 | 7,5 | |
S4 | 11 | 2 | 4 | 6,5 | 8 | 11 | 8 | 9,5 | 12 | 12 | 15,5 | 7,5 | |
S5 | 10 | 2,5 | 4 | 5 | 8 | 11,5 | 8,5 | 8 | 11 | 12 | 15,5 | 6 | |
S6 | 10 | 2,5 | 4,5 | 5 | 7,5 | 10,5 | 8,5 | 8 | 11 | 12 | 15 | 6 | |
S7 | 9,5 | 1 | 4 | 5,5 | 7,5 | 10,5 | 8,5 | 9 | 11 | 12 | 15,5 | 6 | |
S8 | 9,5 | 1 | 3,5 | 6,5 | 7 | 10,5 | 10 | 10,5 | 12 | 10 | 15,5 | 6 | |
S9 | 9,8 | 3 | 3,5 | 6,5 | 7 | 11 | 10,5 | 10 | 12 | 10 | 15 | 7 | |
S10 | 8 | 3 | 3 | 6,5 | 7 | 11 | 10,5 | 10 | 9,5 | 12 | 15 | 6,5 | |
S11 | 8 | 3 | 3 | 6,5 | 7,5 | 10 | 11 | 10,5 | 9,5 | 12 | 15,5 | 6,5 | |
S12 | 8 | 3 | 3 | 6,5 | 7,5 | 9 | 11 | 10,5 | 9,5 | 12 | 15 | 6,5 |
Составляем экономико-математическую модель задачи
F = 10x11 + 2x12 + 3x13 + 7x14 + 7x15 + 9x16 + 10x17 + 10x18 + 10,5x19 + 12x110 + 14,5x111 + 7x112 + 12x21 + x22 + 5x23 + 6,5x24 + 8x25 + 10,5x26 + 8x27 + 9x28 + 12x29 + 11x210 + 15x211 + 7,5x212 + 11x31 + x32 + 3,5x33 + 6,5x34 + 8x3,5 + 10,5x36 + 8x37 + 9x38 + 12x39 + 11x310 + 15x311 +17,5x312 + 11x41 + 2x42 + 4x43 + 6,5x44 + 8x45 + 11x46 + 8x47 + 9,5x48 + 12x49 + 12x410 + 15,5x411 + 7,5x412 + 10x51 + 2,5x52 + 4x53 + 5x54 + 8x55 + 11,5x56 + 8,5x57 + 8x58 + 11x59 + 12x510 + 15,5x511 + 6x512 + 10x61 + 2,5x62 + 4,5x63 + 5x64 + 7,5x65 + 10,5x66 + 8,5x67 + 8x68 + 11x69 + 12x610 + 15x611 + 6x612 + 9,5x71 + x72 + 4x73 + 5,5x74 + 7,5x75 + 10,5x76 +8,5x77 + 9x78 + 11x79 + 12x710 + 15,5x711 + 6x712 + 9,5x81 + 1x82 + 3,5x83 + 6,5x84 + 7x85 + 10,5x86 + 10x87 + 10,5x88 + 12x89 + 10x810 + 15,5x811 + 6x812 + 9,5x91 + 3x92 + 3x93 + 3,5x94 + 6,5x95 + 7x96 + 11x97 + 10,5x98 + 10x99 +12x910 +15x911 + 7x912 + 8x101 + 3x102 + 3x103 + 6,5x104 + 7x105 + 11x106 + 10,5x107 + 10x108 + 9,5x109 + 12x1010 + 15,5x1011 + 6,5x1012 + 8x111 + 3x112 + 3x113 + 6,5x114 + 7,5x115 + 10x116 + 11x117 + 10,5x118 + 9,5x119 + 12x1110 + 15,5x1111 + 6,5x1112 + 8x121 + 3x122 + 3x123 + 6,5x124 + 7,5x125 + 9x126 + 11x127 + 10,5x128 + 9,5x129 + 12x1210 + 15x1211 + 6,5x1212 min
По исходным данным составляем таблицу
R1 | R2 | R3 | R4 | R5 | R6 | R7 | R8 | R9 | R10 | R11 | R12 | |
S1 | 10 | 2 | 3 | 7 | 7 | 9 | 10 | 10 | 10,5 | 12 | 14,5 | 7 |
S2 | 12 | 1 | 5 | 6,5 | 7,5 | 10 | 8 | 9 | 10 | 11 | 14 | 7,5 |
S3 | 11 | 1 | 3,5 | 6,5 | 8 | 10,5 | 8 | 9 | 12 | 11 | 15 | 7,5 |
S4 | 11 | 2 | 4 | 6,5 | 8 | 11 | 8 | 9,5 | 12 | 12 | 15,5 | 7,5 |
S5 | 10 | 2,5 | 4 | 5 | 8 | 11,5 | 8,5 | 8 | 11 | 12 | 15,5 | 6 |
S6 | 10 | 2,5 | 4,5 | 5 | 7,5 | 10,5 | 8,5 | 8 | 11 | 12 | 15 | 6 |
S7 | 9,5 | 1 | 4 | 5,5 | 7,5 | 10,5 | 8,5 | 9 | 11 | 12 | 15,5 | 6 |
S8 | 9,5 | 1 | 3,5 | 6,5 | 7 | 10,5 | 10 | 10,5 | 12 | 10 | 15,5 | 6 |
S9 | 9,8 | 3 | 3,5 | 6,5 | 7 | 11 | 10,5 | 10 | 12 | 10 | 15 | 7 |
S10 | 8 | 3 | 3 | 6,5 | 7 | 11 | 10,5 | 10 | 9,5 | 12 | 15 | 6,5 |
S11 | 8 | 3 | 3 | 6,5 | 7,5 | 10 | 11 | 10,5 | 9,5 | 12 | 15,5 | 6,5 |
S12 | 8 | 3 | 3 | 6,5 | 7,5 | 9 | 11 | 10,5 | 9,5 | 12 | 15 | 6,5 |
Преобразуем составляемую таблицу
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
Произведем назначение каждого сотрудника на один из видов работ:
S1→R2; S2→?; S3→?; S4→R7; S5→R4; S6→R8; S7→?; S8→?; S9→R5; S10→R1; S11→R3; S12→R9
Решение не оптимально; не можем назначить всех сотрудников на выполнение работ.
Делаем дальнейшее преобразование таблицы.
Минимальное число, через которое не проходит ни одна линия: 0,5
1 2 3 4 5 6 7 8 9 10 11 12
Произведем назначение каждого сотрудника на один из видов работ:
S1→R11; S2→R2; S3→?; S4→R7; S5→R4; S6→R8; S7→?; S8→?; S9→R5; S10→R1; S11→R3; S12→R9
Решение не оптимально; не можем назначить всех сотрудников на выполнение работ.
Делаем дальнейшее преобразование таблицы.
Минимальное число, через которое не проходит ни одна линия: 0,5
1 2 3 4 5 6 7 8 9 10 11 12
Произведем назначение каждого сотрудника на один из видов работ:
S1→R11; S2→R2; S3→?; S4→R7; S5→R4; S6→R8; S7→?; S8→?; S9→R5; S10→R1; S11→R3; S12→R9
Решение не оптимально; не можем назначить всех сотрудников на выполнение работ.
Делаем дальнейшее преобразование таблицы.
Минимальное число, через которое не проходит ни одна линия: 0,5
1 2 3 4 5 6 7 8 9 10 11 12
Произведем назначение каждого сотрудника на один из видов работ:
S1→R6; S2→R11; S3→R2; S4→R7; S5→R4; S6→R8; S7→R12; S8→?; S9→R10; S10→R5; S11→R3; S12→R1
Решение не оптимально; не можем назначить всех сотрудников на выполнение работ.
Делаем дальнейшее преобразование таблицы.
Минимальное число, через которое не проходит ни одна линия: 0,5
1 2 3 4 5 6 7 8 9 10 11 12
Произведем назначение каждого сотрудника на один из видов работ:
S1→R6; S2→R11; S3→R2; S4→R7; S5→R4; S6→R8; S7→R12; S8→R10; S9→R5; S10→R3; S11→R1; S12→R9
Решение оптимально; можем назначить всех сотрудников на выполнение работ.
И окончательно:
1 2 3 4 5 6 7 8 9 10 11 12
При этом время, затрачиваемое на выполнение всех работ, составит:
88,5 часов.
Альтернативных решений нет, решение единственное.