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

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

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

Задание №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 м ткани (г).

Запасы красителей (кг).

Р₁

Р₂

Р₃

Р₄

8

А₁

7

6

5

21

500

А₂

9

13

17

16

1402

А₃

5

7

15

19

203

А₄

17

5

24

23

600

А₅

4

7

9

2

150

Стоимость одного метра ткани (руб.)

124

125

195

274

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

Обозначим:

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

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

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

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

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

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

Таблица 1

Базис

С_б

Опорное решение

С₁

С₂

С₃

С₄

С₅

С₆

С₇

С₈

С₉

124

125

195

274

0

0

0

0

0

А₁

А₂

А₃

А₄

А₅

А₆

А₇

А₈

А₉

А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

Базис

С_б

Опорное решение

С₁

С₂

С₃

С₄

С₅

С₆

С₇

С₈

С₉

124

125

195

274

0

0

0

0

0

А₁

А₂

А₃

А₄

А₅

А₆

А₇

А₈

А₉

А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

Базис

С_б

Опорное решение

С₁

С₂

С₃

С₄

С₅

С₆

С₇

С₈

С₉

124

125

195

274

0

0

0

0

0

А₁

А₂

А₃

А₄

А₅

А₆

А₇

А₈

А₉

А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

Базис

С_б

Опорное решение

С₁

С₂

С₃

С₄

С₅

С₆

С₇

С₈

С₉

124

125

195

274

0

0

0

0

0

А₁

А₂

А₃

А₄

А₅

А₆

А₇

А₈

А₉

А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)^Т

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=

Базис

С_б

Опорное решение

С₁

С₂

С₃

С₄

С₅

С₆

С₇

С₈

С₉

500

1402

203

600

150

0

0

0

0

А₁

А₂

А₃

А₄

А₅

А₆

А₇

А₈

А₉

А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 кг каждого. Пределы изменения запасов красителей определяются из условия

Дефицитным является краситель А₃, А₄ и А₅. Значит b₃=10, b₄=10 и b₅=10. Остальные b₁=b₂ =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₆₅

₁₃ = 660+179=839;

₂₁ = 0;

₂₄ = 839;

₃₁ = 114;

₄₂ =660+170=830;

₅₆ = 170+961=1131;

₆₅ = 345+730=1075

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

w = h¹+42= 5464 + 830 = 6294

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

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

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

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

₁₃ = 715+730=1445;

₂₁ = 0;

₂₄ = 839;

₃₁ = 114;

₅₆ = 114+961=1075;

₆₅ = 345+730=1075

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

w = w(4;2)+ 21= 6294

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

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

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

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

₁₃ = 212+730=942;

₃₄ = 212;

₃₆ = 0;

₅₆ = 952;

₆₅ = 231+721=952

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

w = w(2;1)+ 13= 6294+942=7236

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

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

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

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

₃₄ = 721;

₃₆ = 0;

₅₆ = 952;

₆₅ = 231

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

w = w(1;3)+ 36= 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₆₅

₁₃ = 660+9=669;

₂₁ = 0;

₂₄ = 839;

₃₁ = 114;

₄₆ =9;

₅₆ = 961;

₆₅ = 231+730=961

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

w = h⁶+56= 5634 + 961 = 6595

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

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

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

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

₁₂ = 806;

₁₃ = 0;

₂₁ = 0;

₂₄ = 839;

₃₁ = 345;

₄₃ = 98;

₆₅ = 730+345=1075

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

w = w(5;6)+ 24= 6595+839=7434

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

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

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

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

₁₂ = 806;

₁₃ = 0;

₃₁ = 98+345=443;

₄₃ = 98;

₆₅ = 730+222=952

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

w = w(2;4)+ 12= 7434+806=8240

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

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

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

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

₃₁ = 98+345=443;

₄₃ = 730+98=828;

₆₅ = 730+222=952

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

w = w(4;3)+ 12= 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) затрачивают на выполнение каждого вида работ различное время в часах. Распределить работников по видам работ так, чтобы общее время на выполнение работ было минимально. Очередность выполнения работ не имеет значения.

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

№ варианта

Сотрудник

Виды работ

Время, затрачиваемое каждым сотрудником на выполнение каждого вида работ

R₁

R₂

R₃

R₄

R₅

R₆

R₇

R₈

R₉

R₁₀

R₁₁

R₁₂

8

S₁

10

2

3

7

7

9

10

10

10,5

12

14,5

7

S₂

12

1

5

6,5

7,5

10

8

9

10

11

14

7,5

S₃

11

1

3,5

6,5

8

10,5

8

9

12

11

15

7,5

S₄

11

2

4

6,5

8

11

8

9,5

12

12

15,5

7,5

S₅

10

2,5

4

5

8

11,5

8,5

8

11

12

15,5

6

S₆

10

2,5

4,5

5

7,5

10,5

8,5

8

11

12

15

6

S₇

9,5

1

4

5,5

7,5

10,5

8,5

9

11

12

15,5

6

S₈

9,5

1

3,5

6,5

7

10,5

10

10,5

12

10

15,5

6

S₉

9,8

3

3,5

6,5

7

11

10,5

10

12

10

15

7

S₁₀

8

3

3

6,5

7

11

10,5

10

9,5

12

15

6,5

S₁₁

8

3

3

6,5

7,5

10

11

10,5

9,5

12

15,5

6,5

S₁₂

8

3

3

6,5

7,5

9

11

10,5

9,5

12

15

6,5

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

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

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

R₁

R₂

R₃

R₄

R₅

R₆

R₇

R₈

R₉

R₁₀

R₁₁

R₁₂

S₁

10

2

3

7

7

9

10

10

10,5

12

14,5

7

S₂

12

1

5

6,5

7,5

10

8

9

10

11

14

7,5

S₃

11

1

3,5

6,5

8

10,5

8

9

12

11

15

7,5

S₄

11

2

4

6,5

8

11

8

9,5

12

12

15,5

7,5

S₅

10

2,5

4

5

8

11,5

8,5

8

11

12

15,5

6

S₆

10

2,5

4,5

5

7,5

10,5

8,5

8

11

12

15

6

S₇

9,5

1

4

5,5

7,5

10,5

8,5

9

11

12

15,5

6

S₈

9,5

1

3,5

6,5

7

10,5

10

10,5

12

10

15,5

6

S₉

9,8

3

3,5

6,5

7

11

10,5

10

12

10

15

7

S₁₀

8

3

3

6,5

7

11

10,5

10

9,5

12

15

6,5

S₁₁

8

3

3

6,5

7,5

10

11

10,5

9,5

12

15,5

6,5

S₁₂

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

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

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 часов.

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