Динамическое программирование (стр. 2 из 10)

k ( в боковой бомбодержатель), ^y_ijk - в центральный бомбодержатель.

Задача о ранце (о контейнерах, о перевозках).

Имеется j 1, n предметов веса ^a_j ценностью ^c _j . Задана грузоподъемность контейнера A.

Надо так загрузить контейнер предметами, чтобы суммарная стоимость их была максимальной при условии, что предмет может загружаться в количестве 1 штуки или не загружаться.

Обозначим переменные:

1, еслиберем jыйпредмет, x _j

0, иначе.

Модель:

max

Примечания:

- Если ограничений несколько, то будет многомерная задача;

- Если предмет может загружаться в нескольких экземплярах, но не больше ^d _j , тогда вместо требования бивалентности будем иметь:

j .

x _j

2) Модели задач размещения.

Простейшая модель реконструкции.

ûé âàðèàíò ïðèíÿò

Данная модель реализует следующую постановку: предлагается j 1, n - способов вариантов реконструкции каждого из k 1, p предприятий, производящих i 1, n видов продукции.

Заданы удельные в единицу времени (имеется ввиду отрезок планирования) выпуски продукции по способам ^a_ij и приведены затраты на осуществление реконструкции по вариантам j ^c_j , N ^k - множество номеров вариантов реконструкции предприятия k . N ^k не пересекаются, т.е. N ^S S .

Примечание. Если варианты в N ^k пересекаются, то вводится двойная нумерация:

1, если реконструируетсяk приварианте j x_kj

0, иначе

Выбрать такой набор вариантов реконструкции для совокупности предприятий числом p , чтобы затраты на осуществление реконструкции были минимальными и при условии, что требуемый объем продукции i будет произведен.

В случае, когда:

- речь идет не о реконструкции, а о основном строительстве, тогда в подмножестве номеров вариантов N ^k будет только один- вариант строительства;

- задача размещения в этом случае осуществляется или не осуществляется строительство по вариан n n

ту k . Тогда условие выбора единственного варианта

1, p заменяется на 1 .

Приведенная задача не учитывает интересы потребителей (потребности предприятий и оптимизации транспортных потоков). Задачи, которые это учитывают называются производственно-транспортными.

3) Модели комбинаторных задач

Задача о развитии экономической зоны

Задача о развитии экономической зоны – это расширенная задача выбора проектных вариантов.

Пусть имеется m, i 1, m предприятий вновь проектируемых или реконструируемых. Предприятия должны выпускать n видов продукции j 1, n в количествах не менее ^b_j .

Каждое из предприятий i можно реконструировать по одному из заранее разработанных r проектных вариантов k 1, r (если количество вариантов для предприятий разное, то r

Каждый k -ый вариант для предприятия i характеризуется показателями величины выпуска продукции ^a_ij^k по вариантам проектов и заданы приведенные затраты на осуществление проекта ^R_i^k .

Требуется с минимальными затратами на строительство или реконструкцию предприятий удовлетворить потребности региона по всем видам продукции j в объемах ^b_j .

Задача о развитии экономической зоны – это задача выбора проектных вариантов, в которой планирование развития экономической зоны необходимо выполнить с учетом размещения пунктов потребления продукции и осуществления возможных объемов перевозок. Чтобы это реализовать, дополним постановку так:

Пусть в регионе, представляющий собой совокупность n городов ( i 1, m ) (предприятий), каждое предприятие может перевезти в другой город количество продукции. В регионе существуют j 1, n предприятий, потребляющих однородную продукцию в количествах _j .

Заданы затраты на перевозку ^c_ij . Требуется так оптимизировать строительство и реконструкцию предприятий в зоне, чтобы суммарные затраты на строительство предприятий и транспортировку продукции были минимальны.

Введем переменную ^y_ij -объемы перевозок предприятия i к потребителю j . Модель:

Получили частичную ЦЗП, которая решается, например, методом Балаша.

Модификациями транспортной задачи являются: ТЗ с ограниченными пропускными способностями коммуникаций, ТЗ с запретами.

Многие специальные ТЗ сводятся к классической ТЗ: ТЗ с перевалочными пунктами или с промежуточной обработкой, ТЗ с резервированием, ТЗ с дополнительными ограничениями.

К задачам транспортного типа относятся также задача о максимальном потоке и задача о кратчайшем пути. Они называются ТЗ в сетевой постановке.

Задача о коммивояжере

Рассмотрим задачу о коммивояжере (КВ). Есть ( n 1) городов, ^c_ij - матрица расстояний. Из города номер 0 выезжает КВ. Надо найти путь минимальной длины, проходящий раз и только раз через каждый город и заканчивался бы в нулевом.

1, переходизiв jесть x_ij

0, иначе Модель:

1) .

Полученное условие не справедливо, следовательно, условие замкнутости не позволяет затратить часть звеньев на подцикл.

Задача о назначении

Если условие замкнутости отсутствует, то имеем модель о назначении – есть i 1, nкандидатов на

1, n рабочих должностей, если i -ый кандидат назначается на j , то ^c_j - затраты. Надо так провести все назначения, чтобы суммарные затраты были минимальными:

.

Задачи теории расписаний (календарного планирования)

Задача календарного планирования относится к задачам теории расписания. Имеется m, i 1, m станков и n, j 1, n деталей.

Каждая деталь должна пройти обработку на m станках в определенной последовательности, причем операции неделимы.

Задана матрица A ^a_{ij i}^j ₁¹_,^,_mⁿ , которая интерпретируется как время для обработки j -ой детали на i -ом станке.

Надо найти такую последовательность обработки деталей, которая минимизировала бы продолжительность производственного цикла (общее время выполнения всех работ).

Введем обозначение ^x_ij - моменты начала обработки j -ой детали на i -ом станке.

Тогда, календарный план есть совокупность элементов ^x_ij , а продолжительность производственного цикла – общее время выполнения всех работ не складывается из ^x_ij . Ограничения:

1) деталь проходит обработку в определенной последовательности. Пусть деталь j сначала обрабатывается на станке i в продолжительности времени ^a_ij , а затем идет на станок k .

Тогда моменты начала обработки - ^x_kj ^x_ij ^a_ij (1)