Материал: Основы математического моделирования. курс лекций. Перова А.В

При решении практических задач довольно часто могут возникать логические цепочки. EXCEL допускает применение функции ЕСЛИ в цепочке до 7 раз.

Аналогично можно вводить условные ограничения. Условные исходные данные для левых частей (ЛЧ) ограничений вводятся в формате :

=ЕСЛИ (условие; адрес ЛЧ1; адрес ЛЧ2), для правых частей (ПЧ) ограничений формат ввода

аналогичен предыдущему, только вместо ЛЧ1 и ЛЧ2 записываются ПЧ1и ПЧ2.

В одной и той же задаче условия для целевой функции, левых и правых частей ограничений могут вводиться одновременно.

ЛЕКЦИЯ 10 ПРИКЛАДНЫЕ ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО

ПРОГРАММИРОВАНИЯ

Задачей целочисленного линейного программирования

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

ленной, иначе – частично целочисленной. Если множество до-

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

Задача о раскрое.

Для изготовления заготовок D1,…,Dm имеется n способов раскроя материала A1,…,An. aij -количество заготовок i-го

типа, получаемых из единицы материала при способе Aj. Имеется D единиц материала. При раскрое единицы материала по способу Aj имеются отходы площадью Cj . Надо произвести не

105

менее bi заготовок i-го типа и выполнить план с минимизаци-

ей отходов.

Пустьxj - количество единиц материала, раскраиваемого

по j-му способу.

Математическая модель задачи запишется следующим образом:

xj D;

j1

xj 0, j 1,n,xj целые.

Задача о ранце. Имеются предметы n видов, для каждого предмета j-го вида (j=1,n) известны его объем a j 0 и сто-

имость cj 0. Необходимо определить такой набор предме-

тов, суммарный объем которых не превышал бы заданного числа b, а суммарная ценность была бы максимальной. Эта задача интерпретируется как задача загрузки ранца объема b и

называется одномерной задачей о ранце.

Введем целочисленные переменные x j(j 1,n), зна-

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

106

помещенных в ранец. Тогда математическая модель данной задачи имеет вид:

n

C jx j max ;

j 1

n

a jx j b;

j 1

x j 0, x j - целое .

Если ограничениями могут быть не только объем ранца, но и другие его характеристики bi , то получим многомерную задачу о ранце.

n

C j xj max ;

j1 n

aij xj bi ,i 1,m;

j 1

xj 0, xj - целое.

В случае, если количество предметов j-го вида ограничено и равно dj, к задаче добавляется ограничение x j dj.

Если dj=1, то получим задачу о ранце с булевыми перемен-

ными. Тогда x j {0,1}, причем xj 1, если j-й предмет по-

мещен в ранец, xj 0 в противном случае.

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

Пример 1. Для оценки работоспособности систем перед их эксплуатацией производится проверка их функционирования. При проверке контролируются отдельные параметры системы, каждый из которых характеризуется вероятностью отказа проверяемых элементов qj и временем контроля t j. Так

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

107

Пусть n – общее количество параметров. Введем альтернативные булевы переменные:

Задача о назначениях. Линейная задача о назначениях .

Имеется n исполнителей и n видов работ, которые они могут выполнять. ПустьCij - производительность i-го испол-

нителя при выполнении j работы. Каждый исполнитель может выполнять один вид работ, а каждый вид работ может быть выполнен одним исполнителем. Требуется таким образом распределить исполнителей по видам работ, чтобы общая производительность была максимальной.

Введем альтернативные переменные xij:

Тогда математическая модель задачи имеет вид:

108

n n

Cij xij max;

xij {0,1}.

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

ное i-м исполнителем на выполнение j-й работы. Необходимо заметить, что условие целочисленности

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

К задаче о назначениях сводится широкий круг задач дискретной оптимизации (распределение исполнителей по видам работ, закрепление за станками операций, распределение задач между различными ЭВМ, назначение претендентов на вакантные должности при формировании штатного расписания и т.д).

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

Пусть pij- вероятность соответствия принимаемой j-й

буквы передаваемой i-й букве. Введем альтернативные переменные:

109