Загрузка...

Задачи исследования операций с целочисленными переменными. Общая характеристика задач.


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

Эти задачи являются частным случаем дискретного программирования. ЗЛЦП бывают двух типов:1)задачи с не делимостями 2) задачи выбора варианта или экстремальные комбинаторные задачи.

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

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

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

Модели целочисленных задач исследования операций.

1.Задачи, сводящиеся к целочисленности. Такой задачей является транспортная задача.

2.Задача о ранце. Для перевозки m-видов неделимых предметов используется m-видов транспортных средств – ресурсов заданных в количестве clip_image002

Известны стоимость clip_image004 одного предмета вида j, а также расход i-го ресурса необходимого для транспортировки одного предмета вида j это clip_image006

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

Обозначим через clip_image008 количество перевезённых предметов вида j. clip_image010 clip_image012 clip_image014 это задача с не делимостями.

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

clip_image0161-если переменная j выбирается для транспортировки, 0- в противном случае.

clip_image012[1] clip_image019

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

Имеется n работ и n исполнителей. Известны затраты № на выполнение i-м исполнителем j-й работы №

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

Введем переменные clip_image021

1-если i-й исполнитель направлен на работу, 0 –в противном случае.

clip_image023

clip_image025

В этой задаче условие (1’) можно заменить на clip_image027 и получить мат модель транспортной задачи, в которой запасы clip_image029 и потребностиclip_image031.

Загрузка...