Расчётно-графическое задание (стр. 4 из 4)
Составить экономико-математическую модель задачи и решить задачу с помощью венгерского алгоритма.
| № варианта | Сотрудник | Виды работ Время, затрачиваемое каждым сотрудником на выполнение каждого вида работ | |||||||||||
| 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 часов.
Альтернативных решений нет, решение единственное.