МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
Г.Д. Чернышова, И.Н. Булгакова
ДИСКРЕТНЫЕ
И ВЕРОЯТНОСТНЫЕ МОДЕЛИ
(Модели. Алгоритмы)
Методическое пособие для вузов
Воронеж
Издательский дом ВГУ
2014
Стр.1
1 МАТЕМАТИЧЕСКИЕ МОДЕЛИ
ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ
I. Целочисленные задачи линейного программирования
1) Произвольная задача (ЦЗЛП).
A b ,
x =
x ≥ 0 ,
j −
∑c xj
j=1
x целые числа,
n
j =1,2,...,n ,
j →max ().min
(1.1)
(1.2)
(1.3)
(1.4)
Требование целочисленности переменных появляется, например, в задачах
оптимального планирования на производствах, специализирующихся
по выпуску штучных изделий.
2) Задача о ранце.
∑
=
x j = { }1,0 ,
n
a x A ,
j
∑
=
j 1
n
j 1
Такая задача возникает при выборе набора предметов максимальной
стоимости для погрузки в некоторую тару (ранец) при ограничениях на
объем или на «грузоподъемность».
Обобщением этой задачи является многомерная задача о ранце, в которой
присутствует несколько ограничений. Если, кроме того, каждый предмет
имеется в количестве нескольких единиц, то требование (1.5) заменяется
на требование целочисленности. В таком случае задача о ранце превращается
в целочисленную задачу линейного программирования с неотрицательной
матрицей ограничений.
II. Задачи комбинаторного типа
1) Задача о назначениях (задача выбора).
xij = { }1,0 ,
∑ =
=
n
xij
i 1
3
1,
i =1,2,..., n,
(1.8)
(1.9)
j ≤
c j x →max.
j
(1.5)
(1.6)
(1.7)
Стр.3
где M = min , {a b },
ij
i
j
xij ≥ 0,
yij = { } ∀i, j . (1.30)
0,1
Все рассмотренные задачи (кроме задачи о назначениях) относятся к
классу труднорешаемых. Для их решения не известны алгоритмы полиномиальной
сложности. Все точные алгоритмы (ищущие точное решение задачи)
обладают экспоненциальной сложностью.
Для отыскания точного решения используют, как правило, методы типа
ветвей и границ, динамическое программирование и методы отсечений (секущих
плоскостей).
УПРАЖНЕНИЯ
1. Доказать, что любая целочисленная задача математического программирования
может быть эквивалентно переписана как задача с булевыми
переменными.
2. Записать математическую модель задачи коммивояжера с использованием
переменных
⎪
⎨
⎧
⎩
⎪
ij
ij
x =1, если i я город стоит в перестановке на j м месте,
x = 0 в противном случае.
−
−
3. Сформулировать условие совместности в задачах о ранце, о назначениях,
о минимальном покрытии.
6
Стр.6
2 ЗАДАЧА О НАЗНАЧЕНИЯХ
ВЕНГЕРСКИЙ МЕТОД РЕШЕНИЯ
2.1 Постановка задачи. Некоторые свойства
i i, 1,= ) на n мест работы (каждому из них отвечает индекс j j, = ). При
этом известна стоимость ijc затрат, связанных с назначением i-го претен1,
n
Пусть имеются n претендентов (каждому из них отвечает индекс
n
дента на j-е место. Требуется распределить претендентов по рабочим местам
так, чтобы каждый претендент занял одно место, каждое место было
занято одним претендентом, и так, чтобы связанные с этим распределением
суммарные затраты были минимальными.
Для получения математической записи задачи о назначениях можно
ввести 2n переменных следующим образом:
⎩
xij
=
⎨
⎧
1,
0,
если i й претендент назначен на j е место,
в противном случае.
−
Теперь задача принимает следующий вид:
n
Ω ∑
∑
⎨
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎩
0 ≤ xij ∀≤1,
Замечание. Если последние ограничения заменить условиями вида
, ,
i j
то полученная задача является частным случаем транспортной
задачи, у которой, как известно, оптимальное решение всегда существует.
Таким образом, задачу о назначениях можно решать методом потенциалов,
причем в соответствии со спецификой этого метода можно утверждать,
что решением является 2n -мерный вектор, или матрица порядка n Ч n,
элементы которой равны 0 или 1. Это означает, что полученный ответ будет
также являться ответом в исходной задаче о назначениях. Однако начальная
базисная точка, полученная, например, по методу северо-западного угла,
содержит не m + n – 1 = 2n – 1, а всего лишь n ненулевых компонент, равных
1, cледовательно, при
n ≥ 2 этот план становится вырожденным. Как
известно, это обстоятельство существенно усложняет вычислительную
процедуру решения транспортной задачи. По этой причине для решения за7
i=1
n
j=1
xij
∈
L( X ) =
n
∑∑
==
n
i 1 j 1
xij =1,
xij =1,
j =1,n,
{0,1}, , 1, .
1, ,
i =
i j =
n
n
ij
−
c xij →min ,
Стр.7
дачи о назначениях существуют специальные методы. Рассмотрим один из
них, который носит название венгерский метод.
В дальнейшем нам потребуется следующее определение.
Определение. Любые k элементов (k = 2, ) матрицы C = )( ijc порядка
n
n Ч n называются независимыми, если всякие два из них располагаются в
разных строках и в разных столбцах.
Теперь можно переформулировать задачу о назначениях следующим
образом: среди 2n элементов данной матрицы C найти n независимых
элементов
cis sj , s
=1, , таких, что сумма ∑
=
n
n
s 1
ci j ss
минимальна.
Для обоснования венгерского метода потребуются следующие понятия
и утверждения.
Матрицей назначений порядка n Ч n называется матрица, в которой
имеются n независимых единиц и n − = nnn
2
( 1 ) нулей. Иными словами,
−
это матрица, у которой в каждой строке и в каждом столбце имеется ровно
одна единица, а остальные элементы являются нулями.
Обозначим через Ω допустимое множество задачи о назначениях. В
соответствии с определением матриц назначений можно утверждать, что
множество таких матриц составляет допустимое множество Ω.
Замечание. Все задачи о назначениях размера n Ч n имеют одно и то
же допустимое множество и отличаются друг от друга только коэффициентами
целевой функции, т.е. матрицей C= )( ij
c.
Теорема 1. Если элементы матриц C и D порядка n×n связаны равенствами
dij c= + + , то задачи о назначениях с данными матрицами C и D
ij
i
j
эквивалентны, т.е. множества их решений (оптимальных точек) совпадают.
Доказательство. Во-первых, как отмечалось выше, допустимые
множества обеих задач совпадают. Во-вторых, сравним значения целевых
функций обеих задач, используя ограничения. В результате получаем цепочку
равенств
=
∑∑ ∑∑ ∑∑ ∑∑ ∑ ∑ ∑∑
∑∑ ∑∑ ∑∑ ∑∑
n
n
11 11 11 11
j
i
j
j
i
i
j
n
n
i==
ij ij
11j
c x +
d x =
n
ij ij
i
n
n
i==
n
11j
xij +
c x +
n
ij ij
j
n
n
i==
n
11j
xij =
i ijx +
n
n
i== == == ==
n
n
i==
ij ij
11j
c x +
j ijx =
n
i=1
i +
n
142 44 43
const
j=1
j =
n
n
i==
11j
из которой следует, что значения двух целевых функций с матрицами C и D
отличаются на постоянную F. Это означает, что минимумы этих функций достигаются
в одних и тех же точках (на одних и тех же матрицах назначений).
8
c x F ,
ij ij +
β
β
β
α
β
α
α
α
Стр.8