|
целочисленного программи-
рования
. Математическая модель такой задачи может быть представ-
лена уравнениями (5.9)-(5.10).
Частным случаем решения задач целочисленного программиро-
вания являются задачи, в результате решения которых управляющие
переменные могут принимать не любые целые значения, а одно из
двух: либо 0, либо 1. Распространенной задачей с булевыми перемен-
ными является задача выбора вариантов из числа заданных.
(5.9)
где Z - Множество целых чисел.
(5.10)
Использование информационных технологий, для решения
задач линейного программирования – актуальное направление как для
специалистов, занимающихся менеджментом и маркетингом, так и
для тех, кто проявляет научный интерес к решениям задач оптими-
зации.
При построении математической модели и решении задачи оп-
тимизации можно выделить следующие этапы:
1.
Определение цели оптимизации.
max(min)
x
c
f
n
1
j
j
j
,
n
,
1
j
,
Z
x
);
m
,
1
m
i
(
,
b
x
a
);
m
,
1
m
i
(
,
b
x
a
),
m
,
1
i
(
,
b
x
a
j
n
1
j
2
i
j
ij
n
1
j
2
1
i
j
ij
n
1
j
1
i
j
ij
131
2.
Определение параметров модели, т.е. заранее известных
фиксированных факторов, на значение которых исследователь не
влияет.
3.
Формирование управляющих переменных, изменяя значения
которых можно достичь поставленной цели. Значения управляющих
переменных являются решениями задачи.
4.
Определение области допустимых решений, т.е. тех ограни-
чений, которым должны удовлетворять управляющие переменные.
5.
Выявление неизвестных факторов, т.е. величин, которые мо-
гут изменяться случайным или неопределенным образом.
6.
Выражение цели через управляющие переменные, параметры
и неизвестные факторы, т.е. формирование целевой функции, назы-
ваемой также критерием эффективности или критерием оптими-
зации.
Рассмотрим пример задачи о назначениях, оптимальное реше-
ние которой может быть найдено с помощью построения и расчета
соответствующих математических моделей.
Математическая модель задачи о назначениях формулируется
следующим образом. Имеется
работ и
кандидатов для их выпол-
нения. Затраты i-го кандидата на выполнение
- ой работы равны
. Каждый кандидат может быть назначен только на
одну работу, и каждая работа может быть выполнена только од-
ним кандидатом. Требуется назначить кандидатов на работы таким
образом, чтобы затраты на выполнение работ были минимальны.
Цель: Минимизация затрат на выполнение работ.
Параметры модели:
- затраты на выполнение i- ым кандидатом на j-ой работы,
.
n- число работ и число кандидатов на их выполнение.
Управляющие переменные:
– переменная, значение которой
равно 1, если i-ый кандидат выполняет j-ую работу ,
, в противном случае равно 0.
Ограничения задачи: Каждый кандидат выполняет только одну
работу, каждая работа может быть выполнена только одним кан-
дидатом.
Критерий оптимальности: Минимизация суммарных затрат на
выполнение работ.
Таким образом, математическая модель задачи о назначениях
имеет следующий вид:
132
(5.11)
(5.12)
Решение задачи оптимизации назначений рассмотрим на сле-
дующем примере. Институт получил гранты на выполнение четырех
исследовательских проектов. Выходные результаты первого проек-
та являются входными данными для второго проекта, результаты
третьего проекта используются четвертым проектом. В качестве
научных руководителей проектов рассматриваются кандидатуры
четырех ученых, обладающих различным опытом и способностями.
Каждый ученый оценил время, необходимое ему для реализации про-
екта. Матрица времен приведена ниже:
В
- ой строке
- столбце стоит время
на выполнение -ым
ученым
го проекта. Продолжительность времени задана в меся-
цах. Пусть
=1 , если -ый ученый – научный руководитель
- проек-
та, а в противном случае.
,
Требуется выбрать научного руководителя для выполнения про-
екта так, чтобы суммарное время выполнения всех проектов было
минимальным.
Целевая функция задачи имеет вид в соответствии с формулой
4.11:
Для выбора научного руководителя необходимо создать табли-
цу, содержащую исходные данные и зависимости математической
зависимости (рисунке 5.1).
133
Do'stlaringiz bilan baham: |
