Задачи с неделимостями

Математические модели задач дискретного программирования.

Предмет дискретного программирования

Задача минимизации вида называется задачей дискретного программирования (дискретной оптимизации), если допустимое множество дискретно. Дискретными называются конечные и счетные множества.

Чаще всего Х задается следующим образом:

,

где D – дискретное множество.

Нередко множество D разбивается по координатам

Если , то в этом случае задача дискретного программирования называется задачей целочисленного программирования.

Основной проблемой является то, что область Х является невыпуклой и несвязной. Поэтому все рассматриваемые нами методы не работают.

Отбросим требование целочисленности и округлим результат:

Существует 4 варианта округления и все они дают недопустимые наборы, то есть ограничения не выполняются.

Истинное решение:

1)Задачи с неделимостями

2)Экстремальные комбинаторные задачи

3)Задачи на несвязных и на невыпуклых областях

4)Задачи с разрывными целевыми функциями

Используются для описания практических задач, в которых представляют физически неделимые предметы.

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

Пусть имеется m-производственных факторов (сырье, материалы и т.д.), используя которые можно выпускать n-видов конечной продукции.

Введем обозначения:

– прибыль от единицы j-того продукта

– объем выпуска j-того продукта

– количество i-того производственного фактора, необходимое для производства единицы j-того продукта

– наличные ресурсы i-того производственного фактора

Определить производственную программу, обеспечивающую максимум суммарной прибыли и не выходящую за пределы данных ресурсов.

Математическая модель имеет следующий вид:

Задача о ранце (рюкзаке)

Пусть имеется n-предметов. Заданы величины:

– вес j-того предмета

– ценность j-того предмета

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

Введем переменную , которая принимает значения:

Обобщим задачи. Возможны ограничения не только по весу, но и по объему и т.д., то есть возможны m-ограничений. Можно взять более одного предмета данного класса.