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