Постановка задач дискретной оптимизации. Прикладные дискретные модели

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

f(x)->max(min)

g(x)<(>.=)bj, xj принадлежит Dj – множеству допустимых значений параметра xj.

Классификация задач дискретной оптимизации:

1) В зависимости от вида целевой функции и ограничений задачи делятся на линейные и нелинейные.

2) В зависимости от характера изменения параметров различают: полностью дискретные, частично-дискретные, целочисленные задачи и задачи с булевыми переменными.

Прикладные дискретные задачи.

1. Задача о ранце. Имеются предметы n-видов и для каждого j-предмета известна его ценность Cj и объём Aj. Суммарный объём всех предметов ограничен и =b.Необходимо таким образом выбрать предметы, чтобы их суммарная ценность была max, а суммарный объём не превышал бы заданного числа b. Эта Задача интерпретируется как задача загрузки ранца объёма V и называется одномерной задачей о ранце. Если в кач-ве хар-к ранца рассматривается не только объём, ной другие хар-ки bi, то получиться многомерная задача о ранце.

2. Задача о назначении. Имеется n исполнителей и m-видов работ, кот они могут выполнить. Каждый исполнитель может выполнить только одну работу, а каждая работа может быть выполнена только одним исполнителем. Известны значения Cij, характеризующие производительность i-ro работника при назначении на j-ю работу. Необходимо так распределить работников по видам работ, чтобы суммарная производ-ть была max

3 Задача о покрытии. Имеется n-предметов и m признаков, кот они могут обладать. Условия задаются матрицей А с

Переменными Aij (1, если j-й предмет обладает i признаком; 0- в противном случае)

Необходимо выбрать min набор предметов, кот в совокупности обладали всеми m признаками.