Уточним формулировку задачи. Дана плоская географическая карта, на которой граница каждой страны представляет собой замкнутую непрерывную кривую. Две страны называются соседними, если у них есть общая граница - участок кривой определенной длины. Требуется так раскрасить данную карту в четыре цвета, чтобы соседние страны были раскрашены в разные цвета.

Некоторые из этих задач и методы их решения рассматриваются ниже.

7.2. Задача о назначениях иди задача выбора Постановка задачи

Пусть имеется п видов работ и п претендентов (рабочих, механизмов и др.) для их выполнения, причем каждый претендент может использоваться на любой работе. Известна производительность /-го претендента на у'гй работе (с ). Требуется так распределить претендентов по работам, чтобы суммарная производительность была максимальной. При этом каждого претен дента можно назначить только на одну работу и на каждую работу можно назначить только одного претендента.

Хотя для транспортной задачи есть методы, которые проще методов решения общей задачи линейного программирования, особенности задачи о назначениях позволяют решить ее с помощью более простых приемов. Эффективным, методом решения задачи о назначениях является венгерский метод, который рассматривается ниже.

' 0*

2 2

4 0 '

1

0 1

0* 3

0

1 2

2 0*

0

1 0‘

1 3

, I

0* 1

3 3 7

Л24

--V35 "

- *43 -

Пояснения к решению задачи. Процесс нахождения оптимального варианта назначений состоит из предварительного этапа и двух итераций.