Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Топ:
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Интересное:
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2017-05-16 | 421 |
5.00
из
|
Заказать работу |
|
|
Переход от задач с дискретными переменными к целочисленным задачам
1. Изменение масштаба.
2. Преобразование системы ограничений:
а) пусть
Введем бинарную переменную yij, принимающую значения 0, 1.
, при условиях
.
То есть мы перешли от произвольных дискретных переменных к бинарным.
б) аналогично можно преобразовать задачу целочисленного программирования в задачу с бинарными переменными, если .
Поэтому в дальнейшем будем рассматривать задачи с целочисленными переменными.
- задачи с альтернативными переменными (или с логическими условиями). В этих задачах вводятся искусственные альтернативные переменные, отражающие логические условия задачи. Это задачи с дополнительными логическими условиями (“или-или”, “если, то”).
Наиболее распространенными являются задачи целочисленного программирования, так как любую дискретную задачу можно привести к целочисленной.
Прикладные дискретные модели
Задача о раскрое.
Для изготовления заготовок D1,…,Dm имеется n способов раскроя материала A1,…,An. -количество заготовок i-го типа, получаемых из единицы материала при способе Aj. Имеется D единиц материала. При раскрое единицы материала по способу Aj имеются отходы площадью . Надо произвести не менее заготовок i-го типа и выполнить план с минимизацией отходов.
Таблица 11
Виды заготовок | Способы раскроя | План производства | |||
A1 | A2 | … | An | ||
D1 D2 … Dm | A11 a21 ... am1 | a12 a22 ... am2 | ............ | a1n a2 n... amn | b1 b2 ... bm |
Отходы | C1 | c2 | … | cn |
Пусть - количество единиц материала, раскраиваемого по j-му способу.
Математическая модель задачи запишется следующим образом:
;
.
Задача о ранце. Имеются предметы n видов, для каждого предмета j-го вида (j=1,n) известны его объем и стоимость . Необходимо определить такой набор предметов, суммарный объем которых не превышал бы заданного числа b, а суммарная ценность была бы максимальной. Эта задача интерпретируется как задача загрузки ранца объема b и называется одномерной задачей о ранце.
|
Введем целочисленные переменные , значения которых характеризует количество предметов j-го вида, помещенных в ранец. Тогда математическая модель данной задачи имеет вид:
Если ограничениями могут быть не только объем ранца, но и другие его характеристики , то получим многомерную задачу о ранце.
В случае, если количество предметов j-го вида ограничено и равно , к задаче добавляется ограничение . Если =1, то получим задачу о ранце с булевыми переменными. Тогда , причем , если j-й предмет помещен в ранец, в противном случае.
К задаче о ранце сводится широкий класс задач дискретной оптимизации с ограниченными ресурсами.
Пример. Для оценки работоспособности систем перед их эксплуатацией производится проверка их функционирования. При проверке контролируются отдельные параметры системы, каждый из которых характеризуется вероятностью отказа проверяемых элементов и временем контроля . Так как допустимое время контроля всей системы T ограничено, то для проверки необходимо выбрать параметры, контролирующие наиболее ненадежные элементы и требующие для контроля наименьшего времени.
Пусть n – общее количество параметров. Введем альтернативные булевы переменные:
Тогда математическую модель задачи можно сформулировать как одномерную задачу о ранце:
Задача о назначениях.
Линейная задача о назначениях.
Имеется n исполнителей и n видов работ, которые они могут выполнять. Пусть - производительность i-го исполнителя при выполнении j работы. Каждый исполнитель может выполнять один вид работ, а каждый вид работ может быть выполнен одним исполнителем. Требуется таким образом распределить исполнителей по видам работ, чтобы общая производительность была максимальной.
|
Введем альтернативные переменные :
Тогда математическая модель задачи имеет вид:
Иногда задача о назначениях формулируется как задача минимизации, если в качестве выбирается время, затраченное i-м исполнителем на выполнение j-й работы.
Необходимо заметить, что условие целочисленности переменных в задаче о назначениях можно не накладывать, т.к. эта задача является частным случаем транспортной задачи и при целочисленности правых частей ограничений целочисленность решения обеспечивается автоматически.
К задаче о назначениях сводится широкий круг задач дискретной оптимизации (распределение исполнителей по видам работ, закрепление за станками операций, распределение задач между различными ЭВМ, назначение претендентов на вакантные должности при формировании штатного расписания и т.д).
Пример. При передаче сообщений по каналу с шумом необходимо каждой букве передаваемого алфавита поставить в соответствие букву принимаемого таким образом, чтобы сумма вероятностей правильности принимаемых букв была бы максимальна.
Пусть - вероятность соответствия принимаемой j-й буквы передаваемой i-й букве. Введем альтернативные переменные:
Тогда математическая модель задачи будет иметь следующий вид:
Квадратичная задача о назначениях.
Имеется m пунктов, в которых необходимо разместить n объектов. В каждом пункте может быть размещен только один объект. Даны расстояния между i-м и j-м пунктами , а также csk – показатели, характеризующие взаимосвязи между s-м и k-м объектами (стоимость перевозок, число коммукникаций и т.д.). Необходимо определить такое назначение объектов в выделенные пункты, чтобы минимизировать соответствующие затраты.
Математическая модель задачи имеет следующий вид:
В данном случае целевая функция зависит не от всевозможных назначений, а от всевозможных пар назначений (s-й элемент размещается в i-й пункт, а k-й – в j-й пункт). Целевая функция при этом не является линейной.
Квадратичная задача о назначениях имеет широкий круг практических приложений. Она может быть использована для решения задач размещения (оборудования, предприятий, деталей, и т.д.). Особенно часто эта модель используется в задачах конструкторско-топологического проектирования.
|
Пример. Необходимо таким образом разместить n компонентов печатной платы на m позициях монтажного пространства, чтобы суммарная длина электрических соединений между компонентами была бы минимальной.
Предположим, что n=m. Пусть - расстояние между k-й и s-й позициями, - число связей между i-м и j-м компонентами. Введем бинарные переменные
.
Задача коммивояжера
Имеются n пунктов или городов с заданными расстояниями между i-м и j-м пунктами. Необходимо составить оптимальный маршрут из условия минимизации суммарного расстояния для коммивояжера, выходящего из пункта с номером 1, который должен побывать во всех пунктах ровно по одному разу и вернуться в исходный пункт.
Введем альтернативные бинарные переменные:
.
Условия минимизации общего расстояния, а также прибытия в каждый пункт и выезда из него ровно по одному разу могут быть выражены следующим образом:
.
Однако необходимо обеспечить непрерывность маршрута, чтобы набор звеньев, входящих в маршрут, образовывал единую цепочку (например, при n=8 цепочка (1,2) - (2,6) - (6,4) - (4,8) - (8,5) - (5,3) - (3,7) - (7,1)), а не состоял бы из отдельных не связанных цепочек (например, (1,2) - (2,6) - (6,1) и (3,8) - (8,7) - (7,5) - (5,4) - (4,3)). Для устранения замкнутых циклов (подобходов), включающих количество вершин меньшее n, в модель вводятся n дополнительные переменных ui³0 () и n2 дополнительных ограничений:
.
Действительно, пусть маршрут включает несколько цепочек. Тогда существует цепочка, начинающаяся и заканчивающаяся в начальном пункте, но включающая n1 звеньев, где n1<n. Просуммировав эти неравенства вдоль такой цепочки (т.е. при xik=1), получим бессмысленное неравенство n1(n-1)£n1(n-2) (все ui и uj при суммировании взаимно уничтожаются). Покажем теперь, что для маршрута, исключающего подобходы, это неравенство выполняется, т.е., можно найти значения ui, удовлетворяющие дополнительным ограничениям. Положим ui=p, если город i посещается коммивояжером на p-м шаге, p= . Отсюда следует, что . Таким образом, ограничения выполняются для всех . При эти ограничения превращаются в равенства
|
.
Задача коммивояжера имеет широкий круг практических приложений. К ней сводятся задачи оптимальной маршрутизации (выбор маршрутов перевозки грузов, маршрутов движения транспорта, минимизация расстояния, проходимого исполнительным механизмом станка с ЧПУ и т.д.), задачи проектирования электрических и вычислительных сетей, задачи определения последовательности обработки деталей на станках с условием минимизации времени переналадок и т.д.
Пример 11. Пусть необходимо проложить коммуникации между n различными ЭВМ таким образом, чтобы каждая ЭВМ была связана с двумя соседними, вся сеть была бы подключена к центральной ЭВМ, а суммарная длина коммуникаций была бы минимальна.. Заданы расстояния dij между i-й и j-й ЭВМ.
Данная задача формализуется в виде задачи коммивояжера следующим образом:
;
.
При этом xij=1, если i-я и j-я ЭВМ соединяются.
Задача о покрытии
Пусть имеется n предметов, каждый из которых обладает некоторым числом признаков из заданного множества m признаков, а в совокупности эти n предметов обладают всеми m признаками. Необходимо выбрать минимальное число предметов, которые в совокупности обладали бы m признаками. Условия задачи задаются матрицей A с элементами
Введем бинарные переменные:
.
Тогда математическая модель задачи имеет следующий вид:
Каждое i-е ограничение в данном случае показывает, что должен быть выбран хотя бы один предмет, обладающий i-м признаком.
Если каждому j-му предмету приписывается вес , может быть сформулирована взвешенная задача о покрытии:
Если каждому i-му признаку приписывается натуральное число и требуется найти минимальное число таких предметов, что i-м признаком обладает не менее предметов из указанного набора, получаем задачу о кратном покрытии:
Задача о разбиении. Задача о разбиении аналогична задачи о покрытии с тем отличием, что признаки у различных предметов не должны совпадать:
Задача о взвешенном разбиении формулируется следующим образом:
К задаче о покрытии сводится широкий круг задач информационного поиска, синтеза логических схем, задачи разбиения электронных схем на модули и покрытия схем типовыми ячейками и т.д.
Пример. Пусть некоторое количество информации хранится в n массивах (файлах) длины , причем на каждую единицу информации отводится по крайней мере один массив. Задана матрица T с элементами
Получена заявка на m типов единиц информации. Необходимо определить подмножество массивов минимальной длины, необходимых для удовлетворения заявки.
Введем бинарные переменные:
.
Тогда математическая модель задачи формализуется в виде задачи о покрытии:
|
|
|
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!