Проблема целочисленности

УЧЕБНЫЕ ВОПРОСЫ И РАСЧЕТ ВРЕМЕНИ

УЧЕБНЫЕ И ВОСПИТАТЕЛЬНЫЕ ЦЕЛИ

Занятие № 15. Задачи целочисленного программирования.

Тема № 4. Целочисленные задачи ТПР.

Теория принятия решений

По учебной дисциплине

ЛЕКЦИЯ

Обсуждено на заседании кафедры

"___" августа 2011 г.

Протокол № 1

1. Рассмотреть проблему целочисленности в целом.

2. Изучить алгоритм метода отсечений.

3.. Воспитывать творческий подход и настойчивость при изучении дисциплины

Время: 2 часа. Место: Аудитория.

МАТЕРИАЛЬНОЕ ОБЕСПЕЧЕНИЕ:

Литература : Орлов А.И. Теория принятия решений. Учебник. М., «Экзамен», 2006.

Наглядные пособия: дидактический материал (слайды).

Технические средства обучения: “Лектор–2000”.

I.	Введение		мин.
II.	Учебные вопросы
	1. Проблема целочисленности.		мин.
	2. Примеры ЗЦЛП.		мин.
	3. Задача о назначениях. Венгерский алгоритм		мин.
III.	Заключение		мин.

ВВЕДЕНИЕ

Проверить наличие студентов и их готовность к занятию.

Объявить студентам о том, что они начинают изучение новой темы «Целочисленные задачи ТПР», играющей важнейшую роль в понимании сущности дисциплины. Довести до студентов, что данная тема включает 8 часов аудиторных занятий, из которых 4 часа лекций, 2 часа практических занятий и 2 часа лабораторных работ.

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИЗЛОЖЕНИЮ УЧЕБНЫХ ВОПРОСОВ

При изложении первого вопроса рассмотреть основные категории целочисленных задач. Изложение учебного материала проводится с элементами диалогового метода, при этом студентам задается следующий вопрос: ´ В чем состоит проблема при решении целочисленных задач?

При изложении второго вопроса рассмотреть примеры ЗЦЛП. Изложение учебного материала проводится с элементами диалогового метода, при этом студентам задается следующий вопрос: ´ Какая задача носит условное название задачи «о назначениях»?

При изложении третьего вопроса изучить алгоритм метода отсечений. Изложение учебного материала проводится с элементами диалогового метода, при этом студентам задается следующий вопрос: ´ Что происходит на каждой итерации данного метода?

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

Характерные источники целочисленности (дискретности):

1. неделимость объектов, представляемых переменными (например, x – число рабочих или отправляемых вагонов);

2. вариантность типа “да-нет” (например, включать или нет данный пакет в портфель ценных бумаг);

3. заданность возможных значений нормативными документами (например, сечения проводов, диаметров труб, размеров профилей и т.п.);

4. комбинаторность (например, размещение объектов, порядок обхода объектов, упорядочение);

5. логические условия (например, фиксированные затраты имеют место только при производстве продукции).

Различают задачи полностью целочисленные/дискретные и частично целочисленные (смешанные). В последних требование целочисленности накладывается не на все переменные.

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

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

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

Можно, конечно, пренебречь требованием целочисленности и использовать один из методов ЛП, но тогда, за редким исключением, результат не будет целочисленным. Округление дробных значений переменных проблематично. Действительно, так как оптимальное решение непрерывной задачи лежит в вершине допустимого множества, округление может привести к недопустимости. При двух дробных переменных имеется 4, а при n переменных – 2 ⁿ вариантов округления! Какие из них дают допустимые решения, можно определить только после проверки всех ограничений. При этом следует иметь в виду, что, во-первых, целочисленная задача может оказаться неразрешимой несмотря на разрешимость непрерывной задачи; во-вторых, допустимость округленного решения еще не означает его оптимальность. Проиллюстрируем последний тезис известной задачей о садовнике.

Дата добавления: 2014-01-11