ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Особый класс задач с неделимостями составляют целочисленные ТЗ, в которых целочисленные решения обеспечиваются при целочисленности исходных данных.
Переход от задач с дискретными переменными к целочисленным задачам
1. Изменение масштаба. 2. Преобразование системы ограничений: а) пусть Введем бинарную переменную yij, принимающую значения 0, 1. , при условиях . То есть мы перешли от произвольных дискретных переменных к бинарным.
б) аналогично можно преобразовать задачу целочисленного программирования в задачу с бинарными переменными, если . Поэтому в дальнейшем будем рассматривать задачи с целочисленными переменными.
- задачи с альтернативными переменными (или с логическими условиями). В этих задачах вводятся искусственные альтернативные переменные, отражающие логические условия задачи. Это задачи с дополнительными логическими условиями (“или-или”, “если, то”).
Наиболее распространенными являются задачи целочисленного программирования, так как любую дискретную задачу можно привести к целочисленной.
Прикладные дискретные модели Задача о раскрое. Для изготовления заготовок D1,…,Dm имеется n способов раскроя материала A1,…,An. -количество заготовок i-го типа, получаемых из единицы материала при способе Aj. Имеется D единиц материала. При раскрое единицы материала по способу Aj имеются отходы площадью . Надо произвести не менее заготовок i-го типа и выполнить план с минимизацией отходов. Таблица 11
Пусть - количество единиц материала, раскраиваемого по j-му способу. Математическая модель задачи запишется следующим образом: ; .
Задача о ранце. Имеются предметы n видов, для каждого предмета j-го вида (j=1,n) известны его объем и стоимость . Необходимо определить такой набор предметов, суммарный объем которых не превышал бы заданного числа b, а суммарная ценность была бы максимальной. Эта задача интерпретируется как задача загрузки ранца объема b и называется одномерной задачей о ранце. Введем целочисленные переменные , значения которых характеризует количество предметов j-го вида, помещенных в ранец. Тогда математическая модель данной задачи имеет вид:
Если ограничениями могут быть не только объем ранца, но и другие его характеристики , то получим многомерную задачу о ранце. В случае, если количество предметов j-го вида ограничено и равно , к задаче добавляется ограничение . Если =1, то получим задачу о ранце с булевыми переменными. Тогда , причем , если j-й предмет помещен в ранец, в противном случае. К задаче о ранце сводится широкий класс задач дискретной оптимизации с ограниченными ресурсами. Пример. Для оценки работоспособности систем перед их эксплуатацией производится проверка их функционирования. При проверке контролируются отдельные параметры системы, каждый из которых характеризуется вероятностью отказа проверяемых элементов и временем контроля . Так как допустимое время контроля всей системы T ограничено, то для проверки необходимо выбрать параметры, контролирующие наиболее ненадежные элементы и требующие для контроля наименьшего времени. Пусть n – общее количество параметров. Введем альтернативные булевы переменные: Тогда математическую модель задачи можно сформулировать как одномерную задачу о ранце:
Не нашли, что искали? Воспользуйтесь поиском:
|